06. Process Synchronization (4/5)

1. Semaphore

가. P(S): S.value--                //prepare to enter

if (S.value < 0)            //negative, cannot enter

{

add this process to S.L

block();

}

나. V(S): S.value++

if(S.value <= 0){

remove a process P from S.L

wakeup(P)

}

2. Bounded-Buffer Problem(Producer-Consumer problem)

가. Producer: 공유 버퍼에 데이터를 집어넣는 역할

1) 생산자가 같은 버퍼에 동시에 데이터를 집어 넣는 문제

-> lock을 걸고 데이터를 집어 넣음

2) 버퍼가 이미 다 찼는데, 생산자가 도착함 즉, 데이터를 집어 넣을 수 없음

-> 비어있는 버퍼의 개수가 자원임 (세마포어에서는 자원의 개수를 카운트함)

나. Consumer

1) 같은 버퍼에 동시에 데이터를 꺼내는 문제

-> lock을 걸고 데이터를 꺼냄

2) 모든 버퍼가 비어 있음 즉, 꺼낼 데이터가 없음

-> 데이터의 수가 자원의 수임

3. Readers-Writers Problem: DB에 Write 중일 때, 다른 process가 접근하면 안 됨, read는 동시에 여럿이 해도 됨

가. Writer가 DB에 접근 허가를 아직 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.

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

다. 일단, Writer가 DB에 접근 중이면, Reader들은 접근이 금지된다.

라. Writer가 DB에서 빠져나가야만 Reader들 접근할 수 있다.

-> readcount를 위한 mutex와 writer와 reader를 위한 db 를 세마포어로 구성

4. Dining-Philosophers Problem: 원탁에 있는 철학자들이 양쪽에 있는 수저를 둘 다 들어야만 먹을 수 있음

가. 철학자는 배고파서 먹거나, 생각하거나 두 가지 행동이 있음

문제: Deadlock 가능성이 있음(모두 왼쪽을 집음)

해결1: 4명만 앉음

해결2: 모두 집을 수 있을 때만 집음

해결3: (비대칭) 홀수는 왼쪽, 짝수는 오른쪽부터 집음

5. Monitor

가. Semaphore의 문제점: 어려움, 정확성 입증이 어려움, 자발적 협력이 필요함, 한 번의 실수가 치명적임

ex1) V(mutex) - P(mutex) -> Mutual exclusion 깨짐

ex2) P(mutex) - P(mutex) -> Dead lock

나. 정의: 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high level Synchronization construct

다. 모니터에 기본적으로 동시접근을 허락하지 않음, 나머지 프로세스는 줄 서서 기다림

라. condition variable이 자원의 개수를 대신함, wait()과 signal()이 P()와 V()를 대신함(lock 말고, 조건에 맞게 wait시키고 깨움)