(57)【特許請求の範囲】
【請求項１】
ノードが結合されて構成されるコンピュータネットワークシステムにおいて、
各前記ノードは、
両端が他ノードとの接点を有する準閉パスが自ノード内に形成されているか否かを検出する準閉パス検出手段と、
前記準閉パス検出手段により準閉パスの形成が検出されていた際、前記準閉パスの一端側に位置する他ノードに準閉パスの有無のチェックを依頼するチェック依頼手段と、
他ノードから受信したチェック依頼に応答し、受信したチェック依頼が自ノードが発行したチェック依頼が回帰したものであるか否かを判断し、自ノードが発行したチェック依頼が回帰した場合にグローバルなデッドロックが発生したことを判断する回帰判断手段とを具備することを特徴とするコンピュータネットワークシステム。
【請求項２】
複数のノードにまたがるグローバルなデッドロックの検出方法であって、
処理中のプログラムがウエイト状態に入ることにより準閉パスがあるノード内に形成されているか否かを検出する準閉パス検出工程と、
前記準閉パスの形成が検出されていた際、前記準閉パスの一端につながるウエイトパスを辿る工程と、
前記辿る工程により前記ウエイトパスが前記あるノードの前記ウエイトパスの他端に回帰することを検出した際にグローバルなデッドロックが発生したと判別する工程とを具備することを特徴とするデッドロック検出方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明はコンピュータネットワークシステムに関し、特に複数のノードにまたがったグローバルなデッドロック状態を検出し、グローバルなデッドロック状態を解除する技術に関する。
【０００２】
【従来の技術】
ネットワークシステムにおいては、グローバルなデッドロックとローカルなデッドロックが発生する可能性がある。グローバルなデッドロックとは、複数のコンピュータシステム（ノード）で実行されている複数のプログラム（タスク）が互いに相手の待ち状態解除を待ち合い、待ち状態から抜け出せない状況をいう。また、ローカルなデッドロック状態とは、単一のコンピュータシステムで実行されている複数のタスクが互いに相手の待ち状態解除を待ち合い、待ち状態から抜け出せない状況をいう。
従来、グローバルなデッドロックの検出方法としては、次の三つの方法が知られている。
（ｉ）分散型…各コンピュータシステムのローカルなデッドロック検出情報を用いてグローバルなデッドロックを検出する方法。
（ｉｉ）複製型…各コンピュータシステムが同一のデッドロック検出情報を持ち、それぞれが、グローバルなデッドロックを検出する方法。
（ｉｉｉ）  集中型…複数のコンピュータシステムの中の一つがデッドロックの発生を検出する方法。
【０００３】
【発明が解決しようとする課題】
オーバーヘッドの減少およびデッドロック検出情報の情報量の観点からは分散型が最良の検出方法である。しかし、分散型では、複数のコンピュータシステムのデッドロック検出情報の一貫性を保つことが難しく、デッドロックの発生を正確に検出する事が難しい。
【０００４】
また、異なる機種のコンピュータシステムが接続されて構成されるネットワークシステムが存在する。この種のネットワークシステムにおいては、各コンピュータシステムは他のコンピュータシステムに要求を行ってから応答が返送されるまでの時間を監視している。そして、各コンピュータシステムは相手コンピュータシステムからの応答が所定の時間内に無かった場合にデッドロックが発生したと判定している。このデッドロック検出方法はその検出確度が環視時間の長さによって大きく異なるという欠点がある。
【０００５】
この発明は上記事情に鑑みてなされたもので、グローバルなデッドロックを正確に検出し、必要に応じて、グローバルなデッドロックを解消することができるコンピュータネットワークシステムを提供することを目的とする。
【０００６】
【課題を解決するための手段】
本発明は、ノードが結合されて構成されるコンピュータネットワークシステムにおいて、各前記ノードは、両端が他ノードとの接点を有する準閉パスが自ノード内に形成されているか否かを検出する準閉パス検出手段と、前記準閉パス検出手段により準閉パスの形成が検出されていた際、前記準閉パスの一端側に位置する他ノードに準閉パスの有無のチェックを依頼するチェック依頼手段と、他ノードから受信したチェック依頼に応答し、受信したチェック依頼が自ノードが発行したチェック依頼が回帰したものであるか否かを判断し、自ノードが発行したチェック依頼が回帰した場合にグローバルなデッドロックが発生したことを判断する回帰判断手段とを具備することを特徴とする。
【００１２】
【作用】
あるノードで準閉パスが形成された時には、他のノードにそのノード内における準閉パス形成の有無のチェックの依頼が発行される。グローバルなデッドロックが発生していれば、チェック依頼を受け取ったノード内でも準閉パスが形成されている。従って、さらに他のノードにチェック依頼が転送される。このようにして、ウエイトパスを辿ると、グローバルなデッドロックが発生している場合には、最初にチェック依頼を発行したノードにそのノードが発行したチェック依頼が回帰する。これにより、グローバルなデッドロックを検出することができる。
【００１６】
【実施例】
以下、図面を参照して、この発明の実施例を説明する。
【００１７】
図１はこの発明の第１実施例に係わるコンピュータネットワークシステムの一例としてバス型のＬＡＮを示す。ただし、本発明はバス型ＬＡＮに限定されず、リング型、スター型等の種々のネットワークシステムに応用可能である。図１において、各データ処理ノードは回線１０を介して他の複数のデータ処理ノードと有機的に結合されている。図１において、各データ処理ノードはコンピュータシステム、ワークステーション、パーソナルコンピュータ等から構成される。また、回線１０には、コンピュータシステムにより利用されるＲＡＭ、ＲＯＭ、ハードディスク装置等の共用メモリ等も接続されている。
図２は図１に示されるネットワークから２つのノードを取り出して示す。
【００１８】
図２において、１１及び１２はネットワークシステムのデータ処理ノードとして機能するコンピュータシステムである。なお、図２においては、物理的な接続線はオミットされており、モジュール間を接続する矢印は後述するウエイトパスＰ、通知Ｇ等を示している。
【００１９】
１１ａ，１１ｂ，１１ｃは、それぞれプログラム（又はタスク）Ｃ１，Ｃ２，Ｃ３を実行するプログラム実行モジュール（以下、モジュールと呼ぶ）である。モジュール１１ａ，１１ｂ，１１ｃは、それぞれ、リソースの利用権を排他的に獲得すると共に、その利用権を獲得した状態で他のリソースの利用権の要求を出力する。リソースとしては、通常知られているように、メモリ、ファイル等がある。
【００２０】
ウエイトパスＰはプログラム間のウエイト状態を模式的に表わす。ウエイトパスＰはノード１１に設定される管理テーブル（図３参照）のデッドロック検出情報によって得られる。図２、図３においては、モジュール１１ａ（より正確には、モジュール１１ａによって実行されたプログラムＣ１、以下同様）が占有しているリソースに対してモジュール１１ｂが待機状態にある。また、モジュール１１ｂが占有しているリソースに対してモジュール１１ｃが待機状態にある。
【００２１】
ウエイトパス管理部（以下、管理部）１１１は、例えば、オペレーテングシステム（ＯＳ）又はハードウエアから構成され、ノード１１内の複数のモジュール間のウエイト関係を図３を参照して後述する管理テーブルを参照して認識する。図２、３の例では、管理部１１１は、モジュール１１ａ，１１ｂ，１１ｃ間のウエイト関係を認識する。
【００２２】
管理部１１１は、ノード１１に準閉パスが形成されたことを図４を参照して後述する外部パスカウンタテーブルを用いて検出する。ここで、準閉パスとは、両端が他ノードからのウエイトパス又は他ノードのウエイトパスを有するウエイトパスのシーケンスを意味する。最もシンプルな例では、準閉パスは、一端が他ノードからのウエイトパスに始まり他ノードへのウエイトパスで終了するウエイトパスのシーケンスを意味する。例えば、図２のノード１１では、他ノード１２からの要求がモジュール１１ｃに入り、ウエイトパスのシーケンスがモジュール１１ｃ−１１ｂ−１１ａの間に形成され、さらに、モジュール１１ａから他ノード１２へ要求が出力されている。従って、図２のノード１１では、準閉パスが形成されている。さらに、管理部１１１は、他ノード（例えば、順方向の他ノード）へウエイトパス形成のチェックを依頼する。また、管理部１１１は、他ノードからのウエイトパスのチェックの依頼を受けて、受信した依頼が自己が先に出力した依頼が回帰したものであるか否かをチェックする。管理部１１１は、受信した依頼が自己が先に出力した依頼が回帰したものでない場合には、準閉パスが形成されているか否かを認識する。また、管理部１１１はチェック結果に応じて、その依頼を他ノードへ転送する。
【００２３】
通知Ｇは、新たにウエイトパスを形成するモジュールが自己がウエイト状態に入ることを管理部１１１に通知するために発行される。図２では、１１ｃ→１１ｂというウエイトパスを形成するモジュール１１ｂが、ウエイト状態に入る際に管理部１１１に通知Ｇを発行している。
【００２４】
ノード１２もノード１１と同様の構成である。ノード１２において、符号１２ａはプログラムＣ４を実行するモジュール、１２ｂはプログラムＣ５を実行するモジュールを示す。また、符号１２１は管理部であり、ノード１１の管理部１１１と同様の動作を行う。
図２においては、モジュール１１ａ−１１ｃ、１２ａ，１２ｂのみが説明のために示されているが、他のモジュールも当然存在する。
【００２５】
図２の構成においては、要求を出力しているモジュール１１ａに対しモジュール１２ａはサーバプログラムとして機能し、また、要求を出力しているモジュール１２ｂに対しモジュール１１ｃはサーバプログラムとして機能する。なお、要求を出力しているプログラム及びサーバプログラムを合わせて他ノードに接続されたプログラムと呼ぶ。
【００２６】
図３は、プログラム（又はモジュール、タスク）間のウエイト関係を管理する管理テーブルの一例を示す。管理テーブルは各ノードの管理部に保持される。図３は、リソースＲ１をモジュール１１ａが占有し、モジュール１１ｂがリソースＲ１の空きを待ち、リソースＲ２をモジュール１１ｂが占有し、モジュール１１ｃがリソースＲ２の空きを待機し、リソースＲ３をモジュール１１ｃが占有している状態を例示する。
【００２７】
図４は、準閉パスが形成されているか否かを管理するための外部パスカウンタの一例を示す。前述のように、準閉パスとは両端が他ノードに接続された連続したウエイトパスを意味する。外部パスカウンタは各ノードの管理部に、モジュールと一対一に設けられる。初期状態では、各外部パスカウンタに初期値“０”が設定される。他ノードと接点を持つプログラムが実行されると、対応する外部パスカウンタに所定に値（ここでは“１”）が設定される。さらに、あるプログラムが他のプログラムをウエイトする時に、ウエイトすべきプログラムの外部パスカウンタの値がウエイト原因となるプログラムの外部パスカウンタの値に加算される。
ノード１１の外部パスカウンタの動作について、図５から図８を参照して単純化して説明する。
【００２８】
図５に示されるように、他ノードへアクセスを行うプログラムＣ１あるいは他ノードのためのサーバプログラムＣ３が実行されると、管理部１１１は図６に示されるように対応する外部パスカウンタに所定の値“１”を設定する。さらに、図７に示されるように、プログラムＣ３がプログラムＣ２にウエイトする時に、管理部１１１はプログラムＣ３の外部パスカウンタの値１をウエイト原因となるプログラムＣ２の外部パスカウンタ値“０”に加算し、“１”を設定する。最後に、図２に示されるようにプログラムＣ２がプログラムＣ１にウエイトする時、管理部１１１はプログラムＣ２の外部パスカウンタ値“１”をウエイト原因となるプログラムＣ１の外部パスカウンタ値“１”に加算し、図４に示されるように“２”とする。リソースを占有しているプログラムの外部パスカウンタがゼロ以外の値の場合、ウエイトパスツリー（処理対象としているプログラムを頂点とするウエイトパス群）の少なくとも１つの終端のプログラムの中に他ノードと接続されたプログラムが存在する。
【００２９】
一方、ウエイトパスの他端が他ノードに接続されているか否かは、現在処理対象となっているプログラムが参加するウエイトパスの順方向の終端が他ノードに接続されているか否かによって認識できる。
次に、図９図乃至図１４を参照して、図２のコンピュータネットワークシステムにおけるグローバルなデッドロックを検出する動作を説明する。
まず、図９のフローチャートを参照して、グローバルなデッドロック検出の要求動作を説明する。
【００３０】
グローバルなデッドロックは、処理対象のプログラムが形成しようとする連続するウエイトパスの両端が他ノードからのアローと他ノードへのアローを持つという条件が成立した場合に発生する。
そこで、始めに、その条件が発生しているかについて調べる。
【００３１】
まず、管理部は処理中のプログラムがリソース確保のためにウエイト状態に入るか否かを管理テーブルの情報から判断する（ステップＡ１）。例えば、処理中のプログラムＣ２がリソースＲ１を確保必要があり、プログラムＣ１がリソースＲ１にロックしている場合には、プログラムＣ２がウエイト状態に入ることが判別できる。
【００３２】
処理中のプログラムがウエイト状態に入る場合には、それによってノード内にローカルなデッドロックが発生するか否かが判断される（ステップＡ２）。ローカルなデッドロックが発生する場合、グローバルなデッドロック生成の有無を検出するまでもなく、このローカルなデッドロックを解消する必要がある。そこで、ロッカルなデッドロックが発生する場合には、以下の処理は行わない。一方、ローカルなデッドロックが発生しない場合には、グローバルなデッドロックが発生するか否かを検出するため、フローはステップＡ３に進む。図２の例では、ローカルなデッドロックは発生しない。従って、フローはステップＡ３に進む。
【００３３】
ステップＡ３，Ａ４では、処理対象のプログラムが形成するウエイトパスの両端が他ノードからのアロー又は他ノードへのアローを持つか否かが検出される。この検出のため、ステップＡ３で、管理部は処理対象のプログラムがサーバプログラムまたは外部ノードをアクセス中のプログラムをウエイトさせるか否かを判断する。処理中のプログラムがサーバ又は外部ノードをアクセス中のプログラムをウエイトさせるか否かの判断は、処理中のプログラムの外部パスカウンタの値がゼロか否かを検出することにより行うことができる。図４においては、処理中のプログラムＣ２の外部パスカウンタが“１”である。よって、図２のプログラムＣ２がサーバまたはクライアントをウエイトさせることがわかる。
【００３４】
処理中のプログラムがサーバ又はクライアントプログラムをウエイトさせると判断された場合、フローはステップＡ４に進む。ステップＡ４で、処理対象のプログラムが形成するウエイトパスの他端が他ノードへの又は他ノードからのアローを持つか否かが検出される。具体的には、処理対象のプログラムが加わるウエイトパスの順方向の終端がサーバプログラムまたは外部へアクセス中のプログラムであるか否かが管理部１１１により判断される。図２の例では、ウエイトパスの順方向の終端は外部へアクセス中のプログラムＣ１である。従って、処理対象のプログラムＣ２が形成しようとするウエイトパスが他ノードへのアローを持つと判断される。
【００３５】
このように、処理対象のプログラムが形成しようとするウエイトパスの両終端が他ノードと接続されることが検出された場合には、処理対象のプログラムがウエイトパスに加えられて待機状態に設定される（ステップＡ５）。その後、処理対象プログラムの処理が終了し、プログラムから管理部１１１にウエイト状態に入る旨を示す通知Ｇが送られると、グローバルなデッドロックの検出処理の開始が指示される（ステップＡ６）。図２では、プログラムＣ２がウエイト状態に入ると、プログラムＣ２から管理部１１１に通知Ｇが送られ、グローバルなデッドロックの検出処理の開始が指示される。通知Ｇに応答して、管理部は、準閉パスの終端プログラムのグローバルな識別番号と、終端プログラムのアクセス実行内容を示すアクセスシーケンス番号と、最後に準閉パスに加わったプログラムのローカルな識別番号を保持する。プログラムのローカルな識別番号は、最終的にグローバルなデッドロックを検出した時に、強制的にウエイト状態を解除するプログラムを決定するために使用される。通知Ｇを受けとった管理部は、最後に準閉パスに加わったプログラムをキーとして、通知Ｇが発行された時と準閉パスの状態が変っているか否かをチェックする。状態が変わっている場合には、処理を中断する。チェックの内容としては、準閉パスに最後に加わったプログラム及び順方向の終端プログラムの状態が変化したかどうかをチェックする。状態の変化を判定するための情報は通知Ｇに含まれている。プログラムの状態に変化がない場合、管理部は終端プログラムのグローバルな識別番号とアクセスシーケンス番号とウエイトパスの追跡を他ノードに依頼するためのチェック依頼を、終端プログラムがアローで接続された他ノードの管理部に送る。
【００３６】
図２の例では、通知Ｇに応答して、管理部１１１は、準閉パスの終端プログラムＣ１のグローバルな識別番号と、アクセス実行内容を示すアクセスシーケンス番号と、プログラムＣ２のローカルな識別番号を保持する。また、管理部１１１は終端プログラムＣ１のグローバルな識別番号とアクセスシーケンス番号と、チェック依頼をノード１２の管理部１２１に送る。
【００３７】
このチェック依頼に応答して、チェック依頼を受けたノードでは、グローバルなデッドロックが発生しているか否かのチェックを開始する。そこで、次に、図１０のフローチャートを参照して、依頼を受けたノード（図２では１２）で行われる追跡処理を説明する。
【００３８】
単一のノード内のウエイトパスはそのノード独自に安定して調べる事ができる。しかし、複数のノードにまたがったウエイトパスは１つのノードが独自に調べることはできない。そこで、複数のノードが共同してウエイトパスを追跡する必要がある。この際、あるノードが他のノードに追跡処理を依頼してから、前記あるノード内のウエイトパスの状態が変化し、例えば、準閉パスが消滅するようなこともありうる。このような場合には、他のノードで追跡処理を行っても無意味である。従って、複数のノード間でデッドロック状態の認識の一貫性を確保する必要がある。このため、本実施例では、ウエイトパスを形成するあるプログラムの状態が変化しなければ、そのウエイトパス内のそれより下位のプログラムの状態はウエイトのままであるという原理を用いる。換言すると、サーバプログラムの状態が、追跡処理の依頼が発行された時の状態から変っていないことを保証する事により、前ノードでのウエイトパスは変移していないという事を保証できる。この保証を行うための元となる情報が、前ノードから送信されるチェック依頼に付加された「終端プログラムのグローバルな識別番号」と「アクセスシーケンス番号」である。
【００３９】
グローバルな識別番号とは、各プログラムがジョブとして活性化された時点でネットワーク上で固有となるようにそのプログラムに割り当てられる識別子である。クライアントとサーバの関係にあるプログラム同士には同一の識別子が割り当てられる。このグローバルな識別番号により、依頼を受けたノードでのウエイトパスのスタートが認識できる。つまり、他のノードにチェック依頼が届く前に接点プログラムが消滅してしまうような場合を検出できる。
【００４０】
一方、終端プログラムのアクセスシーケンス番号は、クライアント側からサーバ側に要求を送出する度に、ネットワーク内で固有となるように割り当てられる実行状態の識別子である。
【００４１】
次に、図１０のフローチャートを参照する。まず、接点プログラムが存在するか否かが判別される。即ち、チェック依頼に付与されたグローバルな識別番号と同一の識別番号を有する接点プログラムが存在するか否かがチェックされる。チェック依頼の発行・受信・処理等の間に接点プログラムが消滅した場合等には、このステップでチェックされる。
【００４２】
次に、ステップＡ１２でチェック依頼発行時のサーバプログラムのアクセスの状態が変化していないことが、サーバとクライアントのアクセスシーケンス番号を比較することにより確認される。例えば、チェック依頼の発行・受信・処理等の間にサーバプログラムがチェック依頼発行時の処理を終了し、例えば、サーバとクライアントが同一のグローバルな識別番号を有しながら、サーバの処理がすでに次の要求に対する処理のためにウエイト状態にある場合等には、このステップでそのことが判別される。
【００４３】
次に、ステップＡ１３で、接点プログラムがウエイト状態か否かが判別される。接点プログラム（上位プログラム）がウエイト状態から動作中となった場合等はこのステップで識別される。
【００４４】
ステップＡ１１〜Ａ１３ですべてＹＥＳとなると、下位のウエイトパスに対して状態の変移が発生していない事が保証される。即ち、ウエイトパスが有効であること、つまりノード１１と１２のウエイト状態の一貫性が保証される（ステップＡ１４）。これにより、フローは図１１の処理に進む。一方、ステップＡ１１〜Ａ１３のいずれかでＮＯとなった場合には、ウエイトパスが無効と判断され（ステップＡ１５）、そこで処理が中断される。図２の例では、サーバプログラムＣ４とクライアントプログラムＣ１のグローバルな識別番号が一致し、サーバプログラムＣ４とクライアントプログラムＣ１のアクセスシーケンス番号が一致し、接点プログラムＣ４がウエイト状態であるので、ステップＡ１１−Ａ１３ですべてＹＥＳとなり、ウエイトパスが有効と判断される。
【００４５】
図１０の処理により、ウエイト状態の一貫性が確認された後、フローは図１１のステップＡ２１に進む。ステップＡ２１で、チェック依頼を受けたノードの管理部は、ウエイトパスを辿り、終端プログラムを特定する。
【００４６】
検出された終端プログラムがウエイト状態か否かがチェックされる（ステップＳ２２）。終端プログラムがウエイト状態の場合、その終端プログラムが他ノードにアクセス中のプログラム又はサーバプログラムであるか否かが判断される（ステップＡ２３）。終端プログラムがウエイト状態で、且つ、サーバ又はクライアントの場合、フローはステップＡ２４に進む。一方、それ以外の場合には、処理は終了する。
【００４７】
ステップＡ２４で、管理部は、終端プログラムのクローバルな識別番号、アクセスシーケンス番号と共にチェック依頼を次のノードに発行する。このチェック依頼には、さらに、チェック依頼の最初の発行元であるノードからの情報も付与される。
【００４８】
図２では、管理部１２１はウエイト状態で他のノード１１にアクセス中の終端プログラムＣ５が存在する。従って、管理部１２１はチェック依頼を次ノード１１に発行する。このチェック依頼には、終端プログラムＣ５のグローバルな識別番号、アクセスシーケンス番号、チェック依頼の最初の発行元であるノード１１からの情報（プログラムＣ１のグローバルな識別番号、アクセスシーケンス番号、最後にウエイトパスに加わったプログラムＣ２のローカルな識別番号）が付与されている。
次に、図１２を参照して、ノード１１で実行されるチェック依頼の回帰検出処理を説明する。
ノードを順次巡って行くウエイトパスの追跡チェック依頼は、再び発行ノードに戻って来る場合がある。これには次の二つの場合が考えられる。
（ｉ）ウエイトパスの通過点でチェック依頼を発行した発行ノードに戻って来る場合。
（ｉｉ）自分が最初に発行したウエイトパスが終端である自分に戻って来た場合。
【００４９】
二つの内のいずれかであるかは、チェック依頼と一緒に転送されるチェック依頼発行元ノードの終端プログラム識別番号とそのアクセスシーケンス番号を、チェック依頼を受け取ったノードが自ノードのそれらと比較することによって判別できる。比較結果が一致した場合、ウエイト管理部は、ウエイトパスがループしていると認識し、グローバルなデッドロックが発生していることを検出する。
【００５０】
図１２を参照して具体的に説明する。まず、図１０に示した一貫性保障のための処理と同様の手順でウエイトパスの有効性が判断される（ステップＡ３１）。その後、ノードに準閉パスが残っているか否かを調査するための処理（ステップＡ３２〜Ａ３４）が実行される。その後、自ノードが最初に発行したチェック依頼が回帰されたか否かの検出処理（ステップＡ３５，Ａ３６）が行われる。
【００５１】
この回帰検出処理では、チェック依頼と一緒に転送されたチェック依頼発行元ノードの終端プログラムの識別番号とそのアクセスシーケンス番号が、チェック依頼発行時に保持されていた終端プログラムの識別番号とアクセスシーケンス番号が比較される。一致が検出された場合には、グローバルなデッドロックが発生したために、自ノードが発行したチェック依頼が回帰したものである。このため、フローはステップＡ３７に進み、ノードの管理部は、そのノードの準閉パスに最後に加わったプログラムをいわゆる“いけにえプログラム”としてそのウエイト状態を強制的に解除する。その後、いけにえプログラムにはデッドロックステータスが返却される。
【００５２】
一方、自ノードが発行したチェック依頼が回帰したものでない場合は、ウエイトパスの通過点でチェック依頼を発行したノードにチェック依頼がかえってきた場合である。従って、図１１のステップＡ２４と同一のステップＡ３８を実行し、次のノードにチェック依頼を転送する。
【００５３】
図２の例では、チェック依頼発行ノード１１にチェック依頼が再び送られて来た場合、ウエイトパスは有効であり、ノード１１に準閉パスが残っている。このため、ステップＡ３５，Ａ３６の処理が行われる。この処理では、チェック依頼と一緒にノード１２から転送されたチェック依頼発行元ノードの終端プログラムＣ１の識別番号とアクセスシーケンス番号が、チェック依頼発行時に保持されていた終端プログラムＣ１の識別番号とそのアクセスシーケンス番号とが比較され、一致が検出され、グローバルなデッドロックが発生していることが検出される。この場合、管理部１１１はプログラムＣ２が占有しているリソースＲ２の占有状態を解除し、プログラムＣ２にデッドロックステータスを返却する。
【００５４】
以上のように、この発明の第１実施例においては、他ノードに接点を持つプログラム（モジュール／タスク／ジョブ）から他ノードに接点を持つプログラム（モジュール／タスク／ジョブ）へと続く準閉パスが形成された時には、他ノードに対し準閉パス形成の有無のチェック依頼が発行される。このため、グローバルなデッドロックが発生していれば、最終的に、最初にチェック依頼を発行したノードにそのチェック依頼が回帰する。これにより、グローバルなデッドロックを検出することがある。
【００５５】
また、チェック依頼に応答して実行される準閉パス形成のチェック動作は、チェック依頼発行側の準閉パスの状態が遷移してないことを保証した状態で実行される。従って、ノード間のデッドロック情報の一貫性を保った状態でグローバルなデッドロックを正確に検出できる。
【００５６】
次に、図１３を参照して、この発明の第２実施例に係わるコンピュータネットワークシステムを説明する。図１３はコンピュータネットワークシステム内の一ノードを構成するコンピュータシステム２１を示す。
【００５７】
ノード２１は、例えば、図１に示されるように、ネットワークを介して異機種ノードと接続されている。ノード２１において、２１ａ，２１ｂ，２１ｃは、それぞれプログラムＣ１１，Ｃ１２，Ｃ１３を実行するモジュールであり、これらモジュール２１ａ，２１ｂ，２１ｃは、それぞれリソース（資源）の利用権を排他制御の下で獲得すると共に、獲得した状態で他のリソースへの要求を出す。
【００５８】
ウエイト（待機）パスＰは、このノード２１に設定される図３と同様のウエイト管理テーブルのデッドロック検出情報によって得られるプログラム間のウエイト状態を表わす。図１３においては、モジュール２１ａが占有しているリソースに対してモジュール２１ｂが待機状態にあり、また、モジュール２１ｂが占有しているリソースに対してモジュール２１ｃが待機状態にある場合が示されている。
【００５９】
ウエイトパス管理部２１１は、モジュール２１ａ，２１ｂ，２１ｃ間のウエイト状態を前述の管理テーブルから認識すると共に、ノード２１で準閉パスが形成されたことを図４と同様の外部パスカウンタテーブルを用いて検出する。また、管理部２１１の動作は、時間環視機構２１２の時間環視と連動制御される。
【００６０】
通知Ｇは、符号Ｐのウエイトパスに最後に加わるモジュール（ここでは、モジュール２１ｂ）から管理部２１１に発行されるもので、ウエイト状態に入ることを通知する。
時間環視機構２１２は、ノード２１が他のノードにアクセス要求を行ってからその要求に対する応答が返送されるまでの時間を監視する。
次に、図１４のフローチャートを参照して、図１３に示されるシステムのグローバルなデッドロックの検出動作を説明する。
異機種ノードが接続されるコンピュータネットワークシステムにおいては、デッドロックの発生パターンが２つ考えられる。
【００６１】
その第１は、他ノードへのデータアクセスがウエイトした事により発生するデッドロック（擬似デッドロック）であり、その第２は、他ノードのリソースをロックした状態での自ノード内のローカルなウエイトによって結果的にグローバルなデッドロックが発生する場合である。
以下、第１のデッドロックの検出について説明する。
【００６２】
まず、従来と同様に、他ノードにデータアクセスを行うための要求を送出し、その要求に対する応答がある決められた時間内に完了しない場合には強制的に完了通知を発行するモードが設定される。これにより、他ノードへのデータアクセスは取下げられる。これにより相手ノードからの応答が無いという事によるロック状態は解除できる（ただし、この段階では、リソースは開放しない）。さらに、この実施例では、この強制解除が発生した時点で、強制解除が施されたプログラムを頂点とするウエイトパス群のスタート点に、サーバプログラムまたは他ノードへアクセスを行ったプログラムが存在するか否かがチェックされる。スタート点に条件にかなうプログラムが存在する場合、即ち、準閉パスが形成されている場合には、このノードが他ノードのプログラムを待たせ、かつ自分も他ノードのリソースによってウエイトしているという判定が可能である。換言すると、そのノードがグローバルなデッドロックの一部を担っている、という判定が可能である。
上記の判定プロセスを、図１４のフローチャートを参照して具体的に説明する。
【００６３】
まず、時間環視機構２１２がアクセス要求発生からその要求に対する応答が返送されるまでの時間環視を行う（ステップＡ４１）。所定の環視時間内に応答が返送されなかった場合、時間環視機構２１２は管理部２１１に例えば割り込み信号を出力する。この信号に応答して、管理部２１１はノード２１内に準閉パスが形成されているか否かをチェックする。このチェックは、強制解除が施されたプログラム（ここでは、プログラムＣ１１）の外部パスカウンタをチェックして行う（ステップＡ４２，Ａ４３）。より具体的に説明すると、第１実施例において説明したように、外部パスカウンタは、各モジュールと一対一に対応する。そして、他ノードと接点を持つプログラムに対して値“１”が設定され、ウエイトしようとするプログラムの外部パスカウンタの値が、ウエイト原因となるプログラムの外部パスカウンタの値に加算される。従って、強制解除が施されたプログラムの外部パスカウンタの値が“１”のままである場合には、準閉パスが形成されてない。即ち、グローバルなデッドロックは発生していない。これに対し、強制解除が施されたプログラムの外部パスカウンタの値が“１”以上の値の場合には、準閉パスが形成されており、グローバルなデッドロックが発生している可能性がある。
【００６４】
従って、強制解除が施されたプログラムＣ１１の外部パスカウンタの値が初期値つまり“１”のままである場合には、管理部２１１がモジュール２１ａを制御し、受信要求を再送させる（ステップＡ４４）。
【００６５】
一方、強制解除が施されたプログラムＣ１１の外部パスカウンタの値が初期値以外の場合には、デッドロック状態の解消処理を実行する（ステップＡ４５）。この解消処理で、強制解除が施されたプログラムがロックしていたリソースを強制的にすべて解放する（ステップＡ４５）。
【００６６】
次に、第２のデッドロック、即ち、他ノードのリソースをロックした状態での自ノード内のローカルなウエイトによって結果的に発生するデッドロックの検出について、図１５を参照して説明する。
【００６７】
例えば、プログラムＣ１２がプログラムＣ１３に対してウエイトしなければならないと認識した時、プログラムＣ１２は対応する外部パスカウンタをチェックする。プログラムＣ１１がプログラムＣ１２に対してウエイトしている場合には、プログラムＣ１２の外部パスカウンタはゼロ以外なので、プログラムＣ１２は外部との接点プログラムをウエイトさせているということを認識できる（第１のウエイトパスとは逆の方向になる）。
【００６８】
その後ウエイトパスを辿って行くとウエイトパスの終端のプログラムＣ１３に行き着く。プログラムＣ１３の外部パスカウンタがゼロ以外なので（サーバプログラムのため）、外部への接点のプログラムに達したという事が判別できる。即ち、準閉パスが形成されていることが確認できる。
【００６９】
この状態でプログラムＣ１２がウエイトすると、ネットワークにまたがったデッドロックが成立する可能性がある（Ｃ１１が他ノードへリソースをロックしたままＣ１２のためにウエイトした場合）。そこでプログラムＣ１２がウエイトする前に、プログラムＣ１２はプログラムＣ１３およびＣ１２に関する情報を添付し、ウエイト状態に入ることを管理部２１１に通知する。
【００７０】
この通知によって管理部２１１はレディ状態となり、プログラムＣ１３およびＣ１２に関する情報を保持した状態で一定時間のウエイト状態に入る（ステップＡ５１）。
【００７１】
そして、ウエイトに入ってから所定時間経過したことが、例えば時間環視機構２１２によって検出された時点で、管理部２１１はウエイト状態から復帰する（ステップＡ５２）。ウエイト状態から復帰した管理部２１１は、最後にウエイトパスに加わったプログラムＣ１２とウエイトパスの終端プログラムＣ１３の現在の状態（ウエイト中か否か、アクセスシーケンス番号等）を認識する（ステップＡ５３）。認識した状態とプログラムＣ１２からの通知によって受け取った以前の状態が比較され、プログラムＣ１２とプログラムＣ１３の各々の状態が変化したか否かを判断する（ステップＡ５４）。状態が変化していない場合には、グローバルなデッドロックが発生した事を認識して、デッドロック解消処理を実行する（ステップＡ５５）。この解消処理で、ウエイトパスを破るため、いけにえ処理として、最後にウエイトパスに加わったプログラムＣ１２の待機状態を強制的に解除し、そのプログラムにデッドロックステータスを返却する。一方、状態が変化している場合には、処理を終了する。
【００７２】
第２実施例においては、従来の時間環視のみによるデッドロック状態の判定に、自ノード内のデッドロック状態検出の調査を加味している。従って、異機種ノードと接続されるネットワークにおけるグローバルなデッドロック検出を安定した精度で行うことが可能となる。
【００７３】
【発明の効果】
以上説明したように、この発明によれば、グローバルなデッドロックを正確にしかも安定した精度で検出することができる。
【図面の簡単な説明】
【図１】この発明の第１実施例に係わるコンピュータネットワークシステムを示すブロック図、
【図２】この発明の第１実施例に係わるコンピュータネットワークシステムを示すブロック図、
【図３】図１に示したコンピュータネットワークシステムに設けられる管理テーブルの一例を示す図、
【図４】図１に示したコンピュータネットワークシステムに設けられる外部パスカウンタテーブルの一例を示す図、
【図５】ウエイトパスが形成される過程を示す図、
【図６】図５に示される状態での外部パスカウンタの保持値を示すテーブル、
【図７】ウエイトパスが形成される過程を示す図、
【図８】図７に示される状態での外部パスカウンタの保持値を示すテーブル、
【図９】図１図に示したコンピュータネットワークシステムのデッドロック検出動作の前処理を説明するフローチャート、
【図１０】チェック依頼を受けたノードにおいて、ウエイトパスが有効否かを判別する動作を説明するフローチャート、
【図１１】ウエイトパスが有効であると判別された場合に、準閉パスが形成されているか否かを判別するための動作を説明するフローチャート、
【図１２】チェック依頼を発行したノードに、チェック依頼が回帰した場合に、そのノードで実行される処理を説明するフローチャート、
【図１３】この発明の第２実施例に係わるコンピュータネットワークシステムを示すブロック図、
【図１４】図１３に示したコンピュータネットワークシステムのデッドロック検出動作を説明するフローチャートである。
【図１５】図１３に示したコンピュータネットワークシステムのデッドロック検出動作を説明するフローチャートである。
【符号の説明】
１１，１２、２１…ノード、１１ａ，１１ｂ，１１ｃ，１２ａ，１２ｂ，２１ａ，２１ｂ，２１ｃ…モジュール、１１１、１２１，２１１…ウエイトパス管理部，２１２…時間監視機構。
【図１】
0003578408.tif 000002
【図２】
0003578408.tif 000003
【図３】
0003578408.tif 000004
【図４】
0003578408.tif 000005
【図５】
0003578408.tif 000006
【図６】
0003578408.tif 000007
【図７】
0003578408.tif 000008
【図８】
0003578408.tif 000009
【図９】
0003578408.tif 000010
【図１０】
0003578408.tif 000011
【図１１】
0003578408.tif 000012
【図１２】
0003578408.tif 000013
【図１３】
0003578408.tif 000014
【図１４】
0003578408.tif 000015
【図１５】
0003578408.tif 000016