Dining Philosophers 문제

Dining Philosophers 문제

5명의 철학자가 원탁에 앉아 생각과 식사를 반복하며 양쪽 포크를 모두 획득해야 식사 가능한 상황에서 데드락·기아를 방지하는 고전적 동기화 문제

목적: 데드락 이해, 자원 순환 대기, 동기화 해결책 학습

특징: 순환 자원(포크), 데드락 가능, 기아 가능, 공정성 문제

문제 상황: 5개 포크, 각 철학자가 왼쪽·오른쪽 포크 필요 → 모두 왼쪽 포크 집으면 데드락

데드락 발생: 모든 철학자가 동시에 왼쪽 포크 획득 → 오른쪽 포크 대기 → 순환 대기

해결 방법

• •홀수/짝수 구분: 홀수 철학자는 왼쪽 먼저, 짝수는 오른쪽 먼저 → 순환 대기 방지
• •최대 N-1명만 식사: 세마포어(4)로 동시 식사 제한 → 최소 1명은 포크 2개 획득 가능
• •원자적 획득: 양쪽 포크를 한 번에 획득(mutex로 보호) → 데드락 없음, 병렬성 감소
• •자원 순서화: 포크에 번호 부여, 낮은 번호 먼저 → 순환 대기 제거
• •타임아웃: 일정 시간 대기 후 포크 내려놓기 → 재시도

기아 방지: 우선순위, 공정 큐, 타임스탬프

적용사례: 자원 할당 교육, 데드락 연구, 멀티스레드 설계 패턴

비교: Dining Philosophers(순환자원/데드락) vs Producer-Consumer(버퍼/동기화) vs Reader-Writer(읽기공유/쓰기독점)

연관: 데드락, 세마포어, 순환 대기, 동기화, 자원 할당