LeetCode Concurrency Go 語言詳解：經典哲學家吃飯問題：碰運氣解法 | LKY 只有原創內容的 Blog

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

本題 LeetCode 連結：

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

本題題目

「哲學家吃飯問題」是一個作業系統中的經典問題，所以抽象題幹我就不再贅述，直接說實作要求。

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:

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

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

參數 philosopher 代表想要吃飯的哲學家的 ID。

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

參數 pickLeftFork and pickRightFork 是函數，你必須呼叫他們來使哲學家拿起對應的叉子。

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

當哲學家拿起兩隻叉子後，你必須呼叫 eat 這個函數讓哲學家吃一次。

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

參數 putLeftFork and pickRightFork 是函式，你必須呼叫他們來使哲學家放下手中的叉子。

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).

假設哲學家們都會思考很久，中間都不會要求吃東西（呼叫函式 thinking() 不必使用哲學家們的 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.

五個執行緒，每一個執行緒代表都一個哲學家，用一個類(在 Go 語言是 struct)模擬這個 process。這個函式可能被同一個哲學家呼叫多次，甚至在最後一次呼叫結束前的途中都有可能。

「叉子」與「筷子」

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

本題考核難點？「拿得起放不下」造成死結、「無限輪迴」造成活結飢餓至死

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

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

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

這邊我為了示範 goroutine，先用最笨的碰運氣解法，也就是不刻意做任何資源配置，要在運氣很壞的情況下才會遇上 livelock。什麼是「運氣很壞的情況」？就是所有哲學家剛好在同一時間拿起同一邊的叉子。但實作上，由於我給每位哲學家一個隨機的思考時間 50mS（如下列程式碼），碰撞的機會是(1/50)^5，所以絕大部分情況下不會發生 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 上有介紹不需要碰運氣，保證不會讓 thread 飢餓致死的演算法，但我自己也沒搞懂，請容我日後再介紹。

解法與思路：

1. 所用 Channel 型態與定位？

本題採用 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)
}

初始化

// 叫所有哲學家開始動作
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 個哲學家 goroutine 結束時間。
給每一位哲學家起一個「WantToEat」的 goroutine，告訴他 i 你是幾號？又給入「PickLeftFork, PickRightFork, Eat, PutLeftFork, PutRightFork」五個函式的的 function reference。

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

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

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

自循環 & 外部啟動注意事項

這次解題沒有實作這些協調機制，5 個 goroutine 只靠前述的三條規範野蠻生長。

實作前述的三條規範的 WantToEat()

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

有一行「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  //取得該哲學家左邊的號碼
	var rightNum = (philosopher + 6) % 5 //取得該哲學家右邊的號碼

	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] //把已經拿起來的左邊筷子釋放出去
				PutLeftFork(philosopher)
			}
		default: //無法拿起左邊筷子
			fmt.Printf("Philosopher %d can't pick fork %d.\n", philosopher, leftNum)
		}
		this.missingDoubleForkTimes++
		Think()
	}
}

這邊對於每一隻筷子的具體表現就是一個 buffered channel，迴圈流程如下：

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

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

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

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

在 console 輸出，可以看到代表每一位哲學家的 goroutine 詳細動作過程，錯過筷子次數並不多，大部分執行結果的錯過次數在 3~5 次（點擊以下的「完整解題程式碼」就能體驗）。

完整解題程式碼：

https://play.golang.org/p/neTH25E8ayX

示意圖：