운영체제 ch 7. Synchronization Examples

Classical Problems of Synchronization

 

Bounded-Buffer Problem

• Producer, Consumer - Buffer의 full / empty, same slot에 접근
• 3개의 Semaphore (n개의 buffer)
  • Semaphore mutex : 같은 영역에 Producer, Consumer 중 하나만 접근하도록 만들어주는 semaphore, 초기화 : 1
  • Semaphore full : 버퍼가 꽉 차있는지를 나타냄, 초기화 : 0
  • Semaphore empty : 빈 슬롯을 나타냄, 초기화 : n

full = 0, empty = n, mutex = 1

 

Producer

do { 
		... 
	/* produce an item in next_produced */ 
		... 
	wait(empty);	// 빈 공간 하나를 줄임 (empty가 0이면 멈춰있게 됨)
	wait(mutex); 	// 그 자리에 자료를 채움 (Consumer가 같은 데이터에 접근하면 기다려야 함)
		... 
	/* add next produced to the buffer */ 
		... 
	signal(mutex);	// 빠져나가면 signal
	signal(full);	// 공간을 채워 full + 1
} while (true);

Consumer

Do {
	wait(full);		// Consumer가 소비할 것 없다면 멈춰있음
	wait(mutex);	// Producer가 먼저 들어오면 기다려야 함
		...
	/* remove an item from buffer to next_consumed */
		...
	signal(mutex);	// 빠져나가면 signal
	signal(empty);	// 빈 공간이 생겨 empty + 1
		...
	/* consume the item in next consumed */
		...
} while (true);

 

If → Consumer의 순서가 바뀐다면?

// Consumer

wait(mutex);	// Consumer가 먼저 CPU를 받으면 그대로 내려감 (Producer가 접근하지 않았으므로)
wait(full);		// full = 0 이므로 멈춰있게 됨

// Producer

wait(empty);	// empty = n이므로 하나를 줄여 n-1이 되고 밑으로 내려감
wait(mutex);	// Consumer가 먼저 접근했으므로 멈춰있게 됨 → deadlock

 

 

Readers and Writers Problem

• reader : 읽기만 하고 데이터 업데이트는 수행하지 않음
• writer : 읽기와 쓰기 모두 가능
• multiple reader, single writer
• writer와 writer, writer와 reader는 섞이면 안 됨
  • writer와 writer : 서로 같은 파일인데 다른 내용을 가질 수 있게 됨 (writer는 최근에 수정된 내용을 똑같이 가지고 있어야 함!), recovery 할 때 블락이 수정된 순서대로 진행되어야 함 → 한 번에 한 writer만 공유 데이터에 접근 가능하게 해야 함
  • writer와 reader : reader가 데이터를 읽는 동안 writer가 들어와서 수정할 경우 reader가 일부 수정된 데이터를 읽을 수 있어 문제가 생김
• reader는 데이터를 수정하지 않으므로 한 번에 여러 reader가 접근해도 됨
• 만약 writer가 수행하며 writer가 계속 들어온다면 reader의 starvation 문제 발생
• 만약 reader가 수행하며 reader가 계속 들어온다면 writer의 starvation 문제 발생
• 두 개의 semaphore 필요
• 공유 데이터
  • Data set
  • Semaphore rw_mutex
    • reader, writer가 섞이지 못하도록 만들어주는 semaphore
    • 초기에는 1로 초기화
  • Semaphore mutex
    • reader가 다 끝난 다음에 writer가 수행하도록 하는 semaphore
    • reader들이 read_count를 수정할 때 사용해야 하는 semaphore로 언제 writer가 들어올 수 있는지 확인해줌
    • read_count는 한 번에 한 reader가 수정해야 함, 하나 읽을 때마다 증가하여 한 번에 한 reader만 수정하게 함
    • 맨 처음 reader의 read_count = 1, 맨 마지막 reader의 read_count= 0
    • 초기에는 1로 초기화
  • Integer read_count = 0으로 초기화

 

writer

do {
	wait(rw_mutex);
		...
	/* writing is performed */	// 한 번에 한 writer만 수행
		...
	signal(rw_mutex);

} while (true);

reader

do {
	wait(mutex);	// 다른 reader가 접근하지 못하도록 막아줌 (read_count 수정)
	read_count++;	
	if (read_count == 1)	// 첫 번째 reader인 경우
		wait(rw_mutex);		// writer가 접근하지 못하도록 막아줌
	signal(mutex);			// read_count 수정이 끝나고 signal
		...
	/* reading is performed */
		...
	wait(mutex);			// 다른 reader가 접근하지 못하도록 막아줌 (read_count 수정)
	read count--;
	if (read_count == 0)	// 마지막 reader인 경우
		signal(rw_mutex);	// 기다리고 있는 writer를 signal 시켜줌
	signal(mutex);			// 동기화를 위한 mutex signal 시켜줌
} while (true);

• First variation – writer가 공유 데이터를 사용할 수 없다면 reader가 대기하지 않음 → reader가 계속 들어올 때 writer의 starvation 발생 가능
• Second variation – writer가 준비되면 가능한 한 빨리 write를 수행 → writer가 계속 들어올 때 reader가 기다리므로 starvation 발생 가능
• 일부 시스템에서 문제는 reader-writer locks을 제공하는 커널에 의해 해결

 

Dining-Philosophers Problem

• 5명의 철학자들의 경우 공유 데이터
  • Bowl of rice (data set)
  • Semaphore chopstick [5] → 1로 초기화

Philosopher i

The structure of Philosopher i:
do { 
    wait (chopstick[i] );		// 첫 번째 젓가락 집기
	wait (chopStick[ (i + 1) % 5] );	// 다른 한 쪽을 누가 집게 되면 다 먹을 때까지 기다림
	
		//  eat

	signal (chopstick[i] );
	signal (chopstick[ (i + 1) % 5] );
	
		//  think

} while (TRUE);

아무도 못 먹게 되는 deadlock 문제 해결

1. 한 철학자가 양쪽 젓가락을 집어서 먹은 후, 다음 철학자가 양쪽 젓가락을 집어서 먹는 과정 반복
2. 철학자 수 줄이기

---

 

 

 

 

 

참고 자료 : Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne