竇金鳳　曹家寶　郭忠文　劉穎健

摘要:本文根據(jù)多年的教學經(jīng)驗,利用信號量機制、管程機制等思想對哲學家進餐問題進行研究,提出了解決思路,并在教學實驗過程中進行了驗證。希望與其他相關(guān)領(lǐng)域的學習者共享,方便“操作系統(tǒng)”的教學、學習和應用。

關(guān)鍵詞:進程同步;哲學家進餐問題;信號量;死鎖;管程

中圖分類號:G642 文獻標識碼:B

1引言

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

2問題描述

有五個哲學家,共用一張圓桌,分別坐在周圍的五把椅子上,圓桌上有五個碗和五只筷子,每人兩邊各放一只筷子,如圖1所示。哲學家們是交替思考和進餐,饑餓時便試圖取其左右最靠近他的筷子。

哲學家進餐問題可看作是并發(fā)進程并發(fā)執(zhí)行時,處理共享資源的一個有代表性的問題。分析其約束條件:

(1) 只有拿到兩只筷子時,哲學家才能吃飯。

(2) 如果筷子已被別人拿走,則必須等別人吃完之后才能拿到筷子。

(3) 任一哲學家在自己未拿到兩只筷子吃飯前,不會放下手中拿到的筷子。

3用信號量機制解決問題

3.1記錄型信號量

筷子是臨界資源,一段時間只允許一位哲學家使用。為了表示互斥,用一個信號量表示一只筷子,五個信號量構(gòu)成信號量數(shù)組。由于計算機專業(yè)本科生先行課開設C語言,所以本文中算法用類C語言描述偽碼算法。算法描述如下:

Semaphore chopstick[5]={1,1,1,1,1};/*分別表示5支筷子*/

Main()

{

cobegin

philosopher(0);

philosopher(1);

philosopher(2);

philosopher(3);

philosopher(4);

coend

}

第I位哲學家的活動描述為:

philosopher (int I)

{

while (true)

{

思考;

wait (chopstick [ I ]);

wait (chopstick [(I+1)%5]);

進餐;

signal (chopstick [I]);

signal (chopstick [(I+1)%5]);

}

}

當哲學家饑餓時,總是先去拿他左邊的筷子,執(zhí)行wait (chopstick [I]),成功后,再去拿他右邊的筷子,執(zhí)行wait (chopstick [I+1] %5);成功后便可進餐。進餐畢,先放下他左邊的筷子,然后再放下右邊的筷子。

當五個哲學家同時去取他左邊的筷子,每人拿到一只筷子且不釋放,即五個哲學家只得無限等待下去,引起死鎖。

3.2死鎖問題的解決

預防死鎖即是破壞死鎖的必要條件之一。通常用下列方法解決死鎖問題。

3.2.1破壞請求保持條件

利用原子思想完成。即只有拿起兩支筷子的哲學家才可以進餐,否則,一支筷子也不拿。

解法一:利用AND機制實現(xiàn)第I位哲學家的活動描述為:

philosopher (int I)

{

while (true)

{

思考;

swait(chopstick[(I+1)] % 5,chopstick[I]);

進餐;

ssignal(chopstick[I], chopstick[(I+1)% 5]);

}

}

解法二:利用記錄型信號量機制實現(xiàn)在初始化中增加一個信號量定義:semaphore mutex = 1;

第I位哲學家的活動描述:

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]);

}

}

該方法將拿兩只筷子的過程作為臨界資源,一次只允許一個哲學家進入。

3.2.2破壞環(huán)路等待條件

在上述死鎖問題中,哲學家對筷子資源的申請構(gòu)成了有向環(huán)路,如圖2所示。

解法一:奇數(shù)號哲學家先拿他左邊的筷子,偶數(shù)號哲學家先拿他右邊的筷子。這樣破壞了同方向環(huán)路,一個哲學家拿到一只筷子后,就阻止了他鄰座的一個哲學家吃飯。按此規(guī)定,將是1、2號哲學家競爭1號筷子;3、4號哲學家競爭4號筷子。兩種算法描述如下:

(1) 第I個哲學家的活動:

philosopher (int I)

{

while (true)

{

思考;

IfI % 2 == 1 then

wait (stick [ I ]);

wait (stick [(I+1)%5]);

進餐;

signal (stick [I]);

signal (stick [(I+1)%5]);

else

wait (stick [(I+1)%5]);

wait (stick [ I ]);

進餐;

signal (stick [(I+1)%5]);

signal (stick [I]);

}

}

(2) 第I個哲學家的活動:

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] );

}

}

解法二:至多允許四位哲學家進餐,將最后一個哲學家停止申請資源,斷開環(huán)路。最終能保證有一位哲學家能進餐,用完釋放兩只筷子,從而使更多的哲學家能夠進餐。增加一個信號量定義semaphorecount = 4;算法描述第I個哲學家的活動:

philosopher (int I)

{

while (true)

{

思考;

wait (count);

wait(chopstick[I ]);

wait(chopstick[I+1]mod 5);

進餐;

signal(chopstick[I]);

signal(chopstick[I+1]mod 5)

signal(count)

}

}

解法三:哲學家申請資源總是按照資源序號先大后小的順序,這樣0-3號哲學家先右后左,但是4號哲學家先左后右,改變方向,破壞了環(huán)路。算法描述第I個哲學家的活動:

philosopher (int I)

{

while (true)

{

思考;

if I >(I+1) % 5 then

wait (chopstick [I ]);

wait (chopstick [I+1]mod 5);

else

wait (chopstick [I+1]mod 5);

wait (chopstick [I ]);/*哲學家總是先取最 大序號的筷子*/

進餐;

signal (chopstick [I ]);

signal (chopstick [I+1]mod5);

}

}

3.2.3破壞非剝奪條件

打破約束條件(3),設立優(yōu)先權(quán)。比如,根據(jù)哲學家等待筷子的時間設定,時間越大優(yōu)先權(quán)越高,優(yōu)先權(quán)高的可以搶奪優(yōu)先權(quán)低的筷子。

4用管程機制解決哲學家進餐問題

在用信號量機制解決同步問題時,往往比較繁瑣,采用面向?qū)ο蟮乃枷?將資源及資源的共享操作封裝起來,用管程來管理,實現(xiàn)哲學家進餐問題,使用起來更加方便。

算法實現(xiàn)描述如下:

4.1建立管程

monitor PC/*建立管程*/

{

semaphore chopstick [5] = {1,1,1,1,1};

X: condition; /*定義條件變量*/

void Get (int I) /*定義取筷子過程*/

{

If 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];

If X.quene then X.signal;/*喚醒等待筷子 的哲學家*/

}

}

4.2使用管程

第I個哲學家的活動:

void philosopher(int I)

{

while(true)

{

思考;

get (I);

進餐;

put (I);

}

}

5結(jié)束語

哲學家進餐問題是操作系統(tǒng)中一個常見且復雜的同步問題,它可為多個競爭進程或者線程互斥地訪問有限資源這一類問題的解決提供思路。本文根據(jù)多年的教學所得,利用不同的機制探討并提出了這一問題的解決思路。然后提出了解決死鎖問題的相關(guān)思路,將其應用到教學實驗中。提出的解決策略可有效地實現(xiàn),并且避免饑餓和死鎖現(xiàn)象的產(chǎn)生。希望與其他相關(guān)領(lǐng)域的學習者共享,方便操作系統(tǒng)的教學、學習和應用。

參考文獻:

[1] Andrew S. Tanenbaum, Modern Operating System[M]. 2nd ed. Englewood Cliffs, New Jersey:Prentice Hall, 2001.

[2] Abraham S. 操作系統(tǒng)概念(影印版)[M].6版. 北京: 高等教育出版社,2002.

[3] 湯子瀛,哲鳳屏,湯小丹.計算機操作系統(tǒng)(修訂版)[M].西安:西安電子科技大學出版社,2002.

[4] 周蘇,金海溶,李潔. 操作系統(tǒng)原理實驗[M]. 北京:科學出版社,2003.