Zenn
📑

読書メモ Go言語による並行処理 6.1 ワークスティーリング

2024/03/10に公開
Go
#
thread
tech

読書メモ Go言語による並行処理 6.1 ワークスティーリング

はじめに

元同僚と二人で読書会を実施している。
いまは「Go言語による並行処理」を読んでいる。
先日「6.1 ワークスティーリング」を読んだ。
読んだが内容がよくわからなかったので、自分が理解できるように図示してみた。

フィボナッチ数列を再帰的に計算するプログラムのソースコード

「Go言語による並行処理 6.1 ワークスティーリング」(以下、本書)に登場するコードは以下の通り。
本書には説明がないが、fib()関数はフィボナッチ数列0,1,2,3,5...を計算で求めて、引数で指定した順番の値を返す。
つまり、fib(4)は3を返す。

  var fib func(n int) <-chan int
  fib = func(n int) <-chan int {
    result := make(chan int)
    go func() {
      defer close(result)
      if n <= 2 {
        result <- 1
        return
      }
      result <- <-fib(n-1) + <-fib(n-2)
    }()
    return result
  }
  fmt.Printf("fib(4) = %d", <-fib(4))

スレッドのスケジューリングの話をするときにフィボナッチ数列の計算用コードを例に挙げるのはよくあることみたい。

ゴルーチンのツリー

main()からfib()関数を呼ぶとゴルーチンを起動する。そのゴルーチンの中で2つのfib()関数を呼ぶとそれぞれゴルーチンを起動する。それぞれのゴルーチンの中で2つのfib()関数を呼ぶと．．．を図示すると以下の通り。

ワークスティーリングのアルゴリズムの基本的な規則

本書のワークスティーリングのアルゴリズムの基本的な規則は以下の通り。

  1. 分岐地点では、タスクをそのスレッドに紐付いているデックの最後尾に追加します。
  2. そのスレッドがアイドルなときは、他の任意のスレッドに紐付いたデックの先頭から処理を盗み
    ます。
  3. まだ実現していない合流地点（未達の合流地点、つまり、同期しているゴルーチンがまだ完了し
    ていない）において、そのスレッドが持っているデックの最後尾からタスクを取り出します。
  4. もしスレッドのデックが空ならば次のどちらかを行います。
    a. 合流地点で停止する。
    b. 任意のスレッドに紐付いたデックの先頭からタスクを盗む。

実行時のOSスレッド、コールスタック、ワークデックの様子

本書ではこれに続いて、この規則に従って先のプログラムを実行したときの、

  • OSスレッド
  • コールスタック
  • ゴルーチンをスケジュールするためのワークデック
    の様子を説明する。
    が、この説明がよくわからないので自分で書き起こしてみた。

なお、本書にも記述があるが、OSスレッドは2つに限定する。

1

メインゴルーチンを起動した。

2

fib(4)のゴルーチンを起動しメインゴルーチンと分岐。
規則1により、そのゴルーチンをT1ワークデック最後尾に積む。

3

T1の処理はメインゴルーチン(main())の未達の合流地点````<-fib(4)``で止まっている。
規則3により、T1が持つワークデック最後尾よりゴルーチンを取り出しT1のコールスタックに積む。
T1はゴルーチン「go func()#1 fib(4)」を実行する。
T2はアイドル状態だったため、規則2を実施することができたが、ここでは説明のためT1がゴルーチンを取得したことになっている。

4

T1の処理はゴルーチン「go func()#1 fib(4)」の<-fib(3) + <-fib(2)に差し掛かる。
加算の操作は左から右なので、まず、fib(3)を呼び出し、ゴルーチンを起動する。
規則1により、そのゴルーチンをT1ワークデック最後尾に積む。
次にfib(2)を呼び出し、ゴルーチンを起動する。
規則1により、そのゴルーチンをT1ワークデック最後尾に積む。

5

T2はアイドル状態である。
規則2により、T1のワークデック先頭からゴルーチン「go func()#2 fib(3)」を取得(ワークスティーリング)し、T2のコールスタックに積む。
T2はゴルーチン「go func()#2 fib(3)」を実行する。

6

T1の処理はゴルーチン「go func()#1 fib(4)」の未達の合流地点<-fib(3) + <-fib(2)で止まっている。
規則3により、T1が持つワークデック最後尾よりゴルーチンを取り出しT1のコールスタックに積む。
T1はゴルーチン「go func()#3 fib(2)」を実行する。

7

T2の処理はゴルーチン「go func()#2 fib(3)」の<-fib(2) + <-fib(1)に差し掛かる。
加算の操作は左から右なので、まず、fib(2)を呼び出し、ゴルーチンを起動する。
規則1により、そのゴルーチンをT2ワークデック最後尾に積む。
次にfib(1)を呼び出し、ゴルーチンを起動する。
規則1により、そのゴルーチンをT2ワークデック最後尾に積む。

8

T1の処理はゴルーチン「go func()#3 fib(2)」の

      if n <= 2 {
        result <- 1
        return
      }

に到達し実行を完了する。
fib(2)は1を返す。
その1を持って、T1の処理はゴルーチン「go func()#1 fib(4)」の停止位置の式は<-fib(3) + 1となる。
しかし、まだfib(3)が終わらないため、未達の合流地点として処理が止まる。

9

T2の処理はゴルーチン「go func()#2 fib(3)」の未達の合流地点<-fib(2) + <-fib(1)で止まっている。
規則3により、T2が持つワークデック最後尾よりゴルーチンを取り出しT2のコールスタックに積む。
T2はゴルーチン「go func()#5 fib(1)」を実行する。

10

T1はアイドル状態である。
規則2(規則4b?)により、T2のワークデック先頭からゴルーチン「go func()#4 fib(2)」を取得(ワークスティーリング)し、T1のコールスタックに積む。
T1はゴルーチン「go func()#4 fib(2)」を実行する。

11

T2の処理はゴルーチン「go func()#5 fib(1)」の

      if n <= 2 {
        result <- 1
        return
      }

に到達し実行を完了する。
fib(1)は1を返す。

12

T1の処理はゴルーチン「go func()#4 fib(2)」の

      if n <= 2 {
        result <- 1
        return
      }

に到達し実行を完了する。
fib(2)は1を返す。

13

T2の処理はゴルーチン「go func()#2 fib(3)」の未達の合流地点<-fib(2) + <-fib(1)で止まっている。
fib(2)とfib(1)の結果が出たので合流。
結果を反映すると2になる。
fib(3)は2を返す。

14

T1の処理はゴルーチン「go func()#1 fib(4)」の未達の合流地点<-fib(3) + 1で止まっている。
fib(3)の結果出たので合流。
結果を反映すると3になる。
fib(4)は3を返す。

15

T1の処理はメインゴルーチン(main())の未達の合流地点````<-fib(4)``で止まっている。
fib(4)の結果が出たので合流。
以下を実行しメインゴルーチン終了。

  fmt.Printf("fib(4) = %d", 3)

疑問

10では本書の通り「T1はアイドル状態」と書いた。
アイドル状態なので「規則2により」と書いた。

しかし、T1はアイドル状態なんだろうか？
コールスタックにゴルーチンが残っているので非アイドル状態なのでは？
よって、正しくは「規則4b」を実施したのでは？

アイドル状態の定義を書いて欲しい。

Discussion