Synchronization의 고전적인 문제(3)

1. Bounded-Buffer Problem

• Semaphore의 용도
  1) Lock의 문제(생산자가 동시에 도착)
  2) 가용자원의 개수세는 용도(버퍼의 유한함)

프로듀서는 버퍼에 데이터를 집어넣는다.
컨슈머는 버퍼의 데이터를 꺼내간다.

1) 생산자가 동시에 도착 -> Binary Semaphore(Lock/Unlock)

생산자가 둘이 동시에 도착하여 비어있는 버퍼를 보고, 생산자 둘이서 데이터 만들어서 버퍼에 넣는 경우 문제가 생김
이 경우 Lock을 걸어서 동시 접근을 막는다.

2) 버퍼의 유한함 -> Integer Semaphore(가용자원의 개수)

생산자들이 한꺼번에 도착해서 공유버퍼를 가득 채운다. (비어있는 버퍼가 나올때 까지 기다린다)
소비자들이 한꺼번에 와서 다 꺼내간다. (데이터가 있는 버퍼가 있을 때까지 기다린다)

Bounder-Buffer Problem 코드

• semaphore full: 내용이 들어있는 buffer의 개수를 세기위한 변수
• empty: 비어있는 buffer의 개수를 세기위한 변수
• mutex: Lock을 걸기위한 변수
• P(): 자원획득
• V(): 자원반납

P(empty)는 빈 버퍼의 개수를 확인한다(없으면 wait)
P(full)는 데이터가 있는버퍼의 개수를 확인한다(없으면 wait)
P(mutex)는 빈 버퍼를 획득하고 lock을 건다.
V(full)은 내용이 들어있는 buffer변수를 1개 증가시킨다
V(empty)는 비어있는 buffer 변수를 1개 증가시킨다.

2. Readers-Writers Problem

프로세스는 2종류가 있다. 1) 공유데이터를 읽어가는 프로세스, 2) 공유데이터에 쓰는 프로세스

write는 동시에 여러명이 하면 안되지만 read는 여럿이 동시에 해도 synchronization에 아무런 문제가 생기지 않는다. 그러나 Read하러와서 Lock을 걸어 아무도 접근못하게 하면 비효율적이다.

1) shared data

int readcount;는 현재 공유데이터에 접근중이 Reader의 수이다.

2) synchronization variable

semaphore mutex=1 (Lock 용도: readcount변수 보호)
db=1 (Lock 용도: db 보호)

오른쪽 Reader의 경우 최초의 Reader인 경우에 P(db)로 락을 걸어버린다. 그리고 다 읽고 마지막에 readcount가0이면 그제서야 V(db)로 락을 푼다.

위의 소스의 문제점은 Writer의 Starvation이다.
Reader가 Lock을 걸어 놓은 상태에서 Writer가 먼저 와도 Reader가 후에 몇개씩 계속 도착하면 계속 기다려야 하기 때문이다.

3. Dining-Philosophers Problem

식사하는 철학자는 동기화 문제 중 하나로, 여러 프로세스가 공유 자원에 동시에 접근하려고 할 때 발생할 수 있는 교착 상태(Deadlock) 문제를 설명하는 고전적인 예이다.

이 문제는 N명의 철학자가 원형의 테이블에 앉아 있고, 각 철학자 사이에 하나의 젓가락이 놓여있으며, 철학자가 식사하려면 두 개의 젓가락(왼쪽과 오른쪽 젓가락)을 동시에 집어야만 하는 상황을 모델링한다.

semaphore chopstick[5];

do {
    P(chopstick[i]); // 왼쪽 젓가락 잡는 연산
    P(chopstick[(i + 1) % 5]); // 오른쪽 젓가락 잡는 연산
    ...
    eat(); // 양쪽 다 잡으면 밥먹는다
    ...
    V(chopstick[i]); // 왼쪽 젓가락 내려놓음
    V(chopstick[(i + 1) % 5]); // 오른쪽 젓가락 내려놓음
    ...
    think(); // 다시생각
    ...
} while (1);

문제점: Deadlock의 가능성이 있다.
-> 모든 철학자 5명이 동시에 배가 고파서 왼쪽 젓가락을 잡음, 이러면 모든 철학자들이 본인이 밥을 먹고 배부를 때까지 놓지를 않음.
그러면 오른쪽 젓가락을 아무도 못잡음.

해결방법:
1) 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
2) 젓가락을 2개 모두 집을 수 있을때에만 젓가락을 집을 수 있게 한다.
3) 비대칭: 짝수(홀수)철학자는 왼쪽(오른쪽) 젓가락부터 집도록한다.
짝수 -> 왼쪽(우선순위)
홀수 -> 오른쪽(우선순위)
즉 짝수는 왼쪽을 집을 수 있어야 권한이 생긴다.

Monitor

Semaphore의 문제점

1) 코딩하기 어려움
2) 정확성의 입증이 어려움
3) 자발적 협력이 필요함
4) 한번의 실수가 모든 시스템에 치명적 영향을 줌

Monitor

monitor monitor-name
{
	shared variable declarations
    procedure body p1(...){
    	...
    }
    ...
    {
    	initialization code
    }

}

공유 데이터 접근하려면 monitor 내부의 procedure를 통해서만 가능하게한다.
내부의 procedure는 동시에 실행 안되도록 통제 권한을 준다. 즉 Lock을 걸 필요가 없어진다.

1) 모니터 내에서는 한번에 하나의 프로세스만이 활동가능
2) 프로그래머사 동기화 제약조건을 명시적으로 코딩할 필요 없다.
3) 프로세스가 모니터안에서 기다릴 수 있도록 하기 위해 condition변수 사용

• condition 변수는 wait와 signal 연산에 의해서만 접근가능
  1) x.wait(): 기다리는 줄에 줄서서 기다림
  2) x.signal(): 접근 다 하고 빠져나가면 signal 호출해서 기다리고 있는 프로세스를 동작하게끔 함

Bounded-Buffer Problem을 Monitor로 해결

1) 하나의 프로세스만 활성화 되기 때문에 entry queue가 줄서서 기다린다.
2) shared data는
x: 내용이 들어있는 buffer를 기다리는줄
y: 비어있는 buffer를 기다리는줄
로 나뉜다.
3) 이 기다리는 줄을 signal()을 통해 깨워준다.

Dining-Philoshphers Problem을 Monitor로 해결

1) 먼저 test로 젓가락을 잡을 수 있는지 테스트한다.
2) 만약 왼쪽 철학자가 밥을 먹지 않았고 본인이 배고프고 오른쪽 철학자도 밥을 먹지 않은 상태라면 먹는다.(잠들어 있으면 깨운다)
3) 만약 밥을 먹지 못한 상태라면 잠든다.
4) 인접한 철학자가 나 때문에 밥못먹고 잠들어 있으면 깨워주려고 test한다.