(57)【特許請求の範囲】
【請求項１】
少なくとも１つ以上のプロセッサをそれぞれ有する複数のノードと、該複数のノードにより利用可能な資源を有する少なくとも一つの資源管理ノードがネットワークを介して接続された計算機システムにおいて、該資源の使用は、その時点で該資源のロックに成功している単一のノードによる使用に限る排他的制御方法であって、
該複数のノードにそれぞれ備えられたロック制御回路のレジスタに、該資源の排他的使用状態を示す使用状態情報をそれぞれ記憶し、
各ノードは、該資源に対する排他的使用要求を発行すべきときに、該資源が排他的に使用された状態にあるか否かをそのノードのロック制御回路のレジスタに記憶された該資源の使用状態情報に基づいて判別し、該資源が排他的に使用された状態にあると判別された場合、そのノードからの該排他的使用要求の発行を中止し、該資源が排他的に使用された状態にないと判別された場合、そのノードから上記計算機システム内に唯一つ設けられた放送メッセージ中継回路に該排他的使用要求を転送し、
該放送メッセージ中継回路は、転送された複数の排他的使用要求から一つの排他的使用要求を順次選択し、選択された排他的使用要求を上記複数ノードの全てに放送し、
各ノードは、該一つの排他的使用要求が選択されて放送されたことに基づいて、その資源に関する、各ノードのロック制御回路のレジスタに記憶された該使用状態情報を該資源が排他的に使用されることを表わす使用状態情報に更新する排他制御方法。
【請求項２】
上記選択された排他的使用要求を発行したノードより上記資源に対するアクセス要求を発行し、
上記アクセス要求による上記資源のアクセスの終了後に、上記選択された排他的使用要求を発行したノードから上記資源を保持する資源管理ノードに対する上記資源の排他的使用の解除要求を上記放送メッセージ中継回路に発信し、
該排他的使用の解除要求を上記放送メッセージ中継調回路から上記複数のノードの全てに転送し、
各ノードにおいて、放送された上記排他的使用の解除要求に応答して、上記使用状態情報を、上記資源が排他的に使用されていない状態を表わす使用状態情報に変更するステップをさらに有する請求項１記載の排他制御方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、複数のプロセッサを有する計算機システムにおいて、これらのプロセッサにより共有されている資源に対する排他制御方法に関し、とくに、それぞれプロセッサを有する複数のノードがネットワークを介して結合されている並列計算機において、いずれかのノードに属する共有資源に対する排他制御方法に関する。
【０００２】
【従来の技術】
大規模なデータベースを高速に検索するためのデータベースシステムとしては、複数のプロセッサから構成される並列計算機で実行されるかまたは複数の計算機からなるクライアント・サーバ型の分散処理システムで実行される分散データベースシステムが知られている。本明細書では、並列計算機を構成する複数のプロセッサとクライアント・サーバ型の分散処理システムを構成する複数の計算機とを区別することなく言及するために、分散処理システムの分散処理を実行する計算機要素を「ノード」と呼ぶ。
【０００３】
分散データベースシステムでは、データベースは、複数のディスク装置に分散して保持され、ユーザからの一つの検索要求を複数のノードが協調動作して処理する。すなわち、複数のノードが上記検索要求で指定されたデータベースの異なる部分を保持するディスク装置を互いに並行にアクセスして、それぞれのデータベース部分を処理するようになっている。この際、同一のデータベース部分に対して複数ノードからのアクセスが同時に発生する場合がある。この際、これらのアクセスの実行結果を保証するためには、同一のノードからの一連のアクセスが完了する間は、他のノードからのアクセスを禁止するように、異なるノードからのこれらのアクセスを調停する必要がある。
【０００４】
分散データベースシステムの構成方法としては、いくつかの方法が知られている。例えば、参考文献１：「日経エレクトロニクス」６３０号，１９９５．２．２７号，第６７頁〜第７５頁参照。中でも、アクセスの調停における利便性とシステムの構築の簡便さにおいて次の２つが優れている。まず、第１の構成方法は、シェアード・エブリシング方法で、この方法では、主記憶とデータを格納する複数のディスク装置が共有バスに接続され、さらに複数のノードもこの共有バスに接続され、各ノードはこの共有バスを介してこれらのディスク装置のいずれにもアクセスできる。しかし、一般的に共有バス結合のシェアード・エブリシング方法では、共有バスのデータ転送性能がボトルネックとなるため、１つの共有バスに接続できるノード数は大きく制限される。このため、ノード数を増大して、システムの性能をアップすることが難しい。第２の構成方法は、シェアード・ナッシング方法で、主記憶もこれらのディスク装置も複数のノードでは共有されない。すなわち、この方法では、これらの複数のディスク装置を、異なるノード内に分散して配置し、各ディスク装置を、それが属する特定のノードだけが直接にアクセス可能であり、その特定のノード以外のノードが上記ディスク装置をアクセスするときには、その特定のノードにアクセスを依頼する。すなわち、このシステムでは、複数のノードで共有されたディスク装置に格納されたファイルをアクセスする場合、直接アクセスできるノードは、そのディスク装置に物理的に接続された唯一のノード（以下、これを資源管理ノードと呼ぶ）に限定されている。物理的に接続されていない他のノード（以下、これをアクセス要求ノードと呼ぶ）がこのファイルをアクセスする場合には、ネットワークのようなメッセージ交換手段を介して、資源管理ノードにアクセス要求を発行し、その資源管理ノードを介して間接的にそのファイルをアクセスする。したがって、複数のアクセス要求ノードが同時にこのファイルをアクセスする場合には、複数のアクセス要求メッセージが資源管理ノードに送られるが、これらの要求メッセージを資源管理ノードが調停することによりこれらのアクセス要求の実行結果を保証する。
【０００５】
このように、このシェアード・ナッシング方法では、各ノードのディスク装置は物理的には他のノードによりアクセスできないので、そのディスク装置内のファイルも物理的には他のノードにより共有されていないが、上に述べたようにそのファイルの資源管理ノードを介して他のノードからアクセスできる。したがって、以下では、このシェアード・ナッシング方法でも、各ノードのファイルその他の資源の内、他のノードからのアクセスを許す資源を共有資源と呼ぶ。とくに他のノードからのアクセスを許すファイルを共有ファイルと呼ぶ。
【０００６】
このシェアード・ナッシング方法では、ノード数を増大してシステムの性能を増大することは比較的容易である。しかも、資源管理ノードのアクセス要求メッセージの処理および各ノード間でのメッセージ交換手段の性能が高ければ、共有資源へのアクセスの性能が高くなる。
【０００７】
【発明が解決しようとする課題】
しかしながら、従来のシェアード・ナッシング方法を分散データベースシステムに適用した場合では、次ぎの問題が生じる。すなわち、１つの資源、たとえば特定のディスク装置に格納されたファイルに対してアクセスが集中すると、アクセスが集中した共有ファイルを管理している資源管理ノードが、他のアクセス要求ノードからのアクセス要求処理に忙殺される。分散データベースシステムでは、この資源管理ノードは、他のノードと同様に、このデータベースの処理を分担しているので、本来はこのノードも検索処理等を行うように構成される。ところが、上記アクセス要求がその資源管理ノードに集中すると、この本来業務を実行する時間が著しく減少し、そのノードの処理が遅延し、システム全体の性能を低下させる。したがって、この資源管理ノードが、システム全体のボトルネックとなり得る。
【０００８】
複数のノードがいずれかの資源管理ノード内のディスク装置に格納されている共有ファイルを同時にアクセスする場合に、これらのアクセスノードからの複数のアクセス要求が同一のファイルに対して競合する。このアクセス競合を解決する手段として共有ファイルの排他制御が必要となる。従来のロック要求の処理方法をこのシェアード・ナッシング方法を分散データベースシステムに適用すると、アクセスノードは、アクセス要求を資源管理ノードに発行する前に、ロック要求をそこに発行する。上述のように、多数のアクセス要求が特定の資源管理ノードに集中する場合には、その前に、この資源管理ノードに多数のロック要求が集中することになる。このために、資源管理ノードによる本来業務の実行が遅延されるという上記問題がより深刻になる。以下、この問題をさらに説明する。
【０００９】
すなわち、従来のロック要求の処理方法をこのシステムに適用すると、ロックアクセス元ノードは、共有ファイルをアクセスする前に、資源管理ノードに対して、同時に共有ファイルのロック要求を資源管理ノードに転送し、割り込む。資源管理ノードは、それまで実行していた検索処理を中断し、これらのロック要求を解釈し、これらのロック要求が共有ファイルに対するロック要求であることを知ると、これらのロック要求のうちどの要求を許可するかの調停を行う。通常、リモート・プロシジャー・コールを用いたクライアント・サーバ型の処理方法では並行処理サーバ方法（コンカレント・サーバ方法）が用いられる。これは、クライアントからのサービス要求があった場合にサーバはこのサービスを提供する子プロセスを起動して次のサービス要求に備える方法である。したがって、ほぼ同時に２つのサービス要求がサーバに到着した場合、サーバは２つの子プロセスを起動し、これらの子プロセスが並行にそれぞれのクライアントにサービスを提供する。この方法を、上記シェアード・ナッシング方法の分散データベースシステムに適用すると、同一の共有ファイルへのロック要求を２つの子プロセスが発行する可能性があり、これらのロック要求を処理するため、これらの子プロセス間で調停をとる必要が生じる。これらの２つの子プロセスは同一のノードで実行されるため、良く用いられるセマフォ操作による排他制御を用いることで調停を行うことができる。たとえば、テスト・アンド・セット命令などである。
【００１０】
ロック要求の調停が済むと、それぞれの子プロセスはいずれかの調停でロック権を与えられたいずれかのアクセス要求ノードには「ロック許可」を返答し、他のアクセス要求ノードには「ロック拒絶」を返答する。そして、子プロセスの処理終了後、割り込まれていた検索処理を再開する。
【００１１】
ロック許可を受け取ったアクセス要求ノードは、共有ファイルのアクセスを行い、検索処理を続ける。そして、共有ファイルのアクセスが全て終了すると、共有ファイルのロック解除要求を資源管理ノードに転送し、資源管理ノードに割り込む。このノードは、実行中の検索処理を再び中断し、ロック解除要求を解釈し、共有ファイルのロック解除を行う。ロック解除が終了したら、割り込まれていた検索処理を再開する。一方、ロック拒絶を受け取ったアクセス要求ノードはロック許可を得たアクセス要求ノードによる共有ファイルのアクセスが終了するまで待ち、その待ち時間が経過した後、共有ファイルのロック要求を再度発行する。一般的に、この待時間は乱数もしくは一定時間であることが多い。
【００１２】
このように従来のシェアード・ナッシング方法の並列データベース処理システムに従来のロック要求の処理方法を適用すると、資源管理ノードは、ロック要求の解釈、そのロック要求の実行、ロック解除要求の解釈、その要求の実行を行う必要があるので、これらの処理の実行の間、検索処理の進行が妨害される。この妨害は、いずれかのノードがアクセス要求ロック要求を発行する度に発生する。とくに、ロック要求の処理の主要な部分は、いずれかの資源の排他的な使用を要求する複数のロック要求の一つにロック権を与えるように、複数のロック要求を調停することと、その調停でいずれかのロック要求が選ばれた後は、その資源をロックし、その選ばれたロック要求を発行したノード以外のノードからその資源にアクセス要求があった場合に、その資源へのアクセスを禁止することである。
【００１３】
本発明の目的は、同一の資源に対して複数のノードから発行される複数の排他使用要求の一つを選択する調停を高速化する排他制御方法および並列計算機を提供することである。
【００１４】
本発明のより具体的な目的は、一つのノードの管理下にある資源に対する複数のノードからの排他的使用要求の調停を、その一つのノードにあるプロセッサ以外の回路により実行させ、それにより、この調停時間を短縮し、そのプロセッサの負荷を軽減する排他制御方法および並列計算機を提供することである。
【００１５】
【課題を解決するための手段】
このために本発明の排他制御方法では、複数のノードにより使用可能な一つの資源の排他的使用状態を示す使用状態情報を各ノード内に記憶し、
いずれかのノードが該資源に対する排他的使用要求を発行すべきときに、該資源が排他的に使用された状態にあるか否かをそのノード内に記憶された該資源の使用状態情報に基づいて判別し、
該資源が排他的に使用された状態にあると判別された場合、そのノードからの該排他的使用要求の発行を中止し、
該資源が排他的に使用された状態にないと判別された場合、そのノードから該排他的使用要求を発行し、
いずれかの複数のノードから発行された複数の排他的使用要求を、該複数のノードによりアクセス可能な排他的使用の調停用の回路にネットワークを介して転送し、
該転送された複数の排他的使用要求の内、該資源を排他的に使用させる一つの排他的使用要求を該調停用の回路により選択し、
該一つの排他的使用要求が該調停用の回路により選択されたことに基づいて、その資源に関する、各ノード内に記憶されたに該使用状態情報を該資源が排他的に使用されていることを表わす使用状態情報に更新する。
【００１６】
本発明によれば、上記資源へのアクセスを要求するノードにおいて、その資源が排他的使用状態にないことを確認してから、この資源に対するアクセス要求を送出するので、無駄な排他的使用要求を出さない、それにより無駄な排他的使用要求に対する調停処理の実行を減らせる。
【００１７】
本発明による計算機システムは、上記方法を実行するために、
上記資源に対して該複数のノードから発行される複数の排他的使用要求の一つを選択する、上記ネットワークに含まれた、排他的使用要求の調停用の回路とを有し、
各ノードは、
該一つの資源の排他的使用状態を示す使用状態情報を記憶する手段と、
そのノードが該一つの資源に対する排他的使用要求を送出すべきときに、該記憶された使用状態情報に基づいて、上記資源が排他的使用済みか否かを判定する手段と、
該一つの資源が排他的使用状態でないときに、排他的使用要求を上記調停用の回路に上記ネットワークを介して排他的使用要求を含むメッセージを上記調停用の回路に宛てて転送する手段とを有し、
各ノードは、該調停用の回路により選択された一つの排他的使用要求に依存して、そのノード内に記憶されたに該使用状態情報を該資源が排他的に使用されている状態を表わす情報に更新する手段をさらに有する。
【００１８】
本発明のより具体的な態様では、上記調停用の回路は、ネットワーク内のこれらの複数のノードに共通に設けられた調停用の回路からなり、ここにおいていずれかのノードから発行された排他的使用要求に排他的使用を許可するか否かを判定するようになっている。
【００１９】
本発明のより具体的な他の態様では、上記調停用の回路は、各ノードに分散した配置された複数の調停用の回路からなり、各ノードで、いずれかのノードから発行された排他的使用要求に排他的使用を許可するか否かを判定するようになっている。
【００２０】
本発明のより具体的なさらに他の態様では、上記調停用の回路は、上記資源が属するノードに配置された調停用の回路からなり、そのノード内の記憶された上記資源の使用状態情報に基づいて、いずれかのノードから発行された排他的使用要求に排他的使用を許可するか否かを判定し、その結果を各ノードに通知するようになっている。
【００２１】
【実施例】
以下、本発明に係る計算機システムを図面に示したいくつかの実施例を参照してさらに詳細に説明する。なお、以下においては、同じ参照番号は同じものもしくは類似のものを表わすものとする。
【００２２】
＜実施例１＞
図１に本実施例による並列計算機を示す。この並列計算機では、複数のノード２はネットワーク１により結合され、各ノード２は、少なくとも一つのプロセッサ２４と、ディスク装置２５を含み、このディスク装置２５内に、これらのノードの共有資源として利用される一つ又は複数の共有ファイルが保持されている。各共有ファイルは、それを保持するノード（資源管理ノード）のみからアクセス可能であり、このファイルをアクセスしたい他のノード（アクセス要求ノード）は、この資源管理ノードにファイル読み出し要求あるいはファイル書き込み要求を発行し、その要求の実行をこの資源管理元ノードに依頼する。共有資源を使用するに当っては、その資源をいずれかのノードが使用中に他のノードが使用しないように、使用前にその資源の排他的な使用権を取得し、使用終了後にその使用権を放棄する必要がある。従来の、シェアドナッシングのシステムで、いずれかのアクセス要求ノードが、いずれかの資源管理ノードに管理された資源の排他的な使用を要求するとき、ロック要求をこの資源管理ノードに宛てて発信し、その資源管理ノードでは、複数のロック要求を調停してその一つを選択し、選択をしたときに、その資源をロックしていた。従って、ロック要求の処理は、複数の排他的要求の調停と、資源のロックとを伴う。後に説明するように、本実施例では、資源の排他的な使用権をどのアクセス要求ノードに与えられるかに関する調停が行われる。しかし、資源の使用に当っては、資源のロックを行わない。このように本実施例では、共有資源の排他的な使用の仕方が異なるが、本実施例でも、ロック要求あるいはロック状態等、従来と同じ用語「ロック」を使用するが、本実施例では、ロックは排他的使用を意味し、例えば、ロック状態とは、排他的使用状態を意味する。この用語「ロック」の使用方法は他の実施例および変形例においても同様である。
【００２３】
本実施例では、各ノードの共有資源のロック状態の管理をそのノードを含めた全てのノードで行うところに特徴がある。このために、各ノード２には、本実施例で特徴的な、ロック状態レジスタ群５２とロック制御回路５００が設けられている。ロック状態レジスタ群５２は、この並列計算機内の全ての共有資源のロック状態を管理するためのレジスタで、ロックする資源の単位に対応して設けられている。本実施例では、各ノードをロックの単位とする。すなわち、各ノード内に共有資源が複数ある場合でも、これらの共有資源をまとめてロックする。このため、本実施例では、このロック状態レジスタ群５０は、いずれかのノードにそれぞれ対応するレジスタからなり、各ロック状態レジスタは、そのレジスタに対応するノードがロックされた状態にないときには、そのことを示す情報を保持するとともに、その対応するノードがロックされているときには、そのノードをロックしているノードの識別情報を保持するようになっている。各ノードで実行されるプログラムが、他のいずれかのノードをロックしたいときには、自己のノード内のロック状態レジスタ群５０を見て、ロック先のノードがすでにロックされているか否かを判別し、もし、そのロック先ノードがロック中であるならば、ロック要求を送出しないようになっている。これにより、従来技術で発生した、ロック中のファイルに対してロック要求を出すという無駄なロック要求がなくなり、それに伴って、資源管理ノードが無駄なロック要求を処理するという無駄をなくしている。
【００２４】
複数のノードが同じ共有資源に対してロックを要求したときに、それらのロック要求を調停し、いずれか一つのロック要求を選択する必要がある。本実施例では、この調停は、各ノードのロック制御回路５００と放送中継回路１２により行われる。すなわち、いずれかのノード２がいずれかの共有ファイルを使用したい場合、ロック要求とそのファイルを保持している資源管理ノードの識別情報と、そのノード（アクセス要求ノード）の識別情報を放送すべき情報として含む放送要求メッセージを、この放送メッセージ中継回路１２に宛ててネットワーク２を介して転送する。放送メッセージ中継回路１２は、この放送要求メッセージを受け取ると、この放送すべき情報を含む放送メッセージを生成し、ネットワーク２を介して全てのノードに放送する回路である。もし、異なるノード２から、複数の放送要求メッセージがこの回路１２に転送された場合、この放送メッセージ中継回路１２は、これらのメッセージに順次応答する。したがって、この放送メッセージ中継回路１２は、複数の放送要求メッセージを逐次化する回路と言える。この放送メッセージ中継回路１２から放送されたロック要求を含む放送メッセージは、各ノード２にネットワーク２を介して転送され、各ノード２は、この放送メッセージ内のロック要求に対して、ロックを許すか否かを判定する。基本的には、同じ資源に対するロックを要求する複数のロック要求があるときには、最初に到着したロック要求にその資源のロックを許可する。この判定により新たにあるロック要求にロックが許可されたときには、そのノードのロック制御回路５００がロック状態レジスタ５２を書き換える。放送中継回路１２は、異なるノードから発行された複数のロック要求を同じ順で各ノードに供給する働きをする。したがって、各ノードのロック制御回路によるロック判定結果は、ノードによらず同じ結果となる。各ノードのプロセッサ２４は、こうして、新たにロックされた資源管理ノードおよびその資源ノードロックに成功したノードを知ることができる。したがって、ロック要求を含む放送要求メッセージを発信したノード２は、自分がロックに成功したか否かを知ることができ、もし、自分が資源管理ノードのロックに成功したときには、資源管理ノードに宛ててファイルアクセス要求を含むメッセージを発信する。
【００２５】
従来技術は、アクセス要求ノードは、資源管理ノードにロック要求を発信し、そのノードでは実行中のプログラムを中断して、ロック要求をプログラムにより処理していたが、本実施例では、このように、放送メッセージ中継回路１２という回路でロック要求を逐次化し調停した後、各ノードで、ロック状態を管理するので、資源管理ノードでのロック要求の処理は不要である。したがって、資源管理ノードでの処理を減らすことができる。
【００２６】
以下、本実施例の回路とその動作の詳細を説明する。
（ノード２）
図１に示すように、各ノード２は、検索処理３１などのプログラムを実行するプロセッサ２４と、ローカルメモリ２３と、ノードが分担するデータベースを格納するディスク装置２５と、本実施例で特徴的な高速なロック処理を行うための送信制御回路２１と、受信制御回路２２とから構成される。この並列計算機は、いわゆる分散メモリ型並列計算機で、ローカルメモリ２３は、他のノードによっては共有されていないで、そのローカルメモリが属するノードのみによりアクセス可能で、そのノードで実行するプログラムやそのプログラムが使用あるいは生成するデータを格納する。このノード内の各回路は、システムバス２６に接続され、メモリ・マップド・ＩＯ方法によりプロセッサ２４からロード命令やストア命令などのメモリ・アクセス命令により、ローカルメモリ２３と区別することなくアクセスすることができる。
【００２７】
送信制御回路２１は、メッセージ生成回路４１と送信パラメータ格納レジスタ４２と送信状態レジスタＳＴ４３とから構成される。受信制御回路２２は入力バッファ５１と、ロック状態レジスタ群５２と、ロック制御回路５００とからなる。ロック制御回路５００は、２つの入力が同一か否かを判定する一致回路５３と、２つの入力の大小を比較する大小判定回路５４と、２つの入力の加算を行なう加算回路５６と、セレクタ５５、５７と、ゲート回路５８と、アンド回路５９からなる。
【００２８】
（ネットワーク１）
ネットワーク１は、特願平６−５３４０５号明細書に記載のものと同じで、図２に示すように、基本的には、複数のクロスバスイッチ７、８と複数の中継スイッチ３から構成される、いわゆるハイパクロスバスイッチと言われるネットワークからなる。これらのクロスバスイッチは、複数のＸ方向クロスバスイッチ７または８と、複数のＹ方向のクロスバスイッチ５あるいは６からなる。各ノード２は、対応する一つの中継スイッチ３を介して、一つのＸ方向クロスバスイッチ７または８およびＹ方向クロスバスイッチ５または６に接続されている。各中継スイッチ３は、それに接続された、ノード、Ｘ方向クロスバスイッチ、Ｙ方向クロスバスイッチの間でメッセージを中継する。
【００２９】
各ノード２は、２次元空間の格子点のＸ座標Ｙ座標の組みＸＹが与えられ、Ｘ方向クロスバスイッチは、これらのノード２のうちＹ座標が特定の値に等しくＸ座標が異なる一群のノードを結合し、Ｙ方向クロスバスイッチは、これらのノード２のうちＸ座標が特定の値に等しくＹ座標が異なる一群のノードを結合する。また、この放送メッセージ中継回路１２が接続されたＸ方向クロスバスイッチ７は、他のＸ方向クロスバスイッチ８より入出力ポートを一つ多く有し、放送メッセージ中継回路１２が接続されたＹ方向クロスバスイッチ５についても同様である。このため、以下ではこれらのＸ方向クロスバスイッチ７を拡張クロスバスイッチあるいは拡張ＸＢ−Ｘ０と呼び、Ｙ方向クロスバスイッチ５を拡張クロスバスイッチあるいは拡張ＸＢ−Ｙ３と呼ぶことがある。他のＸ方向クロスバスイッチ６をＸＢ−Ｘ１、ＸＢ−Ｘ２、ＸＢ−Ｘ３と呼び、他のＹ方向クロスバスイッチ６をＸＢ−Ｙ０、ＸＢ−Ｙ１、ＸＢ−Ｙ２と呼び、中継スイッチを対応するノードの座標ｉｊを付けて、ＥＸｉｊと呼ぶことがある。各Ｘ方向クロスバスイッチ８あるいはＹ方向クロスバスイッチ５は、いずれかの中継回路３から入力されたメッセージをメッセージ内の宛先アドレスに従って転送するための、入出力ポートの数に等しい数の経路決定回路１３を有し、拡張クロスバスイッチ７あるいは６も同様に拡張ポート対応経路決定回路１４を有する。
【００３０】
（放送メッセージ中継回路１２）
この放送メッセージ中継回路１２の構造も特願平６−５３４０５号明細書に記載のものと同じ、そこに送られた複数の放送要求メッセージを順次選択し、選択された放送要求メッセージを、そのメッセージ内に含まれた放送すべき情報を含む放送メッセージに変更し、ネットワーク１を介して各ノードに放送する回路である。そこでは、この放送メッセージ中継回路１２は、一般に放送メッセージによりネットワーク１がデッドロック状態になるのを防止するために用いられている。本実施例では、その用途以外にも、ロック要求を含む複数の放送要求メッセージが複数のアクセス要求ノードから転送されたときに、それらを順次選択する逐次化回路として使用される。
【００３１】
すなわち、この放送メッセージ中継回路１２は、複数のノード２が接続されている中継スイッチ３とは別に設けられ、Ｘ方向クロスバスイッチの一つである拡張クロスバスイッチ７の拡張入出力ポート（ここではアドレス０４を有するもの）と、Ｙ方向クロスバスイッチの一つである拡張クロスバスイッチ６の拡張入出力ポート（ここではアドレス４３を有するもの）とに接続されている。この拡張Ｘ方向クロスバスイッチ７以外のＸ方向クロスバスイッチ８（例えば、ＸＢ−Ｘ１）に接続された中継スイッチに直接接続されているアクセス要求ノード（たとえば、ＥＸ１２に接続されたノード）が、ロック要求を含む放送要求メッセージをこの放送メッセージ中継回路１２に転送するときには、このノードは、この拡張Ｙ方向クロスバスイッチ６の拡張ポートのアドレス４３をメッセージ宛先アドレスとして含む放送要求メッセージを発信し、このメッセージは、このクロスバスイッチＸＢ−Ｘ１と、中継スイッチ、例えば、ＥＸ１３、拡張Ｙ方向クロスバスイッチ６、拡張入出力ポート４３を経由して放送メッセージ中継回路１２に転送される。一方、拡張Ｘ方向クロスバスイッチ７に接続された中継スイッチに直接接続されているアクセス要求ノード、例えば、中継スイッチＥＸ０１に接続されたノードが、ロック要求を含む放送要求メッセージをこの放送メッセージ中継回路１２に転送するときには、この拡張Ｘ方向クロスバスイッチ７の拡張ポートのアドレス０４をメッセージ宛先アドレスとして含む放送要求メッセージを発信し、このメッセージは、このクロスバスイッチ７のこの拡張入出力ポートを経由して放送メッセージ中継回路１２に転送される。
【００３２】
放送メッセージ中継回路１２は、特願平６−５３４０５号明細書に記載されているように、アドレスがそれぞれ０４と４３である二つの入力ポートに接続された二つの入力バッファと、これらの入力バッファの一方を選択するセレクタと、それらの二つの入力バッファのいずれを選択するかを決めて、このセレクタに指示するプライオリティ回路と、このセレクタにより選択された放送要求メッセージ内のコントロール（ＣＴＬ）ビットを放送メッセージに対するものに変更するコントロールビット変更回路と、この回路により変更された後のコントロールビットを含み、放送要求メッセージ内の放送すべき情報を含む放送メッセージをネットワーク１の出力ポート０４に送出する出力バッファとよりなる。このように、放送メッセージ中継回路１２は、そこに転送された放送要求メッセージをこのコントロールビット変更回路により放送メッセージに変更して、拡張Ｘ方向クロスバスイッチ７のアドレス０４の拡張入出力ポートに送出する。このように、アクセス要求ノードの位置により、放送要求メッセージが経由する経路が異なるのは、この放送要求メッセージに対応する放送メッセージの経路が放送要求メッセージのそれとが重複しないようにし、それにより、重複がある場合に生じ得るデッドロックが生じないようにしている。また、同時に二つの放送要求メッセージを受信したときでも、上述のプライオリティ回路により、これらを順次選択するようになっている。このように、複数の放送要求メッセージが放送メッセージ中継回路１２により、逐次ネットワーク１に送出され、同一の転送経路を通って全ノードに配送される。したがって、ネットワークの途中経路でのメッセージの追越しが発生しないネットワークでは、放送メッセージの到着する順番は全ノードで等しくなる。したがって、異なるノードから出力されたロック要求は、放送メッセージ中継回路１２により選ばれた順にしたがって全ノードに通知されることになる。後に説明するように、本実施例では同じ資源管理ノードに対するロック要求を含む複数の放送メッセージの内、各ノードに最初に到着した放送メッセージ内のロック要求が、有効なロック要求として処理され、その資源管理ノード内の共通ファイルのロックを許される。その後にその資源管理ノードに到着した放送メッセージ内のロック要求は、したがって、その共通ファイルをロックできなくなる。本実施例では、上記放送メッセージ中継回路１２の動作により、各ノードに到着する放送要求メッセージの順番は同じであるから、各ノードは同じアクセスノードから出力されたロック要求にロックを許すことになる。
【００３３】
（バイナリセマフォ）
ロック要求の処理の説明の前に、簡単にセマフォアの動作を説明する。共有ファイルをロックする方法は、本実施例では全ノードの受信制御回路２２にあるロック状態レジスタ群５２をセマフォとして用いることで実現する。ここでいうセマフォとはいわゆるバイナリ・セマフォアであり、同時に共有資源を獲得できる要求者を１つに限定する場合に用いられる。バイナリ・セマフォアは初期値として０で開始し、ロックを取るためのＰ操作とロックを解放するＶ操作が用いられる。
Ｐ（Ｘ）：「ｉｆ  Ｘ＝０  ｔｈｅｎ  Ｘ：＝１」…Ｐ操作
Ｖ（Ｘ）：「ｉｆ  Ｘ＝１  ｔｈｅｎ  Ｘ：＝０」…Ｖ操作
この操作を不可分な操作、例えばテスト・アンド・セット（Ｔ＆Ｓ）命令で行なうこと。そして、Ｐ操作によりバイナリ・セマフォアＸを１できた場合に、ロックが掛けられたことになる。そして、Ｖ操作によりバイナリ・セマフォアＸを０にすることでロックを解放することができる。
【００３４】
本実施例では、この動作を全ノードのロック状態レジスタ群５２をバイナリ・セマフォアとして使用することにより、シェアード・ナッシング方法のシステムで共有ファイルのロックを実現する。
【００３５】
（ロック状態レジスタ群５２の初期化）
全ノードは、装置動作を開始する前に、ロック状態レジスタ群５２の初期化を行なう。各ノード２は、この初期化動作において、ロック状態レジスタ群５２の全てに対して、プロセッサ２４がストア命令を用いてシステムバス２６を介して０を代入する。これによりロック状態レジスタ群５２の各レジスタの値が０になり、いずれのノードもロックされていないことを表す。
【００３６】
（ロック要求の処理）
以下、図３を参照して、資源管理ノード＃０に接続されたディスク装置２５に格納された共有ファイル３５をアクセス要求ノード＃１とアクセス要求ノード＃２がほぼ同時にアクセスする場合の、共有ファイルのロック方法について説明する。なお、図３において、処理２６１など二重線で囲まれた処理は主としてハードウエアにより実行される処理を表し、一重線で囲まれた処理は主としてプロセッサ２４で実行されるプログラムによる処理を表している。
【００３７】
まず資源管理ノード＃０、アクセス要求ノード＃１及び＃２で並列して検索処理プログラム３１がそれぞれのノードのプロセッサ２４により、それぞれローカルメモリ２３およびディスク装置２５を用いて実行される（ステップ２０１、２２１、２４１）。アクセス要求ノード＃１および＃２で資源管理ノード＃０のディスク装置２５の共有ファイル３５をほぼ同時に排他的にアクセスする必要が発生すると（ステップ２２２、２４２）、それぞれのノードで共有ファイルのロック要求を処理する（ステップ２２３、２４３）。
【００３８】
（１）ロック要求メッセージの放送
すでに述べたように、ロック状態レジスタ群５２は、この並列計算機内の全ての共有資源のロック状態を管理するためのレジスタで、ロックする資源の単位に対応して設けられている。本実施例では、各ノードをロックの単位とする。このため、本実施例では、このロック状態レジスタ群５０は、いずれかのノードにそれぞれ対応するレジスタからなる。したがって、以下では、各ノードのロック状態レジスタの番号を、そのレジスタが対応するノードの番号で呼ぶことにする。例えば、資源管理ノード＃０に対するロック状態レジスタを、ロック状態レジスタ＃０と呼ぶ。
【００３９】
アクセス要求ノード＃１、＃２は、この資源管理ノード＃０がすでにロック状態にあるか否かを判定する。このためにプロセッサ２４は、ロック状態レジスタ＃０の内容をシステムバス２６を介して読み出し、その値が０であるかをチェックする。もし、０でないならば、資源管理ノード＃０はロック済みであるため、ロック要求を出力しない。こうして、本実施例では、無駄なロック要求を各ノードが出すのを防いでいる。
【００４０】
アクセス要求ノード＃１、＃２は、この資源管理ノード＃０がロック済みでないことを確認した後、ロック状態レジスタ＃０に対して前述のＰ操作を以下のようにして行う。すなわち、全ノードに次のような以下に示すパラメータを含む放送要求メッセージ１１をメッセージ中継回路１２に送信する。このメッセージは、各ノードのロック状態レジスタ＃０をロック状態にすることを要求するロック要求メッセージを放送することを要求している。
【００４１】
Ｎａｄｒ（アドレス）：＝放送メッセージ中継回路１２のアドレス
ＣＴＬ（コントロール）：＝放送要求メッセージイネーブル
Ｒ＃（レジスタ番号）：＝＃０
Ｉｎｔ（割り込み）：＝ディスエーブル
Ｄ０（データ０）：＝０
Ｄ１（データ１）：＝アクセス要求ノード＃１（又は＃２）の番号
Ｃｔｙｐ０（演算タイプ０）：＝一致判定イネーブル
Ｃｔｙｐ１（演算タイプ１）：＝セットイネーブル
ここで、Ｎａｄｒは、この放送要求メッセージの転送先を表わすネットワークアドレスで、ネットワーク１により使用され、今の場合、このアドレスは放送メッセージ中継回路１２のアドレス０４または４３である。アドレス０４または４３のいずれを用いるかは、そのアクセス要求ノード＃１が拡張Ｘ方向クロスバ７に接続された中継スイッチに接続されているか否かによることはすでに記載したとおりである。ＣＴＬはメッセージの種類を表わすコントロールビットで、今の場合放送要求メッセージであることを表わす。Ｒ＃は、ロック要求の対象となった資源管理ノードに対応するロック状態レジスタの番号で、今の場合は＃０である。Ｉｎｔは、この放送要求メッセージにより要求されるロックの取得が成功した場合に、アクセス要求ノード＃１に割込によりそのことを通知するか否かを指示するフィールドであり、ここではディスエーブルを設定しているため割込は発生しない。この場合、後で述べるようにこのロック要求が成功したか否かは、アクセス要求ノード＃１内のプロセッサ２４がそのノード内のロック状態レジスタ＃０の内容を監視して検出する。一方、Ｉｎｔフィールドをイネーブルにした場合、アクセス要求ノード＃１は、割り込みを待合せて、ロックが成功したか否かの判定する。Ｄ０とＤ１は、それぞれ各ノードのロック制御回路５００での演算に使用されるべきデータを表わす。今の例では、Ｄ０はロック状態レジスタ＃０がロックされていない状態を表わす値０を示し、このレジスタの現在の値が０か否かを判定するのに使用される。Ｄ１は、今の場合、このレジスタのロックが成功した場合に、このレジスタに書き込むべきデータとして、アクセス要求ノード＃１（または＃２）の番号を表わす。Ｃｔｙｐ０は、各ノードでの演算を指定する第１のパラメータで、今の場合、ロック状態レジスタ＃０の現在の値とデータＤ０との一致判定を示す。これにより、現在のこのレジスタがロックされていない状態にあるか否かを判定することになる。Ｃｔｙｐ１は、ロック状態レジスタ＃０にロック制御回路５００での演算結果を書き込むべきか否かを示す信号で、今の場合は、書き込みを指示している。
【００４２】
アクセス要求ノード＃１は、上に述べた放送要求メッセージの送信のために、送信パラメータ格納レジスタ４２に対してプロセッサ２４はシステムバス２６を介して上に述べたパラメータをストア命令を用いて書き込む。送信制御回路２１では、メッセージ生成回路４１が送信パラメータ格納レジスタ４２に以上のパラメータが書き込まれたことを検出すると、この送信パラメータから放送要求メッセージ１１を生成し、ネットワーク１に送出する。ネットワーク１へのこの放送要求メッセージの送出が完了すると、送信状態レジスタ４３内の状態ＳＴを「送信完了」に設定する。プロセッサ２４は送信状態レジスタ４３をロード命令によりシステムバス２６を介して監視することで、共有ファイルのロック要求が終了したことを知ることができる。そして、送信状態レジスタ４３を「送信完了」になったことを確認したら、プロセッサ２４はストア命令により送信状態レジスタ４３をクリアし、次のメッセージの送信ができるようにする。
【００４３】
ネットワーク１に送出されたメッセージ１１はすでに説明したように放送メッセージ中継回路１２に送られる。アクセス要求ノード＃１及び＃２の動作はロック要求の発行に関しては同じ動作をする。これらのノードから発信された上記メッセージを放送メッセージ中継回路１２が順次選択し、この選択したメッセージ内のコントロールビットＣＴＬを、放送要求メッセージを表わすものから放送メッセージを表わすものに変換し、ネットワーク１により全ノードに放送する（ステップ２６１）。さて、先に述べたようにアクセス要求ノード１とアクセス要求ノード２はほぼ同時に共有ファイル３５のロック要求を行なっているが、本ケースではアクセス要求ノード１から送出された放送要求メッセージがアクセス要求ノード２から送出された放送要求メッセージより先に放送メッセージ中継回路１２により選択され、全ノードに放送されると仮定する。このことは既に説明したように全ノードで到着するロック要求メッセージの到着する順番が、アクセス要求ノード１からのロック要求メッセージがアクセス要求ノード２からのロック要求メッセージに先行していることを意味する。
【００４４】
（２ａ）ロック要求の調停（ロック成功ケース）
各ノードの受信制御回路２２は、アクセス要求ノード１からのロック要求を格納した放送メッセージを受信すると、次の動作を行なう。ネットワーク１からメッセージを入力バッファ５１に一時的に格納する。入力バッファ５１に格納されたメッセージのロック状態レジスタ番号＃Ｒ（今の場合は＃０）にしたがって、ロック状態レジスタ＃０に格納された値、ここでは初期値０が、一致判定回路５３、大小判定回路５４、加算回路５６に対して出力される。受信したメッセージのデータＤ０、ここでは値０が一致判定回路５３と大小判定回路５４に出力される。一致判定回路５３は、それへの二つの入力はどちらも０であるため、その出力は１となる。本ケースでは、このメッセージのＣｔｙｐ０が一致判定イネーブルであるため、一致判定回路５３の出力がセレクタ５５により選択され、大小判定回路５４の出力は選択されない。こうして、セレクタ５５の出力はアクティブになり、これに応答するゲート５８はアクティブになる。一方、受信したメッセージのＣｔｙｐ１フィールドはセットイネーブルであるため、受信したメッセージのＤ１、ここではアクセス要求ノード＃１のノード番号＃が、セレクタ５７により選択され、ゲート５８に出力される。ゲート５８がアクティブであるため、ゲート５８の出力であるアクセス要求ノード＃１のノード番号＃１がロック状態レジスタ＃０に書き込まれる。また、受信したメッセージのＩｎｔフィールドはディスエーブルであるため、アンドゲート５９の出力はネガティブであり、プロセッサ２４に対して割込は発生しない。
【００４５】
なお、ロック要求の調停が以上のように行われるが、本実施例では、この調停により選択されたロック要求に対して、資源管理ノードにおける、そのロック要求が要求する資源自体のロックは行われない。
【００４６】
（２ｂ）ロック要求の調停（ロック失敗ケース）
資源管理ノード＃０がすでにロック状態レジスタ＃０の値が
アクセス要求ノード２からのロック要求を格納した放送メッセージは、アクセス要求ノード１からのロック要求を格納した放送メッセージに後に各ノードで受信される。この場合にも上の（２ａ）と同じように処理されるが、この場合には、ロック状態レジスタ＃０にはすでにアクセス要求ノード＃１のノード番号が書き込まれているために、一致判定回路５３では一致は検出されず、その出力はネガティブになり、従って、セレクタ５５の出力もゲート５８もネガティブになる。このためゲート５８はロック状態レジスタ＃０に対して書き込みは行なわない。したがって、アクセス要求ノード＃１がノード＃０をロックしている状態が維持される。
【００４７】
このようにロック状態レジスタ＃０に対する複数のＰ操作が全てのノードに対して同じ順番で実行されることにより、ロックの排他性を保証することができる。また、このロック処理の間、資源管理ノード＃０では、実行中の処理を中断することがない。
【００４８】
（３ａ）ロックの確認（成功ケース）
共有ファイルのロック要求を行なったアクセス要求ノード＃１ではロック状態レジスタ＃０をロード命令により監視し、ロック状態レジスタ＃０の内容が自ノードのノード番号に変更されたことを確認できたことにより、ロックの成功を確認する（ステップ２２４）。これ以降資源管理ノード＃０内の共有ファイル３５へのアクセス権はアクセス要求ノード＃１がロックを解除するまでアクセス要求ノード＃１が獲得する。
【００４９】
（３ｂ）ロックの確認（失敗ケース）
共有ファイルのロック要求を行なったアクセス要求ノード＃２ではロック状態レジスタ＃０をロード命令により監視し、ロック状態レジスタ＃０の内容がはアクセス要求ノード＃１のノード番号に変更されたことにより、ロックの失敗を確認する（ステップ２４４）。これ以降は、アクセス要求ノード＃１がロックを解除するまでアクセス要求ノード＃２は共有ファイル３５をアクセスできない。
【００５０】
（４）ファイルアクセス
以下、アクセス要求ノード＃１は資源管理ノード＃０のプロセッサ２４で実行されるＩ／Ｏ処理プログラム３２に対してネットワーク１を介してアクセス要求を含むメッセージを発行することにより、共有ファイル３５のアクセスを行なう（ステップ２２５）。このメッセージを受けた資源管理ノードでは、このメッセージが入力バッファ５１に取り込まれた時点で、図示しない割り込み回路により、プロセッサ２４に割り込み信号を供給する。そのプロセッサ２４では、割り込み処理プログラムにおいて、このアクセス要求が通信宛先として指定するＩ／Ｏ処理プログラム３３を起動して、このアクセス要求が指定するファイルに対してこの要求が指定するＩ／Ｏ動作を実行することを指示する（ステップ２０２）。このアクセス要求が、読み出し要求のときには、プロセッサ２４は、このデータをディスク装置ディスク装置２５から読み出し、このデータを含むメッセージをアクセス要求ノードに送信する。もしこのアクセス要求が書き込み要求のときには、このアクセス要求には書き込みデータが含まれ、このデータをプロセッサ２４は、ディスク装置２５に書き込み、書き込みの完了を示すメッセージをアクセス要求ノードに送信する。
【００５１】
従来技術では、いずれかの資源管理ノードは、他のノードから発信されたファイルアクセス要求を受信した場合には、そのファイルアクセスが指定するアクセスを実行するためのコプロセスを生成し、そのコプロセスの実行を制御する。この場合、その資源管理ノードは、複数のノードからディスク記憶装置２５内の同一のファイルに対して、異なるノードからロック要求を並行して受信した場合、それぞれのロック要求に対してコプロセスを発生する。これらのコプロセスは同一のファイルに対するアクセスであるので、資源管理ノードでは、これらのコプロセスによる、このファイルへのロック要求を調停するようになっている。すなわち、いずれか一つのコプロセスを選択する。さらに、従来のロック要求の処理では、その選択されたコプロセスがそのファイルを排他的に使用可能なように、そのファイルをロックし、そのコプロセスの使用が終了するまで、そのファイルを他のコプロセスが使用するのを禁止する。
【００５２】
本実施例では、各アクセス要求ノードから資源管理ノードにロック要求を送らない。したがって、資源管理ノードでは、そのノード内の資源をロックすることはない。上述のように、本実施例では、資源管理ノードのプロセッサの外部に設けた排他的な使用要求を調停する回路により、同じ資源管理ノード内のディスク記憶装置２５に対しては一つのアクセス要求ノードのみがアクセスを許されている。すなわち、この資源の排他的な使用が、この資源管理ノードのプロセッサの外部で調停されている。したがって、この資源管理ノードのプロセッサには、同一のディスク記憶装置に対する複数の排他的な要求が供給されない。したがって、アクセスを要求する複数のコプロセスが並行して生成されない。従って、この資源管理ノード内では、ロック制御を行わなくても、同じディスク記憶装置への、異なるノードからのアクセスは同時には生じない。したがって、本実施例では、資源管理ノードでは、資源をロックしない。本実施例においては、各ノードがロック状態レジスタ群を有し、他のノードの資源をアクセスするときに、この状態レジスタ群によりその資源がロック済みか否かを判定することにより、同一の資源の排他的は使用を保証している。
【００５３】
（５）共有ファイルのロック解除要求
共有ファイル３５のアクセスを完了したアクセス要求ノード＃１は、共有ファイル３５のロックを解除するため、次の手順によりロック状態レジスタ＃０に対してＶ操作を行なう。まず、次のパラメータを含む放送要求メッセージを放送中継回路１２に転送し、そこから、このパラメータを含むメッセージを、全ノードに放送することで行なう。
【００５４】
Ｎａｄｒ：＝放送中継回路１２のアドレス
ＣＴＬ：＝放送要求メッセージイネーブル
Ｒ＃：＝＃０
Ｉｎｔ：＝ディスエーブル
Ｄ０：＝アクセス要求ノード＃１のノード番号
Ｄ１：＝０
Ｃｔｙｐ０：＝一致判定イネーブル
Ｃｔｙｐ１：＝セットイネーブル
このパラメータは、先に述べた、ロック要求を含む放送要求メッセージと比べると、データＤ０とＤ１の内容が入れ換わっているだけである。このメッセージは放送メッセージ中継回路１２へ送信され、そこからネットワーク１を介して全ノードへ放送される（ステップ２６２）。その時の回路動作は、先に述べたロック要求を含む放送要求メッセージの場合と同じである。
【００５５】
（６ａ）ロック解除
各ノードでは、アクセス要求ノード＃１からのロック解除要求を格納した放送メッセージを受信すると、受信制御回路２２は、さきのロック要求を含むメッセージの場合と同様に、ロック状態レジスタ＃０に、データＤ０で示されるアクセス要求ノード＃０が保持されていることを一致判定回路５３で判定した上で、このレジスタにデータＤ１で示される値０を書き込む。これにより、ロック状態レジスタ＃０は初期値０に戻り、共有ファイル３５はどのノードも使用していない状態になる。
【００５６】
一方、処理２４４の結果としてロック失敗となったアクセス要求ノード＃２は、共有ファイルのロック再要求待ち（ステップ２４５）になる。通常この処理はプロセッサ２４が内部的に保持しているタイマ機能を用いて、ある時間後に再びロック要求処理（ステップ２４３と同じ）を行なうことで実現される。例えば、アクセス要求ノード＃１がロック状態レジスタ＃０に対してロック解除を行なう前に、アクセス要求ノード＃２がロック要求を再び行なったとしても、ロック状態レジスタ＃０の値はアクセス要求ノード＃１のノード番号が格納されているためＰ操作が失敗し、ロックは失敗する。しかし、ロック状態レジスタ群５２のフリー処理が行なわれた後でアクセス要求ノード＃２がロック要求を行なった場合、処理２１１〜２と同様にして、ロック状態レジスタ＃０にはアクセス要求ノード＃２のノード番号が格納され、アクセス要求ノード＃２はロックの獲得に成功する。
【００５７】
このように本実施例ではロックの要求および解除のどちらにおいても資源管理ノードのような特定のノードのプロセッサが行なっている検索処理を中断することなく実現することができる。このため、システム全体の性能を向上することができる。
【００５８】
＜実施例１の変形例１＞
実施例１は特願平６−５３４０５号明細書に記載の放送メッセージ中継回路１２を使用した。この回路は、ハイパクロスバネットワーク内には存在しないで、新たに設けられている。本変形例ではこのような追加の回路を使用しないで、実施例１と同様の動作を実現する。
【００５９】
すなわち、特願平６−１６９９９５号明細書には、各Ｘ方向クロスバネットワーク方向とＹ方向クロスバネットワークに通常備わっている、そのクロスバネットワークに転送されてきた複数の放送メッセージを逐次に放送する逐次化回路を使用して、特願平６−５３４０５号明細書内の放送メッセージ中継回路と同じようにして、ネットワーク内でのデッドロックを防止する技術が示されている。この技術では、放送を要求するノードが、ネットワーク内の複数のクロスバスイッチの内の、予め放送メッセージの逐次化回路用に定められた特定の一つのクロスバスイッチに接続された一つの中継スイッチに宛てて放送要求メッセージを送出する。この特定の中継スイッチとしては、放送メッセージの送出元のノードが接続され、上記特定のクロスバスイッチと対応する座標軸が異なるクロスバスイッチ（例えば、上記特定のクロスバスイッチがＸ方向クロスバスイッチであるときには、Ｘ方向のクロスバスイッチ）と、上記特定のクロスバスイッチとに接続された中継スイッチが使用される。この特定のクロスバネットワークでは、それに接続された複数の中継スイッチから複数の放送要求メッセージがそのクロスバスイッチに転送されてきたときに、それらの一つを選択して、選択した放送要求メッセージを放送メッセージに変更し、そのクロスバスイッチに接続された上記複数の中継スイッチの各々にこの放送メッセージを送出し、それらの中継スイッチを介してこれらの放送メッセージをネットワークに接続された複数のノードに送出する。
【００６０】
本変形例でもこの特定のクロスバスイッチを実施例１の放送メッセージ中継回路１２と同様に使用する。すなわち、図１において、放送中継回路１２を削除し、それにともなって、拡張Ｘ方向クロスバスイッチ１ＸＥ、拡張Ｙ方向クロスバスイッチ１ＹＥを、それぞれ他のＸ方向クロスバスイッチとＹ方向クロスバスイッチと同じ数の入出力ポートを有するもので構成する。各ノードは、ロック要求を含む放送依頼メッセージを、上記特定のクロスバスイッチに接続されたいずれかの中継スイッチ（具体的には上に説明した特定の中継スイッチ）に宛てて、ロック要求を含む放送要求メッセージを送出するようにすればよい。その後は、特願平６−１６９９９５号明細書に示した方法で、この放送要求メッセージに対する放送メッセージが各ノードに放送される。各ノードは、実施例１に示したのと同じ回路により構成され、その動作も実施例１の場合と同じである。
【００６１】
＜実施例１の変形例２＞
実施例１においては、放送メッセージ中継回路１２は、そこに転送された、ロック要求を含む複数の放送要求メッセージの一つを選択し、選択された放送要求メッセージを放送メッセージに変更してネットワーク１を介して複数のノードに転送した。したがって、この放送メッセージ中継回路１２は、それぞれロック要求を含む、複数の放送要求メッセージを順次選択する逐次化回路として作用している。しかし、この放送メッセージ中継回路１２は、同じノードに対するロック要求を含む複数の放送要求メッセージの内最初に選択した放送要求メッセージに対する放送メッセージを放送するだけでなく、同じノードに対するロック要求を含む後続の放送要求メッセージに対する放送メッセージも放送する。各ノードは、同じノードに対するロック要求を含む複数の放送メッセージを順次受信するが、同じノードに対するロック要求を含むこれらの放送メッセージの内、最初に受信された放送メッセージ内のロック要求のみを有効なロック要求として処理した。このため、実施例１では、同じノードに対するロック要求を含む複数の放送メッセージの内、最初に放送されるメッセージ以外のメッセージは、各ノードでは使用されないにもかかわらず、放送される。このため、ネットワーク１は、このような無駄は放送メッセージのために使用されるという問題がある。本変形例では、このような無駄なメッセージの放送をなくす。
【００６２】
このために、放送メッセージ中継回路１２内にも、各ノードに設けられているロック制御レジスタ群５２とロック制御回路５００とを設ける。すなわち、この放送メッセージ中継回路１２内のプライオリティ回路がいずれかのノードに対するロック要求を含む放送要求メッセージを最初に選択したときに、その放送要求が指定するロック先ノードをそのロック先ノードに対応するロック状態レジスタに格納し、このノードがロック済みであることを表示するように、このロック制御回路を構成する。この放送要求に対しては、実施例１と同様に、この放送メッセージ中継回路１２内のコントロールビット変更回路により、この最初に選択された放送要求メッセージを、放送メッセージに変更した上で、ネットワークに転送する。さらに、この放送メッセージ中継回路１２のプライオリティ回路が、ロック要求を含む後続の放送要求メッセージを受信したときに、放送メッセージ中継回路１２内に設けたロック制御回路により、その放送要求メッセージが要求するロック先のノードに対するロック状態レジスタの内容を調べ、そのレジスタ内にいずれかのロック要求元のノードの番号が格納されているときには、ロック要求を含む、この後続の放送要求メッセージを無効メッセージとし、このメッセージの放送は行わないようにする。こうすることにより、同じノードの対するロック要求を含む放送要求メッセージの内、最初に選択されたものに対応する放送メッセージのみが放送されることになる。各ノードのロック制御回路５００の構成は、実施例１と同じでよい。
【００６３】
＜実施例１の変形例３＞
変形例２で放送メッセージ中継回路１２内に設けた回路と同じ回路を、変形例１で説明した、放送メッセージの逐次化回路用に使用する特定のクロスバスイッチ内の逐次化回路に設けることにより、変形例２と同様の動作を実現できる。
【００６４】
＜実施例１の変形例４＞
実施例１では、放送メッセージ中継回路を、ロック要求を含まない通常の放送要求メッセージの逐次化にも使用し、ネットワーク１をこれらの放送要求メッセージあるいはそれらに対してこの回路により生成された通常の放送メッセージの転送にも使用した。さらに、この放送メッセージ中継回路を、ロック要求を含む放送要求メッセージの逐次化にも使用し、ネットワーク１をこれらの放送要求メッセージあるいはそれらから生成される放送メッセージの転送にも使用した。しかし、ロック要求を含む放送要求メッセージと、それから生成されるロック要求を含む放送メッセージのために、別の放送メッセージ中継回路を含む別のネットワークを使用することは、メッセージの転送速度を向上するのに有効である。
【００６５】
＜実施例２＞
実施例１では、ある資源への複数のロック要求を、その資源がいずれのノードに属するかに関係なく、各ノードで調停し、その結果をそれぞれのノードのロック状態レジスタに保持し、それぞれのノードで利用した。実施例１ではそのためにロック要求元は、放送メッセージ中継回路にロック要求を含む放送要求メッセージを発信し、この回路が、このメッセージを放送メッセージに変更して各ノードに放送した。このため、全てのロック要求を含む放送要求メッセージが放送中継回路に転送された。このために、この放送メッセージ中継回路には、ロック要求を含む多くの放送要求メッセージが転送されることになり、この回路での処理の遅延が発生する恐れがある。さらに、各ノードのロック状態レジスタ群は、それぞれ一つのロック単位、例えば、ノードに対応して使用され、かつ、各ロック状態レジスタは、対応するノードの資源がロックされたときに、そのロックに成功したノードの番号を保持した。このためノードの数が増大すると、より多くのレジスタが必要になる。本実施例はこれらの問題をなくす。
【００６６】
図４は、本実施例での並列計算機の概略構成を示す。以下、実施例１との相違点を中心に説明する。本実施例では、複数のアクセスノードがある資源管理ノードに属する資源へのアクセスを要求する場合、それぞれのアクセス要求ノードはロック要求を含む複数のロック要求を、その資源管理ノードに一対一通信で転送し、その資源管理ノードはこれらのロック要求を調停し、その一つにロック権を与えることを示す調停結果を各ノードに放送メッセージにより通知する。これにより、実施例１での放送中継回路へのロック要求を含むメッセージの集中を避ける。本実施例でのネットワーク１には実施例１と同じく、放送メッセージ中継回路１２が設けられ、上記資源管理ノードは、上記調停結果の放送に当っては、この調停結果を含む放送要求メッセージをこの放送メッセージ中継回路１２に送り、この回路によりこの調停結果を全てのノードに放送する。このように、この放送メッセージ中継回路１２は、ロック要求を含む放送要求メッセージの逐次化には使用されないで、上記調停結果など、ロック要求以外の情報を含む放送要求メッセージの逐次化に使用される。
【００６７】
各ノードのロック制御回路５００では、各ノードでは全ノードに対して一つのロック状態レジスタ１５３が設けられ、このレジスタの複数のビット位置は、一つのロック単位に対応して設けられ、ここでは、ロック単位はシステムのいずれか一つのノードである。それぞれのビット位置は、対応するノードがロックされた状態にあるかに応じて値１または０をとるロック状態を記憶する。これにより、実施例１におけるロック状態レジスタの増大を防いでいる。各ノードにはさらに、自ノードがロック済みの資源を識別するためのロック獲得レジスタ１５２を設ける。このレジスタの各ビットは、それぞれ一つのロック単位、ここではノードに対応し、そのレジスタが属するノードがいずれかの資源管理ノードをロックしたときに、その資源管理ノードに対応するビットに値１を格納するようになっている。ロック制御回路５００は、実施例１と異なり、ここではロック要求の調停を行わないで、いずれかの資源管理ノードから発信された調停結果に基づいて、これらのレジスタの更新を行う。アクセス要求ノードは更新後のレジスタ値に基づいて自己が発信したロック要求が許可されたか否かを判定する。
【００６８】
以下、図４の装置の動作の詳細をさらに説明する。
（レジスタの初期化）
全てのノードにおいて、それぞれの中のプロセッサ２４は、ロック状態レジスタ１５２、ロック獲得レジスタ１５３を０にリセットする。各ノードのノード＃レジスタ１５４には、そのノードの番号をセットする。
【００６９】
（ロック要求の処理）
図５のフローチャートを参照してこの処理の実行方法を説明する
（１）ロック要求メッセージの放送
アクセス要求ノードでは、アクセスすべき資源が属する資源管理ノードがロックされているか否かを、ロック状態レジスタ１５２内の、そのノードに対応するビットの値に基づいてチェックし、そのノードがロックされていないときに、ロック要求を含むメッセージをその資源管理ノードに宛てて発信する（ステップ５２３、５４３）。この発信のために以下のパラメータを送信パラメータ格納レジスタ４２に格納する。
【００７０】
Ｎａｄｒ（ネットワークアドレス）：＝資源管理ノードのノード番号
ＣＴＬ（コントロール）：＝一対一転送メッセージイネーブル
ＣメッセージＤ（コマンド）：＝ロック要求
Ｉｎｔ（割り込み）：＝ディスエーブル
Ｂ＃（ビット番号）：＝資源管理ノードの番号
Ｔ＃（ターゲットノード番号）：＝資源管理ノードの番号
Ｒ＃（アクセス要求ノード番号）：＝自ノードの番号
ここで、ＣＴＬはメッセージの種類を表わすビットで、ここでは一対一メッセージを表わす。ＣメッセージＤは、コマンドの種類を表わすコードで、ここでは、ロック要求を表わす。本実施例では、ロックに関するコマンドとしては、この他に、ロック通知、ロック解除などのコマンドを使用する。Ｂ＃は、ロックすべき資源を識別する情報で、ここでは、その資源の資源管理ノードの番号を使用する。Ｔ＃は、ロックすべき資源が属する資源管理ノードの番号である。Ｒ＃は、アクセス要求ノードの番号である。Ｎａｄｒ、ＣＴＬ、Ｉｎｔに関しては、実施例１と同様である。メッセージ生成回路４１は、このパラメータを含むメッセージをネットワーク１を介して、このアドレスＮａｄｒにより示される資源管理ノードに転送する。
【００７１】
（２ａ）ロック要求の調停（ロック成功ケース）
複数のアクセス要求ノードからそれぞれロック要求を含む複数のメッセージが同じ資源管理ノードに宛てて発信されると、それらのメッセージはネットワーク１によりその資源管理ノードに並行して転送されるが、この資源管理ノードは、これらのメッセージをネットワークから順次受信し、入力バッファ５１に順次供給する。入力バッファ内にこのようなメッセージの内の先頭のメッセージが入力されると、このコマンド内のビット番号Ｂ＃が、ロック状態レジスタ１５３、ロック獲得レジスタ１５２に供給される。さらに、この入力バッファ５１内に設けられたデコーダ（図示せず）によりコマンドビットＣメッセージＤが解読され、このコマンドがロック要求のときには、ロック要求を解読したことを示す信号がＡＮＤゲート１５５に供給される。このＡＮＤゲート１５５の他方の反転入力には、ロック状態レジスタ１５３内の、ビット番号Ｂ＃のビットが入力され、もし、このビットの値が０のとき（すなわち、資源管理ノードがまだロックされていないとき）には、このＡＮＤゲートの出力は１となる。この出力信号は、このロック要求に対して、ロックが許可されることを示すもので、ロック状態レジスタ１５３のセット端子にＯＲゲート１５９を介して送られる。その結果、そのレジスタは、それにすでに入力されているビット番号Ｂ＃のビット位置に値１を書き込み、この資源管理ノードがロックされたことを表示する。さらに、ＡＮＤゲート１５５の出力は、メッセージ生成回路４１に、コマンドとしてロック報告を含む放送要求メッセージを送出することを指示する。このように、このＡＮＤゲート１５５によりロック状態の検査が行なわれる（ステップ５０２）。
【００７２】
メッセージ生成回路４は、ＡＮＤゲート１５５からの上記指示信号に応答して、入力バッファ５１内のメッセージに基づいて、放送要求メッセージを生成する。すなわち、このメッセージ内のパラメータとして、次ぎの新たなパラメータと、入力バッファ５１内の他のパラメータを含むメッセージを生成してネットワーク１に送出する。以下の新たなパラメータはメッセージ生成回路４１内に予め保持されている。
【００７３】
Ｎａｄｒ：放送メッセージ中継回路１２のアドレス
ＣＴＬ：放送要求メッセージ
ＣメッセージＤ：ロック報告
このメッセージは、放送メッセージ中継回路１２により、放送メッセージになるように、コントロールビットＣＴＬが変更された後に、各ノードに放送される（ステップ５０３）。
【００７４】
（２ｂ）ロック要求の調停（ロック失敗ケース）
ロック要求をそれぞれ含む複数のメッセージの内の、上記先頭のメッセージの処理が以上のようにして終了すると、それらのメッセージの内の後続のメッセージがその後順次入力バッファ５１に取り込まれるが、それらのメッセージに対しては、ＡＮＤゲート１５５に入力される、ロック状態レジスタ１５２のビットの値がすでに１になっているので、ＡＮＤゲート１５５の出力は０のままであり、これらのメッセージに含まれたロック要求にはロックは許可されない。
【００７５】
（３）ロックの確認
上記放送中継回路１２から放送されたロック報告を含むメッセージがすでにロック要求を発行したいずれかのノードに転送されたときには、上記メッセージ内のターゲットノード番号Ｔ＃が一致回路１６０に送られ、自ノードレジスタ１５４内のノード番号と比較される。この比較の結果、このノードが、上記資源管理ノード以外のノードであるときには、一致は検出されない。ＡＮＤゲート１５８には、一致回路１６０の反転出力と上記メッセージ内のコマンドＣメッセージＤがロック報告であることを解読した信号が入力される。したがって、上記資源管理ノード以外のノードでは、いずれの入力も１であるから、このＡＮＤゲート１５８の出力は１となり、ＯＲゲート１５９を介してロック状態レジスタ１５３のセット端子に入力され、このレジスタ１５３は、上記メッセージのビット番号Ｂ＃が示すビット位置に１をセットする。こうして、これらのノード内のロック状態レジスタ１５３は、上記資源管理ノードがロックされた状態にあることを表示する（ステップ５２４、５４４）。なお、上記資源管理ノードでは、前述したとおり、いずれかのロック要求にそのノードのロックを許可したときに、このロック状態レジスタ内の同じビット位置に１を書き込んでいる。
【００７６】
上記ロック報告を含むメッセージを受信したノードが、いずれかのアクセス要求ノードであるとき、そのノードでは、そのメッセージ内の、アクセス要求ノード番号Ｒ＃が、一致回路１６１に送られ、そこで、ノード番号レジスタ１５４内のノード番号と比較される。上記資源管理ノードにロック要求を送った複数のアクセス要求ノードのうち、ロックを許可されたアクセス要求ノードでは、この一致判定の結果、一致が検出される。ＡＮＤゲート１５７には、この一致回路１６１の出力と、メッセージ内のロック報告の解読信号が入力されるので、このＡＮＤゲートの出力は、ロックに成功したアクセス要求ノードでは１となり、ロック獲得レジスタ１５２のセット端子に入力され、このレジスタ１５２は、上記メッセージのビット番号Ｂ＃が示すビット位置に１をセットする（ステップ５２４）。一方、アクセス要求ノードのうち、ロックを許可されなかったノードでは、このロック獲得レジスタ１５２の内容は変更されない。
【００７７】
したがって、複数のアクセス要求ノードは、プロセッサ２４が、これらのレジスタ１５２、１５３の内容を見て、資源管理ノードがロックされたか、ロックされたときには、自己がロックに成功したかを判定することができる（ステップ５２５、５４５）。
【００７８】
なお、ＡＮＤゲート１５６は、ロックが成功したアクセス要求ノードにおいて、一致回路１６１で一致が見られ、かつ、受信した上記メッセージ内の割り込み信号Ｉｎｔが１であるとき、そのプロセッサ２４にロックが成功したことを示す割り込み信号を供給する。
【００７９】
（４）ファイルアクセス
ロックに成功したアクセス要求ノードは、上記資源管理ノードに対してアクセス要求を発信し、資源管理ノードはその要求に応答して、資源管理ノード内のディスク装置にアクセスする（ステップ２２５、２０２）。この方法は実施例１と同様である。
【００８０】
（５）共有ファイルのロック解除要求
このアクセス要求ノードによるアクセスが完了すると、このノードはアンロック要求を含む放送依頼メッセージを放送メッセージ中継回路１２に転送する。このメッセージのパラメータは以下のとおりである。このメッセージを受けて、放送メッセージ中継回路１２は、このパラメータを含むメッセージを各ノードに放送する（ステップ５２７）。
【００８１】
Ｎａｄｒ：＝放送中継回路１２のアドレス
ＣＴＬ：＝放送要求メッセージイネーブル
ＣメッセージＤ：＝アンロック
Ｉｎｔ：ディスエーブル
Ｂ＃：＝上記資源管理ノードの番号
Ｔ＃：＝上記資源管理ノードの番号
Ｒ＃：＝自ノードの番号
各ノードでこのメッセージを受信したときには、入力バッファ５１から与えられる、アンロック要求を解読したことを示す信号が、ロック状態レジスタ１５２とロック獲得レジスタ１５３のリセット端子に与えられ、これらのレジスタは、このメッセージ内のビット番号Ｂ＃が示すビットの値を０にリセットする。なお、複数のノードの内、ロックに成功したアクセス要求ノード以外では、ロック獲得レジスタ１５２の値は、それまでにすでに０であるので、このアンロック処理によって変わらない。こうして、各ノードにおいて、これらのレジスタは、上記資源管理ノードがアンロック状態にあることを示す（ステップ５０４、５２８、５４７）。
【００８２】
以上から分かるとおり、本実施例では、実施例１と同様の利点を有するだけでなく、実施例１と異なり、アクセスすべき資源を管理するノードで、その資源に対する複数のロック要求の調停を行うので、実施例１で述べたように放送メッセージ中継回路にロック要求を含む放送要求メッセージを送出する必要がなく、その回路に多くの放送要求メッセージが集中することを緩和できる。さらに、本実施例では、一つのロック状態レジスタと一つのロック獲得レジスタでもって、各資源のロック状態とどのノードがロックに成功したかを判別可能にしたので、実施例１より少ないレジスタで間に合う。
【００８３】
＜実施例２の変形例＞
実施例２では、各ノードに存在する共有ファイルは一つとしたが、各ノードに複数の共有ファイルが存在する場合、ロック状態レジスタとロック獲得レジスタを複数設け、各ノードの異なる共有ファイルに対して、異なるロック状態レジスタと異なるロック獲得レジスタを使用すれば、それぞれの共有ファイルに対して他と独立にロックを管理できる。
【００８４】
【発明の効果】
本発明によれば、アクセス要求ノードにおいて、アクセスすべき資源がロック済みでないことを確認してから、この資源に対するアクセス要求を送出するので、無駄なロック要求を出さない、それにより無駄なロック要求に対する排他制御を減らせる。
【図面の簡単な説明】
【図１】本発明による並列計算機の構成図。
【図２】図１の装置に使用するネットワークの概略構成図。
【図３】図１の装置における共有ファイルへのアクセスの処理のフローチャート。
【図４】本発明による他の並列計算機の構成図。
【図５】図４の装置における共有ファイルへのアクセスの処理のフローチャート。
【符号の説明】
２６…システムバス、５８…論理ゲート
【図１】
0003904251.tif 000002
【図２】
0003904251.tif 000003
【図３】
0003904251.tif 000004
【図４】
0003904251.tif 000005
【図５】
0003904251.tif 000006