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

このコミットは、Go言語のランタイムにおけるスケジューラの大規模な変更に向けた準備の一環として、重要な内部構造の更新と新しいキューの導入を行っています。特に、ゴルーチン（G）の再利用メカニズムとプロセッサ（P）の管理方法に焦点を当てた変更が含まれています。

コミット

commit 6cdfb00f4ed2abcbe4dd58dd640a584c17484a61
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Wed Feb 27 21:17:53 2013 +0200

    runtime: more changes in preparation to the new scheduler
    add per-P cache of dead G's
    add global runnable queue (not used for now)
    add list of idle P's (not used for now)
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/7397061

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

https://github.com/golang/go/commit/6cdfb00f4ed2abcbe4dd58dd640a584c17484a61

元コミット内容

このコミットは、Goランタイムのスケジューラを刷新するためのさらなる変更を導入しています。具体的には、以下の要素が追加されています。

PごとのデッドG（ゴルーチン）キャッシュの追加: 各論理プロセッサ（P）が、終了したゴルーチンを再利用するために独自のキャッシュを持つようになりました。
グローバルな実行可能キューの追加: 現時点では使用されていませんが、実行可能なゴルーチンを管理するためのグローバルなキューが導入されました。
アイドル状態のPのリストの追加: 現時点では使用されていませんが、アイドル状態の論理プロセッサ（P）を追跡するためのリストが導入されました。

これらの変更は、Goスケジューラのパフォーマンスとスケーラビリティを向上させることを目的とした、より広範な取り組みの一部です。

変更の背景

このコミットが行われた2013年2月は、Go言語がバージョン1.1のリリースに向けて開発が進められていた時期にあたります。Go 1.1では、Goスケジューラに大きな改善が加えられ、特にM:Nスケジューリングモデルの効率化と、マルチコア環境でのパフォーマンス向上が図られました。

以前のGoスケジューラは、ゴルーチンの生成と終了が頻繁に行われるワークロードにおいて、グローバルなロックの競合がボトルネックとなることがありました。特に、終了したゴルーチンを再利用するためのgfreeリスト（デッドゴルーチンのキャッシュ）がグローバルに一つしかなかったため、複数のM（OSスレッド）やP（論理プロセッサ）が同時にこのリストにアクセスしようとすると、ロックの競合が発生し、スループットが低下する可能性がありました。

このコミットは、その問題に対処し、新しいスケジューラ設計の基盤を築くための重要なステップです。Pごとのキャッシュを導入することで、ローカルなゴルーチン再利用の効率を高め、グローバルロックへの依存を減らすことを目指しています。また、グローバルな実行可能キューやアイドルPのリストの導入は、将来的にゴルーチンの負荷分散やPの効率的な割り当てを改善するための布石と考えられます。

前提知識の解説

このコミットを理解するためには、Go言語のランタイムとスケジューラの基本的な概念を把握しておく必要があります。

ゴルーチン (Goroutine: G): Go言語における軽量な実行単位です。OSスレッドよりもはるかに軽量で、数百万個のゴルーチンを同時に実行することも可能です。Goランタイムがゴルーチンのスケジューリングを管理します。
論理プロセッサ (Processor: P): Goスケジューラにおける論理的なコンテキストです。Goプログラムが同時に実行できるゴルーチンの数を制限します。通常、GOMAXPROCS環境変数によって設定され、デフォルトではCPUのコア数に等しくなります。各Pは、実行可能なゴルーチンのローカルキューを持ち、そのキューからゴルーチンを取り出して実行します。
OSスレッド (Machine: M): GoランタイムがOSから取得する実際のOSスレッドです。MはPにアタッチされ、Pが管理するゴルーチンを実行します。Mがゴルーチンを実行している間、そのMはPを占有します。Mがシステムコールなどでブロックされると、そのMはPを解放し、別のMがそのPを引き継いでゴルーチンを実行し続けることができます。
M:N スケジューリング: Goスケジューラは、M個のOSスレッドをN個のゴルーチンに多重化するM:Nスケジューリングモデルを採用しています。これにより、OSスレッドの数を抑えつつ、多数のゴルーチンを効率的に実行できます。
デッドGのキャッシュ (gfreeリスト): 終了したゴルーチンはすぐにメモリから解放されるのではなく、再利用のためにキャッシュされます。これにより、新しいゴルーチンを生成する際のメモリ割り当てと初期化のオーバーヘッドを削減できます。以前は、このキャッシュがグローバルなSched構造体内に一つだけ存在していました。
ランタイムロック: Goランタイムの内部データ構造（スケジューラの状態、メモリ管理など）は、複数のMから同時にアクセスされる可能性があるため、整合性を保つためにロックによって保護されています。グローバルなデータ構造へのアクセスが増えると、ロックの競合が発生し、並列性が低下する可能性があります。

技術的詳細

このコミットの技術的な核心は、Goスケジューラの主要なデータ構造であるSchedとPの変更、およびゴルーチンとPの管理ロジックの再構築にあります。

`Sched`構造体の変更

src/pkg/runtime/proc.c内のSched構造体から、グローバルなデッドGリストであるgfreeが削除されました。代わりに、以下の新しいフィールドが追加されています。

P* pidle; と uint32 npidle;: アイドル状態のP（論理プロセッサ）を管理するためのリストとそのカウンタです。Pが実行するゴルーチンがなくなり、アイドル状態になった場合にこのリストに追加され、必要に応じて再利用されます。
G* runqhead;, G* runqtail;, int32 runqsize;: グローバルな実行可能ゴルーチンキューです。このキューは、Pのローカルキューが空になった場合や、ゴルーチンがP間で移動する必要がある場合に使用されることが想定されます。コミットメッセージにあるように、この時点ではまだ使用されていませんが、将来のスケジューラ設計において重要な役割を果たすことになります。
Lock gflock; と G* gfree;: 新しいグローバルなデッドGキャッシュです。以前のgfreeとは異なり、このグローバルキャッシュへのアクセスはgflockという専用のロックによって保護されます。これは、Pごとのキャッシュが導入された後も、Pのキャッシュが溢れた場合や、Pのキャッシュが空の場合にグローバルキャッシュを利用するためのものです。

`P`構造体の変更

src/pkg/runtime/runtime.h内のP構造体には、以下のフィールドが追加されました。

P* link;: Pをリスト（特にpidleリスト）に連結するために使用されます。
G* gfree; と int32 gfreecnt;: これがこのコミットの最も重要な変更点の一つです。各Pが独自のデッドGキャッシュを持つようになりました。これにより、ゴルーチンの生成と終了が頻繁に行われる際に、Pはまず自身のローカルキャッシュからゴルーチンを取得または解放しようとします。これにより、グローバルロックの競合が大幅に削減され、スループットが向上します。
byte pad[64];: キャッシュラインアライメントのためのパディングです。これにより、異なるPのデータが同じキャッシュラインに配置されることによる「フォルスシェアリング」を防ぎ、キャッシュ効率を向上させます。

ゴルーチンキャッシュ管理ロジックの変更 (`gfput`, `gfget`, `gfpurge`)

gfput(P *p, G *gp): ゴルーチンgpをデッドGキャッシュに戻す関数です。
- まず、ゴルーチンを引数で渡されたPのローカルキャッシュ（p->gfree）に追加します。
- もしPのローカルキャッシュのサイズ（p->gfreecnt）が一定の閾値（例: 64）を超えた場合、ローカルキャッシュからゴルーチンの一部（例: 32個）をグローバルなgfreeリストに移動させます。この際、グローバルなgflockを取得して競合を防ぎます。
gfget(P *p): デッドGキャッシュからゴルーチンを取得する関数です。
- まず、引数で渡されたPのローカルキャッシュ（p->gfree）からゴルーチンを取得しようとします。
- もしローカルキャッシュが空の場合、グローバルなgfreeリストからゴルーチンをバッチで（例: 32個）取得し、それをPのローカルキャッシュに補充します。この際、グローバルなgflockを取得します。
gfpurge(P *p): 新しく追加された関数で、Pのローカルキャッシュにある全てのデッドGをグローバルなgfreeリストに移動させます。これは、Pがシャットダウンされる際などに、残っているゴルーチンをグローバルに回収するために使用される可能性があります。

グローバルキューとアイドルPリストの管理ロジックの追加

globrunqput(G *gp) と globrunqget(P *p): グローバルな実行可能キューにゴルーチンを追加したり、そこからゴルーチンを取得したりするための関数です。globrunqgetは、グローバルキューからゴルーチンをバッチで取得し、Pのローカル実行可能キューに補充するロジックを含んでいます。
pidleput(P *p) と pidleget(): アイドル状態のPをpidleリストに追加したり、そこから取得したりするための関数です。

これらの変更は、Goスケジューラがより分散化され、ロックの競合を減らし、マルチコア環境でのパフォーマンスを最大化するための重要な基盤を構築しています。特に、Pごとのキャッシュの導入は、ゴルーチンのライフサイクル管理におけるホットスポットを解消する上で極めて効果的です。

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

このコミットで変更された主要なファイルとコードの変更箇所は以下の通りです。

src/pkg/runtime/proc.c

Sched構造体:

G *gfree; の削除。

以下のフィールドの追加:

P p;  // temporary
P* pidle;  // idle P's
uint32 npidle;
// Global runnable queue.
G* runqhead;
G* runqtail;
int32 runqsize;
// Global cache of dead G's.
Lock gflock;
G* gfree;

関数プロトタイプ宣言の変更/追加:
- static void gfput(G*); から static void gfput(P*, G*); へ変更。
- static G* gfget(void); から static G* gfget(P*); へ変更。
- static void gfpurge(P*); の追加。
- static void globrunqput(G*); の追加。
- static G* globrunqget(P*); の追加。
- static P* pidleget(void); の追加。
- static void pidleput(P*); の追加。
schedule関数内のgfput呼び出し:
- gfput(gp); から gfput(&runtime·sched.p, gp); へ変更。
runtime·newproc1関数内のgfget呼び出し:
- gfget() から gfget(&runtime·sched.p); へ変更。
gfput関数の実装:
- 引数にP *pが追加され、Pのローカルキャッシュにゴルーチンを格納するロジックが追加されました。
- ローカルキャッシュが一定サイズを超えた場合に、グローバルキャッシュにバッチで移動させるロジックが追加されました。
gfget関数の実装:
- 引数にP *pが追加され、Pのローカルキャッシュからゴルーチンを取得するロジックが追加されました。
- ローカルキャッシュが空の場合に、グローバルキャッシュからバッチで取得して補充するロジックが追加されました。
gfpurge関数の実装:
- Pのローカルキャッシュにある全てのデッドGをグローバルキャッシュに移動させる新しい関数が追加されました。
globrunqput, globrunqget, pidleput, pidleget関数の実装:
- グローバルな実行可能キューとアイドルPリストを管理するための新しい関数が追加されました。

src/pkg/runtime/runtime.h

P構造体:

以下のフィールドの追加:

P* link;
// Available G's (status == Gdead)
G* gfree;
int32 gfreecnt;
byte pad[64];

コアとなるコードの解説

このコミットの最も重要な変更は、gfputとgfget関数の実装に見られます。これらは、ゴルーチンの再利用（デッドGのキャッシュ）のメカニズムを、グローバルな単一リストから、Pごとのローカルキャッシュとグローバルキャッシュのハイブリッドモデルへと移行させるものです。

`gfput`関数の変更点

// Put on gfree list.
// If local list is too long, transfer a batch to the global list.
static void
gfput(P *p, G *gp)
{
    if(gp->stackguard - StackGuard != gp->stack0)
        runtime·throw("invalid stack in gfput");
    gp->schedlink = p->gfree; // ゴルーチンをPのローカルキャッシュの先頭に追加
    p->gfree = gp;
    p->gfreecnt++; // ローカルキャッシュのカウンタをインクリメント
    if(p->gfreecnt >= 64) { // ローカルキャッシュが閾値を超えた場合
        runtime·lock(&runtime·sched.gflock); // グローバルロックを取得
        while(p->gfreecnt >= 32) { // バッチでグローバルに移動
            p->gfreecnt--;
            gp = p->gfree;
            p->gfree = gp->schedlink;
            gp->schedlink = runtime·sched.gfree; // グローバルキャッシュの先頭に追加
            runtime·sched.gfree = gp;
        }
        runtime·unlock(&runtime·sched.gflock); // グローバルロックを解放
    }
}

この変更により、ゴルーチンが終了して再利用される際、ほとんどの場合はPのローカルキャッシュに直接格納されるため、グローバルロックの取得が不要になります。これにより、複数のPが同時にゴルーチンを解放しようとした際の競合が大幅に減少します。ローカルキャッシュが大きくなりすぎた場合にのみ、バッチでグローバルキャッシュに移動させることで、グローバルロックの取得頻度を最小限に抑えています。

`gfget`関数の変更点

// Get from gfree list.
// If local list is empty, grab a batch from global list.
static G*
gfget(P *p)
{
    G *gp;

retry:
    gp = p->gfree; // まずPのローカルキャッシュから取得を試みる
    if(gp == nil && runtime·sched.gfree) { // ローカルが空で、グローバルに存在する場合
        runtime·lock(&runtime·sched.gflock); // グローバルロックを取得
        while(p->gfreecnt < 32 && runtime·sched.gfree) { // グローバルからバッチで取得し、ローカルに補充
            p->gfreecnt++;
            gp = runtime·sched.gfree;
            runtime·sched.gfree = gp->schedlink;
            gp->schedlink = p->gfree;
            p->gfree = gp;
        }
        runtime·unlock(&runtime·sched.gflock); // グローバルロックを解放
        goto retry; // ローカルキャッシュに補充されたので、再度ローカルから取得を試みる
    }
    if(gp) { // ローカルキャッシュから取得できた場合
        p->gfree = gp->schedlink;
        p->gfreecnt--;
    }
    return gp;
}

この変更により、新しいゴルーチンが必要な場合、Pはまず自身のローカルキャッシュから取得を試みます。これにより、ほとんどのゴルーチン生成においてグローバルロックが不要になります。ローカルキャッシュが空の場合にのみ、グローバルキャッシュからまとめてゴルーチンを取得し、ローカルキャッシュを補充することで、グローバルロックの取得回数を減らしています。

これらの変更は、Goスケジューラのパフォーマンス、特にゴルーチンの生成と終了が頻繁に行われるアプリケーションにおいて、スループットとスケーラビリティを大幅に向上させるための重要な基盤となります。

参考にした情報源リンク

Go言語の公式ドキュメント
Go言語のソースコード（特にsrc/runtimeディレクトリ）
Goスケジューラに関する技術ブログや解説記事
GitHubのコミット履歴と関連するコードレビュー（CL）

comemo