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()
)越短,就越容易发生死锁。
发生死锁需要同时满足以下四个条件:
- 互斥。至少有一个资源是互斥的,一次只能允许一个任务访问。如筷子是互斥的,同时只能被一个人使用。
- 持有并等待。至少有一个任务持有资源,并且在等待获取其他任务持有的资源。每个人先拿自己右边的筷子,拿到后,再拿左边的筷子。如果左边的筷子正在被别人使用,就会等待。
- 资源无法被抢占。资源只能在任务使用完后释放,不能从任务中抢占资源。每个人都不会抢夺别人正在使用筷子。
- 循环等待。一个任务等待另一个任务释放资源,而持有资源的任务在等待其他任务释放资源,如此往复,直到某一个被等待的任务又在等待第一个任务释放资源,形成一个环。大家同时决定要开吃,拿到了自己右边的筷子后,开始等待自己左边的筷子被释放,形成环形的等待链。
只要打破上面的任一个条件,就不会形成死锁。对上面的例子来说,最简单的方法,是打破循环等待,让其中一个人优先拿自己左边的筷子。假设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(); } }