동시성, 교착상태 문제로 고전적으로 나오는 밈? 문제이다.

나도 원래 몰랐는 데 여러군데 돌아다니다 알게 되었다.

문제 설명

5명의 철학자가 원탁에 앉아 있고 각자 앞에 스파게티와 포크가 놓여져 있다.

  1. 처음에 왼쪽 포크를 집어 든다.
  2. 그다음 오른쪽 포크를 집어 든다.
  3. 양손에 두 개의 포크를 모두 쥐었을 때만 스파게티를 먹는다.
  4. 식사를 마치면 양쪽 포크를 모두 제자리에 내려놓는다.

5명의 철학자 모두 왼쪽 포크는 들고 있을 수 있지만 오른쪽 포크는 없는 상태이기 때문에 어떻게 해야할까?

내 생각

메시지 큐 쓰듯이 그냥 한명씩 순서대로 한입씩 먹으면 되는 거 아닌가..?

아니면 그냥 5명 동시에만 포크를 안들면 되지 않나 하는 생각이다.

교착상태(Deadlock) 발생하는 이유

모든 철학자가 동시에 왼쪽 포크를 집으면, 5개의 포크가 모두 사용 중이 된다. 이제 각 철학자는 오른쪽 포크를 기다리지만, 오른쪽 포크는 옆 철학자가 이미 들고 있다. 아무도 포크를 내려놓지 않으므로 무한 대기 상태에 빠진다.

이는 교착상태의 4가지 조건을 모두 만족한다.

  1. 상호 배제(Mutual Exclusion): 포크는 한 번에 한 철학자만 사용 가능
  2. 점유 대기(Hold and Wait): 왼쪽 포크를 든 채 오른쪽 포크를 기다림
  3. 비선점(No Preemption): 다른 철학자의 포크를 강제로 빼앗을 수 없음
  4. 순환 대기(Circular Wait): 철학자 0 → 1 → 2 → 3 → 4 → 0 순환 구조로 대기

해결 방법(인터넷에 나와있는 것)

1. 자원 순서화 (Resource Ordering)

교착상태 4가지 조건 중 순환 대기를 깨는 방법이다. 모든 포크에 번호를 매기고, 철학자는 항상 번호가 작은 포크부터 집도록 한다.

마지막 철학자(4번)만 왼쪽(4번 포크)이 아닌 오른쪽(0번 포크)을 먼저 집게 되므로 순환이 깨진다.

철학자 0: fork[0] → fork[1]
철학자 1: fork[1] → fork[2]
철학자 2: fork[2] → fork[3]
철학자 3: fork[3] → fork[4]
철학자 4: fork[0] → fork[4]  ← 순서 변경!

2. 세마포어 (Semaphore)

동시에 식사할 수 있는 철학자 수를 최대 4명으로 제한한다. 5개의 포크에 5명이 동시에 접근하지 못하게 하면 최소 한 명은 양쪽 포크를 모두 얻을 수 있다.

semaphore room = 4;  // 동시에 4명만 입장 가능

philosopher(i):
    wait(room)           // 방 입장
    wait(fork[i])        // 왼쪽 포크
    wait(fork[(i+1)%5])  // 오른쪽 포크
    eat()
    signal(fork[(i+1)%5])
    signal(fork[i])
    signal(room)         // 방 퇴장

3. Chandy/Misra 해결법

포크를 깨끗한(clean) 상태와 더러운(dirty) 상태로 구분한다.

  1. 처음에 모든 포크는 더러운 상태로, 번호가 작은 철학자에게 준다
  2. 포크가 필요하면 이웃에게 요청한다
  3. 더러운 포크를 가진 철학자는 포크를 깨끗이 닦고 넘겨준다
  4. 깨끗한 포크를 가진 철학자는 사용할 때까지 넘겨주지 않는다

이 방식은 분산 시스템에서도 동작하며, 기아(starvation) 문제까지 해결한다.

February 20, 2026