JPH0254363A - デッドロック管理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は１台または複数台の計算機から構成されるシス
テム内で並列的に実行される複数プロセス間でのデッド
ロック管理において、複数プロセスからのデッドロック
検出またはデッドロック防止、の要求を矛盾なく、しか
も前記要求の処理中にデッドロック状態に陥らないよう
に管理するデッドロック管理方式に関する。

（従来の技術） 一般にデータベース資源やプリンタ、ブロック等の周辺
機器資源を複数のプロセス間で共有するシステムでは、
各プロセスが資源を取合いしてデッドロック状態に陥ら
ないように管理するために何らかのデッドロック防止方
式が採られている場合が多い。

またデッドロックに陥ったときにそのことをいち速く検
出するデッドロック検出方式が採用されている場合も多
い。

従来のシステムでは、システムを集中管理する管理機構
が前記いずれかの方式を実行している。

これは従来のシステムが大型計算機中心の集中管理方式
を採用しているためであるが、この場合、ホスト計算機
である大型計算機がシステムダウンするとシステムが停
止するので、デッドロック管理ができなくなる。

ところで近年０ＡＳＥＡ、ＦＡ等の各分野におけるシス
テムの分散化は時代の要請となっており、複数の中、小
型計算機がネットワークで相互に接続されたシステム構
成が主流になりつつある。

このような分散システムに要求される機能の１つとして
システムのロバスト性（−頑健性）が挙げられるが、こ
れは複数の計算機のいくつがかダウンしても残りの計算
機で必要な仕事が処理できることを意味している。

しかし分散システムにおいても集中機構がシステム内の
資源に対するデッドロック検出や防止方策を一括管理し
ている場合、集中機構が組込まれた計算機がダウンすれ
ば、他の計算機が動いていても複数プロセスの仕事を処
理することができなくなる。

この状態を回避する方法としては、デッドロック検出や
防止を実行するデッドロック管理機構が、集中機構化さ
れずに各計算機毎に分散化され、かつ各計算機は自分の
計算機に所属する資源（データベース、周辺機器等）の
みに対してデッドロック管理を行う、分散デッドロック
管理方式が挙げられる。

分散デッドロック管理方式を用いれば、複数計算機のい
くつかがダウンしても、残りの計算機で複数プロセスが
デッドロック検出や防止を行いながら仕事の処理するこ
とができるようになる。

しかしながら分散デッドロック管理方式では、複数プロ
セスの各々がどんな資源を必要としており、また現在ど
のプロセスがどの資源を使用しているのかといった資源
使用状況を一括把握する集中機構が存在しないので、プ
ロセスが複数の計算機に所属する資源を使用している場
合には、これら計算機間でデッドロック管理に必要な情
報を通信し合う必要がある。

第４図はプロセスＰＩとプロセスＰ２がそれぞれ資源Ｒ
１と資源Ｒ２とを使用して各プロセスの仕事を処理しよ
うとしているところを表わしている。

今、プロセスＰ１と資源Ｒ１が計算機Ｉに、プロセスＰ
２と資源Ｒ２が計算機Ｈに所属しているとする。そして
プロセスＰ１が資源Ｒ２をロックし、プロセスＰ２が資
源Ｒ１をロックしている状況を想定する。

第４図中では資ｇＲ２からプロセスＰＬに向かった矢印
ａと資源Ｒ１からプロセスＰ２に向かった矢印ａ　かこ
の状況を表現している。この時、はぼ同時にプロセスＰ
１とプロセスＰ２とが各々資源Ｒ１と資源Ｒ２とにロッ
ク要求をしたとする。

プロセスＰｉがデッドロック管理機構Ｉに対し資源Ｒ１
のロック要求をすると、このデッドロック管理機構Ｉは
プロセスＰ１のロック要求がデッドロックを起こすか否
かを調べるためにデッドロック管理機構Ｈに計算機■内
の状況を尋ねる。

デッドロック管理機構■はデッドロック管理機構Ｉから
の要請に対して、プロセスＰ２が資源Ｒ１をロックして
いるのみであることを返答する。

デッドロック管理機構ＩはプロセスＰｉの資源Ｒ１への
ロック要求がデッドロックを起こさないのでプロセスＰ
１に資１ＸＲ１のロック待ちを許可する。

したがって第４図中すのようにプロセスＰＬから資源Ｒ
１への矢印が引がれる。プロセスＰ１の資ｉｎ？ｆＲ１
へのロック要求とほぼ同時刻に、プロセスＰ２もデッド
ロック管理機構■に資源Ｒ２のロック要求を行う。

デッドロック管理機構■はプロセスＰ２のロック要求が
デッドロックを起こさないがを調べるためにデッドロッ
ク管理機構Ｉに計算機Ｉの状況を尋ねる。

この段階ではデッドロック管理機構Ｉのプロセスｐｔの
資Ｆｉ、Ｒ１へのロック要求を受は付けていないので、
デッドロック管理機構ＩはプロセスＰｌが資源Ｒ２をロ
ックしていることをデッドロック管理機構■に返答する
。

したがってデッドロック管理機構■はプロセスＰ２に資
源Ｒ２のロック待ちを許可するので、プロセスＰ２から
資源Ｒ２への矢印ｂ′が引がれる。

この段階でデッドロック管理機構Ｉとデッドロック管理
機構■はプロセスＰｌとプロセスＰ２のロック要求に対
してロック待ちを許可するのみでデッドロックになって
いないと判断している。

（発明が解決しようとする課題） しかしながら第４図に示したように、プロセスルミ、資
源Ｒ１、プロセスＰ２、資源Ｒ２の間で矢印の閉路がで
きているので、実際にはシステムはデッドロックに陥っ
ている。

ここで説明した例のように、実際にデッドロックが発生
しているのにデッドロック管理機構がその発生を検出で
きなかったのは、デッドロック管理機構１．ＩＩが２台
の計算機１．ＩＩ間にわたるデッドロックのチエツク（
防止または検出するための監視）を正しく行わなかった
ためである。

すなわち、゛デッドロック管理機構ＩがプロセスＰｉの
資源Ｒ１へのロック要求に対するデッドロックのチエツ
クをしている間は資源Ｒ１に関係する他プロセスのデッ
ドロックチエツクを許してはならないのに、デッドロッ
ク管理機構Ｉとデッドロック管理機構■とがそれぞれ独
立に他のプロセスのロック要求の発生を考慮しないでデ
ッドロックチエツクを実行したことに起因している。

本発明はこのような事情により成されたもので、集中管
理機構に依存しなくてもデッドロック管理を正しく実行
することができるデッドロック管理方式の提供を目的と
している。

［発明の構成］ （課題を解決するための手段） 本発明のデッドロック管理方式は、複数のプロセスの各
々が１つ以上の資源を共有または専仔保持しつつ各プロ
セスの作業を実行する計算機システム内において、デッ
ドロック管理機構に対しデッドロック検出、デッドロッ
ク防＋Ｌのいずれがの要求を出すプロセスが、前記デッ
ドロック管理機構に出す要求に、前記システム内で重複
しないプロセス識別子を添付する。

（作　用） 本発明のデッドロック管理方式では、プロセスの識別子
を各プロセス毎に付与し、複数の計算機に分散配置され
たデッドロック管理機構が前記識別子をチエツクするこ
とにより、各プロセスのロック要求の受は付けの可否を
判定するので、集中管理機構に依存しなくてもデッドロ
ック管理を正しく実行することかできる。

（実施例） 以下、本発明のデッドロック管理方式の実施例の詳細を
図面に基づいて説明する。

まず第１図に示したように、計算機工にはデッドロック
管理機構Ｉが設けられ、プロセスＰ１と資源Ｒ１とが所
属している。

また計算機■にはデッドロック管理機構■が設けられ、
プロセスＰ２と資源Ｒ２とが所属している。

第２図は前記デッドロック管理機構ＩおよびＨの構成を
示す図である。

デッドロック管理機構は、自計算機内のプロセスからの
資源保持要求と、このプロセスのシステム内で唯一の識
別子を受は付けるモジュールＡと、このプロセスの識別
子と他のプロセスの識別子との比較チエツクを行うモジ
ュールＢと、資源の待合わせグラフを生成し、デッドロ
ックの検出やデッドロック発生の予知を行うモジュール
Ｃとからなる。

そして第３図は前記モジュールＡにおける処理を詳細に
示す図である。

まずデッドロック管理機構ＩのモジュールＡがプロセス
Ｐ１の資［Ｒ２に対するロック要求を受付けた時刻をＴ
ｌ、デッドロック管理機構ＨのモジュールＡがプロセス
Ｐ２の資源Ｒ２に対するロック要求を受付けた時刻をＴ
２とする。

今、Ｔ１くＴ２、すなわちプロセスＰ１の方がプロセス
Ｐ２よりも早くロック要求したとする。

各デッドロック管理機構１．ＩＩのモジュールＡはロッ
ク要求と同時にプロセスから識別子（ＩＤ）を受取る。

識別子は時刻値と計算機の番号（サイト番号と称する）
とから作成され、システム内で唯一のものである。

そして第１図では時刻値ＴＩとサイト番号３１から作成
された識別子ＩＤＩを持つプロセスＰ１が資源Ｒ２をロ
ックし、時刻値Ｔ２とサイト番号Ｓ２から作成された識
別子ＩＤ２を持つプロセスＰ２が資源Ｒ１をロックして
いる。

このとき計算機■中のプロセスＰ２が資源Ｒ２へのロッ
ク要求をデッドロック管理機構■にＩＤ２を添付して行
ったとする。

デッドロック管理機構■は現在デッドロックのチエツク
を実行していないので、プロセスＰ２の資ｉＲ２へのロ
ック要求をＩＤ２として記憶し、かつ資源Ｒ２が既にプ
ロセスＰ１によりロック済なので、ＩＤ２の要求がデッ
ドロックにならないかを判断するためのチエツクを開始
する。

デッドロック管理機構■は自身がＩＤ２の要求を処理中
であることを表示すると共に、計算機Ｉのデッドロック
管理機構ＩにプロセスＰ２か資源Ｒ２を識別子ＩＤ２で
要求している旨を伝える。

デッドロック管理機構Ｉも現在デッドロックチエツクを
実行中ではないので、デッドロック管理機構Ｉからのデ
ッドロックチエツク要求を処理中であることを示すＩＤ
２のフラグを表示してデッドロックチエツクを実施する
。

このチエツクの実施中にプロセスＰ１が資源Ｒ１へのロ
ック要求を識別子ＩＤＩによりデッドロック管理機構■
に対して行ったとする。

デッドロック管理機構Ｉは第３図に示したルーチンにし
たがって識別子のチエツクを行うが、処理中のＩＤ２の
時刻値Ｔ２が要求ＩＤＩの時刻値Ｔｌより大であるので
、図中ステップｂでＮＯと判定され、ＩＤＩの要求は拒
否される。

一方、ＩＤ２からのデッドロックチエツク要求を処理中
のデッドロック管理機構Ｉは、ＩＤ２に関係する資源Ｒ
１がプロセスＰ２のみにロックされている旨を返答し、
デッドロック管理機構ＩがＩＤ２の要求処理を終了する
。

デッドロック管理機構Ｉより返答を受信したデッドロッ
ク管理機構■は、プロセスＰ２の資源Ｒ２へのロック要
求がデッドロックを発生させないので、プロセスＰ２の
資ｇＲ２へのロック待ちを許可する。資源の待ち合わせ
のグラフ表示ではプロセスＰ２から資源Ｒ２への矢印ｉ
が引かれる。

一方、ＩＤＩの識別子で資源Ｒ１のロック要求を拒否さ
れたプロセスｐｔは、現在時刻Ｔ３　　（Ｔ３　＞Ｔ２
　＞Ｔｌ　）で新たな識別子ＩＤ３を作成し、再度ＩＤ
３で資源Ｒ３のロック要求をデッドロック管理機構Ｉに
行う。

デッドロック管理機構Ｉは、もしまだＩＤ２の要求を処
理中ならばＩＤ３の要求を第３図のステップＣに従って
待ち行列に並べ、ＩＤ２の処理の終了後、この要求を待
ち行列から取り出してデッドロックチエツクを開始する
。

デッドロック管理機構Ｉはデッドロック管理機構ＨにＩ
Ｄ３の要求を伝え、デッドロック管理機構■から、資源
Ｒ２がプロセスＰＩにロックされかつプロセスＰ２が資
源Ｒ１のロック待ち状況になっている旨を受信する。

デッドロック管理機構Ｉはこの受信内容とプロセスｐｔ
の資源Ｒ１に対するロック要求とを比較して、このロッ
ク要求によりデッドロックが発生したことを検出する。

資源の待ち合わせ表示では、矢印ｊが引かれるので、プ
ロセスＰｌ、資源Ｒ１，プロセスＰ２、資源Ｒ２間で閉
路が形成され、デッドロック状態であることがわかる。

かくして本実施例によれば複数の計算機から成るシステ
ムに分配して所属する各種資源内容の正当性を維持しな
がらデッドロック管理を分配して実行することが可能に
なり、システムの一部の計算機がダウンしても他の計算
機に所属する資源を矛盾なく管理することができる。

［発明の効果］ 以上説明したように本発明のデッドロック管理方式では
、独自の識別子を各プロセス毎に付与し、複数の計算機
に分散配置されたデッドロック管理機構が前記識別子を
チエツクすることにより、各プロセスのロック要求の受
は付けの可否を判定するので、集中管理機構に依存しな
（でもデッドロック管理を正しく実行することができる
。

【図面の簡単な説明】

第１図は本発明を適用したシステムの一実施例の全体構
成を示す図、第２図は同システムにおけるデッドロック
管理機構の構成を示す図、第３図は同システムにおける
処理の流れを示す図、第４図は従来の分散処理システム
の構成の一例を示す図である。 Ｂ１ Ｃ・・・モジュール、 Ｐｌ　、 Ｂ２・・・プロセ ス、 ・・・資源。

Claims (1)

【特許請求の範囲】
1. （１）複数のプロセスの各々が１つ以上の資源を共有ま
   たは専有保持しつつ各プロセスの作業を実行する計算機
   システム内において、デッドロック管理機構に対しデッ
   ドロック検出、デッドロック防止のいずれかの要求を出
   すプロセスが、前記デッドロック管理機構に出す要求に
   、前記システム内で重複しないプロセス識別子を添付す
   ることを特徴とするデッドロック管理方式。