利用管程概念求解哲學(xué)家進(jìn)餐問題

詹勁松

(福建師范大學(xué)福清分校 電子與信息工程學(xué)院，福建 福清350300)

0 引言

哲學(xué)家進(jìn)餐問題是操作系統(tǒng)中經(jīng)典的同步問題，它需要在多個(gè)進(jìn)程或線程之間分配多個(gè)資源，使進(jìn)程(線程)能向前推進(jìn)。我們的目的是要在這種情況下采用某種策略，預(yù)防死鎖的發(fā)生。管程是一種高級的同步構(gòu)造，利用Java 高級別并發(fā)對象可以實(shí)現(xiàn)管程概念。通過管程可以方便地實(shí)現(xiàn)這種死鎖預(yù)防策略。

1 哲學(xué)家進(jìn)餐問題

5 位哲學(xué)家圍坐在一張圓桌旁邊，圓桌中央放置一碗米飯，每兩人之間放置一支筷子。每位哲學(xué)家思考、饑餓，然后吃飯。為了吃飯，他必須拿起與他相鄰的左、右兩支筷子。他不能從別的哲學(xué)家手里搶奪筷子。吃完飯后，他會(huì)放下筷子，并又開始思考。

如果對每個(gè)哲學(xué)家的吃飯過程不加限制，很快就進(jìn)入這樣一個(gè)狀態(tài)，每人搶得一支筷子，結(jié)果誰也吃不了飯，也就是進(jìn)入了死鎖的狀態(tài)。產(chǎn)生死鎖有4 個(gè)必要條件，互斥、占有并等待、非搶占和循環(huán)等待［1］。如果能夠使一組進(jìn)程(線程)在推進(jìn)的整個(gè)過程中，這4 個(gè)條件之一或更多保持不成立，那么這組進(jìn)程(線程)就不會(huì)陷入死鎖狀態(tài)。哲學(xué)家問題的死鎖預(yù)防有多種方法。其中一種是:每位哲學(xué)家要能取到手邊的兩支筷子才開始吃飯，否則他一支筷子也不取。這種解法的實(shí)質(zhì)是預(yù)先分配需要的全部資源，從而破壞產(chǎn)生死鎖的占有并等待這個(gè)必要條件。本文就是采用這種解法。

2 管程

為了解決同步問題程序中使用信號量容易出錯(cuò)的問題，70 年代初，P.B.Hansen 和C.A.R.Hoare 等人提出了管程的概念。其基本思想是:把分散于各進(jìn)程(線程)中的臨界區(qū)集中起來統(tǒng)一管理，并把共享資源用數(shù)據(jù)結(jié)構(gòu)來抽象表示，建立一個(gè)管程結(jié)構(gòu)來管理相應(yīng)的訪問［2］。管程結(jié)構(gòu)確保一次只能有一個(gè)進(jìn)程(線程)在管程內(nèi)活動(dòng)。

管程結(jié)構(gòu)通過防止對一個(gè)資源的并發(fā)訪問來達(dá)到了實(shí)現(xiàn)臨界區(qū)的目的，從而提供了實(shí)現(xiàn)互斥的手段，但是管程并沒有提供進(jìn)程(線程)和其他進(jìn)程(線程)之間同步的途徑。當(dāng)一個(gè)進(jìn)程(線程)進(jìn)入了管程并調(diào)用了管程的一個(gè)過程。如果該過程在執(zhí)行時(shí)發(fā)現(xiàn)資源不能得到滿足，當(dāng)然應(yīng)該讓此進(jìn)程(線程)阻塞，同時(shí)需要開放管程，讓之前被阻擋在管程外邊的進(jìn)程(線程)之一進(jìn)入。為此需要定義一個(gè)另外的同步機(jī)制，這可由條件(Condition)結(jié)構(gòu)來提供。條件變量只有操作wait()和signal()。前者用于阻塞調(diào)用的進(jìn)程(線程)。后者用于啟動(dòng)一個(gè)被阻塞的進(jìn)程(線程)。

3 Java 高級別并發(fā)對象

在Java SE 5.0 之前，用Java 實(shí)現(xiàn)管程有些不精確。因?yàn)榫€程之間的同步只能使用Object 類的wait()，和notify()或notifyAll()來實(shí)現(xiàn)。只能向任何一個(gè)被阻塞線程或者全部被阻塞線程發(fā)送啟動(dòng)消息，不能準(zhǔn)確定位向某一個(gè)被阻塞線程發(fā)送消息。Java SE 5.0 引入了ReentrantLock 類和Condition 接口［3］，改變了這個(gè)狀況。通過調(diào)用Condtiton 對象的signal 方法，某個(gè)哲學(xué)家吃完飯，放下筷子就可以準(zhǔn)確地向其相鄰的兩位哲學(xué)家線程發(fā)出啟動(dòng)信號。

4 算法描述

借助信號量，算法描述如下:

其Java 實(shí)現(xiàn)代碼:

以Monitor1 類實(shí)現(xiàn)管程概念，內(nèi)含pickup、putdown 兩個(gè)方法，供哲學(xué)家線程對象調(diào)用。這兩個(gè)方法是互斥的，確保一次只能有一個(gè)哲學(xué)家線程在管程內(nèi)活動(dòng)。運(yùn)用管程概念，哲學(xué)家線程運(yùn)行過程編程十分簡單。只要調(diào)用管程相應(yīng)的方法，就能夠保證線程之間的互斥和同步。

我們在四核i5 CPU，4G 內(nèi)存的計(jì)算機(jī)，Windows7 平臺上運(yùn)行該程序4 個(gè)小時(shí)沒有發(fā)生死鎖和也沒有發(fā)生餓死。5 個(gè)哲學(xué)家線程進(jìn)入吃飯狀態(tài)的幾率差不多。

5 結(jié)語

本文利用Java 高級別對象和管程概念給出了哲學(xué)家進(jìn)餐問題死鎖預(yù)防的一種解法。與文獻(xiàn)4 中的方法相比［4］，借助管程概念求解哲學(xué)家進(jìn)餐問題，把所有的互斥、同步相關(guān)代碼集中在于管程類內(nèi)，在更高的層次上解決問題，使代碼不容易出錯(cuò)，可讀性更好，并且程序模塊化的程度更高。

［1］ Abraham Silbertschatz，Peter Baer Galvin，Geg Gagne.操作系統(tǒng)概念［M］.鄭扣根，譯.7 版.北京:高等教育出版社，2010.

［2］ 費(fèi)翔林，駱斌.操作系統(tǒng)教程［M］.5 版。北京:高等教育出版社，2014.

［3］ CayS.Horstmann，Gary Cornell.Java 核心技術(shù)卷1［M］.周立新，陳波，葉乃文，等譯.北京:機(jī)械工業(yè)出版社，2013.

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