java并发系列-Java 中的哲学家就餐问题

1 介绍

哲学家就餐难题是用于描述多线程环境同步议题和解释如何解决该问题的技术的经典难题之一。Dijkstra 第一个提出了该难题并将其用于表达计算机访问磁带机外围设备的场景中。

现在的难题表述由 Tony Hoare 给出,他发明了快排算法。这篇文章中,我们分析这个著名的难题并编程解决。

2 哲学家就餐难题

哲学家就餐难题

上图展示了这个难题。五个安静的哲学家(P1-P5)围坐在一张圆桌前,只做吃饭和思考两件事。

他们共享五个叉子(1-5),为了吃饭,一个哲学家需要两只手同时都握着叉子。吃完饭,他将两个叉子都放下。另一个哲学家可以拿取进行就餐。

The goal is to come up with a scheme/protocol that helps the philosophers achieve their goal of eating and thinking without getting starved to death.

目标是找到一个方案帮助哲学家在吃饭和思考时不会因为拿不到刀叉而活活饿死。

3 解决方案

第一个方案是让各个哲学家遵循下面的约定:

1
2
3
4
5
6
7
8
9
10
11
12
13
while(true) { 
// Initially, thinking about life, universe, and everything
think();

// Take a break from thinking, hungry now
pick_up_left_fork();
pick_up_right_fork();
eat();
put_down_right_fork();
put_down_left_fork();

// Not hungry anymore. Back to thinking!
}

如上面伪代码(pseudo code)所述,各个哲学家初始处于思考状态。在一定时间后,哲学家感到饥饿并渴望吃饭。

这时,他尝试拿取放于两边的叉子,一旦拿到这两个叉子,他就开始吃饭。吃饭一旦结束,他就放下叉子,他盘边的哲学家就可以拿取这些叉子。

4 实现

我们将哲学家定义成类,该类实现了 Runnable 接口,这样我们可以将他们作为线程执行。各个 Philosopher 类可以访问他左右两边的 fork:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Philosopher implements Runnable {

// The forks on either side of this Philosopher
private Object leftFork;
private Object rightFork;

public Philosopher(Object leftFork, Object rightFork) {
this.leftFork = leftFork;
this.rightFork = rightFork;
}

@Override
public void run() {
// Yet to populate this method
}

}

我们也构造了 Philosopher 采取行动的方法 - 吃饭,思考,或者准备吃饭时拿去叉子:

1
2
3
4
5
6
7
8
9
10
11
12
public class Philosopher implements Runnable {

// Member variables, standard constructor

private void doAction(String action) throws InterruptedException {
System.out.println(
Thread.currentThread().getName() + " " + action);
Thread.sleep(((int) (Math.random() * 100)));
}

// Rest of the methods written earlier
}

如上述代码所示,各个动作通过在调用的线程中等待随机时间来模拟,这样执行顺序就不会单单受限于时间。

现在,我们实现 Philosopher 的核心逻辑。

为了模拟获取叉子,我们要锁定叉子以免同时有两个哲学家拿到它。

为了实现这个效果,我们使用关键字 synchronized 获取 fork 对象的内部监视器同时也避免了其他线程执行了相同操作。Java 中关键字 synchronized 的介绍查看这里。我们接着实现 Philosopher 类中的 run() 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Philosopher implements Runnable {

// Member variables, methods defined earlier

@Override
public void run() {
try {
while (true) {

// thinking
doAction(System.nanoTime() + ": Thinking");
synchronized (leftFork) {
doAction(
System.nanoTime()
+ ": Picked up left fork");
synchronized (rightFork) {
// eating
doAction(
System.nanoTime()
+ ": Picked up right fork - eating");

doAction(
System.nanoTime()
+ ": Put down right fork");
}

// Back to thinking
doAction(
System.nanoTime()
+ ": Put down left fork. Back to thinking");
}
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
}
}

这个方法准确实现了之前描述的方案:Philosopher 思考了一会儿然后决定吃饭。之后,他拿到他左右两侧的叉子并开始吃饭。吃完饭,他放下叉子。我们也在各个行为里添加了时间戳,这可以帮助我们更好理解事情发生的顺序。

为了将整个流程跑起来,我们写了一个客户端,创建了 5 个 Philosopher 线程并将他们跑起来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class DiningPhilosophers {

public static void main(String[] args) throws Exception {

Philosopher[] philosophers = new Philosopher[5];
Object[] forks = new Object[philosophers.length];

for (int i = 0; i < forks.length; i++) {
forks[i] = new Object();
}

for (int i = 0; i < philosophers.length; i++) {
Object leftFork = forks[i];
Object rightFork = forks[(i + 1) % forks.length];

philosophers[i] = new Philosopher(leftFork, rightFork);

Thread t
= new Thread(philosophers[i], "Philosopher " + (i + 1));
t.start();
}
}
}

我们将 fork 定义成 Java 对象,并生成哲学家所需数量的 forks。我们将哲学家尝试使用关键字 synchronized锁定的左右两边的叉子交给他们。

执行这个代码会产生如下类似的输出。你的输出很可能与下面不同,因为 sleep() 方法调用时间间隔会变化:

1
2
3
4
5
6
7
8
9
10
11
12
13
Philosopher 1 8038014601251: Thinking
Philosopher 2 8038014828862: Thinking
Philosopher 3 8038015066722: Thinking
Philosopher 4 8038015284511: Thinking
Philosopher 5 8038015468564: Thinking
Philosopher 1 8038016857288: Picked up left fork
Philosopher 1 8038022332758: Picked up right fork - eating
Philosopher 3 8038028886069: Picked up left fork
Philosopher 4 8038063952219: Picked up left fork
Philosopher 1 8038067505168: Put down right fork
Philosopher 2 8038089505264: Picked up left fork
Philosopher 1 8038089505264: Put down left fork. Back to thinking
Philosopher 5 8038111040317: Picked up left fork

所有的哲学家刚开始都处于思考状态,Philosopher 1 开始拿起左右两边的叉子,然后吃饭接着放下叉子。之后,Philosopher 5 拿起叉子。

5 解决方案的问题:死锁

虽然上面的方案看起来没问题,但是可能会出现死锁。

A deadlock is a situation where the progress of a system is halted as each process is waiting to acquire a resource held by some other process.

死锁是由于各个线程互相等待其他线程的资源而导致系统无法进行下去的情况。

我们通过多次执行上述代码可以发现代码确实挂在那里进行不下去。下面是上述问题的一个类似输出:

1
2
3
4
5
6
7
8
9
10
Philosopher 1 8487540546530: Thinking
Philosopher 2 8487542012975: Thinking
Philosopher 3 8487543057508: Thinking
Philosopher 4 8487543318428: Thinking
Philosopher 5 8487544590144: Thinking
Philosopher 3 8487589069046: Picked up left fork
Philosopher 1 8487596641267: Picked up left fork
Philosopher 5 8487597646086: Picked up left fork
Philosopher 4 8487617680958: Picked up left fork
Philosopher 2 8487631148853: Picked up left fork

这个场景中,各个 Philosophers 拿到了他们左手边的叉子,但是拿不到他们右手边的叉子,因此右手边的叉子已经被旁边的哲学家拿走。这种场景称为循环等待(circular wait),是造成死锁的情况之一。

6 解决死锁

如上所见,死锁的主要原因是发生循环等待的情况,各个线程等待被其他线程持有的资源。因此,为了防止死锁,我们需要确保不会发生循环等待的情况。有好几种方式可以解决这个问题,下面描述了最简单的一种:

All Philosophers reach for their left fork first, except one who first reaches for his right fork.

所有的哲学家首先伸手去拿他们左手边的叉子,除了一个哲学家首先伸手去拿他右边的叉子。

我们稍微对之前的代码进行调整来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class DiningPhilosophers {

public static void main(String[] args) throws Exception {

final Philosopher[] philosophers = new Philosopher[5];
Object[] forks = new Object[philosophers.length];

for (int i = 0; i < forks.length; i++) {
forks[i] = new Object();
}

for (int i = 0; i < philosophers.length; i++) {
Object leftFork = forks[i];
Object rightFork = forks[(i + 1) % forks.length];

if (i == philosophers.length - 1) {

// The last philosopher picks up the right fork first
philosophers[i] = new Philosopher(rightFork, leftFork);
} else {
philosophers[i] = new Philosopher(leftFork, rightFork);
}

Thread t
= new Thread(philosophers[i], "Philosopher " + (i + 1));
t.start();
}
}
}

在上面代码的 17-19 行做了修改,让最后一个哲学家首先去拿右边的叉子而不是左边。这破坏了循环等待而产生不了死锁。

下面的输出展示了所有哲学家获得思考和吃饭的机会而不产生死锁的情况之一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Philosopher 1 88519839556188: Thinking
Philosopher 2 88519840186495: Thinking
Philosopher 3 88519840647695: Thinking
Philosopher 4 88519840870182: Thinking
Philosopher 5 88519840956443: Thinking
Philosopher 3 88519864404195: Picked up left fork
Philosopher 5 88519871990082: Picked up left fork
Philosopher 4 88519874059504: Picked up left fork
Philosopher 5 88519876989405: Picked up right fork - eating
Philosopher 2 88519935045524: Picked up left fork
Philosopher 5 88519951109805: Put down right fork
Philosopher 4 88519997119634: Picked up right fork - eating
Philosopher 5 88519997113229: Put down left fork. Back to thinking
Philosopher 5 88520011135846: Thinking
Philosopher 1 88520011129013: Picked up left fork
Philosopher 4 88520028194269: Put down right fork
Philosopher 4 88520057160194: Put down left fork. Back to thinking
Philosopher 3 88520067162257: Picked up right fork - eating
Philosopher 4 88520067158414: Thinking
Philosopher 3 88520160247801: Put down right fork
Philosopher 4 88520249049308: Picked up left fork
Philosopher 3 88520249119769: Put down left fork. Back to thinking

这可以通过执行多次来验证,系统再也不会发生之前发生的死锁的情况。

7 总结

这篇文章,我们研究了著名的哲学家就餐难题以及循环等待和死锁的概念。我们编写了一个简单的方案触发了死锁,然后通过简单的修改破坏了循环等待而避免了死锁。这只是一个开始,其实还有很多精巧的解决方案。


本文为译文,作者通过翻译达到学习目的。 原文链接 | 原文源码链接 | 本站源码链接