(57)【特許請求の範囲】
【請求項１】
分散システムを構成する複数のコンピュータ上で独立に実行される決定的プログラムの実行を、１つのコンピュータのデータを各コンピュータに配送する整列マルチキャストにより多重化する方法において、
前記整列マルチキャストと、前記整列マルチキャストにより配送されたデータに応じて各コンピュータ上で多重実行される前記決定的プログラムとから構成されるプロセスに関し、前記各コンピュータ上で実行中のプロセスとは別に、前記各コンピュータとは異なるコンピュータを含むコンピュータ群上に新規にプロセスを生成し、
次いで、前記プロセスを実行中のコンピュータの状態を、前記実行中のプロセスの決定的プログラムを多重実行する各コンピュータの１つから前記新規に生成されるプロセスの決定的プログラムを多重実行する前記コンピュータ群の各コンピュータへと前記整列マルチキャストを通してコピーし、前記状態のコピーが終わった後に、前記実行中のプロセスを消滅し前記新規に生成されたプロセスに切り替えて実行することを特徴とするプログラム多重化拡大方法。
【請求項２】
前記コンピュータの状態をコピーするに先だって、コンピュータの状態の整理を行なう場合、前記コンピュータの状態の整理は、不要情報の削除、メモリ配置の最適化のうち少なくとも一つであることを特徴とする請求項１記載のプログラム多重化拡大方法。
【請求項３】
前記新規に生成するプロセスを、前記実行中のプロセスが存在するコンピュータ群とは別のコンピュータ群上に生成することを特徴とする請求項１又は請求項２記載のプログラム多重化拡大方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のコンピュータがネットワークで接続された分散システムにおいて決定的プログラムを整列マルチキャストを用いて多重化する方法に関する。
【０００２】
【従来の技術】
先ず、本明細書中で用いられる決定的プログラム、整列マルチキャスト及び多重化の意義について説明する。
【０００３】
決定的プログラムは次のように説明される。すなわち、図６に示すように、決定的プログラム１２は、コンピュータ１０に入力が与えられると、その時のコンピュータ１０の状態１１によって、出力と、次の状態を決めるプログラムであると考えることができる。つまり、決定的プログラム１２は、入力が決まれば、次の状態１２と出力とが一意的に決まるプログラムである。具体的には、不定値や乱数の参照がないプログラムのことを言う。
【０００４】
図７に示すように、決定的プログラムの特徴は、初期状態と入力列が決まれば、その動作が一意的であることである。以下、プログラムと称するとき、決定的プログラムを言う。
【０００５】
また、整列マルチキャストは、次のように説明される。すなわち、複数のコンピュータが結合した分散システムのような環境では、それぞれのコンピュータが独立して動作する。従って、これらのコンピュータを同期的に動作させる場合には、特別な仕組みが必要になってくる。整列マルチキャストは、それぞれのコンピュータから全てのコンピュータにデータを配送するプロトコルであり、データの到着順序が全てのコンピュータで同じであることを保証するものである。
【０００６】
整列マルチキャストを、図８を参照して具体例で説明する。コンピュータ１０―２から時刻ｔ２０に送信されたデータＡは、図示しない整列マルチキャストにより全てコンピュータ１０―１，１０―２，１０―３に時刻ｔ１１，ｔ２１，ｔ３１に受信される。コンピュータ１０―３から時刻ｔ３０に送信されたデータＢは、整列マルチキャストにより全てのコンピュータ１０―１，１０―２，１０―３に時刻ｔ１２，ｔ２２，ｔ３２に受信される。この場合、各コンピュータ１０―１，１０―２，１０―３はデータＡとデータＢとが受信されるが、整列マルチキャストはこの２つの受信順序が全てのコンピュータ１０―１，１０―２，１０―３で同一になるように制御する。
【０００７】
さらに、多重化は、次のように説明される。すなわち、分散システムでは、それぞれのコンピュータが独立に故障する可能性がある。仮に、一つのコンピュータが故障しただけで、システム全体が機能しない場合は、分散システムの稼動率は一台のコンピュータの稼動率よりも低くなってしまう。
【０００８】
かかる事態を防止するために、システム全体に係わる処理は多重化することが必要である。逆に、多重化することによって、分散システムの稼動率を一台のコンピュータの稼動率よりも高くすることが可能である。例えば、稼動率９９パーセントのコンピュータ１０台で構成する分散システムが、全く多重化されていないとすると、その分散システムの稼動率は９０パーセント程度である。また、稼動率９９パーセントのコンピュータ２台に多重化された処理の稼動率は９９．９９パーセント程度である。
【０００９】
次に、図９を参照して、整列マルチキャストを用いた多重化法について説明する。この例は、コンピュータ１０―１，１０―２，１０―３を有する分散システムにおいて、プログラムの実行を、整列マルチキャストを用いて多重化する例である。
【００１０】
図９に示すように、まず、全てのコンピュータ１０―１，１０―２，１０―３はある決まった初期状態１１、例えば全ての変数が０、から始まる。入力されるデータは、必ず整列マルチキャスト１３を通して全てのコンピュータ１０―１，１０―２，１０―３に配送され、夫々のプログラム１２に入力される。出力は一つのコンピュータの出力をとるようにする（図９ではコンピュータ１０―１である）。各プログラムの入力列は、整列マルチキャスト１３により同一順序になっているので、プログラムの特徴により、全てのコンピュータ１０―１，１０―２，１０―３の状態１１が同一に保たれ、出力列も全て同じになる。つまり、プログラムの実行が多重化される。
【００１１】
つぎに、整列マルチキャストを用いて多重化する方式と、マスタースレーブ方式で多重化する方式との相違について説明する。すなわち、マスタースレーブ方式は、マスタと呼ばれるコンピュータ上でプログラムを実行しながら、定期的にスレーブと呼ばれるコンピュータに状態を転送しておき、マスタが故障停止したときスレーブ側でのプログラムの実行に切り替えることにより多重化を実現する。
【００１２】
しかし、マスタースレーブ方式では、切り替えの際に後戻りが発生するため、コンピュータの故障停止の際の切り替え処理が複雑になり、時間がかかるという問題がある。
【００１３】
一方、整列マルチキャストを用いる場合は、コンピュータの故障停止の際に、後戻りがないため、切り替え処理は単純であり、時間がかからない。
【００１４】
また、マスタースレーブ方式では、定期的に状態をコピーするためのオーバヘッドが発生するが、整列マルチキャストを用いる場合、このオーバヘッドはない。
【００１５】
このように、システム全体の信頼性、性能に係わる処理は、整列マルチキャストによって多重化することが好ましい。
【００１６】
一方、マスタースレーブ方式は、非決定的プログラムや、スレーブ側でプログラムを実行することが好ましくない場合に適している。
【００１７】
上記の整列マルチキャストによる多重化の方法では、はじめからコンピュータが全て稼動していることを前提としていた。しかし、実際には途中から多重化を始めなければならない場合もある。例えば、故障していたコンピュータが復旧した場合や、新たにコンピュータを追加した場合がある。これらの場合には多重化の拡大が必要である。
【００１８】
かかる整列マルチキャストによる多重化を拡大する従来例を、図１０を参照して説明する。図１０において、ステップ１として、整列マルチキャスト１３を一時停止する。次に、ステップ２として、組み込まれるコンピュータ１０―３に、状態１１をコピーする。次に、ステップ３として、整列マルチキャスト１３のグループを拡大し、再開する。
【００１９】
この方式では、仮に、状態のコピーが正確に行なわれなかったとすると、組み込まれたコンピュータの動作が、他のコンピュータと異なってしまう。もちろん、整列マルチキャストを一時停止することにより、状態を不変にした上でコピーしているので、このようなことは原理的には起きず、整列マルチキャストを再開したときに全てコンピュータが同一の動作を始まるようになっている。
【００２０】
【発明が解決しようとする課題】
しかしながら、コンピュータの状態が複雑な場合には、状態を正確に取得することは容易ではなく、しばしばバグが潜んでいる場合がある。そのような場合に、従来方式では、組み込まれたコンピュータだけが誤動作し、他のコンピュータは正常に動作するため、却って不具合が発見されにくくなるという問題がある。
【００２１】
本発明の目的は、コンピュータの状態の如何に拘わらず、整列マルチキャストにより決定的プログラムを多重化することが可能な方法を提供することにある。
【００２２】
【課題を解決するための手段】
かかる課題を解決するために本発明は、分散システムを構成する複数のコンピュータ上で独立に実行される決定的プログラムの実行を、１つのコンピュータのデータを各コンピュータに配送する整列マルチキャストにより多重化する方法において、前記整列マルチキャストと、前記整列キャスト配送されたデータに応じて実行される決定的プログラムとから構成されるプロセスに関し、前記各コンピュータ上で実行中のプロセスとは別に、前記各コンピュータとは異なるコンピュータを含むコンピュータ群上に新規にプロセスを生成し、次いで、前記プロセスを実行中のコンピュータの状態を、前記実行中のプロセスの決定的プログラムを多重実行する各コンピュータの１つから前記新規に生成されるプロセスの決定的プログラムを多重実行する前記コンピュータ群の各コンピュータへと前記整列マルチキャストを通してコピーし、前記状態のコピーが終わった後に、前記実行中のプロセスを消滅し前記新規に生成されたプロセスに切り替えて実行することを特徴とする。
【００２３】
本発明によれば、実行中のプロセスを拡大するのではなく、別にプロセスを新しく生成し、実行中のプロセスから新規のプロセスへ状態をコピーするのであるから、状態取得の不具合等の影響は多重化そのものに影響受けることが無い。また、従来のように整列マルチキャスト自体の拡大を必要としなく、よって整列マルチキャストプロトコルを従来よりも簡素化することができ、性能、信頼性の向上につながる。
【００２４】
【発明の実施の形態】
以下本発明にかかるプログラム多重化拡大方法の一実施形態を図面を参照して説明する。先ず、実施形態の説明に先立ち本発明で用いられるプロセスの概念を説明する。即ち、プロセスとは、整列マルチキャストと、この整列マルチキャストにより配送されたデータに応じて各コンピュータ上で多重実行されるプログラムとで構成され、稼働率の高い実行単位である。
【００２５】
前述のプロセスの概念の下で、本実施形態の多重化方法は、従来方式のように、実行中のプロセスを拡大するのではなく、別にプロセスを新しく生成し、実行中のプロセスから新規のプロセスへ、状態をコピーするものである。
【００２６】
従って、本実施形態の多重化方法は、図１に示すように、ステップ１として、新規のプロセスを別に生成する。ステップ２として、実行中のプロセスの整列マルチキャストを一時停止する。ステップ３として、実行中のプロセスから、新規のプロセスに状態をコピーする。ステップ４として、新規のプロセスが入出力を行なうように切り替えられ、旧プロセスは消滅する。この場合、新規のプロセスへの状態のコピーは、整列マルチキャストを通して行なわれるので、全てのコンピュータで同一になることが保証される。また、仮に、状態を正確に取得することができなかったとしても、全てのコンピュータの状態は同一である。つまり、この場合には全てのコンピュータが、再開後に同じ誤動作を始める。
【００２７】
次に、図２，図３を参照して、本実施形態のプログラム多重化拡大方法を、該方法が適用される分散システムとの関係で説明する。図２，図３は、本実施形態のプログラム多重化拡大方法が適用される分散システムを示しており、ネットワーク２０２に複数のコンピュータ２０４が接続されている。各コンピュータ２０４は、少なくとも、複数のプロセス要素１００及び仮想アドレスフィルタ２０１を有する。
【００２８】
ここで、プロセス要素１００は複数有り、これらは各コンピュータ２０４上に設けられており、これら集合がプロセスを形成する。このプロセス要素１００は、図３に示すように、整列マルチキャスト要素１０１，ＴＣＰ（トランスミッション・コントロール・プロトコル）ドライバ１０２，プログラム１０３，デシリアライザ１０４，シリアライザ１０５で構成される。
【００２９】
図３において、整列マルチキャスト要素１０１は、各コンピュータ２０４上に設けられており、それらの集合が整列マルチキャストを形成する。整列マルチキャスト要素１０１間では、整列マルチキャストプロトコルパケット入出力１１５の受け渡しが行われ、整列マルチキャストとしての機能を実現する。
【００３０】
ＴＣＰドライバ１０２は、パケットの再送、並び変えなどを制御し、ランダム順序なパケットデータをシーケンシャルデータに変換する。通常パケットを処理するＴＣＰの状態は、メモリ１０６に保持される。コピーパケットを処理するＴＣＰの状態は、メモリ１０６に保持されない。
【００３１】
プログラム１０３は、任意のプログラムであり、ＴＣＰドライバ１０２からシーケンシャルデータを入力し、メモリ１０６を参照、更新し、ＴＣＰドライバ１０２にデータを出力する。プログラム１０３は、全てのコンピュータ上で同一である。
【００３２】
デシリアライザ１０４は、ＴＣＰドライバ１０２から入力するシーケンシャルデータをメモリ１０６の状態に変換し書き込む。
【００３３】
シリアライザ１０５は、メモリ１０６の状態をシーケンシャルデータに変換しＴＣＰドライバ１０２に出力する。
【００３４】
メモリ１０６は、状態を保持する。
【００３５】
コピー用パケット入力１１１は、コピー用パケットを整列マルチキャスト要素１０１を通して整列化し、ＴＣＰドライバ１０２に入力する。
【００３６】
通常用パケット入力１１２は、通常パケットを整列マルチキャスト要素１０１を通して整列化し、ＴＣＰドライバ１０２に入力する。
【００３７】
コピー用パケット出力１１３は、シリアライザ１０５から出力されたシーケンシャルデータがＴＣＰドライバ１０２で変換されたものである。
【００３８】
通常パケット出力１１４は、プログラム１０３から出力されたシーケンシャルデータがＴＣＰドライバ１０２で変換されたものである。
【００３９】
整列マルチキャストプロトコルパケット入出力１１５は、コピー用パケット入力１０１が整列マルチキャストプロトコルを実現するために行う。
【００４０】
仮想アドレスフィルタ２０１は、プロセスに対応する論理ＩＰアドレスを持っている場合にのみ、コピー用パケット入力１１１，通常用パケット入力１１２，コピー用パケット出力１１３，通常パケット出力１１４を通過させる。プロセスに対応する論理ＩＰアドレスは、どれか一つのコンピュータ上にしか存在しないので、プロセスを構成するプロセス要素のうち、一つプロセス要素のみがネットワークに入出力を行なうことになる。
【００４１】
ネットワーク２０２は、コピー用パケット及び通常パケットが流れ、インターネットに接続するＬＡＮである。
【００４２】
インタコネクト２０３は、整列マルチキャストプロトコルパケットがながれる専用の高速ネットワークである。
【００４３】
コンピュータ２０４は、複数台で分散システムを構成する。図２では２台だけ示しているが、２台を超える場合も含まれる。
【００４４】
論理ＩＰアドレス２０５は、一つのプロセスに対応する。実行中のプロセスに対応する通常の論理ＩＰアドレスと、拡大の時にのみ使われる立ち上げ論理ＩＰアドレスがある。
【００４５】
尚、ＩＰ（インタネットプロトコル）はＩＰパケットを示し、ストリームはシーケンシャルデータを示し、Ｒはメモリ１０６からの読み出しを示し、Ｗはメモリへの書き込みを示し、Ｒ／Ｗはメモリへの読み出し／書き込みを示している。
【００４６】
次に、図４及び図５を参照して本実施形態における多重化の拡大の動作を説明する。尚、図４は拡大中の動作を示す、図５は拡大後の動作を示している。
【００４７】
図４の矢印で示すように、本発明では拡大に際して、新規のプロセスを生成する（ステップ１）。このとき、実行中の整列マルチキャストは一時停止される（ステップ２）。新規のプロセスには、立ち上げ論理ＩＰアドレス２０５Ｂが割り振られ、実行中のプロセス（旧プロセス）に割り当てられている通常論理アドレス２０５Ａと区別される。ステップ３として、状態のコピーは、メモリ１０６→シリアライザ１０５→仮想アドレスフィルタ２０１→整列マルチキャスト要素１０１→ＴＣＰドライバ１０２→デシリアライザ１０４→メモリ１０６を通して行なわれる。
【００４８】
図５は、状態のコピーが終わった状態を示しており、ステップ４として、旧プロセスは消滅し、旧プロセスに対応していた通常論理アドレス２０５Ａは、新プロセスに対応するように切り替えられる。同時に新プロセスに対応していた立ち上げ論理ＩＰアドレス２０５Ｂは消滅する。
【００４９】
このように本実施形態では、多重化そのものの仕組みが状態取得の不具合などによって破綻しにくいという特徴を有しており、整列マルチキャスト自体の拡大は必要ない。従って、整列マルチキャストプロトコルを、従来よりも簡素化することができ、性能及び信頼性が向上する。また、多重化そのものの仕組みが状態取得の不具合などによって破綻しにくいため、システム全体の信頼性の向上、開発期間の短縮化に寄与する。
【００５０】
本発明は上述した実施形態に限定されない。すなわち、前述の実施形態において、１０３プログラムをＪａｖａ（米国Sun Microsystems社が開発したプログラミング言語）プログラムとし、１０４，１０５をそれぞれＪａｖａ上でのデシリアライザ、シリアライザとすることができる。
【００５１】
この場合、シリアライズの機能をＪａｖａ自身が持っているので、新たにＪａｖａ上のデシリアライザ１０４、シリアライザ１０５を作成する必要がないため開発期間が短縮できる効果を有する。
【００５２】
また、前述の実施形態において、プログラム１０３をリスプインタプリタ（Lisp interpreter）を実装するプログラムとし、シリアライザ１０５を、使用中のセルのみを出力するシリアライザとすることができる。この場合、プログラム１０３をリスプインタプリタに代えてＪａｖａインタプリタとすることができる。
【００５３】
このようにプログラム１０３をリスプインタプリタ又はＪａｖａインタプリタとし、シリアライザ１０５を使用中のセルのみを出力するものとした場合、旧プロセスと新プロセスとのメモリの内容は正確には同一にはならないが、実質的にはガベージ・コレクション（garbage collection）を行ったのと同じことになるので、実質的な動作は正常に保たれ、しかもメモリのフラグメンテーション（fragmentation）が解消されるなど性能面でも改善に寄与する。
【００５４】
この方式は、コンピュータの状態を正確に取得することができなかったとしても、全てのコンピュータの状態は同一に保たれるという特徴を積極的に利用したものである。
【００５５】
さらに、前述の実施形態において、新プロセスを、実行中のプロセスとは別のコンピュータ上に生成し、多重化の拡大を行うことなく、多重化の移動又は縮小を行うようにしても良い。この応用例は、従来、多重化の移動は容易ではなかったことを考慮すると、システムのリプレースメントや、メンテナンスのためのコンピュータの一時停止などの際に有効である。
【００５６】
【発明の効果】
以上のように本発明によれば、実行中のプロセスとは別に、新規にプロセスを生成し、次いで、前記プロセスを実行中のコンピュータの状態を、前記実行中のプロセスから前記新規のプロセスへと前記整列マルチキャストを通してコピーすることにより、実行中のプロセスを拡大するのではなく、別にプロセスを新しく生成し、実行中のプロセスから新規のプロセスへ状態をコピーするのであるから、状態取得の不具合等の影響は多重化そのものに影響受けることが無い。また、従来のように整列マルチキャスト自体の拡大を必要としなく、よって整列マルチキャストプロトコルを従来よりも簡素化することができ、性能、信頼性の向上につながる。
【００５７】
よって、本発明によれば、コンピュータの状態の如何に拘わらず、整列マルチキャストにより決定的プログラムを多重化することが可能な方法を提供することができる。
【図面の簡単な説明】
【図１】本発明によるプログラム多重化拡大方法の一実施形態を示す示す図。
【図２】同実施形態の方法が適用される分散システムの一例を示すブロック図。
【図３】図２におけるプロセス要素の詳細ブロック図。
【図４】同実施形態における多重化を拡大中の動作を説明するブロック図。
【図５】同実施形態における多重化を拡大後の動作を説明するブロック図。
【図６】プログラムの概念を示す図。
【図７】決定的プログラムの状態遷移を示す図。
【図８】従来技術におけるイメージ入力システムのブロック図。
【図９】整列マルチキャストによるデータの配送の例を示す図。
【図１０】整列マルチキャストによる多重化法の従来例を示す図。
【符号の説明】
１００…プロセス要素、１０１…整列マルチキャスト要素、１０２…ＴＣＰドライバ、１０３…プログラム、１０４…デシリアライザ、１０５…シリアライザ、１０６…メモリ、１１１…コピー用パケット入力、１１２…通常用パケット入力、１１３…コピー用パケット出力、１１４…通常パケット出力、１１５…整列マルチキャストプロトコルパケット入出力、２０１…仮想アドレスフィルタ、２０２…ネットワーク、２０３…インタコネクト、２０４…コンピュータ、２０５…論理ＩＰアドレス。
【図１】
0003831154.tif 000002
【図２】
0003831154.tif 000003
【図３】
0003831154.tif 000004
【図４】
0003831154.tif 000005
【図５】
0003831154.tif 000006
【図６】
0003831154.tif 000007
【図７】
0003831154.tif 000008
【図８】
0003831154.tif 000009
【図９】
0003831154.tif 000010
【図１０】
0003831154.tif 000011