전통적 동기화 예제 (3) 식사하는 철학자 문제

1. Dining Philosopher Problem

1) 식사하는 철학자 문제

5명의 철학자와 5개의 젓가락이 있다고 가정해보자. 철학자는 생각 → 식사 → 생각 → 식사 과정을 반복한다.

철학자는 자신의 왼쪽 젓가락을 집고, 오른쪽 젓가락을 집어야만 식사가 가능하다.

식사하는 철학자 문제

젓가락을 세마포로 구현하면 프로그램으로 구현할 수 있다. (# of permit = 1)

젓가락은 왼쪽 젓가락을 먼저 사용하고, 오른쪽 젓가락을 나중에 사용해서 철학자가 식사할 수 있도록 구현한다.

 

2) 잘못된 결과 도출 : starvation

실제로 이를 프로그램으로 구현하면 모든 철학자가 식사를 하지 못해 굵어죽는 상황이 발생한다.

즉, 도중에 프로그램이 멈추는 현상이 계속해서 발생하게 된다. 이러한 현상이 발생하는 이유는 교착상태(deadlock) 때문이다.

종종 모든 철학자가 식사를 하기 위해 왼쪽 젓가락을 집게 되면 오른쪽 젓가락은 누군가 사용 중이므로 무한히 대기하는 현상이 발생하게 된다.

 

2. 교착 상태(Deadlocks)

프로세스는 실행을 위해 여러 자원을 필요로 한다. (ex. CPU, 메모리, 파일, 프린터)프로세스는 어떤 자원은 갖고 있으나 다른 자원은 갖지 못할 때(ex. 다른 프로세스가 사용중일때) 대기해야 한다.다른 프로세스 역시 다른 자원을 가지려고 대기할 때 교착상태에 빠질 가능성이 생기게 된다. => 무한대기

 

1) 교착상태 필요조건 (Necessary Conditions)

  - 상호 배타 (Mutual exclusion)

  - 보유 및 대기 (Hold and wait)

  - 비선점 (No Preemption)

  - 환형대기 (Circular wait)

=> 이 4가지 조건이 모두 만족되어야 교착 상태가 발생할 수 있다.

 

3. 자원 (Resources)

동일 형식(type) 자원이 여러개 있을 수 있다. 이 경우 각각의 자원을 인스턴스(instance)라 부른다. (ex. 동일 cpu 2개, 동일 프린터 3개 등)

요청(request) → 사용(use) → 반납(release) 순으로 자원을 사용한다.

 

1) 자원할당도 (Resource Allocation Graph)

  - 어떤 자원이 어떤 프로세스에게 할당되었는가?  - 어떤 프로세스가 어떤 자원을 할당받으려고 기다리고 있는가?이 두가지를 자원할당도를 통해 간단하게 나타낼 수 있다.

자원할당도 예시

  - R1이라는 자원은 P1에게 할당되어져 있다.

  - P2라는 프로세스가 R1이라는 자원을 사용하려고 요청 중에 있다. (=대기 중에 있다.)

이 2가지 의미를 위 예시가 내포하고 있다.

 

교착 상태가 만들어지려면 자원할당도 상에 원이 만들어져야 한다.(=환형 대기)

그러나 환형대기가 만들어진다고 해서 꼭 교착상태에 빠지는 것은 아니다.(=충분조건은 아니다.)

 

식사하는 철학자 문제에서 환형대기가 만들어지지 않게 하려면 간단한 방법으로 짝수 철학자는 왼쪽 → 오른쪽으로 젓가락을 집고, 오른쪽 철학자는 오른쪽 → 왼쪽 방향으로 젓가락을 집도록 만들면 된다.