Process Synchronization(2)
Classic Problems of Synchronization
1. Bounded-Buffer Problem -> 대표적인 동기화 문제
2. Readers and Writers Problem -> scheduling 관련 동기화 문제
3. Dining-Philospohers Problem -> deadlock 관련 동기화 문제
Bounded-Buffer : Shared-Memory Solution
Producer, Consumer 문제
-> Bounded buffer 를 사용하여 producer는 생성만하고 consumer는 소비만 한다.
이때, buffer에 대한 동기화 문제가 발생하는데 이를 semaphore P, V 로 해결가능하다.
(버퍼가 꽉 찬 경우 Producer가 생성할 수 없고 버퍼가 비어있는 경우 Consumer가 읽어 올 수 없음 -> 쓰기,읽기 전 상태 확인 필요)
하지만 본질적인 문제는 Buffer 내의 변수들에 대한 동기화 문제도 동시에 해결해야함 -> 변수 자체를 semaphore 변수로 만들자!
[문제 해결]
변수 자체를 semaphore 변수로 만들어 사용
integer semaphore N을 사용하여 buffer의 개수를 읽어 다른 process가 접근하지 못하도록 해야한다.
N_empty-buf : 버퍼가 비어있는지 확인
N_full-buf : 버퍼가 가득 차있는지 확인
binary semaphore S_mutex 를 사용하여 buffer 에 대한 동기화 문제를 해결
integer semaphore 를 사용하여 buffer 가 비었는지, 꽉 차있는지 확인하여 접근에 대한 동기화 문제 해결
mutex가 필요할까?
-> buffer의 개수는 복수개이다. 반쯤 채워진 경우 두개의 프로세스가 통과하여 동기화 문제를 발생시킬 수 있으므로 P,V 를 사용하여 buffer를 보호해준다.
왔다갔다 할 수 있는 이유 -> P, V 함수가 atomic 하기때문에 가능하다.
Readers-Writers Problem
위에서 다룬 Producer, Consumer 문제와 유사하다. 하지만 생산자,소비자 문제에서는 Date를 소비하였지만 Readers-Writers Problem 에서는 Data를 소비하지 않는다는 차이점이 있다. 즉 Read-Only 동작을 하는 것이다.
동시에 Read를 할 수 있도록 하여 producer, consumer problem에 비해 Throughput을 높이고자 하는 동기화 방식으로 사용된다.
Read-Only를 하는 경우 Reader들간에는 동시에 접근이 가능하여 동기화 문제가 발생하지 않는다.
하지만 Writer 가 쓰는 도중에 읽거나, Reader가 읽는 도중에 쓰기 작업은 문제를 발생시키기 때문에 Reader와 Writer 간의 동기화 문제를 해결해줘야 한다.
<2가지 방식>
1. 모든 reader가 동시에 읽기 수행이 끝난 후 writer가 쓸수 있도록 하는 방식
2. 급한 작업인 경우 writer가 쓰고 난 후에 readers 가 읽을 수 있도록 하는 방식
여기서는 첫번째 방식을 다룬다.
reader 한명이 읽기를 시작한 경우 다른 reader들도 동시에 읽기 작업을 수행하도록 한다.
마지막 reader가 읽기 작업을 끝낸 후 writer가 쓰기 작업을 수행하도록 한다.
semaphore 변수 mutex, db를 사용하여 writer와 reader 간의 상호 배제 문제를 해결한다.
int 변수 readcount를 사용하여 reader의 읽기 상태를 확인하여 동기화 문제를 해결한다.
Reader는 첫 번째 reader 인 경우 P(db)를 호출한 뒤 읽기를 시작한다. -> Writer가 작업을 수행하지 못함
이후의 reader는 따로 P(db)를 호출할 필요가 없다. -> 두번재 reader도 호출하는 경우 동시읽기 작업 자체가 불가능해진다.
마지막 reader의 경우 읽기 작업을 끝낸 후 V(db)를 호출한다. -> Writer 가 작업을 수행할 수 있는 상태
Writer의 경우 대기하다가 마지막 reader가 읽기를 끝내고 V(db)를 호출하는 순간 쓰기 작업이 가능하여 critical section으로 넘어가게 된다.
쓰기 작업에 대해서도 마찬가지로 P(db), V(db)를 사용하여 reader 와의 동기화 문제로부터 보호한다.
Reader의 경우 P,V 함수를 호출하기 위해 첫번째,마지막 reader인지 확인을 위한 변수가 필요하다. => readcount 변수
readcount 변수 자체에 접근할 때에도 동기화 문제가 발생할 수 있다.
ex) 서로다른 reader가 동시에 readcount 를 증가시키고 읽기 작업을 수행하려는 경우 P(db)가 호출되지 않을 수 있다.
=> 즉, read count 변수 자체에 접근하는 과정도 atomic하게 만들어줘야한다.
마찬가지로 readcount 연산 과정 앞뒤로 P,V 함수를 호출하여 count 과정 자체도 atomic하게 만들어줘 동기화 문제를 해결해준다.
( readcount ++; if(readcount ==1) , readcount --; if(readcount == 0) 해당부분이 critical section이 된다.)
Dining-Philosophers Problem : Think & Eat Repeatedly
[문제상황]
철학자들이 원탁에 둘러 앉아 생각을 하며 식사를 하는 상황.
하지만 젓가락은 양 옆으로 하나씩만 세팅되어있어 양쪽 젓가락이 사용 가능할때만 식사를 할 수 있다.
=> 젓가락을 집는 행위 자체가 동기화되어 이루어져야지 문제해결이 가능하다.
젓가락 하나를 공유변수라고 생각하면 왼쪽, 오른쪽 젓가락이 모두 사용중인 상태가 아닐 때 집어들어 식사를 할 수 있다.
P 함수(atomic한 함수)를 사용하여 P(chopstic[i])는 왼쪽, P(chopstick[(i+1)%5]) 은 오른쪽 젓가락을 나타내어 동기화 문제를 해결 할 수 있다.
But, 모든 철학자가 동시에 배가 고파 젓가락을 드는 경우를 생각해보자.
동시에 모두가 왼쪽에 있는 젓가락을 드는 과정까지는 성공을 한다. 하지만 모두의 오른쪽 젓가락은 사용중이기 때문에 대기상태에 빠진다.
서로가 기다리기만 하며 무한히 대기하는 상태가 발생하는데 이러한 상태가 Deadlock 문제가 발생한 것이다.
Deadlock이란 내가 다른 프로세스가 가진 자원을 해당 프로세스가 놓을 때까지 기다리는 형태가 원형회귀적으로 발생하여 해결되지 않고 무한히 서로가 서로를 기다리는 상태에 빠지는 것이다.
Deadlock and Starvation
Deadlock - 두 개 혹은 그 이상의 프로세스가 무한대기를 하는 경우 (대기 중인 프로세스가 깰 수 있지만 무한대기중이라 해결이 불가함)
<예시>
P0는 P(S)를 잡고 P1는 P(Q)를 잡은 상태이다.
이 경우 서로 P(Q), P(S)를 잡지 못해 서로를 계속 기다리는 상태에 빠져 다음 과정 진행이 불가하다. 마찬가지로 V(Q),V(S) 함수 호출 또한 할 수 없어 문제가 해결될 수 없다.
Starvation - 무한하게 blocking 되는 현상이다. 하지만 deadlock 문제와는 다르게 다른 어떤 프로세스는 진도를 나가고 있다는 것이 차이점이다.
LIFO 큐로 구성된 경우 Linked-List의 제일 앞의 프로세스는 거의 깨어나기 힘들어 희생되어 진행되지 못하고 있는 상태이다.
Deadlock - 3가지 해결방안
1. 젓가락을 하나씩 드는 것이 아니라 둘다 확인을 하고 동시에 들어서 문제를 해결하자 (양쪽 젓가락을 하나의 자원으로 취급)
2. Asymmetric coding -> 홀수번째 철학자는 왼쪽 젓가락을, 짝수번째 철학자는 오른쪽 젓가락을 먼저 들도록 함
3. 5명이 있는 경우 4명만 앉혀서 문제를 해결하자
-> 3가지 경우에 대해 직접 알고리즘 구현해보기!
Problems of Semaphore
: Semaphore를 이용하면 동기화 문제를 해결할 수 있지만 사용해서 해결하는 과정이 어렵다
- 코드를 구현하는 것이 어려움
- 정확성을 입증하는 것이 어려움 -> 오류를 재현하는 것이 어렵다
- 협력 과정이 필요하다.
- 잘못된 사용은 전체 시스템을 마비시킬 수 있음
* 조금 더 쉽게 해결할 수 있는 방법이 없을까? ==> Monitor 방식
Monitors : Similar to Abstract data type (private data -- public methods)
Hight-level language 에서 공유 데이터 접근 동기화 문제를 해결해주는 추상적인 데이터 타입
객체지향언어에서와 유사하게 public methods만 private data에 접근 가능한 구조이다.
Schematic View of a Monitor
Monitor 는 내부에서 단 하나의 프로세스만 active 가능하도록 보장한다. (Monitor의 기본개념)
여러 public method가 접근시도하는 경우 하나가 실행중이면 entry queue에서 나머지 프로세스가 대기하도록 한다.
Monitors
코드를 수행하는 중 조건을 만족시켜야 하는 경우가 발생하는데 다른 프로세스가 해당 조건을 만족시키는 경우가 발생한다.
=> Monitor 내부에서 wait 하도록 한다. active 하지 않게 sleep 상태로 wait 하도록 만들어주어 entry queue의 다른 프로세스가 실행할 수 있도록 해준다.
이를 위해 condition variable 을 사용한다.
condition x, y;
x.wait() -> x 조건을 만족시키지 못해 sleep 상태로 기다리도록 한다.
x.signal() -> x에서 기다리는 프로세스에게 시그널을 보내 깨워주도록 한다.
Monitor : Dining-Philosophers Problem
Dining-Philosophers Problem의 Deadlock 문제를 양쪽 젓가락을 드는 방식으로 해결한 경우
*Bounded Buffer Problem을 위한 Monitor 작성해보기
<전체코드>
전체적인 동작 과정
thinking, eating, hungry 세가지 상태로만 구분한다.
Monitor Implementation
Conditional-wait construct : x.wait(c); -> c 변수를 사용하여 우선순위를 정하여 순서를 제어하도록 하자.
Monitor 에서는 다음 두 가지 조건이 만족한다면 올바른 동기화 문제 해결책이 될 수 있다.
1. 항상 올바른 순서로 호출해야한다.
2.비협조적인 프로세스가 monitor 가 제공하는 상호배제 gateway를 무시하지 않도록 하며, 접근 프로토콜을 사용하지 않고 공유 자원에 직접 접근하도록 해야한다.
*access protocol : 장치가 네트워크를 통해 서로 통신하는 방식을 제어하는 일련의 규칙