OS(最小カーネルと協調スケジューラ)
「誰が CPU を握るかを決める」という OS の奥の仕事を Go でモデル化する。CPU は 1 つしかなく、それを分け合うのがスケジューラになる。ここで作るのは協調方式で、タスクが自分から手放したときにだけ次を選ぶ。タスクのコンテキストはプログラムカウンタ 1 つで表せて、context switch はその保存と復元になる。yield を書かないタスクは他を待たせる。
この章で作るもの
コンピュータの CPU コアは(この章では)1 つ。なのに何十ものプロセスが「同時に」動いているように見える。種明かしは単純で、ものすごく速く切り替えているだけだ。ではいつ切り替えるのか。ここに2つの流派がある。
- 協調(cooperative): タスクが自発的に CPU を手放したときだけ切り替える。切り替え点はタスクが決める
- プリエンプティブ(preemptive): タイマ割り込みで OS が強制的に取り上げる。タスクの都合と無関係に切り替わる
この章で作るのは前者だ。初期の Mac OS(〜9)や Windows 3.x が採っていた方式であり、いまの async/await・コルーチン・goroutine が持つ「協調ポイントで切り替わる」感覚の原型でもある。実スレッドも割り込みも使わず、この仕組みを純粋なデータ構造で決定的に組む。
┌──────────── Kernel(論理時計 + スケジューラ)────────────┐
│ │
│ run queue(FIFO = round-robin) blocked(sleep 中) │
│ [ B ][ C ] ← yield したら末尾へ { A: wake @ 6 } │
│ │ 先頭を dispatch ↑ 起床で戻る │
│ ▼ │
│ ┌ Running: A ┐ │
│ │ pc = 3 │ ← コンテキストの実体は pc │
│ │ │ switch = pc の保存と復元 │
│ └────────────┘ │
└────────────────────────────────────────────────────────┘順に見ていく。
- コンテキスト(コンテキスト)= pc: タスクの状態は「プログラムのどこまで実行したか」だけで表せる
- 協調 = 横取りしない:
yieldするまで CPU を握り続ける。書き忘れると他を待たせる - ブロックと空転:
sleepは run queue から外れ、走れるタスクが尽きたら CPU は空転する
① タスクとコンテキスト(pc)
まずタスクを定義する。ここでのタスクは、Run / Yield / Sleep という**命令の並び(プログラム)**にすぎない。そして状態は、実行可能(ready)・実行中(running)・ブロック中(blocked)・完了(done)の4つを行き来する。
いちばん大事なのは Task の pc(program counter)だ。タスクの「コンテキスト」はこの pc だけで表せる。実機ではレジスタやスタックポインタを退避するが、本質は同じで、context switch は「保存した位置を戻して、続きから走らせる」ことになる:
go
// State はタスクの状態。協調スケジューラでは、状態遷移は
// タスク自身の yield / sleep と、スケジューラの dispatch / wake でしか起きない。
type State int
const (
Ready State = iota // 実行可能。run queue で CPU の順番を待っている
Running // いま CPU を握っている(常に高々1つ)
Blocked // sleep 中。起床時刻になるまで run queue に戻らない
Done // プログラムを最後まで実行し終えた
)
// String は状態の短い表示名を返す(トレースやデモ用)。
func (s State) String() string {
switch s {
case Ready:
return "ready"
case Running:
return "running"
case Blocked:
return "blocked"
case Done:
return "done"
}
return "?"
}
// OpKind はタスクのプログラムを構成する命令の種類。
type OpKind int
const (
OpRun OpKind = iota // CPU を Arg tick 使う。この間 yield しない(協調の肝)
OpYield // 自発的に CPU を手放し、run queue の最後尾に並び直す
OpSleep // Arg tick 分ブロックする。時刻が来たら起こされる
)
// Op はタスクのプログラムの 1 命令。プログラムはこの命令の並びにすぎない。
type Op struct {
Kind OpKind
Arg int
}
// Run は CPU を ticks 分使う命令。途中で yield しないので、この命令が長いほど
// 他タスクを待たせる——協調スケジューリングの弱点そのもの。ticks < 1 は 1 として扱う。
func Run(ticks int) Op { return Op{Kind: OpRun, Arg: ticks} }
// Yield は自発的に CPU を手放す命令。協調方式では、ここでだけスケジューラに制御が戻る。
func Yield() Op { return Op{Kind: OpYield} }
// Sleep は ticks 分ブロックする命令。起床時刻が来ると run queue に戻される。
func Sleep(ticks int) Op { return Op{Kind: OpSleep, Arg: ticks} }
// Task は 1 つの実行単位(プロセス/スレッド/コルーチン)。
//
// このタスクの「文脈(コンテキスト)」の実体は pc ——プログラムのどこまで
// 実行したか——だけである。実機ではレジスタやスタックポインタを退避するが、
// 本質は同じで、context switch とは pc の保存と復元にすぎない。
type Task struct {
Name string
prog []Op
pc int // 保存された文脈: 次に実行する命令の位置
st State
cpu int // これまでに使った CPU tick の合計
wake int // Blocked のとき、起こされる時刻
seq int // 生成順。同時起床の決定的な順序づけに使う
}
// State はタスクの現在の状態を返す。
func (t *Task) State() State { return t.st }
// CPU はこのタスクがこれまでに使った CPU tick の合計を返す。
func (t *Task) CPU() int { return t.cpu }Run(n) が「n tick 走るあいだ CPU を手放さない」命令であることに注目してほしい。この一点が、協調方式のすべてを決める。
② スケジューラ: run queue と dispatch
カーネルは論理時計と2つの入れ物を持つ。run queue(実行可能タスクの列)と blocked(sleep 中のタスク)だ。run queue を素朴な FIFO にするだけで、スケジューリング方針は自動的に round-robin(順番に公平)になる。先頭から取り出し、yield したタスクは末尾へ戻すからだ:
go
// Kind はスケジュール記録(トレース)1 行の種類。
type Kind string
const (
KindRun Kind = "run" // タスクが CPU を使った
KindYield Kind = "yield" // 自発的に CPU を手放した
KindSleep Kind = "sleep" // ブロックに入った
KindWake Kind = "wake" // 起床時刻が来て run queue に戻った
KindExit Kind = "exit" // プログラムを実行し終えた
KindIdle Kind = "idle" // 実行可能タスクが無く、CPU が空転した
)
// Event はスケジューラのトレース 1 行。At はその出来事が起きた時刻。
// N は run の tick 数 / sleep の長さ / idle の空転量に使う。
type Event struct {
At int
Task string
Kind Kind
N int
}
// Kernel は最小カーネル。誰が CPU を握るかを決めるスケジューラと、論理時計を持つ。
// プリエンプション(強制的な横取り)は無く、タスクが自発的に yield / sleep した
// ときにだけ制御が戻る = 協調スケジューリング。
type Kernel struct {
clock int
ready []*Task // run queue。先頭から取り出し末尾へ戻す = round-robin
blocked []*Task // sleep 中のタスク
running *Task
switches int
nextSeq int
trace []Event
}
// NewKernel は空のカーネルを作る。
func NewKernel() *Kernel { return &Kernel{} }
// Spawn は新しいタスクを生成し、run queue の末尾に並べる(Ready)。
// プログラムは Run / Yield / Sleep の並びで与える。
func (k *Kernel) Spawn(name string, prog ...Op) *Task {
t := &Task{Name: name, prog: prog, st: Ready, seq: k.nextSeq}
k.nextSeq++
k.ready = append(k.ready, t)
return t
}Spawn はタスクを作って run queue の末尾に並べるだけ。方針を変えたければ、この列の並べ方(たとえば優先度順に差し込む)を変えればいい。スケジューラの「賢さ」はすべてこの列の扱いに宿る。
③ 走らせる: yield / sleep / 空転
心臓部が Step だ。run queue の先頭を取り出し、保存された pc の続きから走らせる。そして yield / sleep / 完了 のいずれかで CPU を手放すまで、走りっぱなしにする。ここが「協調」の実装そのもので、スケジューラはタスクを横取りできない:
go
// wake は起床時刻を迎えた Blocked タスクを run queue に戻す。
// 同時に起きるタスクは、起床時刻 → 生成順で決定的に並べる。
func (k *Kernel) wake() {
if len(k.blocked) == 0 {
return
}
var woken, still []*Task
for _, t := range k.blocked {
if t.wake <= k.clock {
woken = append(woken, t)
} else {
still = append(still, t)
}
}
if len(woken) == 0 {
return
}
sort.Slice(woken, func(i, j int) bool {
if woken[i].wake != woken[j].wake {
return woken[i].wake < woken[j].wake
}
return woken[i].seq < woken[j].seq
})
for _, t := range woken {
t.st = Ready
k.ready = append(k.ready, t)
k.trace = append(k.trace, Event{At: k.clock, Task: t.Name, Kind: KindWake})
}
k.blocked = still
}
// Step は 1 回分のスケジュールを進める。run queue の先頭タスクを取り出し、
// yield / sleep / 完了 のいずれかで CPU を手放すまで走らせる(協調)。
// 進める余地が無ければ false を返す。
func (k *Kernel) Step() bool {
k.wake()
if len(k.ready) == 0 {
// 実行可能タスクが無い。sleep 中のタスクがいれば、CPU は次の
// 起床時刻まで空転(idle)して時計を進める——実機の HLT に当たる。
if len(k.blocked) == 0 {
return false // 全タスク完了
}
next := k.blocked[0].wake
for _, t := range k.blocked {
if t.wake < next {
next = t.wake
}
}
k.trace = append(k.trace, Event{At: k.clock, Task: "(idle)", Kind: KindIdle, N: next - k.clock})
k.clock = next
k.wake()
}
// run queue の先頭を dispatch(round-robin)。ここで文脈(pc)を復元する。
t := k.ready[0]
k.ready = k.ready[1:]
t.st = Running
k.running = t
// yield / sleep / 完了 まで、保存された pc の続きから走らせる。
for {
if t.pc >= len(t.prog) {
t.st = Done
k.trace = append(k.trace, Event{At: k.clock, Task: t.Name, Kind: KindExit})
k.switches++
break
}
op := t.prog[t.pc]
t.pc++ // 文脈を1つ進める。この pc が次回の復元点になる
if op.Kind == OpRun {
n := op.Arg
if n < 1 {
n = 1
}
k.trace = append(k.trace, Event{At: k.clock, Task: t.Name, Kind: KindRun, N: n})
k.clock += n
t.cpu += n
continue // 協調: yield するまで CPU を握り続ける(横取りされない)
}
if op.Kind == OpYield {
t.st = Ready
k.ready = append(k.ready, t) // 末尾へ戻る = round-robin
k.trace = append(k.trace, Event{At: k.clock, Task: t.Name, Kind: KindYield})
k.switches++
break
}
// OpSleep: 起床時刻を決めて blocked へ退避する。
t.st = Blocked
t.wake = k.clock + op.Arg
k.blocked = append(k.blocked, t)
k.trace = append(k.trace, Event{At: k.clock, Task: t.Name, Kind: KindSleep, N: op.Arg})
k.switches++
break
}
k.running = nil
return true
}
// Run は全タスクが完了するまで Step を回し、スケジュール記録を返す。
func (k *Kernel) Run() []Event {
for k.Step() {
}
return k.trace
}3つの要点がこのコードに詰まっている:
- 協調(非プリエンプティブ):
Runを処理したらcontinueで同じタスクの実行を続ける。yieldするまでループを抜けない。だからyieldを書かない貪欲タスクは、プログラムを走り切るまで CPU を独占する - ブロックと起床:
sleepしたタスクは起床時刻を持ってblockedへ退避する。wakeが毎 Step の先頭で「起床時刻を迎えたタスク」を run queue へ戻す - 空転(idle): run queue が空でも sleeper がいれば、CPU は次の起床時刻まで時計を進めて待つ。実機の HLT(なにもせず割り込みを待つ)に当たる
動かす
下のデモは、この協調スケジューラをそのままブラウザで動かしている(Go 実装の考え方を JS に移植)。3つのシナリオを切り替えられる。round-robin は行儀よく yield するタスクが公平に交代する様子。貪欲タスク は yield を書かないタスクが CPU を独占し、他が完了まで一切走れない様子(協調方式の弱点)。sleep と空転 は、寝たタスクを待つあいだ CPU が空転する様子だ。タイムライン(どの tick に誰が CPU を握ったか)と run queue の動きを見比べてほしい。
デモos(協調スケジューラ)6 回切替 · clock 12
round-robin貪欲タスクsleep と空転
全員が Run のあと yield する。CPU は先頭 → 末尾の順で公平に回り、きれいに交代する。
CPU タイムライン — 縦線がいまの時刻(t = 0)
01234567891011
A
B
C
idle
t = 0 の run queue
RunningA
Ready先頭が次に走る →BC
Blocked(なし)
タスクのプログラム(命令の並び)
A
R2 Y R2B
R2 Y R2C
R2 Y R2R=Run(CPUを使う, yieldしない) · Y=Yield(手放す) · S=Sleep(ブロック)
設計の観点: 協調 vs プリエンプティブ
- 協調の弱点 = 1つの暴走が全体を巻き込む:
yieldを書き忘れた(あるいは無限ループに入った)タスクが1つあるだけで、システム全体が固まる。初期 Mac OS で「時計が止まる」体験の正体はこれだ。プリエンプティブ方式(タイマ割り込みで強制的に取り上げる)が生まれた最大の理由が、この弱点にある - 協調の強み = 切り替え点が予測できる:
yield/awaitの場所でしか切り替わらないので、その間はロック無しで共有データを触れる。データ競合が起きる箇所が限定され、推論しやすい。async/await が「シングルスレッドで安全に並行」できるのはこの性質のおかげ - いまの言語ランタイムは両方の良いとこ取り: Go の goroutine は M:N スケジューラ(多数の goroutine を少数の OS スレッドに載せる)で、チャネルや関数呼び出しなどの協調ポイントで切り替えつつ、暴走を防ぐ非同期プリエンプションも持つ。本章の
yield/sleepは、その協調ポイントの最小モデルだ - ブロックは「予約して手放す」:
sleepに限らず、I/O 待ち・ロック待ち・チャネル待ちはすべて「起こされる条件を登録して CPU を手放す」構造。本章では起床条件をタイマ1種類に単純化しているが、骨格(blocked に退避 → 条件成立で ready へ)は共通だ
メリット・デメリットと実例
| 方式 | 切り替え契機 | 暴走への耐性 | 共有データの扱い | 実例 |
|---|---|---|---|---|
| 協調(本章) | タスクが自発的に手放す | 弱い(1つで全停止) | 切り替え点が明示的で楽 | 初期 Mac OS 〜9、Windows 3.x |
| プリエンプティブ | タイマ割り込みで強制 | 強い | ロックが要る | Linux/Windows のカーネルスレッド |
| async/await | await ポイント | 弱い(CPU 専有で詰まる) | シングルスレッドなら安全 | JS イベントループ、Python asyncio |
| M:N ランタイム | 協調点 + 非同期割り込み | 中〜強 | チャネル/ロック | Go goroutine、Erlang プロセス |
裏どり:
- 初期 Mac OS(〜9)の
WaitNextEvent: アプリがこの関数を呼んだときにだけ他アプリへ切り替わった。まさに協調yield。1つのアプリが固まると Mac 全体が固まったのはこのため。Mac OS X(Unix ベース)でプリエンプティブへ移行した - JavaScript のイベントループ: シングルスレッドの協調方式。
awaitや次の task で手放すまで走り続けるので、重い同期ループを書くと UI 全体が固まる(「メインスレッドを塞ぐ」)。本章の貪欲タスクと同じ現象 - Go の goroutine: 関数呼び出しやチャネル操作という協調ポイントで切り替わりつつ、Go 1.14 以降は非同期プリエンプションでタイトループも横取りできる。協調とプリエンプティブのハイブリッドの好例
- Python asyncio:
awaitでだけ切り替わる協調方式。awaitを挟まない CPU 律速の処理はイベントループを止める。だから重い計算は別スレッド/プロセスへ逃がす
簡略化したこと
- プリエンプションは無し: タイマ割り込みで強制的に取り上げる方式は実装しない(対比としてのみ説明)
- スケジューリング方針は round-robin のみ: 優先度・多段フィードバックキュー・Linux CFS のような公平配分は省略
- 1 コア固定: マルチコア・負荷分散・ワークスティーリングは扱わない。走れるのは常に1タスク
- ブロック要因は sleep(タイマ)のみ: mutex・セマフォ・チャネル待ち・I/O 待ちは「起こされる条件」をタイマ1種類に単純化。骨格(blocked へ退避 → 条件成立で ready)は同じ
- 実行は模擬: タスクは
Run/Yield/Sleepの並びで、実際の計算はしない。CPU は論理 tick で数える
参考資料
- Remzi & Andrea Arpaci-Dusseau, Operating Systems: Three Easy Pieces — プロセス・スケジューリングの無料の名著
- Silberschatz ほか, Operating System Concepts — プロセス状態遷移とスケジューリング方針の定番
- The Go scheduler / "Scalable Go Scheduler Design"(Dmitry Vyukov) — M:N と協調点の実際
- 実装: foundations/os