Process Synchronization 3 - classical problems

- 세마포어 방식으로 여러 문제들을 해결하는 방법

1) Bounded-Buffer Problem(Producer-Consumer Problem)

- 버퍼의 길이가 유한일때

- Producer, 생산자 프로세스와 Consumer, 소비자 프로세스가 존재함

- 생산자 프로세스는 버퍼에 자원을 넣는 역할을 담당(원 안에 주황색)

- 소비자 프로세스는 버퍼에 자원을 사용하는 역할(원안에 아무것도 없음)

 

세마포어를 이용해 해결해야할 업무 2가지:

1. 2개의 프로세스가 동시에 접근할때

- 만약 생산자 2개가 같은 원안에 자원을 넣으려고 하면 critical section과 비슷한 문제가 발생함

- 하나의 생산자 프로세스가 자원을 넣으려 할때는 전체 버퍼에 lock을 거는 방식으로 해결

- 마찬가지로 여러 소비자가 자원을 꺼내려 할때도 동일하게 lock을 거는 방식으로 해결

2. 생산자 혹은 소비자가 접근할수 있는 자원 관리

- 만약 전체 버퍼가 다 차있을때 또 생산자가 온다면 빈 버퍼가 있을때까지 기다려야함

- 생산자 입장에서는 빈 버퍼가 접근해야할 자원 개수

- 똑같이 소비자 입장에서는 차있는 버퍼가 접근해야할 자원 개수

 

생산자 입장에서는

1. 빈 버퍼가 있는지 체크(없을경우 기다림)

2. 빈 버퍼가 있을경우 공유 데이터 lock 검

3. 빈 버퍼를 하나 채우고 빈 버퍼 위치를 하나 증가시킴

4. lock 해제

5. 차있는 버퍼 개수 1 추가(소비자에게 차있는 개수 알려주기 위함)

소비자는 빈 버퍼 -> 차있는 버퍼로 바꾸면 됨

 

세마포어 변수 2개가 필요

1. 버퍼의 empty/full을 체크하는 resource count 변수

2. 다른 프로세스가 공유 데이터에 접근하고 있는지 체크하는 mutex 변수(lock을 걸기 위함)

 

 

초기세팅:

- 1개의 프로세스만 접근할수 있도록 mutex 변수는 1로 세팅

- 처음에는 모든 버퍼가 비어있을테니 empty 변수는 n으로 세팅하고 full 변수는 0으로 세팅

 

Producer:

1. produce an item in X : 버퍼를 채울 내용을 만든다

2. P(empty): 빈 버퍼가 있는지 체크, 없다면 기다림

3. P(mutex): 빈 버퍼가 있다면 하나 획득(lock 검)

4. add x to buffer: 만든 내용을 버퍼에 집어넣는다

5. V(mutex): 버퍼에 lock을 푼다

6. V(full): full 변수를 1 증가시킨다

 

 

 

2) Readers and Writers Problem

- read하는 프로세스, write하는 프로세스가 있음

- 공유 데이터는 DB

- read이던 write이던 접근하면 P연산으로 lock을 걸고 나갈때 V연산으로 unlock하면 쉽게 해결 가능하나 사실 read할때는 굳이 lock을 걸 필요 없음

- read는 여러 프로세스가 동시에 접근해도 접근할수 있게 해줌

- write는 하나의 프로세스만 접근 가능하도록 lock, unlock을 해줌

- DB는 lock을 걸어야 하는 공유 데이터

- db는 공유데이터 DB에 세마포어 연산을 하기 위한 세마포어 변수

 

- read하는 동안에는 write가 접근 못하도록 하게 해야하기 때문에 readcount라는 공유데이터를 하나 만듬

- read 프로세스가 들어올때마다 readcount++하고 나갈때마다 readcount--함

- readcount가 1일때는 read가 처음 들어온 것이므로 P(db) 연산을 해줌

- readcount가 0일때는 read하는 프로세스가 없으므로 V(db) 연산을 해줌

- 그리고 readcount 자체도 공유데이터이므로 mutex변수를 통해 P,V 연산을 해줌

 

- read 프로세스가 끊임없이 들어올 경우 똑같이 starvation 문제가 발생할 수 있음

- 신호등처럼 read 프로세스가 lock을 건 후 일정시간이 지나면 더이상 read가 못들어 오게 막는식으로 해결할 수 있음

 

 

3) Dining-Philosophers Problem

- 5명의 철학자는 eat하거나 think 할수있음

- 배고프면 밥을 먹는데 양쪽의 젓가락을 다 들어야 식사할수있음

- 밥을 다 먹으면 젓가락을 놓고 생각함

- 지금은 왼쪽 젓가락을 잡는 P연산과 오른쪽 젓가락을 잡는 P연산이 있음, 만약 젓가락이 없다면 기다려야함

 

- 모든 철학자가 동시에 왼쪽 젓가락을 집으면 아무도 오른쪽 젓가락을 집을수 없는 deadlock이 발생함

해결방안:

1. 4명의 철학자만이 테이블에 동시에 앉을수 있도록 한다

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

3. 짝수 철학자는 왼쪽 젓가락 먼저, 홀수 철학자는 오른쪽 젓가락부터 잡도록 한다

- 아래는 2번째 방법의 코드

- 철학자는 eat() 혹은 think() 할수 있음

- eat 전후로 pickup(i)와 putdown(i)을 해줘야됨, i는 철학자 순서

- pickup, putdown할때 test()를 통해 젓가락을 둘다 집을수 있는지 체크

- state[] 는 철학자의 상태를 나타냄, pickup할땐 hungry, test할땐 eating, putdown할땐 thinking으로 바뀜

- state도 자기 자신만 바꿀수 있는게 아닌 옆 철학자들도 바꿀수 있는 공유데이터이기 때문에 mutex 변수로 lock, unlock 할수 있게 함

 

- pickup 하면서 우선 자신의 상태를 hungry로 바꿈

- test를 통해 젓가락을 집을 수 있는지 체크

- 좌우 철학자가 둘다 밥을 먹고 있지 않고(!=eating), 내가 배고픈 상태에서만 state를 eating으로 바꾸고 V연산을 한다

- 이때 V(self[i])연산은 자원을 하나 빼는것이 아닌 해당 조건이 충족했을때 i에게(지금은 나) 젓가락 집을수 있는 권한을 주는것(이때만 특이하게 V연산이 권한을 주는 역할을 담당)

- 그리고 V(mutex)연산으로 공유자원(state[i])를 빠져나오고 P(self[i])연산으로 젓가락 잡을수 있는 권한을 획득

- eat() 연산

- putdown()에서는 자기 자신을 thinking으로 바꾸고 test()를 두번 호출해 좌우 철학자들이 기다리고 있었으면 젓가락을 잡을 수 있는 권한을 준다

 

 

모니터:

- 세마포어는 코딩할때 실수가 발생하기 쉽고, 에러가 나면 찾기 힘듬

- 프로그래밍 언어 차원에서 공유데이터 문제를 해결해주는게 모니터

- high-level synchronization construct(객체지향 바탕)

- 공유데이터를 접근하기 위해서는 모니터라고 정의된 내부의 프로시저들을 통해서만 접근 가능하도록 함

- 기본적으로 모니터는 동시접근을 허용하지 않기 때문에 lock을 걸 필요가 없어짐

 

- 생산자 소비자 문제를 모니터로 푼 방법:

- 모니터 객체 안에 버퍼(공유데이터)가 있음, 그래서 lock을 걸지 않아도 하나만 접근 가능함

- 객체 내장 함수들을 통해서만 공유데이터에 접근이 가능하도록 함

produce: empty 버퍼가 없다면 empty 큐에서 기다림, 있다면 x를 채우고 full 큐에서 기다리고 있는 프로세스 하나 깨움

consume: full 버퍼가 없다면 full 큐에서 기다리다 있다면 x를 사용하고 empty 큐에있는 프로세스 하나 깨움