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

このコミットは、Goランタイムにおいて、長時間実行されているゴルーチンをプリエンプト（強制的に中断）する機能を追加するものです。具体的には、ゴルーチンが10ミリ秒以上実行された場合にプリエンプションを適用し、他のゴルーチンにCPU時間を公平に割り当てることを目的としています。これにより、特定のゴルーチンがCPUを占有し続けることによる他のゴルーチンの飢餓状態を防ぎ、スケジューラの公平性と応答性を向上させます。

コミット

commit bc31bcccd3b94ec8dd324e523c4c7ae9180b937f
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Fri Jul 19 01:22:26 2013 +0400

    runtime: preempt long-running goroutines
    If a goroutine runs for more than 10ms, preempt it.
    Update #543.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/10796043

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

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

元コミット内容

runtime: preempt long-running goroutines
If a goroutine runs for more than 10ms, preempt it.
Update #543.

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

変更の背景

Goの初期のスケジューラは、協調的プリエンプション（cooperative preemption）に依存していました。これは、ゴルーチンが関数呼び出しなどの「安全なポイント（safe points）」で自発的に実行を中断し、他のゴルーチンにCPUを譲るという方式です。この方式はシンプルでオーバーヘッドが少ないという利点がありましたが、欠点も存在しました。

主な問題点は、関数呼び出しを含まないタイトなループや計算量の多い処理を実行するゴルーチンが、自発的にCPUを譲ることがないため、長時間CPUを占有し続ける可能性があったことです。これにより、他のゴルーチンが実行機会を得られずに飢餓状態に陥ったり、アプリケーション全体の応答性が低下したりする問題が発生していました。特に、CPUバウンドな処理が多いアプリケーションでは、この問題が顕著でした。

この問題は、GoのIssue #543「runtime: preemptive scheduling」で議論されていました。このIssueでは、プリエンプティブスケジューリングの導入により、より公平なCPU時間の割り当て、ライブラリやリクエストのより良い分離と公平性、そして「stop-the-world」方式のガベージコレクション（GC）における長い一時停止の解消といった目標が掲げられていました。

このコミットは、Issue #543で議論されていた問題に対処するための一歩として、長時間実行されるゴルーチンを強制的にプリエンプトするメカニズムを導入し、スケジューラの公平性と応答性を改善することを目的としています。

前提知識の解説

GoのゴルーチンとM:Nスケジューラ

Go言語は、軽量な並行処理の単位として「ゴルーチン（goroutine）」を提供します。ゴルーチンはOSのスレッドよりもはるかに軽量であり、数百万個のゴルーチンを同時に実行することも可能です。

Goのランタイムは、M:Nスケジューラと呼ばれる独自のスケジューラを持っています。これは、M個のゴルーチンをN個のOSスレッド（MはNよりもはるかに大きい）にマッピングして実行する方式です。このスケジューラは、以下の3つの主要な要素で構成されます。

• G (Goroutine): 実行されるゴルーチン。
• M (Machine/OS Thread): OSスレッド。Goのコードを実行する実際のOSスレッド。
• P (Processor/Logical Processor): 論理プロセッサ。Mがゴルーチンを実行するために必要なコンテキスト。Pは実行可能なゴルーチンキューを保持し、Mにゴルーチンをディスパッチします。

M:Nスケジューラは、OSスレッドの切り替えコストを削減し、ゴルーチンの作成・破棄を高速化することで、高い並行性を実現しています。

協調的プリエンプションとプリエンプティブスケジューリング

• 協調的プリエンプション (Cooperative Preemption): この方式では、実行中のタスク（この場合はゴルーチン）が自発的にCPUの制御をスケジューラに返します。Goの場合、これは主に関数呼び出しの際に発生します。関数呼び出しの前に、ランタイムはゴルーチンが長時間実行されているかどうかをチェックし、必要であればプリエンプションを行います。この方式の利点は、実装が比較的簡単で、コンテキストスイッチのオーバーヘッドが少ないことです。しかし、欠点として、関数呼び出しを含まない無限ループのようなCPUバウンドな処理が、他のタスクにCPUを譲らずに実行し続けることで、システム全体の応答性を低下させる可能性があります。

• プリエンプティブスケジューリング (Preemptive Scheduling): この方式では、スケジューラが実行中のタスクの意思に関わらず、強制的にその実行を中断し、別のタスクにCPUを割り当てることができます。これにより、特定のタスクがCPUを独占することを防ぎ、すべてのタスクに公平にCPU時間が割り当てられるようになります。OSのプロセススケジューラは通常、プリエンプティブスケジューリングを採用しています。Goランタイムにおけるプリエンプティブスケジューリングの導入は、協調的プリエンプションの限界を克服し、より堅牢で応答性の高いシステムを実現するために不可欠でした。

Goにおける「安全なポイント」

Goの協調的プリエンプションでは、ゴルーチンは特定の「安全なポイント」でプリエンプションのチェックを行います。これは主に、関数プロローグ（関数の開始時）に挿入されるコードによって実現されます。このコードは、ゴルーチンのスタックガード（gp->stackguard0）が特定のマーカー値（StackPreempt）に設定されているかどうかをチェックします。もし設定されていれば、ランタイムはプリエンプション処理を実行します。

しかし、関数呼び出しを全く行わないタイトなループでは、この安全なポイントに到達しないため、プリエンプションが発生しませんでした。このコミットは、この問題を解決するために、タイマーベースのプリエンプションを導入しています。

技術的詳細

このコミットは、Goランタイムのスケジューラにタイマーベースのプリエンプションメカニズムを導入しています。主要な変更点は以下の通りです。

1. sysmon ゴルーチンによる監視: sysmon (system monitor) ゴルーチンは、Goランタイム内で定期的に実行されるバックグラウンドゴルーチンです。このゴルーチンは、ガベージコレクションのトリガー、ネットワークポーラーの実行、そしてアイドル状態のP（論理プロセッサ）の解放など、様々なランタイムのハウスキーピングタスクを担当しています。このコミットでは、sysmon がプリエンプションのトリガー役も担うようになりました。

2. retake 関数の拡張: sysmon は定期的に retake 関数を呼び出します。元々 retake 関数は、システムコールでブロックされているPを回収する役割を担っていました。このコミットにより、retake 関数は、長時間実行されているゴルーチンをプリエンプトする機能も追加されました。

3. 10ミリ秒のタイムアウト: retake 関数内で、各Pに割り当てられているゴルーチンが10ミリ秒以上実行されているかどうかがチェックされます。この10ミリ秒という閾値は、Goランタイムがゴルーチンをプリエンプトするかどうかを決定するための基準となります。

4. Pdesc 構造体の導入: 各Pの状態を追跡するために、Pdesc という新しい構造体が導入されました。

   typedef struct Pdesc Pdesc;
   struct Pdesc
   {
       uint32  tick; // Pのtickカウンタ
       int64   when; // Pが最後にtickを更新した時刻 (ナノ秒)
   };
   static Pdesc pdesc[MaxGomaxprocs];
   

   • tick: Pの内部カウンタで、Pがゴルーチンをディスパッチするたびに更新されます。
   • when: sysmon が retake を呼び出した時点の現在時刻（ナノ秒単位）が記録されます。これは、Pが最後に新しいゴルーチンを実行し始めた、または既存のゴルーチンがプリエンプションチェックを通過した時刻の目安となります。

   retake 関数は、各Pの tick カウンタが前回の sysmon 呼び出し時と変わっていないかをチェックします。もし変わっていなければ、そのPに割り当てられたゴルーチンが長時間実行されている可能性が高いと判断されます。

5. プリエンプションのトリガー: retake 関数内で、Pのステータスが Prunning（ゴルーチンが実行中）であり、かつ pd->when + 10*1000*1000 > now（現在の時刻が when から10ミリ秒以上経過している）という条件が満たされた場合、そのPに割り当てられているゴルーチンに対して preemptone(p) が呼び出され、プリエンプションがトリガーされます。

6. preemptone 関数: preemptone(p) 関数は、指定されたPで現在実行中のゴルーチンをプリエンプトするようマークします。具体的には、そのゴルーチンのスタックガード（gp->stackguard0）を StackPreempt という特殊な値に設定します。これにより、次にゴルーチンが関数呼び出しを行う際に、ランタイムがプリエンプションを検出し、ゴルーチンを中断して実行キューに戻すことができます。

7. runtime·newstack の変更: runtime·newstack は、スタックの拡張やプリエンプションの処理を行うランタイム関数です。このコミットでは、runtime·newstack 内のプリエンプションチェックの条件が微調整され、m->p->status != Prunning のチェックが追加されました。これは、MがPに割り当てられていない場合や、Pが実行中ではない場合（例えば、Pがシステムコールでブロックされている場合）にはプリエンプションを行わないようにするためのものです。これにより、ランタイムの内部処理中に不必要なプリエンプションが発生するのを防ぎます。

このメカニズムにより、Goランタイムは、関数呼び出しがないタイトなループであっても、ゴルーチンが一定時間以上CPUを占有することを防ぎ、より公平なスケジューリングを実現します。

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

src/pkg/runtime/proc.c

--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -94,7 +94,7 @@ static void wakep(void);\
 static void stoplockedm(void);\
 static void startlockedm(G*);\
 static void sysmon(void);\
-static uint32 retake(uint32*);\
+static uint32 retake(int64);\
 static void inclocked(int32);\
 static void checkdead(void);\
 static void exitsyscall0(G*);\
@@ -2071,7 +2071,6 @@ sysmon(void)\
 	uint32 idle, delay;\
 	int64 now, lastpoll;\
 	G *gp;\
-\tuint32 ticks[MaxGomaxprocs];\
 \n \tidle = 0;  // how many cycles in succession we had not wokeup somebody\
 \tdelay = 0;\
 @@ -2103,19 +2102,29 @@ sysmon(void)\
 \t\t\tinjectglist(gp);\
 \t\t}\
 \t\t// retake P\'s blocked in syscalls\
-\t\tif(retake(ticks))\
+\t\t// and preempt long running G\'s\
+\t\tif(retake(now))\
 \t\t\tidle = 0;\
 \t\telse\
 \t\t\tidle++;\
 \t}\
 }\
 \n+typedef struct Pdesc Pdesc;\
+struct Pdesc\
+{\n+\tuint32\ttick;\n+\tint64\twhen;\n+};\
+static Pdesc pdesc[MaxGomaxprocs];\
+\n static uint32\
-retake(uint32 *ticks)\
+retake(int64 now)\
 {\n \tuint32 i, s, n;\
 \tint64 t;\
 \tP *p;\
+\tPdesc *pd;\
 \n \tn = 0;\
 \tfor(i = 0; i < runtime·gomaxprocs; i++) {\
@@ -2123,24 +2132,34 @@ retake(uint32 *ticks)\
 \t\tif(p==nil)\
 \t\t\tcontinue;\
 \t\tt = p->tick;\
-\t\tif(ticks[i] != t) {\n-\t\t\tticks[i] = t;\n+\t\tpd = &pdesc[i];\n+\t\tif(pd->tick != t) {\n+\t\t\tpd->tick = t;\n+\t\t\tpd->when = now;\
 \t\t\tcontinue;\
 \t\t}\
 \t\ts = p->status;\
-\t\tif(s != Psyscall)\
-\t\t\tcontinue;\
-\t\tif(p->runqhead == p->runqtail && runtime·atomicload(&runtime·sched.nmspinning) + runtime·atomicload(&runtime·sched.npidle) > 0)  // TODO: fast atomic\
-\t\t\tcontinue;\
-\t\t// Need to increment number of locked M\'s before the CAS.\n-\t\t// Otherwise the M from which we retake can exit the syscall,\n-\t\t// increment nmidle and report deadlock.\n-\t\tinclocked(-1);\n-\t\tif(runtime·cas(&p->status, s, Pidle)) {\n-\t\t\tn++;\n-\t\t\thandoffp(p);\n+\t\tif(s == Psyscall) {\n+\t\t\t// Retake P from syscall if it\'s there for more than 1 sysmon tick (20us).\n+\t\t\t// But only if there is other work to do.\n+\t\t\tif(p->runqhead == p->runqtail &&\n+\t\t\t\truntime·atomicload(&runtime·sched.nmspinning) + runtime·atomicload(&runtime·sched.npidle) > 0)\n+\t\t\t\tcontinue;\n+\t\t\t// Need to increment number of locked M\'s before the CAS.\n+\t\t\t// Otherwise the M from which we retake can exit the syscall,\n+\t\t\t// increment nmidle and report deadlock.\n+\t\t\tinclocked(-1);\n+\t\t\tif(runtime·cas(&p->status, s, Pidle)) {\n+\t\t\t\tn++;\n+\t\t\t\thandoffp(p);\n+\t\t\t}\n+\t\t\tinclocked(1);\n+\t\t} else if(s == Prunning) {\n+\t\t\t// Preempt G if it\'s running for more than 10ms.\n+\t\t\tif(pd->when + 10*1000*1000 > now)\n+\t\t\t\tcontinue;\n+\t\t\tpreemptone(p);\
 \t\t}\
-\t\tinclocked(1);\
 \t}\
 \treturn n;\
 }

src/pkg/runtime/proc_test.go

--- a/src/pkg/runtime/proc_test.go
+++ b/src/pkg/runtime/proc_test.go
@@ -192,6 +192,27 @@ var preempt = func() int {\
 	return sum
 }\
 \n+func TestPreemption(t *testing.T) {\
+\tt.Skip(\"preemption is disabled\")\
+\t// Test that goroutines are preempted at function calls.\
+\tconst N = 5\
+\tc := make(chan bool)\
+\tvar x uint32\
+\tfor g := 0; g < 2; g++ {\
+\t\tgo func(g int) {\
+\t\t\tfor i := 0; i < N; i++ {\
+\t\t\t\tfor atomic.LoadUint32(&x) != uint32(g) {\
+\t\t\t\t\tpreempt()\
+\t\t\t\t}\
+\t\t\t\tatomic.StoreUint32(&x, uint32(1-g))\
+\t\t\t}\
+\t\t\tc <- true\
+\t\t}(g)\
+\t}\
+\t<-c\
+\t<-c\
+}\
+\n func TestPreemptionGC(t *testing.T) {\
 \tt.Skip(\"preemption is disabled\")\
 \t// Test that pending GC preempts running goroutines.\

src/pkg/runtime/stack.c

--- a/src/pkg/runtime/stack.c
+++ b/src/pkg/runtime/stack.c
@@ -244,11 +244,11 @@ runtime·newstack(void)\
 \tif(gp->stackguard0 == (uintptr)StackPreempt) {\
 \t\tif(gp == m->g0)\
 \t\t\truntime·throw(\"runtime: preempt g0\");\
-\t\tif(oldstatus == Grunning && (m->p == nil || m->p->status != Prunning))\
+\t\tif(oldstatus == Grunning && m->p == nil)\
 \t\t\truntime·throw(\"runtime: g is running but p is not\");\
 \t\t// Be conservative about where we preempt.\
 \t\t// We are interested in preempting user Go code, not runtime code.\
-\t\tif(oldstatus != Grunning || m->locks || m->mallocing || m->gcing) {\
+\t\tif(oldstatus != Grunning || m->locks || m->mallocing || m->gcing || m->p->status != Prunning) {\
 \t\t\t// Let the goroutine keep running for now.\
 \t\t\t// gp->preempt is set, so it will be preempted next time.\
 \t\t\tgp->stackguard0 = gp->stackguard;\

コアとなるコードの解説

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

1. retake 関数のシグネチャ変更:

   • 変更前: static uint32 retake(uint32* ticks)
   • 変更後: static uint32 retake(int64 now)
   • retake 関数が、各Pの tick カウンタの配列ではなく、現在の時刻 now を引数として受け取るようになりました。これにより、プリエンプションの判断に時間情報を使用できるようになります。

2. sysmon から ticks 配列の削除:

   • sysmon 関数内の uint32 ticks[MaxGomaxprocs]; が削除されました。これは、Pdesc 構造体がPごとの tick 情報と時間情報を保持するようになったため、不要になったためです。

3. sysmon から retake の呼び出し変更:

   • 変更前: if(retake(ticks))
   • 変更後: if(retake(now))
   • sysmon が retake を呼び出す際に、現在の時刻 now を渡すようになりました。コメント // and preempt long running G's が追加され、retake がプリエンプションの役割も担うことが明示されています。

4. Pdesc 構造体の定義と静的配列の追加:

   typedef struct Pdesc Pdesc;
   struct Pdesc
   {
       uint32  tick;
       int64   when;
   };
   static Pdesc pdesc[MaxGomaxprocs];
   

   • Pdesc 構造体が新しく定義され、tick（Pの内部カウンタ）と when（最後にPが更新された時刻）を保持します。
   • MaxGomaxprocs の数だけ Pdesc の静的配列 pdesc が宣言され、各Pの状態を追跡するために使用されます。

5. retake 関数内のプリエンプションロジック:

   • Pdesc *pd; が追加され、各Pに対応する Pdesc エントリへのポインタとして使用されます。
   • pd = &pdesc[i]; で、現在のPに対応する Pdesc エントリを取得します。
   • if(pd->tick != t) ブロックが追加されました。
     • もしPの tick カウンタが前回の retake 呼び出し時と異なっていれば、そのPは新しいゴルーチンを実行し始めたか、既存のゴルーチンがプリエンプションチェックを通過したことを意味します。この場合、pd->tick = t; で tick を更新し、pd->when = now; で現在の時刻を when に記録し、プリエンプションの対象から外れます。
   • else if(s == Prunning) ブロックが追加されました。
     • Pのステータスが Prunning（ゴルーチンが実行中）の場合に、プリエンプションの条件をチェックします。
     • if(pd->when + 10*1000*1000 > now): pd->when（Pが最後に更新された時刻）に10ミリ秒（10 * 1000 * 1000 ナノ秒）を加えた値が現在の時刻 now よりも大きい場合、つまり10ミリ秒以上経過していない場合は continue してプリエンプションを行いません。
     • preemptone(p);: 10ミリ秒以上経過している場合、preemptone(p) を呼び出して、そのPで実行中のゴルーチンをプリエンプトするようマークします。

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

1. TestPreemption 関数の追加:
   • プリエンプション機能のテストケース TestPreemption が追加されました。
   • このテストは、2つのゴルーチンが atomic.LoadUint32 と atomic.StoreUint32 を使って x の値を交互に更新するタイトなループを実行します。
   • preempt() 関数（おそらくランタイム内部のプリエンプションチェックを模倣する関数）がループ内に含まれています。
   • t.Skip("preemption is disabled") がコメントアウトされており、この時点ではまだプリエンプションが完全に有効になっていないことを示唆しています。しかし、テストコード自体はプリエンプションがどのように機能するかを検証するためのものです。

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

1. runtime·newstack 内のプリエンプション条件の修正:

   • 変更前: if(oldstatus == Grunning && (m->p == nil || m->p->status != Prunning))

   • 変更後: if(oldstatus == Grunning && m->p == nil)

   • この変更は、runtime·newstack がプリエンプションを処理する際の条件を調整しています。特に、m->p->status != Prunning のチェックが削除されました。これは、MがPに割り当てられていない場合（m->p == nil）にのみ、ゴルーチンが実行中であるにもかかわらずPが実行中ではないという矛盾をチェックするように変更されたことを意味します。

   • さらに重要な変更は、その次の行の条件です。

     • 変更前: if(oldstatus != Grunning || m->locks || m->mallocing || m->gcing)
     • 変更後: if(oldstatus != Grunning || m->locks || m->mallocing || m->gcing || m->p->status != Prunning)
     • この変更により、ランタイムの内部処理中（m->locks、m->mallocing、m->gcing が真の場合）や、Pが Prunning 状態ではない場合（m->p->status != Prunning）には、ゴルーチンがプリエンプトされないように保守的なチェックが追加されました。これは、ランタイムの重要なセクションでプリエンプションが発生し、ランタイムの整合性が損なわれるのを防ぐためです。ユーザーコードのプリエンプションにのみ関心があり、ランタイムコードのプリエンプションは避けるべきであるというコメントがその意図を説明しています。

これらの変更により、Goランタイムは、協調的プリエンプションの限界を補完し、より公平で応答性の高いゴルーチンスケジューリングを実現するための重要な一歩を踏み出しました。

関連リンク

• Go CL (Change List): https://golang.org/cl/10796043
• Go Issue #543: https://github.com/golang/go/issues/543

参考にした情報源リンク

• Issue #543 in the golang/go GitHub repository, titled "runtime: preemptive scheduling,"
• The primary goals outlined in this early discussion included providing a more habitual environment for users accustomed to preemptive threads, offering better isolation and fairness for libraries and requests, and eliminating long "stop-the-world" garbage collection pauses
• At the time issue #543 was opened, Go's goroutine scheduler primarily relied on cooperative preemption. This meant that goroutines would voluntarily yield control at specific "safe points," such as function calls
• While this approach worked for many scenarios, it could lead to situations where a goroutine executing a tight, CPU-bound loop without function calls would monopolize a CPU, starving other goroutines
• The Go runtime's preemption mechanism has evolved significantly since the discussion in issue #543. A major advancement came with Go 1.14, which introduced asynchronous preemption