식사하는 철학자 문제 — 교착 상태의 교과서적 예제

식사하는 철학자 문제는 Dijkstra가 제안한 동기화 문제의 고전입니다. 데드락의 4가지 조건을 직관적으로 이해할 수 있는 최고의 예제입니다.

문제 설명

원형 테이블에 5명의 철학자가 앉아 있습니다. 각 철학자 사이에 포크가 하나씩 있고, 식사하려면 양쪽 포크를 모두 들어야 합니다.

식사하는 철학자 문제 다이어그램

PLAINTEXT

        P0
      /    \
   F4      F0
    /        \
  P4          P1
   \          /
   F3      F1
     \    /
      P3—P2
        F2

P = 철학자, F = 포크

철학자는 두 가지 행동을 반복합니다:

생각하기 (Think) — 포크 불필요
식사하기 (Eat) — 양쪽 포크 2개 모두 필요

데드락이 발생하는 단순 구현

semaphore fork[5] = {1, 1, 1, 1, 1};

void philosopher(int i) {
    while (true) {
        think();
        wait(fork[i]);           // 왼쪽 포크 집기
        wait(fork[(i+1) % 5]);   // 오른쪽 포크 집기
        eat();
        signal(fork[i]);
        signal(fork[(i+1) % 5]);
    }
}

데드락 시나리오: 5명 모두 동시에 왼쪽 포크를 집으면, 아무도 오른쪽 포크를 못 집고 영원히 대기합니다.

PLAINTEXT

P0: fork[0] 잡음, fork[1] 대기
P1: fork[1] 잡음, fork[2] 대기
P2: fork[2] 잡음, fork[3] 대기
P3: fork[3] 잡음, fork[4] 대기
P4: fork[4] 잡음, fork[0] 대기 ← 원형 대기!

데드락 4가지 조건이 모두 충족됩니다:

상호 배제: 포크는 한 사람만 사용 가능
점유 대기: 왼쪽 포크를 잡은 채 오른쪽을 대기
비선점: 다른 사람의 포크를 뺏을 수 없음
원형 대기: P0→P1→P2→P3→P4→P0 순환

해결 방법 1: 비대칭 순서 (원형 대기 깨기)

마지막 철학자만 포크를 집는 순서를 바꿉니다.

void philosopher(int i) {
    while (true) {
        think();
        if (i == 4) {
            // 마지막 철학자는 오른쪽 먼저
            wait(fork[(i+1) % 5]);
            wait(fork[i]);
        } else {
            // 나머지는 왼쪽 먼저
            wait(fork[i]);
            wait(fork[(i+1) % 5]);
        }
        eat();
        signal(fork[i]);
        signal(fork[(i+1) % 5]);
    }
}

원형 대기 조건이 깨져서 데드락이 발생하지 않습니다.

해결 방법 2: 동시 식사 인원 제한

동시에 식사할 수 있는 철학자 수를 4명으로 제한합니다.

semaphore seats = 4;  // 최대 4명만 동시 식사 시도

void philosopher(int i) {
    while (true) {
        think();
        wait(seats);               // 자리가 있을 때만 시도
        wait(fork[i]);
        wait(fork[(i+1) % 5]);
        eat();
        signal(fork[i]);
        signal(fork[(i+1) % 5]);
        signal(seats);
    }
}

5명 중 4명만 동시에 포크를 잡으려 하면, 최소 한 명은 양쪽 포크를 모두 잡을 수 있습니다.

해결 방법 3: 모니터 사용

enum { THINKING, HUNGRY, EATING } state[5];
condition self[5];
mutex monitor_lock;

void pickup(int i) {
    lock(monitor_lock);
    state[i] = HUNGRY;
    test(i);                // 양쪽 이웃이 안 먹고 있으면 EATING으로 전환
    if (state[i] != EATING)
        wait(self[i]);      // 먹을 수 없으면 대기
    unlock(monitor_lock);
}

void putdown(int i) {
    lock(monitor_lock);
    state[i] = THINKING;
    test((i+4) % 5);        // 왼쪽 이웃 깨움
    test((i+1) % 5);        // 오른쪽 이웃 깨움
    unlock(monitor_lock);
}

void test(int i) {
    if (state[(i+4)%5] != EATING &&
        state[i] == HUNGRY &&
        state[(i+1)%5] != EATING) {
        state[i] = EATING;
        signal(self[i]);     // 대기 중이면 깨움
    }
}

양쪽 포크를 원자적으로 확인하고 집는 방식으로 데드락을 방지합니다.

해결 방법 비교

방법	깨는 조건	장점	단점
비대칭 순서	원형 대기	간단	비대칭이라 직관적이지 않음
인원 제한	점유 대기	간단	동시성 약간 감소
모니터	점유 대기	기아 방지 가능	구현 복잡
trylock + 양보	비선점	유연	라이브락 가능성

핵심 포인트

왜 데드락이 발생하는가: 4가지 조건(상호 배제, 점유 대기, 비선점, 원형 대기)이 모두 충족
가장 간단한 해결법: 포크 집는 순서를 통일 (번호가 낮은 포크부터) → 원형 대기 깨짐
실제 적용: 여러 자원을 순서 없이 잡으면 데드락 위험 → 자원에 번호를 매기고 순서대로 획득

정리

식사하는 철학자 문제는 데드락을 이해하는 가장 직관적인 모델입니다. 핵심은 데드락 4가지 조건 중 하나를 깨면 해결 된다는 것이고, 실제로는 "자원 획득 순서를 통일"하는 것이 가장 흔한 해결책입니다.