|
Go back OS Review Device Driver NS Tools Home Papers Daily Link To Main |
9. 철학자들의 만찬 (The Dining-Philosophers Problem)
철학자들의 만찬에 대한 문제라,,, 웬지 뭔가 있어보이는듯한 멋진 제목인듯 합니다만, 이 상황의 설정을 잘 뜯어보면 말그대로 그냥 밥쳐먹고 몽상하는게 전부인 똘아이 집단에 대한 이야기 입니다. 식사하는 철학자들의 문제는 오에스론에 있어서 꽤 유명한 패러다임인지 전에도 어디에선가 한번 그 제목만을 들어본듯한데, 이기회에 여러분들도 이것이 어떤 문제제기를 하고 있는 것이며, 이 이야기가 주는 교훈이 무엇인지를 한번 잘 음미해보시지요. 뭐 일하지 않는 자여 먹지도 말라같은건 아닙니다요. 백수님들 힘내십쇼. 먼저 5명의 철학자가 원형의 식탁위에 둘러 앉아있습니다. 그들은 평생토록 하는 일이라고는 생각!하거나 또는 먹는것! 딱 이 두가지입니다. 여기서 조금 특이한 상황이 하나 연출되는데, 그것은 이들은 위생관념이 전혀 없는 이 인간들이 젓가락 한짝씩만을 자신의 접시 옆에 놓아두고 두사람이 한짝을 공유하고 있다는 전제이죠. 그림으로 한번 멋지게 승화시켜 보겄습니다.
젓가락한쪽
철학자 철학자
젓가락한쪽 젓가락한쪽
철학자 철학자
젓가락한쪽 젓가락한쪽
철학자
예술입니다. 이 철학자들은 뭔가 생각하고 있을시에는 옆 철학자와 절대 이야기 조차 안하며 생각에만 몰두하다가 제각자 배고플 즈음에는 시도때도 없이 자신의 양 옆에 놓여있는 젓가락 한짝씩을 가져다가 한쌍을 만든뒤 밥을 먹어댑니다. 물론 배고픈 때는 모든 철학자 멋대로입니다. 식사가 끝나면 자신의 젓가락들을 가지런이 양옆에 다시 놓아두고 다시 고뇌를 하게 되지요. 이문제는 정말 고전적인 싱크(synchronization)문제라고 책에서는 언급을 합니다. 여러개의 프로세스와 여러개의 리소스 사이에서의 데드락(deal-lock)과 배고픔(starvation)이 발생할수 있는 상황에 대한 모델인 것입니다. 본 상황에서의 가장 중요한 목적은 위의 철학자들을 모두 행복하게 만들어 주는 것이죠. 이들중 누구 하나라도 배고파서 결국 죽어버리거나(배고픔), 서로 한짝씩 젓가락을 들고 나머지 하나가 젓가락을 놔주기를 평생 기다리다가 굶어죽는 경우(데드락)를 최대한 방지하는 방법을 찾아야 하는겁니다. 자, 이상황에 대한 해결책을 그렇다면 좀더 컴퓨터틱하게 모델링하는 방법을 한번 살펴보죠. 먼저 var chopstick : array [0..4] of semaphore all elememts of chopstick are initialized to 1 하나의 좋은 아이디어는 각각의 젓가락을 하나의 세마포어로, 그리고 철학자를 하나의 프로세스로 설정하는 것입니다. 본 모델은 세마포어를 이용하여 싱크를 구현하는 좋은 예이며, 이때의 세마포어 chopstick은 결국 현재 시스템에 남아있는 사용가능한 리소스(resourse)의 갯수!를 상징하게 되는것이죠. 즉, 세마포어를 이용하여 남은 리소스의 갯수를 트래킹 하는것입니다(바이너리 세마포어여요). 이때 만일 세마포어를 이용하지 않고 그냥 평범한 변수나 IPC중 하나인 쉐어드 메모리만을 이용한다면 어떤 상황이 펼쳐질까요? (뉴스판에 한번 맘껏 자신의 의견 피력해보심이 어떨런지? ) 다음의 코드를 한번 음미해주시길.
repeat wait(chopstick[i]); wait(chopstick[i+1 mod 5]); ... eat ... signal(chopstick[i]); signal(chopstick[i+1 mod 5]); ... think ... until false; 위의 코드는 바로 철학자i를 나타내주는 구조입니다. 여기서 우리는 전장에서 등장했던 wait()과 signal()을 이 철학자의 만찬에서 어떤 행위로 상징이 되는지를 눈여겨 볼 필요가 있을겁니다. 철학자들은 젓가락을 취하기 위해서 wait()을 콜하게 되고, 다 쓴 젓라락을 다시 놓기 위하여 signal()을 콜하게 되는 것이죠. 위의 코드에서 조금 어렵게 보일수 있는 i+1 mod 5는 뭘까요? x mod y 라는 연산은 x를 y로 나눈다음 나온 나머지 값을 의미하지요. 고로 i=5일경우 (5번(마지막) 젓가락) 그 결과는 1이 나온다는 사실((1+5)/5의 나머지)에서 결국 원형순환적!으로 바로 옆에 놓여있는 젓가락을 의미하게 되는 것입니다. 결국 위의 코드는 처음 철학자 자신의 왼쪽(또는 오른쪽)에 놓여있는 젓가락을 먼저 들고, 그다음에 자신의 오른쪽(또는 왼쪽) 젓락락을 든것을 확인한 다음 안전하게 먹고~ 자신이 들고있던 왼쪽 젓가락을 놓고, 마지막으로 오른쪽 젓가락을 놓는 과정을 기술해주고 있죠. 위에서 제공된 코드는 서로 인접한 철학자가 젓가락을 드는 사건을 방지해 주긴 하지만 아킬레스건이 되는 경우의 수가 하나 있습니다. 어떤경우일까요? 바로 모든 철학자들이 한순간 배가 고파져서 일제히 자신의 왼쪽(또는 오른쪽)젓가락을 들게 되는 경우입니다. 바로 데드락이 발생해버리죠. 한 젓가락을 들고 두번째 wait()에 걸려서 결국 철학자들은 평생 젓가락 한개 든채로 굶어죽는 집단 참극이 일어나게 됩니다. 정말 생각하면 생각할수록 미친놈들이 아닐수 없군요. 이 데드락을 방지하기 위하여 몇가지 해결책을 제시해본다면 다음과 같습니다. 1. 최대한 4명의 철학자가 테이블에 앉도록 만든다. 2. 양옆의 젓가락이 모두다 제공 가능한지를 먼저 확인후에 든다. 3. 홀수번째의 철학자는 처음에 왼쪽의 젓가락을 들고, 짝수번째의 철학자는 처음에 오른쪽의 젓가락을 들게 만든다. 4. 찍찍이(jjickjjickii)를 저만찬에 끼워서 철학자들 밥맛 떨어지게 만든다. 제 개인적으로는 특히 3번과 4번이 참으로 획기적인 아이디어로 느껴집니다만은, 역시 모두 한 철학자가 배고파 죽는 사태는 방지하지 못하는 약점을 가지고 있습니다. 세마포어가 프로세스 싱크를 위한 참으로 간편하고 효과적인 메카니즘을 제공해주기는 하지만, 전장에서도 말씀드렸듯이 조그마한 착각으로 인한 실수는 찝어내기조차 힘든 에러를 유발하게 됩니다. 더구나 이때의 에러는 특정한 순서로 프로세스들이 리소스를 요구할때만 나타나고, 그 에러가 나타날 가능성이 반드시 있음에도 희박하기에 발견해 내기가 무지하게 어려워요. 그렇기에 이러한 문제를 극복하기 위하여 또한번 컴퓨터 공학자들은 고민을 하게 되고 이번에는 몇가지의 고레벨 랭귀지 구조체(high-level language construct)를 고안해 내게 됩니다. 대표적인 것이 크리티컬리젼(Critical Region)과 모니터(Monitors)인데 둘 다를 다루기엔 솔직히 벅차므로 그중 후자인 모니터를 간략하게 다뤄보도록 하지요. 모니터는 하나의 구조체(construct)입니다. 모니터 타입(type)은 그 안에 변수와 프로시져(함수가 아닙니다. 프로시져는 리턴값이 없죠?)를 모두 포함하게 되므로 마치 C++의 클래스와 비슷하게 정의됩니다. 여기서 중요한 점은 아무 프로세스나 모니터 타입내의 변수나 함수에 직접 접근할수가 없으며, 반드시 모니터 안에서 정의된 프로시져를 통해서만 모니터 내에서 변수에 대한 접근이 허용되지요. 모니터 구조체는 오직 한개의 프로세스만이 모니터 내에서 활성화 되는것을 보장해주기에 뮤텍스에 대한 장치를 프로그래머가 명시할 필요가 없다는 편리한 점도 가지고 있어요. 모니터에는 또한 가지 결정적 역할을 수행하는 옵션이 있는데, 바로 조건(condition) 구조체입니다. 바로 이 조건구조체를 조작할 수 있는 함수는 오직 wait과 signal이죠. 컨벤션및 그 기능이 세마포어와는 약간 다르니 염두해 주시고 아래에 소개되는 모니터를 이용한 데드락 없는! 철학자들의 만찬의 해법을 봐주셔요. 모니터에 대한 정의입니다.
type dining-philosophers = monitor
var state : array[0..4] of (thinking, hungry, eating)
/* 바로 조건 구조체에 대한 정의입니다. */
var self : array[0..4] of condition
procedure entry pickup(i:0..4);
begin
state[i]:=hungry;
test(i);
if state[i]!=eating then self[i].wait;
end;
procedure entry putdown(i:0..4);
begin
state[i]:=thinking;
test(i+4 mod 5);
test(i+1 mod 5);
end;
procedure test(k:0..4);
begin
if state[k+4 mod 5]!=eating
and state[k]=hungry
and state[k+1 mod 5]!=eating
then begin
state[k]:=eating;
self[k].signal;
end;
end;
begin
for i:=0 to 4
do state[i]:=thinking;
end;
그럼, 모니터의 내부부터 한번 살펴볼까요? 제일먼저 5개짜리 일차원 배열을 정의하는데 그 안에는 3가지의 상태 변수('생각함', '배고픔', '식사중')중 하나를 넣어줄수 있어요, 그리고 또 5개짜리 일차원 배열에는 조건을 담아주되 반드시 .signal또는 .wait으로만 엑세스가 가능하겠죠? 처음 pickup()이라는 프로시져에서는 제일먼저 철학자의 상태를 '배고픔'으로 지정을 해줍니다. 흠,,,솔직히 이거 젓가락을 들기위해서 배고프다고 어거지 쓰는거 같기도 하고,,,하여간 닭이 먼저이냐 달걀이 먼저이냐 같은 논의라고 생각할수 있겠군요. 그뒤에 test()로 뭔가를 판별합니다. test()는 뭔가를 조사한뒤 상태변수를 재지정하는듯 한데, 만일 그 상태가 '식사중'으로 전환되지 못할 경우에는 .wait()을 호출하는군요. 근데, 왜 전환을 못했지??? 결과적으로 젓가락이 없어서 그럴거 뻔하잖애요. 두번째 젓가락을 놓는 프로시져인 putdown()은 역시 예상했던 데로 상태를 다시 생각함으로 지정을 해준뒤 옆 철학자들을 test()로 뭔가 또 판별하는군요. 오른편 철학자와, 왼편 철학자 이 둘을 모두 조사한다는 것을 알수 있을뿐입니다. 마지막 프로시져는 바로 계속 등장하는 test()에 대한 정의가 있습니다. 제일먼저 test()는 테스트를 요청한 철학자의 왼편(또는 오른편)의 철학자의 상태가 '식사중'인지를 살펴봐서 만일 먹지않고 있다면 다음 조건을 또 보게되지요. 다음 조건은 요청한 철학자의 상태가 배고픔인지를 보는데, 만일 상태가 배고픔이 맞다면 또하나의 조건을 더 살펴보게 됩니다. 이번에는 요청한 철학자의 오른편(또는 왼편)의 철학자가 '식사중'인지를 봐서 위의 세가지 조건에 모두 부합되면(양옆의 철학자가 모두 식사를 안하고 있으며 요청한 철학자는 '배고픔'일때죠) 그제서야 요청한 철학자의 상태를 '식사중'으로 전환을 시키고 조건변수에 .signal을 호출해요. 만일 양옆의 철학자들중 한사람이라도 '식사중'이거나 test()를 호출한 사람이 '배고픔'이 아닌 상태라면 아무짓도 안하고 조용히 테스트를 끝내지요. 마지막은 그냥 상태변수 state[i]를 모두 '생각함'으로 초기화 시키는 과정일 뿐입니다. 위의 논리를 잘 따라온 분이시라면, .wait()과 .signal()이 어떤 열쇄를 쥐고 있다는 사실을 느끼시겠죠? 먼저 .wait()은 누군가가 .signal()을 호출해 주기 전까지는 프로세스를 더이상 진행을 못하게 하고, .signal()은 정확히 딱 한개!의 .wait()으로 걸려있는 프로세스를 깨워주는 역할을 합니다. 둘은 세마포어의 wait()과 signal()와 비슷해 보이지만, 결정적 차이점은 만일 아무도 .wait()을 전에 호출하지 않았다면 백번 .signal()을 호출해봐야 아무일 없다는 사실입니다. 세마포어는 각 wait()과 signal()은 해당 세마포어의 값을 반드시 감소시키거나 증가시켜주었다는 사실을 상기하셔요. 위의 둘은 내부적으로 세마포어와 몇가지 카운터를 이용해서 구현한다는정도만 여기서는 알아두셔도 무방합니다. 궁금해서 미치겠는분, 교과서 보십쇼. 봐도 모르겄으면 재경선배나 성일선배에게 질문 때리십쇼. 위의 알고리즘을 떠나기 전에 한가지 짚고 넘어가야 할 부분이 있는데, putdown()에서 양 옆의 철학자들을 테스트로 보내는 부분입니다. 이경우를 해석해 보면, 식사를 마친뒤 양 옆의 철학자들이 혹시 자신의 젓가락만을 바라보며 침을 질질 흘리고 있지 않았는지를 확인하는 경우이죠. 철학자가 젓가락을 기다리는 경우(.wait()을 콜한경우)는 언제나 양옆의 철학자중 한쪽이 젓가락을 들고 있는 경우밖에는 없기에 그들로 하여금 이번엔 식사를 하라는 .signal()을 이때 보내주게 되는 것입니다. 이제 이 모니터를 사용하려면,먼저 dp라는 dining-philosophers type의 변수에 대한 인스턴스(instance:변수를 선언후 그것을 구체적으로 메모리에 생성시켜놓은 상태이죠)를 만들고 다음과 같이 철학자가 식사를 하게 되는 순간을 기술해 줄 수 있습니다.
dp.pickup(i);
...
eat
...
dp.putdown(i);
깔끔!하게 우리는 하이레벨 구조체인 모니터를 이용하여 싱크문제를 무지 난잡한 설명으로 풀어냈습니다요. 차례로 등장하는 알고리즘들을 보면서 무슨 생각이 드시나요. 전 개인적으로 밥벌이로 이짓 못해먹을지도 모르겄다는 좌절이 엄습해 왔어요. 허나 한가지 뼈저리게 느끼는 사실이 있었다면 좋은 알고리즘이란 정말 1억분의 1의 확률로 일어날 사건일지라도 미리 준비를 해놓는 알고리즘이라는 사실이죠. 물론 더 짧고 간결하면 그만큼 더 빠르기에 훌륭한 알고리즘다라는 사실은 두말할 나위도 없고요. 이상으로 6장을 끝내면서 꼬리말을 붙여보면, 사실 논리라는것이 복잡한 말때문에 더욱 어려워질수도 있는데, 저의 난잡한 설명으로 인해 오히려 쉽게 이해할수 있는 분들까지 어리둥절해하시는건 아닐까 싶더군요. 물론 간결하게 알고리즘만 제시해주고 각자가 알아서 해석하라고 할까도 생각해 보았지만, 왠지 그건 제스스로가 주어진 책무를 회피하는 것이라는 느낌이 들기에 불필요한 부분일지라도 자세하게 주석을 달아보았습니다. 또한! 제 주석이 반드시 옳다고는 할수 없습니다. 만일 그런부분을 여러분들이 발견해서 지적해주신다면 전 정말 기쁠겁니다. 엉뚱하게 알고있는것보다는 차라리 모르는게 낫다라는 말이 틀린 말이 아니거든요. 어쨋든, 꽤 어려운 산을 저와 넘어주신 여려분 수고했어요 :) 다음장에서는 근래 자주 등장했던 말인 데드락을 좀더 체계화시키고 세련된 모델로 처리하는 방법을 탐구해볼 예정입니다. 그럼 그때까지,,,모비우스좀 어케 해봐유. 어떻게 살아있는 날보다 죽어있는 날이 더 많은거 같애. -duffer 경준 (http://vorlon.cwru.edu/~kxm73)
|