レートモノトニックスケジューリングのソースを表示

'''レートモノトニックスケジューリング'''（'''Rate-Monotonic Scheduling'''、'''RMS'''<ref name="Liu73">C. L. Liu and J. Layland. 'Scheduling algorithms for multiprogramming in a hard real-time environment', ''Journal of the ACM'', 10(1), 1973.</ref>）は[[リアルタイムオペレーティングシステム]]で使われている[[スケジューリング]][[アルゴリズム]]の一種。プリエンプティブで固定優先度を使用する最適なスケジューリングである。

== 特徴 ==
このアルゴリズムを使用する場合のプロセスの前提条件は以下の通りである。
*リソース([[ハードウェア]][[リソース]]、[[キュー (コンピュータ)|キュー]]、[[セマフォ]]など)を共有しない。
*デッドライン(実行期限)が分かっていて、実行周期と完全に一致している(つまり、次の起動までに今回の実行を終えればよい)。
*固定優先度(プロセッサが解放されたり、新たなタスク周期が開始されたら、最高固定優先度のプロセスが他の全タスクをプリエンプトして起動される)
*固定優先度は ''rate monotonic'' という原則に従って設定される(実行周期/実行期限が短いタスクに高い優先度を与える)。

RMSは統計的なモデルであり、イベントの記録を含んでいる。予測可能な数の入力だけがある閉鎖された環境で使われる。リアルタイムシステムにおいては[[ラウンドロビン・スケジューリング|ラウンドロビン]]や[[タイムシェアリングシステム|タイムシェアリング]]はうまく機能しない。RMSは履歴を参照してプロセスの処理時間やプロセスの起動時刻を決定する。

[[1973年]]、LiuとLaylandは、固有の周期を持つ<math>n</math>個の周期的タスクは、[[CPU]]使用率が以下の式を満たすならば常にデッドラインを満たしてスケジュールできることを証明した。

:<math>U = \sum_{i=1}^{n} C_i / T_i \leq n(\sqrt[n]{2} - 1)</math>

<math>C_i</math>は計算時間、<math>T_i</math>は周期である。例えば、<math>n = 2\,</math> のとき <math>U \leq 0.8284</math> となる。プロセス数が[[無限|無限大]]に近づくとこの式は以下のようになる:

:<math>\lim_{n \rightarrow \infty} n(\sqrt[n]{2} - 1) = \ln 2 \approx 0.693147\ldots</math>

従って、一般にRMSが全デッドラインを満たしてスケジュールできるCPU使用率の限界は <math>69.3\%</math> となる。残りの <math>30.7\%</math> の時間は低優先度の非リアルタイムタスクに使用できる。しかしこれは、'''タスクの組み合わせによらずスケジューリング可能であるための[[同値|十分条件]]にすぎず'''、かなり保守的な値となっている。実際CPU利用率が<math>80\%</math>前後までであるなら、デッドラインミスが起こるタスクの組み合わせは極めて稀である。それを表す端的な例として、ランダムに生成された周期タスクについて、CPU使用率が <math>85\%</math> 以下ならば全デッドラインを満たすことが知られている。<ref name="Lehoczky89">J. Lehoczky, L. Sha and Y. Ding, 'The Rate monotonic scheduling algorithm: exact characterization and average case behavior', ''IEEE Real-Time Systems Symposium'', pp. 166-171, December 1989.</ref> しかし、これはタスクの統計情報(周期、デッドラインなど)を正確に知っているかどうかに依存するので、あらゆるタスクの組合せで保証されるものではない。

レートモノトニックの優先度設定が「最適; optimal」であるという場合、任意の固定優先度スケジューリングアルゴリズムが全デッドラインを満たすことができるなら、RMSアルゴリズムも同様であることを意味している。'''デッドラインモノトニックスケジューリング'''(DMS)は、デッドラインと周期が異なる場合に「最適」のアルゴリズムである。デッドラインと周期が等しい場合RMSとDMSは等価であり、デッドラインが周期より短い場合DMSは「最適」である。<ref name="Leung80">J. Y. Leung and J. Whitehead. 'On the complexity of fixed-priority scheduling of periodic, real-time tasks'. ''Performance Evaluation'', 2(4):237--250, December 1982.</ref>

デッドラインが周期より長い場合の最適な固定優先度スケジューリングは「未解決の問題」である。

==リソースプリエンプションと優先度継承==
多くの実用アプリケーションにおいて、リソースは共有されるものである。従って、RMSは[[優先順位の逆転]]と[[デッドロック]]問題に対処する必要がある。これを解決する方法として[[優先度継承]]が導入された。

優先度継承アルゴリズムの例を以下に列挙する:
*<code>OSIntEnter()</code> と <code>OSIntExit()</code> というプリミティブがリアルタイムカーネル(uC-OS II)でCPU割り込みをロックするために使われている。
*<code>splx()</code> などのプリミティブがデバイス割り込みのロックに使われている(Linux カーネル <!-- UNIX? -->)。
* ''Highest Locker Protocol'' は全タスク間の衝突をオフラインで分析して「上限優先度」(後述)を探す必要がある。
* 基本優先度継承プロトコル(Basic Priority Inheritance Protocol)<ref name="Lampson80">B.W. Lampson, and D. D. Redell. 'Experience with Processes and Monitors in Mesa'. ''Communications of the ACM'', Vol. 23, No. 2 (Feb 1980), pp. 105-117. </ref>は、低優先度タスクの保持するロックを高優先度タスクが要求すると、低優先度タスクの優先度をその高優先度タスクの優先度まで高くする(そのロックを解放するまで)。
*[[優先度上限プロトコル]]<ref name="Sha90">L. Sha, R. Rajkumar and J. P. Lehoczky, 'Priority inheritance protocols: an approach to real-time synchronization', ''IEEE Transactions on Computers'', vol. 39 no. 9, September 1990, pp. 1175-1185.</ref>は基本優先度継承プロトコルを改良したものであり、各セマフォに「上限優先度」を割り当てる。上限優先度とはそのセマフォにアクセスする可能性のある全タスクの最高優先度である。そして、低優先度のタスクがそのセマフォを獲得した状態の場合、上限優先度以下の他のタスクがそれを横取りできない([[プリエンプション]]できない)ようにする。

優先度継承アルゴリズムは2つのパラメータで分類できる。第一は継承が(本当に必要なときだけに)遅延されるか、(衝突が発生する前に)即座に行われるかである。第二は継承が(必要最小限だけ)楽観的に行われるか、(必要以上に)悲観的に行われるかである。

{| class="wikitable"
|-
!
! 悲観的
! 楽観的
|-
! 即時
| <code>OSIntEnter/Exit()</code>
| <code>splx()</code>, Highest Locker
|-
! 遅延
|
| 優先度上限プロトコル, 基本優先度継承プロトコル
|-
|}

実際、遅延アルゴリズムと即時アルゴリズムに数学的な違いはなく、即時アルゴリズムの方が実装が効率的であるため、多くの実用システムで使われている。

基本優先度継承プロトコルは「ブロックの連鎖」を生じる可能性がある。すなわち、高優先度のタスクがクリティカルセクションに入ろうとして実際に入れるまでに長時間待たされる可能性がある。他のプロトコルでは高優先度タスクがクリティカルセクションに入る前にせいぜい1つの低優先度のクリティカルセクションが実行されるだけであることを保証している。

優先度上限プロトコルは[[VxWorks]]リアルタイムカーネルでも使えるが、滅多に使用されない。

基本優先度継承の使用例として[[マーズ・パスファインダー]]のバグ問題がある。火星上でバグを回避する手段して用いられたのが優先度継承である。

==例==
3つの周期的プロセスが動作するシステムを考える。
{| class="wikitable"
|-
! プロセス
! 実行時間
! 周期
|-
! P1
| 1
| 8
|-
! P2
| 2
| 5
|-
! P3
| 2
| 10
|-
|}

なお、実行時間も周期も同じ単位の時間(例えば10ミリ秒)であり、P1は8単位周期(80ミリ秒)に起動し、1単位(10ミリ秒)だけ動作することを示している。CPU使用率は以下のようになる:

:<math>\frac{1}{8} + \frac{2}{5} + \frac{2}{10} = 0.725</math>

<math>3\,</math> プロセスの理論的限界は以下のようになる:

:<math>U = 3(2^\frac{1}{3} - 1) = 0.77976\ldots</math>

従って <math>0.725 < 0.77976\ldots</math> であるため、システムはスケジュール可能である。

==関連項目==
*[[スケジューリング]]
*[[Earliest Deadline First]]
*[[RTEMS]] - レートモノトニックスケジューリングを実装しているRTOS

==参考文献==
<references/>
*M. Joseph and P. Pandya. 'Finding Response times in Real-time systems',  ''BCS Computer Journal'', 29(5), pp. 390-395, October 1986.

==外部リンク==
いずれも英文
*[http://www.netrino.com/Publications/Glossary/RMA.html Introduction to Rate Monotonic Scheduling]
*[http://research.microsoft.com/~mbj/Mars_Pathfinder/Authoritative_Account.html The Mars Pathfinder Bug]
*[http://www.cs.berkeley.edu/~brewer/cs262/PriorityInversion.html Priority Inversion explained via the Mars Pathfinder Bug]

[[Category:OSのプロセス管理|れとものとにつくすけしゆりんく]]
[[Category:並行計算|れとものとにつくすけしゆりんく]]