リアルタイムスケジューリング（SCHED_FIFO/RR/DEADLINE）

リアルタイムとは「速い」ではなく「間に合う」

リアルタイムスケジューリングの目的はスループットでも公平でもなく、締め切り（デッドライン）を必ず守ることです。モーター制御や音声処理では、1回でも処理が間に合わなければ結果が破綻します。だから/os/cfs-scheduler-internals/のように全タスクへ公平に CPU を配る方式は不向きで、Linux はそれらより常に優先される専用クラスを用意しています。

Linux のスケジューラはクラスの階層で動き、上位クラスに実行可能タスクがある限り下位は一切走りません。順位は stop → deadline → realtime（FIFO/RR）→ CFS/EEVDF → idle です。つまり SCHED_DEADLINE が最優先、その下に SCHED_FIFO/SCHED_RR、さらに下に通常の/os/scheduling/が位置します。

SCHED_FIFO ── 固定優先度の純粋なプリエンプション

SCHED_FIFO は最も単純です。各タスクは 1〜99 の固定リアルタイム優先度を持ち、ルールはこれだけです。

1. 実行可能なタスクのうち、最高優先度のものを走らせる
2. 同じ優先度内では FIFO（先に並んだ者が先に走る）
3. 一度走り始めたら、自分でCPUを手放すか、
   より高い優先度のタスクが起きるまで走り続ける

重要なのはタイムスライスが無い点です。同じ優先度のタスクが複数あっても、いま走っているタスクが block・yield・終了しない限り CPU を独占し続けます。より高優先度のタスクが wake up した瞬間だけプリエンプト（/os/context-switch/）されます。応答は予測可能ですが、暴走したループは同優先度以下を完全に飢餓させます。

SCHED_RR ── 同優先度にだけ入るタイムスライス

SCHED_RR（round-robin）は FIFO と同一ですが、同じ優先度の中だけにタイムスライス（既定 100ms 前後、sched_rr_timeslice_ms）を導入した点が違います。スライスを使い切ると同優先度の末尾へ回され、隣のタスクへ順番が移ります。

異なる優先度の間ではどちらも完全プリエンプティブで挙動は同じです。RR のスライスは「同点」のタスクをどう捌くかにしか効きません。

SCHED_DEADLINE ── EDF と CBS で帯域を保証する

固定優先度方式の弱点は、何本のタスクをどの優先度に置けば全員間に合うかを人間が設計しなければならない点です。SCHED_DEADLINE（Linux 3.14 以降）はこれを理論で解きます。タスクは優先度ではなく 3つの時間パラメータ を宣言します。

runtime  : 1周期で必要な実行時間（実行予算 Q）
deadline : 起床からこの時間以内に runtime を消化したい（相対締め切り D）
period   : この周期で runtime を繰り返し要求する（周期 P）
通常 runtime <= deadline <= period

スケジューラは EDF（Earliest Deadline First、最早締め切り優先） で動きます。これは「いま最も締め切りが近いタスクを走らせる」動的優先度方式で、1 プロセッサ上で実行可能タスクの利用率の総和が 1 以下なら、原理上すべての締め切りを守れる最適アルゴリズムです。

利用率 U = runtime / period
スケジュール可能の必要条件: ΣU_i <= 1（マルチコアではコア数まで）

ただし EDF をそのまま使うと、あるタスクが宣言以上に走った（オーバーラン）瞬間に他タスクの締め切りを巻き添えで壊します。これを隔離するのが CBS（Constant Bandwidth Server、一定帯域サーバー） です。

CBS が各タスクを「帯域の檻」に入れる

CBS は各 deadline タスクに (runtime, period) の帯域を割り当て、消費した実行時間を実行時に追跡します。動作の核心はこうです。

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

この仕組みにより、暴走したり想定より重くなったタスクは自分に割り当てた帯域の中に必ず閉じ込められ、他の deadline タスクの締め切りは保護されます。EDF が「誰を走らせるか」を最適に決め、CBS が「各自が宣言した帯域を超えないこと」を強制する——この二段構えが SCHED_DEADLINE の本質です。なお Linux は受付制御（admission control）も行い、ΣU がコア容量を超える deadline タスクの追加は EBUSY で拒否します。

優先度逆転 ── 高優先度が低優先度に負ける

リアルタイムで最も悪名高い障害が 優先度逆転（priority inversion） です。共有資源のロック（/os/concurrency-control/）が絡むと、高優先度タスクが低優先度タスクに事実上追い越されます。

低優先度 L がロック M を保持中
  ↓
高優先度 H が M を要求 → L がM を放すまでブロック
  ↓
中優先度 M2（ロック不要）が起きる → L をプリエンプト
  ↓
L が走れない → M を放せない → H もずっと待つ
（H が M2 に間接的に負ける = 逆転）

1997 年の火星探査機 Mars Pathfinder のリセット連発は、まさにこの古典的な優先度逆転が原因でした。待ち時間が 中優先度タスクの実行時間に依存して際限なく延びる点が致命的で、リアルタイム保証が崩れます。

優先度継承と優先度上限プロトコル

優先度逆転を防ぐ標準的手法が 優先度継承プロトコル（PIP, Priority Inheritance Protocol） です。

• 高優先度 H が、低優先度 L の持つロックで待たされたら、L は一時的に H の優先度へ引き上げられる（継承する）。
• 引き上げられた L は中優先度 M2 にプリエンプトされなくなり、素早くクリティカルセクションを抜けてロックを解放できる。
• 解放と同時に L は元の優先度へ戻り、待っていた H が即座に走る。

これにより H の待ち時間は「L のクリティカルセクション長」だけに有界化されます。Linux の pthread ミューテックスは PTHREAD_PRIO_INHERIT 属性でこれを有効化でき、内部の RT-mutex が継承を実装します。

もう一つが 優先度上限プロトコル（PCP, Priority Ceiling Protocol） で、各ロックに「それを使い得る最高優先度（上限）」を静的に与え、ロック取得時にタスクをその上限へ即引き上げます。実装は重い一方で、デッドロックを構造的に防ぎ、各タスクのブロック回数を高々1回に抑える強い性質を持ちます。

まとめ

• リアルタイムは「速い」ではなく「締め切りに間に合う」こと。Linux では deadline → FIFO/RR の順で通常タスクより常に優先される。
• SCHED_FIFO は固定優先度＋FIFO、SCHED_RR は同優先度内だけタイムスライスを足したもの。どちらもタイムスライスは異優先度には効かない。
• SCHED_DEADLINE は EDF（最早締め切り優先・利用率100%まで最適）で選び、CBS（一定帯域サーバー）が各タスクを宣言帯域に閉じ込めて締め切りを隔離する。
• 優先度逆転はロック越しに高優先度が低優先度へ負ける現象で、優先度継承（PIP）／**優先度上限（PCP）**で待ち時間を有界化して防ぐ。
• スケジュールされる単位やプリエンプトの仕組みは/os/process-thread/も参照。