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

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

このコミットは、Goランタイムのスケジューラにおける競合状態（race condition）を修正するものです。具体的には、starttheworld関数が持つ誤った前提条件によって引き起こされる問題に対処し、P（Processor）が持つローカルなG（Goroutine）が適切に実行されない可能性を排除します。

コミット

commit dbcfed93e75b91819bd01eb228996073b18c8196
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Wed Jun 12 18:46:35 2013 +0400

    runtime: fix scheduler race condition
    In starttheworld() we assume that P's with local work
    are situated in the beginning of idle P list.
    However, once we start the first M, it can execute all local G's
    and steal G's from other P's.
    That breaks the assumption above. Thus starttheworld() will fail
    to start some P's with local work.
    It seems that it can not lead to very bad things, but still
    it's wrong and breaks other assumtions
    (e.g. we can have a spinning M with local work).
    The fix is to collect all P's with local work first,
    and only then start them.

    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/10051045

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

https://github.com/golang/go/commit/dbcfed93e75b91819bd01eb228996073b18c8196

元コミット内容

Goランタイムのスケジューラにおける競合状態を修正します。starttheworld()関数内で、ローカルな作業（Goroutine）を持つP（Processor）がアイドル状態のPリストの先頭に位置するという前提がありました。しかし、最初のM（Machine/OSスレッド）が起動されると、そのMは自身のローカルなGを実行したり、他のPからGを奪ったりする可能性があります。これにより、上記の前提が崩れ、結果としてstarttheworld()がローカルな作業を持つ一部のPを起動できない事態が発生していました。これは致命的な問題には繋がらないものの、誤った動作であり、他の前提（例えば、ローカルな作業を持つMがスピンし続ける可能性があること）を破るものでした。この修正は、まずローカルな作業を持つ全てのPを収集し、その後でそれらを起動するというアプローチを取ることで問題を解決します。

変更の背景

Goランタイムのスケジューラは、M（OSスレッド）、P（Processor）、G（Goroutine）という3つの主要なエンティティで構成されるM:Nスケジューリングモデルを採用しています。MはOSスレッドを表し、GはGoの軽量スレッド、PはMがGを実行するために必要なコンテキスト（ローカルな実行キューなど）を提供します。

starttheworld()関数は、ガベージコレクション（GC）などの特定の操作のために一時的に全てのGoroutineの実行を停止するstoptheworld()の後に呼び出され、停止していたGoroutineの実行を再開させる役割を担います。この関数は、停止中にPがローカルキューにGoroutineを持っている場合、それらのPを再開させる必要があります。

問題の背景には、starttheworld()がPを再開させる際の内部的な処理順序と、MによるGoroutineの実行・スティール（work stealing）のタイミングに関する誤った前提がありました。具体的には、starttheworld()は、ローカルな作業を持つPがアイドルPリストの先頭に集まっていると仮定していました。しかし、starttheworld()が最初のMを起動し、そのMがGoroutineの実行を開始すると、そのMは自身のPのローカルキューにあるGoroutineを全て実行し終えたり、他のPからGoroutineをスティールしたりする可能性があります。このMの活動によって、starttheworld()がPを処理している最中にPの状態（ローカルキューの有無など）が変化し、結果としてローカルな作業を持つPが適切に起動されないという競合状態が発生していました。

この問題は、システムがデッドロックに陥るような深刻なバグには直結しないものの、スケジューラの内部的な整合性を損ない、ローカルな作業を持つMが不必要にスピンし続ける（CPUを消費し続ける）といった非効率な状態を引き起こす可能性がありました。

前提知識の解説

このコミットを理解するためには、Goランタイムのスケジューラに関する以下の概念を理解しておく必要があります。

  1. M (Machine/OS Thread): オペレーティングシステムのスレッドに相当します。Goのランタイムは、MをOSに要求し、そのM上でGoroutineを実行します。MはPにアタッチされ、PのローカルキューからGoroutineを取得して実行します。
  2. P (Processor): 論理的なプロセッサであり、MがGoroutineを実行するためのコンテキストを提供します。PはローカルなGoroutineキューを持ち、通常はMがこのPにアタッチされてGoroutineを実行します。利用可能なPの数は、通常、CPUのコア数に設定されます（GOMAXPROCS）。
  3. G (Goroutine): Goの軽量スレッドです。Goプログラムの並行処理の単位であり、MによってP上で実行されます。
  4. ローカルキューとグローバルキュー: 各Pは自身のローカルなGoroutineキューを持ちます。MはまずこのローカルキューからGoroutineを取得しようとします。ローカルキューが空の場合、MはグローバルなGoroutineキューや、他のPのローカルキューからGoroutineをスティール（work stealing）しようとします。
  5. stoptheworld()とstarttheworld():
    • stoptheworld(): ガベージコレクション（GC）などの特定のランタイム操作を実行する際に、全てのGoroutineの実行を一時的に停止させるメカニズムです。これにより、GCがメモリを安全に操作できるようになります。
    • starttheworld(): stoptheworld()によって停止されたGoroutineの実行を再開させる関数です。停止中にPが持っていたローカルなGoroutineを再開させる責任があります。
  6. pidleput(): アイドル状態になったPをアイドルPリストに追加する関数です。
  7. mget(): 利用可能なM（OSスレッド）を取得する関数です。
  8. newm(): 新しいM（OSスレッド）を作成し、起動する関数です。
  9. runtime·notewakeup(&mp->park): Mをpark状態（スリープ状態）から起こすためのメカニズムです。MがGoroutineの実行を待っている場合に、新しいGoroutineが利用可能になったことを通知するために使用されます。

技術的詳細

このコミットが修正する問題は、starttheworld()関数がPを再開させるロジックに潜んでいました。修正前のコードでは、starttheworld()はアイドル状態のPを順に処理し、もしそのPがローカルなGoroutineを持っていると判断した場合、そのPに新しいMを割り当てて起動しようとしていました。

具体的な問題点は以下の通りです。

  1. 誤った前提: starttheworld()は、Pのリストを走査する際に、ローカルな作業を持つPがアイドルPリストの先頭に集まっているという前提を持っていました。
  2. 競合状態の発生: starttheworld()がPを処理している最中に、既に起動されたMが他のPからGoroutineをスティールしたり、自身のPのローカルキューを空にしたりする可能性があります。
    • 例えば、starttheworld()がP1を処理し、P1にM1を割り当てて起動したとします。M1はP1のローカルキューのGoroutineを実行し始めます。
    • その間に、starttheworld()がP2を処理しようとします。もしM1がP2からGoroutineをスティールした場合、P2はローカルな作業を持たない状態になる可能性があります。
    • あるいは、M1がP1のローカルキューを全て実行し終え、P1がアイドル状態になった後、starttheworld()がP1を再度処理しようとした際に、P1が既にローカルな作業を持っていないと誤って判断する可能性がありました。
  3. 結果: この競合状態により、starttheworld()がローカルな作業を持つ一部のPを適切に起動できないことがありました。これにより、本来実行されるべきGoroutineが遅延したり、ローカルな作業を持つMが不必要にスピンし続けたりする（CPUリソースを無駄に消費する）といった非効率な状態が発生する可能性がありました。コミットメッセージにある「spinning M with local work」とは、まさにこの状態を指します。MがローカルなGoroutineを持っているにも関わらず、スケジューラがそれを認識せず、MがGoroutineを探し続ける（スピンする）状態です。

修正のアプローチ: 修正は、この競合状態を根本的に解決するために、Pの処理順序を変更しました。 新しいアプローチでは、starttheworld()はまず、ローカルな作業を持つ全てのPを一時的なリスト（p1）に収集します。この収集フェーズでは、Mの起動やGoroutineの実行は行いません。全てのPの状態が確定した後に、この収集されたPのリストを順に処理し、必要に応じてMを割り当てて起動します。

これにより、Pの状態がstarttheworld()の処理中に動的に変化する可能性がなくなり、ローカルな作業を持つ全てのPが確実に起動されるようになります。

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

変更は src/pkg/runtime/proc.c ファイルの runtime·starttheworld 関数に集中しています。

--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -420,16 +420,9 @@ runtime·starttheworld(void)
 			pidleput(p);
 			break;
 		}
-		mp = mget();
-		if(mp == nil) {
-			p->link = p1;
-			p1 = p;
-			continue;
-		}
-		if(mp->nextp)
-			runtime·throw("starttheworld: inconsistent mp->nextp");
-		mp->nextp = p;
-		runtime·notewakeup(&mp->park);
+		p->m = mget(); // MをPに一時的に関連付ける
+		p->link = p1;  // Pを一時リストp1に追加
+		p1 = p;
 	}
 	if(runtime·sched.sysmonwait) {
 		runtime·sched.sysmonwait = false;
@@ -440,8 +433,18 @@ runtime·starttheworld(void)
 	while(p1) {
 		p = p1;
 		p1 = p1->link;
-		add = false;
-		newm(nil, p);
+		add = false; // デフォルトで新しいMの追加はしない
+		if(p->m) { // PにMが関連付けられている場合（つまり、既存のMを再利用する場合）
+			mp = p->m;
+			p->m = nil; // PからMの関連付けを解除
+			if(mp->nextp)
+				runtime·throw("starttheworld: inconsistent mp->nextp");
+			mp->nextp = p; // MにPを割り当てる
+			runtime·notewakeup(&mp->park); // Mを起こす
+		} else { // PにMが関連付けられていない場合（つまり、新しいMが必要な場合）
+			// Start M to run P.  Do not start another M below.
+			newm(nil, p); // 新しいMを作成し、Pに割り当てて起動
+			add = false;
+		}
 	}

 	if(add) {
@@ -1154,6 +1157,8 @@ top:
 	}

 	gp = runqget(m->p);
+	if(gp && m->spinning) // 新しいチェック：ローカルな作業があるのにMがスピンしている場合はエラー
+		runtime·throw("schedule: spinning with local work");
 	if(gp == nil)
 		gp = findrunnable();

コアとなるコードの解説

変更は大きく2つのフェーズに分けられます。

フェーズ1: ローカルな作業を持つPの収集とMの仮割り当て

修正前は、forループ内でPを処理し、ローカルな作業を持つPが見つかるとすぐにmget()でMを取得し、そのMを起動していました。

// 修正前 (抜粋)
		mp = mget();
		if(mp == nil) {
			p->link = p1;
			p1 = p;
			continue;
		}
		// ...
		mp->nextp = p;
		runtime·notewakeup(&mp->park); // Mを起動

修正後は、この部分が以下のように変更されました。

// 修正後 (抜粋)
		p->m = mget(); // MをPに一時的に関連付ける
		p->link = p1;  // Pを一時リストp1に追加
		p1 = p;
  • mp = mget(); の呼び出しは残っていますが、取得したMをすぐに起動するのではなく、p->m に一時的に格納するようになりました。これは、このPが後で起動される際に使用されるMを「予約」するようなものです。
  • p->link = p1; p1 = p; は、ローカルな作業を持つPを逆順の単方向リスト p1 に追加する処理です。これにより、starttheworld()の最初のループでは、ローカルな作業を持つ全てのPが収集され、必要に応じてMが仮割り当てされるだけで、実際のMの起動は行われません。

この変更により、Pのリストを走査している間にMがGoroutineを実行したりスティールしたりしてPの状態が変化する競合状態が回避されます。全てのPの状態がこのフェーズで「スナップショット」される形になります。

フェーズ2: 収集したPの起動

修正前は、while(p1) ループ内で newm(nil, p); を呼び出して新しいMを作成し、Pに割り当てて起動していました。

// 修正前 (抜粋)
	while(p1) {
		p = p1;
		p1 = p1->link;
		add = false;
		newm(nil, p); // 新しいMを作成し起動
	}

修正後は、この部分が以下のように変更されました。

// 修正後 (抜粋)
	while(p1) {
		p = p1;
		p1 = p1->link;
		add = false;
		if(p->m) { // PにMが関連付けられている場合（フェーズ1で仮割り当てされたMがある場合）
			mp = p->m;
			p->m = nil;
			if(mp->nextp)
				runtime·throw("starttheworld: inconsistent mp->nextp");
			mp->nextp = p;
			runtime·notewakeup(&mp->park); // 既存のMを起こす
		} else { // PにMが関連付けられていない場合（新しいMが必要な場合）
			// Start M to run P.  Do not start another M below.
			newm(nil, p); // 新しいMを作成し、Pに割り当てて起動
			add = false;
		}
	}
  • このループでは、フェーズ1で収集されたPのリスト p1 を順に処理します。
  • if(p->m) の条件が追加されました。これは、フェーズ1でこのPにMが仮割り当てされたかどうかをチェックします。
    • もし p->m が存在する場合（つまり、既存のMを再利用できる場合）、そのM (mp) を取得し、mp->nextp = p; でPをMに割り当て、runtime·notewakeup(&mp->park); でMをpark状態から起こします。
    • もし p->m が存在しない場合（つまり、新しいMが必要な場合）、newm(nil, p); を呼び出して新しいMを作成し、Pに割り当てて起動します。

この二段階の処理により、starttheworld()はまず全てのPの状態を把握し、その後で一貫した方法でMを起動または再利用してPを再開させることができます。これにより、スケジューラの競合状態が解消され、ローカルな作業を持つPが確実に起動されるようになります。

追加のチェック:

runtime·schedule 関数にも新しいチェックが追加されました。

@@ -1154,6 +1157,8 @@ top:
 	}

 	gp = runqget(m->p);
+	if(gp && m->spinning)
+		runtime·throw("schedule: spinning with local work");
 	if(gp == nil)
 		gp = findrunnable();
  • if(gp && m->spinning): この行は、MがローカルなGoroutine (gp がnilでない) を持っているにも関わらず、m->spinning フラグがtrue（つまり、MがGoroutineを探してスピンしている状態）である場合に、ランタイムエラーを発生させます。これは、修正前の問題（ローカルな作業を持つMが不必要にスピンし続ける）が解消されたことを確認するためのアサーションであり、もしこの状態が発生すれば、それはスケジューラのロジックにまだ問題があることを示唆します。このチェックの追加は、このコミットが解決しようとしている問題の性質を明確に示しています。

関連リンク

参考にした情報源リンク

  • Goのソースコード (src/pkg/runtime/proc.c)
  • Goのスケジューラに関する一般的なドキュメントや解説（M, P, Gモデル、work stealingなど）
    • （Web検索は行っていませんが、これらの概念はGoランタイムの基本的な知識として参照しました。）