《Java-SE-第三十章》之哲学家就餐问题

用户10517932

发布于 2023-10-07 14:47:35

1330

发布于 2023-10-07 14:47:35

文章被收录于专栏：929KC929KC

前言

在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!”
博客主页：KC老衲爱尼姑的博客主页博主的github，平常所写代码皆在于此共勉：talk is cheap, show me the code 作者是爪哇岛的新手，水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

死锁

当某个任务在等待另一个任务,而后者又等待别的任务,这样一直下去,直到这个链条上的任务又在等待第一个任务释放锁。这得到了一个任务之间互相等待的连续循环, 没有那个线程能继续,这称之为死锁。举个栗子,张三想要回家,当开门的时候,发现没钥匙,此时张三突然想起,屋子钥匙放在了车里面,而车的钥匙在房子里面,想要进入就得打开车子,想要打开车子,必须的进屋子,这就"死锁"了。

示例代码

public class DeadlockDemo {
    public static void main(String[] args) {
        Object A = new Object();
        Object B = new Object();
        Thread t1 = new Thread(() -> {
            synchronized (A) {
                System.out.println("lock A");
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                synchronized (B) {
                    System.out.println("lock B");
                }
            }
        });
        t1.start();

        Thread t2 = new Thread(() -> {
            synchronized (B) {
                System.out.println("lock B");
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                synchronized (A) {
                    System.out.println("lock A");
                }
            }
        });
        t2.start();
    }
}

通过使用jconsole观察两个线程的状态

通过观察可知都死锁了

哲学家就餐问题

哲学家就餐问题由Edsger Dijkstra提出的,该问题是一个经典的死锁问题,该问题的基本描述中是指定五个哲学家。这些哲学家将花部分时间思考，花部分时间就餐。当他们思考的时候，不需要任何共享资源；但当他们就餐时，将使用有限数量的餐具。在问题的原始描述中，餐具是叉子。要吃到桌子中央盘子里的意大利面条需要用两把叉子，不过把餐具看成是筷子更合理；很明显，哲学家要就餐就需要两根筷子。问题中引入的难点是：作为哲学家，他们很穷，所以他们只能买五根筷子（更一般地讲，筷子和哲学家的数量相同）。他们围坐在桌子周围，每人之间放一根筷子。当一个哲学家要就餐的时候，这个哲学家必须同时得到左边和右边的筷子。上述问题会产生死锁的情况，当5个哲学家都拿起自己左或者右手手边的筷子，准备拿右手或者左手边的筷子时产生死锁现象。

代码演示

定义一个筷子类

public class Chopstick {
    private String name;

    public Chopstick(String name) {
        this.name = name;
    }
}

定义哲学家

public class Philosopher implements Runnable {
    /**
     * 左手筷子
     */
    private Chopstick left;
    /**
     * 右手筷子
     */
    private Chopstick right;
    /**
     * 名字
     */
    private String name;

    public Philosopher(Chopstick left, Chopstick right, String name) {
        this.left = left;
        this.right = right;
        this.name = name;
    }

    public void thinking() {
        System.out.println(this.name + " " + "thinking");

    }

    public void eating() {
        System.out.println(this.name + " " + "eating");
    }

    @Override
    public void run() {
        while (!Thread.interrupted()) {
            thinking();
            synchronized (this.right) {
                synchronized (this.left) {
                    eating();
                }
            }
        }
    }
}

死锁复现

import java.io.IOException;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class DeadLockPhilosopher {
    public static void main(String[] args) throws InterruptedException, IOException {
        int size = 5;
        ExecutorService exec = Executors.newCachedThreadPool();
        Chopstick []  sticks = new Chopstick[size];
        for (int i = 0; i < sticks.length;i++){
            sticks[i] = new Chopstick(i+"号筷子");
        }
        for (int i = 0; i < size;i++) {
            exec.execute(new Philosopher(sticks[i], sticks[(i+1) % size],i+"号哲学家"));
        }
        TimeUnit.SECONDS.sleep(10);
        exec.shutdownNow();
    }
}

运行结果:

代码先是正常运行了一会,然后将就死锁了,是否死锁依旧用jconsole观察,观察结果如下图

解决办法

要修正死锁问题，你必须明白，当以下四个条件同时满足时，就会发生死锁：

互斥条件。任务使用的资源中至少有一个是不能共享的。这里，一根Chopstick一次就只能被一个Philosopher使用。
请求和保持,至少有一个任务它必须持有一个资源且正在等待获取一个当前被别的任务持有的资源。也就是说，要发生死锁，Philosopher必须拿着一根Chopstick并且等待另一根。
资源不能被任务抢占，任务必须把资源释放当作普通事件。Philosopher很有礼貌，他们不会从其他Philosopher那里抢Chopstick
必须有循环等待，这时，一个任务等待其他任务所持有的资源，后者又在等待另一个任务所持有的资源，这样一直下去，直到有一个任务在等待第一个任务所持有的资源，使得大家都被锁住。在DeadlockingDiningPhilosophers.java中，因为每个Philosopher都试图先得到右边的Chopstick，然后得到左边的Chopstick，所以发生了循环等待。

因为要发生死锁的话，所有这些条件必须全部满足；所以要防止死锁的话，只需破坏其中一个即可。在程序中，防止死锁最容易的方法是破坏第4个条件。有这个条件的原因是每个Philosopher都试图用特定的顺序拿Chopstick：先右后左。正因为如此，就可能会发生“每个人都拿着右边的Chopstick，并等待左边的Chopstick”的情况，这就是循环等待条件。然而，如果最后一个Philosopher被初始化成先拿左边的Chopstick，后拿右边的Chopstick，那么这个Philosopher将永远不会阻止其右边的Philosopher拿起他们的Chopstick。

示例代码

import java.util.concurrent.*;

public class FixedDiningPhilosophers {
    public static void main(String[] args) throws Exception {
        ExecutorService exec = Executors.newCachedThreadPool();
        Chopstick[] sticks = new Chopstick[5];
        int size = 5;
        for (int i = 0; i < sticks.length; i++) {
            sticks[i] = new Chopstick(i + "号筷子");
        }
        for (int i = 0; i < sticks.length; i++) {
            //前四个哲学家
            if (i < (size - 1)) {
                exec.execute(new Philosopher(sticks[i], sticks[(i + 1)], i + "哲学家"));
            } else {
                exec.execute(new Philosopher(sticks[0], sticks[(i)], i + "哲学家"));
            }
        }
        TimeUnit.SECONDS.sleep(5);
        exec.shutdownNow();
    }
}

运行结果: