哲學家進餐問題

哲學家進餐問題是由荷蘭學者Dijkstra提出的經典的同步問題之一。

基本介紹

  • 中文名：哲學家進餐問題
  • 產生背景：一大類並發控制問題的典型例子
  • 約束條件：只有拿到兩隻筷子哲學家才能吃飯
  • 信號量機制：筷子是臨界資源
產生背景,問題描述,死鎖問題,管程機制,

產生背景

由荷蘭學者Dijkstra提出的哲學家進餐問題(The Dinning Philosophers Problem)是經典的同步問題之一。哲學家進餐問題是一大類並發控制問題的典型例子，涉及信號量機制、管程機制以及死鎖等作業系統中關鍵問題的套用，在作業系統文化史上具有非常重要的地位。對該問題的剖析有助於深刻地理解計算機系統中的資源共享、進程同步機制、死鎖等問題，並能熟練地將該問題的解決思想套用於生活中的控制流程。

問題描述

哲學家進餐問題描述有五個哲學家，他們的生活方式是交替地進行思考和進餐，哲學家們共用一張圓桌，分別坐在周圍的五張椅子上，在圓桌上有五個碗和五支筷子，平時哲學家進行思考，飢餓時便試圖取其左、右最靠近他的筷子，只有在他拿到兩支筷子時才能進餐，該哲學家進餐完畢後，放下左右兩隻筷子又繼續思考。
約束條件
(1)只有拿到兩隻筷子時，哲學家才能吃飯。
(2)如果筷子已被別人拿走，則必須等別人吃完之後才能拿到筷子。
(3)任一哲學家在自己未拿到兩隻筷子吃完飯前，不會放下手中已經拿到的筷子。
信號量機制
筷子是臨界資源，一段時間只允許一位哲學家使用。為了表示互斥，用一個信號量表示一隻筷子，五個信號量構成信號量數組。本文中算法用類C語言描述偽碼算法。算法描述如下：n用五支筷子的信號量構成信號量數組：
Semaphore chopstick[5]={1，l，1，l，1}；
p(stick[i])；
p(stick[(i+1) % 5])；
進餐；
v(stick[i])；
v(stick[(i+1) % 5])；
思考；
當哲學家飢餓時，總是先去拿他左邊的筷子，執行wait(chopstick[I])，成功後，再去拿他右邊的筷子，執行wait(chopstick[I+1]%5)；成功後便可進餐。進餐畢，先放下他左邊的筷子，然後再放下右邊的筷子。當五個哲學家同時去取他左邊的筷子，每人拿到一隻筷子且不釋放，即五個哲學家只得無限等待下去，引起死鎖。

死鎖問題

(1)破壞請求保持條件
利用原子思想完成。即只有拿起兩支筷子的哲學家才可以進餐，否則，一支筷子也不拿。
解法一：利用AND機制實現第1位哲學家的活動描述為：
philosopher (int I)
{
while(true)
{
思考;
swait(chopstick[(I+1)]%5，chopstick[I])；
進餐;
Ssignal(chopstick[I]，chopstick[(I+i)%5]);
}
}
解法二：利用記錄型信號量機制實現在初始化中增加一個信號量定義：semaphore mutex=1：
第1位哲學家的活動描述：
philosopher (int I)
{
while(true)
{
思考;
wait(mutex)；
wait(stiCk[I]);
wait(Stick[(I+1)%5]);
Signal(mutex)；
進餐；
signal(stick[I]);
Signal(Stick[(I+1)%5])；
}
}
該方法將拿兩隻筷子的過程作為臨界資源，一次只允許一個哲學家進入。
(2)破壞環路等待條件
在上述死鎖問題中，哲學家對筷子資源的申請構成了有向環路，如圖2所示。
哲學家進餐問題
圖2環路等待
解法一：奇數號哲學家先拿他左邊的筷子，偶數號哲學家先拿他右邊的筷子。這樣破壞了同方向環路，一個哲學家拿到一隻筷子後，就阻止了他鄰座的一個哲學家吃飯。按此規定，將是1、2號哲學家競爭I號筷子；3、4號哲學家競爭4號筷子。兩種算法描述如下：
1)第1個哲學家的活動：
philosopher (int I)
{
while(true)
{
思考;
If I%2==1 then
wait(Stick[I]);
wait(stick[(I+1)%5]);
進餐;
Signal(stick[I J)；
signal(stick[(I+1)%5])；
e1Se
wait(stick[(I+1)%5])；
wait(stick[I]);
進餐；
signal(stick[(I+1)%5])；
Signal(stick[I]);
}
}
(2)第1個哲學家的活動：
philosopher(int I)
{
while(true)
{
思考;
wait(chopstick[I+(I%2)]；
wait(chopstick[(I+(I+1)%2)%5])
進餐;
signal(chopstick[I+(I%2)])；
Signal(chopstick[(I+(I+1)%2)%5])；
}
}
解法二：至多允許四位哲學家進餐，將最後一個哲學家停止申請資源，斷開環路。最終能保證有一位哲學家能進餐，用完釋放兩隻筷子，從而使更多的哲學家能夠進餐。增加一個信號量定義semaphore count=4：算法描述第1個哲學家的活動：
philosopher (int I)
{
while(true)
思考；
wait(count)；
wait(chopstiok[I])；
wait(chopstick[I+1]mod 5)；
進餐；
signal(chopstick[I])；
signal(chopstick[I+1]mod 5)
signal(count);
}
}
解法三：哲學家申請資源總是按照資源序號先大後小的順序，這樣0．3號哲學家先右後左，但是4號哲學家
先左後右，改變方向，破壞了環路。算法描述第1個哲學家的活動：
philosopher(int I)
{
while(true)
{
思考；
if I>(I+1)%5 then
wait(chopstick[I]);
wait(chopstick[I+1]mod 5)；
else
wait(chopstick[T+1]mod 5)；
wait(chopstick[T]);/*哲學家總是先取最
大序號的筷子*/
進餐;
signal(chopstick[I])；
signal(chopstick[I+1]mod5)；
}
}

管程機制

在用信號量機制解決同步問題時，往往比較繁瑣，採用面向對象的思想，將資源及資源的共享操作封裝起來，用管程來管理，實現哲學家進餐問題，使用起來更加方便。
算法實現描述如下：
1）建立管程
monitor PC
{
semaphore chopstick[5]=11，1，1，1，1)；
X：condition；/*定義條件變數*/
void Get：(int T) /*定義取筷子過程*/
{
Tf chopstick[I]=1 and chopstick[(i+1)%5]=1 then
get the chopstick[I]and chopstick[(i+1)%5]；
else X．wait；/*左右筷子沒有，則等待*/
)
void Put(int i) /*定義放下筷子過程*/
{
put：the chopstick[I]and chopstick
(i+1)%5]；
Tf X．quene then X．signal;/*喚醒等待筷子的哲學家*/
)
}
2）使用管程
第1個哲學家的活動：
void philosopher(int I)
{
while(true)
{
思考；
get：(I);
進餐；
put(I);
}
}

相關詞條

熱門詞條

聯絡我們