아래 내용들은 양희재 교수님의 운영체제 강의를 듣고 정리한 내용입니다.

전통적 동기화 예제

• Classical Synchronization Problems

전통적 동기화 예제

• 1. Producer and Consumer Problem
     – 생산자-소비자 문제
     – 유한버퍼 문제 (Bounded Buffer Problem)
• 2. Readers-Writers Problem
     – 공유 데이터베이스 접근
• 3. Dining Philosopher Problem
     – 식사하는 철학자 문제

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

• 생산자가 데이터를 생산하면 소비자는 그것을 소비
• 예: 컴파일러 > 어셈블러, 파일 서버 > 클라이언트, 웹 서버 >
  웹 클라이언트

Bounded Buffer

• 생산된 데이터는 버퍼에 일단 저장 (속도 차이 등)
• 현실 시스템에서 버퍼 크기는 유한
• 생산자는 버퍼가 가득 차면 더 넣을 수 없다.
• 소비자는 버퍼가 비면 뺄 수 없다

잘못된 결과

• 실행 불가, 또는
• count ≠ 0 (생산된 항목 숫자 ≠ 소비된 항목 숫자)
• 최종적으로 버퍼 내에는 0 개의 항목이 있어야

이유

• 공통변수 count, buf[] 에 대한 동시 업데이트
• 공통변수 업데이트 구간(= 임계구역)에 대한 동시 진입

해결법

• 임계구역에 대한 동시 접근 방지 (상호배타)
• 세마포를 사용한 상호배타 (mutual exclusion)
• 세마포: mutex.value = 1 (# of permit)

Busy-wait

• 생산자: 버퍼가 가득 차면 기다려야 = 빈(empty) 공간이 있어야
• 소비자: 버퍼가 비면 기다려야 = 찬(full) 공간이 있어야

세마포를 사용한 busy-wait 회피

• 생산자: empty.acquire() // # of permit = BUF_SIZE
• 소비자: full.acquire() // # of permit = 0
• 위에서도 봤듯이. 생산한게 없으면 소비자가 안돌게 하고, 버퍼가 가득찼으면 생산을 더이상 못하게 만들기위해 두가지 세마포 생성.

class Test {
	public static void main(String[] arg) {
		Buffer b = new Buffer(100);
		Producer p = new Producer(b, 10000);
		Consumer c = new Consumer(b, 10000);
		p.start();
		c.start();
		try {
			p.join();
			c.join();
		} catch (InterruptedException e) {}
		System.out.println("Number of items in the buf is " + b.count);
	}
}

class Buffer {
	int[] buf;
	int size;
	int count;
	int in;
	int out;
	Buffer(int size) {
		buf = new int[size];
		this.size = size;
		count = in = out = 0;
	}
	void insert(int item) {
		/* check if buf is full */
		while (count == size)
			;
		/* buf is not full */
		buf[in] = item;
		in = (in+1)%size;
		count++;
	}
	int remove() {
		/* check if buf is empty */
		while (count == 0)
			;
		/* buf is not empty */
		int item = buf[out];
		out = (out+1)%size;
		count--;
		return item;
	}
}

/****** 생산자 ******/
class Producer extends Thread {
	Buffer b;
	int N;
	Producer(Buffer b, int N) {
		this.b = b; this.N = N;
	}
	public void run() {
		for (int i=0; i<N; i++)
			b.insert(i);
	}
}
/****** 소비자 ******/
class Consumer extends Thread {
	Buffer b;
	int N;
	Consumer(Buffer b, int N) {
		this.b = b; this.N = N;
	}
	public void run() {
		int item;
		for (int i=0; i<N; i++)
			item = b.remove();
	}
}