README.md

Dining philosophers problem

wiki

哲學家就餐問題可以這樣表述，假設有五位哲學家圍坐在一張圓形餐桌旁，做以下兩件事情之一：

• 吃飯,吃東西的時候，他們就停止思考。
• 思考,思考的時候也停止吃東西。

餐桌上有五碗義大利麵，每位哲學家之間各有一筷子。因為用一支筷子很難吃到義大利麵，所以假設哲學家必須用兩支筷子吃東西。 他們只能使用自己左右手邊的那兩支筷子。

Deadlock

這個問題旨在說明避免死結的挑戰，死結是一種程式無法繼續執行的狀態。要更好理解這個問題，假設我們要求哲學家遵守以下規則：

• 哲學家在左邊的筷子可用（沒有其他人拿起）之前處於思考狀 態。如果左邊的筷子可用，就拿起來。
• 哲學家等待右邊的筷子可用。如果右邊的筷子可用，就拿起來。
• 如果兩個筷子都已經拿起來，開始吃義大利麵，每次吃麵都花費同樣的時間。
• 吃完後先放下左邊的筷子。
• 然後放下右邊的筷子。
• 開始思考（進入一個循環）

這個解法是失敗的，當每個哲學家都拿起左側的筷子，等待右側的筷子可用時，就會進入死結狀態，每個哲學家將永遠都在等待（右邊的）另一個哲學家放下筷子。

Solution

確保每個哲學家左右兩隻筷子都可以用時才拿起筷子

code

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
// 0 <= i <= 4 i is the philosopher number
P(i){   
    while(1){
        P(mutex);
        P(chopstick[i]); // pick up left chopstick
        P(chopstick[(i+1)%5]); // pick up right chopstick
        V(mutex);
        // eat
        V(chopstick[i]); // put down left chopstick
        V(chopstick[(i+1)%5]); // put down right chopstick
        // think
    }
}

服務生解法

交給服務生分配筷子,服務生只要確保每個哲學家都能拿到兩隻筷子即可,這樣就不會有死結的問題

資源分級解法

把筷子編號1到5,哲學家總是先拿起左右兩邊編號較低的筷子，再拿編號較高的。 用完餐叉後，他總是先放下編號較高的餐叉，再放下編號較低的。 在這種情況下，當四位哲學家同時拿起他們手邊編號較低的餐叉時，只有編號最高的餐叉留在桌上，從而第五位哲學家就不能使用任何一支餐叉了

這種方法跟奇數哲學家先拿左邊筷子,在拿右邊筷子,偶數哲學家先拿右邊筷子,在拿左邊筷子的方法差不多

錢迪/米斯拉解法

• 對每一對競爭一個資源的哲學家，新拿一個餐叉，給編號較低的哲學家。每隻餐叉都是「乾淨的」或者「髒的」。最初，所有的餐叉都是髒的。
• 當一位哲學家要使用資源（也就是要吃東西）時，他必須從與他競爭的鄰居那裡得到。對每隻他當前沒有的餐叉，他都傳送一個請求。
• 當擁有餐叉的哲學家收到請求時，如果餐叉是乾淨的，那麼他繼續留著，否則就擦乾淨並交出餐叉。
• 當某個哲學家吃東西後，他的餐叉就變髒了。如果另一個哲學家之前請求過其中的餐叉，那他就擦乾淨並交出餐叉。

這個解法允許很大的並列性，適用於任意大的問題。