Concurrency: Deadlock

  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();
    }
}