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

식사하는 철학자들

 

철학자들은 배고프면 식사를 하고 식사를 마쳐서 배가 부르면 사고를 한다.

철학자들 양 옆에는 포크가 놓여져 있고 식사를 하기 위해선 양 옆의 두 개의 포크를 이용해야 한다.

 

 

 

 

철학자들이 식사를 하는 방법은 다음과 같다.

 

-> 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다

-> 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.

-> 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.

-> 오른쪽 포크를 내려놓는다.

-> 왼쪽 포크를 내려놓는다.

-> 다시 1번으로 돌아간다.

 

식사를 하기 위해 어떤 포크를 집어 든다면 그 포크는 다른 철학자가 접근하지 못한다.

- 포크 = 임계 자원(상호 배제를 만족해야 함)

 

 

위의 조건을 지키면서 작업을 수행하는 코드는 다음과 같다.

 

 

fork는 세마포어 변수로 5개가 존재해야 하고 하나의 포크를 사용할 수 있는 프로세스는 하나이므로 1로 초기화

철학자들의 번호는 i로 인덱싱하고 사고와 식사를 반복하는데,

양 옆에 존재하는 포크 번호를 i와 i+1로 접근한다. (mod 5 는 5번 철학자가 0번째 포크에 접근하기 위함)

 

접근하려는 fork번호가 다른 철학자에 의해 사용되고 있다면 그 철학자는 block되고,

식사가 끝난 철학자는 signal로 사용한 fork를 깨워 다른 철학자들에 의해 사용되게 한다.

 

여기서 만약에 모든 철학자가 식사를 하기 위해 자신의 왼쪽 포크를 들고 있다고 있다고 가정하면,

자신의 오른쪽 포크를 사용할 수 없기 때문에 모든 철학자가 block되어 Deadlock상태가 발생할 것이다.

 

 

Dead lock의 해결법

 

무시 (Ignoring)

 - 아래 방법들은 다 오버헤드가 있기 때문에 교착상태 발생 확률이 매우 낮으면 무시하는 방법도 있음

예방 (Prevention)

- 구조적으로 교착상태가 일어나지 않도록 강제

 

회피 (Avoidance)

- allocation을 요청했을 때, deadlock이 발생할 수 있는 경우 거부

- 미래의 request 정보들까지 알고 있어야 함

 

탐지, 복구 (Detection & Recovery)

- 교착상태를 따로 막지 않고, 대신 주기적으로 교착상태 발생 여부를 체크함

- 교착상태 발생 시 rollback, preemption을 해야 함

 

 

교착상태 예방 (prevention)

교착상태 발생을 예방하려면 교착상태의 필요조건 중 하나가 일어나지 않도록 강제해야 한다.

 

상호배제 - 상호 배제를 강제하면 race condition이 발생하여 불가능

 

보유 및 대기 - Request all at once: 자원을 전부 한번에 받도록 만듦

 

환형 대기 -  Resource Ordering: 자원의 순서를 정의

 

 

 

식사하는 철학자의 Deadlock 해결법

 

 

식사할 수 있는 테이블에 4명만 존재하게 하게끔 세마포어 변수인 room을 초기화 한다.

 

-> while문 안을 수행할 수 있는 프로세스(철학자)가 4명이므로 cycle이 발생하지 않음.

 

하지만 5명의 철학자가 동시에 식사나 사고를 하지 못하기 때문에 cuncurency(동시성) 관점에서 손해가 발생

 

 

해결법 2 Deadlock의 조건 중 하나를 제약

 

 

hold wait(점유 대기)

를 없애려면 여러 필요한 자원을 동시에 요청해야함

-> 양 옆의 포크를 한번에 접근해서 사용 가능하다면 점유하고 하나라도 사용하지 못한다면 둘 다 사용하지 않음

 

sucular wait(순환 대기)

를 없애려면 해당 자원을 사용하는 프로세스의 순서를 지정해야함(resource ordering)

-> 포크에 번호를 1, 2, 3, 4, 5로 붙이고(linear) 작은 포크 먼저 집고 큰 포크를 그 다음에 집도록 만들면 자연스럽게 순환 대기가 없어짐