レートモノトニックスケジューリング

コンピュータサイエンスにおけるスケジューリング技術

コンピュータサイエンスにおいて、レートモノトニックスケジューリング（RMS）^[1]は、静的優先度スケジューリングクラスを持つリアルタイムオペレーティングシステム（RTOS）で使用される優先度割り当てアルゴリズムです。 ^[2]静的優先度はジョブのサイクル期間に応じて割り当てられるため、サイクル期間が短いほどジョブの優先度が高くなります。

これらのオペレーティングシステムは一般的にプリエンプティブであり、応答時間に関して決定論的な保証を提供します。レートモノトニック解析は、これらのシステムと組み合わせて使用​​され、特定のアプリケーションのスケジューリング保証を提供します。

導入

レートモノトニック分析の単純なバージョンでは、スレッドに次のプロパティがあることを前提としています。

• リソース共有なし（プロセスは、ハードウェアリソース、キュー、またはあらゆる種類のセマフォブロッキングまたは非ブロッキング（ビジー待機）などのリソースを共有しません）
• 決定論的な期限は期間と全く同じである
• 静的優先度（実行可能な最高の静的優先度を持つタスクが、他のすべてのタスクよりも優先されます）
• レート単調規則に従って割り当てられた静的優先順位（期間/期限が短いタスクには高い優先順位が与えられます）
• コンテキストスイッチ時間やその他のスレッド操作は自由であり、モデルに影響を与えません。

これは、ラウンドロビンやタイムシェアリングスケジューラではスケジューリング要件を満たせない、クローズドシステムにおける周期の計算シミュレーションを含む数学モデルです。レートモノトニックスケジューリングは、システム内のすべてのスレッドの実行モデルを参照し、対象となるスレッドセットの保証を満たすために必要な時間を決定します。

最適性

与えられた仮定の下では、レートモノトニックな優先度割り当てが最適である。つまり、静的優先度スケジューリングアルゴリズムがすべての期限を満たすことができる場合、レートモノトニックなアルゴリズムも満たすことができる。デッドラインモノトニックなスケジューリングアルゴリズムは、周期とデッドラインが等しい場合にも最適であり、実際にはこの場合、両方のアルゴリズムは同一である。さらに、デッドラインモノトニックなスケジューリングは、デッドラインが周期よりも短い場合に最適である。^[3]デッドラインが周期よりも長くなる可能性があるタスクモデルの場合、このモデルに対する正確なスケジューリング可能性テストを備えたAudsleyのアルゴリズムは、最適な優先度割り当てを見つける。^[4]

利用率の上限

最小上限

Liu & Layland (1973) は、 n個の周期タスクの集合において、 CPU使用率が特定の上限（タスク数に依存する）を下回る場合、常に期限内に間に合う実行可能なスケジュールが存在することを証明しました。RMS のスケジュール可能性テストは次のように行われます。

${\displaystyle U=\sum _{i=1}^{n}{U_{i}}=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({2}^{1/n}-1)}$

ここで、 Uは利用率、C _iはプロセスiの計算時間、T _iはプロセスiのリリース周期（期限は1周期後）、nはスケジュールされるプロセス数です。例えば、プロセスが2つの場合、 U ≤ 0.8284 となります。プロセス数が無限大に近づくと、この式は次のようになります。

${\displaystyle \lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots }$

したがって、 RMSがすべてのデッドラインを満たすことができると概算できるのは、CPU使用率合計Uが70%未満の場合です。CPUの残りの30%は、優先度の低い非リアルタイムタスクに割り当てることができます。nの値が小さい場合、またはUがこの推定値に近い場合は、計算された使用率の上限を使用する必要があります。 ${\displaystyle {n}\geq {10}}$

実際には、プロセスの場合、は最悪のケース（つまり、最長）の計算時間を表し、すべての処理が発生する最悪のケースの期限（つまり、最短期間）を表す必要があります。 ${\displaystyle {i^{th}}}$ ${\displaystyle {C_{i}}}$ ${\displaystyle {T_{i}}}$

待ち行列理論との関係

待ち行列理論では、T _iは到着間隔時間、C _iはサービス時間と呼ばれます。これらの2つのパラメータは、しばしば速度として規定されます。

${\displaystyle \lambda _{i}={1 \over T_{i}}}$は到着率であり、

${\displaystyle \mu _{i}={1 \over C_{i}}}$サービス率です。

各タスクの使用率ρ _iは次のようになります。

${\displaystyle \rho _{i}={\lambda _{i} \over \mu _{i}}={C_{i} \over T_{i}}=U_{i}}$

上記の通りです。

調和タスクセットの上限

Liu と Layland は、タスク （ただし、および はの整数倍）の場合、この境界は最大値 1.0 まで緩和される可能性があると指摘しています。つまり、すべてのタスクの周期は、最短周期 の倍数であるだけでなく、どのタスクの周期もすべてのより短い周期の倍数になります。これは、調和タスク セットとして知られています。この例は次のようになります 。Liu と Layland は、調和タスク セットを持つことが常に可能とは限らず、実際には、ソフトタイム期限を持つタスクのバッファリングや、動的優先順位割り当てアプローチの使用などの他の緩和策を代わりに使用して、境界を高くすることができる可能性があることを認めています。 ${\displaystyle {T_{m}}}$ ${\displaystyle {T_{i}}}$ ${\displaystyle {T_{m}}{>}{T_{i}}}$ ${\displaystyle i=1...m-1}$ ${\displaystyle {T_{m}}}$ ${\displaystyle {T_{i}}}$ ${\displaystyle {T_{1}}}$ ${\displaystyle [{T_{1}},{T_{2}},{T_{3}},{T_{4}}]=[1,3,6,12]}$

調和連鎖への一般化

KuoとMok ^[5]は、 K個の調和タスクサブセット（調和チェーンとして知られる）で構成されたタスクセットの場合、最小上限テストは次のようになることを示した。

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq K({2}^{1/K}-1)}$

各タスクの周期が、それより短い周期を持つ他のすべてのタスクの正確な倍数である場合、タスクセットはサイズ1のn個の調和タスクサブセットで構成されていると考えることができるため、 となり、この一般化はLiuとLaylandの最小上限と同等になります。 のとき、上限は1.0となり、完全利用を表します。 ${\displaystyle {K}{=}{n}}$ ${\displaystyle {K}{=}{1}}$

確率的限界

ランダムに生成された周期的なタスクシステムは、利用率が88%以下の場合、通常はすべての期限を満たすことが示されていますが、^[6]この事実は、すべてのタスクセットで保証できない正確なタスク統計（期間、期限）を知っていることに依存しており、場合によっては、使用率がLiuとLaylandによって提示された最小の上限に達したことが著者によって発見されました。

双曲境界

双曲的境界^[7]は、LiuとLaylandによって提示されたものよりも厳密なスケジュール可能性の十分条件である。

${\displaystyle \prod _{i=1}^{n}(U_{i}+1)\leq 2}$、

ここで、U _iは各タスクのCPU使用率です。これは、個々のタスク使用率係数のみを用いて得られる最も厳しい上限です。

リソースの共有

多くの実用的なアプリケーションでは、リソースが共有されるため、変更されていないRMSは優先度反転やデッドロックの危険にさらされます。実際には、この問題はプリエンプションを無効にするか、優先度継承によって解決されます。代替手段としては、ロックフリーアルゴリズムを使用するか、異なる優先度を持つスレッド間でミューテックス/セマフォを共有しないようにする方法があります。これは、そもそもリソースの競合が発生しないようにするためです。

プリエンプションの無効化

• リアルタイムカーネル（例：MicroC/OS-II）でCPU割り込みをOS_ENTER_CRITICAL()ロックするプリミティブOS_EXIT_CRITICAL()
• splx()デバイス割り込みのロックをネストするプリミティブのファミリー（FreeBSD 5.x/6.x ）

優先権継承

• 基本的な優先度継承プロトコル^[8]は、リソースを保持しているタスクの優先度を、そのリソースを要求したタスクの優先度に昇格させます。リソースが解放されると、昇格前の元の優先度レベルに戻ります。この方法ではデッドロックを防ぐことはできず、連鎖ブロッキングの問題が生じます。つまり、高優先度タスクが複数の共有リソースに順番にアクセスすると、各リソースについて低優先度タスクを待機（ブロック）しなければならない場合があります。^[9] Linuxカーネルのリアルタイムパッチ（Wayback Machineで2020年10月13日にアーカイブ）には、この式の実装が含まれています。^[10]

• 優先度上限プロトコル^{[11]は、各セマフォに}上限優先度を割り当てることで、基本的な優先度継承プロトコルを拡張するものです。上限優先度は、そのセマフォにアクセスするジョブの中で最も優先度の高いジョブの優先度です。ジョブの優先度が、そのセマフォの上限優先度よりも低い場合、ジョブは優先度の低いクリティカルセクションをプリエンプトすることはできません。この方法はデッドロックを防ぎ、ブロッキング時間を、優先度の低いクリティカルセクション1つ分の長さまでに制限します。ただし、この方法は、不要なブロッキングを引き起こす可能性があるため、最適とは言えません。優先度上限プロトコルは、VxWorksリアルタイムカーネルで利用可能です。これは、Highest Locker's Priority Protocol (HLP) とも呼ばれます。^[12]

優先度継承アルゴリズムは、2つのパラメータで特徴づけられます。1つ目は、継承が遅延継承（必要な場合のみ）か即時継承（競合が発生する前に優先度を上げる）かです。2つ目は、継承が楽観継承（最低限の優先度を上げる）か悲観継承（最低限の優先度よりも高い優先度を上げる）かです。

	悲観的な	楽観的
すぐに	OS_ENTER_CRITICAL()/OS_EXIT_CRITICAL()	splx()、一番上のロッカー
怠け者		優先度上限プロトコル、基本優先度継承プロトコル

実際には、遅延アルゴリズムと即時アルゴリズムの間に数学的な違いはありません (Liu-Layland システムの利用率の境界に関して)。また、即時アルゴリズムの方が実装が効率的であるため、ほとんどの実用的なシステムで使用されています。^{[引用が必要]}

基本的な優先度継承の使用例は、「Mars Pathfinderのリセットバグ」^{[13] [14]}に関連しており、これは優先度継承を有効にするためにセマフォの作成フラグを変更することによってMarsで修正されました。

割り込みサービスルーチン

割り込みサービスルーチン（ISR）は、ハードリアルタイム期限の有無にかかわらず、RMS分析に含める必要があります。ISRがスケジューラ制御のタスクよりも優先度が高い場合、RMS分析はスケジュール可能性を判断するために必要です。ISRの処理周期が最短の非ISRプロセスよりも短い場合、RMSルールでは既に適切に優先度が付けられている可能性があります。しかし、クリティカル期限を持つ非ISRプロセスよりも長い周期/期限を持つISRはRMS違反となり、タスクセットのスケジュール可能性を判断するために計算された境界を使用できなくなります。

優先順位が誤っているISRの軽減

優先順位付けが不適切な ISR を軽減する方法の 1 つは、可能であれば ISR の周期を最短周期と等しくなるように短縮して分析を調整することです。この短い周期を課すことで、RMS に準拠した優先順位付けが行われますが、ISR の使用率が高くなり、したがって全体の使用率も高くなります。それでも許容範囲を下回っている可能性があり、そのためスケジュール可能性が証明されます。例として、計算時間 が500 マイクロ秒、周期が 4 ミリ秒のハードウェア ISR を考えます。スケジューラによって制御される最短のタスクの周期 が1 ミリ秒の場合、ISR の優先順位は高くなりますが、レートは低くなり、RMS に違反します。スケジュール可能性を証明するために、ISR の使用率を設定して再計算します (これにより全体の使用率も上がります)。この場合、は からに変わります。この利用率は、タスクセット全体の利用率を合計し、上限と比較することでスケジュール可能性を証明する際に使用されます。ISRの周期の調整は分析のみを目的としており、ISRの実際の周期は変更されないことに注意してください。 ${\displaystyle {C_{isr}}}$ ${\displaystyle {T_{isr}}}$ ${\displaystyle {T_{1}}}$ ${\displaystyle {T_{isr}}={T_{1}}}$ ${\displaystyle {U_{isr}}{=}{C_{isr}}/{T_{isr}}}$ ${\displaystyle {0.5ms}/{4ms}{=}0.125}$ ${\displaystyle {0.5ms}/{1ms}{=}0.5}$

優先順位が誤っているISRの影響を軽減する別の方法は、ISRを使用して新しいセマフォ/ミューテックスを設定するだけで、時間のかかる処理を、RMSを使用して適切に優先順位付けされた新しいプロセスに移動し、新しいセマフォ/ミューテックスでブロックすることです。スケジュール可能性を判断する際には、ISRアクティビティによるCPU使用率のマージンを最小上限から差し引く必要があります。使用率が無視できるISRは無視できます。

例

例1

プロセス	計算時間C	リリース期間T	優先度
P1	1	8	2
P2	2	5	1
P3	2	10	3

RMS では、P2 のリリース レートが最も高く (つまり、リリース期間が最も短く)、最も高い優先順位を持ちます。次に P1、最後に P3 が続きます。

最小上限

利用は次のようになります。

${\displaystyle U={\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725}$。

システムがスケジュール可能であると結論付けるためのプロセスの十分な条件は次のとおりです。 ${\displaystyle 3\,}$

${\displaystyle {U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976}$

であり、最小上限境界を下回ることが十分な条件であるため、システムはスケジュール可能であることが保証されます。 ${\displaystyle U<U_{lub}}$

例2

プロセス	計算時間C	リリース期間T	優先度
P1	3	16	3
P2	2	5	1
P3	2	10	2

RMS では、P2 のリリース レートが最も高い (つまり、リリース期間が最も短い) ため、優先順位が最も高くなり、次に P3、最後に P1 が続きます。

最小上限

例 1 のように、Liu と Layland の境界を使用すると、タスク セットがスケジュール可能であると結論付けることができるプロセスの十分な条件は次のようになります。 ${\displaystyle 3\,}$

${\displaystyle {U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976}$

合計使用率は次のようになります。

${\displaystyle U={\frac {3}{16}}+{\frac {2}{5}}+{\frac {2}{10}}=0.7875}$。

なので、システムはLiuとLaylandの境界によってスケジュール可能であることが保証されないと判断されます。 ${\displaystyle U>U_{lub}}$

双曲境界

より厳密な双曲境界を次のように使用します。

${\displaystyle \prod _{i=1}^{n}(U_{i}+1)=({\frac {3}{16}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10}}+1)=1.995\leq 2}$

タスク セットはスケジュール可能であることがわかります。

例3

プロセス	計算時間C	リリース期間T	優先度
P1	7	32	3
P2	2	5	1
P3	2	10	2

RMS では、P2 のレートが最も高い (つまり、期間が最も短い) ため、優先順位が最も高くなり、次に P3、最後に P1 が続きます。

最小上限

例 1 のように、Liu と Layland の境界を使用すると、タスク セットがスケジュール可能であると結論付けることができるプロセスの十分な条件は次のようになります。 ${\displaystyle 3\,}$

${\displaystyle {U_{lub}}=3(2^{\frac {1}{3}}-1)=0.77976}$

合計使用率は次のようになります。

${\displaystyle U={\frac {7}{32}}+{\frac {2}{5}}+{\frac {2}{10}}=0.81875}$。

なので、システムはLiuとLaylandの境界によってスケジュール可能であることが保証されないと判断されます。 ${\displaystyle U>U_{lub}}$

双曲境界

より厳密な双曲境界を次のように使用します。

${\displaystyle \prod _{i=1}^{n}(U_{i}+1)=({\frac {7}{32}}+1)*({\frac {2}{5}}+1)*({\frac {2}{10}}+1)=2.0475}$

システムが双曲境界によってスケジュール可能であることが保証されないと判断されたためです。 ${\displaystyle 2.0{<}2.0475}$

調和タスクセット分析

であるため、タスク2と3は調和タスクサブセットとみなすことができます。タスク1はそれ自体が調和タスクサブセットを形成します。したがって、調和タスクサブセットの数Kは2です。 ${\displaystyle {T_{3}}={2{T_{2}}}}$

$${\displaystyle {U_{lub,harmonic}}=K(2^{\frac {1}{K}}-1)=2(2^{\frac {1}{2}}-1)=0.828}$$

上記で計算した合計利用率 (0.81875) を使用すると、システムはスケジュール可能であると判断されます。 ${\displaystyle 0.81875<0.828}$

参照

• 期限単調スケジューリング
• Deos は、実用的な Rate Monotonic Sc​​heduler を搭載した、時間と空間を分割したリアルタイム オペレーティング システムです。
• 動的優先度スケジューリング
• 締め切りが早い順にスケジュールする
• RTEMS は、実用的な Rate Monotonic Sc​​heduler を含むオープン ソースのリアルタイム オペレーティング システムです。
• スケジューリング（コンピューティング）
• 待ち行列理論
• キングマンの公式

参考文献

1. Liu, CL ; Layland, J. (1973)、「ハードリアルタイム環境におけるマルチプログラミングのスケジューリングアルゴリズム」、Journal of the ACM、20 (1): 46– 61、CiteSeerX  10.1.1.36.8216、doi :10.1145/321738.321743、S2CID  207669821。
2. Bovet, Daniel P.; Cesati, Marco, Linuxカーネルの理解, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 2014-09-21 にWayback Machineでアーカイブされています。
3. Leung, JY; Whitehead, J. (1982)、「周期的リアルタイムタスクの固定優先度スケジューリングの複雑さについて」、パフォーマンス評価、2 (4): 237– 250、doi :10.1016/0166-5316(82)90024-4。
4. アラン・バーンズとアンディ・ウェリングス（2009年）、リアルタイムシステムとプログラミング言語（第4版）、アディソン・ウェスレー、pp. 391、397、ISBN 978-0-321-41745-9
5. T.-W. Kuo; AK Mok (1991). 「適応型リアルタイムシステムにおける負荷調整」. [1991] 第12回リアルタイムシステムシンポジウム論文集. pp.  160– 170. doi :10.1109/REAL.1991.160369. ISBN 0-8186-2450-7. S2CID  31127772。
6. Lehoczky, J.; Sha, L.; Ding, Y. (1989)、「レートモノトニックスケジューリングアルゴリズム：正確な特性評価と平均ケースの動作」、IEEEリアルタイムシステムシンポジウム、pp.  166– 171、doi :10.1109/REAL.1989.63567、ISBN 978-0-8186-2004-1、S2CID  206524469。
7. Enrico Bini; Giorgio C. Buttazzo; Giuseppe M. Buttazzo (2003)、「Rate Monotonic Analysis: the Hyperbolic Bound」、IEEE Transactions on Computers、52 (7): 933– 942、doi :10.1109/TC.2003.1214341、hdl : 11382/200358
8. Lampson, BW ; Redell, DD (1980)、「Mesaにおけるプロセスとモニターの経験」、Communications of the ACM、23 (2): 105– 117、CiteSeerX 10.1.1.46.7240、doi :10.1145/358818.358824、S2CID  1594544 。
9. Buttazzo, Giorgio (2011)、「ハードリアルタイムコンピューティングシステム：予測可能なスケジューリングアルゴリズムとアプリケーション（第3版）」、ニューヨーク、NY：Springer、p. 225
10. 「Real-Time Linux Wiki」. kernel.org. 2008年3月26日. 2014年3月14日閲覧。
11. Sha, L.; Rajkumar, R.; Lehoczky, JP (1990)、「優先度継承プロトコル：リアルタイム同期へのアプローチ」、IEEE Transactions on Computers、39 (9): 1175– 1185、doi :10.1109/12.57058。
12. Buttazzo, Giorgio (2011),ハードリアルタイムコンピューティングシステム：予測可能なスケジューリングアルゴリズムとアプリケーション（第3版）、ニューヨーク、NY：Springer、p. 212
13. 「マイクロソフト リサーチの Mike Jones」.
14. “Mars Pathfinder Reset Bug - Anthology of Interest”. 2011年10月5日時点のオリジナルよりアーカイブ。2008年9月9日閲覧。

さらに読む

• Buttazzo, Giorgio (2011)、「ハードリアルタイムコンピューティングシステム：予測可能なスケジューリングアルゴリズムとアプリケーション」、ニューヨーク、NY：Springer。
• アラン・バーンズとアンディ・ウェリングス（2009年）、リアルタイムシステムとプログラミング言語（第4版）、アディソン・ウェスレー、ISBN 978-0-321-41745-9
• Liu, Jane WS (2000)、『リアルタイムシステム』、アッパーサドルリバー、ニュージャージー州: Prentice Hall、第6章。
• ジョセフ、M.; パンディア、P. (1986)、「リアルタイムシステムにおける応答時間の検出」、BCSコンピュータジャーナル、29 (5): 390– 395、doi : 10.1093/comjnl/29.5.390。
• Sha, Lui; Goodenough, John B. (1990年4月)、「リアルタイムスケジューリング理論とAda」、IEEE Computer、23 (4): 53– 62、doi :10.1109/2.55469、S2CID  12647942

外部リンク

• マイクロソフトの研究による火星探査機のバグ
• 火星探査車パスファインダーで実際に何が起こったのか マイク・ジョーンズ著 リスク・ダイジェスト第19巻第49号より
• [1] 火星パスファインダーのバグの本当の原因は、その問題の説明によって会社や株価が左右されるような人や、その問題について誰かが話しているのを聞いた人ではなく、実際にその問題に対処した人たちによって説明される。

「https://en.wikipedia.org/w/index.php?title=Rate-monotonic_scheduling&oldid=1318442573」より取得