[운영체제] 공룡책🦖 ch07. Synchronization Examples

Reference

1. Abraham Silberschatz, Greg Gagne, Peter B. Galvin - Operating System Concepts (2018)

2. Operating System class by Professor Sukyong-Choi at Korea University 

3. 혼자 공부하는 컴퓨터구조 + 운영채재 (강민철)

중요한 내용 위주로 요약 && 정리했습니다.

 

7.1 Classical Problems of Synchronization

concurrency-control problems

1. Bounded-Buffer problem (유한 버퍼 문제)
2. Readers and Writers Problem (읽기 쓰기 문제)
3. Dining-Philosophers Problem (식사하는 철학자 문제)

 

7.1.1 The Bounded-Buffer Problem

semaphore를 이용하여 문제를 해결한다. (자세한 내용은 ch6 참고)

int n;                    // 총 buffer의 수
semaphore mutex = 1;      // 이진 세마포, 초기값 1, buffer pool에 대한 상호 배제 제공
semaphore empty = n;      // 빈 buffer의 수
semaphore full = 0;       // 꽉 찬 buffer의 수

 

7.1.2 The Readers-Writers Problem

공유되는 DB에서 readers 와 writers process가 있을 때, reader는 동시 접근이 가능하지만, writer는 동시 접근 시 문제가 된다.

따라서 writer는 쓰기 시 exclusive access를 해야 한다!

(1) 우선 순위를 활용

1. first readers-writers problem reader에게 우선 순위를 준다. ⇒ writer에서 starvation 발생 가능
2. second readers-writers problem
3. writer에게 우선 순위를 준다. ⇒ reader에서 starvation 발생 가능

⇒ 두 case 모두 starvation이 발생한다. ⇒ semaphore를 이용하여 문제 해결

(2) first readers-writers problem with semaphore

semaphore rw_mutex = 1;  //초기값1, mutual exclusion for writers
semaphore mutex = 1;     //초기값1, mutual exclusion for read_count
int read_count = 0;      //초기값0, # of reading process

• mutex : reader 프로세스 수를 처리
• rw_mutex : CS에 처음 들어가거나 마지막으로 나오는 reader가 사용한다. 다른 reader가 CS에 있다면, CS에 enter/exit 시 reader는 사용 안 함

(3) Reader-writer locks

• lock 요청 시 mode를 지정
• read mode에서는, 여러 process가 동시에 lock 획득 가능
• write mode에서는, exclusive access를 위해 한 process만 lock을 획득함

 

7.1.3 The Dining-Philosophers Problem

원탁에 다섯 명의 철학자가 앉아 있다. 이 철학자들은 앞에 식사가 있고, 철학자들 사이에는 식사에 필요한 젓가락 한 개가 놓여있다. 그리고 철학자들 앞에 있는 식사는 두 개의 젓가락으로 먹을 수 있다.

그리고 이 철학자들은 아래와 같은 순서로 식사를 한다.

1. 생각을 하다가 왼쪽 젓가락 가 사용 가능하면 집어든다.
2. 생각을 하다가 오른쪽 젓가락 가 사용 가능하면 집어든다.
3. 왼쪽과 오른쪽 젓가락를 모두 집어들면 정해진 시간동안 식사를 한다.
4. 식사가 끝나면 오른쪽 젓가락를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 젓가락를 내려놓는다.
6. 다시 1번부터 반복한다.

이 경우, 한두 명의 철학자가 식사하는 것은 문제없지만, 모든 철학자가 동시에 젓가락을 집어 식사를 하면 어떠한 철학자도 식사를 할 수 없고 영원히 생각만 하게 된다.

모든 철학자가 왼쪽 젓가락을 들면 모든 철학자가 오른쪽 젓가락을 들 수 없기 때문이다.

여기서 철학자 = process , 젓가락 = resource 이다.

자원 할당 그래프를 그리면 아래와 같다.

 

7.1.3.1 Semaphore solution

semaphore chopstick[5];
while (true) {
	wait(chopstick[i]);
	wait(chopstick[(i+1) % 5]);
		...
	/* eat for a while */
		...
	signal(chopstick[i]);
	signal(chopstick[(i+1) % 5]);
		...
	/* think for awhile */
		...
}

⇒ 각 젓가락을 semaphore로 만든다.
⇒ wait()를 통해 젓가락을 집어 든다. && signal()을 통해 젓가락을 내려 놓는다.
⇒ 두 이웃한 철학자가 동시에 식사하지 않음을 보장
⇒ 하지만 deadlock 발생 가능 (5명의 철학자가 동시에 왼쪽 젓가락을 잡는 경우 남은 젓가락은 0개이고, 오른쪽 젓가락을 잡으려고 할 때 영원히 대기하게 된다.)

해결방법

(1) 최대 4명만 동시에 앉는다.

(2) 양쪽 젓가락이 가용할 때만 집도록 허용

(3) 비대칭 방법, 홀수 / 짝수 번호별로 다르게 동작

 

7.1.3.2 Monitor Solution

• 젓가락이 둘 다 가용할 때만 집도록 한다.
• 철학자의 상태를 3가지로 구분

enum {THINKING, HUNGRY, EATING} state[5];

• 이웃들이 Eating이 아닐 때 Eating 상태가 될 수 있다.

(state[(i+4) % 5] != EATING) and (state[(i+1) % 5] != EATING)

• 배고프지만 원하는 젓가락을 잡을 수 없을 때 delay하기 위한 condition을 정의한다.

condition self[5];

• monitor인 DiningPhilosopher에 의해서 젓가락의 분배가 이뤄진다.

DiningPhilosophers.pickup(i);
	...
	eat
	...
DiningPhilosophers.putdown(i);

• 이웃한 두 사람이 동시에 식사하지 않고 deadlock이 일어나지 않음을 보장한다.
• 하지만 starvation이 발생할 수 있다.