Process Synchronization - Bounded Buffer Problem

Bounded Buffer Problem (유한 버퍼 문제)

출처: 운영체제 - 반효경

• Producer-Consumer Problem(생산자-소비자 문제) 이라고도 한다.
• Producer
  • 데이터를 버퍼에 삽입
• Consumer
  • 데이터를 버퍼에서 제거

 

여기서 Shared Data는?

1. 버퍼 자체
2. 버퍼 조작 변수(empty와 full 버퍼의 시작 위치)

 

문제의 원인

• 다수의 Producer / Consumer가 버퍼에 데이터를 삽입, 제거할 수 있기 때문이다.
  • 버퍼 자체의 경쟁 상황 발생
  • 버퍼가 가득 차거나 빌 경우 추가/삭제가 불가능함을 알아야 한다.

 

두 가지 세마포어가 필요

Mutual exclusion

• shared data의 동기화 때문에 Binary semaphore가 필요 (2번 스텝)
  • 다수의 주체가 동시에 버퍼를 변경할 수 없도록 Lock을 건다.

Resource count

• 남은 full/empty 버퍼의 수를 표시하기 위해 Integer semaphore가 필요 (5번 스텝 + 기다리는 프로세스 wake up)
  • EX) Producer가 데이터를 삽입할 때마다 Full 버퍼의 수를 증가 시키고 가득차면 대기 상태에 들어간다. 만약 대기 중인 Consumer가 있다면 Wake up 시켜준다.

 

 

Pseudo Code

Initialization

semaphore full = 0, empty = n, mutex = 1;

• Integer semaphore 변수 full, empty와 Binary semaphore 변수 mutex를 설정
• 최초의 버퍼는 빈 상태이므로 full 값은 0, empty 값은 1로 한다.
• 최초에는 접근 가능해야 하므로 mutex는 1로 설정

 

Producer

do {
  // produce an item in x
  // ...
  P(empty);
  P(mutex);

  // add x to buffer

  V(mutex);
  V(full);
  
} while(1);

• P(empty) 함수는 empty 상태인지(값이 1 이상인지) 확인한 후 자원에 접근하도록 하는 세마포어 오퍼레이션이다.
  • empty 값이 0이면 대기한다.
• P(mutex) 함수는 버퍼 자체에 대한 락을건다.
• V(mutex) 함수는 버퍼 자체에 대한 락을 해제한다.
• V(full) 함수는 full 값을 증가시키고 대기하는(Blocked 상태인) Consumer가 있으면 Wake up 시켜준다.

 

Consumer

do {

    P(full);
    P(mutex);

    // remove an item from buffer to y

    V(mutex);
    V(empty);
    // ...
    // consume the item in y
    // ...
} while(1);

• P(full) 함수는 full 상태인지(값이 1 이상인지) 확인한 후 자원에 접근하도록 하는 세마포어 오퍼레이션이다.
  • full 값이 0이면 대기한다.
• P(mutex) 함수는 버퍼 자체에 대한 락을건다.
• V(mutex) 함수는 버퍼 자체에 대한 락을 해제한다.
• V(empty) 함수는 empty 값을 증가시키고 대기하는(Blocked 상태인) Producer가 있으면 Wake up 시켜준다.

 

 

 

출처

반효경, "운영체제 2014-1", KOCW, http://www.kocw.net/home/cview.do?cid=3646706b4347ef09