EEVDFスケジューラとCFSからの移行

CFSが抱えていた限界

CFS（/os/cfs-scheduler-internals/）は vruntime が最小のタスクを選ぶ一本のルールで長期的な公平を実現しました。しかし「いつ走らせるか」というレイテンシの要求を直接は表現できません。CFS で対話的タスクの応答性を上げる手段は nice か、wakeup 時の vruntime ボーナスといったヒューリスティックに限られ、しかも nice は配分量（どれだけ走るか）とレイテンシ（どれだけ早く走り始めるか）を分けられませんでした。

EEVDF（Earliest Eligible Virtual Deadline First）は1995年の論文に基づく方式で、Linux 6.6（2023年）で CFS を置き換えました。狙いは明快です。長期の公平（配分量）と短期の応答性（レイテンシ）を別々のノブで制御すること。土台の vruntime・重み・赤黒木は CFS から引き継ぐので、CFS の理解はそのまま生きます。

lag ── 公平からのズレを符号付きで測る

中心概念が lag（ラグ、遅れ） です。lag は「理想的に配分されるべきだった CPU 時間 から 実際に受け取った CPU 時間 を引いた差」で、各タスクの公平からのズレを符号付きで表します。

ある瞬間のタスク i について:

  lag_i = S_i - s_i

  S_i = そのタスクが「理想のマルチタスクCPU」で
        受け取っているはずの重み付きCPU時間
  s_i = 実際に受け取ったCPU時間

• lag > 0：本来より 受け取り不足。もっと走る権利がある。
• lag < 0：本来より 受け取り過多。少し遠慮すべき。
• lag = 0：ちょうど公平。

全タスクの lag の重み付き総和は、設計上つねに 0 になります。誰かが受け取り過ぎれば、その分だけ別の誰かが不足する——パイの取り合いなので当然です。EEVDF は CFS の vruntime をこの lag の枠組みで再解釈し、lag をキューの基準値 vruntime とタスクの vruntime の差から導きます。

eligibility ── 走る資格のあるタスクだけを候補にする

EEVDF の1つ目の判断軸が eligibility（適格性） です。ルールはこうです。

これが CFS との決定的な違いです。CFS は単純に vruntime 最小を選ぶため、ひとたび CPU を多く使ったタスクでも他より vruntime が小さければ選ばれ得ました。EEVDF はまず「過剰に使ったタスク」を候補から除外し、取り過ぎたタスクが連続で走り続けて他を押しのける事態を構造的に防ぎます。不適格なタスクも時間経過で S_i が伸びて lag が回復し、やがて適格に戻ります。

仮想デッドライン ── 適格タスクの中で順番を決める

適格なタスクが複数あるとき、どれを先に走らせるか。ここで2つ目の軸 仮想デッドライン（virtual deadline） が効きます。各タスクには 要求スライス（request size） r が与えられ、その分を「いつまでに使い終えるべきか」の締め切りを仮想時間上に置きます。

仮想デッドライン VD_i = ve_i + r_i / weight_i

  ve_i     = タスクが適格になった時点の仮想時間（virtual eligible time）
  r_i      = 要求スライス（一度に走りたい長さ。既定はnice由来の基準値）
  weight_i = タスクの重み

EEVDF は 適格なタスクの中で仮想デッドラインが最も早いものを選びます。名前の通り「Earliest Eligible Virtual Deadline First」です。ここで重要なのは r（要求スライス）の効果です。

• 短いスライスを要求するタスクほどデッドラインが近くなり、優先的に選ばれます。締め切りまでの猶予が短いからです。
• だから対話的タスクは「短いスライスを頻繁に」要求することで、配分量（重み）を変えずに レイテンシだけ を下げられます。

この r こそ、CFS が分けられなかった「配分量」と「応答性」を切り離すノブです。Linux では sched_setattr の sched_runtime フィールドを通じてタスクごとに要求スライスを設定でき、未指定なら sched_base_slice_ns（既定 3ms）が使われます。

赤黒木はどう変わったか

CFS は vruntime をキーに赤黒木へ並べ、最小（左端）を選んでいました。EEVDF も キーは vruntime のまま ですが、各部分木に「その部分木に含まれる最小の仮想デッドライン（min_deadline）」を補助情報として持たせます。vruntime 順に並ぶことで 適格なタスク（lag が非負）はおおむね左側の連続範囲 に収まり、その範囲を min_deadline で枝刈りしながら デッドライン最早のタスクを O(log N) で探索 します。

探索の骨子:
  1. キューの基準仮想時間から「適格ライン」を決める
     （vruntime順なので適格タスクは左側の範囲に収まる）
  2. 木を下りつつ、各ノードで
       - そのタスクが適格か（vruntimeが適格ライン以下か）
       - 部分木のmin_deadlineで枝刈りしつつ仮想デッドライン最早か
     を同時に見て候補を絞る
  3. 適格 かつ デッドライン最早 のタスクを返す

CFS の「左端を取るだけ」より探索はやや重くなりますが、計算量は O(log N) に収まり、得られるのは レイテンシ要求を反映した選択 です。

sleepと負のlagの扱い

I/O 待ちから起きたタスクの lag を、CFS のように単純へ引き上げてしまうと公平が崩れます。EEVDF は 眠る直前の lag を保存し、復帰時に復元 します。受け取り過多（負の lag）のまま眠ったタスクは、起きても不適格な状態から始まり、すぐには独占できません。逆に不足（正の lag）で眠ったタスクは、起きたときに適格なので速やかに走れます。lag を一貫した会計として持ち続けることで、ヒューリスティックに頼らず対話性と公平を両立します。

まとめ

• EEVDF は lag（理想配分と実配分の差） を符号付きで会計し、lag >= 0 の 適格タスク だけを候補にする。
• 適格タスクの中から 仮想デッドラインが最早 のものを選ぶ。デッドラインは 要求スライス r で近くも遠くもなる。
• r により、CFS では一体だった 配分量（重み） と レイテンシ（応答時間） を別々のノブで制御できる。
• vruntime・重み・赤黒木という CFS の土台は継承 され、選択基準にレイテンシ要求が組み込まれた点が本質的な進化。
• スケジュールされる単位は /os/process-thread/、古典的な方式との対比は /os/scheduling/ も参照。