[OS] Ep.10 Synchronization(2)

동기화의 고전 문제 3가지

1. Bounded-Buffer Problem

2. Readers and Writers Problem

• Solution 1
• Solustion 2

3. Dining Philosophers Problem

• Solution 1
• Solution 2

---

1. Bounded-Buffer Problem

N개의 Item을 삽입할 수 있는 Buffer에 여러 생산자(Producer)와 여러 소비자(Consumer)가 접근

생산자(Producer): 하나의 Item을 생산해 Buffer에 저장

• Race Condition
  공유 데이터에 대해 여러 Process가 동시에 접근, 변경을 시도하는 상황
  = Buffer에 대해 여러 Producer가 동시에 Item을 추가하려는 상황

소비자(Consumer): Buffer에서 하나의 Item을 가져옴

• 동작 조건
  Buffer의 상태가 Empty면 대기

여러 생산자, 소비자 중 자신이 버퍼(Critical Section)에 접근하여 생산, 소비할 수 있는가?

produce과정과 consume과정은 모두 Buffer에 쓰는 과정이기에 (Write) 동시에 한 Process만이 Buffer에 접근해야 함.

Bounded-Buffer Problem 구현

Buffer의 구현

• 1차원 배열로 구현
• boolean buffer[n]; 으로 선언
• 초기화
  buffer[0...n-1] = empty;
  

생산자 Operation

• Buffer 배열 중, empty인 index를 찾아 full로 바꿈 (0 -> 1)
• Buffer[m] = full;

소비자 Operation

• Buffer 배열 중, full인 index를 찾아 empty로 바꿈 (1 -> 0)
• Buffer[m] = empty;

Bounded-Buffer Problem Semaphore

문제 해결을 위한 세마포어

• Empty: Buffer 내에 저장할 공간이 있음을 표시
  생산자의 진입을 관리

• Full: Buffer 내에 소비할 아이템이 있음을 표시
  소비자의 진입을 관리

• Mutex: Buffer에 대한 접근을 관리
  생산자, 소비자가 empty, full 세마포어를 진입한 경우, buffer의 상태 값을 변경하기 위한 세마포어
  (버퍼에 쓸 공간이 있더라도 누가 이미 쓰고 있을 때를 위해서...)

초기값

Full = 0
Empty = n 		//buffer에 empty인 entry가 n개 (Counting Sem) 
Mutex = 1

생산자 Process

do {
	...
    produce an item in nextp
    ...
    P(empty);	// 버퍼에 적어도 하나의 공간이 생기기를 기다림
    P(mutex);	// Critical Section에 진입하기 위해 기다림
    ...
    add nextp to buffer
    ...
    V(mutex);	// Critical Section에서 빠져 나왔음을 알림
    V(full);	// 버퍼에 아이템이 있음을 알림
} while(True); 

empty는 n으로 init... => 버퍼의 n칸이 모두 비어있다.

소비자 Process

do {
	P(full); 	// 버퍼에 적어도 하나의 아이템이 들어가기를 기다림
    P(mutex);
    remove an item from buffer to nextc
    ...
    V(mutex);
    V(empty);	// 버퍼에 하나의 빈 공간이 생겼음을 알림
    ...
    consume the item in nextc
    ...
} while(True);

full은 0으로 init...

---

2. Readers-Writers Problem

여러 Readers와 Writers가 하나의 공유 데이터를 읽거나 쓰기위해 접근

Readers - 공유 데이터를 읽음

• 여러 Reader는 동시에 Data를 읽을 수 있음

Writers - 공유 데이터에 씀

• Writer가 데이터를 수정하기 위해서는, Reader혹은 다른 Writer가 작업을 하고 있지 않아야 함

Readers-Writers Problem Solution 1

문제 해결을 위한 자료구조와 세마포어

• Int ReadCount: 버퍼에 현재 몇 개의 Reader가 접근중인지 표시
• Semaphore Wrt: Writers 사이의 동기화 관리
• Semaphore Mutex: Readcount와 wrt에의 접근이 원자적으로 수행됨을 보장하기 위한 세마포어

초기값

Mutex = 1
Wrt = 1
readcount = 0

Writer Process

P(wrt);		// entry section
	...
    writing is performed
    ...
V(wrt);		// exit section

Reader Process

P(mutex);
	readcount++;
    if(readcount == 1)
    	P(wrt); 	// 어떤 writer도 수행되고 있지 않음을 판별
        
V(mutex);
	...
    reading is performed
    ...
P(mutex);
	readcount--;
    if(readcount == 0)
    	V(wrt);
V(mutex);

문제점

Writer의 Starvation

• Readcount == 0 일 때만 V(wrt)가 수행되어 P(wrt)로 대기하고 있던 Writer가 수행할 수 있음

• 첫 번째 Reader(Readcount == 1)가 P(wrt)만 통과하면, 다른 Reader들은 P(mutex)에 대한 P(mutex)만 기다리면 언제든지 수행할 수 있기 때문에 Writer와 상관없이 진입할 수 있음

• 여러 Reader들이 계속해서 진입할 경우, Readcount는 0까지 떨어지지 않을 수 있음

Writer의 Starvation을 예방하는 Solution이 존재함

• Writer process에 우선순위를 부여

Readers-Writers Problem Solution 2

Writer의 Starvation을 해결한 방법

3. Dining-Philosophers Problem

고전적인 Concurrency Method

5명의 철학자가 한 식탁에서 함께 식사를 하는 상황

젓가락이 5개뿐

• 자신의 바로 옆 젓가락만 집을 수 있음
• 두 젓가락을 모두 집어야 식사를 할 수 있음
• 식사를 하고 난 다음에야 두 젓가락을 모두 내려놓을 수 있음

Deadlock과 Starvation이 발생하는 경우

• 모두 자신의 오른쪽(혹은 왼쪽) 젓가락을 집었을 경우

Dining-Philosophers Problem Solution 1

단순히 젓가락을 집는 것에 대한 동기화를 부여하는 방법

• 모든 철학자가 자신의 왼쪽 또는 오른쪽 젓가락부터 집도록 한다.
• boolean waiting[n];

세마포어

• chopstick[5]: 각각의 젓가락에 대한 동기화 관리

초기값은 모두 1

철학자 Process

do {
	...
    think
    ...
    P(chopstick[i]);				// 왼쪽을 잡을 수 있는가
    P(chopstick[(i + 1) % 5])		// 오른쪽을 잡을 수 있는가
    ...
    eat
    ...
    V(chopstick[i]);
    V(chopstick[(i + 1) % 5]);
    ...
} while(True);

동시에 chopstick을 잡으면 deadlock 발생
-> 모두가 왼쪽을 잡으면... (= P(chopstick[i]); 이후에...)

0번이 자신의 왼쪽 젓가락을 든 이후에 Deadlock에 빠졌다
(= 모든 철학자들(프로세스들)이 자신의 왼쪽 젓가락을 들었다)

Dining-Philosophers Problem 개선안

Deadlock의 해결 방안

• 한 번에 최대 4명의 철학자만 식탁에 앉도록 한다
• 젓가락의 상태를 미리 검사하여, 양 쪽의 젓가락이 모두 사용 가능할 때만 젓가락을 집도록 한다.
• 철학자에게 번호를 부여하여 홀수인 철학자는 왼쪽의 젓가락을, 짝수인 철학자는 오른쪽의 젓가락을 먼저 집도록 한다.

위의 해결방안들은 Starvation까지 해결해주지는 못함

• 각각의 방안에 대해 Starvation에 대한 고려를 추가할 수 있음
  ex) 한 차례 굶은 철학자에게 우선권을 줌

Dining-Philosophers Problem Solution 2

양 쪽의 젓가락을 한꺼번에 집는 방법

• 젓가락의 상태를 미리 검사하여 양 쪽의 젓가락이 모두 사용할 때만 젓가락을 집도록 하는 방법

사용되는 자료구조

• State[5]: 각 철학자의 상태를 기록 (THINKING, HUNGRY, EATING)

문제 해결을 위한 세마포어

• mutex : 젓가락을 집거나 놓는 수행을 Critical Section으로 관리하기 위한 세마포어
  초기값 = 1

• self[5] : 철학자 각각이 젓가락 두 개를 잡기를 기다리는 세마포어
  초기값 = 모든 원소가 0
  self[i] 의미는 철학자i가 HUNGRY 상태이더라도, 다른 젓가락 하나를 사용할 수 없을 경우 Waiting을 하기 위한 세마포어

철학자 Process

do {
	...
   	think
    ...
    take_chopsticks(i);
    ...
    eat
    ...
    put_chopsticks(i);
    ...
} while(True);

take_chopstick(int i){
	P(mutex);
    state[i] = HUNGRY;
    test(i);
    V(mutex);
    P(self[i]);
}

put_chopstick(int i){
	P(mutex);
    state[i] = THINKING;
    test(LEFT);
    test(RIGHT);
    V(mutex);
}

test(int i) {
	if(state[i] == HUNGRY &&			// 내가 배고프고 양쪽이 먹고 있지 않은(NOT EATING) 상태일 때
    	state[LEFT] != EATING &&
        state[RIGHT] != EATING){
			state[i] = EATING;
            V(self[i]);
    }
}

take_chopstick() : Mutex를 통해 진입하여, test(i)를 통해 양쪽의 철학자 상태를 검사한 후, 자신이 먹을 차례를 기다린다.

put_chopstick() : Mutex를 통해 진입하여, test(LEFT), test(RIGHT)를 통해 양쪽의 철학자 상태를 검사한 후, 먹을 차례를 기다리는 철학자에게 signal을 보내준다.

test() : Test를 수행한 철학자(i)가 HUNGRY 상태이고, 양쪽의 철학자가 모두 젓가락을 집지 않은 상태 (NOT EATING)이면 take_chopsticks()에서 wait했던 자신의 세마포어 self[i]에 signal을 보내어 EAT으로 진행하도록 함

해설

Solution 2의 전략은 철학자 좌우 젓가락이 사용 가능할 때만 Critical Section에 진입함

• i 번째 철학자가 식사를 하기 위해서는 i-1 (LEFT)와 i+1 (RIGHT) 철학자가 EATING 상태가 아니어야 함

take_chopstick()와 put_chopstick()의 동작을 살펴보자

take_chopstick()

식사할 조건

• test() 함수 안에서 검사하는 LEFT와 RIGHT의 상태가 EATING이 아니어야 함

• test()를 만족하면, signal(self[i])에 의해 self[i]의 값은 1이 되므로, wait(self[i])에서 block되지 않고 식사를 진행한다.

self[i]의 초기 값은 0임

put_chopstick()

식사를 마치면, 좌 우 철학자의 test()함수를 실행한다.

• 이 때, 철학자 L과 R은 i에 의해 take_chopstick()에서 wait()함수에 의해 대기 중

• 철학자 i에 의해 실행한 test(LEFT)
  i와 LL의 상태를 확인

• 철학자 i에 의해 실행한 test(RIGHT)
  i와 RR의 상태를 확인

• 철학자 i가 식사중인 동안 LL 혹은 RR 철학자의 상태가 EATING으로 바뀐다 하더라도, test(LEFT)와 test(RIGHT)를 통해 signal을 수행하므로 동기화에 문제가 없다.

체크 요소들

Data Consistency가 확보되는지

Deadlock이 발생하는지

Starvation 가능성이 있는지

Concurrency를 얼마나 제공하는지