当前位置：首页 > news >正文

用 Java 实现哲学家就餐问题

news 2025/5/10 6:06:15

用 Java 实现哲学家就餐问题

这篇文章将分析死锁产生的条件，并使用 Java 实现经典的哲学家就餐问题以复现死锁，并给出解开死锁的解决方案。

（一）死锁及其产生条件

死锁是多线程编程中常见的问题，指两个或多个线程在执行过程中，因争夺资源而造成的一种互相等待的现象。

死锁产生的条件可以归纳为以下四条。

互斥条件（Mutual Exclusion）：资源一次只能由一个线程占用，如果资源可以被共享，就不会产生死锁；
占有并等待（Hold and Wait）：线程在持有部分资源的情况下，又申请新的资源，新资源被其他线程持有，导致当前线程阻塞；
非抢占条件（No Preemption）：已分配给线程的资源不能被其他线程或操作系统强行夺取，线程持有的资源只能由线程自己释放；
循环等待条件（Circular Wait）：形成一个首尾相连的线程与资源的循环等待链。

（二）哲学家就餐问题及死锁复现

哲学家就餐问题是这样的：五位哲学家围坐在圆桌旁，每人左右各有一根筷子。哲学家需要两根筷子才能吃饭。吃饭前、后以及过程中可能进行思考（其实是为了模拟程序中其它代码的运行，因而这里思考时间具有随机性）。

public class DeadLock {public static class Philosopher {private final Chopstick left;private final Chopstick right;public Philosopher(Chopstick left, Chopstick right) {this.left = left;this.right = right;}public void thinkWhileDoAction(String action) throws InterruptedException {System.out.println(Thread.currentThread().getName() + " - " + action);Thread.sleep(new Random().nextInt(1000) + 1000);}public void eat() throws InterruptedException {thinkWhileDoAction("prepare to eat");synchronized (left) {thinkWhileDoAction(String.format("left %d obtained", left.number));synchronized (right) {thinkWhileDoAction(String.format("right %d obtained and eat", right.number));}}}}public static class Chopstick {public int number;}private final Philosopher[] philosophers;public DeadLock() {Chopstick[] chopsticks = new Chopstick[5];for (int i = 0; i < 5; i++) {chopsticks[i] = new Chopstick();chopsticks[i].number = i;}philosophers = new Philosopher[5];philosophers[0] = new Philosopher(chopsticks[0], chopsticks[1]);philosophers[1] = new Philosopher(chopsticks[1], chopsticks[2]);philosophers[2] = new Philosopher(chopsticks[2], chopsticks[3]);philosophers[3] = new Philosopher(chopsticks[3], chopsticks[4]);philosophers[4] = new Philosopher(chopsticks[4], chopsticks[0]);}public void eat() {for (Philosopher philosopher : philosophers) {new Thread(() -> {try {philosopher.eat();} catch (InterruptedException e) {throw new RuntimeException(e);}}).start();}}public static void main(String[] args) {DeadLock deadLock = new DeadLock();deadLock.eat();}}

通过上面的代码，我们成功的复现了死锁的发生：

Thread-1 - prepare to eat
Thread-5 - prepare to eat
Thread-4 - prepare to eat
Thread-3 - prepare to eat
Thread-2 - prepare to eat
Thread-4 - left 3 obtained
Thread-3 - left 2 obtained
Thread-2 - left 1 obtained
Thread-1 - left 0 obtained
Thread-5 - left 4 obtained

程序最终卡住，不进行任何输出。

（三）哲学家就餐问题的解决

上面提到，死锁发生的条件有四个，因此我们只需要破坏其中一个就可以了。

互斥条件的破坏（不推荐）
- 这种方法下，我们让筷子可以被共享（如使用读写锁，允许多个哲学家同时使用同一根筷子）
- 这与就餐问题的基本设定冲突，因为筷子必须独占使用才能进餐

占有并等待的破坏

让哲学家一次性获取两根筷子，否则不获取任何筷子

public void eat() throws InterruptedException {thinkWhileDoAction("prepare to eat");synchronized (left) {synchronized (right) {thinkWhileDoAction(String.format("both chopsticks %d and %d obtained and eat", left.number, right.number));}}
}

可能导致饥饿（某些哲学家可能永远无法同时获取两根筷子）

非抢占条件的破坏

使用tryLock()等可中断的锁机制

public static class Chopstick {public int number;public Lock lock = new ReentrantLock();
}public void eat() throws InterruptedException {thinkWhileDoAction("prepare to eat");while (true) {if (left.lock.tryLock()) {try {if (right.lock.tryLock()) {try {thinkWhileDoAction(String.format("both chopsticks %d and %d obtained and eat", left.number, right.number));return;} finally {right.lock.unlock();}}} finally {left.lock.unlock();}}}
}