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

このコミットは、Goランタイムにおけるローカルワークキューの実装を追加するものです。これは、新しいスケジューラ導入に向けた準備の一環として行われました。具体的には、src/pkg/runtime/proc.cにゴルーチンを管理するためのローカルキュー操作関数（runqput, runqget, runqgrow, runqsteal）が追加され、関連するヘッダファイルsrc/pkg/runtime/runtime.hにP構造体が定義されました。また、これらの機能のテストコードがsrc/pkg/runtime/export_test.goとsrc/pkg/runtime/proc_test.goに追加されています。

コミット

コミットハッシュ: 353ce60f6e8e5898efec62945fbafd33bc28a37b
Author: Dmitriy Vyukov dvyukov@google.com
Date: Sat Feb 23 08:48:02 2013 +0400

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

https://github.com/golang/go/commit/353ce60f6e8e5898efec62945fbafd33bc28a37b

元コミット内容

runtime: implement local work queues (in preparation for new scheduler)

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

変更の背景

このコミットは、Goランタイムのスケジューラを刷新する準備として、ローカルワークキューを導入するものです。Goのスケジューラは、ゴルーチン（Goの軽量スレッド）を効率的にOSスレッド（M）とプロセッサ（P）に割り当て、実行を管理する役割を担っています。従来のスケジューラでは、ゴルーチンの管理にグローバルなキューが用いられていましたが、マルチコア環境でのスケーラビリティやパフォーマンスの向上のためには、各プロセッサが自身のゴルーチンキューを持つ「ローカルワークキュー」の概念が不可欠となります。

特に、この変更は「ワークスチール（Work Stealing）」アルゴリズムの実装に向けた重要なステップです。ワークスチールとは、あるプロセッサ（P）が自身のローカルキューに実行可能なゴルーチンがない場合に、他のプロセッサのローカルキューからゴルーチンを「盗んで」きて実行するメカニズムです。これにより、CPUコアの利用率を最大化し、負荷分散を最適化することができます。このコミットは、そのワークスチールを実現するための基盤となるローカルキューの管理機能を提供します。

前提知識の解説

Goのランタイムスケジューラを理解するためには、以下の概念が重要です。

Goroutine (G): Go言語における軽量な実行単位です。OSスレッドよりもはるかに軽量で、数百万個のゴルーチンを同時に実行することが可能です。Goランタイムがそのスケジューリングを管理します。
Machine (M): OSスレッドを表します。Goのコードを実行する実際のOSスレッドです。MはP（Processor）にアタッチされてゴルーチンを実行します。
Processor (P): 論理的なプロセッサを表します。Goランタイムがゴルーチンを実行するために必要なコンテキストを提供します。通常、GOMAXPROCS環境変数で指定された数（デフォルトではCPUコア数）のPが存在します。各Pは自身のローカルな実行可能ゴルーチンキュー（Local Run Queue, LRQ）を持ちます。
Local Run Queue (LRQ): 各Pが持つ、実行可能なゴルーチンを格納するキューです。Pはまず自身のLRQからゴルーチンを取得して実行します。
Global Run Queue (GRQ): 全てのPが共有するグローバルな実行可能ゴルーチンキューです。新しいゴルーチンは通常、最初にGRQに配置されるか、LRQが満杯になった場合にLRQからGRQに移動されることがあります。
Work Stealing (ワークスチール): Goスケジューラの重要なメカニズムの一つです。あるPのLRQが空になった場合、そのPはアイドル状態になるのではなく、他のPのLRQからゴルーチンを「盗んで」きて自身のLRQに追加し、実行を継続します。これにより、CPUリソースの有効活用と負荷分散が実現されます。

このコミットは、特にLRQの実装と、ワークスチールに必要なrunqsteal関数の基礎を築いています。

技術的詳細

このコミットでは、Goランタイムのproc.cファイルに、P（Processor）ごとのローカルな実行可能ゴルーチンキューを管理するための関数群が追加されています。

P構造体の導入: src/pkg/runtime/runtime.hにP構造体が定義されました。この構造体は、ローカルキューのヘッド、テール、サイズ、そしてゴルーチンへのポインタの配列（runq）を保持します。また、キューへのアクセスを保護するためのLockも含まれています。
```
struct P
{
    Lock;

    // Queue of runnable goroutines.
    G**     runq;
    int32   runqhead;
    int32   runqtail;
    int32   runqsize;
};
```
ローカルキュー操作関数: src/pkg/runtime/proc.cに以下の関数が追加されました。
- runqput(P *p, G *gp): 指定されたPのローカルキューにゴルーチンgpを追加します。キューが満杯の場合にはrunqgrowを呼び出してキューを拡張します。キューへのアクセスはロックで保護されています。
- runqget(P *p): 指定されたPのローカルキューからゴルーチンを取得します。キューが空の場合にはnilを返します。キューへのアクセスはロックで保護されています。
- runqgrow(P *p): ローカルキューが満杯になった際に、キューのサイズを2倍に拡張します。既存のゴルーチンは新しい、より大きな配列にコピーされます。
- runqsteal(P *p, P *p2): ワークスチールの中核となる関数です。P pがP p2のローカルキューからゴルーチンを「盗みます」。具体的には、p2のキューから約半分のゴルーチンをpのキューに移動させます。デッドロックを防ぐために、ロックの取得順序が考慮されています（p < p2の場合とそうでない場合でロック順序を制御）。盗んだゴルーチンのうちの1つを返します。

これらの関数は、Goスケジューラが各Pのローカルキューを効率的に管理し、必要に応じて他のPからゴルーチンを奪い取ることで、システム全体の負荷分散とスループット向上を図るための基盤となります。

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

このコミットで変更された主要なファイルと、その変更の概要は以下の通りです。

src/pkg/runtime/export_test.go:
- testSchedLocalQueue()とtestSchedLocalQueueSteal()というテスト用の関数がエクスポートされ、外部のテストコードから呼び出せるようになりました。これにより、ローカルキューの基本的な動作とワークスチール機能のテストが可能になります。
src/pkg/runtime/proc.c:
- ローカルワークキューを操作するための主要な関数であるrunqput、runqget、runqgrow、runqstealが実装されました。
- これらの関数は、P（プロセッサ）ごとのゴルーチンキューの管理、キューの拡張、そして他のPからのゴルーチン窃盗（ワークスチール）のロジックを含んでいます。
- また、これらの関数をテストするためのruntime·testSchedLocalQueueとruntime·testSchedLocalQueueStealというテストヘルパー関数も追加されています。
src/pkg/runtime/proc_test.go:
- TestSchedLocalQueueとTestSchedLocalQueueStealというGoのテスト関数が追加されました。これらは、export_test.goでエクスポートされたテストヘルパー関数を呼び出し、ローカルキューとワークスチール機能の正確性を検証します。
src/pkg/runtime/runtime.h:
- P構造体が定義されました。この構造体は、各プロセッサが持つローカルな実行可能ゴルーチンキューの状態（ヘッド、テール、サイズ、ゴルーチン配列）を保持します。

コアとなるコードの解説

src/pkg/runtime/proc.cに追加された主要な関数について詳しく解説します。

`static void runqput(P p, G gp)`

この関数は、指定されたプロセッサpのローカル実行可能キューにゴルーチンgpを追加します。

static void
runqput(P *p, G *gp)
{
    int32 h, t, s;

    runtime·lock(p); // Pのロックを取得し、排他制御を行う
retry:
    h = p->runqhead; // キューのヘッド
    t = p->runqtail; // キューのテール
    s = p->runqsize; // キューの現在のサイズ
    if(t == h-1 || (h == 0 && t == s-1)) { // キューが満杯の場合
        runqgrow(p); // キューを拡張
        goto retry; // 拡張後、再度追加を試みる
    }
    p->runq[t++] = gp; // テール位置にゴルーチンを追加し、テールをインクリメント
    if(t == s) // テールがキューの終端に達した場合
        t = 0; // テールを先頭に戻す（リングバッファとして利用）
    p->runqtail = t; // 更新されたテールをPに設定
    runtime·unlock(p); // Pのロックを解放
}

この関数はリングバッファとして実装されており、runqheadとrunqtailがキューの先頭と末尾を示します。キューが満杯の場合（t == h-1またはh == 0 && t == s-1）、runqgrowを呼び出してキューのサイズを倍に拡張します。

`static G* runqget(P *p)`

この関数は、指定されたプロセッサpのローカル実行可能キューからゴルーチンを取得します。

static G*
runqget(P *p)
{
    G *gp;
    int32 t, h, s;

    if(p->runqhead == p->runqtail) // キューが空の場合
        return nil; // nilを返す
    runtime·lock(p); // Pのロックを取得
    h = p->runqhead;
    t = p->runqtail;
    s = p->runqsize;
    if(t == h) { // ロック取得後にキューが空になった場合
        runtime·unlock(p);
        return nil;
    }
    gp = p->runq[h++]; // ヘッド位置のゴルーチンを取得し、ヘッドをインクリメント
    if(h == s) // ヘッドがキューの終端に達した場合
        h = 0; // ヘッドを先頭に戻す
    p->runqhead = h; // 更新されたヘッドをPに設定
    runtime·unlock(p); // Pのロックを解放
    return gp; // 取得したゴルーチンを返す
}

runqputと同様にリングバッファとして動作します。キューが空の場合はnilを返します。

`static void runqgrow(P *p)`

この関数は、ローカル実行可能キューのサイズを拡張します。

static void
runqgrow(P *p)
{
    G **q;
    int32 s, t, h, t2;

    h = p->runqhead;
    t = p->runqtail;
    s = p->runqsize;
    t2 = 0;
    q = runtime·malloc(2*s*sizeof(*q)); // 現在の2倍のサイズの新しい配列を割り当て
    while(t != h) { // 既存のゴルーチンを新しい配列にコピー
        q[t2++] = p->runq[h++];
        if(h == s)
            h = 0;
    }
    runtime·free(p->runq); // 古い配列を解放
    p->runq = q; // 新しい配列をPに設定
    p->runqhead = 0; // ヘッドを0にリセット
    p->runqtail = t2; // テールをコピーされた要素数に設定
    p->runqsize = 2*s; // サイズを2倍に更新
}

キューが満杯になった際に呼び出され、キューのサイズを倍に増やします。既存のゴルーチンは新しいメモリ領域にコピーされます。

`static G* runqsteal(P p, P p2)`

この関数は、ワークスチールアルゴリズムの中核をなすもので、プロセッサpがプロセッサp2のローカルキューからゴルーチンを「盗む」処理を行います。

static G*
runqsteal(P *p, P *p2)
{
    G *gp, *gp1;
    int32 t, h, s, t2, h2, s2, c, i;

    if(p2->runqhead == p2->runqtail) // 盗む側のキューが空の場合
        return nil; // nilを返す
    // sort locks to prevent deadlocks
    if(p < p2) // デッドロックを防ぐために、Pのアドレスに基づいてロック順序を決定
        runtime·lock(p);
    runtime·lock(p2); // 盗む側のPのロックを取得
    if(p2->runqhead == p2->runqtail) { // ロック取得後にキューが空になった場合
        runtime·unlock(p2);
        if(p < p2)
            runtime·unlock(p);
        return nil;
    }
    if(p >= p2) // デッドロックを防ぐために、Pのアドレスに基づいてロック順序を決定
        runtime·lock(p);
    // now we've locked both queues and know the victim is not empty

    h = p->runqhead;
    t = p->runqtail;
    s = p->runqsize;
    h2 = p2->runqhead;
    t2 = p2->runqtail;
    s2 = p2->runqsize;

    gp = p2->runq[h2++];  // 盗むゴルーチンのうちの1つを最初に取得（返り値となる）
    if(h2 == s2)
        h2 = 0;

    // steal roughly half
    if(t2 > h2) // 盗む側のキューの約半分を計算
        c = (t2 - h2) / 2;
    else
        c = (s2 - h2 + t2) / 2;

    // copy
    for(i = 0; i != c; i++) { // 計算した半分のゴルーチンをコピー
        // the target queue is full?
        if(t == h-1 || (h == 0 && t == s-1)) // 盗む側のキューが満杯の場合
            break;
        // the victim queue is empty?
        if(t2 == h2) // 盗まれる側のキューが空になった場合
            break;
        gp1 = p2->runq[h2++]; // 盗まれる側のキューからゴルーチンを取得
        if(h2 == s2)
            h2 = 0;
        p->runq[t++] = gp1; // 盗む側のキューに追加
        if(t == s)
            t = 0;
    }
    p->runqtail = t; // 盗む側のPのテールを更新
    p2->runqhead = h2; // 盗まれる側のPのヘッドを更新
    runtime·unlock(p2); // 盗まれる側のPのロックを解放
    runtime·unlock(p); // 盗む側のPのロックを解放
    return gp; // 最初に盗んだゴルーチンを返す
}

この関数は、p2のローカルキューから約半分のゴルーチンをpのローカルキューに移動させます。重要なのは、デッドロックを避けるために、2つのPのロックを常に同じ順序で取得するロジック（if(p < p2)）が導入されている点です。これにより、複数のPが同時に互いのキューからゴルーチンを盗もうとした場合に発生しうるデッドロックを防ぎます。

comemo