[운영체제] 식사하는 철학자들 문제 (Dining philosophers problem) - Deadlock, Starvation

 

목차

• 🤔  식사하는 철학자들 문제(Dining philosophers problem)란?
• 💡  문제 해결 방법

 

🤔   식사하는 철학자들 문제(Dining philosophers problem)란?

 

'5명의 식사하는 철학자들'

 

식사하는 철학자들 문제(Dining philosopher problem)는 Deadlock과 Starvation을 비유하여 설명하는 좋은 예제입니다.

 

5명의 철학자가 원탁에 앉아서 식사를 합니다.

애처롭게도, 철학자 사이사이에 젓가락은 하나씩만 주어집니다.

그렇기 때문에 아래와 같은 과정을 통해 식사를 해야 합니다.

 

1. 철학자들은 일정 시간 동안 생각을 한다.
2. 왼쪽 젓가락이 사용 가능할 때까지 기다린다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 젓가락이 사용 가능할 때까지 기다린다. 만약 사용 가능하다면 집어든다.
4. 젓가락 한 쌍을 얻었다면 식사를 한다.
5. 오른쪽 젓가락을 내려 놓는다.
6. 왼쪽 젓가락을 내려 놓는다.
7. 1번 과정으로 돌아간다.

 

얼핏 보면 괜찮은 식사 방법처럼 보일 수 있습니다.

그러나, 만약 철학자들 모두 왼쪽 젓가락만 들고 오른쪽 젓가락을 기다리기만 하는 상황에서 문제가 발생합니다.

 

(Deadlock) - 모두 식사를 하지 못하기 때문에 젓가락을 내려놓을 일이 없고, 3번 과정으로 넘어가지 못하기 때문입니다.

(Starvation) - 이러한 상황이 지속된다면 철학자들 모두 굶어죽고 말 것입니다.

 

 

해당 문제는 OS의 Deadlock, Starvation을 설명하기 위한 상황으로 비유한 대상은 아래와 같습니다.

• 젓가락 -> 자원(Resource)
• 철학자 -> Process(or Thread)
• 젓가락 한 쌍(2개) -> Process가 필요한 자원의 수

[데드락 발생 규칙 4가지]

• Mutual exclusion : 다른 철학자가 사용 중인 젓가락을 서로 공유하며 사용할 수 없습니다.
• Hold and wait : 철학자가 젓가락(자원) 1개를 가지고 있는 상태에서, 다른 철학자가 사용 중인 젓가락을 요청합니다.
• No preemtion : 규칙상 다른 철학자가 가지고 있는 젓가락을 함부로 빼앗거나 선점할 수 없습니다.
• Circular wait : 철학자들이 서로 꼬리에 꼬리를 무는 형태로 젓가락을 기다리고 있습니다.

 

따라서, 철학자들은 현재 Deadlock에 걸린 상황이며 더 이상 식사를 진행하지 못하고 있습니다.

뿐만 아니라, 젓가락(자원)을 요청하고 있으나, 계속해서 할당받지 못하는 상황인 Starvation까지 발생한 상황입니다.

 

 

💡   문제 해결 방법

그렇다면 이러한 문제를 어떻게 해결할 수 있는지 궁금해질 겁니다.

워낙 well-known 문제이며, 그만큼 해결방법은 다양합니다.

해당 포스팅에서는 3가지 정도를 다루어 보겠습니다.

 

 

1. 철학자 5명이 앉을 수 있는 테이블에 최대 4명만 앉을 수 있도록 허용한다.

 

만약 5좌석에서 4명만 앉힐 수 있도록 허용한다면, 3명이 젓가락을 한 개씩 가지고 있다고 하더라도 최소한 나머지 1명은 젓가락을 2개 얻을 수 있으므로 식사가 가능합니다.

따라서 1명이 식사를 마치면, 언젠가는 다른 철학자들도 식사를 할 수 있으므로 Deadlock 발생 상황을 배제할 수 있습니다.

 

 

2. 젓가락을 한 번에 2개씩 들도록 규칙을 바꾼다.

 

현재 규칙은 젓가락을 한 번에 1개씩만 들 수 있는 상황입니다.

하지만, 자신의 왼쪽, 오른쪽에 놓인 젓가락을 동시에 들 수 있도록 바꾸어준다면, 최소한 1명 이상은 식사를 할 수 있으므로 Deadlock 발생 상황을 배제할 수 있습니다.

 

이는 Hardware적 해결책으로, 하드웨어 명령어 즉, Atomic operation을 자원 1개가 아닌, 2개씩 가져가도록 변경해주는 것입니다.

 

참고로 Atomic operation은 더 이상 쪼개어질 수 없는 명령입니다.

따라서, Atomic operation 하나를 실행하는 도중에 interrupt가 발생해서 명령을 방해하는 상황은 발생하지 않습니다.

조금 더 이해하기 쉽게 아래 그림을 살펴보겠습니다.

 

'왼쪽, 오른쪽을 각각 따로 가져가는 operation'

 

위 그림은 왼쪽 젓가락을 가져가는 Atomic operation을 수행하고 나서, Context switch가 발생하여 다른 프로세스에게 CPU가 넘어간 상황입니다.

그리고, 다시 CPU를 할당받았을 때는 이미 오른쪽 젓가락을 그 옆에 있는 프로세스가 가져가서 Deadlock이 발생할 수도 있는 상황을 설명한 그림입니다.

'왼쪽, 오른쪽 젓가락을 한 번에 가져가는 operation'

반면, Atomic operation을 젓가락 1쌍을 한 번에 가져가도록 설계해준다면 Context switch가 발생해도 이미 철학자의 손에는 2개의 젓가락이 쥐어졌기 때문에 나중에 CPU를 다시 할당 받아도 식사를 못할 걱정이 없어집니다.

 

 

3. 앉은 자리별로 젓가락 드는 순서를 다르게 한다.

 

무조건 왼쪽, 오른쪽 순으로 젓가락을 기다리는 방법에서

홀수(1, 3, 5) 철학자는 왼쪽, 오른쪽 순서로 젓가락을 기다리고

짝수(2, 4) 철학자는 오른쪽, 왼쪽 순서로 젓가락을 기다리도록 합니다.

 

'Circular wait'

 

새로운 대기 방식은 기존에 Circular wait이 발생할 수 있는 상황을 배제 할 수 있습니다.

양 옆에 앉아 있는 철학자별로 자원의 Request edge가 서로 반대 방향을 가리키고 있기 때문입니다.

따라서, Deadlock을 방지할 수 있습니다.

참고로, 이처럼 Deadlock 발생 조건 중에 하나 이상을 배제시키는 기법을 Deadlock Prevention 이라고 부르기도 합니다.

 

 

 

 

github : https://github.com/tmdgh1592

tmdgh1592 - Overview