Dining philosopher problem,식사하는 철학자 문제 [운영체제]

[컴퓨터(Computer Science)/운영체제(Operation System)] - 동기화, 세마포 : Synchronization, Semaphores [운영체제]

[컴퓨터(Computer Science)/운영체제(Operation System)] - 동기화, 모니터 : Synchronization, Monitor [운영체제]

 

세마포나 모니터에 대한 사전 지식을 바탕으로 설명한다.

 

---

 

유명한 문제인데 컴퓨터랑 많이 결부지어서 언급되고는 한다.

CPU의 병행 제어 문제 중의 하나로 중요하기 때문이다.

 

 

설명해보자면

 

우선 5명의 철학자들이 둘러앉아 있고 생각한다.

원형 테이블을 공유하며, 테이블 중앙에는 밥이 있다.

또한 철학자들은 서로 상호 대화, 행동 일절 금지이다.

만약 배고파진다면 자신의 왼쪽에 있는 젓가락과 오른쪽에 있는 젓가락으로 식사를 할 수 있다.

다만 누가 이미 쓰고있을 때는 젓가락을 사용하지 못한다.

+젓가락은 한 번에 한 쪽만 집을 수 있다.

젓가락을 2개 집게 되었을 경우 식사를 할 수 있다.

식사를 마치면 젓가락 2개를 모두 놓고 다시 생각한다.

 

 

교착과 기아가 생기지 않게 하는 방법을 생각해보자.

(Deadlock, Starvation)

굶어 죽어서도 안되고 교착상태가 있어도 안된다. 

**굶는 것을 기아(starvation)이라고 한다.

 

---

 

 

Semaphore Soultion, 세마포 해결방법

 

 

각 젓가락을 하나의 세마포로 표현해서 해결한다.

철학자는 세마포에 wait() 연산을 실행하여 젓가락을 집으려고 한다.

또한 signal()연산을 실행해서 젓가락을 놓는다. 

그래서 이렇게 표현 가능하다

 

 

철학자의 구조는 이렇게 된다.

 

 

하지만 위의 해결법은 교착 상태(deadlock)을 야기할 가능성이 크다.

드디어 세마포로 해결안되는 경우가 생겼다.

사실 해결이 안된다기보다 기존의 방법에 조건을 더해야 가능해진다.

 

우선

5명의 철학자가 다같이 배고파서 다같이 동시에 자신 왼쪽의 젓가락을 잡는다면?

chopstick의 모든원소는 0이 된다.

철학자는 오른쪽 젓가락을 영원히 잡을 수 없다.

Deadlock이 발생한다.

 

또한

가운데 사람이 껴서 양쪽의 사람만 밥을 먹고

가운데 사람은 밥을 먹지 못하는 Starvation이 생길 수도 있다.

 

 

그래서 생각해낸 deadlock 해결방법이 또 있는데

아래의 조건을중 하나를 추가한다면 가능한다.

 

1. 최대 4명의 철학자만이 테이블에 동시에 앉을 수 있게 한다

2. 한 철학자가 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 한다.

3. 비대칭 해결안을 사용한다.

ex) 홀수번째 철학자는 왼쪽 젓가락부터 집어야하고 짝수번째 철학자는 오른쪽 젓가락부터 집어야한다.

 

 

---

 

 

다른 해결 방안으로 

Monitor Solution, 모니터 해결 방안이 있다.

 

이 해결방법은 "철학자는 양쪽 젓가락 모두 얻을 수 있을 때만 젓가락을 집을 수 있다" 는 조건이 지켜져야 한다.

 

이 해결안을 구현하려면 3가지의 상태를 구별할 수 있어야 한다.

 

그래서 이렇게 나오는데

 

enum { Thinking, Hungry, Eating} state [5]; 

 

철학자 i는 양쪽 철학자가 식사하지 않을 때만 변수 state[i] = Eating으로 상태가 설정 가능하다.

다시 말해서 state[ (i+4) % 5] != Eating && state[(i+1) % 5] != Eating 인 조건에서 가능하다는 얘기다.

 

그것을 위해서 cindition self[5]; 를 선언해야 한다.

 

self는 철학자 i가 배고프지만 자신이 원하는 젓가락을 집을 수 없을 때 젓가락 집기를 미룰 수 있게 해준다.

 

 

결국 젓가락의 분배는 모니터 DIningPhilosophers에 의해 제어된다.

 

이 모니터의 정의를 보자

 

 

 

철학자들은 식사하기 전에 pickup() 연산을 호출해야한다. 

 

이 연산은 프로세스의 일시 중지를 야기할 수 있다. 그렇지만 연산이 성공적으로 끝나면, 식사할 수 있다.

식사를 하고 난 후 철학자는 putdown()을 호출한다.

 

철학자들은 반드시 pickup()과 putdown() 연산을 순서대로 호출해야한다.

 

이 해결방법도 이웃한 두 철학자가 동시에 식사하지 않는다는 것과 교착상태가 발생하지 않는다는 것을 보장한다는 것을 보이기는 쉽지만...?

 

이 해결방법 또한 굶어죽을 수 있다.

 

---

 

모니터를 이용한 것을 세마포로 바꾸면 이렇게 구현이 된다.

 

철학자의 상태를 나타내는 변수 state[5]가 있다.

** 먹거나, 생각하거나, 배고프거나 3가지 상태

 

세마포 변수가 2개가 있고

self[5]  크기가 5인 배열 하나(젓가락 2개를 점유하는지)

**self[3] = 1이면 4번째 철학자가 젓가락 2개를 잡을 수 있는 권한이 있다.

**초기값은 0으로 권한 없이 시작한다.

 

mutex 철학자 본인만 상태를 바꾸는 것이 아니라 옆의 철학자도 상태를 바꿀 수 있기 때문에 공유 변수가 되고lock을 걸어야 한다.

 

 

pickup의 경우 젓가락을 집는 작업이다.

mutex를 걸어 

자신의 상태를 hungry로 바꾸고

현재 해당 철학자가 젓가락 2개를 다 잡을 수 있는지 test를 해본다.

 

test함수에서는 젓가락 2개를 다 잡을 수 있는지를 주변 철학자 상태로 파악한다.

내 양옆의 철학자가 밥을 먹지 않고, 내가 배고픈 상태면 

나의 상태를 먹는 중으로 바꿀 수 있다.

test가 끝나면 mutex lock을 풀고

self[i]를 0으로 만들어 젓가락을 반납한다.

 

 

putdown에서는

나의 상태를 다시 thinking으로 바꾸고내가 젓가락을 점유하고 있어서  주변 철학자들이 배고픈데 나를 기다리느라 못먹고 있는지를 test한다.

즉, 젓가락을 내려놓을 때 주변 철학자들을 수행하게 할 수 있다.