スケジュール期限

SCHED_DEADLINEは、 Linuxカーネルバージョン3.14以降で利用可能なCPUスケジューラであり、 ^{[1] [2]}最も早い期限優先（EDF）および一定帯域幅サーバー（CBS）^[3]アルゴリズムに基づいており、リソース予約をサポートしています。このようなポリシーでスケジュールされた各タスクは、予算Q（別名ランタイム）と期間Pに関連付けられており、どのプロセッサでも、そのタスクがP時間単位ごとにQ時間単位を必要とするというカーネルへの宣言に対応しています。これは、マルチメディアや産業用制御などのリアルタイムアプリケーションに特に適しています。ここで、Pはタスクの後続のアクティブ化間の経過時間最小値に対応し、Qはタスクの各アクティブ化に必要な最悪の実行時間に対応します。 SCHED_DEADLINE

Linuxカーネルには、さまざまなスケジューラクラスが含まれています。^[4]デフォルトでは、カーネルはカーネルのバージョン2.6.23で導入されたCompletely Fair Scheduler (CFS)と呼ばれるスケジューラメカニズムを使用します。 ^[5]内部的には、このデフォルトのスケジューラクラスは としても知られておりSCHED_NORMAL、カーネルには、(リアルタイム先入れ先出し)と(リアルタイムラウンドロビン)という名前の2つのPOSIX準拠の^[6]リアルタイムスケジューリングクラスも含まれており、どちらもデフォルトクラスよりも優先されます。^[4]スケジューリングクラスは、2014年3月30日にリリースされたLinuxカーネルメインラインのバージョン3.14でLinuxスケジューラに追加され、 ^{[7] [8]} 他のすべてのスケジューリングクラスよりも優先されます。 SCHED_FIFOSCHED_RRSCHED_DEADLINE

デフォルトのスケジューラである CFS は、さまざまなユースケースにうまく対応します。たとえば、長時間実行されるコードのコンパイルや数値計算などのバッチ ワークロードと、デスクトップ アプリケーション、マルチメディアなどの対話型アプリケーションを混在させる場合、CFS はバッチ タスクの優先順位を動的に下げて対話型タスクを優先します。ただし、アプリケーションが予測可能で正確なスケジュールを必要とする場合、通常は他のリアルタイム スケジューラである SCHED_RR または SCHED_FIFO のいずれかを使用する必要があります。これらのスケジューラは、固定優先順位を適用して優先度別にタスクをスケジュールし、SCHED_NORMAL クラスのタスクよりも前にタスクをスケジュールします。

同じシステム上で異種のタイミング要件を持つリアルタイム ワークロードを混在させる場合、 および のよく知られた問題はSCHED_RR、SCHED_FIFOこれらがタスクの優先度に基づいているため、優先度の高いタスクが予想よりも長く実行されると、優先度の低いタスクが制御不能な方法で任意に遅延される可能性があることです。

では、代わりに、タスクは、各タスク期間SCHED_DEADLINEごとに必要なタスクごとの実行時間（および各期間の開始からタスクごとの期限内に完了する必要がある）の観点から、タイミング要件を個別に宣言し、カーネルは、スケジュール可能性テストの後にそれらをスケジューラで受け入れます。ここで、タスクが割り当てられた予算よりも長く実行しようとすると、カーネルはそのタスクを一時停止し、その実行を次のアクティブ化期間まで延期します。スケジューラのこの非作業保存プロパティにより、タスク間の時間的分離が可能になります。これにより、シングルプロセッサ システムまたはパーティション化されたマルチプロセッサ システム（タスクが使用可能な CPU 間でパーティション化されるため、各タスクは特定の CPU に固定され、移行できない）では、受け入れられたすべてのタスクは、タスク自体がブロックされて実行する必要がない場合を除き、期間と同じ長さのすべての時間ウィンドウで、予算に等しい全体時間でスケジュールされることが保証されるという重要なプロパティが得られます。また、CBS アルゴリズムの特異な特性は、タスクが実行をブロックして再開している場合でも時間的な分離を保証することです。これは、タスクの起動が遅すぎる場合はいつでも、タスクのスケジュール期限を 1 周期分だけ離してリセットすることで実現されます。マルチプロセッサ上でタスクが自由に移行できる一般的なケースでは、グローバル EDF を実装しているため、グローバル EDF の一般的な遅延制限が適用されます。^[9]SCHED_DEADLINESCHED_DEADLINE

スケジューラの仕組みをよりよく理解するために、SCHED_DEADLINE期限が期間に等しい、期間が異なる可能性のあるタスクのセットを検討します。各タスクについて、構成された実行時間と (相対) 期間に加えて、カーネルは現在の実行時間と現在の (絶対) 期限を追跡します。タスクは、グローバル EDF を使用して、現在の期限に基づいて CPU 上でスケジュールされます。タスク スケジューリング ポリシーが最初に に設定されてSCHED_DEADLINEいる場合、現在の期限は現在の時刻に構成された期間を加えた時間に初期化され、現在の予算は構成された予算と同じに設定されます。タスクがいずれかの CPU で実行するようにスケジュールされるたびに、カーネルは最大で使用可能な現在の予算の間タスクを実行させ、タスクがスケジュール解除されるたびに、その現在の予算は実行された時間の量だけ減らされます。現在の予算がゼロになると、タスクは次のアクティベーション期間まで一時停止 (調整) され、現在の予算は構成された値まで再び補充され、期限はタスク期間に等しい値だけ前倒しされます。

これは時間的分離を保証するのに十分ではありません。起動直後に一時停止し、現在の期限近くまたは期限を過ぎて起動するタスクは、設定された予算のほぼすべてで起動しますが、現在の期限は期限切れに非常に近いか、または期限を過ぎています。このような状況では、そのタスクは他のどのタスクよりも先にスケジュールされ、シングルプロセッサシステムでは、他の期限タスクの実行を予算と同じだけ遅らせることができます。この問題を回避するために、SCHED_DEADLINECBS アルゴリズムで定義されているウェイクアップスケジューリングルールを採用しています。タスクが起動すると、タスクがブロックされてから比較的短い時間が経過している場合は、タスクの以前の現在の期限と予算は変更されません。ただし、過度に長い時間が経過している場合は、カーネルは現在の期限を現在の時間に予約期間を加えた時間にリセットし、現在の予算を割り当てられた予約予算にリセットします。例を含むより詳しい説明については、^{[9]を参照してください。}

マルチプロセッサまたはマルチコア システムでは、SCHED_DEADLINEグローバル EDF を実装しているため、タスクは利用可能な CPU 間で移行できます。このような場合、構成された予算は、各期間中にタスクが任意の CPU で実行できる合計累積時間です。ただし、スケジューラはタスクのアフィニティ マスクも考慮するため、パーティション化されたスケジュール シナリオ、つまり各グループが特定の CPU に制限されるグループにタスクをパーティション化することや、CPU をパーティション化し、各タスク パーティションが特定の CPU パーティションに固定されるクラスター化されたスケジュール シナリオを簡単に作成できます。

の技術的な詳細についてはSCHED_DEADLINE、カーネルソースツリー内で入手可能なドキュメントを参照してください。^[9] CBSとそれが時間的分離を可能にする方法の詳細については、オリジナルのCBS論文^{[3]またはlwn.netに掲載されたこの記事[10]}のCBSに関するセクションを参照してください。

Earliest Deadline First (EDF) アルゴリズムに基づく Linux スケジューリング クラスの最初のアイデアは、Scuola Superiore Sant'Anna ^[11]の Real-Time Systems (ReTiS) Labとそのスピンオフ企業である Evidence Srl ^{[12]の小さなコンテキストで生まれました。その後、Evidence Srl は、FP7 フレームワーク プログラムを通じて}欧州委員会がサポートするACTORS プロジェクト^{[13] [14]}の資金を活用して、パッチの最初のバージョンの資金調達と開発を促進しました。元のバージョンは、Dario Faggioli (最初の 3 つのバージョンの開発については Evidence Srl と契約) と Juri Lelli (4 番目のバージョン以降) ^[15]によって、Michael Trimarchi と Fabio Checconi からの散発的な支援を受けて開発されました。Johan Eker は ACTORS 内の調整と Ericsson からのサポートを担当しています。 Juri Lelli、Luca Abeni、Claudio Scordinoは、再利用機能（GRUB ^[16]）と周波数スケーリング機能（GRUB-PA ^[17] ）の開発に協力しました。

このパッチは、 Linux カーネル メーリング リスト(LKML)を通じてカーネル コミュニティに定期的にリリースされています。各リリースでは、コードがカーネルの最新バージョンに合わせて調整され、前回の提出時に受け取ったコメントが考慮されました。スケジューラの人気が高まるにつれて、より多くのカーネル開発者がフィードバックと貢献を提供し始めました。

このプロジェクトはもともとSCHED_EDF2009年にLinuxカーネルコミュニティに発表され、その名前が付けられました。 ^[18]数週間後にはこの名前でReal-Time Linux Workshopにも発表されました。^[19]その後、Linuxカーネルコミュニティの要請により、名前はSCHED_DEADLINEに変更されました。^[20]

長年にわたり、以下のバージョンがリリースされました。

• スケジューラの最初のバージョンは2009年9月22日に「」という名前で提出されましたSCHED_EDF。^[18]
• 名前が変更された後のスケジューラの最初のバージョンはSCHED_DEADLINE、2009年10月16日にLKMLに提出されました。^[21]
• スケジューラの2番目のバージョンは2010年2月28日にLKMLに提出され、Deadline Inheritanceプロトコルの最初の実装が含まれていました。^[22]
• スケジューラの3番目のバージョンは2010年10月29日にLKMLに提出され、動的なタスク移行によるグローバル/クラスター化されたマルチプロセッサスケジューリングのサポートが追加されました。^[23]
• スケジューラの4番目のバージョンは2012年4月6日にLKMLに提出され、動的タスク移行のためのrq選択の処理が改善され、PREEMPT_RTとの統合が改善されました。^[24]
• スケジューラの第5バージョンは2012年5月23日にLKMLに提出されました。^[25]
• スケジューラの第6バージョンは2012年10月24日にLKMLに提出されました。^[26]
• スケジューラの第7バージョンは、2013年2月11日にLKMLに提出されました。^[27]内部計算はマイクロ秒単位の解像度に制限され（オーバーフローを避けるため）、RFCタグは削除されました。
• スケジューラの第8バージョンは2013年10月14日にLKMLに提出されました。^[28]
• スケジューラの第9バージョンは2013年11月7日にLKMLに提出されました。^[29]
• 最終バージョンはメインラインLinuxカーネルにマージされ（コミット番号a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8 ^[30]）、それ以来、通常通りLinuxカーネルの一部となっている。

Linux Weekly News ^[31]やPhoronix ^[32]のウェブサイトの記事ではSCHED_DEADLINE、このパッチが次のリリースでメインラインカーネルに統合される可能性があると論じられていました。最終的に、4年以上の歳月と9回のリリースを経て、このパッチは受け入れられ、Linuxカーネル3.14に統合されました。^{[7] [8]}

SCHED_DEADLINE 以前にも、サンタナ高等学校のリアルタイム システム (ReTiS) ラボ^[11]は、他のヨーロッパの研究プロジェクト (OCERA ^[33] 、 FRESCOR プロジェクト内の AQuoSA アーキテクチャ、[ ^34]、IRMOS ^{[35]など) のコンテキストで、Linux カーネル内で CBS とその派生のさまざまなオープン}ソース実装を提供していました。しかし、これらの以前の取り組みは、メインライン カーネルへの統合に適した実装を提供するというよりも、研究プロジェクトのための実験結果を集めることを主な目的とした学術的なアプローチから始まりました。IRMOS によって、ラボは Linux カーネル開発者と初めて本格的に接触しました。^[10]

カーネル4.13以降、SCHED_DEADLINEはGRUB（Greedy Reclamation of Unused Bandwidth）アルゴリズムを使用してCBSを完了しました。^[37]このサポートは、ReTiS LabによってEvidence Srlの協力を得て開発されました。

カーネル4.16以降、SCHED_DEADLINEはGRUB-PAアルゴリズムを実装することでARMプラットフォーム上のエネルギー消費を削減するためにさらに進化しました。^[17]この作業はARM Ltd.がEvidence SrlおよびScuola Superiore Sant'Annaと共同で行いました。^[38]

SCHED_DEADLINEいくつかの学術ワークショップ、会議、ジャーナルを通じて発表されています。

• Dario Faggioli、Fabio Checconi、Michael Trimarchi、Claudio Scordino、Linux カーネル用の EDF スケジューリング クラス、第 11 回リアルタイム Linux ワークショップ (RTLWS)、ドレスデン、ドイツ、2009 年 9 月^{[19] [39]}
• Nicola Manica、Luca Abeni、Luigi Palopoli、Dario Faggioli、Claudio Scordino、「スケジュール可能なデバイスドライバ：実装と実験結果」、組み込みリアルタイムアプリケーション向けオペレーティングシステムプラットフォームに関する国際ワークショップ（OSPERT）、ブリュッセル、ベルギー、2010年7月^{[40] [41]}
• Juri Lelli、Giuseppe Lipari、Dario Faggioli、Tommaso Cucinotta、「LinuxにおけるグローバルEDFの効率的かつスケーラブルな実装」、組み込みリアルタイムアプリケーション向けオペレーティングシステムプラットフォームに関する国際ワークショップ（OSPERT）、ポルト（ポルトガル）、2011年7月。^{[42] [43]}
• Enrico Bini、Giorgio Buttazzo、Johan Eker、Stefan Schorr、Raphael Guerra、Gerhard Fohler、Karl-Erik Arzen、Vanessa Romero Segovia、Claudio Scordino、「マルチコアシステムにおけるリソース管理：ACTORSアプローチ」、IEEE Micro、vol. 31、no. 3、pp. 72–81、2011年5月/6月。^[14]
• Andrea Parri、Juri Lelli、Mauro Marinoni、Giuseppe Lipari、「Linuxにおけるマルチプロセッサ帯域幅継承プロトコルの設計と実装」、第15回リアルタイムLinuxワークショップ（RTLWS）、ルガーノ・マンノ、スイス、2013年10月。^[44]
• Luca Abeni、Juri Lelli、Claudio Scordino、Luigi Paolopoli、「SCHED_DEADLINE のための貪欲な CPU 回収」、第 16 回リアルタイム Linux ワークショップ (RTLWS) の議事録、ドイツ、デュッセルドルフ、2014 年 10 月。^[45]
• Juri Lelli、Claudio Scordino、Luca Abeni、Dario Faggioli、Linux カーネルにおけるデッドライン スケジューリング、ソフトウェア: 実践と経験、46(6): 821–839、2016 年 6 月^[46]
• Claudio Scordino、Luca Abeni、Juri Lelli、「Linuxカーネルにおけるエネルギーを考慮したリアルタイムスケジューリング」、第33回ACM/SIGAPP応用コンピューティングシンポジウム（SAC 2018）、フランス、ポー、2018年4月。^[47]
• Claudio Scordino、Luca Abeni、Juri Lelli、「Linuxにおけるリアルタイム性とエネルギー効率：理論と実践」、ACM SIGAPP Applied Computing Review (ACR) Vol. 18 No. 4、2018年。^[48]

このプロジェクトは、2010年のカーネルサミット^{[49] [50]} 、 2012年のLinux Plumbersカンファレンス^{[51] [52]}、2013年のEmbedded Linuxカンファレンス^{[53]でも発表されています。}

このプロジェクトには公式ページがあります。^[54]メインライン統合前は、コードはGitHubウェブサイト^[55]で公開されていましたが、これはGitoriousの以前のリポジトリに代わるものでした。^[56]メインライン統合以降、公式コードはLinuxカーネルソースツリーに含まれています。

Linux Weekly News、^{[1] [57]} Slashdot、^[58] OSNews ^{[2] [59]} LinuxToday ^[60]にいくつかの記事が掲載されました。YouTube ^[61]にも ビデオがアップロードされています。

メインラインカーネルに統合される前に、SCHED_DEADLINEすでにYoctoプロジェクトに統合されていました。^{[28]また、} Linaroプロジェクト への組み込みにも関心が寄せられていました。^[62]

• 最も早い適格な仮想期限優先スケジュール(EEVDF)