楊 珊

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

在1965年，文獻[1]中Dijkstra將一個同步問題稱為哲學家就餐的同步問題。

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

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

1 經典操作系統(tǒng)同步問題

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

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

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

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

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

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

2 哲學家就餐問題解決思路

我們將哲學家問題抽象為進程或線程對資源訪問的互斥及同步問題，此處我們使用線程函數來描述一位哲學家的行為。

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

圖1 哲學家就餐線程流程圖

3 K.Mani Chandy/J.Misra算法

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

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

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

2)當某位哲學家要使用筷子的時候，他缺哪只叉子，就向擁有那只叉子的哲學家發(fā)送一個請求。

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

4)當哲學家擁有兩只干凈的叉子時，就可以就餐了，吃完以后叉子就變成臟的了。如果有哲學家之前請求過其中一只叉子，則把叉子擦干凈并交出去。

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

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

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

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

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

圖3 哲學家A、B、C競爭進餐過程

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

4 算法實現具體描述

本文接下來將討論算法的實現思路，主要描述兩個重要函數的實現思路。

函數philo://主要的哲學家線程程序

{

while(無限){

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

{

getchopfromneighbor(左叉子)；

//對沒有的叉子進行請求

getchopfromneighbor(右叉子)；

}

//進入互斥區(qū)

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

確認兩個叉子都在手上則吃飯3秒；

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

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

sleep(隨機數秒)；

}

函數Philo結束

函數getchopfromneighbor(chokid)

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

{

if Philo[chokid]＝＝請求者

Status[chokid]＝CLEAN；

if Philo[chokid]！ ＝請求者

{

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

if(需判斷叉子＝＝DIRTY)

{ Philo[chokid] ＝請求者

Status[chokid] ＝CLEAN；}

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

}

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

5 死鎖原因及解決思路

在前文算法介紹處提到，根據此思路實現的算法有時會出現死鎖，即5位哲學家都拿到了干凈的叉子 (哲學家請求資源的順序的一致)[7]。

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

因此，實現了以上思路的代碼后，在運行多次的情況下有可能會出現如圖4所示的結果。

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

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

2)奇數、偶數哲學家拿叉子順序不同；

3)采用異步操作來讓權等待；

4)通過條件變量和信號量的結合使用。

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

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

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

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

初始化一個隨機數；if隨機數%2＝1

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

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

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

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

6 結束語

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

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

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

3)拓寬學生的思考領域，從其他維度分析解決項目問題的能力。

此外，如何加強學生實驗研究的主動性，自主構建多元解決方案，仍是今后需要不斷探索研究的內容。

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

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

[3]張磊，馬軍.描述短時資源混雜占用型任務調度的數學模型與算法[C]//中國計算機學會理論計算機科學專業(yè)委員會.2005年全國理論計算機科學學術年會論文集.北京:中國計算機學會理論計算機科學專業(yè)委員會，2005.

[4]左金平.計算機操作系統(tǒng)中哲學家進餐問題探究[J].晉中學院學報，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]王繼偉，王安，汪樹勛.一個經典進程同步問題的幾種解法[J].甘肅科技，2007，23(1):60－62.

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

[9]白戈力，付學良.哲學家進餐問題產生死鎖的1種解決方案[J].內蒙古農業(yè)大學學報 (自然科學版)，2010，31(1):245－247.

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

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

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