10. Semaphore

Conditional variable은 queue에 park하고 unpark를 기다리는 것이었다. 즉, state가 없다. CV에 state를 넣어서 관리하려고 만든 것이 semaphore이다. 동작은 간단하다.

• Wait
  • sem > 0 이면. semaphore의 값을 1 감소시키고 lock을 acquire한다. 
  • sem < 0 이면, 대기한다. post()에 의해 sem 값이 0보다 커지면 깨어날 수 있다.
• Post: sem의 값을 1 증가시킨다. 그리고 waiter 하나를 깨운다.

위 동작은 atomic하게 구현되어 있다.

 

Conditional variable보다 동작이 간단해진다.

 

Semaphore = Lock + CV

Semaphore로 lock이나 CV처럼 사용할 수 있고, lock과 CV가 있으면 semaphore처럼 동작할 수 있다.

 

Lock from semaphore

Initialize stage에서 sem = 1로 할당하면, 1개의 thread가 lock을 잡을 수 있다. 

• sem = 1
• sem_wait() -> sem = 0, lock을 얻음
  (나머지 wait)
• sem_post() -> sem = 1, waiter 중 하나 깨우기
  • awaked thread -> sem_wait() : sem = 0, lock을 얻음

 

Conditional variable from semaphore

가능한데, 겁나 복잡함. [링크] 읽어보면 이해할 수 있음

 

Semaphore from lock + cv

구조체와 초기화는 다음처럼 진행한다.

 sem의 값을 따로 관리한다.

 

sem_wait(), sem_post()는 다음처럼 구현한다.

전반적인 동작은 conditional variable과 비슷하다. 대신 semaphore를 위해, lock을 얻을 경우, sem 값을 감소, lock을 release할 경우 sem 값을 증가한다.

 

검증을 위해 producer/consumer 문제에 대입해 본다.

 

Producer/consumer

Easy case

CV할 때처럼 2개의 semaphore를 사용한다. Producer를 위한 emptybuffer sem은 1로, consumer를 위한 fullbuffer sem은 0으로 설정한다. 

 

Easy case 2; circular buffer

N개의 element가 buffer에 먼저 저장되게 만들고 싶으면, emptybuffer의 sem 값을 N으로 설정하면 된다.

 

Multiple thread case

Producer와 consumer가 여러개이면, 위에서 봤던 코드는 동작하지 못한다. i와 j는 private하기 때문에 충돌이 발생할 수 있기 때문이다. 이를 해결하기 위해 코드를 다음처럼 변경해볼 수 있다.

Producer와 consumer는 각각 unique한 empty buffer, full buffer를 잡아 index를 얻는다. 그러나 이 코드 역시 myi, myj가 private하기 때문에, race condition이 발생할 수 있다. 따라서 mutual exclusion이 필요한 상황이다. Mutex를 사용하려면, 최대한 적은 영역을 잡아야 한다. 문제가 되는 친구가 index임으로 index 앞뒤로 mutex lock을 설정한다.

이와 같이 mutex를 설정할 경우, mutex에 의한 deadlock에 빠진다. Consumer부터 동작하면, lock을 절대 풀 수 없다.

 

Fill이나 Use를 mutex 안으로 넣을 수 있겠지만, 그렇게 될 경우 한번에 한개의 thread만 fill이나 use를 할 수 있게 된다. 대신 위 처럼 구현할 경우, unique buffer를 찾는 과정만 atomic하게 동작하기 때문에 여러 thread에서 동시에 buffer에 fill, use를 할 수 있게 된다.

 

Reader/writer lock

Multiple reader threads가 lock을 얻을 수 있으며, writer thread는 mutual exclusive하게 동작하는 것이 목표이다. Lock은 다음과 같이 구현한다.

lock을 1, writelock을 1로 설정했기 때문에, 한번에 하나의 reader, writer만 동작할 수 있다.

 

lock을 acquire, release하는 과정은 다음과 같다.

readlock의 경우 acquire 과정에서 reader==1이면, read하려는 thread가 자기자신 뿐임으로, writelock의 값을 0으로 바꿔 write가 발생하지 않도록 만든다. 또한 반대로 말하면, writer가 동작중이라면 reader는 대기하게 된다.

 

 Semaphores

• Semaphore = lock + conditional variable
• State (when init)
  • sem = 1: mutex
  • sem = 0: join (1개의 thread가 우선적으로 arrive해야 함)
  • sem = N: n개 thread가 동시에 사용 가능
• sem_wait(): sem>0, sem--, acquire sem / sem<0, wait
• sem_post(): sem++
• Producer/consumer, read/write lock에 사용 가능