deadlock 4가지

▶ Conditions for deadlock 

1. Mutual exclusion condition : Each resource is either currently assigned to exactly one process or is available.
2. Hold and wait condition : Processes currently holding resources granted earlier can request new resources.
3. No preemption condition : Resources previously granted cannot be forcibly taken away from a process.

                                        They must be explicitly released by the process holding them.
4. Circular wait condition : There must be a circular chain of two or more processes,

                                      each of which is waiting for a resource held by the next member of the chain.

▶ Dining Philosophers Problem

Each lawyer needs two chopsticks to eat. Each grabs chopstick on the right first.
What if all grab at the same time? Deadlock.

 

+

철학자들은 원형테이블을 공유하며, 이 테이블은 가가 한 철학자에 속하는 5개의 의자로 둘러 싸여 있다. 테이블 중앙에는 한사발의 밥이 있고, 테이블에는 다섯개의 젓가락이 놓여있다.   - 철학자가 생각할때는 다른 동료들과 상호작용하지 않는다. - 철학자는 배가고프면 자신에 가장 가까이 있는 두개의 젓가락을 집으려고 시도한다.    (이미 옆사람의 손에 들어간 젓가락은 집을 수 없다.) - 식사중에는 젓가락을 놓지않고, 식사를 마치면 젓가락 두개를 모두 놓고 다시 생각을 시작한다.

- 교착상태(deadlock)가 발생하는 4가지 필요조건에 '식사하는 철학자 문제'에 적용해보자.

 

철 학자는 배가고프면 자신에게 가까운 양쪽의 젓가락을 집어야한다. 하지만 옆의 다른 철학자가 이미 젓가락을 집어서 사용하고 있다면 그 젓가락은 이미 쓰고 있는 철학자만이 공유되지 않고 사용할 수 있기 때문에 배고픈 철학자는 옆의 철학자가 식사를 마치고 젓가락을 놓을 때까지 기다려야한다.

이것은 상호배제(mutual exclusion) 조건으로 최소한 하나의 자원이 비공유 모드로 점유되어 어느 자원에 대해 한 프로세스가 이미 사용중이면 다른 프로세스는 기다려야 하는 것을 보여준다.

또한 배고픈 철학자는 자신의 양 옆중 놓여있는 젓가락을 사용하기위해 하나 집고 다른 철학자가 쓰고 있는 다른 하나의 젓가락을  식사가 끝마쳐져서 놓여지기를 기다리는 경우는, 점유와 대기(Hold and wait) 조건으로  하나 이상의 자원을 할당받은 채로 나머지 자원을 할당 받기 위해 다른 프로세스의 자원이 해제되기를 기다리는 프로세스가 존재하는 경우이다.

젓가락은 미리 선점할 수 없는데, 즉 젓가락을 집고 있는 중 강제로 방출할 수 없다. 식사를 마친 철학자가 젓가락을 자발적으로만 놓을 수 있는 것이다. 이것은 자원을 할당받은 프로세스로부터 자원을 강제로 빼앗지 못하는 비선점(Nopreemption) 조건이다.

마지막으로, 철학자1은 철학자2가 가지고 있는 젓가락을 내려놓기를 기다리고 있고, 철학자2는 철학자3을, 철학자3은 철학자4를, 철학자4는 철학자5를,철학자5는 철학자1의 젓가락을 기다린다면 이것은 자원 할당 그래프 상에서 프로세스의 환형 사슬이 존재하는 것으로 순환대기(circular wait) 조건이다.

이 4가지 조건이 동시에 성립된다면 교착상태가 발생할 것이다.

 

- '식사하는 철학자 문제'에서 기아상태가 발생하는 경우.

 

 철학자들은 식사를 하기 위해서 반드시 양쪽의 젓가락을 들어야한다.

 위의 그림을 참고해서 보면, 철학자1과 철학자4가 식사를 시작하면, 철학자5는 식사를 하지못하고, 철학자2와 철학자4가 식사를 시작하게 되면 철학자3이 식사를 하지못하는 무한정 대기상태인 기아상태가 발생하게 된다.