Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 16577] ファイルの概要

このコミットは、Goランタイムのスケジューラにおける公平性（fairness）を改善することを目的としています。特に、ゴルーチンが互いを継続的に再生成するようなシナリオにおいて、グローバルな実行キュー（global runqueue）が飢餓状態（starvation）に陥る問題を解決します。

コミット

commit 4bb491b12e1461252c9375d6b796c8658b10965f
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Sat Jun 15 16:06:28 2013 +0400

    runtime: improve scheduler fairness
    Currently global runqueue is starved if a group of goroutines
    constantly respawn each other (local runqueue never becomes empty).
    Fixes #5639.
    
    R=golang-dev, iant
    CC=golang-dev
    https://golang.org/cl/10042044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/4bb491b12e1461252c9375d6b796c8658b10965f

元コミット内容

runtime: improve scheduler fairness
Currently global runqueue is starved if a group of goroutines
constantly respawn each other (local runqueue never becomes empty).
Fixes #5639.

R=golang-dev, iant
CC=golang-dev
https://golang.org/cl/10042044

変更の背景

Goランタイムのスケジューラは、複数のP（Processor）とM（Machine/OSスレッド）、そしてG（Goroutine）を用いてゴルーチンを効率的に実行します。各Pはローカルな実行キュー（local runqueue）を持ち、MはPにアタッチされてそのローカルキューからゴルーチンを取得して実行します。また、システム全体で共有されるグローバルな実行キュー（global runqueue）も存在します。

このコミットが修正しようとしている問題は、特定のシナリオでグローバル実行キューに存在するゴルーチンが実行機会を得られず、飢餓状態に陥る可能性があったことです。具体的には、あるPにアタッチされたMが、ローカル実行キュー内のゴルーチンが継続的に新しいゴルーチンを生成し、そのローカルキューが常に非空である場合、Mはグローバル実行キューからゴルーチンを取得する機会がほとんどありませんでした。これにより、グローバルキューにいるゴルーチンはいつまでも実行されないという問題が発生していました。

この問題は、Issue #5639として報告されており、このコミットはその解決策として導入されました。

前提知識の解説

  • Goスケジューラ (M-P-Gモデル):
    • G (Goroutine): Goにおける軽量な実行単位。OSスレッドよりもはるかに軽量で、数百万個作成することも可能。
    • M (Machine/OS Thread): OSが管理するスレッド。GoランタイムはMをOSに要求し、M上でGを実行する。
    • P (Processor): 論理的なプロセッサ。MがGを実行するためのコンテキストを提供する。Pはローカルな実行キューを持ち、MはPにアタッチされてそのキューからGを取得する。GOMAXPROCS環境変数でPの数を制御できる。
  • 実行キュー (Runqueue):
    • ローカル実行キュー (Local Runqueue): 各Pが持つゴルーチンのキュー。Mは優先的にこのキューからゴルーチンを取得する。
    • グローバル実行キュー (Global Runqueue): 全てのPで共有されるゴルーチンのキュー。ローカルキューが空になったMは、グローバルキューからゴルーチンを取得しようとする。
  • ゴルーチンの飢餓 (Goroutine Starvation): 特定のゴルーチンが、他のゴルーチンに実行リソースを奪われ続け、いつまでも実行されない状態。スケジューラの公平性が損なわれている場合に発生する。
  • ワークスティーリング (Work Stealing): あるPのローカルキューが空になった場合、他のPのローカルキューからゴルーチンを「盗んで」実行するメカニズム。これにより、P間の負荷分散とリソースの有効活用が図られる。

技術的詳細

このコミットの主要な変更点は、runtime.schedule関数におけるグローバル実行キューからのゴルーチン取得ロジックの改善です。

以前のスケジューリングロジックでは、Mがローカル実行キューからゴルーチンを取得しようとし、それが成功した場合、グローバル実行キューをチェックする機会がありませんでした。ローカルキューが常にゴルーチンで満たされている場合（例えば、ゴルーチンが新しいゴルーチンを継続的に生成し続けるようなパターン）、グローバルキューに存在するゴルーチンは実行される機会を失っていました。

このコミットでは、schedule関数内に定期的にグローバル実行キューをチェックするメカニズムが導入されました。具体的には、m->p->tickというPごとのティックカウンターを利用し、特定の条件（tick % 61 == 0）が満たされた場合に、ローカルキューをチェックする前にグローバルキューからゴルーチンを取得しようとします。

tick % 61 == 0という条件は、tick - (((uint64)tick*0x4325c53fu)>>36)*61 == 0という最適化された形で実装されています。これは、除算（%）命令が乗算命令よりも一般的に高コストであるため、乗算とビットシフトを組み合わせて剰余演算をエミュレートすることでパフォーマンスを向上させています。0x4325c53fuはマジックナンバーであり、特定の定数（この場合は61）に対する除算を乗算とシフトで近似するためのものです。

また、globrunqget関数にmax引数が追加され、グローバルキューから取得するゴルーチンの数を制限できるようになりました。これにより、グローバルキューから一度に大量のゴルーチンを取得しすぎることなく、公平性を保ちつつローカルキューへの補充を行うことができます。

新しいテストケースTestTimerFairnessとTestTimerFairness2は、この公平性の改善を検証するために追加されました。これらのテストは、複数のゴルーチンがチャネル操作やシステムコールを介して互いに協調し、スケジューラの公平性が保たれていることを確認します。特にTestTimerFairness2ではsyscall.Read(0, buf[0:0])というノンブロッキングなシステムコールをループ内で呼び出すことで、ゴルーチンがCPUを占有しつつも、他のゴルーチンに実行機会が与えられるかを検証しています。

コアとなるコードの変更箇所

src/pkg/runtime/proc.c

  • globrunqget関数のシグネチャ変更: static G* globrunqget(P *p) から static G* globrunqget(P *p, int32 max) へ変更。
  • schedule関数内の変更:
    • uint32 tick; の追加。
    • グローバル実行キューを定期的にチェックするロジックの追加。 
      	tick = m->p->tick;
	// Check the global runnable queue once in a while to ensure fairness.
	// Otherwise two goroutines can completely occupy the local runqueue
	// by constantly respawning each other.
	// This is a fancy way to say tick%61==0,
	// it uses 2 MUL instructions instead of a single DIV and so is faster on modern processors.
	if(tick - (((uint64)tick*0x4325c53fu)>>36)*61 == 0 && runtime·sched.runqsize > 0) {
		runtime·lock(&runtime·sched);
		gp = globrunqget(m->p, 1); // max=1 で呼び出し
		runtime·unlock(&runtime·sched);
	}
	if(gp == nil) {
		gp = runqget(m->p);
		if(gp && m->spinning)
			runtime·throw("schedule: spinning with local work");
	}
  • globrunqget関数内の変更:
    • max引数に基づき、取得するゴルーチンの数を制限するロジックの追加。 
      	if(max > 0 && n > max)
		n = max;
  • topラベルとstopラベル内のglobrunqget呼び出しに0を引数として追加。

src/pkg/runtime/proc_test.go

  • syscallパッケージのインポート追加。
  • TestTimerFairness関数の追加。
  • TestTimerFairness2関数の追加。

コアとなるコードの解説

src/pkg/runtime/proc.c

  • globrunqget(P *p, int32 max): この関数は、グローバル実行キューからゴルーチンを取得する役割を担います。max引数が追加されたことで、取得するゴルーチンの最大数を指定できるようになりました。schedule関数から呼び出される際にはmax=1が渡され、一度に1つのゴルーチンのみを取得することで、ローカルキューが空でない場合でもグローバルキューのゴルーチンに実行機会を与えるための「公平性チェック」として機能します。
  • schedule関数内の公平性チェック: schedule関数は、Mが次に実行するゴルーチンを選択するGoスケジューラの中心的な関数です。 追加されたコードブロックは、m->p->tick（Pごとの実行ティックカウンター）が61の倍数である場合に、グローバル実行キューをチェックします。 tick - (((uint64)tick*0x4325c53fu)>>36)*61 == 0 は、tick % 61 == 0 の高速な代替手段です。これは、コンパイラが除算命令を乗算とシフトに最適化する際に用いられるテクニックをDmitriy Vyukovが手動で適用したものです。これにより、CPUサイクルを節約し、スケジューラのオーバーヘッドを最小限に抑えつつ、定期的なチェックを実現しています。 このチェックにより、ローカルキューが常に忙しい状態であっても、グローバルキューのゴルーチンが定期的に「顔を出す」機会を得られるようになり、飢餓状態が解消されます。

src/pkg/runtime/proc_test.go

  • TestTimerFairness: このテストは、2つのゴルーチンがチャネルcを介して継続的に値を送受信するシナリオをシミュレートします。time.Afterで設定されたタイマーが終了するまで、ゴルーチンが公平に実行されることを期待します。もし公平性が損なわれていると、一方のゴルーチンがチャネルを占有し、もう一方が実行されない可能性があります。
  • TestTimerFairness2: このテストは、より厳しいシナリオを提示します。2つのゴルーチンが無限ループ内でsyscall.Read(0, buf[0:0])（ノンブロッキングな読み取り）とチャネル操作を繰り返します。syscall.Read(0, buf[0:0])は、実際には何も読み取らず、システムコールを呼び出すことでCPU時間を消費します。これにより、ゴルーチンがCPUを積極的に使用している状況下で、スケジューラが公平にゴルーチンを切り替える能力を検証します。もし公平性がなければ、一方のゴルーチンがCPUを独占し、もう一方がdoneチャネルに値を送信できず、テストがハングアップする可能性があります。

これらのテストは、スケジューラの公平性改善が実際に機能していることを確認するための重要な検証手段です。

関連リンク

参考にした情報源リンク

  • Goのスケジューラに関する公式ドキュメントやブログ記事 (当時のGoのバージョンに合わせたもの)
  • Goのランタイムソースコード (src/pkg/runtime/proc.c および src/pkg/runtime/proc_test.go)
  • 剰余演算の最適化に関する一般的な情報 (例: "Fast modulo operation")
  • GoのM-P-Gモデルに関する解説記事
  • Goのチャネルとゴルーチンの動作に関する情報
  • syscall.Readの動作に関する情報