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

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

このコミットは、GoランタイムにおけるCPUの利用率低下（underutilization）の問題を修正することを目的としています。具体的には、Goスケジューラが新しいM（OSスレッド）を起動する際の「意図的なずさんさ」と、それによって発生していたゴルーチン（G）の実行遅延を改善します。特に、スピンしているMが作業を見つけた際に、他のMを起動するように変更することで、CPUのアンダーユースを解消しています。

コミット

commit 32fef9908a6dcd523ae44766717662764e6c14ee
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Thu Jul 11 15:57:36 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.
    This is reincarnation of cl/9776044 with the bug fixed.
    The bug was due to code added after cl/9776044 was created:
    if(tick - (((uint64)tick*0x4325c53fu)>>36)*61 == 0 && runtime·sched.runqsize > 0) {
            runtime·lock(&runtime·sched);\n            gp = globrunqget(m->p, 1);\n            runtime·unlock(&runtime·sched);\n    }\n    If M gets gp from global runq here, it does not reset m->spinning.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/10743044

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

https://github.com/golang/go/commit/32fef9908a6dcd523ae44766717662764e6c14ee

元コミット内容

このコミットは、GoランタイムにおけるCPUの利用率低下を修正します。runtime.newprocやready関数は、新しいM（OSスレッド）を起動する際に意図的に「ずさん」であり、少なくとも1つのスピンしているMが存在することしか保証していませんでした。この問題を補うため、schedule()関数は、現在のP（プロセッサ）にローカルな作業があり、かつスピンしているMがいない場合に、別のMを起動するようにしていました。しかし、ゴルーチンがscheduleを呼び出さない場合、このメカニズムは機能しませんでした。

この変更により、スピンしているMが作業を見つけた際に、別のMを起動するようになります。これは理想的な解決策ではありませんが、CPUの利用率低下を修正します。実行可能なGの正確な数を把握することはコストが高すぎるため、より適切なチェックは困難です。

このコミットは、以前の変更（cl/9776044）の再実装であり、その際に導入されたバグを修正しています。そのバグは、cl/9776044の作成後にschedule関数に追加されたコードが原因でした。具体的には、グローバルな実行キューからゴルーチンを取得した場合に、Mのスピン状態（m->spinning）がリセットされないという問題でした。

変更の背景

Goランタイムのスケジューラは、ゴルーチンを効率的にOSスレッドにマッピングし、CPUリソースを最大限に活用することを目指しています。しかし、このコミットが修正しようとしている問題は、スケジューラの設計上の特定の挙動に起因していました。

従来のGoスケジューラでは、新しいゴルーチンが作成されたり、既存のゴルーチンが実行可能状態になったりする際に、runtime.newprocやreadyといった関数が新しいM（OSスレッド）を起動する役割を担っていました。しかし、これらの関数は「意図的にずさん (deliberately sloppy)」に設計されており、常に最適な数のMを起動するわけではなく、少なくとも1つのMがスピン（アイドル状態で作業を探している状態）していれば十分と判断していました。

この「ずさんさ」を補うため、schedule()関数には、現在のP（論理プロセッサ）にローカルな実行可能なゴルーチンがあり、かつスピンしているMが他にいない場合に、追加のMを起動するというロジックが組み込まれていました。これは、システム全体で利用可能なCPUリソースが十分に活用されていない状況（CPU underutilization）を防ぐための試みでした。

しかし、この補償メカニズムには限界がありました。特に、長時間実行される計算集約的なゴルーチンなど、schedule()関数を頻繁に呼び出さないゴルーチンが存在する場合、このチェックが十分に機能せず、結果としてCPUリソースがアイドル状態になり、全体のパフォーマンスが低下するという問題が発生していました（Fixes #5586）。

このコミットは、このCPU利用率低下の問題に対処するために導入されました。以前の試み（cl/9776044）がありましたが、その後のコード変更によって新たなバグが導入されたため、そのバグを修正しつつ、より堅牢な解決策を提供することが背景にあります。

前提知識の解説

このコミットを理解するためには、Goランタイムのスケジューラが採用している「M, P, G」モデルと、「スピンするM」の概念を理解することが不可欠です。

GoスケジューラのM, P, Gモデル

Goのスケジューラは、以下の3つの主要な要素で構成されています。

  1. G (Goroutine):

    • Goにおける並行処理の最小単位です。非常に軽量なユーザーレベルのスレッドであり、数千から数百万のゴルーチンを同時に実行できます。
    • OSスレッドとは異なり、Goランタイムによって管理されます。
    • 各ゴルーチンは、独自のスタックを持ち、他のゴルーチンと独立して実行されます。

  2. M (Machine):

    • OSスレッド（Operating System Thread）を表します。Goのコードは最終的にOSスレッド上で実行されます。
    • Goランタイムは、必要に応じて複数のMを作成します。これは、一部のMがシステムコール（I/O操作など）でブロックされる可能性があるためです。
    • Mは、Pと関連付けられてGoコードを実行します。

  3. P (Processor):

    • 論理プロセッサ（Logical Processor）を表します。MがGoコードを実行するためのコンテキストを提供します。
    • Pは、ゴルーチンを格納するローカルな実行キュー（run queue）と、メモリキャッシュなどのリソースを保持します。
    • GOMAXPROCS環境変数またはruntime.GOMAXPROCS関数によって設定され、通常は利用可能なCPUコアの数に等しくなります。
    • Mは、Pと関連付けられている間のみGoコードを実行できます。

スケジューラの主な役割は、実行可能なGをMとPに効率的にマッピングすることです。

スピンするM (Spinning M) とCPU利用率低下

MがPと関連付けられており、そのローカルキューやグローバルキューに実行すべきゴルーチンがない場合、Mはすぐにスリープするのではなく、「スピン」状態に入ります。

  • スピン状態: Mがアクティブに作業を探している状態です。具体的には、自身のローカル実行キューを再度確認したり、グローバル実行キューを定期的にチェックしたり、他のPのローカルキューからゴルーチンを「ワークスチール」しようと試みたりします。
  • 目的: スピンの目的は、OSスレッドをスリープさせてから再度起動する際のオーバーヘッド（コンテキストスイッチのコスト）を削減し、レイテンシを低減することです。これにより、ゴルーチンが利用可能になった際に、Mがすぐに実行を開始できるようになります。

しかし、もし本当にMが実行すべき作業を見つけられない場合、このスピンはCPUサイクルを無駄に消費し、CPUの利用率低下につながる可能性があります。Goスケジューラは、この無駄を軽減するために、スピンするMの数を制限したり、長時間作業が見つからないMを最終的にスリープさせたりするメカニズムを持っています。ワークスチールも、システム全体のCPU利用率を向上させるための重要なメカニズムです。

このコミットは、この「スピンするM」が作業を見つけた際に、より積極的に他のMを起動することで、CPUの利用率低下を改善しようとしています。

技術的詳細

このコミットは、Goランタイムのスケジューリングロジック、特にM（OSスレッド）がP（論理プロセッサ）上でゴルーチン（G）を実行する際の挙動を改善します。問題の核心は、runtime.newprocやreadyといった関数が新しいMを起動する際に「意図的にずさん」であるという点にありました。これらの関数は、少なくとも1つのMがスピンしていれば十分と判断し、それ以上のMを積極的に起動しませんでした。

この「ずさんさ」を補うために、schedule()関数には、現在のPにローカルな作業があり、かつスピンしているMが他にいない場合に、別のMを起動するロジックがありました。しかし、このアプローチには以下の問題がありました。

  1. schedule()を呼び出さないゴルーチン: 長時間実行される計算集約的なゴルーチンなど、schedule()を頻繁に呼び出さないゴルーチンが存在する場合、このチェックが機能せず、結果としてCPUリソースがアイドル状態になる可能性がありました。
  2. グローバルキューからの取得時の問題: 以前のcl/9776044の後に導入されたコード（if(tick - ...)ブロック）において、Mがグローバル実行キューからゴルーチン（gp = globrunqget(m->p, 1);）を取得した場合に、m->spinningフラグが適切にリセットされないというバグがありました。これにより、Mが実際にはスピン状態を脱しているにもかかわらず、スケジューラがそのMをスピンしていると誤認し、結果として他のMの起動が抑制され、CPUの利用率低下を引き起こしていました。

このコミットは、これらの問題を解決するために、以下の主要な変更を導入しています。

  • resetspinning関数の導入: 新しい静的関数resetspinning()が導入されました。この関数は、Mがスピン状態を終了する際に呼び出され、m->spinningフラグをfalseに設定し、runtime.sched.nmspinning（スピンしているMの数）をデクリメントします。さらに、nmspinningが0になり、かつアイドル状態のPが存在する場合（runtime.atomicload(&runtime.sched.npidle) > 0）、wakep()を呼び出して別のPを起動し、CPUの利用率を向上させます。
  • schedule()の変更:
    • グローバル実行キューからゴルーチンを取得した場合（gp = globrunqget(m->p, 1);）に、resetspinning()を呼び出すように変更されました。これにより、以前のバグが修正され、Mが作業を見つけた際にスピン状態が正しくリセットされるようになります。
    • findrunnable()が呼び出される前に、Mがスピン状態を終了し、resetspinning()が呼び出されるようにロジックが変更されました。これにより、Mが作業を見つけた際に、より積極的に他のMを起動するようになります。
    • 以前のschedule()内にあった、Pのローカルキューに作業があり、スピンしているMがいない場合にwakep()を呼び出すロジックは削除されました。これは、新しいresetspinning()のロジックがより包括的にこの問題を解決するためです。

この変更により、Mが作業を見つけた際に、より迅速に他のMを起動するようになり、CPUの利用率低下が改善されます。これは、実行可能なGの正確な数を維持するコストが高すぎるため、次善の策ではありますが、実用的な解決策として機能します。

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

このコミットによる主要なコード変更は、src/pkg/runtime/proc.c ファイルと、新しいテストファイルsrc/pkg/runtime/proc_test.go にあります。

src/pkg/runtime/proc.c

  1. resetspinning 関数の追加:

    static void
resetspinning(void)
{
    int32 nmspinning;

    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();
}

    この新しい関数は、Mがスピン状態を終了する際に呼び出され、m->spinningフラグをリセットし、スピンしているMの数を更新します。また、必要に応じて別のPを起動します。

  2. schedule 関数の変更:

    • グローバル実行キューからゴルーチンを取得した場合にresetspinning()を呼び出す行が追加されました。 
      // ...
if(runtime·sched.runqsize > 0) {
    runtime·lock(&runtime·sched);
    gp = globrunqget(m->p, 1);
    runtime·unlock(&runtime·sched);
    if(gp) // <-- ここが追加
        resetspinning(); // <-- ここが追加
}
// ...
    • findrunnable()を呼び出す前にresetspinning()を呼び出すように変更されました。 
      // 変更前:
// if(gp == nil)
//     gp = findrunnable();
//
// if(m->spinning) {
//     m->spinning = false;
//     runtime·xadd(&runtime·sched.nmspinning, -1);
// }
// ...
// 変更後:
if(gp == nil) {
    gp = findrunnable();  // blocks until work is available
    resetspinning(); // <-- ここが追加
}
    • 以前のschedule関数内にあった、Pのローカルキューに作業があり、スピンしているMがいない場合にwakep()を呼び出すロジックが削除されました。 
      // 削除されたコードブロック:
// if (m->p->runqhead != m->p->runqtail &&
//     runtime·atomicload(&runtime·sched.nmspinning) == 0 &&
//     runtime·atomicload(&runtime·sched.npidle) > 0)  // TODO: fast atomic
//     wakep();

src/pkg/runtime/proc_test.go

  1. TestGoroutineParallelism テスト関数の追加: 
    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
        }
    }
}
    この新しいテストは、複数のゴルーチンが同時にスケジュールされ、CPUリソースが適切に利用されていることを検証します。GOMAXPROCSを固定し、アトミック操作を用いてゴルーチンの並行実行をチェックしています。

コアとなるコードの解説

resetspinning 関数

この関数は、Mがスピン状態を終了する際に呼び出されるヘルパー関数です。

  • if(m->spinning): 現在のMがスピン状態にあるかどうかを確認します。
  • m->spinning = false;: Mのスピン状態フラグをfalseに設定し、スピン状態を終了したことを示します。
  • nmspinning = runtime·xadd(&runtime·sched.nmspinning, -1);: グローバルなスピンしているMのカウンタruntime.sched.nmspinningをアトミックにデクリメントします。
  • if(nmspinning < 0) runtime·throw("findrunnable: negative nmspinning");: カウンタが負の値になった場合は、ランタイムエラーをスローします。これは、論理的なエラーを示します。
  • if (nmspinning == 0 && runtime·atomicload(&runtime·sched.npidle) > 0) wakep();: ここが重要なロジックです。もしスピンしているMの数が0になり（つまり、すべてのスピンしていたMが作業を見つけたか、スピンを停止した）、かつアイドル状態のP（論理プロセッサ）が存在する場合、wakep()を呼び出します。wakep()は、新しいMを起動してアイドル状態のPに割り当て、利用可能なCPUリソースを最大限に活用しようとします。これにより、CPUの利用率低下が積極的に解消されます。

schedule 関数の変更点

schedule関数は、Goスケジューラの中心的なループであり、次に実行すべきゴルーチンを見つけて実行する役割を担います。

  • グローバルキューからの取得時のresetspinning呼び出し: 以前のバグは、Mがグローバル実行キューからゴルーチンを取得した場合にm->spinningがリセットされないことでした。この修正により、if(gp)チェックが追加され、ゴルーチンが取得された場合にresetspinning()が呼び出されるようになりました。これにより、Mが作業を見つけた際に、そのスピン状態が正しくクリアされ、スケジューラが他のMを起動する判断を適切に行えるようになります。
  • findrunnable()呼び出し前のresetspinning: schedule関数がfindrunnable()を呼び出すのは、ローカルキューにもグローバルキューにも実行可能なゴルーチンが見つからなかった場合です。findrunnable()は、作業が見つかるまでブロックする可能性があります。この変更により、findrunnable()が呼び出される直前にresetspinning()が呼び出されるようになりました。これは、Mが作業を見つけるためにスピン状態に入り、最終的にfindrunnable()によって作業が見つかった場合に、そのMがスピン状態を終了したことをスケジューラに通知し、必要に応じて他のMを起動する機会を提供します。
  • 古いwakep()ロジックの削除: 以前のschedule関数には、Pのローカルキューに作業があり、スピンしているMがいない場合にwakep()を呼び出すロジックがありました。このロジックは、新しいresetspinning()関数がより包括的にこの問題を解決するため、冗長となり削除されました。

これらの変更により、Goスケジューラは、Mが作業を見つけた際に、より迅速かつ正確にスピン状態を管理し、必要に応じて他のMを起動することで、CPUの利用率低下を効果的に防ぐことができるようになりました。

TestGoroutineParallelism テスト

このテストは、Goランタイムのスケジューラが複数のゴルーチンを並行して、かつ効率的にスケジュールできることを検証します。

  • const P = 4: GOMAXPROCSを4に設定し、4つの論理プロセッサが利用可能であることをシミュレートします。
  • defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(P)): テストの開始時にGOMAXPROCSをPに設定し、テスト終了時に元の値に戻します。
  • for try := 0; try < 10; try++: テストを10回繰り返すことで、様々なスケジューリングのシナリオをカバーし、再現性の低いバグを検出する可能性を高めます。
  • done := make(chan bool): 各ゴルーチンの完了を待つためのチャネルです。
  • x := uint32(0): 複数のゴルーチン間で共有されるアトミックなカウンタです。
  • go func(p int) { ... }(p): Pの数だけゴルーチンを起動します。各ゴルーチンは、自身のp（プロセッサIDのようなもの）に基づいて期待されるxの値を計算し、xがその値になるまでスピン待機します。その後、xをインクリメントします。
  • for atomic.LoadUint32(&x) != expected { }: これは、ゴルーチンが特定の順序で実行されることを保証するためのスピン待機です。これにより、すべてのPが同時にアクティブになり、並行処理が正しく行われているかを検証します。
  • atomic.StoreUint32(&x, expected+1): xをアトミックに更新します。
  • <-done: すべてのゴルーチンが完了するのを待ちます。

このテストは、スケジューラがP個のゴルーチンを同時に実行できる能力、特にCPUの利用率が低下しないように、すべてのPが適切に活用されていることを確認するために設計されています。

関連リンク

  • Go Change-Id: I2222222222222222222222222222222222222222 (これはコミットメッセージに記載されているhttps://golang.org/cl/10743044に対応するGoのコードレビューシステム上のIDです。実際のリンクはhttps://go-review.googlesource.com/c/go/+/10743044となります。)
  • Fixes #5586: https://github.com/golang/go/issues/5586 (Go issue tracker上の関連する問題)

参考にした情報源リンク