哲學(xué)家進(jìn)餐

5個(gè)沉默寡言的哲學(xué)家圍坐在圓桌前，每人面前一盤意面。叉子放在哲學(xué)家之間的桌面上。（5 個(gè)哲學(xué)家，5 根叉子）

所有的哲學(xué)家都只會(huì)在思考和進(jìn)餐兩種行為間交替。哲學(xué)家只有同時(shí)拿到左邊和右邊的叉子才能吃到面，而同一根叉子在同一時(shí)間只能被一個(gè)哲學(xué)家使用。每個(gè)哲學(xué)家吃完面后都需要把叉子放回桌面以供其他哲學(xué)家吃面。只要條件允許，哲學(xué)家可以拿起左邊或者右邊的叉子，但在沒有同時(shí)拿到左右叉子時(shí)不能進(jìn)食。

假設(shè)面的數(shù)量沒有限制，哲學(xué)家也能隨便吃，不需要考慮吃不吃得下。

設(shè)計(jì)一個(gè)進(jìn)餐規(guī)則（并行算法）使得每個(gè)哲學(xué)家都不會(huì)挨餓；也就是說，在沒有人知道別人什么時(shí)候想吃東西或思考的情況下，每個(gè)哲學(xué)家都可以在吃飯和思考之間一直交替下去。

哲學(xué)家從 0 到 4 按順時(shí)針編號(hào)。

請(qǐng)實(shí)現(xiàn)函數(shù) wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：

• philosopher 哲學(xué)家的編號(hào)。

• pickLeftFork 和 pickRightFork 表示拿起左邊或右邊的叉子。

• eat 表示吃面。

• putLeftFork 和 putRightFork 表示放下左邊或右邊的叉子。

• 由于哲學(xué)家不是在吃面就是在想著啥時(shí)候吃面，所以思考這個(gè)方法沒有對(duì)應(yīng)的回調(diào)。

給你 5個(gè)線程，每個(gè)都代表一個(gè)哲學(xué)家，請(qǐng)你使用類的同一個(gè)對(duì)象來(lái)模擬這個(gè)過程。在最后一次調(diào)用結(jié)束之前，可能會(huì)為同一個(gè)哲學(xué)家多次調(diào)用該函數(shù)。

示例

輸入：n = 1

輸出：

[[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]

解釋:

• n 表示每個(gè)哲學(xué)家需要進(jìn)餐的次數(shù)。

• 輸出數(shù)組描述了叉子的控制和進(jìn)餐的調(diào)用，它的格式如下：output[i] = [a, b, c] (3個(gè)整數(shù))

• a 哲學(xué)家編號(hào)。

• b 指定叉子：{1 : 左邊, 2 : 右邊}.

• c 指定行為：{1 : 拿起, 2 : 放下, 3 : 吃面}。

• 如 [4,2,1] 表示 4 號(hào)哲學(xué)家拿起了右邊的叉子。

解題思路

這道題本質(zhì)上其實(shí)是想考察如何避免死鎖。

易知：當(dāng) 5個(gè)哲學(xué)家都拿著其左邊(或右邊)的叉子時(shí)，會(huì)進(jìn)入死鎖。

死鎖的4個(gè)必要條件

• 互斥條件：一個(gè)資源每次只能被一個(gè)進(jìn)程使用，即在一段時(shí)間內(nèi)某資源僅為一個(gè)進(jìn)程所占有。此時(shí)若有其他進(jìn)程請(qǐng)求該資源，則請(qǐng)求進(jìn)程只能等待。

• 請(qǐng)求與保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源已被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程被阻塞，但對(duì)自己已獲得的資源保持不放。

• 不可剝奪條件：進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行奪走，即只能由獲得該資源的進(jìn)程自己來(lái)釋放（只能是主動(dòng)釋放)。

• 循環(huán)等待條件：若干進(jìn)程間形成首尾相接循環(huán)等待資源的關(guān)系。

4個(gè)哲學(xué)家持有叉子？

故最多只允許 4 個(gè)哲學(xué)家去持有叉子，可保證至少有 1個(gè)哲學(xué)家能吃上意大利面（即獲得到 2 個(gè)叉子）。

因?yàn)?strong>最差情況下是：4 個(gè)哲學(xué)家都各自持有1個(gè)叉子，此時(shí)還剩余 1個(gè)叉子可供使用，這 4個(gè)哲學(xué)家中必然有1人能獲取到這個(gè)剩余的 1 個(gè)叉子，從而手持 2個(gè)叉子，可以吃意大利面。

即：4 個(gè)人中，1 個(gè)人有 2 個(gè)叉子，3 個(gè)人各持 1 個(gè)叉子，共計(jì) 5 個(gè)叉子。

3個(gè)哲學(xué)家持有叉子？

既然最多只允許4個(gè)哲學(xué)家去持有叉子，那么如果只允許 3 個(gè)哲學(xué)家去持有叉子是否可行呢？

當(dāng)然可行，3個(gè)哲學(xué)家可以先都各自持有 1 把叉子，此時(shí)還剩余 2 把叉子；

當(dāng)這 3 個(gè)哲學(xué)家剛好都相鄰(比如：編號(hào)為圖中的 0, 1, 2 )，可能會(huì)造成只有 1 個(gè)哲學(xué)家能吃到意面的情況，具體而言即 0號(hào)哲學(xué)家拿到了其左側(cè)的叉子(編號(hào)為 1 )， 1號(hào)哲學(xué)家也拿到了其左側(cè)的叉子(編號(hào)為 2 )，2 號(hào)哲學(xué)家也拿到了其左側(cè)的叉子(編號(hào)為 3 )，此時(shí)只有 0號(hào)哲學(xué)家能拿到其右側(cè)的叉子(編號(hào)為 0 )，因此只有 0 號(hào)哲學(xué)家能吃到意面。

而其余情況下，3個(gè)哲學(xué)家中都能有 2人吃到意面。

即：3 個(gè)人中，2 個(gè)人各自持有 2 個(gè)叉子，1 個(gè)人持有 1 個(gè)叉子，共計(jì) 5 個(gè)叉子。

并且仔細(xì)想想，叉子的數(shù)目是固定的(個(gè)數(shù)為 5 )，直覺上來(lái)講 3 個(gè)人去搶 5 個(gè)叉子比 4 個(gè)人去搶 5 個(gè)叉子效率高。

方法一：信號(hào)量

用Semaphore去實(shí)現(xiàn)上述的限制：Semaphore eatLimit = new Semaphore(4);

一共有5個(gè)叉子，視為5個(gè)ReentrantLock，并將它們?nèi)湃?個(gè)數(shù)組中。

給叉子編號(hào) 0, 1, 2, 3, 40,1,2,3,4（對(duì)應(yīng)數(shù)組下標(biāo)）。

代碼具體實(shí)現(xiàn)：

改進(jìn):

位運(yùn)算就可以表示5個(gè)叉子的使用狀態(tài)，只需用1個(gè)volatile修飾的int變量即可 + CAS操作即可，即AtomicInteger類。

代碼具體實(shí)現(xiàn)：

方法二：只允許1個(gè)哲學(xué)家就餐

設(shè)置 1 個(gè)臨界區(qū)以實(shí)現(xiàn) 1 個(gè)哲學(xué)家 “同時(shí)”拿起左右 2 把叉子的效果。

即進(jìn)入臨界區(qū)之后，保證成功獲取到左右 2 把叉子并執(zhí)行相關(guān)代碼后，才退出臨界區(qū)。

方法2有一定的概率是“并行”，“只允許1個(gè)哲學(xué)家就餐”是嚴(yán)格的“串行”。

代碼如下：

改進(jìn):

位運(yùn)算就可以表示5個(gè)叉子的使用狀態(tài)，只需用1個(gè)volatile修飾的int變量即可 + CAS操作即可，即AtomicInteger類。

方法一和方法二的區(qū)別

2 者之間有細(xì)微的差別：

方法 2 是在成功拿起左右叉子之后就退出臨界區(qū)，而“只讓 1 個(gè)哲學(xué)家就餐”是在拿起左右叉子 + 吃意面 + 放下左右叉子一套流程走完之后才退出臨界區(qū)。

前者的情況可大概分為 2 種，舉具體例子說明(可參照上面給出的圖片)：

• 1 號(hào)哲學(xué)家拿起左右叉子( 1 號(hào)叉子 + 2 號(hào)叉子)后就退出臨界區(qū)，此時(shí) 4 號(hào)哲學(xué)家成功擠進(jìn)臨界區(qū)，他也成功拿起了左右叉子( 0 號(hào)叉子和 4 號(hào)叉子)，然后就退出臨界區(qū)。

• 1 號(hào)哲學(xué)家拿起左右叉子( 1 號(hào)叉子 + 2 號(hào)叉子)后就退出臨界區(qū)，此時(shí) 2 號(hào)哲學(xué)家成功擠進(jìn)臨界區(qū)，他需要拿起 2 號(hào)叉子和 3 號(hào)叉子，但 2 號(hào)叉子有一定的概率還被 1 號(hào)哲學(xué)家持有( 1 號(hào)哲學(xué)家意面還沒吃完)，因此 2 號(hào)哲學(xué)家進(jìn)入臨界區(qū)后還需要等待 2 號(hào)叉子。至于 3 號(hào)叉子，根本沒其他人跟 2 號(hào)哲學(xué)家爭(zhēng)奪，因此可以將該種情況視為“ 2 號(hào)哲學(xué)家只拿起了 1 只叉子，在等待另 1 只叉子”的情況。

總之，第1種情況即先后進(jìn)入臨界區(qū)的 2 位哲學(xué)家的左右叉子不存在競(jìng)爭(zhēng)情況，因此先后進(jìn)入臨界區(qū)的 2 位哲學(xué)家進(jìn)入臨界區(qū)后都不用等待叉子，直接就餐。此時(shí)可視為 2 個(gè)哲學(xué)家在同時(shí)就餐(當(dāng)然前 1 個(gè)哲學(xué)家有可能已經(jīng)吃完了，但姑且當(dāng)作是 2 個(gè)人同時(shí)就餐)。

第 2 種情況即先后進(jìn)入臨界區(qū)的 2 位哲學(xué)家的左右叉子存在競(jìng)爭(zhēng)情況(說明這 2 位哲學(xué)家的編號(hào)相鄰)，因此后進(jìn)入臨界區(qū)的哲學(xué)家還需要等待 1 只叉子，才能就餐。此時(shí)可視為只有 1 個(gè)哲學(xué)家在就餐。

至于“只允許 1 個(gè)哲學(xué)家就餐”的代碼，很好理解，每次嚴(yán)格地只讓 1 個(gè)哲學(xué)家就餐，由于過于嚴(yán)格，以至于都不需要將叉子視為ReentrantLock。

方法三

前面說過，該題的本質(zhì)是考察如何避免死鎖。

而當(dāng) 5 個(gè)哲學(xué)家都左手持有其左邊的叉子或當(dāng) 5 個(gè)哲學(xué)家都右手持有其右邊的叉子時(shí)，會(huì)發(fā)生死鎖。

故只需設(shè)計(jì)1個(gè)避免發(fā)生上述情況發(fā)生的策略即可。

即可以讓一部分哲學(xué)家優(yōu)先去獲取其左邊的叉子，再去獲取其右邊的叉子；再讓剩余哲學(xué)家優(yōu)先去獲取其右邊的叉子，再去獲取其左邊的叉子。

代碼如下：

改進(jìn):

位運(yùn)算就可以表示5個(gè)叉子的使用狀態(tài)，只需用1個(gè)volatile修飾的int變量即可 + CAS操作即可，即AtomicInteger類。

寫在最后

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。