哲學家就餐問題

公眾號：小成同學在coding
文章如有問題歡迎指正

5名哲學家，5根筷子，哲學家左右兩邊的筷子跟身邊的人共享，只有同時拿起左手的筷子和右手的筷子，哲學家才可以夾菜，

這個問題其實是一個死鎖問題，

當0號拿著a筷子的時候，它需要申請b這根筷子，才可以夾菜，但b這根筷子在被1號使用著，因此0號無法夾菜，這時候怎么辦，需要等1號吃完，把b筷子放手，而1號想夾菜則需要申請c這根筷子，但c這根筷子又被2號使用著，所以每名哲學家左手都拿著筷子，而右手的筷子都在被使用中，形成了一個死鎖環，

如圖：

思考一下我們這道題都需要哪些類呢？

每一個哲學家應該是一個執行緒，

• 模擬哲學家問題 OOA - OOD - DDD
• class : 哲學家 class : 筷子
• 筷子：編號
• 哲學家：左手的筷子 右手的筷子 編號

代碼實作

package com.mashibing.juc.c_33_TheDinningPhilosophersProblem;

import com.mashibing.util.SleepHelper;

public class T01_DeadLock {
    public static void main(String[] args) {
        
        // 構建程序
        // 1.創建5根筷子
        ChopStick cs0 = new ChopStick();
        ChopStick cs1 = new ChopStick();
        ChopStick cs2 = new ChopStick();
        ChopStick cs3 = new ChopStick();
        ChopStick cs4 = new ChopStick();

        // 2.創建5個執行緒（哲學家）
        Philosohper p0 = new Philosohper("p0", 0, cs0, cs1);// 將cs0給第0號的左手，將cs1給第0號的右手
        Philosohper p1 = new Philosohper("p1", 1, cs1, cs2);// 將cs1也給第1號的左手，cs2給第1號的右手
        Philosohper p2 = new Philosohper("p2", 2, cs2, cs3);// ...
        Philosohper p3 = new Philosohper("p3", 3, cs3, cs4);
        Philosohper p4 = new Philosohper("p4", 4, cs4, cs0);

        p0.start();
        p1.start();
        p2.start();
        p3.start();
        p4.start();
    }

    // 哲學家就是一個執行緒，我們定義類的時候直接繼承Thread類
    public static class Philosohper extends Thread {

        private ChopStick left, right;
        private int index;

        public Philosohper(String name, int index, ChopStick left, ChopStick right) {
            this.setName(name);
            this.index = index;
            this.left = left;
            this.right = right;
        }

        @Override
        public void run() {
            // 將左手的筷子上鎖
            synchronized (left) {
                SleepHelper.sleepSeconds(1 + index);
                // 搶右手的筷子（鎖定A再搶B）
                synchronized (right) {
                    SleepHelper.sleepSeconds(1);
                    System.out.println(index + " 號 哲學家已經吃完");
                }
            }
        }
    }
}

但是我們執行后，程式沒有做任何的輸出，說明死鎖已經形成了，

死鎖一般具有2把以上的鎖，在鎖定1把的時候等待另外1把鎖，

效率不高的解法

• 執行緒粗化：一次性拿到所有資源，把鎖的范圍放大，

  • 我們可以看到，鎖是有5把的，5把鎖互相之間做同步，太復雜了，我們干脆把5把鎖合并成1把鎖，執行緒只有搶到這1把大鎖的時候才可以執行，我們可以把5個筷子存入陣列，或者5個筷子的物件，直接鎖定整個陣列或者這個大物件，

  • 但是這個效率是不高的，我們明明可以只拿到2個筷子就可以夾菜，但這樣明顯是拿到了5個筷子，只有1個人可以夾菜，效率比較低，

  • 但有的人可能會想到：將5個筷子都存放在陣列里，哲學家每次使用只從陣列里拿出2個筷子，這樣就可以保證不沖突了嗎？肯定是不可以的，因為你沒法保證這幾個執行緒分別拿到的筷子是否沖突，這樣的想法還是存在問題的，

• 最少保證（很簡單的解法）：哲學家有一個是左撇子（先這么理解），

  • 因為之前哲學家都是先拿左手的筷子，再去搶右手的筷子，而此時，這個左撇子的哲學家，會先去拿右手的筷子，再去搶左手的筷子，當左撇子拿到了a筷子時，哲學家1號想拿左手邊的筷子（也就是a筷子）是拿不到的，所以他一定不會去拿b筷子，2、3、4號三位哲學家分別都可以拿到左手邊（也就是b、c、d）筷子，但要注意4號，e筷子這里分為兩種情況，①：e筷子被4號拿到，此時4號已經有了兩個筷子，4號吃完，將d、e筷子解鎖，左撇子和3號都可以使用兩個筷子了，從而死鎖被解開，②：e筷子被左撇子拿到，死鎖同樣被解開，

  • 但是這個效率也不是很高，因為只有一個人可以先吃，然后才能將鎖依次解開，這里只有5個哲學家，假如有500個，5000個呢？依次解開需要花費很長的時間，

    

最優解法

• 奇偶互反：偶數為左撇子，奇數為右撇子，

哲學家就餐問題解決方案：

• 兩把鎖合并一把鎖（5把， 5把鎖合成一把鎖，筷子集合，鎖定整個物件）
• 混進一個左撇子（保證有一個人可以先吃到）
• 效率更高的寫法，奇數 偶數分開，混進一半的左撇子

左撇子代碼實作

public void run() {
            // SleepHelper.sleepSeconds(new Random().nextInt(5));
            if (index == 0) { // 左撇子演算法 也可以index % 2 == 0
				// index為0時，先鎖左面再鎖右面
                synchronized (left) {
                    SleepHelper.sleepSeconds(1);
                    synchronized (right) {
                        SleepHelper.sleepSeconds(1);
                        System.out.println(index + " 吃完了！");
                    }
                }
            } else {
                // index不為0時，先鎖右面再鎖左面
                synchronized (right) {
                    SleepHelper.sleepSeconds(1);
                    synchronized (left) {
                        SleepHelper.sleepSeconds(1);
                        System.out.println(index + " 吃完了！");
                    }
                }
            }
        }

我們可以看到，所有人都吃完了，程式不會再產生死鎖了，