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

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

このコミットは、GoランタイムにおけるCPUのアンダーユーティライゼーション（CPU利用率の低下）の問題を修正することを目的としています。具体的には、Goスケジューラが新しいM（OSスレッド）を起動する際の挙動を改善し、利用可能なG（ゴルーチン）があるにもかかわらずCPUがアイドル状態になる状況を解消します。

コミット

commit 15a1c3d1e46393a0b05ef5f518d1f4d0b7c638b8
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Thu Jun 27 20:52:12 2013 +0400

    runtime: fix CPU underutilization
    runtime.newproc/ready are deliberately sloppy about waking new M's,
    they only ensure that there is at least 1 spinning M.
    Currently to compensate for that, schedule() checks if the current P
    has local work and there are no spinning M's, it wakes up another one.
    It does not work if goroutines do not call schedule.
    With this change a spinning M wakes up another M when it finds work to do.
    It's also not ideal, but it fixes the underutilization.
    A proper check would require to know the exact number of runnable G's,
    but it's too expensive to maintain.
    Fixes #5586.
    
    R=rsc
    CC=gobot, golang-dev
    https://golang.org/cl/9776044

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

https://github.com/golang/go/commit/15a1c3d1e46393a0b05ef5f518d1f4d0b7c638b8

元コミット内容

Goランタイムのruntime.newprocやready関数は、新しいM（OSスレッド）を起動する際に意図的に緩やかな挙動をしており、少なくとも1つのスピニングM（アイドル状態で作業を探しているM）が存在することのみを保証していました。この挙動を補うため、schedule()関数は、現在のP（プロセッサ）にローカルな作業があり、かつスピニングMが存在しない場合に、別のMを起動していました。しかし、この方法はゴルーチンがscheduleを呼び出さない場合には機能しませんでした。

このコミットによる変更では、スピニングMが作業を見つけたときに別のMを起動するようになります。これも理想的な解決策ではありませんが、アンダーユーティライゼーションの問題を修正します。実行可能なG（ゴルーチン）の正確な数を把握することは、維持コストが高すぎるため、適切なチェックは困難です。この変更はIssue #5586を修正します。

変更の背景

Goランタイムのスケジューラは、G（ゴルーチン）、P（プロセッサ）、M（OSスレッド）という3つの主要な抽象化を用いて並行処理を管理します。MはOSスレッドを表し、PはMがGを実行するためのコンテキストを提供します。Gは軽量な実行単位であるゴルーチンです。

従来のGoスケジューラでは、runtime.newproc（新しいゴルーチンを作成する）やready（ゴルーチンを実行可能状態にする）といった関数が、新しいMを起動する際に「少なくとも1つのスピニングMがあれば十分」という緩いポリシーを採用していました。スピニングMとは、実行可能なゴルーチンを探してアイドル状態にあるMのことです。

このポリシーの欠点を補うため、schedule()関数（ゴルーチンが実行を中断し、別のゴルーチンに切り替える際に呼び出される）は、現在のPにローカルな実行可能なゴルーチンがあり、かつスピニングMがいない場合に、追加のMを起動するロジックを持っていました。しかし、この補償メカニズムは、ゴルーチンが明示的にschedule()を呼び出さないような状況（例えば、計算量の多いループで長時間実行されるゴルーチンなど）では機能しませんでした。その結果、実行可能なゴルーチンが存在するにもかかわらず、利用可能なMが不足し、CPUが十分に活用されない（アンダーユーティライゼーション）問題が発生していました。

このコミットは、このCPUアンダーユーティライゼーションの問題を解決するために導入されました。特に、Issue #5586で報告された問題に対処しています。

前提知識の解説

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

  1. G (Goroutine):

    • Goにおける並行実行の単位です。非常に軽量で、数百万個のゴルーチンを同時に実行できます。
    • Goの関数呼び出しの前にgoキーワードを付けることで作成されます。
    • OSスレッドではなく、Goランタイムによって管理されるユーザーレベルのスレッドのようなものです。

  2. M (Machine/OS Thread):

    • OSが提供する実際の実行スレッドです。
    • Goランタイムは、必要に応じてMを作成し、OSにスケジューリングを委ねます。
    • MはPにアタッチされ、Pが提供するコンテキスト上でGを実行します。
    • スピニングM: 実行可能なGを探しているが、まだGを見つけていないアイドル状態のMを指します。CPUを消費してGを探し続けるため、「スピニング」と呼ばれます。

  3. P (Processor):

    • MがGを実行するための論理的なプロセッサ（コンテキスト）です。
    • Pの数は通常、GOMAXPROCS環境変数によって制御され、デフォルトではCPUの論理コア数に設定されます。
    • 各Pは、実行可能なGのローカルキュー（runq）を持っています。
    • MはPにアタッチされている間のみGを実行できます。PはMとGの間の仲介役として機能します。

  4. スケジューリングの基本的な流れ:

    • Goランタイムは、実行可能なGをPのローカルキューまたはグローバルキューに配置します。
    • MはPにアタッチされ、PのローカルキューからGを取り出して実行します。
    • ローカルキューが空の場合、Mは他のPのローカルキューからGを「スティール（盗む）」しようとします。
    • それでもGが見つからない場合、MはグローバルキューやネットワークI/Oなど、他の場所からGを探します。
    • 最終的にGが見つからない場合、Mはスピニング状態になるか、ブロックされます。

  5. runtime.newproc / runtime.ready:

    • runtime.newprocは新しいゴルーチンを作成し、実行可能状態にします。
    • runtime.readyは、ブロックされていたゴルーチンを実行可能状態に戻します。
    • これらの関数は、新しいゴルーチンが利用可能になったときに、必要に応じて新しいMを起動する役割も担いますが、このコミット以前は「少なくとも1つのスピニングMがあれば十分」という緩いポリシーでした。

  6. schedule():

    • 現在実行中のゴルーチンが自発的に実行を中断し、別のゴルーチンに制御を渡す際に呼び出される関数です。
    • Goランタイムのプリエンプティブスケジューリング（Go 1.14以降）とは異なり、これは協調的なスケジューリングポイントです。

このコミットは、特にMが新しい作業を見つけたときに、他のMを適切に起動するメカニズムを改善することで、CPUのアンダーユーティライゼーションを解消しようとしています。

技術的詳細

このコミットの核心は、runtime/proc.c内のfindrunnable関数の変更と、schedule関数のロジックの簡素化にあります。

変更前のアプローチの問題点

コミットメッセージにあるように、以前のGoスケジューラでは、runtime.newprocやreadyが新しいMを起動する際に「少なくとも1つのスピニングMがあれば十分」というポリシーを採用していました。これは、Mの過剰な起動を防ぐための意図的な「緩さ」でした。

この緩さを補うため、schedule()関数内に以下のロジックがありました。

if (m->p->runqhead != m->p->runqtail &&
    runtime·atomicload(&runtime·sched.nmspinning) == 0 &&
    runtime·atomicload(&runtime·sched.npidle) > 0)
    wakep();

このコードは、現在のPにローカルな実行可能なゴルーチンがあり（m->p->runqhead != m->p->runqtail）、かつスピニングMがいない（runtime·atomicload(&runtime·sched.nmspinning) == 0）、そしてアイドル状態のPがある（runtime·atomicload(&runtime·sched.npidle) > 0）場合に、wakep()を呼び出して別のP（とそれにアタッチされるM）を起動しようとします。

しかし、このアプローチには以下の問題がありました。

  • schedule()が呼ばれない場合: 計算量の多いループなど、ゴルーチンが長時間schedule()を呼び出さない場合、この補償ロジックが実行されず、新しいMが起動されないままCPUがアイドル状態になる可能性がありました。
  • スピニングMの役割: スピニングMは作業を探しているMですが、作業を見つけたときに他のMを積極的に起動する役割が明確ではありませんでした。

変更後のアプローチ

このコミットでは、findrunnable関数の役割が変更され、スピニングMが作業を見つけたときに、必要に応じて他のMを起動する責任を負うようになりました。

  1. findrunnable1の導入:

    • 元のfindrunnable関数はfindrunnable1にリネームされました。この関数は、実行可能なゴルーチンを見つけるまでブロックする純粋なロジックを担当します。
    • つまり、findrunnable1は、ゴルーチンが見つかるまで、他のPからのスティール、グローバルキューのチェック、ネットワークポーリングなどを試み、最終的に見つからなければブロックします。

  2. 新しいfindrunnableの導入:

    • 新しいfindrunnable関数が導入され、これがfindrunnable1を呼び出すラッパーとなります。
    • この新しいfindrunnableの主な役割は、findrunnable1がゴルーチンを見つけて戻ってきたときに、現在のMがスピニング状態であったかどうかをチェックし、必要に応じて他のMを起動することです。
    static G*
findrunnable(void)
{
    G *gp;
    int32 nmspinning;

    gp = findrunnable1();  // blocks until work is available
    if(m->spinning) {
        m->spinning = false;
        nmspinning = runtime·xadd(&runtime·sched.nmspinning, -1);
        if(nmspinning < 0)
            runtime·throw("findrunnable: negative nmspinning");
    } else
        nmspinning = runtime·atomicload(&runtime·sched.nmspinning);

    // M wakeup policy is deliberately somewhat conservative (see nmspinning handling),
    // so see if we need to wakeup another P here.
    if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0)
        wakep();

    return gp;
}
    • gp = findrunnable1();: まず、実行可能なゴルーチンを探します。この呼び出しは、作業が見つかるまでブロックする可能性があります。
    • if(m->spinning) { ... }: findrunnable1から戻ってきたMが以前スピニング状態であった場合、m->spinningフラグをfalseに設定し、スピニングMの数をデクリメントします。これは、このMがもはやアイドル状態ではなく、作業を見つけたことを示します。
    • if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0) wakep();: ここが重要な変更点です。もし、作業を見つけたMがスピニング状態を終了し、その結果スピニングMの数が0になり（nmspinning == 0）、かつアイドル状態のPが存在する場合（runtime·atomicload(&runtime·sched.npidle) > 0）、wakep()を呼び出して別のPを起動します。これにより、他のアイドル状態のPが作業を開始できるようになります。

  3. schedule()の簡素化:

    • schedule()関数から、以前存在したMの起動ロジックが削除されました。
    • これにより、Mの起動責任がschedule()からfindrunnableに移管され、より一貫性のあるMの起動ポリシーが実現されます。schedule()は純粋にゴルーチンの切り替えに集中できるようになります。

この変更による効果

  • CPUアンダーユーティライゼーションの修正: スピニングMが作業を見つけたときに、他のMを積極的に起動するようになったため、実行可能なゴルーチンがあるにもかかわらずCPUがアイドル状態になる状況が減少します。これにより、CPUの利用率が向上します。
  • スケジューラのロジックの明確化: Mの起動ポリシーがfindrunnableに集約され、scheduleからそのロジックが削除されたことで、スケジューラの各コンポーネントの役割がより明確になりました。
  • Issue #5586の修正: この変更は、GoランタイムのCPUアンダーユーティライゼーションに関する既知の問題（Issue #5586）を直接的に解決します。

テストケースの追加

src/pkg/runtime/proc_test.goにTestGoroutineParallelismという新しいテストケースが追加されました。このテストは、複数のP（プロセッサ）が同時にゴルーチンをスケジュールできることを検証します。

func TestGoroutineParallelism(t *testing.T) {
    const P = 4
    defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(P))
    for try := 0; try < 10; try++ {
        done := make(chan bool)
        x := uint32(0)
        for p := 0; p < P; p++ {
            // Test that all P goroutines are scheduled at the same time
            go func(p int) {
                for i := 0; i < 3; i++ {
                    expected := uint32(P*i + p)
                    for atomic.LoadUint32(&x) != expected {
                    }
                    atomic.StoreUint32(&x, expected+1)
                }
                done <- true
            }(p)
        }
        for p := 0; p < P; p++ {
            <-done
        }
    }
}

このテストは、P個のゴルーチンを同時に起動し、atomic.LoadUint32とatomic.StoreUint32を使って共有変数xを特定の順序で更新できることを確認します。もしスケジューラが適切に並行性を活用できていなければ、このテストはデッドロックしたり、タイムアウトしたりする可能性があります。このテストの追加は、今回の変更が意図した並行実行の改善をもたらしたことを検証するものです。

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

src/pkg/runtime/proc.c

  • findrunnable関数がfindrunnable1にリネームされました。
  • 新しいfindrunnable関数が追加され、findrunnable1を呼び出し、スピニングMの管理とMの起動ロジックを含みます。
  • schedule関数から、Mの起動に関するロジックが削除されました。
--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -1018,7 +1018,7 @@ execute(G *gp)
 // Finds a runnable goroutine to execute.
 // Tries to steal from other P's, get g from global queue, poll network.
 static G*
-findrunnable(void)
+findrunnable1(void)
 {
 	G *gp;
 	P *p;
@@ -1127,6 +1127,29 @@ stop:
 	goto top;
 }
 
+static G*
+findrunnable(void)
+{
+	G *gp;
+	int32 nmspinning;
+
+	gp = findrunnable1();  // blocks until work is available
+	if(m->spinning) {
+		m->spinning = false;
+		nmspinning = runtime·xadd(&runtime·sched.nmspinning, -1);
+		if(nmspinning < 0)
+			runtime·throw("findrunnable: negative nmspinning");
+	} else
+		nmspinning = runtime·atomicload(&runtime·sched.nmspinning);
+
+	// M wakeup policy is deliberately somewhat conservative (see nmspinning handling),
+	// so see if we need to wakeup another P here.
+	if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0)
+		wakep();
+
+	return gp;
+}
+
 // Injects the list of runnable G's into the scheduler.
 // Can run concurrently with GC.
 static void
@@ -1185,21 +1208,11 @@ top:
 		runtime·throw("schedule: spinning with local work");
 	}
 	if(gp == nil)
-		gp = findrunnable();
-
-	if(m->spinning) {
-		m->spinning = false;
-		runtime·xadd(&runtime·sched.nmspinning, -1);
-	}
-
-	// M wakeup policy is deliberately somewhat conservative (see nmspinning handling),
-	// so see if we need to wakeup another M here.
-	if (m->p->runqhead != m->p->runqtail &&
-		runtime·atomicload(&runtime·sched.nmspinning) == 0 &&
-		runtime·atomicload(&runtime·sched.npidle) > 0)  // TODO: fast atomic
-		wakep();
+		gp = findrunnable();  // blocks until work is available
 
 	if(gp->lockedm) {
+		// Hands off own p to the locked m,
+		// then blocks waiting for a new p.
 		startlockedm(gp);
 		goto top;
 	}

src/pkg/runtime/proc_test.go

  • TestGoroutineParallelismという新しいテスト関数が追加されました。
--- a/src/pkg/runtime/proc_test.go
+++ b/src/pkg/runtime/proc_test.go
@@ -93,6 +93,30 @@ func TestYieldLocked(t *testing.T) {
 	<-c
 }
 
+func TestGoroutineParallelism(t *testing.T) {
+	const P = 4
+	defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(P))
+	for try := 0; try < 10; try++ {
+		done := make(chan bool)
+		x := uint32(0)
+		for p := 0; p < P; p++ {
+			// Test that all P goroutines are scheduled at the same time
+			go func(p int) {
+				for i := 0; i < 3; i++ {
+					expected := uint32(P*i + p)
+					for atomic.LoadUint32(&x) != expected {
+					}
+					atomic.StoreUint32(&x, expected+1)
+				}
+				done <- true
+			}(p)
+		}
+		for p := 0; p < P; p++ {
+			<-done
+		}
+	}
+}
+
 func TestBlockLocked(t *testing.T) {
 	const N = 10
 	c := make(chan bool)

コアとなるコードの解説

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

  1. findrunnableからfindrunnable1へのリネーム:

    • 元のfindrunnable関数は、実行可能なゴルーチンを見つけるための主要なロジック（ローカルキュー、スティール、グローバルキュー、ネットワークポーリングなど）を含んでいました。このコミットでは、その純粋な検索ロジックをfindrunnable1という名前に分離しました。これにより、関数の責務が明確になります。

  2. 新しいfindrunnable関数の導入:

    • この新しいfindrunnable関数は、findrunnable1を呼び出して実際に実行可能なゴルーチンを取得します。
    • gp = findrunnable1();: ここで、Mは実行可能なGが見つかるまでブロックする可能性があります。
    • if(m->spinning) { ... }: findrunnable1からGが返された場合、現在のMが以前「スピニング」状態（つまり、作業を探してアイドル状態だった）であったかどうかをチェックします。もしそうであれば、このMはもはやスピニング状態ではないため、m->spinning = false;を設定し、グローバルなスピニングMのカウンタruntime·sched.nmspinningをデクリメントします。これにより、ランタイムは現在スピニングしているMの正確な数を把握できます。
    • if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0) wakep();: この行が、CPUアンダーユーティライゼーションを修正する主要なロジックです。
      • nmspinning == 0: 現在のMがスピニング状態を終了した結果、スピニングしているMが他に誰もいなくなったことを意味します。
      • runtime·atomicload(&runtime·sched.npidle) > 0: アイドル状態のP（プロセッサ）がまだ存在することを示します。
      • この両方の条件が真である場合、つまり、作業を見つけたMがスピニング状態を終了し、他にスピニングしているMがおらず、かつアイドル状態のPがある場合、wakep()を呼び出します。wakep()は、アイドル状態のPを起動し、それに新しいMをアタッチして、そのPが実行可能なゴルーチンを探し始めるように促します。これにより、利用可能なCPUリソースが最大限に活用され、アンダーユーティライゼーションが防止されます。

  3. schedule関数からのM起動ロジックの削除:

    • 変更前は、schedule関数内に、現在のPにローカルな作業があり、スピニングMがいない場合にwakep()を呼び出すロジックがありました。
    • このコミットでは、そのロジックがscheduleから削除されました。これにより、Mの起動に関する責任がfindrunnableに一元化され、scheduleは純粋にゴルーチンの切り替えと、必要に応じてfindrunnableを呼び出すことに集中するようになりました。この分離により、スケジューラの設計がよりクリーンになります。

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

  1. TestGoroutineParallelismの追加:
    • このテストは、Goスケジューラが複数のCPUコア（P）を効率的に利用し、並行してゴルーチンを実行できることを検証するために追加されました。
    • const P = 4: テストで使用するPの数を4に設定しています。これは、GOMAXPROCSが4に設定されることを意味します。
    • defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(P)): テストの開始時にGOMAXPROCSをPに設定し、テスト終了後に元の値に戻すことで、テスト環境をクリーンに保ちます。
    • x := uint32(0): 複数のゴルーチン間で共有されるアトミックなカウンタです。
    • for p := 0; p < P; p++ { go func(p int) { ... }(p) }: P個のゴルーチンを起動します。各ゴルーチンは、自身のp（0からP-1）に基づいて、xが特定のexpected値になるのを待ち、その後xをインクリメントします。
    • for atomic.LoadUint32(&x) != expected { }: 各ゴルーチンは、xが期待する値になるまでスピンループで待機します。これは、他のゴルーチンが先にxを更新するのを待つための同期メカニズムです。
    • atomic.StoreUint32(&x, expected+1): xが期待する値になったら、そのゴルーチンはxをインクリメントします。
    • このテストは、すべてのゴルーチンが並行して進行し、xが期待通りに更新されることを保証します。もしスケジューラがCPUをアンダーユースしている場合、ゴルーチンがブロックされたり、テストがタイムアウトしたりする可能性があります。このテストの成功は、今回の変更が並行実行の効率を改善したことを示します。

これらの変更により、Goランタイムは、実行可能なゴルーチンが存在する際に、より積極的にOSスレッド（M）を起動し、CPUリソースを最大限に活用できるようになりました。

関連リンク

参考にした情報源リンク

  • Go Issue #5586の議論
  • Goランタイムスケジューラに関する一般的なドキュメントと解説
  • Goのソースコード（src/pkg/runtime/proc.cおよびsrc/pkg/runtime/proc_test.go）
  • Goのsync/atomicパッケージに関するドキュメント
  • GoのGOMAXPROCSに関するドキュメント

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

このコミットは、GoランタイムにおけるCPUのアンダーユーティライゼーション（CPU利用率の低下）の問題を修正することを目的としています。具体的には、Goスケジューラが新しいM（OSスレッド）を起動する際の挙動を改善し、利用可能なG（ゴルーチン）があるにもかかわらずCPUがアイドル状態になる状況を解消します。

コミット

commit 15a1c3d1e46393a0b05ef5f518d1f4d0b7c638b8
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Thu Jun 27 20:52:12 2013 +0400

    runtime: fix CPU underutilization
    runtime.newproc/ready are deliberately sloppy about waking new M's,
    they only ensure that there is at least 1 spinning M.
    Currently to compensate for that, schedule() checks if the current P
    has local work and there are no spinning M's, it wakes up another one.
    It does not work if goroutines do not call schedule.
    With this change a spinning M wakes up another M when it finds work to do.
    It's also not ideal, but it fixes the underutilization.
    A proper check would require to know the exact number of runnable G's,
    but it's too expensive to maintain.
    Fixes #5586.
    
    R=rsc
    CC=gobot, golang-dev
    https://golang.org/cl/9776044

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

https://github.com/golang/go/commit/15a1c3d1e46393a0b05ef5f518d1f4d0b7c638b8

元コミット内容

Goランタイムのruntime.newprocやready関数は、新しいM（OSスレッド）を起動する際に意図的に緩やかな挙動をしており、少なくとも1つのスピニングM（アイドル状態で作業を探しているM）が存在することのみを保証していました。この挙動を補うため、schedule()関数は、現在のP（プロセッサ）にローカルな作業があり、かつスピニングMが存在しない場合に、別のMを起動していました。しかし、この方法はゴルーチンがscheduleを呼び出さない場合には機能しませんでした。

このコミットによる変更では、スピニングMが作業を見つけたときに別のMを起動するようになります。これも理想的な解決策ではありませんが、アンダーユーティライゼーションの問題を修正します。実行可能なG（ゴルーチン）の正確な数を把握することは、維持コストが高すぎるため、適切なチェックは困難です。この変更はIssue #5586を修正します。

変更の背景

Goランタイムのスケジューラは、G（ゴルーチン）、P（プロセッサ）、M（OSスレッド）という3つの主要な抽象化を用いて並行処理を管理します。MはOSスレッドを表し、PはMがGを実行するためのコンテキストを提供します。Gは軽量な実行単位であるゴルーチンです。

従来のGoスケジューラでは、runtime.newproc（新しいゴルーチンを作成する）やready（ゴルーチンを実行可能状態にする）といった関数が、新しいMを起動する際に「少なくとも1つのスピニングMがあれば十分」という緩いポリシーを採用していました。スピニングMとは、実行可能なゴルーチンを探してアイドル状態にあるMのことです。

このポリシーの欠点を補うため、schedule()関数（ゴルーチンが実行を中断し、別のゴルーチンに切り替える際に呼び出される）は、現在のPにローカルな実行可能なゴルーチンがあり、かつスピニングMがいない場合に、追加のMを起動するロジックを持っていました。しかし、この補償メカニズムは、ゴルーチンが明示的にschedule()を呼び出さないような状況（例えば、計算量の多いループで長時間実行されるゴルーチンなど）では機能しませんでした。その結果、実行可能なゴルーチンが存在するにもかかわらず、利用可能なMが不足し、CPUが十分に活用されない（アンダーユーティライゼーション）問題が発生していました。

このコミットは、このCPUアンダーユーティライゼーションの問題を解決するために導入されました。特に、Issue #5586で報告された問題に対処しています。

前提知識の解説

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

  1. G (Goroutine):

    • Goにおける並行実行の単位です。非常に軽量で、数百万個のゴルーチンを同時に実行できます。
    • Goの関数呼び出しの前にgoキーワードを付けることで作成されます。
    • OSスレッドではなく、Goランタイムによって管理されるユーザーレベルのスレッドのようなものです。

  2. M (Machine/OS Thread):

    • OSが提供する実際の実行スレッドです。
    • Goランタイムは、必要に応じてMを作成し、OSにスケジューリングを委ねます。
    • MはPにアタッチされ、Pが提供するコンテキスト上でGを実行します。
    • スピニングM: 実行可能なGを探しているが、まだGを見つけていないアイドル状態のMを指します。CPUを消費してGを探し続けるため、「スピニング」と呼ばれます。

  3. P (Processor):

    • MがGを実行するための論理的なプロセッサ（コンテキスト）です。
    • Pの数は通常、GOMAXPROCS環境変数によって制御され、デフォルトではCPUの論理コア数に設定されます。
    • 各Pは、実行可能なGのローカルキュー（runq）を持っています。
    • MはPにアタッチされている間のみGを実行できます。PはMとGの間の仲介役として機能します。

  4. スケジューリングの基本的な流れ:

    • Goランタイムは、実行可能なGをPのローカルキューまたはグローバルキューに配置します。
    • MはPにアタッチされ、PのローカルキューからGを取り出して実行します。
    • ローカルキューが空の場合、Mは他のPのローカルキューからGを「スティール（盗む）」しようとします。
    • それでもGが見つからない場合、MはグローバルキューやネットワークI/Oなど、他の場所からGを探します。
    • 最終的にGが見つからない場合、Mはスピニング状態になるか、ブロックされます。

  5. runtime.newproc / runtime.ready:

    • runtime.newprocは新しいゴルーチンを作成し、実行可能状態にします。
    • runtime.readyは、ブロックされていたゴルーチンを実行可能状態に戻します。
    • これらの関数は、新しいゴルーチンが利用可能になったときに、必要に応じて新しいMを起動する役割も担いますが、このコミット以前は「少なくとも1つのスピニングMがあれば十分」という緩いポリシーでした。

  6. schedule():

    • 現在実行中のゴルーチンが自発的に実行を中断し、別のゴルーチンに制御を渡す際に呼び出される関数です。
    • Goランタイムのプリエンプティブスケジューリング（Go 1.14以降）とは異なり、これは協調的なスケジューリングポイントです。

このコミットは、特にMが新しい作業を見つけたときに、他のMを適切に起動するメカニズムを改善することで、CPUのアンダーユーティライゼーションを解消しようとしています。

技術的詳細

このコミットの核心は、runtime/proc.c内のfindrunnable関数の変更と、schedule関数のロジックの簡素化にあります。

変更前のアプローチの問題点

コミットメッセージにあるように、以前のGoスケジューラでは、runtime.newprocやreadyが新しいMを起動する際に「少なくとも1つのスピニングMがあれば十分」というポリシーを採用していました。これは、Mの過剰な起動を防ぐための意図的な「緩さ」でした。

この緩さを補うため、schedule()関数内に以下のロジックがありました。

if (m->p->runqhead != m->p->runqtail &&
    runtime·atomicload(&runtime·sched.nmspinning) == 0 &&
    runtime·atomicload(&runtime·sched.npidle) > 0)
    wakep();

このコードは、現在のPにローカルな実行可能なゴルーチンがあり（m->p->runqhead != m->p->runqtail）、かつスピニングMがいない（runtime·atomicload(&runtime·sched.nmspinning) == 0）、そしてアイドル状態のPがある（runtime·atomicload(&runtime·sched.npidle) > 0）場合に、wakep()を呼び出して別のP（とそれにアタッチされるM）を起動しようとします。

しかし、このアプローチには以下の問題がありました。

  • schedule()が呼ばれない場合: 計算量の多いループなど、ゴルーチンが長時間schedule()を呼び出さない場合、この補償ロジックが実行されず、新しいMが起動されないままCPUがアイドル状態になる可能性がありました。
  • スピニングMの役割: スピニングMは作業を探しているMですが、作業を見つけたときに他のMを積極的に起動する役割が明確ではありませんでした。

変更後のアプローチ

このコミットでは、findrunnable関数の役割が変更され、スピニングMが作業を見つけたときに、必要に応じて他のMを起動する責任を負うようになりました。

  1. findrunnable1の導入:

    • 元のfindrunnable関数はfindrunnable1にリネームされました。この関数は、実行可能なゴルーチンを見つけるまでブロックする純粋なロジックを担当します。
    • つまり、findrunnable1は、ゴルーチンが見つかるまで、他のPからのスティール、グローバルキューのチェック、ネットワークポーリングなどを試み、最終的に見つからなければブロックします。

  2. 新しいfindrunnableの導入:

    • 新しいfindrunnable関数が導入され、これがfindrunnable1を呼び出すラッパーとなります。
    • この新しいfindrunnableの主な役割は、findrunnable1がゴルーチンを見つけて戻ってきたときに、現在のMがスピニング状態であったかどうかをチェックし、必要に応じて他のMを起動することです。
    static G*
findrunnable(void)
{
    G *gp;
    int32 nmspinning;

    gp = findrunnable1();  // blocks until work is available
    if(m->spinning) {
        m->spinning = false;
        nmspinning = runtime·xadd(&runtime·sched.nmspinning, -1);
        if(nmspinning < 0)
            runtime·throw("findrunnable: negative nmspinning");
    } else
        nmspinning = runtime·atomicload(&runtime·sched.nmspinning);

    // M wakeup policy is deliberately somewhat conservative (see nmspinning handling),
    // so see if we need to wakeup another P here.
    if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0)
        wakep();

    return gp;
}
    • gp = findrunnable1();: まず、実行可能なゴルーチンを探します。この呼び出しは、作業が見つかるまでブロックする可能性があります。
    • if(m->spinning) { ... }: findrunnable1から戻ってきたMが以前スピニング状態であった場合、m->spinningフラグをfalseに設定し、スピニングMの数をデクリメントします。これは、このMがもはやアイドル状態ではなく、作業を見つけたことを示します。
    • if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0) wakep();: ここが重要な変更点です。もし、作業を見つけたMがスピニング状態を終了し、その結果スピニングMの数が0になり（nmspinning == 0）、かつアイドル状態のPが存在する場合（runtime·atomicload(&runtime·sched.npidle) > 0）、wakep()を呼び出して別のPを起動します。これにより、他のアイドル状態のPが作業を開始できるようになります。

  3. schedule()の簡素化:

    • schedule()関数から、以前存在したMの起動ロジックが削除されました。
    • これにより、Mの起動責任がschedule()からfindrunnableに移管され、より一貫性のあるMの起動ポリシーが実現されます。schedule()は純粋にゴルーチンの切り替えに集中できるようになります。

この変更による効果

  • CPUアンダーユーティライゼーションの修正: スピニングMが作業を見つけたときに、他のMを積極的に起動するようになったため、実行可能なゴルーチンがあるにもかかわらずCPUがアイドル状態になる状況が減少します。これにより、CPUの利用率が向上します。
  • スケジューラのロジックの明確化: Mの起動ポリシーがfindrunnableに集約され、scheduleからそのロジックが削除されたことで、スケジューラの各コンポーネントの役割がより明確になりました。
  • Issue #5586の修正: この変更は、GoランタイムのCPUアンダーユーティライゼーションに関する既知の問題（Issue #5586）を直接的に解決します。

テストケースの追加

src/pkg/runtime/proc_test.goにTestGoroutineParallelismという新しいテストケースが追加されました。このテストは、複数のP（プロセッサ）が同時にゴルーチンをスケジュールできることを検証します。

func TestGoroutineParallelism(t *testing.T) {
    const P = 4
    defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(P))
    for try := 0; try < 10; try++ {
        done := make(chan bool)
        x := uint32(0)
        for p := 0; p < P; p++ {
            // Test that all P goroutines are scheduled at the same time
            go func(p int) {
                for i := 0; i < 3; i++ {
                    expected := uint32(P*i + p)
                    for atomic.LoadUint32(&x) != expected {
                    }
                    atomic.StoreUint32(&x, expected+1)
                }
                done <- true
            }(p)
        }
        for p := 0; p < P; p++ {
            <-done
        }
    }
}

このテストは、P個のゴルーチンを同時に起動し、atomic.LoadUint32とatomic.StoreUint32を使って共有変数xを特定の順序で更新できることを確認します。もしスケジューラが適切に並行性を活用できていなければ、このテストはデッドロックしたり、タイムアウトしたりする可能性があります。このテストの追加は、今回の変更が意図した並行実行の改善をもたらしたことを検証するものです。

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

src/pkg/runtime/proc.c

  • findrunnable関数がfindrunnable1にリネームされました。
  • 新しいfindrunnable関数が追加され、findrunnable1を呼び出し、スピニングMの管理とMの起動ロジックを含みます。
  • schedule関数から、Mの起動に関するロジックが削除されました。
--- a/src/pkg/runtime/proc.c
+++ b/src/pkg/runtime/proc.c
@@ -1018,7 +1018,7 @@ execute(G *gp)
 // Finds a runnable goroutine to execute.
 // Tries to steal from other P's, get g from global queue, poll network.
 static G*
-findrunnable(void)
+findrunnable1(void)
 {
 	G *gp;
 	P *p;
@@ -1127,6 +1127,29 @@ stop:
 	goto top;
 }
 
+static G*
+findrunnable(void)
+{
+	G *gp;
+	int32 nmspinning;
+
+	gp = findrunnable1();  // blocks until work is available
+	if(m->spinning) {
+		m->spinning = false;
+		nmspinning = runtime·xadd(&runtime·sched.nmspinning, -1);
+		if(nmspinning < 0)
+			runtime·throw("findrunnable: negative nmspinning");
+	} else
+		nmspinning = runtime·atomicload(&runtime·sched.nmspinning);
+
+	// M wakeup policy is deliberately somewhat conservative (see nmspinning handling),
+	// so see if we need to wakeup another P here.
+	if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0)
+		wakep();
+
+	return gp;
+}
+
 // Injects the list of runnable G's into the scheduler.
 // Can run concurrently with GC.
 static void
@@ -1185,21 +1208,11 @@ top:
 		runtime·throw("schedule: spinning with local work");
 	}
 	if(gp == nil)
-		gp = findrunnable();
-
-	if(m->spinning) {
-		m->spinning = false;
-		runtime·xadd(&runtime·sched.nmspinning, -1);
-	}
-
-	// M wakeup policy is deliberately somewhat conservative (see nmspinning handling),
-	// so see if we need to wakeup another M here.
-	if (m->p->runqhead != m->p->runqtail &&
-		runtime·atomicload(&runtime·sched.nmspinning) == 0 &&
-		runtime·atomicload(&runtime·sched.npidle) > 0)  // TODO: fast atomic
-		wakep();
+		gp = findrunnable();  // blocks until work is available
 
 	if(gp->lockedm) {
+		// Hands off own p to the locked m,
+		// then blocks waiting for a new p.
 		startlockedm(gp);
 		goto top;
 	}

src/pkg/runtime/proc_test.go

  • TestGoroutineParallelismという新しいテスト関数が追加されました。
--- a/src/pkg/runtime/proc_test.go
+++ b/src/pkg/runtime/proc_test.go
@@ -93,6 +93,30 @@ func TestYieldLocked(t *testing.T) {
 	<-c
 }
 
+func TestGoroutineParallelism(t *testing.T) {
+	const P = 4
+	defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(P))
+	for try := 0; try < 10; try++ {
+		done := make(chan bool)
+		x := uint32(0)
+		for p := 0; p < P; p++ {
+			// Test that all P goroutines are scheduled at the same time
+			go func(p int) {
+				for i := 0; i < 3; i++ {
+					expected := uint32(P*i + p)
+					for atomic.LoadUint32(&x) != expected {
+					}
+					atomic.StoreUint32(&x, expected+1)
+				}
+				done <- true
+			}(p)
+		}
+		for p := 0; p < P; p++ {
+			<-done
+		}
+	}
+}
+
 func TestBlockLocked(t *testing.T) {
 	const N = 10
 	c := make(chan bool)

コアとなるコードの解説

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

  1. findrunnableからfindrunnable1へのリネーム:

    • 元のfindrunnable関数は、実行可能なゴルーチンを見つけるための主要なロジック（ローカルキュー、スティール、グローバルキュー、ネットワークポーリングなど）を含んでいました。このコミットでは、その純粋な検索ロジックをfindrunnable1という名前に分離しました。これにより、関数の責務が明確になります。

  2. 新しいfindrunnable関数の導入:

    • この新しいfindrunnable関数は、findrunnable1を呼び出して実際に実行可能なゴルーチンを取得します。
    • gp = findrunnable1();: ここで、Mは実行可能なGが見つかるまでブロックする可能性があります。
    • if(m->spinning) { ... }: findrunnable1からGが返された場合、現在のMが以前「スピニング」状態（つまり、作業を探してアイドル状態だった）であったかどうかをチェックします。もしそうであれば、このMはもはやスピニング状態ではないため、m->spinning = false;を設定し、グローバルなスピニングMのカウンタruntime·sched.nmspinningをデクリメントします。これにより、ランタイムは現在スピニングしているMの正確な数を把握できます。
    • if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0) wakep();: この行が、CPUアンダーユーティライゼーションを修正する主要なロジックです。
      • nmspinning == 0: 現在のMがスピニング状態を終了した結果、スピニングしているMが他に誰もいなくなったことを意味します。
      • runtime·atomicload(&runtime·sched.npidle) > 0: アイドル状態のP（プロセッサ）がまだ存在することを示します。
      • この両方の条件が真である場合、つまり、作業を見つけたMがスピニング状態を終了し、他にスピニングしているMがおらず、かつアイドル状態のPがある場合、wakep()を呼び出します。wakep()は、アイドル状態のPを起動し、それに新しいMをアタッチして、そのPが実行可能なゴルーチンを探し始めるように促します。これにより、利用可能なCPUリソースが最大限に活用され、アンダーユーティライゼーションが防止されます。

  3. schedule関数からのM起動ロジックの削除:

    • 変更前は、schedule関数内に、現在のPにローカルな作業があり、スピニングMがいない場合にwakep()を呼び出すロジックがありました。
    • このコミットでは、そのロジックがscheduleから削除されました。これにより、Mの起動に関する責任がfindrunnableに一元化され、scheduleは純粋にゴルーチンの切り替えと、必要に応じてfindrunnableを呼び出すことに集中するようになりました。この分離により、スケジューラの設計がよりクリーンになります。

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

  1. TestGoroutineParallelismの追加:
    • このテストは、Goスケジューラが複数のCPUコア（P）を効率的に利用し、並行してゴルーチンを実行できることを検証するために追加されました。
    • const P = 4: テストで使用するPの数を4に設定しています。これは、GOMAXPROCSが4に設定されることを意味します。
    • defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(P)): テストの開始時にGOMAXPROCSをPに設定し、テスト終了後に元の値に戻すことで、テスト環境をクリーンに保ちます。
    • x := uint32(0): 複数のゴルーチン間で共有されるアトミックなカウンタです。
    • for p := 0; p < P; p++ { go func(p int) { ... }(p) }: P個のゴルーチンを起動します。各ゴルーチンは、自身のp（0からP-1）に基づいて、xが特定のexpected値になるのを待ち、その後xをインクリメントします。
    • for atomic.LoadUint32(&x) != expected { }: 各ゴルーチンは、xが期待する値になるまでスピンループで待機します。これは、他のゴルーチンが先にxを更新するのを待つための同期メカニズムです。
    • atomic.StoreUint32(&x, expected+1): xが期待する値になったら、そのゴルーチンはxをインクリメントします。
    • このテストは、すべてのゴルーチンが並行して進行し、xが期待通りに更新されることを保証します。もしスケジューラがCPUをアンダーユースしている場合、ゴルーチンがブロックされたり、テストがタイムアウトしたりする可能性があります。このテストの成功は、今回の変更が並行実行の効率を改善したことを示します。

これらの変更により、Goランタイムは、実行可能なゴルーチンが存在する際に、より積極的にOSスレッド（M）を起動し、CPUリソースを最大限に活用できるようになりました。

関連リンク

参考にした情報源リンク

  • Go Issue #5586の議論
  • Goランタイムスケジューラに関する一般的なドキュメントと解説
  • Goのソースコード（src/pkg/runtime/proc.cおよびsrc/pkg/runtime/proc_test.go）
  • Goのsync/atomicパッケージに関するドキュメント
  • GoのGOMAXPROCSに関するドキュメント