基本介紹
- 中文名：哲學家就餐問題
- 所屬：計算機科學
- 相關：並行計算中多執行緒同步
- 人物：艾茲格·迪科斯徹
問題描述,問題解法,服務生解法,資源分級解法,Chandy/Misra解法,
問題描述
哲學家就餐問題可以這樣表述，假設有五位哲學家圍坐在一張圓形餐桌旁，做以下兩件事情之一：吃飯，或者思考。吃東西的時候，他們就停止思考，思考的時候也停止吃東西。餐桌中間有一大碗意大利麵，每兩個哲學家之間有一隻餐叉。因為用一隻餐叉很難吃到意大利麵，所以假設哲學家必須用兩隻餐叉吃東西。他們只能使用自己左右手邊的那兩隻餐叉。哲學家就餐問題有時也用米飯和筷子而不是意大利麵和餐叉來描述，因為很明顯，吃米飯必須用兩根筷子。
哲學家從來不交談，這就很危險，可能產生死鎖，每個哲學家都拿著左手的餐叉，永遠都在等右邊的餐叉（或者相反）。即使沒有死鎖，也有可能發生資源耗盡。例如，假設規定當哲學家等待另一隻餐叉超過五分鐘後就放下自己手裡的那一隻餐叉，並且再等五分鐘後進行下一次嘗試。這個策略消除了死鎖（系統總會進入到下一個狀態），但仍然有可能發生“活鎖”。如果五位哲學家在完全相同的時刻進入餐廳，並同時拿起左邊的餐叉，那么這些哲學家就會等待五分鐘，同時放下手中的餐叉，再等五分鐘，又同時拿起這些餐叉。
在實際的計算機問題中，缺乏餐叉可以類比為缺乏共享資源。一種常用的計算機技術是資源加鎖，用來保證在某個時刻，資源只能被一個程式或一段代碼訪問。當一個程式想要使用的資源已經被另一個程式鎖定，它就等待資源解鎖。當多個程式涉及到加鎖的資源時，在某些情況下就有可能發生死鎖。例如，某個程式需要訪問兩個檔案，當兩個這樣的程式各鎖了一個檔案，那它們都在等待對方解鎖另一個檔案，而這永遠不會發生。
問題解法
服務生解法
一個簡單的解法是引入一個餐廳服務生，哲學家必須經過他的允許才能拿起餐叉。因為服務生知道哪只餐叉正在使用，所以他能夠作出判斷避免死鎖。
為了演示這種解法，假設哲學家依次標號為A至E。如果A和C在吃東西，則有四隻餐叉在使用中。B坐在A和C之間，所以兩隻餐叉都無法使用，而D和E之間有一隻空餘的餐叉。假設這時D想要吃東西。如果他拿起了第五隻餐叉，就有可能發生死鎖。相反，如果他徵求服務生同意，服務生會讓他等待。這樣，我們就能保證下次當兩把餐叉空餘出來時，一定有一位哲學家可以成功的得到一對餐叉，從而避免了死鎖。
資源分級解法
另一個簡單的解法是為資源（這裡是餐叉）分配一個偏序或者分級的關係，並約定所有資源都按照這種順序獲取，按相反順序釋放，而且保證不會有兩個無關資源同時被同一項工作所需要。在哲學家就餐問題中，資源（餐叉）按照某種規則編號為1至5，每一個工作單元（哲學家）總是先拿起左右兩邊編號較低的餐叉，再拿編號較高的。用完餐叉後，他總是先放下編號較高的餐叉，再放下編號較低的。在這種情況下，當四位哲學家同時拿起他們手邊編號較低的餐叉時，只有編號最高的餐叉留在桌上，從而第五位哲學家就不能使用任何一隻餐叉了。而且，只有一位哲學家能使用最高編號的餐叉，所以他能使用兩隻餐叉用餐。當他吃完後，他會先放下編號最高的餐叉，再放下編號較低的餐叉，從而讓另一位哲學家拿起後邊的這隻開始吃東西。
儘管資源分級能避免死鎖，但這種策略並不總是實用的，特別是當所需資源的列表並不是事先知道的時候。例如，假設一個工作單元拿著資源3和5，並決定需要資源2，則必須先要釋放5，之後釋放3，才能得到2，之後必須重新按順序獲取3和5。對需要訪問大量資料庫記錄的電腦程式來說，如果需要先釋放高編號的記錄才能訪問新的記錄，那么運行效率就不會高，因此這種方法在這裡並不實用。
這種方法經常是實際計算機科學問題中最實用的解法，通過為分級鎖指定常量，強制獲得鎖的順序，就可以解決這個問題。
Chandy/Misra解法
1984年，K. Mani Chandy和J. Misra提出了哲學家就餐問題的另一個解法，允許任意的用戶（編號P1, ..., Pn）爭用任意數量的資源。與迪科斯徹的解法不同的是，這裡編號可以是任意的。
1.對每一對競爭一個資源的哲學家，新拿一個餐叉，給編號較低的哲學家。每隻餐叉都是“乾淨的”或者“髒的”。最初，所有的餐叉都是髒的。
2.當一位哲學家要使用資源（也就是要吃東西）時，他必須從與他競爭的鄰居那裡得到。對每隻他當前沒有的餐叉，他都傳送一個請求。
3.當擁有餐叉的哲學家收到請求時，如果餐叉是乾淨的，那么他繼續留著，否則就擦乾淨並交出餐叉。
4.當某個哲學家吃東西後，他的餐叉就變髒了。如果另一個哲學家之前請求過其中的餐叉，那他就擦乾淨並交出餐叉。
這個解法允許很大的並行性，適用於任意大多問題。
