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