(57)【要約】【課題】非同期共有オブジェクトシステムにおいて、予期せず停止するプロセッサ停止故障の存在に耐え、プロセッサ数に影響されない値以下に待ち時間を抑えて命令を実行し、高信頼で安定したサービスの質を保証する。【解決手段】複数のプロセッサが非同期に動作する共有メモリシステムで１つの共有オブジェクトの読出しと別の共有オブジェクトへの書込みを不可分に行う命令を用いた耐故障合意手法と書込み対象となる変数の取る値の範囲を限定することによりその合意手法の実行における待ち時間をプロセッサ数に影響されない値以下に抑える機能を有する実現機構を備えた非同期共有オブジェクトシステムにおいて、１つの変数に対する読出し書込み不可分命令を競合なく合意されるプロセッサを耐故障合意手法により選出し、他のプロセッサが合意されるプロセッサの命令の引数情報をもとに独立して命令を終えることにより実行し、他のプロセッサの処理による待ち時間を低減させる。【選択図】  図１
2004302831.tif 000002
【特許請求の範囲】
【請求項１】
共有メモリと、該共有メモリに接続される複数のプロセッサを備えており、
該複数のプロセッサが非同期に動作可能で、かつ、複数のプロセッサ間が共有メモリを介してのみ通信されるよう構成された分散システムにおいて、システム上で共有メモリ上の共有変数に対して実行可能な命令には、命令自体をそれ以上他の命令によって構成せず、命令の実行の途中で実行が中断することがないメモリ命令と、
複数の基本的な命令の実行を含む処理を命令の実行とするオブジェクト命令の２種類が存在し、システム上で用いられる変数には基本的な命令が適用される共有変数と
オブジェクト命令が適用される共有オブジェクト変数が存在し、
共有オブジェクト変数１つに
関する読出しと書込みの２つの処理を該２つの処理の途中で中断することがなく不可分に実行することを要求する読出し書込み不可分命令が
ある時刻において１つの該共有オブジェクト変数に対して発行され、実行が終了していない複数のプロセッサによる命令が存在する場合に、
他のプロセッサに予期せずに停止する停止故障という状態にないプロセッサが、同一の共有オブジェクト変数に対し発行した前記読出し書込み不可分命令の実行を
直列に順序付けできるという前記共有オブジェクト変数の値の整合性を維持し、かつ、
プロセッサの前記読出し書込み不可分命令の発行から終了までの間に、
他の停止故障状態にあるプロセッサの前記読出し書込み不可分命令により
前記読出し書込み不可分命令の実行がブロックされることがないという
耐故障性を維持し、かつ、
あるプロセッサの前記読出し書込み不可分命令の発行から終了までに
２つ以上の長さをもつ連続する
停止故障状態にないプロセッサによる前記読出し書込み不可分命令の処理に属する
ある１つの命令の実行にかかる時間以上
読出し書込み不可分命令の処理に属する命令の実行がブロックされることがないという
競合回避性を維持することを特徴とする分散システム。
【請求項２】
請求項１において、
１つの共有オブジェクト変数に対する読出し書込み不可分命令実行を
該共有オブジェクト変数の値を変更することができるプロセッサを
決定する変更権利獲得処理と
変更権利を獲得したプロセッサが書き込む値として
前記読出し書込み不可分命令の引数として与えた値に
前記共有オブジェクト変数の値を変更する変数値変更処理に分割することにより前記読出し書込み不可分命令の実行における前記共有オブジェクト変数の値の整合性を維持し、かつ、
前記読出し書込み不可分命令の実行の耐故障性と競合回避性を維持する機能を有する
ことを特徴とした請求項１における分散システム。
【請求項３】
請求項２において、
それぞれが局所変数に格納された入力値をもつプロセッサの集合において、
故障していない全てのプロセッサがある１つのプロセッサのもつ入力値に合意するという機能を有する合意手法を１つの共有オブジェクト変数に対する読出しと１つの共有オブジェクト変数に対する書込みを不可分に行う２変数読出し書込み不可分命令を読出し変数の取りうる値の範囲を限定することによって当該命令を競合回避性をもって実行する機能を有する共有オブジェクトシステム上で動作させることによる
耐故障性と競合回避性を備えた合意実行により
１つの共有オブジェクト変数に対する読出し書込み不可分命令の実行での
耐故障性と競合回避性を備えた変更権利獲得処理を行うことを特徴とした
請求項２の分散システム。
【請求項４】
請求項２において、
１つの共有オブジェクト変数に対する読出し書込み不可分命令実行での変更権利獲得処理によって選出された変更権利獲得プロセッサが共有オブジェクト変数値変更処理を行わない場合でも、他のプロセッサによる共有オブジェクト変数値変更処理によって共有オブジェクト変数値の整合性を維持する機能を有することを特徴とした
請求項２の分散システム。
【請求項５】
請求項３、かつ、請求項４において、
１つの共有オブジェクト変数に対する読出し書込み不可分命令実行での共有オブジェクト変数値変更処理を複数の共有オブジェクト変数の値を不可分にあらかじめ決められた１つの値に設定する共有オブジェクト変数不可分初期化命令と不可分初期化命令により初期化される共有オブジェクト変数の１つの読出しと他の共有オブジェクト変数の書込みとを不可分に行う初期化変数読出し書込み不可分命令を実現する共有オブジェクト上で共有オブジェクト変数不可分初期化命令を用いたオブジェクト変数値変更手法を動作させることにより共有オブジェクト変数値の整合性を維持し、耐故障性、および、競合回避性を維持する機能を有することを特徴とする請求項３、かつ、請求項４の分散システム。
【請求項６】
請求項５において、システムの実行開始から終了までの間に各プロセッサが高々一度しか読出し書込み不可分命令を実行しないという性質を利用することを特徴とした請求項５の分散システム。
【請求項７】
請求項５において、請求項６の性質が満たされていないとき、あるプロセッサが該分散システムにおけるある命令を実行可能かどうかの可否が、ある変数の値によって決定され、その変数の読み出しとその命令の実行が不可分に行われることを特徴とした請求項５の分散システム。
【請求項８】
請求項５において、耐故障合意手法で使用する共有オブジェクトの２値変数、２値変数配列の初期化を不可分に実行可能な命令。
【請求項９】
請求項５において、プロセッサ数と同数存在する権限変数の値を不可分に初期化することができる命令。
【請求項１０】
請求項５において、読出し書込み不可分命令を実行する対象となる変数の値を不可分に更新可能な命令。
【請求項１１】
請求項７において、請求項８、９、および１０の命令を権限変数の値によって全てを不可分に実行するか、または全く実行しないかを決定することを特徴とする請求項７の分散システム。
【請求項１２】
請求項１１において、２値変数を多重読み出し多重書き込み可能な２値変数配列を用いて実現し、権限変数配列、２値変数配列、復帰値格納変数配列、引数格納変数配列、読出し書込み命令を発行する変数を多重読み出し単一書き込み可能な２値変数配列群を用いて実現することを特徴とする請求項１１の分散システム。
【請求項１３】
請求項１１において、２値変数、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する変数を多重読み出し多重書き込み可能な２値変数配列群を用いて実現し、権限変数配列、２値変数配列、復帰値格納変数配列、引数格納変数配列を多重読み出し単一書き込み可能な２値変数配列群を用いて実現することを特徴とする請求項１１の分散システム。
【発明の詳細な説明】
【発明の属する技術分野】
【０００１】
本発明は、分散システムの１つである複数のプロセッサが非同期に動作可能であり、複数のプロセッサ間で通信するためのシステム共通領域をもつ非同期共有メモリシステム、それにより構成される非同期共有オブジェクトシステム、および、それらシステム上での複数プロセッサにより並行発行された排他的命令の実行方法に関し、特に変数値の整合性の維持、および、プロセッサ故障に対する耐性の確保、および、待ち時間の低減に関する。
【従来の技術】
【０００２】
従来、分散システムにおける共有メモリを介してのみプロセッサ間の通信が可能なシステムにはプロセッサの処理を同期して動作可能である同期共有メモリシステムとプロセッサ間の処理が非同期に動作可能である非同期共有メモリシステムに大別される。非同期共有メモリシステムはプロセッサごとの命令の処理時間は様々であり、プロセッサ間の負荷の違いやプロセッサ性能特性の違いを反映できる一般性の高い分散システムのモデルである。しかし、非同期共有メモリシステムでは他のプロセッサの命令の実行時間の上限をどのプロセッサも求めることができないため、発行した命令の実行が他のプロセスの処理を待ち、かつ、その処理の途中で処理を実行しているプロセッサが停止するという停止故障の可能性がある場合に命令を発行してから終了するまでに他のプロセッサによるブロックで生じる待ち時間が無限となる可能性がある。一方、ブロックされているにも拘わらず他のプロセッサの処理の終了を待たない場合、複数のプロセッサによって同一メモリ領域群に実行された命令集合を順序付けできるという値の整合性を維持できなくなる。
【０００３】
また、データの整合性を維持し、かつ、故障に対する耐性を備えるために複数の命令を不可分に実行する強力な命令を導入することにより、１つのプロセスの１つの命令が複数のプロセッサの命令の実行にブロックされ、かつ、その命令が排他的に実行される場合、競合が生じシステムを構成しているプロセッサ数に依存する命令実行の待ち時間を生じる可能性がある。この競合による実行の待ち時間は多くのプロセッサにより構成されている分散システムでは実際的な性能の隘路となっている。
【０００４】
競合を低減するために１変数に対して複数のプロセスによって発行された異なる命令をプロセッサ台数に比例するバッファを設けることによって、命令の同時実行を可能とする多重読出し多重書込み共有メモリオブジェクト変数を実現する非同期共有オブジェクトシステムが提案されている。しかし、書込み命令と読出し命令の実行の機能を備える分散システムでは解決できない問題がある。例えば、複数のプロセッサが局所変数として外部から与えられたある１つの入力値に故障していない全てのプロセッサが合意するという合意問題に対して、書込み命令と読出し命令のみの実行の機能を備える非同期分散システムでは耐故障性と値の整合性を保つ手法は存在しないことが示されている。
【０００５】
合意問題を解く１つのシステムとして、１つの変数に対する読出しと書込みを不可分に実行すること要求する強力な読出し書込み不可分命令を実行する機能を備える非同期分散システムがある。つまり、該読出し書込み不可分命令では１つの変数から読み出した値を用いて、該変数へ書き込む値を決定し、決定された値を書き込むという一連の処理を１命令ステップで実行する。従来の非同期分散システムでは、読出し書込み不可分命令を並行して実行するためには合意問題を解かなければならず、合意問題を解くためには読出し書込み不可分命令を実行できる分散システムと同等に強力な分散システムを必要とすることが示されている。
【０００６】
従来の共有オブジェクトシステムでのオブジェクト変数の種類としては１命令中に読出しまたは書込みのみを実行可能なｒｅａｄ−ｗｒｉｔｅ  ２値変数配列と書込みと読出しの両方を不可分に１命令中で実行可能な  ｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ  ２値変数配列に大別される。
【０００７】
従来の共有オブジェクトシステムにおいて、２値変数配列内容の多重書き込みを許さない単一書き込みのみ可能な２値変数配列ｘの場合、変数ｘに対するｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ命令は排他的に実行されるため、ｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ命令を実行中、変数ｘはロックされ変数ｘに対する他の全ての命令が実行不能となる。
【０００８】
したがって、複数のプロセッサが同時に変数ｘに対するｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ命令を発行した場合、プロセッサ数の長さをもつロックの連なりができてしまう。
【０００９】
ｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ命令の１つであるｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令について説明する。共有２値変数配列ｘと値ｖ、  値ｋにおいてｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ（ｘ、ｖ、ｋ）命令は共有２値変数配列ｘの値ｗがｖと一致するなら共有２値変数配列ｘに値ｋを書き込み値ｗを戻り値として返す。そうでなければ何もせず、値ｗを戻り値として返す。この手続きを１命令ステップ中に実行する。そして、その１命令ステップの実行中に故障の影響を他のプロセッサに与えない、かつ、受けないようにするために命令は不可分に実行される。ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ  命令を用いた解法により前記合意問題を耐故障性を備えて解けることが知られている。従来のｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の実行をハードウェアによりそれ以上分割できない処理として実現する共有オブジェクトシステムではｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の実行の排他性を保証するためには、前述した理由により同時に発行された命令を逐次的に処理するためのロックの連なり、つまり、該システム上のプロセッサ数に依存した命令に対する待ち時間を課する可能性のある競合が生じる。したがって、合意問題の従来の共有オブジェクトシステムでの競合によって解決までに発生する待ち時間もプロセッサ数に依存した時間となる可能性がある。さらに、前述共有オブジェクトシステムでの合意問題の高い競合コストをもつという特性はｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ  命令の耐故障性を備える実行をプロセッサ数に依存しない競合コストをもって同システム上では実現できないことを意味する。
【００１０】
【発明が解決しようとする課題】従来の共有メモリシステムでは複数のプロセッサが同時にｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を実行しようとする場合、排他的に命令を実行するというｒｅａｄ−ｍｏｄｉｆｙ−ｗｒｉｔｅ命令の特性により、プロセッサ数に依存する待ち時間が発生してしまうという問題がある。分散システムにおいて、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令はセマフォの実現など様々な基本的処理に用いられており、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の高い競合コストは分散システムの実際的な性能の隘路となっている。
【００１１】
本発明の目的は、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の耐故障性、排他性を保つ実行をプロセッサ数に依存しない待ち時間とし、分散システムのサービスの質を高信頼、かつ、安定にすることである。
【００１２】
【課題を解決するための手段】本発明は、合意問題を耐故障性を保証して、かつ、プロセッサ数に依存しない待ち時間で処理できるよう構成されたハードウエアから成る分散システムと、そのシステム上の共有オブジェクトに対する排他的な処理が要求されている複数の命令を並行に実行するためのソフトウェアの処理方式を実現するものである。
【００１３】
基本的には、分散システムにおいて、耐故障性を保証した合意問題をプロセッサ数に依存しない待ち時間をもって解く機構を備え、かつ、１つの共有オブジェクト変数に対するｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の実行を該変数の値を変更する権利をもつプロセッサを決定する処理と該変数の値を変更する処理に分割する。これにより、耐故障性を保証して、かつ、権利をもつプロセッサの決定の処理にかかる待ち時間をプロセッサ数に依存しない時間とでき、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ  命令の耐故障性を備える並列な実行を可能とする。
【００１４】
以上を実現する為には、２つの共有オブジェクト変数に対して、１つの変数を読出し、読み出した値によって、もう一方の変数に書き込む値を決定する２変数読出し書込み不可分命令を並行に実行するための機構、および、変数集合の値を不可分に初期化することができる命令を実行するための機構を共有メモリシステムをハードウエア上に構成する。実現した分散システムの上で、各プロセッサはｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ  （ｘ、ｖ、ｋ）命令の引数ｋを多重読出し単一書込み可能なｒｅａｄ−ｗｒｉｔｅ共有オブジェクト変数に書き、２変数に対する読出し書込み不可分命令を用いることによって、プロセッサ数に依存しない待ち時間で合意問題を解決する。これにより、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ  命令の対象とする共有オブジェクト変数の値を変更する権利をもつプロセッサを非同期周期で命令が実行された場合においても、全ての故障状態にないプロセッサがプロセッサ数に依存しない待ち時間で知ることができ、かつ、各プロセッサが知った権利を獲得したプロセッサを同一にすることができる。つぎに、各故障状態にないプロセッサは権利を獲得したプロセッサが書き込んだ引数を読出し、その値を他のすべてのプロセッサに知らせるために多重書込み単一読出し可能な共有オブジェクト変数の集合に書き込む。そして、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の対象となっている共有オブジェクト変数の値を新しい値に並行に書き換える。
【００１５】
以上より、ソフトウェアによりｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の耐故障性を保証した処理方式と、その処理方式で用いられている命令をハードウエアによりプロセッサ数に依存しない待ち時間をもつ命令で並列に実行可能とすることによって、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の耐故障性をもった、プロセッサ数に依存しない待ち時間をもつ並列実行が可能となる。
【００１６】
【発明の実施の形態】図１に本発明の１実施例による分散システムの構成を示す。本システムは耐故障性を備える合意手法で使用する為の２値変数と２値変数配列、あるプロセッサが複数回命令を発行可能とする権限変数配列、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の復帰値を格納する復帰値格納変数配列、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の引数を格納する引数格納変数配列、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する変数を、共有オブジェクトとして備える。更に、プロセッサと共有オブジェクトの通信手段として使用する外部入出力ポートと、共有オブジェクトが認識可能な命令に変換する命令フェッチブロックと、命令を識別する命令デコーダと、請求項８の２値変数、２値変数配列の初期化を不可分に実行可能な命令、請求項９の権限変数の値を不可分に初期化することができる命令、請求項１０のｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する対象となる変数の更新とを、請求項１１のように権限変数の値によって不可分に実行可能とする為の命令制御ブロックと、耐故障合意手法を使用するための合意ブロックと、復帰値を格納する為、そしてｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令として整合性を保つ復帰値を選出する為の復帰値ブロックとを使用する機構を備える。
【００１７】
また、共有オブジェクト機構、あるプロセッサが複数回命令を発行可能とする権限変数配列、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の復帰値を格納する復帰値格納変数配列、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令の引数を格納する引数格納変数配列、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する変数を備える。
【００１８】
耐故障合意機構は、権限変数配列はプロセッサ数ｎと同数の２値変数の集合であり、復帰値格納変数配列はプロセッサ数ｎと同数の復帰値オブジェクトの集合により構成されている。復帰値オブジェクトは復帰値の型と同型の変数４つと２値変数から成っている。引数格納変数配列は引数を格納するために、プロセッサ数ｎと同数の行数を持つ２次元配列である。そして、それぞれはプロセッサのインデックス（１，…，ｎ）毎の連続する領域を持つ。
【００１９】
非同期で動作するｎ個のプロセッサと共有オブジェクトとの通信手段としてｎ個の外部入出力ポートを共有オブジェクトに備える。プロセッサ１つに対して入出力ポート１つが対応する。プロセッサと共有オブジェクトは必ず外部入出力ポートを介して通信し合う。
【００２０】
各プロセスから外部入出力ポートに送られた信号は、共有オブジェクト内の命令フェッチブロックに送られる。命令フェッチブロックは各外部入出力ポートに対してひとつ存在する。外部入出力ポートに送られた信号は、命令フェッチブロックによって共有オブジェクトに対する命令に変換される。
【００２１】
命令デコーダは、各ブロックや変数へ命令信号を送る。その際、各命令においてその命令を発行したプロセッサのインデックスｉを識別できる型にする場合がある。
【００２２】
命令制御ブロックは、制御ブロック、初期化ブロック、ロックブロック、書き込みブロックから構成されている。制御ブロックは不可分命令を実行するかどうかを判定し、実行するならば、残りの３ブロックへ実行信号を送る。初期化ブロックは実行信号を受け、合意ブロックの共有オブジェクトである２値変数と２値変数配列の値、そして権限変数配列の値をそれぞれ初期化する。ロックブロックは実行信号と制御信号を制御ブロックから受け取り、制御信号によって指定された変数を命令が終了するまで他のプロセッサから読み出し不可能とする為にロックする。書き込みブロックは制御ブロックから実行信号と書き込むべき値の信号を受け、書き込みの対象となる変数の値を更新する。
【００２３】
合意ブロックは耐故障合意手法を実現する為の機構である。本発明では合意ブロックへプロセッサ毎の権限変数の値を信号として合意ブロックへ送り、耐故障合意手法でのｒｅａｄ−ａｎｄ−ｗｒｉｔｅ命令、多重読み出し多重書き込み可能な２値変数へのｗｒｉｔｅ命令の実行を制限することに使用する。
【００２４】
復帰値ブロックは各プロセッサの復帰値を保持・管理する為の機構である。ブロック内にある値を読み出し、又は値の書き込みを実行するための信号とプロセッサのインデックスｉを特定する信号を入力として受ける。
【００２５】
本発明の各共有オブジェクトは複数プロセッサによる同時読み出しを可能とする特徴を持つ。１変数につきプロセッサ数に比例するバッファを備え、プロセッサが同時に読み出そうとする時に各プロセッサごとに読み出すバッファが重複しない機構である。請求項１２においては上述の機構で実現可能だが、請求項１３においてはｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する変数を多重読み出し多重書き込み可能な変数で実現した機構にする必要がある。
【００２６】
初期設定として権限変数配列の値を状態αとし、復帰値格納変数配列の復帰値と同型の４つの２値変数配列はｎｕｌｌ値を設定し、２値変数はα’を設定する。引数格納変数配列、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する変数共にｎｕｌｌ値を設定する。合意手法を用いる為の２値変数と２値変数配列の初期設定値は実現機構に従う。上記の機構を用いて、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ（Ｘ，Ａ，Ｂ）という命令を各プロセッサｉにおいて以下のプロトコルを実行する。始めに２次元の引数格納変数のインデックスｉの１次元目の２値変数配列に値Ａ、２次元目の２値変数配列に値Ｂを格納する。次に権限変数配列のｉ番目の２値変数配列の値をΒに設定する。
【００２７】
次に復帰値格納変数配列の２値変数がα’ならばΒ’へΒ’ならばα’へ設定する。次にｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する２値変数配列の値を読み出し局所２値変数配列ｋへ格納する。次にもしｋの値と引数Ａの値が等しいならば耐故障合意手法を実行し合意するプロセッサのインデックスｓを検出する。
【００２８】
本発明での、耐故障合意手法について示す。本発明で使用する共有２値変数配列群ｙはプロセッサのインデックス（１，…，ｎ）毎の連続する領域を持ち、その領域をさらに個別状態部と入力値格納部の２領域に分割する構造である。
【００２９】
命令デコーダは、共有２値変数配列群ｙのプロセッサｉの状態フラグ部を読み出すという信号を命令フェッチブロックから受け取った後、
個別フラグ読み込みブロックに変換した信号を送る。
個別フラグ読み込みブロックに信号を送る際にｉを識別可能な信号に変換する。
【００３０】
ロックブロックでは命令フェッチブロックから共有２値変数配列群ｙの領域ｊの状態フラグ部をロックするという信号と命令デコーダから共有２値変数配列群ｙの領域ｋの状態フラグ部を読み出すという信号を入力として受ける。
【００３１】
ロックブロックはプロセッサｉのｒｅａｄ−ａｎｄ−ｗｒｉｔｅ命令中に共有２値変数配列群ｙの領域ｉの状態フラグ部の値を読み出すことができないようにロックする機構である。
それに加えて各入力がいくつ同時に発生したとしても出力は正常である特性を持つ。
命令デコーダから入力として受ける
共有２値変数配列群ｙの領域ｊの状態フラグ部を読み出すという信号に対して共有２値変数配列群ｙの領域ｊの状態フラグ部がロックされているかどうかの結果を出力する。
また出力される内容によって外部ポートに値を書き込むか否かを制御する。
【００３２】
フラグブロックは共有２値変数配列ｘと共有２値変数配列群ｙの値を管理・保持するブロックである。命令フェッチブロックから入力を受け２値変数配列の値を操作する。
複数の命令フェッチブロックからの信号が同時に発生したとしても
結果は正常に出力されるという特性を持つ。
共有２値変数配列群ｙの状態フラグ部の値が出力される。
【００３３】
個別フラグ読み込みブロックでは、共有２値変数配列群ｙの状態フラグ部の値を読み出す。入力として命令デコーダからどの値を読み出すかを示す信号とフラグブロックから共有２値変数配列群ｙの状態フラグ部の値を受ける。
共有２値変数配列群ｙの状態フラグ部の値を出力する。
入力の際に、命令デコーダからいくつ同時に信号を受けたとしても出力は正常であるという特性を持つ。
【００３４】
外部入力値格納ブロックでは、共有２値変数配列群ｙの入力値格納部の値、つまり各プロセッサが合意すべき入力値を保持・管理する。
入力として命令フェッチブロックから値格納先の場所と書き込みの際の値と読み出しか書き込みかを区別する信号とを受ける。
この際に、入力のがいくつ同時に発生しても出力は正常であるという特性を持つ。
【００３５】
初期設定としてｘを状態αとし、ｙの各個別状態部は合意不可能状態とし各入力値格納部にはｎｕｌｌ値を設定する。上記の機構を用いて、各プロセッサＩにおいて以下のプロトコルを実行する始めに入力値ｋとする。次に共有２値変数配列群ｙの領域Ｉの入力値格納部に値ｋを書き込む。次にｒｅａｄ−ａｎｄ−ｗｒｉｔｅ命令を実行し共有２値変数配列ｘが状態αであるならば共有２値変数配列群ｙの領域Ｉの状態フラグ部を合意可能状態とする、そうでなければ何もしない。次に共有２値変数配列ｘを状態βとする。次にプロセッサインデックスの昇順に共有２値変数配列群ｙの領域１の状態フラグ部から順に合意可能状態か否かを調査し、合意可能状態が発見できるまで調査を続ける。
次に最初に合意可能状態を発見した領域の入力値格納部の値を読み出し、合意すべき値として決定する。
【００３６】
上記の耐故障合意手法のｒｅａｄ−ａｎｄ−ｗｒｉｔｅ命令、多重読み出し多重書き込み変数に対する書き込み命令は権限変数配列のインデックスｉの値がΒの場合のみ実行可能である。もしｋの値と引数Ａの値が等しくないならばｋの値を復帰値として処理を終了する。
次にあるプロセッサのインデックスをｔとし、最小のものから順に合意処理で検出したプロセッサのインデックスｓと等しいかどうかを調べる。等しいならば復帰値格納変数配列のインデックスｔの２値変数の値がα’であり、かつ権限変数配列のインデックスｔの値がΒならば、復帰値格納変数配列のインデックスｔの復帰値の型を持つ４つの２値変数配列のうち１番目と２番目の２値変数配列に引数格納変数配列のインデックスｓの１次元目の２値変数配列の値を、３番目と４番目の２値変数配列の値に値ｋをそれぞれ書き込む。なおこれらの引数格納変数配列への書き込みは権限変数配列のインデックスｉの値がΒの時のみに不可分に実行される。また以降の処理での引数格納変数配列への書き込みも権限変数配列のインデックスｉの値がΒの時のみに不可分に実行されるものである。ｓ＝ｔでありかつ復帰値格納変数配列のインデックスｔの２値変数の値がα’であるが権限変数配列のインデックスｔの変数の値がαならば復帰値格納変数配列のインデックスｔの復帰値の型を持つ４つの２値変数配列の１番目の２値変数配列に引数格納変数配列のインデックスｓの２次元目の２値変数配列の値を、３番目の２値変数配列に値ｋをそれぞれ書き込む。ｓとｔが等しくなく、かつ復帰値格納変数配列のインデックスｔの２値変数の値がα’であり、かつ権限変数配列のインデックスｔの２値変数の値がΒならば、復帰値格納変数配列のインデックスｔの復帰値の型を持つ４つの２値変数配列の１番目と２番目の２値変数配列に引数格納変数配列のインデックスｓの２次元目の２値変数配列の値を、３番目と４番目の２値変数配列の値に値ｋをそれぞれ書き込む。ｓとｔが等しくなく、かつ復帰値格納変数配列のインデックスｔの２値変数の値がα’であり、かつ権限変数配列のインデックスｔの２値変数の値がαならば、復帰値格納変数配列のインデックスｔの復帰値の型を持つ４つの２値変数配列の２番目の２値変数配列に引数格納変数配列のインデックスｓの２次元目の値を、４番目の２値変配列の値に値ｋをそれぞれ書き込む。次に権限変数配列のインデックスｉがΒであるならばｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令を発行する変数の値を引数格納変数配列の２次元目の２値変数配列の値へ更新し、権限変数配列の値を全て状態αとし、耐故障合意手法で使用する２値変数と２値変数配列の値の初期化を不可分に実行する。次に復帰値格納変数配列のインデックスｉの２値変数の値がα’であり、かつ、復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列のうちの１番目の２値変数配列と引数格納変数配列のインデックスｉの１次元目の２値変数配列の値が異なるならば復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列のうちの１番目の２値変数配列の値を復帰値とする。復帰値格納変数配列のインデックスｉの２値変数の値がα’であり、かつ、復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列のうちの１番目の２値変数配列と引数格納変数配列のインデックスｉの１次元目の２値変数配列の値が等しいならば、復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列うちの３番目の２値変数配列の値を復帰値とする��復帰値格納変数配列のインデックスｉの２値変数の値がΒ’であり、かつ、復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列の２番目の２値変数配列と引数格納変数配列のインデックスｉの１次元目の２値変数配列の値が異なるならば復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列のうちの２番目の２値変数配列の値を復帰値とする。復帰値格納変数配列のインデックスｉの２値変数の値がΒ’であり、かつ、復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列のうちの２番目の２値変数配列と引数格納変数配列のインデックスｉの１次元目の２値変数配列の値が等しいならば、復帰値格納変数配列のインデックスｉの復帰値の型を持つ４つの２値変数配列の４番目の２値変数の値を復帰値とする。
【００３７】
【発明の効果】
本発明によれば、分散システム中に故障したプロセッサが存在しても、故障していないプロセッサはｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令のプロトコルを終了することができ、かつ、ｃｏｍｐａｒｅ−ａｎｄ−ｓｗａｐ命令と同じ引数で、変数の値を更新する、復帰値を得るという操作において、任意のプロセッサの命令の実行は高々定数個のプロセッサがシステム上での命令に要する実行時間の影響しか受けない。よって、分散システムのサービスの質を高信頼、かつ、安定にする効果がある。
【図面の簡単な説明】
【図１】本発明の一実施例による分散システム
【図１】
2004302831.tif 000003