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

このコミットは、Goランタイムにおけるスケジューリングの公平性を改善することを目的としています。特に、頻繁なガベージコレクション（GC）が発生する状況下で、特定のゴルーチン（特にタイマーゴルーチン）が飢餓状態に陥る問題を解決します。

コミット

commit 90eca36a23cf5ec59a46626771f8074e2b68df60
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Jan 21 10:24:42 2014 +0400

    runtime: ensure fair scheduling during frequent GCs
    What was happenning is as follows:
    Each writer goroutine always triggers GC during its scheduling quntum.
    After GC goroutines are shuffled so that the timer goroutine is always second in the queue.
    This repeats infinitely, causing timer goroutine starvation.
    Fixes #7126.
    
    R=golang-codereviews, shanemhansen, khr, khr
    CC=golang-codereviews
    https://golang.org/cl/53080043

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

https://github.com/golang/go/commit/90eca36a23cf5ec59a46626771f8074e2b68df60

元コミット内容

このコミットの目的は、頻繁なGC中に公平なスケジューリングを保証することです。 問題は、各ライターゴルーチンがそのスケジューリングクォンタム中に常にGCをトリガーし、GC後にゴルーチンがシャッフルされ、タイマーゴルーチンが常にキューの2番目になるというものでした。これが無限に繰り返され、タイマーゴルーチンの飢餓を引き起こしていました。 このコミットは、Go Issue #7126 を修正します。

変更の背景

Goランタイムは、複数のゴルーチンを効率的にスケジューリングし、利用可能なプロセッサ（P）に分散させることで並行性を実現しています。しかし、特定の条件下、特にガベージコレクション（GC）が頻繁に発生する場合に、スケジューリングの公平性が損なわれる可能性がありました。

このコミットが修正しようとしている具体的な問題は、以下のシナリオで発生していました。

1. GCトリガー: 特定のゴルーチン（このコミットの例では「ライターゴルーチン」）が、その実行クォンタム中に頻繁にGCをトリガーするような処理を行う。これは、大量のメモリ割り当てや、GCを強制的に実行するような操作によって起こりえます。
2. ゴルーチンのシャッフル: GCが実行されると、ランタイムは一時的にすべてのゴルーチンの実行を停止し、GC処理を行います。GCが完了した後、実行可能なゴルーチンは再度スケジューリングキューに入れられます。この際、以前のランタイムの挙動では、ゴルーチンの順序が特定のパターンでシャッフルされることがありました。
3. タイマーゴルーチンの飢餓: シャッフルされた結果、特定の重要なゴルーチン（例えば、time.Sleepやtime.Afterなどのタイマーイベントを処理する「タイマーゴルーチン」）が常にキューの後方に配置されてしまう状況が発生しました。これにより、タイマーゴルーチンが実行される機会が極端に減少し、結果としてタイマーイベントが遅延したり、全く処理されなかったりする「飢餓状態」に陥っていました。

この問題は、特にI/O処理やネットワーク通信など、時間ベースのイベントに依存するアプリケーションにおいて、深刻なパフォーマンス問題やデッドロックを引き起こす可能性がありました。コミットメッセージにある「Fixes #7126」は、この具体的な問題を追跡していたGoのIssue番号を示しています。

前提知識の解説

このコミットの変更を理解するためには、Goランタイムの以下の主要な概念を理解しておく必要があります。

Goランタイムスケジューラ (M-P-G モデル)

Goのスケジューラは、M-P-Gモデルとして知られる3つの主要な要素で構成されています。

• M (Machine/OS Thread): オペレーティングシステムのスレッドを表します。Goプログラムは、OSスレッド上で実行されます。Mは、Pにアタッチされてゴルーチンを実行するか、システムコールを実行します。
• P (Processor): 論理プロセッサを表します。これは、Goランタイムがゴルーチンを実行するために使用するコンテキストです。Pは、Mにゴルーチンを実行するためのリソース（ローカルランキュー、メモリ割り当てキャッシュなど）を提供します。GOMAXPROCS環境変数によって設定されるPの数は、同時に実行できるOSスレッドの最大数（つまり、同時に実行できるゴルーチンの数）を決定します。
• G (Goroutine): Goの軽量な実行単位です。ゴルーチンは、OSスレッドよりもはるかに軽量で、数百万個作成することも可能です。ゴルーチンは、Pのローカルランキューまたはグローバルランキューに配置され、Mによって実行されます。

ゴルーチンのランキュー

Goランタイムには、実行可能なゴルーチンを管理するための2種類のキューがあります。

• ローカルランキュー (Pのランキュー): 各Pは、自身のローカルランキューを持っています。MがPにアタッチされている間、Mはまずこのローカルランキューからゴルーチンを取得して実行します。これにより、ロックの競合が減り、キャッシュの局所性が向上します。
• グローバルランキュー: すべてのPが共有するグローバルなランキューです。ローカルランキューが空になったPは、グローバルランキューからゴルーチンを取得しようとします。また、システムコールから戻ってきたゴルーチンや、ネットワークI/Oなどでブロック解除されたゴルーチンは、一時的にグローバルランキューに配置されることがあります。

ガベージコレクション (GC) とスケジューラ

GoのGCは、並行かつインクリメンタルに動作しますが、特定のフェーズ（特にマークフェーズの開始時や終了時）では、すべてのゴルーチンの実行を一時的に停止する「Stop-The-World (STW)」フェーズが発生します。STWフェーズ中、ランタイムはゴルーチンの状態をスキャンし、必要に応じてメモリを再配置します。

GCが完了し、STWフェーズが終了すると、停止していたゴルーチンは再び実行可能な状態になり、ランキューに戻されます。この際、ゴルーチンがランキューにどのように再配置されるかが、スケジューリングの公平性に影響を与えます。

飢餓 (Starvation)

飢餓とは、特定のプロセスやスレッド（この場合はゴルーチン）が、リソース（この場合はCPU時間）を割り当てられずに、 indefinitely 長い間実行できない状態を指します。Goのコンテキストでは、これは特定のゴルーチンが他のゴルーチンに比べて極端に実行機会が少なくなることを意味します。タイマーゴルーチンの飢餓は、時間ベースの処理が期待通りに動作しないという深刻な問題を引き起こします。

procresize 関数

procresize関数は、Goランタイムにおいて、利用可能なPの数（GOMAXPROCSによって決定される）が変更された際に呼び出される重要な関数です。この関数は、Pの数を調整し、それに伴って既存の実行可能なゴルーチンを新しいPの構成に合わせて再分配する役割を担います。具体的には、古いPのローカルランキューにあるゴルーチンをグローバルランキューに集め、その後、新しいPの構成に基づいてそれらを再分配します。この再分配のロジックが、本コミットの変更の中心となります。

技術的詳細

このコミットの技術的な核心は、src/pkg/runtime/proc.cファイル内のprocresize関数におけるゴルーチンの再分配ロジックの変更にあります。以前のバージョンでは、Pの数が変更された際に、各Pのローカルランキューからゴルーチンをグローバルランキューに集める際に、その順序が保証されていませんでした。これが、特定のゴルーチンが飢餓状態に陥る原因となっていました。

変更前は、procresize関数内で以下のような処理が行われていました。

// collect all runnable goroutines in global queue
for(i = 0; i < old; i++) {
    p = runtime·allp[i];
    while(gp = runqget(p))
        globrunqput(gp);
}

このコードは、各Pのローカルランキューからゴルーチンをrunqgetで取得し、グローバルランキューにglobrunqputで追加していました。runqgetは通常、キューのヘッドから要素を取り出すため、ローカルキューのFIFO順序は保たれますが、複数のPからグローバルキューに集める際に、P間の相対的な順序や、グローバルキューへの追加順序が、結果的にゴルーチンの実行順序を予測不能にし、不公平な状態を生み出す可能性がありました。特に、GC後のゴルーチン再配置において、この問題が顕在化していました。

このコミットでは、この部分が以下のように変更されました。

// collect all runnable goroutines in global queue preserving FIFO order
// FIFO order is required to ensure fairness even during frequent GCs
// see http://golang.org/issue/7126
empty = false;
while(!empty) {
    empty = true;
    for(i = 0; i < old; i++) {
        p = runtime·allp[i];
        if(p->runqhead == p->runqtail)
            continue;
        empty = false;
        // pop from tail of local queue
        p->runqtail--;
        gp = p->runq[p->runqtail%nelem(p->runq)];
        // push onto head of global queue
        gp->schedlink = runtime·sched.runqhead;
        runtime·sched.runqhead = gp;
        if(runtime·sched.runqtail == nil)
            runtime·sched.runqtail = gp;
        runtime·sched.runqsize++;
    }
}

この変更のポイントは以下の通りです。

1. FIFO順序の保証: 新しいコメントにあるように、「FIFO順序は頻繁なGC中でも公平性を保証するために必要」と明記されています。
2. while(!empty) ループ: すべてのPのローカルランキューが空になるまで、繰り返しゴルーチンを収集するループが導入されました。これにより、各Pから一度に1つのゴルーチンを順番に収集し、グローバルキューに移動させることで、より公平な順序を保つことができます。
3. ローカルキューの末尾からのポップ: p->runqtail--; gp = p->runq[p->runqtail%nelem(p->runq)]; の行は、各Pのローカルランキューからゴルーチンを末尾から取り出すことを意味します。これは、ローカルキューがリングバッファとして実装されているため、末尾から取り出すことで、ローカルキュー内でのゴルーチンの相対的な順序を維持しつつ、グローバルキューへの追加順序を制御するためです。
4. グローバルキューの先頭へのプッシュ: gp->schedlink = runtime·sched.runqhead; runtime·sched.runqhead = gp; の行は、取り出したゴルーチンをグローバルランキューの先頭に追加することを意味します。ローカルキューから末尾の要素を取り出し、それをグローバルキューの先頭に追加することで、結果的にグローバルキュー全体でゴルーチンのFIFO順序が維持されるように工夫されています。例えば、ローカルキューAに[G1, G2, G3]、ローカルキューBに[G4, G5, G6]があった場合、このロジックでは、まずG3、次にG6、次にG2、次にG5...というように取り出され、グローバルキューの先頭に追加されるため、最終的にグローバルキューは[G1, G4, G2, G5, G3, G6]のような順序になる可能性があります。これは、元のローカルキューの順序を保ちつつ、P間の公平な取り込みを試みるものです。

この変更により、GC後のゴルーチン再分配において、特定のゴルーチンが常に後回しにされるという問題が解消され、より公平なスケジューリングが実現されるようになりました。

また、src/pkg/runtime/proc_test.goには、この公平性を検証するための新しいテストTestGCFairnessが追加されました。このテストは、GOMAXPROCS(1)を設定し、2つのゴルーチンが/dev/nullに継続的に書き込むというシナリオをシミュレートします。/dev/nullへの書き込みは非常に高速であり、これによりGCが頻繁にトリガーされる状況を作り出します。このテストは、このような状況下でもタイマーゴルーチンが飢餓状態に陥らず、time.Sleepが期待通りに動作することを確認します。

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

src/pkg/runtime/proc.c

--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -2207,6 +2207,7 @@ static void
 procresize(int32 new)
 {
 	int32 i, old;
+	bool empty;
 	G *gp;
 	P *p;
 
@@ -2231,11 +2232,27 @@ procresize(int32 new)
 	}
 
 	// redistribute runnable G's evenly
-	// collect all runnable goroutines in global queue
-	for(i = 0; i < old; i++) {
-		p = runtime·allp[i];
-		while(gp = runqget(p))
-			globrunqput(gp);
+	// collect all runnable goroutines in global queue preserving FIFO order
+	// FIFO order is required to ensure fairness even during frequent GCs
+	// see http://golang.org/issue/7126
+	empty = false;
+	while(!empty) {
+		empty = true;
+		for(i = 0; i < old; i++) {
+			p = runtime·allp[i];
+			if(p->runqhead == p->runqtail)
+				continue;
+			empty = false;
+			// pop from tail of local queue
+			p->runqtail--;
+			gp = p->runq[p->runqtail%nelem(p->runq)];
+			// push onto head of global queue
+			gp->schedlink = runtime·sched.runqhead;
+			runtime·sched.runqhead = gp;
+			if(runtime·sched.runqtail == nil)
+				runtime·sched.runqtail = gp;
+			runtime·sched.runqsize++;
+		}
 	}
 	// fill local queues with at most nelem(p->runq)/2 goroutines
 	// start at 1 because current M already executes some G and will acquire allp[0] below,

src/pkg/runtime/proc_test.go

--- a/src/pkg/runtime/proc_test.go
+++ b/src/pkg/runtime/proc_test.go
@@ -244,6 +244,49 @@ func TestPreemptionGC(t *testing.T) {
 	atomic.StoreUint32(&stop, 1)
 }
 
+func TestGCFairness(t *testing.T) {
+	output := executeTest(t, testGCFairnessSource, nil)
+	want := "OK\n"
+	if output != want {
+		t.Fatalf("want %s, got %s\n", want, output)
+	}
+}
+
+const testGCFairnessSource = `
+package main
+
+import (
+	"fmt"
+	"os"
+	"runtime"
+	"time"
+)
+
+func main() {
+	runtime.GOMAXPROCS(1)
+	f, err := os.Open("/dev/null")
+	if os.IsNotExist(err) {
+		// This test tests what it is intended to test only if writes are fast.
+		// If there is no /dev/null, we just don't execute the test.
+		fmt.Println("OK\n")
+		return
+	}
+	if err != nil {
+		fmt.Println(err)
+		os.Exit(1)
+	}
+	for i := 0; i < 2; i++ {
+		go func() {
+			for {
+				f.Write([]byte("."))
+			}
+		}()
+	}
+	time.Sleep(10 * time.Millisecond)
+	fmt.Println("OK")
+}
+`
+
 func stackGrowthRecursive(i int) {
 	var pad [128]uint64
 	if i != 0 && pad[0] == 0 {

コアとなるコードの解説

src/pkg/runtime/proc.c の変更点

procresize関数内のゴルーチン再分配ロジックが完全に書き換えられました。

• bool empty; の追加: 新しいループの制御に使用されるフラグです。
• while(!empty) ループ: このループは、すべてのPのローカルランキューが空になるまで繰り返されます。
  • ループの各イテレーションで、emptyは最初にtrueに設定されます。これは、もしこのイテレーションでどのPからもゴルーチンが取り出されなければ、すべてのキューが空になったと判断するためです。
  • for(i = 0; i < old; i++) ループは、既存のすべてのPを順番に処理します。
  • if(p->runqhead == p->runqtail): 現在のPのローカルランキューが空であるかをチェックします。空であればスキップします。
  • empty = false;: もしゴルーチンが取り出された場合、emptyをfalseに設定し、まだ処理すべきゴルーチンがあることを示します。
  • p->runqtail--;: ここが重要な変更点です。ローカルランキューからゴルーチンを末尾から取り出します。Goのランキューはリングバッファとして実装されており、通常はヘッドから取り出されますが、ここでは末尾から取り出すことで、グローバルキューへの追加順序を逆転させ、結果的にFIFOを維持しようとします。
  • gp = p->runq[p->runqtail%nelem(p->runq)];: 末尾から取り出したゴルーチンへのポインタを取得します。
  • gp->schedlink = runtime·sched.runqhead; runtime·sched.runqhead = gp;: 取り出したゴルーチンをグローバルランキューの先頭に追加します。これにより、ローカルキューから末尾の要素が取り出され、それがグローバルキューの先頭に追加されるため、全体としてゴルーチンの相対的な順序が保たれ、公平性が向上します。
  • if(runtime·sched.runqtail == nil) runtime·sched.runqtail = gp;: グローバルランキューが空の場合、テールも設定します。
  • runtime·sched.runqsize++;: グローバルランキューのサイズをインクリメントします。

この新しいロジックにより、GC後のゴルーチン再分配において、ゴルーチンがより公平な順序でグローバルランキューに配置されるようになり、特定のゴルーチンが飢餓状態に陥るのを防ぎます。

src/pkg/runtime/proc_test.go の変更点

• TestGCFairness 関数の追加:
  • このテストは、executeTestヘルパー関数を使用して、testGCFairnessSourceで定義されたGoプログラムを実行します。
  • 期待される出力は "OK\n" です。
• testGCFairnessSource 定数の追加:
  • この文字列定数は、テスト対象となるGoプログラムのソースコードを含んでいます。
  • runtime.GOMAXPROCS(1): Pの数を1に制限し、単一のOSスレッドで実行されるようにします。これにより、スケジューリングの競合がより顕著になります。
  • os.Open("/dev/null"): /dev/nullへの書き込みは非常に高速であり、大量のI/O操作をシミュレートします。これにより、Goランタイムが頻繁にGCをトリガーする状況を作り出します。
  • for i := 0; i < 2; i++ { go func() { for { f.Write([]byte(".")) } }(): 2つのゴルーチンを起動し、それぞれが無限ループで/dev/nullに書き込み続けます。これらのゴルーチンはGCを頻繁にトリガーする「ライターゴルーチン」の役割を果たします。
  • time.Sleep(10 * time.Millisecond): この行が、タイマーゴルーチンが飢餓状態に陥っていないかを検証する鍵となります。もしタイマーゴルーチンが飢餓状態であれば、このSleepが期待通りに動作せず、テストが失敗する可能性があります。
  • fmt.Println("OK"): Sleepが正常に完了した場合に"OK"を出力し、テストが成功したことを示します。

このテストは、本コミットが解決しようとしている「頻繁なGC中のスケジューリングの公平性」の問題を直接的に検証するためのものです。

関連リンク

• Go Issue #7126: https://github.com/golang/go/issues/7126
• Go CL 53080043: https://golang.org/cl/53080043

参考にした情報源リンク

• Goのスケジューラに関する公式ドキュメントやブログ記事 (一般的なGoランタイムのM-P-Gモデル、ランキューの概念について)
• Goのガベージコレクションに関する公式ドキュメントやブログ記事 (GCの動作、STWフェーズについて)
• Goのソースコード (特にsrc/runtime/proc.goやsrc/runtime/proc.cなど、スケジューラ関連のファイル)
• GoのIssueトラッカー (Issue #7126の詳細な議論について)
• Goのコードレビューシステム (CL 53080043のレビューコメントについて)
• オペレーティングシステムのスケジューリングアルゴリズムに関する一般的な知識 (公平性、飢餓の概念について)
• リングバッファのデータ構造に関する一般的な知識 (ランキューの実装について)
• Goのテストフレームワークに関する知識 (テストコードの理解について)
• os.Open("/dev/null") の挙動に関する知識 (テストシナリオの理解について)
• runtime.GOMAXPROCS の挙動に関する知識 (テストシナリオの理解について)
• time.Sleep の挙動に関する知識 (テストシナリオの理解について)