[운영체제] Dining Philosophers Problem

오늘은 대표적인 deadlock 문제 중 Dining Philosophers Problem에 대해 알아보겠습니다.

 

n명의 철학자들과 n개의 젓가락이 있습니다. (n쌍이 아니라 n개입니다)

철학자들이 음식을 먹기 위해서는 총 두개의 젓가락이 필요합니다.

철학자들은 자신의 왼쪽에 있는 젓가락을 먼저 든 후에 오른쪽의 젓가락을 들 수 있습니다.

 

 

5명의 철학자와 5개의 젓가락이 있을 때의 상황으로 예를 들어보겠습니다. 

만약 모든 철학자가 동시에 자신의 왼쪽에 있는 젓가락을 든다면 모든 철학자가 음식을 먹지 못하게 됩니다.

(circular wait에 의해 deadlock 발생)

 

 

모든 젓가락에 우선순위를 부여하고 우선순위가 높은 것부터 집을 수 있다면 deadlock을 방지할 수 있습니다. 

4명의 철학자는 자신의 양쪽에 있는 젓가락 중 우선순위가 높은 젓가락부터 집습니다.

철학자5는 자신의 양쪽에 있는 젓가락 중 우선순위가 높은 젓가락이 이미 사용되고 있기 때문에 아무 자원도 선점하지 못한채 기다려야 합니다.

이때 철학자 5는 나머지 한쪽 젓가락이 누구에게도 사용중이 아니기 때문에 양쪽 젓가락을 사용할 수 있습니다.

차례대로 젓가락 사용을 마치고 나면 결국에는 철학자 5를 포함한 모든 철학자가 젓가락을 사용할 수 있게 됩니다.