Concurrency: Deadlock

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

  这里使用筷子代替叉子:

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

  下面是Philosopher的实现:

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

  下面的程序会产生死锁:

这里可能发生的一种情况是,所有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不会持有任何筷子,如同上面变成四个人用五只筷子的情况。

  代码如下: