식사하는 철학자들 문제
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
식사하는 철학자 문제는 다섯 명의 철학자가 두 개의 포크로 먹어야 하는 스파게티를 먹기 위해 경쟁하는 상황을 묘사하는 병행성(concurrency) 문제이다. 이 문제는 교착 상태(deadlock)를 피하면서 모든 철학자가 식사와 생각을 반복할 수 있도록 하는 알고리즘 설계의 어려움을 보여준다. 해결책으로는 포크를 잡는 순서에 비대칭성을 부여하거나, 웨이터를 두어 포크 사용을 중재하는 방법, 또는 철학자 수를 제한하는 방법 등이 제시된다. 또한, 모니터와 세마포어와 같은 동기화 도구를 사용한 코드 예시가 파스칼과 자바 언어로 제공된다.
더 읽어볼만한 페이지
- 계산 문제 - 다체 문제
다체 문제는 상호작용하는 여러 물체의 운동을 다루는 문제로, 특히 중력적으로 상호작용하는 천체들의 운동을 예측하는 문제가 대표적이며, 삼체 문제부터는 해석적 해를 구하기 어려워 섭동 이론이나 수치 해석 등의 방법이 활용된다. - 계산 문제 - 최적화 문제
최적화 문제는 주어진 제약 조건 하에 특정 목적 함수의 값을 최소화하거나 최대화하는 해를 찾는 문제로, 제약 조건 유무, 함수 종류, 변수 성격에 따라 다양한 유형으로 나뉜다. - 병행성 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다. - 병행성 - 기아 상태
기아 상태는 컴퓨터 과학에서 프로세스가 필요한 자원을 할당받지 못해 무한정 대기하는 현상으로, 단순한 스케줄링 알고리즘, 우선순위 역전, 교착 상태 등으로 인해 발생하며 시스템 효율성을 저하시키고 작업 완료를 지연시키지만, 에이징 기법과 같은 공정한 스케줄링 알고리즘이나 우선순위 조정으로 해결할 수 있다. - 1965년 도입 - 가이아 이론
가이아 이론은 지구를 생물권, 대기권, 수권, 지권이 상호작용하며 항상성을 유지하는 하나의 거대한 자기조절 시스템으로 보는 이론으로, 지구 시스템 과학의 연구 대상이자 환경 운동 등 다양한 영역에 영향을 미치고 있다. - 1965년 도입 - 게토레이
게토레이는 1965년 플로리다 대학교 미식축구팀을 위해 개발된 스포츠 음료로, 물, 나트륨, 설탕 등을 혼합하여 만들어졌으며, 1967년 오렌지 볼 대회에서 팀의 승리에 기여하며 유명해졌다.
| 식사하는 철학자들 문제 | |
|---|---|
| 개요 | |
| 문제 유형 | 동시성 문제 |
| 분야 | 컴퓨터 과학 |
| 주제 | 병행성, 자원 고갈, 교착 상태, 상호 배제 |
| 해결 방법 | 세마포어, 모니터, 뮤텍스, 교착 상태 회피 |
| 설명 | |
| 요약 | 여러 철학자가 식탁에 앉아 스파게티를 먹으려고 할 때 발생하는 교착 상태와 자원 고갈 문제 |
| 비유 | 여러 프로세스가 한정된 자원을 공유하려고 할 때 발생하는 문제를 비유적으로 설명 |
| 등장 인물 | 철학자 5명, 젓가락 5개 (또는 포크), 스파게티 |
| 문제 상황 | 철학자는 생각하거나 먹을 수 있으며, 먹기 위해서는 양쪽에 젓가락이 필요함. 젓가락이 제한되어 있기 때문에 모든 철학자가 동시에 먹을 수 없음. |
| 목표 | 교착 상태나 자원 고갈 없이 모든 철학자가 식사를 할 수 있도록 하는 것 |
| 해결책 | |
| 핵심 아이디어 | 자원 접근에 대한 규칙을 정의하여 교착 상태를 방지 |
| 일반적인 해결책 | 모든 철학자가 동시에 젓가락을 잡지 못하게 함 철학자가 젓가락을 잡을 수 있는지 확인하는 중재자 도입 젓가락을 짝수/홀수 철학자에게 다른 순서로 할당 |
| 알고리즘 | 다양한 알고리즘 (예: 데이크스트라 알고리즘)을 사용하여 문제 해결 |
| 추가 정보 | |
| 중요성 | 운영 체제와 병행성 프로그래밍에서 중요한 문제 |
| 관련 개념 | 상호 배제, 세마포어, 모니터, 교착 상태 회피 |
| 변형 | 다양한 변형 (예: 식탁에 앉은 철학자 수 변경, 젓가락 수 변경)이 존재 |
2. 문제 상황
다섯 명의 철학자가 원탁에 둘러앉아 식사를 하거나 생각을 한다. 각 철학자 앞에는 스파게티가 담긴 접시가 놓여 있고, 접시 사이에는 포크 (또는 젓가락[12])가 하나씩 놓여 있다. 철학자들은 스파게티를 먹기 위해 양쪽에 있는 포크 두 개를 모두 사용해야 하는데, 한 번에 하나의 포크만 집을 수 있다.
철학자들이 식사할 때는 다음과 같은 제약이 따른다.
- 왼쪽과 오른쪽 포크를 모두 가지고 있어야 한다.
- 포크는 한 번에 하나만 집을 수 있다.
- 다른 철학자와 대화하거나, 포크를 내려놓는 등의 조정을 할 수 없다.
이러한 상황 때문에 모든 철학자가 동시에 왼쪽 포크를 집고 오른쪽 포크를 기다리는 교착 상태가 발생할 수 있다.
2. 1. 발생 가능한 문제
이 문제에서는 다음과 같은 상황들이 발생할 수 있다.- 교착 상태(Deadlock): 모든 철학자가 동시에 왼쪽(또는 오른쪽) 포크를 집으면, 더 이상 진행할 수 없다.[13] 예를 들어, 모든 철학자가 왼쪽 포크를 잡고 오른쪽 포크가 놓이기를 기다리는 상황이 발생할 수 있다. 이는 실제 컴퓨터 프로그래밍에서 여러 프로그램이 서로 락(Lock)된 자원을 기다리며 영원히 멈추는 상황과 유사하다.[12]
- 기아 상태(Starvation): 특정 철학자가 계속해서 포크를 얻지 못하고 굶주리는 상태이다. 예를 들어, 어떤 철학자가 양쪽 포크를 모두 얻지 못하는 상황이 계속될 수 있다. 이는 자원 기아라고도 불린다.[13]
- 라이브락(Livelock): 철학자들이 서로 양보하려 하지만, 계속해서 같은 상황이 반복되어 진행되지 않는다. 예를 들어, 모든 철학자가 동시에 왼쪽 포크를 집고, 오른쪽 포크를 기다리다가, 다시 왼쪽 포크를 놓고, 이 과정을 반복하는 상황이 발생할 수 있다.[13]
이러한 문제들은 실제 컴퓨터 프로그래밍에서 공유 자원의 락과 관련된 문제, 즉 상호 배제 문제와 유사하다. 여러 프로세스가 공유 자원에 접근할 때 교착 상태, 자원 기아, 데이터 파괴 등이 발생하지 않도록 주의해야 한다.
3. 해결책
에츠허르 데이크스트라는 철학자들이 포크를 집는 순서에 변화를 주어 교착 상태를 해결하는 방법을 제시했다.[5][4]
- 기본 규칙:
- 5명의 철학자를 P1, P2, P3, P4, P5로, 각 철학자의 왼쪽 포크를 f1, f2, f3, f4, f5로 표시한다.
- P1, P2, P3, P4는 먼저 자신의 왼쪽 포크(fn)를 집은 후 오른쪽 포크(fn+1)를 집는다.
- P5는 반대로 f1(오른쪽) 포크를 먼저 집은 후 f5(왼쪽) 포크를 집는다.
이 방법은 철학자들이 동시에 모든 포크를 잡으려고 할 때 발생하는 원형 대기 상태를 막는다.
교착 상태 발생 조건은 ''상호 배제''(젓가락은 여러 철학자가 동시에 사용 불가), ''자원 점유''(철학자는 다른 젓가락을 기다리는 동안 젓가락을 쥐고 있음), ''비선점''(다른 사람에게서 젓가락을 빼앗을 수 없음), ''원형 대기''(각 철학자는 왼쪽에 있는 철학자를 기다림)이다. 해결책은 이 중 하나 이상을 무효화해야 한다.
대부분의 이론적 논의는 상호 배제나 비선점을 변경 불가능하다고 가정하고, 자원 점유나 원형 대기를 해결하는 데 집중한다.
3. 1. 에츠허르 데이크스트라의 해결책
에츠허르 데이크스트라는 철학자들이 포크를 집는 순서에 비대칭성을 도입하여 교착 상태를 방지하는 해결책을 제시했다.[5][4]- 기본 규칙:
- 5명의 철학자를 P1, P2, P3, P4, P5로, 각 철학자의 왼쪽 포크를 f1, f2, f3, f4, f5로 표시한다.
- P1, P2, P3, P4는 먼저 자신의 왼쪽 포크(fn)를 집은 후 오른쪽 포크(fn+1)를 집는다.
- P5는 반대로 f1(오른쪽) 포크를 먼저 집은 후 f5(왼쪽) 포크를 집는다.
이러한 비대칭적 접근 방식은 철학자들이 동시에 모든 포크를 잡으려고 할 때 발생하는 순환 대기 상태를 방지한다.
데이크스트라의 해결책은 자원 점유를 무효화한다. 철학자들은 원자적으로(한 번에) 양쪽 포크를 모두 집거나, 아니면 기다린다. 임계 구역 밖에서는 하나의 포크도 잡지 않는다. 이를 위해 뮤텍스, 철학자당 하나의 세마포어, 철학자당 하나의 상태 변수를 사용한다.
다음은 Tanenbaum의 변경 사항이 적용된 Dijkstra 해결책의 C++20 버전이다(코드 설명은 생략).
```cpp
#include
#include
#include
#include
#include
#include
constexpr const size_t N = 5; // 철학자(및 포크)의 수
enum class State
{
THINKING = 0, // 철학자는 생각 중
HUNGRY = 1, // 철학자는 포크를 얻으려고 시도
EATING = 2, // 철학자는 먹고 있음
};
size_t inline left(size_t i)
{
// 양쪽 포크를 모두 사용할 수 있는 철학자 i의 왼쪽 이웃의 번호
return (i - 1 + N) % N; // i - 1이 음수인 경우를 위해 N을 더합니다.
}
size_t inline right(size_t i)
{
// 양쪽 포크를 모두 사용할 수 있는 철학자 i의 오른쪽 이웃의 번호
return (i + 1) % N;
}
State state[N]; // 모든 사람의 both_forks_available 상태를 추적하기 위한 배열
std::mutex critical_region_mtx; // 임계 구역에 대한 상호 배제
// (포크를 집어 올리고 내려놓기)
std::mutex output_mtx; // 동기화된 cout용(THINKING/HUNGRY/EATING 상태 출력)
// 이진 세마포어 배열, 철학자당 하나의 세마포어.
// 획득한 세마포어는 철학자 i가 두 개의 포크를 획득했음(차단되었음)을 의미합니다.
std::binary_semaphore both_forks_available[N]
{
std::binary_semaphore{0}, std::binary_semaphore{0},
std::binary_semaphore{0}, std::binary_semaphore{0},
std::binary_semaphore{0}
};
size_t my_rand(size_t min, size_t max)
{
static std::mt19937 rnd(std::time(nullptr));
return std::uniform_int_distribution<>(min, max)(rnd);
}
void test(size_t i)
// 철학자 i가 배고프고 양쪽 이웃이 먹고 있지 않으면 먹습니다.
{
// i: 철학자 번호, 0에서 N-1까지
if (state[i] == State::HUNGRY &&
state[left(i)] != State::EATING &&
state[right(i)] != State::EATING)
{
state[i] = State::EATING;
both_forks_available[i].release(); // 이 먹는 세션에는 더 이상 포크가 필요하지 않습니다.
}
}
void think(size_t i)
{
size_t duration = my_rand(400, 800);
{
std::lock_guard
std::cout << i << " is thinking " << duration << "ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}
void take_forks(size_t i)
{
{
std::lock_guard
state[i] = State::HUNGRY; // 철학자 i가 State::HUNGRY임을 기록
{
std::lock_guard
std::cout << "\t\t" << i << " is State::HUNGRY\n";
}
test(i); // 2개의 포크를 획득하려고 시도(허가)
} // 임계 구역 종료
both_forks_available[i].acquire(); // 포크가 획득되지 않은 경우 차단
}
void eat(size_t i)
{
size_t duration = my_rand(400, 800);
{
std::lock_guard
std::cout << "\t\t\t\t" << i << " is eating " << duration << "ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}
void put_forks(size_t i)
{
std::lock_guard
state[i] = State::THINKING; // 철학자가 State::EATING을 완료했습니다.
test(left(i)); // 왼쪽 이웃이 이제 먹을 수 있는지 확인
test(right(i)); // 오른쪽 이웃이 이제 먹을 수 있는지 확인
// 함수를 종료하여 임계 구역 종료
}
void philosopher(size_t i)
{
while (true)
{ // 영원히 반복
think(i); // 철학자는 State::THINKING입니다.
take_forks(i); // 두 개의 포크를 획득하거나 차단합니다.
eat(i); // 냠냠, 스파게티
put_forks(i); // 두 개의 포크를 테이블에 다시 놓고 이웃이 먹을 수 있는지 확인합니다.
}
}
int main() {
std::cout << "dp_14\n";
std::jthread t0([&] { philosopher(0); }); // [&]는 뒤따르는 모든 변수를 의미합니다.
std::jthread t1([&] { philosopher(1); }); // 람다는 참조로 캡처됩니다.
std::jthread t2([&] { philosopher(2); });
std::jthread t3([&] { philosopher(3); });
std::jthread t4([&] { philosopher(4); });
}
```
철학자를 "짝수 그룹"과 "홀수 그룹"으로 나누어 서로 인접한 철학자가 다른 그룹에 속하도록 하고, "짝수 그룹"은 오른쪽 포크를, "홀수 그룹"은 왼쪽 포크를 먼저 잡도록 하는 방법도 의존 관계 순환을 방지하여 문제를 해결할 수 있다.
3. 2. 자원 계층 해결책
이 해결책은 자원(포크)에 부분 순서를 할당하여 순환 대기를 무효화하는 것이다. 모든 자원은 순서대로 요청되며, 순서와 관련이 없는 두 개의 자원은 동일한 작업 단위에서 동시에 사용하지 않는다는 규칙을 설정한다.[2] 여기서 자원(포크)은 1부터 5까지 번호가 매겨지고, 각 철학자는 항상 낮은 번호의 포크를 먼저 집어 들고, 그 다음 높은 번호의 포크를 집어 든다. 철학자가 포크를 내려놓는 순서는 중요하지 않다.[2]다섯 명의 철학자 중 네 명이 동시에 낮은 번호의 포크를 집어 들면, 가장 높은 번호의 포크만 테이블에 남게 되므로 다섯 번째 철학자는 어떤 포크도 집어 들 수 없다. 또한, 한 명의 철학자만 가장 높은 번호의 포크에 접근할 수 있으므로 두 개의 포크를 사용하여 식사할 수 있다. 이는 직관적으로 다른 모든 철학자와 달리 먼저 왼쪽에서 포크를 집어 드는 "왼손잡이" 철학자가 있는 것으로 생각할 수 있다.[2]
자원 계층 해결책은 교착 상태를 피하지만, 특히 필요한 자원 목록이 미리 완전히 알려지지 않은 경우 항상 실용적이지는 않다. 예를 들어, 작업 단위가 자원 3과 5를 가지고 있다가 자원 2가 필요하다고 결정하면, 2를 얻기 전에 5를 해제하고, 그 다음 3을 해제한 후, 해당 순서로 3과 5를 다시 얻어야 한다. 많은 수의 데이터베이스 레코드에 접근하는 컴퓨터 프로그램은 새로운 레코드에 접근하기 전에 모든 상위 번호의 레코드를 해제해야 한다면 효율적으로 실행되지 않으므로, 이 방법은 그 목적에 맞지 않는다.[2]
자원 계층 솔루션은 공정하지 않다. 만약 철학자 1이 포크를 집는 데 느리고, 철학자 2가 생각하고 포크를 다시 집는 데 빠르다면, 철학자 1은 두 개의 포크를 모두 집어 들 수 없을 것이다. 공정한 솔루션은 다른 철학자에 비해 그 철학자가 얼마나 느리게 움직이든 각 철학자가 결국 식사할 수 있도록 보장해야 한다.[6]
3. 3. 중재자(웨이터) 해결책
중재자(웨이터)를 두어 철학자가 포크를 집기 전에 허락을 받도록 하는 해결책이다. 철학자는 웨이터에게 허가를 요청해야 하고, 웨이터는 한 번에 한 명의 철학자에게만 허가를 주어 두 개의 포크를 모두 집을 수 있게 한다. 포크를 내려놓는 것은 항상 허용된다. 웨이터는 뮤텍스로 구현될 수 있다.[1]이 접근 방식은 교착 상태를 방지하지만, 병렬 처리를 감소시킬 수 있다. 한 철학자가 식사 중이고 이웃이 포크를 요청하면, 다른 모든 철학자는 포크가 사용 가능하더라도 요청이 완료될 때까지 기다려야 한다.[1]
철학자를 "Even 그룹"과 "Odd 그룹"으로 나누고 인접한 철학자가 서로 다른 그룹에 속하도록 한다. "Even 그룹" 철학자는 오른쪽 포크를 먼저 잡고, "Odd 그룹"은 왼쪽 포크를 먼저 잡는다. 이렇게 하면 의존 관계 순환이 발생하지 않아 문제가 해결된다.[1]
3. 4. 식사하는 철학자 수 제한
윌리엄 스톨링스[7]가 제시한 해결책은 한 번에 최대 ''n-1''명의 철학자만 앉도록 허용하는 것이다. 마지막 철학자는 누군가가 식사를 마칠 때까지 (예: 세마포어를 사용하여) 기다린 후 "착석"하여 포크에 대한 접근 권한을 요청해야 한다. 이렇게 하면 순환 대기가 무효화되어 최소한 한 명의 철학자는 항상 두 개의 포크를 모두 획득할 수 있어 시스템이 진행될 수 있다.철학자를 "Even 그룹"과 "Odd 그룹"의 두 그룹으로 분류하고, 서로 인접한 철학자는 서로 다른 그룹에 속하도록 한다. 그리고 "Even 그룹"의 철학자는 반드시 먼저 오른쪽 포크를 잡으려 하고, "Odd 그룹"은 먼저 반드시 왼쪽 포크를 잡으려 한다. 이와 같이 하면 의존 관계의 순환이 존재하지 않으므로 문제는 발생하지 않는다.
3. 5. 찬디/미스라 해결책
1984년, K. 마니 찬디와 J. 미스라[8]는 식사하는 철학자 문제에 대한 또 다른 해결책을 제시했다. 이 해결책은 임의의 에이전트(''P''1, ..., ''P''''n'')가 임의의 수의 자원을 놓고 경쟁할 수 있도록 하며, 다익스트라의 해법과 달리 완전히 분산되어 있고 중앙 권한이 필요하지 않다. 하지만, 철학자들이 서로 대화하지 않는다는 요구 사항은 위반된다(요청 메시지 때문에).찬디/미스라 해결책의 핵심은 다음과 같다.
- 포크의 상태: 각 포크는 '더러움' 또는 '깨끗함' 상태를 가진다. 처음에 모든 포크는 더럽다.
- 포크 할당: 자원을 놓고 경쟁하는 철학자 쌍에 대해, 더 낮은 ID를 가진 철학자에게 포크를 준다.
- 요청 및 응답:
- 철학자가 식사하려는 경우, 필요한 포크를 가진 이웃에게 요청 메시지를 보낸다.
- 포크를 가진 철학자는 요청을 받으면, 포크가 깨끗하면 자신이 가지고, 더러우면 넘겨준다. 넘겨줄 때는 깨끗하게 닦아서 준다.
- 식사 후: 철학자가 식사를 마치면, 모든 포크는 더러워진다. 다른 철학자가 요청한 포크가 있다면, 깨끗하게 닦아서 보낸다.
이 해결책은 기아(starvation) 문제도 해결한다. 깨끗함/더러움 상태는 오랫동안 식사하지 못한 철학자에게 우선순위를 부여하고, 최근에 식사한 철학자에게는 불이익을 주는 방식으로 작동한다.
이러한 방식은 방향 비순환 그래프를 통해 설명될 수 있는데, 이 그래프가 순환되지 않도록 보장함으로써 교착 상태(deadlock)를 방지한다. 그러나 시스템이 완벽하게 대칭적인 상태로 초기화되면(예: 모든 철학자가 왼쪽 포크를 잡는 경우) 교착 상태가 발생할 수 있다. 이를 방지하기 위해, 더 낮은 ID를 가진 철학자가 더러운 포크를 갖도록 초기화하여 그래프를 비순환으로 만들 수 있다.
이 문제를 해결하기 위해 철학자를 "짝수 그룹"과 "홀수 그룹"으로 분류하고, 서로 인접한 철학자는 서로 다른 그룹에 속하도록 할 수 있다. "짝수 그룹"의 철학자는 반드시 먼저 오른쪽 포크를 잡으려 하고, "홀수 그룹"은 먼저 반드시 왼쪽 포크를 잡으려 한다. 이렇게 하면 의존 관계의 순환이 존재하지 않으므로 교착 상태가 발생하지 않는다.
3. 6. 모니터(Monitor)를 사용한 해결책
철학자를 "짝수(Even) 그룹"과 "홀수(Odd) 그룹"으로 나누어, 인접한 철학자가 서로 다른 그룹에 속하게 한다. "짝수 그룹" 철학자는 오른쪽 포크를 먼저 잡고, "홀수 그룹"은 왼쪽 포크를 먼저 잡는다. 이렇게 하면 의존 관계 순환이 없어 문제가 발생하지 않는다.아래 코드 예시는 포크를 명시적으로 나타내지 않는다. 철학자는 양옆 철학자가 식사 중이 아닐 때만 식사할 수 있다. 이는 두 번째 포크를 잡을 수 없는 철학자는 포크를 내려놓고 기다린 후, 첫 번째 포크부터 다시 시도하는 방식이다.
포크마다 락(lock)이 없기 때문에, 철학자는 양옆 철학자의 상태에 따라 식사 시작 여부를 결정해야 한다. 하지만 그 상태 정보가 최신 정보임을 보장해야 한다. 예를 들어 철학자 2가 철학자 1이 식사하지 않음을 확인하고 철학자 3을 보았을 때, 1은 2가 3을 보는 동안 식사를 시작할 수 있다. 이를 방지하기 위해 단일 상호 배타적 락을 사용한다. 이는 특정 포크가 아닌, 철학자 상태 변경 절차 자체에 대응하는 모니터라는 기구이다. 절차 ''test'', ''pickup'', ''putdown''은 모니터에 결합되어 하나의 상호 배타적 락을 공유한다. 식사하기를 기다리는 철학자는 포크를 가지고 있지 않다. 식사하고 싶은 철학자가 있으면, 모니터는 첫 번째 포크를 놓고, 두 번째 포크도 사용 가능해지면 첫 번째 포크부터 다시 시도하게 한다. 식사가 끝나면 철학자는 모니터에 신호를 보내 양쪽 포크가 사용 가능함을 알린다.
코드 예시는 자원 기아를 방지할 수 없다. 예를 들어 1번과 3번 철학자가 식사하는 기간이 항상 겹치면, 2번 철학자는 계속 식사할 수 없다.
기아를 방지하려면 배고픈 철학자가 식사 못한 횟수를 유지하고, 한도를 넘으면 상태를 ''Hungry''에서 ''Starving''으로 변경한다. 그리고 포크를 줄지 결정할 때 양옆이 모두 ''Starving''이 아니라는 조건을 추가한다.
''Starving'' 상태인 이웃 때문에 식사 못한 철학자는 그 이웃의 이웃이 식사를 마칠 때까지 기다리게 된다. 의존 관계가 추가되어 병행성이 줄어든다. ''Starving'' 임계값을 크게 하면 영향을 억제할 수 있다.
4. 해결책의 예시 (코드)
다익스트라(Dijkstra)의 해결책은 C++20 버전으로 제시되며, 자원 점유를 무효화하는 방식으로 구현되었다. 철학자들은 원자적으로 양쪽 포크를 모두 집거나, 그렇지 않으면 기다린다. 이를 위해 뮤텍스, 세마포어, 상태 변수가 사용된다.[5][4]
다음은 이 해결책을 C++ 코드로 구현한 것이다.
```cpp
#include
#include
#include
#include
#include
#include
constexpr const size_t N = 5; // 철학자(및 포크)의 수
enum class State
{
THINKING = 0, // 철학자는 생각 중
HUNGRY = 1, // 철학자는 포크를 얻으려고 시도
EATING = 2, // 철학자는 먹고 있음
};
size_t inline left(size_t i)
{
// 양쪽 포크를 모두 사용할 수 있는 철학자 i의 왼쪽 이웃의 번호
return (i - 1 + N) % N; // i - 1이 음수인 경우를 위해 N을 더합니다.
}
size_t inline right(size_t i)
{
// 양쪽 포크를 모두 사용할 수 있는 철학자 i의 오른쪽 이웃의 번호
return (i + 1) % N;
}
State state[N]; // 모든 사람의 both_forks_available 상태를 추적하기 위한 배열
std::mutex critical_region_mtx; // 임계 구역에 대한 상호 배제
// (포크를 집어 올리고 내려놓기)
std::mutex output_mtx; // 동기화된 cout용(THINKING/HUNGRY/EATING 상태 출력)
// 이진 세마포어 배열, 철학자당 하나의 세마포어.
// 획득한 세마포어는 철학자 i가 두 개의 포크를 획득했음(차단되었음)을 의미합니다.
std::binary_semaphore both_forks_available[N]
{
std::binary_semaphore{0}, std::binary_semaphore{0},
std::binary_semaphore{0}, std::binary_semaphore{0},
std::binary_semaphore{0}
};
size_t my_rand(size_t min, size_t max)
{
static std::mt19937 rnd(std::time(nullptr));
return std::uniform_int_distribution<>(min, max)(rnd);
}
void test(size_t i)
// 철학자 i가 배고프고 양쪽 이웃이 먹고 있지 않으면 먹습니다.
{
// i: 철학자 번호, 0에서 N-1까지
if (state[i] == State::HUNGRY &&
state[left(i)] != State::EATING &&
state[right(i)] != State::EATING)
{
state[i] = State::EATING;
both_forks_available[i].release(); // 이 먹는 세션에는 더 이상 포크가 필요하지 않습니다.
}
}
void think(size_t i)
{
size_t duration = my_rand(400, 800);
{
std::lock_guard
std::cout << i << " is thinking " << duration << "ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}
void take_forks(size_t i)
{
{
std::lock_guard
state[i] = State::HUNGRY; // 철학자 i가 State::HUNGRY임을 기록
{
std::lock_guard
std::cout << "\t\t" << i << " is State::HUNGRY\n";
}
test(i); // 2개의 포크를 획득하려고 시도(허가)
} // 임계 구역 종료
both_forks_available[i].acquire(); // 포크가 획득되지 않은 경우 차단
}
void eat(size_t i)
{
size_t duration = my_rand(400, 800);
{
std::lock_guard
std::cout << "\t\t\t\t" << i << " is eating " << duration << "ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}
void put_forks(size_t i)
{
std::lock_guard
state[i] = State::THINKING; // 철학자가 State::EATING을 완료했습니다.
test(left(i)); // 왼쪽 이웃이 이제 먹을 수 있는지 확인
test(right(i)); // 오른쪽 이웃이 이제 먹을 수 있는지 확인
// 함수를 종료하여 임계 구역 종료
}
void philosopher(size_t i)
{
while (true)
{ // 영원히 반복
think(i); // 철학자는 State::THINKING입니다.
take_forks(i); // 두 개의 포크를 획득하거나 차단합니다.
eat(i); // 냠냠, 스파게티
put_forks(i); // 두 개의 포크를 테이블에 다시 놓고 이웃이 먹을 수 있는지 확인합니다.
}
}
int main() {
std::cout << "dp_14\n";
std::jthread t0([&] { philosopher(0); }); // [&]는 뒤따르는 모든 변수를 의미합니다.
std::jthread t1([&] { philosopher(1); }); // 람다는 참조로 캡처됩니다.
std::jthread t2([&] { philosopher(2); });
std::jthread t3([&] { philosopher(3); });
std::jthread t4([&] { philosopher(4); });
}
```
이 해결책은 자원에 부분 순서를 할당하여 순환 대기를 방지한다. 모든 자원은 정해진 순서대로 요청되며, 순서와 관련 없는 두 자원은 동시에 사용되지 않는다.
자원 계층 해결책은 C++11로 구현될 수 있다.
```cpp
#include
#include
#include
#include
#include
#include
using namespace std;
int myrand(int min, int max) {
static mt19937 rnd(time(nullptr));
return uniform_int_distribution<>(min,max)(rnd);
}
void philosopher(int ph, mutex& ma, mutex& mb, mutex& mo) {
for (;;) { // prevent thread from termination
int duration = myrand(200, 800);
{
// Block { } limits scope of lock
lock_guard
cout<
}
this_thread::sleep_for(chrono::milliseconds(duration));
{
lock_guard
cout<<"\t\t"<
}
lock_guard
// sleep_for() Delay before seeking second fork can be added here but should not be required.
lock_guard
duration = myrand(200, 800);
{
lock_guard
cout<<"\t\t\t\t"<
}
this_thread::sleep_for(chrono::milliseconds(duration));
}
}
int main() {
cout<<"dining Philosophers C++11 with Resource hierarchy\n";
mutex m1, m2, m3, m4, m5; // 5 forks are 5 mutexes
mutex mo; // for proper output
// 5 philosophers are 5 threads
thread t1([&] {philosopher(1, m1, m2, mo);});
thread t2([&] {philosopher(2, m2, m3, mo);});
thread t3([&] {philosopher(3, m3, m4, mo);});
thread t4([&] {philosopher(4, m4, m5, mo);});
thread t5([&] {philosopher(5, m1, m5, mo);}); // Force a resource hierarchy
t1.join(); // prevent threads from termination
t2.join();
t3.join();
t4.join();
t5.join();
}
```
이 코드는 각 철학자를 스레드로, 포크를 뮤텍스로 표현한다. `philosopher` 함수는 각 철학자의 행동(생각, 배고픔, 식사)을, `main` 함수는 5개의 철학자 스레드를 생성 및 실행한다. 자원 계층은 `philosopher` 함수에서 `mutex`를 잠그는 순서로 강제된다.
또 다른 접근 방식은 중재자(웨이터)를 도입하는 것이다. 철학자는 웨이터에게 허가를 요청하여 포크를 집고, 웨이터는 한 번에 한 명의 철학자에게만 두 포크를 모두 집도록 허가한다. 이 방식은 병렬 처리를 감소시킬 수 있다.
마지막으로, 철학자를 "Even 그룹"과 "Odd 그룹"으로 나누고, "Even 그룹"은 오른쪽 포크를 먼저, "Odd 그룹"은 왼쪽 포크를 먼저 잡도록 하는 방법도 있다.
4. 1. Pascal 코드 예시
pascal
PROGRAM d_p;
CONST
DoomsDay = FALSE;
MONITOR dining_philosophers; { 모니터 선언 시작 }
CONST
Eating = 0;
Hungry = 1;
Thinking = 2;
VAR
i : INTEGER; { 루프 변수 초기화 }
state : ARRAY [0..4] OF INTEGER; { Eating, Hungry, Thinking }
can_eat : ARRAY [0..4] OF CONDITION; { 철학자 각각에 대응, 젓가락이 모일 때까지 배고픈 철학자를 둔다 }
PROCEDURE test(k : INTEGER);
BEGIN
IF (state[k] = Hungry)
AND (state[(k+4) MOD 5] <> Eating)
AND (state[(k+1) MOD 5] <> Eating) THEN
BEGIN
state[k] := Eating;
SIGNALC(can_eat[k]); { 대기 상태의 사람이 있으면 그 상태를 종료시킨다 }
END;
END;
PROCEDURE pickup(i: INTEGER);
BEGIN
state[i] := Hungry;
WRITELN('philosopher ',i,' hungry');
test(i); { 옆 사람은 식사 중인가? }
IF state[i] <> Eating THEN
WAITC(can_eat[i]); { 옆 사람의 식사가 끝날 때까지 기다린다 }
WRITELN('philosopher ',i,' eating');
END;
PROCEDURE putdown(i : INTEGER);
BEGIN
state[i] := Thinking;
WRITELN('philosopher ',i,' thinking');
test( (i+4) MOD 5); { 왼쪽 옆 사람이 식사할 기회를 준다 }
test( (i+1) MOD 5); { 오른쪽 옆 사람이 식사할 기회를 준다 }
END;
BEGIN { 모니터 초기화 }
FOR i := 0 TO 4 DO state[i] := Thinking;
END; { 모니터 정의의 끝 }
PROCEDURE philosopher(i : INTEGER);
BEGIN
REPEAT
pickup(i); { 젓가락을 잡는다 }
putdown(i); { 젓가락을 놓는다 }
UNTIL DoomsDay;
END;
BEGIN { 주 프로그램 }
COBEGIN { 5개의 프로세스를 동시에 시작 }
philosopher(0); philosopher(1); philosopher(2);
philosopher(3); philosopher(4);
COEND;
END
```
다음은 모니터를 사용하여 파스칼로 작성된 해결책의 예시이다. 이 코드는 철학자들의 상태를 `state` 배열에 저장하고, 각 철학자에게 `can_eat`이라는 조건을 할당하여 젓가락이 모두 준비될 때까지 기다리게 한다. `pickup` 프로시저는 철학자가 젓가락을 집는 과정을, `putdown` 프로시저는 젓가락을 내려놓는 과정을 나타낸다. `test` 프로시저는 철학자가 식사할 수 있는 상태인지 확인하고, 식사할 수 있으면 상태를 `Eating`으로 변경하고 대기 중인 철학자에게 신호를 보낸다.
4. 2. Java 코드 예시
java
import java.util.concurrent.Semaphore;
import java.util.Random;
import java.util.Vector;
public class Philosopher extends Thread {
private static final Random rand = new Random();
private static int event = 0;
private static String binary = "";
private int id;
private Semaphore sem;
private static Vector
public Philosopher(int i, Semaphore s) {
id = i;
sem = s;
binary = binary + "0";
}
private void busy() {
try {
Thread.sleep(rand.nextInt(1000));
} catch (InterruptedException e) {}
}
private void thinking() {
String str = "Philosopher " + id + " is thinking";
vector.add(this.addToObject(System.currentTimeMillis(), event, str));
event++;
busy();
}
private void eating() {
String str = "Philosopher " + id + " is hungry and is trying to pick up his chopsticks";
vector.add(this.addToObject(System.currentTimeMillis(), event, str));
event++;
busy();
str = "Philosopher " + id + " is eating";
this.oneToBinary(id);
vector.add(this.addToObject(System.currentTimeMillis(), event, str));
event++;
busy();
str = "Philosopher " + id + " finished eating, and puts away his chopsticks";
this.zeroToBinary(id);
vector.add(this.addToObject(System.currentTimeMillis(), event, str));
event++;
}
private Object[] addToObject(long t, int i, String s) {
Object[] o = new Object[4];
o[3] = s;
o[2] = i;
o[1] = binary;
o[0] = t;
return o;
}
private void oneToBinary(int i) {
binary = binary.substring(0, i) + "1" + binary.substring(i + 1);
}
private void zeroToBinary(int i) {
binary = binary.substring(0, i) + "0" + binary.substring(i + 1);
}
@Override
public void run() {
for (int i = 0; i < 10; ++i) {
thinking();
try {
sem.acquire();
} catch (InterruptedException e) {}
eating();
sem.release();
}
}
public static void main(String[] args) {
final int N = 5;
Semaphore sem = new Semaphore(N, true);
Philosopher[] philosopher = new Philosopher[N];
// 철학자를 생성
for (int i = 0; i < N; i++) {
philosopher[i] = new Philosopher(i, sem);
philosopher[i].start();
}
// 완료를 기다린다
for (int i = 0; i < N; i++) {
try {
philosopher[i].join();
} catch (InterruptedException ex) {
return;
}
}
for (int i = 0; i < vector.size(); i++) {
Object[] o = vector.get(i);
System.out.printf("%d %d %s %s\n", o[0], o[2], o[1], o[3]);
}
}
}
참조
[1]
EWD
[2]
서적
Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings
https://books.google[...]
Birkhäuser
[3]
웹사이트
Communicating Sequential Processes
http://www.usingcsp.[...]
usingcsp.com
[4]
간행물
Operating Systems - Design and Implementation, 3rd edition [Chapter: 2.3.1 The Dining Philosophers Problem]
Pearson Education, Inc.
2006
[5]
EWD
[6]
간행물
Operating Systems - Design and Implementation, 3rd edition [Chapter: 3.3.5 Deadlock Prevention]
Pearson Education, Inc.
2006
[7]
서적
Operating systems : internals and design principles
https://www.worldcat[...]
Pearson PLC
2018
[8]
논문
The Drinking Philosophers Problem
"//www.cs.utexas.edu[...]
1984
[9]
문서
EWD-1000
http://www.cs.utexas[...]
[10]
서적
Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings
https://books.google[...]
Birkhäuser
[11]
웹사이트
Communicating Sequential Processes
http://www.usingcsp.[...]
usingcsp.com
2012-07-16
[12]
웹사이트
海外での例
http://msdn.microsof[...]
[13]
문서
EWD-310
http://www.cs.utexas[...]
[14]
문서
EWD-123
http://www.cs.utexas[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com