(57)【要約】【課題】プログラム実行環境の処理能力を維持し、デッドロックをリアルタイムに検知可能にした情報処理方法を提供する。【解決手段】プログラム実行環境のリソースにおける一部の利用を制限するロックを保持することで、その一部の利用が許可されているスレッドであるオーナースレッドと、ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとの情報を含む待ち行列グラフを記憶部に記憶させ、プログラム実行環境で発行されるイベントを受信すると、イベントに対応して待ち行列グラフを更新し、更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定し、デッドロックが発生した場合、その旨を外部に出力する。【選択図】図１
2015215722.tif 000002
【特許請求の範囲】
【請求項１】
プログラム実行環境のリソースにおける一部の利用を制限するロックを保持することで、該一部の利用が許可されているスレッドであるオーナースレッドと、前記ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとの情報を含む待ち行列グラフを記憶する記憶部と、
前記プログラム実行環境で発行されるイベントを受信する入力部と、
前記イベントに対応して前記待ち行列グラフを更新し、更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定し、デッドロックが発生した場合、その旨を外部に出力する制御部と、
を有する情報処理装置。
【請求項２】
請求項１記載の情報処理装置において、
前記入力部が、新規のスレッドが待ち行列に追加された旨のイベントを前記プログラム実行環境から受信すると、
前記制御部は、前記リソースのうち前記一部とは異なる部分に対するロックである別ロックを前記新規のスレッドが獲得している場合、該新規のスレッドを前記待ち行列グラフに追加し、前記新規のスレッドが前記別ロックを獲得していない場合、該新規のスレッドを前記待ち行列グラフに追加しない、情報処理装置。
【請求項３】
請求項２記載の情報処理装置において、
前記制御部は、前記待ちスレッドエリアにあるスレッドが保持している前記別ロックを前記オーナースレッドが獲得しようとした場合、前記デッドロックが発生したと判定する、情報処理装置。
【請求項４】
請求項１から３のいずれか１項記載の情報処理装置において、
前記待ち行列グラフは、前記スレッド毎に異なるスレッド名をキーとし、該スレッドが所属する前記待ちスレッドエリアを値に持つハッシュテーブルで管理される、情報処理装置。
【請求項５】
請求項１から４のいずれか１項記載の情報処理装置において、
前記制御部は、前記オーナースレッドが前記ロックを解放し、別のスレッドが該ロックを獲得すると、前記待ち行列グラフを再構築する、情報処理装置。
【請求項６】
記憶部を有する情報処理装置による情報処理方法であって、
プログラム実行環境のリソースにおける一部の利用を制限するロックを保持することで、該一部の利用が許可されているスレッドであるオーナースレッドと、前記ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとの情報を含む待ち行列グラフを前記記憶部に記憶させ、
前記プログラム実行環境で発行されるイベントを受信すると、該イベントに対応して前記待ち行列グラフを更新し、
更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定し、デッドロックが発生した場合、その旨を外部に出力する、情報処理方法。
【請求項７】
コンピュータに
プログラム実行環境のリソースにおける一部の利用を制限するロックを保持することで、該一部の利用が許可されているスレッドであるオーナースレッドと、前記ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとの情報を含む待ち行列グラフを記憶する手順と、
前記スレッドを処理するプログラム実行環境で発行されるイベントを受信すると、該イベントに対応して前記待ち行列グラフを更新する手順と、
更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定し、デッドロックが発生した場合、その旨を外部に出力する手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータの処理能力を維持したまま、複数タスク間で発生するデッドロックをリアルタイムに検知するための技術に関する。
【背景技術】
【０００２】
並列処理に対応したＯＳ（Operating System）上では、プログラムの最小単位であるスレッドで処理が順に実行される。複数のスレッドが並列処理される際、プログラム実行環境におけるデータやデバイス等のリソースの利用を制限するロックを取得しているスレッドが実行され、その後、ロックが解放されると、そのロックの解放を待っていた次のスレッドが実行される。このような相互排他制御でプログラムが実行される際、複数のスレッドが互いに相手のロックの解放を待ち続けるデッドロックが発生してしまうことがある。
デッドロックが発生した場合には、デッドロック状態を速やかに解除する必要があり、デッドロックの検知は重要な技術である。デッドロックを検知するための方法がいくつか知られている。
【０００３】
特許文献１には、トランザクション同期機構と連携し、ロックとリソースの関係を表す「ロック管理テーブル」と、トランザクションと要求するロックの関係を表す「リソース要求リスト」を用いて、デッドロック状態を検出する方法が開示されている。特許文献２には、ロック状態を保持する領域を作成し、獲得要求のたびにデッドロック発生の可能性を探索する方法が開示されている。特許文献３には、デッドロック状態検出のために、タスクとイベントが紐づいた管理情報を網羅的に記録することが開示されている。
別の方法として、参照カウンタやロック獲得時間、一定間隔でのタスク動作状況のサンプリングを基にして、デッドロック発生の可能性を推測する方法がある。その一例として、ウォッチドッグタイマが一定間隔で発するイベントをきっかけとして、デッドロックの発生有無を検知する方法が特許文献４に開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平５−１３４８８６号公報
【特許文献２】特開２００９−２７１８５８号公報
【特許文献３】特開２００８−２１７５６６号公報
【特許文献４】特開２０００−２５９４３３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に開示された方法では、システム上で実行中のプログラムと、そのロック保持・要求関係を網羅的に取得することで、メモリ・プロセッサともに大きなオーバーヘッドが発生し、また、特許文献２および３に開示された方法のように、リアルタイム性を重視して常にロック状態を参照すると余計なオーバーヘッドが発生し、アプリケーションの動作を阻害することがあった。
特許文献４に開示された方法では、一定間隔でデッドロックの有無をチェックするためリアルタイム性に乏しく、アプリケーションが動作不能の状態になってからそれを検知するまでにタイムラグが生じることがあった。
【０００６】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、プログラム実行環境の処理能力を維持し、デッドロックをリアルタイムに検知可能にした情報処理装置、情報処理方法、およびその方法をコンピュータに実行させるためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するための本発明の情報処理装置は、
プログラム実行環境のリソースにおける一部の利用を制限するロックを保持することで、該一部の利用が許可されているスレッドであるオーナースレッドと、前記ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとの情報を含む待ち行列グラフを記憶する記憶部と、
前記プログラム実行環境で発行されるイベントを受信する入力部と、
前記イベントに対応して前記待ち行列グラフを更新し、更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定し、デッドロックが発生した場合、その旨を外部に出力する制御部と、
を有する構成である。
【０００８】
また、本発明の情報処理方法は、記憶部を有する情報処理装置による情報処理方法であって、
プログラム実行環境のリソースにおける一部の利用を制限するロックを保持することで、該一部の利用が許可されているスレッドであるオーナースレッドと、前記ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとの情報を含む待ち行列グラフを前記記憶部に記憶させ、
前記プログラム実行環境で発行されるイベントを受信すると、該イベントに対応して前記待ち行列グラフを更新し、
更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定し、デッドロックが発生した場合、その旨を外部に出力するものである。
【０００９】
さらに、本発明のプログラムは、コンピュータに
プログラム実行環境のリソースにおける一部の利用を制限するロックを保持することで、該一部の利用が許可されているスレッドであるオーナースレッドと、前記ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとの情報を含む待ち行列グラフを記憶する手順と、
前記スレッドを処理するプログラム実行環境で発行されるイベントを受信すると、該イベントに対応して前記待ち行列グラフを更新する手順と、
更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定し、デッドロックが発生した場合、その旨を外部に出力する手順を実行させるものである。
【発明の効果】
【００１０】
本発明によれば、プログラム実行環境における処理能力を低下させることなく、デッドロックをリアルタイムに検知することができる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態の情報処理方法の手順を示すフローチャートである。
【図２】本実施形態の情報処理装置の一構成例を示すブロック図である。
【図３】待ち行列グラフの構成を説明するための図である。
【図４】本実施形態における待ち行列グラフをハッシュテーブルで管理する場合の一例を示す図である。
【図５】グラフ追加処理の手順を示すフローチャートである。
【図６】新規に待ち行列グラフを追加する場合を示す図である。
【図７】記憶部に記憶されている待ち行列グラフにスレッドを追加する場合を示す図である。
【図８Ａ】スレッドＥが既存の待ち行列グラフに追加される前のスレッド情報の一例である。
【図８Ｂ】スレッドＥが既存の待ち行列グラフに追加された場合のスレッド情報の一例である。
【図９】グラフ再構築処理の手順を示すフローチャートである。
【図１０】グラフ再構築処理の一例を説明するための図である。
【図１１】ロック解放および別スレッドのロック獲得の手順を示すフローチャートである。
【図１２】スレッド情報の他の構成例を示す図である。
【図１３】デッドロック検知処理の手順を示すフローチャートである。
【図１４】デッドロックの検知方法を説明するための図である。
【発明を実施するための形態】
【００１２】
本実施形態の情報処理装置を説明する。
図１は本実施形態の情報処理方法の手順を示すフローチャートである。図２は本実施形態の情報処理装置の一構成例を示すブロック図である。
図２に示すように、情報処理装置１０は、ＯＳおよび仮想マシン等のプログラム実行環境で発行されるイベントを受信する入力部１１と、プログラム実行環境で実行されるスレッドの待ち行列を管理するための情報を記憶する記憶部１２と、入力部１１が受信するイベントと記憶部１２が記憶する情報に基づいてデッドロック発生の有無を判定する制御部１３と、制御部１３の判定結果を出力する出力部１４とを有する。
プログラム実行環境で実行されるプログラムには、イベント発生時にイベントの内容を情報処理装置１０に通知するイベントハンドラが組み込まれている。イベントの情報には、例えば、スレッドの「待ち行列への追加」および「待ち行列からの脱出（ロックの獲得）」がある。
【００１３】
制御部１３は、本実施形態の情報処理方法の手順が記述されたプログラムを記憶するメモリ（不図示）と、メモリが記憶するプログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）（不図示）とを有する。
記憶部１２は、プログラム実行環境で実行されるスレッドの待ち行列を管理するための情報の１つとして、待ち行列グラフを記憶する。待ち行列グラフは、プログラム実行環境のリソースにおける一部の利用を制限するロックを保持し、ロックの対象部分の利用が許可されているスレッドであるオーナースレッドと、ロックの解放を直接的または間接的に待つスレッド群で構成される待ちスレッドエリアとを管理するためのグラフである。待ち行列グラフの詳細は後述する。
制御部１３は、入力部１１がプログラム実行環境からイベントを受け取ると、イベントに対応して待ち行列グラフを更新するグラフ操作機能と、更新後の待ち行列グラフを参照してデッドロックが発生したか否かを判定するデッドロック探索機能とを有する。待ち行列グラフの更新とは、グラフの追加、削除および再構築を意味する。
【００１４】
本実施形態の情報処理方法を説明する前に、待ち行列グラフについて詳しく説明する。
図３は待ち行列グラフの構成を説明するための図である。
待ち行列グラフは、ロック（モニター）を獲得しているスレッドと、そのロックの解放を待つスレッドを管理するためのグラフである。このグラフの構成要素は、「オーナースレッド」と「待ちスレッドエリア」の２つに大きく分けられる。
オーナースレッドとは、特定のロックを保持し、処理を継続しているスレッドである。たとえ１つのスレッドが２以上のロックを保有する場合であっても、１つのロックにつき、１つのスレッドしか存在しえない。図３に示すグラフでは、スレッドＡがオーナースレッドに相当する。
待ちスレッドエリアとは、オーナースレッドのロックの解放を直接的または間接的に待つスレッド群を構成するエリアである。待ちスレッドエリアを図３に破線枠で示す。図３を参照すると、スレッドＢ〜スレッドＩが待ちスレッドエリアに所属していることがわかる。この待ちスレッドエリアに所属するスレッドは全て「何らかのロックの解放待ち」であるため、処理は必ず中断されている状態となっている。例えば、複数のロックが１つのスレッドにより保持されている場合もあり得る。図３に示すケースがその一例であり、図３は、複数のロック（モニター１とモニター２）が１つのスレッドＡに保持されている場合を示す。
また、待ちスレッドエリアに所属するスレッドは、オーナースレッドが保持するロックの対象とは異なるリソース部分に対するロック（「別ロック」に相当）を獲得している。ロック獲得済みのスレッドのみが待ちスレッドエリアに登録される。
【００１５】
待ち行列グラフは、記憶部１２内の「待ち行列グラフ領域」に記憶されている。待ち行列グラフを、スレッド毎に異なるスレッド名をキーとして、所属する待ちスレッドエリアを値（value）に持つハッシュテーブルで管理してもよい。
図４は本実施形態における待ち行列グラフをハッシュテーブルで管理する場合の一例を示す図である。図４では、図３に破線枠で示した待ちスレッドエリアのエリア名を「エリアＡ」としている。図３に示すグラフにおいてオーナースレッドであるスレッドＡは待ちスレッドエリアに所属していないので、図４に示すように、スレッドエリア名の欄にはヌル値（NULL）が書き込まれている。
待ち行列グラフをハッシュテーブルで管理することにより、スレッド名をキーとして待ちスレッドエリア名を探索する探索コストをＯ（１）にすることができる。また、オーナースレッドは待ちスレッドエリアに所属することがないため、ハッシュテーブル中ではヌル値を保持させる。これにより、調査したいスレッドがオーナースレッドなのか、待ちスレッドエリア内のスレッドなのかもＯ（１）で判別できるようになる。
【００１６】
また、ポインタによる紐づけの情報を示すスレッド情報が記憶部１２に記憶されていてもよい。スレッド情報は、待ち行列のスレッドに対応して、スレッド名と、そのスレッドが解放を待つモニターと、そのスレッドのオーナースレッド名を組にして記述されたテーブルである。スレッド情報の具体例は後述する。本実施形態では、スレッド情報が記憶部１２内の「スレッド情報領域」に記憶されている場合で説明する。
図３を参照すると、図３中の矢印はポインタであり、下位のスレッドが上位のスレッダのロック（モニター）が解放されるのを待っていることを示す。例えば、スレッドＢはスレッドＡが保持するロック（モニター１）が解放されるのを待っている。このポインタによる紐づけがスレッド情報で参照可能となる。
【００１７】
次に、本実施形態の情報処理方法について図１を参照して説明する。
入力部１１は、プログラム実行環境からイベントを受信すると、イベントを制御部１３に渡す（ステップＳ１１０）。制御部１３は、入力部１１から受け取るイベントから内容を読み出し、新規にスレッドが待ち行列に追加されたか否かを判定する（ステップＳ１２０）。
ステップＳ１２０の判定の結果、イベントの情報が新規のスレッドが待ち行列に追加された内容である場合、制御部１３は、ロック獲得済みか否かを判定する（ステップＳ１３０）。ステップＳ１３０の判定の結果、新規のスレッドがロック獲得済みである場合、制御部１３は、そのスレッドを待ち行列グラフに追加する（ステップＳ１４０）。
ステップＳ１３０の判定において、新規のスレッドがロック獲得済みでない場合、そのスレッドがデッドロックのファクターになることはありえない。そのため、制御部１３は、新規のスレッドがロック獲得済みでない場合、デッドロックの可能性がないと判定し、新規のスレッドを待ち行列グラフに追加しない。このとき、制御部１３は、デッドロックの可能性がない旨を外部に出力部１４を介して出力する（ステップＳ１６０）。
ステップＳ１６０の処理の後、制御部１３は、待ち行列グラフを参照し、オーナースレッドが待ちスレッドエリア内のスレッドが保持するロックを獲得しようとしている場合、その操作はデッドロックと判定し（ステップＳ１５０）、その旨を外部に出力部１４を介して通知する。
一方、ステップ１２０の判定の結果、イベントの情報が新規のスレッドが待ち行列に追加されていない内容である場合、制御部１３は、イベントの情報が待ち行列からの脱出であるか否かを判定する（ステップＳ１７０）。ステップＳ１７０の判定の結果、イベントの情報が待ち行列からの脱出である場合、例えば、別スレッドがオーナースレッドのロックを獲得して待ち行列から脱出した場合、制御部１３は、グラフ再構築処理を行う（ステップＳ１８０）。グラフの再構築は、オーナースレッドがロックを解放し、別スレッドがロックを獲得したタイミングで行われる。
【００１８】
本実施形態では、図１に示すステップＳ１４０のグラフ追加処理の前に、グラフに追加しようとするスレッドの獲得済みロックの有無を確認し、もしロックを獲得していない場合はグラフへの追加を行わないようにしている。通常、ＯＳが管理するプロセス管理テーブルやＰＣＢは全てのプロセスやスレッドの情報を保持しているが、本実施形態では、上記の処理により、今後デッドロックを発生させる可能性があるスレッド（プロセス）のみの情報を保持しているため、情報量が少なくて済み、検索も高速になる効果が得られる。
【００１９】
次に、図１に示したフローチャートにおけるグラフ追加処理、グラフ再構築処理およびデッドロック検知処理を、具体例を用いて詳しく説明する。
はじめに、図１に示したステップＳ１４０のグラフ追加処理について説明する。
図５はグラフ追加処理の手順を示すフローチャートである。図６は新規に待ち行列グラフを追加する場合を示す図である。
図７は記憶部に記憶されている待ち行列グラフにスレッドを追加する場合を示す図である。以下では、記憶部１２に記憶されている待ち行列グラフを「既存の待ち行列グラフ」と称し、既存の待ち行列グラフに含まれる待ちスレッドエリアを「既存の待ちスレッドエリア」と称する。ただし、図７は、後で説明する、スレッドＥの追加が既に行われた後の状態を示している。
図８ＡはスレッドＥが既存の待ち行列グラフに追加される前のスレッド情報の一例である。図８ＢはスレッドＥが既存の待ち行列グラフに追加された場合のスレッド情報の一例である。
【００２０】
図１に示したステップＳ１１０において、スレッドＥがモニター３の獲得待ち状態になった旨のイベントがプログラム実行環境から入力部１１を介して制御部１３に通知される。図１に示したステップＳ１３０において、制御部１３は、スレッドＥが保持するロックを調査する。もし獲得済みロックが存在しない場合、制御部１３は、スレッドＥは今後デッドロックを発生させる可能性がないと判断し、既存グラフへの追加処理を実行しない（ステップＳ１６０）。
図７に示す場合、スレッドＥが獲得したいロックがモニター３である。そのため、図７に示す場合では、制御部１３は、スレッドＥが獲得したいロック（モニター３）のオーナースレッドを調査し、それがスレッドＢであることを確定する（図５に示すステップＳ２１０）。
図５のステップＳ２２０において、制御部１３は、スレッドＢが既存の待ち行列グラフに存在するか否かを判定する。判定の結果、スレッドＢが既存の待ち行列グラフに存在していない場合、制御部１３は、図６に示すように、スレッドＢをオーナースレッドとし、スレッドＢが保持するモニター３をスレッドＥがポイントする形でグラフを作成する（ステップＳ２４０）。待ち行列グラフをハッシュテーブルで管理している場合、制御部１３は、スレッドＢとスレッドＥをハッシュテーブルに追加する。
一方、ステップＳ２２０の判定の結果、スレッドＢが既存の待ち行列グラフに存在する場合、制御部１３は、図７に示すように、スレッドＥがスレッドＢをポイントする形で既存の待ち行列グラフを更新する（ステップＳ２３０）。また、制御部１３は、図８Ｂに示すように、スレッド情報にスレッドＥを追加する（ステップＳ２３０）。待ち行列グラフをハッシュテーブルで管理している場合、制御部１３は、スレッドＥをハッシュテーブルに追加する。
なお、図４に示したハッシュテーブルおよび図８Ｂに示したスレッド情報は、待ち行列グラフを記憶部１２に保存するための手段の一例である。
【００２１】
次に、図１に示したステップＳ１８０のグラフ再構築処理の動作を詳しく説明する。
図９はグラフ再構築処理の手順を示すフローチャートである。図１０はグラフ再構築処理の一例を説明するための図である。ここでは、複数の待ち行列グラフを含むグラフを「ロック待ちグラフ」と称する。
図１に示したステップＳ１１０で受信したイベントが競合モニター取得（Monitor Contended Entered）である場合（図９に示すステップＳ１０１０）、ステップＳ１０２０において、制御部１３は、取得したイベントを参照することで、新しくモニターを取得したスレッドを認識すると、そのスレッドをキーにロック待ちグラフを探索し、そのスレッドが所属する待ちスレッドエリアを識別する。
続いて、制御部１３は、Ｓ１０２０で取得した待ちスレッドエリアのオーナースレッドを取得する（ステップＳ１０３０）。制御部１３は、ステップＳ１０４０の処理に進み、Ｓ１０３０で取得した旧オーナースレッドから、リリースされたモニターを削除し、新しく取得したスレッド（図６を参照して説明した「待ち行列グラフの追加処理」で渡されるスレッド）に割り当てる。
【００２２】
ステップＳ１０５０において、制御部１３は、旧オーナースレッドが保持するモニターは存在するか判断する。判定の結果、もし旧オーナースレッドが保持するモニターが存在する場合、制御部１３は、新しくロック待ちグラフを作成し、そのモニターを待っているスレッドすべてを新しいロック待ちグラフに所属するよう、ハッシュテーブルのｖａｌｕｅ（所属する待ちスレッドエリア）を更新する（ステップＳ１０６０）。一方、ステップＳ１０５０の判定の結果、もし旧オーナースレッドが保持するモニターが存在しなくなった場合、制御部１３は、ロック待ちグラフから旧オーナースレッドを削除する（ステップＳ１０７０）。
その後、制御部１３は、ロック待ちグラフ上で、まだ旧オーナースレッドを親とするスレッドが存在するか判断する（ステップＳ１０８０）。続いて、制御部１３は、ロック待ちグラフ上でまだ旧オーナースレッドを親とするスレッドが存在する場合、そのオーナースレッドを新オーナーとして更新する（ステップＳ１０９０）。
【００２３】
次に、グラフ再構築処理の別の例として、ロック解放および別スレッドのロック獲得の処理を説明する。
図１１はロック解放および別スレッドのロック獲得の手順を示すフローチャートである。
スレッドＢがモニター１を獲得できた旨のイベントがプログラム実行環境から入力部１１を介して制御部１３に通知される（リソース獲得のイベント受信）（ステップＳ３１０）。
ステップＳ３１０で受信したイベントが発行された時点で、それまでのオーナースレッドであるスレッドＡは、獲得していたモニター１を解放したことになる。そのため、制御部１３は、既存の待ちスレッドエリアからスレッドＢをオーナースレッドに昇格させ（ステップＳ３２０）、付随する待ちスレッドエリアの再構築を行う（ステップＳ３３０）。ただし、グラフの再構築範囲は次の（ａ）〜（ｃ）の３点のみに限定される。そのため、オーバーヘッドを極力抑えることが可能である。
（ａ）ロック解放スレッドにまだ待ちスレッドエリアが存在する場合、制御部１３は、待ちスレッドエリアの分離し、関連するハッシュテーブルエントリの更新を行う。
（ｂ）制御部１３は、オーナースレッドをロック獲得スレッドに置き換え、関連するハッシュテーブルエントリの更新を行う。
（ｃ）制御部１３は、当該ロックをロック獲得スレッドに移動させる。
制御部１３は、上記のようにして、待ちスレッドエリアの再構築を行った後、当該ロックを待機するスレッドがあるか否かを判定し（ステップＳ３４０）、待機するスレッドがなくなった場合、当該グラフを削除する（ステップＳ３５０）。
【００２４】
図１０を参照すると、手順１「待ちスレッドエリアの分離」→手順２「オーナースレッドへの昇格」→手順３「所有ロックの移動」が模式的に示されている。手順１において、スレッドＡとスレッドＡに紐づけされたスレッドＤが元の待ち行列グラフから分離され、新規に待ち行列グラフが追加されている。手順２において、スレッドＢがオーナースレッドに昇格している。手順３では、スレッドＡが保持していたモニター１がスレッドＢに移動している。
【００２５】
なお、各スレッドが保有しているモニターの情報をスレッド情報に記録するようにしてもよい。図１２はスレッド情報の他の構成例を示す図である。図１２を参照すると、スレッドＡ〜スレッドＩのそれぞれについて、保有するモニターがスレッド情報に記録されている。
【００２６】
次に、図１に示したステップＳ１５０のデッドロック検知処理を説明する。
図１３はデッドロック検知処理の手順を示すフローチャートである。図１４はデッドロックの検知方法を説明するための図である。
図１４に示すもののうち、スレッドＡのみが実行可能状態で、他のスレッドはそれぞれ関連するロック（モニター１〜モニター１２までのいずれか）の獲得待ちで処理中断状態となっている。
図１に示したステップＳ１１０において、スレッドＡがモニター１２の獲得待ち状態になった旨のイベントがプログラム実行環境から入力部１１を介して制御部１３に通知される（待ち行列追加イベントの受信）。
制御部１３は、スレッドＡの保持するロックを調査する（ステップＳ１３０）。もし獲得済みロックが存在しない場合、制御部１３は、当該スレッドは今後デッドロックを発生させる可能性はないと判断し、ハッシュテーブルおよびスレッド情報のいずれにも登録しない（ステップＳ１６０）。
ステップＳ１４０の処理の後、制御部１３は、スレッドＡが獲得したいロック（モニター１２）のオーナースレッドを調査し、それがスレッドＩであることを確定する（図１３に示すステップＳ４１０）。制御部１３は、スレッドＩをハッシュテーブルから探索し、スレッドＡをオーナー（待ち行列の先頭）とする待ちスレッドエリアに所属していることを確定する（ステップＳ４２０）。制御部１３は、待ち行列の先頭がスレッドＡであること、またその最後尾に再びスレッドＡが追加されようとしていることから、デッドロック状態が発生したと確定し、その旨を外部へ出力部１１を介して通知する（ステップＳ４３０）。
【００２７】
本実施形態では、オーナースレッドと待ち行列のスレッドを待ち行列グラフとして管理することで、プログラム実行環境から通知されるイベントをトリガにして、待ち行列グラフに対してＯ（１）でデッドロックを探索している。イベントドリブンでグラフの更新およびデッドロック探索を行うので、動作のきっかけが最小限に抑えられる。イベントを発行するプログラム実行環境に対して処理能力を低下させることもない。また、デッドロックを起こし得ないスレッドを管理対象から除外し、デッドロック検知のために管理すべき情報を絞り込むことで、限られた情報をグラフの端点（所属する待ちスレッドエリアと、そのオーナースレッド）を確認するだけの作業となるため、リアルタイムにデッドロックを検出することが可能となる。リアルタイムなデッドロック検知が可能なため、ミッションクリティカルシステムにおいてダウンタイムを短くすることができる。消費するＣＰＵリソースを最小限にすることができる。
【００２８】
また、デッドロックを起こし得ないスレッドを管理対象から除外し、デッドロック検知のために管理すべき情報をオーナースレッドと待ちスレッドエリアの２つに大別して管理し、グラフの構成要素を全てポインタで紐づけている。待ちスレッドエリアで管理される情報がロックを獲得しているスレッドとそのロックに関連する情報のみとなるため、メモリ使用量を削減することができ、ロックの関係把握を従来よりも低い管理コストで実現することが可能となる。
さらに、本実施形態の情報処理方法は、ロック関連イベントが通知される実行環境であれば後付けで実現できる手法であるため、既存システムに容易に導入することができる。
【符号の説明】
【００２９】
１０    情報処理装置
１１    入力部
１２    記憶部
１３    制御部
１４    出力部
【図１】
2015215722.tif 000003
【図２】
2015215722.tif 000004
【図３】
2015215722.tif 000005
【図４】
2015215722.tif 000006
【図５】
2015215722.tif 000007
【図６】
2015215722.tif 000008
【図７】
2015215722.tif 000009
【図８Ａ】
2015215722.tif 000010
【図８Ｂ】
2015215722.tif 000011
【図９】
2015215722.tif 000012
【図１０】
2015215722.tif 000013
【図１１】
2015215722.tif 000014
【図１２】
2015215722.tif 000015
【図１３】
2015215722.tif 000016
【図１４】
2015215722.tif 000017