LKY 只有原創內容的 Blog

今之能者,謂能轉貼,至於魯蛇,皆能轉貼。不原創,何以別乎?

LeetCode Concurrency Go 語言詳解:Print FooBar Alternately

Lin, Kao-Yuan's Avatar 2020-01-16

  1. 1. 本題 LeetCode 連結:
  2. 2. 本題考核點?
  3. 3. 解法與思路:
    1. 3.1. 1. 所用 Channel 型態與定位?
    2. 3.2. 2. Foo() 與 Bar() 如何交接棒?
    3. 3.3. 3. Foo() 與 Bar() 如何收尾?
    4. 3.4. 4. 自循環啟動
    5. 3.5. 5. 特別條件下,用 unbuffered channel 取代 sync.WaitGroup
  4. 4. 完整解題程式碼:
  5. 5. 示意圖:

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

本題 LeetCode 連結:

https://leetcode.com/problems/print-foobar-alternately/

本題考核點?

指定次數交替執行 printFoo()printBar()。若任由兩個 goroutine 分別各自 print,不能保證其結果一定會互相交錯。

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

解法與思路:

1. 所用 Channel 型態與定位?

本題採用三個 unbuffered channel

1
2
3
4
5
6
type FooBar struct {
n int
streamFooToBar chan struct{}
streamBarToFoo chan struct{}
streamEnd chan struct{}
}

分別是:

  • streamFooToBar: Foo() 交棒給 Bar()
  • streamBarToFoo: Bar() 交棒給 Foo()
  • streamEnd: 結束訊號

2. Foo()Bar() 如何交接棒?

1
2
3
4
5
6
7
8
9
10
11
12
func (this *FooBar) Foo(printFoo func()) {

for i := 0; i < this.n; {
// printFoo() outputs "foo". Do not change or remove this line.
<-this.streamBarToFoo
printFoo()
i++
this.streamFooToBar <- struct{}{}
}

<-this.streamBarToFoo //等待 Bar() 印完最後一次
}
  • 根據設定次數 n 重複執行
  • 每一輪都要得到 Bar() 交出棒,才會執行 printFoo() 以印出字串
  • 印出字串後,以 this.streamFooToBar <- struct{}{} 交棒給 Bar()

下方的 Bar() 也是一樣的道理。

1
2
3
4
5
6
7
8
9
10
11
12
func (this *FooBar) Bar(printBar func()) {

for i := 0; i < this.n; {
// printBar() outputs "bar". Do not change or remove this line.
<-this.streamFooToBar
printBar()
i++
this.streamBarToFoo <- struct{}{}
}

this.streamEnd <- struct{}{}
}

3. Foo()Bar() 如何收尾?

這裡要特別注意的是,Foo()Bar() 只有差異在最後一行,用意是什麼?

多個 goroutine 用 unbuffered channel 互相交接棒,會有一個尷尬的情況,就是互為消費者、又互為生產者,因此先 return 的 goroutine 沒事,但是後 return 的 goroutine 會由於消費者消失,send to channel 的時候發生 Deadlock。

根據本題遊戲規則, printBar() 一定要比 printFoo() 晚執行,因此不做特別處理的話,會在 Bar() 試圖做最後一次交棒時,由於消費者消失發生 Deadlock。

我的應對方式,就是讓 Foo() return 前做一次無特別作用的接棒,這樣就可以避免 Bar() return 前找不到消費者的問題。

4. 自循環啟動

1
fooBar.streamBarToFoo <- struct{}{} //啟動

前面說過,本題解法採用 Foo()Bar() 彼此循環交棒的方式,因此不能自行啟動,需要外界給訊號,所以在 main() 執行各個 goroutine 以後以 fooBar.streamBarToFoo <- struct{}{} ,讓 main() 假裝自己是 Bar() 交棒給 Foo(),以啟動交接棒循環。

5. 特別條件下,用 unbuffered channel 取代 sync.WaitGroup

1
<-fooBar.streamEnd                  //as wg.Wait()

為了等待多個 goroutine 都結束再往下,一般來說用 sync.WaitGroup.Wait() 是標準做法。但這一題還有更輕量的方法。

雖然這一題是 Concurrency,但是各個 goroutine 的結束順序已經被定死,我們很清楚知道誰負責收尾,所以讓負責收尾的 goroutine send to unbuffered channel,然後在 main() read 掉,這樣就不需要使用 sync.WaitGroup

執行各個 goroutine 以後,main() 會由於 <-fooBar.streamEnd 還沒有被傳入而被卡住,這就相當於 sync.WaitGroup.Wait() 的作用了。

由於是 Bar() 會做最後一次有意義的執行,因此讓 Bar() return 之前執行 this.streamEnd <- struct{}{},這就相當於交棒給 main()main() 終於可以從被卡住的 <-fooBar.streamEnd 往下(因為終於有東西可以讀),就像便秘了三天突然暢通一樣!

完整解題程式碼:

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

示意圖:

This article was last updated on days ago, and the information described in the article may have changed.