(57)【特許請求の範囲】
【請求項１】
他のプロセッサの識別子とは異なる識別子をもち、
自己の識別子とすべてのプロセッサの識別子からなる集合Ｎを知っており、自己の識別子を変数ｉに代入しているプロセッサであって、
非同期に動作する他のプロセッサと
共有２値変数配列群ｙと共有２値変数配列ｘという共有オブジェクトを介して通信するプロセッサであって、
前記共有２値変数配列群ｙは前記識別子集合Ｎに属する要素を値として取る変数ｊの任意の値によって参照可能な個別の該当領域ｙ[ｊ]を含み、
前記該当領域ｙ[ｊ]は合意可能状態、
合意不可能状態の２状態を記憶でき、初期状態を合意不可能状態とする状態フラグ部と、
外部からの入力値を記憶でき、初期値をNULLとする入力値格納部を含み、
前記共有２値変数配列ｘは、
状態αと状態βの２状態を記録でき、初期状態をαとする、
共有オブジェクトを介して
通信するプロセッサであって、
入力値受信手段、入力値格納手段、合意可能状態記録手段、状態β記録手段、状態フラグ部読み出し手段とプロセッサ識別子発見手段を有するプロセッサ
によって使用される合意手法であって、
前記入力値受信手段が外部からの入力値を受け取り、変数ｋに代入する入力値受信ステップと、
前記入力値格納手段が前記変数ｋに代入された値を前記共有２値変数配列群ｙの自己の識別子を記録している変数ｉの値によって参照可能な該当領域ｙ[ｉ]の入力値格納部に記録する入力値格納ステップと、
前記合意可能状態記録手段が、
前記共有２値変数配列ｘの状態がαであるときに限り、
前記共有２値変数配列群ｙの前記変数ｉの値によって参照可能な該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録し、
前記共有２値変数配列ｘの状態がαでないとき、なにもしない合意可能状態記録ステップと、
前記状態β記録手段が、
前記共有２値変数配列ｘに状態βと記録する状態β記録ステップと、
前記状態フラグ部読み出し手段が、
前記識別子集合Ｎに属する要素を値として取る変数ｊの任意の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｊ]の状態フラグ部の値を読み出す状態フラグ部読み出しステップと、
前記プロセッサ識別子発見手段が、
前記識別子集合Ｎに属する要素を値として取りうる変数ｊの値であり、かつ、変数ｊに代入された当該の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｊ]の状態フラグ部の状態が合意可能状態であるという条件を満たす値の集合に属する識別子の中で最も小さい識別子を発見し、変数ｍに代入するプロセッサ識別子発見ステップとを有し、
前記合意可能状態記録ステップでは、
前記合意可能状態記録手段が
前記変数ｉの値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部の記録の開始から終了までの途中で他のプロセッサの状態β記録ステップを実行している状態β記録手段によって
前記共有２値変数配列ｘが状態βと記録されることを禁止しない、
前記状態β記録ステップでは、
前記状態β記録手段が
前記共有２値変数配列ｘの記録の開始から終了までの途中で他のプロセッサの合意可能状態記録ステップを実行している合意可能状態記録手段によって前記共有２値変数配列ｘの値が読み出されることを禁止しない、
ことを特徴とする合意手法。
【請求項２】
請求項１に記載の合意手法を使用できるプロセッサであって、さらに合意値決定手段を有するプロセッサによって使用される合意手法であって、
前記合意値決定手段が
前記プロセッサ識別子発見ステップの実行により前記変数ｍに代入された値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｍ]の入力値格納部の値を合意する値とする合意値決定ステップ、
とをさらに有することを特徴とする請求項１に記載の合意手法。
【請求項３】
前記合意可能状態記録ステップでは、
前記合意可能状態記録手段が
前記変数ｉの値により参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録を始めると同時に、または、以降に他のプロセッサの状態β記録ステップを実行している状態β記録手段による前記共有２値変数配列ｘへの状態βの記録が開始され終了し、
次に、他のプロセッサの状態フラグ部読み出しステップを実行している状態フラグ部読み出し手段による前記変数ｉの値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部の読み出しが開始され終了したときに、
当該読み出しの結果が合意可能状態であることを保証すること
を特徴とする請求項１または請求項２に記載のいずれかの合意手法。
【請求項４】
前記合意可能状態記録ステップでは、
前記合意可能状態記録手段が前記変数ｉの値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録を始めると同時に、状態フラグ部読み出しステップを実行している他のプロセッサの状態フラグ読み出し手段による前記該当領域ｙ[ｉ]の状態フラグ部の読み出しをロックし、
一定時間以内にロックを解除する
ことを特徴とする請求項３に記載の合意手法。
【請求項５】
前記合意可能状態記録ステップでは、
前記合意可能状態記録手段が
状態β記録ステップを実行している他のいずれかのプロセッサの状態β記録手段による前記共有２値変数配列ｘの記録の開始から終了までの途中であっても、
または、合意可能状態記録ステップを実行している他のいずれかのプロセッサの合意可能状態記録手段による前記共有２値変数配列ｘの読み出しの開始から終了までの途中であっても、
合意可能状態記録手段による前記共有２値変数配列ｘの読み出し開始に
前記共有２値変数配列ｘに記録されていた状態か、
前記状態βのどちらか一方のみを一定時間以内に読み出すという、
前記共有２値変数配列ｘの書き込みの最中の多重読み出しを許し、
前記状態β記録ステップでは、
前記状態β記録手段が、
状態β記録ステップを実行している他のいずれかのプロセッサの状態β記録手段による前記共有２値変数配列ｘの記録の開始から終了の途中であっても、または、
合意可能状態記録ステップを実行している他のいずれかのプロセッサの合意可能状態記録手段による前記共有２値変数配列ｘの読み出しの開始から終了までの途中であっても、
前記共有２値変数配列ｘに状態βと一定時間以内に書き込むという、
前記共有２値変数配列ｘの読み出し最中の多重書き込みを許す、
ということを特徴とする請求項１及至４のいずれか１項に記載の合意手法。
【請求項６】
非同期に動作し、各々異なる識別子をもち、
自己の識別子とすべてのプロセッサの前記識別子からなる識別子集合Ｎを知っており、
自己の識別子を変数ｉに代入している、
２以上のプロセッサと
共有２値変数配列群ｙと共有２値変数配列ｘという共有オブジェクトからなる非同期共有オブジェクトシステムであって、
前記共有２値変数配列群ｙは
前記識別子集合Ｎに属する要素を値として取る変数ｊの任意の値によって参照可能な個別の該当領域ｙ[ｊ]を含み、
前記該当領域ｙ[ｊ]は
合意可能状態、合意不可能状態の２状態のみを記憶でき、初期状態を合意不可能状態とする状態フラグ部と
外部からの入力値を記憶でき、初期値をNULLとする入力値格納部を含み、
前記共有２値変数配列ｘは
状態αと状態βの２状態のみを記録でき、初期状態をαとする、
共有オブジェクトを介してプロセッサが通信する非同期共有オブジェクトシステムであって、
前記プロセッサは各々
外部からの入力値を受け取り、変数ｋに代入する入力値受信手段と、
前記変数ｋに代入された値を前記共有２値変数配列群ｙの自己の識別子を記録している変数ｉの値によって参照可能な該当領域ｙ[ｉ]の入力値格納部に記録する入力値格納手段と、
前記共有２値変数配列ｘの状態がαであるときに限り、
前記共有２値変数配列群ｙの前記変数ｉの値によって参照可能な該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録し、
前記共有２値変数配列ｘの状態がαでないときなにもしない合意可能状態記録手段と、
前記共有２値変数配列ｘに状態βと記録する状態β記録手段と、
前記識別子集合Ｎに属する要素を値として取る変数ｊの任意の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｊ]の状態フラグ部の値を読み出す状態フラグ部読み出し手段と、
前記識別子集合Ｎに属する要素を値として取る変数ｊの任意の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｊ]の
状態フラグ部が合意状態のときに前記該当領域ｙ[ｊ]の入力値格納部の値を
読み出す入力値読み出し手段と、
前記共有２値変数配列ｘの値、または前記識別子集合Ｎに属する要素を値として取る変数ｊの任意の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｊ]の状態フラグ部の値、または入力値格納部の値を外部に出力する外部出力手段と
を有し、
前記合意可能状態記録手段は、
前記変数ｉの値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部の記録の開始から終了までの途中で他のプロセッサの状態β記録手段によって
前記共有２値変数配列ｘが状態βと記録されることを禁止しない、
前記状態β記録手段は前記共有２値変数配列ｘの記録の開始から終了までの途中で
他のプロセッサの合意可能状態記録手段によって前記共有２値変数配列ｘの値が読み出されることを禁止しない、
ことを特徴とする非同期共有オブジェクトシステム。
【請求項７】
前記プロセッサの各々は
前記識別子集合Ｎに属する要素を値として取りうる変数ｊの値であり、かつ、
前記変数ｊに代入された当該の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部の状態が合意可能状態であるという条件を満たす値の集合に属する識別子の中で最も小さい識別子を発見し、
変数ｍに代入するプロセッサ識別子発見手段と、
前記変数ｍに代入された値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｍ]の入力値格納部の値を合意する値とする合意値決定手段と、
をさらに有することを特徴とする請求項６に記載の非同期共有オブジェクトシステム。
【請求項８】
前記合意可能状態記録手段は
前記変数ｉの値により参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録を始めると
同時に、または、以降に他のプロセッサの状態β記録手段による
前記共有２値変数配列ｘへの状態βの記録が開始され終了し、
次に、他のプロセッサの状態フラグ読み出し手段による前記変数ｉの値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部の読み出しが開始され終了したときに、
当該読み出しの結果が合意可能状態であることを保証する
ことを特徴とする請求項６または請求項７に記載のいずれかの非同期共有オブジェクトシステム。
【請求項９】
前記合意可能状態記録手段は
前記変数ｉの値により参照可能な前記共有２値変数配列群ｙの
該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録を始めると
同時に、他のプロセッサの状態フラグ部読み出し手段による
前記該当領域ｙ[ｉ]の状態フラグ部の読み出しをロックし、
一定時間以内にロックを解除する
ことを特徴とする請求項８に記載の非同期共有オブジェクトシステム。
【請求項１０】
前記合意可能状態記録手段は
他のいずれかのプロセッサの状態β記録手段による
前記共有２値変数配列ｘの記録の開始から終了までの途中であっても、
または、他のいずれかのプロセッサの合意可能状態記録手段による
共有２値変数配列ｘの読み出しの開始から終了までの途中であっても、
前記合意状態記録手段による前記共有２値変数配列ｘの読み出し開始に
前記共有２値変数配列ｘに記録されていた状態か、
前記状態βのどちらか一方のみを一定時間以内に読み出すという、
前記共有２値変数配列ｘの書き込み最中の多重読み出しを許し、
前記状態β記録手段は
他のいずれかのプロセッサの前記状態β記録手段による前記共有２値変数配列ｘの記録の開始から終了までの途中であっても、
または、他のいずれかのプロセッサの合意可能状態記録手段による前記共有２値変数配列ｘの読み出しの開始から終了までの途中であっても、
前記共有２値変数配列ｘに状態βと一定時間以内に書き込むという、
前記共有２値変数配列ｘの読み出し最中の多重書き込みを許す、
ことを特徴とする請求項６乃至９のいずれか１項に記載の非同期共有オブジェクトシステム。
【請求項１１】
他のプロセッサの識別子とは異なる識別子をもち、
自己の識別子とすべてのプロセッサの識別子からなる集合Ｎを知っていて、
自己の識別子を変数ｉに代入しているプロセッサであって、
非同期に動作する他のプロセッサと
共有２値変数配列群ｙと共有２値変数配列ｘという共有オブジェクトを介して通信するプロセッサであって、
前記共有２値変数配列群ｙは
前記識別子集合Ｎに属する要素を値として取る変数ｊの任意の値によって参照可能な個別の該当領域ｙ[ｉ]を含み、
前記該当領域ｙ[ｉ]は合意可能状態、
合意不可能状態の２状態を記憶でき、初期状態を合意不可能状態とする状態フラグ部と
外部からの入力値を記憶でき、初期値をNULLとする入力値格納部を含み、
前記共有２値変数配列ｘは
状態αと状態βの２状態を記録でき、初期状態をαとする、
共有オブジェクトを介して通信するプロセッサであって、
外部からの入力値を受け取り、変数ｋに代入する入力値受信手段と、
前記変数ｋに代入された値を前記共有２値変数配列群ｙの自己の識別子を記録している変数ｉの値によって参照可能な該当領域ｙ[ｉ]の入力値格納部に記録する入力値格納手段と、前記共有２値変数配列ｘの状態がαであるときに限り、
前記共有２値変数配列群ｙの前記変数ｉの値によって参照可能な該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録し、
前記共有２値変数配列ｘの状態がαでないとき、なにもしない合意可能状態記録手段と、
前記共有２値変数配列ｘに状態βと記録する状態β記録手段と、
前記識別子集合Ｎに属する要素と値として取る変数ｊの任意の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｊ]の
状態フラグ部の値を読み出す状態フラグ部読み出し手段と、
前記識別子集合Ｎに属する要素を値として取りうる変数ｊの値であり、かつ、
変数ｊに代入された当該の値で参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｊ]の状態フラグ部の状態が合意可能状態であるという条件を満たす値の集合に属する識別子の中で最も小さい識別子を発見し、変数ｍに代入するプロセッサ識別子発見手段とを有し、
前記合意可能状態記録手段は
前記変数ｉの値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部の記録の開始から終了までの途中で他のプロセッサの状態記録手段によって
前記共有２値変数配列ｘが状態βと記録されることを禁止しない、
前記状態β記録手段は
前記共有２値変数配列ｘの記録の開始から終了までの途中で他のプロセッサの合意可能状態記録手段によって前記共有２値変数配列ｘの値が読み出されることを禁止しない、
ことを特徴とするプロセッサ。
【請求項１２】
前記合意可能状態記録手段は
前記変数ｉによって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録を始めると
同時に、または、以降に他のプロセッサの状態β記録手段による
前記共有２値変数配列ｘへの状態βの記録が開始され終了し、
次に、他のプロセッサの状態フラグ部読み出し手段による前記変数ｉの値によって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部の読み出しが開始され終了したときに、
当該読み出しの結果が合意可能状態であることを保証する
ことを特徴とする請求項１１に記載のプロセッサ。
【請求項１３】
前記合意可能状態記録手段は
前記変数ｉによって参照可能な前記共有２値変数配列群ｙの該当領域ｙ[ｉ]の状態フラグ部に合意可能状態と記録を始めると
同時に、他のプロセッサの状態フラグ読み出し手段による
前記該当領域ｙ[ｉ]の状態フラグ部の読み出しをロックし、
一定時間以内にロックを解除する
ことを特徴とする請求項１２に記載のプロセッサ。
【請求項１４】
前記合意可能状態記録手段は
他のいずれかのプロセッサの状態β記録手段による
前記共有２値変数配列ｘの記録の開始から終了までの途中であっても、
または、他のいずれかのプロセッサの合意可能状態記録手段による
前記共有２値変数配列ｘの読み出しの開始から終了までの途中であっても、
合意可能状態記録手段による前記共有２値変数配列ｘの前記読み出し開始に
前記共有２値変数配列ｘに記録されていた状態か、
前記状態βのどちらか一方のみを一定時間以内に読み出すという、
前記共有２値変数配列ｘの書き込みの最中の多重読み出しを許し、
前記状態β記録手段は、
他のいずれかのプロセッサの状態β記録手段による前記共有２値変数配列ｘの記録の開始から終了であっても、
または、他のいずれかのプロセッサの合意可能状態記録手段による前記共有２値変数配列ｘの読み出しの開始から終了までの途中であっても、
前記共有２値変数配列ｘに状態βと一定時間以内に書き込むという、
前記共有２値変数配列ｘの読み出し最中の多重書き込みを許す、
ということを特徴とする請求項１１乃至１３のいずれか１項に記載のプロセッサ。
【発明の詳細な説明】
【０００１】
複数の非同期プロセッサが共有オブジェクトを介して通信し合う共有オブジェクトシステムにおいて、故障していないプロセッサの全てが故障により停止したプロセッサの影響を受けることなく有限ステップ後に合意を得る手法、耐故障性をもつ非同期共有オブジェクトシステムにおける合意問題を
解く手法、および、それらの実現に必要な機構と、多重書き込み多重読み出し可能な２値変数配列と単一書き込み多重読み出し可能な２値変数配列とを実現する機構。
【従来の技術】
【０００２】
複数のプロセッサからなる共有オブジェクトシステムにおいて、故障して停止しているプロセッサに関わらず、故障していないプロセッサの全てが１つの値に合意する非同期共有オブジェクトシステムにおける耐故障合意問題は非同期システムにおける同期化およびプロセッサの故障検出に有効な応用をもつ。非同期共有オブジェクトシステムは複数のプロセッサと有限個の共有２値変数配列の集合である共有オブジェクトからなる。プロセッサは共有２値変数配列を介して通信する。各プロセッサは入力動作や出力動作を行い外部と対話するためのポートをもつ。Vをある値の集合とし、1からnまでの自然数でラベル付けされたn個のプロセッサと共有２値変数の集合Xからなる共有オブジェクトシステムを考える。各プロセッサへの外部入力をinit(v)とする。ここで、vは集合Vの要素である。また、各プロセッサはdecide(v) の形で外部に出力する。
【０００３】
各プロセッサは特別な入力 Stop をもつ可能性がある。Stop信号は特定できない外部からの入力で、プロセスのStop信号受信後は動作を停止する。共有オブジェクトシステムが以下の３つの条件を満たすとき合意に達する。
（１） 任意のプロセッサに対して、そのプロセッサのinitとdecideとの時間的系列は列init(v)、 decide(w)のある接頭辞である。
つまり、何もないか、init(v) のみであるか、init(v)、 decide(w)の2つの動作の列である。
（２） 全ての決定値は同じ値である。(Agreement条件)  （３） 決定値はあるプロセッサの入力値である。(Validity条件)
【０００４】
共有オブジェクトシステムで１からn-1までの任意の個数のプロセッサがStop信号を受信して停止した場合でも、残りの停止していないプロセッサの全てが合意するとき、システムは耐故障合意に達する。
【０００５】
この耐故障合意を共有オブジェクトの各２値変数配列を適用可能な操作でタイプ分けした場合、どのような手法が存在するかを示す。従来、共有オブジェクトの２値変数配列は1命令中に読み出しまたは書き込みのみを許すread-write ２値変数配列と書き込みと読み出しの両方を1命令中に実行可能な read-modify-write ２値変数配列に大別される。非同期共有オブジェクトシステムでは、read-write２値変数配列のみでは耐故障合意が得られない。初期値unknownである共有２値変数配列xを用いる合意手法の具体例を示す。
【０００６】
外部からの入力値をkとする。次に、read(x)命令により共有２値変数配列xの値を戻り値vとして受け取る。もし、値vが初期値unknownのままであれば、write(x、k)命令により共有２値変数配列xにkの値を代入しdecide(k)で値kに合意する。そうでなければ、decide(v)で値vに合意する。この場合共有オブジェクトの内容を読み込んで、プロセッサがその内容に従って書き込みを行う前に共有オブジェクトの内容が変化してしまうことで不合意を導いてしまう。
【０００７】
そこで、読み出しと書き込みの両方を1命令で行うread-modify-write により耐故障性をもつ合意手法が考えられる。read-modify-write命令の1つであるcompare-and-swap命令について説明する。共有２値変数配列xと値v、 値kにおいてcompare-and-swap(x、v、k)命令は共有２値変数配列xの値wがvと一致するなら共有２値変数配列xに値kを書き込み値wを戻り値として返す。そうでなければ何もせず、値wを戻り値として返す。この手続きを１命令ステップ中に実行する。
【０００８】
compare-and-swap命令による耐故障合意を得る手法の例を示す。初期値がunknownである共有２値変数配列xにおいて、始めに外部からの入力値をkとする。次に、compare-and-swap(x、unknown、k)命令により共有２値変数配列xの値wがunknownならxにkを書き込み戻り値としてunknownを受け取る。そうでなければ、wを戻り値として受け取る。compare-and-swap命令の戻り値vがunknownなら、decide(k)により値kに合意する。そうでなければ、decide(v)により値vに合意する。
【０００９】
共有２値変数配列内容の多重書き込みを許さない単一書き込みのみ可能な２値配列変数xの場合、read-modify-write命令を実行中、変数xはロックされ、変数xに対する他の全ての命令が実行不能となる。
【００１０】
複数のプロセッサが同時に変数xに対するread-modify-write命令を発行した場合、プロセッサ数の長さをもつロックの連なりができてしまう。この状況を競合と呼ぶ。また、１つの命令に対してできる可能性のあるロックの連なりに属しているロックの最大個数、つまり、長さを競合のコストとする。
【発明が解決しようとする課題】
【００１１】
非同期に動作する複数のプロセッサ間で、故障したプロセッサが存在すると高速に、かつ、競合なく合意を得ることができないという問題点。
【００１２】
更に、実現機構で使用する多重書き込み多重読み込み可能な２値変数配列と単一書き込み多重読み込み可能な２値変数配列は、通常では２値変数に対する書き込みの間の読み込みや
読み込みの間の書き込みが頻繁に発生するために、２値変数の整合性を保つための処理時間や、物理的な装置を多く用いて実現しなければならないという問題点。
【課題を解決するための手段】
【００１３】
上記の問題点を解決するために、ある共有２値変数配列の読み込みともう一方の共有２値変数配列の書き込みを１ステップで実行するread-and-write命令を使用する。更に、本発明の共有オブジェクトシステムではプロセッサと共有オブジェクトの通信手段として使用する外部入出力ポートと、共有オブジェクトが認識可能な命令に変換する命令フェッチブロックと、命令を認識する命令デコーダと、共有２値変数配列の値を管理・保持するフラグブロックと、個別用フラグの値を読み込む個別フラグ読み込みブロックと、外部入力値格納ブロックとを備える機構を使用する。
上記のある共有２値変数配列の読み込みともう一方の共有２値変数配列の書き込みを1ステップで実行するread-and-write命令において、その命令の発行から応答までの時間がread-and-write命令の書き込み対象以外の共有２値変数配列の書き込み命令の発行から応答までの時間とread-and-write命令の書き込み対象である共有変数配列の読み込み命令の発行から応答までの時間の総和以下であるときに、read-and-write命令により書き込まれた内容が先に述べた読み出し命令の応答となることが保証されているという条件（以下、「ロック不必要条件」という）を上記ブロック構成だけで満たす場合は上記機構をそのまま使用する。一方で、先のロック不必要条件を満たさない場合には上記のブロックに加え、共有２値変数配列の値を書き込み中は読み込むことができないように制御するロックブロックを備えなければならない。
【００１４】
本発明の共有オブジェクトシステムは多重書き込み多重読み出し可能な共有２値変数配列ｘと単一書き込み多重読み出し可能な共有２値変数配列群ｙを備え持つ。
【００１５】
本発明で使用する多重書き込み多重読み出し可能な２値変数配列は、２つの状態を示す値しかとり得ないという点と、ある状態を示す値からもう一方の状態を示す値へ変化し、その後値の変化はないという点が通常の多重書き込み多重読み出し可能な２値変数配列とは異なる。単一書き込み多重読み出し可能な共有２値変数配列群に関して、ある値への書き込みの間にある値への読み出しは発生しないという点が通常の単一書き込み多重読み出し可能な共有２値変数配列群とは異なる。
【００１６】
本発明で使用する多重書き込み多重読み出し可能な２値変数配列と、単一書き込み多重読み出し可能な共有２値変数配列群は、上記の特性を利用し、多重書き込み多重読み出し可能な２値変数配列と単一書き込み多重読み出し可能な共有２値変数配列群を、同数のプロセッサに対応できる一番小さい規模の通常のものと比較して、物理的な規模を小さく、かつ、命令に対する出力をプロセッサの数に依存することなく実現することができる。
【００１７】
本発明で使用する共有２値変数配列群ｙはプロセッサのインデックス(1,...,n)毎の連続する領域を持ち、その領域をさらに状態フラグ部と入力値格納部の2領域に分割する構造である。
【００１８】
非同期で動作するn個のプロセッサと共有オブジェクトとの通信手段としてn個の外部入出力ポートを共有オブジェクトに備える。プロセッサ１つに対して入出力ポート１つが対応する。プロセッサと共有オブジェクトは必ず外部入出力ポートを介して通信し合う。
【００１９】
各プロセスから外部入出力ポートに送られた信号は、共有オブジェクト内の命令フェッチブロックに送られる。命令フェッチブロックは各外部入出力ポートに対してひとつ存在する。外部入出力ポートに送られた信号は、命令フェッチブロックによって共有オブジェクトに対する命令に変換される。
【００２０】
命令デコーダは、共有２値変数配列群ｙのプロセッサｉの状態フラグ部を読み出すという信号を命令フェッチブロックが受け取った後、個別フラグ読み込みブロックに変換した信号を送る。
個別フラグ読み込みブロックに信号を送る際にｉを識別可能な信号に変換する。この際、先のロック不必要条件を満足しないような共有オブジェクトシステムの場合はロックブロックを必要とするため、個別フラグ読み込みブロックとロックブロックの両ブロックへｉを識別可能な信号を送る。
【００２１】
ロックブロックでは命令フェッチブロックから共有２値変数配列群ｙの領域ｊの状態フラグ部をロックするという信号と命令デコーダから共有２値変数配列群ｙの領域ｋの状態フラグ部を読み出すという信号と、フラグブロックから共有２値変数配列ｘの状態を入力として受ける。
【００２２】
ロックブロックはプロセッサiのread-and-write命令中に条件が成立する場合に共有２値変数配列群ｙの領域iの状態フラグ部の値を読み出すことができないようにロックする機構である。それに加えて各入力がいくつ同時に発生したとしても出力は正常である特性を持つ。命令デコーダから入力として受ける共有２値変数配列群ｙの領域ｊの状態フラグ部を読み出すという信号に対して共有２値変数配列群ｙの領域ｊの状態フラグ部がロックされているかどうかの結果を出力する。
【００２３】
フラグブロックは共有２値変数配列ｘと共有２値変数配列群ｙの値を管理・保持するブロックである。命令フェッチブロックから入力を受け２値変数配列の値を操作する。複数の命令フェッチブロックからの信号が同時に発生したとしても結果は正常に出力されるという特性を持つ。共有２値変数配列群ｙの状態フラグ部の値が出力される。
【００２４】
個別フラグ読み込みブロックでは、共有２値変数配列群ｙの状態フラグ部の値を読み出す。入力として命令デコーダからどの値を読み出すかを示す信号とフラグブロックから共有２値変数配列群ｙの状態フラグ部の値を受ける。共有２値変数配列群ｙの状態フラグ部の値を出力する。入力の際に、命令デコーダからいくつ同時に信号を受けたとしても出力は正常であるという特性を持つ。
【００２５】
外部入力値格納ブロックでは、共有２値変数配列群ｙの入力値格納部の値、つまり各プロセッサが合意すべき入力値を保持・管理する。入力として命令フェッチブロックから値格納先の場所と書き込みの際の値と読み出しか書き込みかを区別する信号とを受ける。この際に、入力がいくつ同時に発生しても出力は正常であるという特性を持つ。
【００２６】
初期設定としてｘを状態αとし、ｙの各状態フラグ部は合意不可能状態とし各入力値格納部にはnull値を設定する。上記の機構を用いて、各プロセッサｉにおいて以下のプロトコルを実行する。始めに入力値ｋとする。次に共有２値変数配列群ｙの領域ｉの入力値格納部に値ｋを書き込む。次にread-modify-write命令を実行し共有２値変数配列ｘが状態αであるならば共有２値変数配列群ｙの領域ｉの状態フラグ部を合意可能状態とする、そうでなければ何もしない。次に共有２値変数配列ｘを状態βとする。次にプロセッサインデックスの昇順に共有２値変数配列群ｙの先頭の領域１の状態フラグ部から順に合意可能状態か否かを調査し、合意可能状態が発見できるまで調査を続ける。次に最初に合意可能状態を発見した領域の入力値格納部の値を読み出し、合意すべき値として決定する。
【００２７】
発明合意プロトコルではシステム中に故障したプロセッサが存在しても、故障していないプロセッサはプロトコルを終了することができる。発明合意プロトコルを発明機構を用いて実施した場合、各命令に対するロックの連なりは高々１であり、発明合意プロトコルの競合コストは１である。このことは、先のロック不必要条件を満足しない共有オブジェクトシステムでロックブロックを使用して実現した場合でも同様である。
【００２８】
更に、本発明機構に備える、多重書き込み多重読み込み可能な共有２値変数配列と、単一書き込み多重読み込み可能な共有２値変数配列とを、制限された動作のみを保障することで、２値変数配列の整合性を保つために要する処理のサイクル時間の短縮と、物理的に小さな規模での実現が可能となる。
【図面の簡単な説明】
【図１】ロック不必要条件を満たす共有オブジェクトシステムの実現機構
【図２】ロック不必要条件を満たさないロック機構を必要とする共有オブジェクトシステムの実現機構
【図３】ロック不必要条件を満たす非同期共有オブジェクトシステムの実現機構
【図４】ロック不必要条件を満たさないロック機構を必要とする非同期共有オブジェクトシステムの実現機構
【図１】
0005201434.tif 000002
【図２】
0005201434.tif 000003
【図３】
0005201434.tif 000004
【図４】
0005201434.tif 000005