EDF (Earliest Deadline First)（イーディーエフ）
英語表記: EDF (Earliest Deadline First)
概要
EDF（Earliest Deadline First）は、オペレーティングシステム（OS）のスケジューリング機能、特にリアルタイム処理が求められる環境で利用される、非常に重要なアルゴリズムの一つです。これは、実行可能なタスク群の中から、「最も締切（デッドライン）が近いタスク」を最優先で実行するという、直感的でありながら非常に効率的な動的優先度スケジューリング方式です。
この方式は、OSのプロセス管理において、CPUの利用権をどのプロセスに割り当てるかを決定する際に使われます。リアルタイムシステムでは、単に速く処理するだけでなく、「定められた時間内に処理を完了する」ことが絶対条件となるため、EDFはデッドラインの厳守を最優先目標とする点で、他の一般的なスケジューリング方式と一線を画しています。
詳細解説
EDFは、OSの基本機能であるプロセス管理におけるスケジューリングの中でも、特に厳しい時間制約を持つリアルタイム処理のために設計されています。その最大の目的は、システム内のすべてのタスクがそれぞれの設定された締切時刻（デッドライン）を確実に守れるように、CPUの利用を最適化することにあります。
動作原理：動的優先度の真髄
EDFの核となるのは「動的優先度」である点です。従来の一般的なスケジューリング方式（例えば、静的優先度やラウンドロビン）では、一度決められた優先度や実行順序はあまり変わりません。しかし、EDFでは、タスクの優先度が時間とともに変化します。
- デッドラインの設定: 各タスクには、いつまでに処理を完了しなければならないかを示すデッドラインが設定されます。
- 優先度の決定: スケジューラは、実行待ち行列にあるすべてのタスクを確認し、現時点で最もデッドラインまでの残り時間が短いタスクに、最も高い優先度を割り当てます。
- 実行: 優先度が最も高いタスクがCPUを獲得し、実行されます。
- 再評価: 新しいタスクが到着したり、現在実行中のタスクが完了したり、あるいはシステムタイマーの割り込みが発生するたびに、スケジューラはデッドラインに基づいて優先度を再評価し、必要に応じてプリエンプション（実行中のタスクを中断して別のタスクに切り替えること）を行います。
この仕組みのおかげで、システム全体としてデッドラインをミスする（タスクが時間内に終わらない）リスクを最小限に抑えることができるのです。デッドラインという時間軸を直接スケジューリングの基準にしている点が、本当に素晴らしいアイデアだと感じますね。
EDFの優位性
EDFは、理論上、特定の条件下において「最適なスケジューリングアルゴリズム」であることが証明されています。これは、タスクセットの実行可能性（すべてのデッドラインを満たせるかどうか）を最大限に引き出す能力があることを意味します。
特に重要なのは、CPU利用率の観点です。EDFは、タスクの周期や実行時間が様々であっても、CPU利用率が100%に近づくまで、理論的にはすべてのタスクのデッドラインを守りながら動作できます。これは、静的優先度方式の代表であるRM（Rate Monotonic）が、一般的にCPU利用率の上限が約69%程度に制限されるのと比べると、非常に大きなメリットです。限られたリソースをギリギリまで使いこなせるのは、組み込みシステムにとっては非常に魅力的ですよね。
OSにおける位置づけ
このEDFは、OSのプロセス管理における心臓部、すなわちスケジューラとして機能します。特に、自動車の制御システム、産業用ロボット、医療機器など、一瞬の遅れが許されないハードリアルタイム環境で真価を発揮します。これらの環境では、デッドラインを守れないことは致命的な事故につながりかねません。
しかし、動的優先度を常に計算し続けるため、RMなどの静的優先度方式に比べて、スケジューリングのためのオーバーヘッド（OSが費やす計算時間）が大きくなるというトレードオフも存在します。高性能なCPUを持つ現代のRTOSでは、このオーバーヘッドは許容される傾向にありますが、設計時には注意が必要です。
具体例・活用シーン
EDFの概念は、私たちが日常生活で直面する「締切管理」と驚くほど似ています。この比喩を通じて、EDFがどのように機能しているかを理解してみましょう。
宅配便の仕分け作業（比喩）
ある物流センターの仕分け担当者（これがOSのスケジューラです）が、大量の荷物（タスク）を配送しなければならない状況を想像してください。
- タスクの到着: 午前中に多くの荷物がセンターに到着しました。荷物にはそれぞれ「本日18時までに配達」「本日14時までに配達」「明日午前中までに配達」といった配送締切時間（デッドライン）が記されています。
- EDFの適用: 仕分け担当者は、荷物を仕分ける際、最も締切が早い「本日14時までに配達」の荷物を最優先でトラックに積み込みます。次に締切が早い「本日18時まで」の荷物、そして最後に「明日午前中」の荷物を処理します。
- 動的変化: 途中で「緊急！1時間以内に届けなければならないクール便」という新しいタスク（デッドラインが非常に近い）が飛び込んできた場合、担当者はすぐに現在作業中の荷物を中断し、そのクール便を最優先で処理します（プリエンプション）。
この仕分け担当者が行っている判断こそが、まさにEDFです。デッドラインまでの残り時間という動的な要素に基づいて、常に最も重要なタスク（締切が近いタスク）を選び出すことで、すべての締切を破らないように最大限の努力をしているのです。OSも同じように、CPUという限られたリソースを使って、すべてのプロセスの締切厳守を目指しているわけです。
実際の活用例
- リアルタイム制御システム: 産業用ロボットのアーム制御や、CNC（コンピュータ数値制御）機械の動作制御など、厳密な時間精度が求められる場面で、EDFはタスクの応答性を保証するために使われます。
- 航空宇宙システム: 飛行機の操縦翼面やエンジン制御など、安全性が最優先されるシステムでは、デッドラインの保証能力が高いEDFが採用されることがあります。
- マルチメディア処理: 音声や動画のストリーミング再生において、途切れることなく滑らかにデータを表示するためにも、EDFのようなリアルタイムスケジューリングが役立ちます。
資格試験向けチェックポイント
EDFは、特に難易度の高い応用情報技術者試験や、基本情報技術者試験の午後問題（組み込みシステムやOS分野）で出題される可能性が高い、重要な概念です。ITパスポートでは詳細なアルゴリズムの理解までは求められませんが、リアルタイム処理の文脈で知っておくと有利です。
| 試験レベル | 典型的な出題パターンと対策 |
| :— | :— |
| 基本情報・応用情報 | 動的優先度スケジューリングの代表例として問われます。EDFの定義（最も締切の早いタスクを優先）を正確に覚えましょう。 |
| 応用情報（特に） | 静的優先度方式（RM: Rate Monotonic）との比較が頻出します。RMが「周期の短いタスクを優先」（静的）であるのに対し、EDFは「デッドラインの近いタスクを優先」（動的）であることを区別できるようにしてください。 |
| 全レベル共通 | EDFがリアルタイムOSのスケジューリング機能に分類されることを理解し、その目的が「デッドラインの厳守」であることを確認してください。 |
| 重要キーワード | 「動的優先度」「デッドライン」「最適スケジューリング」「プリエンプション（横取り）」は、EDFを説明する際の必須ワードです。 |
試験対策のヒント:
EDFは、理論上は優れていますが、実装の複雑さ（常にデッドラインを追跡し、優先度を計算し直す手間）がデメリットとなる点も押さえておきましょう。この「理論上の最適性」と「実装上のオーバーヘッド」のバランスに関する知識は、応用情報レベルで問われることがあります。
関連用語
EDFを理解する上で、比較対象となる用語や、関連する上位概念がいくつか存在します。
- RM (Rate Monotonic)（レートモノトニック）: EDFと並び称されるリアルタイムスケジューリングアルゴリズムです。こちらは「周期が最も短いタスク」に最高の優先度を与える静的優先度方式であり、EDFとの比較対象として非常に重要です。
- リアルタイムOS (RTOS): EDFのようなリアルタイムスケジューリングを中核機能として持つOSです。デッドライン厳守を保証するために設計されています。
- 動的優先度スケジューリング: タスクの実行中に優先度が変化する方式全般を指します。EDFはその代表格です。
関連用語の解説については、現在、情報不足です。特に、EDFとRMの具体的なCPU利用率の限界値（EDFが約100%、RMが約69%）に関する詳細な比較情報や、これらのアルゴリズムが抱える「優先度逆転問題」に関する情報などが加わると、理解が深まります。
