(57)【要約】  アプリケーションプログラム１２０，１３０のプログラムコード上で、デッドロックを発生させるロック命令を検出するデッドロック検出部３６０と、デッドロック検出部３６０が検出したロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、プログラムコードに新たなロック命令とアンロック命令を挿入する応急処理部１８０を備える。
2012153722.tif 000002
【特許請求の範囲】
【請求項１】
アプリケーションプログラムのコード上で、デッドロックを発生させるロック命令を検出するデッドロック発生位置検出部と、
前記デッドロック発生位置検出部が検出した前記ロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する応急処理部を備えたデッドロック予防装置。
【請求項２】
前記デッドロック発生位置検出部は、前記アプリケーションプログラムによるロックの状態の記録情報に基づいて、デッドロックが発生したロック命令を検出することを特徴とする請求項１に記載のデッドロック予防装置。
【請求項３】
前記アプリケーションプログラムからロック・アンロック要求を受信し、ロックの状態を管理するロックモニタと、
前記ロックモニタが、前記ロックの状態を管理するためのロック管理表記憶部と、
前記ロックモニタが、前記デッドロックを検出するために前記ロックの状態を記録するデッドロック管理表記憶部と、
前記ロックの状態の履歴を管理し、前記アプリケーションプログラムにおいてロックを行った箇所を記録するデッドロックグラフ行列記憶部と、
前記デッドロック管理表を参照し、前記デッドロックグラフ行列を作成するデッドロックグラフ作成部と、を備え、
前記デッドロック発生位置検出部は、前記デッドロックグラフ行列に基づいてデッドロックが発生する可能性のある位置を検出する、請求項１に記載のデッドロック予防装置。
【請求項４】
前記デッドロック発生位置検出部が検出した前記位置を提示するためのＧＵＩを備えたことを特徴とする請求項１から３のいずれかに記載のデッドロック予防装置。
【請求項５】
前記ロックモニタが、プログラムコード上のロック要求が発行される位置を記録するロックアドレス表記憶部を備え、
前記デッドロックグラフ作成部は、前記デッドロック管理表と前記ロックアドレス表を参照して前記デッドロックグラフ行列を作成し、
前記デッドロック発生位置検出部は、前記デッドロックグラフ行列に基づいて、デッドロック発生の可能性と、そのデッドロックを引き起こす可能性がある前記プログラムコード上のロック命令の位置を検出する、請求項３に記載のデッドロック予防装置。
【請求項６】
前記デッドロック発生位置検出部が検出したデッドロック発生の可能性と、そのデッドロックを引き起こす可能性がある前記プログラムコード上のロック命令の位置を提示するためのＧＵＩを備えたことを特徴とする請求項５に記載のデッドロック予防装置。
【請求項７】
前記アプリケーションプログラムに、前記アプリケーションプログラムを実行することにより前記デッドロック管理表や前記ロックアドレス表にロック情報を記録するためのプロブを埋め込むプロブ挿入部、を備えた請求項１〜６のいずれかに記載のデッドロック予防装置。
【請求項８】
前記アプリケーションプログラムによるロック命令の履歴を記録するデッドロックグラフ行列記憶部と、
前記アプリケーションプログラムによるロック命令に対応するプログラムコード上のロック命令箇所を記録するロックアドレス表記憶部と、を備え、
前記応急処理部は、前記デッドロックグラフ行列に基づいて検出された前記デッドロックを発生させるロック命令に対応するロック命令箇所を、前記ロックアドレス表を参照して取得するとともに、前記プログラムコードを検索してそのロック命令箇所に対応したアンロック命令箇所を取得し、そのロック命令箇所からそのアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する、請求項１に記載のデッドロック予防装置。
【請求項９】
アプリケーションプログラムのコード上で、デッドロックを発生させるロック命令を検出し、
前記検出した前記ロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する、デッドロック予防方法。
【請求項１０】
コンピュータを、
アプリケーションプログラムのコード上で、デッドロックを発生させるロック命令を検出するデッドロック発生位置検出部と、
前記デッドロック発生位置検出部が検出した前記ロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する応急処理部と、して機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デッドロック予防装置、デッドロック予防方法およびプログラムに関する。
【背景技術】
【０００２】
特許文献１、特許文献２にデッドロック自動解除システムの一例が、記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−１９１９４４号公報
【特許文献２】特開２００４−２４６４３９公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１に記載のデッドロック自動解除システムは、ロックを要求するアプリケーションプログラムに制約がある。すなわち、デッドロック状態からデッドロックを解除するには、アプリケーションプログラムがデッドロックを解除するために必要な処理を実行できなければならない。例えば、特許文献１では、各アプリケーションプログラムは大域ロックを取得しておかなければならない。また、特許文献２では、プロセス強制停止手段がプロセス（もしくはスレッド）をアンロックする際に、そのプロセスがロックしてからアンロックするまでのロールバック処理をアプリケーションプログラムが実行する必要がある。このように、アプリケーションプログラムをデッドロックの自動解除に対応できるように作る必要があった。【０００５】
本発明は、アプリケーションプログラムにデッドロック回避のための機能を持たせなくてもデッドロックを回避できるようにするデッドロック予防装置、デッドロック予防方法およびプログラムを提供することを一つの目的とする。
【課題を解決するための手段】
【０００６】
本発明に係るデッドロック予防装置は、アプリケーションプログラムのコード上で、デッドロックを発生させるロック命令を検出するデッドロック発生位置検出部と、前記デッドロック発生位置検出部が検出した前記ロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する応急処理部を備えたものである。
【発明の効果】
【０００７】
本発明によれば、アプリケーションプログラムにデッドロック回避のための機能を持たせなくてもデッドロックを回避できるデッドロック予防装置、デッドロック予防方法およびプログラムを提供できる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施の形態１によるデッドロック予防装置の構成を示すブロック図。
【図２】本発明の実施の形態２によるデッドロック予防装置の構成を示すブロック図。
【図３】本発明の実施の形態によるデッドロック予防装置の動作を示すフローチャート。
【図４】本発明の実施の形態によるロックモニタのロック要求処理のフローチャート。
【図５】本発明の実施の形態によるロックモニタのデッドロック管理処理のフローチャート。
【図６】本発明の実施の形態によるロックモニタのデッドロックアドレス登録処理のフローチャート。
【図７】本発明の実施の形態によるロックモニタのロック管理処理のフローチャート。
【図８】本発明の実施の形態によるロックモニタのアンロック処理のフローチャート。
【図９】本発明の実施の形態によるロックモニタのアンロック管理処理のフローチャート。
【図１０】本発明の実施の形態によるデッドロックグラフ作成部のロック処理のフローチャート。
【図１１】本発明の実施の形態１によるデッドロックグラフ作成部のアンロック処理のフローチャート。
【図１２】本発明の実施の形態によるデッドロック危険部位検出部の危険部位検出処理のフローチャート。
【図１３】本発明の実施の形態によるデッドロック危険部位検出部のデッドロック危険性検出処理のフローチャート。
【図１４】本発明の実施の形態によるデッドロック検出作業領域を示す図。
【図１５】本発明の実施の形態による応急処理部の動作のフローチャート。
【図１６】本発明の実施の形態によるデッドロック管理表を示す図。
【図１７】本発明の実施の形態によるデッドロックグラフ行列を示す図。
【図１８】本発明の実施例によるデッドロックグラフの例を示す図。
【図１９】本発明の実施の形態によるロック管理表を示す図。
【図２０】本発明の実施の形態によるロックアドレス表を示す図。
【図２１】本発明の実施の形態によるロック管理表を示す図。
【図２２】本発明の実施の形態によるロック、アンロック命令発行の時系列を示す図。
【図２３】本発明の実施の形態によるロック、アンロック命令発行の時系列を示す図。
【図２４】本発明の実施の形態２によるデッドロックグラフ作成部のアンロック処理のフローチャート。
【図２５】本発明の実施の形態３によるデッドロック予防装置の構成を示すブロック図。
【図２６】本発明の実施の形態３によるデッドロック予防装置の動作のフローチャート。
【図２７】本発明の実施例によるロックアドレス表の例を示す図。
【図２８】本発明の実施例によるデッドロック管理表の状態を示す図。
【図２９】本発明の実施例によるデッドロックグラフ行列の例を示す図。
【図３０】本発明の実施例によるデッドロックグラフの例を示す図。
【図３１】本発明の実施例によるＧＵＩの表示例を示す図。
【図３２】本発明の実施例による応急処理適用前のプログラムコードを示す図。
【図３３】本発明の実施例による応急処理適用後のプログラムコードを示す図。
【図３４】本発明の実施例によるロック、アンロック命令発行の時系列を示す図。
【発明を実施するための形態】
【０００９】
実施の形態１．
次に、本発明を実施するための形態について、図面を参照して詳細に説明する。
図１は、本発明の実施の形態１によるデッドロック予防装置の構成を示すブロック図である。図に示すように、本発明の実施の形態１によるデッドロック予防装置は、プログラム制御により動作する単数もしくは複数のＣＰＵ１００，１０１、複数のアプリケーションプログラム１２０，１３０、複数のアプリケーションプログラム１２０，１３０がアクセスする共有資源１１０、共有資源１１０へのアクセスの順番を制御するロックモニタ１４０、ロックモニタ１４０により管理されているロックの状態を記録するログＤＢ１５０、ログＤＢ１５０に記録された情報に基づいて、デッドロック箇所を検出するデッドロック検出部（デッドロック発生位置検出部）３６０、デッドロックの発生状況を管理者に伝えるためのＧＵＩ１７０、アプリケーションプログラム１２０，１３０のプログラムコード１９０、検出されたデッドロックの危険部位のうち、ＧＵＩ１７０を介して管理者が指定、承認した個所について、アプリケーションプログラム１２０，１３０のプログラムコード１９０にデッドロックを防止するコードを埋め込む応急処理部１８０、および、ロックモニタ１４０、デッドロック検出部３６０などのプログラムを格納するメモリ１０５を備えている。
【００１０】
ログＤＢ１５０には、ロックの獲得状況を示すロック管理表１５５、デッドロック管理表１５３、デッドロックを検出するための作業領域であるデッドロックグラフ行列１５７、アプリケーションプログラム上でのロック要求の発生箇所を記録するロックアドレス表１５９が格納されている。また、メモリ１０５には、デッドロック管理表１５３からデッドロックグラフ行列１５７を生成するデッドロックグラフ作成部３５６が格納されている。
【００１１】
ロック管理表１５５は、例えば、図１９に示すように、ロック対象オブジェクトＩＤ  をキーとして、ロック要求を行ったスレッドのＩＤを線形リストで管理する一覧表である。線形リスト上のスレッドＩＤのうち、最初に登録されたスレッドＩＤに対応するスレッドが、ロック対象オブジェクトに対してロックを獲得したスレッドである。それ以外の線形リスト上のスレッドはロック待ちスレッドとなる。
【００１２】
ロックアドレス表１５９は、例えば図２０に示すように、行ＩＤ（＃）と、プログラムコード１９０上のロック命令個所であるファイル名とアドレスを記録する一覧表である。
【００１３】
デッドロック管理表１５３は、例えば図１６に示すように、デッドロック管理表本体とロック対象オブジェクトスタックで構成される。デッドロック管理表１５３本体は、ロック要求を行ったスレッドＩＤをキーとして、ロック対象オブジェクトスタックを管理する一覧表である。ロック対象オブジェクトスタックは、該当スレッドがロック要求を出したロック対象オブジェクトのＩＤと、ロックアドレス表１５９に記録されたロック命令個所を示す行ＩＤの組を保持するスタックである。
【００１４】
デッドロックグラフ行列１５７は、例えば図１７で示すように、デッドロックグラフ行列本体と、デッドロックグラフスレッド表と、デッドロックグラフ行列本体の行列要素毎に存在するデッドロックグラフ辺属性表で構成される。図１７のデッドロックグラフ行列１５７は、図１８のデッドロックグラフと同値である。デッドロックグラフ行列本体は、同一スレッドが複数のロック要求を行った履歴を示す。例えば、スレッドＴがロックＶ４  要求し、Ｖ４をアンロックする前にＶ１のロックを要求した場合、デッドロックグラフ行列の行Ｖ４列Ｖ１の要素が１になる。
【００１５】
デッドロックグラフスレッド表は、行ごとに与えられたＩＤである系列ＩＤをキーとして、同一スレッドが複数回のロックを獲得している場合に、その先頭を指し示すデッドロックグラフ行列本体の行列要素への先頭ポインタと、現在ロック要求中のスレッドＩＤを管理する表である。ただし、スレッドがロックしたオブジェクトをすべてアンロックした場合、「スレッドＩＤ」の列は、そのスレッドＩＤから“終了済”に値が書き変わる。
【００１６】
デッドロックグラフ辺属性表は、デッドロックグラフスレッド表の系列ＩＤをキーとして、スレッドが先にロック要求したオブジェクト“ｓｒｃ”のロック要求個所が記録されたロックアドレス表の行ＩＤと、次にロック要求したオブジェクト“ｄｅｓｔ” のロック要求個所が記録されたロックアドレス表の行ＩＤを管理する一覧表である。
【００１７】
例えば、スレッドＴがデッドロックグラフスレッド表の系列ＩＤ１に記録されており、Ｖ１→Ｖ３のロック要求をした場合を例に説明する。Ｖ１へのロック要求を発行したロック要求個所が記録されたロックアドレス表１５９の行ＩＤを＃２、Ｖ３へのロック要求を発行したロック要求個所が記録されたロックアドレス表１５９の行ＩＤを＃６とすると、（Ｖ１，Ｖ３）の行列要素に対応するデッドロックグラフ辺属性表には、｛系列ＩＤ＝１，  ｓｒｃ＝＃２，ｄｅｓｔ＝＃６｝という行が記録される。
【００１８】
デッドロック検出作業領域１６５は、図１４に示すように、ロック対象オブジェクトを格納するスタックである。
【００１９】
次に、デッドロック予防装置の動作について説明する。
アプリケーションプログラム１２０，１３０は、システム利用者にサービスを提供するプログラムである。本実施形態では、デッドロック検出対象のプログラムである。なお、アプリケーションプログラムでは複数のスレッドが並行して動作する。
【００２０】
ロックモニタ１４０は、アプリケーションプログラム１２０，１３０からのロック要求を受け付ける。アプリケーションプログラム１２０，１３０は、共有資源１１０にアクセスする際、他のアプリケーションからの影響により一貫性が維持できなくなることを避けるため、ロックを要求する。その要求をロックモニタ１４０が受理し、ロック管理表１５５、デッドロック管理表１５３、およびロックアドレス表１５９にロック要求を記録する。さらに、状況に応じて、ロックを許可するか、あるいはロックを要求したスレッドを待ち状態にする。
【００２１】
デッドロックグラフ作成部３５６は、デッドロック管理表１５３に記録されたロックの状態を読み込み、デッドロックグラフ行列１５７に、ロック要求の履歴を記録する。デッドロックグラフ行列１５７は、デッドロックの危険性を検出するための作業領域である。
【００２２】
デッドロック検出部３６０は、デッドロックグラフ行列１５７を参照し、デッドロックグラフ上の閉グラフを検出することで、デッドロック部位を検出し、それをＧＵＩ１７０に表示する。
【００２３】
応急処理部１８０は、プログラムコード１９０を読み込み、デッドロック検出部３６０で検出したデッドロックが発生する個所に相当するプログラム部位を書き換えて、アプリケーションプログラム１２０，１３０を置換する。
【００２４】
次に、図３を参照して本実施の形態によるデッドロック予防装置の動作について詳細に説明する。
まず、アプリケーションプログラム１２０が、処理実行のリクエストを受け付ける（ステップＺ１１０）。
次に、アプリケーションプログラム１２０は、リクエストに応じてサービスを実行する（ステップＺ１２０）。
【００２５】
アプリケーションプログラムの実行中、共有資源１１０にアクセスする必要があれば、アプリケーションプログラム１２０は、ロックモニタ１４０にロックを要求する（ステップＺ１３０）。
【００２６】
アプリケーションプログラム１２０は、ロックを獲得すると、サービスを実行する（ステップＺ１４０）。
アプリケーションプログラム１２０は、共有資源１１０が不要になると、ロックモニタ  １４０にアンロックを通知する（ステップＺ１５０）。
【００２７】
アプリケーションプログラム１２０は、引き続きサービスを実行する（ステップＺ１６０）。
アプリケーションプログラム１２０は、一連の処理が完了すると、応答を返す（ステップＺ１７０）。さらに、ステップＺ１１０に戻り、リクエストを受け付ける。
【００２８】
次に、図４を参照してロックモニタ１４０のロック要求処理について詳細に説明する。
まず、ロックモニタ１４０は、ロック要求を行ったスレッドのＩＤと、ロック対象オブジェクトのＩＤ、ロック命令を実行したファイル名とファイル内のアドレス（例えば、行番号）を取得する（ステップＡ１２０）。なお、以下、ロック命令を実行したファイル名とファイル内のアドレス（例えば、行番号）のことを、ロック命令個所と呼ぶ。
【００２９】
続いて、ロックモニタ１４０は、デッドロックの危険性を検出するために、デッドロック管理表１５３にロック情報を記録するデッドロック管理処理を行う（ステップＡ１３０）。次に、ロック命令が発生した個所を記録するロックアドレス登録処理を行う（ステップＡ１４０）。
【００３０】
続いて、ロック管理表１５５にロック情報を記録するロック管理処理を行う（ステップ  Ａ１５０）。
【００３１】
次に、図５を参照してロックモニタ１４０のデッドロック管理処理について説明する。本処理は、ロックモニタ１４０のロック要求処理（ステップＡ１３０）から起動される。
【００３２】
まず、デッドロックモニタ１４０は、デッドロック管理表１５３に、オブジェクトＩＤ、スレッドＩＤ、ロック命令個所を登録した、ロックアドレス表１５９の該当行ＩＤの、３つ組のデータを登録する（ステップＥ１１０）。ただし、該当する行が既に登録済みならば、登録はせずに終了する（ステップＥ１２０）。例えば、ｊａｖａ（登録商標）のように、同じスレッドから同じロック対象オブジェクトへのロック（ｊａｖａ（登録商標）の場合はｓｙｎｃｈｒｏｎｉｚｅｄ）は行わない言語の場合、ステップＥ１２０が必要となる。これは、後述のステップＣ１２５、ステップＧ１２０でも同様である。
【００３３】
ステップＥ１２０で未登録ならば、デッドロック管理表１５３にロック対象オブジェクトＩＤ、スレッドＩＤ、およびロック要求個所が登録されたロックアドレス表１５９の該当行のエントリＩＤを登録する（ステップＥ１３０）。すなわち、デッドロック管理表１５３の該当スレッドＩＤのエントリにあるロック対象オブジェクトスタックに、ロック対象オブジェクトＩＤと、ロックアドレス表１５９の該当行ＩＤの組をプッシュして記録する。
【００３４】
さらに、デッドロックグラフ作成部３５６が、デッドロックグラフ行列１５７に該当オブジェクトＩＤと、登録したロック対象オブジェクトＩＤを記録する（ステップＥ１４０）。
【００３５】
次に、図６を参照してロックモニタ１４０のデッドロックアドレス登録処理について説明する。本処理は、前述のロックモニタ１４０のロック要求処理から起動される。
【００３６】
まず、ロックモニタ１４０は、デッドロック管理表１５３にロック命令個所、すなわち、ロック発生箇所のファイル名、アドレスを登録する（ステップＧ１１０）。もし、該当ロック発生箇所のファイル名およびアドレスと同じエントリがロックアドレス管理表１５３に登録済みならば重複登録はしない（ステップＧ１２０）。
【００３７】
ステップＧ１２０で未登録ならば、ロックモニタ１４０は、ロック命令個所、すなわち、ロック発生箇所のファイル名、アドレスを、ロックアドレス管理表１５３に記録する（ステップＧ１３０）。その後元の処理に復帰する。
【００３８】
次に、図７を参照してロックモニタ１４０のロック管理処理について説明する。本処理は、前述のロックモニタ１４０のロック要求処理（ステップＡ１５０）から起動される。
【００３９】
まず、ロックモニタ１４０は、ロック管理表１５５の該当箇所にロック対象オブジェクトのＩＤとロック要求を行ったスレッドのＩＤを登録する（ステップＣ１２０）。なお、既にロック管理表１５５の該当箇所に同じオブジェクトＩＤとスレッドＩＤが登録済みならば、本処理を終了し、元の処理に戻る（ステップＣ１２５）。このステップは、ｊａｖａ（登録商標）のように同じスレッドから同じロック対象オブジェクトへのロック（ｓｙｎｃｈｒｏｎｉｚｅｄ）は行わない特性を有するプログラミング言語の場合に必要である。ただし、同じオブジェクトＩＤとスレッドＩＤが既にロック要求している場合でも、別のロックをとるようなプログラム言語の場合は、ステップＣ１２５の条件判断処理を行わずに、ステップＣ１２７に進む。
【００４０】
ロックモニタ１４０は、ロック対象オブジェクトＩＤとスレッドＩＤをロック管理表  １５５に登録する（ステップＣ１２７）。すなわち、図２１で示されるロック管理表１５５の該当ロック対象オブジェクトＩＤの線形リストの後尾に、該当スレッドＩＤを追加する。
【００４１】
ロック管理表１５５において、各線形リストの先頭のスレッドがロックを獲得しているスレッドであり、後続のスレッドがロック待ち状態のスレッドである。
【００４２】
次に、ロック対象オブジェクトＩＤに対して既に他のスレッドがロックを有しているか否かを、ロック管理表１５５を参照して判断する（ステップＣ１３０）。既にロック待ちならば（ｙｅｓ）、スレッドを待ち状態にする（ステップＣ１４０）。待ち状態に入ったスレッドは、他のスレッドが共有資源１１０をアンロックしないと、処理が停止したままとなる。ステップＣ１３０でロック待ちでなければ、ロック獲得状態となって元の処理に復帰する。
【００４３】
次に、図８を参照してロックモニタ１４０のアンロック処理について説明する。本処理は、前述の図３のステップＺ１５０から起動される。
【００４４】
まず、ロックモニタ１４０は、ロック要求を行ったスレッドのＩＤとロック対象オブジェクトのＩＤを取得する（ステップＢ１１０）。
【００４５】
次に、ロックモニタ１４０は、デッドロック管理表１５３の該当ロック対象オブジェクトのＩＤの行から、スレッドＩＤを取り除く（ステップＢ１３０）。すなわち、デッドロック管理表１５３から、該当するスレッドＩＤのエントリが有するロック対象オブジェクトスタックをポップし、該当ロック対象オブジェクトＩＤとロックアドレス表の該当エントリＩＤの組を除去する。
【００４６】
続いて、ロックモニタ１４０は、ロック管理表１５５を参照し、アンロックを行うためのアンロック管理処理を行う（ステップＢ１５０）。
【００４７】
続いて、デッドロックグラフ作成部３５６は、スレッドＩＤと、除去したオブジェクトＩＤと、ロックアドレス表の該当エントリＩＤの情報に基づいてアンロック処理を行う（ステップＢ１６０）。
【００４８】
次に、図９を参照してロックモニタ１４０のアンロック管理処理について説明する。本処理は、前述のロックモニタ１４０の動作のアンロック処理（ステップＢ１５０）から起動される。
【００４９】
まず、ロックモニタ１４０は、ロック管理表１５５から該当ロック対象オブジェクトＩＤ、スレッドＩＤを削除する（ステップＤ１１０）。すなわち、ロック管理表１５５の、該当オブジェクトＩＤのエントリが有する線形リストからスレッドＩＤを削除する。
【００５０】
次に、ロックモニタ１４０は、アンロックしたオブジェクトで待ち状態にあるスレッドがあるか否かを、ロック管理表１５５を参照して確認する（ステップＤ１２０）。もし、後続の待ちスレッドがあれば（ステップＤ１３０：ｙｅｓ）、待ちスレッドの１つを再開し、ロック管理表１５５のロック獲得スレッドに記録する（ステップＤ１４０）。
【００５１】
すなわち、ステップＤ１１０〜Ｄ１４０では、ロック管理表１５５の該当ロック対象オブジェクトＩＤのエントリから、ロック獲得中の該当スレッドＩＤを取り除き、そのロック対象オブジェクトに対するロック待ちのスレッドがあれば、それをロック獲得中のスレッドとして、待ち状態から起動する。
【００５２】
次に、図１０を参照してデッドロックグラフ作成部３５６のロック処理について説明する。本処理は、図５に示すロックモニタ１４０のデッドロック管理処理を構成するステップＥ１４０から起動される。
【００５３】
まず、デッドロックグラフ作成部３５６は、デッドロック管理表１５３を参照し、新たにロックされたロック対象オブジェクトＩＤと、ロック要求を行ったスレッドＩＤを取得する（ステップＭ１１０）。
【００５４】
次に、デッドロックグラフ作成部３５６は、デッドロック管理表１５３の該当スレッドＩＤのロック対象オブジェクトスタックを参照し、新たなロック対象オブジェクトと同一のオブジェクトＩＤがないか否かを調べる（ステップＭ１２０）。もし、該当するロック対象オブジェクトがなければ（ステップＭ１３０：ｎｏ）、元の処理に復帰する。該当するロック対象オブジェクトがある場合（ステップＭ１３０：ｙｅｓ）、デッドロックグラフ作成部３５６は、デッドロックグラフ行列の行（新たなロック対象オブジェクトの一つ前のロック対象オブジェクト。該当スレッドＩＤに対応したロック対象オブジェクトスタックの先頭から二番目のノードＩＤで示す行）と、列（新たなロック対象オブジェクト。スレッドＩＤに対応したロック対象オブジェクトスタックの先頭のノードＩＤで示す列）で示す行列の要素を１にする（ステップＭ１４０）。
【００５５】
次に、デッドロックグラフ作成部３５６は、デッドロックグラフスレッド表を参照し、該当スレッドＩＤを検索する（ステップＭ１５０）。該当スレッドＩＤがある場合には（ステップＭ１６０：ｙｅｓ）、デッドロックグラフスレッド表の該当する系列ＩＤを取得する（ステップＭ１８０）。該当スレッドＩＤがある場合には（ステップＭ１６０：ｎｏ）、デッドロックグラフスレッド表に新たな行を作成し、その系列ＩＤを返す（ステップＭ１７０）。
【００５６】
すなわち、デッドロックグラフ作成部３５６は、新たな系列ＩＤを生成し、系列ＩＤ  と、ロック要求スレッドのＩＤと、デッドロックグラフ行列１５７の行列要素で、ステップＭ１４０で値を１にした要素への参照の３つ組をデッドロックグラフスレッド表に記録する。そして、新たに生成した系列ＩＤを返す。
【００５７】
次に、デッドロックグラフ作成部３５６は、ロック対象オブジェクトスタック内に記録されたロック対象オブジェクトと一つ前のロック対象オブジェクトのそれぞれのロックアドレス表１５９の行ＩＤを取得し、ステップＭ１４０で値を１にしたデッドロックグラフ行列１５７の要素に対応したデッドロックグラフ辺属性表に、系列ＩＤと以前のロック対象オブジェクトと新たなロック対象のそれぞれの行ＩＤの三つ組を追記する（ステップＭ１９０）。
【００５８】
次に、図１１を参照してデッドロックグラフ作成部３５６のアンロック処理の動作ついて説明する。本処理は、図５に示すロックモニタ１４０のアンロック処理を構成するステップＥ１４０から起動される。
【００５９】
まず、デッドロックグラフ作成部３５６は、アンロックされたロック対象オブジェクトＩＤと、アンロック要求を行ったスレッドＩＤを取得する（ステップＰ１０１）。
【００６０】
次に、デッドロックグラフ作成部３５６は、デッドロック管理表１５３のロック対象オブジェクトのリストを参照し、アンロックされたオブジェクトがロックされた直前に、同一スレッドでロック要求されたオブジェクトがあったか否かを調べる（ステップＰ１０２）。
【００６１】
同一スレッドでロック要求されたオブジェクトがあった場合（ステップＰ１０３：ｙｅｓ）ステップＰ１０４に移行し、なかった場合は、ステップＰ１０８に移行する。
ステップＰ１０４で、デッドロックグラフ作成部３５６は、デッドロックグラフ行列１５７の行（前のロック対象オブジェクト）と列（アンロック対象オブジェクト）で示す要素に対応するデッドロックグラフ辺属性表から、スレッドＩＤに相当する系列ＩＤの行を削除する。
【００６２】
次に、デッドロックグラフ作成部３５６は、デッドロックグラフ辺属性表が空になったか否かを判定する（ステップＰ１０５、Ｐ１０６）。空の場合にはステップＰ１０７へ進み、空でない場合にはステップＰ１０８に移行する。
【００６３】
ステップＰ１０７でデッドロックグラフ作成部３５６は、デッドロックグラフ行列１５７の該当要素を０にする。
【００６４】
次に、デッドロックグラフ作成部３５６は、デッドロック管理表１５３のロック対象オブジェクトスタックのうち、アンロック要求スレッドのＩＤに対応した、ロック対象オブジェクトスタックを検索し、ロック対象オブジェクトスタックが空か否かを調べる（ステップＰ１０８）。もし空でなければ（ステップＰ１０９：ｎｏ）、元の処理に復帰する。もし、空ならば（ステップＰ１０９：ｙｅｓ）、デッドロックグラフ作成部３５６は、デッドロックグラフスレッド管理表からアンロック要求したスレッドＩＤの行を削除する（ステップＰ１１０）。
【００６５】
次に、図１２を参照してデッドロック検出部３６０のデッドロック部位検出処理について説明する。本動作は、定期的もしくは適当なタイミングで起動される。
【００６６】
まず、デッドロックグラフ行列１５７のうち、１が立っている行列要素を１つ選ぶ（ステップＩ１１０）。既にすべてのノードが選択済みの場合（ステップＩ１２０：ｙｅｓ）、処理を終了する。それ以外の場合（ステップＩ１２０：ｎｏ）、後述のデッドロック危険性検出処理（ステップＩ１３０）を行う。その後、ステップＩ１１０に戻り処理を繰り返す。
【００６７】
次に、図１３を参照してデッドロック検出部３６０のデッドロック検出処理について説明する。本処理は、前述のデッドロック検出部３６０の危険部位検出処理（ステップＩ１３０）から呼び出される。または、当処理から再帰的に呼び出される。その際、デッドロックグラフ行列１５７の検査対象行、すなわちグラフを構成する有向辺の出発ノード（ロック対象オブジェクト）の一つが引数として渡される。
【００６８】
まず、その出発ノードを現ノードとし、その現ノードがデッドロック検出作業領域１６５に記録されていれば（ステップＪ１１０：ｙｅｓ）、既にデッドロック検出作業領域１６５に格納済みのノードを含み、それノード以降にデッドロック検出作業領域１６５に格納されたノードまでのノード列を、取得する。さらに、ノード列に対応したデッドロックグラフ行列１５７の該当箇所をデッドロック危険領域とする（ステップＪ１７０）。
【００６９】
図１４の例を用いて説明する。新たにＶ４をデッドロック検出作業領域にプッシュしようとするとき、Ｖ４は既にデッドロック検出作業領域にある。このとき、デッドロックグラフ行列１５７の（Ｖ４，Ｖ１）、（Ｖ１，Ｖ３）、（Ｖ３，Ｖ４）の要素がデッドロック危険部位である。ステップＪ１７０の後は、元の処理に復帰する。
【００７０】
ステップＪ１１０で、現ノードがデッドロック検出作業領域１６５に記録されていない場合、デッドロック検出部３６０は、現ノードのＩＤをデッドロック検出作業領域にプッシュする（ステップＪ１２０）。
【００７１】
次に、デッドロック検出部３６０は、デッドロックグラフ行列１５７のうち、現ノードの該当行のうち、１が立っている列を選び出す（ステップＪ１３０）。もし、１が立っている列に関してすべての行き先ノードを検査済みならば（ステップＪ１４０：ｙｅｓ）、デッドロック検出作業領域にプッシュした現ノードの情報を取り出し（ステップＪ１６０）、本処理から元処理へ復帰する。
【００７２】
ステップＪ１４０で検査未済のノードがある場合は（ｎｏ）、１が立っている列の一つが表すノードＩＤを現ノードＩＤとして引数とし、デッドロック検出処理を再帰的に呼び出す（ステップＪ１５０）。
【００７３】
次に、図１５を参照して応急処理部１８０の動作ついて説明する。本処理は、デッドロック検出部３６０が発見したデッドロック危険部位のうち、管理者がＧＵＩ１７０を介して選択したデッドロック危険部位に対して行う。
【００７４】
まず、デッドロック検出部３６０が検出した複数のデッドロック部位から一つを取り出す（ステップＫ１１０）。デッドロック検出部３６０は、デッドロック危険部位、例えば“（Ｖ４，Ｖ１）、（Ｖ１，Ｖ３）、（Ｖ３，Ｖ４）”を取り出すとともに、（Ｖ４，Ｖ１）等の各辺のデッドロックグラフ行列辺属性表を参照し、辺ごとの系列ＩＤと、辺ごとのロックアドレス表１５９の行ＩＤの組が参照する複数のロック命令個所の組を複数取得する。
【００７５】
既にすべてのデッドロック危険部位について応急処理済みならば（ステップＫ１２０：ｙｅｓ）、元の処理に復帰する。応急処理未済のデッドロック危険領域がある場合は（ｎｏ）、新たなロック対象オブジェクトＶを作成する（ステップＫ１２５）。
【００７６】
ステップＫ１１０において、取得したデッドロック危険部位に対応した複数の系列ＩＤ  の中から一つを取り出し、それに対応するデッドロック危険部位のサブセットを取り出す。（ステップＫ１３０）。
【００７７】
すべての系列ＩＤについて処理が完了したら（ステップＫ１４０：ｙｅｓ）、ステップＫ１１０に戻り、他のデッドロック部位に対して処理を行う。
【００７８】
処理未済の系列ＩＤがある場合（ステップＫ１４０：ｎｏ）、応急処理部１８０は、デッドロッククラススレッド表の該当系列ＩＤの行を取り出し、その行が指すデッドロックグラフ行列の要素の、デッドロックグラフ辺属性表の該当系列ＩＤの行のｓｒｃノードのロック命令個所を、ロックアドレス表１５９を参照して取得する。さらに、応急処理部１８０は、プログラムコード１９０を検索し、そのロック命令箇所に対応したアンロック該当箇所を取得する（ステップＫ１５０）。
【００７９】
先頭のロック命令個所とそれに対応するアンロック命令個所について、応急処理部１８０は、ロック対象オブジェクトＶを対象にしたロック要求命令とアンロック命令を、該当ファイルに挿入する（ステップＫ１７０）。
【００８０】
すなわち、応急処理部１８０は、デッドロックを起こしたロック・アンロック命令に対して、それを包含するようにロック命令を作成するため、デッドロックを防ぐことができる。図２２にロック、アンロック命令発行の時系列を示す。簡略化のため、図２２では、デッドロックが発生している例を示した図２３からデッドロックに無関係なＴ２，Ｔ３，Ｔ５を除いている。図２２は、図２３に対して、Ｔ１，Ｔ４にロック対象オブジェクトＶに対するロック命令、アンロック命令を挿入した。これにより、Ｔ４が、Ｔ１をロック待ちにし、一連の操作を実行することができる。これによりデッドロックを防ぐことができる。
【００８１】
また、既存のロック対象オブジェクトとは別に新たなロック対象オブジェクトＶを生成するため、ロック対象オブジェクトＶに対するロックが既存のロックと干渉し、新たなデッドロックを発生することはない。ステップＫ１７０の処理が終了したら、ステップＫ１４０に戻り、次のスレッドの検査を行う。
【００８２】
以上のように、本実施形態によれば、応急処理部１８０がデッドロック検出部３６０によって検出されたデッドロック個所に対してプログラムコード１９０を書き換え、デッドロック危険部位を包含するようなロック・アンロックを挿入するようにしたので、次回のデッドロックを予防することができる。
【００８３】
また、アプリケーションプログラム１２０，１３０にデッドロック回避のための機能を持たせなくてもデッドロックを回避できる。その理由は、アプリケーションプログラムにおけるデッドロックの危険個所を応急処理部１８０が書き換え、デッドロック危険部位に対してロック命令を挿入するためである。このコードの挿入は、応急処理部１８０が行うため、アプリケーションプログラム自体を書き換える必要がない。
【００８４】
実施の形態２．
図２は、本発明の実施の形態２によるデッドロック予防装置の構成を示すブロック図である。図に示すように、本発明の実施の形態によるデッドロック予防装置は、プログラム制御により動作する単数もしくは複数のＣＰＵ１００，１０１、複数のアプリケーションプログラム１２０，１３０、複数のアプリケーションプログラム１２０，１３０がアクセスする共有資源１１０、共有資源１１０へのアクセスの順番を制御するロックモニタ１４０、ロックモニタ１４０により管理されているロックの状態を記録するログＤＢ１５０、ログＤＢ１５０に記録された情報に基づいて、デッドロックを検出するデッドロック危険部位検出部（デッドロック発生位置検出部）１６０、デッドロックの発生状況を管理者に伝えるためのＧＵＩ１７０、アプリケーションプログラム１２０，１３０のプログラムコード１９０、検出されたデッドロックの危険部位のうち、ＧＵＩ１７０を介して管理者が指定、承認した個所について、アプリケーションプログラム１２０，１３０のプログラムコード１９０にデッドロックを防止するコードを埋め込む応急処理部１８０、および、ロックモニタ１４０、デッドロック危険部位検出部１６０などのプログラムを格納するメモリ１０５を備えている。
【００８５】
ログＤＢ１５０には、ロックの獲得状況を示すロック管理表１５５、デッドロック管理表１５３、デッドロックを検出するための作業領域であるデッドロックグラフ行列１５７、アプリケーションプログラム上でのロック要求の発生箇所を記録するロックアドレス表１５９が格納されている。また、メモリ１０５には、デッドロック管理表１５３からデッドロックグラフ行列１５７を生成するデッドロックグラフ作成部１５６が格納されている。
【００８６】
ロック管理表１５５は、例えば、図１９に示すように、ロック対象オブジェクトＩＤ  をキーとして、ロック要求を行ったスレッドのＩＤを線形リストで管理する一覧表である。線形リスト上のスレッドＩＤのうち、最初に登録されたスレッドＩＤに対応するスレッドが、ロック対象オブジェクトに対してロックを獲得したスレッドである。それ以外の線形リスト上のスレッドはロック待ちスレッドとなる。
【００８７】
ロックアドレス表１５９は、例えば図２０に示すように、行ＩＤ（＃）と、プログラムコード１９０上のロック命令個所であるファイル名とアドレスを記録する一覧表である。
【００８８】
デッドロック管理表１５３は、例えば図１６に示すように、デッドロック管理表本体とロック対象オブジェクトスタックで構成される。デッドロック管理表１５３本体は、ロック要求を行ったスレッドＩＤをキーとして、ロック対象オブジェクトスタックを管理する一覧表である。ロック対象オブジェクトスタックは、該当スレッドがロック要求を出したロック対象オブジェクトのＩＤと、ロックアドレス表１５９に記録されたロック命令個所を示す行ＩＤの組を保持するスタックである。
【００８９】
デッドロックグラフ行列１５７は、例えば図１７で示すように、デッドロックグラフ行列本体と、デッドロックグラフスレッド表と、デッドロックグラフ行列本体の行列要素毎に存在するデッドロックグラフ辺属性表で構成される。図１７のデッドロックグラフ行列１５７は、図１８のデッドロックグラフと同値である。デッドロックグラフ行列本体は、同一スレッドが複数のロック要求を行った履歴を示す。例えば、スレッドＴがロックＶ４  要求し、Ｖ４をアンロックする前にＶ１のロックを要求した場合、デッドロックグラフ行列の行Ｖ４列Ｖ１の要素が１になる。
【００９０】
デッドロックグラフスレッド表は、行ごとに与えられたＩＤである系列ＩＤをキーとして、同一スレッドが複数回のロックを獲得している場合に、その先頭を指し示すデッドロックグラフ行列本体の行列要素への先頭ポインタと、現在ロック要求中のスレッドＩＤを管理する表である。ただし、スレッドがロックしたオブジェクトをすべてアンロックした場合、「スレッドＩＤ」の列は、そのスレッドＩＤから“終了済”に値が書き変わる。
【００９１】
デッドロックグラフ辺属性表は、デッドロックグラフスレッド表の系列ＩＤをキーとして、スレッドが先にロック要求したオブジェクト“ｓｒｃ”のロック要求個所が記録されたロックアドレス表の行ＩＤと、次にロック要求したオブジェクト“ｄｅｓｔ” のロック要求個所が記録されたロックアドレス表の行ＩＤを管理する一覧表である。
【００９２】
例えば、スレッドＴがデッドロックグラフスレッド表の系列ＩＤ１に記録されており、Ｖ１→Ｖ３のロック要求をした場合を例に説明する。Ｖ１へのロック要求を発行したロック要求個所が記録されたロックアドレス表１５９の行ＩＤを＃２、Ｖ３へのロック要求を発行したロック要求個所が記録されたロックアドレス表１５９の行ＩＤを＃６とすると、（Ｖ１，Ｖ３）の行列要素に対応するデッドロックグラフ辺属性表には、｛系列ＩＤ＝１，  ｓｒｃ＝＃２，ｄｅｓｔ＝＃６｝という行が記録される。
【００９３】
デッドロック検出作業領域１６５は、図１４に示すように、ロック対象オブジェクトを格納するスタックである。
【００９４】
次に、デッドロック予防装置の動作について説明する。
アプリケーションプログラム１２０，１３０は、システム利用者にサービスを提供するプログラムである。本実施形態では、デッドロック検出対象のプログラムである。なお、アプリケーションプログラムでは複数のスレッドが並行して動作する。
【００９５】
ロックモニタ１４０は、アプリケーションプログラム１２０，１３０からのロック要求を受け付ける。アプリケーションプログラム１２０，１３０は、共有資源１１０にアクセスする際、他のアプリケーションからの影響により一貫性が維持できなくなることを避けるため、ロックを要求する。その要求をロックモニタ１４０が受理し、ロック管理表１５５、デッドロック管理表１５３、およびロックアドレス表１５９にロック要求を記録する。さらに、状況に応じて、ロックを許可するか、あるいはロックを要求したスレッドを待ち状態にする。
【００９６】
デッドロックグラフ作成部１５６は、デッドロック管理表１５３に記録されたロックの状態を読み込み、デッドロックグラフ行列１５７に、ロック要求の履歴を記録する。デッドロックグラフ行列１５７は、デッドロックの危険性を検出するための作業領域である。
【００９７】
デッドロック危険部位検出部１６０は、デッドロックグラフ行列１５７を参照し、デッドロックグラフ上の閉グラフを検出することで、デッドロックの危険部位を検出し、それをＧＵＩ１７０に表示する。
【００９８】
応急処理部１８０は、プログラムコード１９０を読み込み、デッドロック危険部位検出部１６０で検出したデッドロックが発生する危険個所に相当するプログラム部位を書き換えて、アプリケーションプログラム１２０，１３０を置換する。
【００９９】
次に、図３を参照して本実施の形態によるデッドロック予防装置の動作について詳細に説明する。
まず、アプリケーションプログラム１２０が、処理実行のリクエストを受け付ける（ステップＺ１１０）。
次に、アプリケーションプログラム１２０は、リクエストに応じてサービスを実行する（ステップＺ１２０）。
【０１００】
アプリケーションプログラムの実行中、共有資源１１０にアクセスする必要があれば、アプリケーションプログラム１２０は、ロックモニタ１４０にロックを要求する（ステップＺ１３０）。
【０１０１】
アプリケーションプログラム１２０は、ロックを獲得すると、サービスを実行する（ステップＺ１４０）。
アプリケーションプログラム１２０は、共有資源１１０が不要になると、ロックモニタ  １４０にアンロックを通知する（ステップＺ１５０）。
【０１０２】
アプリケーションプログラム１２０は、引き続きサービスを実行する（ステップＺ１６０）。
アプリケーションプログラム１２０は、一連の処理が完了すると、応答を返す（ステップＺ１７０）。さらに、ステップＺ１１０に戻り、リクエストを受け付ける。
【０１０３】
次に、図４を参照してロックモニタ１４０のロック要求処理について詳細に説明する。
まず、ロックモニタ１４０は、ロック要求を行ったスレッドのＩＤと、ロック対象オブジェクトのＩＤ、ロック命令を実行したファイル名とファイル内のアドレス（例えば、行番号）を取得する（ステップＡ１２０）。なお、以下、ロック命令を実行したファイル名とファイル内のアドレス（例えば、行番号）のことを、ロック命令個所と呼ぶ。
【０１０４】
続いて、ロックモニタ１４０は、デッドロックの危険性を検出するために、デッドロック管理表１５３にロック情報を記録するデッドロック管理処理を行う（ステップＡ１３０）。次に、ロック命令が発生した個所を記録するロックアドレス登録処理を行う（ステップＡ１４０）。
【０１０５】
続いて、ロック管理表１５５にロック情報を記録するロック管理処理を行う（ステップ  Ａ１５０）。
【０１０６】
次に、図５を参照してロックモニタ１４０のデッドロック管理処理について説明する。本処理は、ロックモニタ１４０のロック要求処理（ステップＡ１３０）から起動される。
【０１０７】
まず、デッドロックモニタ１４０は、デッドロック管理表１５３に、オブジェクトＩＤ、スレッドＩＤ、ロック命令個所を登録した、ロックアドレス表１５９の該当行ＩＤの、３つ組のデータを登録する（ステップＥ１１０）。ただし、該当する行が既に登録済みならば、登録はせずに終了する（ステップＥ１２０）。例えば、ｊａｖａ（登録商標）のように、同じスレッドから同じロック対象オブジェクトへのロック（ｊａｖａ（登録商標）の場合はｓｙｎｃｈｒｏｎｉｚｅｄ）は行わない言語の場合、ステップＥ１２０が必要となる。これは、後述のステップＣ１２５、ステップＧ１２０でも同様である。
【０１０８】
ステップＥ１２０で未登録ならば、デッドロック管理表１５３にロック対象オブジェクトＩＤ、スレッドＩＤ、およびロック要求個所が登録されたロックアドレス表１５９の該当行のエントリＩＤを登録する（ステップＥ１３０）。すなわち、デッドロック管理表１５３の該当スレッドＩＤのエントリにあるロック対象オブジェクトスタックに、ロック対象オブジェクトＩＤと、ロックアドレス表１５９の該当行ＩＤの組をプッシュして記録する。
【０１０９】
さらに、デッドロックグラフ作成部１５６が、デッドロックグラフ行列１５７に該当オブジェクトＩＤと、登録したロック対象オブジェクトＩＤを記録する（ステップＥ１４０）。
【０１１０】
次に、図６を参照してロックモニタ１４０のデッドロックアドレス登録処理について説明する。本処理は、前述のロックモニタ１４０のロック要求処理から起動される。
【０１１１】
まず、ロックモニタ１４０は、デッドロック管理表１５３にロック命令個所、すなわち、ロック発生箇所のファイル名、アドレスを登録する（ステップＧ１１０）。もし、該当ロック発生箇所のファイル名およびアドレスと同じエントリがロックアドレス管理表１５３に登録済みならば重複登録はしない（ステップＧ１２０）。
【０１１２】
ステップＧ１２０で未登録ならば、ロックモニタ１４０は、ロック命令個所、すなわち、ロック発生箇所のファイル名、アドレスを、ロックアドレス管理表１５３に記録する（ステップＧ１３０）。その後元の処理に復帰する。
【０１１３】
次に、図７を参照してロックモニタ１４０のロック管理処理について説明する。本処理は、前述のロックモニタ１４０のロック要求処理（ステップＡ１５０）から起動される。
【０１１４】
まず、ロックモニタ１４０は、ロック管理表１５５の該当箇所にロック対象オブジェクトのＩＤとロック要求を行ったスレッドのＩＤを登録する（ステップＣ１２０）。なお、既にロック管理表１５５の該当箇所に同じオブジェクトＩＤとスレッドＩＤが登録済みならば、本処理を終了し、元の処理に戻る（ステップＣ１２５）。このステップは、ｊａｖａ（登録商標）のように同じスレッドから同じロック対象オブジェクトへのロック（ｓｙｎｃｈｒｏｎｉｚｅｄ）は行わない特性を有するプログラミング言語の場合に必要である。ただし、同じオブジェクトＩＤとスレッドＩＤが既にロック要求している場合でも、別のロックをとるようなプログラム言語の場合は、ステップＣ１２５の条件判断処理を行わずに、ステップＣ１２７に進む。
【０１１５】
ロックモニタ１４０は、ロック対象オブジェクトＩＤとスレッドＩＤをロック管理表  １５５に登録する（ステップＣ１２７）。すなわち、図２１で示されるロック管理表１５５の該当ロック対象オブジェクトＩＤの線形リストの後尾に、該当スレッドＩＤを追加する。
【０１１６】
ロック管理表１５５において、各線形リストの先頭のスレッドがロックを獲得しているスレッドであり、後続のスレッドがロック待ち状態のスレッドである。
【０１１７】
次に、ロック対象オブジェクトＩＤに対して既に他のスレッドがロックを有しているか否かを、ロック管理表１５５を参照して判断する（ステップＣ１３０）。既にロック待ちならば（ｙｅｓ）、スレッドを待ち状態にする（ステップＣ１４０）。待ち状態に入ったスレッドは、他のスレッドが共有資源１１０をアンロックしないと、処理が停止したままとなる。ステップＣ１３０でロック待ちでなければ、ロック獲得状態となって元の処理に復帰する。
【０１１８】
次に、図８を参照してロックモニタ１４０のアンロック処理について説明する。本処理は、前述の図３のステップＺ１５０から起動される。
【０１１９】
まず、ロックモニタ１４０は、ロック要求を行ったスレッドのＩＤとロック対象オブジェクトのＩＤを取得する（ステップＢ１１０）。
【０１２０】
次に、ロックモニタ１４０は、デッドロック管理表１５３の該当ロック対象オブジェクトのＩＤの行から、スレッドＩＤを取り除く（ステップＢ１３０）。すなわち、デッドロック管理表１５３から、該当するスレッドＩＤのエントリが有するロック対象オブジェクトスタックをポップし、該当ロック対象オブジェクトＩＤとロックアドレス表の該当エントリＩＤの組を除去する。
【０１２１】
続いて、ロックモニタ１４０は、ロック管理表１５５を参照し、アンロックを行うためのアンロック管理処理を行う（ステップＢ１５０）。
【０１２２】
続いて、デッドロックグラフ作成部１５６は、スレッドＩＤと、除去したオブジェクトＩＤと、ロックアドレス表の該当エントリＩＤの情報に基づいてアンロック処理を行う（ステップＢ１６０）。
【０１２３】
次に、図９を参照してロックモニタ１４０のアンロック管理処理について説明する。本処理は、前述のロックモニタ１４０の動作のアンロック処理（ステップＢ１５０）から起動される。
【０１２４】
まず、ロックモニタ１４０は、ロック管理表１５５から該当ロック対象オブジェクトＩＤ、スレッドＩＤを削除する（ステップＤ１１０）。すなわち、ロック管理表１５５の、該当オブジェクトＩＤのエントリが有する線形リストからスレッドＩＤを削除する。
【０１２５】
次に、ロックモニタ１４０は、アンロックしたオブジェクトで待ち状態にあるスレッドがあるか否かを、ロック管理表１５５を参照して確認する（ステップＤ１２０）。もし、後続の待ちスレッドがあれば（ステップＤ１３０：ｙｅｓ）、待ちスレッドの１つを再開し、ロック管理表１５５のロック獲得スレッドに記録する（ステップＤ１４０）。
【０１２６】
すなわち、ステップＤ１１０〜Ｄ１４０では、ロック管理表１５５の該当ロック対象オブジェクトＩＤのエントリから、ロック獲得中の該当スレッドＩＤを取り除き、そのロック対象オブジェクトに対するロック待ちのスレッドがあれば、それをロック獲得中のスレッドとして、待ち状態から起動する。
【０１２７】
次に、図１０を参照してデッドロックグラフ作成部１５６のロック処理について説明する。本処理は、図５に示すロックモニタ１４０のデッドロック管理処理を構成するステップＥ１４０から起動される。
【０１２８】
まず、デッドロックグラフ作成部１５６は、デッドロック管理表１５３を参照し、新たにロックされたロック対象オブジェクトＩＤと、ロック要求を行ったスレッドＩＤを取得する（ステップＭ１１０）。
【０１２９】
次に、デッドロックグラフ作成部１５６は、デッドロック管理表１５３の該当スレッドＩＤのロック対象オブジェクトスタックを参照し、新たなロック対象オブジェクトと同一のオブジェクトＩＤがないか否かを調べる（ステップＭ１２０）。もし、該当するロック対象オブジェクトがなければ（ステップＭ１３０：ｎｏ）、元の処理に復帰する。該当するロック対象オブジェクトがある場合（ステップＭ１３０：ｙｅｓ）、デッドロックグラフ作成部１５６は、デッドロックグラフ行列の行（新たなロック対象オブジェクトの一つ前のロック対象オブジェクト。該当スレッドＩＤに対応したロック対象オブジェクトスタックの先頭から二番目のノードＩＤで示す行）と、列（新たなロック対象オブジェクト。スレッドＩＤに対応したロック対象オブジェクトスタックの先頭のノードＩＤで示す列）で示す行列の要素を１にする（ステップＭ１４０）。
【０１３０】
次に、デッドロックグラフ作成部１５６は、デッドロックグラフスレッド表を参照し、該当スレッドＩＤを検索する（ステップＭ１５０）。該当スレッドＩＤがある場合には（ステップＭ１６０：ｙｅｓ）、デッドロックグラフスレッド表の該当する系列ＩＤを取得する（ステップＭ１８０）。該当スレッドＩＤがある場合には（ステップＭ１６０：ｎｏ）、デッドロックグラフスレッド表に新たな行を作成し、その系列ＩＤを返す（ステップＭ１７０）。
【０１３１】
すなわち、デッドロックグラフ作成部１５６は、新たな系列ＩＤを生成し、系列ＩＤ  と、ロック要求スレッドのＩＤと、デッドロックグラフ行列１５７の行列要素で、ステップＭ１４０で値を１にした要素への参照の３つ組をデッドロックグラフスレッド表に記録する。そして、新たに生成した系列ＩＤを返す。
【０１３２】
次に、デッドロックグラフ作成部１５６は、ロック対象オブジェクトスタック内に記録されたロック対象オブジェクトと一つ前のロック対象オブジェクトのそれぞれのロックアドレス表１５９の行ＩＤを取得し、ステップＭ１４０で値を１にしたデッドロックグラフ行列１５７の要素に対応したデッドロックグラフ辺属性表に、系列ＩＤと以前のロック対象オブジェクトと新たなロック対象のそれぞれの行ＩＤの三つ組を追記する（ステップＭ１９０）。
【０１３３】
次に、図２４を参照してデッドロックグラフ作成部１５６のアンロック処理の動作ついて説明する。本処理は、図５に示すロックモニタ１４０のアンロック処理を構成するステップＥ１４０から起動される。
【０１３４】
まず、デッドロックグラフ作成部１５６は、アンロックされたロック対象オブジェクトＩＤと、アンロック要求を行ったスレッドＩＤを取得する（ステップＮ１０３）。
【０１３５】
次に、デッドロックグラフ作成部１５６は、デッドロック管理表１５３のロック対象オブジェクトスタックのうち、アンロック要求スレッドのＩＤに対応した、ロック対象オブジェクトスタックを検索し、ロック対象オブジェクトスタックが空か否かを調べる（ステップＮ１１０）。もし空でなければ（ステップＮ１１５：ｎｏ）、元の処理に復帰する。もし、空ならば（ステップＮ１１５：ｙｅｓ）、デッドロックグラフ作成部１５６は、デッドロックグラフスレッド管理表そしてデッドロックグラフ行列１５７を検索し、アンロック命令を要求したスレッドＩＤが獲得したロック対象オブジェクトの系列を取得する。
【０１３６】
このロック対象オブジェクトのＩＤの系列を新規のロック対象オブジェクト系列と呼ぶ。そして、デッドロックグラフ行列１５７で、スレッドＩＤの欄が“終了済み”になっているロック対象オブジェクト系列から、新規のロック対象オブジェクト系列と同じロック対象オブジェクトＩＤの並びであるロック対象オブジェクト系列を検索する（ステップＮ１２０）。
【０１３７】
もし、該当するロック対象オブジェクト系列があれば（ステップＮ１３０：ｙｅｓ）、デッドロックグラフ作成部１５６は、デッドロックグラフスレッド管理表からアンロック要求したスレッドＩＤの行を削除する（ステップＮ１５０）。該当するロック対象オブジェクト系列がなければ（ステップＮ１３０：ｎｏ）、デッドロックグラフスレッド管理表の該当スレッドＩＤを終了済みに変更する（ステップＮ１４０）。
【０１３８】
次に、図１２を参照してデッドロック危険部位検出部１６０の危険部位検出処理について説明する。本動作は、定期的もしくは適当なタイミングで起動される。
【０１３９】
まず、デッドロックグラフ行列１５７のうち、１が立っている行列要素を１つ選ぶ（ステップＩ１１０）。既にすべてのノードが選択済みの場合（ステップＩ１２０：ｙｅｓ）、処理を終了する。それ以外の場合（ステップＩ１２０：ｎｏ）、後述のデッドロック危険性検出処理（ステップＩ１３０）を行う。その後、ステップＩ１１０に戻り処理を繰り返す。
【０１４０】
次に、図１３を参照してデッドロック危険部位検出部１６０のデッドロック危険性検出処理について説明する。本処理は、前述のデッドロック危険部位検出部１６０の危険部位検出処理（ステップＩ１３０）から呼び出される。または、当処理から再帰的に呼び出される。その際、デッドロックグラフ行列１５７の検査対象行、すなわちグラフを構成する有向辺の出発ノード（ロック対象オブジェクト）の一つが引数として渡される。
【０１４１】
まず、その出発ノードを現ノードとし、その現ノードがデッドロック検出作業領域１６５に記録されていれば（ステップＪ１１０：ｙｅｓ）、既にデッドロック検出作業領域１６５に格納済みのノードを含み、それノード以降にデッドロック検出作業領域１６５に格納されたノードまでのノード列を、取得する。さらに、ノード列に対応したデッドロックグラフ行列１５７の該当箇所をデッドロック危険領域とする（ステップＪ１７０）。
【０１４２】
図１４の例を用いて説明する。新たにＶ４をデッドロック検出作業領域にプッシュしようとするとき、Ｖ４は既にデッドロック検出作業領域にある。このとき、デッドロックグラフ行列１５７の（Ｖ４，Ｖ１）、（Ｖ１，Ｖ３）、（Ｖ３，Ｖ４）の要素がデッドロック危険部位である。ステップＪ１７０の後は、元の処理に復帰する。
【０１４３】
ステップＪ１１０で、現ノードがデッドロック検出作業領域１６５に記録されていない場合、デッドロック危険部位検出部１６０は、現ノードのＩＤをデッドロック検出作業領域にプッシュする（ステップＪ１２０）。
【０１４４】
次に、デッドロック危険部位検出部１６０は、デッドロックグラフ行列１５７のうち、現ノードの該当行のうち、１が立っている列を選び出す（ステップＪ１３０）。もし、１が立っている列に関してすべての行き先ノードを検査済みならば（ステップＪ１４０：ｙｅｓ）、デッドロック検出作業領域にプッシュした現ノードの情報を取り出し（ステップＪ１６０）、本処理から元処理へ復帰する。
【０１４５】
ステップＪ１４０で検査未済のノードがある場合は（ｎｏ）、１が立っている列の一つが表すノードＩＤを現ノードＩＤとして引数とし、デッドロック危険性検出処理を再帰的に呼び出す（ステップＪ１５０）。
【０１４６】
次に、図１５を参照して応急処理部１８０の動作ついて説明する。本処理は、デッドロック危険部位検出部１６０が発見したデッドロック危険部位のうち、管理者がＧＵＩ１７０を介して選択したデッドロック危険部位に対して行う。
【０１４７】
まず、デッドロック危険部位検出部１６０が検出した複数のデッドロック危険部位から一つを取り出す（ステップＫ１１０）。デッドロック危険部位検出部１６０は、デッドロック危険部位、例えば“（Ｖ４，Ｖ１）、（Ｖ１，Ｖ３）、（Ｖ３，Ｖ４）”を取り出すとともに、（Ｖ４，Ｖ１）等の各辺のデッドロックグラフ行列辺属性表を参照し、辺ごとの系列ＩＤと、辺ごとのロックアドレス表１５９の行ＩＤの組が参照する複数のロック命令個所の組を複数取得する。
【０１４８】
既にすべてのデッドロック危険部位について応急処理済みならば（ステップＫ１２０：ｙｅｓ）、元の処理に復帰する。応急処理未済のデッドロック危険領域がある場合は（ｎｏ）、新たなロック対象オブジェクトＶを作成する（ステップＫ１２５）。
【０１４９】
ステップＫ１１０において、取得したデッドロック危険部位に対応した複数の系列ＩＤ  の中から一つを取り出し、それに対応するデッドロック危険部位のサブセットを取り出す。（ステップＫ１３０）。
【０１５０】
すべての系列ＩＤについて処理が完了したら（ステップＫ１４０：ｙｅｓ）、ステップＫ１１０に戻り、他のデッドロック危険部位に対して処理を行う。
【０１５１】
処理未済の系列ＩＤがある場合（ステップＫ１４０：ｎｏ）、応急処理部１８０は、デッドロッククラススレッド表の該当系列ＩＤの行を取り出し、その行が指すデッドロックグラフ行列の要素の、デッドロックグラフ辺属性表の該当系列ＩＤの行のｓｒｃノードのロック命令個所を、ロックアドレス表１５９を参照して取得する。さらに、応急処理部１８０は、プログラムコード１９０を検索し、そのロック命令箇所に対応したアンロック該当箇所を取得する（ステップＫ１５０）。
【０１５２】
先頭のロック命令個所とそれに対応するアンロック命令個所について、応急処理部１８０は、ロック対象オブジェクトＶを対象にしたロック要求命令とアンロック命令を、該当ファイルに挿入する（ステップＫ１７０）。
【０１５３】
すなわち、応急処理部１８０は、デッドロックを起こす危険性のあるロック・アンロック命令に対して、それを包含するようにロック命令を作成するため、デッドロックを防ぐことができる。図２２にロック、アンロック命令発行の時系列を示す。簡略化のため、図２２では、デッドロックが発生している例を示した図２３からデッドロックに無関係なＴ２，Ｔ３，Ｔ５を除いている。図２２は、図２３に対して、Ｔ１，Ｔ４にロック対象オブジェクトＶに対するロック命令、アンロック命令を挿入した。これにより、Ｔ４が、Ｔ１をロック待ちにし、一連の操作を実行することができる。これによりデッドロックを防ぐことができる。
【０１５４】
また、既存のロック対象オブジェクトとは別に新たなロック対象オブジェクトＶを生成するため、ロック対象オブジェクトＶに対するロックが既存のロックと干渉し、新たなデッドロックを発生することはない。ステップＫ１７０の処理が終了したら、ステップＫ１４０に戻り、次のスレッドの検査を行う。
【０１５５】
実施の形態１では、プログラムにデッドロックが発生する危険部位が存在しても、実際にデッドロックが発生しない限り、危険部位を検出することができない。しかし、実際にデッドロックが発生すると、システムがサービスを提供できない事態になる場合があるため、デッドロックの発生は事前に予知することが望ましい。実施の形態２によれば、アプリケーションプログラム１２０、１３０がロック要求を行うたびに、デッドロックグラフ作成部１５６がデッドロックグラフ行列１５７にロックの履歴を記録するため、デッドロック発生時にデッドロックを検出するだけでなく、デッドロックの危険性があるもののタイミングによりたまたまデッドロックが発生しないときも、デッドロックの危険性がある個所を指摘することができる。
【０１５６】
また、実施の形態２によれば、応急処理部１８０が、デッドロック危険部位検出部１６０が指摘したデッドロック危険個所に対してプログラムコード１９０を書き換え、デッドロック危険部位を包含するようなロック・アンロックを挿入するので、デッドロックを予防することができる。
【０１５７】
また、アプリケーションプログラム１２０，１３０にデッドロック回避のための機能を持たせなくてもデッドロックを回避できる。その理由は、アプリケーションプログラムにおけるデッドロックの危険個所を応急処理部１８０が書き換え、デッドロック危険部位に対してロック命令を挿入するためである。このコードの挿入は、応急処理部１８０が行うため、アプリケーションプログラム自体を書き換える必要がない。
【０１５８】
実施の形態３．
図２５は、本発明の実施の形態３によるデッドロック予防装置の構成を示すブロック図である。図２５に示すように、実施の形態３は、実施の形態２に加えて、プロブ挿入部１８５と、プロブ１２５，１３５を備えている。なお、実施の形態１の構成に加えて、プロブ挿入部１８５と、プロブ１２５，１３５を備えるようにしてもよい。
【０１５９】
プロブ挿入部１８５は、プログラムコード１９０からアプリケーションプログラム１２０，１３０等を配備する際に、後述のプロブ１２５，１３５をアプリケーションプログラムのロック命令の直前に、挿入する。プロブ１２５，１３５は、ロック命令が実行される直前に実行され、ロックアドレス表１５９やデッドロック管理表１５３に、ロック対象オブジェクトやロックを要求したスレッド、ロック要求したプログラムを記述したプログラムファイルとプログラムファイル中のロック命令が記述されたアドレスを記録する。
【０１６０】
次に、図２６を参照して本実施形態の全体の動作について詳細に説明する。
まず、プロブ挿入部１８５は、アプリケーションプログラム１２０，１３０を実現するプログラムコード１９０を読み込む（ステップＬ１１０）。
【０１６１】
次に、プロブ挿入部１８５は、プログラムコード１９０内のロック命令の直前にプロブ１２５，１３５を埋め込む（ステップＬ１３０）。最後に、プロブ挿入部１８５は、プロブ１２５，１３５を埋め込んだアプリケーションプログラム１２０，１３０を配備する（ステップＬ１５０）。
【０１６２】
以上のように、本実施形態によれば、プロブ挿入部１８５がプログラムを書き換え、ロック動作を記録するように構成されているため、既存のロックモニタ１４０を改造しなくても、ロックの危険性を指摘し、ロックを予防することができる。
【実施例】
【０１６３】
次に、本発明の実施例について説明する。
例えば、図３４に示すようなロック・アンロックが発生する事例を考える。時刻ｔ１において、スレッドＴ１がロック対象オブジェクトＶ４をロックする操作に関して、直前の状態と、直後の状態を比較する。【０１６４】
図３４で示すようなロック・アンロックを行うことで、時刻ｔ１において、ロックモニタ１４０は、ロック管理表１５５を図１９に示すように記録する（図４のステップＡ１５０）。ただし、実線の部分はロック管理表１５５が記録しているロック要求スレッドである。点線はアンロック済みのロック要求スレッドである。これは、説明のために記載しており、時刻ｔ１の時点では、ロック管理表１５５に記録されていない。図３４を参照すると、ロック対象オブジェクトＶ１に対し、スレッドＴ４，Ｔ２，Ｔ１の順番でロックを要求している。そのため、図１９で示すロック管理表１５５においてＶ１の行は、Ｔ４→Ｔ２→Ｔ３  →Ｔ４→Ｔ２の順番に記録される。ただし、下線はアンロック命令、下線無しはロック命令を表す。【０１６５】
最初にロックを要求したＴ４、Ｔ１はアンロックし、Ｖ１を解放しているので（図８のステップＢ１５０）、三番目にロックを要求したＴ２がオブジェクトＶ１のロックを獲得したスレッドとなる。また、前述の通り、図１９のロック管理表１５５中で、点線で書かれたスレッドはアンロック済みのスレッドで、ロック管理表１５５から削除されている。【０１６６】
図３４の時刻ｔ１でのデッドロック管理表１５３の状態を図１６に示す。ステップＡ１３０及びステップＢ１３０で示す通り、ロック要求があれば、デッドロック管理表１５３の該当スレッドＩＤのスタックにロック対象オブジェクトＩＤをプッシュし、アンロック要求があれば、ポップする。【０１６７】
図３４の時刻ｔ１において、Ｔ１がＶ３を、Ｔ３がＶ１をロックしているので、図１６のようになる。【０１６８】
図３４の時刻ｔ１における、デッドロックグラフ１５７の状態を図１７に示す。ステップＡ１５０にて、ロックモニタ１４０がロック情報をデッドロック管理表１５３に記述するたびに、デッドロックグラフ作成部１５６は、デッドロックグラフ行列１５７の該当エントリに１を記入する（図５のステップＥ１４０）。【０１６９】
図３４の時刻ｔ１において、Ｔ４がＶ４→Ｖ１→Ｖ３→Ｖ３→Ｖ１→Ｖ４とロック・アンロックを行うので、ロックが連続的に行われたＶ４→Ｖ１およびＶ１→Ｖ３の関係を、デッドロックグラフ作成部１５６はデッドロックグラフ行列１５７に記述する。すなわち、（Ｖ４，Ｖ１）、（Ｖ１，Ｖ３）の要素に１が書き込まれる。【０１７０】
また、スレッドＴ４はＶ４→Ｖ１→Ｖ３→Ｖ３→Ｖ１→Ｖ４とすべてアンロック済みなため、この順序列の先頭であるＶ４を指す、デッドロックグラフスレッド表の系列ＩＤ１の行は、スレッドＩＤが“終了済”になっている。【０１７１】
また、デッドロックグラフ行列の（Ｖ１，Ｖ３）に対応するデッドロックグラフ辺属性表には、Ｖ１に対するロックのロック命令個所である＃２とＶ２に対するロックのロック命令個所である＃６と、系列ＩＤ１が記録されている。【０１７２】
次に、図３４の時刻ｔ１におけるロックアドレス表１５９の状態を図２０に示す。ロックモニタ１４０は、ロック要求を行ったロック要求個所（ファイル名、アドレス）をロックアドレス表１５９に記録する（ステップＡ１４０）。【０１７３】
次に、図３４の時刻ｔ２においてのロック管理表１５５の状態を図２１に示す。すなわち、時刻ｔ１の後に、スレッドＴ１がオブジェクトＶ４に対してロック要求を行った例を示す。まず、ロックモニタ１４０が、ロック管理表１５５にスレッドＴ１がオブジェクトＶ４にロック要求を行ったことを登録する（ステップＡ１５０）。この操作により、図２１のロック管理表１５５のロック対象オブジェクトＶ４の行に、スレッドＴ１が加わる。【０１７４】
次に、図３４の時刻ｔ２においてのロックアドレス表１５９の状態を図２７に示す。図２０で示したロックアドレス表１５９に、ロックモニタ１４０が、ロック要求を起こしたファイル名ｃｏｍ．ｎｅｃ．ａ．Ｂと、ロック要求命令を起こしたファイル上でのアドレス  “１９”を記録する（図６のステップＧ１１０）。この行ＩＤ“＃８”を、ロックモニタ１４０が取得する。【０１７５】
次に、図３４の時刻ｔ２においてのデッドロック管理表１５３の状態を図２８に示す。ロックモニタ１４０が、デッドロック管理表１５３のスレッドＴ１に該当するロック対象オブジェクトスタックに、オブジェクトＶ４に対するロック要求というロック情報を記録する（図５のステップＥ１３０）。すなわち、ロックモニタ１４０は、図１６で示したデッドロック管理表１５３のスレッドＴ１の行に、ロックアドレス表１５９の該当するロック命令個所の行ＩＤ“＃８”と、ロック対象オブジェクトＩＤＶ４との組をプッシュする  （ステップＥ１３０）。その結果、図２８のデッドロック管理表１５３が得られる。【０１７６】
デッドロック管理表１５３が変更されると、デッドロックグラフ作成部１５６は、デッドロックグラフ行列１５７の（Ｖ３，Ｖ４）に１を記録する（図１０のステップＭ１４０）。これにより、図１７で示したデッドロックグラフ行列１５７は、図２９に示すとおりとなる。これは、図２８に示すように、デッドロック管理表１５３にプッシュされたロック対象オブジェクトＶ４の一つ前に格納されているロック対象オブジェクトがＶ３だからである。図２９のデッドロックグラフ行列１５７は、図３０のグラフと同値である。そして、図２９に示すように、デッドロッククラススレッド表にスレッドＩＤＴ１が記録されていなかったので（ステップＭ１６０）、デッドロッククラススレッド表に新たな行  （系列ＩＤ２）を追加し、デッドロックグラフ行列の要素（Ｖ３，Ｖ４）へのポインタと、スレッドＩＤＴ１を記録する（ステップＭ１８０）。これにより、図１７で示したデッドロッククラススレッド表は、図２９の通りになる。【０１７７】
そして、図２９で示すように、デッドロックグラフ作成部１５６は、デッドロックグラフ行列の要素（Ｖ３，Ｖ４）に対応するデッドロックグラフ辺属性表に対して新たな行として、系列ＩＤ２、ｓｒｃであるＶ３のロックアドレス表１５９の該当エントリ＃７と、ｄｅｓｔであるＶ４のロックアドレス表１５９の該当エントリ＃８を追記する（ステップＭ１９０）。これにより、図１７で示したデッドロックグラフ辺属性表は、図２９に示すとおりとなる。【０１７８】
デッドロック危険部位検出部１６０は、デッドロックグラフ行列１５７を参照し、閉グラフが構成されていないかどうかチェックする。例えば、図１２のステップＩ１１０において、デッドロック対象オブジェクトＶ４を選んだ場合について、図２９を用いて説明する。グラフ上の次のノードをＶ４の後、Ｖ１→Ｖ３と検索する（ステップＪ１３０）。その結果、図１４で示すように、デッドロック危険部位検出部１６０は、デッドロック検出作業領域１６５に、Ｖ４，Ｖ１，Ｖ３とロック対象オブジェクトのＩＤを記録している。【０１７９】
そして、デッドロック検出作業領域１６５に、デッドロック対象オブジェクトＶ４があることを検査する（ステップＪ１１０）。このとき、図１４に示すように、デッドロック対象オブジェクトＶ４は既にデッドロック検出作業領域１６５にあるので、デッドロックありと判別し、Ｖ４，Ｖ１，Ｖ３をデッドロック危険領域とする（ステップＪ１７０）。【０１８０】
この結果を、ＧＵＩ１７０を介して管理者に提示する。ＧＵＩの一例を図３１に示す。例えば、デッドロック危険領域としたノードのデッドロックグラフ辺属性表に記録されたロック命令個所のリストを表示したり、ロック命令個所に関係したアプリケーションプログラムのプログラムコードを表示したり、ロック防止のためのプログラムコード改変の可否を管理者に確認するためのボタンが配置される。すなわち、管理者はＧＵＩ１７０を通して、デッドロック防止用コードを挿入するかどうかを判断する。【０１８１】
応急処理部１８０は、デッドロックの危険性のある個所のプログラムコード１９０を修正し、アプリケーションプログラム１２０，１３０として再配備する。すなわち、まず、応急処理部１８０は、デッドロック対象オブジェクトＶを作成する（ステップＫ１２５）。【０１８２】
応急処理部１８０は、デッドロック危険領域としてされたデッドロックグラフ行列１５７の要素（Ｖ４，Ｖ１）、（Ｖ１，Ｖ３）、（Ｖ３，Ｖ４）について、デッドロックグラフ辺属性表を検索し、それぞれ、（１，＃１，＃２）、（１，＃２，＃６）、（２，＃７，  ＃８）の値の行を得る。系列ＩＤとしては、１及び２が含まれている。まず、そのうちの一つとして、系列１を選ぶ（ステップＫ１２５）。【０１８３】
系列ＩＤ１に関して、図２９に示すデッドロックグラフスレッド表を引くと、先頭は、（Ｖ４，Ｖ１）である。また、図２９の（Ｖ４，Ｖ１）対応するデッドロックグラフ辺属性表を参照すると、ｓｒｃであるＶ４のロックアドレス表行ＩＤは、＃１である。【０１８４】
図２７のロックアドレス表１５９を参照すると、＃１が示すロック命令個所は、ｃｏｍ．ｎｅｃ．ａ．Ａのアドレスｈｏｇｅ＠３である。そこで、応急処理部１８０は、ｃｏｍ．ｎｅｃ．ａ．Ａのアドレスｈｏｇｅ＠３でのロック命令に対応するアンロック命令をプログラムコード１９０から検索し（ステップＫ１５０）、当該ロック命令とアンロック命令を囲むように、Ｖに対するロック命令・アンロック命令を挿入する（ステップＫ１６０）。【０１８５】
続いて、系列２に関して、デッドロックグラフスレッド表を引くと、先頭は（Ｖ３，Ｖ４）である。また、（Ｖ３，Ｖ４）対応するデッドロックグラフ辺属性表を参照すると、ｓｒｃであるＶ３のロックアドレス表行ＩＤは＃７である。【０１８６】
図２７のロックアドレス表１５９を参照すると、＃３が示すロック命令個所は、ｃｏｍ．ｎｅｃ．ａ．Ｆのアドレスｇ＠３０である。そこで、ｃｏｍ．ｎｅｃ．ａ．Ｆのアドレスｇ＠３０でのロック命令に対応するアンロック個所を、プログラムコード１９０から検索し（ステップＫ１５０）、当該ロック命令とアンロック命令を囲むように、Ｖに対するロック命令・アンロック命令を挿入する（ステップＫ１６０）。【０１８７】
なお、応急処理部１８０が参照しているプログラムコード１９０の例を図３２に、書き替え後のコードの例を図３３に示す。図３３のアドレス３−５にロック命令、アドレス１４−１６にアンロック命令が挿入されている。【０１８８】
この出願は、２０１１年５月１２日に出願された日本出願特願２０１１−１０７５８８を基礎とする優先権を主張し、その開示の全てをここに取り込む。【０１８９】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１９０】
上記の実施の形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）アプリケーションプログラムのコード上で、デッドロックを発生させるロック命令を検出するデッドロック発生位置検出部と、
前記デッドロック発生位置検出部が検出した前記ロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する応急処理部を備えたデッドロック予防装置。【０１９１】
（付記２）前記デッドロック発生位置検出部は、前記アプリケーションプログラムによるロックの状態の記録情報に基づいて、デッドロックが発生したロック命令を検出することを特徴とする付記１に記載のデッドロック予防装置。【０１９２】
（付記３）前記アプリケーションプログラムからロック・アンロック要求を受信し、ロックの状態を管理するロックモニタと、
前記ロックモニタが、前記ロックの状態を管理するためのロック管理表記憶部と、
前記ロックモニタが、前記デッドロックを検出するために前記ロックの状態を記録するデッドロック管理表記憶部と、
前記ロックの状態の履歴を管理し、前記アプリケーションプログラムにおいてロックを行った箇所を記録するデッドロックグラフ行列記憶部と、
前記デッドロック管理表を参照し、前記デッドロックグラフ行列を作成するデッドロックグラフ作成部と、を備え、
前記デッドロック発生位置検出部は、前記デッドロックグラフ行列に基づいてデッドロックが発生する可能性のある位置を検出する、付記１に記載のデッドロック予防装置。【０１９３】
（付記４）前記デッドロック発生位置検出部が検出した前記位置を提示するためのＧＵＩを備えたことを特徴とする付記１から３のいずれかに記載のデッドロック予防装置。【０１９４】
（付記５）前記ロックモニタが、プログラムコード上のロック要求が発行される位置を記録するロックアドレス表記憶部を備え、
前記デッドロックグラフ作成部は、前記デッドロック管理表と前記ロックアドレス表を参照して前記デッドロックグラフ行列を作成し、
前記デッドロック発生位置検出部は、前記デッドロックグラフ行列に基づいて、デッドロック発生の可能性と、そのデッドロックを引き起こす可能性がある前記プログラムコード上のロック命令の位置を検出する、付記３に記載のデッドロック予防装置。【０１９５】
（付記６）前記デッドロック発生位置検出部が検出したデッドロック発生の可能性と、そのデッドロックを引き起こす可能性がある前記プログラムコード上のロック命令の位置を提示するためのＧＵＩを備えたことを特徴とする付記５に記載のデッドロック予防装置。【０１９６】
（付記７）前記アプリケーションプログラムに、前記アプリケーションプログラムを実行することにより前記デッドロック管理表や前記ロックアドレス表にロック情報を記録するためのプロブを埋め込むプロブ挿入部、を備えた付記１〜６のいずれかに記載のデッドロック予防装置。【０１９７】
（付記８）前記アプリケーションプログラムによるロック命令の履歴を記録するデッドロックグラフ行列記憶部と、
前記アプリケーションプログラムによるロック命令に対応するプログラムコード上のロック命令箇所を記録するロックアドレス表記憶部と、を備え、
前記応急処理部は、前記デッドロックグラフ行列に基づいて検出された前記デッドロックを発生させるロック命令に対応するロック命令箇所を、前記ロックアドレス表を参照して取得するとともに、前記プログラムコードを検索してそのロック命令箇所に対応したアンロック命令箇所を取得し、そのロック命令箇所からそのアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する、付記１に記載のデッドロック予防装置。【０１９８】
（付記９）アプリケーションプログラムのコード上で、デッドロックを発生させるロック命令を検出し、
前記検出した前記ロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する、デッドロック予防方法。【０１９９】
（付記１０）コンピュータを、
アプリケーションプログラムのコード上で、デッドロックを発生させるロック命令を検出するデッドロック発生位置検出部と、
前記デッドロック発生位置検出部が検出した前記ロック命令に対応するロック命令箇所からアンロック命令箇所までを包含するように、前記プログラムコードに新たなロック命令とアンロック命令を挿入する応急処理部と、して機能させるプログラム。
【産業上の利用可能性】
【０２００】
本発明は、共有資源を使い、クライアントの要求に応じて、コンピュータに処理を並行に実行させることに適している。
【符号の説明】
【０２０１】
１００，１０１  ＣＰＵ、１０５  メモリ、１１０  共有資源、１２０，１３０  アプリケーションプログラム、１２５，１３５  プロブ、１４０  ロックモニタ、１５０  ログＤＢ、１５３  デッドロック管理表、１５５  ロック管理表、１５６，３５６  デッドロックグラフ作成部、１５７  デッドロックグラフ行列、１５９  ロックアドレス表、１６０  デッドロック危険部位検出部、１６５  デッドロック検出作業領域、１７０  ＧＵＩ、１８０  応急処理部、１８５  プロブ挿入部、１９０  プログラムコード、３６０  デッドロック検出部
【図１】
2012153722.tif 000003
【図２】
2012153722.tif 000004
【図３】
2012153722.tif 000005
【図４】
2012153722.tif 000006
【図５】
2012153722.tif 000007
【図６】
2012153722.tif 000008
【図７】
2012153722.tif 000009
【図８】
2012153722.tif 000010
【図９】
2012153722.tif 000011
【図１０】
2012153722.tif 000012
【図１１】
2012153722.tif 000013
【図１２】
2012153722.tif 000014
【図１３】
2012153722.tif 000015
【図１４】
2012153722.tif 000016
【図１５】
2012153722.tif 000017
【図２４】
2012153722.tif 000018
【図２５】
2012153722.tif 000019
【図２６】
2012153722.tif 000020
【図１６】
2012153722.tif 000021
【図１７】
2012153722.tif 000022
【図１８】
2012153722.tif 000023
【図１９】
2012153722.tif 000024
【図２０】
2012153722.tif 000025
【図２１】
2012153722.tif 000026
【図２２】
2012153722.tif 000027
【図２３】
2012153722.tif 000028
【図２７】
2012153722.tif 000029
【図２８】
2012153722.tif 000030
【図２９】
2012153722.tif 000031
【図３０】
2012153722.tif 000032
【図３１】
2012153722.tif 000033
【図３２】
2012153722.tif 000034
【図３３】
2012153722.tif 000035
【図３４】
2012153722.tif 000036
【国際調査報告】
2012153722.tif 000037
2012153722.tif 000038
2012153722.tif 000039
2012153722.tif 000040