goroutineの動き方を調べた

shinjuku.rbで話した内容です。
が、スライドだけだとよくわからないのでもう少し文章を補足した版を上げておきます。

要約

  • goroutineの実態はスレッド
  • go xxxした関数はプロセッサ数に応じて適切なスレッドに割り振られて処理される
  • work-stealingアルゴリズムで処理のスケジューリングをする

goroutineとは何か

以下のように書くと、非同期でgo xxxに渡した関数が実行されます。

実態はスレッドらしいのですが、基本的にはうまく覆い隠されており、以下のような細かい点は意識しなくてよいようになっています。

  • 実行までの手順はどうなってるのか
  • 非同期処理の管理はどうしているのか
  • スレッド数の調節はどう行われているのか

今回は、goはこれらの点をどう解決しているのかを調べました。

goroutineの登録

上記のコードのうち、go xxxの部分をコンパイルした結果は以下のようになっています。

go xxxと書いた場合、コンパイルした結果を見る限り、runtime.newprocに関数ポインタ(?)を渡しています。
newprocは実質newproc1を読んでいるだけなので、newproc1で関数の非同期処理を始めていそうです。

newproc1の中身

newproc1の中身はかなり巨大なため、ここから攻めるのは用意ではありません。
https://github.com/golang/go/blob/99e9be804379d0607de4a322353b317aa087073d/src/runtime/proc.go#L3316

幸いにもおそらくgo1.1の頃のDesign docが存在しています。
現在の実装を見る限り大きく変わってはいないので、これベースで見ていきます。
https://golang.org/s/go11sched

goroutineの処理フロー

goroutineの処理において関わる要素は以下の3つです。

  • P
  • Processor
  • Gを処理していくプロセッサ
  • GOMAXPROCSの数だけPがある
  • M
    • Thread
    • 特定のPに紐付く
  • G
    • gorutineに渡された関数
    • Mに紐付けられて実行される

goroutineの登録

Gは作成されるとキューに積まれます。

PはGを取り出して、Mにくっつけて関数を実行します。

Mがsyscallとかロックとかで待ち状態になると、別のMを作りGを処理します。
Mのロックが解除されたらまた実行を始めます。

goroutineのスケジュール

複数Pが存在する場合、キューが1つだと取り出し時に競合が発生します。
そのため、このままだと並列数を上げても速度が上がりません。

そのため、Pごとにキューを用意して自分のキューを操作するようにします。
これにより、競合が発生しなくなるためスケールするようになります。
ただしこの方法ではP間でキューの中身に差が出るので適切な負荷分散が必要です。

work-stealingアルゴリズム

Pごとにキューを持つようになったので、キューの量に差が出てしまい、結局スケールしなくなってしまいます。

Goではwork-stealingアルゴリズムで負荷分散を行うことで、この問題を回避しています。

このアルゴリズムは以下のような特徴があります。

  1. 暇なworkerが別のworkerから処理をsteal(盗む)
  2. 中央の管理者無しで良い感じにjobが分散する
  3. 別workerへのアクセス回数が少ないので競合が発生しにくい

このアルゴリズムに従い、Pは自分のキューが空になると、別のPのキューにアクセスして中身を半分奪います。

自分のキューが空になった時だけ奪うので、複数ワーカーでもアクセス回数は少なく抑えられています。
また、どのキューから盗むのかもランダムにしています。
この場合、キューが空になるタイミングが同じで、かつ奪うキューが被った場合のみ競合するため、起きにくくなっています。

なお、Pが持つキューがあふれた場合の待避用としてglobalなキューも用意されています。
ここに対しては競合が発生しやすいですが、他のキューを見る回数は抑えられているため、あまり問題にはならないのではと思います。

このあたりの挙動は主にfindrunnable関数で行っているようです。
https://github.com/golang/go/blob/0a7ac93c27c9ade79fe0f66ae0bb81484c241ae5/src/runtime/proc.go#L2266

まとめ

  • goroutineは関数をキューに積む
  • プロセスが取り出して実行する
  • プロセスは自分のキューがなくなったら他から奪う

参考資料

https://golang.org/s/go11sched
https://github.com/golang/go/blob/0a7ac93c27c9ade79fe0f66ae0bb81484c241ae5/src/runtime/proc.go
https://rakyll.org/scheduler/