식사하는 철학자 문제 (Dining Philosophers Problem)
식사하는 철학자 문제 (Dining Philosophers Problem)
“이 책은 도대체 왜 이런 이상한 논의를 하는걸까?…”
식사하는 철학자 문제는 컴퓨터 과학에서 동시성(concurrency)과 동기화(synchronization) 문제를 잘 보여주는 고전적인 문제입니다. 이 문제는 1965년에 에드거 다익스트라(Edsger Dijkstra)가 처음 제시했으며, 멀티스레드 환경에서 발생할 수 있는 교착 상태(deadlock)와 기아 상태(starvation)를 설명하는 데 자주 사용됩니다.
문제 설명
식사하는 철학자 문제는 다음과 같이 설명할 수 있습니다.
- 원형 테이블에 5명의 철학자가 앉아 있습니다.
- 각 철학자 사이에는 포크(또는 젓가락)가 하나씩 놓여 있어 총 5개의 포크가 있습니다.
- 철학자들은 생각하는 시간과 식사하는 시간을 번갈아가며 보냅니다.
- 식사를 하기 위해서는 철학자가 자신의 양쪽에 있는 두 개의 포크를 모두 집어야 합니다.
- 한 번에 하나의 포크만 집을 수 있으며, 이미 다른 철학자가 사용 중인 포크는 집을 수 없습니다.
- 식사를 마친 철학자는 두 개의 포크를 모두 내려놓고 다시 생각하는 시간을 갖습니다.
문제의 핵심
이 문제의 핵심은 다음과 같은 상황이 발생할 수 있다는 것입니다.
교착 상태(Deadlock): 모든 철학자가 동시에 자신의 왼쪽(또는 오른쪽) 포크를 집은 경우, 아무도 식사를 시작할 수 없고 아무도 포크를 내려놓지 않게 됩니다. 이로 인해 시스템이 영원히 진행되지 않는 교착 상태에 빠집니다.
기아 상태(Starvation): 일부 철학자들이 계속해서 식사할 기회를 얻지 못하는 상황입니다. 예를 들어, 두 명의 철학자가 번갈아가며 식사하면서 그 사이에 있는 철학자는 항상 포크를 얻지 못하는 경우입니다.
자원 경쟁(Resource Contention): 여러 철학자가 동일한 포크를 사용하려고 할 때 발생하는 경쟁 상태입니다.
해결 방법
식사하는 철학자 문제를 해결하기 위한 여러 접근 방법이 있습니다.
1. 리소스 계층화 (Resource Hierarchy)
각 포크에 번호를 부여하고, 철학자들은 항상 낮은 번호의 포크를 먼저 집도록 규칙을 정합니다.
void philosopher(int id) {
while (true) {
think();
int firstFork = Math.Min(leftFork(id), rightFork(id));
int secondFork = Math.Max(leftFork(id), rightFork(id));
pickup(firstFork);
pickup(secondFork);
eat();
putdown(secondFork);
putdown(firstFork);
}
}이 방법은 모든 철학자가 낮은 번호의 포크를 먼저 집기 때문에 순환 대기(circular wait) 조건이 발생하지 않아 교착 상태를 방지할 수 있습니다.
2. 웨이터 도입 (Arbitrator/Waiter Solution)
웨이터라는 중재자를 도입하여 동시에 식사할 수 있는 철학자의 수를 제한합니다.
Semaphore waiter = new Semaphore(4); // 최대 4명만 테이블에 앉을 수 있음
void philosopher(int id) {
while (true) {
think();
waiter.acquire(); // 웨이터에게 허가를 받음
pickup(leftFork(id));
pickup(rightFork(id));
eat();
putdown(rightFork(id));
putdown(leftFork(id));
waiter.release(); // 웨이터에게 식사 완료 알림
}
}이 방법은 최대 n-1명의 철학자만 동시에 테이블에 앉을 수 있도록 하여 교착 상태를 방지합니다.
3. 찬드라-미스라 해결책 (Chandy-Misra Solution)
이 방법은 비대칭적인 접근 방식으로, 철학자들을 ‘청결한’ 상태와 ‘더러운’ 상태로 분류합니다.
- 포크는 깨끗하거나 더러운 상태를 가집니다.
- 처음에는 모든 포크가 테이블에 놓여 있고 철학자들은 생각 중입니다.
- 철학자가 배고프면 먼저 가지고 있지 않은 포크를 요청합니다.
- 포크를 가진 철학자는 다음 조건에서만 포크를 넘겨줍니다.
- 포크가 더러운 상태일 때
- 철학자가 다른 포크도 가지고 있을 때
- 식사 후에는 사용한 포크가 더러워집니다.
4. 타임아웃 및 재시도 (Timeout and Retry)
철학자가 일정 시간 내에 두 번째 포크를 집지 못하면 첫 번째 포크를 내려놓고 잠시 기다린 후 다시 시도합니다.
void philosopher(int id) {
while (true) {
think();
boolean haveBothForks = false;
while (!haveBothForks) {
pickup(leftFork(id));
if (tryPickup(rightFork(id), TIMEOUT)) {
haveBothForks = true;
} else {
putdown(leftFork(id));
sleep(RANDOM_DELAY);
}
}
eat();
putdown(rightFork(id));
putdown(leftFork(id));
}
}C# 코드 예제
다음은 세마포어를 사용한 식사하는 철학자 문제의 C# 구현 예제입니다.
using System;
using System.Threading;
using System.Threading.Tasks;
class DiningPhilosophers
{
private const int NumberOfPhilosophers = 5;
private Semaphore[] forks;
private Semaphore waiter;
private Random random = new Random();
public DiningPhilosophers()
{
// 각 포크를 세마포어로 표현 (1개의 리소스만 사용 가능)
forks = new Semaphore[NumberOfPhilosophers];
for (int i = 0; i < NumberOfPhilosophers; i++)
{
forks[i] = new Semaphore(1, 1);
}
// 웨이터 세마포어 (최대 4명만 테이블에 앉을 수 있음)
waiter = new Semaphore(NumberOfPhilosophers - 1, NumberOfPhilosophers - 1);
}
private int LeftFork(int philosopherId)
{
return philosopherId;
}
private int RightFork(int philosopherId)
{
return (philosopherId + 1) % NumberOfPhilosophers;
}
private void Think(int philosopherId)
{
Console.WriteLine($"철학자 {philosopherId}이(가) 생각 중...");
Thread.Sleep(random.Next(1000, 3000)); // 1-3초 동안 생각
}
private void Eat(int philosopherId)
{
Console.WriteLine($"철학자 {philosopherId}이(가) 식사 중...");
Thread.Sleep(random.Next(1000, 2000)); // 1-2초 동안 식사
Console.WriteLine($"철학자 {philosopherId}이(가) 식사 완료!");
}
public void StartPhilosopher(int philosopherId)
{
while (true)
{
Think(philosopherId);
Console.WriteLine($"철학자 {philosopherId}이(가) 배고픔을 느낌");
// 웨이터에게 허가 요청
waiter.WaitOne();
// 왼쪽 포크 집기
forks[LeftFork(philosopherId)].WaitOne();
Console.WriteLine($"철학자 {philosopherId}이(가) 왼쪽 포크 {LeftFork(philosopherId)}를 집음");
// 오른쪽 포크 집기
forks[RightFork(philosopherId)].WaitOne();
Console.WriteLine($"철학자 {philosopherId}이(가) 오른쪽 포크 {RightFork(philosopherId)}를 집음");
// 식사
Eat(philosopherId);
// 오른쪽 포크 내려놓기
forks[RightFork(philosopherId)].Release();
Console.WriteLine($"철학자 {philosopherId}이(가) 오른쪽 포크 {RightFork(philosopherId)}를 내려놓음");
// 왼쪽 포크 내려놓기
forks[LeftFork(philosopherId)].Release();
Console.WriteLine($"철학자 {philosopherId}이(가) 왼쪽 포크 {LeftFork(philosopherId)}를 내려놓음");
// 웨이터에게 자리 반납
waiter.Release();
}
}
public void Start()
{
// 각 철학자를 위한 태스크 생성
Task[] philosophers = new Task[NumberOfPhilosophers];
for (int i = 0; i < NumberOfPhilosophers; i++)
{
int philosopherId = i;
philosophers[i] = Task.Run(() => StartPhilosopher(philosopherId));
}
// 모든 철학자 태스크가 완료될 때까지 대기 (이 경우 무한 루프라 실제로는 완료되지 않음)
Task.WaitAll(philosophers);
}
static void Main()
{
Console.WriteLine("식사하는 철학자 문제 시뮬레이션 시작");
DiningPhilosophers dp = new DiningPhilosophers();
dp.Start();
}
}리소스 계층화를 사용한 구현
포크에 우선순위를 부여하여 교착 상태를 방지하는 방법입니다.
using System;
using System.Threading;
using System.Threading.Tasks;
class HierarchicalDiningPhilosophers
{
private const int NumberOfPhilosophers = 5;
private Semaphore[] forks;
private Random random = new Random();
public HierarchicalDiningPhilosophers()
{
// 각 포크를 세마포어로 표현
forks = new Semaphore[NumberOfPhilosophers];
for (int i = 0; i < NumberOfPhilosophers; i++)
{
forks[i] = new Semaphore(1, 1);
}
}
private void Think(int philosopherId)
{
Console.WriteLine($"철학자 {philosopherId}이(가) 생각 중...");
Thread.Sleep(random.Next(1000, 3000));
}
private void Eat(int philosopherId)
{
Console.WriteLine($"철학자 {philosopherId}이(가) 식사 중...");
Thread.Sleep(random.Next(1000, 2000));
Console.WriteLine($"철학자 {philosopherId}이(가) 식사 완료!");
}
public void StartPhilosopher(int philosopherId)
{
int leftFork = philosopherId;
int rightFork = (philosopherId + 1) % NumberOfPhilosophers;
// 항상 번호가 작은 포크를 먼저 집음
int firstFork = Math.Min(leftFork, rightFork);
int secondFork = Math.Max(leftFork, rightFork);
while (true)
{
Think(philosopherId);
Console.WriteLine($"철학자 {philosopherId}이(가) 배고픔을 느낌");
// 번호가 작은 포크 먼저 집기
forks[firstFork].WaitOne();
Console.WriteLine($"철학자 {philosopherId}이(가) 포크 {firstFork}를 집음");
// 번호가 큰 포크 집기
forks[secondFork].WaitOne();
Console.WriteLine($"철학자 {philosopherId}이(가) 포크 {secondFork}를 집음");
// 식사
Eat(philosopherId);
// 포크 내려놓기 (순서는 중요하지 않음)
forks[secondFork].Release();
Console.WriteLine($"철학자 {philosopherId}이(가) 포크 {secondFork}를 내려놓음");
forks[firstFork].Release();
Console.WriteLine($"철학자 {philosopherId}이(가) 포크 {firstFork}를 내려놓음");
}
}
public void Start()
{
// 각 철학자를 위한 태스크 생성
Task[] philosophers = new Task[NumberOfPhilosophers];
for (int i = 0; i < NumberOfPhilosophers; i++)
{
int philosopherId = i;
philosophers[i] = Task.Run(() => StartPhilosopher(philosopherId));
}
// 모든 철학자 태스크가 완료될 때까지 대기
Task.WaitAll(philosophers);
}
static void Main()
{
Console.WriteLine("계층적 해결책을 이용한 식사하는 철학자 문제 시뮬레이션 시작");
HierarchicalDiningPhilosophers dp = new HierarchicalDiningPhilosophers();
dp.Start();
}
}문제의 의의
식사하는 철학자 문제는 다음과 같은 이유로 컴퓨터 과학에서 중요합니다.
동시성 제어의 교육 도구: 교착 상태, 기아 상태, 경쟁 상태와 같은 동시성 문제를 직관적으로 설명합니다.
해결책 비교: 다양한 동기화 기법과 교착 상태 방지 전략을 비교할 수 있는 기반을 제공합니다.
실제 응용: 데이터베이스 트랜잭션, 운영 체제의 자원 할당, 네트워크 프로토콜 설계 등에서 유사한 문제가 발생합니다.
분산 시스템 관련성: 분산 시스템에서의 자원 공유와 조정 문제를 논의하는 데 활용됩니다.
결론
식사하는 철학자 문제는 단순한 설정에서 복잡한 동시성 문제를 보여주는 우아한 예시입니다. 이 문제는 다양한 동기화 기법과 교착 상태 방지 전략을 이해하는 데 도움이 되며, 실제 시스템 설계에서도 유용한 통찰력을 제공합니다. 컴퓨터 과학에서 이론적인 개념을 실용적인 문제 해결에 연결하는 중요한 교량 역할을 합니다.