(57)【要約】      （修正有）【課題】プロセッサキャッピング有効の仮想計算機がビジーで、他にアイドルの仮想計算機が存在する場合に、偏りの無いスケジュールとプロセッサキャッピングの両方を実現する。【解決手段】物理計算機全体の持ちプロセッサ時間から前記プロセッサキャッピング有効仮想計算機に与えられる持ちプロセッサ時間を差し引いた時間を持ちプロセッサ時間とする補仮想計算機を生成し、各仮想計算機が単位時間に物理プロセッサを使用したプロセッサ時間を求め、各仮想計算機及び前記補仮想計算機の持ちプロセッサ時間と前記求められた使用プロセッサ時間に基づいて各仮想計算機及び前記補仮想計算機のスケジュール優先度を求め、前記プロセッサキャッピング有効仮想計算機のスケジュール優先度が前記補仮想計算機のスケジュール優先度より大きい場合には前記プロセッサキャッピング有効仮想計算機の有する仮想プロセッサのスケジュールは行わない。【選択図】図８
2008186210.tif 000002
【特許請求の範囲】
【請求項１】
仮想計算機モニタが、1以上の物理プロセッサを有する物理計算機を時分割して１以上の仮想プロセッサを有する複数の仮想計算機を構築し、スケジュール優先度に基づき前記仮想計算機及び該仮想計算機の有する仮想プロセッサのスケジュールを制御する仮想計算機システムにおいて、前記仮想計算機モニタが各仮想計算機のプロセッサ利用率を指定された比率以下に制限するプロセッサキャッピング方法であって、プロセッサキャッピングが有効な仮想計算機に対して、物理計算機全体の持ちプロセッサ時間から前記プロセッサキャッピング有効仮想計算機に与えられる持ちプロセッサ時間を差し引いた時間を持ちプロセッサ時間とする補仮想計算機を生成し、各仮想計算機が単位時間に物理プロセッサを使用したプロセッサ時間を求め、各仮想計算機及び前記補仮想計算機の持ちプロセッサ時間と前記求められた使用プロセッサ時間に基づいて各仮想計算機及び前記補仮想計算機のスケジュール優先度を求め、前記プロセッサキャッピング有効仮想計算機のスケジュール優先度と該プロセッサキャッピング有効仮想計算機に対応する補仮想計算機のスケジュール優先度とを比較し、前記プロセッサキャッピング有効仮想計算機のスケジュール優先度が前記補仮想計算機のスケジュール優先度より大きい場合には前記プロセッサキャッピング有効仮想計算機の有する仮想プロセッサのスケジュールは行わないことを特徴とする仮想計算機システムのプロセッサキャッピング方法。
【請求項２】
前記プロセッサキャッピング有効仮想計算機のスケジュール優先度が前記補仮想計算機のスケジュール優先度以下の場合には前記プロセッサキャッピング有効仮想計算機のスケジュール優先度と他の仮想計算機のスケジュール優先度とを比較し、前記プロセッサキャッピング有効仮想計算機のスケジュール優先度が最小の場合に該プロセッサキャッピング有効仮想計算機の有する仮想プロセッサのスケジュールを行うことを特徴とする請求項１記載の仮想計算機システムのプロセッサキャッピング方法。
【請求項３】
１以上の物理プロセッサを有する物理計算機上で、仮想計算機モニタがスケジュール優先度に基づき、仮想計算機及び該仮想計算機の有する１以上の仮想プロセッサのスケジュールを制御する仮想計算機システムにおいて、仮想計算機モニタが、仮想計算機のプロセッサ利用率を、指定された比率以下に制限するプロセッサキャッピング方式であって、
物理計算機の持ちプロセッサ時間Ｕ、仮想計算機の持ちプロセッサ時間Ｑ、物理計算機の物理プロセッサ数Ｎ、物理計算機の経過時間Ｔ、及び仮想計算機の使用プロセッサ時間Ｒから成り、
仮想計算機モニタは、仮想計算機の持ちプロセッサ時間Ｑを、物理計算機の持ちプロセッサ時間Ｕを分母とし、該仮想計算機の持ちプロセッサ時間Ｑを分子とした分数Ｑ／Ｕが、該仮想計算機に対して指定したプロセッサ利用率Ａと等しくなるように与え、すなわちＱ／Ｕ＝Ａとなるようにし、仮想計算機のスケジュール優先度を、該仮想計算機の持ちプロセッサ時間Ｑを分母とし、使用プロセッサ時間Ｒを分子とした分数Ｒ／Ｑと求め、対応する補仮想計算機のスケジュール優先度を、物理計算機の持ちプロセッサ時間Ｕから該仮想計算機の持ちプロセッサ時間Ｑを引いた値Ｕ−Ｑを分母とし、物理計算機の経過時間Ｔに物理プロセッサ数Ｎを乗じたその時点の物理計算機の使用プロセッサ時間Ｔ×Ｎから、該仮想計算機の使用プロセッサ時間Ｒを引いた値Ｔ×Ｎ−Ｒを分子とした分数（Ｔ×Ｎ−Ｒ）／（Ｕ−Ｑ）と求め、仮想計算機のスケジュール優先度Ｒ／Ｑが、補仮想計算機のスケジュール優先度（Ｔ×Ｎ−Ｒ）／（Ｕ−Ｑ）以下の場合、すなわち
Ｒ／Ｑ ≦ （Ｔ×Ｎ−Ｒ）／（Ｕ−Ｑ）
を満たす場合に限り、該仮想計算機の有する仮想プロセッサを物理プロセッサにスケジュールすることを認めることで、プロセッサキャッピング対象の仮想計算機及び物理計算機の情報のみを使い、該仮想計算機のプロセッサ利用率 Ｒ／（Ｔ×Ｎ）がユーザの指定した比率Ａを超えない範囲で、該仮想計算機のスケジュールを偏り無く行うことを特徴とする仮想計算機システムのプロセッサキャッピング方法。
【請求項４】
仮想計算機モニタは、アイドルプロセスを物理プロセッサごとに有し、ある時点において、実行可能な仮想プロセッサを有する仮想計算機の全てが、請求項３記載の条件式（Ｔ×Ｎ−Ｒ）／（Ｕ−Ｑ）を満たさずに、プロセッサキャッピングを課せられている状態であるならば、前記の状態を検出した物理プロセッサは、該物理プロセッサ上のアイドルプロセスを、物理時間が経過し、少なくとも１つの仮想計算機が前記の条件式を満たすようになるまで、実行させ続けることを特徴とする請求項３記載の仮想計算機システムのプロセッサキャッピング方法
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想計算機システムに係わり、特に仮想計算機モニタが、スケジュール優先度に基づき、仮想計算機及び該仮想計算機の有する仮想プロセッサのスケジュールを制御する方法に関する。
【背景技術】
【０００２】
複数プロセッサ構成の物理計算機が標準で使われるようになり、また技術の発展によりプロセッサの高多重化も進んできている。今後、複数プロセッサ構成の物理計算機を用いる仮想計算機システム、更には複数の仮想プロセッサ構成の仮想計算機を構築する仮想計算機システムの重要性が増すと予測される。
【０００３】
仮想計算機システムには、物理計算機の物理プロセッサを有効に使うためのサービス率制御という機能を備えたものがある。サービス率とは、仮想計算機ごとにユーザが指定する値であり、仮想計算機に割り当てられる物理プロセッササービス量を表す。
【０００４】
サービス率の指定は、全ての仮想計算機の全ての仮想プロセッサが、アイドルになることなく、物理プロセッサを割り当てられると、常に与えられたタイムスライス時間を使い切ることができる状態にある場合に、仮想計算機の間のプロセッサ使用率の比率がサービス率の比率に等しくなるようにすることを要求する。
仮想計算機モニタは、この要求を満たすように、仮想計算機の仮想プロセッサを物理プロセッサにスケジュールする。
【０００５】
一方、仮想計算機システムの仮想計算機モニタは、指定サービス率に従いプロセッササービス量を与えても、それを使い切るだけの負荷を持たない仮想計算機がある場合には、余ったプロセッササービス量を、プロセッササービス量の足りない仮想計算機に与えることで、仮想計算機システムとしてのプロセッサ利用効率を向上させる。
【０００６】
前記は、仮想計算機システムとしてのプロセッサ利用効率を向上させるが、各々の仮想計算機の視点では、指定サービス率に従い与えられるプロセッササービス量と、実際に必要とするプロセッササービス量には不一致がある。また、1つの仮想計算機をとっても、仮想計算機が必要とするプロセッササービス量は一定とは限らず、時間帯によって異なる場合がある。
仮想計算機のユーザには、必要なプロセッササービス量に対して費用を支払うという契約を結んで、仮想計算機を使用したいというユーザもいる。
このようなユーザに対しては、仮想計算機に与えるプロセッササービス量を、契約した比率以下に制限する必要がある。プロセッササービス率を制限する機能にプロセッサキャッピングがある。
サービス率及びプロセッサキャッピングが、下記特許文献１で報告されている。下記特許では、長期の実時間（分または時間のオーダ）において仮想計算機のプロセッサ利用率を指定した比率に抑える、大域的なプロセッサキャッピング方法が記載されている。
【０００７】
【特許文献１】特許第３５４３４４１号
【発明の開示】
【発明が解決しようとする課題】
【０００８】
全ての仮想計算機がビジーである場合には、プロセッサキャッピング有効の仮想計算機のプロセッサ利用率は、サービス率制御によって、自然とサービス率で指定された比率以下に制限され(実際には指定した比率と等しくなり)、また、サービス率制御の提供する偏りの無いスケジュールも守られる。
【０００９】
これに対して、プロセッサキャッピング有効の仮想計算機がビジーで、他の仮想計算機の中にアイドルの仮想計算機が存在するならば、明示的にプロセッサキャッピング処理を行わないと、プロセッサキャッピング有効の仮想計算機のプロセッサ利用率が、サービス率で指定した比率を超えてしまう。
【００１０】
従来の仮想計算機システムでは、プロセッサキャッピング有効の仮想計算機の使用プロセッサ時間が該仮想計算機の持ちプロセッサ時間を超えないように、該仮想計算機の物理プロセッサへのスケジュールを制限することで、プロセッサキャッピングを実現していた。
単位プロセッサ時間は、タイムスライスと比べて十分に大きな値とするので、プロセッサキャッピングを有効にした仮想計算機は、例えば他の全ての仮想計算機がアイドル状態で、該仮想計算機がビジー状態であるならば、仮想計算機モニタは、該仮想計算機の仮想プロセッサを物理プロセッサに連続してスケジュールするので、該仮想計算機の使用プロセッサ時間が直ちに該仮想計算機の持ちプロセッサ時間に達し、プロセッサキャッピングの制限がかかり、使用プロセッサ時間がリセットされるまで該仮想計算機の物理計算機へのスケジュールが行われなくなり、プロセッサキャッピング有効の仮想計算機のスケジュールには大きな偏りができるという問題があった。
これでは、システム応答性の面で問題があり、特に長い待ち時間を認めず、偏りの無いスケジュールを要求するプログラムには、プロセッサキャッピングを使用することができなかった。
【００１１】
本発明の目的は、単に仮想計算機の使用プロセッサ時間が持ちプロセッサ時間を超えないことに制限を課すのではなく、時間の経過に沿って仮想計算機の使用プロセッサ時間の増加率に制限を課すことで、アイドルの仮想計算機が存在する場合であっても、プロセッサキャッピング有効の仮想計算機の物理プロセッサへのスケジュールを、該仮想計算機のプロセッサ利用率がユーザの指定したサービス率を超えない範囲で偏り無く行うことである。
【００１２】
また、本発明は、対象の仮想計算機の情報と物理計算機全体の情報のみを使用することで、処理時間が、仮想計算機システムに構築した仮想計算機及び該仮想計算機の有する仮想プロセッサ数の数に依らないプロセッサキャッピング方法を実現することも目的とする。
【課題を解決するための手段】
【００１３】
本発明は、仮想計算機モニタが各仮想計算機のプロセッサ利用率を指定された比率以下に制限するプロセッサキャッピング方法であって、プロセッサキャッピングが有効な仮想計算機に対して、物理計算機全体の持ちプロセッサ時間から前記プロセッサキャッピング有効仮想計算機に与えられる持ちプロセッサ時間を差し引いた時間を持ちプロセッサ時間とする補仮想計算機を生成し、各仮想計算機が単位時間に物理プロセッサを使用したプロセッサ時間を求め、各仮想計算機及び前記補仮想計算機の持ちプロセッサ時間と前記求められた使用プロセッサ時間に基づいて各仮想計算機及び前記補仮想計算機のスケジュール優先度を求め、前記プロセッサキャッピング有効仮想計算機のスケジュール優先度と該プロセッサキャッピング有効仮想計算機に対応する補仮想計算機のスケジュール優先度とを比較し、前記プロセッサキャッピング有効仮想計算機のスケジュール優先度が前記補仮想計算機のスケジュール優先度より大きい場合には前記プロセッサキャッピング有効仮想計算機の有する仮想プロセッサのスケジュールは行わないことを特徴とする仮想計算機システムのプロセッサキャッピング方法である。
【発明の効果】
【００１４】
本発明によれば、プロセッサキャッピング有効の仮想計算機がビジーで、他にアイドルの仮想計算機が存在する場合に、偏りの無いスケジュールとプロセッサキャッピングの両方を実現することができる。
【００１５】
また、本発明のプロセッサキャッピング制御は、対象の仮想計算機及び物理計算機全体の情報のみを使用する為、仮想計算機システムの有する仮想計算機及び該仮想計算機の仮想プロセッサの数に、処理時間が依存しない方式で、プロセッサキャッピングを実現することができる。
【発明を実施するための最良の形態】
【００１６】
本発明を適用した一実施形態を、図面を用いて詳細に説明する。
【００１７】
図１は、本発明を適用した仮想計算機システムの概要を示す構成図である。
物理計算機００１は、物理プロセッサ０ ００２ａ、物理プロセッサ１ ００２ｂ、システム時刻００６、及び物理プロセッサ０ ００２ａと物理プロセッサ１ ００２ｂにそれぞれタイマ００４ａとタイマ００４ｂを有する。
本実施形態においては、物理プロセッサの数を２つとしているが、本発明は物理プロセッサの数を限定するものではなく、１つまたはそれ以上の任意の数の物理プロセッサを有する物理計算機に適用可能である。
【００１８】
システム時刻００６は、仮想計算機モニタ１００が物理プロセッサ時間を測定する為に参照する、全ての物理プロセッサの間の共通時刻であり、物理計算機００１単独で、あるいは物理計算機００１と仮想計算機モニタ１００で連携し、常に全ての物理プロセッサの間で同期することを保証する。本発明は、システム時刻００６の実現方法は問わない。
タイマ００４ａとタイマ００４ｂは、指定した時刻に外部割り込みを発生させる機能を有し、仮想計算機モニタ１００が、タイムスライスによって物理プロセッサ０ ００２ａと物理プロセッサ１ ００２ｂを時分割共有する為に、及び時分割共有におけるプロセッサ利用率の制御を、ある時間間隔で区切って周期的に行う為に使用する。
【００１９】
仮想計算機モニタ１００は、物理プロセッサ０ ００２ａと物理プロセッサ１ ００２ｂを時分割共有して、仮想プロセッサ０ ３０２ａ、仮想プロセッサ１ ３０２ｂ、及び仮想プロセッサ２ ３０２ｃの計３つの仮想プロセッサを有する仮想計算機１ ３００、仮想プロセッサ０ ３１２ａと仮想プロセッサ１ ３１２ｂの計２つの仮想プロセッサを有する仮想計算機２ ３１０、及び仮想プロセッサ０ ３２２ａの１つの仮想プロセッサを有する仮想計算機３ ３２０を構築する。
【００２０】
本実施形態においては、プロセッサキャッピング方法は、仮想プロセッサ単位ではなく、仮想計算機単位で考える為、仮想計算機の仮想プロセッサの数には依存しない。また、本発明のプロセッサキャッピング方法は、1つまたはそれ以上の任意の数の仮想プロセッサを有する仮想計算機に適用可能である。また、仮想計算機の仮想プロセッサの数は、物理プロセッサの数よりも大きくても構わない。
【００２１】
仮想計算機モニタ１００は、物理プロセッサ０ ００２ａと物理プロセッサ１ ００２ｂにアイドルプロセス０ ４００ａとアイドルプロセス１ ４００ｂをそれぞれ対応付け、物理プロセッサ上でスケジュールする仮想プロセッサが見つからなかったときに、該物理プロセッサ上にスケジュールすることができる仮想プロセッサが見つかるまで、該物理プロセッサ上で対応するアイドルプロセスを実行させる。
【００２２】
本発明の仮想計算機システムのプロセッサキャッピング方式は、サービス率の理論に基づくものである。サービス率とは、仮想計算機ごとにユーザが指定する値であり、仮想計算機に割り当てられる物理プロセッサ資源の大きさを表す。サービス率が要求するのは、全ての仮想計算機の全ての仮想プロセッサがアイドルになることなく、物理プロセッサを割り当てられると、常に与えられたタイムスライス時間を使い切ることができる状態にある場合に、仮想計算機の間のプロセッサ利用率の比率を、サービス率の比率と等しくすることである。
【００２３】
本実施形態においては、サービス率の機能を持つ仮想計算機システムに、プロセッサキャッピング機能を追加することにより実現する、仮想計算機システムのプロセッサキャッピング方式の形態を説明する。
【００２４】
図２は、本実施形態における、仮想計算機モニタ１００の概要を示すブロック図である。
仮想計算機モニタ１００が有するブロックは、物理プロセッサ、仮想計算機、及び仮想計算機の仮想プロセッサの区分に分類される。
【００２５】
仮想計算機モニタ１００は、物理プロセッサに対して、物理プロセッサテーブル１１０を有する。物理プロセッサテーブル１１０は、単位プロセッサ時間 Ｅ １１２、物理プロセッサ数 Ｎ １１４、及び各単位プロセッサ時間の開始時刻 Ｔ０ １１６、物理計算機１００の持ちプロセッサ時間 Ｕ １１８を含む。
【００２６】
次に仮想計算機モニタ１００は、仮想計算機に対して、仮想計算機ごとの、仮想計算機テーブル１ １２０、仮想計算機テーブル２ １３０、及び仮想計算機テーブル３ １４０を有する。
又仮想計算機モニタ１００は、仮想計算機ごとにプロセッサキャッピング有効・無効の指定を保持するプロセッサキャッピングフラグ１ ２００、プロセッサキャッピングフラグ２ ２０２、プロセッサキャッピングフラグ３ ２０４を有する。更に、仮想計算機がプロセッサキャッピング有効の場合のみ使用する、補仮想計算機テーブル１ ２１０、補仮想計算機テーブル２ ２２０、及び補仮想計算機テーブル３ ２３０を有する。
【００２７】
仮想計算機モニタ１００は、サービス率制御において、全ての仮想計算機の仮想計算機テーブルを使用する。仮想計算機モニタ１００は、本発明のプロセッサキャッピング制御において、対象のプロセッサキャッピング有効の仮想計算機の仮想計算機テーブルと、該仮想計算機の補仮想計算機テーブルを使用する。
【００２８】
仮想計算機１ ３００の仮想計算機テーブル１２０は、サービス率Ｓ１ １２２、仮想計算機の持ちプロセッサ時間Ｑ１ １２４と使用プロセッサ時間Ｒ１ １２６、仮想計算機１ ３００のスケジュール優先度Ｐ１ １２８、及び実行可能な仮想プロセッサのみを格納する仮想計算機レディキュー１ １５０を含む。仮想計算機２ ３１０の仮想計算機テーブル２ １３０と仮想計算機３ ３２０の仮想計算機テーブル３ １４０も同様である。
【００２９】
仮想計算機１ ３００のプロセッサキャッピングフラグ１ ２００は、該仮想計算機に対して、プロセッサキャッピング制御を有効にするか否かを判定する為に使用する。仮想計算機２ ３１０のプロセッサキャッピングフラグ２ ２０２と仮想計算機３ ３２０のプロセッサキャッピングフラグ３ ２０４も同様である。
【００３０】
仮想計算機１ ３００がプロセッサキャッピング有効であるならば、補仮想計算機という概念に対応した、補仮想計算機テーブル１ ２１０を使用する。
補仮想計算機テーブル１ ２１０は、サービス率を除いて前記の仮想計算機テーブル１ １２０と同様に、持ちプロセッサ時間Ｇ１ ２１２、使用プロセッサ時間Ｈ１ ２１４、及びスケジュール優先度Ｃ１ ２１６を有する。仮想計算機２ ３１０と仮想計算機３ ３２０も同様にプロセッサキャッピング有効であるならば、それぞれ補仮想計算機テーブル２ ２２０と補仮想計算機テーブル３ ２３０を使用する。また、補仮想計算機テーブル２ ２２０と３ ２３０は、補仮想計算機テーブル１ ２１０と同様の構成である。補仮想計算機テーブルについては、本発明のプロセッサキャッピング方法の実現方法のところで、詳しく説明する。
【００３１】
仮想プロセッサの仮想プロセッサテーブル１６０ａ、１６０ｂ、１６０ｃ、１７０ａ、１７０ｂ、１８０ａは、対応付けられた仮想プロセッサのスケジュール開始時刻 ｔ０をそれぞれ含む。
【００３２】
以上の図２記載の情報を使って、本実施形態で採用するサービス率の１つの実現方式では、どのようにしてサービス率指定の要求が満たされるのかを説明する。
【００３３】
まず、仮想計算機モニタ１００がサービス率指定の要求を満たす為に使用する情報の計算方法を説明する。
【００３４】
物理計算機の持ちプロセッサ時間は次のようにして求める。
物理計算機００１の物理プロセッサ００２ａと００２ｂを単位プロセッサ時間Ｅ １１２で時分割し、物理計算機００１の持ちプロセッサ時間Ｕ １１８を、単位プロセッサ時間Ｅ １１２と物理プロセッサ数Ｎ １１４を乗じて、（式１）のように求める。
【００３５】
Ｕ ＝ Ｅ × Ｎ  （式１）
物理計算機００１の持ちプロセッサ時間Ｕ １１８は、物理計算機００１の有する物理プロセッサ資源の大きさを表す。単位プロセッサ時間Ｅ １１２は、タイムスライスよりも十分大きな適切な値とする。ある1つの実現形態においては、単位プロセッサ時間Ｅ １１２は１秒としている。
【００３６】
各仮想計算機の持ちプロセッサ時間は次のようにして求める。
（式１）で求めた物理計算機００１の持ちプロセッサ時間Ｕ １１８を、全ての仮想計算機の間で、サービス率で指定された比率で分割し、仮想計算機１ ３００の持ちプロセッサ時間Ｑ１ １２４、仮想計算機２ ３２０の持ちプロセッサ時間Ｑ２ １３４、及び仮想計算機３ ３３０の持ちプロセッサ時間Ｑ３ １４４を求める。
各仮想計算機の持ちプロセッサ時間Ｑ１ １２４、持ちプロセッサ時間Ｑ２ １３４、及び持ちプロセッサ時間Ｑ３ １４４は、それぞれ仮想計算機に割り当てられた物理プロセッサ資源の大きさを表す。
【００３７】
図３は、物理計算機１００の持ちプロセッサ時間Ｕ １１８を、仮想計算機１ ３００のサービス率Ｓ１ １２２、仮想計算機２ ３１０のサービス率Ｓ２ １３２、仮想計算機３ ３２０のサービス率Ｓ３ １４２の比率に従って分割し、それぞれの仮想計算機の持ちプロセッサ時間Ｑ１ １２４、持ちプロセッサ時間Ｑ２ １３４、持ちプロセッサ時間Ｑ３ １４４を求めたイメージを示す図である。サービス率は仮想計算機単位で考える為、仮想計算機が有する仮想プロセッサの数は問わない。
物理計算機００１の持ちプロセッサ時間Ｕ １１８を、仮想計算機のサービス率Ｓ１ １２２、仮想計算機２ ３１０のサービス率Ｓ２ １３２、仮想計算機３ ３２０のサービス率Ｓ３ １４２の比率で分割し、それぞれの仮想計算機に持ちプロセッサ時間Ｑ１ １２４、持ちプロセッサ時間Ｑ２ １３４、持ちプロセッサ時間Ｑ３ １４４を与える、すなわち、次の（式２）と（式３）のようにする。
【００３８】
Ｓ１ ： Ｓ２ ： Ｓ３ ＝ Ｑ１ ： Ｑ２ ： Ｑ３    （式２）
Ｕ ＝ Ｑ１ ＋ Ｑ２ ＋ Ｑ３    （式３）
一方、仮想計算機の使用プロセッサ時間Ｒは以下のようにして求める。
仮想計算機モニタ１００は、仮想プロセッサをスケジュールする度に、該仮想プロセッサのスケジュール終了時に、仮想プロセッサテーブルに保持する仮想プロセッサのスケジュール開始時刻と、スケジュール終了時のシステム時刻を使って、仮想プロセッサの使用プロセッサ時間を求め、該仮想プロセッサが属する仮想計算機の仮想計算機テーブルにある使用プロセッサ時間Ｒに加算する。
【００３９】
図４に仮想プロセッサの使用プロセッサ時間Ｒの更新処理のフローチャートを示す。仮想計算機１ ３００の仮想プロセッサ０ ３０２ａを例とする。
仮想プロセッサ０ ３０２ａのスケジュールを開始するときに、その時点のシステム時刻を該仮想プロセッサの仮想プロセッサテーブル０ １６０ａのスケジュール開始時刻 ｔ０として保持し、該仮想プロセッサのスケジュールを終了するときに、その時点のシステム時刻 ｔ１から、仮想プロセッサテーブル０ １６０ａに保存したスケジュール開始時刻 ｔ０を引くことで、該仮想プロセッサの使用プロセッサ時間ｔ１−ｔ０を求める。
【００４０】
仮想プロセッサの使用プロセッサ時間Ｒは、該仮想プロセッサのスケジュールの度に、そのときの使用プロセッサ時間として求められる一方、仮想計算機の使用プロセッサ時間Ｒは、該仮想計算機の有する仮想プロセッサのスケジュールの度の加算と、単位プロセッサ時間Ｅ １１２の間隔でのリセットを繰り返す。
【００４１】
図５に仮想計算機の使用プロセッサ時間の更新処理のイメージを示す。求めた仮想プロセッサの使用プロセッサ時間ｔ１−ｔ０を該仮想プロセッサが属する仮想計算機１ ３００の使用プロセッサ時間Ｒ１ １２６に加算する。
【００４２】
また、全ての仮想計算機１ ３００使用プロセッサ時間 Ｒ１ １２６、仮想計算機２ ３１０の使用プロセッサ時間Ｒ２、及び仮想計算機３の使用プロセッサ時間Ｒ３は全て、単位プロセッサ時間Ｅ １１２の時間間隔で周期的にリセットされる。
【００４３】
仮想計算機モニタ１００は、仮想計算機の持ちプロセッサ時間と使用プロセッサ時間を用いて、以下のようにして、仮想計算機のスケジュール優先度を求める。
仮想計算機モニタ１００は、例えば仮想計算機１ ３００のスケジュール優先度Ｐ１ １２８を、仮想計算機１ ３００の持ちプロセッサ時間Ｑ１ １２４を分母、使用プロセッサ時間Ｒ１ １２６を分子とした分数、すなわち（式４）と求める。
【００４４】
Ｐ１ ＝ Ｒ１／Ｑ１    （式４）
仮想計算機２ ３２０のスケジュール優先度Ｐ２と仮想計算機３ ３３０のスケジュール優先度Ｐ３も全く同様にして求めることができる。
【００４５】
仮想計算機モニタ１００は（式４）で求めた仮想計算機のスケジュール優先度に従い、仮想計算機１ ３００、仮想計算機２ ３１０、及び仮想計算機３ ３２０を物理プロセッサ０  ００２ａと物理プロセッサ１ ００２ｂにスケジュールし続けることで、サービス率Ｓ１ １２２、サービス率Ｓ２ １３２、及びサービス率Ｓ３ １３４の要求を満たす。
【００４６】
仮想計算機モニタ１００は常に、スケジュール可能な仮想プロセッサを有する全ての仮想計算機の中で、仮想計算機のスケジュール優先度Ｐが最小の仮想計算機の仮想プロセッサを、該仮想計算機のレディキューから取り出して、物理プロセッサにスケジュールすることで、
全ての仮想計算機の全ての仮想プロセッサがアイドルになることなく、物理プロセッサを割り当てられると、常に与えられたタイムスライス時間を使い切ることができる状態にある場合に、仮想計算機の間のプロセッサ利用率の比率を、サービス率の比率と等しくするという、サービス率の要求を満たすことができる。
【００４７】
図６は、仮想計算機モニタ１００の、スケジュール対象仮想計算機の選択処理のアルゴリズムのフローチャートを示す。プロセッサキャッピング制御は含まない。
【００４８】
仮想計算機モニタ１００は図６のフローチャートで示すアルゴリズムにおいて、仮想計算機のスケジュール優先度Ｐの他に、一時変数として、ｆｏｒループで使用し仮想計算機番号を表すｉ、仮想計算機のスケジュール優先度Ｐは、その値が小さいほど優先度は高いので、その最小値を保持するＭＩＮＰＲＩＯ、及びＭＩＮＰＲＩＯの値のスケジュール優先度を有する仮想計算機番号、すなわちスケジュール対象の仮想計算機番号を保持するＳＣＨＥＤＶＭを使用する。
【００４９】
まず、最初にＭＩＮＰＲＩＯを無効な値、具体的にはスケジュール優先度Ｐがとり得ない十分に大きな値で初期化する。また、ＳＣＨＥＤＶＭを存在しない仮想計算機番号０で初期化する。
そして、スケジュール優先度Ｐが最小の仮想計算機番号を取得するｆｏｒループを開始する。ｆｏｒループは、ｉ＝１からｉを１ずつ増加させながらｉが最大仮想計算機番号と等しくなるまでとする。
ｆｏｒループ内の処理を説明する。
まず、仮想計算機ｉのスケジュール優先度Ｐｉを取得する。次に、Ｐｉの値が、一時変数ＭＩＮＰＲＩＯ未満であるならば、ＭＩＮＰＲＩＯにＰｉの値を代入し、ＳＣＨＥＤＶＭにｉを代入する。
Ｐｉの値が一時変数ＭＩＮＰＲＩＯ以上であるならば何もしない。
ｆｏｒループを抜けると、スケジュール対象の仮想計算機番号が一時変数ＳＣＨＥＤＶＭに格納されている。
もし、ＳＣＨＥＤＶＭの値が非０であるならば、スケジュール対象の仮想計算機が見つかったことを意味する。仮想計算機モニタ１００は、ＳＣＨＥＤＶＭの番号の仮想計算機のレディキューから仮想プロセッサを取り出して、物理プロセッサにスケジュールする。
ところが、もしＳＣＨＥＤＶＭの値が０であるならば、これはスケジュールする仮想計算機が見つからなかったことを意味する。このときは、仮想計算機モニタ１００はアイドルプロセスを物理プロセッサにスケジュールする。
【００５０】
図６のアルゴリズムにより、サービス率の要求が満たされる理由を説明する。
【００５１】
仮想計算機ｉのスケジュール優先度Ｐｉは、該仮想計算機ｉの仮想プロセッサが実行されるにつれて増加する。
仮想計算機モニタ１００が、スケジュール優先度Ｐｉが最小の仮想計算機をスケジュールし続けることは、常に全ての仮想計算機のスケジュール優先度Ｐｉを等しくなるように作用する。
図２に示す3つの仮想計算機、仮想計算機１ ３００、仮想計算機２ ３１０、及び仮想計算機３ ３２０のスケジュール優先度Ｓ１ １２２、スケジュール優先度Ｓ２、及びスケジュール優先度Ｓ３が等しいことは、次の式（式５）が満たされることを意味する。
【００５２】
Ｐ１ ＝ Ｐ２ ＝ Ｐ３    −＞    Ｒ１／Ｑ１ ＝ Ｒ２／Ｑ２ ＝ Ｒ３／Ｑ３    （式５）
（式５）の右側の等式を変換すると、以下の比例式（式６）が導かれる。
【００５３】
Ｒ１ ： Ｒ２ ： Ｒ３ ＝ Ｑ１ ： Ｑ２ ： Ｑ３    （式６）
一方、仮想計算機１ ３００、仮想計算機２ ３１０、及び仮想計算機３ ３２０の持ち時間Ｑ１ １２４、Ｑ２、Ｑ３はその比率がサービス率Ｓ１ １２２、Ｓ２、Ｓ３の比率と等しくなるように定める。すなわち、以下の比例式（式７）が成り立つ。
【００５４】
Ｑ１ ： Ｑ２ ： Ｑ３ ＝ Ｓ１ ： Ｓ２ ： Ｓ３    （式７）
この2つの式（式６）と（式７）から、
Ｒ１ ： Ｒ２ ： Ｒ３ ＝ Ｓ１ ： Ｓ２ ： Ｓ３    （式８）
が導かれる。
【００５５】
更に、仮想計算機の使用プロセッサ時間Ｒ１ １２６、Ｒ２、Ｒ３は、単位プロセッサ時間Ｅ １１２の時間間隔で周期的にリセットされるので、例えばある時点において、仮想計算機１ ３００の使用プロセッサ時間Ｒ１ １２６に対する物理的な経過時間と、仮想計算機２ ３１０の使用プロセッサ時間Ｒ２に対する物理的な経過時間は等しい。
これは、ある時間区間の開始時刻をＴｓ、終了時刻をＴｅとし、ＴｓからＴｅまでの仮想計算機１ ３００、仮想計算機２ ３１０、及び仮想計算機３ ３２０の使用プロセッサ時間をそれぞれ ΔＲ１、ΔＲ２、及びΔＲ３とすると、次式（式９）が成り立つことを意味する。
【００５６】
ΔＲ１／（Ｔｅ−Ｔｓ） ： ΔＲ２／（Ｔｅ−Ｔｓ） ： ΔＲ３／（Ｔｅ−Ｔｓ） ＝ Ｓ１ ： Ｓ２ ： Ｓ３    （式９）
が成り立つことを意味する。ここで、ΔＲ１／（Ｔｅ−Ｔｓ）、ΔＲ２／（Ｔｅ−Ｔｓ）、及びΔＲ３／（Ｔｅ−Ｔｓ）は、それぞれ時間区間Ｔｅ−Ｔｓにおける、仮想計算機１ ３００、仮想計算機２ ３１０、及び仮想計算機３ ３２０のプロセッサ利用率を表す。
【００５７】
Ｔｓおよび  Ｔｅは任意の値とすることができるので、図６に示したアルゴリズムにより、任意の時間区間で、サービス率の要求が満たされる。
【００５８】
次に、本発明の仮想計算機システムのプロセッサキャッピング方法を説明する。
【００５９】
上述のように、アイドルの仮想計算機が存在する場合は、ビジーの仮想計算機のプロセッサ利用率が、サービス率で指定した比率を超えてしまうので、ビジーの仮想計算機をプロセッサキャッピング有効にする場合は、該仮想計算機のプロセッサ利用率を、明示的にサービス率で指定した比率以下に制限する手段を適用する必要がある。
本発明の仮想計算機システムのプロセッサキャッピング方法は、サービス率の理論を採用することで実現する。
【００６０】
サービス率がある特定の条件の下で保証するのは、仮想計算機のプロセッサ利用率が、サービス率の比率に等しくなるということである。
プロセッサキャッピングが満たさなければならない、仮想計算機のプロセッサ利用率をサービス率の比率以下に制限するという条件は、仮想計算機のプロセッサ利用率をサービス率の比率に等しくするということを含む。
プロセッサキャッピング有効の仮想計算機が、指定されたサービス率の比率を超えるプロセッサ利用率を必要とする負荷を有する場合には、該仮想計算機は、サービス率の比率と等しいプロセッサ利用率で、偏り無く均一に物理プロセッサを利用できることが望ましい。
【００６１】
サービス率が要求する上記の特定の条件とは、全ての仮想計算機の全ての仮想プロセッサがアイドルになることなく、物理プロセッサを割り当てられると、常に与えられたタイムスライス時間を使い切ることができる状態である。
プロセッサキャッピングを明示的に課す必要がある場合に、この特定の条件を作り出すことができれば、後は上記のサービス率のアルゴリズムを使うことで、望ましいプロセッサキャッピングが実現できる。
【００６２】
一方、プロセッサキャッピング有効の仮想計算機の負荷が、サービス率の比率ほどのプロセッサ利用率を必要としない場合には、該仮想計算機のプロセッサ利用率が、サービス率の比率を越えることは無い。
プロセッサキャッピング方法は、この場合には、サービス率制御の動作を妨げないものである必要がある。本発明のプロセッサキャッピング方法が、これを満たすことは実施例の中で具体的に説明する。
【００６３】
以下に、本実施形態における、仮想計算機システムのプロセッサキャッピング方法の実現方式を説明する。
【００６４】
まず、プロセッサキャッピング有効の対象の仮想計算機は、サービス率で指定された比率以上のプロセッサ利用率を必要とする負荷を有し、他の仮想計算機の負荷は、サービス率で指定された比率程のプロセッサ利用率を必要としないと仮定する。
【００６５】
このとき、仮想計算機モニタが、サービス率の理論を使って、プロセッサキャッピング有効の対象の仮想計算機のプロセッサ利用率をサービス率で指定された比率と等しくする為には、（式５）で示す関係を成立させる必要がある。
ところが、該仮想計算機の他の仮想計算機は負荷が低いので、仮想計算機の間のサービス率制御では、（式５）に示す関係は成立しない。
【００６６】
ここで都合のよいことに、（式５）に示す関係を成立させる為には、仮想計算機は少なくとも2つ存在すればよい。
そこで、プロセッサキャッピング有効の仮想計算機に対しては、仮想計算機の間のサービス率制御では（式５）に示す関係が成立しない場合に、常に（式５）に示す関係を成立させるように、仮想計算機モニタのスケジュールアルゴリズムが動作するような、概念的な仮想計算機を擬似的に生成する。
【００６７】
この概念的な仮想計算機の満たさなければならない要求は、プロセッサキャッピング有効の仮想計算機との間で、物理計算機の持ちプロセッサ時間の全てが、指定された比率で分割されるようにすること、前記の物理計算機の持ちプロセッサ時間の分割により、持ちプロセッサ時間を与えられると、該持ちプロセッサ時間を使い切るだけの負荷をもつことである。
【００６８】
前者の要求は、プロセッサキャッピング有効の仮想計算機と概念的な仮想計算機の持ちプロセッサ時間の和が、物理計算機の持ちプロセッサ時間と等しくすることで満たすことができる。
これは、物理計算機の持ちプロセッサ時間から、プロセッサキャッピング有効の仮想計算機の持ちプロセッサ時間を引いた余りのプロセッサ時間を、概念的な仮想計算機の持ちプロセッサ時間とすることで実現できる。
【００６９】
後者の要求は、プロセッサキャッピング有効の仮想計算機と概念的な仮想計算機がともにビジーになれば、すなわちスケジュールのアルゴリズムから見て、アイドルのプロセッサ時間が存在しなければ、満たされる。
スケジュールのアルゴリズムから見て、アイドルのプロセッサ時間が存在しないということは、プロセッサキャッピング有効の仮想計算機と概念的な仮想計算機の使用プロセッサ時間の和が単位プロセッサ時間の開始時刻からの経過時間に物理プロセッサ数を乗じた値と等しいということに置き換えられる。
【００７０】
これは、概念的な仮想計算機の使用プロセッサ時間を、単位プロセッサ時間の開始時刻からの経過時間に物理プロセッサ数を乗じた値から、プロセッサキャッピング有効の仮想計算機の使用プロセッサ時間を引いた値とすることで、実現することができる。
【００７１】
上記の2つの要求に対する実現方式は、共に全体から対象を引いた残りを使うという考え方に基づいている。全体集合Ｕから集合Ｑを引いた残りの部分をＱの補集合と呼ぶことから、この残りの情報で擬似的に実現する概念的な仮想計算機を補仮想計算機と定義する。プロセッサキャッピング無効の仮想計算機に対しては、この補仮想計算機の概念は意味を持たない。
【００７２】
補仮想計算機がサービス率の理論に基づき、プロセッサキャッピングの役割を果たす為には、通常の仮想計算機と同様に、持ちプロセッサ時間と使用プロセッサ時間を有する必要がある。この要求を具体化したのが、図２に示す補仮想計算機テーブル２１０、２２０、２３０である。
【００７３】
仮想計算機１ ３００の補仮想計算機テーブル１  ２１０を例に取り上げる。補仮想計算機テーブル１ １２０は、持ちプロセッサ時間Ｇ１ ２１２、使用プロセッサ時間Ｈ１ ２１４、及びスケジュール優先度Ｃ１ ２１６を有する。仮想計算機２ ３１０と仮想計算機３ ３２０についても全く同様である。
【００７４】
仮想計算機１ ３００がプロセッサキャッピング有効であると仮定し、仮想計算機１ ３００、仮想計算機１ ３００に対応する補仮想計算機１の持ちプロセッサ時間と使用プロセッサ時間の関係を図７に示す。
【００７５】
仮想計算機１ ３００に対応する補仮想計算機１の持ちプロセッサ時間Ｇ１ ２１２は、物理計算機の持ちプロセッサ時間Ｕ １１８から該仮想計算機の持ちプロセッサ時間Ｑ１ １２４を引くことにより、(式１０)のように求めた値とする。
【００７６】
Ｇ１ ＝ Ｕ−Ｑ１    （式１０）
次に、該補仮想計算機１の使用プロセッサ時間Ｈ１ ２１４は、物理計算機００１の使用プロセッサ時間、その時点のシステム時刻Ｔ１から、単位プロセッサ時間の開始時刻Ｔ０ １１６を引いた値（T１−T０）に物理プロセッサ数Ｎ １１４を乗じた（T１− T０）ｘＮから、対応する仮想計算機の使用プロセッサ時間Ｒ１ １２６を引くことにより、（式１１）のように求めた値とする。
【００７７】
Ｈ１ ＝ （Ｔ１−Ｔ０）×Ｎ−Ｒ１    （式１１）
（式１１）から分かるように、補仮想計算機１の使用プロセッサ時間H１ ２１４は、対応する仮想計算機１ ３００以外が使用したプロセッサ時間の合計を意味する。
そして補仮想計算機 １のスケジュール優先度Ｃ１を対応する仮想計算機のスケジュール優先度Ｐ１と同様に、（式１２）のように求める。
【００７８】
Ｃ１ ＝ Ｈ１／Ｇ１    （式１２）
補仮想計算機１の持ちプロセッサ時間 G１ ２１２、使用プロセッサ時間Ｈ１ ２１４、及びスケジュール優先度Ｃ１ ２１６は全て、対応する仮想計算機１ ３００の情報と物理計算機１００全体の情報のみから求められる。計算は単純であり、また計算時間は仮想計算機システムが有する仮想計算機の数、その他の仮想計算機の持ちプロセッサ時間、使用プロセッサ時間には依存しない。
【００７９】
仮想計算機モニタ１００は、プロセッサキャッピング有効の仮想計算機１ ３００がビジーで、残りの仮想計算機２ ３１０と仮想計算機３ ３２０がアイドルである場合には、仮想計算機１ ３００のスケジュール優先度Ｐ１ １２８と対応する補仮想計算機１のスケジュール優先度Ｃ１ ２１６を比較し、小さい値をとる仮想計算機をスケジュールする。
仮想計算機１ ３００をスケジュールすることは、仮想計算機１の有する、ある仮想プロセッサをスケジュールすることを意味する。
しかし、補仮想計算機１をスケジュールすることは、補仮想計算機１の仮想プロセッサをスケジュールすることは意味しない。なぜなら補仮想計算機１は仮想プロセッサを有しない概念であるからである。
正確には、仮想計算機１ ３００の仮想プロセッサをスケジュールしないことを意味する。仮想計算機モニタ１００が、ある物理プロセッサ上で、その他にスケジュール可能な仮想計算機を見つけることができなかったならば、見つかるまでアイドルプロセス４００ａ、４００ｂがスケジュールされる。
【００８０】
仮想計算機ｉのスケジュール優先度Ｐｉが補仮想計算機ｉのスケジュール優先度Ｃｉ以下であるならば、仮想計算機ｉのある仮想プロセッサをスケジュールし、そうでないならば、決してスケジュールしない。スケジュールする仮想プロセッサが見つからない場合には、見つかるまでアイドルプロセスがスケジュールされる。
【００８１】
仮想計算機モニタ１００が上記のスケジュールを続けることは、（式５）と同様に、常に仮想計算機ｉのスケジュール優先度Ｐｉと補仮想計算機ｉのスケジュール優先度Ｃｉが等しくなるように作用する。
【００８２】
仮想計算機ｉのスケジュール優先度Ｐｉと補仮想計算機ｉのスケジュール優先度Ｃｉが等しいことは、以下の（式１３）が満たされることを意味する。
【００８３】
Ｐｉ ＝ Ｃｉ    −＞    Ｒｉ／Ｑｉ ＝ Ｈｉ／Ｇｉ    （式１３）
（式１３）の右側の等式を変換すると、以下の比例式（式１４）が導かれる。
【００８４】
Ｒｉ ： Ｈｉ ＝ Ｑｉ ： Ｇｉ    （式１４）
一方、仮想計算機ｉの持ち時間Ｑｉと補仮想計算機ｉの持ち時間Ｇｉに対して次式（式１５）が成り立つ。
【００８５】
Ｑｉ＋Ｇｉ ＝ Ｑｉ＋（Ｕ−Ｑｉ） ＝ Ｕ    （式１５）
これより、Ｑｉ／Ｕは、プロセッサキャッピングを課すプロセッサ利用率であることがいえる。
【００８６】
以上より、上記のサービス率と同様に論述を進めると、仮想計算機モニタ１００が、仮想計算機ｉのスケジュール優先度Ｐｉと補仮想計算機ｉのスケジュール優先度Ｃｉのうち小さい値をとる仮想計算機をスケジュールし続けると、仮想計算機ｉのプロセッサ利用率はＱｉ／Ｕと等しく、すなわちサービス率Ｓｉで指定した比率と等しくなり、プロセッサキャッピングが課す、プロセッサ利用率がサービス率Ｓｉで指定した比率以下となるという条件も満たすことができる。
【００８７】
一方、プロセッサキャッピング有効の仮想計算機ｉがアイドルのときは、仮想計算機ｉのスケジュール優先度Ｐｉは対応する補仮想計算機ｉのスケジュール優先度Ｃｉよりも小さい、すなわち、次の式（式１６）が成り立つので、本発明のプロセッサキャッピング方法による、プロセッサ利用率の制限は課せられない。
【００８８】
Ｐｉ ＜ Ｃｉ    （式１６）
（式１６）が成り立つことを導く。プロセッサキャッピング有効の仮想計算機ｉがビジーのときの、単位プロセッサ時間の開始時刻Ｔ０からその時点のシステム時刻Ｔ１までの使用プロセッサ時間をＲｉとすると、Ｒｉは（式１３）を満たす。同じ時間区間における、前記仮想計算機 ｉがビジーのときの使用プロセッサ時間をＲｉ’とすると、ＲｉとＲｉ’の間には次式（式１７）の関係式が成り立つ。
【００８９】
Ｒｉ ＜ Ｒｉ’    （式１７）
また、使用プロセッサ時間がＲｉのときの仮想計算機ｉ及び補仮想計算機ｉのスケジュール優先度をそれぞれＰｉとＣｉとし、使用プロセッサ時間がＲｉ’のときの仮想計算機ｉ及び補仮想計算機ｉのスケジュール優先度をそれぞれＰｉ’とＣｉ’とする。このとき、（式１０）、（式１１）、（式１２）、（式１７）より、次式（式１８）と（式１９）が成り立つ。
【００９０】
Ｒｉ’／Ｑｉ ＜ Ｒｉ／Ｑｉ    −＞    Ｐｉ’ ＜ Ｐｉ    （式１８）
（（Ｔ１−Ｔ０）×Ｎ−Ｒｉ）／Ｇｉ ＜ （（Ｔ１−Ｔ０）×Ｎ−Ｒｉ’）／Ｇｉ    −＞    Ｃｉ ＜ Ｃｉ’    （式１９）
（式１３）、（式１８）、（式１９）より、Ｐｉ’とＣｉ’の間に
Ｐｉ’ ＜ Ｃｉ’    （式２０）
が成り立つ。以上より、プロセッサキャッピング有効の仮想計算機ｉがアイドルのときは（式１６）を満たすことが導かれた。
【００９１】
次に、上記で説明した本発明のプロセッサキャッピング方法が、サービス率制御と共存できることを示す。
【００９２】
図２の仮想計算機システム構成において、仮想計算機１ ３００、仮想計算機２ ３１０、及び仮想計算機３ ３２０が全てビジーのときに、仮想計算機１ ３００をプロセッサキャッピング有効にし、仮想計算機２ ３１０と仮想計算機３ ３２０ をプロセッサキャッピング無効にした状態を考える。
このとき、サービス率制御により、次式（式２１）が成立する。
【００９３】
Ｐ１ ＝ Ｐ２ ＝ Ｐ３    −＞    Ｒ１／Ｑ１ ＝ Ｒ２／Ｑ２ ＝ Ｒ３／Ｑ３    （式２１）
このとき、仮想計算機1 ３００のスケジュール優先度Ｐ１ １２８と対応する補仮想計算機１のスケジュール優先度Ｃ１ ２１６が等しいことを導く。これを示すことができれば、本発明のプロセッサキャッピング方法は、サービス率制御の正常動作を妨げないことが言える。
【００９４】
まず、仮想計算機１ ３００に対応する補仮想計算機１の持ちプロセッサ時間Ｇ１ ２１２は、仮想計算機２ ３１０と３ ３２０の持ちプロセッサ時間の和Ｑ２＋Ｑ３に等しい。すなわち、次式（式２２）が成り立つ。
【００９５】
Ｇ１ ＝ Ｕ−Ｑ１ = （Ｑ１＋Ｑ２＋Ｑ３）−Ｑ１ ＝ Ｑ１＋Ｑ２    （式２２）
また、上式（式２２）が成立するときは、物理プロセッサのアイドル時間が０であることより、仮想計算機１ ３００、仮想計算機２ ３１０、及び仮想計算機３ ３２０の使用プロセッサ時間Ｒ１ １２６、使用プロセッサ時間Ｒ２、及び使用プロセッサ時間Ｒ３の和が、物理計算機００１の使用プロセッサ時間、すなわちその時点のシステム時刻Ｔ１から、単位プロセッサ時間の開始時刻Ｔ０ １１６を引いた値（Ｔ１−Ｔ０）に物理プロセッサ数 Nを乗じた（Ｔ１−Ｔ０）ｘＮに等しい、すなわち次式（式２３）が成立する。
【００９６】
Ｒ１＋Ｒ２＋Ｒ３ ＝ （Ｔ１−Ｔ０）ｘＮ    （式２３）
これより、仮想計算機１ ３００に対応する補仮想計算機１の使用プロセッサ時間Ｈ１ ２１４はＲ２＋Ｒ３に等しいことが（式２４）のように導かれる。
【００９７】
Ｈ１ ＝ （Ｔ１−Ｔ０）ｘＮ−Ｒ１ = （Ｒ１＋Ｒ２＋Ｒ３）−Ｒ１ ＝ Ｒ２＋Ｒ３    （式２４）
上記の手順で求めた、補仮想計算機１の持ちプロセッサ時間Ｇ１ ２１２と使用プロセッサ時間Ｈ１２１４を使うと、補仮想計算機１のスケジュール優先度Ｃ１は次式（式２５）のように求まる。
【００９８】
Ｃ１ ＝ Ｈ１／Ｇ１ = （Ｒ２＋Ｒ３）／（Ｑ１＋Ｑ２）    （式２５）
仮想計算機１ ３００のスケジュール優先度Ｐ１ １２６とＣ１ ２１６が等しい、すなわち次式（式２６）が成り立つことが、上式（式２５）から導かれる。
【００９９】
Ｐ１ ＝ Ｃ１    ＜――＞     Ｒ１／Ｑ１ ＝ （Ｒ２＋Ｒ３）／（Ｑ２＋Ｑ３）    （式２６）
サービス率制御と本発明のプロセッサキャッピング方法は共存できるので、図６のサービス率制御に基づくスケジュール対象仮想計算機の選択処理のアルゴリズムに、本発明のプロセッサキャッピング方法のアルゴリズムを追加することができる。
【０１００】
図８に本発明のプロセッサキャッピング方法を追加した、仮想計算機モニタ１００のスケジュール対象仮想計算機のアルゴリズムのフローチャートを示す。
【０１０１】
図６のフローチャートに追加するのは、仮想計算機のプロセッサキャッピングが有効かどうかを判定するステップ（８０４）と、プロセッサキャッピング有効の仮想計算機に対して、該仮想計算機のスケジュール優先度が、対応する補仮想計算機のスケジュール優先度以下であるかどうかを判定するステップ（８０５）である。
【０１０２】
仮想計算機モニタ１００は図８のフローチャートで示すアルゴリズムにおいて、仮想計算機のスケジュール優先度Ｐの他に、一時変数として、ｆｏｒループで使用し仮想計算機番号を表すｉ、仮想計算機のスケジュール優先度Ｐは、その値が小さいほど優先度は高いので、その最小値を保持するＭＩＮＰＲＩＯ、及びＭＩＮＰＲＩＯの値のスケジュール優先度を有する仮想計算機番号、すなわちスケジュール対象の仮想計算機番号を保持するＳＣＨＥＤＶＭを使用する。
【０１０３】
まず、最初にＭＩＮＰＲＩＯを無効な値、具体的にはスケジュール優先度Ｐがとり得ない十分に大きな値で初期化する。また、ＳＣＨＥＤＶＭを存在しない仮想計算機番号０で初期化する。
そして、スケジュール優先度Ｐが最小の仮想計算機番号を取得するｆｏｒループを開始する。ｆｏｒループは、ｉ＝１からｉを１ずつ増加させながらｉが最大仮想計算機番号と等しくなるまでとする。
ｆｏｒループ内の処理を説明する。
まず、仮想計算機ｉのスケジュール優先度Ｐｉを取得する。
次の２つのステップ８０４と８０５が、本発明のプロセッサキャッピング方法を実現する為に追加するステップである。
まず、仮想計算機ｉがプロセッサキャッピング有効かどうかを判定する（８０４）。有効ならば、次へ進む。無効ならば、仮想計算機ｉのスケジュール優先度が全ての仮想計算機の中で最小かどうかを判定するステップ８０６へと進む。
仮想計算機ｉがプロセッサキャッピング有効であるならば、仮想計算機ｉのスケジュール優先度Ｐｉと対応する補仮想計算機ｉのスケジュール優先度Ｃｉを比較する（８０５）。ＰｉがＣｉよりも大きいならば、プロセッサキャッピングが掛かり、スケジュールできない状態であると判定し、以降の全てのステップをスキップし、次の仮想計算機ｉ＋１へと進む。
ＰｉがＣｉ以下であるならば、プロセッサキャッピングは掛かっていないと判定し、次のステップ８０６へと進む。
次に、Ｐｉの値が、一時変数ＭＩＮＰＲＩＯ未満であるならば、ステップ８０７においてＭＩＮＰＲＩＯにＰｉの値を代入し、ＳＣＨＥＤＶＭにｉを代入する。
Ｐｉの値が一時変数ＭＩＮＰＲＩＯ以上であるならば何もしない。
ｆｏｒループを抜けると、スケジュール対象の仮想計算機番号が一時変数ＳＣＨＥＤＶＭに格納されている。
もし、ＳＣＨＥＤＶＭの値が非０であるならば、スケジュール対象の仮想計算機が見つかったことを意味する。仮想計算機モニタ１００は、ＳＣＨＥＤＶＭの番号の仮想計算機のレディキューから仮想プロセッサを取り出して、物理プロセッサにスケジュールする。
ところが、もしＳＣＨＥＤＶＭの値が０であるならば、これはスケジュールする仮想計算機が見つからなかったことを意味する。このときは、仮想計算機モニタ１００はアイドルプロセスを物理プロセッサにスケジュールする。
【０１０４】
本発明のプロセッサキャッピング方式によれば、例えば、仮想計算機に、プロセッサ利用率が２５％の以下のスケジュールを認める、すなわち１分間では１５秒のスケジュールを認めるというプロセッサキャッピングを課した場合に、最初の１５秒間連続して実行され、そこでプロセッサキャッピングの制限がかかり、残りの４５秒間は全く実行されないというシステム応答性の問題が解決でき、どの時間で計測してもプロセッサ利用率を２５％とすることができる。
【図面の簡単な説明】
【０１０５】
【図１】本発明を適用した仮想計算機システムの一実施形態を示す構成図である。
【図２】本発明を適用した一実施形態における、仮想計算機モニタの構成図である。
【図３】物理計算機と仮想計算機の間のプロセッサ時間の関係を示す概念図である。
【図４】仮想プロセッサの使用プロセッサ時間の更新処理のフローチャートである。
【図５】仮想計算機の使用プロセッサ時間の更新処理のフローチャートである。
【図６】仮想計算機モニタの、プロセッサキャッピングを適用しない場合の、スケジュール対象の仮想計算機の選択処理を示すフローチャートである。
【図７】物理計算機、仮想計算機、及び補仮想計算機の間の持ちプロセッサ時間の関係、及び使用プロセッサ時間の関係を示す概念図である。
【図８】仮想計算機モニタの、本発明のプロセッサキャッピング方法を適用する場合の、スケジュール対象の仮想計算機の選択処理を示すフローチャートである。
【符号の説明】
【０１０６】
００１  物理計算機
００２ａ、００２ｂ  物理プロセッサ
００４ａ、００４ｂ  タイマ
００６  システム時刻
１００  仮想計算機モニタ
３００、３１０、３２０  仮想計算機
３０２ａ、３０２ｂ、３０２ｃ、３１２ａ、３１２ｂ、３２２ａ  仮想プロセッサ
４００ａ、４００ｂ  アイドルプロセス
１１０  物理プロセッサテーブル
１１２  物理計算機の単位プロセッサ時間
１１４  物理計算機の物理プロセッサ数
１１６  物理計算機の単位プロセッサ時間開始時刻
１１８  物理計算機の持ちプロセッサ時間
１２０、１３０、１４０  仮想計算機テーブル
１２２  仮想計算機のサービス率
１２４  仮想計算機の持ちプロセッサ時間
１２６  仮想計算機の使用プロセッサ時間
１２８  仮想計算機のスケジュール優先度
１５０、１５２、１５４  仮想計算機レディキュー
１６０ａ、１６０ｂ、１６０ｃ、１７０ａ、１７０ｂ、１８０ａ  仮想プロセッサテーブル
１６２ａ、１７２ａ、１８２ａ  仮想プロセッサのスケジュール開始時刻
２１０、２２０、２３０  補仮想計算機テーブル
２１２  補仮想計算機の持ちプロセッサ時間
２１４  補仮想計算機の使用プロセッサ時間
２１６  補仮想計算機のスケジュール優先度
６０１  仮想計算機１の仮想プロセッサ０の使用プロセッサ時間
６０２  物理計算機の使用プロセッサ時間
【図１】
2008186210.tif 000003
【図２】
2008186210.tif 000004
【図３】
2008186210.tif 000005
【図４】
2008186210.tif 000006
【図５】
2008186210.tif 000007
【図６】
2008186210.tif 000008
【図７】
2008186210.tif 000009
【図８】
2008186210.tif 000010