レートモノトニックスケジューリング
レートモノトニックスケジューリング(Rate-Monotonic Scheduling、RMS)はリアルタイムオペレーティングシステムで使われているスケジューリングアルゴリズムの一種。プリエンプティブで固定優先度を使用する最適なスケジューリングである。
このアルゴリズムを使用する場合のプロセスの前提条件は以下の通りである。
リソース(ハードウェアリソース、キュー、セマフォなど)を共有しない。
デッドライン(実行期限)が分かっていて、実行周期と完全に一致している(つまり、次の起動までに今回の実行を終えればよい)。
固定優先度(プロセッサが解放されたり、新たなタスク周期が開始されたら、最高固定優先度のプロセスが他の全タスクをプリエンプトして起動される)
固定優先度は rate monotonic という原則に従って設定される(実行周期/実行期限が短いタスクに高い優先度を与える)。
RMSは統計的なモデルであり、イベントの記録を含んでいる。予測可能な数の入力だけがある閉鎖された環境で使われる。リアルタイムシステムにおいてはラウンドロビンやタイムシェアリングはうまく機能しない。RMSは履歴を参照してプロセスの処理時間やプロセスの起動時刻を決定する。
1973年、LiuとLaylandは、固有の周期を持つ n {\displaystyle n} 個の周期的タスクは、CPU使用率が以下の式を満たすならば常にデッドラインを満たしてスケジュールできることを証明した。
そして、低優先度のタスクがそのセマフォを獲得した状態の場合、上限優先度以下の他のタスクがそれを横取りできない(プリエンプションできない)ようにする。
優先度継承アルゴリズムは2つのパラメータで分類できる。第一は継承が(本当に必要なときだけに)遅延されるか、(衝突が発生する前に)即座に行われるかである。第二は継承が(必要最小限だけ)楽観的に行われるか、(必要以上に)悲観的に行われるかである。
実際、遅延アルゴリズムと即時アルゴリズムに数学的な違いはなく、即時アルゴリズムの方が実装が効率的であるため、多くの実用システムで使われている。
基本優先度継承プロトコルは「ブロックの連鎖」を生じる可能性がある。すなわち、高優先度のタスクがクリティカルセクションに入ろうとして実際に入れるまでに長時間待たされる可能性がある。他のプロトコルでは高優先度タスクがクリティカルセクションに入る前にせいぜい1つの低優先度のクリティカルセクションが実行されるだけであることを保証している。
優先度上限プロトコルはVxWorksリアルタイムカーネルでも使えるが、滅多に使用されない。
基本優先度継承の使用例としてマーズ・パスファインダーのバグ問題がある。火星上でバグを回避する手段して用いられたのが優先度継承である。