(57)【特許請求の範囲】
【請求項１】
ｎ台（ｎは４以上の整数）のコンピュータを備え、当該ｎ台のコンピュータ上での決定性のプログラムの実行であって、当該コンピュータに与えられた入力と、その時点における当該コンピュータの状態とによって、出力と、次の当該コンピュータの状態とが一意的に決まる決定性のプログラムの実行を、整列マルチキャスト機構により多重化することによって、入力は前記整列マルチキャスト機構により前記ｎ台の各コンピュータに配送され、前記各コンピュータ上の前記プログラムは、その入力と、その時点における当該コンピュータの状態とによって動作する分散コンピュータシステムにおいて、
前記各コンピュータは、
コンピュータの状態を表す複数の状態変数を保存するための状態データ記憶部が割り当てられた不揮発性の記憶装置と、
前記プログラムからの状態読み出し要求に応じて、要求された状態変数の読み出し要求を自コンピュータを含む前記ｎ台のコンピュータに対して発行し、前記ｎ台のコンピュータのうちのｎ−ｆ台（ｆは故障停止が許容される最大のコンピュータ数で、且つ３ｆ＜ｎを満足する最大の整数）のコンピュータから当該コンピュータの前記状態データ記憶部に保存されている要求された状態変数の値を読み出したならば、ｎ−ｆ個の状態変数の値のうち最も多い値を、前記状態読み出し要求に対する最終的な読み出し値と決定する読み出し多数決手段と
を具備することを特徴とする分散コンピュータシステム。
【請求項２】
前記各コンピュータは、前記読み出し多数決手段により決定された最終的な読み出し値と、自コンピュータの前記不揮発性記憶装置内の前記状態データ記憶部に保存されている前記要求された状態変数の値とを比較し、値が異なっている場合には、当該状態データ記憶部内の状態変数の値を前記最終的な読み出し値に書き換える書き換え手段を更に具備することを特徴とする請求項１に記載の分散コンピュータシステム。
【請求項３】
前記各コンピュータは、前記プログラムからの状態書き込み要求に応じて、要求された状態変数の値を自コンピュータの前記不揮発性記憶装置内の前記状態データ記憶部に書き込んだ場合、前記ｎ台のコンピュータのうちのｎ−ｆ台のコンピュータで自コンピュータと同一の書き込みが行われるのを待って前記要求された書き込み処理を完了する書き込み待ち合わせ手段を更に具備することを特徴とする請求項１に記載の分散コンピュータシステム。
【請求項４】
不揮発性の記憶装置を有するｎ台（ｎは４以上の整数）のコンピュータから構成され、当該ｎ台のコンピュータ上での決定性のプログラムの実行であって、当該コンピュータに与えられた入力と、その時点における当該コンピュータの状態とによって、出力と、次の当該コンピュータの状態とが一意的に決まる決定性のプログラムの実行を、整列マルチキャスト機構により多重化することによって、入力は前記整列マルチキャスト機構により前記ｎ台の各コンピュータに配送され、前記各コンピュータ上の前記プログラムは、その入力と、その時点における当該コンピュータの状態とによって動作する分散コンピュータシステムにおけるコンピュータ状態の多重化記憶方法であって、
コンピュータの状態を表す複数の状態変数の値を前記各コンピュータの前記不揮発性記憶装置に保存し、
前記プログラムからの状態読み出し要求時には、要求された状態変数の読み出し要求を前記ｎ台のコンピュータに対して発行することにより、前記ｎ台のコンピュータのうちのｎ−ｆ台（ｆは故障停止が許容される最大のコンピュータ数で、且つ３ｆ＜ｎを満足する最大の整数）のコンピュータから当該コンピュータの前記不揮発性記憶装置に保存されている要求された状態変数の値を読み出したならば、ｎ−ｆ個の状態変数の値のうち最も多い値を、前記状態読み出し要求に対する最終的な読み出し値と決定する
ことを特徴とするコンピュータ状態の多重化記憶方法。
【請求項５】
前記決定された最終的な読み出し値と、前記不揮発性記憶装置に保存されている前記要求された状態変数の値とを比較し、値が異なっている場合には、当該不揮発性記憶装置内の状態変数の値を前記最終的な読み出し値に書き換えることを特徴とする請求項４記載のコンピュータ状態の多重化記憶方法。
【請求項６】
前記プログラムからの状態書き込み要求に応じて、要求された状態変数の値を前記不揮発性記憶装置に書き込んだ場合、前記ｎ台のコンピュータのうちのｎ−ｆ台のコンピュータで自コンピュータと同一の書き込みが行われるのを待って前記要求された書き込み処理を完了することを特徴とする請求項４記載のコンピュータ状態の多重化記憶方法。
【請求項７】
不揮発性の記憶装置を有するｎ台（ｎは４以上の整数）のコンピュータから構成され、当該ｎ台のコンピュータ上での決定性のプログラムの実行であって、当該コンピュータに与えられた入力と、その時点における当該コンピュータの状態とによって、出力と、次の当該コンピュータの状態とが一意的に決まる決定性のプログラムの実行を、整列マルチキャスト機構により多重化することによって、入力は前記整列マルチキャスト機構により前記ｎ台の各コンピュータに配送され、前記各コンピュータ上の前記プログラムは、その入力と、その時点における当該コンピュータの状態とによって動作する分散コンピュータシステムに適用される、コンピュータ状態の多重化記憶プログラムを記憶したコンピュータ読み取り可能な記憶媒体であって、
前記コンピュータに、
コンピュータの状態を表す複数の状態変数の値を前記不揮発性記憶装置に保存する機能と、
前記プログラムからの状態読み出し要求時には、要求された状態変数の読み出し要求を前記ｎ台のコンピュータに対して発行することにより、前記ｎ台のコンピュータのうちのｎ−ｆ台（ｆは故障停止が許容される最大のコンピュータ数で、且つ３ｆ＜ｎを満足する最大の整数）のコンピュータから当該コンピュータの前記不揮発性記憶装置に保存されている要求された状態変数の値を読み出したならば、ｎ−ｆ個の状態変数の値のうち最も多い値を、前記状態読み出し要求に対する最終的な読み出し値と決定する機能と
を実現させるためのコンピュータ状態の多重化記憶プログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、４台以上のコンピュータが結合した分散コンピュータシステムに係り、特に決定性（deterministic）のプログラムの実行を整列マルチキャスト機構を用いて多重化する分散コンピュータシステム及び同システムにおけるコンピュータ状態の多重化記憶方法に関する。
【０００２】
【従来の技術】
複数のコンピュータがネットワーク等により接続された分散コンピュータシステムとして、各コンピュータ上での決定性のプログラムの実行を整列マルチキャスト機構により多重化することで、各コンピュータの状態を同一に保ち、出力列も同一とするように構成された分散コンピュータシステムが知られている。以下、この種の分散コンピュータシステムで適用される、決定性のプログラム、整列マルチキャスト機構及び多重化の意義について説明する。
【０００３】
決定性のプログラムは次のように説明される。
まず、プログラムの実行は、コンピュータに入力が与えられると、そのときのコンピュータの状態によって、出力と、次の状態を求めるものであると考えることができる。そして、決定性のプログラムは、実行時に、出力と、次の状態が一意的に決まるプログラムとして定義される。決定性のプログラムは具体的には、不定値や乱数の参照がないプログラムのことをいう。
【０００４】
決定性のプログラムの特徴は、初期状態と入力列が決まれば、その動作が一意的であることにある。以下の説明では、プログラムと称するとき、決定性のプログラムのことを指す。
【０００５】
また、整列マルチキャスト機構は、次のように説明される。
まず、複数のコンピュータが結合した分散コンピュータシステムのような環境では、それぞれのコンピュータが独立して動作する。したがって、これらのコンピュータを同期的に動作させる場合には、特別な仕組みが必要である。整列マルチキャスト機構は、分散システムへの入力を全てのコンピュータに配送する仕組みであり、データの到着順序が、全てのコンピュータで同じであることを保証する。
【０００６】
更に、多重化は、次のように説明される。
まず、分散コンピュータシステムでは、それぞれのコンピュータが独立に故障する可能性がある。仮に、１つのコンピュータが故障しただけでシステム全体が機能しない場合は、分散コンピュータシステムの稼働率は１台のコンピュータの稼働率よりも低くなってしまう。
【０００７】
かかる事態を防止するために、システム全体に係わる処理は多重化することが必要である。逆に、多重化することによって、分散システムの稼働率を１台のコンピュータの稼働率よりも高くすること可能とある。
【０００８】
例えば、稼働率９９％のコンピュータ１０台で構成する分散コンピュータシステムが全く多重化されていないとすると、その分散コンピュータシステムの稼働率は９０％程度である。もし、それが、多重化によって、３台の故障まで耐え得るとすると、稼働率は、９９．９９９８％程度となる。
【０００９】
次に、整列マルチキャスト機構を用いた決定性のプログラムの実行の多重化方法について説明する。ここでは、４台のコンピュータを有する分散コンピュータシステムにおいて、プログラムの実行を整列マルチキャスト機構を用いて多重化する例を挙げる。
【００１０】
まず、システム内の全てのコンピュータは、同一の初期状態から始まる。
入力されるデータは、必ず整列マルチキャスト機構を通して、全てのコンピュータに入力順に配送され、つまり整列マルチキャストされて、各コンピュータ上のそれぞれのプログラムが当該データに基づき動作する。
【００１１】
このシステムでは、各コンピュータの出力のうち、いずれか１台のコンピュータの出力が、システムの出力とされる。
【００１２】
各プログラムへの入力列は、整列マルチキャスト機構により同一順序となっている。したがって、決定性のプログラムの特徴により、全てのコンピュータの状態が同一に保たれ、出力列も全て同じとなる。つまり、プログラムの実行が多重化される。
【００１３】
上記の整列マルチキャスト機構による多重化の説明では、システム内の全てのコンピュータが初めから稼働していることを前提とした。しかし、実際には途中から多重化を始めなければならない場合もある。例えば、故障していたコンピュータが復旧した場合である。この場合には、整列マルチキャスト機構による多重化の拡大が必要である。
【００１４】
かかる整列マルチキャスト機構による多重化の拡大について説明する。
まず第１のステップとして、整列マルチキャスト機構による整列マルチキャストを一時停止する。
次に第２のステップ２として、故障から復旧してシステムに組み込まれるコンピュータに、現在稼働中のいずれかのコンピュータからコンピュータ状態をコピーする。
最後に第３のステップ３として、整列マルチキャストを再開する。
【００１５】
この方式では、整列マルチキャストを一時停止することにより、コンピュータ状態が変化しないようにした上で、当該コンピュータ状態をコピーしている。このため、整列マルチキャストを再開したときに、全てのコンピュータが同一の動作を始めることができる。つまり、状態をコピーしている間は、プログラムの実行が一時的に停止される。
【００１６】
また、上記の整列マルチキャスト機構による多重化の説明では、システム内の全てのコンピュータが同一の初期状態から始まることを前提とした。しかし、ディスク装置などの不揮発性の記憶装置に、前回のプログラムの実行の状態を保存することで、立ち上げ時にその続きを行いたい場合がある。この場合には、立ち上げ時に、全てのコンピュータに保存されているデータが同一であるとは限らなくなる。
【００１７】
従来の分散コンピュータシステムでは、このデータを一致化するため、システム内で最後まで動作していたコンピュータに保存されている最新の状態を、他のコンピュータにコピーしてから多重化を開始していた。
【００１８】
【発明が解決しようとする課題】
このように、従来の分散コンピュータシステムにおいて適用されている整列マルチキャストを用いたコンピュータ状態の多重化記憶方法では、通常時はコンピュータ状態のコピーを必要としないものの、システムへのコンピュータの組み込み時や立ち上げ時にはコンピュータ状態のコピーが必要となる場合があった。特に、ディスク装置などの大容量不揮発性記憶装置に保存された状態データの場合には、そのコピーには長時間を必要とするため、実用上問題となる虞があった。
【００１９】
本発明は上記事情を考慮してなされたものでその目的は、コンピュータ組み込み時や、立ち上げ時のコンピュータ状態のコピーを不要とすることができる分散コンピュータシステム及び同システムにおけるコンピュータ状態の多重化記憶方法を提供することにある。
【００２０】
【課題を解決するための手段】
本発明は、ｎ台のコンピュータを備え、当該ｎ台のコンピュータ上での決定性のプログラムの実行を整列マルチキャスト機構により多重化する分散コンピュータシステムにおいて、上記各コンピュータに、コンピュータの状態を表す複数の状態変数を保存するための状態データ記憶部が割り当てられた不揮発性の記憶装置と、上記プログラムからの状態読み出し要求に応じて、上記ｎ台のコンピュータのうちのｎ−ｆ台（ｆは３ｆ＜ｎを満足する最大の整数）のコンピュータから当該コンピュータの上記状態データ記憶部に保存されている要求された状態変数の値を読み出し、ｎ−ｆ個の状態変数の値のうち最も多い値を、上記状態読み出し要求に対する最終的な読み出し値と決定する読み出し多数決手段とを設けたことを特徴とする。
【００２１】
本発明によれば、分散コンピュータシステム内の各コンピュータにおいて、プログラムからの状態読み出し要求に対して、ｎ−ｆ台のコンピュータからの読み出しは必要となるものの、コンピュータ組み込み時や立ち上げ時のコピーを不要とすることができる。
【００２２】
ここで、揮発性の記憶装置に状態データ記憶部を割り当てて、コンピュータの状態を表す複数の状態変数のうち、アクセス頻度が高い方から一定数の状態変数を当該揮発性記憶装置内の状態記憶部に保持し、残りを上記不揮発性記憶装置内の状態記憶部に保存する構成とするならば、読み出し量を減らして最適な性能を得ることができる。
【００２３】
また、上記不揮発性記憶装置内の状態記憶部の一部の写しを保持するキャッシュメモリ（状態データキャッシュメモリ）が追加された構成としても、読み出し量を減らして最適な性能を得ることができる。
【００２４】
また上記各コンピュータに、次の書き換え手段、即ち上記読み出し多数決手段により決定された最終的な読み出し値と、自コンピュータの不揮発性記憶装置内の状態データ記憶部に保存されている上記要求された状態変数の値とが異なっている場合に、当該状態データ記憶部内の状態変数の値を上記最終的な読み出し値に書き換える書き換え手段を追加するならば、ｎ−ｆ台のコンピュータのうちの多数を占めるｎ−２ｆ台で、常に最新の値データを保持することができる。この理由については、説明の重複を避けるため、発明の実施の形態の欄で述べる。
【００２５】
また上記各コンピュータに、次の書き込み待ち合わせ手段、即ちプログラムからの状態書き込み要求に応じて、要求された状態変数の値を自コンピュータの上記不揮発性記憶装置内の状態データ記憶部に書き込んだ場合に、上記ｎ台のコンピュータのうちのｎ−ｆ台のコンピュータで自コンピュータと同一の書き込みが行われるのを待って上記要求された書き込み処理を完了する書き込み待ち合わせ手段を持たせるとよい。
【００２６】
また上記書き換え手段が追加されたｎ台のコンピュータのうち最大でｆ台のコンピュータで故障が発生した場合、そのコンピュータの不揮発性記憶装置のデータが消失している場合を考慮して、その故障したｆ台のコンピュータを停止させた状態で、稼働中の少なくともｎ−ｆ台のコンピュータにおいて、上記プログラムの実行と並行して、不揮発性記憶装置内の状態データ記憶部からの全状態変数の読み出しが行われる構成とするとよい。
【００２７】
このような構成においては、読み出し多数決手段と書き換え手段の動作とにより、少なくともｎ−ｆ台のコンピュータに最新のコンピュータの状態を保持させることができる。したがって、この段階で故障から復旧したコンピュータをシステムに組み込んでも、状態のコピーは必要ない。
【００２８】
なお、以上に述べた装置（分散コンピュータシステム）に係る本発明は方法（コンピュータ状態の多重化記憶方法）に係る発明としても成立する。
また、以上に述べた装置に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（或いはコンピュータを当該発明に相当する手段として機能させるための、或いはコンピュータに当該発明に相当する機能を実現させるための）プログラム（コンピュータ状態の多重化記憶プログラム）を記憶したコンピュータ読み取り可能な記憶媒体としても成立する。
【００２９】
【発明の実施の形態】
以下、本発明の実施の形態につき図面を参照して説明する。
【００３０】
［第１の実施形態］
図１は本発明の第１の実施形態に係る分散コンピュータシステムの構成を示すブロック図である。
図１の分散コンピュータシステムは、ｎ台（ここではｎ＝４）のコンピュータ＃１〜＃Ｎ、即ちコンピュータ１０-1〜１０-n（１０-4）と、これらの各コンピュータを結合するネットワーク２０とから構成されている。
【００３１】
各コンピュータ（＃ｉ）１０-i（ｉ＝１〜ｎ）は、不揮発性記憶装置としての磁気ディスク装置１１を備えている。この磁気ディスク装置１１には、コンピュータの状態を保存するための状態データ記憶部１２が割り当てられている。コンピュータの状態は、複数の状態変数の値データによって構成されると考えることができる。したがって状態データ記憶部１２には、コンピュータの状態として、それぞれの状態変数の値データが記憶される。
【００３２】
各コンピュータ１０-i（＃ｉ）はまた、整列マルチキャスト用単位モジュール１３、読み出し多数決部１４及び書き込み待ち合わせ部１５を備えている。整列マルチキャスト用単位モジュール１３、読み出し多数決部１４及び書き込み待ち合わせ部１５は、オペレーティングシステム（ＯＳ）とアプリケーション（アプリケーションプログラム）との間に位置するソフトウェア、即ちミドルウェアにより実現される。
【００３３】
各コンピュータ１０-iの整列マルチキャスト用単位モジュール１３は、互いに連携して動作することで、整列マルチキャスト機構１６を実現する。この整列マルチキャスト機構１６により、各コンピュータ１０-i上のプログラム（決定性のプログラム）１７の実行が多重化される。
【００３４】
読み出し多数決部１４は、当該読み出し多数決部１４が置かれているコンピュータ１０-i上のプログラム１７が磁気ディスク装置１１内の状態データ記憶部１２から状態変数を読み出すときに動作して、図１の分散コンピュータシステムを構成するｎ台のコンピュータのうちのｎ−ｆ台のコンピュータから同じ種類の状態変数の値を読み出し、最も多い値を最終的な読み出し値としてプログラム１７に渡す。ここで、ｆは３ｆ＜ｎとなる最大の整数である。例えば、図１のシステムのようにｎ＝４であるならば、ｆ＝１である。また、ｎ＝１０ならばｆ＝３である。
【００３５】
書き込み待ち合わせ部１５は、当該書き込み待ち合わせ部１５が置かれているコンピュータ１０-i上のプログラム１７が磁気ディスク装置１１内の状態データ記憶部１２に状態変数を書き込むときに動作して、図１の分散コンピュータシステムを構成するｎ台のコンピュータのうちのｎ−ｆ台のコンピュータで自コンピュータと同一の書き込みが行われるのを待って状態変化数の書き込み処理を完了する。
【００３６】
さて本実施形態では、分散コンピュータシステムを構成するコンピュータの台数がｎ台の場合、ｆ台までの故障停止が許容されるものとする。つまり、整列マルチキャスト機構１６により多重化されるプログラム１７は、少なくともｎ−ｆ台のコンピュータ上で実行される。
また、ｆ＋１台以上の故障停止が発生した場合には、多重化されたプログラムの実行は継続しない（いわゆるフェイルストップとする）ものとする。
この前提はシステムの稼働率に制限を設けるものであるが、ｎ＝１０の場合を例にとると、従来の技術の欄で述べた稼働率の計算から明らかなように、実用上全く問題ないといえる。
【００３７】
ここで、各コンピュータ１０-i（i＝１〜ｎ）の読み出し多数決部１４の動作について、図２のフローチャートを参照して説明する。
まず、コンピュータ１０-i上のプログラム１７から状態変数の読み出しが要求されると、読み出し多数決部１４は当該読み出し要求を受け付ける（ステップＳ１）。この場合、読み出し多数決部１４は、以下に述べる読み出し要求に対して応答を返したコンピュータ＃j（ｊは１〜Ｎのいずれか）の数をカウントするための変数ｃｏｕｎｔと、各コンピュータ＃１〜＃Ｎからの読み出しデータを保持するデータ領域ｄａｔａ“１”〜ｄａｔａ“Ｎ”とを０（ｎｕｌｌ値）に初期化する（ステップＳ２）。変数ｃｏｕｎｔの領域とデータ領域ｄａｔａ“１”〜ｄａｔａ“Ｎ”とは、揮発性の記憶装置、例えば図示せぬ主記憶のワーク領域上に確保される。
【００３８】
次に読み出し多数決部１４は、自コンピュータを含む各コンピュータ＃１〜＃Ｎに対し、上記プログラム１７により要求された状態変化数の読み出し要求を発行する（ステップＳ３）。そして読み出し多数決部１４は、読み出し要求に対する、コンピュータ＃１〜＃Ｎのうちのいずれかのコンピュータ＃jからの応答を待つ（ステップＳ４）。
【００３９】
一方、各コンピュータ＃１〜＃Ｎは、コンピュータ＃iの読み出し多数決部１４からの読み出し要求に応じて、自コンピュータの磁気ディスク装置１１内の状態データ記憶部１２に保存されている状態変数のうち、要求された状態変数の値データを読み出して要求元に返す。
【００４０】
読み出し多数決部１４は、自身の発行した読み出し要求に対してコンピュータ＃１〜＃Ｎのうちのいずれかのコンピュータ＃jから応答が返されると、当該コンピュータ＃jから返された読み出しデータをデータ領域ｄａｔａ“ｊ”に設定すると共に、変数ｃｏｕｎｔを１だけインクリメントする（ステップＳ５）。
【００４１】
読み出し多数決部１４は以上のステップＳ４，Ｓ５の処理を、変数ｃｏｕｎｔの値がｎ−ｆ以上となるまで繰り返す（ステップＳ６）。そして変数ｃｏｕｎｔの値がｎ−ｆ以上となると、即ち任意の合計ｎ−ｆ台のコンピュータから当該コンピュータの状態データ記憶部１２に保存されている（プログラム１７から）要求された状態変数の値データを受け取ると、データ領域ｄａｔａ“１”〜ｄａｔａ“Ｎ”に設定されているデータのうちのｎｕｌｌ値でないもので、最も多い値のデータを正しい読み出しデータと決定する（ステップＳ７）。ここで、ステップＳ４，Ｓ５の処理の繰り返し回数をｎ−ｆ以上としたのは、本実施形態の前提により、ｎ台のコンピュータのうち少なくともｎ−ｆ台のコンピュータが動作していることによる。
【００４２】
次に、各コンピュータ１０-i（i＝１〜ｎ）の書き込み待ち合わせ部１５の動作について、図３のフローチャートを参照して説明する。
まず、コンピュータ１０-i上のプログラム１７から状態変数の書き込みが要求されると、書き込み待ち合わせ部１５は当該書き込み要求を受け付けて（ステップＳ１１）、要求された状態変数の値データを自コンピュータの状態データ記憶部１２に書き込む（ステップＳ１２）。
【００４３】
次に書き込み待ち合わせ部１５は、書き込み完了を示す完了可フラグをセットし（ステップＳ１３）、以下に述べる書き込み待ち合わせ要求に対して応答を返したコンピュータ＃ｊ（ｊは１〜Ｎのいずれか）の数をカウントするための変数ｃｏｕｎｔを０に初期化する（ステップＳ１４）。
【００４４】
次に書き込み待ち合わせ部１５は、各コンピュータ＃１〜＃Ｎに対し、上記プログラム１７により要求された状態変数の書き込み待ち合わせ要求を発行する（ステップＳ１５）。そして書き込み待ち合わせ部１５４は、書き込み待ち合わせ要求に対する、コンピュータ＃１〜＃Ｎのうちのいずれかのコンピュータ＃ｊからの応答を待つ（ステップＳ１６）。
【００４５】
以上の動作は、（稼働状態にある）各コンピュータ１０-iの書き込み待ち合わせ部１５で行われる。
【００４６】
さて、各コンピュータ＃１〜＃Ｎの応答プロセスは、他のコンピュータの書き込み待ち合わせ部１５から書き込み待ち合わせが要求されると、自コンピュータの完了可フラグがセットされているか否か、即ち書き込み待ち合わせの要求元での書き込みと同一の状態変数の書き込みが終了しているか否かを判定する（ステップＳ１９）。もし、完了可フラグがセットされているならば、書き込み待ち合わせ要求元に応答を返して、当該フラグをリセットする（ステップＳ２０，Ｓ２１）。これに対し、完了可フラグがセットされていないならば、コンピュータ＃１〜＃Ｎの応答プロセスは待ち（ＷＡＩＴ）状態となる（ステップＳ２２）。この待ち状態は、自コンピュータでの書き込みが完了して完了可フラグがセットされると（ステップＳ１２，Ｓ１３）、書き込み待ち合わせ部１５からの割り込み（“ＷＡＫＥ  ＵＰ”割り込み）により解除される。この場合、ステップＳ１９の判定が再び行われ、今度は完了可フラグはセットされていることから、書き込み待ち合わせ要求元に応答が返され、当該フラグがリセットされる（ステップＳ２０，Ｓ２１）。
【００４７】
書き込み待ち合わせ部１５は、自身の発行した書き込み要求に対してコンピュータ＃１〜＃Ｎのうちのいずれかのコンピュータ＃ｊから応答が返されると、変数ｃｏｕｎｔを１だけインクリメントする（ステップＳ１７）。
【００４８】
書き込み待ち合わせ部１５は以上のステップＳ１６，Ｓ１７の処理を、変数ｃｏｕｎｔの値がｎ−ｆ以上となるまで繰り返す（ステップＳ１８）。そして変数ｃｏｕｎｔの値がｎ−ｆ以上となると、即ち任意の合計ｎ−ｆ台のコンピュータで、自身と同様の書き込みが行われるのを待ち合わせると、一連の状態変数の書き込み処理を完了する。ここで、ステップＳ１６，Ｓ１７の処理の繰り返し回数をｎ−ｆ以上としたのは、先の読み出し多数決部１４の動作でも述べたように、本実施形態の前提により少なくともｎ−ｆ台のコンピュータが動作していることによる。
【００４９】
以上に述べた実施形態によれば、故障から復旧したコンピュータをシステムに組み込む多重化の拡大時、及びシステムの立ち上げ時も含めて、一切、コンピュータの状態（状態変数）のコピーを必要としないという格別な効果を得ることができる。以下に、その理由を説明する。
【００５０】
まず、上記の効果が得られることの正当性は、読み出し多数決部１４が常に最新の状態を読み出すことを示せばよい。ここで、最新の状態とは、それぞれの状態変数に最も最近に書き込まれた値データということになる。
【００５１】
まず、状態データ記憶部１２は磁気ディスク装置１１（不揮発性の記憶装置）上に確保されているため、当該状態データ記憶部１２に一度書き込まれたデータは消滅することはない。これは、コンピュータ１０-iが一時的に停止し、再開した場合でも当てはまる。
【００５２】
そして、状態変数の書き込みは、書き込み待ち合わせ部１５によって、少なくともｎ−ｆ台のコンピュータの状態データ記憶部１２に反映されていることが保証されている。
【００５３】
したがって、最新の値データは、（現時点で動作していないコンピュータが含まれるかもしれないが）少なくともｎ−ｆ台のコンピュータの状態データ記憶部１２に保存されていることになる。
【００５４】
一方、読み出し多数決部１４は、ｎ−ｆ台のコンピュータの状態データ記憶部１２から値データを読み出す。ここで値データが読み出されたｎ−ｆ台のコンピュータは、最新の値データを保存するｎ−ｆ台のコンピュータとは、異なるかもしれないが、それらのうち、少なくともｎ−２ｆ台はオーバーラップする。この様子を図４に示す。
【００５５】
したがって、読み出し多数決部１４は、少なくともｎ−２ｆ個の最新の値データを取得していることになる。
【００５６】
実は、ｎ−２ｆ個はｎ−ｆ個のうちの過半数を占めている。なぜなら、ｆの定義より３ｆ＜ｎなので、
２（ｎ−２ｆ）−（ｎ−ｆ）＝ｎ−３ｆ＞０
となるからである。
【００５７】
以上により、読み出し多数決部１４がｎ−ｆ台のコンピュータから読み出す同一状態変数のｎ−ｆ個の値データのうち、少なくともｎ−２ｆ個の値データは最新の値データであり、しかもｎ−ｆ個のうちの多数（過半数）を占めることは明白である。よって読み出し多数決部１４は、常に多数を占める最新の値データを取得する。
【００５８】
［第２の実施形態］
前記した第１の実施形態に係る分散コンピュータシステムは、次の２つの理由により、通常時の性能が、従来のシステムより少し落ちる。
【００５９】
（１）コンピュータの状態を、ランダムアクセスメモリ（ＲＡＭ）等の揮発性の記憶装置ではなくて、当該記憶装置に比べてアクセス性能が遅い磁気ディスク装置１１（不揮発性の記憶装置）に保存している。
（２）コンピュータ状態（状態変数）の読み出しが、ｎ−ｆ台のコンピュータを対象に行われるため、従来に比べて読み出し量がｎ−ｆ倍となる。
【００６０】
そこで、前記第１の実施形態の特徴を生かしながら、読み出し量を減らして最適な性能を得ることができるようにした本発明の第２の実施形態について、図面を参照して説明する。
【００６１】
図５は本発明の第２の実施形態に係る分散コンピュータシステムを構成するコンピュータ５０-iのブロック構成を示す。なお、図１中の１０-1〜１０-n（１０-4）と同一部分には同一符号を付してある。
【００６２】
図５のコンピュータ５０-iが、図１中のコンピュータ１０-1〜１０-n（１０-4）と異なる点は、例えば主記憶を構成するＲＡＭ等の揮発性メモリ５１内に、磁気ディスク装置１１内の状態データ記憶部１２に相当する状態データ記憶部５２を割り当てて、当該状態データ記憶部５２に状態変数をアクセス頻度が高い方から一定数を格納し、残りのアクセス頻度が低い状態変数だけを磁気ディスク装置１１内の状態データ記憶部１２に保存する構成としたことである。ここで、状態データ記憶部５２に格納されるアクセス頻度が高い状態変数は、状態データ記憶部１２に保存されるアクセス頻度が低い状態変数より十分少ない数に設定されている。
【００６３】
この構成では、メモリ５１内の状態データ記憶部５２に格納されている状態変数、つまりアクセス頻度が高い状態変数については、システムへのコンピュータの組み込み時（多重化の拡大時）等において、従来と同様にコピーが必要となる。しかし、コピーが必要となる状態変数、即ちアクセス頻度が高い状態変数は、状態データ記憶部１２に保存されるアクセス頻度が低い状態変数より十分に少ないため、全ての状態変数についてコピーが必要となる従来システムと比べて、コピーに要する時間が少なくて済む。
【００６４】
更に、ｎ−ｆ台のコンピュータからの読み出しが必要となる状態データ記憶部１２内の状態変数については、数は多くてもアクセス頻度が低い。したがって、全ての状態変数についてｎ−ｆ台のコンピュータからの読み出しが必要となる前記第１の実施形態に比べて、読み出し量が著しく減少する。
【００６５】
このように本実施形態においては、アクセス頻度が高い少数の状態変数を従来方式で処理し、残りのアクセス頻度の低い多数の状態変数を前記第１の実施形態で適用した方式で処理することにより、最適な性能を得ることができる。
【００６６】
［第３の実施形態］
次に、本発明の第３の実施形態について、図面を参照して説明する。
図６は本発明の第３の実施形態に係る分散コンピュータシステムを構成するコンピュータ６０-iのブロック構成を示す。なお、図５のコンピュータ５０-iと同一部分には同一符号を付してある。
【００６７】
図６のコンピュータ６０-iが図５のコンピュータ５０-iと異なる点は、磁気ディスク装置１１内の状態データ記憶部１２には、前記第１の実施形態（におけるコンピュータ１０-1〜１０-n）と同様に全ての状態変数を保存すると共に、当該状態データ記憶部１２の一部の写しを保持するキャッシュメモリ（以下、状態データキャッシュと称する）６２を、メモリ５１内の状態データ記憶部５２に代えて設けたことである。
【００６８】
この構成では、状態データ記憶部１２の一部の写しである、状態データキャッシュ６２に保持されている状態変数は、システムへのコンピュータの組み込み時（多重化の拡大時）等において、稼働中のコンピュータのいずれか１つのコンピュータからシステムに組み込むコンピュータ（の状態データキャッシュ６２）へのコピーが必要となる。しかし、このコピーが必要となる状態変数は、全状態変数の一部であるため、全ての状態変数についてコピーが必要となる従来システムと比べて、コピーに要する時間が少なくて済む。
【００６９】
更に、自コンピュータのプログラム１７から読み出しが要求され、且つ要求された状態変数が状態データキャッシュ６２に存在するキャッシュヒット時には、前記第１の実施形態と異なってｎ−ｆ台のコンピュータからの読み出しが不要となる。したがって、全ての状態変数についてｎ−ｆ台のコンピュータからの読み出しが必要となる前記第１の実施形態に比べて、読み出し量が著しく減少する。
【００７０】
ここで、上記要求された状態変数が状態データキャッシュ６２に存在しないキャッシュミスヒット時には、上記要求された状態変数が自コンピュータの磁気ディスク装置１１の状態データ記憶部１２から読み出されて、状態データキャッシュ６２に保持される。また、状態データ記憶部１２からの状態変数の読み出しが発生する場合、前記第１の実施形態と同様に読み出し多数決部１４が動作して、システム内のｎ−ｆ台のコンピュータから当該コンピュータの磁気ディスク装置１１の状態データ記憶部１２に保存されている上記要求された状態変数が読み出され、ｎ−ｆ個の状態変数の値のうち最も多い値が最終的な読み出し値と決定されてプログラム１７に渡される。
【００７１】
このように本実施形態においては、磁気ディスク装置１１内の状態データ記憶部１２の一部の写しを保持する状態データキャッシュ６２を設けて、当該状態データキャッシュ６２に保持されている状態変数を従来方式で処理し、当該状態データキャッシュ６２にミスヒットした場合の状態変数を前記第１の実施形態で適用した方式で処理することにより、最適な性能を得ることができる。本実施形態で適用した方式は、状態変数をアクセス頻度が高い状態変数と低い状態変数とに区分できない場合に適している。
【００７２】
［第４の実施形態］
以上に述べた各実施形態では、磁気ディスク装置１１に確保された状態データ記憶部１２にデータが正しく保存されていることを前提としている。しかし、磁気ディスク装置１１が故障して、状態データ記憶部１２のデータが消えてしまう場合もあり得る。
【００７３】
そこで、ｎ台のコンピュータのうち、最大でｆ台のコンピュータが故障し、しかも、これら故障したコンピュータ内の磁気ディスク装置１１のデータが消えてしまった場合の復旧を可能とした本発明の第４の実施形態について、図面を参照して説明する。
【００７４】
図７は本発明の第４の実施形態に係る分散コンピュータシステムを構成するコンピュータ７０-iのブロック構成を示す。なお、図１中の１０-1〜１０-n（１０-4）と同一部分には同一符号を付してある。
【００７５】
図７のコンピュータ７０-iが、図１中のコンピュータ１０-1〜１０-n（１０-4）と異なる点は、読み出し多数決部１４により決定された読み出しデータＡと自コンピュータの状態データ記憶部１２からの読み出しデータＢとが異なる場合に、自コンピュータの状態データ記憶部１２のデータＢをデータＡに書き換える書き換え部７１を追加したことである。
【００７６】
次に、図７のコンピュータ７０-iをｎ台、図１のシステムと同様にネットワーク等により結合して構成された分散コンピュータシステム（図示せず）における復旧動作について、図８のフローチャートを参照して説明する。
【００７７】
まず、ｎ台のコンピュータ７０-iのうち、最大でｆ台のコンピュータ７０-iが故障し、そのうちの少なくとも一部のコンピュータ７０-iの故障の要因が磁気ディスク装置１１の故障にあり、データが消えてしまった磁気ディスク装置１１も存在するものとする。
この場合、まず故障したコンピュータ７０-iを停止する（ステップＳ３１）。
【００７８】
次に、動作している少なくともｎ−ｆ台のコンピュータ７０-iで、プログラム１７の多重化実行の一環として、本来のプログラム１７の実行と並行して、磁気ディスク装置１１内の状態データ記憶部１２からの全状態変数の読み出しを行う（ステップＳ３２）。この動作は、読み出しなので、本来のプログラム１７の実行には影響しない。
【００７９】
次に、故障から復旧してシステムに組み込まれるコンピュータ７０-iに多重化を拡大する（ステップＳ３３）。本実施形態では、この多重化の拡大において、つまりコンピュータ７０-iの組み込み時において、状態のコピーは必要ない。その理由を以下に述べる。
【００８０】
まず、上記ステップＳ３２を実行するコンピュータ７０-iは、少なくともｎ−ｆ台ある。また、この少なくともｎ−ｆ台のコンピュータ７０-iから読み出された全状態変数の値は最新のものであり、その値は、書き換え部７１によって状態データ記憶部１２に反映されていることが保証される。
【００８１】
したがって、ステップＳ３２が完了した時点では、故障したコンピュータ以外のコンピュータのうち、少なくともｎ−ｆ台のコンピュータで最新のコンピュータの状態が保持されていることになる。
【００８２】
このことは、ｎ−ｆ台のコンピュータで最新のデータを書き込んだのと同等とみなすことができ、結局、前記第１の実施形態と同様の場合に帰結される。
【００８３】
なお、上記書き換え部７１をコンピュータ６０-iに追加するには、当該書き換え部７１に次の機能、即ち状態データ記憶部１２のデータＢをデータＡに書き換える際に、状態データキャッシュ６２のデータＢもデータＡに書き換える機能を持たせればよい。
【００８４】
以上に述べた第１乃至第４の実施形態に係る分散コンピュータを構成する各コンピュータとは、独立して動作する実行環境を指し、必ずしも物理的な計算機とは限らず、計算機以外にも、例えば仮想マシン（Virtual Machine：ＶＭ）、ＯＳ（オペレーティングシステム）上で動くプロセス（Process）なども含む。
【００８５】
なお、本発明は、上記各実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。更に、上記実施形態には種々の段階の発明が含まれており、開示される複数の構成要件における適宜な組み合わせにより種々の発明が抽出され得る。例えば、実施形態に示される全構成要件から幾つかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題が解決でき、発明の効果の欄で述べられている効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【００８６】
【発明の効果】
以上詳述したように本発明によれば、コンピュータの状態を表す複数の状態変数の値を分散コンピュータシステムのｎ台のコンピュータの各不揮発性記憶装置にそれぞれ保存し、決定性のプログラムからの状態読み出し要求時には、上記ｎ台のコンピュータのうちのｎ−ｆ台（ｆは３ｆ＜ｎを満足する最大の整数）のコンピュータから当該コンピュータの不揮発性記憶装置に保存されている要求された状態変数の値を読み出し、ｎ−ｆ個の状態変数の値のうち最も多い値を、状態読み出し要求に対する最終的な読み出し値とするようにしたので、コンピュータ組み込み時や立ち上げ時のコピーを不要とすることができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る分散コンピュータシステムの構成を示すブロック図。
【図２】図１中の読み出し多数決部１４の動作を説明するためのフローチャート。
【図３】図１中の書き込み待ち合わせ部１５の動作を説明するためのフローチャート。
【図４】同第１の実施形態の効果を説明するための図。
【図５】本発明の第２の実施形態に係る分散コンピュータシステムを構成するコンピュータのブロック構成を示す図。
【図６】本発明の第３の実施形態に係る分散コンピュータシステムを構成するコンピュータのブロック構成を示す図。
【図７】本発明の第４の実施形態に係る分散コンピュータシステムを構成するコンピュータのブロック構成を示す図。
【図８】同第４の実施形態に係る分散コンピュータシステムにおける復旧動作を説明するためのフローチャート。
【符号の説明】
１０-1〜１０-4，５０-i，６０-i，７０-i…コンピュータ
１１…磁気ディスク装置（不揮発性記憶装置）
１２，５２…状態データ記憶部
１３…整列マルチキャスト用単位モジュール
１４…読み出し多数決部
１５…書き込み待ち合わせ部
１６…整列マルチキャスト機構
１７…プログラム（決定性のプログラム）
２０…ネットワーク
５１…メモリ（揮発性記憶装置）
６２…状態データキャッシュ
７１…書き換え部
【図１】
0004060522.tif 000002
【図２】
0004060522.tif 000003
【図３】
0004060522.tif 000004
【図４】
0004060522.tif 000005
【図５】
0004060522.tif 000006
【図６】
0004060522.tif 000007
【図７】
0004060522.tif 000008
【図８】
0004060522.tif 000009