225.死锁（进餐哲学家）

àì夳堔傛蜴生んèń 2023-10-04 15:38 38阅读 0赞

什么是死锁？网络上的一个著名笑话解释如下：

*面试者：*向我们解释死锁，我们会雇用你！

*求职者：*雇用我，我会向你解释......

一个简单的死锁可以解释为一个 A 线程持有 L 锁并试图获取 P 锁，同时，有一个 B 线程持有 P 锁并试图获取 L 锁。这种死锁被称为循环**等待**。Java 没有死锁检测和解决机制（如数据库那样），因此死锁对于应用程序来说可能非常尴尬。死锁可能完全或部分阻塞应用程序，可能导致严重的性能损失、奇怪的行为等。通常，死锁很难调试，解决死锁的唯一方法是重新启动应用程序并期待最好的结果。

哲学家进餐是一个用来说明死锁的著名问题。这个问题说五个哲学家围坐在一张桌子旁。他们每个人都交替思考和进食。为了吃饭，哲学家需要手里拿着两把叉子——左手的叉子和右手的叉子。困难在于只有五个叉子。吃完后，哲学家将两个叉子放回桌子上，然后可以由重复相同循环的另一个哲学家拿起。当哲学家 不吃饭时，他/她在思考。下图说明了这种情况：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70][]

主要任务是找到解决这个问题的方法，让哲学家们以这样的方式思考和进食，以避免被饿死。

在代码中，我们可以将每个哲学家视为一个Runnable实例。作为Runnable 实例，我们可以在单独的线程中执行它们。每个哲学家可以拿起放在他左右两侧的两个叉子。如果我们将叉表示为String，那么我们可以使用以下代码：

public class Philosopher implements Runnable {
    
      private final String leftFork;
      private final String rightFork;
    
      public Philosopher(String leftFork, String rightFork) {
        this.leftFork = leftFork;
        this.rightFork = rightFork;
      }
    
      @Override
      public void run() {
        // implemented below
      }
    }

因此，哲学家可以选择 leftFork和rightFork。但是由于哲学家共享这些叉子，因此哲学家必须获得这两个叉子的排他锁。拥有一个排他锁 leftFork和一个排他锁rightFork， 就相当于手里拿着两把叉子。拥有独占的leftFork锁r和rightFork锁r等同于哲学家的饮食。释放两个排他锁，相当于哲学家不吃饭进行思考。

可以通过synchronized关键字实现锁定，如下run()方法所示：

@Override
    public void run() {
    
      while (true) {
        logger.info(() -> Thread.currentThread().getName() 
          + ": thinking");
        doIt();
    
        synchronized(leftFork) {
          logger.info(() -> Thread.currentThread().getName() 
            + ": took the left fork (" + leftFork + ")");
          doIt();
    
          synchronized(rightFork) {
            logger.info(() -> Thread.currentThread().getName() 
              + ": took the right fork (" + rightFork + ") and eating");
            doIt();
    
            logger.info(() -> Thread.currentThread().getName() 
              + ": put the right fork ( " + rightFork 
              + ") on the table");
            doIt();
          }
    
          logger.info(() -> Thread.currentThread().getName() 
            + ": put the left fork (" + leftFork 
            + ") on the table and thinking");
          doIt();
        }
      }
    }

哲学家从思考开始。过了一会儿，他饿了，所以他试图拿起左右叉。如果成功，他会吃一段时间。随后，他将叉子放在桌上，继续思考，直到又饿了。与此同时，另一位哲学家将吃饭。

该doIt()方法通过随机睡眠模拟所涉及的动作（思考、进食、拿起和放回叉子）。这可以在代码中看到如下：

private static void doIt() {
      try {
        Thread.sleep(rnd.nextInt(2000));
      } catch (InterruptedException ex) {
        Thread.currentThread().interrupt();
        logger.severe(() -> "Exception: " + ex);
      }
    }

最后，我们需要叉子和哲学家，看下面的代码：

String[] forks = {
      "Fork-1", "Fork-2", "Fork-3", "Fork-4", "Fork-5"
    };
    
    Philosopher[] philosophers = {
      new Philosopher(forks[0], forks[1]),
      new Philosopher(forks[1], forks[2]),
      new Philosopher(forks[2], forks[3]),
      new Philosopher(forks[3], forks[4]),
      new Philosopher(forks[4], forks[0])
    };

每个哲学家都会在一个线程中运行，如下所示：

Thread threadPhilosopher1 
      = new Thread(philosophers[0], "Philosopher-1");
    ...
    Thread threadPhilosopher5 
      = new Thread(philosophers[4], "Philosopher-5");
    
    threadPhilosopher1.start();
    ...
    threadPhilosopher5.start();

这个实现似乎没问题，甚至可以正常工作一段时间。但是，这个实现迟早会阻塞，输出如下：

[17:29:21] [INFO] Philosopher-5: took the left fork (Fork-5)
    ...
    // nothing happens

这是一个死锁！每个哲学家都拿着他的左叉子（上面有排他锁）并等待右叉子放在桌子上（锁要被释放）。显然，这种期望是无法满足的，因为叉子只有五个，每个哲学家手里都拿着一个。

为了避免这种死锁，有一个非常简单的解决方案。我们只是强迫其中一位哲学家先拿起右边的叉子。成功选择右边的叉子后，他可以尝试选择左边的叉子。在代码中，这是对以下行的快速修改：

// the original line
    new Philosopher(forks[4], forks[0])
    
    // the modified line that eliminates the deadlock
    new Philosopher(forks[0], forks[4])

这一次我们可以无死锁地运行应用程序。

package modern.challenge;
    
    public class Main {
    
        public static void main(String[] args) {
    
            System.setProperty("java.util.logging.SimpleFormatter.format",
                    "[%1$tT] [%4$-7s] %5$s %n");
    
            String[] forks = {"Fork-1", "Fork-2", "Fork-3", "Fork-4", "Fork-5"};
            Philosopher[] philosophers = {
                new Philosopher(forks[0], forks[1]),
                new Philosopher(forks[1], forks[2]),
                new Philosopher(forks[2], forks[3]),
                new Philosopher(forks[3], forks[4]),
                new Philosopher(forks[0], forks[4])
            };
    
            Thread threadPhilosopher1 = new Thread(philosophers[0], "Philosopher-1");
            Thread threadPhilosopher2 = new Thread(philosophers[1], "Philosopher-2");
            Thread threadPhilosopher3 = new Thread(philosophers[2], "Philosopher-3");
            Thread threadPhilosopher4 = new Thread(philosophers[3], "Philosopher-4");
            Thread threadPhilosopher5 = new Thread(philosophers[4], "Philosopher-5");
    
            threadPhilosopher1.start();
            threadPhilosopher2.start();
            threadPhilosopher3.start();
            threadPhilosopher4.start();
            threadPhilosopher5.start();
        }
    
    }

package modern.challenge;
    
    import java.util.Random;
    import java.util.logging.Logger;
    
    public class Philosopher implements Runnable {
    
        private static final Logger logger = Logger.getLogger(Philosopher.class.getName());
        private static final Random rnd = new Random();
    
        private final String leftFork;
        private final String rightFork;
    
        public Philosopher(String leftFork, String rightFork) {
            this.leftFork = leftFork;
            this.rightFork = rightFork;
        }
    
        @Override
        public void run() {
    
            while (true) {
                logger.info(() -> Thread.currentThread().getName() + ": thinking");
                doIt();
                synchronized (leftFork) {
                    logger.info(() -> Thread.currentThread().getName()
                            + ": took the left fork (" + leftFork + ")");
                    doIt();
                    synchronized (rightFork) {
                        logger.info(() -> Thread.currentThread().getName()
                                + ": took the right fork (" + rightFork + ") and eating");
                        doIt();
                        logger.info(() -> Thread.currentThread().getName()
                                + ": put the right fork ( " + rightFork + ") on the table");
                        doIt();
                    }
                    logger.info(() -> Thread.currentThread().getName()
                            + ": put the left fork (" + leftFork + ") on the table and thinking");
                    doIt();
                }
            }
        }
    
        private static void doIt() {
            try {
                Thread.sleep(rnd.nextInt(2000));
            } catch (InterruptedException ex) {
                Thread.currentThread().interrupt();
                logger.severe(() -> "Exception: " + ex);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210606174326281.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70