전통적 동기화 예제 (1) 생산자 - 소비자 문제

1. 전통적 동기화 예제

1) 생산자 소비자 문제 (Producer - Consumer Problem)

 - 생산자 - 소비자 문제

 - 유한 버퍼 문제 (Bounded Buffer Problem)

2) 공유 데이터베이스 접근 (Readers-Writers Problem)

3) 식사하는 철학자 문제 (Dining Philosopher Problem)

 

---

2. 생산자 소비자 문제 (Producer - Consumer Problem)

생산자가 데이터를 생산하면 소비자는 생산된 데이터를 소비한다.

예) 컴파일러 > 어셈블러, 파일 서버 > 클라이언트, 웹서버 > 웹클라이언트

컴파일러가 생산한 코드를 어셈블러가 소비해서 실행가능한 오브젝트 코드로 만든다고 볼 수 있다.

1) Bounded Buffer

생산된 데이터는 버퍼에 일단 저장된다.(속도 차이 등의 이유)

현실 시스템에서 버퍼 크기는 유한(=Bounded)하다. 이로 인해 다음과 같은 문제가 발생하게 된다.

- 생산자는 버퍼가 가득차면 더 넣을 수 없다.

- 소비자는 버퍼가 비어있으면 뺄 수 없다.

2) 문제점

유한한 버퍼를 사용하면서 프로세스가 실행불가 또는 count != 0 이라는 잘못된 결과가 나오게 된다. 여기서 count != 0 이라는 의미는 생산된 데이터와 소비된 데이터가 최종적으로 맞지 않는다는 뜻이다.

 

문제가 발생하는 이유는 count, buf[]라는 공통변수를 이용하면서 공통변수에 대한 업데이트가 동시에 이루어지기 때문이다.

즉, 공통변수 업데이트 구간(=임계구역)에 생산자와 소비자가 동시에 진입하기 때문에 문제가 발생한다.

한 예로 생산자가 데이터를 넣은 다음 count++를 하기 전에 context switching이 발생한다면 count의 값은 맞지 않게될 것이다.

3) 해결방법

세마포를 사용해 임계구역에 대한 동시 접근을 방지하면 된다.(=상호배타)

=> 세마포: mutex.value = 1 (# of permit)

      > Buffer에 접근가능한 쓰레드의 개수를 최대 1개로 허용한다음 임계구역을 빠져나올때 풀어준다.

4) Busy-wait

이렇게 세마포를 만들면 정상적으로 동작하여 count = 0 이 출력된다. 그러나 이 방식은 굉장히 비효율적이다.

우리가 운영체제를 사용하는 이유 중 가장 중요한 것은 편리성과 효율성이다.

이 방식에서는 다음과 같은 문제가 존재한다.

    1.버퍼가 꽉찼을때 생산자는 버퍼에 저장공간이 생길때까지 무한히 기다려야 한다.

    2. 버퍼가 비어있을때 소비자는 버퍼에 데이터가 들어올때까지 무한히 기다려야 한다.

=> cpu가 기다리느라 아무 일도 못하는 문제가 발생한다.

 

이역시 세마포를 사용해 위와 같은 busy-wait를 회피할 수 있다.

- 생산자: empty-acquire() // # of permit = BUF_SIZE

- 소비자: full-acquire() // # of permit = 0

자바 코드로 구현한 코드는 다음과 같다.

//버퍼 클래스 생성
class Buffer {
	int[] buf;
	int size;
	int count;
	int in;
	int out;
	Semaphore mutex, empty, full;
	
	Buffer(int size) {
		buf = new int[size];
		this.size = size;
		count = in = out = 0;
		mutex = new Semaphore(1);
		empty = new Semaphore(size);
		full = new Semaphore(0);
	}
	
	void insert(int item) {
		/* buf is not full */
		try {
			empty.acquire();
			mutex.acquire();
			///////////////////////////////////
			//critical section
			buf[in] = item;
			in = (in+1)%size;
			count++;
			///////////////////////////////////
			mutex.release();
			full.release();
		} catch (InterruptedException e) {}
	}
	
	int remove() {
		/* buf is not full */
		try {
			full.acquire();
			mutex.acquire();
			///////////////////////////////////
			//critical section
			int item = buf[out];
			out = (out+1)%size;
			count--;
			mutex.release();
			empty.release();
			return item;
			///////////////////////////////////
		} catch (InterruptedException e) {
			return -1;
		}
		
	}
}