スケジューラの状態遷移とランキュー構造

状態遷移とランキューを分けて捉える

スケジューラの仕事は2層に分かれます。1つは各タスクが「いま走れるのか／待っているのか／死んだのか」という状態を管理すること。もう1つは、走れるタスクの中から次の1つを選ぶデータ構造を運用することです。古典的な ready / running / blocked の3状態モデル（/os/scheduling/）は概念図としては正しいのですが、Linux の実装はもう少し細かく、待ちの種類や終了の途中段階まで状態として区別します。ここを正確に押さえると、ps で見える D や Z の正体、マルチコアでの偏りの均し方まで一本の筋で理解できます。

TASK_RUNNING を起点とした状態遷移

Linux のタスク状態は task_struct の state（現行カーネルでは __state）フィールドが持ちます。重要なのは、実行可能（ready）と実行中（running）が同じ TASK_RUNNING で表される点です。両者を分けるのは状態フィールドではなく、「いまランキューから選ばれて CPU を握っているか」という実行時の事実です。

                 fork / clone
                      │
                      ▼
   ┌──────────────────────────────┐
   │ TASK_RUNNING                 │  ← ready と running は同じ状態値
   │  ・ランキュー上で順番待ち     │
   │  ・選ばれてCPUを実行中         │
   └──────────────────────────────┘
     ▲   │              │      ▲
 wakeup  │ schedule()   │      │ SIGCONT
（起床）  ▼（待機へ）     │      │
   ┌─────────────┐      │   ┌──────────────┐
   │ INTERRUPTIBLE│      │   │ STOPPED       │
   │ UNINTERRUPT. │      │   │ (SIGSTOP等)   │
   └─────────────┘      │   └──────────────┘
                        │ exit()
                        ▼
                   ┌──────────┐  親が wait() ┌──────────┐
                   │ ZOMBIE   │ ───────────▶│ 解放(消滅) │
                   │(EXIT_*)  │              └──────────┘
                   └──────────┘

遷移の本質は「ランキューに載っているか否か」です。TASK_RUNNING のタスクだけがランキュー上に存在し、スケジューラの選択対象になります。待ち状態へ移るときはランキューから外され（dequeue）、起床時に再び載せられます（enqueue）。状態フィールドの書き換えとランキュー操作は必ずセットで起きる、と捉えるのが正確です。

各状態の意味と分岐

待ち状態を1つにまとめず2種類に分けている点が、初学者がつまずきやすい所です。違いはシグナルで起こせるか否かです。

• TASK_INTERRUPTIBLE：ソケットやパイプ、タイマーなど「待っても安全に途中で諦められる」イベントの待ち。シグナルが届くと待ちを中断して TASK_RUNNING へ戻り、システムコールは EINTR を返すか自動再開します。通常スリープしているプロセスの大半はこれで、S と表示されます。
• TASK_UNINTERRUPTIBLE：ディスク I/O の完了など、途中で中断すると整合性が壊れる待ち。シグナルでは起こせず、待っているイベント（I/O 完了割り込みなど）でのみ起床します。ストレージが固まると D 状態のプロセスが滞留し、kill -9 でも消えないのはこのためです（割り込みの仕組みは /os/interrupt-io/ を参照）。
• __TASK_STOPPED：SIGSTOP / SIGTSTP（Ctrl+Z）などで一時停止した状態。SIGCONT で TASK_RUNNING に戻ります。SIGSTOP と SIGKILL はハンドラで捕まえられない特別なシグナルです（/os/signals/）。
• EXIT_ZOMBIE：exit() 後、終了コードなどのメタ情報だけ残して本体を解放した抜け殻。親が wait() で回収すると完全に消えます。詳しくは /os/zombie-process/。

per-CPUランキュー ── なぜ単一キューにしないのか

「走れるタスク（TASK_RUNNING）の集合」を保持するのがランキュー（runqueue, struct rq）です。素朴には全 CPU で1つの大きなキューを共有すれば良さそうですが、現代の Linux はCPU ごとに独立したランキューを1つずつ持ちます。

  グローバル単一キュー（採用しない）        per-CPUランキュー（現行）

      [ 全CPUが奪い合う1本 ]            CPU0       CPU1       CPU2
       ↑    ↑    ↑    ↑                 [rq0]      [rq1]      [rq2]
     CPU0  CPU1 CPU2 CPU3                │          │          │
       └─ 1個のロックに集中 ─┘           ローカル    ローカル    ローカル
        ・ロック競合が深刻               ロックのみ  ロックのみ  ロックのみ
        ・キャッシュ行が全コア間で往復     ・競合が局所化
        ・コア数に対してスケールしない     ・キャッシュ局所性を維持

単一キューを避ける理由は2つです。第一にロック競合。全 CPU が1本のキューのロックを取り合うと、コア数が増えるほど待ちが増え、スケールしません。per-CPU なら各 CPU は自分の rq->lock だけを取れば良く、競合が局所化します。第二にキャッシュ局所性。あるタスクを直前に走らせた CPU のキャッシュ・TLB にはそのタスクのデータが温まっています（/os/context-switch/）。同じ CPU で再び走らせればキャッシュが効くため、タスクは原則として元の CPU のランキューに留まろうとします。

各ランキューの内部は、スケジューリングクラスごとにサブ構造を持ちます。公平配分を担う CFS は cfs_rq の中で実行可能タスクを赤黒木に並べ、vruntime 最小のものを次に選びます（内部動作は /os/cfs-scheduler-internals/）。リアルタイムクラスは優先度ごとのキュー配列を持つ、という具合に構造が分かれています。

ロードバランシング ── 偏りをどう均すか

per-CPU に分けた代償として、CPU 間の負荷が偏ります。あるコアのランキューに5タスク、隣は空、では公平でも効率的でもありません。これを均すのがロードバランサで、起動のきっかけは大きく2系統あります。

擬似コード：周期的バランシング（簡略）

on each scheduler tick (各CPUで定期的に):
    domain = この CPU の最下位スケジューリングドメイン
    while domain is not null:
        if この CPU がバランス担当 かつ 間隔が経過:
            busiest = ドメイン内で最も混んだグループを探す
            if busiest の負荷 - 自分の負荷 が閾値を超える:
                pull_tasks(busiest -> 自CPU)   # 混んだ側から引き取る
        domain = domain.parent   # 上位ドメインへ

• 周期的バランシング（periodic）：スケジューラティックごとに、混んだランキューから空いた側へタスクを**引き取り（pull）**ます。引っ張る側が動く pull 型が基本です。
• アイドル時バランシング（newidle / nohz）：ある CPU が走らせるタスクを失って暇になった瞬間、即座に他から仕事を探して引き取ります。コアを遊ばせないための即応的な経路です。
• 起床時の配置（wake-up placement）：眠っていたタスクが起きるとき、select_task_rq() がどの CPU のランキューに載せるかを選びます。キャッシュが温かい元の CPU と、いますぐ空いている CPU を天秤にかけます。

均し方を決める鍵がスケジューリングドメインの階層です。CPU 同士の「近さ」（キャッシュやメモリの共有度）を木構造で表し、近い範囲から優先して均します。

階層の意図は明快です。移動コストが小さい近い CPU 間ほど頻繁・積極的に均し、コストの大きい遠い CPU 間（特に NUMA ノードをまたぐ移動）は閾値を高くして慎重にする。下位ドメインから順に上へたどることで、まず安いペアで均し、それでも収まらない大きな偏りだけ高コストな広域移動に踏み込みます。タスクを別 CPU へ移すと温めたキャッシュを捨てることになるため、「均す利得」が「移動の損」を上回るときだけ動かす、という損得勘定が全体を貫く設計思想です。

まとめ

• Linux のタスク状態は TASK_RUNNING を起点に、INTERRUPTIBLE / UNINTERRUPTIBLE の待ち、STOPPED、終了後の ZOMBIE へ遷移する。ready と running は同じ状態値で、差はランキューに載っているか・CPU を握っているか。
• 待ちの2種はシグナルで起こせるかで分かれ、UNINTERRUPTIBLE（D）は SIGKILL でも消せない。
• ランキューはCPU ごとに独立。ロック競合の局所化とキャッシュ局所性のために単一キューを避け、内部はスケジューリングクラス別の構造（CFS は赤黒木）を持つ。
• per-CPU の偏りはスケジューリングドメイン階層をたどるロードバランサが均す。近い CPU ほど積極的に、NUMA をまたぐ移動は慎重に——「均す利得 ＞ 移動の損」のときだけ動かす。
• 状態遷移を起こすシグナルは /os/signals/、回収待ちの抜け殻は /os/zombie-process/、スケジュールされる単位は /os/process-thread/ も参照。