面試官：這個經(jīng)典的并發(fā)問題用 Go 語言如何實(shí)現(xiàn)？

前言：由于 LeetCode Concurrency(并發(fā)) 還沒有 Go 語言版本，我先自行用 Go 語言來解題。為了能在 LeetCode 以外的平臺獲得討論，所以我打算逐漸把自己的解題思路寫下。

本題 LeetCode 鏈接

https://leetcode.com/problems/the-dining-philosophers/

本題題目

「哲學(xué)家吃飯問題」是一個操作系統(tǒng)中的經(jīng)典問題，所以抽象題干我就不再贅述，直接說實(shí)作要求。

The philosophers' ids are numbered from 0 to 4 in a clockwise order. Implement the function void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) where:

有幾位哲學(xué)家，他們的 ID 順時針由 0~4，實(shí)作一個函式 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)，其中...

philosopher is the id of the philosopher who wants to eat.

變量 philosopher 代表想要吃飯的哲學(xué)家的 ID。

pickLeftFork and pickRightFork are functions you can call to pick the corresponding forks of that philosopher.

變量 pickLeftFork and pickRightFork 是函式，你必須調(diào)用他們來使哲學(xué)家拿起對應(yīng)的叉子。

eat is a function you can call to let the philosopher eat once he has picked both forks.

當(dāng)哲學(xué)家拿起兩只叉子后，你必須調(diào)用?eat 這個函式讓哲學(xué)家吃一次。

putLeftFork and pickRightFork are functions you can call to put down the corresponding forks of that philosopher.

變量 putLeftFork and pickRightFork 是函式，你必須調(diào)用他們來使哲學(xué)家放下手中的叉子。

The philosophers are assumed to be thinking as long as they are not asking to eat (the function is not being called with their number).

假設(shè)哲學(xué)家們都會思考很久，中間都不會要求吃東西（調(diào)用函式 thinking() 不必使用哲學(xué)家們的 ID）

Five threads, each representing a philosopher, will simultaneously use one object of your class to simulate the process. It is possible that the function will be called for the same philosopher more than once, even before the last call ends.

五個執(zhí)行緒，每一個執(zhí)行緒代表都一個哲學(xué)家，用一個類(在 Go 語言是 struct)模擬這個 process。這個函式可能被同一個哲學(xué)家調(diào)用多次，甚至在最后一次調(diào)用結(jié)束前的途中都有可能。

「叉子」與「筷子」

最早課本里都是說「叉子」。但我大學(xué)上 OS 的時候老師就提過一個疑問：「用叉子吃義大利面，一只就夠了，沒必要用到兩只吧？所以，改成用筷子是不是更合理一點(diǎn)？但沒辦法，誰叫這門學(xué)問是西方先發(fā)明的？我們就當(dāng)作筷子吧」。
于是，本文也決定照改，以下都用「筷子」代替「叉子」。

本題考核難點(diǎn)？「拿得起放不下」造成死結(jié)、「無限輪回」造成活結(jié)饑餓至死

在過去的 LeetCode Concurrency 詳解中，我提到過很多次：

goroutine 若不刻意控制，將無法保證執(zhí)行的先后順序，因此本題就是要考核對 goroutine 順序控制的能力。

但前面幾題的解法，大多是把判斷責(zé)任中心化，方便控管順序。這次，與前面幾題不同的是，這一題要求把判斷責(zé)任分散到每一位哲學(xué)家 thread 身上，哲學(xué)家彼此之間并不溝通，因此很容易發(fā)生資源互卡，也就是 deadlock。本文所示范的 channel 使用方法已經(jīng)完全避免了死結(jié)(deadlock)。但這樣就沒問題了嗎？不，還有可能發(fā)生活結(jié)(livelock)。

這邊我為了示范 goroutine，先用最笨的碰運(yùn)氣解法，也就是不刻意做任何資源配置，要在運(yùn)氣很壞的情況下才會遇上 livelock。什么是「運(yùn)氣很壞的情況」？

就是所有哲學(xué)家剛好在同一時間拿起同一邊的叉子。但實(shí)際上，由于我給每位哲學(xué)家一個隨機(jī)的思考時間 50mS（如下列代碼），碰撞的機(jī)會是(1/50)^5，所以絕大部分情況下不會發(fā)生 livelock。

func?Think()?{
?Random?:=?func(max?int)?int?{
??rand.Seed(time.Now().Unix())
??return?rand.Int()?%?(max?+?1)
?}
?<-time.After(time.Millisecond?*?time.Duration(Random(50)))
}

Wiki 上有介紹不需要碰運(yùn)氣，保證不會讓 thread 饑餓致死的演算法，但我自己也沒搞懂，請容我日后再介紹。

解法與思路：

1. 所用 Channel 型態(tài)與定位？

本題采用 5 個 buffered channel，分別代表 5 支筷子

type?DiningPhilosophers?struct?{
?wg?????????????????????*sync.WaitGroup
?streamForks????????????[5]chan?interface{}
?missingDoubleForkTimes?int
}

//?Channel?初始化
for?i?:=?range?diningPhilosophers.streamForks?{
?diningPhilosophers.streamForks[i]?=?make(chan?interface{},?1)
}

初始化

//?叫所有哲學(xué)家開始動作
start?:=?time.Now()
for?i?:=?range?diningPhilosophers.streamForks?{
?diningPhilosophers.wg.Add(1)
?go?diningPhilosophers.WantToEat(i,?PickLeftFork,?PickRightFork,?Eat,?PutLeftFork,?PutRightFork)
}

這邊開始計時后，是一個 foreach。

老方法，用 sync.WaitGroup 同步 5 個哲學(xué)家 goroutine 結(jié)束時間。
給每一位哲學(xué)家起一個「WantToEat」的 goroutine，告訴他 i 你是幾號？又給入「PickLeftFork, PickRightFork, Eat, PutLeftFork, PutRightFork」五個函式的的 function reference。

2. 五個 goroutine 之間，如何交接棒？

沒有交接棒問題，每位哲學(xué)家就憑運(yùn)氣去搶左右邊的兩只筷子。
要注意的只有三件事情：

1. 無法同時搶到兩只筷子的哲學(xué)家，必須先放棄到手的一支筷子。
2. 已經(jīng)同時搶到兩只筷子的哲學(xué)家，吃完就必須退出餐桌。
3. 還沒吃到的哲學(xué)家，可以無限次搶。

自循環(huán) & 外部啟動注意事項

這次解題沒有實(shí)作這些協(xié)調(diào)機(jī)制，5 個 goroutine 只靠前述的三條規(guī)范野蠻生長。

實(shí)作前述的三條規(guī)范的 WantToEat()

• 本質(zhì)上就是代表「還沒吃到的哲學(xué)家，可以無限次搶」的無限回圈。
• 「已經(jīng)同時搶到兩只筷子的哲學(xué)家，吃完就必須退出餐桌」是此回圈的結(jié)束條件。
• 「無法同時搶到兩只筷子的哲學(xué)家，必須先放棄到手的一支筷子。」是此回圈其中一個分支。

有一行「return //吃飽離開」，整個流程最終目的就是要走到這一行。

func?(this?*DiningPhilosophers)?WantToEat(philosopher?int,?pickLeftFork?func(int),?pickRightFork?func(int),?eat?func(int),?putLeftFork?func(int),?putRightFork?func(int))?{
?defer?this.wg.Done()

?var?leftNum?=?(philosopher?+?4)?%?5??//取得該哲學(xué)家左邊的號碼
?var?rightNum?=?(philosopher?+?6)?%?5?//取得該哲學(xué)家右邊的號碼

?for?{
??select?{
??case?this.streamForks[leftNum]?<-?philosopher:?//嘗試拿起左邊筷子
???PickLeftFork(philosopher)?//成功拿起左邊筷子
???select?{
???case?this.streamForks[rightNum]?<-?philosopher:?//嘗試拿起右邊筷子
????PickRightFork(philosopher)??//成功拿起又邊筷子
????Eat(philosopher)????????????//左右邊都拿到了，開始吃
????<-this.streamForks[leftNum]?//吃完了，放下左邊筷子
????PutLeftFork(philosopher)
????<-this.streamForks[rightNum]?//吃完了，放下右邊筷子
????PutRightFork(philosopher)
????return?//吃飽離開
???default:?//無法拿起右邊筷子
????fmt.Printf("Philosopher?%d?can't?pick?fork?%d.\n",?philosopher,?rightNum)
????<-this.streamForks[leftNum]?//把已經(jīng)拿起來的左邊筷子釋放出去
????PutLeftFork(philosopher)
???}
??default:?//無法拿起左邊筷子
???fmt.Printf("Philosopher?%d?can't?pick?fork?%d.\n",?philosopher,?leftNum)
??}
??this.missingDoubleForkTimes++
??Think()
?}
}

這邊對于每一只筷子的具體表現(xiàn)就是一個 buffered channel，回圈流程如下：

1. 先嘗試把自己的號碼塞入左邊的 buffered channel

• 成功了，就是搶到一只筷子，往下。
• 失敗了，跳到「default: //無法拿起左邊筷子」，思考一下，然后從頭開始。

2. 再嘗試把自己的號碼塞入右邊的 buffered channel

• 成功了，就是搶到兩只筷子，開始吃，吃飽離開，退出餐桌。
• 失敗了，跳到「default: //無法拿起右邊筷子」，把已經(jīng)搶到的左邊筷子還回去，思考一下，然后從頭開始。

在 console 輸出，可以看到代表每一位哲學(xué)家的 goroutine 詳細(xì)動作過程，錯過筷子次數(shù)并不多，大部分執(zhí)行結(jié)果的錯過次數(shù)在 3~5 次（點(diǎn)擊以下的「完整解題代碼」就能體驗）。

完整解題代碼：

https://play.studygolang.com/p/neTH25E8ayX

示意圖：

最后附上本文作者的求職信息：

「座標(biāo)廣東中山，臺灣師范大學(xué)機(jī)電碩士，三年開發(fā)經(jīng)驗，有Windows應(yīng)用、單片機(jī)、AI/ML/數(shù)據(jù)分析、Go后端相關(guān)經(jīng)驗，懂 Go/C#/C++/Python，Github:mosdeo」

可以通過 wx 聯(lián)系他：LinKaoYuan_WeChatID