JPH0628199A - 並行処理の同期方法 - Google Patents

Abstract

(57)【要約】 【目的】 コンピュータシステムにおける並行処理を同
期化するための方法を提供する。 【構成】 メッセージが受信され、処理によって作動さ
れる際に、そのようなメッセージが処理の現在の仮想時
間よりも大きいか待ち行列それに等しい受信時間を有し
ている場合、状態の一致性が仮定できる。ガード検査が
使用可能となっていれば、ガードは好ましくは、そのメ
ッセージが作動する以前に満たされていなければならな
い。メッセージの受信時間が現在の仮想時間よりも小さ
い場合、さらに状態の一致性検査が行われる。このよう
な一致性検査は変数バージョンおよびガードの一致性の
検査を含む。処理の状態がメッセージの内容と一致すれ
ば、そのメッセージは、たとえ現在の仮想時間がメッセ
ージの受信時間より大きくても、処理されることができ
る。同様の一般的方法は、仮想タイムスタンプおよび変
数バージョンによって共用変数が状態の一致性を検査さ
れる、並行動作を有する１処理内でも使用することがで
きる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、電子計算機システム、
より詳しくは１コンピュータシステム内の並行処理の動
作を制御する方法に関する。

【０００２】

【従来の技術およびその問題点】コンピュータのアプリ
ケーションは、一連の論理処理がそのアプリケーション
に要求する作業を分割する場合、並行同時的に実行す
る。処理は、多重プログラミング環境におけるプログラ
ム、多重プロセッサまたは多重コンピュータのシステム
のプロセッサの活動、他のトランザクションと並行同時
的にデータベースにアクセスするトランザクション、ま
たは、目的向き計算における目的などである。

【０００３】並行処理は、密結合または疎結合であると
分類することもできる。密結合処理は、共通にアクセス
された記憶空間の変数を共用することによって相互作用
する。疎結合処理は、各処理が自己の記憶空間に単独に
アクセスしながら、処理間でメッセージを渡すことによ
って相互作用する。

【０００４】疎結合処理の場合、メッセージは非同期的
に渡すことができるので、処理間での情報の単方向転送
が可能である。メッセージは同期させて渡すこともで
き、この場合、単方向または双方向の情報転送が可能で
ある。

【０００５】同期化の一般的方法は、ペシミスティック
またはオプティミスティックのいずれかに分類できる。
ペシミスティックな方法は、並行演算の間違った順序づ
けが絶えず発生しないようにするものである。これは、
システムの大域的状態がある演算を実行する前にその演
算と一致しているようにすることによって達成できる。
オプティミスティックな方法は、局所的に使用可能な情
報にもとづいて順序づけを実行し、後に演算の順序づけ
が間違っていることが分かった場合に、以前に一致して
いた状態へのロールバックを行う。ペシミスティックな
方法は、演算を実行する前に大域的なシステム状態を検
査する時間を比例増加的に費やし、演算を繰り返す必要
はない。オプティミスティックな方法は、演算を実行す
る前に局所的なシステム状態を検査する最小限の時間を
費やすが、場合によってはロールバックが発生した後に
いくつかの演算を繰り返し実行しなければならないこと
もある。

【０００６】並行処理の同期化を容易にするために多数
の基本的な方法が使用されている。これらの方法には、
ガード、データバージョン、および、事象インデックス
を使用することが含まれる。ガードは処理の各動作に関
する述語である。ある動作のガードは、その動作の実行
が許可される前に真でなければならない。

【０００７】データバージョンの使用は、並行計算の順
序が正しい計算順序に一致するように、並行計算によっ
て利用されるデータに対して行われるタギング変更を含
む。処理は、それらが作成しアクセスするデータのバー
ジョンに関連づけられる。この方法の使用の例に、デー
タベースのためのマルチバージョン並行性制御がある。

【０００８】タイムスタンプやシーケンス番号などの事
象インデックスは、それぞれの順序が事象の因果的順序
に一致するように並行計算の事象にタグを付けるために
使用される。これらのインデックスは、事象を処理と関
係づけることによって並行計算を同期化するために使用
できる。このような方法の一例が、Ｄ．Ｒ．Ｊｅｆｆｅ
ｒｓｏｎによって開発され、“Ｖｉｒｔｕａｌ Ｔｉｍ
ｅ”（Ｄａｖｉｄ Ｒ．Ｊｅｆｆｅｒｓｏｎ，ＡＣＭ
Ｔｒａｎｓａｃｔｉｏｎｓｏｎ Ｐｒｏｇｒａｍｍｉｎ
ｇ Ｌａｎｇｕａｇｅｓ ａｎｄ Ｓｙｓｔｅｍｓ，
Ｖｏｌｕｍｅ ７， Ｎｏ．３， Ｊｕｌｙ １９８
５， ｐｐ．４０４−４２５）で説明された“タイムワ
ープ”機構である。この機構は、オプティミスティック
な方法による非同期式メッセージパッシングモデルにも
とづいている。各局所的処理は関係づけられた局所仮想
時間を持っている。処理間で渡されたメッセージは、そ
れらが受信されるべき仮想時間を刻印される。処理がメ
ッセージを受信すると、メッセージの受信時間がその処
理の現在の仮想時間に満たない場合、処理はすでに、メ
ッセージが届くはずであった時点を過ぎて進んでいる。
このような事象では、処理はメッセージの受信時間より
も前の仮想時間にロールバックされる。これは、多数の
動作の取消しを含み、その後、処理は再始動し、受信さ
れたメッセージが作用する。

【０００９】“タイムワープ”機構に関する問題の一つ
は、その効率が本来求められるべき効率よりも著しく低
くなり得ることである。その処理の現在の仮想時間より
も小さい受信時間を持つメッセージが受信されると常
に、処理はロールバックされる。ある場合には、処理が
このメッセージを処理した後に再始動すると、計算は以
前同様に正確に進行する。言い換えれば、メッセージの
内容および、その処理は、ロールバックしたいずれの動
作に対しても影響しなかったことになる。処理のロール
バックおよびその動作の再実行は費用がかかるので、実
行される不要なロールバック量を最小限にするように並
行処理を同期させるための方法を付与することが望まし
いであろう。

【００１０】上述と同様の考慮は、１処理内の並行動作
がデータを共用する場合にも生じる。通常、１処理内の
並行動作が不一致状態にならないように各種のロック方
式が使用されている。１処理内の共用変数についてのタ
イムスタンプ順序づけの利用は、“タイムワープ”機構
に関する上述と同様の非効率を生ずる。１処理の動作を
実行するために必要な合計時間と実行されなければなら
ないロールバック量の双方を最小限にするように処理の
並行動作を同期させるための方法を付与することが望ま
しいであろう。さらに、そうした方法が、上述の課題に
配慮した処理間同期方法と両立し矛盾しないことも望ま
しいであろう。

【００１１】

【問題点を解決するための手段】従って、本発明の目的
は、コンピュータシステムにおける並行処理間の同期お
よび状態の一致性を保証するための方法を提供すること
である。本発明の第２の目的は、データの不一致の発生
を最小限にする局所的に使用可能な情報にもとづいて処
理が進行できるようにし、かつ、不一致が生じた場合に
は必要な再計算の量を最小限にする、そうした方法を提
供することである。本発明の第３の目的は、データを共
用する並行動作の１処理内の同期を行うために使用でき
るような方法を提供することである。

【００１２】従って、本発明によれば、コンピュータシ
ステムにおける並行処理を同期させるための方法が得ら
れる。各処理は仮想時間を有する。メッセージが受信さ
れ、処理にって作用される際、これらのメッセージはそ
の処理の現在の仮想時間に等しいかそれより大きい受信
時間を有している場合、状態の一致性が仮定できる。ガ
ード検査が使用可能であれば、ガードは、好ましくは、
メッセージが作用される以前にすでに満たされていなけ
ればならない。メッセージの受信時間が現在の仮想時間
に満たない場合、さらに状態の一致性の検査が行われ
る。このような一致性検査は変数バージョンおよびガー
ドの一致性の検査を含むことができる。処理状態がメッ
セージの内容と一致すれば、そのメッセージは現在の仮
想時間がメッセージの受信時間よりも大きい場合でも処
理されることができる。同様の一般的方法は、共用変数
が仮想タイムスタンプや変数バージョンによって状態一
致性を検査される、並行動作を有する１処理内でも使用
することができる。

【００１３】

【実施例】図１について説明する。処理Ｐ，ＱおよびＲ
の同時実行が図式的に示されている。矢印１０は処理Ｐ
の進行を、同様に、矢印１２は処理Ｑの、矢印１４は処
理Ｒの進行をそれぞれ示している。これらの各線１０，
１２および１４の下方への動きは、各処理によって遂行
された作業量が増えたことを表現する。これらの時間線
１０，１２および１４上の丸点は、１処理内における事
象、または動作を表し、波線１６，１８，２０および２
２は処理間で送られたメッセージを表す。各メッセージ
は、送信側処理の局所仮想時間に送信され、受信側処理
の局所仮想時間に受信される。例えば、メッセージ１６
は、事象Ｐ１で示された処理Ｐの局所仮想時間に送信さ
れ、事象Ｑ４で示された処理Ｑの局所仮想時間に受信さ
れている。

【００１４】各処理間のメッセージの送信はこれらの処
理内の各事象間の優先順位関係を確定する。処理時間線
１０，１２および１４ならびにメッセージ線１６，１
８，２０および２２に沿って、ある事象から別の事象へ
１経路を描くことができれば、これらの処理は規定の順
序で実行されなければならない。例えば、事象Ｐ１は事
象Ｑ４よりも前に実行されなければならず、事象Ｒ１は
事象Ｐ２よりも前に実行されなければならない。２事象
間に経路がまったく描くことができなければ、それらの
事象はまったく同時並行であり、いずれかの順序で実行
されることになる。例えば、事象Ｐ１は、事象Ｒ１，Ｑ
１，Ｑ２，Ｑ３およびＲ４のいずれとも同時並行であ
る。事象Ｑ４は事象Ｐ２およびＲ２と同時並行である。

【００１５】図２は、本発明に従って並行性制御を行う
ために使用されるメッセージ２４の内容を示す。本発明
による処理同期化には要求されない、付加的な制御信号
および情報は、含めることは可能であるが、示されては
いない。各メッセージは、送信側処理の識別子２６およ
び受信側処理の識別子２８を有している。メッセージが
送信された時間の送信側処理３０の局所仮想時間が含ま
れる。要求受信時間３２がメッセージに付加され、メッ
セージが含む何らかのデータ３５がそれに続く。

【００１６】メッセージ２４の受信時間３２は、送信側
処理の送信時間３０に等しいかそれより大きい仮想時間
として表される。受信側処理は受信時間３２にメッセー
ジを読取り、処理しなければならない。送信側処理が、
受信側処理の仮想時間がメッセージ２４の処理される時
がどのような時であるかを考慮しない場合、ＮＵＬＬの
ような特殊な標識をメッセージ２４の受信時間領域３２
に置くことができる。

【００１７】図３は、２処理間のメッセージの渡り方を
示している。送信側処理３４はメッセージ３６を生成
し、図２に関して述べたように情報を満たす。このメッ
セージ３６はその後、システムによって付与されたいず
れかの機構によって受信側処理３８に転送される。多重
プロセッサシステムまたは複数コンピュータリンケージ
の場合では、それぞれ、メッセージ３６は、システムバ
スまたはネットワークによって渡すことができる。並行
処理がすべて単一のプロセッサで実行される場合、メッ
セージ３６は通常、大域的システムエリアに置かれた情
報によって転送される。

【００１８】受信側処理３８は、通常、メッセージ３６
が到着してすぐにメッセージを作用させることはない。
代わりに、メッセージ３６は待ち行列４０に入れられ
る。待ち行列４０は、着信メッセージがメッセージ受信
時間３２によって順序づけられる優先待ち行列である。
受信側処理３８は、待ち行列４０からメッセージを選択
する準備ができると、最小要求受信時間３２を持った未
処理メッセージを選択する。

【００１９】受信側処理３８は、標識線４２で示された
局所仮想時間を有している。処理３８が待ち行列４０か
らメッセージを受け取るごとに、処理はその局所仮想時
間４２をメッセージの受信時間３２に向けて進める。処
理３８の局所仮想時間４２がメッセージ３６の受信時間
３２に満たない時点でメッセージ３６が待ち行列４０に
着信した場合、メッセージは、矢印４４および４６で示
される将来に処理されるようにする位置で待ち行列４０
に入れられる。

【００２０】時には、メッセージ３６が矢印４８で示し
たような局所仮想時間４２にも満たない受信時間３２を
有することがある。こうした場合、受信側処理３８の仮
想時間は、メッセージ３６をすでに処理すべきであった
時点を過ぎてしまっていることになる。前述の“ワープ
タイム”機構のような、従来技術によるシステムでは、
受信側処理３８の局所仮想時間はメッセージ３６の受信
時間３２以前の値までロールバックされなければならな
い。これは、受信時間３２に一致する局所仮想時間と現
在の局所仮想時間４２との間に実行されたすべての動作
を取り消すことを包含する。

【００２１】ロールバックを実行する処理は、受信側処
理３８を以前の退避された状態まで戻し、その間に送信
されていたあらゆるメッセージを取り消すことを伴う。
処理の出力待ち行列に転送されたすべてのメッセージの
コピーの退避方法および、ロールバックの事象でそうし
たすでに送信されていたメッセージを取り消すための除
去メッセージの転送方法を含む、この実行方法に関する
詳細は、前述のＤ．Ｒ．Ｊｅｆｆｅｒｓｏｎによる論文
“Ｖｉｒｔｕａｌ Ｔｉｍｅ”に詳述されている。大域
的仮想時間５０は、通常、待ち行列４０でいずれかの処
理を待っている、または、現在システム内を通過中の、
最も古い未処理メッセージと同程度以上に古い仮想時間
である。Ｊｅｆｆｅｒｓｏｎの参考文献に述べられてい
るように、大域的仮想時間５０は、ロールバックが生じ
る時点を過ぎた仮想時間を表し、すべての処理は、大域
的仮想時間より以前のメッセージおよびその間に退避さ
れた処理状態を放棄することができる。

【００２２】各処理は互いに独立した仮想時間で動作し
ているので、メッセージ３６が受信側処理３８の現在の
局所仮想時間４２より以前の受信時間３２を持つことは
まれではない。これは、処理３８がメッセージ３６の受
信時間３２より前の仮想時間にロールバックされなけれ
ばならないことになり、これは相当に時間・資源集約的
な手続きである。多くの場合、ロールバックは、メッセ
ージ３６の内容がロールバックの間に行われなかった動
作にまったく影響していなかったので、必要でない場合
さえある。

【００２３】図４は、メッセージが作用されるべきかロ
ールバックが必要かを判断するために待ち行列４０のメ
ッセージを取り出す際に受信側処理３８により利用され
る、好ましい手順のフローチャートである。最初のステ
ップ５２は、受信側処理３８が待ち行列から次のメッセ
ージを選択することである。選択されたメッセージは、
まだ作用されていないいずれかの未決定のメッセージの
うち最も早い受信時間３２を有するような、待ち行列４
０のメッセージである。その後、メッセージの受信時間
Ｔ（Ｍ）がその処理の現在の局所仮想時間Ｔ（Ｐ）であ
るか否かを判断するために比較５４が行われる。メッセ
ージの受信時間が現在の局所仮想時間よりも大きい場
合、局所仮想時間は進められ、メッセージの受信時間に
等しく設定される５６。メッセージの時間が局所仮想時
間に満たない場合、処理は自動的にロールバックされる
ことはなく、その代わり、メッセージ内の参照されるい
ずれかの変数Ｖ（Ｍ）が受信側処理３８内の現在の処理
変数バージョンＶ（Ｐ）と異なっているかどうかを判断
するために検査が行われる５８。当業で公知のように、
これらの処理変数バージョンは、それが必要になる場
合、以前の状態へのロールバックを可能にするために処
理によって保持される。ステップ５８では、受信メッセ
ージを処理するために必要な変数が処理の現在の状態に
一致しているかどうかを判断するために検査が行われ
る。

【００２４】ステップ５８の試験に対する答えが肯定で
あれば、処理を初期状態にロールバックする必要はな
い。メッセージの処理に必要な変数は、受信側処理３８
が後の仮想時間に移行されている間に変更されておら
ず、ロールバックの間の一時的なすべての動作を取り消
すことは不要であろう。処理の現在の状態は、そのメッ
セージに関する限り、以前の仮想時間のその状態と一致
しており、それにより制御はステップ６０に渡されるこ
とができる。

【００２５】ステップ６０は、受信側処理３８に付与さ
れたメッセージに対応するいずれかのガードの述語が満
たされているかどうかを判断するための検査ステップで
ある。ガードは、規定の要求条件が満たされるまで１以
上の動作の処理を遅らせるために使用される、当業で公
知の述語である。ガードがステップ６０に達した時に満
足されていれば、制御はステップ６２に渡り、受信メッ
セージを処理するために必要な動作が実行される。ガー
ドが満たされていなければ、例外が発生する６４。好ま
しくは、例外ハンドラはただちにエラーを指示すること
はない。ガードは、未着信メッセージにより生じたロー
ルバックの結果として満たされるようにすることができ
る。そのようなロールバックは大域的仮想時間より遅い
いずれかの仮想時間に対して生じることができるので、
例外ハンドラは、好ましくは、大域的仮想時間が例外が
発生した局所仮想時間に等しいまたはそれより大きくな
るまで、エラーの信号を発しない。この時点では、いず
れの処理も大域的仮想時間より以前の時間にロールバッ
クさせることができないので、ガードを満たすことがで
きなかったことによるエラーは取り消すことができず、
エラーの信号が発信される。

【００２６】ステップ５８からのＮＯ分岐によって指示
された、処理変数の状態が一致しない場合、処理動作ガ
ードは、ステップ６０におけると同様に検査される６
６。動作ガードが満足されない場合、ステップ５４およ
び５８で検査された相対仮想時間および処理バージョン
は無関係となり、動作が実行される６２。制御がステッ
プ６６に達して、ガードが満たされていない場合、処理
の局所仮想時間は、メッセージの受信時間Ｔ（Ｍ）より
前の値にただちにロールバックされる６８。

【００２７】図４で述べた３種類の試験は、ある程度独
立して取り扱うことができる。従って、ステップ５４の
仮想時間の比較、ステップ５８での処理変数バージョン
の比較、ステップ６０および６６で示されたガードの検
査は必ずしもすべて実行される必要はない。全処理状態
のこれらの３部分のそれぞれを検査することは、システ
ムまたはアプリケーション設計者の要求によって、個別
に作動させたり作動させないようにすることができる。

【００２８】変数バージョンおよびガードの試験が使用
禁止となっていれば、ステップ５８，６０および６６は
実行されない。こうした事象では、ロールバックは、メ
ッセージの受信時間が処理の現在の仮想時間よりも小さ
い場合に自動的に実行される。これは、前述の“タイム
ワープ”機構に極めて類似の同期機構をもたらす。仮想
時間の比較５４および処理変数の比較５８の試験が使用
禁止となっていれば、制御はステップ６０に直接渡る。
これは、当業で公知の方法に類似の方法で動作ガードを
単純に検査するシステムをもたらす。システムが、仮想
時間が使用禁止となっていて、こうした方法で作動して
いる場合、ガードが初期に満たされていない場合に例外
ハンドラによって検査される大域的仮想時間はまったく
ない。こうした事象では、例外ハンドラは、単に、ガー
ドが絶えず満たされているかどうかを判断するために待
っているにすぎない。ガードがずっと満たされるように
なれば、対応する動作が実行される６２。ガードがまっ
たく満たされないようになれば、システムが非活動状態
になった場合にエラー状態の信号が発信できる。

【００２９】他の検査の組合せは、設計されるアプリケ
ーションまたはシステムに対する希望によって、適切に
行うことができる。３の独立した検査が行うことができ
るので、検査を行うべきかどうか判断するために使用で
きる、８の組合せが可能である。図４で示したように３
の検査全部を使用可能にすることは、実行されなければ
ならないロールバック数を最小限にするオプティミステ
ィックな非決定性システムをもたらす。

【００３０】図５は、図４のフローチャートで説明した
規則を用いた受信側処理によるメッセージ処理の単純な
例である。リアルクロックタイムは図５で上から下へ増
加する。列７０は、４の異なるメッセージの着信を示
す。各メッセージは単一の文字によって識別されてお
り、各メッセージの要求仮想受信時間が示されている。

【００３１】列７２は、受信メッセージに応答するため
に必要な動作を実行するために受信側処理によって費や
された時間を示す。この単純な例では、受信側処理は、
逐次動作を実行できるにすぎない。しかし、一般には、
基本システムがこうした処理を支援していれば、受信側
処理が動作を並行して実行することは可能である。

【００３２】列７４は、各入力メッセージを処理するた
めに必要な動作の実行において更新されなければならな
い変数を示している。列７６は、各メッセージが処理さ
れている間の処理の仮想時間を示す。この局所仮想時間
は単一メッセージの処理中には変更されない。列７８は
受信待ち行列４０の現時点でのメッセージおよび、それ
らの優先順位を示す。

【００３３】時間８０において、メッセージＡが着信
し、ただちに受信側処理によって処理される。局所仮想
時間は、このメッセージの要求受信時間と同じ値まで進
められる。メッセージＡが処理されている間に、メッセ
ージＢおよびＣがそれぞれ、時間８２および８４に着信
する。列７８に示すように、メッセージＣは、その２８
という要求受信時間が３０というＢの要求受信時間より
も小さいために、メッセージＢより前に待ち行列に置か
れる。メッセージＡの処理は時間８６に完了する。

【００３４】時間８８に、待ち行列の次のメッセージが
処理のために取り出される。これはメッセージＣであ
り、その結果、メッセージＢだけが待ち行列に残され
る。メッセージＣの要求受信時間は２８なので、局所仮
想時間は２８に設定される。時間９０に、メッセージＤ
が着信し、メッセージＢの前に待ち行列に入れられる。
メッセージＣの処理が時間９２に完了し、時間９４に次
のメッセージＤが処理のために取り出される。

【００３５】この時、メッセージＤの要求受信時間はそ
の処理の現在の仮想時間よりも小さい。しかし、処理は
必ずしも仮想時間２６にロールバックされるとは限らな
い。列７４に示すように、メッセージＡを処理している
間に変数ＸおよびＹが更新され、メッセージＣを処理し
ている間に変数Ｚが更新される。変数の更新は、新しい
処理変数バージョンの生成を要求するが、それらを読取
ることは生成を求めないので、従って新バージョンは更
新された変数についてのみ生成される。列７４に示すよ
うに、変数ＺはメッセージＤの処理においては使用され
ないので、結果的に変数のバージョンは一致している。
言い換えれば、メッセージＣの処理による変数Ｚの更新
は、メッセージＤの処理に影響しない。これは、メッセ
ージＤが仮想時間２６までロールバックすることなく処
理できることを意味する。

【００３６】時間９６にメッセージＤの処理が完了す
る。その後、メッセージＢが待ち行列から取り出され、
時間９８から処理される。メッセージＢの処理は時間１
００に完了する。メッセージＤの処理がいずれかの方法
で変数Ｚの値にアクセスした場合、Ｚの最新の値は、メ
ッセージＤが処理されているはずであった仮想時間２６
の時点で正しくないものであったであろう。この場合、
２つの方法で取り扱うことができる。一つは、単に局所
処理を仮想時間２６までロールバックさせ、メッセージ
Ｃの処理をやり直すことである。しかし、好ましくは、
変数の値は必要な場合にロールバックを実行するために
各バージョンについて退避されているので、メッセージ
Ｄの処理は単に変数Ｚの以前のバージョンを参照できる
だけかもしれない。このロールバックの回避は、Ｚがメ
ッセージＤの処理中に読み出されるだけで書き込まれな
い場合にのみ使用できる。メッセージＤの処理が変数Ｚ
または、メッセージＣの処理によって読み出されたいず
れかの変数を変更させる場合は、処理は仮想時間２６に
ロールバックされるべきである。例えば、メッセージＣ
の処理が、以前の仮想時間にメッセージＤの処理におい
て変更されているはずであった、変数Ｘの値を読み出す
場合、メッセージＣの処理はやり直されなければならな
い。

【００３７】変数のバージョンにもとづいてロールバッ
クを行うべきか否かの上述の決定は、当然、図４のステ
ップ６６に示したガードをうまく検査することによって
無効にすることができる。前述の通り、メッセージ２４
の受信時間３２は送信時間３０に等しいかまたはそれよ
り大きくなければならない。受信時間３２が送信時間３
０より大きければ、（仮想時間に関して）非同期のメッ
セージの渡しが処理間で生じる。送信時間３０と受信時
間３２が等しければ、（仮想時間に関して）同期的なメ
ッセージの渡しが生じる。これは、各処理の状態によっ
て定義された仮想空間内のある時点で、メッセージの送
信処理および受信処理が同一仮想時間に同一状態に達す
ることを意味する。これは、Ａｄａのようなある種のプ
ログラム言語におけるランデブーを実行する技法と類似
である。

【００３８】このような同期通信によって、送信側処理
は、受信側処理が同一の仮想時間に同期されるまで待つ
ことができる。これは、受信側処理がその仮想時間をメ
ッセージの要求受信時間まで進めるか、または、そうし
た仮想時間へのロールバックを許可するかのいずれかに
よって生じることができる。受信側処理はその後、要求
される場合、送信側処理に返信メッセージを生成するこ
とができる。これが生じると、その２処理は、データ交
換を実行するために結合または同期される。同期化時に
実行されるいずれかの事象が発生した後、２処理は独立
した実行を再開できる。

【００３９】図５に関して説明したように、受信側処理
の仮想時間は、別様ではメッセージの仮想受信時間によ
って要求されるであろうロールバックを変数バージョン
の等しいことが防止するのであれば、メッセージの要求
受信時間より大きいことも可能である。しかし、そうし
た状況は、同期メッセージが渡された場合に２の処理の
仮想時間を同期させることに一致しない。従って、好ま
しい実施例では、処理変数バージョンの同等またはガー
ドの満足化にかかわらず、同期メッセージのメッセージ
時間へのロールバックが必ず実行される必要がある。こ
れにより、受信側処理は、受信側処理の仮想時間がロー
ルバックされたので、同期メッセージと同一の仮想時間
を持つ返信メッセージを送信することができる。

【００４０】ロールバックが発生しなければならない場
合を判断するために仮想時間および処理バージョンを使
用する方法は、処理内の並行動作の活動を同期させるた
めに単一処理内で使用することもできる。処理変数の新
しいバージョンが生成される場合、それが生成された仮
想時間およびそれを生成した動作は、そのバージョンに
よって記録される。同一または大きい仮想時間を有する
処理内の動作だけがいずれかの所与のバージョンを読み
出すことができる。あるバージョンを読み出した動作す
べてのリストは、それが必要になった場合にロールバッ
ク手順を単純にするために、各バージョンによって保持
される。

【００４１】図６について説明する。本発明に従って処
理変数バージョンを記録するためのデータ構造が示され
ている。処理変数の現在のバージョン１０２は、その生
成の仮想時間のポインタ１０４、それを生成した動作の
識別子１０６を含んでいる。さらに、リーダリスト１０
８も変数１０２に付加されており、変数１０２を読み出
す各動作についての動作および仮想時間を識別する。同
一変数のその前のバージョン１１０も、仮想時間１１２
およびその生成の生成動作１１４ならびに、変数の以前
のバージョン１１０を読み出した全動作のリーダリスト
１１６を含んでいる。同様に、同一変数のさらに前のバ
ージョン１１８も、生成時間１２０、生成動作識別子１
２２およびリーダリスト１２４を含んでいる。

【００４２】１処理内の並行動作の正しい同期化を保証
するには、変数にアクセスするための以下の規則で十分
である。

【００４３】（１）時間１０４と同じかそれようり大き
い仮想時間を有する動作だけがその変数の現在のバージ
ョン１０２を読み出すことができる。以前の仮想時間を
有する動作はその変数の以前のバージョンを読み出せる
だけである。各動作は、必ず、読み出されることが可能
な変数の最新のバージョンを読み出す。 （２）処理変数の新バージョンが生成される場合、生成
時間は、同一変数のすべての既存のバージョンの生成時
間よりも大きくなければならない。大きい仮想時間を有
する現行バージョンを生成したすべての動作はロールバ
ックされなければならない。さらに、これらのバージョ
ンのリーダリスト上のすべての動作もロールバックされ
なければならない。新バージョンが生成される場合、代
わってこの新バージョンを読み出すべき直前のバージョ
ンのリーダリスト上のすべての動作もロールバックされ
なければならない。こうした場合の例は、１５という仮
想時間に別の動作によって読み出されていた１０という
仮想生成時間を持つ現行の変数バージョンであろう。こ
のような変数の新バージョンが仮想時間１３に生成され
る場合、仮想時間１５に以前のバージョンを読み出した
動作は、仮想時間１３に生成された、より新しいバージ
ョンを読み出すことを可能にするためにロールバックさ
れなければならない。 （３）各処理変数バージョンは、ブロック１０６，１１
４および１２２で識別されたように、それを生成した動
作によってのみ修正することができる。こうした修正
は、生成時間と同一の仮想時間にのみ行うことができ
る。変数のバージョンがそのように修正された場合は必
ず、その変数のリーダリストの全動作は、それらが変数
を読み出すための等しいかそれ以後の時間を持ってお
り、新しく修正された変数を読み出すことが可能となら
なければならないので、ロールバックされる。

【００４４】図６に関して説明したロールバックは、図
４に関して概説した試験によって生じるロールバックに
付加されるものである。上述のような生成時間および変
数バージョンの保持は、共用変数が使用される場合に１
処理内の並行動作の同期化を保証する。この並行処理バ
ージョンの保持はまた、図５の例で説明した処理の現在
の仮想時間より以前の要求受信時間を有するメッセージ
を処理する際に、変数の読出し要求を満たすために、処
理が以前のバージョンを使用できるようにさせる。仮想
時間が前述のように変数バージョンと組み合わされ、処
理間通信だけでなく、並行動作間で変数を共用する処理
内通信に適用された場合、システム内で完全な状態の一
致性が維持される。

【００４５】上述の技法は並行目的向き計算にも適用で
きる。こうした計算では、各目的は論理的処理に、目的
の属性は処理変数に、そして、目的の方法は処理動作に
対応する。そのようなシステムでは、仮想時間、目的属
性バージョンおよび目的方法予備条件が並行目的向き計
算を同期させるために使用される。これは、上述の仮想
時間、処理変数バージョンおよび、従来の並行処理のた
めのガードの使用と直接的に類似であり、同様に解釈で
きる。

【００４６】並行処理および１処理内の並行動作を同期
させるための上述のシステムおよび方法は、並行処理を
包含する通常のシステムの効率を向上させる。発生しな
ければならない処理のロールバック数は、処理の現在の
仮想時間より小さい要求受信時間を有するメッセージの
受信ごとに処理をロールバックさせる必要が必ずしもな
いため、低減される。さらに、ガードが満たされていな
いために動作が遅延される場合、後の要求されるロール
バックは、その処理の状態についてそれ以上の変更が行
われず、メッセージもまったく生成されないので、著し
く容易になる。メッセージは並行処理の間を同期させて
も非同期でも渡すことができる。同期メッセージは２の
処理が仮想時間でその活動を同期するようにさせる。ア
プリケーションプログラマは、それらの動作がプログラ
マにとっては知らなくてもよい形でオペレーティングシ
ステムによって取り扱われることができるので、仮想処
理時間および変数バージョン検査の機能に配慮する必要
がない。上述の技法によって正しい同期化が保証される
ので、アプリケーションプログラマは、他に先行して実
行される必要があるすべての動作がその通りに実行され
ることを想定できる。

【００４７】本発明を好ましい実施例によって詳細に説
明したが、本発明の精神および範囲を逸脱することなく
形式および細部の各種変更が可能であることは当業者に
よって理解されるであろう。

【図面の簡単な説明】

【図１】並行処理間で渡されるメッセージを図示するタ
イミング図。

【図２】並行処理間で渡されるメッセージに含まれる情
報を示すデータ構造の説明図。

【図３】１処理への１メッセージの着信を示す高水準ブ
ロック図。

【図４】処理間メッセージの受信時に処理により実行さ
れる状態一致性検査の好ましい集合を示すフローチャー
ト。

【図５】図４の方法の１例を示すタイミングチャート。

【図６】１処理内の並行動作への好ましい方法の適用に
おいて作成されるデータ構造の集合。

【符号の説明】

５２ 受信側処理が待ち行列から次のメッセージを選択
する ５４ メッセージの受信時間Ｔ（Ｍ）とその処理の現在
の局所仮想時間Ｔ（Ｐ）とを比較する ５６ 局所仮想時間をメッセージの受信時間に等しく設
定する ５８ メッセージ内の参照変数Ｖ（Ｍ）と受信側処理内
の現在の処理変数バージョンＶ（Ｐ）とを比較検査する ６０ ガード述語が満たされているかどうかを判断する
ために検査する ６２ 受信メッセージを処理するのに必要な動作を実行
する ６４ 例外が発生する ６６ ガード述語が満たされているかどうかを判断する
ために検査する ６８ 処理の局所仮想時間をメッセージの受信時間Ｔ
（Ｍ）より前の値にロールバックする

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ダニエル、ティー、チャン アメリカ合衆国カリフォルニア州、サン、 ノゼ、オリーブ、ブランチ、レーン、1126

Claims (22)

【特許請求の範囲】
1. 【請求項１】２処理間でメッセージを通信するための方
   法であって、 第１の処理から第２の処理へメッセージを転送するステ
   ップと、 そのメッセージのメッセージ時間を第２の処理の局所時
   間と比較するステップと、 そのメッセージ時間が第２の処理の局所時間よりも小さ
   い場合はメッセージの内容が第２の処理の現在の状態と
   不一致であるどうかを判断するステップと、 メッセージの内容が不一致である場合は第２の処理をメ
   ッセージの内容と一致する状態までロールバックさせる
   ステップと、 メッセージの内容が一致している場合はそのメッセージ
   を処理するステップとを含む方法。
2. 【請求項２】請求項１記載の方法であって、判断するス
   テップが、 第２の処理の処理変数バージョンを、メッセージを処理
   するために要求される変数バージョンと比較するステッ
   プと、 そのメッセージを処理するために要求される変数の変数
   バージョンが第２の処理の同一変数の現在のバージョン
   と異なる場合、そのメッセージの内容を第２の処理の現
   在の状態と不一致であると定義するステップとを含む方
   法。
3. 【請求項３】請求項２記載の方法であって、判断するス
   テップはさらに、 そのメッセージを処理するために要求される変数バージ
   ョンが第２の処理の現在の処理変数バージョンと異なる
   場合、メッセージを処理するために要求される処理動作
   のためのガード述語の値を判定するステップと、 ガード述語が満たされない場合、そのメッセージの内容
   を第２の処理の現在の状態と不一致であると定義するス
   テップとを含む方法。
4. 【請求項４】請求項１記載の方法であって、さらに、 そのメッセージ時間が第２の処理の処理時間よりも大き
   い場合、または、メッセージの内容が第２の処理の現在
   の状態と一致する場合、そのメッセージを処理するため
   に必要な動作に関するガード述語の値を検査するステッ
   プを含む方法。
5. 【請求項５】請求項４記載の方法であって、さらに、 ガード述語の全部が必ずしも満たされない場合、当該ガ
   ード述語が満たされるまで不満足なガードを有するあら
   ゆる動作の実行を遅延させるステップを含む方法。
6. 【請求項６】請求項１記載の方法であって、さらに、 そのメッセージ時間が第２の処理の処理時間よりも大き
   い場合、メッセージが処理される際に第２の処理の処理
   時間をメッセージの値に等しく設定するステップを含む
   方法。
7. 【請求項７】請求項１記載の方法であって、メッセージ
   を処理するステップが、 第２の処理の１以上の処理ステップを実行するステップ
   と、 結果のメッセージを第１の処理に戻すステップとを含む
   方法。
8. 【請求項８】請求項７記載の方法であって、結果メッセ
   ージが本来のメッセージのメッセージ時間の値に等しい
   メッセージ時間を有している方法。
9. 【請求項９】請求項１記載の方法であって、メッセージ
   時間が、第２の処理が当該メッセージを第２の処理のい
   ずれかの仮想時間に処理できることを指示する既定の値
   を有する方法。
10. 【請求項１０】請求項１記載の方法であって、第１の処
    理および第２の処理が目的向きシステムにおける目的を
    含む方法。
11. 【請求項１１】請求項１記載の方法であって、メッセー
    ジ時間は意図された受信時間であり、かつ、メッセージ
    はメッセージが送信された時間に第１の処理の局所仮想
    時間を指示する値も含んでいる方法。
12. 【請求項１２】請求項１１記載の方法であって、意図さ
    れた受信時間および送信の仮想時間が同一の値を有する
    方法。
13. 【請求項１３】１処理内の並行動作の一致性を保証する
    ための方法であって、 処理変数の新バージョンが生成される際に、処理仮想時
    間および生成動作の識別性を、生成時間が当該変数のす
    べての現行バージョンの生成時間よりも大きくなければ
    ならないような変数に関連づけるステップと、 処理動作が変数を読み出す際に、その動作が実行される
    処理仮想時間に等しいかまたはそれより小さい仮想時間
    を有する変数の最新バージョンをその動作に読み出さ
    せ、かつ、動作の識別子および実行される仮想時間をそ
    の変数バージョンに関連するリストに加えるステップ
    と、 変数のバージョンがいずれかの既存のバージョンよりも
    小さい仮想時間を持って生成された場合、当該の既存の
    バージョンを生成または読み出したすべての動作をロー
    ルバックさせるステップとを含み、さらに、 変数の特定のバージョンを生成した動作だけがそのバー
    ジョンを修正することができ、当該の修正はそのバージ
    ョンが生成された同一の処理仮想時間にのみ行うことが
    でき、その変数バージョンに関するリーダリストで識別
    されるいずれの動作も当該変数バージョンが修正される
    際にロールバックされるものである方法。
14. 【請求項１４】並行処理を実行する１コンピュータシス
    テムにおける処理間通信を管理するための方法であっ
    て、 各処理の局所仮想時間を維持するステップと、 メッセージが２処理間で渡される際にそのメッセージ内
    に当該メッセージの要求受信時間を含ませるステップ
    と、 受信メッセージが処理されるために処理によって選択さ
    れる際にメッセージの状態がその処理の現在の状態と一
    致するかを判断するステップと、 メッセージおよび処理の状態が一致しない場合に処理を
    一致した状態までロールバックさせるステップとを含む
    方法。
15. 【請求項１５】請求項１４記載の方法であって、処理の
    状態が、その処理の仮想時間および、処理変数バージョ
    ンを含むように定義される方法。
16. 【請求項１６】請求項１５記載の方法であって、メッセ
    ージの状態は、そのメッセージの仮想受信時間が処理の
    現在の仮想時間よりも大きい、または、メッセージを処
    理するために必要な処理変数のバージョンがその処理内
    のそれらの変数の現在のバージョンに等しい場合に、処
    理の状態に一致しているものである方法。
17. 【請求項１７】請求項１６記載の方法であって、処理の
    状態はさらに、処理の状態がメッセージの状態と一致し
    ていなければ満足化を検査される、処理ガード述語によ
    って定義されるものである方法。
18. 【請求項１８】請求項１７記載の方法であって、ガード
    述語は、処理の状態がメッセージの状態と一致している
    場合でも満足化を検査されるものである方法。
19. 【請求項１９】請求項１４記載の方法であって、各メッ
    セージはまたそのメッセージが送信される際に送信側処
    理の仮想時間を含み、かつ、各メッセージの仮想送信時
    間はそのメッセージの要求受信時間よりも小さいかまた
    は等しいものである方法。
20. 【請求項２０】請求項１４記載の方法であって、処理に
    送信されたメッセージは、各メッセージで定義された要
    求受信時間の優先順に待ち行列に入れられ、その優先順
    に処理によって処理されるために選択されるものである
    方法。
21. 【請求項２１】請求項２０記載の方法であって、すべて
    の処理のすべての仮想時間、すべての処理待ち行列に残
    っているすべての未処理メッセージの仮想送信時間およ
    び、処理間を移行中のすべてのメッセージの仮想送信時
    間のうちの最小のものとして、大域的仮想時間が定義さ
    れるものである方法。
22. 【請求項２２】請求項２１記載の方法であって、大域的
    仮想時間よりも小さい仮想時間を有するすべてのメッセ
    ージおよび中間的な退避された処理状態が、システムお
    よび再利用される各自の記憶空間によって放棄すること
    ができるものである方法。