JP2000222368A - リモ―ト・メソッド呼び出しシステムにおける複製サポ―トのための方法及びシステム - Google Patents

Abstract

(57)【要約】 【課題】 コンピュータ・ネットワーク内の複製サーバ
間で、一貫性を維持するための改善された方法及びシス
テムを提供すること。 【解決手段】 複製サーバに接続される少なくとも１つ
のクライアントを有するコンピュータ・ネットワークに
おいて、決定的且つプリエンプティブ・スケジューラと
連係して、順序付けマルチキャスト・プロトコルを介す
るクライアント要求の確実且つ順序付けられた転送を通
じて、サーバのレプリカの間の一貫性を強制する方法及
びシステムが開示される。スケジューラが、マルチキャ
スト・プロトコルにより指定される要求の順序付けに一
致するように、実行順序を強制する。決定的スケジュー
ラは実行ストリームを命令スライスに細分し、各スライ
ス内の命令の数は予め決定される。命令スライスの満了
時に割込みを生成するために、命令カウンタが使用され
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は一般に、コンピュー
タ及び情報処理システムに関して、特に、分散システム
内に配備される複製サーバに関する。より詳細には、本
発明はマルチキャスト及び決定的スレッド・スケジュー
リングの使用により、分散システム内の複製サーバ間
で、一貫性を強制する方法及びシステムに関する。

【０００２】

【従来の技術】コンピュータ・ネットワークは、データ
処理システムのユーザが、これまで電子媒体において使
用不能であった膨大な量の電子情報を検索することを可
能にする。コンピュータ・ネットワークは、新聞、雑
誌、テレビなどの従来の情報伝達手段を益々置換しつつ
ある。コンピュータ・ネットワークはマシンのセットを
接続し、それらが互いに通信することを可能にする。今
日広範に使用される典型的なネットワーク化システム
は、クライアント／サーバ・アーキテクチャに従う。ネ
ットワーク・コンピュータでは、クライアントは、別の
プログラムすなわちサーバにより提供されるサービスを
要求するプロセス（概してプログラムまたはタスク）で
ある。クライアント・プロセスは、サーバのオペレーシ
ョンまたは要求サービスそのものの作業詳細を知る必要
無しに、要求サービスを使用し得る。

【０００３】今日では、ネットワーク・コンピュータ環
境においてサーバを実装するために、リモート・プロシ
ージャ呼び出し（コール）（ＲＰＣ）を使用することが
一般的である。更に、リモート・プロシージャ呼び出し
は、クライアント及びサーバがソフトウェア実装及びソ
フトウエア通信のために、オブジェクト指向パラダイム
を使用するとき、しばしばリモート・メソッド呼び出し
システムと呼ばれる。リモート・プロシージャ呼び出し
とリモート・メソッド呼び出しとは、互換に使用される
べきである。この実行モデルでは、クライアントがそれ
らの要求を"プロシージャ呼び出し"または"メソッド呼
び出し"として公式化し、それらがサーバ・マシン上で
実行される。サーバは、要求されたプロシージャ呼び出
し及びメソッドを実装する。通常オペレーションの間、
サーバはそのクライアントからの要求を、ネットワーク
を介して待機し、受信する。ネットワーク・サブシステ
ムがこうした要求をサーバに受け渡すとき、サーバはク
ライアントの要求を実行するための"スレッド"を作成
し、適切な応答を生成する。スレッドは、サーバ・プロ
セスのアドレス空間内に存在する軽量の実行単位であ
り、その資源を、他のことによると独立のクライアント
要求を実行している潜在的な他のスレッドと共用する。
このモデルでは、スレッドはクライアントの要求により
指定されるプロシージャ呼び出し時に、実行を開始し、
プロシージャ呼び出しが返却されるまで実行する。サー
バは次に、プロシージャ呼び出しにより生成された値を
クライアントに返送し、スレッドを割当て解除する。こ
のＲＰＣ実行モデルは、分散コンピュータ環境（ＤＣ
Ｅ）、共通オブジェクト要求ブローカ・アーキテクチャ
（ＣＯＲＢＡ）及びＤＣＯＭ（分散共通オブジェクト・
モデル）などの分散コンピュータ規格の最重要なものと
なった。

【０００４】サーバ・アーキテクチャはしばしば、複製
を使用することにより、信頼性及び高可用性を達成する
ように構成される。こうしたシステムでは、サーバの状
態を複製する幾つかのプロセッサまたはマシンが、サー
ビスを提供するために使用される。こうしたマシンは"
サーバ・レプリカ"または単に"レプリカ"と呼ばれる。
クライアントはサーバ・レプリカのサブセットと通信す
る。こうしたサブセットは、使用可能なレプリカの全て
または一部、或いは１つだけを含み得る。クライアント
はサブセットをランダムに選択するか、所定の選択基準
に従い選択する。従って、サーバにより操作された情報
の一貫したビューが、同一のクライアントにより、また
は異なるクライアントにより認識されるように保証する
ために、全てのサーバ・レプリカが同一の状態を保持す
ることが必要である。

【０００５】各レプリカは、サービスを構成するリモー
ト・プロシージャの専用実装を有する。クライアントの
要求の実行は、異なるサーバ間で独立に進行するが、こ
の独立の実行形式にも関わらず、レプリカの状態が一貫
的であるように保証することが重要である。サーバ・レ
プリカが故障の場合、残りのサーバ・レプリカが動作し
続け、それにより途切れの無いサービスをクライアント
に保証する。

【０００６】複製サービスを実装するにおいて、設計者
が遭遇する問題は、レプリカが同一の状態を保持するよ
うに保証することであり、これはサービスとのクライア
ント・トランザクションに影響する。例えば、２つの異
なるクライアントが２つのリモート・プロシージャ呼び
出しを発行し、複製サービスにより保持されるデータベ
ース内の同一の記録を更新するとしよう。２つのプロシ
ージャ呼び出しが、２つ以上のレプリカにより異なる順
序で処理される場合、複製記録の値は不一致となる。

【０００７】２つの異なるクライアント要求を、異なる
サーバ・レプリカにおいて２つの異なる順序で実行する
ように導く、ＲＰＣシステムの２つの属性が存在する。

【０００８】第１に、ネットワークが要求をサーバ・レ
プリカに異なる順序で転送し得る。例えば、クライアン
トＡ及びＢが、ＲＰＣのＲ及びＰをサーバ・レプリカＣ
及びＤに送信する場合、もしネットワークがＲＰＣのＲ
をＰより先にサーバ・レプリカＣに転送すれば、ＲＰＣ
のＲをサーバ・レプリカＣにおいて実行するスレッド
が、ＲＰＣのＰを実行するスレッドより先に開始し得
る。同様に、もしネットワークがＲＰＣのＰをＲより先
にサーバ・レプリカＤに転送すれば、ＲＰＣのＰをサー
バ・レプリカＤにおいて実行するスレッドが、ＲＰＣの
Ｒを実行するスレッドより先に開始し得る。従って、ネ
ットワークがクライアントの要求を同一の順序でサーバ
・レプリカＣ及びＤに転送しないと、サーバ・レプリカ
は要求を異なる順序で実行し、不一致となり得る。

【０００９】第２に、各サーバ内のスレッド・スケジュ
ーラが、クライアントの要求を異なる順序で実行してい
るスレッドをスケジュールし得る。従来のスレッド・ス
ケジューラはタイマを使用し、スケジューリング決定を
可能にする。しかしながら、タイマは教育的理由から、
異なるマシン間で正確ではなく、スレッド・スケジュー
リング決定は異なるサーバ・レプリカ間で同一でないか
もしれない。従って、たとえネットワークが全てのレプ
リカの間で、クライアント要求を同一の順序で転送して
も、スレッド・スケジューリングは必ずしもその順序に
従わず、異なるサーバ・レプリカ上でのクライアント要
求の実行が、異なり得る。

【００１０】全ての既存の分散コンピュータ規格は、前
述の問題に影響され易い。従来、順序付けられたマルチ
キャスト・プロトコルが、この問題を解決しようとし
た。それらは、全てのサーバ・レプリカが同一のメッセ
ージをネットワークから同一の順序で受信することを保
証する。この時、サーバ・レプリカ内での実行は、ネッ
トワークにより指定された順序に従い直列化され、ある
要求は前の要求が終了する前に、実行を開始できない。
この解決法は満足のいくものではない。なぜなら、これ
は各サーバ内で有効な同時処理の利点を排除し、性能を
劇的に低下させるからである。その結果、複製による性
能損失が大きくなる。更に、従来技術では、マルチキャ
スト・プロトコルにより指定される順序と、要求を実行
するスレッドの実行順序との間に、つながりが存在しな
かった。前述の理由から、サーバの全てのレプリカがク
ライアントの要求を同一順序で受信し、実行することを
保証するために、スレッド・スケジューリング機構と連
携して、順序付けプロトコルを実現する改善された方法
及びシステムが待望される。本発明は従来技術の一部に
属さない新規で固有の方法により、これらの全ての問題
を解決する。

【００１１】

【課題を解決するための手段】従って、本発明の目的
は、コンピュータ・ネットワーク内の複製サーバ間で、
一貫性を維持するための改善された方法及びシステムを
提供することである。

【００１２】本発明の別の目的は、クライアント及びサ
ーバがリモート・プロシージャ呼び出しを介して通信す
るコンピュータ・ネットワーク内の複製サーバ間で、一
貫性を維持するための改善された方法及びシステムを提
供することである。

【００１３】更に本発明の別の目的は、クライアント及
びサーバがリモート・プロシージャ呼び出しを介して通
信し、サーバが複数のスレッドを使用することにより、
複数のクライアント要求を並列に実行し、性能を改善す
るコンピュータ・ネットワーク内の複製サーバ間で、一
貫性を維持するための改善された方法及びシステムを提
供することである。

【００１４】

【発明が解決しようとする課題】前述の及び他の目的
が、次に述べるように達成される。コンピュータ・ネッ
トワーク内のサーバのレプリカの間で、一貫性を維持す
る方法及びシステムが開示され、そこではクライアント
及びサーバが通信のためにリモート・プロシージャ呼び
出し（ＲＰＣ）を使用し、サーバが複数のスレッドによ
り、クライアント要求を実行する。コンピュータ・ネッ
トワークは、１つ以上のクライアントを複製サーバに接
続するように想定される。サーバ・レプリカのグループ
内の各サーバ・レプリカは、特定のネットワーク・サー
ビスを複製し、特定のネットワーク・サービスがサーバ
故障の際に中断されないように維持する。クライアント
の要求は、確立済みの技術に従い、リモート・プロシー
ジャ呼び出し内で公式化される。各サーバ・レプリカ
は、従来一般的なように、所望のサービスをプロシージ
ャ呼び出しまたはオブジェクト・メソッドの形式で実装
する。

【００１５】ここでは、クライアントの要求（ＲＰＣ）
を確実に同一の順序で全てのサーバ・レプリカに転送す
る、順序付けマルチキャスト・プロトコルの存在を想定
する。多くのこうしたプロトコルが提案され、実現され
ており、本発明は次のような任意のプロトコルと協働す
るように、容易に適応化され得る。マルチキャスト・プ
ロトコルは、クライアント要求をサーバ・レプリカにラ
ウンド式に転送する。１ラウンドの間、各サーバ・レプ
リカはクライアント要求の同一のセットを、マルチキャ
スト・プロトコルにより決定された関連実行順序で受信
する。マルチキャスト・プロトコルが要求を転送する順
序は、全てのサービス・レプリカの間で強制される。従
来一般的なように、マルチキャスト・ラウンドは空のこ
ともあり、その場合要求を転送しない。こうした空のラ
ウンドは、従来、故障検出をサポートし、実行の進行を
保証するために使用された。

【００１６】マルチキャスト・プロトコルに関連して、
命令カウンタにもとづく決定的且つプリエンプティブ・
スレッド・スケジューラが使用される。決定的スケジュ
ーラは実行ストリームを命令スライスに細分し、各スラ
イス内の命令数は予め決定される。全てのレプリカは既
知のアルゴリズム（例えばラウンドロビン）に従い、ス
レッドを切り替え、スケジューリングが各命令スライス
の終りに発生する。すなわち、あらゆるスレッドは、ス
レッド内の命令の数が尽きるか、スレッドが自発的に中
断するまで、実行する。従って、全てのスケジューリン
グ決定は至る所で同一であり、従来のスレッド・スケジ
ューラの時間ベースのスケジューリングによる非決定性
を排除する。

【００１７】更に、決定的スケジューラは新たなスレッ
ドを、ここでは許可制御窓（ＡＣＷ：admission contro
l window）と呼ぶレディ・キューに組み込む。この技法
に従い、スケジューラはｍ命令スライス毎にだけ、新た
なスレッドを許可する。ここで、ｍはＡＣＷの頻度を規
制する調整可能な実装パラメータである。全てのサービ
ス・レプリカの間で、スレッド実行は同一に維持され
る。スレッドは全てのレプリカにおいて、同一のＡＣＷ
の間に許可され、コンテキスト切替えの間に、同一の数
の命令を実行するようにスケジュールされる。結果的
に、全てのレプリカにおいて、同一の出力を有する実行
が達成される。

【００１８】各ＡＣＷの発生は、マルチキャスト・ラウ
ンドの到来に結び付けられる。すなわち、マルチキャス
ト・ラウンドとＡＣＷとの間には、１対１の対応が存在
する。マルチキャスト・ラウンド内で到来する新たな要
求は、スケジューラのレディ・キュー内に入れられる。
ラウンドが空の場合、スケジューラは既存のスレッドの
スケジューリングを継続する。

【００１９】本発明の前述の及び追加の目的、特徴及び
利点が、以下の説明から明らかとなろう。

【００２０】

【発明の実施の形態】図１を参照すると、本発明の好適
な実施例に従い実現されるクライアント／複製サーバ・
アーキテクチャを示す詳細ブロック図が示される。図１
に示されるクライアント及びサーバは、実行時にコンピ
ュータ・システム（例えばワークステーション）内で解
釈及び実行される、高級プログラミング言語（例えばＣ
＋＋）から生成され得るプロセスを表す。

【００２１】図１に示されるクライアント／複製サーバ
・アーキテクチャでは、クライアント９２がコンピュー
タ・ネットワークを介して、リモート・サービスに接続
される。リモート・サービスは、アプリケーションを１
つ以上の異なるサーバ・レプリカ８４、８６、８８にお
いて実行し、プロセス、マシンまたは通信の故障による
サービスの使用不能確率を低減する。こうしたレプリカ
は同一であり、特定のサービス・プログラムを実装する
ために要求される同一のソフトウェアを実行する。クラ
イアント９２はリモート・プロシージャ呼び出しを、レ
プリカ８４、８６及び８８のいずれかにまたは全てに送
信する。特に図１は、クライアントがそのリモート・プ
ロシージャ呼び出し２４をレプリカ８４、８６及び８８
に転送する状況を示す。プログラム・サービスはＲＰＣ
を各サーバ・レプリカにおいて実行し、結果３４が生成
され、クライアントに返送される。クライアントは結果
を全てのレプリカから受信するが、１つの結果だけがク
ライアントに達するように、これらをフィルタリングす
ることが好ましい（全ての結果は同一である）。

【００２２】図２を参照すると、本発明により要求され
るマルチキャスト・プロトコルのオペレーションが示さ
れる。マルチキャスト・プロトコルは、クライアント９
２、９４及び９６により発行されるリモート・プロシー
ジャ呼び出し４４、４６及び４８を順序付けし、それら
をマルチキャスト・ラウンド１２０にグループ化する。
マルチキャスト・ラウンド１２０は、確実に全てのサー
ビス・レプリカ８４、８６及び８８に転送され、従っ
て、全てのレプリカは、クライアントのリモート・プロ
シージャ呼び出しが実行されるべき順序に同意する。こ
うしてマルチキャスト・ラウンドの間、各サーバ・レプ
リカはリモート・プロシージャ呼び出しの同一のセット
を受信し、指定順序で実行する。

【００２３】図３を参照すると、決定的スレッド・スケ
ジューラ３１の１実施例が示される。各サーバはこのス
ケジューラのコピーを実装する。スケジューラ３１は、
従来一般的なように、スケジューリング機構をサポート
するために要求される従来のデータ構造を含む。これら
は実行（またはレディ）キュー３０を含む。データ処理
システムの主メモリは、スケジューラ３１を実装するコ
ードと一緒に、データ構造を含む。全てのデータ構造は
全てのレプリカに渡り、同様に初期化される。更に、既
存の技術と異なり、スケジューラ３１は命令カウンタ３
９を含み、これはスレッドが各複製サーバのＣＰＵ上で
１命令を実行する度に、１カウント・ダウンされるレジ
スタである。命令カウンタは、各々が固定数の命令を含
む命令スライスを実現する役目をする。命令カウンタ３
９は命令スライスの開始前に、選択値ｐを与えられる。
命令カウンタ３９が０に達するとき、スケジューラを活
動化する割込みが生成される。この命令カウンタ３９は
ハードウェアにより、複製サーバ内のＣＰＵレジスタの
形式で使用可能か、ソフトウェアによりエミュレートさ
れる。ここで述べられる本発明は、いずれの形態によっ
ても機能する。更に、スケジューラの設計は、タイマに
依存しない点で、従来技術とは異なる。

【００２４】本発明は、決定的且つプリエンプティブ・
スレッド・スケジューリングを実現する。スケジューラ
３１は命令スライスをＣＰＵ上で割当て、命令スライス
は、スレッドが予め指定された数ｐの命令を実行するス
ケジューリング単位として作用し、その後スレッドはプ
リエンプトする。従って、本開示の目的上、"命令スラ
イス"によるスケジューリングは、実行時間または実行
サイクル数にもとづくのではなしに、実行される命令の
数にもとづき、スレッドをスケジューリングすることを
意味する。命令スライスは、命令カウンタ３９の支援に
より実現される。スライスの開始時に、命令カウンタ３
９はｐにセットされる。スレッドが命令スライス内で実
行するとき、カウンタは各命令が実行される度に、１減
分される。命令カウンタが０に達すると、割込みがスレ
ッドをプリエンプトし、スケジューラ３１が引き継ぐ。
スケジューラ３１は必要なコンテキスト切替えを実行
し、ことによると別のスレッドの実行をもたらすか、既
存のスレッドの実行の継続を許可するように決定する。
いずれの場合にも、前述のように命令カウンタ３９をｐ
にセットすることにより、新たな命令スライスが開始す
る。

【００２５】図３を参照すると、キュー３０内のスレッ
ドＡ３２の状態は、その開始時の初期状態、それが実行
した命令のストリーム及びそれが受信した入力により、
固有に決定される。スレッドが同一の初期状態を与えら
れ、所与の数の命令を実行し、この実行の間に同一の入
力を受信する場合、スレッドの状態は、異なる実行にお
いてその数の命令を実行後、常に同一である。従来技術
では、（例えばタイマの満了の結果）スレッドがあるラ
ンダムな位置においてプリエンプトされるとき、非決定
性が発生した。プリエンプション（強制排除）は、別の
スレッドＢ３７がスレッドＡ３２が後に読むであろう共
用変数３５を変更することを可能にし得る。プリエンプ
ションはスレッドＡ３２及びＢ３７の実行を順序付ける
ので、スレッドＡ３２が共用変数３５を読む前後に、ス
レッドＢ３７がその変更に着手するか否かに応じて、ス
レッドＡ３２は２つの異なる実行において、異なる値を
読み得る。これはプリエンプション位置により固有に決
定されるが、プリエンプション位置は、コンピュータの
タイマの不正確性及びＣＰＵの実行からのタイマの独立
性により、サーバ・レプリカに渡って再現可能でない。

【００２６】本発明では、プリエンプションは命令スラ
イスの満了時に発生する。従って、プリエンプションは
任意のサーバ・レプリカにおけるプログラムの任意の実
行の間に、同一位置において発生する。プリエンプショ
ンは、プログラムの結果に影響する非決定性の原因であ
るので、それらを任意のサーバ・レプリカにおける任意
のプログラム実行内で同一位置において発生させること
は、もしプログラムが同一の入力を受信すれば、プログ
ラムに同一の結果を生成させることになる。前述の例に
ついて考えてみよう。スレッドＢ３７がその第２の命令
スライスの間に変数を変更し、スレッドＡ３２がその第
３の命令スライスの間に変数を読出し、ラウンド・ロビ
ン・スケジューリングを想定する場合、スレッドＡ３２
は常に、スレッドＢ３７が共用変数３５を変更した後
に、それを読出すことになる。従って、命令スライスを
制御するために、同一の値ｐが使用される場合、結果は
全てのサーバ・レプリカに渡り決定的である。

【００２７】スケジューラ３１はまた、その命令スライ
スが満了する前に、ＣＰＵを放棄すると決定するとき、
スレッドをプリエンプトする。これは例えば、一般に知
られるように、スレッドが同期変数に従い中断するか、
ある入力を待機する場合に発生する。これらの事象は、
単一プロセッサ上では決定的である。なぜなら、スレッ
ドは各実行内での同一数の命令後、常に中断するか、入
力を待機するため、スケジューリングの決定的性質が保
存されるからである。

【００２８】マルチキャスト・プロトコルに関連するス
ケジューリング機構は、全てのサーバ・レプリカの同一
の実行を保証するために使用される。この属性を実現す
るために、マルチキャスト・プロトコルにより定義され
る順序に従い、スケジューリング機構がスレッドを順序
付けることが必要である。こうした一貫性が実現される
場合、スレッドは全て、マルチキャスト・プロトコルに
より定義された同一の順序に従い、スケジュールされる
ことになる。

【００２９】前述の特徴を可能にするため、このスケジ
ューリング機構は、許可制御窓（Admission Control Wi
ndow、ＡＣＷ）４０に関連付けられる。これは新たなク
ライアント要求が到来し、スケジューラのレディ・キュ
ー内に配置されるとき、新たなスレッドの生成を許可す
る方法を表す。ＡＣＷ４０はその開閉を制御する所定値
ｍを有する。値ｍは、命令スライスが満了する度に、１
減分する。ｍ個の命令スライスが満了後、サーバは新た
なマルチキャスト・ラウンドを待機する。新たなラウン
ドが使用可能なとき、そのラウンド内で使用可能な各要
求に対してスレッドが生成され、新たなスレッドがレデ
ィ・キュー３０内に入れられる。その時点から、決定的
スケジューラはサーバ・レプリカの実行が同一であるこ
とを保証する。

【００３０】当業者であれば、従来技術とは根本的に異
なる本発明の２つの特徴が理解できよう。

【００３１】第１に、ここでのマルチキャスト・プロト
コルの役割は、クライアント要求の実行に関する特定の
セマンティクス順序を強制することではない。代わり
に、マルチキャスト・プロトコルは、要求をサーバ内に
受け入れるために、同一の初期順序を定義する役目をす
る。従来技術では、マルチキャスト・プロトコルにより
指定される順序が拘束的であり、同時実行の結果が、マ
ルチキャスト順序に従う要求の直列化に一致しなければ
ならなかった。本発明では、たとえ特定の順序に一致し
なくても、全てのサーバ・レプリカの間で同一の順序を
要求する。当業者であれば、直列化が必要でなく（Cher
iton及びSkeenによる"Proceedings of theACM Symposiu
m on Operating Systems Principles"、1993参照）、本
発明が同一の考え方を採用することが理解できよう。

【００３２】第２に、サーバはスケジューリング決定
を、マルチキャスト・プロトコルにより定義される順序
に関連付ける。従来技術では、スケジューリング及び要
求の引渡しは常に独立であった。

【００３３】従って、ｍの選択は、非決定性を導入する
タイマの使用を回避する一方で、システムが外部事象及
びクライアント要求に対して、どの程度応答的であるか
を制御する。ｍの選択はまた、マルチキャスト・ラウン
ドの発生に関連付けられなければならない。特に、マル
チキャスト・ラウンドとＡＣＷとの間には、１対１の対
応が存在する。当業者であれば、ｍの値をマルチキャス
ト・ラウンドの発生頻度に一致させるように調整するこ
とは、特定の実施例ではかなり直接的であることが理解
できよう。

【００３４】マルチキャスト・ラウンドの発生頻度は、
調整可能である。有効なクライアント要求が存在しない
場合でも、要求を含まないマルチキャスト・ラウンドが
生成される。これらの空のラウンドは、全てのレプリカ
が同一のＡＣＷを通過することを保証することにより、
レプリカを同期させるために役立つ。これらのラウンド
はまた、従来技術で見られるように、故障検出のために
も使用され得る。

【００３５】スレッドは、ローカル・システム・サービ
ス（例えばファイルの読出し）が完了するのを待機する
ことを中断できる。こうした中断が発生するとき、スレ
ッドはその命令スライスを放棄し、もはやスケジューラ
のレディ・キュー３０の一部ではない。中断の理由がも
はや有効でないとき（例えばファイルの読出しが完了し
たとき）、一貫性を保証するために、レディ・キューへ
のスレッドの再入力が、サーバ・レプリカの間で調整さ
れなければならない。これは次のように達成される。ス
レッドがあるレプリカにおいて実行を再開する準備が整
うと、そのレプリカはこの事実を次のマルチキャスト・
ラウンドにおいて公示する（これはクライアント要求に
加えて出現する）。将来のラウンドにおいて、全てのレ
プリカが、その特定のスレッドをどこででも実行できる
準備完了状態となる。そのラウンドにおいて、スレッド
が再度実行キューに再挿入される。

【００３６】スケジューラ３１及びＡＣＷ４０の作用
は、更に図４を参照することにより理解される。この実
施例の論理フローに従い、スレッド・スケジューラの処
理が示される。一旦プロセスが開始すると、スケジュー
ラ３１及びマルチキャスト・プロトコル・スタックがブ
ロック５０で初期化され、カウンタ変数ｎが０にセット
される。ｎ変数は、サーバにおいて現在実行中の活動ク
ライアント要求の数をカウントする。スケジューラ３１
は次にブロック５２で、新たなマルチキャスト・ラウン
ドが使用可能か否かを判断する。使用可能な場合、スケ
ジューラ３１はブロック５４で新たな要求を許可する。
新たな要求が使用可能な場合、ｎ変数が１増分され、要
求を処理するスレッドが生成され、スレッドがスケジュ
ーラ３１に追加され、その後ブロック５２に戻る。この
プロセスは、使用可能な追加の新たなマルチキャスト要
求が無くなるまで継続する。スケジューラは次にブロッ
ク５８で、実行される要求が存在することを確認する。
キュー内にスレッドが存在する場合、スケジューラはブ
ロック６２で、スライス内の第１のスレッドから開始
し、各スレッドを実行する。この時、ブロック６０で、
ＡＣＷカウンタ変数ｊが０にセットされる。スレッドは
ブロック６２で、ｐ個の命令（または１スライス）を実
行するように、またはスレッドが中断するか、クライア
ントに応答するまで、実行するように指示される。各ス
ライスが実行されると、ブロック６４でＡＣＷカウンタ
変数が１増分される。このカウンタ変数が所定数ｍに達
したか否かがチェックされ、新たなマルチキャスト・ラ
ウンドがチェックされるべき時期を決定する。スレッド
・スライスは、この数に達するまで継続する。ブロック
６６で示されるように、ＡＣＷカウンタ変数がｍよりも
大きくなると、ＡＣＷが開き、新たなマルチキャスト・
ラウンドがブロック５２で受け入れられる。スケジュー
リング・プロセス全体は、無期限に継続する。

【００３７】スレッド・スケジューリングとマルチキャ
スト転送の前述の組み合わせは、サーバ・レプリカ８
４、８６及び８８がクライアント要求を同様に実行する
ことを保証する。例えば、命令のストリームとして、マ
ルチスレッド・プログラムの実行について考えてみよ
う。新たな要求がｍ命令スライス毎に、命令のストリー
ムに入れられる。全てのレプリカは、マルチキャストを
命令ストリーム内の同一ポイントにおいて受信し、マル
チキャスト・プロトコルはどこにおいても、順序付けら
れた確実な転送を保証するので、新たな要求は全てのレ
プリカにおいて、命令ストリーム内の同一のポイントに
おいて認められる。従って、対応するスレッドが、命令
ストリーム内の同一の実行ポイントにおいて開始し、任
意のレプリカのスレッド・スケジューラが、スレッドが
同様にスケジュールされることを保証する。決定的スレ
ッド・スケジューリングの使用により、スレッド実行の
インタリーブも、全てのレプリカにおいて同一である。

【００３８】本発明は完全機能型のリモート・メソッド
呼び出しシステムの状況において述べられたが、当業者
であれば、本発明の機構が任意の形態のプログラム製品
として、任意のタイプの情報処理システムに分散され、
本発明が実際に分散を実施するために使用される特定タ
イプの信号担持媒体に関係なく、同様に適用されること
が理解できよう。信号担持媒体の例には、フロッピー・
ディスクやＣＤ−ＲＯＭなどの記録可能型媒体、及びア
ナログ通信リンクまたはデジタル通信リンクなどの伝送
型媒体が含まれる。

【００３９】ＣＯＲＢＡ規格は現在、高可用性のために
自動フェール・オーバを保証するための活動的複製をサ
ポートしない。問題は困難である。なぜなら、ＣＯＲＢ
Ａオブジェクトはマルチスレッド型であり、複製時に同
一の実行を生成できないからである。ここで述べた本発
明は、この問題に対する解決策を提供するもので、ＣＯ
ＲＢＡ準拠のシステムの状況において、活動的複製の使
用を可能にし、従来システムにより提供されるのと同一
の高可用性をもたらす。本発明は特定の実施例に関連し
て述べられたが、この説明は限定的な意味で解釈される
べきではない。当業者であれば、本明細書を参照するこ
とにより、開示された実施例の様々な変更、並びに本発
明の代替実施例が明らかとなろう。例えば、図４ではＡ
ＣＷが別々のカウンタを有するように示されるが、スケ
ジューラとカウンタを共用することが可能であり、それ
によりＡＣＷは、全てのスケジュール済みスレッドが１
度実行された後に、開くことになる。従って、こうした
変更も、本発明の趣旨及び範囲から逸れることなく、実
施され得るものである。

【００４０】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００４１】（１）リモート・メソッド呼び出しシステ
ムにおける複製サポートのための方法であって、リモー
ト・プロシージャ呼び出しを通じて、複製サーバと通信
する複数のクライアントと、順序付けマルチキャスト・
プロトコルを介して、前記クライアントの前記リモート
・プロシージャ呼び出しを順序付けし、グループ化する
ステップと、前記リモート・プロシージャ呼び出しを前
記サーバ・レプリカに確実に、同一の順序で転送するス
テップと、前記各サーバ・レプリカにおいて、前記クラ
イアントの要求を、前記マルチキャスト・プロトコルに
より指定された順序に従い実行するスレッドを生成する
ステップと、全ての前記サーバ・レプリカにおいて、前
記クライアント要求に関連して命令スライスを割当てる
ことにより、前記スレッドを前記順序に従い、決定的且
つプリエンプティブにスケジュールするステップとを含
む、方法。 （２）前記クライアント要求をマルチキャスト・ラウン
ド内にグループ化し、順序付けるステップと、前記マル
チキャスト・ラウンド内の前記クライアント要求が実行
されるべき順序を指定するステップと、前記マルチキャ
スト・ラウンドを前記サーバ・レプリカに確実に前記順
序で転送するステップとを含む、前記（１）記載の方
法。 （３）前記命令スライス内に含まれる命令の数ｐを指定
するステップと、各命令の実行に対して１減分される命
令カウンタを使用するステップと、前記命令カウンタを
前記各命令スライスの初めにｐにセットするステップ
と、前記各命令スライスの初めに、前記スレッドをスケ
ジュールするステップと、前記カウンタがゼロ値に達す
るとき、割込みを生成するステップと、前記割込みを使
用し、新たな命令スライスの初めに、新たなスレッドの
スケジューリングを可能にするステップとを含む、前記
（１）記載の方法。 （４）前記マルチキャスト・プトロコルにより指定され
る順序に従い、前記スレッドをスケジューリング・キュ
ー内に配置するステップを含む、前記（３）記載の方
法。 （５）所与の前記スレッドがｐ個の命令を実行するか、
自発的に中断するまで、前記命令スライスを実行する、
前記（３）記載の方法。 （６）中断する所与のスレッドが、全てのレプリカが前
記マルチキャスト・ラウンドにおいて、前記スレッドが
実行キューに入力されるべきことに同意するまで、前記
実行キューへの再入力を許可されない、前記（３）記載
の方法。 （７）前記サーバ・レプリカが前記マルチキャスト・プ
ロトコル・ラウンドを介して、中断されたスレッドの準
備に関する情報を伝播する、前記（３）記載の方法。 （８）前記マルチキャスト・ラウンドの間に転送される
新たな要求の許可が、特定の数の前記命令スライスの実
行後にチェックされる、前記（４）記載の方法。 （９）前記マルチキャスト・ラウンドが、２つ毎の前記
マルチキャスト・ラウンド転送の間の前記命令スライス
の数を決定する数値定数の使用を通じて、新たなクライ
アント要求のスレッド・スケジューラの許可と同期され
る、前記（４）記載の方法。 （１０）前記数値定数に等しい数の前記命令スライスが
実行された後、新たなクライアント要求をサーバに許可
するステップと、前記クライアント要求を前記マルチキ
ャスト・プロトコルにより指定された順序で許可するス
テップと、前記マルチキャスト・ラウンドの転送の間を
除き、新たなクライアント要求の許可を禁止するステッ
プと、２つ毎の連続マルチキャスト・ラウンド間の、あ
る数値定数の前記命令スライスを追跡するステップと、
任意の２つの連続マルチキャスト間の前記命令スライス
が実行される度に、前記サーバの実行を停止するステッ
プと、空のマルチキャスト・ラウンドを生成し、進行、
故障検出及びレプリカ同期を保証するステップとを含
む、前記（８）記載の方法。 （１１）初期スレッド・スケジューリングが、前記マル
チキャスト・プロトコルにより指定される順序により決
定される、前記（１）記載の方法。 （１２）リモート・プロシージャ呼び出しを通じて、複
数のクライアントが複製サーバと通信する手段と、順序
付けマルチキャスト・プロトコルを介して、前記クライ
アントの前記リモート・プロシージャ呼び出しを順序付
けし、グループ化する手段と、前記リモート・プロシー
ジャ呼び出しを前記サーバ・レプリカに確実に、同一の
順序で転送する手段と、前記各サーバ・レプリカにおい
て、前記クライアントの要求を、前記マルチキャスト・
プロトコルにより指定された順序に従い実行するスレッ
ドを生成する手段と、全ての前記サーバ・レプリカにお
いて、前記クライアント要求に関連して命令スライスを
割当てることにより、前記スレッドを前記順序に従い、
決定的且つプリエンプティブにスケジュールする手段と
を含む、情報処理システム。 （１３）前記クライアント要求をマルチキャスト・ラウ
ンド内にグループ化し、順序付ける手段と、前記マルチ
キャスト・ラウンド内の前記クライアント要求が実行さ
れるべき順序を指定する手段と、前記マルチキャスト・
ラウンドを前記サーバ・レプリカに確実に前記順序で転
送する手段とを含む、前記（１２）記載の情報処理シス
テム。 （１４）前記命令スライス内に含まれる命令の数ｐを指
定する手段と、各命令の実行に対して１減分される命令
カウンタを使用する手段と、前記命令カウンタを前記各
命令スライスの初めにｐにセットする手段と、前記各命
令スライスの初めに、前記スレッドをスケジュールする
手段と、前記カウンタがゼロ値に達するとき、割込みを
生成する手段と、前記割込みを使用し、新たな命令スラ
イスの初めに、新たなスレッドのスケジューリングを可
能にする手段とを含む、前記（１３）記載の情報処理シ
ステム。 （１５）前記マルチキャスト・プトロコルにより指定さ
れる順序に従い、前記スレッドをスケジューリング・キ
ュー内に配置する手段を含む、前記（１４）記載の情報
処理システム。 （１６）所与の前記スレッドがｐ個の命令を実行する
か、自発的に中断するまで、前記命令スライスを実行す
る、前記（１５）記載の情報処理システム。 （１７）中断する所与のスレッドが、全てのレプリカが
前記マルチキャスト・ラウンドにおいて、前記スレッド
が実行キューに入力されるべきことに同意するまで、前
記実行キューへの再入力を許可されない、前記（１６）
記載の情報処理システム。 （１８）前記サーバ・レプリカが前記マルチキャスト・
プロトコル・ラウンドを介して、中断されたスレッドの
準備に関する情報を伝播する、前記（１７）記載の情報
処理システム。 （１９）前記マルチキャスト・ラウンドの間に転送され
る新たな要求の許可が、特定の数の前記命令スライスの
実行後にチェックされる、前記（１８）記載の情報処理
システム。 （２０）リモート・プロシージャ呼び出しを通じて、複
数のクライアントが複製サーバと通信する命令手段と、
順序付けマルチキャスト・プロトコルを介して、前記ク
ライアントの前記リモート・プロシージャ呼び出しを順
序付けし、グループ化する命令手段と、前記リモート・
プロシージャ呼び出しを前記サーバ・レプリカに確実
に、同一の順序で転送する命令手段と、前記各サーバ・
レプリカにおいて、前記クライアントの要求を、前記マ
ルチキャスト・プロトコルにより指定された順序に従い
実行するスレッドを生成する命令手段と、全ての前記サ
ーバ・レプリカにおいて、前記クライアント要求に関連
して命令スライスを割当てることにより、前記スレッド
を前記順序に従い、決定的且つプリエンプティブにスケ
ジュールする命令手段とを含む、コンピュータ・プログ
ラム。

【図面の簡単な説明】

【図１】本発明の好適な実施例に従うクライアントと複
製サーバ間の対話を表すブロック図である。

【図２】本発明の好適な実施例に従い、クライアントの
リモート・プロシージャ呼び出しを順序付けるための、
マルチキャスト・プロトコルのオペレーションを示すブ
ロック図である。

【図３】本発明に従う命令スライス式マルチスレッド・
スケジューラの１実施例を示すブロック図である。

【図４】本発明の１実施例に従い、命令スライスを用い
てスレッドをスケジュールすることに関連する、順序付
けマルチキャストの方法の論理フローを示すフロー図で
ある。

【符号の説明】

２４、４４、４６、４８ リモート・プロシージャ呼び
出し ３１ スケジューラ ３９ 命令カウンタ ４０ 許可制御窓（ＡＣＷ） ８４、８６、８８ サーバ・レプリカ ９２、９４、９６ クライアント １２０ マルチキャスト・ラウンド

Claims (20)

【特許請求の範囲】
1. 【請求項１】リモート・メソッド呼び出しシステムにお
   ける複製サポートのための方法であって、 リモート・プロシージャ呼び出しを通じて、複製サーバ
   と通信する複数のクライアントと、 順序付けマルチキャスト・プロトコルを介して、前記ク
   ライアントの前記リモート・プロシージャ呼び出しを順
   序付けし、グループ化するステップと、 前記リモート・プロシージャ呼び出しを前記サーバ・レ
   プリカに確実に、同一の順序で転送するステップと、 前記各サーバ・レプリカにおいて、前記クライアントの
   要求を、前記マルチキャスト・プロトコルにより指定さ
   れた順序に従い実行するスレッドを生成するステップ
   と、 全ての前記サーバ・レプリカにおいて、前記クライアン
   ト要求に関連して命令スライスを割当てることにより、
   前記スレッドを前記順序に従い、決定的且つプリエンプ
   ティブにスケジュールするステップとを含む、方法。
2. 【請求項２】前記クライアント要求をマルチキャスト・
   ラウンド内にグループ化し、順序付けるステップと、 前記マルチキャスト・ラウンド内の前記クライアント要
   求が実行されるべき順序を指定するステップと、 前記マルチキャスト・ラウンドを前記サーバ・レプリカ
   に確実に前記順序で転送するステップとを含む、請求項
   １記載の方法。
3. 【請求項３】前記命令スライス内に含まれる命令の数ｐ
   を指定するステップと、 各命令の実行に対して１減分される命令カウンタを使用
   するステップと、 前記命令カウンタを前記各命令スライスの初めにｐにセ
   ットするステップと、 前記各命令スライスの初めに、前記スレッドをスケジュ
   ールするステップと、 前記カウンタがゼロ値に達するとき、割込みを生成する
   ステップと、 前記割込みを使用し、新たな命令スライスの初めに、新
   たなスレッドのスケジューリングを可能にするステップ
   とを含む、請求項１記載の方法。
4. 【請求項４】前記マルチキャスト・プトロコルにより指
   定される順序に従い、前記スレッドをスケジューリング
   ・キュー内に配置するステップを含む、請求項３記載の
   方法。
5. 【請求項５】所与の前記スレッドがｐ個の命令を実行す
   るか、自発的に中断するまで、前記命令スライスを実行
   する、請求項３記載の方法。
6. 【請求項６】中断する所与のスレッドが、全てのレプリ
   カが前記マルチキャスト・ラウンドにおいて、前記スレ
   ッドが実行キューに入力されるべきことに同意するま
   で、前記実行キューへの再入力を許可されない、請求項
   ３記載の方法。
7. 【請求項７】前記サーバ・レプリカが前記マルチキャス
   ト・プロトコル・ラウンドを介して、中断されたスレッ
   ドの準備に関する情報を伝播する、請求項３記載の方
   法。
8. 【請求項８】前記マルチキャスト・ラウンドの間に転送
   される新たな要求の許可が、特定の数の前記命令スライ
   スの実行後にチェックされる、請求項４記載の方法。
9. 【請求項９】前記マルチキャスト・ラウンドが、２つ毎
   の前記マルチキャスト・ラウンド転送の間の前記命令ス
   ライスの数を決定する数値定数の使用を通じて、新たな
   クライアント要求のスレッド・スケジューラの許可と同
   期される、請求項４記載の方法。
10. 【請求項１０】前記数値定数に等しい数の前記命令スラ
    イスが実行された後、新たなクライアント要求をサーバ
    に許可するステップと、 前記クライアント要求を前記マルチキャスト・プロトコ
    ルにより指定された順序で許可するステップと、 前記マルチキャスト・ラウンドの転送の間を除き、新た
    なクライアント要求の許可を禁止するステップと、 ２つ毎の連続マルチキャスト・ラウンド間の、ある数値
    定数の前記命令スライスを追跡するステップと、 任意の２つの連続マルチキャスト間の前記命令スライス
    が実行される度に、前記サーバの実行を停止するステッ
    プと、 空のマルチキャスト・ラウンドを生成し、進行、故障検
    出及びレプリカ同期を保証するステップとを含む、請求
    項８記載の方法。
11. 【請求項１１】初期スレッド・スケジューリングが、前
    記マルチキャスト・プロトコルにより指定される順序に
    より決定される、請求項１記載の方法。
12. 【請求項１２】リモート・プロシージャ呼び出しを通じ
    て、複数のクライアントが複製サーバと通信する手段
    と、 順序付けマルチキャスト・プロトコルを介して、前記ク
    ライアントの前記リモート・プロシージャ呼び出しを順
    序付けし、グループ化する手段と、 前記リモート・プロシージャ呼び出しを前記サーバ・レ
    プリカに確実に、同一の順序で転送する手段と、 前記各サーバ・レプリカにおいて、前記クライアントの
    要求を、前記マルチキャスト・プロトコルにより指定さ
    れた順序に従い実行するスレッドを生成する手段と、 全ての前記サーバ・レプリカにおいて、前記クライアン
    ト要求に関連して命令スライスを割当てることにより、
    前記スレッドを前記順序に従い、決定的且つプリエンプ
    ティブにスケジュールする手段とを含む、情報処理シス
    テム。
13. 【請求項１３】前記クライアント要求をマルチキャスト
    ・ラウンド内にグループ化し、順序付ける手段と、 前記マルチキャスト・ラウンド内の前記クライアント要
    求が実行されるべき順序を指定する手段と、 前記マルチキャスト・ラウンドを前記サーバ・レプリカ
    に確実に前記順序で転送する手段とを含む、請求項１２
    記載の情報処理システム。
14. 【請求項１４】前記命令スライス内に含まれる命令の数
    ｐを指定する手段と、 各命令の実行に対して１減分される命令カウンタを使用
    する手段と、 前記命令カウンタを前記各命令スライスの初めにｐにセ
    ットする手段と、 前記各命令スライスの初めに、前記スレッドをスケジュ
    ールする手段と、 前記カウンタがゼロ値に達するとき、割込みを生成する
    手段と、 前記割込みを使用し、新たな命令スライスの初めに、新
    たなスレッドのスケジューリングを可能にする手段とを
    含む、請求項１３記載の情報処理システム。
15. 【請求項１５】前記マルチキャスト・プトロコルにより
    指定される順序に従い、前記スレッドをスケジューリン
    グ・キュー内に配置する手段を含む、請求項１４記載の
    情報処理システム。
16. 【請求項１６】所与の前記スレッドがｐ個の命令を実行
    するか、自発的に中断するまで、前記命令スライスを実
    行する、請求項１５記載の情報処理システム。
17. 【請求項１７】中断する所与のスレッドが、全てのレプ
    リカが前記マルチキャスト・ラウンドにおいて、前記ス
    レッドが実行キューに入力されるべきことに同意するま
    で、前記実行キューへの再入力を許可されない、請求項
    １６記載の情報処理システム。
18. 【請求項１８】前記サーバ・レプリカが前記マルチキャ
    スト・プロトコル・ラウンドを介して、中断されたスレ
    ッドの準備に関する情報を伝播する、請求項１７記載の
    情報処理システム。
19. 【請求項１９】前記マルチキャスト・ラウンドの間に転
    送される新たな要求の許可が、特定の数の前記命令スラ
    イスの実行後にチェックされる、請求項１８記載の情報
    処理システム。
20. 【請求項２０】リモート・プロシージャ呼び出しを通じ
    て、複数のクライアントが複製サーバと通信する命令手
    段と、 順序付けマルチキャスト・プロトコルを介して、前記ク
    ライアントの前記リモート・プロシージャ呼び出しを順
    序付けし、グループ化する命令手段と、 前記リモート・プロシージャ呼び出しを前記サーバ・レ
    プリカに確実に、同一の順序で転送する命令手段と、 前記各サーバ・レプリカにおいて、前記クライアントの
    要求を、前記マルチキャスト・プロトコルにより指定さ
    れた順序に従い実行するスレッドを生成する命令手段
    と、 全ての前記サーバ・レプリカにおいて、前記クライアン
    ト要求に関連して命令スライスを割当てることにより、
    前記スレッドを前記順序に従い、決定的且つプリエンプ
    ティブにスケジュールする命令手段とを含む、コンピュ
    ータ・プログラム。