Process Synchronization 3

Classical problems of shynchronization

 

1. bounded-buffer problem.

- 버퍼의 크기가 유한한 환경에서 producer-consumer problem. 생산자 소비자 문제 발생. 

producer 프로세스와 consumer 프로세스 존재. 각각 여러개 존재.

producer는 공유 버퍼에 데이터를 하나 만들어서 집어 넣는 역할을 한다. 

 

producer 

1. empty 버퍼가 있는가?- 없으면 기다림. 

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

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

4. lock을 푼다. 

5. full buffer 하나 증가. 

 

consumer 

1. full 버퍼가 있나요? - 없으면 기다림

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

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

4. lock을 푼다. 

5. empty buffer 하나 증가. 

 

생산자 2개가 동시에 도착해서 비어있는 버퍼를 동시에 보고 접근하려 했을 때 문제가 발생한다. 

생산자가 비어있는 버퍼를 확인하고 데이터를 집어넣는 과정에서 lock을 건다. 따른 프로세스의 접근을 막는다. 소비자도 마찬가지의 과정을 거친다. 

공유 버퍼에 lock을 걸고 풀며 문제 해결. 

 

생산자 입장에서 자원은 비어있는 버퍼. 비어있는 버퍼가 없으면 생산자 프로세스는 자원의 여분이 생길때까지 기다려야한다. 소비자가 꺼내가야만 빈 버퍼가 생긴다. 

 

소비자 입장에서는 자원이 내용이 들어있는 버퍼이다. 해당 자원이 0이면 소비자 프로세스는 생산자 프로세스가 내용을 넣어줄때까지 기다린다. 

 

세마포어로 해야할 업무가 2가지.

공유 버퍼 전체에 lock을 건다. 버퍼가 가득 차거나 비었을 때 가용 자원의 개수를 세어주는 counting 세마포어 용도로 세마포어 변수가 사용된다. 

 

synchronization variables

 

semaphore full=0(내용이 들어있는 버퍼 수), empty=n(비어있는 버퍼 수), mutex=1(lock을 걸기 위한 변수)

공유 버퍼의 수가 n개. 

P연산은 자원 획득, V는 자원 반납

 

Producer

do{ ...

   produce an item in x

   P(empty);  //빈 버퍼가 있다면

   P(mutex);   //lock을 건다.

   ...

   add x to buffer

   V(mutex);   //lock 푼다. 

   V(full);       //소비자 입장에서의 자원을 증가시킨다. 

}while(1);

 

Consumer

do{ 

   P(full);    //내용이 들어있는 버퍼가 있다면

   P(mutex);

    ...

   remove an item from buffer to y

    ....

   V(mutex);

   V(empty);  //비어있는 버퍼 개수 1증가. 

   ...

  consume the item in y

  ...

}while(1);

 

2. Readers-Writers Problem

한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨. 

read는 동시에 여럿이 해도 됨. 해당 문제를 어떻게 해결하느냐. 

 

shared data 

int readcount=0(몇명이 읽고 있는지-현재 DB에 접근 중인 reader의 수); , DB 자체

 

synchronization variables

semaphore mutex=1(공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용), db=1(Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할);

 

Writer

P(db);  //lock을 걸었다. 

...

writing DB is performed  //DB에 쓰는 작업

...

V(db);  //lock을 푼다. 

 

Reader

P(mutex);

readcount++;

if(readcount==1) P(db);   //초기 reader만 lock을 건다. 

V(mutex);                     //

...

reading DB is performed

....

P(mutex);

readcount--;

if(readcount==0) V(db);  //마지막 reader라면 db에 건 lock을 풀어준다. 

V(mutex); 

 

3. Dining-Philosophers Problem

 

synchronization variables : semaphore chopstick[5];초기 값은 1

 

deadlock의 가능성이 있다. - 모두 왼쪽 젓가락을 잡아버리면 아무도 먹을 수 없다. 

해결방안 - 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다. 

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

짝수 철학자는 왼쪽 젓가락만 잡게 한다. 홀수는 반대로. 

 

 

semaphore의 문제점

- 코딩하기 힘들다. 

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

- 자발적 협력이 필요하다. 

- 한번의 실수가 모든 시스템에 치명적 영향.

ex) V와 P가 바뀌면 mutual exclusion 깨짐. V를 하지 않고 P를 2번 하게 되면 deadlock이된다. 

 

 

Monitor

- 동시접근을 허용하지 않아서 monitor에 있는 공유 데이터에 접근하면 된다. lock을 걸 필요가 없다. 

모니터 내부에 공유 데이터 선언을 하고 해당 데이터에 접근하기 위한 프로시저들을 모니터 내부에 선언을 한다. 

모니터 내에서는 한번에 하나의 프로세스만이 활동 가능하다. 

프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해

condition variable 사용. wait와 signal 연산에 의해서만 접근 가능. 

condition x,y;

 

producer, consumer 코드 monitor로.