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

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

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

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

1引言

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

2問題描述

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

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

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

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

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

3用信號(hào)量機(jī)制解決問題

3.1記錄型信號(hào)量

筷子是臨界資源,一段時(shí)間只允許一位哲學(xué)家使用。為了表示互斥,用一個(gè)信號(hào)量表示一只筷子,五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。由于計(jì)算機(jī)專業(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é)家的活動(dòng)描述為:

philosopher (int I)

{

while (true)

{

思考;

wait (chopstick [ I ]);

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

進(jìn)餐;

signal (chopstick [I]);

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

}

}

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

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

3.2死鎖問題的解決

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

3.2.1破壞請求保持條件

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

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

philosopher (int I)

{

while (true)

{

思考;

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

進(jìn)餐;

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

}

}

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

第I位哲學(xué)家的活動(dòng)描述:

philosopher (int I)

{

while (true)

{

思考;

wait(mutex);

wait (stick [ I ]);

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

signal (mutex);

進(jìn)餐;

signal (stick [I]);

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

}

}

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

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

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

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

(1) 第I個(gè)哲學(xué)家的活動(dòng):

philosopher (int I)

{

while (true)

{

思考;

IfI % 2 == 1 then

wait (stick [ I ]);

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

進(jìn)餐;

signal (stick [I]);

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

else

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

wait (stick [ I ]);

進(jìn)餐;

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

signal (stick [I]);

}

}

(2) 第I個(gè)哲學(xué)家的活動(dòng):

philosopher (int I)

{

while (true)

{

思考;

wait (chopstick[I +(I % 2)];

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

進(jìn)餐;

signal (chopstick[I +(I % 2)]);

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

}

}

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

philosopher (int I)

{

while (true)

{

思考;

wait (count);

wait(chopstick[I ]);

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

進(jìn)餐;

signal(chopstick[I]);

signal(chopstick[I+1]mod 5)

signal(count)

}

}

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

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é)家總是先取最 大序號(hào)的筷子*/

進(jìn)餐;

signal (chopstick [I ]);

signal (chopstick [I+1]mod5);

}

}

3.2.3破壞非剝奪條件

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

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

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

算法實(shí)現(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個(gè)哲學(xué)家的活動(dòng):

void philosopher(int I)

{

while(true)

{

思考;

get (I);

進(jìn)餐;

put (I);

}

}

5結(jié)束語

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

參考文獻(xiàn):

[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] 湯子瀛,哲鳳屏,湯小丹.計(jì)算機(jī)操作系統(tǒng)(修訂版)[M].西安:西安電子科技大學(xué)出版社,2002.

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