[OS7] Synchronization Examples

Bounded-Buffer Probelm

이전에서 다뤘듯이 동기화가 이루어지지 않은 Bounded Buffer 에서는 두 가지 문제점이 존재한다.

1. ++, – 가 3개의 인스트럭션이므로 사이에서 인터럽트가 발생하면 문제가 발생할 수 있다.
2. CPU가 낭비되면서 기다리고 있다. (Busy wait)

위의 두 가지 문제를 Semaphore 를 사용해서 해결한 예시이다. shared data를 접근하는 부분에서 lock/unlock 을 사용해 mutual exclusive 를 보장한다. 또한 busy wait 을 없애기 위해서 empty/full semaphore 정의했다.

같은 문제를 mutex lock 과 condition variable 을 사용해서 해결한 예시이다. critical section 안에서 뭔가를 기다릴 때 사용하는 것이 condition variable이다. count==0 이면 모두 비어있으므로 wait을 해서 Consumer 가 waiting 상태로 간다. 이 때 mutex lock 도 unlock 된다. 이후 signal로 Consumer가 풀리면 다시 mutex lock이 설정된다. signal(not_full)에서 기다리는게 없으면 아무 동작 없이 지나간다. while(count == N) 인 이유는 여러 스레드가 동시에 진행되는 상황을 고려한 것이다. 두 개의 Consumer가 wait 상태에서 producer 하나가 실행되어 count = 1 일 때 한 번에 둘다 ready 상태가 되면 하나는 실행하고 하나는 다시 count =0 이므로 wait 해야하기 때문에 while 문을 사용했다.

Readers and Writers Problem

Readers and Writers Problem 은 read는 상관없이 읽어되지만 누군가 읽고 있다면 write 은 불가능하다. 또한 마찬가지로 누가 write 할 때는 read 도 불가능하다. 따라서 read 만 일어난다면 동시성을 높여 모든 스레드들이 하나의 데이터에 접근하도록 허용할 수 있다는 것이 이번 문제이다.

readcount 도 shared data 이므로 mutex lock 으로 보호해주는 모습이다. 또한 Wireter 가 wait 일 경우 readcount == 0 일때 다시 동작할 수 있다.

Dining-Philosopher Problem

다섯 명의 철학자가 원탁에 앉아 있고, 각자의 양옆에 젓가락이 하나씩 있다. 이때 철학자가 음식을 먹기 위해서는 양 옆의 젓가락을 동시에 들어야 한다.

가장 간단하게는 각 젓가락을 Lock/unlock 을 통해 관리하는 것이다. 하지만 이때 모든 철학자들이 자신의 왼쪽 젓가락을 든다면 모두 자신의 오른쪽 젓가락을 기다리고 있기 때문에 교착상태에 빠지게 된다. 이를 DeadLock 이라 한다.

데드락을 피하기 위해서는 양 옆의 젓가락을 하나씩 집는 것이 아니라 동시에 집으면 된다. 이는 젓가락 별로 semaphore를 쓰지말고 철학자별로 사용한다는 의미이다. 왼쪽과 오른쪽을 확인하고 모두 사용할 수 있으면 동시에 집는다. state 가 전역변수이므로 바꾸는 부분이 critical section이기에 보호해야한다.

하지만 이 알고리즘에서 1번이 먼저 밥을 먹고 2번이 밥을 먹으려 wait 일 때 3번이 밥을 먹기 시작하고 1번이 식사를 마친다면 2번은 계속해서 wait 해야한다. 이때 다시 1번과 3번이 번갈아가면서 식사를 하면 2번은 계속 식사하지 못하는 Starvation 문제가 발생한다. 이는 우선순위 aging 등으로 해결할 수 있다.

다음은 모니터를 사용한 예시이다. 모니터를 설정하면 펑션들에 들어갈 수 있는 스레드는 오직 하나이므로 알아서 mutex lock이 된다. 내부 펑션은 위에와 거의 똑같다. 젓가락 내려놓는 것을 기다릴때 condition variable 이용한다.