利用管程概念求解哲學家進餐問題

詹勁松

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

0 引言

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

1 哲學家進餐問題

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

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

2 管程

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

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

3 Java 高級別并發對象

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

4 算法描述

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

其Java 實現代碼:

以Monitor1 類實現管程概念，內含pickup、putdown 兩個方法，供哲學家線程對象調用。這兩個方法是互斥的，確保一次只能有一個哲學家線程在管程內活動。運用管程概念，哲學家線程運行過程編程十分簡單。只要調用管程相應的方法，就能夠保證線程之間的互斥和同步。

我們在四核i5 CPU，4G 內存的計算機，Windows7 平臺上運行該程序4 個小時沒有發生死鎖和也沒有發生餓死。5 個哲學家線程進入吃飯狀態的幾率差不多。

5 結語

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

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

［2］ 費翔林，駱斌.操作系統教程［M］.5 版。北京:高等教育出版社，2014.

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

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