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

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

このコミットは、Goランタイムにおけるゴルーチンのプリエンプション（横取り）メカニズムを改善し、より信頼性の高いものにすることを目的としています。特に、ブロッキングしないcgo呼び出しやシステムコールを周期的に実行するゴルーチンが、スケジューラによって適切にプリエンプトされない可能性があった問題を解決します。この変更により、スケジューラのティックとシステムコールのティックが分離され、このような状況が防止されます。

コミット

commit f9066fe1c0a7181242f77d8534e0b6e112c982a9
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Aug 13 22:14:04 2013 +0400

    runtime: more reliable preemption
    Currently it's possible that a goroutine
    that periodically executes non-blocking
    cgo/syscalls is never preempted.
    This change splits scheduler and syscall
    ticks to prevent such situation.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/12658045

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

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

元コミット内容

runtime: more reliable preemption
Currently it's possible that a goroutine
that periodically executes non-blocking
cgo/syscalls is never preempted.
This change splits scheduler and syscall
ticks to prevent such situation.

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

変更の背景

Goランタイムのスケジューラは、複数のゴルーチンが利用可能な論理プロセッサ（P）上で公平に実行されるように設計されています。この公平性を保証するための一つのメカニズムが「プリエンプション（preemption）」です。プリエンプションとは、実行中のゴルーチンが一定時間以上CPUを占有した場合に、スケジューラがそのゴルーチンの実行を中断し、別のゴルーチンにCPUを割り当てる機能です。これにより、一部のゴルーチンがCPUを独占し、他のゴルーチンが飢餓状態になることを防ぎます。

しかし、このコミット以前のGoランタイムでは、特定のシナリオにおいてプリエンプションがうまく機能しない問題がありました。具体的には、ブロッキングしないcgo呼び出し（C言語の関数をGoから呼び出す）やシステムコールを周期的に実行するゴルーチンが、スケジューラによって適切にプリエンプトされない可能性がありました。

従来のプリエンプションメカニズムでは、P構造体内のtickという単一のカウンタを使用して、スケジューラの活動とシステムコールの活動の両方を追跡していました。このtickは、ゴルーチンが実行されるたび、またはシステムコールから復帰するたびにインクリメントされていました。問題は、ブロッキングしないシステムコールやcgo呼び出しが非常に高速に完了する場合、ゴルーチンがシステムコールからすぐに戻り、tickが頻繁にインクリメントされるため、スケジューラがそのゴルーチンを「長時間実行されている」と認識しにくくなる点にありました。結果として、そのゴルーチンはプリエンプションの対象と見なされず、他のゴルーチンにCPUを譲ることなく実行し続ける可能性があったのです。これは、特にCPUバウンドな処理とI/Oバウンドな処理が混在するアプリケーションにおいて、パフォーマンスの偏りや応答性の低下を引き起こす可能性がありました。

このコミットは、この問題を解決するために、スケジューラの活動とシステムコールの活動を別々のカウンタで追跡するように変更することで、より信頼性の高いプリエンプションを実現しようとしています。

前提知識の解説

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

  1. ゴルーチン (Goroutine): Goにおける軽量な並行実行単位です。OSのスレッドよりもはるかに軽量で、数百万個のゴルーチンを同時に実行することも可能です。
  2. Goスケジューラ: Goランタイムの心臓部であり、ゴルーチンをOSスレッドにマッピングし、実行を管理します。Goスケジューラは、M（Machine）、P（Processor）、G（Goroutine）という3つの主要な要素で構成される「M-P-Gモデル」を採用しています。
    • G (Goroutine): 実行されるコードとスタックを持つゴルーチンそのものです。
    • M (Machine): OSスレッドを表します。MはPと関連付けられ、そのP上でGを実行します。
    • P (Processor): 論理プロセッサを表します。PはMにCPU時間を提供し、実行可能なGのキュー（ローカル実行キュー）を保持します。GOMAXPROCS環境変数によってPの数が決定されます。
  3. プリエンプション (Preemption): 実行中のゴルーチンが一定時間以上CPUを占有した場合に、スケジューラがそのゴルーチンの実行を中断し、別のゴルーチンにCPUを割り当てるメカニズムです。これにより、ゴルーチンの公平な実行が保証されます。Goのプリエンプションは協調的プリエンプションと非協調的プリエンプションの両方を含みますが、このコミットが対象としているのは、主に非協調的プリエンプションに関連する部分です。
  4. システムコール (System Call): プログラムがOSの機能（ファイルI/O、ネットワーク通信など）を利用するためにOSカーネルに発行する要求です。
  5. cgo: GoプログラムからC言語のコードを呼び出すためのメカニズムです。cgo呼び出しは、内部的にはシステムコールと同様にOSスレッドの切り替えを伴う場合があります。
  6. P構造体: Goランタイム内部で論理プロセッサの状態を管理する構造体です。この構造体には、現在実行中のゴルーチン、ローカル実行キュー、そしてプリエンプションに関連するカウンタなどが含まれます。

技術的詳細

このコミットの核心は、P構造体内のtickカウンタをschedtickとsyscalltickの2つに分割した点にあります。

  • schedtick: スケジューラがゴルーチンをP上で実行するたびにインクリメントされるカウンタです。これは、ゴルーチンがCPU時間をどれだけ消費しているかを追跡するために使用されます。
  • syscalltick: ゴルーチンがシステムコールから復帰するたびにインクリメントされるカウンタです。これは、ゴルーチンがシステムコールにどれだけ頻繁に出入りしているかを追跡するために使用されます。

この分離により、スケジューラはゴルーチンのCPU使用状況とシステムコールへの出入り状況を独立して監視できるようになります。

具体的な変更点は以下の通りです。

  1. P構造体の変更 (src/pkg/runtime/runtime.h):

    • 既存のuint32 tick;が削除され、代わりにuint32 schedtick;とuint32 syscalltick;が追加されました。

  2. Pdesc構造体の変更 (src/pkg/runtime/proc.c):

    • Pdescは、sysmon（システムモニター）ゴルーチンがプリエンプションの判断に使用する、各Pの状態を記録するための構造体です。
    • ここでも、uint32 tick;とint64 when;が削除され、uint32 schedtick;、int64 schedwhen;、uint32 syscalltick;、int64 syscallwhen;が追加されました。whenは、最後にtickが更新された時刻を記録していました。

  3. execute関数の変更 (src/pkg/runtime/proc.c):

    • ゴルーチンがP上で実行を開始する際に、m->p->tick++がm->p->schedtick++に変更されました。これにより、ゴルーチンの実行開始がschedtickのインクリメントに直接関連付けられます。

  4. runtime·exitsyscall関数の変更 (src/pkg/runtime/proc.c):

    • ゴルーチンがシステムコールから復帰する際に、m->p->tick++がm->p->syscalltick++に変更されました。これにより、システムコールからの復帰がsyscalltickのインクリメントに直接関連付けられます。

  5. retake関数の変更 (src/pkg/runtime/proc.c):

    • retake関数はsysmonゴルーチンによって定期的に呼び出され、プリエンプションやシステムコールからのPの奪還を判断します。
    • システムコールからのPの奪還ロジック:
      • PがPsyscall（システムコール中）状態にある場合、p->syscalltickとpd->syscalltick（Pdescに記録された前回のsyscalltick）を比較します。
      • もしsyscalltickが更新されていれば、ゴルーチンはシステムコールから復帰したばかりなので、Pを奪還する必要はありません。pd->syscallwhenも更新されます。
      • syscalltickが更新されておらず、かつPが一定時間以上システムコールに留まっている場合（pd->syscallwhenとnowの比較）、Pを奪還して他のゴルーチンに割り当てます。
    • 実行中のゴルーチンのプリエンプションロジック:
      • PがPrunning（ゴルーチン実行中）状態にある場合、p->schedtickとpd->schedtickを比較します。
      • もしschedtickが更新されていれば、ゴルーチンは最近実行を開始したばかりなので、プリエンプトする必要はありません。pd->schedwhenも更新されます。
      • schedtickが更新されておらず、かつゴルーチンが10ms以上実行されている場合（pd->schedwhen + 10*1000*1000 > nowの条件が偽になる場合）、preemptone(p)を呼び出してゴルーチンをプリエンプトします。

この変更により、ブロッキングしないシステムコールを頻繁に実行するゴルーチンであっても、schedtickの更新が滞ることで、スケジューラがそのゴルーチンを「長時間実行されている」と正しく認識し、プリエンプションの対象とすることができるようになりました。これにより、ゴルーチンの公平性が向上し、特定のゴルーチンがCPUを独占する状況が緩和されます。

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

src/pkg/runtime/proc.c

--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -1085,7 +1085,7 @@ execute(G *gp)
 	gp->status = Grunning;
 	gp->preempt = false;
 	gp->stackguard0 = gp->stackguard;
-	m->p->tick++;
+	m->p->schedtick++;
 	m->curg = gp;
 	gp->m = m;
 
@@ -1272,7 +1272,7 @@ top:
 	// 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.
-	tick = m->p->tick;
+	tick = m->p->schedtick;
 	// 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) {
@@ -1440,7 +1440,6 @@ void
 	}
 
 	m->mcache = nil;
-	m->p->tick++;
 	m->p->m = nil;
 	runtime·atomicstore(&m->p->status, Psyscall);
 	if(runtime·gcwaiting) {
@@ -1509,7 +1508,7 @@ runtime·exitsyscall(void)
 
 	if(exitsyscallfast()) {
 		// There's a cpu for us, so we can run.
-		m->p->tick++;
+		m->p->syscalltick++;
 		g->status = Grunning;
 		// Garbage collector isn't running (since we are),
 		// so okay to clear gcstack and gcsp.
@@ -1539,6 +1538,7 @@ runtime·exitsyscall(void)
 	// is not running.
 	g->syscallstack = (uintptr)nil;
 	g->syscallsp = (uintptr)nil;
+	m->p->syscalltick++;
 }
 
 #pragma textflag NOSPLIT
@@ -2282,8 +2282,10 @@ sysmon(void)
 typedef struct Pdesc Pdesc;
 struct Pdesc
 {
-	uint32	tick;
-	int64	when;
+	uint32	schedtick;
+	int64	schedwhen;
+	uint32	syscalltick;
+	int64	syscallwhen;
 };
 static Pdesc pdesc[MaxGomaxprocs];
 
@@ -2300,17 +2302,17 @@ retake(int64 now)
 		tp = runtime·allp[i];
 		if(p==nil)
 			continue;
-		tt = p->tick;
 		pd = &pdesc[i];
-		if(pd->tick != t) {
-			pd->tick = t;
-			pd->when = now;
-			continue;
-		}
 		s = p->status;
 		if(s == Psyscall) {
 			// Retake P from syscall if it's there for more than 1 sysmon tick (20us).
 			// But only if there is other work to do.
+			tt = p->syscalltick;
+			if(pd->syscalltick != t) {
+				pd->syscalltick = t;
+				pd->syscallwhen = now;
+				continue;
+			}
 			if(p->runqhead == p->runqtail &&
 			runtime·atomicload(&runtime·sched.nmspinning) + runtime·atomicload(&runtime·sched.npidle) > 0)
 				continue;
@@ -2326,7 +2328,13 @@ retake(int64 now)
 			incidlelocked(1);
 		} else if(s == Prunning) {
 			// Preempt G if it's running for more than 10ms.
-			if(pd->when + 10*1000*1000 > now)
+			tt = p->schedtick;
+			if(pd->schedtick != t) {
+				pd->schedtick = t;
+				pd->schedwhen = now;
+				continue;
+			}
+			if(pd->schedwhen + 10*1000*1000 > now)
 				continue;
 			preemptone(p);
 		}

src/pkg/runtime/runtime.h

--- a/src/pkg/runtime/runtime.h
+++ b/src/pkg/runtime/runtime.h
@@ -361,9 +361,10 @@ struct P
 {
 	Lock;
 
-	uint32	status;  // one of Pidle/Prunning/...
+	uint32	status;	// one of Pidle/Prunning/...
 	P*	link;
-	uint32	tick;   // incremented on every scheduler or system call
+	uint32	schedtick;	// incremented on every scheduler call
+	uint32	syscalltick;	// incremented on every system call
 	M*	m;	// back-link to associated M (nil if idle)
 	MCache*	mcache;

コアとなるコードの解説

上記の差分は、Goランタイムのスケジューラがゴルーチンの実行とシステムコールからの復帰を追跡する方法を根本的に変更しています。

  1. P構造体 (src/pkg/runtime/runtime.h):

    • tickフィールドは、以前はスケジューラの活動とシステムコールの活動の両方を追跡する汎用カウンタでした。
    • これをschedtickとsyscalltickに分割することで、それぞれの活動を独立して監視できるようになりました。
      • schedtick: ゴルーチンがP上で実行を開始するたびにインクリメントされます。これは、ゴルーチンがCPUをどれだけ占有しているかを示す指標となります。
      • syscalltick: ゴルーチンがシステムコールから復帰するたびにインクリメントされます。これは、ゴルーチンがシステムコールにどれだけ頻繁に出入りしているかを示す指標となります。

  2. execute関数 (src/pkg/runtime/proc.c):

    • execute関数は、スケジューラがゴルーチンをP上で実行状態にする際に呼び出されます。
    • m->p->tick++がm->p->schedtick++に変更されたことで、ゴルーチンの実行開始がschedtickのインクリメントに直接結びつけられるようになりました。これにより、スケジューラはゴルーチンが実際にCPU上で実行されている時間をより正確に追跡できます。

  3. runtime·exitsyscall関数 (src/pkg/runtime/proc.c):

    • runtime·exitsyscall関数は、ゴルーチンがシステムコールからGoランタイムに戻る際に呼び出されます。
    • m->p->tick++がm->p->syscalltick++に変更されたことで、システムコールからの復帰がsyscalltickのインクリメントに結びつけられるようになりました。これにより、システムコールへの出入りの頻度を正確に把握できます。

  4. Pdesc構造体とretake関数 (src/pkg/runtime/proc.c):

    • Pdesc構造体は、sysmonゴルーチンが各Pの状態を監視するために使用するスナップショットのようなものです。以前は単一のtickとwhen（最終更新時刻）を持っていましたが、これもschedtick/schedwhenとsyscalltick/syscallwhenに分割されました。
    • retake関数は、sysmonゴルーチンによって定期的に呼び出され、Pのプリエンプションや奪還を判断します。
      • システムコールからのPの奪還: 以前は単一のtickで判断していましたが、syscalltickを使用するように変更されました。これにより、システムコールから頻繁に復帰するゴルーチンであっても、syscalltickが更新され続けるため、Pがシステムコールに「長時間留まっている」と誤って判断されることがなくなりました。Pが実際にシステムコールでブロッキングしている場合にのみ、Pが奪還される可能性が高まります。
      • 実行中のゴルーチンのプリエンプション: 以前は単一のtickで判断していましたが、schedtickを使用するように変更されました。これにより、ゴルーチンがCPU上で実際に実行されている時間に基づいてプリエンプションが判断されるようになります。ブロッキングしないシステムコールを頻繁に呼び出すゴルーチンは、システムコールからすぐに戻るためsyscalltickは頻繁に更新されますが、schedtickの更新はゴルーチンがCPU上で実行されている間だけなので、スケジューラはゴルーチンがCPUを長時間占有していることを正しく認識し、プリエンプトできるようになります。

この変更は、Goランタイムのスケジューラの公平性と応答性を向上させる上で重要な役割を果たします。特に、CPUバウンドな処理とI/Oバウンドな処理が混在するアプリケーションにおいて、よりスムーズなゴルーチンの切り替えと全体的なパフォーマンスの改善が期待できます。

関連リンク

  • Goスケジューラに関する公式ドキュメントやブログ記事（当時のものがあれば）
  • Goのプリエンプションに関する議論や設計ドキュメント

参考にした情報源リンク