# 僵局，第 3 部分：餐飲哲學家 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Deadlock%2C-Part-3%3A-Dining-Philosophers> ## 背景故事  所以你讓你的哲學家坐在桌子周圍，想要吃一些意大利面（或其他任何東西），他們真的很餓。每個哲學家本質上是相同的，意味著每個哲學家都有基于另一個哲學家的相同指令集，即你不能告訴每個甚至哲學家做一件事，每個奇怪的哲學家做另一件事。 ## 解決方案失敗 ## 左右僵局 我們做什么？我們來試試一個簡單的解決方案 ```c void* philosopher(void* forks){ info phil_info = forks; pthread_mutex_t* left_fork = phil_info->left_fork; pthread_mutex_t* right_fork = phil_info->right_fork; while(phil_info->simulation){ pthread_mutex_lock(left_fork); pthread_mutex_lock(right_fork); eat(left_fork, right_fork); pthread_mutex_unlock(left_fork); pthread_mutex_unlock(right_fork); } } ``` 但這遇到了問題！如果每個人拿起他們的左叉并且正在他們的右叉上等待怎么辦？我們已經使該計劃陷入僵局。重要的是要注意，死鎖不會一直發生，并且隨著哲學家數量的增加，這種解決方案死鎖的可能性會下降。值得注意的是，最終這個解決方案將陷入僵局，讓線程挨餓哪個壞。 ## 的 tryLock？更喜歡活鎖 所以現在你正在考慮打破其中一個 coffman 條件。我們有 * 相互排斥 * 沒有先發制人 * 等等 * 循環等待 好吧，我們不能讓兩個哲學家同時使用一個分叉，相互排斥是不合適的。在我們當前的簡單模型中，一旦他/她掌握它，我們就不能讓哲學家放開互斥鎖，所以我們現在就把這個解決方案拿出來 - 底部有一些注釋。有關此解決方案的頁面讓我們休息一下等待！ ```c void* philosopher(void* forks){ info phil_info = forks; pthread_mutex_t* left_fork = phil_info->left_fork; pthread_mutex_t* right_fork = phil_info->right_fork; while(phil_info->simulation){ pthread_mutex_lock(left_fork); int failed = pthread_mutex_trylock(right_fork); if(!failed){ eat(left_fork, right_fork); pthread_mutex_unlock(right_fork); } pthread_mutex_unlock(left_fork); } } ``` 現在我們的哲學家拿起左叉并試圖抓住右邊。如果它可用，他們會吃。如果它不可用，他們將左叉放下并重試。沒有死鎖！ 但有個問題。如果所有的哲學家同時拿起他們的左手，試圖抓住他們的權利，把他們的左手放下，拿起他們的左手，試圖抓住他們的權利......我們現在已經解決了我們的解決方案！我們可憐的哲學家仍在挨餓，所以讓我們給他們一些適當的解決方案。 ## 可行的解決方案 ## 仲裁員（天真和高級）。 天真的仲裁者解決方案有一個仲裁員（例如互斥）。讓每個哲學家都要求仲裁員吃飯。這種解決方案允許一個哲學家一次吃。當他們完成后，另一位哲學家可以請求允許進食。 這可以防止死鎖，因為沒有循環等待！沒有哲學家必須等待任何其他哲學家。 高級仲裁者解決方案是實施一個類，確定哲學家的分叉是否在仲裁員的掌握之中。如果他們是，他們把它們交給哲學家，讓他吃，并把分叉拿回來。這有額外的好處，可以讓多個哲學家同時吃。 ### 問題： * 這些解決方案很慢 * 他們有一個單點的失敗，仲裁員使其成為瓶頸 * 仲裁者也需要公平，并能夠在第二個解決方案中確定死鎖 * 在實際系統中，仲裁員傾向于將重復的分叉交給那些因為過程調度而吃的哲學家 ## 離開桌子（Stallings 的解決方案） 為什么第一個解決方案陷入僵局？那么有 n 個哲學家和 n 個筷子。如果餐桌上只有 1 個 philsopher 怎么辦？我們可以陷入僵局嗎？沒有。 2 個 philsophers 怎么樣？ 3？ ......你可以看到它的發展方向。斯托林斯的解決方案說要將哲學家從桌子上移除，直到陷入僵局為止 - 想想桌上哲學家的神奇數量是多少。在實際系統中這樣做的方法是通過信號量并讓一定數量的哲學家通過。 ### Problems: * 該解決方案需要大量的上下文切換，這對 CPU 來說非常昂貴 * 你需要事先知道資源的數量，才能讓那些哲學家知道 * 再次優先考慮已經吃過的過程。 ## 部分訂購（Dijkstra 的解決方案） 這是 Dijkstra 的解決方案（他是在考試中提出這個問題的人）。為什么第一個解決方案陷入僵局？ Dijkstra 認為最后一個拿起左叉的哲學家（使解決方案陷入僵局）應該選擇他的權利。他用數字 1..n 來完成它，并告訴每個哲學家拿起他的較低數字叉。 讓我們再次遇到死鎖情況。每個人都試圖先拿起他們的低號碼叉。哲學家 1 獲得分叉 1，哲學家 2 獲得分叉 2，依此類推，直到我們到達哲學家 n。他們必須在 fork 1 和 n 之間進行選擇。 fork 1 已被哲學家 1 所阻擋，所以他們無法拿起那個分叉，這意味著他不會拿起分叉。我們已經打破了循環等待！意味著死鎖是不可能的。 ### Problems: * 在獲取任何資源之前，哲學家需要按順序了解資源集。 * 您需要為所有資源定義部分訂單。 * 優先考慮已經吃過的哲學家。 ## 高級解決方案 還有許多更為先進的解決方案，非詳盡列表包括 * 清潔/臟叉（錢德拉/米斯拉解決方案） * 演員模型（其他消息傳遞模型） * 超級仲裁員（復雜的管道）