Product Design, Manufacturing & Innovation Resources
» レートモノトニックスケジューリング(RMS)

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

1973
  • C. L. Liu
  • James Layland
制御室にあるコンピュータワークステーションで、リアルタイムシステムのレートモノトニックスケジューリングを解析している。

(画像はイメージです)

レートモノトニックスケジューリング(RMS)は、リアルタイムシステムにおける周期的なタスクのための静的優先度スケジューリングアルゴリズムです。タスクの頻度に基づいて優先度を割り当てます。タスクの周期が短いほど(レートが高いほど)、優先度が高くなります。RMSは最適な静的優先度アルゴリズムであり、静的優先度アルゴリズムでタスクセットをスケジューリングできる場合、RMSでもスケジューリングできます。スケジューリング可能性は、利用率に基づくテストで確認できます。

レートモノトニックスケジューリング(RMS)は、リアルタイムシステム理論の礎石であり、1973年にLiuとLaylandによって発表された画期的な論文で初めて提唱されました。これは、単一のプロセッサ上で、独立したプリエンプティブな周期タスク群をスケジューリングするための、シンプルでありながら強力な手法です。その基本原理は、各タスクの周期に反比例する固定優先度をタスクに割り当てることです。例えば、10ミリ秒ごとに実行する必要のあるタスクは、100ミリ秒ごとに実行されるタスクよりも高い優先度を持つことになります。

RMS の重要性は、その最適性と、単純なスケジューラビリティ テストの存在にあります。これは、最適な静的優先度スケジューリング ポリシーであることが証明されています。つまり、タスク セットが任意の静的優先度アルゴリズムによってスケジュールできる場合、RMS でもスケジュールできます。RMS の下でのタスク セットのスケジューラビリティは、利用率境界テストを使用して決定できます。n 個のタスクのセットの場合、プロセッサの総利用率 U は、各タスク i の実行時間 C_i を期間 T_i で割った値の合計です。U = sum_{i=1}^{n} frac{C_i}{T_i} LiuとLaylandは、この総利用率が特定の上限[latex]U le n(2^{1/n}-1)[/latex]以下であれば、タスクセットはスケジューリング可能であることが保証される(つまり、期限を逃すことはない)ことを証明した。nが無限大に近づくと、この上限は[latex]ln(2) approx 0.693[/latex]に収束する。これはスケジューリング可能性の十分条件ではあるが、必要条件ではない。より精密だが複雑なテストとして、厳密解析または応答時間解析と呼ばれる方法も使用できる。

UNESCO Nomenclature: 1203
コンピュータサイエンス

タイプ

ソフトウェア/アルゴリズム

混乱

増分

使用法

広く普及している

前駆物質

  • 待ち行列理論
  • オペレーションズリサーチ
  • コンピュータスケジューリングアルゴリズムに関する初期の研究
  • タイムシェアリングオペレーティングシステムの開発

アプリケーション

  • 衛星制御システム
  • 自動車制御アプリケーション
  • 航空電子機器および飛行制御システム
  • 産業オートメーションとロボット工学
  • リアルタイム信号処理

特許:

NA

潜在的なイノベーションのアイデア

ボットによるトラフィック(現在1日あたり4万件以上)を排除するため、このコンテンツはコミュニティメンバー限定となっています。
> ログイン < または > 登録 < (100%無料)でこれにアクセスできます。他のすべての制限付きコンテンツとツールも同様です。

関連キーワード:レートモノトニックスケジューリング、RMS、リアルタイムシステム、スケジューリングアルゴリズム、静的優先度、周期タスク、スケジューリング可能性分析、利用限界、LiuとLayland、最適スケジューリング。

歴史的背景

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

1970
1970
1970
1973
1980
1980
1980
1970
1970
1970
1970-01-01
1975-06-01
1980
1980
1980

(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)

フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。