Synchronization Problems

Classical Synchronization Problems

여러 전통적인 synchronization 문제가 있다.

 

Semaphore와 mutex는 단지 primitive로, 실제 프로그래밍을 할 때 발생하는 문제에 대해서는 단순히 이용해서는 안되고 응용해야 한다.

• readers and writers problem
• dining-philosopher problem

 

---

Readers and Writers Problem

Critical section에 접근하는 프로세스가 2종류인 상황을 의미한다.

• reader : critical section에 읽기만 가능하다.
• writer : critical section에 쓰기만 가능하다.

 

Race condition은 여러 프로세스가 동시에 한 shared resource에 write 할 때 일어난다.

따라서 reader 들은 동시에 수행을 해도 문제를 발생하지 않으므로 block 하지 않는다.

 

• strict mutual exclusion
  • reader와 writer의 구분 없이 엄격하게 통제하는 것을 말한다.
  • 동시에 여러 read 작업은 할 수 있음에도 막기 때문에 성능이 떨어진다.
• weak mutual exclusion
  • correctness 관점보다는 performance 관점에서 개선된 것이다.
  • 동시에 진행되는 여러 read 작업은 허용한다.

 

해결방법

• first readers-writers problem
  • reader에게 우선순위를 준다.
  • 어떤 reader도 critical section에 들어가있지 않다면 writer가 들어갈 수 있다.
  • writer가 starvation 될 수 있다.
• second readers-writers problem
  • writer에게 우선순위를 준다.
  • writer가 critical section에 들어가기를 기다리고 있으면 reader는 들어갈 수 없다.
  • reader가 starvation 될 수 있다.
  • reader가 많고 writer가 적다면 write의 starvation을 피하기 위해서 second가 더 적합한 방법이다.
• third reader-writer problem
  • reader/writer에게 우선순위를 주지 않는다.
  • 각 작업들이 들어온 순서대로 실행한다.
  • starvation을 겪지 않는다.
  • strict mutual exclusion과 유사하지만, 동시에 reader들이 여러개 들어갈 수 있다.

 

First Readers-Writers Problem

reader에게 우선순위를 주는 것이다.

writer는 unbounded waiting 되고, starvation 되는 문제가 있다.

 

총 3개의 변수가 필요하다.

• 두 개의 semaphore 변수
  • <pre>semaphore S, wrt</pre>
  • 초기값 : S = 1, wrt = 1
• 하나의 int 변수
  • <pre>int readcount</pre> 
  • 초기값 : readcount = 0

 

readcount는 여러 reader가 동시에 critical section에 들어가도록 허락하기 위해 사용한다.

 

semaphore S는 readcount를 보호하기 위한 semaphore이다.

readcount에 대한 race condition을 방지한다.

 

 

Second Reader-Writer Problem

Writer에게 우선순위를 부여한다.

 

Critical section에 들어가기 위해 기다리는 writer가 있으면 reader는 작업하지 못한다.

먼저 들어간 reader가 있다면 그 작업이 끝난 후에 writer를 실행한다.

따라서 reader는 unbounded waiting 되고, starvation을 겪을 수 있다.

 

5개의 semaphore와 2개의 int 변수를 사용한다.

• <pre>Semaphore S1, S2, wrt, rd, wrtpending</pre>
  • 초기값은 모두 1이다.
• <pre>int readcount, writecount</pre>
  • 초기값은 모두 0 이다.

 

---

Dining-Philosopher Problem

각 자리의 왼쪽과 오른쪽에 젓가락이 1개씩 놓여있다.

한 번에 하나의 젓가락만 잡을 수 있다.

두 젓가락을 모두 잡아야만 식사를 할 수 있다.

5자리가 있다면 동시에 밥을 먹을 수 있는 최대 인원은 2명이다.

 

마찬가지로 여러 개의 shared resource가 존재하고, 여러 개의 process 가 존재할 때 위의 문제처럼 생각할 수 있다.

 

Deadlock

간단한 해결방법은 다음과 같다.

그러나 이는 모든 사람이 동시에 오른쪽 젓가락을 들거나 동시에 왼쪽 젓가락을 들었을 때 deadlock에 빠져버린다.

do {
	// entry section
	wait(chopstick[i]);			// 오른쪽 젓가락 잡기
    wait(chopstic[(i+1) % 5]);	// 왼쪽 젓가락 잡기

	// critical section
    ...
    
    // exit section
    signal(chopstic[i]);		// 오른쪽 젓가락 내려놓기
    signal(chopstic[(i+1)%5]);	// 왼쪽 젓가락 내려놓기
    
    ...
} while(1);

 

해결방법

deadlock과 starvation을 피하기 위해서 아래와 같이 할 수 있다.

• 5개의 자리에 4명의 사람만 앉힌다.
  • deadlock을 해결할 수 있다.
  • 그러나 의자 한개를 활용하지 못한다.
• 양쪽 젓가락을 확보할 수 있을 때만 잡기
  • mutex_lock과 mutex_trylock을 이용한다.
  • 한쪽은 잡고 있되, 다른 한쪽은 block을 하지 않고 다른 작업을 함으로써 deadlock을 피할 수 있다.
• asymmetric solution 사용
  • 비대칭 성질을 이용한다.
  • 홀수번자리 사람은 왼쪽부터, 짝수번자리 사람은 오른쪽부터 잡기를 시도한다.
  • 동시에 한쪽 방향을 잡는 것을 방지할 수 있다.