レートモノトニックスケジューリング（Rate-Monotonic Scheduling、RMS）はリアルタイムオペレーティングシステムで使われているスケジューリングアルゴリズムの一種。プリエンプティブで固定優先度を使用する最適なスケジューリングである。このアルゴリズムを使用する場合のプロセスの前提条件は以下の通りである。RMSは統計的なモデルであり、イベントの記録を含んでいる。予測可能な数の入力だけがある閉鎖された環境で使われる。リアルタイムシステムにおいてはラウンドロビンやタイムシェアリングはうまく機能しない。RMSは履歴を参照してプロセスの処理時間やプロセスの起動時刻を決定する。1973年、LiuとLaylandは、固有の周期を持つformula_1個の周期的タスクは、CPU使用率が以下の式を満たすならば常にデッドラインを満たしてスケジュールできることを証明した。formula_3は計算時間、formula_4は周期である。例えば、formula_5 のとき formula_6 となる。プロセス数が無限大に近づくとこの式は以下のようになる:従って、一般にRMSが全デッドラインを満たしてスケジュールできるCPU使用率の限界は formula_8 となる。残りの formula_9 の時間は低優先度の非リアルタイムタスクに使用できる。しかしこれは、タスクの組み合わせによらずスケジューリング可能であるための十分条件にすぎず、かなり保守的な値となっている。実際CPU利用率がformula_10前後までであるなら、デッドラインミスが起こるタスクの組み合わせは極めて稀である。それを表す端的な例として、ランダムに生成された周期タスクについて、CPU使用率が formula_11 以下ならば全デッドラインを満たすことが知られている。 しかし、これはタスクの統計情報(周期、デッドラインなど)を正確に知っているかどうかに依存するので、あらゆるタスクの組合せで保証されるものではない。レートモノトニックの優先度設定が「最適; optimal」であるという場合、任意の固定優先度スケジューリングアルゴリズムが全デッドラインを満たすことができるなら、RMSアルゴリズムも同様であることを意味している。デッドラインモノトニックスケジューリング(DMS)は、デッドラインと周期が異なる場合に「最適」のアルゴリズムである。デッドラインと周期が等しい場合RMSとDMSは等価であり、デッドラインが周期より短い場合DMSは「最適」である。デッドラインが周期より長い場合の最適な固定優先度スケジューリングは「未解決の問題」である。多くの実用アプリケーションにおいて、リソースは共有されるものである。従って、RMSは優先順位の逆転とデッドロック問題に対処する必要がある。これを解決する方法として優先度継承が導入された。優先度継承アルゴリズムの例を以下に列挙する:優先度継承アルゴリズムは2つのパラメータで分類できる。第一は継承が(本当に必要なときだけに)遅延されるか、(衝突が発生する前に)即座に行われるかである。第二は継承が(必要最小限だけ)楽観的に行われるか、(必要以上に)悲観的に行われるかである。実際、遅延アルゴリズムと即時アルゴリズムに数学的な違いはなく、即時アルゴリズムの方が実装が効率的であるため、多くの実用システムで使われている。基本優先度継承プロトコルは「ブロックの連鎖」を生じる可能性がある。すなわち、高優先度のタスクがクリティカルセクションに入ろうとして実際に入れるまでに長時間待たされる可能性がある。他のプロトコルでは高優先度タスクがクリティカルセクションに入る前にせいぜい1つの低優先度のクリティカルセクションが実行されるだけであることを保証している。優先度上限プロトコルはVxWorksリアルタイムカーネルでも使えるが、滅多に使用されない。基本優先度継承の使用例としてマーズ・パスファインダーのバグ問題がある。火星上でバグを回避する手段して用いられたのが優先度継承である。3つの周期的プロセスが動作するシステムを考える。なお、実行時間も周期も同じ単位の時間(例えば10ミリ秒)であり、P1は8単位周期(80ミリ秒)に起動し、1単位(10ミリ秒)だけ動作することを示している。CPU使用率は以下のようになる:formula_13 プロセスの理論的限界は以下のようになる:従って formula_15 であるため、システムはスケジュール可能である。いずれも英文

出典:wikipedia