11.3.優先度スケジューリング規律（１）：Quantitative System Performance

「11.2.密結合マルッチプロセッサ」の続きです。（目次はこちら）

11.3.優先度スケジューリング規律

　現在の大部分のオペレーティング・システムでは、プロセッサ・スケジューリング規律は優先度に基づいている。これらの優先度は静的（ある作業負荷要素に他に対する一貫した優先をあたえる）かもしれないし、あるいはそれらは動的（作業負荷特性の変化する評価を反映して）かもしれない。優先度スケジューリング規律は分離可能モデルと両立可能ではない。これらの規律は性能にかなりの影響を与え得るので、それらを表現出来ることは重要である。これまで多くの方法が考案されてきた。
　ひとつの方法が第８章に一例として記述された。まず、Ｉ／Ｏサブシステムはそれ自身は分離可能であったが、分離して解析され、複数クラス・フロー等価サービス・センターが構築された。次に２つのセンター、つまり、このＦＥＳＣと優先スケジュールのＣＰＵからなる高レベル・モデルが定義された。最後に、このモデルを評価するために大域バランス技法が使われた。この方法は全く正確である。その欠点は、第１に、それが特定目的大域バランス・ソフトウェアを要求することで、第２に、大域バランス解析の複雑さのために、数クラスあるいは数個の客以上を持つモデルについて、そして複数の優先度スケジュールのセンターを持つモデルについてそれは実行不可能になるということである。
　今、最後の段落で説明した技法を用いることの難しさのため、他の方法が要求される。我々がここで紹介するものは、平均値解析技法に基づいている。実際、それは受入れ可能な程度の精度であることを示してきたし、非常に大きなモデルであっても適用可能である。種の客クラスをもち、その各々が区別される優先度をＣＰＵで持っているようなモデルを考察しよう。（同じ優先度を持ついくつかのクラスへの一般化は単純である。）　記法を簡単にするために、クラスはより大きい数のクラスがより小さい数のクラスより優先権があるように並んでいると仮定しよう。我々はクラス客のＣＰＵでの滞在時間の近似を、クラスより低い、と等しい、より高いジョブの効果を続けて考察することによって開発する。

• より優先度の低い客（クラス１からまで）
  • クラスはクラス１からまでに対して割込み優先度を持っているので、これらのクラスの客はクラス客を邪魔しない。これらのより低いクラスだけを考慮して我々はクラスのＣＰＵ滞在時間の以下の近似を得る。
    • 
• 優先度の等しい客（クラス）
  • ＣＰＵに到着する個々のクラス客はすでにそこにいる全ての他のクラス客のうしろに待たなければならない。それ以降到着したクラス客はそれ以上の遅れを引き起こさない。より低い優先度と等しい優先度の両方のクラスを考慮することにより我々は、
    • 
  • ただしは、もしクラスがトランザクション・タイプでなければ（つまり、もしクラスがクローズドであれば）、１個のクラス客を除いた負荷強度のベクトルであり、さもなければ（つまり、もしクラスがオープンであれば）完全な負荷強度である。
• より優先度の高い客（クラス からまで）
  • 到着するクラス客は、すでにキューにいる全てのより高い優先度の客を待たなければならない。それはまた、それがＣＰＵにいる間に到着する全てのより高い優先度の客をも待たなければならない。この複雑さのために、クラス客が待たなければならないような、より高い優先度の客の数を正確に見積もることは可能ではない。その代わり我々は、より高い優先度の客へのサービスがクラス客へ充てられるサービスに関してプロセッサの分解であると考える。これらの分解のため、サービス中のクラス客が時間単位を積み上げるために時間単位以上が要求される。特に、ＣＰＵは時間の の割合、より高い優先度の客でビジーなので、現在選ばれたクラス客が完了するのに時間単位かかる。（例えば、一旦サービスが始まったら、より高い優先度の客で５０％ビジーのプロセッサ上で完了するのはＦＣＦＳプロセッサ上でよりも２倍の長さだけかかる。）　より低い、等しい、より高い優先度クラスを考慮した、クラス の滞在時間についての最終近似は、よって
    • （１１．１）
  • である。

　式（１１．１）をアルゴリズム７．１や７．２における標準滞在時間方程式に代入することにより平均値解析からひとつの解法を構築することが出来るであろう。しかし、我々がモデル化技法を拡張する度にこれらの基本アルゴリズムをさらに複雑にするよりもむしろ、我々の拡張したアルゴリズム内のサブルーチンとして基本アルゴリズムを用いて、それらを足場にして進めるほうがよい。（我々は第１６章でこの層構造実装のコンセプトに戻る。）
　優先度スケジューリングの場合、シャドウＣＰＵ技法を用いて滞在時間方程式を置き換えることによって得られるのと同じ結果を得ることが出来る。この技法は、実際のシステムでの１台の優先度スケジュールＣＰＵは、各々に１つのクラスが訪問するような個のFCFSサービス・センターによってモデル内に表現されるという事実からその名を得ている。が、クラスにのみが訪問する 番目のシャドウＣＰＵを示しているとしよう。でのサービス要求時間を

• 

に等しく設定する。そのシャドウＣＰＵでのクラスの滞在時間は式（１１．１）で与えられることは明白であるはずであろう。より高い優先度クラスによって引き起こされたサービス要求時間の水増しはシャドウＣＰＵでのサービス要求時間の再定義において捉えられ、他のクラスではなくクラスの客を待つことはシャドウＣＰＵで使用されるＦＣＦＳスケジュールの結果、プラス、クラスだけがそこを訪問するという事実の結果である。よって、我々は第７章の解析技法に素直に従う、優先度スケジューリングの効果を表現する待ち行列ネットワークを構築した。

「11.3.優先度スケジューリング規律（２）」に続きます。