[Synchronization] Semaphore

💡Semaphore란

 

✅sem_init(&m, 0, X)

X: semaphore의 초기값

  0이면 Condition variable, 1이면 Mutex로 이용하게 됨.

 

✅sem_wait(&m)

semaphore값을 1 뺀 뒤,

semaphore < 0이면 wait / 그 외엔 바로 return

 

✅sem_post(&m)

semaphore값을 1 더한 뒤,

waiting하는 스레드가 존재하면, 하나를 깨움

 

 

💡Mutex로 쓰이는 예시

 

 

 

💡Condition variable로 쓰이는 예시 - Ordering: a parent waiting for its child

 

 

이같은 구현은 어떤 경우에서든 잘 돌아간다.

 

Case 1: parent의 sem_wait()까지 다행히 interrupt가 없는 경우 -> 잘 작동됨

 

Case 2: parent가 sem_wait()하기도 전에 interrupt에 의해 child가 실행되는 경우 -> 이것도 잘 작동됨

 

💡Producer/consumer (bounded-buffer) problem

 

i) first attempt

 

 

✅문제점: race condition 발생

 

MAX = 10이라고 가정하자.

 

어느날 Pa가 put()을 호출했다 하자. 그럼 Pa는 정상적으로는 line F1에서 buffer의 첫 entry를 채운 뒤, line F2에서 "fill"을 1로 증가시켜야 한다.

🚩

그런데 만약 Pa의 put() 바로 직후 우연히 Pb도 put()을 호출했었다면, 

Pa의 line F1 수행 ~ line F2 수행 사이에 Pa에게 interrupt가 발생해서 Pb가 실행되기 시작하여, Pb 역시 line F1에서 buffer의 첫 entry를 채우는 불상사가 일어날 수 있다.

이미 Pa가 채워놓은 자리에 Pb가 다시 채워버림으로써 Overwrite가 발생하는 것이다!

 

buffer와 index도 엄연히 critical section인데 보호받지 못하고 있는 것이 원인이라 할 수 있다.

 

🚩

ii) adding mutex

put(), get() 전후로 lock을 걸었다 푼다.

 

 

✅문제점: deadlock 발생

 

어느날 두 스레드 C와 P가 있었다.

 

C가 먼저 실행됐다 하자. 그럼 C는 우선 line C0에서 mutex를 얻은 뒤 line C1에서 sem_wait()을 호출한다. 

이때, 아직 produce된 data가 없으니 C는 sleep하며 CPU를 넘겨줄 것이다.

 

한편 P도 실행되기 시작하여 line P0가 수행된다.

🚩

이제서야 문제를 깨닫는다!: 이런, C가 mutex를 지닌 채로 sleep하고 있잖아..

P는 mutex가 없으니, 어쩔 수 없이 P도 sleep해야 한다.

 

즉, C와 P 둘다 잠들어버린 것이다. 

이들은 영원히 깰 수 없다. 왜냐하면, P가 만드는 signal인 "full"만이 C를 깨울 수 있는데, 

일단 C가 일어나서 mutex부터 넘겨줘야 P가 signal을 보내든 말든 할 수 있기 때문이다. 

 

 

iii) avoiding deadlock (real solution)

🚩

lock을 걸었다 푸는 범위를 좁힌다.

"empty"나 "full" signal을 wait, post하는 부분보다 안쪽에 놓는 것이다. 

 

 

 

💡Dining Philosophers problem

5명의 철학자 (P0 ~ P4)와 5개의 포크 (f0 ~ f4)가 있다.

철학자는 두 가지 행위를 할 수 있다: think(포크 안 필요함), eat(왼쪽과 오른쪽 포크 필요함) 

 

 

각 철학자는 아래와 같은  loop를 돈다.

getforks()와 putforks()는 포크를 위한 semaphore를 구현하기 위한 것이다.

 

 

또한, 아래 함수를 통해 양쪽 포크를 참조해온다.

 

 

그럼, getforks()와 putforks()는 어떻게 구현할까? 

여기서 중요하게 고려할 점이 있다: deadlock과 starvation을 일으키지 않아야 한다!!

 

구현 i) 모든 P는 get할 때건, put할 때건 왼쪽 다음 오른쪽 포크를 참조하는 방식

※ forks: sem_t forks[5];로써 생성된, 각 포크를 위한 semaphore이다.

 

 

✅문제점: deadlock 발생

 

만약 모든 P가 자신의 왼쪽 포크를 가져갔다 치자.

그럼 모든 P는 이제 자신의 오른쪽 포크를 가지려 할 것이다.

🚩

문제는, 현재 모든 포크는 자신의 오른쪽 P에게 이미 소유되었으므로,

어떤 P도 오른쪽 포크를 가질 수 없다는 것이다.

즉 모든 P는 포크를 못 챙겨서 eat을 못하고 기다리고만 있으며, 이 기다림은 끝날 수가 없다.

 

🚩

구현 ii) 한 P (eg. P4)만 get이나 put을 하는 순서를 오른쪽 다음 왼쪽으로 바꾼다.

이 방식에서는 deadlock과 starvation이 발생하지 않는다.