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

このコミットは、Goランタイムにおけるデッドロック検出の改善に関するものです。具体的には、以下のファイルが変更されています。

src/pkg/runtime/mheap.c: 3行追加
src/pkg/runtime/proc.c: 19行追加、5行削除
test/fixedbugs/bug429.go: 13行追加 (新規ファイル)
test/golden.out: 3行追加

コミット

コミットハッシュ: 84bb2547fb81f00c563e3cbe0f310307980d7408
Author: Rémy Oudompheng oudomphe@phare.normalesup.org
Date: Mon Mar 26 23:06:20 2012 -0400

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

https://github.com/golang/go/commit/84bb2547fb81f00c563e3cbe0f310307980d7408

元コミット内容

runtime: restore deadlock detection in the simplest case.

Fixes #3342.

R=iant, r, dave, rsc
CC=golang-dev, remy
https://golang.org/cl/5844051

このコミットは、Goランタイムにおけるデッドロック検出機能が、特定の単純なケースで機能しなくなっていた問題を修正するために行われました。具体的には、Go issue #3342で報告された問題に対応しています。Goの並行処理モデルでは、複数のゴルーチン（軽量スレッド）が同時に実行されますが、これらのゴルーチンが互いにリソースを待機し合うことで、プログラムが進行不能になる「デッドロック」が発生する可能性があります。Goランタイムは、このようなデッドロックを検出し、プログラムを異常終了させることで、開発者に問題の存在を知らせるメカニズムを持っています。しかし、この機能が一部のシナリオで失われていたため、本コミットによってその検出ロジックが復元されました。

前提知識の解説

デッドロック (Deadlock)

デッドロックとは、並行処理において、複数のプロセスやスレッド（Goにおいてはゴルーチン）が互いに相手が保持しているリソースの解放を待ち続け、結果としてどのプロセスも処理を進められなくなる状態を指します。デッドロックが発生すると、プログラムは応答しなくなり、無限に待機し続けることになります。

デッドロックが発生するための4つの必要条件（コフマンの条件）があります。

相互排他 (Mutual Exclusion): リソースが一度に1つのプロセスによってのみ使用される。
保持と待機 (Hold and Wait): プロセスが既にリソースを保持しており、さらに別のリソースを待機している。
非割込み (No Preemption): リソースは、それを保持しているプロセスによって自発的に解放されるまで、強制的に奪われることはない。
循環待機 (Circular Wait): 複数のプロセスが、それぞれが保持しているリソースを、別のプロセスが待機しているリソースとして要求し、循環を形成している。

Goランタイムは、すべてのゴルーチンがスリープ状態になり、実行可能なゴルーチンが一つも存在しない場合に、デッドロックと判断してruntime.throw("all goroutines are asleep - deadlock!")というパニックを発生させます。これは、プログラムが進行不能になったことを開発者に知らせるための重要な診断機能です。

Goランタイムとスケジューラ

Goプログラムは、Goランタイムによって管理されます。Goランタイムは、ゴルーチンをOSスレッドにマッピングし、実行をスケジュールする役割を担っています。Goのスケジューラは、M（Machine）、P（Processor）、G（Goroutine）という3つのエンティティで構成されます。

G (Goroutine): Goの軽量スレッド。関数呼び出しとして表現され、スタックサイズが小さく、数百万個作成することも可能です。
M (Machine): OSスレッド。ゴルーチンを実行する実際のOSスレッドです。
P (Processor): 論理プロセッサ。MとGを仲介し、MがGを実行するためのコンテキストを提供します。GOMAXPROCS環境変数によってPの数が制御されます。

スケジューラは、実行可能なゴルーチンをPに割り当て、Mがそのゴルーチンを実行します。ゴルーチンがシステムコールを実行したり、チャネル操作でブロックされたりすると、そのゴルーチンは実行を中断し、スケジューラは別の実行可能なゴルーチンを探してMに割り当てます。

`runtime.gosched()`

runtime.gosched()は、現在のゴルーチンを一時停止し、他のゴルーチンにCPUを譲る関数です。これにより、スケジューラは別の実行可能なゴルーチンを選択して実行することができます。これは、協調的マルチタスクの一種であり、長時間実行される計算処理などで他のゴルーチンに実行機会を与えるために使用されます。

技術的詳細

このコミットの主要な変更点は、Goランタイムのスケジューリングロジックとデッドロック検出ロジックにあります。

`src/pkg/runtime/mheap.c` の変更

runtime.MHeap_Scavenger関数は、Goのガベージコレクタの一部として、ヒープのクリーンアップを行う役割を担っています。この関数はループ内で動作し、定期的にヒープの状態をチェックします。

変更前は、このループ内でruntime.gosched()が呼び出されていませんでした。変更後、ループの先頭にruntime.gosched()が追加されました。

// Return to the scheduler in case the rest of the world is deadlocked.
runtime·gosched();

この変更の意図は、runtime.MHeap_Scavengerが長時間実行される可能性があるため、その間に他のゴルーチンがデッドロック状態に陥った場合に、スケジューラに制御を戻すことでデッドロック検出の機会を与えることです。もしruntime.MHeap_Scavengerがgosched()せずに実行され続けている間に他のすべてのゴルーチンがブロックされてしまうと、デッドロック検出が遅れるか、全く行われない可能性がありました。gosched()を呼び出すことで、スケジューラが定期的に実行され、デッドロック状態をチェックする機会が生まれます。

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

src/pkg/runtime/proc.cは、Goランタイムのプロセッサ（P）とゴルーチン（G）の管理、スケジューリングに関するコアロジックが含まれています。

`checkdeadlock` 関数の導入とロジックの変更

このコミットでは、デッドロック検出ロジックをカプセル化するためにcheckdeadlockという静的関数が導入されました。

// Check for a deadlock situation.
static void
checkdeadlock(void) {
	if((scvg == nil && runtime·sched.grunning == 0) ||
	   (scvg != nil && runtime·sched.grunning == 1 && runtime·sched.gwait == 0 &&
	    (scvg->status == Grunnable || scvg->status == Grunning || scvg->status == Gsyscall))) {
		runtime·throw("all goroutines are asleep - deadlock!");
	}
}

この関数は、以下の条件のいずれかが満たされた場合にデッドロックと判断し、runtime.throw("all goroutines are asleep - deadlock!")を呼び出します。

scvg == nil && runtime·sched.grunning == 0:
- scvgはスカベンジャーゴルーチン（ガベージコレクタの一部）を指します。nilの場合、スカベンジャーゴルーチンが存在しないことを意味します。
- runtime·sched.grunningは現在実行中のゴルーチンの数を表します。これが0ということは、実行中のゴルーチンが一つもない状態です。
- この条件は、スカベンジャーゴルーチンが存在せず、かつ実行中のゴルーチンが一つもない場合にデッドロックと判断します。
scvg != nil && runtime·sched.grunning == 1 && runtime·sched.gwait == 0 && (scvg->status == Grunnable || scvg->status == Grunning || scvg->status == Gsyscall):
- scvg != nil: スカベンジャーゴルーチンが存在します。
- runtime·sched.grunning == 1: 実行中のゴルーチンが1つだけ存在します。
- runtime·sched.gwait == 0: 待機中のゴルーチンがありません。
- scvg->status == Grunnable || scvg->status == Grunning || scvg->status == Gsyscall: その唯一実行中のゴルーチンがスカベンジャーゴルーチンであり、その状態が実行可能、実行中、またはシステムコール中である場合。
- この条件は、スカベンジャーゴルーチンのみが実行中（または実行可能/システムコール中）であり、他のすべてのゴルーチンが待機状態にない（つまり、すべてブロックされている）場合にデッドロックと判断します。これは、スカベンジャーゴルーチンが単独で動作しているが、他のゴルーチンがすべて停止している状況を捉えます。

`schedule` 関数内の呼び出し箇所の変更

schedule関数は、Goスケジューラの中心的な部分であり、次に実行するゴルーチンを選択する役割を担っています。

変更前は、schedule関数内でデッドロック検出ロジックが直接記述されていました。

// Look for deadlock situation.
if((scvg == nil && runtime·sched.grunning == 0) ||
   (scvg != nil && runtime·sched.grunning == 1 && runtime·sched.gwait == 0 &&
    (scvg->status == Grunning || scvg->status == Gsyscall))) {
    runtime·throw("all goroutines are asleep - deadlock!");
}

このロジックは、checkdeadlock関数に抽出され、schedule関数の複数の箇所から呼び出されるようになりました。

ゴルーチンが実行可能になった直後: schedule関数内で、実行可能なゴルーチンが見つかり、runtime·sched.grunningがインクリメントされた直後にcheckdeadlock()が呼び出されるようになりました。
```
runtime·sched.grunning++;
// The work could actually have been the sole scavenger
// goroutine. Look for deadlock situation.
checkdeadlock();
```
これは、新たに実行可能になったゴルーチンが、実は唯一のスカベンジャーゴルーチンであった場合など、特定の状況でデッドロックが発生する可能性を早期に検出するためです。
ゴルーチンが見つからなかった場合: schedule関数が実行可能なゴルーチンを見つけられなかった場合、以前と同様にデッドロック検出が行われます。
```
// Look for deadlock situation.
checkdeadlock();
```
これにより、すべてのゴルーチンがブロックされ、スケジューラが何も実行できない状態になった場合に、デッドロックが検出されます。

`test/fixedbugs/bug429.go` の追加

このコミットでは、デッドロック検出が正しく機能することを確認するための新しいテストケースbug429.goが追加されました。

// $G $D/$F.go && $L $F.$A && ! ./$A.out || echo BUG: bug429

// Copyright 2012 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Should print deadlock message, not hang.

package main

func main() {
	select{}
}

このテストケースは非常にシンプルで、main関数内でselect{}という無限のselectステートメントを使用しています。select{}は、どのケースも実行されないため、ゴルーチンを永久にブロックします。これにより、プログラム内のすべてのゴルーチン（この場合はmainゴルーチンのみ）がスリープ状態になり、デッドロックが発生するはずです。このテストの目的は、プログラムがハングアップするのではなく、デッドロックメッセージ（throw: all goroutines are asleep - deadlock!）を出力して終了することを確認することです。

`test/golden.out` の変更

test/golden.outは、Goのテストスイートが期待する出力の「ゴールデンファイル」です。bug429.goテストが追加されたことにより、そのテストの期待される出力（デッドロックメッセージ）がこのファイルに追加されました。

=========== fixedbugs/bug429.go
throw: all goroutines are asleep - deadlock!

これにより、bug429.goが実行された際に、この特定のデッドロックメッセージが出力されることがテストスイートによって検証されます。

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

`src/pkg/runtime/mheap.c`

--- a/src/pkg/runtime/mheap.c
+++ b/src/pkg/runtime/mheap.c
@@ -358,6 +358,9 @@ runtime·MHeap_Scavenger(void)\n \n 	h = &runtime·mheap;\n 	for(k=0;; k++) {\n+		// Return to the scheduler in case the rest of the world is deadlocked.\n+		runtime·gosched();\n+\n 		runtime·noteclear(&note);\
 		runtime·entersyscall();\
 		runtime·notetsleep(&note, tick);\

`src/pkg/runtime/proc.c`

--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -521,6 +521,16 @@ mnextg(M *m, G *g)\n 	}\n }\n \n+// Check for a deadlock situation.\n+static void\n+checkdeadlock(void) {\n+\tif((scvg == nil && runtime·sched.grunning == 0) ||\n+\t   (scvg != nil && runtime·sched.grunning == 1 && runtime·sched.gwait == 0 &&\n+\t    (scvg->status == Grunnable || scvg->status == Grunning || scvg->status == Gsyscall))) {\n+\t\truntime·throw("all goroutines are asleep - deadlock!");\n+\t}\n+}\n+\n // Get the next goroutine that m should run.\n // Sched must be locked on entry, is unlocked on exit.\n // Makes sure that at most $GOMAXPROCS g's are\
@@ -570,6 +580,9 @@ top:\
 				continue;\
 			}\
 			runtime·sched.grunning++;\
+			// The work could actually have been the sole scavenger\
+			// goroutine. Look for deadlock situation.\n+			checkdeadlock();\
 			schedunlock();\
 			return gp;\
 		}\
@@ -591,11 +604,7 @@ top:\
 	}\n \n 	// Look for deadlock situation.\n-\tif((scvg == nil && runtime·sched.grunning == 0) ||\n-\t   (scvg != nil && runtime·sched.grunning == 1 && runtime·sched.gwait == 0 &&\n-\t    (scvg->status == Grunning || scvg->status == Gsyscall))) {\n-\t\truntime·throw("all goroutines are asleep - deadlock!");\n-\t}\n+\tcheckdeadlock();\
 \n 	m->nextg = nil;\
 	m->waitnextg = 1;\

`test/fixedbugs/bug429.go` (新規ファイル)

// $G $D/$F.go && $L $F.$A && ! ./$A.out || echo BUG: bug429

// Copyright 2012 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Should print deadlock message, not hang.

package main

func main() {
	select{}
}

コアとなるコードの解説

`src/pkg/runtime/mheap.c` の変更

runtime·MHeap_Scavenger関数内のループにruntime·gosched()が追加されました。これにより、ガベージコレクタのスカベンジャーがヒープをスキャンしている間も、定期的にスケジューラに制御が戻され、他のゴルーチンの状態（特にデッドロックの可能性）がチェックされる機会が増えます。これは、スカベンジャーが長時間実行されることで、他のゴルーチンのデッドロック検出が妨げられるのを防ぐためのものです。

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

checkdeadlock関数の導入: デッドロック検出のロジックがcheckdeadlockという独立した関数に抽出されました。これにより、コードの可読性と保守性が向上し、デッドロック検出ロジックの一貫性が保たれます。
schedule関数内でのcheckdeadlockの呼び出し:
- ゴルーチンが実行可能になった直後: runtime·sched.grunningがインクリメントされた直後にcheckdeadlock()が呼び出されます。これは、新たに実行可能になったゴルーチンが、実は唯一のスカベンジャーゴルーチンであり、他のすべてのゴルーチンがブロックされているような特殊なケースで、デッドロックを早期に検出するために重要です。
- 実行可能なゴルーチンが見つからなかった場合: schedule関数が実行可能なゴルーチンを見つけられなかった場合にもcheckdeadlock()が呼び出されます。これは、従来のデッドロック検出の主要なポイントであり、すべてのゴルーチンがスリープ状態になったことを確認します。

これらの変更により、Goランタイムはより堅牢にデッドロックを検出し、プログラムがハングアップする代わりに、明確なエラーメッセージを出力して終了するようになります。

`test/fixedbugs/bug429.go` の追加

このテストケースは、select{}というGoの構文を利用して、意図的にデッドロックを発生させます。select{}は、どのcaseも存在しないため、実行されるチャネル操作がなく、ゴルーチンは永久にブロックされます。このテストは、Goランタイムがこのような単純なデッドロック状況を正しく検出し、"all goroutines are asleep - deadlock!"というパニックメッセージを出力することを確認します。これにより、デッドロック検出機能の回帰テストとして機能します。

参考にした情報源リンク

Web search results for "Go issue 3342":
Go言語のスケジューラについて: (一般的なGoスケジューラに関する情報源、例: Go公式ドキュメント、ブログ記事など)
デッドロックの概念について: (一般的な並行処理におけるデッドロックに関する情報源、例: オペレーティングシステムに関する教科書、並行プログラミングのチュートリアルなど)

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

デッドロック (Deadlock)

Goランタイムとスケジューラ

`runtime.gosched()`

技術的詳細

`src/pkg/runtime/mheap.c` の変更

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

`checkdeadlock` 関数の導入とロジックの変更

`schedule` 関数内の呼び出し箇所の変更

`test/fixedbugs/bug429.go` の追加

`test/golden.out` の変更

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

`src/pkg/runtime/mheap.c`

`src/pkg/runtime/proc.c`

`test/fixedbugs/bug429.go` (新規ファイル)

コアとなるコードの解説

`src/pkg/runtime/mheap.c` の変更

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

`test/fixedbugs/bug429.go` の追加

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo