(57)【特許請求の範囲】
【請求項１】
リモート・プロシージャ呼び出しにより複数のクライアントと通信するサーバおよび前記サーバの状態を複製するサーバ・レプリカにおいて、実行する命令の順序と数を同一にすることにより同一の実行結果を出力する方法であって、
前記クライアントの要求により、前記リモート・プロシージャ呼び出しを順序付けマルチキャスト・プロトコルに基づき順序付けしたデータセットであるマルチキャスト・ラウンドにグループ化するステップと、
前記マルチキャスト・ラウンドを、前記順序付けマルチキャスト・プロトコルにより指定される同一の順序に従い全てのサーバ・レプリカに転送するステップと、
前記マルチキャスト・ラウンドを実行するスレッドを、スケジューラによりキューに配置するステップと、
許可制御窓にキューにスレッドを配置する許可を制御する値を与えるステップと、
前記キュー内にスレッドが存在する場合に、各スレッドに固定数の命令を含む命令スライスを割当てるステップと、
命令カウンタに命令スライスの含む命令の固定数と同じ値を与えるステップと、
前記命令カウンタの値をサーバ・レプリカのＣＰＵが１命令を実行する度に１減分するステップと、
前記命令カウンタの値が０になるとき、割込みにより前記スケジューラを活動化するステップと、
前記許可制御窓の値を前記命令スライスが満了する度に１減分するステップと、
前記許可制御窓の値が０になるとき、新たなマルチキャスト・ラウンドを実行するスレッドを前記スケジューラにより前記キューに配置するステップと、
を含む、方法。
【請求項２】
前記サーバ・レプリカにおいて、スレッドが自発的に中断するとき、前記サーバ・レプリカのＣＰＵが前記命令の実行を中断する、請求項１記載の方法。
【請求項３】
前記サーバ・レプリカにおいて、前記許可制御窓の値および前記命令カウンタの値を調整して、スレッドの割当ておよびマルチキャスト・ラウンドの発生を同期する、請求項１記載の方法。
【請求項４】
リモート・プロシージャ呼び出しにより複数のクライアントと通信するサーバおよび前記サーバの状態を複製するサーバ・レプリカにおいて、実行する命令の順序と数を同一にすることにより同一の実行結果を出力するシステムであって、
前記クライアントの要求により、前記リモート・プロシージャ呼び出しを順序付けマルチキャスト・プロトコルに基づき順序付けしたデータセットであるマルチキャスト・ラウンドにグループ化する手段と、
前記マルチキャスト・ラウンドを、前記順序付けマルチキャスト・プロトコルにより指定される同一の順序に従い全てのサーバ・レプリカに転送する手段と、
前記マルチキャスト・ラウンドを実行するスレッドを、スケジューラによりキューに配置する手段と、
許可制御窓にキューにスレッドを配置する許可を制御する値を与える手段と、
前記キュー内にスレッドが存在する場合に、各スレッドに固定数の命令を含む命令スライスを割当てる手段と、
命令カウンタに命令スライスの含む命令の固定数と同じ値を与える手段と、
前記命令カウンタの値をサーバ・レプリカのＣＰＵが１命令を実行する度に１減分する手段と、
前記命令カウンタの値が０になるとき、割込みにより前記スケジューラを活動化する手段と、
前記許可制御窓の値を前記命令スライスが満了する度に１減分する手段と、
前記許可制御窓の値が０になるとき、新たなマルチキャスト・ラウンドを実行するスレッドを前記スケジューラにより前記キューに配置する手段と、
を含む、システム。
【請求項５】
前記サーバ・レプリカにおいて、スレッドが自発的に中断するとき、前記サーバ・レプリカのＣＰＵが前記命令の実行を中断する、請求項４記載の情報処理システム。
【請求項６】
リモート・プロシージャ呼び出しにより複数のクライアントと通信するサーバおよび前記サーバの状態を複製するサーバ・レプリカにおいて、実行する命令の順序と数を同一にすることにより同一の実行結果を出力するためのコンピュータ・プログラムを記憶した記憶可能型媒体または伝送型媒体であって、
前記クライアントの要求により、前記リモート・プロシージャ呼び出しを順序付けマルチキャスト・プロトコルに基づき順序付けしたデータセットであるマルチキャスト・ラウンドにグループ化する手段と、
前記マルチキャスト・ラウンドを、前記順序付けマルチキャスト・プロトコルにより指定される同一の順序に従い全てのサーバ・レプリカに転送する手段と、
前記マルチキャスト・ラウンドを実行するスレッドを、スケジューラによりキューに配置する手段と、
許可制御窓にキューにスレッドを配置する許可を制御する値を与える手段と、
前記キュー内にスレッドが存在する場合に、各スレッドに固定数の命令を含む命令スライスを割当てる手段と、
命令カウンタに命令スライスの含む命令の固定数と同じ値を与える手段と、
前記命令カウンタの値をサーバ・レプリカのＣＰＵが１命令を実行する度に１減分する手段と、
前記命令カウンタの値が０になるとき、割込みにより前記スケジューラを活動化する手段と、
前記許可制御窓の値を前記命令スライスが満了する度に１減分する手段と、
前記許可制御窓の値が０になるとき、新たなマルチキャスト・ラウンドを実行するスレッドを前記スケジューラにより前記キューに配置する手段と、
を含む手段を実行するためのコンピュータ・プログラムを記憶した記憶可能型媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般に、コンピュータ及び情報処理システムに関して、特に、分散システム内に配備される複製サーバに関する。より詳細には、本発明はマルチキャスト及び決定的スレッド・スケジューリングの使用により、分散システム内の複製サーバ間で、一貫性を強制する方法及びシステムに関する。
【０００２】
【従来の技術】
コンピュータ・ネットワークは、データ処理システムのユーザが、これまで電子媒体において使用不能であった膨大な量の電子情報を検索することを可能にする。コンピュータ・ネットワークは、新聞、雑誌、テレビなどの従来の情報伝達手段を益々置換しつつある。コンピュータ・ネットワークはマシンのセットを接続し、それらが互いに通信することを可能にする。今日広範に使用される典型的なネットワーク化システムは、クライアント／サーバ・アーキテクチャに従う。ネットワーク・コンピュータでは、クライアントは、別のプログラムすなわちサーバにより提供されるサービスを要求するプロセス（概してプログラムまたはタスク）である。クライアント・プロセスは、サーバのオペレーションまたは要求サービスそのものの作業詳細を知る必要無しに、要求サービスを使用し得る。
【０００３】
今日では、ネットワーク・コンピュータ環境においてサーバを実装するために、リモート・プロシージャ呼び出し（コール）（ＲＰＣ）を使用することが一般的である。更に、リモート・プロシージャ呼び出しは、クライアント及びサーバがソフトウェア実装及びソフトウエア通信のために、オブジェクト指向パラダイムを使用するとき、しばしばリモート・メソッド呼び出しシステムと呼ばれる。リモート・プロシージャ呼び出しとリモート・メソッド呼び出しとは、互換に使用されるべきである。この実行モデルでは、クライアントがそれらの要求を"プロシージャ呼び出し"または"メソッド呼び出し"として公式化し、それらがサーバ・マシン上で実行される。サーバは、要求されたプロシージャ呼び出し及びメソッドを実装する。通常オペレーションの間、サーバはそのクライアントからの要求を、ネットワークを介して待機し、受信する。ネットワーク・サブシステムがこうした要求をサーバに受け渡すとき、サーバはクライアントの要求を実行するための"スレッド"を作成し、適切な応答を生成する。スレッドは、サーバ・プロセスのアドレス空間内に存在する軽量の実行単位であり、その資源を、他のことによると独立のクライアント要求を実行している潜在的な他のスレッドと共用する。このモデルでは、スレッドはクライアントの要求により指定されるプロシージャ呼び出し時に、実行を開始し、プロシージャ呼び出しが返却されるまで実行する。サーバは次に、プロシージャ呼び出しにより生成された値をクライアントに返送し、スレッドを割当て解除する。このＲＰＣ実行モデルは、分散コンピュータ環境（ＤＣＥ）、共通オブジェクト要求ブローカ・アーキテクチャ（ＣＯＲＢＡ）及びＤＣＯＭ（分散共通オブジェクト・モデル）などの分散コンピュータ規格の最重要なものとなった。
【０００４】
サーバ・アーキテクチャはしばしば、複製を使用することにより、信頼性及び高可用性を達成するように構成される。こうしたシステムでは、サーバの状態を複製する幾つかのプロセッサまたはマシンが、サービスを提供するために使用される。こうしたマシンは"サーバ・レプリカ"または単に"レプリカ"と呼ばれる。クライアントはサーバ・レプリカのサブセットと通信する。こうしたサブセットは、使用可能なレプリカの全てまたは一部、或いは１つだけを含み得る。クライアントはサブセットをランダムに選択するか、所定の選択基準に従い選択する。従って、サーバにより操作された情報の一貫したビューが、同一のクライアントにより、または異なるクライアントにより認識されるように保証するために、全てのサーバ・レプリカが同一の状態を保持することが必要である。
【０００５】
各レプリカは、サービスを構成するリモート・プロシージャの専用実装を有する。クライアントの要求の実行は、異なるサーバ間で独立に進行するが、この独立の実行形式にも関わらず、レプリカの状態が一貫的であるように保証することが重要である。サーバ・レプリカが故障の場合、残りのサーバ・レプリカが動作し続け、それにより途切れの無いサービスをクライアントに保証する。
【０００６】
複製サービスを実装するにおいて、設計者が遭遇する問題は、レプリカが同一の状態を保持するように保証することであり、これはサービスとのクライアント・トランザクションに影響する。例えば、２つの異なるクライアントが２つのリモート・プロシージャ呼び出しを発行し、複製サービスにより保持されるデータベース内の同一の記録を更新するとしよう。２つのプロシージャ呼び出しが、２つ以上のレプリカにより異なる順序で処理される場合、複製記録の値は不一致となる。
【０００７】
２つの異なるクライアント要求を、異なるサーバ・レプリカにおいて２つの異なる順序で実行するように導く、ＲＰＣシステムの２つの属性が存在する。
【０００８】
第１に、ネットワークが要求をサーバ・レプリカに異なる順序で転送し得る。例えば、クライアントＡ及びＢが、ＲＰＣのＲ及びＰをサーバ・レプリカＣ及びＤに送信する場合、もしネットワークがＲＰＣのＲをＰより先にサーバ・レプリカＣに転送すれば、ＲＰＣのＲをサーバ・レプリカＣにおいて実行するスレッドが、ＲＰＣのＰを実行するスレッドより先に開始し得る。同様に、もしネットワークがＲＰＣのＰをＲより先にサーバ・レプリカＤに転送すれば、ＲＰＣのＰをサーバ・レプリカＤにおいて実行するスレッドが、ＲＰＣのＲを実行するスレッドより先に開始し得る。従って、ネットワークがクライアントの要求を同一の順序でサーバ・レプリカＣ及びＤに転送しないと、サーバ・レプリカは要求を異なる順序で実行し、不一致となり得る。
【０００９】
第２に、各サーバ内のスレッド・スケジューラが、クライアントの要求を異なる順序で実行しているスレッドをスケジュールし得る。従来のスレッド・スケジューラはタイマを使用し、スケジューリング決定を可能にする。しかしながら、タイマは教育的理由から、異なるマシン間で正確ではなく、スレッド・スケジューリング決定は異なるサーバ・レプリカ間で同一でないかもしれない。従って、たとえネットワークが全てのレプリカの間で、クライアント要求を同一の順序で転送しても、スレッド・スケジューリングは必ずしもその順序に従わず、異なるサーバ・レプリカ上でのクライアント要求の実行が、異なり得る。
【００１０】
全ての既存の分散コンピュータ規格は、前述の問題に影響され易い。従来、順序付けられたマルチキャスト・プロトコルが、この問題を解決しようとした。それらは、全てのサーバ・レプリカが同一のメッセージをネットワークから同一の順序で受信することを保証する。この時、サーバ・レプリカ内での実行は、ネットワークにより指定された順序に従い直列化され、ある要求は前の要求が終了する前に、実行を開始できない。この解決法は満足のいくものではない。なぜなら、これは各サーバ内で有効な同時処理の利点を排除し、性能を劇的に低下させるからである。その結果、複製による性能損失が大きくなる。更に、従来技術では、マルチキャスト・プロトコルにより指定される順序と、要求を実行するスレッドの実行順序との間に、つながりが存在しなかった。前述の理由から、サーバの全てのレプリカがクライアントの要求を同一順序で受信し、実行することを保証するために、スレッド・スケジューリング機構と連携して、順序付けプロトコルを実現する改善された方法及びシステムが待望される。本発明は従来技術の一部に属さない新規で固有の方法により、これらの全ての問題を解決する。
【００１１】
【課題を解決するための手段】
従って、本発明の目的は、コンピュータ・ネットワーク内の複製サーバ間で、一貫性を維持するための改善された方法及びシステムを提供することである。
【００１２】
本発明の別の目的は、クライアント及びサーバがリモート・プロシージャ呼び出しを介して通信するコンピュータ・ネットワーク内の複製サーバ間で、一貫性を維持するための改善された方法及びシステムを提供することである。
【００１３】
更に本発明の別の目的は、クライアント及びサーバがリモート・プロシージャ呼び出しを介して通信し、サーバが複数のスレッドを使用することにより、複数のクライアント要求を並列に実行し、性能を改善するコンピュータ・ネットワーク内の複製サーバ間で、一貫性を維持するための改善された方法及びシステムを提供することである。
【００１４】
【発明が解決しようとする課題】
前述の及び他の目的が、次に述べるように達成される。コンピュータ・ネットワーク内のサーバのレプリカの間で、一貫性を維持する方法及びシステムが開示され、そこではクライアント及びサーバが通信のためにリモート・プロシージャ呼び出し（ＲＰＣ）を使用し、サーバが複数のスレッドにより、クライアント要求を実行する。コンピュータ・ネットワークは、１つ以上のクライアントを複製サーバに接続するように想定される。サーバ・レプリカのグループ内の各サーバ・レプリカは、特定のネットワーク・サービスを複製し、特定のネットワーク・サービスがサーバ故障の際に中断されないように維持する。クライアントの要求は、確立済みの技術に従い、リモート・プロシージャ呼び出し内で公式化される。各サーバ・レプリカは、従来一般的なように、所望のサービスをプロシージャ呼び出しまたはオブジェクト・メソッドの形式で実装する。
【００１５】
ここでは、クライアントの要求（ＲＰＣ）を確実に同一の順序で全てのサーバ・レプリカに転送する、順序付けマルチキャスト・プロトコルの存在を想定する。多くのこうしたプロトコルが提案され、実現されており、本発明は次のような任意のプロトコルと協働するように、容易に適応化され得る。マルチキャスト・プロトコルは、クライアント要求をサーバ・レプリカにラウンド式に転送する。１ラウンドの間、各サーバ・レプリカはクライアント要求の同一のセットを、マルチキャスト・プロトコルにより決定された関連実行順序で受信する。マルチキャスト・プロトコルが要求を転送する順序は、全てのサービス・レプリカの間で強制される。従来一般的なように、マルチキャスト・ラウンドは空のこともあり、その場合要求を転送しない。こうした空のラウンドは、従来、故障検出をサポートし、実行の進行を保証するために使用された。
【００１６】
マルチキャスト・プロトコルに関連して、命令カウンタにもとづく決定的且つプリエンプティブ・スレッド・スケジューラが使用される。決定的スケジューラは実行ストリームを命令スライスに細分し、各スライス内の命令数は予め決定される。全てのレプリカは既知のアルゴリズム（例えばラウンドロビン）に従い、スレッドを切り替え、スケジューリングが各命令スライスの終りに発生する。すなわち、あらゆるスレッドは、スレッド内の命令の数が尽きるか、スレッドが自発的に中断するまで、実行する。従って、全てのスケジューリング決定は至る所で同一であり、従来のスレッド・スケジューラの時間ベースのスケジューリングによる非決定性を排除する。
【００１７】
更に、決定的スケジューラは新たなスレッドを、ここでは許可制御窓（ＡＣＷ：admission control window）と呼ぶレディ・キューに組み込む。この技法に従い、スケジューラはｍ命令スライス毎にだけ、新たなスレッドを許可する。ここで、ｍはＡＣＷの頻度を規制する調整可能な実装パラメータである。全てのサービス・レプリカの間で、スレッド実行は同一に維持される。スレッドは全てのレプリカにおいて、同一のＡＣＷの間に許可され、コンテキスト切替えの間に、同一の数の命令を実行するようにスケジュールされる。結果的に、全てのレプリカにおいて、同一の出力を有する実行が達成される。
【００１８】
各ＡＣＷの発生は、マルチキャスト・ラウンドの到来に結び付けられる。すなわち、マルチキャスト・ラウンドとＡＣＷとの間には、１対１の対応が存在する。マルチキャスト・ラウンド内で到来する新たな要求は、スケジューラのレディ・キュー内に入れられる。ラウンドが空の場合、スケジューラは既存のスレッドのスケジューリングを継続する。
【００１９】
本発明の前述の及び追加の目的、特徴及び利点が、以下の説明から明らかとなろう。
【００２０】
【発明の実施の形態】
図１を参照すると、本発明の好適な実施例に従い実現されるクライアント／複製サーバ・アーキテクチャを示す詳細ブロック図が示される。図１に示されるクライアント及びサーバは、実行時にコンピュータ・システム（例えばワークステーション）内で解釈及び実行される、高級プログラミング言語（例えばＣ＋＋）から生成され得るプロセスを表す。
【００２１】
図１に示されるクライアント／複製サーバ・アーキテクチャでは、クライアント９２がコンピュータ・ネットワークを介して、リモート・サービスに接続される。リモート・サービスは、アプリケーションを１つ以上の異なるサーバ・レプリカ８４、８６、８８において実行し、プロセス、マシンまたは通信の故障によるサービスの使用不能確率を低減する。こうしたレプリカは同一であり、特定のサービス・プログラムを実装するために要求される同一のソフトウェアを実行する。クライアント９２はリモート・プロシージャ呼び出しを、レプリカ８４、８６及び８８のいずれかにまたは全てに送信する。特に図１は、クライアントがそのリモート・プロシージャ呼び出し２４をレプリカ８４、８６及び８８に転送する状況を示す。プログラム・サービスはＲＰＣを各サーバ・レプリカにおいて実行し、結果３４が生成され、クライアントに返送される。クライアントは結果を全てのレプリカから受信するが、１つの結果だけがクライアントに達するように、これらをフィルタリングすることが好ましい（全ての結果は同一である）。
【００２２】
図２を参照すると、本発明により要求される順序付けマルチキャスト・プロトコルのオペレーションが示される。順序付けマルチキャスト・プロトコルは、クライアント９２、９４及び９６により、各々のクライアントのクライアント要求に基づき発行されるリモート・プロシージャ呼び出し４４、４６及び４８を順序付けし、それらをマルチキャスト・ラウンド１２０にグループ化する。マルチキャスト・ラウンド１２０は、前記順序付けマルチキャスト・プロトコルにより指定される同一の順序に従い、全てのサーバ・レプリカ８４、８６及び８８に転送される。こうしてマルチキャスト・ラウンドの間、各サーバ・レプリカはリモート・プロシージャ呼び出しの同一のセットを受信し、指定順序で実行する。
【００２３】
図３を参照すると、決定的スレッド・スケジューラ３１の１実施例が示される。各サーバはこのスケジューラのコピーを実装する。スケジューラ３１は、従来一般的なように、スケジューリング機構をサポートするために要求される従来のデータ構造を含む。これらは実行（またはレディ）キュー３０を含む。データ処理システムの主メモリは、スケジューラ３１を実装するコードと一緒に、データ構造を含む。全てのデータ構造は全てのレプリカに渡り、同様に初期化される。更に、既存の技術と異なり、スケジューラ３１は命令カウンタ３９を含み、これはスレッドが各複製サーバのＣＰＵ上で１命令を実行する度に、１カウント・ダウンされるレジスタである。命令カウンタは、各々が固定数の命令を含む命令スライスを実現する役目をする。命令カウンタ３９は命令スライスの開始前に、選択値ｐを与えられる。命令カウンタ３９が０に達するとき、スケジューラを活動化する割込みが生成される。この命令カウンタ３９はハードウェアにより、複製サーバ内のＣＰＵレジスタの形式で使用可能か、ソフトウェアによりエミュレートされる。ここで述べられる本発明は、いずれの形態によっても機能する。更に、スケジューラの設計は、タイマに依存しない点で、従来技術とは異なる。
【００２４】
本発明は、決定的且つプリエンプティブ・スレッド・スケジューリングを実現する。スケジューラ３１は命令スライスをＣＰＵ上で割当て、命令スライスは、スレッドが予め指定された数ｐの命令を実行するスケジューリング単位として作用し、その後スレッドはプリエンプトする。従って、本開示の目的上、"命令スライス"によるスケジューリングは、実行時間または実行サイクル数にもとづくのではなしに、実行される命令の数にもとづき、スレッドをスケジューリングすることを意味する。命令スライスは、命令カウンタ３９の支援により実現される。スライスの開始時に、命令カウンタ３９はｐにセットされる。スレッドが命令スライス内で実行するとき、カウンタは各命令が実行される度に、１減分される。命令カウンタが０に達すると、割込みがスレッドをプリエンプトし、スケジューラ３１が引き継ぐ。スケジューラ３１は必要なコンテキスト切替えを実行し、ことによると別のスレッドの実行をもたらすか、既存のスレッドの実行の継続を許可するように決定する。いずれの場合にも、前述のように命令カウンタ３９をｐにセットすることにより、新たな命令スライスが開始する。
【００２５】
図３を参照すると、キュー３０内のスレッドＡ３２の状態は、その開始時の初期状態、それが実行した命令のストリーム及びそれが受信した入力により、固有に決定される。スレッドが同一の初期状態を与えられ、所与の数の命令を実行し、この実行の間に同一の入力を受信する場合、スレッドの状態は、異なる実行においてその数の命令を実行後、常に同一である。従来技術では、（例えばタイマの満了の結果）スレッドがあるランダムな位置においてプリエンプトされるとき、非決定性が発生した。プリエンプション（強制排除）は、別のスレッドＢ３７がスレッドＡ３２が後に読むであろう共用変数３５を変更することを可能にし得る。プリエンプションはスレッドＡ３２及びＢ３７の実行を順序付けるので、スレッドＡ３２が共用変数３５を読む前後に、スレッドＢ３７がその変更に着手するか否かに応じて、スレッドＡ３２は２つの異なる実行において、異なる値を読み得る。これはプリエンプション位置により固有に決定されるが、プリエンプション位置は、コンピュータのタイマの不正確性及びＣＰＵの実行からのタイマの独立性により、サーバ・レプリカに渡って再現可能でない。
【００２６】
本発明では、プリエンプションは命令スライスの満了時に発生する。従って、プリエンプションは任意のサーバ・レプリカにおけるプログラムの任意の実行の間に、同一位置において発生する。プリエンプションは、プログラムの結果に影響する非決定性の原因であるので、それらを任意のサーバ・レプリカにおける任意のプログラム実行内で同一位置において発生させることは、もしプログラムが同一の入力を受信すれば、プログラムに同一の結果を生成させることになる。前述の従来技術では、例えば、タイマの満了の結果スレッドがあるランダムな位置においてプリエンプトされるとき、非決定性が発生した。しかし、本発明ではスレッドＢ３７がその第２の命令スライスの間に変数を変更し、スレッドＡ３２がその第３の命令スライスの間に変数を読出し、ラウンド・ロビン・スケジューリングを想定する場合、スレッドＡ３２は常に、スレッドＢ３７が共用変数３５を変更した後に、それを読出すことになる。従って、命令スライスを制御するために、同一の値ｐが使用される場合、結果は全てのサーバ・レプリカに渡り決定的である。
【００２７】
スケジューラ３１はまた、その命令スライスが満了する前に、ＣＰＵを放棄すると決定するとき、スレッドをプリエンプトする。これは例えば、一般に知られるように、スレッドが同期変数に従い中断するか、ある入力を待機する場合に発生する。これらの事象は、単一プロセッサ上では決定的である。なぜなら、スレッドは各実行内での同一数の命令後、常に中断するか、入力を待機するため、スケジューリングの決定的性質が保存されるからである。
【００２８】
マルチキャスト・プロトコルに関連するスケジューリング機構は、全てのサーバ・レプリカの同一の実行を保証するために使用される。この属性を実現するために、本発明では、許可制御窓４０に関連付けられるスケジューリング機構がスレッドを順序付ける。こうして一貫性が実現され、スレッドは全て、マルチキャスト・プロトコルにより定義された同一の順序に従い、スケジュールされる。
【００２９】
上述の特徴を可能にするため、スケジューリング機構は、新たなスレッド生成の許可を制御する許可制御窓（Ａｄｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｗｉｎｄｏｗ、ＡＣＷ）４０に関連付けられる。許可制御窓４０によるスレッド生成の制御について説明する。初めに、サーバ・レプリカに新たなクライアント要求が到来する。到来したクライアント要求に基づきリモート・プロシージャ呼び出しを発行する。発行したリモート・プロシージャ呼び出しを、順序付けマルチキャスト・プロトコルにより順序付けする。順序付けしたリモート・プロシージャ呼び出しを、マルチキャスト・ラウンドにグループ化する。グループ化したマルチキャスト・ラウンドを、順序付けマルチキャスト・プロトコルにより同一の順序を指定して全てのサーバ・レプリカに転送する。同一の順序に従い全てのサーバ・レプリカに転送したマルチキャスト・ラウンドを、スケジューラ３１のレディ・キュー３０内に配置する。許可制御窓４０は、スケジューリング機構を制御する値を有する。許可制御窓４０の有する値は、予め定められた命令数を含む命令スライスに含まれる命令が満了する度に、命令の実行をカウントする命令カウンタを１減分する。命令スライスは、スレッドが命令スライスに含まれる命令数の命令を実行すると、スレッドの実行をプリエンプトする。したがって、命令スライスは、スケジューリング単位として作用する。命令カウンタが０に達すると、割込みがスレッドの実行をプリエンプトし、スケジューラ３１が引き継ぐ。スケジューラ３１は必要なコンテキスト切替えを実行し、ことによると別のスレッドの実行をもたらすか、既存のスレッドの実行の継続を許可するように決定する。許可制御窓４０の有する値の命令スライスが満了したとき、サーバは新たなマルチキャスト・ラウンドを待機する。許可制御窓４０の有する値の命令スライスが満了したときであって、さらに新たなラウンドが使用可能なとき、そのラウンド内で使用可能な各要求に対してスレッドが生成され、新たなスレッドがレディ・キュー３０内に入れられる。したがって、スレッドは全て、マルチキャスト・プロトコルにより定義された同一の順序に従い全てのサーバ・レプリカにおいて同一の順序で、スケジュールされる。サーバ・レプリカ間において、レディ・キュー３０内のスレッドの順序は、同一となる。その時点から、本発明のスケジューリング機構による決定的スケジューラは、全てのサーバ・レプリカの実行が同一であることを保証する。
【００３０】
当業者であれば、従来技術とは根本的に異なる本発明の２つの特徴が理解できよう。
【００３１】
第１に、ここでのマルチキャスト・プロトコルの役割は、クライアント要求の実行に関する特定のセマンティクス順序を強制することではない。代わりに、マルチキャスト・プロトコルは、要求をサーバ内に受け入れるために、同一の初期順序を定義する役目をする。従来技術では、マルチキャスト・プロトコルにより指定される順序が拘束的であり、同時実行の結果が、マルチキャスト順序に従う要求の直列化に一致しなければならなかった。本発明では、たとえ特定の順序に一致しなくても、全てのサーバ・レプリカの間で同一の順序を要求する。当業者であれば、直列化が必要でなく（Cheriton及びSkeenによる"Proceedings of the ACM Symposium on Operating Systems Principles"、1993参照）、本発明が同一の考え方を採用することが理解できよう。
【００３２】
第２に、サーバはスケジューリング決定を、マルチキャスト・プロトコルにより定義される順序に関連付ける。従来技術では、スケジューリング及び要求の引渡しは常に独立であった。
【００３３】
従って、ｍの選択は、非決定性を導入するタイマの使用を回避する一方で、システムが外部事象及びクライアント要求に対して、どの程度応答的であるかを制御する。例えば、ｍの選択は、マルチキャスト・ラウンドの発生に関連付けることができる。マルチキャスト・ラウンドとＡＣＷとの間には、相関関係が存在しうる。当業者であれば、ｍの値をマルチキャスト・ラウンドの発生頻度に一致させるように調整することは、特定の実施例では比較的容易であることが理解できよう。
【００３４】
マルチキャスト・ラウンドの発生頻度は、調整可能である。有効なクライアント要求が存在しない場合でも、要求を含まないマルチキャスト・ラウンドを生成することができる。これらの空のラウンドは、全てのレプリカが同一のＡＣＷを通過することを保証することにより、レプリカを同期させるために役立つ。これらのラウンドはまた、従来技術で見られるように、故障検出のためにも使用され得る。
【００３５】
スレッドは、ローカル・システム・サービス（例えばファイルの読出し）が完了するのを待機することを中断できる。こうした中断が発生するとき、スレッドはその命令スライスを放棄し、もはやスケジューラのレディ・キュー３０の一部ではない。中断の理由がもはや有効でないとき（例えばファイルの読出しが完了したとき）、一貫性を保証するために、レディ・キューへのスレッドの再入力が、サーバ・レプリカの間で調整されなければならない。これは次のように達成される。スレッドがあるサーバ・レプリカにおいて実行を再開する準備が整うと、そのサーバ・レプリカはこの事実を次のリモート・プロシージャ呼び出しにおいて公示し、マルチキャスト・ラウンドにより他のサーバ・レプリカに伝えられる（これはクライアント要求に加えて出現する）。将来のラウンドにおいて、全てのレプリカが、その特定のスレッドをどこででも実行できる準備完了状態となる。そのラウンドにおいて、スレッドが再度実行キューに再挿入される。
【００３６】
スケジューラ３１及びＡＣＷ４０の作用は、更に図４を参照することにより理解される。この実施例の論理フローに従い、スケジューラ３１の処理が示される。一旦プロセスが開始すると、スケジューラ３１及びマルチキャスト・プロトコル・スタックがブロック５０で初期化され、カウンタ変数ｎが０にセットされる。ｎ変数は、サーバにおいて現在実行中の活動クライアント要求の数をカウントする。スケジューラ３１は次にブロック５２で、新たなマルチキャスト・ラウンドが使用可能か否かを判断する。使用可能な場合、スケジューラ３１はブロック５４で新たな要求を許可する。新たな要求が使用可能な場合、ｎ変数が１増分され、要求を処理するスレッドが生成され、スレッドがスケジューラ３１に追加され、その後ブロック５２に戻る。このプロセスは、使用可能な追加の新たなマルチキャスト要求が無くなるまで継続する。スケジューラ３１は次にブロック５８で、実行される要求が存在することを確認する。キュー内にスレッドが存在する場合、スケジューラ３１はブロック６２で、スライス内の第１のスレッドから開始し、各スレッドを実行する。この時、ブロック６０で、ＡＣＷカウンタ変数ｊが０にセットされる。スレッドはブロック６２で、ｐ個の命令スライスを実行するように、またはスレッドが中断するか、クライアントに応答するまで、実行するように指示される。各命令スライスが実行されると、ブロック６４でＡＣＷカウンタ変数が１増分される。このカウンタ変数が所定数ｍに達したか否かがチェックされ、新たなマルチキャスト・ラウンドがチェックされるべき時期を決定する。命令スライスの処理は、この数に達するまで継続する。ブロック６６で示されるように、ＡＣＷカウンタ変数がｍよりも大きくなると、ＡＣＷが開き、新たなマルチキャスト・ラウンドがブロック５２で受け入れられる。スケジューリング・プロセス全体は、無期限に継続する。
【００３７】
スレッド・スケジューリングとマルチキャスト転送の前述の組み合わせは、サーバ・レプリカ８４、８６及び８８がクライアント要求を同様に実行することを保証する。例えば、命令のストリームとして、マルチスレッド・プログラムの実行について考えてみよう。新たな要求がｍ命令スライス毎に、命令のストリームに入れられる。全てのレプリカは、マルチキャストを命令ストリーム内の同一ポイントにおいて受信し、マルチキャスト・プロトコルはどこにおいても、順序付けられた確実な転送を保証するので、新たな要求は全てのレプリカにおいて、命令ストリーム内の同一のポイントにおいて認められる。従って、対応するスレッドが、命令ストリーム内の同一の実行ポイントにおいて開始し、任意のレプリカのスレッド・スケジューラが、スレッドが同様にスケジュールされることを保証する。決定的スレッド・スケジューリングの使用により、スレッド実行のインタリーブも、全てのレプリカにおいて同一である。
【００３８】
本発明は完全機能型のリモート・メソッド呼び出しシステムの状況において述べられたが、当業者であれば、本発明の機構が任意の形態のプログラム製品として、任意のタイプの情報処理システムに分散され、本発明が実際に分散を実施するために使用される特定タイプの信号担持媒体に関係なく、同様に適用されることが理解できよう。信号担持媒体の例には、フロッピー・ディスクやＣＤ−ＲＯＭなどの記録可能型媒体、及びアナログ通信リンクまたはデジタル通信リンクなどの伝送型媒体が含まれる。
【００３９】
ＣＯＲＢＡ規格は現在、高可用性のために自動フェール・オーバを保証するための活動的複製をサポートしない。問題は困難である。なぜなら、ＣＯＲＢＡオブジェクトはマルチスレッド型であり、複製時に同一の実行を生成できないからである。ここで述べた本発明は、この問題に対する解決策を提供するもので、ＣＯＲＢＡ準拠のシステムの状況において、活動的複製の使用を可能にし、従来システムにより提供されるのと同一の高可用性をもたらす。本発明は特定の実施例に関連して述べられたが、この説明は限定的な意味で解釈されるべきではない。当業者であれば、本明細書を参照することにより、開示された実施例の様々な変更、並びに本発明の代替実施例が明らかとなろう。例えば、図４ではＡＣＷが別々のカウンタを有するように示されるが、スケジューラとカウンタを共用することが可能であり、それによりＡＣＷは、全てのスケジュール済みスレッドが１度実行された後に、開くことになる。従って、こうした変更も、本発明の趣旨及び範囲から逸れることなく、実施され得るものである。
【００４０】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４１】
（１）リモート・メソッド呼び出しシステムにおける複製サポートのための方法であって、
リモート・プロシージャ呼び出しを通じて、複製サーバと通信する複数のクライアントと、
順序付けマルチキャスト・プロトコルを介して、前記クライアントの前記リモート・プロシージャ呼び出しを順序付けし、グループ化するステップと、
前記リモート・プロシージャ呼び出しを前記サーバ・レプリカに確実に、同一の順序で転送するステップと、
前記各サーバ・レプリカにおいて、前記クライアントの要求を、前記マルチキャスト・プロトコルにより指定された順序に従い実行するスレッドを生成するステップと、
全ての前記サーバ・レプリカにおいて、前記クライアント要求に関連して命令スライスを割当てることにより、前記スレッドを前記順序に従い、決定的且つプリエンプティブにスケジュールするステップと
を含む、方法。
（２）前記クライアント要求をマルチキャスト・ラウンド内にグループ化し、順序付けるステップと、
前記マルチキャスト・ラウンド内の前記クライアント要求が実行されるべき順序を指定するステップと、
前記マルチキャスト・ラウンドを前記サーバ・レプリカに確実に前記順序で転送するステップと
を含む、前記（１）記載の方法。
（３）前記命令スライス内に含まれる命令の数ｐを指定するステップと、
各命令の実行に対して１減分される命令カウンタを使用するステップと、
前記命令カウンタを前記各命令スライスの初めにｐにセットするステップと、前記各命令スライスの初めに、前記スレッドをスケジュールするステップと、
前記カウンタがゼロ値に達するとき、割込みを生成するステップと、
前記割込みを使用し、新たな命令スライスの初めに、新たなスレッドのスケジューリングを可能にするステップと
を含む、前記（１）記載の方法。
（４）前記マルチキャスト・プトロコルにより指定される順序に従い、前記スレッドをスケジューリング・キュー内に配置するステップを含む、前記（３）記載の方法。
（５）所与の前記スレッドがｐ個の命令を実行するか、自発的に中断するまで、前記命令スライスを実行する、前記（３）記載の方法。
（６）中断する所与のスレッドが、全てのレプリカが前記マルチキャスト・ラウンドにおいて、前記スレッドが実行キューに入力されるべきことに同意するまで、前記実行キューへの再入力を許可されない、前記（３）記載の方法。
（７）前記サーバ・レプリカが前記マルチキャスト・プロトコル・ラウンドを介して、中断されたスレッドの準備に関する情報を伝播する、前記（３）記載の方法。
（８）前記マルチキャスト・ラウンドの間に転送される新たな要求の許可が、特定の数の前記命令スライスの実行後にチェックされる、前記（４）記載の方法。
（９）前記マルチキャスト・ラウンドが、２つ毎の前記マルチキャスト・ラウンド転送の間の前記命令スライスの数を決定する数値定数の使用を通じて、新たなクライアント要求のスレッド・スケジューラの許可と同期される、前記（４）記載の方法。
（１０）前記数値定数に等しい数の前記命令スライスが実行された後、新たなクライアント要求をサーバに許可するステップと、
前記クライアント要求を前記マルチキャスト・プロトコルにより指定された順序で許可するステップと、
前記マルチキャスト・ラウンドの転送の間を除き、新たなクライアント要求の許可を禁止するステップと、
２つ毎の連続マルチキャスト・ラウンド間の、ある数値定数の前記命令スライスを追跡するステップと、
任意の２つの連続マルチキャスト間の前記命令スライスが実行される度に、前記サーバの実行を停止するステップと、
空のマルチキャスト・ラウンドを生成し、進行、故障検出及びレプリカ同期を保証するステップと
を含む、前記（８）記載の方法。
（１１）初期スレッド・スケジューリングが、前記マルチキャスト・プロトコルにより指定される順序により決定される、前記（１）記載の方法。
（１２）リモート・プロシージャ呼び出しを通じて、複数のクライアントが複製サーバと通信する手段と、
順序付けマルチキャスト・プロトコルを介して、前記クライアントの前記リモート・プロシージャ呼び出しを順序付けし、グループ化する手段と、
前記リモート・プロシージャ呼び出しを前記サーバ・レプリカに確実に、同一の順序で転送する手段と、
前記各サーバ・レプリカにおいて、前記クライアントの要求を、前記マルチキャスト・プロトコルにより指定された順序に従い実行するスレッドを生成する手段と、
全ての前記サーバ・レプリカにおいて、前記クライアント要求に関連して命令スライスを割当てることにより、前記スレッドを前記順序に従い、決定的且つプリエンプティブにスケジュールする手段と
を含む、情報処理システム。
（１３）前記クライアント要求をマルチキャスト・ラウンド内にグループ化し、順序付ける手段と、
前記マルチキャスト・ラウンド内の前記クライアント要求が実行されるべき順序を指定する手段と、
前記マルチキャスト・ラウンドを前記サーバ・レプリカに確実に前記順序で転送する手段と
を含む、前記（１２）記載の情報処理システム。
（１４）前記命令スライス内に含まれる命令の数ｐを指定する手段と、
各命令の実行に対して１減分される命令カウンタを使用する手段と、
前記命令カウンタを前記各命令スライスの初めにｐにセットする手段と、
前記各命令スライスの初めに、前記スレッドをスケジュールする手段と、
前記カウンタがゼロ値に達するとき、割込みを生成する手段と、
前記割込みを使用し、新たな命令スライスの初めに、新たなスレッドのスケジューリングを可能にする手段と
を含む、前記（１３）記載の情報処理システム。
（１５）前記マルチキャスト・プトロコルにより指定される順序に従い、前記スレッドをスケジューリング・キュー内に配置する手段を含む、前記（１４）記載の情報処理システム。
（１６）所与の前記スレッドがｐ個の命令を実行するか、自発的に中断するまで、前記命令スライスを実行する、前記（１５）記載の情報処理システム。
（１７）中断する所与のスレッドが、全てのレプリカが前記マルチキャスト・ラウンドにおいて、前記スレッドが実行キューに入力されるべきことに同意するまで、前記実行キューへの再入力を許可されない、前記（１６）記載の情報処理システム。
（１８）前記サーバ・レプリカが前記マルチキャスト・プロトコル・ラウンドを介して、中断されたスレッドの準備に関する情報を伝播する、前記（１７）記載の情報処理システム。
（１９）前記マルチキャスト・ラウンドの間に転送される新たな要求の許可が、特定の数の前記命令スライスの実行後にチェックされる、前記（１８）記載の情報処理システム。
（２０）リモート・プロシージャ呼び出しを通じて、複数のクライアントが複製サーバと通信する命令手段と、
順序付けマルチキャスト・プロトコルを介して、前記クライアントの前記リモート・プロシージャ呼び出しを順序付けし、グループ化する命令手段と、
前記リモート・プロシージャ呼び出しを前記サーバ・レプリカに確実に、同一の順序で転送する命令手段と、
前記各サーバ・レプリカにおいて、前記クライアントの要求を、前記マルチキャスト・プロトコルにより指定された順序に従い実行するスレッドを生成する命令手段と、
全ての前記サーバ・レプリカにおいて、前記クライアント要求に関連して命令スライスを割当てることにより、前記スレッドを前記順序に従い、決定的且つプリエンプティブにスケジュールする命令手段と
を含む、コンピュータ・プログラム。
【図面の簡単な説明】
【図１】本発明の好適な実施例に従うクライアントと複製サーバ間の対話を表すブロック図である。
【図２】本発明の好適な実施例に従い、クライアントのリモート・プロシージャ呼び出しを順序付けるための、マルチキャスト・プロトコルのオペレーションを示すブロック図である。
【図３】本発明に従う命令スライス式マルチスレッド・スケジューラの１実施例を示すブロック図である。
【図４】本発明の１実施例に従い、命令スライスを用いてスレッドをスケジュールすることに関連する、順序付けマルチキャストの方法の論理フローを示すフロー図である。
【符号の説明】
２４、４４、４６、４８  リモート・プロシージャ呼び出し
３１  スケジューラ
３９  命令カウンタ
４０  許可制御窓（ＡＣＷ）
８４、８６、８８  サーバ・レプリカ
９２、９４、９６  クライアント
１２０  マルチキャスト・ラウンド
【図１】
0004124547.tif 000002
【図２】
0004124547.tif 000003
【図３】
0004124547.tif 000004
【図４】
0004124547.tif 000005