哲學(xué)家就餐問(wèn)題的實(shí)驗(yàn)課程思路拓展

楊 珊

(電子科技大學(xué) 信息與軟件學(xué)院，四川 成都 610000)

在1965年，文獻(xiàn)[1]中Dijkstra將一個(gè)同步問(wèn)題稱為哲學(xué)家就餐的同步問(wèn)題。

在軟件工程專業(yè)的操作系統(tǒng)實(shí)驗(yàn)課程中，哲學(xué)家就餐問(wèn)題是學(xué)生掌握信號(hào)量使用的第一步嘗試，同樣也是一次重要的實(shí)驗(yàn)項(xiàng)目，目的是加強(qiáng)學(xué)生在互斥量信號(hào)量等同步及互斥機(jī)制的實(shí)踐訓(xùn)練。

操作系統(tǒng)這門課程具有概念多、算法多、內(nèi)容抽象且廣泛等特點(diǎn)，實(shí)驗(yàn)效果反饋顯示學(xué)生自主完成該實(shí)驗(yàn)項(xiàng)目具有一定難度。因此本文將主要通過(guò)同步問(wèn)題內(nèi)容分解、算法實(shí)現(xiàn)思路、死鎖解決方案3大內(nèi)容來(lái)提高學(xué)生對(duì)實(shí)驗(yàn)學(xué)習(xí)的達(dá)成度及動(dòng)手能力。首先本文將通過(guò)對(duì)哲學(xué)家就餐問(wèn)題的詳細(xì)分解加深加強(qiáng)對(duì)該同步問(wèn)題的理解；進(jìn)而實(shí)現(xiàn)一種并發(fā)量較大的算法思路，目的是為了拓寬學(xué)生的知識(shí)面，使其從多種角度學(xué)習(xí)理解操作系統(tǒng)的同步問(wèn)題，延展解決思路；最后討論死鎖的產(chǎn)生原因及預(yù)防的一種方案，鍛煉學(xué)生對(duì)于解決死鎖問(wèn)題的思考能力。參與本門實(shí)驗(yàn)課程的學(xué)生亦可將本文作為實(shí)驗(yàn)指導(dǎo)內(nèi)容。

1 經(jīng)典操作系統(tǒng)同步問(wèn)題

哲學(xué)家就餐問(wèn)題描述[2－3]為:一共有5個(gè)哲學(xué)家和5把叉子，每人面前一盤通心粉 (需要兩把叉子才能拿起)，大家圍繞桌子，進(jìn)行思考與進(jìn)食的活動(dòng)。

哲學(xué)家的活動(dòng)方式為:要么放下左右手刀叉進(jìn)行思考，要么拿起刀叉開始吃飯(刀叉拿起時(shí)，必須拿兩把，而且只能左右手依次拿，先左手拿左邊，后右手拿右邊，或者先右手拿右邊，后左邊拿左邊)。即只有思考和進(jìn)餐兩種交替狀態(tài)。

哲學(xué)家面臨的問(wèn)題為:哲學(xué)家需要統(tǒng)一思考邏輯，同時(shí)能夠保證以下兩個(gè)條件:

1)他們至少有人且盡可能兩個(gè)人能同時(shí)拿到兩把叉子開始吃飯；

2)不會(huì)發(fā)生 “死鎖”和 “饑餓”的狀態(tài)。

哲學(xué)家進(jìn)餐和思考的時(shí)機(jī)是隨機(jī)的，不能指定哲學(xué)家們進(jìn)餐順序。同時(shí)要保證不會(huì)出現(xiàn)死鎖和饑餓[3]這兩種讓 “進(jìn)餐”無(wú)法繼續(xù)的狀態(tài)。

2 哲學(xué)家就餐問(wèn)題解決思路

我們將哲學(xué)家問(wèn)題抽象為進(jìn)程或線程對(duì)資源訪問(wèn)的互斥及同步問(wèn)題，此處我們使用線程函數(shù)來(lái)描述一位哲學(xué)家的行為。

關(guān)系分析:5名哲學(xué)家 (線程)對(duì)5只叉子的訪問(wèn)特征為占有之后，其他鄰居不可以訪問(wèn)，因此是互斥關(guān)系。由于哲學(xué)家線程行為是一致的，所以如何定義哲學(xué)家對(duì)資源的獲取是每個(gè)算法的核心思想。通常哲學(xué)家線程的進(jìn)餐及思考流程如圖1所示。

圖1 哲學(xué)家就餐線程流程圖

3 K.Mani Chandy/J.Misra算法

本文討論的是由K.Mani Chandy和J.Misra在1984年提出的一種哲學(xué)家就餐算法的實(shí)現(xiàn)，主要原理旨在增加哲學(xué)家獲取叉子的時(shí)候，競(jìng)爭(zhēng)者之間的 “交流”，使得線程沒(méi)有盲目地去搶奪資源。

文獻(xiàn)[4－5]中解法思路為原解法，允許哲學(xué)家數(shù)量為P1，P2，…，PN，此處仍舊討論5位哲學(xué)家的情況。

1)每一對(duì)競(jìng)爭(zhēng)同一資源的哲學(xué)家，新拿一個(gè)叉子，分給編號(hào)較低的哲學(xué)家。剛開始的時(shí)候，把每只叉子(F)依次分給編號(hào)較小的哲學(xué)家 (A，B，C，D，E)，即有 A－F1，B－F2，C－F3，DF4，E－F5，并把筷子都定義為“臟的”。

2)當(dāng)某位哲學(xué)家要使用筷子的時(shí)候，他缺哪只叉子，就向擁有那只叉子的哲學(xué)家發(fā)送一個(gè)請(qǐng)求。

3)當(dāng)擁有叉子的哲學(xué)家收到請(qǐng)求時(shí)，如果叉子是臟的，就把叉子擦干凈并交出去；否則就繼續(xù)留著。

4)當(dāng)哲學(xué)家擁有兩只干凈的叉子時(shí)，就可以就餐了，吃完以后叉子就變成臟的了。如果有哲學(xué)家之前請(qǐng)求過(guò)其中一只叉子，則把叉子擦干凈并交出去。

首先算法定義叉子是屬于某位哲學(xué)家的，并且永遠(yuǎn)都在某位哲學(xué)家手上，只有該哲學(xué)家同意，筷子才可以交出去。這種哲學(xué)家之間 “交流”的算法思想和傳統(tǒng)解決方法有極大的差別。

其中，哲學(xué)家手上的叉子狀態(tài)有兩種，一種是 “干凈的”，一種是 “臟的”。在整個(gè)哲學(xué)家吃飯和休息 (思考)的過(guò)程中，叉子只有在某個(gè)哲學(xué)家準(zhǔn)備開始到吃飯行為結(jié)束期間是干凈的，如圖2所示。

圖2 筷子狀態(tài)變化示意圖

圖2的例子詳細(xì)地解釋了本算法的重要規(guī)則。本例中有5位哲學(xué)家參與進(jìn)餐過(guò)程，叉子是依次分給編號(hào)較小的哲學(xué)家，即有A－F1，B－F2，C－F3，D－F4，E－F5，根據(jù)算法規(guī)則，叉子的狀態(tài)在一開始的時(shí)候都是 “臟的”。如圖3所示，給出了哲學(xué)家就餐開始到某個(gè)時(shí)間點(diǎn)的過(guò)程中，A、B、C 3位哲學(xué)家對(duì)叉子進(jìn)行競(jìng)爭(zhēng)分配、交出叉子或進(jìn)餐的過(guò)程。

最先需要進(jìn)餐的B將手上的叉子F2擦干凈，同時(shí)向A請(qǐng)求叉子F1，A的叉子F1是 “臟的”，所以擦干凈交給B。此時(shí)C需要進(jìn)餐，向B請(qǐng)求叉子F2，但是叉子F2此時(shí)是 “干凈的”，所以B留在手上。最后B進(jìn)餐結(jié)束，叉子F1與叉子F2都變?yōu)?“臟的”，此時(shí)C的請(qǐng)求得到響應(yīng)，拿到叉子F2。

圖3 哲學(xué)家A、B、C競(jìng)爭(zhēng)進(jìn)餐過(guò)程

這種算法可以解決大規(guī)模的并發(fā)問(wèn)題 (哲學(xué)家數(shù)量可以為Pn)，也能避免餓死問(wèn)題。但是，不能完全避免死鎖現(xiàn)象 (當(dāng)每個(gè)哲學(xué)家拿到一只干凈叉子的時(shí)候，則陷入了死鎖)[6]。

4 算法實(shí)現(xiàn)具體描述

本文接下來(lái)將討論算法的實(shí)現(xiàn)思路，主要描述兩個(gè)重要函數(shù)的實(shí)現(xiàn)思路。

函數(shù)philo://主要的哲學(xué)家線程程序

{

while(無(wú)限){

while(左叉子不在手上或者右叉子不在手上)

{

getchopfromneighbor(左叉子)；

//對(duì)沒(méi)有的叉子進(jìn)行請(qǐng)求

getchopfromneighbor(右叉子)；

}

//進(jìn)入互斥區(qū)

pthread＿mutex＿lock(＆g＿mtx)；

確認(rèn)兩個(gè)叉子都在手上則吃飯3秒；

將兩把叉子狀態(tài)設(shè)置為DIRTY

pthread＿mutex＿unlock(＆g＿mtx)；

sleep(隨機(jī)數(shù)秒)；

}

函數(shù)Philo結(jié)束

函數(shù)getchopfromneighbor(chokid)

//判斷是否讓鄰居交出叉子

{

if Philo[chokid]＝＝請(qǐng)求者

Status[chokid]＝CLEAN；

if Philo[chokid]！ ＝請(qǐng)求者

{

pthread＿mutex＿lock(＆g＿mtx)；

if(需判斷叉子＝＝DIRTY)

{ Philo[chokid] ＝請(qǐng)求者

Status[chokid] ＝CLEAN；}

pthread＿mutex＿unlock(＆g＿mtx)；

}

函數(shù)Philo是主要的哲學(xué)家線程函數(shù)，包括了哲學(xué)家的所有行為流程，主要有吃飯行為和思考行為。吃飯行為在獲取到叉子之后進(jìn)入互斥區(qū)開始進(jìn)餐，使用互斥主要是為了保證吃飯行為的原子性；思考行為主要是sleep函數(shù)，線程阻塞數(shù)秒。

5 死鎖原因及解決思路

在前文算法介紹處提到，根據(jù)此思路實(shí)現(xiàn)的算法有時(shí)會(huì)出現(xiàn)死鎖，即5位哲學(xué)家都拿到了干凈的叉子 (哲學(xué)家請(qǐng)求資源的順序的一致)[7]。

在上述流程描述中，哲學(xué)家在得到一只叉子之后，設(shè)為 “干凈的”，此時(shí)如果每位哲學(xué)家依次獲得一只干凈叉子，程序會(huì)進(jìn)入死鎖狀態(tài)。

因此，實(shí)現(xiàn)了以上思路的代碼后，在運(yùn)行多次的情況下有可能會(huì)出現(xiàn)如圖4所示的結(jié)果。

圖4中5位哲學(xué)家同時(shí)拿到右手干凈的叉子而未進(jìn)入進(jìn)餐，出現(xiàn)死鎖狀態(tài)。對(duì)于解決哲學(xué)家進(jìn)餐的死鎖問(wèn)題[8－11]，有許多人已經(jīng)提出了以下的思路:

1)保證拿起左右叉子操作的原子性；

2)奇數(shù)、偶數(shù)哲學(xué)家拿叉子順序不同；

3)采用異步操作來(lái)讓權(quán)等待；

4)通過(guò)條件變量和信號(hào)量的結(jié)合使用。

如在計(jì)算機(jī)局域網(wǎng)的實(shí)際應(yīng)用中，為了避免死鎖，人們嘗試將等待的時(shí)間設(shè)為隨機(jī)時(shí)間 (在哲學(xué)家問(wèn)題里描述為 “如果哲學(xué)家在拿不到右邊叉子時(shí)等待一段隨機(jī)時(shí)間，而不是等待相同的時(shí)間”[12])。如果兩臺(tái)計(jì)算機(jī)同時(shí)發(fā)送數(shù)據(jù)包，則每臺(tái)計(jì)算機(jī)等待隨機(jī)時(shí)間之后再進(jìn)行嘗試。

結(jié)合這幾條思路研究此處死鎖出現(xiàn)的條件，可得知是由于所有哲學(xué)家同一時(shí)間 (間隔極短)請(qǐng)求同方向的叉子而導(dǎo)致死鎖。因此在考慮請(qǐng)求叉子時(shí)，使用隨機(jī)數(shù)加入隨機(jī)請(qǐng)求左右叉子的判斷 (拿叉子順序不同)，則能以極大概率避免了死鎖的發(fā)生。

將上面的philo函數(shù)中while循環(huán)段的示意代碼做一些修改，如下:

while(左叉子不在手上或者右叉子不在手上){

初始化一個(gè)隨機(jī)數(shù)；if隨機(jī)數(shù)%2＝1

則getchopfromneighbor(左叉子)；if隨機(jī)數(shù)%2＝＝0

則getchopfromneighbor(右叉子)；}此種避免死鎖的方法和上述解決思路2中奇數(shù)、偶數(shù)哲學(xué)家拿叉子順序不同的原理一致，在實(shí)驗(yàn)過(guò)程中可以根據(jù)此思路來(lái)完成死鎖避免的具體實(shí)現(xiàn)。

以上程序提供源碼下載，供讀者研究參考，死鎖的解決方法在源碼中已經(jīng)隱藏，讀者可以嘗試多次運(yùn)行得到死鎖狀態(tài)，再嘗試解決死鎖問(wèn)題。

源碼地址如下:http://download.csdn.net/detail/forsaking/9906530。

6 結(jié)束語(yǔ)

哲學(xué)家進(jìn)餐問(wèn)題是一個(gè)經(jīng)典的操作系統(tǒng)同步問(wèn)題。作為操作系統(tǒng)實(shí)驗(yàn)課的一個(gè)小型實(shí)驗(yàn)項(xiàng)目，哲學(xué)家進(jìn)餐實(shí)驗(yàn)具有一定的難度。通過(guò)本文介紹的K.Mani Chandy/J.Misra哲學(xué)家就餐算法內(nèi)容和相關(guān)實(shí)現(xiàn)過(guò)程及對(duì)死鎖的解決方法，可以延展學(xué)生解決該同步問(wèn)題的思路，幫助學(xué)生提高分析問(wèn)題的能力。學(xué)生在采用本文算法進(jìn)行實(shí)踐后，可以幫助其提高學(xué)習(xí)效果。

1)加深對(duì)死鎖的理解，從實(shí)例中體會(huì)死鎖對(duì)程序的影響及產(chǎn)生死鎖的具體原因；體會(huì)解決死鎖思路的不同方式，解決死鎖可能只需要一行代碼。

2)在不使用信號(hào)量的情況下，使用本文的算法解決多線程之間的通信，理解信號(hào)量的解決問(wèn)題的最根本原始思路。

3)拓寬學(xué)生的思考領(lǐng)域，從其他維度分析解決項(xiàng)目問(wèn)題的能力。

此外，如何加強(qiáng)學(xué)生實(shí)驗(yàn)研究的主動(dòng)性，自主構(gòu)建多元解決方案，仍是今后需要不斷探索研究的內(nèi)容。

[1]竇金鳳，曹家寶，郭忠文，等.計(jì)算機(jī)操作系統(tǒng)哲學(xué)家進(jìn)餐問(wèn)題的教學(xué)探討[J].計(jì)算機(jī)教育，2009(14):86－88.

[2]賈玉珍，王祥雒.哲學(xué)家進(jìn)餐問(wèn)題的一種解決方案[J].電腦知識(shí)與技術(shù)，2006(14):163－164.

[3]張磊，馬軍.描述短時(shí)資源混雜占用型任務(wù)調(diào)度的數(shù)學(xué)模型與算法[C]//中國(guó)計(jì)算機(jī)學(xué)會(huì)理論計(jì)算機(jī)科學(xué)專業(yè)委員會(huì).2005年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集.北京:中國(guó)計(jì)算機(jī)學(xué)會(huì)理論計(jì)算機(jī)科學(xué)專業(yè)委員會(huì)，2005.

[4]左金平.計(jì)算機(jī)操作系統(tǒng)中哲學(xué)家進(jìn)餐問(wèn)題探究[J].晉中學(xué)院學(xué)報(bào)，2004，21(4):343－344.

[5]JENNIFER L W，NANCY A.Lynch a modular drinking philosophers algorithm[J]. Distributed Computing，1993，6(4):233－244.

[6]CHANDY K M，MISRA J.Parallel program design:a foundation[J].Addison－Wesley Longman，1988，16(11):1313－1334.

[7]王繼偉，王安，汪樹勛.一個(gè)經(jīng)典進(jìn)程同步問(wèn)題的幾種解法[J].甘肅科技，2007，23(1):60－62.

[8]孫時(shí)光，張晉.解決哲學(xué)家進(jìn)餐問(wèn)題陷入死鎖狀態(tài)的系統(tǒng)改造方案分析[J].遼寧大學(xué)學(xué)報(bào) (自然科學(xué)版)，2013，40(3):210－212.

[9]白戈力，付學(xué)良.哲學(xué)家進(jìn)餐問(wèn)題產(chǎn)生死鎖的1種解決方案[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào) (自然科學(xué)版)，2010，31(1):245－247.

[10]詹勁松.利用Java高級(jí)別并發(fā)對(duì)象求解哲學(xué)家進(jìn)餐問(wèn)題[J].佳木斯大學(xué)學(xué)報(bào) (自然科學(xué)版)，2013，31(6):905－907.

[11]詹勁松.哲學(xué)家進(jìn)餐問(wèn)題一種解法的改進(jìn)[J].佳木斯大學(xué)學(xué)報(bào) (自然科學(xué)版)，2008，26(4):553－555.

[12]曹建立，王祥雒.用附加規(guī)則解決哲學(xué)家進(jìn)餐問(wèn)題[J].福建電腦，2006(7):88－89.