LeetCode Concurrency Go 語言詳解：Print Zero Even Odd | LKY 只有原創內容的 Blog

前言：由於 LeetCode Concurrency(併發) 還沒有 Go 語言版本，我先自行用 Go 語言來解題。為了能在 LeetCode 以外的平台獲得討論，所以我打算逐漸把自己的解題思路寫下。這是我寫的第三題 LeetCode Concurrency Go 語言詳解，技術比前面兩題都要複雜。為了解釋到我自認夠清楚，寫的時間多花了好幾倍（1x = 2hr）。

本題 LeetCode 連結：

https://leetcode.com/problems/print-zero-even-odd/

本題題目

The same instance of ZeroEvenOdd will be passed to three different threads:

同一個 instance ZeroEvenOdd 會被傳到三個 thread 裡面:

Thread A will call zero() which should only output 0’s.
Thread B will call even() which should only ouput even numbers.
Thread C will call odd() which should only output odd numbers.

Thread A 將會呼叫 zero() 並且只會輸出 0
Thread B 將會呼叫 even() 並且只會輸出偶數
Thread C 將會呼叫 odd() 並且只會輸出奇數

Each of the threads is given a printNumber method to output an integer. Modify the given program to output the series 010203040506… where the length of the series must be 2n.

每一個 thread 都會被傳入一個 printNumber() 以輸出一個整數。
修改已給的程式碼，使其輸出序列為 010203040506…，該序列長度必須為 2n。

本題考核難點？

在一個未知長度的序列中，依照「0-奇數-0-偶數」的順序將數字印出，且一種元素只能由一個執行緒印出，代表各個執行緒之間要依照這個數列的規則溝通。

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

與前面幾題不同的是，這一題最後工作的 thread 具有不確定性，視數列最後一個元素為奇數或偶數來決定，這點小小的提高了難度。

解法與思路：

1. 所用 Channel 型態與定位？

本題採用五個 unbuffered channel，並且是 ZeroEvenOdd 的成員變數。

type ZeroEvenOdd struct {
	n                int
	streamEvenToZero chan struct{}
	streamOddToZero  chan struct{}
	streamZeroToEven chan struct{}
	streamZeroToOdd  chan struct{}
	streamZeroToEnd  chan struct{}
}

var zeo = &ZeroEvenOdd{
	n:                testNum,
	streamEvenToZero: make(chan struct{}),
	streamOddToZero:  make(chan struct{}),
	streamZeroToEven: make(chan struct{}),
	streamZeroToOdd:  make(chan struct{}),
	streamZeroToEnd:  make(chan struct{}),
}

定位分別是:

• streamEvenToZero: Even() 交棒給 Zero()
• streamOddToZero: Odd() 交棒給 Zero()
• streamZeroToEven: Zero() 交棒給 Even()
• streamZeroToOdd: Zero() 交棒給 Odd()
• streamZeroToEnd: Zero() 交棒給啟動它的 goroutine

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

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

以前的文章說過，由於本題解法採用各個 goroutine 彼此循環交棒的方式，因此不能自行啟動，需要外界給訊號，所以在包住一整題的 PrintZeroEvenOdd() 執行各個 goroutine 同時以 zeo.streamEvenToZero <- struct{}{} 作為起頭的火種 ，讓 main() 假裝自己是 Even() 交棒給 Zero()，以啟動交接棒循環。具體程式碼如下：

go func() { zeo.streamEvenToZero <- struct{}{} }() //給起頭的火種
go zeo.Zero(PrintNumber)
go zeo.Even(PrintNumber)
go zeo.Odd(PrintNumber)

要特別注意的是，這個「啟動火種」也要寫成 goroutine，否則會由於執行當下尚未等到消費者「出世」，發生 deadlock！

另外一種不用 goroutine 啟動的做法，也可以讓消費者先「出世」，在 goroutine 的阻塞中等待時，再給「啟動火種」。具體程式碼如下：

go zeo.Zero(PrintNumber)
go zeo.Even(PrintNumber)
go zeo.Odd(PrintNumber)
func() { zeo.streamEvenToZero <- struct{}{} }() //給起頭的火種

交接棒流程：Zero() 視角

中心化：由 Zero() 做控管中心，遍歷 0 to n 每一個數字，印完自己責任該印的 “0” 以後，根據數字性質決定要把棒子交給 Even() 或 Odd()。此處會用到 select-case-default。具體程式碼如下：

func (this *ZeroEvenOdd) Zero(printNumber func(int)) {
	for i := 0; i < this.n; i++ {
		select {
		case <-this.streamOddToZero:
			printNumber(0)
			this.streamZeroToEven <- struct{}{}
		case <-this.streamEvenToZero:
			printNumber(0)
			this.streamZeroToOdd <- struct{}{}
		default:
			runtime.Gosched()
			//<-time.After(time.Microsecond)
			i--
		}
	}

	if 0 == this.n%2 {
		<-this.streamEvenToZero //等待 Even() 結束，自己再結束
	} else {
		<-this.streamOddToZero //等待 Odd() 結束，自己再結束
	}
}

雖然順序都是固定的，但在此先假裝 Zero() 並不知道誰會交棒給自己？所以 Zero() 交棒（send to chan）以後，就會在 for-select 裡無窮迴圈，每一次 select{} 都會隨機選擇一個 case 或 default，也就是以亂槍打鳥的方式 polling 是誰交棒給自己？

謎之聲：「難道有不是中心化的流程嗎？」，有喔！我解決「DiningPhilosophers」這一題用的就是去中心化方法，但目前還沒寫那一題詳解。

交接棒流程：Even() & Odd() 視角

對於 Even() 與 Odd() 來說，流程很固定，只有 Zero() 會交棒給自己，印完數字後，也只需要交棒給同樣的 Zero() ，一種「哪裡來，就哪裡去」的概念。

唯一比較複雜的部分，就是數字「遞增」與「終點」的控制：

• 「遞增」每一次都是 += 2，不必解釋。
• 「終點」一開始就算好題目下的奇數上限、偶數上限，算法看程式碼也很清楚了，不解釋。超過終點就直接結束。

具體程式碼如下（太相似，故此處只放 Even() 舉例）：

func (this *ZeroEvenOdd) Even(printNumber func(int)) {
	evenUpper := this.n - this.n%2
	// fmt.Println("evenUpper:", evenUpper)
	for i := 2; i <= evenUpper; {
		<-this.streamZeroToEven
		printNumber(i)
		i += 2
		this.streamEvenToZero <- struct{}{}
	}
}

收尾之一：為什麼要 Zero() 善後？

由於題目的關係，Even() 或 Odd() 其中一個，都有可能是最後印出字元的 goroutine，若讓這兩者去收尾，流程上的不確定性比較大。因此，幾經考慮後，還是決定讓 Zero() 去收尾。

讓 Zero() 去收尾的套路，之前的詳解也寫過，就是先 return 的 goroutine 最後都要 send to chan 到負責收尾的 goroutine，收尾 goroutine 在最後一一將這些 chan 都 receive 掉。

但由於本題特性，可由題目給定數字的奇偶判斷，Zero() 會從哪個 channnel 收到收尾訊號？因此在 Zero() 最後段的 receive，是以奇偶數判斷要在何處等待。具體的局部程式碼如下：

if 0 == this.n%2 {
	<-this.streamEvenToZero //等待 Even() 結束，自己再結束
} else {
	<-this.streamOddToZero //等待 Odd() 結束，自己再結束
}

收尾之二：代替 sync.WaitGroup.Wait() 的「chan receive 阻塞法」

主程式為了等待 goroutine 都結束才往下的同步情況，往往會用 sync.WaitGroup.Wait()。
根據本文前面所介紹，我已經將流程結束的不確定性減少，使得一定會由 Zero() 負責收尾，因此只要在主程式阻塞一個 chan receive，由 Zero() 結束前 send 一下，便可以將主程式打通，繼續往下。

具體的局部程式碼如下：

goroutine Zero() 結束前 send 一下，交棒出去。

func (this *ZeroEvenOdd) Zero(printNumber func(int)) {
	//.....略過多行
	this.streamZeroToEnd <- struct{}{}
}

在主程式啟動完其他 goroutine 之後，阻塞一個 chan receive，等待被 Zero() 打通，繼續往下。

go zeo.Zero(PrintNumber)
go zeo.Even(PrintNumber)
go zeo.Odd(PrintNumber)
<-zeo.streamZeroToEnd //等待 Zero() 送出結束訊號

完整解題程式碼：

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

示意圖：