|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
レートモノトニックスケジューリング（Rate-Monotonic Scheduling、RMS〔C. L. Liu and J. Layland. 'Scheduling algorithms for multiprogramming in a hard real-time environment', ''Journal of the ACM'', 10(1), 1973.〕）はリアルタイムオペレーティングシステムで使われているスケジューリングアルゴリズムの一種。プリエンプティブで固定優先度を使用する最適なスケジューリングである。 == 特徴 == このアルゴリズムを使用する場合のプロセスの前提条件は以下の通りである。 *リソース(ハードウェアリソース、キュー、セマフォなど)を共有しない。 *デッドライン(実行期限)が分かっていて、実行周期と完全に一致している(つまり、次の起動までに今回の実行を終えればよい)。 *固定優先度(プロセッサが解放されたり、新たなタスク周期が開始されたら、最高固定優先度のプロセスが他の全タスクをプリエンプトして起動される) *固定優先度は ''rate monotonic'' という原則に従って設定される(実行周期/実行期限が短いタスクに高い優先度を与える)。 RMSは統計的なモデルであり、イベントの記録を含んでいる。予測可能な数の入力だけがある閉鎖された環境で使われる。リアルタイムシステムにおいてはラウンドロビンやタイムシェアリングはうまく機能しない。RMSは履歴を参照してプロセスの処理時間やプロセスの起動時刻を決定する。 1973年、LiuとLaylandは、固有の周期を持つ個の周期的タスクは、CPU使用率が以下の式を満たすならば常にデッドラインを満たしてスケジュールできることを証明した。 : は計算時間、は周期である。例えば、 のとき となる。プロセス数が無限大に近づくとこの式は以下のようになる: : 従って、一般にRMSが全デッドラインを満たしてスケジュールできるCPU使用率の限界は となる。残りの の時間は低優先度の非リアルタイムタスクに使用できる。しかしこれは、タスクの組み合わせによらずスケジューリング可能であるための十分条件にすぎず、かなり保守的な値となっている。実際CPU利用率が前後までであるなら、デッドラインミスが起こるタスクの組み合わせは極めて稀である。それを表す端的な例として、ランダムに生成された周期タスクについて、CPU使用率が 以下ならば全デッドラインを満たすことが知られている。〔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.〕 しかし、これはタスクの統計情報(周期、デッドラインなど)を正確に知っているかどうかに依存するので、あらゆるタスクの組合せで保証されるものではない。 レートモノトニックの優先度設定が「最適; optimal」であるという場合、任意の固定優先度スケジューリングアルゴリズムが全デッドラインを満たすことができるなら、RMSアルゴリズムも同様であることを意味している。デッドラインモノトニックスケジューリング(DMS)は、デッドラインと周期が異なる場合に「最適」のアルゴリズムである。デッドラインと周期が等しい場合RMSとDMSは等価であり、デッドラインが周期より短い場合DMSは「最適」である。〔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.〕 デッドラインが周期より長い場合の最適な固定優先度スケジューリングは「未解決の問題」である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「レートモノトニックスケジューリング」の詳細全文を読む スポンサード リンク
|