(57)【要約】【課題】非決定的なクライアント／サーバアプリケーションを、そのアプリケーションを変更することを必要とせずに、複製状態マシンとして実行させることを可能にする機構を提供する。【解決手段】複製状態マシンサブストレートを利用して、それぞれがオペレーティングシステムおよびサーバアプリケーションの同一のコピーを実行させる、複数の仮想マシンモニタの実行が調整される。仮想マシンモニタは、それぞれ、決定的状態マシンとして動作し、状態マシン特性および挙動を仮想化する。【選択図】図１
2006185446.tif 000002
【特許請求の範囲】
【請求項１】
ホストオペレーティングシステムと、
アプリケーションと、
前記アプリケーションをホスティングする非決定的仮想マシンと、
前記仮想マシンおよび前記アプリケーションに決定的挙動特性を提供するように構成される、前記仮想マシンと前記ホストオペレーティングシステムの間でやりとりする仮想マシンモニタと
を備えることを特徴とするコンピュータシステム。
【請求項２】
前記仮想マシンモニタは、実行を求める要求に応答して、第１の決定的な実行の時間にわたって前記仮想マシンの実行を可能にするように構成されることを特徴とする請求項１に記載のコンピュータシステム。
【請求項３】
プロセッサをさらに備え、前記仮想マシンモニタは、実行の時間を設定するのに前記プロセッサ上の機構を利用することによって、前記第１の決定的な実行の時間にわたって前記仮想マシンの実行を可能にするように構成されることを特徴とする請求項２に記載のコンピュータシステム。
【請求項４】
プロセッサをさらに備え、前記仮想マシンモニタは、前記仮想マシンを決定的な時間にわたって実行させ、次いで、前記プロセッサを、前記第１の決定的な実行の時間に到達するまでシングルステップ実行させることによって、前記第１の決定的な実行の時間にわたって前記仮想マシンの実行を可能にするように構成されることを特徴とする請求項２に記載のコンピュータシステム。
【請求項５】
前記決定的な時間は、前記第１の決定的な時間を超えない実行を行うように決定される時間であることを特徴とする請求項４に記載のコンピュータシステム。
【請求項６】
前記仮想マシンモニタは、前記第１の決定的な実行の時間の実行の後、前記プロセッサのシングルステップ実行の前に、前記仮想マシンを第２の決定的な実行の時間にわたって実行させることによって、前記仮想マシンの実行を可能にするようにさらに構成されることを特徴とする請求項４に記載のコンピュータシステム。
【請求項７】
前記第２の決定的な実行の時間は、前記第１の決定的な実行の時間より短いことを特徴とする請求項６に記載のコンピュータシステム。
【請求項８】
前記仮想マシンモニタは、前記仮想マシン用のコードの少なくとも一部をバイナリ書換えすることによって、前記第１の決定的な実行の時間にわたって前記仮想マシンの実行を可能にするように構成されることを特徴とする請求項２に記載のコンピュータシステム。
【請求項９】
前記仮想マシンモニタは、前記仮想マシンが命令を実行するようにローカル仮想装置をプログラムしたことに応答して、決定的な時間にわたって前記仮想マシンの動作を可能にするように構成されることを特徴とする請求項１に記載のコンピュータシステム。
【請求項１０】
前記仮想マシンモニタは、前記仮想マシンの前記決定的な時間にわたる動作の後に、前記命令が完了していない場合、前記命令が完了するまで前記仮想マシンの動作を休止させるようにさらに構成されることを特徴とする請求項９に記載のコンピュータシステム。
【請求項１１】
前記仮想マシンの実行の一定の時間の後にトリガされる周期的仮想クロック割込みをさらに備えることを特徴とする請求項１に記載のコンピュータシステム。
【請求項１２】
前記仮想マシンの実行カウンタの値に基づく値を有する仮想リアルタイムクロックをさらに備えることを特徴とする請求項１に記載のコンピュータシステム。
【請求項１３】
方法を実行するコンピュータ実行可能命令を有するコンピュータ読取り可能記憶媒体であって、前記方法は、
非決定的仮想マシンがホスティングされる、コンピュータを設けること、および、
前記仮想マシンの実行を求める要求に応答して、第１の決定的な実行の時間にわたる前記仮想マシンの実行を連続して増分させること
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項１４】
前記第１の決定的な実行の時間にわたって前記仮想マシンを実行することは、実行の時間を設定するのにプロセッサ上の機構を利用することを含むことを特徴とする請求項１３に記載のコンピュータ読取り可能記憶媒体。
【請求項１５】
前記第１の決定的な実行の時間にわたって前記仮想マシンを実行することは、前記仮想マシンを決定的な時間にわたって実行させ、次いで、前記第１の決定的な実行の時間に到達するまで命令をシングルステップ実行させることを含むことを特徴とする請求項１４に記載のコンピュータ読取り可能記憶媒体。
【請求項１６】
前記第１の決定的な実行の時間にわたって前記仮想マシンを実行することは、前記仮想マシン用のコードの少なくとも一部の動的バイナリ書換え、前記仮想マシンの命令のシングルステップ実行、決定的な時間にわたる前記仮想マシンの実行、またはそれらの一部を含むことを特徴とする請求項１３に記載のコンピュータ読取り可能記憶媒体。
【請求項１７】
方法を実行するコンピュータ実行可能命令を有するコンピュータ読取り可能記憶媒体であって、前記方法は、
非決定的仮想マシンがホスティングされる、コンピュータを設けること、および、
前記仮想マシンが命令を実行するようにローカル仮想装置をプログラムしたことに応答して、前記仮想マシンを決定的な時間にわたって操作すること
を含むことを特徴とするコンピュータ読取り可能記憶媒体。
【請求項１８】
前記決定的な時間は、決定的に見積もられることを特徴とする請求項１７に記載のコンピュータ読取り可能記憶媒体。
【請求項１９】
前記決定的な時間にわたる前記仮想マシンの操作の後に、前記操作が完了している場合、前記仮想マシンに前記操作のための割込みを送出することをさらに含むことを特徴とする請求項１７に記載のコンピュータ読取り可能記憶媒体。
【請求項２０】
前記決定的な時間にわたる前記仮想マシンの操作の後に、前記操作が完了していない場合、前記操作が完了するまで前記仮想マシンの操作を休止させることをさらに含むことを特徴とする請求項１７に記載のコンピュータ読取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、コンピュータに関し、より詳細には、分散コンピューティングに関する。
【背景技術】
【０００２】
分散システムの一利点は、単一のモノリシックなコンピュータ装置を麻痺させるはずの物理的障害に直面しても、動作し続けられることである。そのような障害には、持続的停電、悪天候、洪水、テロ活動などが含まれ得るであろう。
【０００３】
個々のメンバコンピュータ装置がネットワークから切断され、電源を切られ、システム不具合を被り、あるいは別な形で使用不能になり得る、高まるリスクを補償するために、冗長性を使用して、分散コンピューティングシステムが動作し続けられるようにすることができる。ゆえに、任意の１つのコンピューティング装置上で格納され、またはプロセス実行される情報は、別のコンピュータ装置上にも重複して格納することができ、たとえコンピューティング装置の１つに障害が発生した場合でも、情報をアクセス可能なままにすることができる。
【０００４】
分散コンピューティングシステムは、システム内のあらゆる装置が同一のタスクを実行し、同一の情報を格納する、完全な冗長性を実施することができる。そのようなシステムは、たとえほぼ半数の装置に障害が発生した場合でも、ユーザが有用な操作を実行し続けられるようにすることができる。代替として、そのようなシステムは、同じ情報の複数のコピーをある地理的地域全体に分散させるのにも使用され得る。例えば、多国籍企業は、世界規模の分散コンピューティングシステムを構築することができる。
【０００５】
しかしながら、分散コンピューティングシステムは、システムを構成する個々の装置が、間違いなく同じ順序で同一の操作を実行するようにするという複雑さのために、維持するのが難しくなり得る。この困難の多いタスクを円滑化するために、しばしば、状態マシンの手法を使用して、個々の装置間の活動が調整される。状態マシンは、１組の状態、１組のコマンド、１組の応答、および応答／状態対を各コマンド／状態対にリンクさせるクライアントコマンドによって記述され得る。状態マシンは、その状態を変更し、応答を生成することによってコマンドを実行することができる。ゆえに、状態マシンは、その現在の状態、およびそれが実行しようとするアクションによって完全に記述され得る。
【０００６】
したがって、状態マシンの現在の状態は、その前の状態、その後に実行されたコマンド、およびそれらのコマンドが実行された順序に依存するものである。２つ以上の状態マシン間で同期を維持するために、共通の初期状態が確立され、各状態マシンは、初期状態から開始して、同一の順序で同一のコマンドを実行することができる。したがって、ある状態マシンを別の状態マシンに同期させるには、他方の状態マシンによって実行されるコマンドが決定される必要がある。したがって、同期の問題は、実行されるコマンドの順序を決定する問題、あるいは、より具体的には、所与のステップで実行される特定のコマンドを決定する問題になる。
【０００７】
分散コンピューティングシステムは、全体が、状態マシンとしてモデル化され得る。ゆえに、完全な冗長性を実施する分散コンピューティングシステムは、装置のそれぞれにシステム全体の状態を複製させて、各装置が、複製状態マシン（replicated state machine）またはＲＳＭと呼ばれる同じ状態マシンの自身の「レプリカ」をホスティングするようにすることができる。そのようなシステムは、各ＲＳＭが同じ状態を維持することを必要とする。いくつかのレプリカはあるクライアントコマンドが実行されたと考えており、第２のレプリカグループは異なるクライアントコマンドが実行されたと考えている場合、システム全体はもはや単一の状態マシンとして動作しない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
複製状態マシンコンピュータシステムの大きな欠点は、サーバアプリケーションが状態マシンとして設計されなければならないことである。この要件は、もともと状態マシンとして書かれたものではない既存のアプリケーションにとって、かつ／またはアプリケーションが複数の制御スレッドを用いて書かれていた場合には、満足させるのが非常に難しくなり得る。新しいプログラムを決定的（deterministic）状態マシンとして書くことでさえも、簡単ではない。なぜなら、このプログラミングスタイルは、多くのプログラマにとってなじみがなく、しかもスレッドなどの、非決定的抽象化（non-deterministic abstractions）の使用を排除するからである。
【課題を解決するための手段】
【０００９】
一実施形態によれば、非決定的（nondeterministic）クライアント／サーバアプリケーションを、そのアプリケーションが変更されることを必要とせずに、複製状態マシン（replicated state machine）として動作させることを可能にする機構が提供される。複製状態マシンサブストレート（substrate）を利用して、そのそれぞれがオペレーティングシステムおよびサーバアプリケーションのコピーを動作させる、複数の仮想マシンモニタの実行が調整される。一実施形態において、オペレーティングシステムおよびサーバアプリケーションのコピーは同一である。各仮想マシンモニタは、決定的（deterministic）状態マシンとして動作し、状態マシンの特性および挙動を仮想化する。
【００１０】
一実施形態によれば、時間が別個のインターバルのシーケンスに区分化される実行プロトコルが定義され、各インターバル内において、同意プロトコル（agreement protocol）が、任意のメッセージが処理されるべきであるかどうかを判定し、処理すべきメッセージがある場合には、処理すべき順序を決定する。同意プロトコルがその決定を完了した後に、仮想マシンは、決定的な実行の時間（length of execution）（以後、「決定的実行チャンキング」という）にわたって実行することを許される。決定的実行チャンキングを使用して、プログラム実行をインターバルへ分割することは、各仮想マシンを同じ状態まで実行させる。
【００１１】
一実施形態によれば、仮想マシンが決定的実行チャンキングを行うための具体的機構は、一部は、プロセッサアーキテクチャによって決定される。決定的な実行の時間にわたって動作する直接の機構がプロセッサによって提供されない場合、仮想マシンは、目標量を上回らない実行を行うよう保証されている時間にわたって動作することを許され得る。目標が十分に近づくまで、追加の、おそらくより短い実行期間が使用され得る。次いで、仮想マシンは、目標実行ポイントまでシングルステップ実行される。このシステムの代替または追加として、バイナリ書換えも使用され得る。また、シングルステップ実行のみ、仮想マシンモニタによるプロセッサの仮想化、またはこれらの任意の組み合わせも使用され得る。シングルステップ実行およびバイナリ書換えは公知の技法である。
【００１２】
同意プロトコルは、決定的実行チャンキングと共に、仮想ネットワーク割込みハンドラの実行をスケジューリングするために利用される。このようにして、ネットワーク装置が決定的に仮想化され得る。通常、ネットワーク通信など何らかの外部入力を伴うために、その挙動が非決定的である類似の装置は、類似の方法で処理され得る。これらの装置を本明細書では一括して「ネットワーク仮想装置」と呼ぶが、これらの装置は、実際には、ローカルとすることができる。
【００１３】
一実施形態によれば、ローカル装置の動作は、仮想マシンモニタによって、決定的に振る舞うように仮想化される。ローカル仮想装置は仮想マシンによってある操作を実行するようにプログラムされ、仮想マシンモニタは、対応する実際の装置上でその操作を実行する時間を決定的に見積もる。見積もられた実行期間の後に仮想マシンに割込みがかけられ、操作が終了しているかどうか判断される。終了している場合、操作についての割込みが仮想マシンに送出される。終了していない場合、仮想マシンは、操作が完了するまで休止され、次いで、割込みが送出される。その挙動が仮想マシンに関して決定的であるが、そのタイミングが決定的でない可能性のある類似の装置も、同様に扱われ得る。これらの装置を本明細書では「ローカル仮想装置」と呼ぶが、そのような装置が必ずしもローカルであるというわけではない。
【００１４】
一実施形態によれば、仮想マシンの実行に関して決定的である、周期的仮想クロック割込みが提供される。この実施形態によれば、この割込みは、前述の技法として使用する、仮想マシン実行の一定の時間の後にトリガされる。すなわち、利用可能な割込み、バイナリ書換え、シングルステップ実行、時間見積り、仮想マシンモニタによるプロセッサの仮想化、またはこれらの組み合わせが使用され得る。このように、時間は、実時間ではなく、実行に関して測定される。
【００１５】
一実施形態によれば、仮想マシンの実行に関して決定的である、仮想リアルタイムクロックが提供される。この実施形態において、仮想リアルタイムクロック値は、リタイア命令カウンタ、または特定のプロセッサアーキテクチャ上で利用可能な任意の実行カウンタとすることのできる、仮想マシンの実行カウンタの値である。プロセッサアーキテクチャが、ラッピングのおそれがあるような少数のビットを有する実行カウンタを備える場合、このカウンタは、公知の技法を使用してソフトウェアとして拡張され得る。
【００１６】
決定的なネットワーク仮想装置およびローカル仮想装置を提供する上記の方法は、サーバアプリケーションが遭遇するほとんどの操作に使用され得る。例えば、周辺装置はネットワーク装置として扱われ得る。１つの例外は、ローカル装置として扱われるが外部同期を利用する、前述のリアルタイムクロックである。
【００１７】
添付の特許請求の範囲は本発明の特徴を具体的に記述しているが、本発明およびその利点は、以下の詳細な説明を添付の図面と併せて読めば最も適切に理解される。
【発明を実施するための最良の形態】
【００１８】
本発明の範囲内の実施形態には、コンピュータ実行可能命令またはデータ構造を搬送し、またはそれらを格納する、コンピュータ読取り可能記憶媒体が含まれる。そのようなコンピュータ読取り可能記憶媒体は、汎用または専用コンピュータによってアクセスされ得る任意の利用可能な媒体とすることができる。例としてあげるにすぎないが、そのようなコンピュータ読取り可能記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたはその他の光ディスク記憶装置、磁気ディスク記憶装置またはその他の磁気記憶装置、あるいは所望のプログラムコード手段をコンピュータ実行可能命令またはデータ構造の形で搬送し、または格納するのに使用され、汎用または専用コンピュータによってアクセスされ得る他の任意の媒体などの物理的コンピュータ読取り可能記憶媒体が含まれ得る。
【００１９】
情報が、ネットワークまたは別の通信接続（有線、無線、あるいは有線または無線の組み合わせ）を介してコンピュータシステムに転送され、または提供される場合、コンピュータシステムは、その接続を、正しくコンピュータ読取り可能記憶媒体とみなす。ゆえに、任意のそのような接続を、正しく、コンピュータ読取り可能記憶媒体と呼ぶ。また、上記の組み合わせも、コンピュータ読取り可能記憶媒体の範囲内に含めるべきである。コンピュータ実行可能命令には、例えば、汎用コンピュータシステム、専用コンピュータシステム、または専用処理装置に、ある機能または機能グループを実行させる任意の命令およびデータが含まれる。コンピュータ実行可能命令は、例えば、バイナリ、アセンブリ言語などの中間フォーマット命令、あるいはソースコードとすることもできる。
【００２０】
本明細書において、「論理通信リンク」は、コンピュータシステムやモジュールなどの２つのエンティティ間の電子データの転送を可能にし得る任意の通信パスであると定義される。２つのエンティティ間の通信パスの実際の物理的表現は重要ではなく、時間の経過と共に変化し得る。論理通信リンクには、システムバスの一部、ローカルエリアネットワーク（イーサネット（登録商標）ネットワークなど）、広域ネットワーク、インターネット、それらの組み合わせ、または電子データの転送を円滑化し得る他の任意のパスの一部が含まれ得る。論理通信リンクには、有線リンク、無線リンク、または有線リンクと無線リンクの組み合わせが含まれ得る。また、論理通信リンクには、電子データの一部を、本発明の原理を実施するコンポーネントからアクセス可能にするように、調整し、またはフォーマット設定するソフトウェアまたはハードウェアモジュールも含まれ得る。そのようなモジュールには、例えば、プロキシ、ルータ、ファイアウォール、スイッチ、ゲートウェイなどが含まれる。また、論理通信リンクには、例えば、仮想プライベートネットワーク（「ＶＰＮ」）や、仮想ローカルエリアネットワーク（「ＶＬＡＮ」）などの仮想ネットワークの一部も含まれ得る。
【００２１】
図１および以下の考察は、本発明が実施され得る適当なコンピューティング環境の、簡潔で、一般的な説明を提供するためのものである。必須ではないが、以下では本発明を、ネットワーク環境においてコンピュータによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的文脈で説明する。一般に、プログラムモジュールには、個々のタスクを実行し、または個々の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。コンピュータ実行可能命令、関連付けられるデータ構造、およびプログラムモジュールは、本明細書で開示する方法のステップを実行するプログラムコード手段の例を表す。そのような実行可能命令の特定のシーケンスは、そのようなステップに記述される機能を実施する、対応する動作の例を表す。
【００２２】
図１を参照すると、本発明を実施する例示的システムは、処理装置１２１、システムメモリ１２２、およびシステムメモリ１２２を含む様々なシステムコンポーネントを処理装置１２１に結合するシステムバス１２３を含む、従来方式のコンピュータ１２０の形の汎用コンピューティングデバイスを含む。システムバス１２３は、様々なバスアーキテクチャを使用する、メモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含む数種類のバス構造のいずれでもよい。システムメモリには、読取り専用メモリ（ＲＯＭ）１２４およびランダムアクセスメモリ（ＲＡＭ）１２５が含まれる。基本入出力システム（ＢＩＯＳ）１２６は、始動時などに、コンピュータ１２０内の諸要素間の情報転送を支援する基本ルーチンを含み、ＲＯＭ１２４に格納され得る。
【００２３】
また、コンピュータ１２０は、磁気ハードディスク１３９との間で読取りおよび書込みを行う磁気ハードディスクドライブ１２７、取外し可能な磁気ディスク１２９との間で読取りおよび書込みを行う磁気ディスクドライブ１２８、ならびにＣＤ−ＲＯＭやその他の光メディアなどの取外し可能な光ディスク１３１との間で読取りおよび書込みを行う光ディスクドライブ１３０も含み得る。磁気ハードディスクドライブ１２７、磁気ディスクドライブ１２８、および光ディスクドライブ１３０は、それぞれ、ハードディスクドライブインターフェース１３２、磁気ディスクドライブインターフェース１３３、および光ディスクドライブインターフェース１３４によってシステムバス１２３に接続される。各ドライブおよびそれらに関連付けられたコンピュータ読取り可能記憶媒体は、コンピュータ１２０のためのコンピュータ実行可能命令、データ構造、プログラムモジュールおよびその他のデータの不揮発性記憶領域を提供する。本明細書で説明する例示的環境では、磁気ハードディスク１３９、取外し可能な磁気ディスク１２９、および取外し可能な光ディスク１３１を用いるが、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ、ＲＡＭ、ＲＯＭなどを含む、データを格納するその他の種類のコンピュータ読取り可能記憶媒体も使用され得る。
【００２４】
オペレーティングシステム１３５、１つまたは複数のアプリケーションプログラム１３６、その他のプログラムモジュール１３７、およびプログラムデータ１３８を含む、１つまたは複数のプログラムモジュールを有するプログラムコードは、ハードディスク１３９、磁気ディスク１２９、光ディスク１３１、ＲＯＭ１２４またはＲＡＭ１２５に格納され得る。ユーザは、キーボード１４０、ポインティングデバイス１４２、またはマイクロホン、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナなど他の入力装置（図示せず）を介してコンピュータにコマンドおよび情報を入力することができる。上記その他の入力装置は、しばしば、システムバス１２３に結合されたシリアルポートインターフェース１４６を介して処理装置１２１に接続される。代替として、入力装置は、パラレルポート、ゲームポート、ユニバーサルシリアルバス（ＵＳＢ）など他のインターフェースによっても接続され得る。また、モニタ１４７または別の表示装置も、ビデオアダプタ１４８などのインターフェースを介してシステムバス１２３に接続される。モニタ以外に、パーソナルコンピュータは、通常、スピーカやプリンタなど、他の周辺出力装置（図示せず）も含む。
【００２５】
コンピュータ１２０は、リモートコンピュータ１４９ａ、１４９ｂなど１つまたは複数のリモートコンピュータへの論理通信リンクを使用するネットワーク化された環境においいて動作し得る。リモートコンピュータ１４９ａ、１４９ｂは、それぞれ、別のパーソナルコンピュータ、クライアント、サーバ、ルータ、スイッチ、ネットワークＰＣ、ピアデバイスまたはその他の一般のネットワークノードとすることができ、コンピュータ１２０に関して前述した要素の多くまたは全部を含み得るが、図１には、メモリ記憶装置１５０ａ、１５０ｂおよびそれらに関連付けられたアプリケーションプログラム１３６ａ、１３６ｂだけが示されている。図１に示す論理通信リンクには、本明細書において例として提示するにすぎないが、ローカルエリアネットワーク（「ＬＡＮ」）１５１および広域ネットワーク（「ＷＡＮ」）１５２が含まれる。そのようなネットワーク環境は、オフィスまたは企業規模のコンピュータネットワーク、イントラネットおよびインターネットでは一般的である。
【００２６】
ＬＡＮネットワーク環境（イーサネット（登録商標）ネットワークなど）で使用される場合、コンピュータ１２０は、有線または無線インターフェースとすることのできる、ネットワークインターフェースまたはアダプタ１５３を介してＬＡＮ１５１に接続される。ＷＡＮネットワーク環境で使用される場合、コンピュータ１２０は、例えば、モデム１５４などの有線リンク、無線リンク、またはＷＡＮ１５２を介して通信を確立するその他の手段を含み得る。モデム１５４は、内蔵でも外付けでもよく、シリアルポートインターフェース１４６を介してシステムバス１２３に接続される。ネットワーク化された環境では、コンピュータ１２０に関連して示すプログラムモジュール、またはその一部は、リモートメモリ記憶装置にも格納され得る。図示のネットワーク接続は例であり、広域ネットワーク１５２を介して通信を確立するその他の手段も使用され得ることが理解されるであろう。
【００２７】
図１には、本発明の原理を実施し得るコンピュータシステムの一例が示されているが、任意のコンピュータシステムが本発明の機能を実施し得る。この説明および特許請求の範囲において、「コンピュータシステム」は、概して、ソフトウェアを使用して１つまたは複数の機能を実行することのできる任意の１つまたは複数のハードウェアコンポーネントであると定義される。コンピュータシステムの例には、デスクトップコンピュータ、ラップトップコンピュータ、携帯情報端末（「ＰＤＡ」）、（固定とモバイル両方の）電話機、無線アクセスポイント、ゲートウェイ、ファイアウォール、プロキシ、ルータ、スイッチ、ハンドヘルド機器、マルチプロセッサシステム、マイクロプロセッサベースまたはプログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、あるいは処理能力を有する他の任意のシステムまたは装置が含まれる。
【００２８】
また、本発明が、事実上、任意のコンピュータシステム構成を使用するネットワークコンピューティング環境において実施され得ることも、当分野の技術者は理解するであろう。また、本発明は、ネットワークを介して（有線リンク、無線リンク、または有線リンクと無線リンクの組み合わせによって）リンクされた、ローカルおよびリモートのコンピュータシステムが、両方ともタスクを実行する分散システム環境においても実施され得る。分散システム環境において、プログラムモジュールは、ローカルとリモート両方のメモリ記憶装置内に配置され得る。
【００２９】
一般に、本発明は、分散コンピュータシステムへの適用を有する。ますます普及しつつある分散コンピューティングシステムでの使用法は、様々な形の情報についての中央記憶リポジトリ（central storage repository）として働くことのできるネットワークサーバとしてのものである。そのような分散システムは、中央記憶（central storage）と通信しようとしているあらゆるクライアントが、通信するのに好都合で、効率のよい装置を見つけられるように、その構成装置のすべてにおいて中央記憶（central store）を複製しようとする。さらに、システムの分散性のおかげで、停電、洪水、政情不安、セキュリティ侵入などのローカルイベントは、わずかなコンピューティングデバイスだけにしか影響を及ぼさず、システム全体が、適正に動作し、情報およびその他のサービスへのアクセスをクライアントに提供し続けられるようにする。
【００３０】
サーバとして働く分散コンピューティングシステムは、多国籍企業の中央データベースや、人気のあるワールドワイドウェブサイトなど、多種多様なクライアントに大量の情報を提供するのに特に役立ち得る。そのような状況では、多数のクライアントが、サーバとして働く分散コンピューティングシステムからの情報を要求し得る。複数のデバイスにまたがるサーバ機能を実装することによって、サーバは、増大した冗長性のおかげで、全体としてずっと障害が発生しにくくなる。
【００３１】
図２に、クライアントコンピュータ２０２および２つのサーバコンピュータ２０４１、２０４２を備えるコンピュータシステム２００を示す。１つのクライアントコンピュータ２０２だけしか示されていないが、コンピュータシステム２００には、複数のクライアントコンピュータが含まれ得る。同様に、２つのサーバコンピュータ２０４だけしか示されていないが、第２のサーバコンピュータ２０４２の後に続く点で示すように、複製ネットワークでは、通常、もっと多くのサーバコンピュータが使用される。クライアントコンピュータ２０２は、例えば、コンピュータ１２０とすることができ、サーバコンピュータ２０４１、２０４２は、前述のリモートコンピュータ１４９ａ、１４９ｂとすることができる。クライアントおよびサーバとして示すが、クライアントコンピュータ２０２は、他のコンピュータに対するサーバとして働くこともでき、サーバコンピュータ２０４１、２０４２は、他のサーバに対するクライアントとして働くこともできる。
【００３２】
図２に示すコンピュータシステム２００は、従来技術の複製状態マシンに基づくクライアント／サーバコンピュータシステムである。クライアントコンピュータ２０２は、クライアントアプリケーション２０６、オペレーティングシステム１３５などのオペレーティングシステム２０８、ディスク２１２とやりとり（communicating）するディスクドライバ２１０、およびネットワークインターフェースカード（ＮＩＣ）２１６とやりとりするＮＩＣドライバ２１４を含む。また、クライアントコンピュータ２０２は、複製状態マシン（ＲＳＭ）クライアントサブストレート２２０も含む。
【００３３】
サーバコンピュータ２０４１、２０４２のそれぞれは、サーバアプリケーション２２６、オペレーティングシステム２２８、ディスクドライバ２３０、およびハードディスク２３２を含む。また、サーバコンピュータ２０４１、２０４２は、それぞれ、ＮＩＣドライバ２３４およびＮＩＣ２３６も含む。サーバコンピュータのそれぞれは、複製状態マシン（ＲＳＭ）サーバサブストレート２４０を含む。
【００３４】
図２の破線は、クライアントアプリケーション２０６が、複製状態マシンクライアントサブストレート２２０および複製状態マシンサーバサブストレート２４０を介してサーバアプリケーション２２６と通信することを示す。この通信の実際のパスは、オペレーティングシステム２０８、２２８、ネットワークインターフェースカードドライバ２１４、２３４、およびネットワークインターフェースカード２１６、２３６を伴う。ネットワークインターフェースカード２１６、２３６は、論理通信リンク２４２によって接続される。
【００３５】
知られているように、ＲＳＭクライアントサブストレート２２０は、クライアントアプリケーション２０６によって送られるメッセージが複製サーバアプリケーション２２６によって確実に受け取られるようにする。ＲＳＭクライアントサブストレート２２０はこれを、各サーバコンピュータ２０４上のサーバアプリケーション２２６にメッセージを送ることによって行う。しかしながら、最適化として、ＲＳＭクライアントサブストレート２２０は、まず、メッセージをただ１つのサーバアプリケーション２２６に送ることができ、そのサーバアプリケーションが正しく応答しない場合、メッセージをすべてのサーバアプリケーション２２６に送ることができる。また、ＲＳＭクライアントサブストレート２２０は、サーバアプリケーション２２６から応答を収集し、単一の集約された応答をクライアントアプリケーション２０６に渡す。
【００３６】
図２に示す複製状態マシンシステムの代替として、（図示しないが、当分野で知られている）リダイレクタコンピュータも、クライアントコンピュータ２０２とサーバコンピュータ２０４の間のリエゾン（liaison）として働くことができる。そのようなコンピュータシステムでは、クライアントコンピュータ２０２はＲＳＭサブストレートを含まない。その代わりに、クライアントコンピュータ２０２はリダイレクタコンピュータにネットワークメッセージを送り、リダイレクタコンピュータがメッセージを複製し、それらをサーバコンピュータ２０４に送る。また、リダイレクタコンピュータも、サーバコンピュータ２０４から複数のメッセージを収集し、それらを、クライアントコンピュータ２０２に送られる単一のメッセージに集約する。このリダイレクタコンピュータは、単一障害点を構成しないように複製され得る。
【００３７】
ＲＳＭサーバサブストレート２４０の１つのタスクは、サーバの動作についてのタスクの順序付けを確立することである。図３に、ＲＳＭサーバサブストレート２４０などのＲＳＭサーバサブストレートによって処理されるタスクについての、タイミング図の一例を示す。図２には、任意の数のサーバが示されている。図３には、特定の３つのサーバのセット上での動作のタイミングが示されている。下向き矢印は、動作を求める要求を示す。各要求は、クライアントアプリケーション２０６からの要求とすることもでき、サーバベースのタイマによってトリガされる要求とすることもできる。各ＲＳＭサーバサブストレート２４０は、要求についての同意された順序を決定するプロトコルを実行し、次いで、各サーバコンピュータ２０４１、２０４２がその要求を実行する。例えば、図３に示すように、要求Ｆｏｏが受け取られると、この受け取りがＲＳＭサーバサブストレート２４０をトリガしてその同意プロトコルを実行し、同意プロトコルは、Ｆｏｏが、実行すべき次の要求であると判断する。同意の後、サーバコンピュータ２０４１、２０４２のそれぞれは、動作Ｆｏｏを実行する。類似のイベントシーケンスが、要求Ｂａｒが受け取られた場合にも発生する。
【００３８】
要求ＺｏｔおよびＢａｚは、同意プロトコルがまだ要求Ｂａｒを判断している間に受け取られる。要求Ｂａｒについての同意が受け取られた後、ＲＳＭサーバサブストレート２４０は、次にＺｏｔを処理すべきか、それともＢａｚを処理すべきか判断する。この例では、サブストレートはＢａｚを選択し、その後の同意ステップにおいて、サブストレートはＺｏｔを選択する。
【００３９】
図３に示す例では、実行０および１を行うレプリカは、同意プロトコルが判断するよりもゆっくり動作を実行する。同意が、任意に実行のずっと前になるのを防ぐために、現在のＲＳＭサーバサブストレート２４０は、同意プロセスが、所与の動作カウントを超えて実行よりも前になる場合、同意を延期する。
【００４０】
図３に示すように、サーバコンピュータ２０４は、異なる速度で動作を実行することがある。これは、異なるサーバコンピュータ２０４１、２０４２が異なるプロセッサ速度を持つためであり、あるいは、それらが、複製サーバアプリケーション２２６を実行する作業負荷以外の種々の作業負荷を持つためである。例えば、図３に示すように、実行２を行うレプリカは、動作ＦｏｏおよびＢａｒを比較的高速で実行するが、次いで、おそらく別のプロセスがリソースを求めて競合し始めたために、動作ＢａｚおよびＺｏｔを低速で実行する。
【００４１】
図４に、ＲＳＭサーバサブストレート２４０などのＲＳＭサーバサブストレートによって提示され得る、インターフェースの一例を示す。ＲＳＭサーバサブストレート２４０は、ｅｘｅｃｕｔｅ呼び出し４００を使用して、サーバアプリケーション２２６にその状態を更新するよう知らせる。このｅｘｅｃｕｔｅ呼び出し４００は、更新をトリガしたクライアントメッセージを含む。サーバアプリケーション２２６は、ｒｅｐｌｙ呼び出し４０２を使用して、クライアントアプリケーション２０６に送るメッセージを指示する。
【００４２】
ＲＳＭサーバサブストレート２４０は、サーバアプリケーション２２６の状態を追跡する。サーバアプリケーション２２６は、その状態の任意の部分を変更する前に、ｍｏｄｉｆｙ呼び出し４０４を使用して、ＲＳＭサーバサブストレート２４０に、サーバアプリケーションが変更しようとするサーバアプリケーションの状態の部分に関して警告する。ＲＳＭサーバサブストレート２４０は、ｇｅｔ呼び出し４０６を使用して、サーバアプリケーション２２６の状態の任意の部分の値を取り出し、ｐｕｔ呼び出し４０８を使用して、サーバアプリケーション２２６の状態の一部の値を変更する。
【００４３】
図４に示す例では、ＲＳＭサーバサブストレート２４０は、ｃｈｅｃｋｐｏｉｎｔ呼び出し４１０を使用して、サーバアプリケーション２２６に、その状態のチェックポイントを保存するよう知らせる。サーバアプリケーションの状態のチェックポイントを保存すれば、サーバアプリケーションがクラッシュした場合に、サーバアプリケーション２２６をその最新のチェックポイントの状態まで再開させることができる。チェックポイントは自動的に保存され、ＲＳＭサーバサブストレートのそれ自体の内部状態の保存と調整される。
【００４４】
図２〜４を参照して説明した従来技術の複製状態マシンコンピュータシステム２００の大きな欠点は、このシステムが、サーバアプリケーション２２６が前述のような厳格に定義された方法でＲＳＭサーバサブストレート２４０と対話することを必要とすることである。サーバアプリケーション２２６は、クライアントアプリケーション２０６から、またはサーバベースのタイマから、ＲＳＭサーバサブストレート２４０を介して受け取られるメッセージだけに応答してその状態を更新する状態マシンとして、設計されなければならない。また、クライアントコンピュータ２０２へのメッセージは、直接にではなく、ＲＳＭサーバサブストレート２４０を介して送られなければならない。さらに、サーバアプリケーション２２６は、その状態をＲＳＭサーバサブストレート２４０にエクスポートすることができなければならない。また、サーバアプリケーション２２６は、その状態をＲＳＭサーバサブストレート２４０からインポートすることもできなければならず、サーバアプリケーション２２６は、そのアクションのすべてが決定的（deterministic）であるようにもしなければならない。さらに、サーバアプリケーション２２６は、アトミックな方法と、ＲＳＭサーバサブストレート２４０の状態の保存と調整される方法との両方で、その状態をチェックポイント指定することができなければならない。
【００４５】
これらの要件は、もともと状態マシンとして書かれたものではない既存のアプリケーションにとって、満足させるのが非常に難しくなり得る。これらの要件は、アプリケーションが複数の制御スレッドを用いて書かれている場合には、満足させるのが極めて難しくなり得る。新しいプログラムを決定的な状態マシンとして書くことでさえも簡単ではない。というのは、このプログラミングスタイルは、多くのプログラマにとってなじみがなく、スレッドなどの非決定的抽象化の使用を排除するからである。
【００４６】
一実施形態によれば、本発明は、仮想マシンモニタを利用して、サーバアプリケーション用の状態マシンを提供する。仮想マシンモニタは、決定的に書かれていないアプリケーションを、決定的に振る舞わせるように構成される。
【００４７】
仮想マシンモニタは、コンピュータ上のホストオペレーティングシステム内で動作する、カーネルモードのドライバである。代替として、仮想マシンモニタは、パーティショニングを提供するハイエンドサーバなどの中にある、複数のオペレーティングシステムを同時に動作させることのできる特殊なチップを備えるコンピュータを用いても実施され得る。例としては、より高度なＩＢＭ社のハイエンドＰＯＷＥＲ４およびＰＯＷＥＲ５プロセッサ、ならびにサンマイクロシステムズ社、ヒューレットパッカード社およびインテル社による競合するサーバ設計があげられるであろう。仮想マシンモニタは、通常、物理コンピュータプロセッサにアクセスすることができ、コンピュータ上のホストオペレーティングシステムとそのコンピュータ上の「仮想マシン」との間でリソースを管理する。周知のように、仮想マシンは本質的に、コンピュータ内のコンピュータであり、ソフトウェアとして実装される。仮想マシンは、プロセッサからネットワークカードに至る完全なハードウェアシステムを、自己完結型の、隔離されたソフトウェア環境としてエミュレートし、通常は互換性のないオペレーティングシステムの同時動作を可能にする。
【００４８】
代替として、仮想マシンモニタは、パーティショニングを提供するハイエンドサーバなどの中にある、複数のオペレーティングシステムを同時に動作させることのできる特殊なチップを備えるコンピュータを用いても実施され得る。例としては、より高度なＩＢＭ社のハイエンドＰＯＷＥＲ４およびＰＯＷＥＲ５プロセッサ、ならびにサンマイクロシステムズ社、ヒューレットパッカード社およびインテル社による競合するサーバ設計があげられる。パーティションの管理は、この構成では管理コンソールとも呼ばれることのある、仮想マシンモニタによって維持される。
【００４９】
仮想マシンモニタは、仮想マシンに仮想リソースを提示する。特に、仮想マシンモニタは、仮想ディスク、仮想物理メモリ、仮想ネットワークインターフェースなどを提示する。仮想物理メモリを仮想メモリと混同すべきではない。仮想物理メモリは、ゲストオペレーティングシステムには物理メモリとして見え、ゲストオペレーティングシステムは、この仮想物理メモリの上にさらに仮想メモリを実装する。仮想マシンモニタは、ホストオペレーティングシステムの仮想メモリを使用して、その仮想物理メモリを実装する。
【００５０】
周知のように、仮想マシンの使用に際して、仮想マシンプロセスは、コンピュータ上の別のアプリケーションのように扱われ、コンピュータのプロセッサの使用を他のアプリケーションと分け合う。オーバーヘッドを最小限に抑えるために、仮想マシンモニタは、通常、コンピュータ命令を仮想マシンからプロセッサに直接渡す。しかしながら、場合によっては、仮想マシンモニタがプロセッサに命令を直接渡さない方が有用であることもある。そのような状況において、仮想マシンモニタは、特権命令の挙動をシミュレートし、入出力命令を仮想リソースに指定変更する命令をトラップする。トラップされ得ないが、その挙動が仮想化のために増大される必要のある命令を、特定のプロセッサアーキテクチャが持つ場合、動的バイナリ書換えを使用して、これらの命令のインスタンスを明示的トラップ命令に置き換え得る。代替として、仮想マシンモニタは、プロセッサをシミュレートし、各命令を評価し、その命令をプロセッサに渡すこともできるが、そうすると、命令が大幅に遅くなる。しかしながら、仮想マシンの命令をプロセッサに直接渡せば、全命令の間プロセッサを仮想化することを必要とせずに、仮想マシンを動作させることができる。
【００５１】
図５に、本発明の一実施形態による、仮想マシンモニタを利用するコンピュータシステム５００を示す。コンピュータシステム５００は、クライアントコンピュータ２０２に類似のコンポーネントを備える、クライアントコンピュータ５０２を含む。すなわち、クライアントコンピュータは、クライアントアプリケーション５０６、オペレーティングシステム５０８、ディスクドライバ５１０、ディスク５１２、ＮＩＣドライバ５１４、およびＮＩＣ５１６を含む。ＲＳＭクライアントドライバ５２０は、前述のＲＳＭクライアントサブストレート２２０に類似の機能を提供する。使用に際して、クライアントアプリケーション５０６との間のネットワークメッセージは、前述のように、送信メッセージ複製および受信メッセージ集約を行うＲＳＭクライアントドライバ５２０によって代行受信される。
【００５２】
また、コンピュータシステム５００は、サーバコンピュータ５０４も含む。図５に示すシステムの代替として、ＲＳＭクライアントドライバ５２０の代わりに、前述のような、リダイレクタコンピュータも使用され得る。そのような実施形態において、リダイレクタコンピュータは、クライアントコンピュータ５０２とサーバコンピュータ５０４１、５０４２の間のリエゾンとして働く。
【００５３】
一つのクライアントコンピュータ５０２だけしか示されていないが、コンピュータシステム５００には複数のクライアントコンピュータ５０２が含まれ得る。同様に、２つのサーバコンピュータ５０４だけしか示されていないが、第２のサーバコンピュータ５０４２の後に続く点で示すように、もっと多くのサーバコンピュータが企図されている。
【００５４】
サーバコンピュータ５０４１、５０４２は、サーバコンピュータ２０４１、２０４２と同様に、それぞれ、この場合はホストオペレーティングシステム５２８であるオペレーティングシステム５２８、ディスクドライバ５３０、ディスク５３２、ＮＩＣドライバ５３４、およびＮＩＣ５３６を含む。また、ＲＳＭサーバサブストレート５４０が、サーバコンピュータ５０４１、５０４２のそれぞれに存在する。また、一実施形態によれば、サーバコンピュータ５０４１、５０４２は、サーバコンピュータ５０４においてホストオペレーティングシステム５２８と仮想マシン（ＶＭ）５５２との間でやりとりする仮想マシンモニタ（ＶＭＭ）５５０も含む。仮想マシン５５２は、サーバアプリケーション５２６、ゲストオペレーティングシステム５５４、ディスクドライバ５５６、およびＮＩＣドライバ５５８を含む。
【００５５】
サーバコンピュータ５０４１、５０４２は、類似の参照番号を持つコンポーネントを備えるが、異なるコンピュータのコンポーネントは異なり得る。例えば、ホストオペレーティングシステム５２８、５５４は、プロセッサまたはハードウェアアーキテクチャと同様に、異なり得る。
【００５６】
仮想マシンモニタ５５０は、仮想マシン５５２に仮想リソースを提示する。例えば、仮想マシンモニタ５５０は、仮想ディスク５６０および仮想ＮＩＣ５６２を提示する。仮想マシンモニタ５５０は、仮想マシンモニタがホストオペレーティングシステム５２８を介してアクセスする実記憶リソースを使用して仮想記憶リソースを実装し、仮想マシンモニタがホストオペレーティングシステムを介してアクセスする実通信リソースを使用して、仮想通信リソースを実装する。例えば、仮想マシンモニタ５５０は、仮想マシン５５２に仮想ディスク５６０を提示し、物理ディスク５３２をこの仮想ディスクのためのバッキングストア（backing store）として使用する。同様に、仮想マシンモニタ５５０は、仮想マシン５５２に仮想ネットワークカード５６２を提示し、仮想ネットワークカードの代わりに物理ネットワークカード５３６を使用してパケットを送受信する。
【００５７】
ＲＳＭサーバサブストレート５４０は、本発明の一実施形態によれば、サーバアプリケーション５２６を、図４の従来技術のシステムを用いて前述したようなインターフェースに従う決定的状態マシンとして働かせるように構成された、仮想マシンモニタ５５０と通信する。そのために、以下でさらに説明するように、仮想マシンモニタ５５０およびＲＳＭサーバサブストレート５４０は、仮想マシン５５２に状態マシンの挙動をエミュレートさせる。
【００５８】
一実施形態によれば、仮想マシン５５２は、決定的状態マシンとして書かれていない。その代わり、仮想マシンモニタ５５０およびＲＳＭサーバサブストレート５４０は、仮想マシン５５２のアクションが決定的状態マシンになるよう制約されるように構成される。
【００５９】
仮想マシン５５２は状態マシンではないため、図３に示す同意／実行パターンを用いるのは困難である。この同意／実行パターンの代わりに、一実施形態によれば、サーバアプリケーション５２６およびゲストオペレーティングシステム５５４は、見かけ上連続して実行され、メッセージその他のイベントは見かけ上非同期的に到着する。この効果を達成するために、図３の同意プロトコルが異なる方法で使用される。一実施形態によれば、時間が、別個のインターバルのシーケンスに分割され、各インターバル内において、同意プロトコルは、任意のメッセージが処理されるべきであるかどうか、および処理されるべきメッセージがある場合には、それらを処理すべき順序を決定する。以下でさらに説明するように、ここでは、時間の概念は、必ずしも実際の実時間を意味せず、他の方法で、例えば、仮想マシン５５２によって実行される実行命令の数で測定され得る。
【００６０】
ＲＳＭサーバサブストレート５４０によって処理されるタスクのタイミング図の一例を図６に示す。図６において、下向き矢印は、例えば、命令についての１つまたは複数の要求を含み得るメッセージを示す。各メッセージは、命令についての要求を含むことができ、またはメッセージは複数の命令についての要求を含むこともでき、あるいはメッセージは、命令に対する明確な意味関係を持たないこともあり得る。この例では、メッセージは、命令についての要求と１対１の関係を持つ。
【００６１】
メッセージＭ１が到着する同意インターバルの後に開始する同意インターバルの間に、ＲＳＭサーバサブストレート５４０は、その同意プロトコルに従って、次の実行インターバルがメッセージＭ１を含むと判断する。メッセージＭ１が同意プロトコルによって処理されている同意インターバルの間にはメッセージが到着しないため、ＲＳＭサーバサブストレート５４０は、その後の実行はメッセージを含まないと判断する。その同意インターバルの間にメッセージＭ２が到着し、そのため、それに続く同意インターバルの間にＲＳＭサーバサブストレート５４０は、次の実行がメッセージＭ２を含むと判断する。その同意インターバルの間にメッセージＭ３およびＭ４が到着し、そのため、それに続く同意インターバルの間に、ＲＳＭサーバサブストレート５４０は、次の実行はメッセージＭ３およびＭ４を含むと判断し、これらのメッセージの順序はＭ４の後にＭ３が続くものになると判断する。
【００６２】
同意プロトコルがその判断を完了した後、仮想マシン５５２は、決定的な実行の時間にわたって実行することを許される。実行の時間は各仮想マシン５５２ごとに同じであり、このプロセスを、本明細書では、「決定的実行チャンキング」と呼ぶ。実行の時間が選択されるのは、それが各仮想マシンを同じ状態まで実行させるからである。これに対して、実時間を使用すると、クロックサイクルおよび命令の実時間タイミングが可変であるために、異なるサーバコンピュータ５０２上の仮想マシン５５２を、それらのコード中の異なるポイントまで実行させることになり得る。どのようにして決定的な実行の時間にわたって実行するかの一例としては、プロセッサ命令のカウントが使用され得る。しかしながら、決定的結果を生み出す他の任意の方法も利用され得る。
【００６３】
仮想マシン５５２が決定的な実行の時間にわたって実行することを許される（すなわち、目標実行量まで決定的実行チャンキングを実行させる）ための具体的機構は、一部は、プロセッサアーキテクチャによって決定され得る。図７に、本発明の一実施形態による、機構を選択するステップを一般的に記述する流れ図を示す。ステップ７００から開始して、プロセッサが、リタイア命令の一定のカウント後にトリガされ得る、割込みまたは類似の機構を備えるかどうか判断される。そうである場合、ステップ７００はステップ７０２に分岐し、そこで割込みが使用される。そのようなアーキテクチャにおいて、割込みは、単に、目標実行量後にトリガするように設定される。
【００６４】
プロセッサが、決定的な実行の時間にわたって実行させる直接の機構を備えていない場合、ステップ７００はステップ７０４に分岐し、そこで、仮想マシン５５２は、目標量を超えない実行を行うよう保証されている期間にわたって実行することが許される。この期間は、例えば、それが効率的なプロセッサのリソースのすべてを備えているときに目標量を実行するのに要する期間を知っており、目標量をその期間より短い期間、例えば、その期間の８０％に設定することによって計算され得る。
【００６５】
この量は、時間の経過と共にプロセッサ速度が増大するにつれて変更が必要になることがあり、様々なサーバコンピュータ２０４によって異なり得る。一実施形態では、様々なサーバコンピュータ２０４上で様々な期間が利用され、効率に関するフィードバックがサーバサブストレート５４０に提供され得る。このフィードバックは、後の近似を調整するのに使用され、最終的には、より効率のよいプロセスをもたらし得る。
【００６６】
ステップ７０６において、目標実行ポイントが、さらなる実行期間が使用されるのに十分なほど遠く離れているかどうか判断される。一例として、ステップ７０４における最初の操作において、プロセッサは、１秒間実行するように命令され得る。例えば、その期間に実行の６０％だけが行われる場合、ステップ７０６において、ステップ７０４に折り返し、１０分の１秒など、さらにより短い期間にわたって実行するよう決定され得る。このプロセスは、目標が十分に近づく（例えば、１００，０００命令の距離）まで続行され得る。さらに、期間は、目標量が接近するにつれて徐々により短くすることもできる。ステップ７０６の増分の後、プロセスはステップ７０８に分岐し、そこで仮想マシン５５２は、例えば、プロセッサのトラップフラグを、プロセッサをシングルステップ実行するように設定することによって、目標実行ポイントまでシングルステップ実行される。
【００６７】
図７に示す判断の代替として、動的バイナリ書換えを利用して仮想マシン５５２内のコードの一部を書き換え、そのコードがプロセッサに渡される前に仮想マシン５５２内で変更されるようにすることもできる。プロセッサに提供されるバイナリコードを変更することによって、プロセッサが実行する命令数を追跡できるように、追加機能が提供され得る。例えば、バイナリコード内で、カウントが維持され、設定された命令数の後に増分され得る。このカウントの使用は、バイナリ書換えの分野では公知の技法である。この設定数は、普通、「基本ブロック」であり、事前設定の命令数ではなく、ジャンプによって境界を定められる命令の線形シーケンスである。これらのカウントは、目標実行ポイントに到達しており、またはそこに接近しているかどうか判断するのに使用され得る。次いで、（カウントが正確である場合）カウントに到達した後に仮想マシン５５０が操作を中止するための命令が発行され、あるいは目標量が十分に近い場合にはシングルステップ実行が行われ得る。
【００６８】
バイナリ書換えは、通常、シングルステップ実行よりもずっと処理の遅らせ方が小さい。ゆえに、リソース使用および／または遅延を最小限に抑えるために、バイナリ書換えとシングルステップ実行の混成、または設定時間にわたる実行、バイナリ書換えおよびシングルステップ実行の混成が使用され得る。別の代替方法として、プロセッサのシングルステップ実行を最初から開始することもできるが、前述の処理の減速のために、これは高くつく選択肢である。
【００６９】
やはり高くつく別の代替方法としては、仮想マシン５５２についての実行時間の多めの見積りが、たとえその時間がプロセッサに目標実行ポイントを超えさせる場合でも、許容され得る。プロセッサの状態が追跡されるため、プロセッサは、目標実行ポイントを超えた場合に、変更が取り消されて目標実行ポイントまで戻ることができるように構成され得る。しかしながら、この代替方法もやはり高くつくものになり得る。
【００７０】
このように、多種多様な方法を使用して、仮想プロセッサを決定的に振る舞わせることができる。これらの代替方法の１つまたは複数が、仮想マシン５５２が決定的に動作するように使用され得る。
【００７１】
どのようにして決定的な実行の時間にわたって実行させるかという機構が確立された後、この機構は、ネットワーク割込みを処理するためにＲＳＭサーバサブストレート５４０によって設けられた同意プロトコルと共に使用され得る。図８に、一実施形態による、ネットワーク割込みのための同意プロトコルについてのプロセスステップを一般的に示す。ステップ８００から始めて、実行インターバルが開始される。実行インターバルが着信メッセージを含まない場合、ステップ８０２はステップ８０４に分岐し、仮想マシンモニタ５５０は実行インターバルを開始して、以前に割込みをかけられた実行ポイントから仮想マシン５５２を再開する。同意プロトコルによって決定されたように、実行インターバルが、１つまたは複数の着信メッセージを含む場合、ステップ８０２はステップ８０６に分岐し、そこで仮想マシンモニタ５５０は、その１つまたは複数のメッセージを仮想マシン５５２に送出する。そのために、仮想マシンモニタ５５０は、仮想マシンの、仮想ＮＩＣ５６２からの割込みのための処理ルーチンに向かうことができる。ステップ８０８において、仮想マシン５５２は、現在の実行インターバル中のすべてのメッセージについての割込み処理を完了する。次いで、プロセスはステップ８０４に折り返し、通常の割込みからの戻りが、割込みをかけられた実行ポイントから仮想マシン５５２を再開させる。
【００７２】
以上では、ネットワーク割込みおよびそれらが本発明の実施形態によってどのようにして処理されるかについて論じてきた。その挙動が非決定的である類似の装置は、通常、それらの装置が、ネットワーク通信など何らかの外部入力を伴うために、類似の方法で処理され得る。これらの装置を、本明細書では、「ネットワーク仮想装置」と呼ぶが、それらの装置はローカルとすることもできる。やはり、通常は仮想マシン５５２に決定的に送出されない、他の種類の割込みもある。例えば、ディスク５６０などのローカル仮想装置、および仮想リアルタイムクロックなどである。以下で、そのような装置を処理する方法を説明する。
【００７３】
図９に、一実施形態による、ディスクなどのローカル仮想装置からの割込みを処理する例示的ステップを示す。挙動が決定的であるが、タイミングは決定的ではないことのある類似の装置も、同様に扱われ得る。これらの装置を、本明細書では、「ローカル仮想装置」と呼ぶが、そのような装置は必ずしもローカルではない。
【００７４】
ステップ９００から始めて、ディスク５６０などのローカル仮想装置が、仮想マシン５５２によって操作を実行するようにプログラムされる。ステップ９０２において、仮想マシンモニタ５５０は、その操作を行うための時間（すなわち実行の長さ）を見積もる。この見積りは、すべての仮想マシン５５２が同じ時間見積りを利用するように、決定的に行われる。ステップ９０４において、仮想マシンは、見積もられた期間の後に割込みをかけられる。
【００７５】
ステップ９０６において、操作が終了しているかどうか判断される。終了している場合、ステップ９０６はステップ９０８に分岐し、そこで操作のための割込みが仮想マシン５５２に送出される。終了していない場合、ステップ９０６はステップ９１０に分岐し、そこで仮想マシンは操作が完了するまで休止する。次いで、プロセスはステップ９０８に進み、そこで割込みが送出される。
【００７６】
図１０は、ローカル仮想装置および割込み処理の一例に利用される。この図には、図５のサーバコンピュータ５０４の仮想および物理ディスクサブシステムの、より詳細な図が示されている。仮想マシンモニタ５５０は類似のコンポーネントを含むが、仮想ディスク５６０は、仮想ダイレクトメモリアクセス（ＤＭＡ）１００２と仮想記憶域１００４とに分割される。同様に、実際のディスク５３２も、実際のダイレクトメモリアクセス（ＤＭＡ）１００６と実際の記憶域１００８とに分割される。
【００７７】
仮想マシン５５２中のディスクドライバ５５６は、仮想ディスク５６０からデータを読み取ろうとする場合に、読取り要求を用いて仮想ダイレクトメモリアクセス１００２をプログラムし、ダイレクトメモリアクセスが指示されたデータを仮想ディスクからディスクドライバ５５６のメモリに転送した後で、割込みをかけられると期待する。仮想マシンモニタ５５０は、ホストオペレーティングシステム５２８を介してアクセスされる、物理ディスクダイレクトメモリアクセス１００６および物理ディスクドライバ５３０を使用して、物理ディスクへの対応する読取り操作を行うことによって、この挙動を実施する。
【００７８】
従来の仮想マシンモニタでは、物理読取り操作が完了すると、仮想マシンモニタは、仮想ディスク読取りの完了を知らせるために仮想マシンに割込みをかける。物理ディスクは、この読取り操作を行うのに非決定的な時間量を要する。しかしながら、本発明によれば、プロセスは、複製状態マシンの要件を満たすために、決定的な挙動を示す必要がある。
【００７９】
そのために、図９に示す時間見積りプロセスが利用される。仮想ダイレクトメモリアクセス１００２が操作を行うようにプログラムされる場合、仮想マシンモニタ５５０は、ダイレクトメモリアクセス操作が行われる間に経過することになる仮想マシン実行の時間を決定的に見積もり、操作が完了しているかどうかチェックする前にその期間にわたって仮想マシン５５２を実行する。
【００８０】
見積りは、効率性のために行われる。代替方法として、仮想マシンモニタ５５０は、操作を行うように仮想ダイレクトメモリアクセス１００２をプログラムした直後に、仮想マシン５５２を休止させることもできる。この代替方法は、ゼロの時間見積りを使用することに相当する。そのため、仮想マシンモニタ５５０が仮想マシン５５２に仮想ダイレクトメモリアクセス割込みを送出するポイントである、物理読取り操作が完了するときまで、仮想マシンは待機するはずである。しかしながら、仮想マシン５５２を直ちに停止させ、または仮想マシンを非常に短期間停止させると、仮想マシンが計算を入出力遅延とオーバーラップさせるのを妨げることによって、仮想マシンの計算速度を低下させ、望ましくない遅延時間を生じる。ゼロ時間見積りの手法は決定的であり、使用され得るが、本明細書で説明する時間見積りの方法はより効率がよい。使用される見積りは、定数と同じくらい大ざっぱなものとすることもでき（例えば、あらゆる操作が、５００，０００プロセッサ命令を要すると見積もられるなど）、データのサイズに基づいて計算することもでき、決定的に利用可能な他の任意のデータ、すなわち、仮想マシン内からのデータによってパラメータ化されたモデルを使用して計算することもできる。それがどのようにして計算されるかに関わらず、見積りは、仮想マシン５５２のすべてのコピーによって知られている決定的な値に基づくものである。この例では、その値は、転送サイズに関係し得る。
【００８１】
次いで、プロセッサに関する前述の技法を使用して、指示された実行の時間の後に、仮想マシンモニタ５５０が仮想マシン５５２に割込みをかける。物理読取り操作が（見積りが高かったために）すでに完了している場合、仮想マシンモニタ５５０は、仮想マシン５５２に仮想ダイレクトメモリアクセス割込みを送出する。物理読取り操作が（見積りが低かったために）まだ完了していない場合、仮想マシンモニタ５５０は仮想マシン５５２を休止させ、仮想マシンに仮想ダイレクトメモリアクセス割込みを送出するポイントである物理読取り操作が完了するときまで、仮想マシン５５２を再開しない。
【００８２】
前述のように、非ゼロ見積りの使用は、仮想マシン５５２の効率性を向上させる。また、システムは、見積りの正確さが増すと、より効率よく動作する。高い見積りは、ディスクの仮想マシン５５２へのデータ転送速度を低下させる。低い見積りは、仮想マシンの計算速度を低下させる。
【００８３】
以上で、ローカル装置およびネットワークを扱う方法について述べたが、大部分の項目は、これら２つの方法に関連して処理され得る。例えば、決定的に振る舞う項目、すなわち、仮想マシンから見える項目の挙動が、仮想マシンの外部のプロセスによって変更されない項目は、ローカル仮想装置として扱われ得る。これらの多くは、テープドライブやＣＤ−ＲＯＭドライブのように、サーバコンピュータ５０４１、５０４２上に存在し得る。しかしながら、これらの装置はローカルでないこともある。例えば、リモートの読取り専用ネットワークボリュームは、ローカル仮想装置として扱われ得る。別の例としては、ベクトル計算を行うハードウェアアクセラレータや、（スマートカードなどの）暗号化エンジンも、ローカル仮想装置として扱われ得る。周辺装置およびリモートに位置する装置は、ネットワーク仮想装置のように扱われ得る。
【００８４】
割込みに関して対処すべき別の問題が、クロックの必要性である。物理コンピュータは、通常、オペレーティングシステムによって読み取られ得るリアルタイムクロック（ＲＴＣ）レジスタを提供する。また、物理コンピュータは、通常、特に、いくつかのプロセスの間でプロセッサを時分割するのに使用される、周期的クロック割込みも提供する。仮想マシン５５０では、クロックは、図６を伴う説明で論じたように、実行時間を分割するのに必要とされる。また、仮想マシン５５２のそれぞれについて、操作は同じ実行ポイントにおいて割込みをかけられなければならず、すべての仮想マシンが同一のクロック値を読み取る必要がある。
【００８５】
一実施形態によれば、仮想マシンの実行に関して決定的である周期的仮想クロック割込みが提供される。このクロック割込みは、実時間ではないが、仮想マシン５５２のクロックとして使用される。この実施形態によれば、割込みは、図７を伴う説明で前述したような技法を使用して、一定時間の仮想マシン実行の後にトリガされる。すなわち、利用可能な割込み、バイナリ書換え、シングルステップ実行、時間見積り、仮想マシンモニタ５５０によるプロセッサ仮想化、またはこれらの任意の組み合わせが使用され得る。ゆえに、時間は、実際の実時間ではなく実行に関して測定される。
【００８６】
例えば、仮想マシン５５２がおおよそ１ミリ秒に１回割込みをかけられると期待し、プロセッサが毎秒おおよそ１億命令実行する場合、クロック割込みは、１０万命令ごとに仮想マシンに送出され得る。この手法は決定的な実行を保証し、有効な時分割のために必要な頻度で割込みを提供する。
【００８７】
命令が、様々なコンピュータによって様々な速度で処理されるため、割込みは、たいてい、実時間と異なる不規則な間隔で発生する。一実施形態によれば、仮想マシンの実行に関して決定的である仮想リアルタイムクロックが提供される。この実施形態において、仮想リアルタイムクロック値は、リタイア命令カウンタ、または特定のプロセッサアーキテクチャ上で利用可能な任意の実行カウンタとすることのできる、仮想マシン５５２の実行カウンタの値である。ゆえに、リタイア命令カウンタの場合は、仮想マシンが実行する１０億番目の命令がリアルタイムクロックの読取りである場合、戻り値は１０億になる。プロセッサアーキテクチャが、ラッピングのおそれがあるような、少数のビットを有する実行カウンタを備える場合、このカウンタは、公知の技法を使用してソフトウェアとして拡張され得る。
【００８８】
前述の説明において、リアルタイムクロックはローカル仮想装置として機能する。仮想リアルタイムクロックは、仮想マシンの実行速度の変動性のために、実際の実時間をあまり正確に追跡することができない。サーバアプリケーション５２６が、より正確な実際のリアルタイムクロックを必要とする場合、仮想マシン５５２中のゲストオペレーティングシステム５５４は、より正確なリアルタイムクロックを備えるコンピュータを用いて、ネットワークタイムプロトコル（ＮＴＰ）などの任意の標準的なクロック同期プロトコルに関与することができる。時刻同期情報を提供するコンピュータは、ＲＳＭクライアントドライバ５２０などのＲＳＭクライアントドライバを含むこともでき、前述のようなリダイレクタコンピュータと対話することもできる。
【００８９】
前述の、仮想クロック、ローカル装置、および仮想ネットワーク接続に関連付けられる割込みは、それぞれ、ＲＳＭサーバサブストレート２４０のｅｘｅｃｕｔｅ呼び出し４００（図４）に関連する。図４の記述と共に前述したように、サーバアプリケーション５２６によってＲＳＭサーバサブストレート２４０に送られる応答もあり、サーバアプリケーション５２６の状態は、追跡され、ＲＳＭサーバサブストレート２４０に送られる必要がある。
【００９０】
従来方式の複製状態マシンにおいて、クライアントとサーバの間の通信は、リモートプロシージャコール（ＲＰＣ）構造を有する。クライアントは要求を行うことができ、この要求は、他のクライアントからの要求と共に一貫して配列される。サーバは要求を実行し、クライアントに応答する。ゆえに、ｒｅｐｌｙ呼び出し４０２（図４）は、通常、要求側クライアントに、状態更新を開始したという要求への応答を送るために、状態更新ごとに１回呼び出される。
【００９１】
一実施形態によれば、任意のアプリケーションは、たとえそれらのアプリケーションがＲＰＣ通信構造を用いて書かれていない可能性のある場合であっても、サーバアプリケーション５２６として使用するためにサポートされる。この実施形態によれば、サーバアプリケーション５２６は、それがクライアントから受け取った要求との自明な関係を持たない方法でクライアントにメッセージを送ることができる。一実施形態によれば、メッセージは、サーバから直接的に処理される。すなわち、メッセージは、クライアントまたはリダイレクタに直ちに送られる。ＲＳＭクライアントドライバ５２０または（例えばリダイレクタ環境における）類似のエンボイ（envoy）が、サーバアプリケーション５２６からのメッセージの十分な数のコピーを受け取ったとき、ＲＳＭクライアントドライバまたはリダイレクタは、そのメッセージをクライアントアプリケーション５０６に渡す。メッセージの順序付けは、信頼性の高いトランスポート層（例えばＴＣＰ）など、仮想マシン内部のネットワーク層によって、リダイレクタまたはクライアントドライバにおいて提供される。すなわち、本発明は、メッセージの順序付けを提供するための特別な考慮を必要としない。
【００９２】
また、ＲＳＭサーバサブストレート５４０は、複製アプリケーション５２６においても状態を追跡する必要がある。一実施形態によれば、この状態は、仮想マシンモニタ５５０と仮想マシン５５２両方の状態を含む。
【００９３】
仮想マシンモニタ５５０の状態は、大部分の複製状態マシンと同じように処理され得る。すなわち、システムのこの部分についてのコードは、それがその状態を変更する前に、ｍｏｄｉｆｙ呼び出し４０４（図４）を使用することができる。また、それは、ｇｅｔ呼び出しインターフェース４０６およびｐｕｔ呼び出しインターフェース４０８も適切に実施することができる。また、仮想マシンモニタ５５０は、ｃｈｅｃｋｐｏｉｎｔ呼び出し４１０に応答して、その状態を持続的に、アトミックに記録する必要もある。これらの操作のそれぞれについて公知の技法があり、これらの操作は、複製状態マシンの世界では標準的なものである。
【００９４】
仮想マシンのメモリへの変更を追跡するには、知られているｃｏｐｙ−ｏｎ−ｗｒｉｔｅ（書込み時コピー）技法が使用され得る。仮想マシンモニタ５５０は、各チェックポイント指定可能なインターバルの最初に、仮想マシンのメモリ上の保護ビットを書込み不可に設定する。チェックポイントインターバルは、実行インターバルより長くなる可能性が高い。ゆえに、仮想マシン５５２が書込み命令を実行するとき、この実行は、仮想マシンモニタ５５０にトラップを生じさせる。その場合、仮想マシンモニタ５５０は、ｍｏｄｉｆｙ呼び出し４０４を使用して、ＲＳＭサーバサブストレート５４０に、指示されたメモリページが変更されていることを知らせる。仮想マシンモニタ５５０は、指示されたページを読み取り、または指示されたページに書き込むことによって、仮想マシンのメモリにｇｅｔ呼び出しインターフェース４０６およびｐｕｔ呼び出しインターフェース４０８を実施する。最後に、仮想マシンモニタ５５０は、変更されている仮想マシンページの値を記録することによって、仮想マシンのメモリにチェックポイント指定する。
【００９５】
仮想マシンモニタ５５０と仮想マシン５５２両方の状態に加えて、複製状態マシンの分野で知られているレジスタおよびプログラムカウンタおよびプロセッサに関連して格納されるその他の情報などを含む、サーバコンピュータ５０４についてのプロセッサの状態も追跡される必要がある。また、ディスク５３２およびディスクドライバ５３０の状態も追跡される。サーバアプリケーションおよび仮想マシンを所与のポイントまで復元するのに影響を及ぼすはずの、サーバコンピュータ５０４に関連付けられる任意の状態が追跡される。
【００９６】
本明細書で引用する、出版物、特許出願、および特許を含むすべての参照文献は、あたかも各参照文献が、参照によって組み込まれることを個々に、具体的に、指示され、その全体が本明細書に記述されたのと同程度に、参照によって本明細書に組み込まれるものである。
【００９７】
本発明を説明する文脈における（特に、添付の特許請求の範囲の文脈における）「ａ」および「ａｎ」および「ｔｈｅ」および類似の指示の使用は、本明細書で特に指示し、または文脈と明らかに矛盾しない限り、単数と複数両方をカバーするものであると解釈すべきである。「ｃｏｍｐｒｉｓｉｎｇ」、「ｈａｖｉｎｇ」、「ｉｎｃｌｕｄｉｎｇ」および「ｃｏｎｔａｉｎｉｎｇ」という用語は、特に指示しない限り、非制限的用語である（すなわち、「〜を含むがそれだけに限らない」を意味する）と解釈すべきである。本明細書における値の範囲の列挙は、本明細書で特に指示しない限り、単に、その範囲内に含まれる個々の値への個々の言及を簡略に記載する方法として使用するためのものにすぎず、個々の値は、あたかもそれが本明細書で個々に列挙されたかのように本明細書に組み込まれるものである。本明細書で説明するすべての方法は、本明細書で特に指示しない限り、あるいは文脈と明らかに矛盾しない限り、任意の適当な順序で実行され得る。本明細書に示す任意のすべての例、または例示する文言（「ｓｕｃｈ  ａｓなど」）の使用は、単に、本発明をより適切に説明するためのものにすぎず、特に特許請求しない限り、本発明の範囲を限定するものではない。本明細書中のどんな文言も、任意の特許請求されない要素を本発明の実施に不可欠であると指示しているものと解釈すべきではない。
【００９８】
本明細書では、発明者らに知られている、本発明を実行する最適な形態を含めて、本発明の好ましい実施形態を説明している。それらの好ましい実施形態の変形は、以上の説明を読めば、当分野の技術者には明らかになると考えられる。発明者らは、当分野の技術者がそのような変形を適宜用いることを期待しており、発明者らは、本発明が、本明細書で具体的に説明したものとは別のやり方で実施されることを意図している。したがって、本発明は、準拠法によって許される、添付の特許請求の範囲に記載される内容のあらゆる変形および均等物を含むものである。さらに、前述の要素の、そのあらゆる可能な変形としての任意の組み合わせも、本明細書で特に指示せず、あるいは文脈と明らかに矛盾しない限り、本発明によって包含されるものである。
【図面の簡単な説明】
【００９９】
【図１】本発明の一実施形態を実施するのに使用可能な例示的コンピュータシステムを一般的に示す概略図である。
【図２】従来技術の複製状態マシンに基づくクライアント／サーバコンピュータシステムを一般的に示す概略図である。
【図３】従来技術の複製状態マシンサーバサブストレートによって処理されるタスクを表すタイミング図である。
【図４】ＲＳＭサーバサブストレートによって提示され得るインターフェースの一例を表す図である。
【図５】一実施形態による、複製状態マシンに基づくクライアント／サーバコンピュータシステムを一般的に示す概略図である。
【図６】一実施形態による、ＲＳＭサーバサブストレートによって処理されるタスクを表すタイミング図である。
【図７】本発明の一実施形態による、仮想マシンを決定的な実行の時間にわたって動作させるための機構を選択するステップを一般的に表す流れ図である。
【図８】一実施形態による、ネットワーク割込みのための同意プロトコルを処理するプロセスのステップを一般的に表す流れ図である。
【図９】一実施形態による、ディスクなどのローカル仮想装置からの割込みを処理するステップを一般的に表す流れ図である。
【図１０】図５のサーバコンピュータの仮想および物理ディスクサブシステムをより詳細に表す図である。
【図１】
2006185446.tif 000003
【図２】
2006185446.tif 000004
【図３】
2006185446.tif 000005
【図４】
2006185446.tif 000006
【図５】
2006185446.tif 000007
【図６】
2006185446.tif 000008
【図７】
2006185446.tif 000009
【図８】
2006185446.tif 000010
【図９】
2006185446.tif 000011
【図１０】
2006185446.tif 000012
【外国語明細書】
2006185446000001.pdf