TIL 정리_95(동기화 관련 문제(2))

http://www.kocw.net/home/m/search/kemView.do?kemId=1046323

운영체제 강의를 듣고 정리한 내용입니다

 

 

동기화와 관련된 문제

동기화와 관련된 고전적인 문제가 3가지 있다

1. Bounded-Buffer-Problem
2. Readers-Writers Problem
3. Dining-Philosophers Problem

---

3. Dining Philosophers Example 

= 식사하는 철학자 문제(Dining-Philosophers Problem)

 

 

Dining Philosophers Example 코드 

Synchronization variables
semaphore chopstick[5];
//모든 초기값은 1로 가정한다

Phiolsopher i
do {
P(chopstick[i]);
P(chopstick[(i+1)%5]);
...
eat();
...
V(chopstick[i]);
V(chopstick[(i+1) % 5]);
...
think();
...
} while(1);

 

 

> 위 해결코드의 문제점

Deadlock의 가능성이 있다

*Deadlock : 더 이상 아무것도 진행이 안되고 막혀있는 현상

-> 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우가 이에 해당한다

 

 

해결방안

• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 잡을 수 있게 한다
• 비대칭 -> 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.

 

Semaphore를 이용한 해결코드

enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0; //권한을 0으로 설정한다
semaphore mutex = 1;

Philosopher i
do {
pickup(i);
eat(i);
putdown(i);
think();
} while(1);

void putdown(int i) {
P(mutex);
state[i] = thinking;
test((i+4) % 5);
test((i+1) % 5);
V(mutex);
}

void pickup(int i) {
P(mutex);
state[i] = hungry;
test(i);
V(mutex);
P(self[i]);
}

void test(int I) {
if(state[(i+4)%5] != eating && state[i] ==hungry && state[(i+1) % 5] != eating {
state[i] = eating;
V(self[i]);
}
}

 

 

Semaphore의 문제점

• 코딩하기 힘들다
• 정확성의 입증이 어렵다
• 자발적 협력(voluntary cooperation)이 필요하다
• 한 번의 실수가 모든 시스템에 치명적 영향을 끼친다

 

문제점의 예시

V(mutex)

Ctirical Section

P(mutex)

-> Mutual exclusion이 깨진다

 

P(mutex)

Ctirical Section

P(mutex)

-> Deadlock

 

 

Monitor

동시 수행중인 프로세스 사이에서 추상 데이터 타입의 안전한 공유를 보장하기 위한

high-level synchronization construct이다

 

 

Monitor의 특징

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능하다
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다
• Semaphore에서 존재한 자원의 개수를 세고 자원이 있으면 접근하게 하고, 없으면 기다리게 하는 기능이 monitor에서도 필요하기 때문에, 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 사용한다

-> condition x, y;

 

**Condition variable은 wait와 signal 연산에 의해서만 접근이 가능하다

 

 

x.wait();

• x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 중단된다

 

x.signal();

• 정확하게 하나의 중단된 프로세스를 재개한다
• 중단된 프로세스가 없으면 아무일도 일어나지 않는다