スケジューラー（Scheduler） - Golang learning step 2-9

roadmap.sh > Go > Going Deeper > Scheduler の学習を進めていきます。

※ 学習メモとしての記録ですが、後にこのセクションを学ぶ道しるべとなるよう、ですます調で記載しています。

contents

1. 開発環境
2. 参考 URL
3. Go のスケジューラー（Go Scheduler）
4. スケジューラーの概要
   1. 1. G (Goroutine)
   2. 2. M (Machine, OS Thread)
   3. 3. P (Processor)
5. スケジューリングの仕組み
   1. 基本的な実行フロー
   2. Work Stealing
6. システムコールの扱い
7. 特徴的な最適化
8. パフォーマンス面の特徴

開発環境

• チップ: Apple M2 Pro
• OS: macOS Sonoma
• go version: go1.23.2 darwin/arm64

参考 URL

• [article] OS Scheduler - 1
• [article] Go Scheduler - 2
• [article] Illustrated Tales of Go Runtime Scheduler
• [video] Go scheduler: Implementing language with lightweight concurrency

Go のスケジューラー（Go Scheduler）

Go のスケジューラーは、軽量な並行処理の実行を支援するために設計されています。Go の並行処理は、ゴルーチンという軽量な並行処理単位を用いて管理され、スケジューラーがこれらのゴルーチンの実行を最適化する役割を果たします。

以下は、複数のゴルーチンを作成する簡単な例です。

func main() {
    // 1000個のゴルーチンを作成
    for i := 0; i < 1000; i++ {
        go func(id int) {
            fmt.Printf("Goroutine %d processing\n", id)
            time.Sleep(time.Millisecond)  // 実際の処理を模擬
        }(i)
    }
    time.Sleep(time.Second)  // メインゴルーチンが終了するのを防ぐ
}

スケジューラーの概要

Go 言語では、並行処理を効率的に行うために独自のスケジューラーを実装しています。これは、オペレーティングシステムのスケジューラーとは異なり、ユーザーレベルで動作します。

Go 1.1 以前は Global Run Queue を使用する単純なモデルを採用していましたが、現在の MPG モデルでは P（Processor）が追加され、より効率的なスケジューリングが可能になりました。

Go のスケジューラーは、M（OSスレッド）、P（プロセッサ）、G（ゴルーチン）という三つのコンポーネントを管理し、効率的な並行処理を行います。これらの関係は「MPG スケジューリングモデル」（または「GMP モデル」）に基づいており、複数のゴルーチン（G）を少数の OS スレッド（M）上で実行します。

1. G (Goroutine)

軽量な並行処理単位。関数呼び出しの形で作成され、スケジューラーによって割り当てられた P 上で実行されます。

package main

import (
    "fmt"
    "time"
)

func main() {
    for i := 0; i < 5; i++ {
        go func(id int) {
            fmt.Printf("Goroutine %d started\n", id)
            time.Sleep(2 * time.Second)
            fmt.Printf("Goroutine %d finished\n", id)
        }(i)
    }
    time.Sleep(3 * time.Second)  // メインゴルーチンが終了するのを防ぐ
}

• ユーザーが作成する軽量な並行処理単位
• 数 KB 程度の初期スタックサイズで開始
• 実行中に必要に応じてスタックサイズが動的に拡大/縮小

2. M (Machine, OS Thread)

実際に OS によって管理されるスレッドで、複数の M が P に紐付けられ、G を実行します。

• OS のスレッドを表す
• システムコールの実行を担当
• 通常、利用可能な CPU コア数と同程度の数が作成される

3. P (Processor)

Go ランタイムが G を実行するために必要なリソースを保持し、G をスケジュールする役割を担います。GOMAXPROCS 環境変数で数を制御できます。

// GOMAXPROCS の設定例
runtime.GOMAXPROCS(2)  // 論理プロセッサ（P）の数を2に設定
n := runtime.GOMAXPROCS(0)  // 現在の設定値を取得

package main

import (
    "fmt"
    "runtime"
    "sync"
)

func main() {
    runtime.GOMAXPROCS(1) // P を 1 に設定してみる
    var wg sync.WaitGroup
    wg.Add(2)

    go func() {
        defer wg.Done()
        for i := 0; i < 5; i++ {
            fmt.Println("Goroutine 1")
        }
    }()

    go func() {
        defer wg.Done()
        for i := 0; i < 5; i++ {
            fmt.Println("Goroutine 2")
        }
    }()
    wg.Wait()
}

• M が持つ実行コンテキスト
• ローカルなランキューを持つ
• デフォルトで CPU コア数と同じ数が作成される

スケジューリングの仕組み

基本的な実行フロー

1. スケジューリングキュー
   • 各 P にはローカルキューがあり、ゴルーチンがキューに追加され、順番に実行されます。全 P が処理する必要があるキューはグローバルキューに保持されます。
2. 実行と切り替え
   • 各 G が一定の時間またはシステムコールを介してブロックすると、スケジューラーは他の準備ができている G に切り替えます。
3. ワークスティーリング
   • P がローカルキューで処理する G を持たない場合、他の P から G を取得して処理を分散させる仕組みが備わっています。

P1 [G1 G2 G3] ← ローカルキュー
|
M1

1. ゴルーチンが P のローカルキューに割り当てられる
2. P が M と結びついてゴルーチンを実行
3. キューが空になると、他の P からタスクを盗む（Work Stealing）

Work Stealing

効率的な負荷分散のため、以下の順序でタスクを探します。

1. 自身のローカルキューから探す（約61回に1回の頻度でグローバルキューもチェック）
2. グローバルキューから取得を試みる
3. 他の P のキューからタスクを盗む（Work Stealing）
   • ランダムに選択された P のキューの半分のタスクを取得
4. ネットワークポーラー（非同期I/O処理を管理するランタイムコンポーネント）をチェックし、I/O待機が完了したゴルーチンがあれば取得

以下は、実際の負荷分散の動作を示す具体例です。（不均衡な負荷がどのように分散されるか）

package main

import (
	"fmt"
	"runtime"
	"sync"
	"time"
)

func generateWork(id int) {
	// 重い計算を模擬
	sum := 0
	for i := 0; i < 1000000; i++ {
		sum += i
	}
	fmt.Printf("Work %d completed\n", id)
}

func main() {
	// 2つのプロセッサのみを使用
	runtime.GOMAXPROCS(2)

	var wg sync.WaitGroup

	// P1に多くのタスクを割り当て
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			generateWork(id)
		}(i)

		// 最初の5つのタスクは少し待って実行開始
		if i < 5 {
			time.Sleep(10 * time.Millisecond)
		}
	}

	// P2は初期状態では仕事が少ない
	for i := 10; i < 12; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			generateWork(id)
		}(i)
	}

	wg.Wait()
}

システムコールの扱い

システムコール実行時の動作

1. ゴルーチンがシステムコールをトリガーすると、M が P から切り離される
2. 他の M が P を取得して残りのゴルーチンを実行
3. システムコール完了後、元のゴルーチンは実行可能な状態に戻される
4. 実行可能になったゴルーチンは、利用可能な P のローカルキューに戻されるか、グローバルキューに配置される

Before syscall:     After syscall start:
P1 [G1 G2 G3]      P1 [G2 G3]
|                   |
M1 (running G1)     M2
                    
M1 (syscall G1)

以下は、システムコール時の動作を示す具体例です。（I/O操作時にM（OSスレッド）がPから切り離され、他のゴルーチンが実行を継続できる）

package main

import (
    "fmt"
    "os"
    "runtime"
    "sync"
    "time"
)

func main() {
    runtime.GOMAXPROCS(1) // 1つのPのみを使用
    
    var wg sync.WaitGroup
    
    // システムコールを実行するゴルーチン
    wg.Add(1)
    go func() {
        defer wg.Done()
        fmt.Println("Goroutine 1: Starting file operation (syscall)")
        
        // システムコールの例（ファイル操作）
        f, err := os.Create("temp.txt")
        if err != nil {
            fmt.Println("Error:", err)
            return
        }
        defer os.Remove("temp.txt")
        defer f.Close()
        
        // ファイル書き込み（システムコール）
        f.WriteString("Hello, World!")
        fmt.Println("Goroutine 1: File operation completed")
    }()
    
    // CPU負荷の高い処理を実行する他のゴルーチン
    for i := 0; i < 3; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            fmt.Printf("Goroutine %d: Starting CPU-bound work\n", id+2)
            
            // CPU負荷の高い処理を模擬
            sum := 0
            for i := 0; i < 1000000; i++ {
                sum += i
            }
            
            fmt.Printf("Goroutine %d: Completed CPU-bound work\n", id+2)
        }(i)
    }
    
    wg.Wait()
}

特徴的な最適化

1. スピンスレッド
   • 一部の M をアイドル状態で維持し、すぐに新しいタスクに対応できるようにする
   • 新しいタスクへの素早い対応が可能
2. スタックの動的サイズ調整
   • 必要に応じてスタックサイズを拡大/縮小
   • メモリ使用の効率化
3. 協調的スケジューリング
   • 関数呼び出し
   • チャネル操作
   • runtime.Gosched() 呼び出し
   • GC などのポイントでスケジューリングが発生
   • プリエンプティブなスケジューリング（Go 1.14以降）により、長時間実行されるゴルーチンも強制的に切り替え可能
     • 長時間実行されているゴルーチンも適切にスケジューリングするため、Go 1.14 以降は強制的に切り替えを行う機能が追加されました

パフォーマンス面の特徴

1. 高速な起動
   • ゴルーチンは数キロバイトのスタックで開始
   • OSスレッドと比べて非常に軽量
   • OS スレッド: 約 1MB（固定） vs ゴルーチン: 約 2KB（初期スタックサイズ、必要に応じて拡張可能）
2. 効率的なスケーリング
   • 数千〜数百万のゴルーチンを効率的に管理
   • Work Stealing による効率的な負荷分散
   • 一般的なサーバーで 100 万個以上のゴルーチンを同時実行可能
3. メモリ効率
   • スタックの動的拡張により必要なメモリのみ使用
   • 未使用時はスタックサイズを縮小
4. コンテキストスイッチの効率
   • ユーザーレベルでのスケジューリングによる低オーバーヘッド
   • カーネルレベルのコンテキストスイッチより効率的

これらの特徴により、Go のスケジューラーは大量の並行処理を効率的に実行できる設計となっています。

なお、より詳細な動作やデバッグについては、以下の環境変数を使用できます。

• GODEBUG=schedtrace=1000：スケジューラーのトレース情報を 1 秒ごとに出力
• GODEBUG=scheddetail=1,schedtrace=1000：より詳細なスケジューリング情報を出力

出力例

SCHED 1000ms: gomaxprocs=4 idleprocs=0 threads=10 spinningthreads=0 idlethreads=3 runqueue=0 [0 0 0 0]

各フィールドの意味

• gomaxprocs: 現在の GOMAXPROCS 値
• idleprocs: アイドル状態の P の数
• threads: 作成されたスレッドの総数
• runqueue: グローバルキュー内のゴルーチン数
• [0 0 0 0]: 各 P のローカルキュー内のゴルーチン数

以下は、メモリ使用量とパフォーマンスの比較を示す例です。大量のゴルーチンを作成した場合のメモリ使用量と実行時間を具体的に示し、ゴルーチンの軽量性を実証しています。

package main

import (
    "fmt"
    "runtime"
    "sync"
    "time"
)

func memStats() runtime.MemStats {
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    return m
}

func main() {
    // メモリ使用量を表示
    fmt.Println("Initial memory stats:")
    initial := memStats()
    fmt.Printf("Alloc: %v MiB\n", initial.Alloc/1024/1024)
    
    start := time.Now()
    var wg sync.WaitGroup
    
    // 100,000個のゴルーチンを作成
    for i := 0; i < 100000; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            // 軽い処理
            time.Sleep(time.Millisecond)
        }(i)
    }
    
    wg.Wait()
    duration := time.Since(start)
    
    // 終了時のメモリ使用量を表示
    final := memStats()
    fmt.Printf("\nFinal memory stats:\n")
    fmt.Printf("Alloc: %v MiB\n", final.Alloc/1024/1024)
    fmt.Printf("Total time: %v\n", duration)
    fmt.Printf("Goroutines created: 100,000\n")
    fmt.Printf("Average creation+execution time per goroutine: %v\n", duration/100000)
}

まとめ

以下に「まとめ」の章を追加し、記事全体の解説を簡潔に箇条書きで整理しました。

• Go のスケジューラーは、G（ゴルーチン）、P（プロセッサ）、M（OS スレッド）の 3 つの要素で構成される MPG モデルを採用
• ゴルーチンは軽量な並行処理の単位で、スタックの動的拡張により効率的にメモリを使用
• P はゴルーチンのスケジューリングを担い、各プロセッサが独自のローカルキューを持つ
• M は OS のスレッドを表し、システムコール時に P から切り離され他のタスクが進行できる
• Work Stealing によるタスクの分散により、効率的な負荷分散が可能
• プリエンプティブなスケジューリングにより、長時間実行されるゴルーチンの切り替えが可能
• スケジューラーの最適化により、大量のゴルーチンを低オーバーヘッドで実行可能

Go のスケジューラーの設計により、大規模な並行処理を効率的に行うための基盤が提供されています。

---

---

[Next] Step 2-10: ジェネリクス（Generics）

[Prev] Step 2-8: ミューテックス（Mutex）