JPH0690703B2

JPH0690703B2 - グロ−バルデツドロツク検出方式

Info

Publication number: JPH0690703B2
Application number: JP60092482A
Authority: JP
Inventors: 理一郎武; 進安達; 康男山根
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1985-04-30
Filing date: 1985-04-30
Publication date: 1994-11-14
Anticipated expiration: 2009-11-14
Also published as: JPS61250767A

Description

【発明の詳細な説明】〔目次〕概要産業上の利用分野従来の技術と発明が解決しようとする問題点問題点を解決するための手段作用実施例ロック管理機構（第１図）待合せ通知部（第１図、第２図）待合せ問合せ部（第１図）デッドロック検出処理例（第３図、第４図）発明の効果〔概要〕複数のサイトからなる計算機ネットワークで実行される
トランザクションによって、サイト間にまたがって発生
する、いわゆるグローバルデッドロックを検出する方式
である。トランザクション間の待合せ情報を、トランザ
クション識別子の関数として定まるサイトへ集め、又同
様に定まるサイトへの問合せにより情報を補充して、グ
ローバルデッドロックの存在を検出する。

〔産業上の利用分野〕

本発明は、情報処理システムにおける、複数のサイトか
らなる計算機ネットワークの、複数のサイトで実行され
るトラザクションによって、サイト間にまたがって発生
する。いわゆるグローバルデッドロックを検出する方式
に関する。

計算機システムの複数の共用資源を、複数のトランザク
ションが排他的に占有して使用する場合には、例えばト
ランザクション間で、他のトランザクションが占有して
いる資源の空くのを互いに待ち合うために、それらのト
ランザクションの処理が進まなくなる、いわゆるデッド
ロックの状態が生じ得ることは、よく知られている。

公知のように、デッドロックが発生した場合には、原因
の複数トランザクションのうちの、少なくとも１トラン
ザクションの実行を中断しない限り、原因の全トランザ
クションが、処理の進まない状態に凍結される。

通信回線で相互に結ばれた複数のサイトに、例えばデー
タベースを分散した。計算機ネットワーク等において
は、１つのトランザクションで、複数のサイトのデータ
ベースのデータを排他的にアクセスする必要がある場合
がある。

このようなトランザクションが複数存在して、各サイト
で並列に実行され、且つ通常行われるように、各トラン
ザクションは所要の全サイトのアクセスが成功したと
き、該全サイトのデータ等の排他的占有を解く方式の場
合には、複数のサイトにまたがったデッドロック、いわ
ゆるグローバルデッドロックが発生し得る。

グローバルデッドロックは、各サイトで発生するトラン
ザクションの待合せ状態を、２以上のサイトについて結
合して見て、初めて検出できるので、効率よく検出する
ためには特別の考慮が必要である。

〔従来の技術と発明が解決しようとする問題点〕

第５図は４サイトからなる計算機ネットワークを示し、
各サイト１、２、３、４には、データベースシステムが
分散して設けられるものとし、サイト間は通信回線５に
よって接続される。

各サイト１〜４においては、例えば利用者の端末装置６
から入力されるコマンドに従って、指定のデータベース
処理をするためのトランザクションを発生する。

トランザクションは一般に、最初に発生される親サブト
ランザクションと、親サブトランザクションによって、
処理の必要に従って発生される１以上の子サブトランザ
クションからなる。なお、子トランザクションが、更に
子トランザクションを発生する方式のシステムもある。

例えばサイト１で発生したトランザクションT₁が、サイ
ト１及びサイト２の両データベースにアクセスする処理
を要する場合には、サイト１にサブトランザクションT₁
が作られると、サブトランザクションT₁はサイト２と通
信して、サイト２に子サブトランザクションT₁′を発生
する。

以下において、データベースへのアクセスは、すべて所
要のデータを排他的に占有して行う必要があるものとす
ると、サブトランザクションT₁及びT₁′は、それぞれの
サイト１及び２のロック管理機構に、所要のデータを排
他的に占有することを要求し、占有ができた場合のみ、
該データへのアクセス処理を開始する。

処理を終わったサブトランザクションT₁、T₁′は、相互
に終了を通知し、両者のアクセスが完了したことによっ
て、ロック管理機構に占有解除を要求する。

前記の占有要求において、他のトランザクションが、既
にそのデータを占有していた場合には、待合せが必要に
なり、前要求の他のトランザクションの処理がすべて終
わった後に、占有が可能になる。

このような制御の下に、上記のようにトランザクション
T₁のサブトランザクションがサイト１と２にあり、トラ
ンザクションT₂のサブトランザクションがサイト２と３
にあり、トランザクションT₃のサブトランザクションが
サイト３と１にあって、各サイトのサブトランザクショ
ンが、同じデータを占有しようとしたために、第６図
（ａ）に示すような待合せ関係が生じたとする。

なお、この説明において、トランザクションTiのサブト
ランザクションは、すべてTiと表すものとする。又、Ti
→Tjにより、サブトランザクションTiが、サブトランザ
クションTjの占有終了を待っている状態を示す。

第６図（ａ）に示すような待合せ関係が生じると、例え
ばトランザクションT₁についてみると、サイト１のT₁が
占有を果たしたとしても、サイト２のT₁の処理終了まで
占有を解除できないという関係が、すべてのトランザク
ションにあり、互いに他のトランザクションの占有解除
を待つので、この状態は変化できない。即ち、グローバ
ルデッドロックが発生している。

このようなグローバルデッドロックの発生は、各サイト
内の待合せ状態を見ただけでは検出できず、この例の場
合は、サイト１〜３の状態を１個所に集めて、第６図
（ｂ）のような待合せ関係グラフを得、そこにループが
あることにより、初めて検出できる。

このために、例えばすべてのサイトの待合せ情報を、特
定の１サイトに転送し、該特定サイトでグローバルデッ
ドロックを検出する、いわゆる集中方式がある。

このような集中方式は、制御構成としては簡明である
が、ネットワーク全体のグローバルデッドロック監視を
行う特定サイトに、特に高い信頼性が要求され、特定サ
イトのダウン時の処理を考慮すると、必ずしも制御は単
純では無く、又特定サイトに多量の待合せ情報の受信及
び処理の負荷が課せられること等から、例えば比較的小
規模のローカルエリアネットワーク等にのみ向く方式で
ある。

そのために、グローバルデッドロックの検出を特定の１
サイトに集中しない、いわゆる分散方式が考えられてい
る。

その１方式として、例えば他サイトに子サブトランザク
ションのあるサブトランザクションを待合せる状態を検
出して、その他サイトへ待合せ情報を転送する操作を繰
り返すことにより、待合せ関係のグラフが逐次成長され
ることにより、トランザクションの発生状態に応じて、
特定されないあるサイトでデッドロックが検出されるよ
うにする方式がある。

しかし、この方式は制御が複雑であり、又サイト間にお
ける、待合せ情報の転送量が多くなる等の問題がある。

〔問題点を解決するための手段〕

第１図は、本発明の構成を示すブロック図であり、10は
他サイト等との通信を制御する通信制御部、11はサブト
ランザクション、12はトランザクション識別子からサイ
トアドレスを発生するサイトアドレス関数部、13は待合
せ関係についての情報を所定のサイトへ送出する待合せ
通知部、14はデッドロック検出部15で構成される待合せ
関係グラフから、所要の待合せ情報の問合せを送出する
待合せ問合せ部である。

〔作用〕

サブトランザクションは、前記のようにロック管理機構
16に、所要のデータ等の共有資源の占有を要求する。

ロック管理機構16は、占有の待合せが生じると、サブト
ランザクション間の待合せ関係を示す情報を待合せ通知
部13に渡す。

待合せ通知部13は、この待合せに関係するサブトランザ
クションのトランザクション識別子をサイトアドレス関
数部12に渡して、サイトアドレスを得、通信制御部10を
経て、そのサイトへ待合せ情報を送信する。

デッドロック検出部15は、他サイト及び自サイトからの
待合せ情報を受信し、それらを結合して、トランザクシ
ョン間のグローバルな待合せ関係グラフを構成する。

待合せ問合せ部14は、構成された待合せ関係グラフ上の
各ノードについて、所定の条件で問合せの要否を判定
し、問合せの必要な場合には、そのトランザクション識
別子をサイトアドレス関数部12に渡して問合せ先サイト
を決定し、問合せを送信する。

問合せは、宛先サイトのデッドロック検出部15が受信
し、指定のトランザクションにつながる待合せ関係の所
定部分の情報を返送する。

要求元のデッドロック検出部15は、これを受信し、先の
待合せ関係グラフを補充する。

要すれば、この補充操作を反復し、グラフ上にループが
構成された場合には、公知の適当な方法により、ループ
上のトランザクションの１つを選択し、そのトランザク
ションの実行を中断して、終了させることにより、グロ
ーバルデッドロックを解消する。

以上の構成の制御により、待合せ情報の通知は、待合せ
の発生ごとに１回、所定のサイト（一般に２サイト）へ
行えばよい。

その後、所要のトランザクションについて、問合せを必
要とする場合が生じるが、上記の通知方式によって、所
要の情報を必ず保持するサイトが定まっているので、無
駄な問合せ、或いは問合せの中継等を生じることが無
い。

従って、グローバルデッドロックの検出を効率よく制御
することが可能になる。

サイトアドレス関数部12の、トランザクション識別子か
らサイトアドレスを決定する関数は、例えばトランザク
ションを発生したサイトのサイトアドレスを関数値とす
ることにより、一般に適切な分散が可能である。

しかし、システムの必要に応じて、例えば、関数値を固
定値とすれば、集中方式となり、トランザクション識別
子の値の適当なハッシュ関数とすれば、複数の特定サイ
トがグローバルデッドロック検出を分担する半集中方式
となる等、融通性の高い運用が可能である。

〔実施例〕

ロック管理機構第１図において、サブトランザクション11は、図示しな
い機構により、前記のようにして、このサイトで発生さ
れたトランザクションの親サブトランザクションか、又
は他サイトで発生されたトランザクションの子サブトラ
ンザクションであるが、何れの場合も、トランザクショ
ンが発生されたサイトで付けられるトランザクション識
別子を持っている。

トランザクション識別子は、この計算機ネットワークの
中で、ユニークにトランザクションを識別できるもので
なければならない。このために、トランザクション識別
子は、例えば各サイトを識別するサイトアドレスと、サ
イトごとに重複無く発生する一連番号とをつないだ構成
をとるものとする。

ロック管理機構16は、サブトランザクション11から、デ
ータベースの指定のデータの占有制御を要求されると、
そのデータが占有されていなければ、これを占有状態に
設定して、サブトランザクション11に占有を通知するの
で、サブトランザクション11は該データのアクセスを開
始する。

しかし、前記要求時、既に他のサブトランザクションに
よって占有されていた場合には、その要求を待ち行列に
接続し、サブトランザクション11を待合せ状態に置く。

この場合にロック管理機構16は、要求サブトランザクシ
ョン11と、サブトランザクション11によって待たれるこ
とになった、待ち行列上の直前につながるサブトランザ
クションとのトランザクション識別子の並びを、待合せ
情報として待合せ通知部13へ通知する。

待合せ通知部待合せ通知部13は、この待合せ情報の両トランザクショ
ン識別子を、サイトアドレス関数部12に渡して、それぞ
れに対応する関数値として、サイトアドレスを得る。

待合せ通知部13は、サイトアドレス関数部12から得たア
ドレスのサイトを宛先として、上記待合せ情報の送信
を、通信制御部10に依頼することにより、待合せ情報を
通知する。

なお、送信先には自サイト宛も含まれてよく、その場合
には、通信制御部10からデッドロック検出部15に待合せ
情報が中断される。

こゝで、サイトアドレス関数部12のアドレス関数値は、
入力されるトランザクション識別子の一部を構成するサ
イトアドレス部分の値を採るものとすれば、上記による
待合せ情報はトランザクションの発生元サイトへ集めら
れることになる。

通常は、トランザクションの発生量を主要データとし
て、各サイトのシステム規模が定められることを考える
と、前記のアドレス関数により、一般に妥当な負荷分担
がなされることになると期待できる。

デッドロック検出部15は、通信制御部10から受信する待
合せ情報を結合して、グローバルな待合せ関係グラフを
得る。即ち、第６図（ａ）のような個々の待合せ情報
を、第６図（ｂ）のように結合して、待合せ関係グラフ
とする。

その結果、待合せ関数T₁→T₂、T₂→T₃、……が、すべて
異なるサイトで発生したとしても、第２図に示すよう
に、デッドロックループ上で、少なくとも１つ置きのト
ランザクションによって定まる通知先サイトが同一の場
合には、そのサイト（図の場合、サイトS₁）に待合せ情
報が集まって、直ちにループを検出することができる。

なお、図において、Ｓ（）によって、サイトアドレス
関数部12の関数を示し、Smはサイトアドレスを示すもの
とする。

待合せ問合せ部しかし、このような特別な条件に無い場合には、一般に
前記の通知によって集まる待合せ情報のみでは、デッド
ロックを検出できない場合があるので、デッドロック検
出部15は、待合せ問合せ部14により、他サイトに問合せ
を出して、待合せ情報を補充する。

こゝで、冗長な問合せを除き、デッドロックの解消処理
の重複を避ける等のために、例えば待合せ関係グラフに
デッドロックループがある場合に、そのループ内のトラ
ンザクションの、トランザクション識別子の、或る重み
関数値が最も大きいトランザクションのサイトが、その
ループを処理するという規約を設けることにする。

このようにすると、あるサイトが、待合せ情報グラフ上
のループの存否を追跡しなければならないのは、待合せ
情報グラフ上で待ち側の端末にある他サイトのトランザ
クションから、待たれ側の端末にある他サイトのトラン
ザクションに至るパスのうち、そのパス上のトランザク
ションの、上記重み関数値が最大のものが、自サイトの
トランザクションであるパス（このパスを該サイトの責
任パスという）のみになる。

従って、待合せ問合せ部14は、この条件に合致する責任
パスの、例えば待たれ側の端末のトランザクションを指
定して、そのトランザクションのトランザクション識別
子のアドレス関数で定まるサイトへ、問合せを送信す
る。

前記の、待合せ情報の通知処理の論理から、指定のトラ
ンザクションに関する待合せが存在している場合には、
この送信先サイトは、必ず指定のトランザクションの待
合せに関する情報を持ち、問合せ元サイトは、有効な待
合せ情報の回答を受信することができる。

問合せ元サイトのデッドロック検出部15は、問合せに対
する応答情報によって、待合せ関係グラフを補充し、こ
のようにして、待合せ関係が続く限り、責任のあるパス
について、待合せ関係グラフの枝を逐次延長し、その結
果、もしもループが存在する場合には、ループを検出す
る。

デッドロック検出処理例以上の処理により、ループを検出する過程を、第３図及
び第４図に示す一例により説明する。

第３、４図において、サイトのアドレスは１〜４（以下
において、他の数字と区別するために、〜で示す）
とし、２桁の数字はトランザクション識別子の値を示
し、その１位桁でサイトアドレスを示している。即ち、
トランザクション識別子ikとしたとき、Ｓ（ik）＝ｋと
する。又、□形内のトランザクション識別子は、それが
示されているサイトのトランザクションを示す。

第３図はトランザクション間の待合せ関係について仮定
した状況を示し、第４図（ａ）、（ｂ）、（ｃ）は、第
３図の待合せ関係がある場合に、何れかのサイトでデッ
ドロックループを検出する処理の過程を示す。

第４図（ａ）、（ｂ）、（ｃ）は、それぞれの処理フェ
ーズ、第１〜第３フェーズの初期における、各サイト内
の待合せ関係グラフと、それ基づいて送受されるメッセ
ージとを示し、第４図（ａ）は待合せ情報を通知する第
１フェーズ、第４図（ｂ）は問合せによって情報を補充
する第２フェーズ、第４図（ｃ）は判定処理の第３フェ
ーズである。

この例において、重み関数は、トランザクション識別子
の値を、そのまゝ関数値として採るものとする。

第１フェーズにおいて、サイトの待合せ通知部13は、
13→32なる待合せ情報を、トランザクション識別子‘1
3'のトランザクションのサイトであるサイト、及びト
ランザクション識別子‘32'のトランザクションのサイ
トへ送信する。同様にして、待合せ情報34→33は、サ
イトとへ、待合せ情報31→12→22の内、31→12の部
分はサイトと、12→22の部分はサイトに送信して
通知する。

こゝで、サイト宛は、自身の待合せ通知部13からデッ
ドロック検出部15への転送であり、図には宛先に括弧を
付して区別してある。

サイト、、も、図の第１フェーズに示すように、
サイトの場合と同様に各サイトへ待合せ情報を通知す
る送信を行う。

その結果、例えばサイトのデッドロック検出部15は、
第１フェーズのメッセージに示すように、自サイトの待
合せ通知部13から待合せ情報31→12、サイトから21→
14→31、41→13及び12→11、サイトから21→41、サイ
トから24→11→21を受信するので、それらを結合し
て、図の（ｂ）第２フェーズのサイトに示す待合せ関
係グラフを得る。

サイトでは、このグラフ上に11→21→14→31→12→11
なるデッドロックループを検出し、且つこのループ上の
最大の重み関数値はトランザクション識別子‘31'であ
り、それは自サイトのトランザクションであることか
ら、このデッドロックを解消するため、トランザクショ
ン識別子‘31'のトランザクションの実行を中断し、各
サイトに通知する。

又、待合せ問合せ部14は、待合せ関係グラフ上に、下記
のパスが残ることを検出する。

（イ） 24→11→21→41→13 （ロ） 24→11→21→14 （ハ） 12→11→21→41→13 （ニ） 12→11→21→14 このうち、前記の条件による責任パスは、（イ）、
（ハ）及び（ニ）であるので、それらのパスの待たれ側
の端末にあるトランザクション‘13'及び‘14'を指定す
る問合せのメッセージ（図に、13?、14?として示す）
を、それぞれサイトアドレス関数部12のアドレス関数で
定まる、サイト及びに送る。

他の各サイトも同様に、問合せの必要なパスを検出し
て、問合せメッセージを送る。例えば、サイトは、図
に示すように宛先をサイトとして、メッセージ11?を
送信するので、サイトのデッドロック検出部15は、こ
の問合せメッセージに対して、サイト宛てに、図示の
ようにトランザクション‘11'に始まる待合せパスの情
報を応答する。

各サイトは、他のサイトに送った問合せに対する応答
を、各サイトから受信すると、それらの応答情報で第２
フェーズの待合せ関係グラフを補充して、第４図（ｃ）
に示す第３フェーズの待合せ関係グラフを得る。

サイトの場合、サイトからの応答は、新しい情報を
追加しないが、サイトからの応答により、トランザク
ション‘13'が、更にトランザクション‘32'を待ち、待
合せ関係32→23→34→33を経て、トランザクション‘1
2'に至るパスが追加されることにより、図示のようにデ
ッドロックループがあることを検出できる。

そこで、サイトが、例えばトランザクション識別子
‘41'のトランザクションの実行を中断させることによ
り、このデッドロックを解消することができる。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、複数
のサイトからなる計算機ネットワークのトランザクショ
ンに発生する、サイト間にまたがるグローバルデッドロ
ックの検出を、効率よく行うことができるので、計算機
ネットワークの性能を向上するという著しい工業的効果
がある。

【図面の簡単な説明】

第１図は本発明の実施例構成ブロック図、第２図はデッドロックループの一例を示す図、第３図は待合せ関係の一例を示す図、第４図はグローバルデッドロック検出処理説明図、第５図は計算機ネットワークの構成ブロック図、第６図はデッドロック発生状態の説明図である。図において、１〜４はサイト、５は通信回線、６は端末装置、10は通信制御部、 11はサブトランザクション、 12はサイトアドレス関数部、 13は待合せ通知部、14は待合せ問合せ部、 15はデッドロック検出部、 16はロック管理機構を示す。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献武理一郎他、「最適負荷配分が可能な分散型グローバルデッドロック検出方式」、情報処理学会第31回全国大会２Ｂ−２（1985)

Claims

【特許請求の範囲】

【請求項１】互いに通信する手段（10）を有し、それぞ
れ個別の計算機システムからなる複数のサイトからな
り、トランザクションを構成する複数のサブトランザク
ション（11）が、それぞれ複数の該サイトで並列に実行
される計算機ネットワークにおいて、該各サブトランザクション（11）は、該サブトランザク
ションによって構成されるトランザクションのトランザ
クション識別子を有し、該各サイトは、該サイトで実行するサブトランザクショ
ン間に、共有資源の排他的使用のための待合せが生じた
場合には、該サブトランザクションのトランザクション
識別子のみの関数（12）として一意に定まるサイトへ、
該待合せに関する情報を通知する手段（13）、及び、あるサブトランザクションから待合せ関係を待ち側に辿
って到達し得る部分を始点側と呼び、同じく待たれ側に
辿って到達し得る部分を終点側と呼ぶとき、受信した該
待合せに関する情報に基づき、始点側および終点側に他
サイトのサブトランザクションが存在し、該始点側と該
終点側の中間に自サイトのサブトランザクションが存在
し、かつ該自サイトのサブトランザクションの関数値が
最大である待合せ情報を検出し、該検出した待合せ情報
の該終点側のサブトランザクションについて、前記関数
（12）によって定まるサイトに問い合わせる手段（14）
を有することを特徴とするグローバルデッドロック検出
方式。
【請求項２】トランザクション識別子には、該トランザ
クションを発生したサイトのサイトアドレスを含み、ト
ランザクション識別子の前記関数は、該トランザクショ
ン識別子に含まれるサイトアドレスを値とすることを特
徴とする、特許請求の範囲第１項記載のグローバルデッ
ドロック検出方式。