Process Synchronization: 프로세스 동기화 (2/2)

<Semaphores>

자원을 획득하고 반환하는 걸 처리하는 것을 추상화한 것이다.

Semaphores S

- integer variable (변수 값 = 정수, 변수가 1이라면 lock, unlock에 활용하고 자원의 개수가 5개라면 5개가 사용 가능)

- 아래의 두 가지 atomic 연산에 의해서만 접근 가능하다.

p -> 자원이 0보다 아래라면(모든 자원이 사용 중이라면) 기다리기 근데 이 때도 busy waiting 문제가 발생한다. / s -> 계산 완료 후 자원을 내놓는 것

P(S)는 공유데이터(자원)을 얻는 연산이다. 그러니까 lock을 거는 과정이라고 생각해도 된다.

 

<Critical Section of n Process>

세마포어 객체 mutex는 1로 초기화되어 있다. (1개가 크리티컬 섹션에 들어갈 수 있다는 뜻임)

busy - wait는 효율적이지 못함 ( = spin lock)

block & wake up 방식의 구현 (= sleep lock)

락을 못 얻으면 blocked (잠들어버리기) -> 쓸데없이 cpu 낭비하는거 막음 약간 i/o할 때 block queue되듯이

 

<Block & Wake up Implementation>

 

* block과 wake up을 다음과 같이 가정한다.

- Block:   커널은 block을 호출한 프로세스를 suspend 시킨다.

             이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음

- Wake up (P) : block 된 프로세스 P를 wake up 시킨다. 이 프로세스의 PCB를 ready queue에 옮긴다.

잠들어있는 세마포어들 하나가 반납되면 하나 wake up

 

<Implementation block / wake up bersion of P( ) & v( )>

v(s)연산에서 S.value <= 0 이거는 내가 자원 반납해도 s.value가 <= 0이라는 것은 자고 있는 프로세스가 있다는 이야기이다 (blocked)

여기서 S.value는 자원의 개수보단 음수 = 자고 있는 애 있음 양수 = 자원에 여유가 있다. 기다리지 않고 자원 사용가능함 S.value는 자고 있는 애 있나 확인하려는 용도에 가깝다.

<Which is Better?>

Busy - wait  VS Block / wake up

Blocked / wake up 오버헤드 vs critical section 길이

 - critical section의 길이가 긴 경우 block / wake up 

 - critical section의 길이가 매우 짧은 경우 block / wake up 오버 헤드가 busy - wait 오버헤드보다 더 커질 수 있다.

 - 일반적으로는 block / wake up 방식이 더 좋다.

 

<Two types of Semaphore>

* counting Semaphores

 - 도메인이 0 이상인 임의의 정수값 -> 자원이 여러 개라 가져다 쓰면 된다.

 - 주로 resource counting 에 사용된다.

 

* Binary Semaphores

 - 0 또는 1만 가질 수 있는 Semaphore

 - 주로 mutual exclusion(lock/unlock)에 사용된다.

 

<Deadlock & Starvation>

Deadlock

 - 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 

S와 Q가 1로 초기화된 semaphore이라고 하자.

p0은 S를 얻고 p1은 Q를 얻는다. 그리고 다음 줄에 서로의 것을 요구한다. 해결 방법은 p1도 S부터 요구하게 하는 것이다.

Starvation

 - idefinite blocking: 프로세스가 suspend 된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

 

<Bounded - Buffer Problem (Producer - Consumer Problem)>

in (Producer)

1. empty 버퍼가 있나? (없으면 기다림)

2. 공유데이터에서 lock을 건다 -> 동시 접근 막음

3. empty buffer에 데이터 입력 및 buffer 조작

4. lock을 푼다.

5. full buffer 하나 증가

 

out (Consumer)

1. full buffer가 있나? (없으면 기다림)

2. 공유 데이터에 lock을 건다.

3. full buffer에서 데이터 꺼내고 buffer 조작

4. lock 을 푼다.

5. empty buffer 하나 증가

 

* shared data

 - 버퍼 자체 및 버퍼 조작 변수 (empty/ full buffer의 시작 위치)

* synchronization variables

 - Mutual exclusion -> need binary semaphore (shared data의 mutual exclusion을 위해서)

 - resource count -> need integer semaphore (남은 full / empty buffer의 수 표시)

 

<Bounded Buffer Problem>

Synchronization variables

semaphores full = 0 (들어 있는 버퍼), empty = n (비어있는 버퍼), mutex = 1 (공유 데이터에 하나만 접근할 수 있게 락 거는 용도)

<Readers & Writers Problem>

* 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안된다. write는 하려면 reader, writer 1개도 없어야 한다. 아무도 있으면 안됨

* read는 동시에 여럿이 해도 된다. 

* Solution 

 - writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들을 전부 DB에 접근하게 해준다.

 - writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.

 - 일단 writer가 DB에 접근 중에면 reader들은 접근이 금지된다.

 - writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

 

shared data

DB 전체, readCount(현재 DB에 접근 중인 Reader의 수)

Synchronization Variables

* mutex 공유 변수 readcount를 접근하는 코드 (critical section)의 mutual exclusion 보장을 위해 사용

* DB Reader와 writer가 공유 DB자체를 올바르게 접근하게 하는 역할

 

shared data

DB 전체, readCount(현재 DB에 접근 중인 Reader의 수) = 0;

Synchronization Variables

semaphore mutex = 1, db = 1;

reader코드를 설명하자면 write하려면 reader가 있으면 안된다 readcount도 공유변수니까 락 걸어주고 readcounnt가 1이면 내가 최초의 reader라는 뜻이고 db에 락 걸어주고 v(mutex) = seginal(mutex)로 readcount 락 풀어준다.

 

<Dining - Philosophers Problem>

Synchronization variables

semaphore chopstick[5] 1로 초기화 되어있음

 

데드락의 가능성이 있다. 만약 모든 철학자가 동시에 배고파서 왼쪽 젓가락을 집었다면 오른쪽 젓가락은 획득하지 못하므로 데드락이 걸릴 수있다.

해결방안 1: 4명만 테이블에 앉을 수 있게 하는 것이다.

             2: 젓가락을 두 개 모두 잡을 수 있을 때에만 젓가락을 잡게 한다.

             3: 비대칭(짝수 (홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 잡도록 한다.

 

<Monitor>

* Semaphore의 문제점

- 코딩하기 힘들다.

- 정확성(correctness)의 입증이 어렵다.

- 자발적 협력(voluntary cooperation)이 필요하다.

- 한 번의 실수가 모든 시스템에 영향을 끼친다.

 

프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용한다. 

Condition x, y;

condition variable은 wait(여분이 없으면 기다리기) 과 signal(빠져나갈 때 기다리는 다른 애 있으면 잠들게) 연산에 의해서만 접근이 가능하다.

ex) X.wait( ): 잠들게   /     X.signal( ): 깨우게 

X.signal( )은 정확하게 하나의 suspend된 프로세스를 return 한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

 

조건에 안맞는 얘들 잠들게 하는데 그 조건에 따라 얘들 줄세운다. (1)은 x가 안맞고 (2)는 y가 안맞는다. wait, signal 두 가지 연산으로만 접근 가능하다. 실행하다가 어떤 조건(condition)이 맞지 않으면 wait( ), 줄 선다.