식사 철학자의 문제

Dining philosophers problem
식생활 철학자의 문제에 대한 삽화.

컴퓨터 과학에서 식사 철학자의 문제는 동기 문제와 이를 해결하기 위한 기술을 설명하기 위해 동시 알고리즘 설계에 자주 사용되는 예제 문제입니다.

1965년 Edsger Dijkstra에 의해 학생 시험 연습으로 처음 고안되었으며, 테이프 드라이브 주변기기에 대한 컴퓨터 액세스 경쟁을 통해 제시되었습니다.얼마 지나지 않아 토니 호어는 문제의 현재 형태를 [1][2][3][4]제시하였다.

문제문

다섯 명의 철학자가 한 테이블에 모여 식사를 한다.철학자는 각자 식탁에 설 자리가 있다.이 경우 그들의 철학적인 문제는 제공되는 요리가 두 개의 포크로 먹어야 하는 스파게티의 일종이라는 것이다.

각각의 접시 사이에는 포크가 있다.각 철학자는 오로지 번갈아 생각하고 먹을 수 있을 뿐이다.게다가 철학자는 왼쪽과 오른쪽 포크가 모두 있을 때만 스파게티를 먹을 수 있다.따라서 두 개의 포크는 그들의 가장 가까운 이웃이 먹지 않고 생각하고 있을 때만 사용할 수 있을 것이다.철학자가 음식을 다 먹고 나면, 그들은 두 개의 포크를 모두 내려놓습니다.문제는 철학자가 굶주리지 않도록 어떻게 요리법을 설계하느냐이다; 즉, 어떤 철학자도 언제 먹고 싶거나 생각하기를 원하는지 알 수 없다고 가정하면, 각각은 영원히 먹는 것과 생각하는 것 사이를 번갈아 갈 수 있다.

문제

이 문제는 진행이 불가능한 시스템 상태인 교착 상태를 피하기 위한 과제를 설명하기 위해 설계되었습니다.이 문제에 대한 적절한 해결책이 명확하지 않음을 확인하기 위해 각 철학자가 다음과 같이 행동하도록 지시된 제안을 고려하십시오.

  • 왼쪽 포크를 사용할 수 있을 때까지 생각하고, 사용할 수 있을 때 집는다.
  • 올바른 포크가 사용 가능할 때까지 생각하고, 사용 가능할 때 집는다.
  • 두 개의 포크가 모두 잡혔을 때 정해진 시간 동안 먹는다;
  • 왼쪽 포크를 내려놓는다;
  • 오른쪽 포크를 내려놓는다.
  • 처음부터 다시 하다

하지만, 그들은 각각 미정의 시간 동안 생각할 것이다.그리고 왼쪽 포크를 들고 생각하면서 접시의 오른쪽을 바라보면서 오른쪽 포크가 없어서 굶을 때까지 먹을 수 없게 될지도 모릅니다.

자원 부족, 상호 배제 및 라이브록은 다른 유형의 시퀀스 및 액세스 문제입니다.

솔루션

다이크스트라의 해

Dijkstra의 솔루션은 철학자당 하나의 세마포, 철학자당 하나의 상태 변수를 사용합니다.이 솔루션은 리소스 계층 [5][6]솔루션보다 더 복잡합니다.이것은 Dijkstra 솔루션의 C++20 버전과 Tanenbaum의 변경 사항입니다.

#실패하다 <iostream> #실패하다 <크로노> #실패하다 <blocks> #실패하다 <138x> #실패하다 <세마포> #실패하다 <blocks>  컨스턴트 인트 N = 5;          // 철학자 수 열거하다 {   생각중=0,             // 철학자는 생각하고 있다   배고픈=1,               // 철학자가 포크를 구하려고 합니다.   밥먹어=2,               // 철학자는 먹고 있다 };    #왼쪽 정의(i+N-1)%N// 왼쪽 네이버 수 #오른쪽 정의 (i+1) %N// i의 오른쪽 네이버 수  인트 주[N];             // 어레이: 모든 사용자의 상태를 추적합니다. 표준::뮤텍스 뮤텍스_;        // 중요 지역에 대한 상호 제외 표준::바이너리_세마포어 s[N]{0, 0, 0, 0, 0};                            // 철학자당 하나의 세마포 표준::뮤텍스 모;            // 동기화된 cout의 경우  인트 마이랜드(인트 분, 인트 맥스.) {   정적인 표준::mt1937 rnd(표준::시간을(특수));   돌아가다 표준::균일_int_distribution<< 고객명 >>님(분,맥스.)(rnd); }  무효 시험(인트 i) {        // i: 철학자 번호(0 ~N-1)   한다면 (주[i] == 배고픈     & & 주[왼쪽] != 밥먹어 & & 주[맞다] != 밥먹어) {     주[i] = 밥먹어;     s[i].풀어주다();   } }  무효 생각해(인트 i) {   인트 지속 = 마이랜드(400, 800);   {     표준::lock_guard< >표준::뮤텍스> gmo(모);     표준::외치다<< >i<< >"라고 생각한다.<< >지속<< >「ms.\n";   }   표준::this_discriptions(이_discriptions)::sleep_for(표준::크로노::밀리초(지속)); }  무효 테이크아웃(인트 i) {  // i: 철학자 번호(0 ~N-1)   뮤텍스_.잠그다();          // 위험 영역 입력   주[i] = 배고픈;      // 철학자 I가 배고프다는 사실을 기록하다   {     표준::lock_guard< >표준::뮤텍스> gmo(모);     표준::외치다<< >"\t\t"<< >i<< >배가 고프다\n";   }   시험(i);                // 포크 2개 획득 시도   뮤텍스_.언락();        // 위험 영역 종료   s[i].얻다();         // 포크를 획득하지 않은 경우 차단 }   무효 먹는다(인트 i) {   인트 지속 = 마이랜드(400, 800);   {     표준::lock_guard< >표준::뮤텍스> gmo(모);     표준::외치다<< >"\t\t\t"<< >i<< >"먹다"<< >지속<< >「ms.\n";   }   표준::this_discriptions(이_discriptions)::sleep_for(표준::크로노::밀리초(지속)); }  무효 put_internals(풋)_internals(스위치(인트 i) {   // i: 철학자 번호(0 ~N-1)   뮤텍스_.잠그다();          // 위험 영역 입력   주[i] = 생각중;    // 철학자가 다 먹었다   시험(왼쪽);             // 왼쪽 인접 라우터가 먹을 수 있는지 확인합니다.   시험(맞다);            // 올바른 이웃이 식사를 할 수 있는지 확인합니다.   뮤텍스_.언락();        // 위험 영역 종료 }  무효 철학자(인트 i) { // i: 철학자 번호(0 ~N-1)   하는 동안에 (진실의) {          // 영원히 반복     생각해(i);             // 철학자는 생각하고 있다     테이크아웃(i);        // 포크 또는 블록 2개 획득     먹는다(i);               // 얌-스파게티     put_internals(풋)_internals(스위치(i);         // 양쪽 포크를 테이블 위에 다시 놓습니다.   } }  인트 주된() {   표준::외치다<< >"dp_14\n";    표준::실 t0([&] {철학자(0);});   표준::실 t1([&] {철학자(1);});   표준::실 t2([&] {철학자(2);});   표준::실 t3([&] {철학자(3);});   표준::실 t4([&] {철학자(4);});   t0.합류하다();   t1.합류하다();   t2.합류하다();   t3.합류하다();   t4.합류하다(); }

test() 함수와 take_forks() 및 put_forks()에서의 그 사용은 Dijkstra 솔루션을 교착 상태로 만듭니다.

리소스 계층 솔루션

이 솔루션은 리소스(이 경우 포크)에 부분 순서를 할당하고 모든 리소스가 순서대로 요구되며 순서와 무관한2개의 리소스가 동시에 단일 작업 유닛에 의해 사용되지 않는다는 규칙을 확립합니다.여기서 자원(포크)은 1~5까지 번호가 매겨지며, 각 작업 단위(철학자)는 항상 사용할 예정인 2개의 포크 중에서 낮은 번호의 포크를 먼저 선택한 다음 높은 번호의 포크를 선택합니다.각각의 철학자들이 포크를 내려놓는 순서는 중요하지 않다.이 경우 5명의 철학자 중 4명이 동시에 낮은 번호의 포크를 집어들면 가장 높은 번호의 포크만 테이블에 남게 되므로 5번째 철학자는 어떤 포크도 집어들 수 없게 된다.게다가, 오직 한 명의 철학자만이 가장 높은 번호의 포크에 접근할 수 있게 될 것이고, 그래서 그는 두 개의 포크를 사용하여 식사를 할 수 있게 될 것이다.

리소스 계층 솔루션은 교착 상태를 방지하지만 특히 필요한 리소스 목록을 미리 완전히 알지 못하는 경우 항상 실용적인 것은 아닙니다.예를 들어, 작업단위가 자원 3과 5를 보유하고 있으며 자원 2가 필요하다고 판단될 경우, 작업단위는 자원 2를 취득하기 전에 5, 그 후 3을 해방하고 그 순서로 재취득해야 합니다.다수의 데이터베이스 레코드에 액세스하는 컴퓨터 프로그램은 새 레코드에 액세스하기 전에 번호가 높은 레코드를 모두 공개해야 하는 경우 효율적으로 실행되지 않으므로 이 방법은 [2]이 목적에 적합하지 않습니다.

리소스 계층 솔루션이 공평하지 않습니다.만약 철학자 1이 포크를 가져가는 것이 느리고, 철학자 2가 재빨리 생각하고 포크를 다시 집어 든다면, 철학자 1은 결코 두 포크를 모두 집지 못할 것이다.공정한 해결책은 철학자가 다른 철학자에 비해 얼마나 느리게 움직이든지 상관없이 각각의 철학자가 결국 먹을 것을 보장해야 한다.

다음 소스코드는 3명의 철학자를 위한 자원 계층 솔루션의 C++11 구현입니다.sleep_for() 함수는 비즈니스 [7]로직을 사용하여 통상적인 시간을 시뮬레이트합니다. 

#실패하다 <iostream> #실패하다 <크로노> #실패하다 <138x> #실패하다 <blocks> #실패하다 <blocks> #실패하다 <ctime> 사용. 네임스페이스 표준; 인트 마이랜드(인트 분, 인트 맥스.) {   정적인 mt1937 rnd(시간을(특수));   돌아가다 균일_int_distribution<< 고객명 >>님(분,맥스.)(rnd); } 무효 필(인트 ph, 뮤텍스& 엄마., 뮤텍스& MB, 뮤텍스& 모) {   위해서 (;;) {  // 스레드 종료를 방지합니다.     인트 지속 = 마이랜드(200, 800);     {       // 블록 { }이(가) 잠금 범위를 제한함       lock_guard< >뮤텍스> gmo(모);       외치다<< >ph<< >"라고 생각한다.<< >지속<< >「ms.\n";     }     this_discriptions(이_discriptions)::sleep_for(크로노::밀리초(지속));     {       lock_guard< >뮤텍스> gmo(모);       외치다<< >"\t\t"<< >ph<< >배가 고프다\n";     }     lock_guard< >뮤텍스> gma(엄마.);     this_discriptions(이_discriptions)::sleep_for(크로노::밀리초(400));     lock_guard< >뮤텍스> gmb(MB);     지속 = 마이랜드(200, 800);     {       lock_guard< >뮤텍스> gmo(모);       외치다<< >"\t\t\t"<< >ph<< >"먹다"<< >지속<< >「ms.\n";     }     this_discriptions(이_discriptions)::sleep_for(크로노::밀리초(지속));   } } 인트 주된() {   외치다<< >"리소스 계층에 Philosophers C++11 식사"\n";   뮤텍스 m1, m2, m3;   // 포크 3개는 뮤텍스 3개   뮤텍스 모;           // 적절한 출력을 위해   // 3 철학자는 3 스레드입니다.   실 t1([&] {필(1, m1, m2, 모);});   실 t2([&] {필(2, m2, m3, 모);});   실 t3([&] {필(3, m1, m3, 모);});  // 자원 계층   t1.합류하다();  // 스레드 종료 방지   t2.합류하다();   t3.합류하다(); }

중재자 솔루션

또 다른 접근법은 철학자가 웨이터와 같은 중재자를 도입하여 포크 또는 포크 둘 다 픽업할 수 있도록 하는 것이다.포크를 집으려면 철학자는 웨이터에게 허락을 구해야 한다.웨이터는 철학자가 두 개의 포크를 모두 집어들 때까지 한 번에 한 명의 철학자에게만 허락합니다.포크를 내려놓는 것은 항상 허용된다.웨이터는 뮤텍스로 사용할 수 있습니다.새로운 중심 실체(웨이터)를 도입하는 것 외에, 이 접근방식은 평행성을 감소시킬 수 있다.철학자가 식사를 하고 있고 그의 이웃 중 하나가 포크를 요청하고 있다면, 다른 모든 철학자는 포크가 아직 사용 가능하더라도 이 요구가 충족될 때까지 기다려야 한다.

동시 알고리즘 설계

테이블 내 식사 인원 제한

William[8] Stallings가 제시한 해결책은 최대 n-1 철학자들이 언제든지 앉을 수 있도록 하는 것입니다.마지막 철학자는 누군가 "앉기" 전에 식사를 마칠 때까지 기다렸다가 어떤 포크로든 접근을 요청해야 할 것이다.이를 통해 적어도 한 명의 철학자가 항상 두 가지 포크를 모두 획득할 수 있으므로 시스템이 진보할 수 있습니다.

샨디/Misra 솔루션

1984년, K. Mani Chandy와 J[9]. Misra는 다이크스트라의 해결책과는 달리 임의의 수의 자원을 위해 임의의 에이전트1(번호 P, ..., Pn)가 경쟁할 수 있도록 하는 식사 철학자들의 문제에 대한 다른 해결책을 제안했다.또한 완전히 분산되어 초기화 후 중앙 권한이 필요하지 않습니다.다만, 「철학자는 서로 대화하지 않는다」(요청 메세지로 인해)의 요건을 위반하고 있습니다.

  1. 리소스를 경쟁하는 철학자의 각 쌍에 대해 포크를 생성하여 ID가 작은 철학자에게 전달합니다(에이전트n P의 경우 n).각각의 포크는 더럽거나 깨끗할 수 있다.처음에는 모든 포크가 더럽습니다.
  2. 철학자가 일련의 자원을 사용하고 싶을 때(즉, 먹는 것), 철학자는 경쟁하는 이웃으로부터 포크를 얻어야 한다고 말했다.철학자가 가지고 있지 않은 모든 포크에 대해 그들은 요청 메시지를 보냅니다.
  3. 포크를 든 철학자가 요청 메시지를 받았을 때, 그들은 포크가 깨끗하면 보관하고 더러우면 포기한다.만약 철학자가 포크를 보낸다면, 그들은 그렇게 하기 전에 포크를 청소한다.
  4. 철학자가 음식을 다 먹고 나면, 모든 포크가 더러워진다.만약 다른 철학자가 이전에 포크 중 하나를 요청했다면, 막 식사를 마친 철학자가 포크를 청소해서 보낸다.

이 솔루션은 또한 많은 동시성을 허용하며 임의로 큰 문제를 해결할 수 있습니다.

그것은 또한 기아 문제를 해결한다.청결/더러운 라벨은 가장 "부족한" 프로세스를 우선시하는 방법으로서 작용하며, 막 "먹힌" 프로세스에는 단점이 있습니다.철학자들이 중간에 포크를 사용하지 않고 연속해서 두 번 먹는 것을 허용하지 않는 것과 그들의 해결책을 비교할 수 있다.Chandy와 Misra의 솔루션은 그것보다 유연하지만, 그러한 방향으로 향하는 요소를 가지고 있습니다.

분석에서, 그들은 포크의 분포와 깨끗하고 더러운 상태로부터 선호도 수준의 시스템을 도출한다.그들은 이 시스템이 지향성 비순환 그래프를 설명할 수 있다는 것을 보여주며, 만약 그렇다면, 프로토콜의 연산은 그 그래프를 순환 그래프로 바꿀 수 없다.이것에 의해, 교착 상태가 발생하지 않게 됩니다.그러나 시스템이 모든 철학자들이 왼쪽 포크를 잡고 있는 것처럼 완벽하게 대칭적인 상태로 초기화되면 그래프는 처음에 순환하며, 그들의 솔루션은 교착 상태를 막을 수 없습니다.ID가 낮은 철학자가 더티 포크를 가지도록 시스템을 초기화하면 그래프가 처음에는 비순환적입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Dijkstra, Edsger W. EWD-1000 (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (설명)
  2. ^ a b J. Díaz; I. Ramos (1981). Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings. Birkhäuser. pp. 323 , 326. ISBN 978-3-540-10699-9.
  3. ^ Hoare, C. A. R. (2004) [originally published in 1985 by Prentice Hall International]. "Communicating Sequential Processes" (PDF). usingcsp.com.
  4. ^ Tanenbaum, Andrew S. (2006), Operating Systems - Design and Implementation, 3rd edition [Chapter: 2.3.1 The Dining Philosophers Problem], Pearson Education, Inc.
  5. ^ Dijkstra, Edsger W. EWD-310 (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (설명)
  6. ^ Tanenbaum, Andrew S. (2006), Operating Systems - Design and Implementation, 3rd edition [Chapter: 2.3.1 The Dining Philosophers Problem], Pearson Education, Inc.
  7. ^ Tanenbaum, Andrew S. (2006), Operating Systems - Design and Implementation, 3rd edition [Chapter: 3.3.5 Deadlock Prevention], Pearson Education, Inc.
  8. ^ Stallings, William (2018). Operating systems : internals and design principles (9th ed.). Harlow, Essex, England: Pearson. p. 310. ISBN 1-292-21429-5. OCLC 1009868379.
  9. ^ 챈디, K.M.; 미스라, J. (1984년)음주 철학자의 문제프로그래밍 언어 및 시스템상의 ACM 트랜잭션.

참고 문헌

  • Silberschatz, Abraham; Peterson, James L. (1988). Operating Systems Concepts. Addison-Wesley. ISBN 0-201-18760-4.
  • 다이크스트라, E. W. (1971년, 6월)순차 프로세스의 계층적 순서 지정.Acta Informatica 1(2): 115~138.
  • Lehmann, D. J., Rabin M. O, (1981)자유선택의 이점:식사 철학자의 문제에 대한 대칭적이고 완전히 분산된 해결책.프로그래밍 언어의 원리 1981(POPL'81) 페이지 133–138.

외부 링크