首页 > 编程札记 > 编程

哲学家就餐问题（死锁）

阅读：评论：0

哲学家就餐问题（死锁）

本文主要讲述死锁的一个经典案例—哲学家就餐问题，并对该问题进行修复。

1. 问题描述

看上图，有五位哲学家，每天循环做两件事：思考，吃面。吃面时每人面前都有一个盘子，盘子左边和右边都有一根筷子，他们在吃面之前需要先拿起左边的筷子再拿起右边的筷子，有了一双筷子就可以吃面了。

具体逻辑：

哲学家在吃面之前一般先思考一段时间
思考之后，先拿起左手的筷子
然后拿起右手的筷子
如果筷子被人使用了，那就等别人用完
吃完后，依次把筷子放回原位

逻辑的伪代码如下：

while(true){//思考think();//拿起左边的筷子pick_up_left_fork();//拿起右边的筷子pick_up_right_fork();//吃饭eat();//放下右边的筷子put_down_left_fork();//放下左边的筷子put_down_right_fork();
}

**分析：**如果每个哲学家同时都拿着左手的筷子，并在等右边的筷子，就会有死锁的风险。

2. 代码实现

代码展示如下：

public class Philosopher implements Runnable {private Object leftChopstick;private Object rightChopstick;public Philosopher(Object leftChopstick, Object rightChopstick) {this.leftChopstick = leftChopstick;this.rightChopstick = rightChopstick;}/*** 每个哲学家重复做的事就是：思考，拿筷子吃面*/@Overridepublic void run() {try {while (true) {doAction("思考中...");synchronized (leftChopstick) {doAction("拿起左手的筷子...");synchronized (rightChopstick) {doAction("拿起右手的筷子...");System.out.println("吃面");doAction("放下右手的筷子...");}doAction("放下左手的筷子...");}}} catch (InterruptedException e) {e.printStackTrace();}}private void doAction(String action) throws InterruptedException {System.out.println(Thread.currentThread().getName() + " " + action);Thread.sleep((long) (Math.random() * 10));}
}
public class DiningPhilosophers {public static void main(String[] args) {//五根筷子Object[] chopsticks = new Object[philosophers.length];for (int i = 0; i < chopsticks.length; i++) {chopsticks[i] = new Object();}//五个哲学家,创建5个线程，每个线程持有两把筷子锁for (int i = 0; i < philosophers.length; i++) {Object leftChopstick = chopsticks[i];Object rightChopstick = chopsticks[(i + 1) % chopsticks.length];Philosopher philosophers = new Philosopher(leftChopstick, rightChopstick);new Thread(philosophers, "哲学家" + (i + 1) + "号").start();}}
}

打印结果：

可以看到，五个哲学家最后都拿起了左边筷子，都在等右边筷子，就发生了死锁。

3. 解决哲学家就餐问题的4种方案

服务员检查（避免策略）：引入一个服务员协调，就是说当哲学家要拿起筷子的时候，先询问服务员能否拿起，服务员就会检查拿起筷子是否会有死锁的发生，不会的话就允许哲学家拿起筷子，相反如果可能会发生死锁就不让哲学家拿起筷子。
改变一个哲学家拿叉子的顺序（避免策略）：因为要发生死锁，一定是所有哲学家都拿起了左边的筷子，发生了死锁环路，但是假如有个哲学家不按照顺时针拿的话，就是说先拿右边筷子，这样就永远不会发生都在等右边筷子的死锁环路了。
餐票（避免策略）：就是说每个人吃饭前都要先拿到餐票才能拿筷子吃面，餐票总共只有4张，也就是说看肯定有一个人没有餐票，那么他就不能去拿筷子，那么其余的人就不会死锁，等他们吃完把餐票还回去之后，最后那个人才能吃面。
领导调节（检测与恢复策略）：并不是不让你发生死锁，而是等你死锁了，领导检测到了死锁发生（五个人都拿起了左边的筷子），就会命令其中一个人放下筷子，让别人先吃。

4. 针对第二个方案进行实现：改变一个哲学家拿筷子的顺序（代码演示）

public class DiningPhilosophers {public static void main(String[] args) {//五个哲学家Philosopher[] philosophers = new Philosopher[5];//五根筷子Object[] chopsticks = new Object[philosophers.length];for (int i = 0; i < chopsticks.length; i++) {chopsticks[i] = new Object();}for (int i = 0; i < philosophers.length; i++) {Object leftChopstick = chopsticks[i];Object rightChopstick = chopsticks[(i + 1) % chopsticks.length];// 修改点：这里我们将最后一个哲学家拿筷子的顺序反过来if (i == philosophers.length - 1) {philosophers[i] = new Philosopher(rightChopstick, leftChopstick);} else {philosophers[i] = new Philosopher(leftChopstick, rightChopstick);}new Thread(philosophers[i], "哲学家" + (i + 1) + "号").start();}}
}

打印结果：

程序会一直运行下去，不再发生死锁。