Initial Attempts to Solve Problem
프로그램적 해결법의 충족 조건
Algorithm 1
0번 프로세스는 turn이 0이 아니면 기다리고, 0이면 critical section을 처리하고 turn을 1로 만들어 1번 프로세스가 들어가게 해준다.
하지만 busy waiting이 발생한다.
Algorithm 2
flag는 들어가고자 하는 의중을 드러낸다.
만약 flag로 의중을 나타내자마자 cpu를 빼앗기고, 상대방도 flag를 들고 또 cpu를 빼앗기면 서로 끊임 없이 양보하는 상황이 발생한다.
Algorithm 3 (Peterson's Algorithm)
의중을 드러내고, 우선 턴을 상대방껄로 만들어 놓는다. 상대방이 들어가고자하고, 턴이 상대방 차례이면 기다린다.
여기서는 busy waiting이 발생한다.
Synchronization Hardware
hardware적으로 데이터를 읽는 것과 쓰는 것이 한번의 instruction으로 가능하다면 쉽게 문제가 해결 가능하다.
Semaphores
세마포어 자체는 추상자료형이다. 개발자가 매번 앞의 과정들을 하는 것은 불편하기 때문에 지원하는 것이다.
p 연산은 공유데이터를 획득하는 과정이고 v 연산은 반납하는 과정이다.
여기서 p 와 v는 atomic하게 접근 가능하다고 가정한다.
Critical Section of n Processes
이 방법을 쓰더라고 busy-wait은 피할 수 없다.
busy-wait을 피하려면 block & wakeup을 해야한다.
Block / Wakeup Implementation
만약 세마ㅣ포어를 획득할 수 없으면 프로세스를 block시키고, 누군가 쓰고 반납하면 block된것을 깨운다.
Implementation
자원을 내놓았는데도 불구하고 세마포어가 0이하면 block된 것들이 있다는 뜻이디 깨워준다.
Which is better?
보통은 block/wakeup이 훨씬 효율적이다. 하지만 block/wakeup에도 overhead가 있기 때문에 critical section이 매우 짧은 경우 오버헤드가 더 안좋을 수도 있다.
Two Types of Semaphores
Deadlock and Starvation
세마포어를 쓸 때는 주의해야 할 점이 있다. deadlock이 발생할 수 있다는 것이다. 또한 starvation 문제도 발생할 수 있다.
Classical Problems of Synchronization
Bounded-Buffer Problem
프로세스가 두 개가 있다. producer, consumer 프로세스가 각각 여러개 있다. 주황색은 생산자가 집어 넣은 것이고, 빈 것은 원래 비어있든가 생산자가 만든걸 consumer가 쓴거인가다.
세마포어를 이용해서 두 개 이상이 공유데이터에 접근하는 것을 막고, 가용자원이 가득차거나 비었을 때 생산자와 소비자에게 알려주기 위해 counting 세마포어가 필요하다.
Readers-Writers Problem
읽을 때도 lock은 걸어놓지만, 다른 프로세스가 read하려고 오면 허용해줘야 한다.
처음 read하는 것이면 lock을 걸고, 만약 마지막에 나가는 read 프로세스라면 lock을 풀어준다.
Dining-Philosophes Problem
두 번째 방법에 대해서만 알아보자.
mutex는 상태를 바꾸는데 lock을 거는 것이다.
pickup함수에서 test가 들어가는데 test 함수에서는 양옆이 밥을 안먹고 있고, 내가 배가 고플때 밥을 먹게 하는 것이다.
Monitor
모니터는 프로그래밍 언어차원에서 제공하는 것이다.
공유데이터에 접근하려면 monitor에 정의된 operation을 통해서만 접근 가능하다. monitor는 기본적으로 동시 접근을 허용하지 않고, 모니터가 알아서 하나의 프로세스만 접근 가능하게하고 나머지는 줄 세운다. 즉 락을 걸 필요가 없다. 이게 매우 편리하다.
만약 조건이 충족되지 않으면 잠들게 할 수 있다. 그 명령어가 wait이다. 깨우려고 하면 signal 명령어를 사용하면 된다.
Bounded-Buffer Problem
모니터의 코드에는 락을 걸고 푸는 코드가 없는 것을 알 수 있다.
모니터는 동시접근을 아예 모니터 차원에서 방지하고, 세마포어는 프로그래머가 해준다.
