JPH08202665A - 疎結合計算機における計算機間結合装置 - Google Patents

Abstract

(57)【要約】 【目的】ネットワーク通信方式において、信頼性を保証
する一斉同報通信を高速に実現する計算機間結合装置を
安価に実現する。 【構成】疎結合計算機システムにおいて、計算機間結合
装置内に、ネットワーク上の全ての計算機から参照可能
な再送要求ロックフラグ１１３及びカウンタ１１２を持
たせ、計算機からの参照の都度カウンタ１１２の内容を
１だけ進める。また、一斉同報の履歴情報を全計算機内
のロック情報記憶手段１０８に記憶させる。 【効果】本発明によれば、少ないネットワーク資源で一
斉同報通信の信頼性を保証出来、相互排除に必要なネッ
トワークパケットを少なくする事が出来る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】疎結合計算機システムにおけるネ
ットワークの構成法及びその制御方法に関する。

【０００２】

【従来の技術】従来、疎結合計算機システムにおいて、
計算機間でメッセージを互いに交換しあいながら相互排
除を実現する方式があった。例えば「分散アルゴリズ
ム、亀田恒彦・山下雅史著、近代科学社、１９９４」の
論文中で様々なアルゴリズムが紹介されている。これら
の分散ロック方式は、いずれも一対一のメッセージ通信
を用いて実現する方式である。これらの方式では、ロッ
クをとる可能性のある計算機に対してメッセージを送
り、全てのメッセージが返って来るのを待つ必要があ
る。例えば、Ricart-Agrawal のアルゴリズムでは、ロ
ックを要求する計算機の個数をＮとすると１回のロッ
ク、アンロックを行うのに ２（Ｎ−１）個のメッセー
ジが必要になり、その内の Ｎ−１個のメッセージはロ
ックを要求した計算機に集中的に送信される。一つのノ
ードでは、処理は逐次に行われるので、ロック要求が完
了するにはロックを取り合う計算機の個数Ｎに比例して
大きくなるという問題がある。

【０００３】前述の様に分散ロックのアルゴリズムにお
いては、ロックを設定する可能性のある全てのノードに
対してメッセージを送信する。この全てのノードに対し
てメッセージを送る操作を、ハードウェアの支援を用い
た一斉同報機能によって実現する方法がある。例えば、
現在、普及している Ethernet 等のＬＡＮでは、一斉同
報機能が提供されている。しかし、一斉同報したメッセ
ージにおいても、メッセージの到着を確認するために、
一斉同報した計算機に対して、メッセージが到着した事
を保証する必要が生じる。一斉同報を受信した計算機
が、一斉同報を送信した計算機に対して、確認応答のた
めのメッセージを送信する事も考えられるが、この方法
では、前述の様な一対一通信で問題となったのと同様に
処理量が大きくなってしまう。

【０００４】この問題を解決するために、一斉同報した
メッセージが到着し無かった時だけ、メッセージの再送
を要求する方式が提案されている。M.F.Kaashoek 他に
依る論文 "An Efficient Reliable Broadcast", Operat
ing Systems Review, Vol.23, Oct.1989, pp.5-19 で報
告されている。この方式では、一斉同報の順序を管理す
る計算機（シーケンサ）を予め決めておき、一斉同報を
発行する計算機はシーケンサのある計算機に一斉同報を
依頼する。一斉同報を受信した場合、一斉同報に対する
確認応答をせず、受信パケットの欠落が発見された時だ
け再送をシーケンサに対して要求する。

【０００５】

【発明が解決しようとする課題】従来例で示した方法で
は以下に示すような問題がある。

【０００６】第１の問題としては、M.F.Kaashoek 他の
方法では、一度シーケンサに対してメッセージを送出す
るため、往復２つのメッセージが必要となる。また、自
計算機の出した一斉同報はどの順番にあるかは自計算機
にシーケンサとなった計算機から一斉同報が到着した時
だけにしか判らない。このため、一斉同報通信によって
ロックを実現した場合、一斉同報通信をシーケンサに依
頼し、シーケンサからの一斉同報を受信するまでの間は
ロック要求が待たされてしまう。

【０００７】第２の問題としては、シーケンサでは欠落
したパケットの再送を行う必要があるため、一斉同報し
たメッセージの履歴情報を持っている必要がある。履歴
情報を持つ計算機、即ちシーケンサに障害が発生した場
合には、一斉同報のための履歴情報が失われてしまい、
メッセージの欠落に対する保証が困難になる。

【０００８】

【課題を解決するための手段】以上の問題点を解決する
ために、本発明においては計算機間結合装置内に、接続
された全ての計算機から参照可能なフラグを少なくとも
二つ持ち、ネットワークに接続された全ての計算機から
参照可能なカウンタを少なくとも一つ持たせ、このカウ
ンタは参照の度毎にカウンタの内容を１つ増やす事を特
徴とする。このカウンタを持たせる事により、第１の問
題である一斉同報通信の番号付けの際に２つ必要だった
メッセージを一つに削減する事が出来る。第２の問題で
ある一斉同報のための履歴情報を全計算機に持たせるこ
とにより、どの計算機に障害が発生しても他の計算機で
代用出来る様にする。しかしこの場合、一斉同報通信し
た再送要求を全計算機に対して送信すると、全計算機か
ら再送パケットを受信してしまい、メッセージ数が増大
すると言う第３の問題が発生する。このような全計算機
からの再送を避けるために、全計算機から参照可能な２
つのフラグを持たせる事により、再送する計算機を一つ
に限定する。

【０００９】

【作用】本発明によれば、ネットワーク通信方式におい
て、信頼性を保証する一斉同報通信を高速に実現する計
算機間結合装置を安価に実現する事が出来る。

【００１０】

【実施例】図１に本発明における疎結合計算機システム
の実施例の一つを示す。疎結合計算機システムは、複数
の計算機１０１と計算機１０１を接続する計算機結合装
置１１０とから構成される。各計算機１０１は、プロセ
ッサ１０４、補助記憶装置１０５、メインメモリ１０
６、ネットワークインタフェース１０７、ロック情報記
憶手段１０８から構成される。計算機結合装置１１０
は、各計算機１０１を接続するネットワークインタフェ
ース１１１と、ネットワークインタフェース１１１を相
互接続しパケットを交換するためのパケット交換網１１
５、及び、各ネットワークインタフェース１１１を介し
て各計算機１０１のプロセッサ１０４から参照可能なカ
ウンタ１１２、再送要求ロックフラグ１１３を備えてい
る。計算機結合装置１１０は、一つの計算機１０１から
他の全ての計算機に対して、パケットを送信する一斉同
報機能を持っている。この一斉同報機能は、公知の例と
して、例えば「並列計算機構成論、富田真治著、昭晃
堂」１０１ページで紹介されている。カウンタ１１２
は、各計算機からの読み出し命令によって、カウンタの
値を読み出し、要求を出した計算機に送り返した後カウ
ンタの内容を１つ増す機能を持っており、例えば、ＴＴ
Ｌ、ＣＭＯＳ等の論理回路によって構成することができ
る。再送要求ロックフラグ１１３は、TestAndSet 機能
を備えている。TestAndSet 機能は、公知の技術であ
り、例えば「オペレーティングシステムの基礎、Ａ．
Ｎ．ハーバーマン著、土井範久訳、培風館」の７３ペー
ジに紹介されている。この TestAndSet 機能では、前の
ロックフラグ１１３の値を読み出し、もし０であれば、
ロックフラグ１１３の値を１とし、前の値０を読み出
す。もし、ロックフラグ１１３の値が１であれば、この
ままロックフラグの値を１とする。以上の操作を他の操
作に邪魔されずに、一度に出来るようにする事で、ロッ
クフラグを排他的に用いる事が可能となる。再送要求ロ
ックフラグ１１３は、公知の技術でありＴＴＬ、ＣＭＯ
Ｓ等の論理回路によって構成することができる。ロック
情報記憶手段１０８は、図１に示す様に、計算機１０１
のシステムバスに独立に接続されていても良いし、メイ
ンメモリ１０６、或いは、ネットワークインタフェース
１０７に内蔵されていても良い。

【００１１】本発明においては、ロック要求、及び、ロ
ック解除をするために、一斉同報通信機能を用いて、各
計算機１０１の間で通信を行い、ロック情報が全計算機
で同じになることを保証する。一般にネットワーク上の
外乱等によって、一斉同報通信のパケットの欠落がある
ため、欠落したパケットを再送する事により補償する必
要がある。このパケットの欠落を補償するために、カウ
ンタ１１２、再送要求ビット１１３を用いる。以下、本
発明において、これらのカウンタ１１２、再送要求ビッ
ト１１３を用いてロック機能が動作する様子をＰＡＤ図
を用いて、処理を説明する。

【００１２】図２に本発明におけるロック情報記憶手段
１０８の一実施例を示す。ロック情報記憶手段１０８は
ロック待ちキュー２０１、実行カウンタ２０６、最新受
信カウンタ２０７を備えている。ロック待ちキュー２０
１は、シーケンス番号２０２、ロックＩＤ２０３、ロッ
ク要求計算機番号２０４、要求プロセス番号２０５を組
とする待ち行列として構成される。実行カウンタ２０６
は、ロックを実行した最新の計算機番号を示し、最新受
信カウンタ２０７は、ロック要求を実行した最新の計算
機番号を示す。ロック待ちキュー２０１には、全ての計
算機１０１からのロック要求が含まれている。他の計算
機からのロック要求は、一斉同報通信によって通知され
る。もし、一斉同報通信のパケットがネットワーク上で
欠落しなければ、ロック要求は全ての計算機で同一にな
る。しかし、前述したように、現実のネットワークにお
いては、パケットの欠落が起こり得る。本発明の目的
は、この欠落したパケットを他の計算機のロック待ちキ
ュー２０１にあるパケット内容２０８によって補償する
技術を提供する事である。

【００１３】図３に本発明で用いる一斉同報通信のパケ
ットの内容の一実施例を示す。一斉同報通信パケット３
０１は、パケットヘッダ３０２、及び、データ３０３か
ら構成される。パケットヘッダ３０２は送付元計算機３
０４、パケットの種類３０５、シーケンス番号３０６か
ら構成される。送付元計算機３０４は、一斉同報通信パ
ケットを送出した計算機の番号を示す。パケットの種類
３０５は、次の３種類あり、ロック要求、ロック解除、
再送要求がある。シーケンス番号は、計算機結合装置１
１０の中のカウンタ１１２の値であり、この番号を用い
る事で一斉同報パケットの欠落を各計算機で検知する。
ロック識別子３０７は、複数種類のロックを要求するた
めに用意する。もし、全計算機で一つのロックを用いる
ならば、このロック識別子は必要ない。

【００１４】以下、上述の３種類のパケットを送信、或
いは、受信する時の各計算機での処理を示す。

【００１５】図４は、本発明における任意の計算機から
ロック要求を送信する際の処理フローを示したＰＡＤ図
である。ロック要求があると、まず、ステップ４０１に
示す様に、計算機結合装置１１０中のカウンタ１１２の
内容を一時的にメインメモリに読み出す。次にステップ
４０２に示すように、カウンタ１１２は読み出されると
同時にカウンタ１１２の値を１つ増やす。メインメモリ
１０６に読み込んだカウンタ１１２の値はステップ４０
３で示すようにパケットヘッダ３０２内のシーケンス番
号３０６に格納する。ここで、ステップ４０４で、も
し、自計算機の実行カウンタ２０６に１を加えた値がパ
ケットヘッダ３０２内のシーケンス番号３０６と等しけ
れば、他にロック要求を発行した計算機が無い事が判る
ので、ステップ４０５でロック要求が成立した事をロッ
ク要求したユーザプロセスに通知する。ステップ４０６
では、現在、自計算機でロック要求を出し、まだ、解除
していない事を示すため、自計算機のロック待ちキュー
２０１にパケット管理情報２０９を挿入する。このロッ
ク待ちキュー２０１内のシーケンス番号２０２、ロック
ＩＤ２０３、ロック要求計算機番号２０４は、それぞ
れ、一斉同報パケット３０１のシーケンス番号３０５、
ロック識別子３０７、送付元計算機３０４に対応する。
要求プロセス番号２０５は、複数の計算機から要求を受
ける場合に、どのプロセスから要求があったかを記憶す
るために用いられ、例えば、ＵＮＩＸオペレーティング
システムにおけるプロセス番号で代用する事が出来る。
ＵＮＩＸオペレーティングシステムのプロセス番号につ
いては、「ＵＮＩＸ４．３ＢＳＤの設計と実装、 S.J.L
effler 他著、中村明他訳、丸善株式会社」の２５ペー
ジに詳細が記述されている。ロック待ちキュー２０１に
挿入する順番は、パケット内のシーケンス番号の昇順と
する。ステップ４０７では、自計算機のロック要求を他
の計算機に通知するため送付元計算機３０４に自計算機
の番号を格納し、然る後に送付元計算機３０４は一斉同
報通信のパケットを送信する。以上の処理によって、送
付元計算機３０４がロック要求を全計算機に通知し、も
し、他に要求が無ければ、他の計算機にロック要求を通
知する前に、ロックが確保出来る。

【００１６】図５は、本発明における一斉同報パケット
受信処理を示すＰＡＤ図である。

【００１７】一斉同報通信をステップ５０１で受信し、
パケットの種類をステップ５０２で検査する。もし、パ
ケットの種類が再送処理であれば、ステップ５０３にお
いて再送処理を行う。この再送処理の詳細については後
述する。もし、再送要求が無ければ、ステップ５０４に
おいて自計算機の最新受信カウンタ２０７に１を加えた
ものがパケット内のシーケンス番号３０６と比較し、も
し、小さければ、パケットの欠落があるものとして、ス
テップ５０５において、再送要求処理を行う。この再送
要求処理の詳細については後述する。ステップ５０６に
おいては、自計算機の最新受信カウンタ２０７の内容を
パケット内のシーケンス番号３０６とし、このパケット
まではパケットの欠落無しに受信した事を記憶する。ス
テップ５０７では、再び、パケットの種類を検査し、ロ
ック要求であれば、ロック待ちキュー２０１内にロック
要求を格納する。ロック待ちキューの挿入する位置は、
前述した様に、パケット内のシーケンス番号の昇順とす
る。ステップ５０７において、パケットの種類がロック
解除であった場合には、ステップ５０９において、ロッ
ク解除受信処理を行う。ロック解除受信処理の詳細につ
いては後述する。

【００１８】図６は、本発明における再送要求処理を示
すＰＡＤ図である。再送処理においては、まず、ステッ
プ６０１において、自計算機の最新受信カウンタ２０７
に１を加えた値と受信パケット内のシーケンス番号の値
よりも小さいか否かを検査する。もし、小さければ、そ
の間のシーケンス番号を持つ一斉同報通信パケットが欠
落している事になる。以下では、欠落したパケットを他
の計算機から送信してもらう事を要求する処理である。
ステップ６０２では、計算機結合装置内の再送要求ロッ
クフラグ１１１の値を TestAndSet 機能によって検査
し、TestAndSet機能によって得られた値がもし１であれ
ば、他の計算機が再送処理中であるので、そのまま待ち
続ける。もし、TestAndSet の値が０であれば、再送処
理をしている計算機が無い事が判り、ステップ６０３に
進む。ステップ６０３では、一斉同報通信パケットの種
類を再送要求とし、自計算機の最新受信カウンタ２０７
の値に１加えた値をシーケンス番号として、一斉同報通
信を行う。ステップ６０４では他の計算機からパケット
の再送がある迄待つ処理である。自分の計算機で要求し
たロック要求は必ずロック要求処理のステップ４０６で
自計算機のロック要求待ちキュー２０１に格納されてい
る筈なので、仮に、一斉同報通信パケットが全計算機に
到着しなかった場合でも、少なくとも一つの計算機で
は、シーケンス番号に対応するロック要求のパケットを
持っている事が保証できる。ステップ６０４では再送さ
れたパケットを受信する処理である。このステップ６０
４における再送パケット受信処理においては、再送する
計算機との一対一通信によって実現し、パケットの到着
を確認する、確認応答を再送する計算機に送り返す。ま
た、再送要求のための一斉同報通信がどの計算機に対し
ても到着しない場合が考えられるので、そのよ様な状況
を想定して、ステップ６０４の待ち処理の前にタイマを
かけ、もし、設定した時間が経過した場合には、ステッ
プ６０３を再度実行する処理もステップ６０４に含まれ
る。ステップ６０５では、再送されたパケットをロック
待ちキュー２０１の先頭に入れる。ステップ６０６で
は、再送処理を終了するため、再送要求ロックビット１
１３の値を０とする。最後に、ステップ６０７で、自計
算機の最新受信カウンタ２０７に１を加える。もし、カ
ウンタの値がステップ６０１の条件に満たなければ、再
び、ステップ６０２からステップ６０６の処理を繰り返
し、欠落したパケットを他計算機から送信してもらう。
図７は本発明における再送処理を示すＰＡＤ図である。
再送要求を受けた計算機は次の様にして、再送処理を行
う。ステップ７０１では、ロック待ちキュー２０１の中
のシーケンス番号２０２を走査し、再送要求のあったシ
ーケンス番号と等しいシーケンス番号２０２があった場
合に、ステップ７０２以降に進む。もし、無い場合に
は、再送処理を打ち切る。ステップ７０２では、ステッ
プ７０１で発見したシーケンス番号２０２に対応するパ
ケットが自計算機から送信したものであるかどうかを検
査する。対応するパケットが自計算機から送信されたも
のであれば、ステップ７０３において、ステップ７０１
で検査した結果該当したパケットを再送要求計算機に送
信する。前述した様に、ステップ７０１における送信処
理は、確認応答処理を含んだ一対一通信にを用いて実現
する。

【００１９】図６、および、図７で示した処理によっ
て、一斉同報通信を用いたロック要求パケットが全計算
機で保持することが出来る様になるため、どの計算機が
故障してもロック情報を復旧可能となる。

【００２０】図８は、本発明におけるロック解除要求の
受信処理を示したＰＡＤ図である。ステップ８０１で
は、実行パケットカウンタとパケット内のシーケンス番
号を検査する。もし、実行カウンタ２０６の値とパケッ
ト内のシーケンス番号が等しければ、ロック待ちキュー
２０１の先頭にロック情報がある事が判るので、その情
報を削除する。ロック待ち情報を削除する処理は、ステ
ップ８０２、８０３で示すように、ロック待ちキュー２
０１からの先頭を取り除く処理で実現できる。ステップ
８０４で自計算機内のロック待ちキューの先頭が自計算
機からの要求であるかどうかを検査し、もし、そうであ
れば、ステップ８０５において、自計算機のロック要求
したプログラムにロックが獲得できたことを通知する。
なお、ステップ８０１で、もし、実行カウンタ２０６の
値とパケット内のシーケンス番号が等しく無い場合に
は、ロック要求のパケットが欠落しているため、ステッ
プ８０６において、再送要求処理をした後に、ステップ
８０１の処理を繰り返す。

【００２１】

【発明の効果】本発明によれば、複数の計算機をネット
ワークで結合し、各計算機は独立したアドレス空間を持
ち、各計算機内のメモリ上に複数計算機間でデータを共
有するための共有データメモリを持つ疎結合計算機シス
テムにおいて、共有データの一貫性保証のための同期
と、並列プログラムを制御するための同期とのために必
要なネットワークパケットを少なくする事が出来るの
で、ネットワーク資源を有効に活用することが出来る。
また、並列プログラムを制御するための同期と共に共有
データの一貫性保証も行う事が出来るので、並列プログ
ラムを記述するプログラマの負担を軽減する事が出来
る。その結果、特に、通信時間に比して計算時間が長
く、自動的に負荷の分散が困難である様な並列処理の問
題を効率良く処理する事が可能となる。

【図面の簡単な説明】

【図１】本発明の一実施例を示す疎結合計算機システム
のブロック図。

【図２】本発明に於けるロック情報記憶手段のの一実施
例を示す図。

【図３】本発明に於ける一斉同報通信パケットの一実施
例を示す図。

【図４】本発明に於けるロック時一斉同報通信パケット
の送信処理を示すＰＡＤ図。

【図５】本発明に於ける一斉同報通信パケットの受信処
理を示すＰＡＤ図。

【図６】本発明に於ける一斉同報通信パケットの再送要
求処理を示すＰＡＤ図。

【図７】本発明に於ける一斉同報通信パケットの再送処
理を示すＰＡＤ図。

【図８】本発明に於けるロック解除パケット受信時の処
理を示すＰＡＤ図。

【符号の説明】

１００：疎結合計算機システム、 １０１：計算機、 １０３：システムバス、 １０４：プロセッサ、 １０５：補助記憶装置、 １０６：メインメモリ、 １０７：計算機内のネットワークインタフェース、 １０８：ロック情報記憶手段、 １１０：計算機間結合装置、 １１１：計算機結合装置内のネットワークインタフェー
ス、 １１２：カウンタ、 １１３：再送要求ロックフラグ、 １１５：パケット交換網、 ２０１：ロック待ちキュー、 ２０２：シーケンス番号、 ２０３：ロックＩＤ、 ２０４：ロック要求計算機番号、 ２０５：要求プロセス番号、 ２０６：実行カウンタ、 ２０７：最新受信カウンタ、 ３０１：ネットワークパケット、 ３０２：パケットヘッダ、 ３０３：ネットワークパケット内のデータ、 ３０４：一斉同報通信パケットの送付元計算機、 ３０５：一斉同報通信パケットの種類、 ３０６：一斉同報通信パケットのシーケンス番号、 ３０７：一斉同報通信パケットによって実現されるロッ
ク識別子、 ４０１〜４０７：ロック時一斉同報通信の処理、 ５０１〜５０９：一斉同報通信パケットの受信処理、 ６０１〜６０７：一斉同報通信で欠落したパケットを再
送要求する処理、 ７０１〜７０３：一斉同報通信で欠落したパケットを再
送する処理、 ８０１〜８０５：ロック解除受信処理

───────────────────────────────────────────────────── フロントページの続き (72)発明者 吉沢 聡 東京都国分寺市東恋ケ窪１丁目280番地 株式会社日立製作所中央研究所内 (72)発明者 林 剛久 東京都国分寺市東恋ケ窪１丁目280番地 株式会社日立製作所中央研究所内 (72)発明者 北野 昌宏 神奈川県海老名市下今泉810番地 株式会 社日立製作所オフィスシステム事業部内

Claims (4)

【特許請求の範囲】
1. 【請求項１】計算機がネットワークで結合された疎結合
   計算機システムにおいて、各計算機間で発生する通信パ
   ケットを交換する交換ネットワークであって、ネットワ
   ークに接続されたすべての計算機から参照可能なカウン
   タを少なくとも一つ持ち、該カウンタは参照の度にカウ
   ンタの内容を１つ増し、かつ、ネットワークに接続され
   た全ての計算機から参照可能なフラグを少なくとも一つ
   持つ事を特徴とする計算機間結合装置。
2. 【請求項２】請求項１の計算機間結合装置を持つ疎結合
   計算機システムにおいて、該計算機間結合装置に接続さ
   れた任意の一つの計算機から通信パケットを他の全ての
   計算機に対して送出する一斉同報機能を持ち、請求項１
   のカウンタで読み込んだカウンタ値を、該一斉同報の通
   信パケットに含ませる事を特徴とする計算機間結合装
   置。
3. 【請求項３】請求項２の疎結合計算機システムの計算機
   において、受信した一斉同報の通信パケットの履歴を記
   憶する手段と、受信した一斉同報の通信パケットに含ま
   れたカウンタ値を記憶する手段と、受信した一斉同報の
   通信パケットのヘッダ情報に格納されたカウンタ値の記
   憶手段とを比較する手段を持ち、該比較手段によって、
   記憶したカウンタ値とヘッダ情報のカウンタ値の差が１
   でない場合には、一斉同報の通信パケットが到着しなか
   ったと判断する事を特徴とする計算機間結合装置。
4. 【請求項４】請求項３の疎結合計算機システムにおい
   て、カウンタ値を含む一斉同報通信パケットが受信側の
   計算機に到着しなかった場合には、一斉同報通信を用い
   て再送要求を行ない、再送要求を受信した計算機が該カ
   ウンタ値を含む一斉同報通信パケットを送出した計算機
   であった場合に、再送要求を行なった計算機に対して該
   カウンタ値を含む一斉同報通信パケットを再送する事を
   特徴とする計算機間結合装置。