RTOSのスケジューリング（RMS・EDF）

「間に合う」を保証するということ

汎用OSのスケジューラは公平性やスループットを最適化しますが、リアルタイムシステムで問われるのは平均ではなく最悪ケースです。「割り込みから何マイクロ秒以内に必ず応答する」という締切（デッドライン）を、どんなに条件が重なっても破らないと保証できるか——これがRTOS（リアルタイムOS）のスケジューリングが解こうとしている問題です。ここでは周期タスクの集合を対象に、なぜ間に合うと言い切れるのかを、スケジューリング可能性解析の原理から見ていきます。CPU側の割り込み機構やコンテキストスイッチの土台は /os/ 側の話題と地続きです。

優先度ベースのプリエンプティブスケジューリング

RTOSの中核は極めて単純な規則です。実行可能状態にあるタスクのうち、最も優先度の高いものを常に走らせる。そして、より高い優先度のタスクが実行可能になった瞬間、走行中のタスクを中断してCPUを奪う——これがプリエンプション（横取り）です。タイムスライスで公平に回すのではなく、優先度が絶対的な序列を与えます。

この方式が成立する前提は、コンテキストスイッチと割り込み応答が短く、かつ上限が確定していることです。最悪ケースを積み上げるには、各要素の遅延に必ず上界がなければなりません。周期タスクは通常、次の3つの量で特徴づけます。

全タスクのCPU利用率の総和 U（各タスクの C/T を合計した値）が1を超えれば、どんな方式でも物理的に間に合いません。問題は「1未満のどこまでなら保証できるか」で、その答えが方式ごとに異なります。

RMS：周期が短いほど高優先度

RMS（Rate Monotonic Scheduling、レート単調）は固定優先度方式の代表です。規則は一つ、周期 T が短いタスクほど高い優先度を割り当てる。周期が固定なら優先度も一度決めたら変わりません。実装が単純で、優先度の付け替えが不要なため、多くの商用RTOSの標準的な使い方に馴染みます。

RMSの美点は、Liu と Layland（1973）が示したスケジューリング可能性の十分条件が閉じた形で書けることです。n個のタスクに対し、利用率の総和 U が次の上界以下なら、必ず全締切を守れます。

U ≤ n × (2^(1/n) − 1)

  n = 1 : 1.000
  n = 2 : 0.828
  n = 3 : 0.780
  n → ∞ : ln 2 ≈ 0.693  （約69%）

タスク数が増えると上界は約69%に収束します。つまりCPUの約3割を「保険」として空けておけば、周期と実行時間がどんな配置でもRMSは間に合う、という強い保証です。ただしこれは十分条件にすぎません。69%を超えていても実際にはスケジュール可能な場合が多く、そこを正確に判定するのが後述の応答時間解析です。

EDF：締切が近いものを優先

EDF（Earliest Deadline First、最早デッドライン優先）は動的優先度方式です。優先度を静的に固定せず、その瞬間に絶対デッドライン（起動時刻＋相対デッドライン）が最も早いタスクを走らせます。同じタスクでも起動のたびに締切の絶対時刻が変わるため、優先順位は動的に入れ替わります。

EDFの決定的な強みは、暗黙デッドライン（D = T）の周期タスクに対して利用率 U が1以下でありさえすればスケジュール可能という点です。すなわち理論上CPUを100%まで詰め込める。RMSの69%と比べ、同じハードウェアでより多くの負荷をさばけます。

理論性能はEDFが上ですが、実務でRMSが根強いのには理由があります。EDFは締切ごとにレディキューを整列し直すオーバーヘッドがあり、何より過負荷（U が1超）に弱い。RMSなら負荷超過時も低優先度タスクから順に締切を落とすため、重要タスクは守られます。一方EDFは、一つ締切を落とすと連鎖的に他タスクの締切も崩れる「ドミノ効果」を起こしやすく、最悪ケースの振る舞いが読みにくいのです。

応答時間解析：本当に間に合うかを個別に検証

利用率の上界チェックは手軽ですが保守的です。固定優先度方式で必要十分に判定するのが応答時間解析（RTA）です。タスク i の最悪応答時間 R は、自身の実行時間に、より高優先度タスクからの妨害（プリエンプション）を積み上げて求めます。R が相対デッドライン D 以下ならスケジュール可能です。

R_i = C_i + Σ ceil( R_i / T_j ) × C_j
              j∈hp(i)

  hp(i) : i より高優先度のタスク集合
  ceil(x) : x の天井関数（切り上げ）

右辺に R が現れる再帰式なので、R = C_i から始めて値が収束するまで反復します。ceil(R/T_j) は「応答時間の窓の間に高優先度タスク j が何回起動して割り込んでくるか」を表し、その回数ぶんの実行時間が妨害として上乗せされます。この解析があるからこそ、利用率が69%を超える設計でも「このタスク集合は確かに全締切を守る」と定量的に言い切れます。

優先度逆転：低優先度が高優先度を止める

ここまでは各タスクが独立に走る前提でしたが、実際には共有資源（ミューテックスで保護された領域など）を奪い合います。ここで厄介な現象が起きます。

これは理論上の懸念ではありません。1997年の火星探査機 Mars Pathfinder が現地で繰り返しリセットを起こした原因が、まさにこの優先度逆転でした。中間優先度の通信タスクが、高優先度タスクの待つ資源を握った低優先度タスクを締め出し、ウォッチドッグが暴走とみなして再起動をかけていたのです。

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

対策の核心は、ブロック時間に上界を与えることです。青天井を有界化できれば、応答時間解析にブロック項 B を足すだけで保証が復活します。代表的な2つのプロトコルがあります。

優先度継承（Priority Inheritance Protocol）は、資源を握った L が H の優先度を借りることで、中間タスク M の割り込みを排除します。Mars Pathfinder はこの機能を有効化する設定を遠隔で送り込み、復旧しました。より強力な優先度上限プロトコル（Priority Ceiling Protocol）は、ブロックを高々1回に抑えデッドロックまで防げるため、厳密な最悪ケース保証が要る系で好まれます。

まとめ

RTOSのスケジューリングは、優先度ベースのプリエンプションという単純な規則の上に、最悪ケースを積み上げて締切を数学的に保証する体系です。RMSは周期でまるごと優先度を固定する実装容易な方式で約69%の利用率まで無条件に保証し、それを超える領域は応答時間解析で個別に詰めます。EDFは締切を動的に見て理論上100%まで使えますが過負荷に脆く、採用は慎重に判断します。そして共有資源が入った瞬間に立ちはだかる優先度逆転を、優先度継承や優先度上限で有界化し解析へ織り込むことで、実システムの締切保証が完成します。より低いレイヤーで応答時間の上界を支えるタイマや割り込みの土台は /hardware-components/、制御周期そのものの設計思想は /dsp-control/ の観点と合わせて理解すると立体的になります。