1. Bounded-Buffer Problem : 공유버퍼 문제 (Producer-Consumer Problem)

Producer : 데이터를 넣어주는 생산자

Comsumer : 데이터를 사용하는 소비자

발생하는 문제

1) 복수의 생산자 동시접근

2) 복수의 소비자 동시접근

3) 버퍼가 꽉 차있을 때 생산자의 접근

4) 버퍼가 비어있을 때 소비자의 접근

 

Shared data]

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

Synchronization variables]

mutual exclusion : need binary semaphore (공유데이터의 상호배제를 위해(자원 접근 넣고 빼기))

resource count : need integer semaphore (남은 full/empty buffer 수 표시를 위해(가용자원에 대한 문제))

 

Synchronization variables
semaphore full = 0, empty = n, mutex = 1; // lock을 거는용 mutex, 비어있는 변수 empty, 내용있는 버퍼 full

Producer
do {
   P(empty);    //빈 버퍼 확인 후 기다리거나 획득하거나
   P(mutex);    //버퍼 획득시 lock 걸기
   add x to buffer
   V(mutex);   //버퍼 반납 후 lock 풀기
   V(full);       //데이터 넣은 버퍼 갯수 증가
} while(1);

Consumer
do {
   P(full);       //데이터 있는 버퍼 확인 후 기다리거나 획득하거나
   P(mutex);   //버퍼 획득시 lock 걸기
   remove an item from buffer to y
   V(mutex);   //버퍼 반납 후 lock 풀기
   V(empty);   //비어있는 버퍼 갯수 증가
} while(1);

 

2. Readers-Writers Problem : 읽고 쓰기 문제

한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안된다

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
int readcount = 0;
DB 자체;
Synchronization variables
semaphore mutex=1, db=1; //mutex 는 readcount 에 대한 lock 용, db는 DB lock 용

Writer
P(db);  // Starvation 발생 가능 (Reader 가 계속 들어와서 존재할 경우 Writer 순서가 오지 않음)
writing DB is performed
V(db);

Reader
P(mutex); // readcount 도 mutex 가 보장되어야 하므로 readcount lock시킨다
readcount++;
if(readcount==1) P(db); //block writer : 최초의 reader 접근시 writer lock시킨다
V(mutex); //readers follow
reading DB is performed
P(mutex);
readcount--;
if(readcount == 0) V(db);  //enable writer (writer lock을 푼다)
V(mutex);

 

3. Dining-Philosophers Problem

Dead lock 의 가능성

해결방안 :

1) 최대 4명만 동시에 테이블에 앉도록

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

3) 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

 

2번 해결방안에 대한 코드]

 

Semaphore의 문제점

- 코딩하기 힘들다

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

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

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

실수의 예]

 

Monitor

: 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct (java 디자인 패턴에서 어댑터 패턴을 사용하여 세마포를 캡슐화한 어댑터와 비슷한 느낌)

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

- 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음

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

- Condition variable 은 wait과 signal 연산에 의해서만 접근 가능

x.wait()

: x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend 된다

x.signal()

: x.signal()은 정확하게 하나의 suspend 된 프로세스를 resume 한다

Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다

 

monitor 를 사용한 bounded buffer 문제 해결 코드]

monitor bounded_buffer
{
   int buffer[N];
   condition full, empty;
   // condition var은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나
   // 큐에서 프로세스를 깨우는 역할만 함

   void produce(int x){
      empty.wait(); // if there is no empty buffer 
      full.signal(); // add x to an empty buffer
   }
   void consume(int x){
      full.wait(); // if there is no full buffer
      empty.signal(); // remove an item from buffer and store it top x
   }
}

monitor 를 사용한 dining philosopher 문제 해결 코드]

 

※ 이화여대 반효경 교수님의 운영체제 강의 정리

반응형

+ Recent posts