リアルタイムスケジューリングのスケジューラビリティ解析

スケジューラビリティ解析とは「間に合う証明」

/os/realtime-scheduling/が「どう動かすか」を扱うのに対し、スケジューラビリティ解析はそのタスク集合が原理上すべての締め切りを守れるかを、実機で動かす前に数理で判定することを指します。リアルタイムの正しさは平均性能ではなく最悪ケースで決まるため、テストではなく証明が要ります。

前提として周期タスクモデルを置きます。タスク i は周期 T_i、最悪実行時間（WCET）C_i、相対締め切り D_i を持ち、利用率を U_i = C_i / T_i と定義します。多くの基本理論は単一プロセッサ・独立タスク・D_i = T_i（暗黙締め切り）を仮定します。

EDF の最適性と利用率テスト

動的優先度方式の EDF（Earliest Deadline First） は、各時点で最も締め切りが近いジョブを走らせます。暗黙締め切りの単一プロセッサでは、次の必要十分条件が成り立ちます。

タスク集合がEDFでスケジュール可能 <=> ΣU_i <= 1
（U_i = C_i / T_i、総利用率が1以下）

利用率100%まで使い切れるため、EDF は単一プロセッサにおける最適な方式です。最適とは「他のどんなアルゴリズムでもスケジュール可能なら EDF でもスケジュール可能」という意味で、可否の境界そのものを実現します。締め切りが周期より短い（D_i < T_i）一般のケースでは利用率だけでは判定できず、後述の需要境界関数や応答時間解析が必要になります。

レート単調（RM）の最適性と Liu-Layland 境界

固定優先度（静的優先度）方式では、優先度の付け方が可否を左右します。レート単調（RM, Rate Monotonic） は周期が短いタスクほど高優先度を与える規則で、暗黙締め切りのもとで固定優先度方式の中で最適であることが Liu と Layland により 1973 年に示されました。D_i = T_i でない場合は、締め切りが短いほど高優先度にするデッドライン単調（DM, Deadline Monotonic） が固定優先度の最適規則になります。

RM の有名な利用率テストが Liu-Layland 境界です。

n本のタスクがRMでスケジュール可能（十分条件）:
  ΣU_i <= n * (2^(1/n) - 1)

n=1: 1.000
n=2: 0.828
n=3: 0.780
n→∞: ln 2 ≈ 0.693

ここで決定的に重要なのは、この境界が 十分条件であって必要条件ではない点です。総利用率が境界以下なら確実にスケジュール可能ですが、超えてもスケジュール可能なことは多いのです。境界はあらゆるタスク集合に通用させるための最悪ケース値で、ln 2 ≈ 69% はその下限です。

EDF が利用率で優れる一方、RM/DM は過負荷時に「どのタスクが先に落ちるか」が周期順で予測でき、実装も/os/scheduling/の固定優先度機構で素直に載るため、実務では今も広く使われます。

応答時間解析（RTA）── 厳密な可否判定

利用率テストの限界を超え、固定優先度で厳密に可否を判定する標準手法が 応答時間解析（RTA, Response Time Analysis） です。各タスク i の最悪応答時間 R_i（起床から完了までの最長時間）を求め、R_i <= D_i を全タスクで確認します。

R_i は「自分の実行時間 C_i」と「自分より高優先度のタスクから受ける干渉（その間に割り込んで走る時間）」の和です。高優先度タスクは応答時間の窓の中で何度も起き得るため、次の漸化式を不動点に達するまで反復します（hp(i) は i より高優先度のタスク集合）。

初期値: R = C_i
反復:   R_new = C_i + Σ_{j in hp(i)} ceil(R / T_j) * C_j
R_new = R になったら収束 = 最悪応答時間 R_i
R が D_i を超えたら、その時点で判定不能（不合格）

ceil(R / T_j) は「応答窓 R の間にタスク j が起き得る回数」を表し、各回が C_j だけ干渉します。R が増えると干渉も増えて R がさらに伸びる——この単調増加列は、総利用率が1以下なら必ず有限値に収束します。RTA は利用率テストのような十分条件ではなく、固定優先度に対する必要十分の厳密判定であり、D_i != T_i や任意の優先度割り当てにも対応できる点が強力です。

ブロッキングとマルチコアへの拡張

これまでは独立タスクを仮定しましたが、共有資源のロックが絡むと優先度逆転による待ち（ブロッキング項 B_i）が応答時間に加わります。優先度継承や優先度上限プロトコルでこの B_i を有界化したうえで、漸化式の初期値を R = C_i + B_i として解くのが実務の作法です。詳細は/os/realtime-scheduling/を参照してください。

マルチプロセッサでは話が一変します。グローバルEDFでも単一プロセッサの ΣU <= m（コア数 m）は保証になりません。これは「Dhall効果」と呼ばれ、高利用率の1本と多数の低利用率タスクが組み合わさると、総利用率が m をはるかに下回っても締め切りを落とす反例が作れます。実機では各タスクをコアへ固定する分割スケジューリング（パーティション化）に持ち込み、各コアを単一プロセッサ問題として上の理論で解くのが堅実です。なお実行時間 C_i の見積りには/os/context-switch/のオーバーヘッドやキャッシュミスを織り込む必要があり、WCET 解析そのものが別個の難問です。

まとめ

• スケジューラビリティ解析は周期タスクが締め切りを守れるかを実機前に数理で証明する手続き。最悪ケースで判定する。
• 単一プロセッサ・暗黙締め切りでは EDF が最適で、ΣU_i <= 1 が必要十分。固定優先度では RM（DM）が最適。
• Liu-Layland 境界（n(2^(1/n)-1)、n→∞ で ln 2）は RM の十分条件にすぎず、超えてもスケジュール可能なことは多い。
• 応答時間解析（RTA） は高優先度の干渉を漸化式で積み上げ収束させる必要十分の厳密判定で、D!=T や任意優先度にも対応する。
• ロックのブロッキング項やマルチコアの Dhall効果を考慮しないと保証は崩れる。スケジュールされる単位は/os/process-thread/も参照。