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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

レートモノトニックスケジューリング（Rate-Monotonic Scheduling、RMS^[1]）はリアルタイムオペレーティングシステムで使われているスケジューリングアルゴリズムの一種。プリエンプティブで固定優先度を使用する最適なスケジューリングである。

[編集] 特徴

このアルゴリズムを使用する場合のプロセスの前提条件は以下の通りである。

リソース(ハードウェアリソース、キュー、セマフォなど)を共有しない。
デッドライン(実行期限)が分かっていて、実行周期と完全に一致している(つまり、次の起動までに今回の実行を終えればよい)。
固定優先度(プロセッサが解放されたり、新たなタスク周期が開始されたら、最高固定優先度のプロセスが他の全タスクをプリエンプトして起動される)
固定優先度は rate monotonic という原則に従って設定される(実行周期/実行期限が短いタスクに高い優先度を与える)。

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

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

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

$C i$ は計算時間、 $T i$ は周期である。例えば、 $n = 2\,$ のとき $U \leq 0.8284$ となる。プロセス数が無限大に近づくとこの式は以下のようになる:

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

従って、一般にRMSが全デッドラインを満たしてスケジュールできるCPU使用率の限界は $69.3\%$ となる。残りの $30.7\%$ の時間は低優先度の非リアルタイムタスクに使用できる。ランダムに生成された周期タスクについて、CPU使用率が $85\%$ 以下ならば全デッドラインを満たすことが知られている。^[2] しかし、これはタスクの統計情報(周期、デッドラインなど)を正確に知っているかどうかに依存するので、あらゆるタスクの組合せで保証されるものではない。

レートモノトニックの優先度設定が「最適; optimal」であるという場合、任意の固定優先度スケジューリングアルゴリズムが全デッドラインを満たすことができるなら、RMSアルゴリズムも同様であることを意味している。デッドラインモノトニックスケジューリング(DMS)は、デッドラインと周期が異なる場合に「最適」のアルゴリズムである。デッドラインと周期が等しい場合RMSとDMSは等価であり、デッドラインが周期より短い場合DMSは「最適」である。^[3]

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

[編集] リソースプリエンプションと優先度継承

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

優先度継承アルゴリズムの例を以下に列挙する:

OSIntEnter() と OSIntExit() というプリミティブがリアルタイムカーネル(uC-OS II)でCPU割り込みをロックするために使われている。
splx() などのプリミティブがデバイス割り込みのロックに使われている(Linux カーネル )。
Highest Locker Protocol は全タスク間の衝突をオフラインで分析して「上限優先度」(後述)を探す必要がある。
基本優先度継承プロトコル(Basic Priority Inheritance Protocol)^[4]は、低優先度タスクの保持するロックを高優先度タスクが要求すると、低優先度タスクの優先度をその高優先度タスクの優先度まで高くする(そのロックを解放するまで)。
優先度上限プロトコル^[5]は基本優先度継承プロトコルを改良したものであり、各セマフォに「上限優先度」を割り当てる。上限優先度とはそのセマフォにアクセスする可能性のある全タスクの最高優先度である。そして、低優先度のタスクがそのセマフォを獲得した状態の場合、上限優先度以下の他のタスクがそれを横取りできない(プリエンプションできない)ようにする。

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

	悲観的	楽観的
即時	`OSIntEnter/Exit()`	`splx()`, Highest Locker
遅延		優先度上限プロトコル, 基本優先度継承プロトコル

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

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

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

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

[編集] 例

3つの周期的プロセスが動作するシステムを考える。

プロセス	実行時間	周期
P1	1	8
P2	2	5
P3	2	10

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

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

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

$U = 3(2^\frac{1}{3} - 1) = 0.77976\ldots$

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

[編集] 関連項目

[編集] 参考文献

↑ C. L. Liu and J. Layland. 'Scheduling algorithms for multiprogramming in a hard real-time environment', Journal of the ACM, 10(1), 1973.
↑ 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.
↑ 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.
↑ 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.
↑ 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.

M. Joseph and P. Pandya. 'Finding Response times in Real-time systems', BCS Computer Journal, 29(5), pp. 390-395, October 1986.

[編集] 外部リンク

いずれも英文

"http://ja.wikipedia.org../../../%E3%83%AC/%E3%83%BC/%E3%83%88/%E3%83%AC%E3%83%BC%E3%83%88%E3%83%A2%E3%83%8E%E3%83%88%E3%83%8B%E3%83%83%E3%82%AF%E3%82%B9%E3%82%B1%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0.html" より作成

カテゴリ: OSのプロセス管理 | 並行計算