Goスケジューラの仕事は、1つまたは複数のプロセッサ上で実行する複数のワーカOSスレッドに、実行可能なGoルーチンを配分することです。マルチスレッドのコンピュータ処理では、スケジューリングに2つの考え方が登場してきています。
* ワークシェアリング： あるプロセッサが新しいスレッドを生成したとき、idle状態か十分に活用されていないプロセッサが利用してくれることに期待して、生成したスレッドのいくつかを他のプロセッサに移行させます。
* ワークスティーリング： 十分に活用されていないプロセッサが他のプロセッサのスレッドを積極的に探し、そのいくつかを「スティール」ます。

スレッド移行の発生頻度は、ワークスティーリングではワークシェアリングよりも少なくなります。実行すべきワークがどのプロセッサにもあるときは、移行されるスレッドはありません。そして、あるプロセッサがidle状態になれば、直ちに移行が検討されます。

Goには、1.1のときから、Dmitry Vyukovが寄与したワークスティーリング型スケジューラがあります。この記事では、ワークスティーリング型スケジューラとは何か、そしてGoがどのようにしてそれを実装するかについて詳しく説明します。

スケジューリングの基本

GoにはM:Nスケジューラがあり、複数プロセッサを利用することもできます。任意の時点で、M個のGoルーチンを、最大GOMAXPROCS個のプロセッサ上で実行するN個のOSスレッドにスケジューリングする必要があります。Goスケジューラでは、Goルーチン、スレッド、プロセッサに次の用語を使用します。
* G：Goルーチン
* M：OSスレッド（マシン）
* P：プロセッサ

Goルーチンのキューには、P固有のローカルなキューとグローバルなキューがあります。Mはそれぞれ、1つのPに対して指定されます。Pは、ブロックされている場合またはシステムコール内では、Mを指定されないことがあります。任意の時点で存在するPは、最大GOMAXPROCS個です。任意の時点で1つのPについて実行できるMは、ただ1つです。必要に応じて、それより多くのMをスケジューラにより作成可能です。

注釈：
グローバルキュー
ローカルキュー
ローカルキュー

毎回のスケジューリングは、単に、実行可能なGoルーチンを探し、それを実行させるだけです。毎回のスケジューリングでは、検索は次の順序で行われます。

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}

注釈：
61回に1回だけ、グローバルの実行可能キューでGをチェックする。
（グローバルキューで）見つからない場合は、ローカルキューをチェックする。
（ローカルキューで）見つからない場合は、
他のPからスティールを試みる。
スティールできない場合は、グローバルの実行可能キューをチェックする。
（グローバルキューで）見つからない場合は、ネットワークをポーリングする。

実行可能なGが見つかると、ブロックされるまで、それが実行されます。

注：グローバルキューの方がローカルキューより有利なように見えますが、Mがローカルキューの中のGoルーチンがなくなるまでローカルキューだけからスケジューリングするのを避けるために、グローバルキューを時々チェックすることが重要です。

スティーリング

新しいGが作成されたか既存のGが実行可能になると、そのGは、現在のPの実行可能なGoルーチンのリストに入れられます。PはGの実行を終了すると、自分の実行可能なGoルーチンのリストからGを1つ取り出そうとします。リストが空であれば、Pは他のプロセッサ（P）をランダムに選び、そのPの実行可能なGoルーチンのリストの半分をキューからスティールしようとします。

注釈：
グローバルキュー（空）
ローカルキュー
ローカルキュー（空）
ワークが見つからない
P1から3個のGをスティールする

この例では、P2は実行可能なGoルーチンを見つけることができません。そこで、P2はランダムに別のプロセッサ（P1)を選び、3個のGoルーチンを盗んで自分のローカルキューに入れます。P2はこの3個のGoルーチンを実行させることができるようになり、スケジューラの作業が複数のプロセッサ間に上手く配分されます。

空転スレッド

スケジューラは常に、プロセッサを利用するためにできる限り多くのGoルーチンをMに配分しようとしていますが、それと同時に、CPUと電力を温存するために過剰なワークを待機させる必要があります。これに反して、スケジューラには、高スループットでCPU負荷の高いプログラムに合わせて調整する能力も要求されます。

絶え間ないプリエンプションは高費用で、パフォーマンスが重要な場合には高スループットのプログラムにとって問題でもあります。OSスレッドは実行可能なGoルーチンを互いの間で頻繁にハンドオフすべきではありません。遅延の増加につながるからです。それに加えて、syscallがある場合には、絶え間なくOSスレッドをブロックしたりブロック解除したりする必要があります。

ハンドオフを最小限に抑えるために、Goスケジューラは「空転スレッド」を実装します。空転スレッドは余分のCPU電力を少し消費しますが、OSスレッドのプリエンプションを最小限に抑えます。次の場合に、スレッドは空転します。
* Pに指定されたMが実行可能なGoルーチンを探しているとき。
* Pに指定されていないMが利用可能なPを探しているとき。
* idle状態のPがあって、空転中の他のスレッドがない場合にも、スケジューラは、あるGoルーチンの準備中に別のスレッドを待機させ、それを空転させます。

任意の時点で、最大GOMAXPROCS個の空転Mがあります。空転中のスレッドがワークを見つけると、そのスレッドは空転状態から抜け出します。

Pに割り当てられていないadle状態のMがある場合には、Pに割り当てられているadle状態のスレッドはブロックしません。新しいGoルーチンが作成されるか、あるMがブロックされると、スケジューラは、必ず少なくとも1つのMを空転させます。これにより、実行可能なGoルーチンが他の方法で実行中にならないようにして、過剰な、Mのブロッキングまたはブロック解除を回避します。

まとめ

Goスケジューラは、十分に活用されていない適切なプロセッサへのスティーリングによってOSスレッドをスケジューリングすることにより、OSスレッドの過剰なプリエンプションを回避するために非常に役立ち、また、「空転」スレッドを実装して、移行のブロックまたはブロック解除が高頻度に発生しないようにします。

スケジューリングイベントは execution tracer によって追跡することができます。プロセッサの利用率が良くないと感じたら、何が起こっているのか調べることができます。

参考

• Goランタイムスケジューラのソース
• スケーラブルなGoスケジューラ設計のドキュメント
• Daniel MorsingのGoスケジューラ

ご意見やご提案は、 @rakyll まで。