(57)【特許請求の範囲】
【請求項１】
ユーザによるシステム・リソースの使用をスケジューリングする方法であって、
ユーザ・ディスパッチ優先順位に関連付けられている第１の人工時刻クロックを維持するステップと、
限界リスト優先順位に関連付けられている第２の人工時刻クロックを維持するステップと、
ディスパッチ・プロセス中に
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングするステップと、
それ以外の場合に、
ユーザ時間分だけ前記第１の人工時刻クロックを進めるステップと、
ユーザ時間および待機時間分だけ前記第２の人工時刻クロックを進めるステップと、
待機プロセス中に、
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出すステップと、
それ以外の場合に、前記待機時間が所定の値を超過したときに活動待機状況にあるＣＰＵが存在する場合、前記待機時間分だけ前記第１の人工時刻クロックを増分し、前記ディスパッチ・プロセスを呼び出すステップと
を含む方法。
【請求項２】
スケジューラ・プロセス中に
前記ユーザのユーザ・シェアを決定するステップと、
前記ユーザ・シェアが所定の最大許容シェアを超過した場合、前記ユーザ・シェアと、前のタイム・スライス上のオーバランに応じて調整されたタイム・スライスとに基づいてユーザ・オフセットを計算するステップと、
前記ユーザ・オフセットを加えた現行ディスパッチ優先順位に等しい前記ユーザの新しいディスパッチ優先順位を計算するステップと、
前記新しいディスパッチ優先順位が前記ユーザ・オフセットの関数分だけ前記第１の人工時刻クロックを超過した場合、前記ユーザを待機状況にして前記ディスパッチ・プロセスを呼び出し、それ以外の場合に前記ディスパッチ・プロセスを呼び出すステップと、
前記ディスパッチ・プロセス中に、前記ユーザがタイム・スライスを完了したときに、前記スケジューラ・プロセスを呼び出すステップと
をさらに含む請求項１に記載の方法。
【請求項３】
さらに前記ディスパッチ・プロセス中に
前記ユーザが前記第２の人工時刻クロックの１つのタイム・スライス内の限界優先順位で待機状況になっている場合、限界状況から前記ユーザを除去するステップを
さらに含む請求項２に記載の方法。
【請求項４】
複数の限定ユーザ間でシステム・リソースの使用をスケジューリングする方法であって、
ユーザ・ディスパッチ優先順位に関連付けられている第１の人工時刻クロックを維持するステップと、
限界リスト優先順位に関連付けられている第２の人工時刻クロックを維持するステップと、
ディスパッチ・ルーチンを実行するステップと、
活動待機ルーチンを実行するステップと、
優先順位再計算ルーチンを実行するステップを
含み、
前記優先順位再計算ルーチンが
第１のユーザのユーザ・シェアを計算するステップと、
前記ユーザ・シェアが所定の最大許容シェアを超過した場合、前記ユーザ・シェアと、前のマイナー・タイム・スライス上のオーバランに応じて調整されたマイナー・タイム・スライスのサイズとに基づいてユーザ・オフセットを計算するステップと、
前記ユーザ・オフセットを加えた古い優先順位に等しいユーザ・ディスパッチ優先順位を計算するステップと、
前記ユーザ・ディスパッチ優先順位が前記ユーザ・オフセットの関数を加えた前記第１の人工時刻クロックに等しい最大降下値を超過し、これが限定ユーザであり、このユーザがその最大シェアでスケジューリングされる場合、前記ユーザを限界リストに追加するステップと、
それ以外の場合に前記ユーザをディスパッチ・リスト上に優先順位順に再順序付けするステップと、
前記ディスパッチャ・ルーチンを実行するステップと
を含み、
前記ディスパッチャ・ルーチンが
ディスパッチすべき作業がない場合、前記活動待機ルーチンを実行し、それ以外の場合にいずれかの優先順位システム作業を実行するステップと、
前記ユーザのマイナー・タイム・スライスが終了したばかりの場合、前記スケジューラ・ルーチンを実行するステップと、
それ以外の場合にユーザ時間によって前記第１の人工時刻クロックを進めるステップと、
ユーザ時間および待機時間によって第２の人工時刻クロックを進めるステップと、
前記限界リスト上のユーザが前記第２の人工時刻クロックの１つのマイナー・タイム・スライス内にある場合、前記限界リストから前記ユーザを除去するステップと、
ディスパッチ・リスト優先順位に基づいてユーザをディスパッチするステップと
を含み、
前記活動待機ルーチンが
実行すべき新しい作業がある場合、前記ディスパッチャ・ルーチンを実行するステップと、
それ以外の場合に前記限界リスト上にユーザが存在し、活動待機処理が所定の限界を超過した場合、
前記第１の人工時刻クロックに待機時間を追加するステップと、
前記ディスパッチャ・ルーチンを実行するステップと
を含み、
それにより、ユーザが早すぎない時期に前記限界リストに追加され、遅すぎない時期に前記限界リストから除去される方法。
【請求項５】
システム・リソースをスケジューリングする方法において、
（１）（ａ）ユーザ最小シェア割当てと、（ｂ）ユーザがシステム・リソースを消費しているときに前進する第１の人工時刻クロックと、（ｃ）高ディスパッチ優先順位限界と、（ｄ）低ディスパッチ優先順位限界とによって定義される境界内でプロセッサ使用率に関する優先順位をユーザに付けるステップであって、前記第１の人工時刻クロックは、ユーザ・ディスパッチ優先順位に関連付けられている、前記ステップと、
（２）（ａ）選択されたユーザに割り当てられるユーザ最大限定シェア割当てを確立し、（ｂ）限界リストを設け、及び（ｃ）ユーザがシステム・リソースを消費している場合および前記システム・リソースが待機している場合に前進する第２の人工時刻クロックを設けることにより、ユーザによる中央演算処理装置の消費を前記境界内の指定の絶対値に制限するステップであって、前記第２の人工時刻クロックは、限界リスト優先順位に関連付けられている、前記ステップと、
（３）限界リスト優先順序を決定し、前記第２の人工時刻クロックの前進に基づいて前記限界リストから除去すべき時期を決定するステップと、
（４）前記ＣＰＵがアイドルであるときに、着信タスクの活動待機対話式連続モニタを用意するステップと、
（５）最大使用率シェアに基づいてユーザに優先順位を割り当てるステップと、
（６）前記低ディスパッチ優先順位限界を超過したときに、前記限界リストにユーザを掲載するステップと、
（７）前記限界リスト上の存続持続時間を決定するために前記第１の人工時刻クロックの時間を前記第２の人工時刻クロックの時間に変換するステップと、
（８）限界シェア・ユーザがＣＰＵリソースを求めて競合する時期を認識するステップと、
（９）前記システム・リソースが定義された実時間間隔の間、連続活動待機状況になっていた時期を認識し、それに対する応答として、前記第１の人工時刻クロックおよび前記第２の人工時刻クロックを待機時間分だけ更新するステップと、
（１０）ユーザを前記限界リストから除去する（図９符号７０）ステップであって、前記ユーザは、前記第２の人工時刻クロック値が低ロード条件下で前記第２の人工時刻クロックに含まれる実質的にすべての前記待機時間を有する前記限界リスト優先順位を超過する、前記除去するステップと
を含む方法。
【請求項６】
ユーザによるシステム・リソースの使用をスケジューリングするための方法ステップを実行するためにマシンによって実行可能な命令からなるプログラムを具体的に実施する、マシンによって読取り可能なプログラム記憶装置において、前記方法ステップが、
ユーザ・ディスパッチ優先順位に関連付けられている第１の人工時刻クロックを維持することと、
限界リスト優先順位に関連付けられている第２の人工時刻クロックを維持することと、
ディスパッチ・プロセス中に
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングすることと、
それ以外の場合にユーザ時間分だけ前記第１の人工時刻クロックを前進することと、
ユーザ時間および待機時間分だけ前記第２の人工時刻クロックを前進することと、
待機プロセス中に
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出すことと、
それ以外の場合に、前記待機時間が所定の値を超過したときに活動待機状況にあるＣＰＵが存在する場合、前記待機時間分だけ前記第１の人工時刻クロックを増分し、前記ディスパッチ・プロセスを呼び出すことと
を含む、プログラム記憶装置。
【請求項７】
ユーザによるシステム・リソースの使用をスケジューリングするプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
コンピュータに、
ユーザ・ディスパッチ優先順位に関連付けられている第１の人工時刻クロックを維持することを実施させる手段と、
限界リスト優先順位に関連付けられている第２の人工時刻クロックを維持することをコンピュータに実施させる手段と、
ディスパッチ・プロセス中に
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングすることと、
それ以外の場合にユーザ時間分だけ前記第１の人工時刻クロックを前進することと、
ユーザ時間および待機時間分だけ前記第２の人工時刻クロックを前進することを実施させる手段と、
待機プロセス中に
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出すことと、
それ以外の場合に、前記待機時間が所定の値を超過したときに待機状況にあるユーザが存在する場合、前記待機時間分だけ前記第１の人工時刻クロックを増分し、前記ディスパッチ・プロセスを呼び出すこととを実施させる手段として機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項８】
ユーザによるシステム・リソースの使用をスケジューリングするためのシステムにおいて、
ユーザ・ディスパッチ優先順位に関連付けられている第１の人工時刻クロックと、
限界リスト優先順位に関連付けられている第２の人工時刻クロックと、
ディスパッチ・プロセスであって
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングし、
それ以外の場合にユーザ時間分だけ前記第１の人工時刻クロックを前進し、
ユーザ時間および待機時間分だけ前記第２の人工時刻クロックを前進するためのディスパッチ・プロセスと、
待機プロセスであって
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出し、
それ以外の場合に、前記待機時間が所定の値を超過したときに待機状況にあるユーザが存在する場合、前記待機時間分だけ前記第１の人工時刻クロックを増分し、前記ディスパッチ・プロセスを呼び出すための待機プロセスと
を含むシステム。
【請求項９】
スケジューラ・プロセスであって
前記ユーザのユーザ・シェアを決定し、
前記ユーザ・シェアが所定の最大許容シェアを超過した場合、前記ユーザ・シェアと、前のタイム・スライス上のオーバランに応じて調整されたタイム・スライスとに基づいてユーザ・オフセットを計算し、
前記ユーザ・オフセットを加えた現行ディスパッチ優先順位に等しい前記ユーザの新しいディスパッチ優先順位を計算し、
前記新しいディスパッチ優先順位が前記ユーザ・オフセットの関数分だけ前記第１の人工時刻クロックを超過した場合、前記ユーザを待機状況にして前記ディスパッチ・プロセスを呼び出し、それ以外の場合に前記ディスパッチ・プロセスを呼び出すためのスケジューラ・プロセスと、
前記ユーザがタイム・スライスを完了したときに、前記スケジューラ・プロセスを呼び出す前記ディスパッチ・プロセスと
をさらに含む、請求項８に記載のシステム。
【請求項１０】
前記ディスパッチ・プロセスが、
前記ユーザが前記第２の人工時刻クロックの１つのタイム・スライス内の限界優先順位で待機状況になっている場合、限界状況から前記ユーザを除去するための前記ディスパッチ・プロセスをさらに含む、請求項９に記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、システム・スケジューラに関する。より詳細には、ユーザがディスパッチ主導型マルチプロセッサ・システムにおいてそれに対する資格を有するリソースをユーザに対してスケジューリングすることに関する。
【０００２】
【従来の技術】
オペレーティング・システムには、ユーザが消費するシステム・リソースの量を制御するためにスケジューラが設けられている。Ｇ．Ａ．デヴィソン（Ｄａｖｉｓｏｎ）により１９９４年６月２日に出願された同時係属の米国特許出願第０８／２５２８６４号には、このようなシステムが記載されている。
【０００３】
多くの場合、コンピュータ・システムでは、多くのプログラムまたはユーザが並行して実行することが必要になる。複数のプログラムを実行するために１つまたは複数のプロセッサが使用可能になる場合もある。どのような１つのプロセッサも一度に１つのプログラムまたはトランザクションしか実行することができない。２つまたはそれ以上のプログラムが同時に実行することを要求し、１つのプロセッサまたは実行を必要とするプログラムの数より少ないプロセッサしかない場合、オペレーティング・システムは、どのプログラムが一度に１つのプロセッサまたは各プロセッサを使用できるかを決定しなければならない。通常、この決定は、それぞれのプログラムの相対的優先順位に基づいて行われる。通常、低速入出力動作が完了するのを待っているものなど、待機状態にあるプログラムは、「中断」され、したがって、その優先順位にかかわらず、そのプロセッサを求めて競合する資格はない。
【０００４】
どのプログラムが特定の時点で１つのプロセッサまたは各プロセッサを使用できるかを決定することに加え、オペレーティング・システムは、優先順位が等しい（またはおそらくそれより低い）他のプログラムがそれぞれの順番を獲得できるように、実行を開始した後で、どのくらいの間、選択したプログラムがそれぞれのプロセッサを使用できるかも決定しなければならない。実行を開始した後で、どのくらいの間、各プログラムがプロセッサを使用できるかを決定するための既知の技法はいくつか存在する。最も単純な技法では、優先順位が最も高いプログラムが完了（または中断）までプロセッサの使用を維持する。しかし、これにより、このプログラムがそのプロセッサを「ホグ」し、他のプログラムを「飢えさせる」場合もある。他の既知の技法では、実行のために選択された各プログラムに対し、全プロセッサ時間のうちのシェアまたは「スライス」が与えられる。プログラムの全シェアは等しいものにするかまたは好ましいことに様々な要因に基づいて重み付けすることができる。全シェアに重み付けするための既知の技法の１つは以下の通りである。一部のプログラムは全プロセッサ時間のうちの「絶対」または確定シェアを指揮するよう定義され、他のプログラムは残りのプロセッサ時間のうちの「相対」シェアを指揮するよう定義される。絶対シェアは「先頭から取られ」、相対シェアはそれぞれの相対シェアに比例して残りを分割する。たとえば、第１のプログラムは４０パーセントの絶対シェアで定義され、第２のプログラムは１００の相対シェアで定義され、第３のプログラムは３００の相対シェアで定義される。このシナリオでは、第１のプログラムが全プロセッサ時間の４０パーセントを指揮し、第２のプログラムが全プロセッサ時間の１５パーセントを指揮し、第３のプログラムが全プロセッサ時間の４５パーセントを指揮することになる。
【０００５】
１つのプログラムは、その絶対または相対シェア全体を必要としない場合がある。この絶対／相対シェア環境で超過分を割り振るための既知の技法は、最高絶対または相対シェアを伴うプログラムに超過分をすべて与えることである。超過分が全プロセッサ時間のうちのわずかな割合である場合、この既知の技法で十分であると思われる。しかし、多くの場合、全プロセッサ時間の半分など、超過分は相当な量であり、超過分をすべて１つのプログラムに割り振ることが最適ではない場合もある。
【０００６】
システムのうち、ユーザがそれに対する資格を有する相対シェアは、現在、システム・リソースを求めて競合しているすべての相対シェア・ユーザの優先順位の割合に基づくものである。しかし、相対シェア・ユーザにとって必ずしもすべてのシステム・リソースが使用可能であるわけではない。リソースを求めて競合する複数の絶対シェア・ユーザが存在する場合、このような絶対シェア・ユーザには、システムの残りのシェアが相対シェア・ユーザ間で比例分割される前に、先にシステムの一部が与えられる。このような関係は一般に以下のように表すことができる。
残りのシェア＝システムの１００％−すべての絶対シェアの合計
【０００７】
次に、残りのシェアは以下のように相対シェア・ユーザ間で比例分割される。
相対ユーザのシェア＝残りのシェア＊（ユーザの相対シェア／すべての相対ユーザの合計シェア）
【０００８】
マイナー・タイム・スライスとは、スケジューラによる再検査のための割込みなしに所与のユーザが所有できるプロセッサ時間の量である。マイナー・タイム・スライスのサイズは、マシン速度と、あるいは顧客設定とに依存する。ユーザがディスパッチされると、ＣＰＵタイマはマイナー・タイム・スライスの時間の量で設定される。このタイマは、時間切れになると、減分して割込みを提示し、その結果、ユーザのマイナー・タイム・スライスが終了したことをスケジューラに通知する。
【０００９】
限定ユーザ、すなわち、「リミットハード」ユーザとは、ユーザがそれに対する資格を有するプロセッサ・リソースの最大量を表すものとして限界値が定義されたユーザである。この限界値は、最大使用率シェアを表し、そのユーザのディスパッチ優先順位を計算するために使用する。通常、プロセッサ・リソースのうち、それぞれの最大許容シェアを超過するかまたは超過しそうなリミットハード・ユーザが掲載された限界リストが用意される。あるユーザが限界リストに掲載されている（またはそれ以外の方法で限界状況によって特徴づけられている）間、その使用のためにリソースがディスパッチされることはない。
【００１０】
ユーザ作業をディスパッチする際に、人工時刻（ＡＴＯＤ）クロックが使用される。このＡＴＯＤ値は、マシンの時刻（ＴＯＤ）クロックと同じ速度で増加するが、そのユーザ作業（オペレーティング・システム作業などの非ユーザ作業とは区別される）がマシンによって実行されている間に限られる。システム・リソースをスケジューリングするために少なくとも一部はＡＴＯＤに依存する現行システムでは、限定シェア・ユーザは、ＣＰＵリソースが使用可能であっても、その最大使用率シェアに達することが許されない場合がある。明らかなことに、アイドル・プロセッサ・リソース時間を含む低ロード状況では、アイドル時間の間、人工時刻（ＡＴＯＤ）値が十分な速さで移行するわけではない。したがって、実行中のリミットハード・ユーザのディスパッチ優先順位はＡＴＯＤに対して本来あるべき速度より速く移行し、時期尚早に限界リストに入る（すなわち、限界状況が与えられる）。さらに、活動状態の（非アイドル）プロセッサだけがそのリストを監視するので、ユーザが不必要に限界リスト上に保持される場合もある。低ロード状況（すべてのプロセッサを使用中として維持するのに十分な作業がない時間）では、活動状態のプロセッサの数が減少し、したがって、限界リストの監視頻度が低下する。このため、ユーザが限界リストから出なければならない時期からそれが出なければならないことをプロセッサが検出する時期までの時間が増加する。これまでは、プロセッサが活動待機状態にある間にこのユーザを限界リストから除去するためのメカニズムはまったく存在しなかった。このような状況では、プロセッサが実行すべきユーザ作業を一切持たず、したがって、活動待機メカニズムでループしている時間があり、限界リストの検査を行わせるような何かが他のプロセッサ上で発生するまで、限界リスト上のユーザはそこに存続する。
【００１１】
その結果、上記のデヴィソン出願に記載されているような現行システムがそのうえに有するユーザが非常に少ない場合、または現行システムが使用中ではない場合、そのスケジューラは、ハード限界までの使用率を有することができるはずであるときにそのハード限界より少ないＣＰＵ時間をユーザに与える。コンピュータ・システム上のユーザが非常に少ない場合、不思議なことに、ユーザは資格を有するものより２０％減以内の著しく少ないＣＰＵ時間を獲得する。その結果、特にＣＰＵ時間が売却される場合に、支払っただけのＣＰＵ時間のすべてを獲得できないユーザから苦情が出る可能性がある。逆に、請求できるときに、ＣＰＵ時間が請求されないこともある。
【００１２】
【発明が解決しようとする課題】
本発明の一目的は、低ロード状況でそのハード限界に極めて近いかまたは等しいシステム・リソースへのユーザ・アクセスの許可を容易にするためのスケジューラ・システムおよび方法を提供することにある。
【００１３】
本発明の他の目的は、システム・リソースに関する最適請求を容易にし、請求の総額またはこのようなリソースの可用性に対するユーザの不快感を低減する、改良されたスケジューラを提供することにある。
【００１４】
本発明の他の目的は、ユーザの優先順位を決定し、どのユーザが次に実行できるかを決定するためにシステムが使用するスケジューリング・アルゴリズムへのフィードバック・メカニズムとしてモニタ・データが使用される、システムおよび方法を提供することにある。
【００１５】
本発明の他の目的は、限定アクセス権を有するユーザを早すぎない時期に限界リストに掲載し、遅すぎない時期に限界リストから除去することにより、このようなユーザに対してシステム・リソースをスケジューリングするためのシステムおよび方法を提供することにある。
【００１６】
本発明の他の目的は、遅すぎない時期にリソースのスケジューリングを可能にし、早すぎない時期にリソースのスケジューリングを禁止することにより、限定アクセス権を有するユーザに対してシステム・リソースをスケジューリングするためのシステムおよび方法を提供することにある。
【００１７】
【課題を解決するための手段】
第１のクロックを維持し、第２のクロックを維持し、ディスパッチ・プロセス中に実行すべき作業がある場合、ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順にユーザに対してシステム・リソースの使用をスケジューリングし、それ以外の場合にユーザ時間分だけ第１のクロックを前進し、ユーザ時間および待機時間分だけ第２のクロックを前進し、待機プロセス中に実行すべき作業がある場合、ディスパッチ・プロセスを呼び出し、それ以外の場合に待機時間の時間的調節を行い、待機時間が所定の値を超過したときに待機状況にあるユーザが存在する場合、待機時間分だけ第１のクロックを増分し、ディスパッチ・プロセスを呼び出すことにより、システム・リソースはユーザによる使用のためにスケジューリングされる。
【００１８】
【発明の実施の形態】
上記の同時係属特許出願第０８／２５２８６４号に記載されているシステムに対する改良である本発明の好ましい実施の形態によれば、オペレーティング・システムは、限定アクセス権を有するユーザを早すぎない時期に限界リストに掲載し、遅すぎない時期に限界リストから除去することにより、このようなユーザに対してシステム・リソースをスケジューリングする。
【００１９】
したがって、活動待機ルーチンに組み込まれたモニタの使用により「ディスパッチ主導型」マルチプロセッシング・システムにおいて特定のユーザのＣＰＵ使用率をある絶対値に制限するためのシステムおよび方法が提供される。使用するメカニズムは、ユーザのリストであって、そのＣＰＵリソースはそれぞれの消費量が限界値を超過しないように制限されなければならない。このようなユーザは「限界状況」を有するものとして特徴づけられる。あるユーザを低ロード状況でリストから除去しなければならない（このため、「ディスパッチ状況」に復元される）時期を決定し、その結果、それが使用可能であれば最大ＣＰＵ使用率をそのユーザに供給するために、限界リストは活動待機監視される。本発明の好ましい実施の形態によれば、この活動待機ルーチン（プロセスまたはプロシージャとも言う）は、ユーザの優先順位を決定し、どのユーザが次に実行（ディスパッチ）できるかを決定する際にその有効性を強化するようスケジューリング・ルーチンを動的に調整するために監視されフィードバックされたパフォーマンス・データを使用して、限界リストからユーザを除去するためにディスパッチ・ルーチンを呼び出す時期を決定するために、限界リスト上のユーザを監視する。ユーザの限界リスト優先順位の１つのマイナー・タイム・スライス内に入るようＡＴＯＤ２が計算されたときに、ユーザはディスパッチ・ルーチンによって限界リストから除去される。
【００２０】
ユーザ・タスクは、あるユーザのタイム・スライスの終わりを表すディスパッチ優先順位値に応じて実行されるようスケジューリングされる。この値は、時刻（ＴＯＤ）フォーマットになっており、以下に詳述する。
【００２１】
図１を参照すると、システム図は本発明の好ましい実施の形態のプログラミング（データおよび方法）構造を示している。このようなプログラミング構造としては、システム・リソース２０、実時間クロック２２、ユーザ最小シェア割当て２４、ユーザ最大シェア割当て２６、活動待機連続モニタ３０、着信タスク３２、ディスパッチャ４０、スケジューラ４４、ＡＴＯＤ２  ２１、ＡＴＯＤ２３、オフセット２５、限界リスト２７、限界リスト上の存続持続時間（存続時間とも言う）２９、ユーザの優先順位境界３５、ディスパッチ・リスト３７、最大降下１８、ＴＯＤ−ＴＩＥＤ２８を含む。以下に説明するように、このような構造間の連係によって本発明の方法の好ましい実施の形態が実現される。
【００２２】
もう一度、図１を参照すると、動作に当たっては、線８１が表すように、ディスパッチャ４０は、着信作業３２を探し、実行すべき何らかの作業がある場合にスケジューラ４４によって設定された優先順位に基づいてそれを実行させる。線８２が表すように、実行すべき作業がまったくない場合、ディスパッチャ４０は活動待機連続モニタ３０を呼び出す。線８３が表すように、活動待機プロセス３０は、着信作業３２がないかどうかシステムを連続的に監視し、線８２がさらに表すように、何らかの作業が到着したときにそれを実行するためにディスパッチャ４０を呼び出す。線８４が表すように、ディスパッチャ４０は、ユーザがマイナー・タイム・スライスの終わりに達したときにユーザのディスパッチ優先順位を再計算するためにスケジューラ４４を呼び出す。線８５、８６、８７、８８がそれぞれ表すように、スケジューラ４４は、ディスパッチ優先順位計算への入力として、システム・リソース２０、実時間クロック２２、ユーザの最小シェア割当て２４、ユーザの最大シェア割当て２６を使用する。線８９が表すように、スケジューラ４４は、最後にＡＴＯＤ２が更新されてから実際にユーザを実行するために使用したＣＰＵ時間に待機時間（実行すべき作業がまったく使用可能になっていない場合）を加えた量だけＡＴＯＤ２を前進することにより、ＡＴＯＤ２  ２１を更新する。線９０が表すように、スケジューラ４４は、最後にＡＴＯＤが更新されてから実際にユーザを実行するために使用したＣＰＵ時間の量だけＡＴＯＤを前進し、本発明にとって重要な所与の状況下では待機時間分も前進することにより、ＡＴＯＤ２３を更新する。更新されたＡＴＯＤ＝前のＡＴＯＤ＋最後にＡＴＯＤが再計算されてからのユーザＣＰＵ時間になる。線９１が表すように、スケジューラ４４は、優先順位計算に使用されるそのユーザのオフセット２５を計算する。オフセット２５は、ユーザのディスパッチ優先順位３５を計算するときにＡＴＯＤ２３の現行値からの変位として使用される。線９２および９３が表すように、ユーザのディスパッチ・リスト優先順位３５（締切り優先順位または予測完了時間とも言う）は、スケジューラ４４の計算に基づいて設定され、ＡＴＯＤ２３の現行値とユーザのオフセット２５のサイズに基づく境界内にある。線３１および３３が表すように、ユーザのディスパッチ・リスト優先順位３５は、ディスパッチャ４０がそれを実行を必要とする着信タスク３２と見なすように、他の作業による優先順位順にユーザの作業をディスパッチ・リスト３７に掲載するために使用される。スケジューラ４４は、そのユーザをディスパッチ・リスト３７に掲載するためにＡＴＯＤ２３を使用してユーザのディスパッチ・リスト優先順位３５を計算し、そのユーザを限界リスト２７に掲載することによりそのユーザのリソース消費量を制限する必要があるときにＡＴＯＤ２  ２１を使用して限界リスト２７の優先順位を計算する。線９５が表すように、計算された上部境界はＴＯＤ−ＴＩＥＤ２８と呼ばれる。線９４が表すように、計算された下部境界は最大降下１８と呼ばれる。線９６が表すように、最大降下境界１８の外側になるようにスケジューラによってそのディスパッチ優先順位３５が計算��れる限定シェア・ユーザは、限界リスト２７に追加される。線９７および９８が表すように、限界リスト２７上の存続持続時間２９の予測は、ＡＴＯＤ２  ２１に基づいて行われる。線９９が表すように、ユーザは、スケジューラ４４によって除去すべき時期になるまで、限界リスト２７上に存続する。線１２０が表すように、低ロード状況では、活動待機プロセス３０は、ユーザを除去しなければならない可能性のある時期を決定するために限界リスト２７を監視する。
【００２３】
ＡＴＯＤ、ＴＯＤ−ＴＩＥＤ、ディスパッチ優先順位、オフセットを決定するために必要な計算ならびにユーザに対してリソースをスケジューリングする際のその使い方について、以下に説明する。最大降下を計算するための式は以下の通りである。
最大降下＝ＡＴＯＤ＋４＊オフセット
【００２４】
オフセットを計算するための式は以下の通りである。
オフセット＝（マイナー・タイム・スライス−オーバラン）／（ＣＰＵの数＊シェア）
【００２５】
式中、オーバラン＝ユーザが優先順位がより高い作業によって先取りされた場合にユーザの前のマイナー・タイム・スライス上に残っている時間の量である。
【００２６】
ユーザのディスパッチ優先順位は、優先順位境界である最大降下とＴＯＤ−ＴＩＥＤの範囲内で計算された整数値である。ＴＯＤ−ＴＩＥＤメカニズムに関するより完全な説明を以下に示す。
【００２７】
ＡＴＯＤ２３およびＡＴＯＤ２  ２１は、システム上のすべてのユーザのユーザ時間とシステムの待機時間を全体として累積するために使用するデータ構造（フィールド）である。個々のユーザ時間または待機時間あるいはその両方は追跡する必要はない。このような累積は、システムの活動と比較して、ユーザのマイナー・タイム・スライスの終わりなど、発生すべき所与の事象を予測する際に使用する。
【００２８】
図２〜図８およびそれらに関する以下の説明は、デヴィソンによる同時係属特許出願第０８／２５２８６４号から適応され、本発明の理解にとって重要な基本概念のチュートリアルを構成し、これは主に、実質的に早すぎない時期にユーザを限界リストに追加し、遅すぎない時期にそのユーザを除去するという目標に改良を加えるように待機時間を含むようにＡＴＯＤおよびＡＴＯＤ２を調整するために提供されたメカニズムの改良である。
【００２９】
図２は、オペレーティング・システム３８がディスパッチャ４０と、スタッカ４２と、スケジューラ４４と、残りの諸機能４６とを含むことを示している。スタッカは、スケジューラとディスパッチャならびにディスパッチャおよびスケジューラとオペレーティング・システムの残りの部分とのインタフェースである。処理の流れに関する高レベル説明を以下に示す。典型的なシナリオでは、ユーザは何らかの作業を実行するようオペレーティング・システムの「残りの部分」４６に要求する。この作業要求は、ユーザの状況を「作動可能」として記録するスタッカ４２に渡される。スタッカは、ユーザがその作業に対して異なる視点を有する可能性があっても、ユーザから到着する作業を１つまたは複数の「トランザクション」として見る。ユーザが完全アイドルの状態（「アイドル」）から実行準備ができている状態（「作動可能」）に移行したときに、「新しい」トランザクションが開始される。また、ユーザが依然として進行中の作業（トランザクション）を持っているが、完了すべき仮想入出力要求を待っており、したがって、一時的に実行準備ができていないときに存在する「中断」という第３の状態もある。中断の期間は、新しいトランザクションを宣言するのに十分な根拠にならない。次に、スタッカはこのユーザに関する作業待ち行列に要求を渡す。また、スタッカは、ディスパッチ・リスト３７上の他のユーザに対するこのユーザのディスパッチ優先順位３５を示す情報を入手するためにスケジューラも呼び出す。次に、スタッカは、このユーザ（実際にはユーザのＶＭＤＢＫ）をディスパッチ・リスト３７に掲載し、オペレーティング・システムの「残りの部分」に戻る。ディスパッチ優先順位はディスパッチ・リスト上のユーザの順序付けを実施する。オペレーティング・システムの残りの部分は、その現行作業部片を完了すると、ディスパッチャ４０に制御を移して、実行すべき次のユーザおよび作業部片を決定する。次にディスパッチャは、ディスパッチ・リスト３７内の第１の作動可能ユーザと、次にディスパッチすべきユーザの作業待ち行列内の第１の作業部片を選択する。次に、ディスパッチャ４０は、オペレーティング・システムの残りの部分に制御を移して、この作業の実行を開始する。次に、ディスパッチされた作業は所定の持続時間のタイム・スライス、たとえば、１ミリ秒の間、実行される。１ミリ秒のタイム・スライスが終了する前にこの作業項目が完了した場合、ディスパッチャは実行すべき同じユーザの作業待ち行列から他の作業部片を選択する。このタイム・スライスの終了時に、ユーザが依然として実行すべき作業を持っている場合、ディスパッチャは、このユーザ用の次のタイム・スライスの新しい優先順位を入手するために、もう一度スケジューラ４４を呼び出す。この新しい優先順位によりユーザはディスパッチ・リスト内で位置変更され、次にこれが、同じユーザのためにこの次のタイム・スライスが始まる時期を決定する。同じユーザ用の連続タイム・スライス間の時間は、一部分ではこのユーザ用のプロセッサ時間のシェアを決定する。
【００３０】
すべてのユーザは、それぞれの絶対または相対シェアにかかわらず、均一持続時間の個別タイム・スライスについてディスパッチされ実行される。前述の例では、各タイム・スライスは１ミリ秒である。タイム・スライスは一般にプロセッサの速度に基づくものであり、この実施の形態のために選択された１ミリ秒は一例に過ぎず、システムに合わせるために指定変更することができる。各ユーザ（ＶＭＤＢＫによって表される）は、タイム・スライスを完了した後、割込みが行われ、ディスパッチ・リスト内の下の方に移動する（再優先順位付けが行われる）。これにより一般に他のユーザがこのプロセッサを使用できるようになる。プロセッサの各ユーザのシェアは、そのユーザに割り振られたタイム・スライス間の間隔と、ユーザが各タイム・スライスを使用するために必要とする時間によって決定され、各ユーザは必ずしも１連続ミリ秒で単一のタイム・スライスを消費するわけではない。ユーザが入出力動作を待たなければならない場合、入出力動作が完了するのを待つ時間がこのユーザのタイム・スライスにカウントされないように、一時的に中断され、プロセッサから外される（しかし、ディスパッチ・リスト３７内に存続する）。たとえば、ある入出力動作では数ミリ秒が完了する必要がある可能性があっても、入出力制約のユーザは、単一タイム・スライスを使い果たす前に１０回またはそれ以上の入出力動作を開始し、その完了を待つことができる場合が多いだろう。また、優先順位がより高い他のユーザ用の作業が到着した場合、ディスパッチャは、そのユーザのタイム・スライスの終了前にそのプロセスから実行中のユーザを除去し、ある期間の間、それを中断することができる。オペレーティング・システムは、タイム・スライス間の間隔を制御することにより、各ユーザのプロセッサ時間の実際のシェアを制御することができる。あるユーザのためのタイム・スライス間の間隔は逆に、瞬間ごとのディスパッチ・リスト内の他のユーザのシェアと比較して、ディスパッチ・リスト３７内のユーザのシェアの大きさに対応する。ＶＭＤＢＫが１つのタイム・スライスを完了するたびに、その１つのＶＭＤＢＫについてのみディスパッチ・リスト３７内で再優先順位付けおよび位置変更が行われる。単一タイム・スライスがばらばらに使用される場合、累積された時間が１ミリ秒のタイム・スライスと等しくなるまで、スケジューラはそのユーザのタイム・スライス間の間隔を再計算しない。タイム・スライス間の公称間隔を決定するための技法については、以下に詳述する。
【００３１】
ＮウェイＭＰシステム内の各ＣＰＵは、時刻（ＴＯＤ）クロック２２とＣＰＵタイマとを有する。ＴＯＤクロックは、マイクロ秒ごとに増分される５２ビットのハードウェア・レジスタを含む。ＴＯＤクロックは、オペレーティング・システムが初期設定され（ブートされ）、その後まったく変更されないときに設定される。ＮウェイＭＰシステムでは、ＴＯＤクロックのすべてのＮが互いに正確にマイクロ秒に同期している。ＴＯＤクロックは、時間ゼロが１９００年１月１日の夜中の１２時になるように設定される。５２ビットのＴＯＤクロック（すなわち、ビット０〜５１）がマイクロ秒をカウントする場合、このクロックは繰り返す前に１４０年以上の間動作することができる。ＴＯＤクロックは、決して停止せず、必ず増加し、実時間を示す信頼でき正確なタイム・スタンプかつ基準である。
【００３２】
ＣＰＵタイマは、各タイム・スライスの時間的調節を行うためにオペレーティング・システム３８が使用する、もう１つの５２ビットのハードウェア・レジスタを含む。ＣＰＵタイマは、システム・オペレータがＣＰＵを停止した場合に動作を停止し、オペレータがＣＰＵを再始動すると直ちにもう一度開始する（これに対してＴＯＤクロックは連続的に動作する）。ＣＰＵタイマおよびタイム・スライスの前進は、ＣＰＵがもう一度始動されたときに再開する。各ユーザがそのタイム・スライスを開始すると、ＣＰＵタイマから開始時間が明記される。同様に、ユーザが中断状態になるたびに、それがもう一度実行するときにこのユーザのためにタイム・スライスのうちのどの程度が残っているかを決定するために、ＣＰＵタイマの時間が明記される。したがって、ＣＰＵが停止したときに処理中であり、ＣＰＵタイマと比較されるユーザは、そのタイム・スライスの資格を一切失うことはない。
【００３３】
また、スケジューラは、人工時刻（ＡＴＯＤ）クロックとして知られるソフトウェア・クロック（および後述する第２の人工時刻クロックＡＴＯＤ２）も有する。ＡＴＯＤクロックはハードウェアＴＯＤクロックと同様であるが、（ＣＰＵあたり１つずつではなく）１つしか存在せず、わずかに遅く動作する。ＣＰＵの全使用可能処理能力のうちの所与の量は、特定のユーザに帰することができないオペレーティング・システム・オーバヘッドに費やされる。したがって、全処理時間のうちのこの量はユーザのシェアとして分割するために使用可能なものではない。全処理のうち、システム・オーバヘッドである割合は瞬間ごとに変動し、１００％未満のうちのどの程度がユーザのシェアのために使用可能であるかを把握することが難しい。このような困難は、オペレーティング・システムがオーバヘッド機能を実行している間は停止するようにＡＴＯＤクロックを定義し、ユーザにシェアを供給する計算においてＴＯＤ時間ではなくＡＴＯＤ時間を使用することによって回避される。次にＡＴＯＤクロックでは、オーバヘッドが実行されている間、時間が停止する。したがって、ＡＴＯＤクロックが測定する時間の１００％は使用可能な処理に対応する。シェアを供給するための計算は、ＡＴＯＤクロックに基づくものであり、したがって、処理の１００％がユーザのシェアのために使用可能である場合と同様に計算することができる。
【００３４】
オペレーティング・システム３８では、優先順位番号が低ければ低いほど、実際の優先順位が高くなる。優先順位番号は各ユーザごとに変化し続け、ディスパッチ順序は作動可能ユーザ間の相対優先順位番号に基づくものである。優先順位番号は、ユーザ／ＶＭＤＢＫがディスパッチ・リスト３７に掲載されたときにそれぞれの絶対または相対シェアに基づいてスケジューラによって計算される。ディスパッチ・リストに入ったばかりのユーザについて計算する場合、優先順位番号は通常、ＡＴＯＤクロックの現行値よりわずかに（数ミリ秒だけ）大きくなる。（しかし、実際上、最初のいくつかのタイム・スライスの場合、非常に短いトランザクションの場合にユーザに対して迅速応答を行うために、より小さい優先順位が使用される。このような変更はユーザのシェアに著しく影響しないように非常に短時間のものである。）ＡＴＯＤはいつでも前進しているので、古く未完了のタスクは、新しいタスクよりも、通常、より低い優先順位番号を有し、それ故に高い優先順位を有し、且つディスパッチ・リストの最上部付近に位置する傾向がある。以下に詳述するように、ディスパッチャは、実行リスト（非作動可能または中断ユーザを除くディスパッチ・リスト３７のコピーであり、したがって、実行状況を有するユーザの集合またはリストである）上で最上部から下にサーチし、実行すべきユーザを突き止める。時間が進むにつれて、作動可能タスクの方が優先順位がより高いためにユーザがディスパッチされない場合、またはユーザがディスパッチされたが入出力制約を受け、そのタイム・スライスを完了せずに「中断された」多くの時間を費やす場合、ユーザの優先順位は、（１）より最近、トランザクションを開始するユーザと、（２）入出力制約を受けないユーザに関して増加する。このような２つの点はそれぞれ真実である。というのは、（１）そのタイム・スライスが完了するまでユーザの優先順位番号が固定されたままになるのに対し、新しいトランザクションを開始する他のユーザには、ＡＴＯＤが増加するにつれて累進的により高い優先順位番号が割り当てられ、（２）より多くのＣＰＵ制約のユーザが多くのタイム・スライスを使用し、それぞれの後で下に移動するからである。したがって、入出力制約のユーザは、非入出力制約のユーザより高い相対優先順位を有する傾向にあり、一般に、ディスパッチおよび実行リストの最上部付近に位置決めされ、実行準備ができているときに、すなわち、各入出力動作が完了した後で、迅速にＣＰＵが提供される。
【００３５】
各ユーザごとに、絶対または相対シェア２４、２６（システム・ディレクトリ内に指定され、時にはシステム・オペレータによって変更される）が存在する。また、各ユーザごとに、指定の「ソフト限界」、「ハード限界」、または「限界なし」も存在する。未使用処理時間が使用可能になると、すべてのユーザは、未使用処理時間がまったくない場合と同様に計算されたそれぞれの絶対シェアおよび相対シェアに比例して超過処理時間を受け取り始める。しかし、いずれかのハード限界ユーザがそのハード限界に達すると、それ以上の割振りは一切行われない。いずれのハード限界ユーザに対しても、ハード限界を超過する処理時間のシェアを割り振ることはできない。いずれかのソフト限界ユーザがそのソフト限界に達すると、他のいずれかのソフト限界ユーザがまだそのソフト限界に達しなければならないかまたは他のいずれかのハード限界ユーザがまだそのハード限界に達しなければならない場合、あるいは超過処理時間を使用できる無制限ユーザが存在する場合、このソフト限界ユーザに対してそれ以上の割振りは一切行われない。まだそれぞれの限界に達していない他のソフト限界ユーザおよびハード限界ユーザは、それぞれの限界にも達するまで、超過シェアを受け取り続ける。他のすべてのソフト限界ユーザがそれぞれのソフト限界に達し、すべてのハード限界ユーザがそれぞれのハード限界に達したときに、超過処理時間を使用できる無制限ユーザがまったく存在しない場合、最も大きい絶対シェアまたは相対シェア（未使用処理時間がまったくない場合と同様に計算されたもの）を備えたソフト限界ユーザは残りの未使用処理時間をすべて受け取る。あるいは、すべてのソフト限界ユーザがそれぞれのソフト限界に達し、すべてのハード限界ユーザがそれぞれのハード限界に達したときに、超過処理時間を使用できる無制限ユーザがまったく存在しない場合、すべてのソフト限界ユーザは、未使用処理時間がまったくない場合と同様に計算されたそれぞれの絶対シェアまたは相対シェアに比例して、残りの未使用処理時間を分担する。
【００３６】
以下に詳述するように、シェア割振り技法は、ユーザが各タイム・スライスを完了した後で各ユーザをディスパッチ・リスト内で位置変更するかまたは下にオフセットすることによって実現される。オフセットの量は、絶対または相対シェアの大きさに基づくものである。各ユーザの入出力制約の相対量は、タイム・スライスを完了する直前にそのユーザの位置からオフセットを開始することにより、タイム・スライスを完了した後にディスパッチ・リスト内でそのユーザを位置変更するときに考慮される。その結果、ユーザは、非常に入出力制約を受ける場合、そのタイム・スライスを完了する前にディスパッチ・リストの最上部付近に位置することになり、したがって、タイム・スライスを完了し、下方オフセットを経験した後でもディスパッチ・リスト内の高い位置に位置変更される。（あるユーザが最初にディスパッチ・リストに入ると、オフセットはＡＴＯＤの付近から開始される。）
【００３７】
ディスパッチャ４０は図４〜図６に示すように実現される。ステップ１００では、ＣＰＵは、あるユーザ用の作業部片の実行を完了し、それをディスパッチャに通知する。応答として、ディスパッチャの第１のレベルは、そのユーザが現行の１ミリ秒タイム・スライスを完了したかどうかを判定する（判断１０２）。完了していない場合、第１のレベルのディスパッチャは、優先順位がより高いユーザがプロセッサを待っているかどうかを判定する（判断１０４）。待っていない場合、第１レベルのディスパッチャは、１つの作業部片を完了したばかりのユーザが実行すべき他の作業部片、すなわち、その作業待ち行列内の他の作業部片を有するかどうかを判定する（判断１０６）。有する場合、第１のレベルのディスパッチャは、ディスパッチャの第２のレベルを呼び出して、この同じユーザ用の他の作業部片を完了したばかりの同じＣＰＵ上で実行するためにこのユーザの待ち行列から次の作業部片をディスパッチする（ステップ１１０）。応答として、第２のレベルのディスパッチャは、このユーザの作業待ち行列上の第１の作業部片を選択し、この特定の作業部片を処理するためにオペレーティング・システム内の適切なルーチンに制御を移す（ステップ１１２）。
【００３８】
もう一度、判断１０２、１０４、１０６を参照すると、判断１０２がＹＥＳであるか、判断１０４がＹＥＳであるか、または判断１０６がＮＯである場合、第１のレベルのディスパッチャは、判断１２０に移行して、以下に説明するようにスケジューラのＡＴＯＤクロック（およびＡＴＯＤ２クロック）を更新する時期であるかどうかを判定する。この判断は、クロックの最後の更新以来、少なくとも１ミリ秒が経過したかどうかに基づいて行われる。経過した場合、ディスパッチャは、スタッカを呼び出して、ＡＴＯＤクロックおよびＡＴＯＤ２クロックを更新するようスケジューラに通知する（ステップ１２２）。次に、第１のレベルのディスパッチャは、未使用のものがある場合にユーザのタイム・スライスのうちのどの程度が未使用のまま存続しているかをまず記録することにより、ユーザを「アンディスパッチ」する（ステップ１３０）。判断１０２の結果としてステップ１３０に到達した場合、このタイム・スライスのうちのいずれも存続していない。しかし、ステップ１３０の前に判断１０４または判断１０６のいずれかが行われた場合、ある程度のタイム・スライスが存続している。次に、第１のレベルのディスパッチャは、そのタイム・スライスが完了されたかどうか（ならびにそのユーザを適格リストに循環して戻すべきかなどの他のいくつかのスケジューラ条件のいずれかを検査したかどうか）を判定する（判断１３２）。完了された場合、第１のレベルのディスパッチャは、スタッカを呼び出して、タイム・スライスの終了または他のスケジューラ条件を処理するようスケジューラに通知する（ステップ１３４）。次に、第１のレベルのディスパッチャは、トランザクションの実行を完了したばかりのＣＰＵの実行リストから優先順位が最も高いユーザを選択する（ステップ１３６）。このようなユーザが存在する場合（判断１４０）、第１のレベルのディスパッチャは、このユーザをディスパッチ済みとしてマークし、このユーザ用のタイム・スライスの時間的調節を行うためにそのタイム・スライス（またはその残りの部分）をＣＰＵタイマにロードし、第２のレベルのディスパッチャに移行する（ステップ１４２）。応答として、第２のレベルのディスパッチャは、ユーザの作業待ち行列からこのユーザ用の第１の作業部片を選択し、この特定の作業部片を処理するためにオペレーティング・システム部分４６内の適切なルーチンに制御を移す（ステップ１４４）。
【００３９】
もう一度、判断１４０を参照すると、トランザクションの実行を完了したばかりのＣＰＵに関するユーザが一切見つからなかった場合、第１のレベルのディスパッチャは、他のＣＰＵの実行リストから優先順位が最も高いユーザを選択する（ステップ１５０）。このようなユーザが見つかった場合（判断１５２）、第１のレベルのディスパッチャは、ステップ１４２に移行して、他のＣＰＵの実行リストからこのユーザをディスパッチする。しかし、他のＣＰＵの実行リスト上でこのようなユーザが一切見つからない場合、第１のレベルのディスパッチャは待機状態に移行する（ステップ１５４）。
【００４０】
図７はスケジューラ４４の一部分を示している。スケジューリングすべき新しいユーザの識別子を第２のレベルのディスパッチャから（スタッカを介して）受け取った後、スケジューラは、以下の通り、「ディスパッチ・リスト・シェア」を決定する（ステップ２００）。ステップ２０２では、スケジューラは、従来技術のＶＭ／ＥＳＡオペレーティング・システムに関して前述したようにユーザの絶対または相対シェアをシステムの処理時間の分数に変換する。すなわち、すべての絶対シェアは先頭から取られ（また、合計が９９パーセントを上回る場合は比例して削減され）、残りはそれぞれの相対シェアに比例してディスパッチ・リスト上の他のユーザ間で分割される。各ユーザごとの結果はプロセッサ時間の分数（０と１の間）であり、すべてのユーザの値を合計すると１になる。次に、スケジューラは、「適格」リストで待機して費やす時間についてユーザに補償するために、このユーザの「必須分数」（Ｒ’）を決定する（ステップ２０４）。ユーザは実行準備ができると適格リストに掲載されるが、そのユーザの作業を実行するために使用可能なメモリが不十分である。必須分数は、ステップ２０２で決定したシェアの分数に（ディスパッチ・リスト内の時間＋適格リスト内の時間）／（ディスパッチ・リスト内の時間）を掛けることによって決定される。各ユーザごとの必須分数は、適格リスト内に存続するたびにその後で再計算され、結果はディスパッチ・リスト内の次の期間に使用する。しかし、通常、すべてのユーザのために十分なメモリがあるので、適格リストへの「トリップ」はまれなことであり、通常、ステップ２０４はステップ２０２の結果に１を掛ける単純な乗算になる。次に、ディスパッチ・リスト内のすべてのユーザの必須分数を合計すると１になるように、スケジューラはこのユーザの必須分数Ｒ’を正規化する（ステップ２０６）。このユーザの正規化必須分数は「ディスパッチ・リスト・シェア」（または実行リスト・シェア）であり、以下に詳述する。このユーザのディスパッチ・リスト・シェアから、スケジューラはディスパッチ・リストおよび実行リストの下方への「オフセット」を決定する。大ざっぱに言えば、ユーザのオフセットは、ディスパッチ・リスト・シェアにタイム・スライスの長さを掛けて実ＣＰＵの数で割ったものの逆数である。オフセットが小さくなればなるほど、ユーザからＣＰＵへのアクセス数が増し、その逆も同様である。ユーザのオフセットの正確な値については以下に詳述する。
【００４１】
図８は、ある瞬間におけるディスパッチ・リスト３００を示している。このディスパッチ・リストは、実行準備ができているユーザと、中断されているユーザを含む。上記の通り、ディスパッチ・リスト３００上にあって実行準備ができているユーザは、サーチ時間を短縮するために実行リストにも掲載されているが、説明のためにはディスパッチ・リスト３００の図解の方が適当である。ディスパッチ・リストは一番上から下にサーチされ、最も高い優先順位（および最低優先順位番号）を備えたユーザが順序の先頭に掲載される。各ユーザがそのタイム・スライスを完了したときに、実行すべき作業をそれ以上有している場合、スケジューラはディスパッチ・リスト３００上（および間接的に実行リスト上）でその現行位置から下にこのユーザ用のオフセット２５に等しい量だけそのユーザを位置変更する。したがって、２つの要因がディスパッチ・リスト３００上のユーザの分布を実施する。第１の要因はオフセット２５の大きさである。上記の通り、各ユーザごとのオフセットの大きさは、ディスパッチ・リスト上の他のユーザのシェアに対するそのシェアに反比例し、異なるシェアを備えた他のユーザとは異なっている。したがって、シェアが小さければ小さいほど、オフセットは大きくなる。これは、ほとんどの場合、ディスパッチ３００の最下部付近に低シェア・ユーザを位置決めする傾向がある。第２の要因は、そのタイム・スライスを完了するためにユーザが必要とする実時間の量である。「入出力制約」のユーザは、１つのタイム・スライスを完了するために相当な入出力時間を必要とする。というのは、ユーザが入出力動作を開始した後でその入出力動作が完了するまで待っている相当な時間の間、そのユーザおよびそのタイム・スライス時間が中断されるからである。したがって、入出力制約のユーザは、そのタイム・スライスの実行を完了するために１ミリ秒のタイム・スライスよりかなり長い実時間を必要とし、入出力制約のユーザが実行リスト３００の最上部まで上昇すると、そのユーザは相当な時間そこに存続してから、そのタイム・スライスを完了し、下にオフセットされることになる。逆に、「ＣＰＵ制約」のユーザは、入出力時間をほとんど必要とせず、１ミリ秒またはそれよりわずかに長い時間でほとんど連続的にそのタイム・スライスを完了する。したがって、ＣＰＵ制約のユーザは、頻繁に下にオフセットされ、一般にディスパッチ・リストの最下部付近に常駐する。
【００４２】
したがって、どのような瞬間でも、入出力制約のユーザと、非常に大きいシェアを備えた他のユーザは、ディスパッチ・リストの最上部付近に位置する傾向があり、ＣＰＵ制約のユーザと、非常に小さいシェアを備えたユーザは、ディスパッチ・リストの最下部付近に位置する傾向がある。シェアおよび入出力対ＣＰＵ制約という２つの要因のうち、入出力の量対ＣＰＵ制約の方がディスパッチ・リスト内の位置に及ぼす影響が大きい（通常範囲のシェアの場合）。上記のような実行リスト上のユーザの位置決めは高いスループットをもたらす。というのは、入出力制約のユーザが実行準備ができたときに、すなわち、最後の入出力動作が完了したときに、ユーザは実行リスト３００の最上部付近に位置する可能性があり、迅速にＣＰＵを獲得することになるからである。
【００４３】
図８では、このようなオフセットは下方に曲線を描いて延びる矢印として左側に示されている。異なるユーザが異なるシェアを備えているので、オフセットによっては他のオフセットより長かったり短かったりする。典型的な状況では、現行（瞬時）ＡＴＯＤマークより下にあるすべてのユーザはＣＰＵ制約のユーザであり、現行ＡＴＯＤマークより上にあるすべてのユーザは入出力制約のユーザである。ユーザは、上記の効果により、そのようにソートされている。また、ディスパッチャは一般に、作動可能ユーザを見つけるために現行ＡＴＯＤマークより下にある多くのものをサーチする必要はなくなるだろう。というのは、その付近にあるＣＰＵ制約のユーザはほとんどいつでもディスパッチすることができるからである。したがって、ＡＴＯＤマーク位置およびそれより下の図８の左側にある「オフセット」矢印は一般にＡＴＯＤマーク位置またはそれよりわずかに下にあるユーザから発生することになる。しかし、ＡＴＯＤマークより上のディスパッチ・リストの上部部分では、矢印がどこでも発生する傾向がある。ただし、入出力制約のユーザがタイム・スライスを完了すると、前のタイム・スライスの時点におけるその典型的な高優先順位および高位置のために、そのユーザは通常はリストの最下部に移動せず、通常は依然としてＡＴＯＤマークより上に存続することに留意されたい。したがって、入出力制約のユーザは、入出力待機を完了した直後にもう一度ディスパッチされる可能性があり、高スループットが維持される。
【００４４】
上記のスケジューラは、自分のシェアを吸収できないユーザを「非常に激しく急き立てる」。このようなユーザの１人がその割当て済みシェアについてますます後れをとるので、このユーザがその全シェアを占める見込みがある場合に最終的にそのようにするまで、そのユーザはディスパッチ・リスト内をますます上昇する。したがって、上記のスケジューラは、単に各ユーザにＣＰＵへの所望のＡＣＣＥＳＳを与えるのではなく、ＣＰＵの各ユーザに所望のＳＨＡＲＥＳのうちの多くを与える際に効果的である。所望のシェアは、各ユーザの消費の履歴を計算せずに提供される。これは、「履歴」がそのユーザのディスパッチ・リスト位置に常駐しているからである。ＡＴＯＤマークに対するディスパッチ・リスト内のユーザの位置は、ユーザが受けるに値するものに対して、ユーザが過去に受け取ったプロセッサ時間のシェアを表している。ユーザがそれまでに受けるに値するものを正確に獲得している場合、そのユーザはＡＴＯＤマークの位置に正確に位置する。ユーザがＡＴＯＤマークより上にある場合、そのユーザは受けるに値するものより受け取ったものの方が少ない。ユーザがＡＴＯＤマークより下にある場合、そのユーザは受けるに値するものより受け取ったものの方が多い。
【００４５】
ステップ２０４で決定した必須分数Ｒ’は、以下のようにステップ２０６で正規化される。３通りの正規化のケースと、それぞれのケースの２通りの変形が存在する。３通りのすべてのケースでは、ディスパッチ・リスト上のすべてのユーザ（ＳＲＭＲＴＨＲＵ）またはＡＴＯＤマークより下にあるユーザ（ＳＲＭＣＴＨＲＵ）の必須分数の合計に基づいて計算が行われる。第２および第３のケースでは、前述のように限界を実施するために、その（ハードまたはソフト）限界に達していると判断されるかどうかに応じて、ＶＭＤＢＫは異なる方法で検討される。ディスパッチ・リスト内のすべてのユーザのＲ’の合計は以下の式で表される。
ＳＲＭＲＴＨＲＵ＝ＳＲＭＲＴＨＲＮ＋ＳＲＭＲＴＨＲＬ＋Ｒ’
【００４６】
式中、ＳＲＭＲＴＨＲＮはディスパッチ・リスト内にあって無制限であるかまたは自分の限界に達していないすべてのユーザの必須分数の合計であり、ＳＲＭＲＴＨＲＬはディスパッチ・リスト内にあって自分の限界に達したすべてのユーザの必須分数の合計であり、加算されるものとして示されているＲ’は現在検討中であって計算時にまだＳＲＭＲＴＨＮまたはＳＲＭＲＴＨＬ内に加えられていない１人のユーザのＲ’を表す。同様に、ＡＴＯＤマークより下にあるユーザの合計については以下の通りである。
ＳＲＭＣＴＨＲＵ＝ＳＲＭＣＴＨＲＮ＋ＳＲＭＣＴＨＲＬ＋Ｒ’
【００４７】
式中、ＳＲＭＣＴＨＲＮはＡＴＯＤマークより下にあって無制限であるかまたは自分の限界に達していないユーザの必須分数の合計であり、ＳＲＭＣＴＨＲＬはＡＴＯＤマークより下にあって自分の限界に達したユーザの必須スループットの合計である。（それぞれの変数内の文字「Ｃ」は、ＡＴＯＤマークより下にあるユーザをＣＰＵ制約のユーザとして見なすことができるという合図である。）以下の計算では（３通りのケースの場合）、ＳＲＭＲＴＨＲＮ変数およびＳＲＭＲＴＨＲＬ変数のみを示すが、検査中のユーザがＡＴＯＤマークより下にあるユーザの１人である場合にＳＲＭＣＴＨＲＮ変数およびＳＲＭＣＴＨＲＬ変数を代用する予定であることに注目することに留意されたい。これは、３通りのケースのそれぞれについて前述したように２通りの変形があることを反映している。
【００４８】
第１のケース：
（（ＳＲＭＲＴＨＲＬ＋ＳＲＭＲＴＨＲＮ＋Ｒ’）＞１かつＳＲＭＲＴＨＲＬ＞０．５）である場合、一部のユーザのシェアはより小さいものにしなければならず、自分の限界に達しているユーザは大きい部分（＞０．５）を構成するので、この時間の短縮にすべて含まれる。その場合、現行ユーザは以下のように正規化される。
正規化Ｒ’＝Ｒ’／（ＳＲＭＲＴＨＲＬ＋ＳＲＭＲＴＨＲＮ＋Ｒ’）
【００４９】
したがって、現行ユーザのシェアはより小さいものになる。
【００５０】
第２のケース：
（（ＳＲＭＲＴＨＲＬ＋ＳＲＭＲＴＨＲＮ＋Ｒ’）＞１であるがＳＲＭＲＴＨＲＬ＜０．５）である場合、一部のユーザのシェアはより小さいものにしなければならない。しかし、自分の限界に達しているユーザは大したものにはならない（それぞれのＲ’の合計＜０．５）ので、正規化されない。その場合、現行ユーザがその限界に達していない場合のみ、現行ユーザのシェアは以下のように調整される。
正規化Ｒ’＝Ｒ’＊（１−ＳＲＭＲＴＨＲＬ）／（ＳＲＭＲＴＨＲＮ＋Ｒ’）
【００５１】
したがって、その限界に達していないユーザのシェアはより小さいものになる。しかし、その限界に達している現行ユーザは以下の式を使用する。
正規化Ｒ’＝Ｒ’（限界）
【００５２】
式中、Ｒ’（限界）は、指定のハード限界またはソフト限界の正規化分数、すなわち、適格リスト時間の効果に応じて調整されたハード限界またはソフト限界である。正規化分数はその限界に達しているユーザ向けに限定されるので、これは、まだその限界に達していない少なくとも１人のユーザまたは少なくとも１人の無制限ユーザが存在する限り、それぞれの限界にあるこのようなユーザのシェアを制限する。
【００５３】
第３のケース：
（（ＳＲＭＲＴＨＲＬ＋ＳＲＭＲＴＨＲＮ＋Ｒ’）＜１．０）である場合、一部のユーザのシェアはより大きいものにしなければならない。その限界に達しているユーザのシェアはより大きいものにする必要がないので、その限界に達していないユーザについてのみ調整が行われる。現行ユーザがその限界に達していない場合、そのシェアは以下のように調整される。
正規化Ｒ’＝（上記のケース（２）と同じ）
【００５４】
この時点では、通常のユーザのシェアはより大きいものになる（上記のケース（２）とは異なる）。しかし、現行ユーザがその限界に達している場合、そのシェアは以下のように調整される。
正規化Ｒ’＝Ｒ’（限界）
【００５５】
正規化分数はその限界に達しているユーザ向けに限定されるので、これは、まだその限界に達していない少なくとも１人のユーザまたは少なくとも１人の無制限ユーザが存在する限り、それぞれの限界にあるこのようなユーザのシェアを制限する。
【００５６】
第１のケースと第２のケースが異なる理由は、可能であれば、限定ユーザのシェアは決して増加しないので、このようなユーザのシェアを低減しないことが好ましいからである（第３のケースを参照）。対照的に、他の時点でより大きいシェアを獲得することにより、無制限ユーザ用のシェアの損失が統計的に構成されることになる。
【００５７】
第１のケースと第２のケースとを区別する際に、ＳＲＭＲＴＨＲＬ＞０．５であるかどうかのテストが行われる。現行ユーザのシェアはより大きいものではなくより小さいものになるので、上記のどちらのケースでも現行ユーザのＲ’は考慮されない。したがって、その限界に達する見込みはない。したがって、このようなユーザの合計が＞０．５になるかどうかを確認するためにテストする場合、このようなユーザはその限界に達していると見なされない。
【００５８】
第１のケースでは、各Ｒ’ごとにすべてのＲ’の合計で割る。したがって、結果の値（正規化Ｒ’）の合計は１になる。式（ＳＲＭＲＴＨＲＬ＋ＳＲＭＲＴＨＲＮ＋Ｒ’）はすべてのＲ’の合計を表す。
【００５９】
ＳＲＭＲＴＨＲＬおよびＳＲＭＲＴＨＲＮがＳＲＭＲＴＨＲＵの構成要素部分（またはアレイ要素）であり、ＳＲＭＲＴＨＲＵがＲ’の合計であることを想起されたい。上記の各種ケースで計算を行う時点を除き、現行ユーザのＲ’はたまたまＳＲＭＲＴＨＲＵから引かれており、どの要素を新しいＲ’に加えるべきかを決定することはできないだろう。したがって、式（ＳＲＭＲＴＨＲＬ＋ＳＲＭＲＴＨＲＮ＋Ｒ’）はＲ’が明示的に加えられることを示している。
【００６０】
第２のケースでは、それぞれの限界に達していないユーザについてのみＲ’が調整されるのに対し、それぞれの限界に達しているユーザのＲ’は一定のままになる。したがって、その限界に達していないユーザのＲ’は、その限界に達していないすべてのユーザのＲ’の合計（ＳＲＭＲＴＨＲＮ＋Ｒ’）で割り、次にその結果に（１−ＳＲＭＲＴＨＲＬ）を掛けることによって正規化される。その限界に達しているユーザも存在するので、その限界に達していないユーザの正規化シェアの合計は１になる必要がないので、後者の要因は必要である。また、（ＳＲＭＲＴＨＲＮ＋Ｒ’）で割り、乗数を省くことによって得られる正規化Ｒ’は合計が１になる値を示すものと思われるので、当然の結果として、その正規化Ｒ’に（１−ＳＲＭＲＴＨＲＬ）を掛けた後で合計が（１−ＳＲＭＲＴＨＲＬ）になるだろう。事実、ＳＲＭＲＴＨＲＬに含まれるＲ’値はその限界であるＲ’（限界）に等しく設定されている。
【００６１】
以下の理由により、そのソフト限界またはハード限界にまだ達していないすべてのユーザにとって、その絶対または相対シェアに比例した超過プロセッサ時間が使用可能になる。図表では、これは、ディスパッチ・リスト内のユーザが（理論的には）ＡＴＯＤマークと同じ速度で進むことによって発生する。一般に、上記のメカニズムは、それに応じてオフセットを設定（または調整）することにより、絶対および相対シェアに比例してプロセッサ時間を分担しようと試みる。
【００６２】
ＡＴＯＤマークより下にあるユーザについては、このような比例は、ステップ２０６におけるＲ’の上記の正規化の２通りの特性によって発生する。ステップ２０６の説明で前述したように、ＡＴＯＤマークより下にある各ユーザごとの必須分数Ｒ’の正規化は、ＡＴＯＤマークより上にあるものを除き、ＡＴＯＤマークより下にあるユーザのセットに関する合計ＳＲＭＣＴＨＲＵに基づいて行われる。したがって、これはＡＴＯＤマークより下にあるユーザにより高い優先順序を与える傾向があり、それはオフセットがより小さいものであることによるものである。というのは、「正規化Ｒ’式」の分母はより小さく、すなわち、合計がＡＴＯＤマークより下にあるユーザのみに限定されているときに各ユーザのシェアは合計のうちのより大きい割合を占めると思われるからである。また、ＡＴＯＤより上にある入出力制約のユーザはなかなかそのタイム・スライスを使用しないが、プロセッサ時間の一部を使用する。したがって、ＣＰＵサービスのうちの１００％未満のものがＡＴＯＤマークより下にあるユーザに供給されることになり、そのオフセットは１００％を獲得するものに基づくことになるので、ＡＴＯＤマークより下にあるユーザは低速で上に移動する傾向があり、事実、ＡＴＯＤマークより遅れ始める。しかし、ＡＴＯＤマークより遅れることは、以下の理由によりディスパッチ・リスト内でこのようなユーザをもう一度下に移動させる傾向がある。ユーザがＡＴＯＤマークより上に移動すると直ちにそれはＡＴＯＤマークより下にあるユーザのセット内に入らなくなり、したがって、ＳＲＭＣＴＨＲＵではなくＳＲＭＲＴＨＲＵが「正規化Ｒ’」式の分母で使用されることになる。このようにＡＴＯＤマークより上に移動することは、ディスパッチ・リスト内でこのようなユーザをもう一度下に移動させる傾向がある。というのは、「正規化Ｒ’」式の分母がより大きいものになるからである（その結果、正規化Ｒ’はより小さいものになるが、オフセットはより大きいものになる）。ＡＴＯＤマークより上および下に移動する際のこのような２通りの傾向の正味の影響は、インストール定義の絶対および相対シェアに比例して「過剰」サービスが（それを使用できるユーザに）割り当てられることである。このようなユーザは、より速くではなく、ＡＴＯＤマークと同じ速度で前進する。
【００６３】
ＡＴＯＤマークより上の高い位置に位置するユーザには、そのユーザが使用できるのと同じ程度のプロセッサ時間が提供されるが、そのユーザは、自分の元のシェアの全量ではない場合であっても、一般に超過分のうちの自分のシェアの多くを使用することができない。しかし、それらがＣＰＵ制約のユーザになるようにそれぞれの条件が変化した場合、上記の理由により速やかにＡＴＯＤマークより下に低下し、そのインストール定義シェアに比例して超過プロセッサ時間を与える前記原理によって支配されることになる。
【００６４】
ステップ２０６のシェアの正規化に関する上記の説明では、その限界に達していない少なくとも１人の他のユーザまたは少なくとも１人の無制限ユーザが（ＡＴＯＤマークより下に）存在する場合に、ハードまたはソフト限定ユーザがそれぞれの限界に制限される方法について説明している。また、上記の説明には、ハード限界ユーザがそのハード限界より大きいシェアを受け取ることができないようにする方法、ならびにすべてのユーザがそれぞれの限界に達した後に残っているすべての超過プロセッサ時間を最も大きいシェアを備えたソフト限定ユーザに割り振る方法が記載されている。
【００６５】
上記のように、あるユーザがマイナー・タイム・スライスを完了すると、そのユーザはステップ１６０で計算した１つのオフセット分だけディスパッチ・リスト内で下に移動する。しかし、移動する前に、これによりＭＡＸＦＡＬＬ限界を超えてそれが移動するかどうかの判断が行われる。各ユーザのＭＡＸＦＡＬＬ限界はそのユーザのオフセットの４倍、すなわち、ＡＴＯＤマークより上の４つのオフセットに等しい。無制限ユーザまたはソフト限定ユーザがそれぞれのオフセットのためにＭＡＸＦＡＬＬ限界を超えて移動する場合、そのユーザはそのＭＡＸＦＡＬＬ限界を超えずにその限界まで下に移動する。ＭＡＸＦＡＬＬ限界により、無制限ユーザおよびソフト限定ユーザは自分のシェアより多くのものを獲得することができる。というのは、その結果、ディスパッチ・リスト内でそのシェアが本来示すものより高い位置に位置決めされるからである。事実、すべてのユーザがその限界に達しており、無制限ユーザがまったく存在しない場合、最も大きいシェアを備えたソフト限定ユーザは最も小さいオフセットを有し、したがって、最も小さいＭＡＸＦＡＬＬ限界を有することになるので、このようなユーザは実質的に残りのすべての超過プロセッサ時間を入手することになる。これにより、このようなユーザはディスパッチ・リスト内で他のソフト限定ユーザより上に位置決めされ、このようなユーザが使用できるすべての超過プロセッサ時間が与えられることになる。
【００６６】
しかし、ハード限定ユーザはＭＡＸＦＡＬＬ限界によって制限されないが、ＭＡＸＦＡＬＬ限界より下に低下すると、ハード限定ユーザは実行リストから限界リストに移動することになる。限界リストはユーザの優先順序（ＶＭＤＬＰＲＴＹ）に応じて順序付けられる。したがって、ハード限定ユーザがＭＡＸＦＡＬＬ限界より下に低下すると、そのユーザは一般にそれ以上のマイナー・タイム・スライスを完了しなくなるかまたはディスパッチ・リスト内でそれ以上下に移動しなくなる。このため、ハード限定ユーザはその指定の限界を超過するプロセッサ時間を入手できなくなる。というのは、ディスパッチャは限界リストに入っているユーザをディスパッチしないからである（ユーザは限界リストに掲載されている間、実行リストに入ることができない）。
【００６７】
ユーザはもはやスケジュールより早くならないようにそこで十分な時間を費やした後、限界リストから除去される。これは以下のように実施される。第２の「人工時刻」クロック「ＡＴＯＤ２」が形成される。このＡＴＯＤ２時間は、ユーザに与えられる生産的ＣＰＵサービスと待機時間の両方に比例して前進する。ＡＴＯＤ２が限界リストの先頭にあるユーザの限界リスト締切りに達すると、そのユーザは限界リストから除去され、実行リストに戻される。締切りに達する時間までにタイム・スライスを完了する時間をユーザに与えるために、そのユーザはその締切りより１タイム・スライス前に限界リストを離れる資格を有する。同時に、ディスパッチ・リストに入るユーザのために開始ディスパッチ・リスト優先順位を確立し、ＭＡＸＦＡＬＬ限界を計算するために、既存のＡＴＯＤを使用し続けることになる。言い換えると、ＡＴＯＤはディスパッチ・リストおよび実行時リスト用の「締切り」として機能する。
【００６８】
時にはユーザは、たとえば、それが続行する前に人間の介入を必要とする入出力装置のために、過度に長い入出力待機を経験することになる。その結果、ユーザは、ディスパッチ・リスト上で他のユーザより十分上の過度に高い位置に位置することになる。これは、ユーザがもう一度実行を開始するときに問題を含む。というのは、ユーザがＣＰＵ制約のユーザになった場合、そのユーザが他のすべてのユーザを超えて下に移動するまで他のすべてのユーザが実行できなくなり、そのユーザが非常に高い場合ならびにユーザを下に移動するために通常のオフセット機構に依存している場合に時間がかかりすぎる可能性があるからである。したがって、以下のメカニズムを使用して、このようなユーザを検出し、ディスパッチ・リスト上で高い位置にあるが、このような過度の入出力待機を経験したことがない他のユーザの付近に位置決めするのに十分なほど下にそれをオフセットする。「疑わしくない」ユーザ（すなわち、過度に入出力制約を受けているとまだ疑われていないユーザ）がタイム・スライスを完了する場合、そのユーザは必ず前述のように１つのオフセット分だけ下に移動する。しかし、ユーザがこの移動中に他の「疑わしくない」ユーザを通過しない場合、移動中のユーザは「疑わしい」ものとして指定される。（これは、移動中のユーザに関連するビットを設定することによって行われる。）この疑わしいユーザが次にタイム・スライスを完了するときに、疑わしいユーザは通常のオフセット分だけ下に移動し、そのユーザがこの移動中に「疑わしくない」ユーザを通過する場合、移動中のユーザはもう一度「疑わしくない」ものとしてマークされ、通過しない場合、移動中のユーザは、移動中のユーザが最初に遭遇する「疑わしくない」ユーザのすぐ上まで、さらに下に移動する。そのうえ、ＡＴＯＤマークより下にあるすべてのユーザは「疑わしくない」ものである。
【００６９】
「疑わしい」ユーザは、ＴＯＤ−ＴＩＥＤ（ＴＴ）属性が与えられたユーザである。ＴＯＤ−ＴＩＥＤメカニズムの目的は、優先順位を再配列することではなく、むしろユーザの相対順序を通常通り維持し、高く上昇しすぎたことによって発生するギャップを低減することである。ＴＯＤ−ＴＩＥＤ（ＴＴ）属性は、ＡＴＯＤの位置またはＡＴＯＤより下にあるすべてのユーザに属す。また、それは、あるＶＭＤＢＫの位置変更によってそれがＴＴを備えたＶＭＤＢＫを通過するときには必ず、あるＶＭＤＢＫから他のＶＭＤＢＫへ（ＡＴＯＤから）上に伝播される。ＡＴＯＤより上にあるＶＭＤＢＫがＴＴを備えた他のＶＭＤＢＫを通過しない場合、そのＶＭＤＢＫは属性を失う。その次のマイナー・タイム・スライスの後、あるＶＭＤＢＫがＴＴを取り戻せない場合、それはＴＴ属性を備えた次のＶＭＤＢＫの直前（または、介在ユーザがまったくいない場合はＡＴＯＤ）まで強制的に下ろされる。
【００７０】
過度に入出力制約のユーザは、入出力が完了するのを待っているので、スケジュール通りにそのマイナー・タイム・スライスを終了することは滅多にない可能性がある。システムが忙しすぎてユーザに対して十分なＣＰＵリソースを与えることができないためではなく、それが入出力動作を要求したために、そのユーザはスケジュールより遅れているように見える。本来、スケジューラ４４は、スケジュールより遅れているように見えるので、より高い優先順位によってこのユーザをスケジュールする傾向があるものと思われる。ＴＯＤ−ＴＩＥＤ２８境界の目的は、過度に入出力制約のユーザが高すぎるディスパッチ優先順位３５を獲得できないようにすることである。あるユーザがしばらくの間、過度に入出力制約のものとして存続する場合、その優先順位はますます高くなるだろう。そうである場合、そのユーザの優先順位は非常に高くなり、このユーザは、次にディスパッチされるときにＣＰＵ制約にならなければならない場合、システムのＣＰＵリソースを独占できるだろう。このようなシナリオを回避するため、ユーザはそのディスパッチ優先順位３５が高い優先順位であるＡＴＯＤ２３より遅れているときにＴＯＤ−ＴＩＥＤ属性を取得する。その後、このＴＯＤ−ＴＩＥＤ属性を備えたユーザには、それがＣＰＵ制約になった場合にシステムを引き継ぐことができなくなるように、優先順位の点でＡＴＯＤにかなり近いディスパッチ・リスト上にまとめて密集するように制限されている優先順位が与えられることになる。このＴＯＤ−ＴＩＥＤまたは「疑わしい」メカニズムは、ユーザのディスパッチ優先順位を高優先順位側のＡＴＯＤから妥当な変位内に維持するために使用されるが、最大降下は、ユーザをＡＴＯＤの低優先順位側に制限された状態に維持するために使用するメカニズムである。
【００７１】
ＡＴＯＤクロックは用意されている使用可能ＣＰＵ時間に比例して前進する。システム時間（オーバヘッド）はユーザのタスクまたはシェアのために使用可能なものではなく、したがって、ＡＴＯＤを前進するためにカウントするわけではない。各実行ＣＰＵは定期的にＡＴＯＤを増分し、待機中のＣＰＵは増分しない。これは、ステップ１２０および１２２でディスパッチャによって駆動される。ＡＴＯＤは、最後の増分以来、複数の実ＣＰＵによってどの程度のユーザ時間が供給されたかに応じて前進する。すなわち、各ＣＰＵは、そのＣＰＵの実際のユーザ実行時間アキュムレータ（ＰＦＸＵＴＩＭＥ）の前進に比例してＡＴＯＤを増分する。その意図（すべてのＣＰＵが生産的に動作している場合）は、ＡＴＯＤがほぼ実時間（壁掛け時計時間またはＴＯＤ）で前進することである。Ｎ個のすべてのＣＰＵが動作している場合、各ＣＰＵは一般にほぼ実時間でそれ自体のＰＦＸＵＴＩＭＥを前進している。したがって、以下のようにＮ個のＣＰＵによる寄与をＮで割る。
ＡＴＯＤ＝ＡＴＯＤ＋（ＰＦＸＵＴＩＭＥのデルタ）／Ｎ
【００７２】
式中、「ＰＦＸＵＴＩＭＥのデルタ」は、最後にそれが検査されてからこのＣＰＵのＰＦＸＵＴＩＭＥアキュムレータにおける変化である。
【００７３】
ＡＴＯＤ２は、以下のように各ＣＰＵのユーザ時間（ＰＦＸＵＴＩＭＥ）および各ＣＰＵの待機時間（ＰＦＸＴＯＴＷＴ）とを含む。
ＡＴＯＤ２＝ＡＴＯＤ２＋（ＰＦＸＵＴＩＭＥのデルタ＋ＰＦＸＴＯＴＷＴのデルタ）／Ｎ
【００７４】
式中、ＰＦＸＵＴＩＭＥおよびＰＦＸＴＯＴＷＴはどちらもＣＰＵタイマと同様のダブルワード・クロックである。
【００７５】
しかし、いずれかのＣＰＵが複数の連続間隔を待っている場合、他の実行ＣＰＵがそれに代わって動作し、ＡＴＯＤ２に対して（および何らかの状況ではＡＴＯＤに対しても）待ち時間の寄与をすることになる。このような待機ＣＰＵはその時間のすべてを待機状態で費やしており、待機状態の場合、ＡＴＯＤ２に対するその寄与は実時間（ＴＯＤクロックによって測定されたもの）の前進と同じでなければならないと想定する。しかし、待機ＣＰＵの実行時間については、いかなる想定または寄与も他のＣＰＵによってなされない。このような待機ＣＰＵがもう一度実行を開始すると、それは通常通りＡＴＯＤに対して、また実時間による最終的なおそらくわずかな間隔についてはＡＴＯＤ２に対して、寄与することになる。（他のＣＰＵは前の間隔を処理済みである。）
【００７６】
上記のように、１つまたは複数のＣＰＵが複数の連続タイム・スライス間隔を待っており、同時に現行ＣＰＵがその実行リスト内の作業（ＶＭＤＢＫ）を持っていない場合、ＡＴＯＤのために何らかの待ち時間がカウントされる。現行ＣＰＵがその実行リスト内に作業を持っていた場合、待機ＣＰＵがその作業を実行するために「使用可能」なものではない可能性があり、持っていなかった場合、たぶん、すでにその作業を実行しているものと思われる。逆に、現行ＣＰＵが実行リスト内にいずれの作業も持っていない場合、その待機時間が使用可能時間である場合と同様に待機ＣＰＵをカウントすることが本当に安全なことになるだろう。したがって、拡張待機モードの１つまたは複数のＣＰＵが存在し、同時に現行ＣＰＵがその実行リスト内にいずれの作業も持っていない場合、現行ＣＰＵは以前の式の代わりに以下の式を使用する。
ＡＴＯＤ＝ＡＴＯＤ＋（デルタ／Ｎ）＋（デルタ／Ｎ）＊ＴＲＫＣＴ／（Ｎ−ＴＲＫＣＴ）
【００７７】
式中、ＡＴＯＤ＝ＡＴＯＤ＋（デルタ／Ｎ）は、「デルタ」が「ＰＦＸＵＴＩＭＥのデルタ」の省略形である元の式を表し、「（デルタ／Ｎ）＊ＴＲＫＣＴ／（Ｎ−ＴＲＫＣＴ）」は、待機時間を反映するために追加される項であり、この場合も「デルタ」は「ＰＦＸＵＴＩＭＥのデルタ」の省略形である（また、「ＰＦＸＴＯＴＷＴのデルタ」ではない）。ＴＲＫＣＴはＳＲＭＴＲＫＣＴであり、現在依然として拡張待機モードになっているＣＰＵのカウントである。
【００７８】
待機ＣＰＵが（結局）それ自体の待機時間に対して寄与できた場合、その寄与は大きい固まりで到着するだろう。しかし、上記の式を使用すると、動作中のＣＰＵはそれ自体の（ＣＰＵベースの）寄与程度のサイズの待機ＣＰＵに代わって寄与する。したがって、第２項の寄与の基本サイズはデルタ／Ｎによって表され、複数の拡張待機モードＣＰＵに対して寄与するためにＳＲＭＴＲＫＣＴが掛けられる。しかし、動作中のもののように動作中のＣＰＵと同様に寄与することになる現行のもの（すなわち、拡張待機モードになっていないもの）のように他に多くのＣＰＵが存在するので、その結果を（Ｎ−ＳＲＭＴＲＫＣＴ）で割る。
【００７９】
ＳＲＭＴＯＤＳＶタイムスタンプは現行ＴＯＤの良好な近似値であるが、すべてのマイナー・タイム・スライスの終了（および他のスケジューリング・ポイント）時と、ＶＭＤＢＫが作動可能になった場合、すなわち、ほとんどの入出力動作後に、間欠的に更新されるだけである。ＳＲＭＴＯＤＳＶは、ＡＴＯＤを更新する時期であるかどうかを判断するために十分なほど正確であるが、その判断が行われると、より正確なＴＯＤ値が使用される。
【００８０】
上記のように、ＣＰＵの待機時間はいつでもＡＴＯＤに含まれるわけではない。というのは、本来、ＡＴＯＤはユーザより速く前進でき、前述の「疑わしい／疑わしくない」メカニズム（ユーザがディスパッチ・リスト内でどの程度の高さに位置することができるかを制限するよう機能する）はそれぞれのシェアにかかわらず、すべてのユーザを均一に前進させるものと思われるからである。にもかかわらず、ＡＴＯＤから待機時間を完全に除外すると、システムの複数のＣＰＵのうちの１つ（または少数）だけが動作し、残りのものが通常は待機している場合に問題が発生する。このような場合、ＡＴＯＤは実時間に比例して遅れ、前進しなくなる。それは、無制限ユーザおよびソフト限定ユーザまたは小さいシェアのハード限定ユーザの場合は問題にならないが、大きいシェアのハード限定ユーザの場合は顕著な矛盾を引き起こす恐れがある。これは、ＡＴＯＤとＴＯＤとの適度な差が重要ではないようなタイム・スライスを完了した後、小さいシェアのユーザがディスパッチ・リスト内で下に向かってこのように大きく踏み出すからである。しかし、大きいシェア（および対応する小さいオフセット）を備えたハード限定ユーザの場合、ＡＴＯＤの正確な動きが重要である。ＡＴＯＤは、そのユーザが非常に迅速にそれを超え、ＭＡＸＦＡＬＬ限界に達し、時期尚早に限界リストに掲載されないように、比較的速いペースで大きいＳＨＡＲＥを備えたユーザの後に続かなければならない。このような事態の発生が許されている場合、システムは、使用中のシステム上のハード限定ユーザがそのシェアを獲得するが、非使用中のシステム上では（特にそれが単独でそのシステム上に存在する場合）そのシェアより少ない量を獲得するだろうという望ましくない特性を示すだろう。これは、相当な待機時間があり、その待機時間が既存の作業のために「使用可能」であると証明できる場合にＡＴＯＤに待機時間（またはその一部）を含めることにより発生が防止される。上記のように、待機中のＣＰＵが存在し、現行ＣＰＵがその実行リスト内にいかなる作業も持っていない場合、待機時間の一部分がＡＴＯＤに含まれる。現行ＣＰＵは、待機中のＣＰＵに代わって待機時間に寄与する。
【００８１】
デヴィソンの同時係属特許出願第０８／２５２８６４号では、待機時間の過剰寄与がそれぞれのシェアを無視して「疑わしい／疑わしくない」メカニズムによってすべてのユーザを均一に前進させる恐れがあるので、有害なものになりうることが認識されている。寄与を現行ＣＰＵが使用しているＣＰＵ時間の量（ＰＦＸＵＴＩＭＥのデルタ）程度と等しいものにすることにより、それがカウントする場合、すなわち、ＣＰＵ制約の作業ならびにユーザが限界リストに掲載される見込みがある場合には完全な寄与がなされ、ＣＰＵがそれほど使用されていない場合にはより小さい寄与がなされることをデヴィソンは教示している。デヴィソンによって加えられた待機時間によるこのように「より小さい寄与」は、本発明によれば、後述するように、より一層頻繁に発生する諸事情により実質的に待機時間のすべてによって増大し、したがって、著しく良好な結果を達成する。
【００８２】
実行リストおよび限界リスト内のユーザは異なる速度で動作する様々なクロック（ＡＴＯＤおよびＡＴＯＤ２）によって時間的調節が行われるので、あるユーザが限界リスト２７内にまたは限界リスト２７外に移動するときに変換が行われる。あるユーザが限界リスト内にある間、そのユーザは、ディスパッチ・リスト優先順位（ＶＭＤＤＰＲＴＹ）３５と限界リスト優先順位（ＶＭＤＬＰＲＴＹ）２９という２通りの優先順位を有する。限界リスト優先順位はそのユーザのディスパッチ・リスト優先順位から導き出される。その意図は、ユーザが限界リスト２７内でその「遅延」を開始したときにユーザがＡＴＯＤ２３から持っているものと同じ程度のＡＴＯＤ２  ２１からの変位を持っていなければならないということである。その変位は、ユーザがもう一度実行する予定になる前に経過しなければならない遅延の量を表すが、（「待機時間」を完全にカウントできるようにするために）その遅延はＡＴＯＤ２クロックで測定する必要がある。したがって、その変換は以下の通りである。
ＶＭＤＬＰＲＴＹ＝ＡＴＯＤ２＋（ＶＭＤＤＰＲＴＹ−ＡＴＯＤ）
【００８３】
このＶＭＤＬＰＲＴＹの計算は、ユーザが限界リストに入ったときに行われる。ユーザが限界リストを離れるときは、ユーザは、そのユーザの締切りより１マイナー・タイム・スライス前に実行リストに入らなければならない。したがって、（定義により）ユーザが限界リストから実行リストに移動すると、ユーザのＶＭＤＤＰＲＴＹは（ＡＴＯＤ＋ＴＳ）に設定され、ユーザに通知し、ユーザを移動させる前に限界リストの締切りを超えるわずかな遅延について下記の補正が行われる。
ＶＭＤＤＰＲＴＹ＝（ＡＴＯＤ＋ＴＳ）−（（ＡＴＯＤ２＋ＴＳ）−ＶＭＤＬＰＲＴＹ）＝ＶＭＤＬＰＲＴＹ＋ＡＴＯＤ−ＡＴＯＤ２
【００８４】
図１に関連して図９を参照すると、ユーザが早すぎない時期に待機され、遅すぎない時期に待機から除去されるように、相対シェアおよび絶対シェア・ユーザ間で中央処理装置使用率をスケジューリングするために、本発明の方法の好ましい実施の形態を実現するための以下ステップともいうプログラミング要素の図解表現が示されている。これらのステップ間の関係は、必ずしも図９に示すように順次ではなく、表１に示す本発明の好ましい実施の形態の疑似コード表現に関連して以下に説明する。
【００８５】
中央処理装置または他のシステム・リソース２０の消費に関するユーザのシェアは絶対値に制限することができ、その値は正確な最大量２６、たとえば、ＣＰＵリソース２０の２０％である。この使用率における絶対値は、一般にこの用語に関連する数学的定義を指すのではなく、相対シェアおよび絶対シェアというＩＢＭのＶＭスケジューラ概念によるものである。たとえば、５人のユーザがそれぞれ１００という相対シェアで定義され、５人全員が活動状態である場合、スケジューラ４４はシステムＣＰＵリソース２０の１／５をそれぞれに与えようと試みる。そのうちの４人だけが活動状態である場合、スケジューラ４４はシステム・リソース２０の１／４をそれぞれに与えようと試みる。それぞれは、自分の優先順位と、その時点で活動状態のすべての相対シェア・ユーザの全優先順位とに基づいてシステムの相対シェアを獲得する。システムの絶対シェアも１人のユーザに与えることができる。たとえば、あるユーザには、システムの２０％という絶対シェアを与えることができる。これは、何人の相対シェア・ユーザが活動状態であっても、このユーザがシステム・リソースの２０％を獲得することを意味する。相対シェア・ユーザには残りの部分、この場合、ＣＰＵリソースの８０％の比例シェアが与えられる。
【００８６】
ステップ５０では、（ａ）ユーザ最小シェア割当て２４、（ｂ）ユーザが中央演算処理装置（ＣＰＵ）リソース２０を消費しているときに前進する第１の人工時刻クロック（ＡＴＯＤ）２３、（ｃ）高ディスパッチ優先順位限界（ＴＯＤ−ＴＩＥＤ）２８、（ｄ）低ディスパッチ優先順位限界（最大降下）１８によって定義される境界内で決定される値３５によって、プロセッサ使用率に関する優先順位がユーザに付けられる。
【００８７】
システム・リソースのシェアに関するユーザ限界は、指定の絶対または相対値としてシステム・ディレクトリに定義される。たとえば、ＶＭディレクトリは、システムに対してユーザを定義するために使用する。各ユーザごとに、システム・リソースのうち、相対シェアまたは絶対シェアのどちらのシェアをこのユーザが持つことができるかを指定するためにＳＨＡＲＥステートメント２４、２６を含むことができる項目が存在する。このシェアは、ＳＥＴ  ＳＨＡＲＥコマンドを使用することにより、システムが動作している間に動的に変更することもできる。
【００８８】
ユーザには「境界内で優先順位を付ける」ことによりシステム・リソースが与えられるが、これにより、その優先順位３５に基づいて、しかし、新たに計算した優先順位によってシステムに関するユーザのシェアがその定義済み最小シェア２８より低下するかまたはその定義済み最大シェア２６を超えない場合に限り、ＣＰＵリソース２０などのシステム・リソースがユーザに与えられることを意味する。たとえば、ＶＭスケジューラ４４の場合、ユーザは、最小相対または絶対シェア２４および最大相対または絶対シェア２６によって定義することができる。このような定義は、あるユーザに関するディスパッチ優先順位値３５を計算するときに考慮される境界を形成する。たとえば、あるユーザに２００という相対シェア２４と２０％という「リミットハード」絶対最大シェア２６が割り当てられ、このユーザと他の相対２００ユーザだけが活動状態である場合、「リミットハード」ユーザは、最大境界が指定されていない場合にそのユーザがシステムＣＰＵリソース２０の５０％を受け取れるとしても、２０％の最大境界２６内で優先順位が付けられることになる。
【００８９】
それに関する「ユーザ最小シェア」２４が定義されているユーザは、すべての活動ユーザの全相対シェアの一部分としてそのユーザの指定の相対シェアに基づいてシステム・リソースのシェアに対する資格を有する。ユーザ最小シェアは、そのユーザに関するＶＭディレクトリに指定され、残りのシェア（上記の通り）と同じように計算されるが、そのディレクトリからの指定の最小シェアを使用する。また、ユーザ最大シェアも同じ計算であるが、これはＶＭディレクトリ内のユーザの指定の最大シェア２６に基づくものである。
【００９０】
「人工時刻」（ＡＴＯＤ）２３は、システム全体の時刻クロック・フォーマット・フィールドである。特定のＣＰＵリソースは、同時に作業中（すなわち、消費中）と待機中の両方になることはできず、値ＡＴＯＤ２３は、システム・オーバヘッドとは区別されるように、そのユーザ（任意のユーザ）作業がシステム上で実行されている間に増加する。システムのディスパッチ優先順位計算は、ＡＴＯＤ値２３に基づき、それと比較される。「ＡＴＯＤ」２３および「ＡＴＯＤ２」２１はどちらも人工時刻クロックである。ＡＴＯＤまたはＡＴＯＤ２はどちらも実際のクロックではないが、ソフトウェアで管理されるフィールドであって、ＴＯＤクロック・フォーマットになっており、時間値が累積されるフィールドである。このソフトウェアはこれらのフィールドを適宜更新する。ＡＴＯＤ２は、システムが実際にユーザ作業を実行しているすべての時間とシステムが待機している時間を累積する。ＡＴＯＤはシステムが実際にユーザ作業を実行しているすべての時間を累積し、所与の状況では待機時間も累積する。したがって、ＡＴＯＤは実際には、ＡＴＯＤ２に累積される時間のサブセットの累積である。
【００９１】
（デヴィソンによる同時係属特許出願第０８／２５２８６４号の場合と同様に）待機時間によるＡＴＯＤの更新がディスパッチャ経路内のみではなく活動待機プロセスで発生することは、本発明の好ましい実施の形態の本質的な特徴である。以下に述べるように、通常のディスパッチャ経路（前述のように待機時間の小さい部分のみを加えるもの）内ではなく活動待機プロセス内のすべての待機時間によりＡＴＯＤを更新する理由は、活動待機が少なくともたとえば２５０ミリ秒であったことなど、ある種の状況で待機時間全体をＡＴＯＤに含めることが望ましいからである。したがって、一般にＡＴＯＤはユーザ作業時間を累積する。ほとんどのシステムではそのようになるだろう。しかし、何らかの待機時間がＡＴＯＤに含まれることになるような所与の状況が存在する。これまで、このような状況は極めて制限されてきたかまたはまれなことであり、ＡＴＯＤに含まれる待機時間の量はごくわずかであった。本発明によれば、より頻繁に発生する状況ではより多くの待機時間がＡＴＯＤの累積に含まれる。すなわち、低ロード状況中（活動待機ルーチン中）に、限定ユーザが存在し、中央処理装置がたとえば２５０ミリ秒またはそれ以上の間、連続的に活動待機になっていた場合である。
【００９２】
優先順位限界３５は「高ディスパッチ」値および「低ディスパッチ」値によって定義される。特定のユーザのディスパッチ優先順位３５が現行ＡＴＯＤ値２３から外れすぎないようにするため、スケジューラ４４はたとえば、現行ＡＴＯＤ２３とユーザの優先順位３５との差を高ディスパッチ優先順位限界（ＴＯＤ−ＴＩＥＤ）２８という最大値と低ディスパッチ優先順位限界（最大降下）１８に制限する。あるユーザのディスパッチ優先順位３５は、そのユーザに関する常軌を逸した応答時間を防止するために、このような限界の外側に設定されることはないだろう。
【００９３】
ステップ５２では、リソース２０の消費は、（ａ）選択されたユーザに割り当てられるユーザ最大限定シェア割当て２６を確立し、（ｂ）限界リスト２７を設け、（ｃ）ユーザがＣＰＵリソース２０を消費している場合およびＣＰＵが待機している場合に前進する第２の人工時刻クロック（ＡＴＯＤ２）２１を設けることにより、ユーザのために境界１８、２８内の指定の絶対値に制限される。
【００９４】
限界リストは、リソースに関するその消費がシステム・ディレクトリ内のそのＳＨＡＲＥステートメント２４、２６によってまたはＳＥＴ  ＳＨＡＲＥコマンドにより許される最大絶対シェアに達するかまたはそれを超えたユーザのリスト２７である。このリスト２７上にある間、ユーザはスケジューラ４４によってディスパッチされず、したがって、そのリソース２０の消費は制限される。ユーザは最大絶対シェアまたは最大相対シェアによって指定することができ、これらのうちのいずれか一方はリミットハードにすることができる。いずれかのタイプの最大シェア（絶対または相対）を備えたリミットハード・ユーザは、限界リスト上に置くことによって制限することができる。また、リミットハード機能とは異なる働きをするリミットソフト機能も存在する。リミットソフト・ユーザは、限界リスト上に置くことによって制限されることはない。
【００９５】
本発明によれば、リミットハード・ユーザが早すぎない時期に限界リストに掲載され、遅すぎない時期に限界リストから除去されることを保証するために、あるユーザが限定ユーザであり、しかもそのディスパッチ優先順位が最大降下（現行ＡＴＯＤ＋Ｎ＊オフセット）を超える新しいディスパッチ優先順位に再計算され、しかもそのユーザがその限界に達した場合に、そのユーザは限界リストに加えられる。ＡＴＯＤ２があるユーザの限界リスト優先順位の１つのマイナー・タイム・スライス内になるように計算された場合に、そのユーザは限界リストから除去されるが、ただし、Ｎは何らかの事前選択値であり、一例としてＮ＝４である。
【００９６】
ステップ５４では、そのユーザの限界リスト２７の優先順位が決定され、第２の人工時刻クロック（ＡＴＯＤ２）２１の前進に基づいて限界リストからユーザを除去すべきかどうかも決定される。
【００９７】
ステップ５６では、ＣＰＵがアイドルであるときに、着信タスク３２の活動待機連続モニタ３０が用意される。この「活動待機ルーチン」または「活動待機メカニズム」は、マルチプロセッシング・システムで使用される方法であり、それにより実行すべき作業を持たないプロセスがループし、使用不可能の待機状態をロードするのではなく使用可能になる作業を活動的に探す。これは、作業をスタックするプロセッサからその作業がスタックされているプロセッサに作業がその上にスタックされていることを認識しなければならないという負担からプロセッサを解放するものである。
【００９８】
ステップ５８では、ディレクトリ内のそのシェア定義２６によって制限されるユーザにとって使用可能なＣＰＵリソースの最大シェアである最大使用率シェア２６に基づいてユーザに優先順位が割り当てられる。そのユーザのみに使用可能なシステムのシェアに基づいてスケジューラ４４が優先順位を割り当てる時期があり、それが限定シェア・ユーザであるために使用可能なシェアがユーザに許されているものより大きくなる時期がある。ユーザが（限界リスト２７内に存在することにより）制限され、使用可能なシェアがユーザに許されているシェア２６より大きくなる場合、「最大使用率シェア」２６を使用してそのユーザのディスパッチ優先順位３５を計算する。
【００９９】
ステップ６０では、そのユーザのディスパッチ優先順位３５について計算された新しい値分だけ低ディスパッチ優先順位限界（最大降下）１８を超える場合、ユーザは限界リスト２７に掲載される。ディスパッチ優先順位３５は１人のユーザについて様々な時期に計算される。あるユーザを限界リスト２７に掲載すべきかどうかを判定するための検査は、そのユーザのディスパッチ優先順位３５が再計算されるときに行われる。
【０１００】
ステップ６２では、限界リスト上の存続持続時間２９はＡＴＯＤ２３およびＡＴＯＤ２  ２１を参照することによって決定される。あるユーザのディスパッチ優先順位３５が計算される場合、それはある事象が今後発生するときのＡＴＯＤ２３の値の予測であり、その事象はユーザのマイナー・タイム・スライスの終了になる。ＡＴＯＤ２３のこの予測値はユーザのディスパッチ優先順位３５として使用される。そのユーザを限界リスト２７上に掲載しなければならないと判定された場合、そのユーザをリストから除去するための基礎として、ＡＴＯＤ２３ではなくＡＴＯＤ２  ２１を使用する。その場合、ＡＴＯＤ２３に基づくそのユーザのディスパッチ優先順位は、ＡＴＯＤ２  ２１から離れて基礎としなければならない限界リスト優先順位３５（限界リスト２７から離れるべき予測時間）に変更しなければならない。これを行うために使用する計算は、限界リスト優先順位＝ＡＴＯＤ２＋（ディスパッチ優先順位−ＡＴＯＤ）である。
【０１０１】
ステップ６４では、限界シェア・ユーザがＣＰＵを求めて競合する時期が決定される。
【０１０２】
ステップ６６では、中央演算処理装置（ＣＰＵ）などのシステム・リソースが連続的に、定義された実時間間隔の間、活動待機状況（割込みなしに動作中、すなわち、いずれのユーザ作業３２の検出も実行もなし）になっていた時期が決定される。この決定は、活動待機状態に入ったときに実システムＴＯＤクロックの値を保管し、それを現行ＴＯＤ値と比較することによって行われる。
【０１０３】
ステップ６８では、ＡＴＯＤ２３が増分され、ＡＴＯＤ２  ２１が更新される。
【０１０４】
本発明の好ましい実施の形態によれば、ＡＴＯＤ２３のこの増分は活動待機プロセス３０中に行われる。活動待機コードのループを通るたびに、限界リスト２７上にユーザが存在するかどうかを判定するための検査が行われる。存在し、活動待機プロセス３０が指定の時間間隔（たとえば、２．５ミリ秒）の間、連続的に実行中であった場合、最後にＡＴＯＤ２３が更新されてから活動待機で経過した時間の全量分だけ、ＡＴＯＤ２３値が増加する。したがって、システムが低ロード状態（新しい作業が一切使用可能にならずに、少なくとも２５０ミリ秒の間、活動待機になっているプロセッサによって定義される）になっており、限界リスト上に限定ユーザが存在する場合、待機時間間隔全体がＡＴＯＤ２３に追加される。
【０１０５】
ＡＴＯＤ２  ２１のこの更新もディスパッチャへのその呼出しにより活動待機プロセス３０中に行われる。活動待機３０コードのループを通るたびに、限界リスト２７上にユーザが存在するかどうかを判定するための検査が行われる。存在し、活動待機プロセス３０が指定の時間間隔（たとえば、２．５ミリ秒）の間、連続的に実行中であった場合、活動待機ルーチンがディスパッチャを呼び出し、それが最後にＡＴＯＤ２  ２１が更新されてから活動待機で経過した時間の量だけ、ＡＴＯＤ２  ２１の値を増加する。低ロード状態にあるときに活動待機処理中にＡＴＯＤ２を更新するためにディスパッチャを呼び出すことにより、限界リストからユーザを除去する必要性についてより頻繁に検査が行われる。
【０１０６】
ステップ７０では、ＡＴＯＤ２値２１が限界リスト優先順位３５の１マイナー・タイム・スライス内にあり、ＣＰＵの連続的活動待機状況時間がＡＴＯＤ２  ２１に含まれる場合に、ユーザが限界リスト２７から除去される。
【０１０７】
したがって、本発明の好ましい実施の形態によれば、ＣＰＵ待機時間をＡＴＯＤ２３に追加すると、ユーザが低ロード（アイドルＣＰＵ）状況で時期尚早に限界リスト２７に掲載されないことが保証され、活動待機ルーチンからディスパッチャへの呼出しにより限界リスト２７からユーザを除去するかどうかの検査の細分性が増加するので限界リスト存続に関するより良い精度が得られる。このようにして、ユーザを除去すべきかどうかについて限界リスト２７を検査する時期と次にそれを検査する時期との間隔のサイズが低減される。時間間隔が小さくなるということは、細分性が増加することを意味する。
【０１０８】
限界リスト２７は、ユーザがそれに許されているもの（２６）より多くのＣＰＵリソース２０を受け取るときにそのユーザを抑えるために使用する。このような事態が発生する場合、ユーザは一時的に限界リスト２７に掲載される。スケジューラ４４は、そのユーザを限界リスト２７から取り除く時期であるかどうかを判定するために検査を行う。これらの検査は、限界リストからの「除去の検査」と呼ばれるものである。この「検査」は事象主導型である。本発明以前は、限界リストはこのユーザ作業をスケジューリングしディスパッチするプロセス中に活動プロセッサ（実行すべきユーザ作業を備えたもの）によって検査されていた。本発明によれば、活動待機メカニズムでもこれらの検査が行われる。
【０１０９】
表１は、本発明の好ましい実施の形態の方法の疑似コード説明を示している。この疑似コードは、括弧［］内の図２の諸ステップへの参照で注釈が付けられている。表１に関連して図１を参照すると、ディスパッチャ４０（ＨＣＰＤＳＰＣＨという）は行２から始まるディスパッチャ・ループによって実現され、モニタ３０は行１８から始まる活動待機ルーチンによって実現され、スケジューラ４４は行３６から始まるスケジュール優先順位再計算コードによって実現される。行２０には、実行すべき新しい作業が存在し、たとえば、着信タスク３２は空ではない。行２５では、２５０ミリ秒への参照を他のシステムの適切な事前選択時間値に合わせることができるだろう。行１１と行２７の両方では、最後に待機時間が追加されてからの待機時間がＡＴＯＤに追加され、行３２のディスパッチャへの呼出しにより、ＡＴＯＤ２にも追加される。ディスパッチャを呼び出すことにより待機ルーチン中に待機時間が追加される理由は本発明にとって重要なことである。以前は、行１１の処理が行われるまで、待機時間は決してＡＴＯＤ２に追加されなかった。低ロード状況では、その処理が行われるまでかなりの時間がある可能性がある。この結果、これまでは限界リスト２７上のユーザが非常に長い間そこに存続していた。本発明では、低ロード状況では待機時間のより小さい増分がより頻繁に追加され、同時に限界リストが検査され、それに値するユーザがそうすべきときに限界リストから除去される。表１の行３５は図１の線８２によって表されるが、これは、活動待機連続モニタ３０が待機時間をＡＴＯＤに追加するときに活動待機連続モニタ３０がディスパッチャ４０に移行してＡＴＯＤ２を更新するという追加の意味を有する。表１の行５０に記載されている新しい優先順位は、そのユーザがもう一度ディスパッチされる時期を決定するために使用するそのユーザの再計算ディスパッチ（すなわち、締切り）優先順位である。このディスパッチ優先順位は、最大降下およびＴＯＤ−ＴＩＥＤという限界によって制限される。スケジューラ４４は行５８のこの優先順位を使用して、そのユーザを優先順位順にディスパッチ・リスト３７に掲載する。表１の行５４に示す式内の数字「４」は経験的に定義された最適数を表し、本発明の範囲から逸脱せずに変更できるはずである。表１の行６１では、そのユーザは、その新たに再計算されたディスパッチ・リスト優先順位３５に基づいてディスパッチ・リスト３７上で再順序付けが行われる。
【表１】
0003606555.tif 000002
【表２】
0003606555.tif 000003
【表３】
0003606555.tif 000004
【０１１０】
従来技術を超える利点
本発明の１つの利点は、低ロード状況でそのハード限界に極めて近いかまたは等しいシステム・リソースへのユーザ・アクセスの許可を容易にするためのスケジューラ・システムおよび方法が提供されることである。
【０１１１】
本発明の他の利点は、システム・リソースに関する最適請求を容易にし、請求の総額またはこのようなリソースの可用性に対するユーザの不快感を低減する、改良されたスケジューラが提供されることである。
【０１１２】
本発明の他の利点は、ユーザの優先順位を決定し、どのユーザが次に実行できるかを決定するためにシステムが使用するスケジューリング・アルゴリズムへのフィードバック・メカニズムとしてモニタ・データが使用される、システムおよび方法が提供されることである。
【０１１３】
本発明の他の利点は、限定アクセス権を有するユーザを早すぎない時期に限界リストに掲載し、遅すぎない時期に限界リストから除去することにより、このようなユーザに対してシステム・リソースをスケジューリングするためのシステムおよび方法が提供されることである。
【０１１４】
本発明の他の利点は、遅すぎない時期にリソースのスケジューリングを可能にし、早すぎない時期にリソースのスケジューリングを禁止することにより、限定アクセス権を有するユーザに対してシステム・リソースをスケジューリングするためのシステムおよび方法が提供されることである。
【０１１５】
代替実施の形態
例示のために本発明の具体的な実施の形態についてここで説明してきたが、本発明の精神および範囲から逸脱せずに様々な変更が可能であることが分かるだろう。特に、本発明の方法によりコンピュータの動作を制御するためにマシンによって読取り可能な信号を記憶するための固体または流体伝送媒体、磁気または光学ワイヤ、テープ、ディスクなどのプログラム記憶装置またはメモリ・デバイスを提供することまたは本発明のシステムによりその構成要素を構築することあるいはその両方は、本発明の範囲内である。
【０１１６】
さらに、この方法の各ステップは、ＩＢＭのシステム３９０、ＡＳ／４００、ＰＣなどの汎用コンピュータのいずれでも、Ｃ＋＋、Ｊａｖａ、Ｐｌ／１、Ｆｏｒｔｒａｎなどのいずれかのプログラミング言語から生成されたプログラム・モジュールまたはオブジェクトの１つまたは複数あるいは１つまたは複数のうちの一部により実行することができる。さらに、前記各ステップまたは前記各ステップを実現するファイルまたはオブジェクトなどは、そのために設計された専用ハードウェアまたは回路モジュールによって実行することができる。
【０１１７】
まとめとして、本発明の構成に関して以下の事項を開示する。
【０１１８】
（１）ユーザによるシステム・リソースの使用をスケジューリングする方法であって、
第１のクロックを維持するステップと、
第２のクロックを維持するステップと、
ディスパッチ・プロセス中に
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングするステップと、
それ以外の場合に、
ユーザ時間分だけ前記第１のクロックを進めるステップと、
ユーザ時間および待機時間分だけ前記第２のクロックを進めるステップと、
待機プロセス中に
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出すステップと、
それ以外の場合に待機時間の時間的調節を行うステップと、
前記待機時間が所定の値を超過したときに待機状況にあるユーザが存在する場合、前記待機時間分だけ前記第１のクロックを増分し、前記ディスパッチ・プロセスを呼び出すステップを
含む方法。
（２）スケジューラ・プロセス中に
前記ユーザのユーザ・シェアを決定するステップと、
前記ユーザ・シェアが所定の最大許容シェアを超過した場合、前記ユーザ・シェアと、前のタイム・スライス上のオーバランに応じて調整されたタイム・スライスとに基づいてユーザ・オフセットを計算するステップと、
前記ユーザ・オフセットを加えた現行ディスパッチ優先順位に等しい前記ユーザの新しいディスパッチ優先順位を計算するステップと、
前記新しいディスパッチ優先順位が前記ユーザ・オフセットの関数分だけ前記第１のクロックを超過した場合、前記ユーザを待機状況にして前記ディスパッチ・プロセスを呼び出し、それ以外の場合に前記ディスパッチ・プロセスを呼び出すステップと、
前記ディスパッチ・プロセス中に、前記ユーザがタイム・スライスを完了したときに、前記スケジューラ・プロセスを呼び出すステップを
さらに含む上記（１）に記載の方法。
（３）さらに前記ディスパッチ・プロセス中に
前記ユーザが前記第２のクロックの１つのタイム・スライス内の限界優先順位で待機状況になっている場合、限界状況から前記ユーザを除去するステップを
さらに含む上記（２）に記載の方法。
（４）複数の限定ユーザ間でシステム・リソースの使用をスケジューリングする方法であって、
第１の時刻クロックを維持するステップと、
第２の時刻クロックを維持するステップと、
ディスパッチ・ルーチンを実行するステップと、
活動待機ルーチンを実行するステップと、
優先順位再計算ルーチンを実行するステップを
含み、
前記優先順位再計算ルーチンが
第１のユーザのユーザ・シェアを計算するステップと、
前記ユーザ・シェアが所定の最大許容シェアを超過した場合、前記ユーザ・シェアと、前のマイナー・タイム・スライス上のオーバランに応じて調整されたマイナー・タイム・スライスのサイズとに基づいてユーザ・オフセットを計算するステップと、
前記ユーザ・オフセットを加えた古い優先順位に等しいユーザ・ディスパッチ優先順位を計算するステップと、
前記ユーザ・ディスパッチ優先順位が前記ユーザ・オフセットの関数を加えた前記第１のクロックに等しい最大降下値を超過し、これが限定ユーザであり、このユーザがその最大シェアでスケジューリングされる場合、前記ユーザを限界リストに追加するステップと、
それ以外の場合に前記ユーザをディスパッチ・リスト上に優先順位順に再順序付けするステップと、
前記ディスパッチャ・ルーチンを実行するステップを
含み、
前記ディスパッチャ・ルーチンが
ディスパッチすべき作業がない場合、前記活動待機ルーチンを実行し、それ以外の場合にいずれかの優先順位システム作業を実行するステップと、
前記ユーザのマイナー・タイム・スライスが終了したばかりの場合、前記スケジューラ・ルーチンを実行するステップと、
それ以外の場合にユーザ時間によって前記第１の時刻クロックを進めるステップと、
ユーザ時間および待機時間によって第２の時刻クロックを進めるステップと、
前記限界リスト上のユーザが前記第２の時刻クロックの１つのマイナー・タイム・スライス内にある場合、前記限界リストから前記ユーザを除去するステップと、
ディスパッチ・リスト優先順位に基づいてユーザをディスパッチするステップを
含み、
前記活動待機ルーチンが
実行すべき新しい作業がある場合、前記ディスパッチャ・ルーチンを実行するステップと、
それ以外の場合に前記限界リスト上にユーザが存在し、活動待機処理が所定の限界を超過した場合、
前記第１の時刻クロックに待機時間を追加するステップと、
前記ディスパッチャ・ルーチンを実行するステップを
含み、
それにより、ユーザが早すぎない時期に前記限界リストに追加され、遅すぎない時期に前記限界リストから除去される方法。
（５）システム・リソースをスケジューリングする方法において、
（１）（ａ）ユーザ最小シェア割当て、（ｂ）ユーザがシステム・リソースを消費しているときに前進する第１の人工時刻クロック、（ｃ）高ディスパッチ優先順位限界、（ｄ）低ディスパッチ優先順位限界によって定義される境界内でプロセッサ使用率に関する優先順位をユーザに付けるステップと、
（２）（ａ）選択されたユーザに割り当てられるユーザ最大限定シェア割当てを確立し、（ｂ）限界リストを設け、（ｃ）ユーザがシステム・リソースを消費している場合および前記システム・リソースが待機している場合に前進する第２の人工時刻クロックを設けることにより、ユーザによる中央演算処理装置の消費を前記境界内の指定の絶対値に制限するステップと、
（３）限界リスト優先順序を決定し、前記第２の人工時刻クロックの前進に基づいて前記限界リストから除去すべき時期を決定するステップと、
（４）前記ＣＰＵがアイドルであるときに、着信タスクの活動待機対話式連続モニタを用意するステップと、
（５）最大使用率シェアに基づいてユーザに優先順位を割り当てるステップと、
（６）前記低ディスパッチ優先順位限界を超過したときに、前記限界リストにユーザを掲載するステップと、
（７）前記限界リスト上の存続持続時間を決定するために前記第１の人工時刻クロックの時間を前記第２の人工時刻クロックの時間に変換するステップと、
（８）限界シェア・ユーザがＣＰＵリソースを求めて競合する時期を認識するステップと、
（９）前記システム・リソースが定義された実時間間隔の間、連続活動待機状況になっていた時期を認識し、それに対する応答として、前記第１の人工時刻クロックおよび前記第２の人工時刻クロックを待機時間分だけ更新するステップと、
（１０）それに関する前記第２の人工時刻クロック値が低ロード条件下で前記第２の人工時刻クロックに含まれる前記待機時間の実質的にすべてによって前記限界リスト優先順位を超過するユーザを前記限界リストから除去するステップを
含む方法。
（６）ユーザによるシステム・リソースの使用をスケジューリングするための方法ステップを実行するためにマシンによって実行可能な命令からなるプログラムを具体的に実施する、マシンによって読取り可能なプログラム記憶装置において、前記方法ステップが、
第１のクロックを維持することと、
第２のクロックを維持することと、
ディスパッチ・プロセス中に
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングすることと、
それ以外の場合にユーザ時間分だけ前記第１のクロックを前進することと、
ユーザ時間および待機時間分だけ前記第２のクロックを前進することと、
待機プロセス中に
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出すことと、
それ以外の場合に待機時間の時間的調節を行うことと、
前記待機時間が所定の値を超過したときに待機状況にあるユーザが存在する場合、前記待機時間分だけ前記第１のクロックを増分し、前記ディスパッチ・プロセスを呼び出すこととを含む、プログラム記憶装置。
（７）ユーザによるシステム・リソースの使用をスケジューリングするためにそこで実施されるコンピュータ可読プログラム・コード手段を有するコンピュータ使用可能媒体を含む製品において、前記製品における前記コンピュータ可読プログラム手段が、
第１のクロックを維持することをコンピュータに実施させるためのコンピュータ可読プログラム・コード手段と、
第２のクロックを維持することをコンピュータに実施させるためのコンピュータ可読プログラム・コード手段と、
ディスパッチ・プロセス中に
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングすることと、
それ以外の場合にユーザ時間分だけ前記第１のクロックを前進することと、ユーザ時間および待機時間分だけ前記第２のクロックを前進することをコンピュータに実施させるためのコンピュータ可読プログラム・コード手段と、
待機プロセス中に
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出すことと、
それ以外の場合に待機時間の時間的調節を行うことと、
前記待機時間が所定の値を超過したときに待機状況にあるユーザが存在する場合、前記待機時間分だけ前記第１のクロックを増分し、前記ディスパッチ・プロセスを呼び出すことをコンピュータに実施させるためのコンピュータ可読プログラム・コード手段とを含む製品。
（８）ユーザによるシステム・リソースの使用をスケジューリングするためのシステムにおいて、
第１のクロックと、
第２のクロックと、
ディスパッチ・プロセスであって
実行すべき作業がある場合、前記ユーザが待機状況になっていないときのみ、他のユーザとともにディスパッチ優先順位順に前記ユーザに対してシステム・リソースの使用をスケジューリングし、
それ以外の場合にユーザ時間分だけ前記第１のクロックを前進し、
ユーザ時間および待機時間分だけ前記第２のクロックを前進するためのディスパッチ・プロセスと、
待機プロセスであって
実行すべき作業がある場合、前記ディスパッチ・プロセスを呼び出し、
それ以外の場合に待機時間の時間的調節を行い、
前記待機時間が所定の値を超過したときに待機状況にあるユーザが存在する場合、前記待機時間分だけ前記第１のクロックを増分し、前記ディスパッチ・プロセスを呼び出すための待機プロセスとを含むシステム。
（９）スケジューラ・プロセスであって
前記ユーザのユーザ・シェアを決定し、
前記ユーザ・シェアが所定の最大許容シェアを超過した場合、前記ユーザ・シェアと、前のタイム・スライス上のオーバランに応じて調整されたタイム・スライスとに基づいてユーザ・オフセットを計算し、
前記ユーザ・オフセットを加えた現行ディスパッチ優先順位に等しい前記ユーザの新しいディスパッチ優先順位を計算し、
前記新しいディスパッチ優先順位が前記ユーザ・オフセットの関数分だけ前記第１のクロックを超過した場合、前記ユーザを待機状況にして前記ディスパッチ・プロセスを呼び出し、それ以外の場合に前記ディスパッチ・プロセスを呼び出すためのスケジューラ・プロセスと、
前記ユーザがタイム・スライスを完了したときに、前記スケジューラ・プロセスを呼び出す前記ディスパッチ・プロセスをさらに含む、上記（８）に記載のシステム。
（１０）前記ディスパッチ・プロセスであって
前記ユーザが前記第２のクロックの１つのタイム・スライス内の限界優先順位で待機状況になっている場合、限界状況から前記ユーザを除去するための前記ディスパッチ・プロセスをさらに含む、上記（９）に記載のシステム。
【図面の簡単な説明】
【図１】本発明の好ましい実施の形態を実現する方法およびデータ構造のシステム図である。
【図２】コンピュータ・オペレーティング・システムの流れ図である。
【図３】ディスパッチャの流れ図の関係を示す図である。
【図４】ディスパッチャの流れ図である。
【図５】ディスパッチャの流れ図である。
【図６】ディスパッチャの流れ図である。
【図７】図２のオペレーティング・システム内のスケジューラの（小さい部分の）流れ図である。
【図８】ディスパッチ・リストを示す図である。
【図９】本発明の方法の好ましい実施の形態を実現するプログラミング・モジュールの図解表現である。
【符号の説明】
１８  最大降下
２０  システム・リソース
２１  ＡＴＯＤ２
２２  実時間クロック
２３  ＡＴＯＤ
２４  ユーザ最小シェア割当て
２５  オフセット
２６  ユーザ最大シェア割当て
２７  限界リスト
２８  ＴＯＤ−ＴＩＥＤ
２９  限界リスト上の存続時間（限界リスト優先順位）
３０  活動待機連続モニタ
３２  着信タスク
３５  ユーザのディスパッチ・リスト優先順位
３７  ディスパッチ・リスト
４０  ディスパッチャ
４４  スケジューラ
【図１】
0003606555.tif 000005
【図２】
0003606555.tif 000006
【図３】
0003606555.tif 000007
【図４】
0003606555.tif 000008
【図５】
0003606555.tif 000009
【図６】
0003606555.tif 000010
【図７】
0003606555.tif 000011
【図８】
0003606555.tif 000012
【図９】
0003606555.tif 000013