본 글의 내용은 Operating Systems: Three Easy Pieces의 Semaphores 챕터를 정리한 것입니다.

☑️ 개요

• 동시성 문제를 해결하려면 condition variable과 lock모두 필요하다.

• 다익스트라는 synchronization primitive로 세마포어를 도입했는데, 세마포어는 lock인 동시에 condition variable로 사용될 수 있다.

☑️ 정의

• 세마포어는 int 값을 갖는 객체로, sem_wait 와 sem_post 두 가지 루틴으로 조작 가능하다.

• sem_wait 는 P() , sem_post 는 V() 라고 역사적으로 불렸다.

(세마포어 초기화 코드)

• 세마포어는 초기값에 따라 동작이 달라지므로, 초기화가 필요하다.

• sem_init 의 두번째 파라미터가 0이면 같은 프로세스 내의 스레드 간에 공유함을 의미하고, 세번째 파라미터는 세마포어의 초기값이 된다.

• sem_wait는 변수 s의 값을 1 감소시키고, s가 음수가 되면 대기한다.

• sem_post는 변수 s의 값을 1 증가시키고, 하나 이상의 스레드가 대기중이면 스레드를 깨운다.

• 세마포어의 int 값은 사실상 대기중인 스레드의 수와 같다.

(세마포어 사용 예시 코드)

☑️ 이진 세마포어

• 세마포어의 초기값으로는 어떤 값이 설정되어야 할까?

  • 보통 critical section에는 하나의 스레드만 진입해야 되기 때문에, 1이 되어야 한다.

  • 스레드 A, B가 있다고 가정하면, 먼저 진입한 스레드가 int 값을 0으로 만들고, 후진입한 스레드가 int 값을 음수로 만들며 해당 값이 다시 0이 될때까지 대기한다.

• 이렇게 값을 1로 설정한 세마포어를 lock으로 활용할 수 있다.
  

• Lock은 두가지 상태(보유 혹은 미보유)만 존재하기 때문에, lock으로 사용하는 세마포어를 이진 세마포어라고 부르기도 한다.

☑️ 세마포어로 순서 만들기

• 세마포어는 이벤트의 순서를 정할 때도 유용하다.

• sem_wait 로 대기 중이던 스레드를 다른 스레드가 작업 처리 후 깨울 수가 있다.

• 그래서 세마포어를 ordering primitive로서도 사용한다. (condition variable과 유사하다.)
  

• 예시로 부모 스레드가 자식 스레드를 기다릴 때, 부모는 sem_wait 를 호출하고 자식은 sem_post 를 실행하면 된다.

  • 여기서 세마포어의 값은 당연히 0으로 시작해야 한다.

  • 부모가 먼저 sem_wait 를 하든 자식이 sem_post 를 하든 0으로 설정하면 세마포어의 값은 목표하는 대로 수정된다. (0 → -1 → 0) 혹은 (1 → 0)

☑️ 생산자/소비자 (Bounded Buffer) 문제

• 조건 변수에서 언급되었던 생산자/소비자 문제를 세마포어로도 다룰 수 있다.

🔎 문제 접근

생산자와 소비자. 두 스레드가 존재할 때,

• 소비자가 먼저 실행된다면? 먼저 sem_wait 를 호출하고 full 을 -1로 만든다. 음수가 됐으므로 sem_post(&full)이 호출되기를 기다릴 것이다.

• 이후 생산자가 실행된다면 empty 를 파라미터로 sem_wait 를 호출하는데, empty 는 위 코드에서 MAX(=1)로 초기화됐기 때문에 0으로 변하며, 생산자는 대기하지 않고 코드를 진행한다.

• 그러므로 sem_post 가 full 에 이어서 호출되고, 소비자를 깨운다.

• 만약 생산자가 먼저 실행된다면? 생산자가 한 바퀴를 돌고 sem_wait 에서 대기할 것이다. 하지만 소비자가 다시 생산자를 깨우면서 정상적으로 진행된다.

생산자-소비자가 여러명일 때 (empty 의 초기값인 MAX가 1보다 클 때)

• 생산자 여러 명이 먼저 시작한다고 가정해보자.

• 생산자 1이 put을 호출하여 6번째 줄을 작업하는 동안, interrupt가 발생하여 생산자 2가 6번째 줄을 작업했다고 해보자.

• 그럼 이전 데이터를 덮어씌우게 되고, 사실상 생산자1의 데이터는 유실된다.

• 따라서 기존의 1대1 방식과 달리 올바르게 작동하지 못한다.

🔎 Mutual exclusion 추가

• 위 예시처럼 버퍼를 채우고 인덱스를 증가시키거나 하는 핵심 로직은 주의해서 값을 변경해야 한다.

• 위 코드는 세마포어로 mutual exclusion을 제공한다. 그런데 이제 또 다른 문제가 발생하는데, 바로 Deadlock(교착 상태)이 발생한다.

🔎 Deadlock 회피

• 위 예시에서 왜 Deadlock이 발생했을까? 소비자 스레드부터 실행됐다고 가정해보자.

• sem_wait(mutex) 이후, set_wait(full)을 실행하고 생산자를 기다릴 것이다.

• 이제 생산자는 set_wait(mutex)부터 호출한다. 그런데 당연하게도 소비자 쪽에서 lock을 가지고 있기 때문에 더이상 나아갈 수 없다. 그리고 무한히 대기한다.

• 이 문제를 해결하기 위해서는 mutex로 사용하는 세마포어를 put과 get, 즉 critical section에 조금 더 가까운 위치에서 호출해야 된다.

☑️ Reader-Writer Lock

• 어떤 데이터 구조에 접근할 때, 삽입이나 조회가 발생할 수 있을 것이다.

• 만약 조회를 할 때 데이터가 변경되지 않는 것을 보장할 수 있다면, 동시 다발적으로 조회할 수 있도록 허용할 수 있다.

• 이런 경우에 Reader-Writer lock을 사용하게 된다.

• 사용은 매우 간단한데, 데이터에 write 하려면 acquire_writelock 을, 갱신 후 잠금을 해제하려면 release_writelock 을 호출하면 된다.

• writelock 을 얻으려는 시도는 reader가 존재하면 미뤄진다.

• 그런데 reader가 존재할 때 write를 미룬다는 단순한 방식은 Writer에게 starvation을 야기할 수 있다.

• 이것을 고려한 대책이 필요하며, 너무 정교한 구현은 너무 많은 오버헤드를 만들 수 있으므로 주의가 필요하다.

☑️ 식사하는 철학자 문제

• 다익스트라가 제시한 유명한 동시성 문제이다.

• 원형 테이블에 둘러앉은 철학자들이 단순히 생각을 하거나, 양쪽 포크를 들고 식사를 한다.

• 이때 굶는 철학자는 없어야 하며, 동시다발적으로 잘 먹어야 된다.

🔎 틀린 접근

• 우선 왼쪽 포크에 lock을 채우고, 채워지면 오른쪽에 lock을 채우면 된다는 생각을 해볼 수도 있다. 그리고 다 먹으면 둘 다 unlock하면 된다.

• 이런 발상은 deadlock을 회피하지 못한다. 만약 철학자들이 왼쪽 포크를 집어들면 오른쪽 포크는 옆자리 철학자의 왼쪽 포크이므로, 모두 다 오른쪽 포크를 기다리게 된다.

🔎 솔루션: 의존성 제거

• 이것을 해결하기 위해 생각보다 단순한 접근이 가능한데, 한 철학자가 포크를 오른쪽부터 집어들게 되면 deadlock을 회피할 수 있게 된다.

☑️ 스레드 스로틀링

• 세마포어 사용 사례 중 또 하나는 스레드 스로틀링이다.

• 너무 많은 스레드가 일을 하여 시스템을 마비시킬 수도 있기 때문에, 특정 critical section에 세마포어로 임계값을 설정한다.

• 많은 양의 메모리를 확보해야 되는 코드 영역이 있다고 해보자.

• 수많은 스레드가 해당 영역에 접근하면 일이 다 처리되기도 전에 메모리가 부족해지며, thrashing(메모리 확보를 위해 페이징을 더 많이 하며 정작 작업은 제대로 못하는 것)이 발생하여 작업이 느려진다.

• 세마포어의 값을 진입 스레드 임계 값으로 설정하는 것으로 스레드 스로틀링을 실현할 수 있다.

✅ 요약

• 세마포어는 condition variable과 lock의 역할을 모두 할 수 있는 존재이다.

• 세마포어의 값을 1로 초기화해두고 lock처럼 사용하면 이진 세마포어라고도 부른다.

• 세마포어로 reader-writer lock, 스레드 스로틀링 등을 실현시킬 수 있으며, 이때 세마포어에 설정하는 초기값에 따라 다양한 용도로 활용 가능하다.