哲學家就餐問題
哲學家就餐問題（英語：Dining philosophers problem）是在計算機科學中的一個經典問題，用來演示在並發計算中多線程同步時產生的問題。
1971年，荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出了一個同步問題，即假設有五台計算機都試圖訪問五份共享的磁帶驅動器。稍後，這個問題被東尼·霍爾重新表述為哲學家就餐問題。這個問題可以用來解釋死鎖和資源耗盡。[1][2][3]
問題描述
[編輯]
哲學家就餐問題可以這樣表述，假設有五位哲學家圍坐在一張圓形餐桌旁，做以下兩件事情之一：吃飯，或者思考。吃東西的時候，他們就停止思考，思考的時候也停止吃東西。餐桌上有五碗意大利麵，每位哲學家之間各有一支餐叉。因為用一支餐叉很難吃到意大利麵，所以假設哲學家必須用兩支餐叉吃東西。他們只能使用自己左右手邊的那兩支餐叉。哲學家就餐問題有時也用米飯和五根筷子而不是意大利麵和餐叉來描述，因為吃米飯必須用兩根筷子。
這個問題不考慮意大利麵有多少，也不考慮哲學家的胃有多大。假設兩者都是無限大。
問題在於如何設計一套規則，使得在哲學家們在完全不交談，也就是無法知道其他人可能在什麼時候要吃飯或者思考的情況下，可以在這兩種狀態下永遠交替下去。
進一步說明
[編輯]這個問題旨在說明避免死鎖的挑戰，死鎖是一種程序無法繼續運行的狀態。要更好理解這個問題，假設我們要求哲學家遵守以下規則：
- 哲學家在左邊的叉子可用（沒有其他人拿起）之前處於思考狀態。如果左邊的叉子可用，就拿起來。
- 哲學家等待右邊的叉子可用。如果右邊的叉子可用，就拿起來。
- 如果兩個叉子都已經拿起來，開始吃意大利麵，每次吃麵都花費同樣的時間。
- 吃完後先放下左邊的叉子。
- 然後放下右邊的叉子。
- 開始思考（進入一個循環）
這個解法是失敗的，當每個哲學家都拿起左側的叉子，等待右側的叉子可用時，就會進入死鎖狀態，每個哲學家將永遠都在等待（右邊的）另一個哲學家放下叉子。[4]
如果特定的哲學家由於時間問題而無法同時獲得兩個資源，那麼資源匱乏也可能獨立於死鎖而發生。例如，假設規定當哲學家等待另一支餐叉超過五分鐘後就放下自己手裡的那一支餐叉，並且再等五分鐘後進行下一次嘗試。這個策略消除了死結（系統總會進入到下一個狀態），但仍然有可能發生「活結」。如果五位哲學家在完全相同的時刻進入餐廳，並同時拿起左邊的餐叉，那麼這些哲學家就會等待五分鐘，同時放下手中的餐叉，再等五分鐘，又同時拿起這些餐叉。
互斥是此問題的基本概念。在實際的計算機問題中，缺乏餐叉可以類比為缺乏共享資源。一種常用的計算機技術是資源加鎖，用來保證在某個時刻，資源只能被一個程序或一段代碼訪問。當一個程序想要使用的資源已經被另一個程序鎖定，它就等待資源解鎖。當多個程序涉及到加鎖的資源時，在某些情況下就有可能發生死鎖。例如，某個程序需要訪問兩個文件，當兩個這樣的程序各鎖了一個文件，那它們都在等待對方解鎖另一個文件，而解鎖永遠不會發生。
複雜的系統（例如操作系統內核）使用成千上萬的鎖，如果要避免死鎖，資源匱乏和數據損壞等問題，就需要遵守更嚴格的方法和同步協議。
解法
[編輯]服務生解法
[編輯]一個簡單的解法是引入一個餐廳服務生，哲學家必須經過他的允許才能拿起餐叉。因為服務生知道哪支餐叉正在使用，所以他能夠作出判斷避免死鎖。
為了演示這種解法，假設哲學家依次標號為A至E。如果A和C在吃東西，則有四支餐叉在使用中。B坐在A和C之間，所以兩支餐叉都無法使用，而D和E之間有一隻空餘的餐叉。假設這時D想要吃東西。如果他拿起了第五支餐叉，就有可能發生死鎖。相反，如果他徵求服務生同意，服務生會讓他等待。這樣，我們就能保證下次當兩把餐叉空餘出來時，一定有一位哲學家可以成功的得到一對餐叉，從而避免了死鎖。
資源分級解法
[編輯]另一個簡單的解法是為資源（這裡是餐叉）分配一個偏序或者分級的關係，並約定所有資源都按照這種順序獲取，按相反順序釋放，而且保證不會有兩個無關資源同時被同一項工作所需要。在哲學家就餐問題中，資源（餐叉）按照某種規則編號為1至5，每一個工作單元（哲學家）總是先拿起左右兩邊編號較低的餐叉，再拿編號較高的。用完餐叉後，他總是先放下編號較高的餐叉，再放下編號較低的。在這種情況下，當四位哲學家同時拿起他們手邊編號較低的餐叉時，只有編號最高的餐叉留在桌上，從而第五位哲學家就不能使用任何一支餐叉了。而且，只有一位哲學家能使用最高編號的餐叉，所以他能使用兩支餐叉用餐。當他吃完後，他會先放下編號最高的餐叉，再放下編號較低的餐叉，從而讓另一位哲學家拿起後邊的這隻開始吃東西。
儘管資源分級能避免死鎖，但這種策略並不總是實用的，特別是當所需資源的列表並不是事先知道的時候。例如，假設一個工作單元拿着資源3和5，並決定需要資源2，則必須先要釋放5，之後釋放3，才能得到2，之後必須重新按順序獲取3和5。對需要訪問大量數據庫記錄的計算機程序來說，如果需要先釋放高編號的記錄才能訪問新的記錄，那麼運行效率就不會高，因此這種方法在這裡並不實用。
錢迪/米斯拉解法
[編輯]1984年，曼尼·錢迪和賈亞達夫·米斯拉提出了哲學家就餐問題的另一個解法[5] ，允許任意的用戶（編號）爭用任意數量的資源。與資源分級解法不同的是，這裡編號可以是任意的。
- 對每一對競爭一個資源的哲學家，新拿一個餐叉，給編號較低的哲學家。每隻餐叉都是「乾淨的」或者「髒的」。最初，所有的餐叉都是髒的。
- 當一位哲學家要使用資源（也就是要吃東西）時，他必須從與他競爭的鄰居那裡得到。對每隻他當前沒有的餐叉，他都傳送一個請求。
- 當擁有餐叉的哲學家收到請求時，如果餐叉是乾淨的，那麼他繼續留著，否則就擦乾淨並交出餐叉。
- 當某個哲學家吃東西後，他的餐叉就變髒了。如果另一個哲學家之前請求過其中的餐叉，那他就擦乾淨並交出餐叉。
這個解法允許很大的並行性，適用於任意大的問題。
參考資料
[編輯]- ^ 戴克斯特拉, 艾茲赫爾. EWD-1000 (PDF). E·W·戴克斯特拉檔案館. 得克薩斯大學奧斯汀分校美國歷史中心. (文字版本)
- ^ J. Díaz; I. Ramos. Formalization of Programming Concepts: International Colloquium, Peniscola, Spain, April 19–25, 1981. Proceedings. Birkhäuser. 1981: 323 , 326 [2020-12-16]. ISBN 978-3-540-10699-9. （原始內容存檔於2016-12-19）.
- ^ Hoare, C. A. R. Communicating Sequential Processes (PDF). usingcsp.com. 2004 [最初由普林帝斯霍爾於1985出版] [2020-12-16]. （原始內容存檔 (PDF)於2016-01-27）.
- ^ 戴克斯特拉, 艾茲赫爾. EWD-310 (PDF). E·W·戴克斯特拉檔案館. 得克薩斯大學奧斯汀分校美國歷史中心. (文字版本)
- ^ Chandy, K. M.; Misra, J. The Drinking Philosophers Problem. (PDF). ACM Transactions on Programming Languages and Systems. 1984 [2021-01-17]. （原始內容存檔 (PDF)於2012-01-13）.
延伸閱讀
[編輯]- Silberschatz, Abraham; Peterson, James L. Operating Systems Concepts. Addison-Wesley. 1988. ISBN 0-201-18760-4.
- Dijkstra, E. W.（1971, June）. Hierarchical ordering of sequential processes（頁面存檔備份，存於網際網路檔案館）. Acta Informatica 1 (2): 115-138.
- Lehmann, D. J., Rabin M. O,（1981）. On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. Principles Of Programming Languages 1981（POPL'81）, pages 133-138.
