經典的哲學家就餐問題，忘記的再回憶回憶
哲學家就餐問題是用于描述多線程環境中的同步問題并闡釋解決這些問題的技術的經典問題之一。該問題最初由Dijkstra提出，是關于計算機訪問磁帶驅動器外設的情況。當前的表述由Tony Hoare給出，他還發明了快速排序算法。
在本文中，我們將分析這個著名的問題并編寫一個常用的解決方案。
一、問題描述
經典的哲學家就餐問題
上述圖表展示了哲學家就餐問題。有五位沉默的哲學家（P1 - P5）圍坐在一張圓形餐桌旁，他們一生都在進食和思考。
有五把叉子供他們共享（1 - 5），為了能夠進食，一位哲學家需要雙手都持有叉子。用餐完畢后，他放下兩把叉子，然后其他哲學家可以拿起它們，重復相同的循環。
目標是設計一種方案，幫助哲學家們實現進食和思考的目標，而不會餓死。
二、解決方案
最初的解決方案是讓每個哲學家遵循以下邏輯：
while (true) {
// 初始狀態，思考人生、宇宙及萬物
think();
// 停止思考，感到饑餓
pick_up_left_fork();
pick_up_right_fork();
eat();
put_down_right_fork();
put_down_left_fork();
// 不再饑餓，繼續思考！
}如上述偽代碼所述，每個哲學家最初都在思考。一段時間后，哲學家感到饑餓并希望進食。
此時，他拿起左右兩邊的叉子，一旦拿到兩把叉子，就開始進食。進食完成后，哲學家放下叉子，以便鄰居可以使用。
三、實現
我們將每個哲學家建模為實現Runnable接口的類，以便可以作為單獨的線程運行它們。每個哲學家都可以訪問其左右兩側的兩把叉子：
public class Philosopher implements Runnable {
// 此哲學家左右兩側的叉子
private Object leftFork;
private Object rightFork;
public Philosopher(Object leftFork, Object rightFork) {
this.leftFork = leftFork;
this.rightFork = rightFork;
}
@Override
public void run() {
// 待填充此方法
}
}我們還有一個方法，用于指示哲學家執行某個動作——進食、思考或獲取叉子準備進食：
public class Philosopher implements Runnable {
// 成員變量、標準構造函數
private void doAction(String action) throws InterruptedException {
System.out.println(Thread.currentThread().getName() + " " + action);
Thread.sleep(((int) (Math.random() * 100)));
}
// 之前編寫的其他方法
}如上述代碼所示，每個動作通過隨機暫停調用線程一段時間來模擬，這樣執行順序就不僅僅由時間決定。
現在，我們實現哲學家的核心邏輯。
為了模擬獲取叉子，我們需要鎖定它，以確保沒有兩個哲學家線程同時獲取它。
為了實現這一點，我們使用synchronized關鍵字獲取叉子對象的內部監視器，并防止其他線程執行相同操作。現在我們繼續在Philosopher類中實現run()方法：
public class Philosopher implements Runnable {
// 之前定義的成員變量、方法
@Override
public void run() {
try {
while (true) {
// 思考
doAction(System.nanoTime() + ": Thinking");
synchronized (leftFork) {
doAction(System.nanoTime() + ": Picked up left fork");
synchronized (rightFork) {
// 進食
doAction(System.nanoTime() + ": Picked up right fork - eating");
doAction(System.nanoTime() + ": Put down right fork");
}
// 回到思考狀態
doAction(System.nanoTime() + ": Put down left fork. Back to thinking");
}
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
}
}此方案準確實現了前面描述的內容：哲學家思考一段時間后決定進食。
之后，他獲取左右兩邊的叉子并開始進食。用餐完畢后，他放下叉子。我們還為每個動作添加了時間戳，這將有助于我們了解事件發生的順序。
為了啟動整個過程，我們編寫一個Main函數，創建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();
}
}
}我們將每個叉子建模為通用的Java對象，并創建與哲學家數量相同的叉子。我們將每個哲學家的左右叉子傳遞給他，嘗試使用synchronized關鍵字鎖定這些叉子。
運行此代碼將產生類似以下的輸出。你的輸出很可能與下面給出的不同，主要是因為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 fork所有哲學家最初都在思考，我們看到哲學家1拿起了左右叉子，然后進食并放下兩把叉子，之后哲學家5拿起了叉子。
四、解決方案的問題：死鎖
雖然上述解決方案看起來是正確的，但存在死鎖問題。
死鎖是指系統中的每個進程都在等待獲取其他進程持有的資源，從而導致系統進展停滯的情況。
我們可以通過多次運行上述代碼并檢查有時代碼是否掛起來確認這一點。以下是一個示例輸出，展示了上述問題：
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在這種情況下，每個哲學家都拿到了他左邊的叉子，但無法拿到右邊的叉子，因為他的鄰居已經拿到了。這種情況通常稱為循環等待，是導致死鎖并阻止系統進展的條件之一。
五、解決死鎖
如上文所述，死鎖的主要原因是循環等待條件，即每個進程都在等待其他進程持有的資源。因此，為了避免死鎖情況，我們需要確保打破循環等待條件。有幾種方法可以實現這一點，最簡單的方法如下：
除了一個哲學家先拿右邊的叉子外，所有哲學家都先拿左邊的叉子。
我們通過在現有代碼中進行相對較小的更改來實現這一點：
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) {
// 最后一個哲學家先拿起右邊的叉子
philosophers[i] = new Philosopher(rightFork, leftFork);
} else {
philosophers[i] = new Philosopher(leftFork, rightFork);
}
Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1));
t.start();
}
}
}我們引入了一個條件，使最后一個哲學家先拿起右邊的叉子，而不是左邊的。這打破了循環等待條件，我們可以避免死鎖。
以下輸出顯示了所有哲學家都有機會思考和進食而不導致死鎖的一種情況：
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通過多次運行代碼可以驗證，系統不再出現之前的死鎖情況。
文末總結
在本文中，我們探討了著名的哲學家就餐問題以及循環等待和死鎖的概念。我們編寫了一個導致死鎖的簡單解決方案，并進行了簡單的更改以打破循環等待并避免死鎖。這只是一個開始，實際上還有更復雜的解決方案。
