計算機操作系統(tǒng)哲學(xué)家進餐問題的教學(xué)探討

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

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

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

中圖分類號:G642 文獻標(biāo)識碼:B

1引言

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

2問題描述

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

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

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

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

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

3用信號量機制解決問題

3.1記錄型信號量

筷子是臨界資源,一段時間只允許一位哲學(xué)家使用。為了表示互斥,用一個信號量表示一只筷子,五個信號量構(gòu)成信號量數(shù)組。由于計算機專業(yè)本科生先行課開設(shè)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位哲學(xué)家的活動描述為:

philosopher (int I)

{

while (true)

{

思考;

wait (chopstick [ I ]);

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

進餐;

signal (chopstick [I]);

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

}

}

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

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

3.2死鎖問題的解決

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

3.2.1破壞請求保持條件

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

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

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位哲學(xué)家的活動描述:

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

}

}

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

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

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

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

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

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個哲學(xué)家的活動:

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

}

}

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

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)

}

}

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

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 ]);/*哲學(xué)家總是先取最 大序號的筷子*/

進餐;

signal (chopstick [I ]);

signal (chopstick [I+1]mod5);

}

}

3.2.3破壞非剝奪條件

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

4用管程機制解決哲學(xué)家進餐問題

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

算法實現(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;/*喚醒等待筷子 的哲學(xué)家*/

}

}

4.2使用管程

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

void philosopher(int I)

{

while(true)

{

思考;

get (I);

進餐;

put (I);

}

}

5結(jié)束語

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

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