OSスケジューラの系譜（O(n)→O(1)→CFS→EEVDF）

系譜を「設計動機の連鎖」として読む

Linux の CPU スケジューラは約20年で4世代を経ました。単なる置き換えではなく、前世代の弱点が次世代の設計目標になるという動機の連鎖があります。本稿はその系統を、年代と分岐点を明示しながら文章でたどります。各方式の内部実装は個別記事（/os/cfs-scheduler-internals/、/os/eevdf-scheduler/）に譲り、ここでは「なぜ作り直されたか」に絞ります。

系統樹（採用バージョンと主要な分岐動機）

  O(n)スケジューラ        〜2.4         全走査で良さ(goodness)を計算
        │  動機: 選択コストがタスク数に比例 → 多コアで破綻
        ▼
  O(1)スケジューラ        2.6.0(2003)  優先度別キュー＋ビットマップ
        │  動機: 対話性ヒューリスティックが複雑・脆弱
        ▼
  CFS                     2.6.23(2007) vruntime＋赤黒木で公平を原理化
        │  動機: 配分量とレイテンシを分離できない
        ▼
  EEVDF                   6.6(2023)    lag(適格性)＋仮想デッドライン

第1世代 O(n) ── 全走査という素朴さの限界

初期 Linux のスケジューラは、schedule() のたびに実行可能タスクを1つ残らず走査し、各タスクの「良さ（goodness）」を計算して最大のものを選びました。良さは残りタイムスライス・nice 値・直近のキャッシュ親和性などの加重和です。

schedule() の骨子（概念）:
  best = NULL; best_goodness = -1
  for p in runqueue:            # ← ここが O(n)
      g = goodness(p)
      if g > best_goodness:
          best_goodness = g; best = p
  switch_to(best)

設計は素直ですが弱点は二つ。第一に選択コストが実行可能タスク数 n に比例します。第二に、ランキューがシステム全体で1本だったため、CPU が増えるほど単一ロックの競合とキャッシュ行の取り合いが激化しました。タスク数が少ない時代には実用的でしたが、SMP（対称マルチプロセッシング）の普及で「選択そのものが律速する」状況が見えてきます。これが次世代の目標、選択を定数時間にへ直結します。

第2世代 O(1) ── ビットマップで選択を定数時間に

2.6.0（2003年）の O(1) スケジューラは、選択コストをタスク数から切り離しました。鍵は優先度ごとに独立したキューと優先度ビットマップです。優先度は 140 段階（リアルタイム 0–99＋通常 100–139）で、各段に FIFO のリストを持ちます。

active配列: 140本の優先度別キュー＋140ビットのビットマップ

  bitmap: 0001 0000 ... 1000   ← 1のビット = 非空のキュー
  「最高優先度の非空キュー」= 最初に立っているビット
   → ビットスキャン命令で固定時間に求まる

最高優先度の非空キューは、ビットマップの先頭ビットを CPU 命令（ビットスキャン）で求めるだけなので、優先度段数が一定なら選択は O(1)。さらにランキューを per-CPU に分割し、第1世代のグローバルロック問題も解きました。スライスを使い切ったタスクは expired 配列へ移し、active が空になったら両配列を入れ替える（O(1) で「次のエポック」へ）巧妙さもありました。

問題は別の場所にありました。対話的タスクをどう優先するかです。O(1) は睡眠時間の長さからタスクの「対話性」を推定し、優先度に最大±5のボーナス／ペナルティを与えました。

第3世代 CFS ── 公平を物差しに変える

2.6.23（2007年）の CFS（Completely Fair Scheduler）は、ヒューリスティックを捨て、公平そのものを測れる量に変換しました。中心は vruntime（重み付き仮想実行時間） で、実行可能タスクを vruntime をキーにした赤黒木に並べ、最小のものを次に走らせます。

• 選択は左端ノードのキャッシュで実質 O(1)、再挿入は O(log N)。O(1) の「定数時間」を概ね保ちつつ、優先度段数という離散性から解放されました。
• nice 値は重みテーブルに変換され、vruntime の進む速さと持ち時間に一貫して効きます。対話性の推定式は不要になりました。

つまり CFS は「速さ（O(1) の成果）」を保ったまま、「何が良いか（公平）」を場当たりでなく原理で定義し直した世代です。内部の vruntime・赤黒木・nice の効き方は /os/cfs-scheduler-internals/ に詳しく、選ばれる単位の状態遷移とランキュー構造は /os/scheduler-state-machine/ を参照してください。

それでも残った弱点が一つ。CFS が均すのは長期の配分量だけで、「いつ走り始めるか」というレイテンシを配分量と切り離して指定できません。対話タスクの応答性を上げる手段は nice か wakeup 時の vruntime ボーナスに限られ、後者は再びヒューリスティックでした。これが EEVDF の動機です。

第4世代 EEVDF ── レイテンシを一級市民にする

6.6（2023年）の EEVDF（Earliest Eligible Virtual Deadline First）は、1995年の論文に基づき、CFS の土台（vruntime・重み・赤黒木）を継承したまま二つの軸を追加しました。

• lag（適格性）：理想配分と実配分の差を符号付きで会計し、lag >= 0（受け取り不足）のタスクだけを候補にします。取り過ぎたタスクを構造的に除外する点が、vruntime 最小なら選ばれ得た CFS との違いです。
• 仮想デッドライン：要求スライス r から「いつまでに使い終えるべきか」を定め、適格タスクの中で最早を選びます。短いスライスを要求すれば配分量を変えずにレイテンシだけ下げられる——CFS で一体だった二つのノブが分離しました。

詳細な探索手順と sleep 時の lag 保存は /os/eevdf-scheduler/ にあります。重要なのは、これが置き換えではなく拡張だという点です。土台が共通なので、CFS の理解はそのまま EEVDF に生きます。

4世代を一表で比較する

まとめ

• 系譜は 計算量 → 公平の原理化 → レイテンシ制御 という動機の連鎖で読める。各世代の弱点が次の設計目標になった。
• O(n) は全走査ゆえタスク数に比例して律速し、O(1) はビットマップで選択を定数時間にしたが対話性推定が脆かった。
• CFS は vruntime と赤黒木で公平を物差しに変え、EEVDF は lag と仮想デッドラインでレイテンシを配分量から分離した。
• 切り替えコストそのものは /os/context-switch/、各方式の深掘りは /os/cfs-scheduler-internals/ と /os/eevdf-scheduler/ を参照。