SCHED_DEADLINEとCBS（Constant Bandwidth Server）

固定優先度では設計できない問題

SCHED_FIFO/SCHED_RR のような固定優先度方式は、「どのタスクを何番の優先度に置けば全員が間に合うか」を人間が手で設計し、レートモノトニック解析などで検証する必要があります。タスクが1本増えるたびに全体の優先度割り当てを見直さねばならず、しかも単一プロセッサでの理論利用率上限は約 69%（タスク数 n が大のとき ln 2）に留まります。

SCHED_DEADLINE（Linux 3.14 以降）はこの設計問題そのものを排します。タスクは優先度という相対値ではなく、自分が必要とする時間量を絶対値で宣言し、スケジューラがその宣言から自動的に順序と帯域を導きます。クラス階層では deadline は realtime（FIFO/RR）より上位に置かれ、/os/realtime-scheduling/ で扱った FIFO/RR タスクよりも常に先に走ります。

3つのパラメータが宣言するもの

deadline タスクは sched_setattr で次の3つを宣言します。意味を正確に押さえることが全ての出発点です。

runtime  : 1周期あたり必要とする実行時間（実行予算 Q）
deadline : 各起床（job 到着）から runtime を消化し終えたい相対締め切り D
period   : runtime を要求する繰り返し間隔（周期 P）
制約: runtime <= deadline <= period

ここで重要なのは deadline が 相対値だという点です。タスクの新しいジョブが時刻 t に到着すると、そのジョブの絶対締め切りは t + deadline として計算されます。EDF はこの絶対締め切りを比較します。deadline < period を許す（制約付き締め切り）ことで、周期より短い厳しい締め切りも表現できます。

EDFが順序を決める

スケジューラ本体は EDF（Earliest Deadline First、最早締め切り優先） です。ルールは一行で、「実行可能なタスクのうち、絶対締め切りが最も早いものを走らせる」だけです。優先度は固定値ではなくジョブの締め切りから動的に決まり、新しいジョブが到着して締め切りが更新されるたびに順位は入れ替わります。

H, M, L が実行可能で、絶対締め切りが
  d_H = 105, d_M = 110, d_L = 130 のとき
  → 105 が最早なので H を走らせる
H の締め切りが period 分後ろへ更新され d_H = 205 になると
  → 次は d_M = 110 が最早になり M へ切り替わる

EDF の決定的な強みは最適性です。単一プロセッサ上で実行可能タスク集合の利用率総和が 1 以下なら、EDF は必ず全締め切りを守れます。固定優先度の約 69% に対し、EDF は利用率 100% まで使い切れます。これが /os/cfs-scheduler-internals/ の公平指向や /os/eevdf-scheduler/ の遅延指向とは別世界の、締め切り保証に特化した設計です。

CBSがオーバーランを隔離する

EDF をそのまま使うと致命的な弱点があります。あるタスクが宣言した runtime を超えて走った（オーバーラン）瞬間、CPU を余分に奪われた他タスクの締め切りが巻き添えで破られます。EDF は「締め切りが最早のものを走らせる」だけで、各タスクが宣言量を守っているかは関知しないからです。

これを隔離するのが CBS（Constant Bandwidth Server、一定帯域サーバー） です。CBS は各 deadline タスクを1つのサーバーとして扱い、消費した実行時間をナノ秒精度で実行時に追跡します。核心の動作はこうです。

タスクが走るたび: 残り予算 -= 実際に走った時間
残り予算が 0 に達したら（runtime を使い切ったら）:
  → タスクをスロットル（throttle）し、走らせない
  → 次の周期境界まで待機させる
周期境界に達したら:
  → 予算を runtime まで補充（replenish）
  → 絶対締め切りを period 分だけ後ろへ更新して再開可能にする

この仕組みにより、暴走したタスクや想定より重くなったタスクは自分に割り当てた利用率の檻に必ず閉じ込められます。CBS が補充時に「予算 = runtime かつ 締め切り += period」とセットで更新するため、使い切った直後にすぐ走り続けることはできず、利用率 runtime/period を長期的に超えられません。EDF が「誰を走らせるか」を最適に決め、CBS が「各自が宣言帯域を超えないこと」を強制する——この二段構えが SCHED_DEADLINE の本質です。

CBSのウェイクアップ規則

CBS が帯域を一定に保つうえで微妙なのが、長く眠っていたタスクが起きたときの扱いです。古い締め切りと残り予算をそのまま使うと、眠っていた分を一気にまとめて要求でき、瞬間的に帯域を超えてしまいます。そこで CBS は起床時に次の判定を行います。

起床時刻 t に対し、現在の残り予算 q と絶対締め切り d を見て
  q / (d - t) > runtime / period を満たすなら
  → 予算と締め切りを使うと帯域超過になる
  → 締め切りを d = t + deadline に、予算を runtime にリセット
そうでなければ → 既存の q と d をそのまま引き継ぐ

つまり「残っている予算を残り時間で割った瞬間利用率が、宣言利用率を超えるなら巻き直す」という不変条件を保ちます。これにより、長時間スリープしたタスクが復帰しても他タスクの帯域を侵食しません。

許容制御（admission control）

CBS は各タスクを帯域に閉じ込めますが、そもそも全タスクの帯域合計がコア容量を超えていたら、いくら隔離しても全員は間に合いません。これを入口で防ぐのが許容制御（admission control） です。Linux は新しい deadline タスクの追加や属性変更のたびに、利用率総和を検査します。

スケジュール可能の必要条件:
  Σ (runtime_i / period_i) <= M
  （M は対象ルートドメイン内の CPU 数）
この不等式を満たさない追加・変更は EBUSY で拒否される

単一コアなら総和が 1 を超える集合は受け付けられません。マルチコアではコア数まで許されますが、グローバル EDF はコア数ぶんの容量があっても個々の締め切りを常には保証できない（マルチプロセッサ EDF の既知の限界）ため、Linux の保証は厳密には「各 CPU に対する利用率上限の検査」というやや保守的な形を取ります。なお既定では全帯域の予約は許されず、sched_rt_runtime_us/sched_rt_period_us が realtime+deadline 全体に割く上限（既定で 1 秒あたり 0.95 秒）を決め、残りは通常タスクの飢餓を避けるために確保されます。

まとめ

• SCHED_DEADLINE はタスクを runtime/deadline/period の3つで宣言させ、固定優先度の手作業設計を不要にする。runtime <= deadline <= period が制約。
• EDF は絶対締め切り（到着時刻 + deadline）が最早のタスクを動的に選び、単一CPUでは利用率100%まで全締め切りを守れる最適アルゴリズム。
• CBS は各タスクを利用率 runtime/period の帯域に閉じ込め、予算切れでスロットル・周期境界で補充し、オーバーランの巻き添えを隔離する。起床時には瞬間利用率の不変条件で締め切りを巻き直す。
• 許容制御は Σ(runtime/period) <= CPU数 を入口で検査し、超過する追加を EBUSY で拒否する。RT スロットリングが全帯域予約を防ぎ通常タスクの飢餓を避ける。
• プリエンプトや起床の下回りは /os/kernel-preemption/ も参照。