Concurrency: Deadlock

Author: 2016-07-07

Java

　　Edsger Dijkstra提出的Dining Philosophers是死锁（Deadlock）的一个经典问题。五个哲学家坐在一张圆桌周围，桌子中间放了一盆面条，哲学家们时而思索，时而吃面。哲学家思索的时候互不妨碍，吃面的时候需要使用两把叉子。叉子只有五把，相邻两个哲学家之间放有一把。吃面时，哲学家只会使用与他相邻的左边和右边的两把叉子，如果叉子被其他人使用，则哲学家就会耐心等待别人用完，再拿起来使用。

　　这里使用筷子代替叉子：

public class Chopstick {
    private boolean taken = false;
    public synchronized
    void take() throws InterruptedException {
        while(taken)
            wait();
        taken = true;
    }
    public synchronized void drop() {
        taken = false;
        notifyAll();
    }
}

通过take()来占用Chopstick，如果已经被别人占用，则wait()，直到别人drop()。

　　下面是Philosopher的实现：

import java.util.concurrent.*;
import java.util.*;

public class Philosopher implements Runnable {
    private Chopstick left;
    private Chopstick right;
    private final int id;
    private final int ponderFactor;
    private Random rand = new Random(47);
    private void pause() throws InterruptedException {
        if(ponderFactor == 0) return;
        TimeUnit.MILLISECONDS.sleep(rand.nextInt(ponderFactor * 10));
    }
    public Philosopher(Chopstick left, Chopstick right, int ident, int ponder) {
        this.left = left;
        this.right = right;
        id = ident;
        ponderFactor = ponder;
    }
    public void run() {
        try {
            while(!Thread.interrupted()) {
                System.out.println(this + " " + "thinking");
                pause();
                // Philosopher becomes hungry
                System.out.println(this + " " + "grabbing right");
                right.take();
                System.out.println(this + " " + "grabbing left");
                left.take();
                System.out.println(this + " " + "eating");
                pause();
                right.drop();
                left.drop();
            }
        } catch(InterruptedException e) {
            System.out.println(this + " " + "exiting via interrupt");
        }
    }
    public String toString() { return "Philosopher " + id; }
}

Philosopher会先思考（pause()）一段时间，然后决定要开吃。Philosopher优先拿取右手边的筷子，然后拿取左手边的筷子，都拿到后，开始吃面，吃完放下两只筷子，从头开始循环。Thinking in Java原书使用的是ponderFactor * 250，这里改成ponderFactor * 10，以使潜在的死锁能够更快地暴露出来。

　　下面的程序会产生死锁：

import java.util.concurrent.*;

public class DeadlockingDiningPhilosophers {
    public static void main(String[] args) throws Exception {
        int ponder = 5;
        if(args.length > 0)
            ponder = Integer.parseInt(args[0]);
        int size = 5;
        if(args.length > 1)
            size = Integer.parseInt(args[1]);
            
        ExecutorService exec = Executors.newCachedThreadPool();
        Chopstick[] sticks = new Chopstick[size];
        for(int i = 0; i < size; i++)
            sticks[i] = new Chopstick();
        for(int i = 0; i < size; i++)
            exec.execute(new Philosopher(
                    sticks[i], sticks[(i+1) % size], i, ponder));
                    
        if(args.length == 3 && args[2].equals("timeout"))
            TimeUnit.SECONDS.sleep(5);
        else {
            System.out.println("Press ‘Enter’ to quit");
            System.in.read();
        }
        
        exec.shutdownNow();
    }
}

这里可能发生的一种情况是，所有Philosopher都想要开吃，每人都拿到了自己左手边的筷子，然后等待自己右边的人放下筷子，结果是大家一起等待，发生死锁。Philosopher花在思考上的时间比花在吃面上的时间越多，占用公共资源（筷子）的时间越短，就越不容易发生死锁。反映在程序上，使用的ponder越小，Philosopher思考和吃面的时间（pause()）越短，就越容易发生死锁。

　　发生死锁需要同时满足以下四个条件：

  1. 互斥。至少有一个资源是互斥的，一次只能允许一个任务访问。如筷子是互斥的，同时只能被一个人使用。
  2. 持有并等待。至少有一个任务持有资源，并且在等待获取其他任务持有的资源。每个人先拿自己右边的筷子，拿到后，再拿左边的筷子。如果左边的筷子正在被别人使用，就会等待。
  3. 资源无法被抢占。资源只能在任务使用完后释放，不能从任务中抢占资源。每个人都不会抢夺别人正在使用筷子。
  4. 循环等待。一个任务等待另一个任务释放资源，而持有资源的任务在等待其他任务释放资源，如此往复，直到某一个被等待的任务又在等待第一个任务释放资源，形成一个环。大家同时决定要开吃，拿到了自己右边的筷子后，开始等待自己左边的筷子被释放，形成环形的等待链。

　　只要打破上面的任一个条件，就不会形成死锁。对上面的例子来说，最简单的方法，是打破循环等待，让其中一个人优先拿自己左边的筷子。假设A、B、C、D、E五个人围着圆桌做成一圈，相邻两人之间放有一只筷子，令A优先拿自己左边的筷子，B、C、D、E优先拿自己右边的筷子。如果大家同时决定要开吃，A和E会同时去拿二人中间的筷子，快的人拿到筷子：

  • 如果A拿到筷子：E会等待A放下筷子，不会去拿自己左边的筷子；在A放下筷子前，E不会持有任何筷子，四个人用五只筷子，总有人能同时拥有两只筷子，成功开吃，并在吃完后放下筷子供别人使用。
  • 如果E拿到筷子：A会等待E放下筷子，不会去拿自己右边的筷子；在E放下筷子前，A不会持有任何筷子，如同上面变成四个人用五只筷子的情况。

　　代码如下：

import java.util.concurrent.*;

public class FixedDiningPhilosophers {
    public static void main(String[] args) throws Exception {
        int ponder = 5;
        if(args.length > 0)
            ponder = Integer.parseInt(args[0]);
        int size = 5;
        if(args.length > 1)
            size = Integer.parseInt(args[1]);
            
        ExecutorService exec = Executors.newCachedThreadPool();
        Chopstick[] sticks = new Chopstick[size];
        for(int i = 0; i < size; i++)
            sticks[i] = new Chopstick();
        for(int i = 0; i < size; i++)
            if(i < (size-1))
                exec.execute(new Philosopher(sticks[i], sticks[i+1], i, ponder));
            else
                exec.execute(new Philosopher(sticks[0], sticks[i], i, ponder));
                
        if(args.length == 3 && args[2].equals("timeout"))
            TimeUnit.SECONDS.sleep(5);
        else {
            System.out.println("Press ‘Enter’ to quit");
            System.in.read();
        }
        
        exec.shutdownNow();
    }
}