1. Introduction
1.介绍
The Dining Philosophers problem is one of the classic problems used to describe synchronization issues in a multi-threaded environment and illustrate techniques for solving them. Dijkstra first formulated this problem and presented it regarding computers accessing tape drive peripherals.
Dining Philosophers问题是用于描述多线程环境中的同步问题并说明解决问题的技术的经典问题之一。Dijkstra首先提出了这个问题，并就计算机访问磁带机外围设备提出了这个问题。
The present formulation was given by Tony Hoare, who is also known for inventing the quicksort sorting algorithm. In this article, we analyze this well-known problem and code a popular solution.
目前的表述是由Tony Hoare给出的，他也因发明quicksort排序算法而闻名。在这篇文章中，我们分析了这个著名的问题，并编写了一个流行的解决方案。
2. The Problem
2.问题
The diagram above represents the problem. There are five silent philosophers (P1 – P5) sitting around a circular table, spending their lives eating and thinking.
上图代表了这个问题。有五个沉默寡言的哲学家（P1-P5）围坐在一张圆桌旁，用他们的生命在吃饭和思考。
There are five forks for them to share (1 – 5) and to be able to eat, a philosopher needs to have forks in both his hands. After eating, he puts both of them down and then they can be picked by another philosopher who repeats the same cycle.
有五把叉子供他们分享（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. A Solution
3.一个解决方案
An initial solution would be to make each of the philosophers follow the following protocol:
一个初步的解决方案是让每个哲学家都遵循以下协议。
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!
}
As the above pseudo code describes, each philosopher is initially thinking. After a certain amount of time, the philosopher gets hungry and wishes to eat.
正如上面的伪代码所描述的，每个哲学家最初都在思考。在一定时间后，哲学家会感到饥饿，希望吃东西。。
At this point, he reaches for the forks on his either side and once he’s got both of them, proceeds to eat. Once the eating is done, the philosopher then puts the forks down, so that they’re available for his neighbor.
这时，他伸手去拿他两边的叉子，一旦他拿到这两把叉子，就开始吃。一旦吃完了，哲学家就把叉子放下，这样就可以给他的邻居使用。
4. Implementation
4.实施
We model each of our philosophers as classes that implement the Runnable interface so that we can run them as separate threads. Each Philosopher has access to two forks on his left and right sides:
我们将每个哲学家建模为实现Runnable接口的类，这样我们就可以将他们作为独立的线程来运行。每个哲学家都可以在他的左右两边访问两个分叉。
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
}
}We also have a method that instructs a Philosopher to perform an action – eat, think, or acquire forks in preparation for eating:
我们也有一个方法，指示一个哲学家执行一个动作–吃饭，思考，或者获得叉子准备吃饭。
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
}As shown in the code above, each action is simulated by suspending the invoking thread for a random amount of time, so that the execution order isn’t enforced by time alone.
如上面的代码所示，每个动作都是通过暂停调用线程的随机时间来模拟的，所以执行顺序并不是仅仅由时间来强制执行。
Now, let’s implement the core logic of a Philosopher.
现在，让我们来实现一个哲学家的核心逻辑。
To simulate acquiring a fork, we need to lock it so that no two Philosopher threads acquire it at the same time.
为了模拟获取一个分叉，我们需要锁定它，以便没有两个哲学家线程同时获取它。
To achieve this, we use the synchronized keyword to acquire the internal monitor of the fork object and prevent other threads from doing the same. A guide to the synchronized keyword in Java can be found here. We proceed with implementing the run() method in the Philosopher class now:
为了实现这一点，我们使用synchronized关键字来获取分叉对象的内部监视器，并防止其他线程做同样的事情。关于Java中的synchronized关键字的指南可以在这里找到。我们现在继续在Philosopher类中实现run()方法。
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;
}
}
}
This scheme exactly implements the one described earlier: a Philosopher thinks for a while and then decides to eat.
这个方案完全实现了前面描述的方案：一个哲学家思考了一会儿，然后决定吃饭。
After this, he acquires the forks to his left and right and starts eating. When done, he places the forks down. We also add timestamps to each action, which would help us understand the order in which events occur.
之后，他取得左右两边的叉子并开始吃。完成后，他把叉子放下。我们还为每个动作添加了时间戳，这将有助于我们了解事件发生的顺序。
To kick start the whole process, we write a client that creates 5 Philosophers as threads and starts all of them:
为了启动整个过程，我们写了一个客户端，将5个哲学家创建为线程，并启动所有的线程。
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();
}
}
}We model each of the forks as generic Java objects and make as many of them as there are philosophers. We pass each Philosopher his left and right forks that he attempts to lock using the synchronized keyword.
我们将每个分叉都建模为通用的Java对象，并使它们的数量与哲学家的数量相同。我们把他试图用synchronized关键字锁定的左右分叉传递给每个Philosopher。
Running this code results in an output similar to the following. Your output will most likely differ from the one given below, mostly because the sleep() method is invoked for a different interval:
运行这段代码的结果是与下面类似的输出。你的输出很可能与下面的不同，主要是因为sleep()方法被调用的时间间隔不同。
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 forkAll the Philosophers initially start off thinking, and we see that Philosopher 1 proceeds to pick up the left and right fork, then eats and proceeds to place both of them down, after which `Philosopher 5` picks it up.
所有的哲学家一开始都在思考，我们看到哲学家1接着拿起左叉和右叉，然后吃东西，接着把两个叉子都放下，之后`哲学家5`拿起了它。
5. The Problem With the Solution: Deadlock
5.问题与解决方案 Deadlock
Though it seems that the above solution is correct, there’s an issue of a deadlock arising.
虽然看起来上面的解决方案是正确的，但有一个问题，即出现了死锁。
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.
死锁是一种情况，即系统的进展被停止，因为每个进程都在等待获得其他进程持有的资源。
We can confirm the same by running the above code a few times and checking that some times, the code just hangs. Here’s a sample output that demonstrates the above issue:
我们可以通过运行上述代码几次，并检查某些时候，代码只是挂起，来证实这一点。下面是一个演示上述问题的输出样本。
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 forkIn this situation, each of the Philosophers has acquired his left fork, but can’t acquire his right fork, because his neighbor has already acquired it. This situation is commonly known as the circular wait and is one of the conditions that results in a deadlock and prevents the progress of the system.
在这种情况下，每个哲学家都获得了他的左叉，但无法获得他的右叉，因为他的邻居已经获得了。这种情况通常被称为循环等待，是导致死锁的条件之一，阻碍了系统的进展。
6. Resolving the Deadlock
6.解决僵局
As we saw above, the primary reason for a deadlock is the circular wait condition where each process waits upon a resource that’s being held by some other process. Hence, to avoid a deadlock situation we need to make sure that the circular wait condition is broken. There are several ways to achieve this, the simplest one being the follows:
正如我们在上面看到的，死锁的主要原因是循环等待条件，即每个进程都在等待一个被其他进程持有的资源。因此，为了避免死锁情况，我们需要确保循环等待条件被打破。有几种方法可以实现这一点，最简单的方法如下。
All Philosophers reach for their left fork first, except one who first reaches for his right fork.
所有哲学家都先伸向他们的左手叉子，只有一个人先伸向他的右手叉子。
We implement this in our existing code by making a relatively minor change in code:
我们在现有的代码中通过对代码做一个相对较小的改动来实现这一点。
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();
}
}
}
The change comes in lines 17-19 of the above code, where we introduce the condition that makes the last philosopher reach for his right fork first, instead of the left. This breaks the circular wait condition and we can avert the deadlock.
变化出现在上述代码的第17-19行，在这里我们引入了一个条件，使最后一个哲学家首先伸向他的右叉，而不是左叉。这打破了循环等待的条件，我们可以避免死锁。
Following output shows one of the cases where all the Philosophers get their chance to think and eat, without causing a deadlock:
下面的输出显示了其中一种情况，所有的哲学家都得到了他们思考和吃东西的机会，没有造成僵局。
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
It can be verified by running the code several times, that the system is free from the deadlock situation that occurred before.
通过多次运行代码可以验证，系统已经摆脱了之前发生的死锁情况。
7. Conclusion
7.结论
In this article, we explored the famous Dining Philosophers problem and the concepts of circular wait and deadlock. We coded a simple solution that caused a deadlock and made a simple change to break the circular wait and avoid a deadlock. This is just a start, and more sophisticated solutions do exist.
在这篇文章中，我们探讨了著名的餐饮哲学家问题和循环等待和死锁的概念。我们编写了一个导致死锁的简单解决方案，并做了一个简单的修改来打破循环等待，避免死锁。这只是一个开始，更复杂的解决方案确实存在。
The code for this article can be found over on GitHub.
这篇文章的代码可以在GitHub上找到over。