(57)【要約】【課題】効率的にデッドロックを検知すること。【解決手段】第一の実行主体が前記情報資源へのアクセス占有権を獲得している状態においてそのアクセス占有権の獲得を試みた第二の実行主体が、所定のタイミングまでにそのアクセス占有権を獲得したか否かを判断し、前記所定のタイミングまでに獲得していないと判断された場合に、前記第一の実行主体と前記第二の実行主体とを含む複数の実行主体が獲得しているアクセス占有権のうち、自身の獲得しているアクセス占有権を除く他のアクセス占有権の少なくとも何れかのアクセス占有権の獲得を、前記複数の実行主体それぞれが試み、前記複数の実行主体が獲得しているアクセス占有権それぞれが、前記複数の実行主体の少なくとも何れかによる獲得待ち状態であるか否かを判断し、前記獲得待ち状態であると判断された場合に、情報処理が実行途中で停止していると判定する。【選択図】図１
2015075871.tif 000002
【特許請求の範囲】
【請求項１】
情報処理を実行する複数の実行主体から共通してアクセスされ得る情報資源に排他的にアクセスするための権利であるアクセス占有権の獲得を試みた実行主体のうち一の実行主体に対してのみ前記アクセス占有権を獲得させ、前記一の実行主体からの前記情報資源へのアクセスが完了すると、前記一の実行主体に前記アクセス占有権を解放させることで、前記一の実行主体のみが前記情報資源に排他的にアクセスするように制御する排他制御プログラムであって、
第一の実行主体が前記情報資源へのアクセス占有権を獲得した後、前記第一の実行主体が前記情報資源へのアクセス占有権を獲得している状態において前記情報資源へのアクセス占有権の獲得を試みた第二の実行主体が、所定のタイミングまでに前記第一のアクセス占有権を獲得したか否かを判断するアクセス占有権獲得判断処理ステップと、
前記第二の実行主体が前記所定のタイミングまでに前記情報資源へのアクセス占有権を獲得していないと判断された場合に、前記第一の実行主体と前記第二の実行主体とを含む複数の実行主体を選択する実行主体選択処理ステップと、
選択された前記複数の実行主体が獲得しているアクセス占有権のうち、自身の獲得しているアクセス占有権を除く他のアクセス占有権の少なくとも何れかのアクセス占有権の獲得を、前記複数の実行主体それぞれが試み、前記複数の実行主体が獲得しているアクセス占有権それぞれが、前記複数の実行主体の少なくとも何れかにより獲得を待たれている獲得待ち状態であるか否かを判断する獲得待機状態判断処理ステップと、
前記獲得待ち状態であると判断された場合に、前記情報処理が実行途中で停止していると判定する実行停止判定処理ステップと、
を実行することを特徴とする排他制御プログラム。
【請求項２】
前記実行主体選択処理ステップは、前記第二の実行主体が前記所定のタイミングまでに前記情報資源へのアクセス占有権を獲得していないと判断された場合に、前記第一の実行主体と前記第二の実行主体とを選択するステップを実行し、
前記獲得待機状態処理ステップは、選択された前記第一の実行主体がアクセス占有権の獲得を試みた情報資源が、選択された前記第二の実行主体がアクセス占有権を獲得している情報資源と同一であるか否かを判断するステップを実行することを特徴とする請求項１に記載の排他制御プログラム。
【請求項３】
実行主体が情報資源へのアクセス占有権を獲得する際に、その実行主体がその情報資源へのアクセス占有権を獲得するまでに実行された情報処理の実行過程に関する情報を取得する実行過程情報取得処理ステップを実行することを特徴とする請求項１又は２に記載の排他制御プログラム。
【請求項４】
前記情報処理が実行途中で停止していると判定された際に、取得された前記情報処理の実行過程に関する情報を出力する実行過程情報出力処理ステップを実行することを特徴とする請求項３に記載の排他制御プログラム。
【請求項５】
請求項１乃至４いずれか１項に記載の排他制御プログラムがインストールされたことを特徴とする情報処理装置。
【請求項６】
情報処理を実行する複数の実行主体から共通してアクセスされ得る情報資源に排他的にアクセスするための権利であるアクセス占有権の獲得を試みた実行主体のうち一の実行主体に対してのみ前記アクセス占有権を獲得させ、前記一の実行主体からの前記情報資源へのアクセスが完了すると、前記一の実行主体に前記アクセス占有権を解放させることで、前記一の実行主体のみが前記情報資源に排他的にアクセスするように制御する排他制御方法であって、
第一の実行主体が情報資源へのアクセス占有権を獲得した後、前記第一の実行主体が前記情報資源へのアクセス占有権を獲得している状態において前記情報資源へのアクセス占有権の獲得を試みた第二の実行主体が、所定のタイミングまでに前記第一のアクセス占有権を獲得したか否かを判断し、
前記第二の実行主体が前記所定のタイミングまでに前記情報資源へのアクセス占有権を獲得していないと判断された場合に、前記第一の実行主体と前記第二の実行主体とを含む複数の実行主体を選択し、
選択された前記複数の実行主体が獲得しているアクセス占有権のうち、自身の獲得しているアクセス占有権を除く他のアクセス占有権の少なくとも何れかのアクセス占有権の獲得を、前記複数の実行主体それぞれが試み、前記複数の実行主体が獲得しているアクセス占有権それぞれが、前記複数の実行主体の少なくとも何れかにより獲得を待たれている獲得待ち状態であるか否かを判断し、
前記獲得待ち状態であると判断された場合に、前記情報処理が実行途中で停止していると判定することを特徴とする排他制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、排他制御プログラム、情報処理装置、排他制御方法に関し、特に、デッドロックの効率的な検知方法に関する。
【背景技術】
【０００２】
通常、ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）やサーバ、画像形成装置等の情報処理装置にインストールされて使用されるオペレーティング・システムには、プロセスやスレッド、タスク等、情報処理を実行する複数の実行主体が同時に同一の情報資源にアクセスすることを避けるために排他制御機能が搭載されている。ここで、情報資源とは、実行主体が処理を実行する際に使用するデータ等の要素や、実行主体が処理を実行する際に共通して利用する特殊なメモリ領域のことである。
【０００３】
このような排他制御機能により、オペレーティング・システムは、特定の実行主体のみが排他的に情報資源にアクセスするように制御することができ、複数の実行主体が同じデータを同時に書き換えることにより発生する不整合を防ぐことができるようになっている。
【０００４】
このような排他制御機能が搭載されているオペレーティング・システムにおいては、実行主体から排他的にアクセスされるべき情報資源にロックと呼ばれるアクセス占有権が予め紐付けられている。そして、このようなオペレーティング・システムにおいて、各実行主体がその情報資源にアクセスする際には、それら各実行主体が上記ロックの獲得を試み、ロックを獲得することができた実行主体のみがその情報資源にアクセスすることができるようになっている。
【０００５】
このとき、ロックの獲得ができなかった他の実行主体は、ロック獲得に成功して上記情報資源へアクセスしている実行主体がその情報資源へのアクセスを完了してロックを解放するまで待たされることになる。その後、情報資源へのアクセスが完了した実行主体はロックを解放し、これにより、ロック獲得待ちの他の実行主体がロックを獲得することができるようになる。
【０００６】
このようなロック機能により、通常のオペレーティング・システムにおいては、特定の実行主体のみが排他的に上記情報資源にアクセスするので、複数の実行主体が同時に同一の情報資源にアクセスすることを回避することができ、上記不整合の発生を防ぐことが可能となる。
【０００７】
ところで、このようなロック機能が搭載されたオペレーティング・システムにおいて、デッドロックと呼ばれる不具合が発生することが知られている。デッドロックとは、複数の実行主体それぞれが互いに相手の実行主体が獲得しているロックが解放されてそのロックを獲得するまで処理が完了しないような一連の処理において発生し、複数の実行主体それぞれが互いに相手の獲得しているロックの解放を待ってしまい、処理が停止してしまうといった不具合のことである。
【０００８】
例えば、情報資源Ａへのアクセスが完了した後に情報資源Ｂに紐付けられているロックｂを獲得することで処理が完了する実行主体αと、情報資源Ｂへのアクセスが完了した後に情報資源Ａに紐付けられているロックａを獲得することで処理が完了する実行主体βとが並列に処理を実行するとする。このような場合まず、実行主体αが情報資源Ａに、実行主体βが情報資源Ｂにそれぞれ排他的にアクセスすることになる。
【０００９】
そして、実行主体α、実行主体βはそれぞれ情報資源Ａ、情報資源Ｂへのアクセスを完了すると、次に、それぞれロックｂ、ロックａの獲得を試みるが、互いに相手が獲得しているロックが解放されるのを待ってしまい、即ち、実行主体αがロックｂの解放を、実行主体βがロックαの解放を待ってしまい、どちらも処理が停止してしまう。このようなデッドロックは、発生要因が各実行主体の処理タイミングに強く依存し、実行主体や情報資源に不具合が無くても発生するため、原因不明の不具合として検知されないことが多い。
【００１０】
そこで、実行主体がロックの獲得を試みる度に、後述するデッドロック検知処理を実行することでデッドロックの発生を検知するデッドロック検知方法が開示され既に知られている（例えば、特許文献１参照）。このようなデッドロック検知方法でデッドロックの発生を検知する場合、オペレーティング・システムは、実行主体によるロックの獲得状況及び獲得待ち状況を、方向性を持つ矢印で示すことにより構成される有向グラフにおいてループが形成されているか否かを判断することでデッドロックの発生を検知するといったデッドロック検知処理を実行するようになっている。
【００１１】
例えば、上記実行主体α及び実行主体βについてのデッドロックを例にすると、「実行主体αは、ロックａを獲得し、かつ、ロックｂの獲得待ちの状態にあり、実行主体βは、ロックｂを獲得し、かつ、ロックａの獲得待ちの状態にある」という関係が成り立つ。そのため、このような場合には、有向グラフにおいて、「実行主体α→ロックａ→実行主体β→ロックｂ→実行主体α」といったループが形成されることになる。ここで、実行主体からロックへの矢印は、矢印元の実行主体が矢印先のロックを獲得していることを表し、ロックから実行主体への矢印は、矢印先の実行主体が矢印元のロックを獲得待ちであることを表す。
【００１２】
そして、このように、上記有向グラフにおいてループが形成されると、オペレーティング・システムは、デッドロック検知処理において、デッドロックが発生したことを検知することになる。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ところが、このようなデッドロック検知方法では、オペレーティング・システムは、実行主体がロックの獲得を試みる度に上記デッドロック検知処理を実行するため、デッドロック検知の効率が悪いといった問題がある。
【００１４】
また、このようなデッドロック検知方法では、オペレーティング・システムは、数百、数千といった多数の実行主体が並列に処理を実行することで、一つのロックに対してそれら多数の実行主体が獲得を試みるような場合であっても、実行主体がロックの獲得を試みる度に上記デッドロック検知処理を実行するため、デッドロック検知の効率がさらに悪いといった問題がある。
【００１５】
尚、このような問題は、情報処理装置にインストールされて使用されるオペレーティング・システムに限らず、複数の実行主体がそれぞれ同一の複数の情報資源にアクセスするプログラムであれば、どのようなプログラムでも発生し得る問題である。
【００１６】
本発明は、効率的にデッドロックを検知することを目的とする。
【課題を解決するための手段】
【００１７】
上記課題を解決するために、情報処理を実行する複数の実行主体から共通してアクセスされ得る情報資源に排他的にアクセスするための権利であるアクセス占有権の獲得を試みた実行主体のうち一の実行主体に対してのみ前記アクセス占有権を獲得させ、前記一の実行主体からの前記情報資源へのアクセスが完了すると、前記一の実行主体に前記アクセス占有権を解放させることで、前記一の実行主体のみが前記情報資源に排他的にアクセスするように制御する排他制御プログラムであって、第一の実行主体が前記情報資源へのアクセス占有権を獲得した後、前記第一の実行主体が前記情報資源へのアクセス占有権を獲得している状態において前記情報資源へのアクセス占有権の獲得を試みた第二の実行主体が、所定のタイミングまでに前記第一のアクセス占有権を獲得したか否かを判断するアクセス占有権獲得判断処理ステップと、前記第二の実行主体が前記所定のタイミングまでに前記情報資源へのアクセス占有権を獲得していないと判断された場合に、前記第一の実行主体と前記第二の実行主体とを含む複数の実行主体を選択する実行主体選択処理ステップと、選択された前記複数の実行主体が獲得しているアクセス占有権のうち、自身の獲得しているアクセス占有権を除く他のアクセス占有権の少なくとも何れかのアクセス占有権の獲得を、前記複数の実行主体それぞれが試み、前記複数の実行主体が獲得しているアクセス占有権それぞれが、前記複数の実行主体の少なくとも何れかにより獲得を待たれている獲得待ち状態であるか否かを判断する獲得待機状態判断処理ステップと、前記獲得待ち状態であると判断された場合に、前記情報処理が実行途中で停止していると判定する実行停止判定処理ステップと、を実行することを特徴とする。
【００１８】
また、本発明の他の態様は、情報処理装置であって、上記排他制御プログラムがインストールされたことを特徴とする。
【００１９】
また、本発明の更に他の態様は、情報処理を実行する複数の実行主体から共通してアクセスされ得る情報資源に排他的にアクセスするための権利であるアクセス占有権の獲得を試みた実行主体のうち一の実行主体に対してのみ前記アクセス占有権を獲得させ、前記一の実行主体からの前記情報資源へのアクセスが完了すると、前記一の実行主体に前記アクセス占有権を解放させることで、前記一の実行主体のみが前記情報資源に排他的にアクセスするように制御する排他制御方法であって、第一の実行主体が情報資源へのアクセス占有権を獲得した後、前記第一の実行主体が前記情報資源へのアクセス占有権を獲得している状態において前記情報資源へのアクセス占有権の獲得を試みた第二の実行主体が、所定のタイミングまでに前記第一のアクセス占有権を獲得したか否かを判断し、前記第二の実行主体が前記所定のタイミングまでに前記情報資源へのアクセス占有権を獲得していないと判断された場合に、前記第一の実行主体と前記第二の実行主体とを含む複数の実行主体を選択し、選択された前記複数の実行主体が獲得しているアクセス占有権のうち、自身の獲得しているアクセス占有権を除く他のアクセス占有権の少なくとも何れかのアクセス占有権の獲得を、前記複数の実行主体それぞれが試み、前記複数の実行主体が獲得しているアクセス占有権それぞれが、前記複数の実行主体の少なくとも何れかにより獲得を待たれている獲得待ち状態であるか否かを判断し、前記獲得待ち状態であると判断された場合に、前記情報処理が実行途中で停止していると判定することを特徴とする。
【発明の効果】
【００２０】
本発明によれば、効率的にデッドロックを検知することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施形態に係る情報処理装置のハードウェア構成を模式的に示すブロック図である。
【図２】本発明の実施形態に係る情報処理装置の機能構成を模式的に示すブロック図である。
【図３】本発明の実施形態に係るロックのデータ構造を説明するための図である。
【図４】本発明の実施形態に係る実行主体のデータ構造を説明するための図である。
【図５】本発明の実施形態に係るオペレーティング・システムがロック獲得処理を行う際の処理を説明するためのフローチャートである。
【図６】本発明の実施形態に係るオペレーティング・システムがロック獲得処理を行う際の処理を説明するためのフローチャートである。
【図７】本発明の実施形態に係るオペレーティング・システムが関数戻りアドレス登録処理を行う際の処理を説明するためのフローチャートである。
【図８】本発明の実施形態に係るオペレーティング・システムがロック解放処理を行う際の処理を説明するためのフローチャートである。
【図９】本発明の実施形態に係るオペレーティング・システムがデッドロック可能性判定処理を行う際の処理を説明するためのフローチャートである。
【図１０】本発明の実施形態に係るオペレーティング・システムがデッドロック判定処理を行う際の処理を説明するためのフローチャートである。
【図１１】本実施形態に係る有向グラフの一例を示す図である。
【図１２】本実施形態に係る組み合わせリストの一例を示す図である。
【図１３】本実施形態に係る有向グラフの一例を示す図である。
【図１４】本発明の実施形態に係るオペレーティング・システムがデバッグ情報出力処理を行う際の処理を説明するためのフローチャートである。
【図１５】本実施形態に係る組み合わせリストの一例を示す図である。
【図１６】本実施形態に係る有向グラフの一例を示す図である。
【図１７】本実施形態に係る組み合わせリストの一例を示す図である。
【図１８】本実施形態に係る有向グラフの一例を示す図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照して、本発明の実施形態を詳細に説明する。本実施形態においては、排他制御プログラムとして、ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）やサーバ、画像形成装置等の情報処理装置にインストールされて使用されるオペレーティング・システムを例として説明する。
【００２３】
本実施形態に係るオペレーティング・システムは、プロセスやスレッド、タスク等、情報処理を実行する情報処理を実行する複数の実行主体から共通してアクセスされ得る情報資源に排他的にアクセスするための権利であるアクセス占有権の獲得を試みた実行主体のうち一の実行主体に対してのみ前記アクセス占有権を獲得させ、前記一の実行主体からの前記情報資源へのアクセスが完了すると、前記一の実行主体に前記アクセス占有権を解放させることで、前記一の実行主体のみが前記情報資源に排他的にアクセスするように制御する。ここで、情報資源とは、実行主体が処理を実行する際に使用するデータ等の要素や、実行主体が処理を実行する際に共通して利用する特殊なメモリ領域のことである。
【００２４】
具体的には、本実施形態に係るオペレーティング・システムにおいては、実行主体から排他的にアクセスされるべき情報資源にロックと呼ばれるアクセス占有権が予め紐付けられている。そして、このようなオペレーティング・システムにおいて、各実行主体がその情報資源にアクセスする際には、それら各実行主体が上記ロックの獲得を試み、ロックを獲得することができた実行主体のみがその情報資源にアクセスすることができるようになっている。
【００２５】
このとき、ロックの獲得ができなかった他の実行主体は、ロック獲得に成功して上記情報資源へアクセスしている実行主体がその情報資源へのアクセスを完了してロックを解放するまで待たされる。その後、情報資源へのアクセスが完了した実行主体はロックを解放し、これにより、ロック獲得待ちの他の実行主体がロックを獲得することができるようになる。
【００２６】
このようなロック機能により、本実施形態に係るオペレーティング・システムにおいては、特定の実行主体のみが排他的に上記情報資源にアクセスするので、複数の実行主体が同時に同一の情報資源にアクセスすることを回避することができ、同じデータを複数の実行主体が同時に書き換えることによる発生する不整合を防ぐことが可能となっている。
【００２７】
このように構成されたオペレーティング・システムにおいて、本実施形態に係る要旨の一つは、一の実行主体に獲得されており、かつ、他の実行主体から獲得待ちされているロックであって、上記一の実行主体に獲得されてから所定時間経過しても上記他の実行主体に獲得されていないロックのみを対象として、デッドロックを引き起こしているか否かを判定するためのデッドロック判定処理を実行することにある。これにより、本実施形態に係るオペレーティング・システムによれば、効率的にデッドロックを検知することが可能となる。
【００２８】
まず、本実施形態に係るオペレーティング・システム１００がインストールされる情報処理装置１を構成するハードウェアについて、図１を参照して説明する。図１は、本実施形態に係る情報処理装置１のハードウェア構成を模式的に示すブロック図である。
【００２９】
図１に示すように、本実施形態に係る情報処理装置１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２０、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）４０及びＩ／Ｆ５０がバス８０を介して接続されている。また、Ｉ／Ｆ５０にはＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）６０及び操作部７０が接続されている。
【００３０】
ＣＰＵ１０は演算手段であり、情報処理装置１全体の動作を制御する。ＲＡＭ２０は、情報の高速な読み書きが可能な揮発性の記憶媒体であり、ＣＰＵ１０が情報を処理する際の作業領域として用いられる。ＲＯＭ３０は、読み出し専用の不揮発性記憶媒体であり、ファームウェア等のプログラムが格納されている。ＨＤＤ４０は、情報の読み書きが可能な不揮発性の記憶媒体であり、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）や各種の制御プログラム、アプリケーション・プログラム等が格納される。
【００３１】
Ｉ／Ｆ５０は、バス８０と各種のハードウェアやネットワーク等を接続し制御する。ＬＣＤ６０は、利用者が情報処理装置１の状態を確認するための視覚的利用者インタフェースである。操作部７０は、キーボード、マウス、各種のハードボタン、タッチパネル等、利用者が情報処理装置１に情報を入力するためのユーザインタフェースである。
【００３２】
このようなハードウェア構成において、ＲＯＭ３０やＨＤＤ４０若しくは図示しない光学ディスク等の記憶媒体に格納されたプログラムがＲＡＭ２０に読み出され、ＣＰＵ１０がそれらのプログラムに従って演算を行うことによりソフトウェア制御部が構成される。このようにして構成されたソフトウェア制御部と、ハードウェアとの組み合わせによって、本実施形態に係る情報処理装置１の機能を実現する機能ブロックが構成される。
【００３３】
次に、本実施形態に係る情報処理装置１の機能構成について、図２を参照して説明する。図２は、本実施形態に係る情報処理装置１の機能構成を模式的に示すブロック図である。図２に示すように、本実施形態に係る情報処理装置１には、オペレーティング・システム１００がインストールされている。また、図２に示すように、本実施形態に係る情報処理装置１は、タイマ２００、スタック３００、実行主体４００、情報資源５００、ロック６００を含む。
【００３４】
オペレーティング・システム１００は、情報処理装置１にインストールされて、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等のプロセッサによる演算処理により、ロック獲得処理部１０１、ロック解放処理部１０２、デッドロック可能性判定処理部１０３、デッドロック判定処理部１０４、デバッグ情報出力処理部１０５、実行主体管理部１０６、情報資源管理部１０７、ロック管理部１０８を構成する。
【００３５】
ロック獲得処理部１０１は、情報資源に紐付けられているロックを実行主体が獲得する際の処理であるロック獲得処理を行う。ロック解放処理部１０２は、実行主体が獲得しているロックを解放する際の処理であるロック解放処理を行う。デッドロック可能性判定処理部１０３は、所定の条件を満たしているロックを対象にして、そのロックがデッドロックを引き起こしている可能性があるか否かを判定する際の処理であるデッドロック可能性判定処理を行う。ここで、所定の条件を満たしているロックとは、ある実行主体に獲得されており獲得待ちである他の実行主体があるロックのことである。
【００３６】
デッドロック判定処理部１０４は、デッドロック可能性判定処理においてデッドロックを引き起こしている可能性があると判定されたロックを対象にして、実際にデッドロックを引き起こしているか否かを判定する際の処理であるデッドロック判定処理を行う。デバッグ情報出力処理部１０５は、デッドロック判定処理において実際にデッドロックを引き起こしていると判定された場合に、そのデッドロックが発生するに至った過程等のデバッグ情報をＬＣＤ６０等の表示部やＨＤＤ４０等の不揮発性記憶媒体に出力する際の処理であるデバッグ情報出力処理を行う。
【００３７】
実行主体管理部１０６、情報資源管理部１０７、ロック管理部１０８はそれぞれ、実行主体４００、情報資源５００、ロック６００を管理する。
【００３８】
タイマ２００は、現在時刻をカウントする。スタック３００は、過去に呼び出された関数のスタックフレームを保持する。このスタック３００は、図１に示したＣＰＵ１０のレジスタにより実現される。実行主体４００は、プロセスやスレッド、タスク等、プロセッサが演算を行うことにより情報処理を実行する主体となるものである。情報資源５００は、実行主体が処理を実行する際に使用するデータ等の要素や、実行主体が処理を実行する際に共通して利用する特殊なメモリ領域のことである。ロック６００は、一の実行主体に排他的に情報資源へアクセスさせるためのアクセス占有権であり、各情報資源に一対一で紐付けられている。
【００３９】
次に、本実施形態に係るロックのデータ構造について、図３を参照して説明する。図３は、本実施形態に係るロックのデータ構造を説明するための図である。図３に示すように、本実施形態に係るロックは、「ロックＩＤ」、「格納先アドレス」、「獲得主」、「獲得待ちリスト」、「獲得状況」、「獲得時刻」、「属性」、「関数戻りアドレス」により構成される。尚、図３においては、本発明に関係する情報のみを示し、その他の情報は省略している。
【００４０】
「ロックＩＤ」は、ロックを識別するための識別子である。「格納先アドレス」は、ロックの格納先アドレスである。「獲得主」は、ロックを獲得している実行主体の格納先アドレスである。「獲得待ちリスト」は、ロック獲得を試みた結果、そのロックの獲得を待っている実行主体の格納先アドレスのリストである。尚、本実施形態においては、この「獲得待ちリスト」にはロック獲得の試みを行った順に登録され、その登録順に獲得主になる。
【００４１】
「獲得状況」は、実行主体にロックが獲得されているか否かを表す変数であり、この変数が０である場合には、どの実行主体からも獲得されていないことを表し、１である場合には、ある実行主体に獲得されているが獲得待ちである他の実行主体がないことを表し、２以上である場合には、ある実行主体に獲得されており獲得待ちである他の実行主体があることを表す。「獲得時刻」は、ロック獲得処理においてロック獲得が確定した時刻を表す。
【００４２】
「属性」は、ロックの属性を表す変数であり、この変数が０００である場合には、どの実行主体からも獲得されておらず獲得待ちの実行主体もないフリーなロックであることを表し、００１である場合には、ある実行主体に獲得されているが獲得待ちである他の実行主体がないロックであることを表し、０１０である場合には、ある実行主体に獲得されており獲得待ちである他の実行主体があるロックであることを表し、０１１である場合には、デッドロック可能性判定処理の結果、デッドロックを引き起こす可能性があると判定されたロックであることを表し、１００である場合には、デッドロック可能性判定処理の結果、デッドロックを引き起こす可能性がないと判定されたロックであることを表し、１０１である場合には、デッドロック判定処理の結果、デッドロックを引き起こしていると判定されたロックであることを表し、１１０である場合には、デッドロック判定処理の結果、デッドロックを引き起こしていないと判定されたロックであることを表し、１１１である場合には、デバッグ情報出力処理の結果、デバッグ情報が出力されたロックであることを表す。
【００４３】
「関数戻りアドレス」は、ロック獲得が確定した時点から所定ステップだけ遡った関数の戻りアドレスである。
【００４４】
次に、本実施形態に係る実行主体のデータ構造について、図４を参照して説明する。図４は、本実施形態に係る実行主体のデータ構造を説明するための図である。図４に示すように、本実施形態に係る実行主体は、「実行主体ＩＤ」、「格納先アドレス」、「獲得済みリスト」を含む。尚、図４においては、本発明に関係する情報のみを示し、その他の情報は省略している。「実行主体ＩＤ」は、実行主体を識別するための識別子である。「格納先アドレス」は、実行主体の格納先アドレスである。「獲得済みリスト」は、獲得済みロックの格納先アドレスのリストである。
【００４５】
このように構成されたオペレーティング・システム１００において、本実施形態に係る要旨の一つは、一の実行主体に獲得されており、かつ、他の実行主体から獲得待ちされているロックであって、上記一の実行主体に獲得されてから所定時間経過しても上記他の実行主体に獲得されていないロックのみを対象として、デッドロックを引き起こしているか否かを判定するためのデッドロック判定処理を実行することにある。これにより、本実施形態に係るオペレーティング・システム１００は、効率的にデッドロックを検知することが可能となる。
【００４６】
次に、本実施形態に係るオペレーティング・システム１００がロック獲得処理を実行する際の処理について、図５及び図６を参照して説明する。図５及び図６は、本実施形態に係るオペレーティング・システム１００がロック獲得処理を実行する際の処理を説明するためのフローチャートである。尚、図５及び図６においては、ある特定の実行主体αが、ある情報資源Ａのロックａを獲得する例について示している。
【００４７】
図５に示すように、本実施形態に係るオペレーティング・システム１００がロック獲得処理を実行する際にはまず、実行主体αがロックａの獲得を試みると、ロック獲得処理部１０１は、ロックａの「獲得主」若しくは「獲得状況」を確認することにより、ロックａが既に他の実行主体に獲得されているか否かを判断する（Ｓ５０１）ロック獲得処理部１０１は、Ｓ５０１の判断処理において、ロックａが他の実行主体に獲得されていないと判断した場合には（Ｓ５０１／ＹＥＳ）、ロックａの「獲得状況」の変数に１を加算する（Ｓ５０２）。
【００４８】
ロック獲得処理部１０１は、「獲得状況」の変数に１を加算すると、実行主体αの「格納先アドレス」を、ロックａの「獲得主」に登録して（Ｓ５０３）、実行主体αによるロックａの獲得を確定し（Ｓ５０４）、そのときの現在時刻を実行主体αによるロックａの獲得時刻としてタイマ２００から取得してロックａの「獲得時刻」に登録する（Ｓ５０５）。尚、実行主体αによるロックａの獲得の確定は、その他のタイミング、例えば、実行主体αがロックａを獲得するために実行されたロック獲得処理が完了したタイミングであっても良い。
【００４９】
ロック獲得処理部１０１は、現在時刻を「獲得時刻」に登録すると、スタック３００から関数の戻りアドレスを取得してロックａの「関数戻りアドレス」に登録する（Ｓ５０６）と共に、ロックａの「格納先アドレス」を実行主体αの「獲得済みリスト」に登録し（Ｓ５０７）、ロックａの「獲得待ちリスト」若しくは「獲得状況」を確認することにより、ロックａの獲得を待っている実行主体があるか否かを判断する（Ｓ５０８）。即ち、本実施形態においては、Ｓ５０６の処理が、実行過程情報取得処理ステップに相当する。尚、Ｓ５０６の関数戻りアドレス登録処理については、図７を参照して後に詳述する。
【００５０】
ロック獲得処理部１０１は、Ｓ５０８の判断処理において、ロックａの獲得を待っている実行主体があると判断した場合には（Ｓ５０８／ＹＥＳ）、ロックａの「属性」が０１０であるか否かを判断する（Ｓ５０９）。ロック獲得処理部１０１は、Ｓ５０９の判断処理において、ロックａの「属性」が０１０ではないと判断した場合には（Ｓ５０９／ＮＯ）、ロックａの「属性」を０１０に更新して（Ｓ５１０）ロック獲得処理を終了し、０１０であると判断した場合には（Ｓ５０９／ＹＥＳ）、そのまま、ロック獲得処理を終了する。
【００５１】
ロック獲得処理部１０１は、Ｓ５０８の判断処理において、ロックａの獲得を待っている実行主体がないと判断した場合には（Ｓ５０８／ＮＯ）、ロックａの「属性」が００１であるか否かを判断する（Ｓ５１１）。ロック獲得処理部１０１は、Ｓ５１１の判断処理において、ロックａの「属性」が００１ではないと判断した場合には（Ｓ５１１／ＮＯ）、ロックａの「属性」を００１に更新して（Ｓ５１２）ロック獲得処理を終了し、００１であると判断した場合には（Ｓ５１１／ＹＥＳ）、そのまま、ロック獲得処理を終了する。
【００５２】
一方、ロック獲得処理部１０１は、Ｓ５０１の判断処理において、ロックａが既に他の実行主体に獲得されていると判断した場合には（Ｓ５０１／ＮＯ）まず、図６に示すように、実行主体αの「格納先アドレス」を、ロックａの「獲得待ちリスト」に登録して（Ｓ６０１）、ロックａの「属性」が０１０であるか否かを判断する。
【００５３】
ロック獲得処理部１０１は、ロックａの「属性」が０１０ではないと判断した場合には（Ｓ６０２／ＮＯ）、ロックａの「属性」を０１０に更新した（Ｓ６０３）後、ロック解放処理部１０２によるロック解放処理が終了するのを待ち（Ｓ６０４）、０１０であると判断した場合には（Ｓ６０２／ＹＥＳ）、そのまま、ロック解放処理部１０２によるロックａのロック解放処理が終了するのを待つ（Ｓ６０４）。尚、Ｓ６０４のロック解放処理については、図８を参照して後に詳述する。
【００５４】
ロック獲得処理部１０１は、ロック解放処理の結果、ロックａの獲得の順番が回ってきたことを通知する獲得通知がロック解放処理部１０２からロックａの獲得を待っている実行主体へ通知されると、その獲得通知が実行主体αへのものか否かを判断する（Ｓ６０５）。
【００５５】
ロック獲得処理部１０１は、Ｓ６０５の判断処理において、ロックａの獲得通知が実行主体αへのものではないと判断すると（Ｓ６０５／ＮＯ）、ロックａの獲得通知が通知された他の実行主体がロックａを獲得するためのロック獲得処理を実行する（Ｓ６０６）。尚、Ｓ６０６で実行されるロック獲得処理は、Ｓ５０３〜Ｓ５１２の処理と同様の処理である。
【００５６】
ロック獲得処理部１０１は、他の実行主体がロックａを獲得するためのロック獲得処理の実行を終了すると、再度、ロック解放処理部１０２によるロックａのロック解放処理が終了するのを待って（Ｓ６０４）、改めて、ロックａの獲得通知がロック解放処理部１０２からロックａの獲得を待っている実行主体へ通知されると、その獲得通知が実行主体αへのものか否かを判断する（Ｓ６０５）。
【００５７】
ロック獲得処理部１０１は、Ｓ６０５の判断処理において、ロックａの獲得通知が実行主体αへのものであると判断すると（Ｓ６０５／ＹＥＳ）、実行主体αの「格納アドレス」をロックａの「獲得待ちリスト」から削除し（Ｓ６０７）、再度、Ｓ５０３以降の処理と同様の処理を行う。このようにして、本実施形態に係るオペレーティング・システム１００は、ロック獲得処理を終了する。
【００５８】
次に、本実施形態に係るオペレーティング・システム１００が関数戻りアドレス登録処理を実行する際の処理について、図７を参照して説明する。図７は、本実施形態に係るオペレーティング・システム１００が関数戻りアドレス登録処理を実行する際の処理を説明するためのフローチャートである。尚、図７においては、ある情報資源Ｂのロックｂの「関数戻りアドレス」に関数の戻りアドレスを登録する例について示している。
【００５９】
図７に示すように、本実施形態に係るオペレーティング・システム１００が関数戻りアドレス登録処理を実行する際にはまず、ロック獲得処理部１０１は、スタック３００の最上位に積まれているスタックフレームにアクセスして（Ｓ７０１）、そのスタックフレームに含まれる関数の戻りアドレスを取得し（Ｓ７０２）、それをロックｂの「関数戻りアドレス」に登録する（Ｓ７０３）。
【００６０】
そして、ロック獲得処理部１０１は、１ステップ前に取得した関数の戻りアドレスが指すスタックフレームにアクセスして（Ｓ７０４）、そのスタックフレームに含まれる関数の戻りアドレスを取得し（Ｓ７０５）、それをロックｂの「関数戻りアドレス」に登録した後（Ｓ７０６）、所定ステップだけ遡ったか否かを判断する（Ｓ７０７）。
【００６１】
ロック獲得処理部１０１は、Ｓ７０７の判断処理において、所定ステップだけ遡っていないと判断した場合には（Ｓ７０７／ＮＯ）、再度、Ｓ７０４以降の処理と同様の処理を行い、所定ステップだけ遡ったと判断した場合には（Ｓ７０７／ＹＥＳ）、そのまま、関数戻りアドレス登録処理を終了する。
【００６２】
次に、本実施形態に係るオペレーティング・システム１００がロック解放処理を実行する際の処理について、図８を参照して説明する。図８は、本実施形態に係るオペレーティング・システム１００がロック解放処理を実行する際の処理を説明するためのフローチャートである。尚、図８においては、ある特定の実行主体βが、ある情報資源Ｂのロックｂを解放する例について示している。
【００６３】
図８に示すように、本実施形態に係るオペレーティング・システム１００がロック解放処理を実行する際にはまず、実行主体βがロックｂの解放を試みると、ロック解放処理部１０２は、ロックｂの「獲得状況」の変数から１を減算する（Ｓ８０１）。ロック解放処理部１０２は、「獲得状況」の変数から１を減算すると、ロックｂの「獲得主」、「獲得時刻」、「デバグ情報」をクリアする（Ｓ８０２、Ｓ８０３、Ｓ８０４）と共に、「獲得済みリスト」からロックｂの格納先アドレスを削除し（Ｓ８０５）、ロックｂの「属性」が０００であるか否かを判断する（Ｓ８０６）。
【００６４】
ロック解放処理部１０２は、Ｓ８０６の判断処理において、ロックｂの「属性」が０００ではないと判断した場合には（Ｓ８０６／ＮＯ）、ロックｂの「属性」を０００に更新して（Ｓ８０７）、ロックｂの「獲得待ちリスト」若しくは「獲得状況」を確認することにより、ロックｂの獲得を待っている実行主体があるか否かを判断し（Ｓ８０８）、０００であると判断した場合には（Ｓ８０６／ＹＥＳ）、そのまま、ロックｂの「獲得待ちリスト」若しくは「獲得状況」を確認することにより、ロックｂの獲得を待っている実行主体があるか否かを判断する（Ｓ８０８）。
【００６５】
ロック解放処理部１０２は、Ｓ８０８の判断処理において、ロックｂの獲得を待っている実行主体があると判断した場合には（Ｓ８０８／ＹＥＳ）、ロックｂの獲得の順番が回ってきたことを通知する獲得通知を、ロックｂの「獲得待ちリスト」の先頭の実行主体に通知して（Ｓ８０９）ロック解放処理を終了し、ロックｂの獲得を待っている実行主体がないと判断した場合には（Ｓ８０８／ＮＯ）、そのままロック解放処理を終了する。
【００６６】
次に、本実施形態に係るオペレーティング・システム１００がデッドロック可能性判定処理を行う際の処理について、図９を参照して説明する。図９は、本実施形態に係るオペレーティング・システム１００がデッドロック可能性判定処理を行う際の処理を説明するためのフローチャートである。
【００６７】
図９に示すように、本実施形態に係るオペレーティング・システム１００がデッドロック可能性判定処理を行う際にはまず、デッドロック可能性判定処理部１０３は、「属性」が０１０であるロックをロック６００から一つ選択する（Ｓ９０１）。以下では、ここで選択されたロックをロックｃとする。
【００６８】
デッドロック可能性判定処理部１０３は、ロックを一つ選択すると、現在時刻をタイマ２００から取得し（Ｓ９０２）、Ｓ９０２で取得した現在時刻と、ロックｃの「獲得時刻」との差を算出して（Ｓ９０３）、その差が所定時間以上であるか否かを判断する（Ｓ９０４）。即ち、本実施形態においては、Ｓ９０４の処理が、アクセス占有権獲得判断処理ステップに相当する。尚、Ｓ９０２における現在時刻の取得処理は、Ｓ９０１の処理の前であっても良い。
【００６９】
デッドロック可能性判定処理部１０３は、Ｓ９０４の判断処理において、差が所定時間以上であると判断すると（Ｓ９０４／ＹＥＳ）、ロックｃがデッドロックを引き起こしている可能性があると判定して（Ｓ９０５）、ロックｃの「属性」を０１１に更新する（Ｓ９０６）。一方、デッドロック可能性判定処理部１０３は、Ｓ９０４の判断処理において、差が所定時間以上ではないと判断すると（Ｓ９０４／ＮＯ）、ロックｃがデッドロックを引き起こしている可能性はないと判定して（Ｓ９０７）、ロックｃの「属性」を１００に更新する（Ｓ９０８）。
【００７０】
デッドロック可能性判定処理部１０３は、ロックｃの「属性」を更新すると、「属性」が０１０であるロックがあるか否かを判断する（Ｓ９０９）。デッドロック可能性判定処理部１０３は、Ｓ９０９の判断処理において、「属性」が０１０であるロックがあると判断した場合には（Ｓ９０９／ＹＥＳ）、Ｓ９０１以降の処理と同様の処理を行う。
【００７１】
一方、デッドロック可能性判定処理部１０３は、Ｓ９０８の判断処理において、０１０であるロックがないと判断した場合には（Ｓ９０９／ＮＯ）、「属性」が１００であるロックをロック６００から全て選択して、それらの「属性」を０１０に更新し（Ｓ９１０）、デッドロック判定処理部１０４にデッドロック可能性判定処理が完了したことを通知し（Ｓ９１１）、デッドロック可能性判定処理を終了する。
【００７２】
ここで、デッドロック可能性判定処理部１０３が、Ｓ９１０における「属性」の更新処理を行う理由について説明する。デッドロック可能性判定処理において一旦はデッドロックを引き起こしている可能性がないと判定されたロックではあるが、ある程度時間が経過して再度そのロックを対象にしてデッドロック可能性判定処理が実行された場合、Ｓ９０４の判断処理において、差が所定時間以上であると判断される可能性がある（Ｓ９０４／ＹＥＳ）。
【００７３】
即ち、デッドロック可能性判定処理において一旦はデッドロックを引き起こしている可能性がないと判定されたロックではあっても、ある程度時間が経過すると、再度実行されたデッドロック可能性判定処理において、デッドロックを引き起こしている可能性があると判定される可能性が残っている。そこで、このようなロックについては、再度実行されるデッドロック可能性判定処理の対象から外さないためである。
【００７４】
次に、本実施形態に係るオペレーティング・システム１００がデッドロック判定処理を行う際の処理について、図１０を参照して説明する。図１０は、本実施形態に係るオペレーティング・システム１００がデッドロック判定処理を行う際の処理を説明するためのフローチャートである。
【００７５】
図１０に示すように、本実施形態に係るオペレーティング・システム１００がデッドロック判定処理を行う際にはまず、デッドロック判定処理部１０４は、デッドロック可能性判定処理部１０３からデッドロック可能性判定処理が完了したことを通知されると（Ｓ１００１）、ロック６００から「属性」が０１１のロックを一つ選択する（Ｓ１００２）。以下では、ここで選択されたロックをロックｄとする。
【００７６】
このＳ１００２の処理が、本実施形態の要旨の一つである。即ち、本実施形態に係るオペレーティング・システム１００は、「属性」が０１１のロックのみを対象として、以下で説明するデッドロック判定処理を行うことを要旨の一つとしている。これにより、本実施形態に係るオペレーティング・システム１００によれば、効率的にデッドロックを検知することが可能となる。
【００７７】
デッドロック判定処理部１０４は、Ｓ１００２で選択されたロックｄの組み合わせリストを作成する（Ｓ１００３）。即ち、本実施形態においては、Ｓ１００２及びＳ１００３の処理が、実行主体選択処理ステップに相当する。ここで、ロックｄの組み合わせリストとは、ロックｄの「獲得待ちリスト」に格納先アドレスが登録されている実行主体の実行主体ＩＤ（以下、「実行主体δ」とする）と、実行主体δの「獲得済みリスト」に格納先アドレスが登録されているロックのロックＩＤ（以下、「ロックｅ」とする）と、ロックｅの「獲得待ちリスト」に格納先アドレスが登録されている実行主体の実行主体ＩＤ（以下、「実行主体ε」とする）と、実行主体εの「獲得済みリスト」に格納先アドレスが登録されているロックのロックＩＤ（以下、「ロックｆ」とする）とがその順番通りに組み合わせ毎に登録されたリストのことである。
【００７８】
ここで、本実施形態に係る組み合わせリストの具体的な構成について、図１１及び図１２を参照して説明する。図１１は、本実施形態に係る有向グラフの一例を示す図である。図１２は、本実施形態に係る組み合わせリストの一例を示す図である。ここで、有向グラフとは、実行主体によるロックの獲得状況及び獲得待ち状況を、方向性を持つ矢印で示すことにより構成されるグラフのことであり、実行主体からロックへの矢印は、矢印元の実行主体が矢印先のロックを獲得していることを表し、ロックから実行主体への矢印は、矢印先の実行主体が矢印元のロックを獲得待ちであることを表す。ロックｄを起点とする有向グラフが図１１に示すような場合、ロックｄの組み合わせグラフは、図１２に示すようになる。
【００７９】
デッドロック判定処理部１０４は、Ｓ１００３で作成したロックｄの組み合わせリストから選択済みフラグがたっていない組み合わせを一組選択して（Ｓ１００４）、その組み合わせに選択済みフラグをたて（Ｓ１００５）、ロックｄと、Ｓ１００４で選択した組み合わせにおけるロックｆとが同一であるか否かを判断する（Ｓ１００６）。即ち、本実施形態においては、Ｓ１００６の処理が、獲得待機状態判断処理ステップに相当する。
【００８０】
デッドロック判定処理部１０４は、Ｓ１００６の判断処理において、ロックｄとロックｆとが同一であると判断した場合には（Ｓ１００６／ＹＥＳ）、Ｓ１００４で選択した組み合わせにおいてデッドロックが発生し、ロックｄ（＝ロックｆ）がデッドロックを引き起こしていると判定して（Ｓ１００７）、ロックｄ（＝ロックｆ）の「属性」を１０１に更新する（Ｓ１００８）。即ち、本実施形態においては、Ｓ１００７の処理が、実行停止判定処理ステップに相当する。
【００８１】
ここで、Ｓ１００４で選択された組み合わせでデッドロックが発生していると判定されたとき（Ｓ１００６／ＹＥＳ）の有向グラフを図１３に示す。図１３は、本実施形態に係る有向グラフの一例を示す図である。図１３に示すように、デッドッロックが発生した場合、その有向グラフにおいてループが形成される。これはつまり、デッドロックが発生しているか否かの判定処理（Ｓ１００６）は、有向グラフにおいてループが形成されているか否かを判定するための処理に相当することを意味する。
【００８２】
一方、デッドロック判定処理部１０４は、Ｓ１００６の判断処理において、ロックｄとロックｆとが同一ではないと判断した場合には（Ｓ１００７／ＮＯ）、Ｓ１００４で選択した組み合わせではデッドロックが発生しておらず、ロックｄはデッドロックを引き起こしていないと判定して（Ｓ１００９）、ロックｄの組み合わせリストから全ての組み合わせを選択したか否かを判断する（Ｓ１０１０）。
【００８３】
デッドロック判定処理部１０４は、Ｓ１０１０の判断処理において、ロックｄの組み合わせリストから全ての組み合わせを選択していないと判断した場合には（Ｓ１０１０／ＮＯ）、Ｓ１００４以降の処理と同様の処理を行い、ロックｄの組み合わせリストから全ての組み合わせを選択したと判断した場合には（Ｓ１０１０／ＮＯ）、ロックｄの「属性」を１１０に更新する（Ｓ１０１１）。
【００８４】
デッドロック判定処理部１０４は、ロックｄの「属性」を更新すると、ロック６００に「属性」が０１１のロックがあるか否かを判断する（Ｓ１０１２）。デッドロック判定処理部１０４は、Ｓ１０１２の判断処理において、「属性」が０１１のロックがあると判断した場合には（Ｓ１０１２／ＹＥＳ）、Ｓ１００２以降の処理と同様の処理を行い、ロック６００に「属性」が０１１のロックがないと判断した場合には（Ｓ１０１２／ＮＯ）、デバッグ情報出力処理部１０５にデッドロック検知処理が完了したことを通知し（Ｓ１０１３）、デッドロック判定処理を終了する。
【００８５】
このように、本実施形態に係るオペレーティング・システム１００は、デッドロック判定処理において、一の実行主体に獲得されており、かつ、他の実行主体から獲得待ちされているロックであって、上記一の実行主体に獲得されてから所定時間経過しても上記他の実行主体に獲得されていないロックのみを対象として、デッドロックを引き起こしているか否かを判定することを要旨の一つとしている。これにより、本実施形態に係るオペレーティング・システム１００によれば、効率的にデッドロックを検知することが可能となる。
【００８６】
次に、本実施形態に係るオペレーティング・システム１００がデバッグ情報出力処理を行う際の処理について、図１４を参照して説明する。図１４は、本実施形態に係るオペレーティング・システム１００がデバッグ情報出力処理を行う際の処理を説明するためのフローチャートである。
【００８７】
図１４に示すように、本実施形態に係るオペレーティング・システム１００がデバッグ情報出力処理を行う際にはまず、デバッグ情報出力処理部１０５は、デッドロック判定処理部１０４からデッドロック判定処理が完了したことを通知されると（Ｓ１４０１）、ロック６００から「属性」が１０１のロックを一つ選択する（Ｓ１４０２）。以下では、ここで選択されたロックをロックｋとする。
【００８８】
デバッグ情報出力処理部１０５は、Ｓ１４０２で選択されたロックｋの「格納先アドレス」、「獲得主」、「獲得時刻」、「関数戻りアドレス」（以下、総称して「デバッグ情報」とする）をＬＣＤ６０等の表示部に出力し、若しくは、ＨＤＤ４０等の不揮発性の記憶媒体に出力する（Ｓ１４０３）。即ち、本実施形態においては、Ｓ１４０３の処理が、実行過程情報出力処理ステップに相当する。
【００８９】
このＳ１４０２、Ｓ１４０３の一連の処理が、本実施形態における他の要旨の一つである。即ち、本実施形態に係るオペレーティング・システム１００は、デッドロックが発生すると、デッドロックに陥った過程を自動的に出力することを他の要旨の一つとしている。これにより、本実施形態に係るオペレーティング・システム１００によれば、ユーザは、デッドロックに陥った原因を容易に解析することができ、また、デッドロックに陥った際の情報をいつでも取り出すことができ、いつでもどこでも容易にデバッグを行うことが可能となる。
【００９０】
デバッグ情報出力処理部１０５は、ロックｋの「属性」を１１１に更新し（Ｓ１４０４）、ロック６００に「属性」が１０１のロックがあるか否かを判断する（Ｓ１４０５）。デバッグ情報出力処理部１０５は、Ｓ１４０５の判断処理において、ロック６００に「属性」が１０１のロックがあると判断した場合には（Ｓ１４０５／ＹＥＳ）、Ｓ１４０３以降の処理と同様の処理を行い、「属性」が１０１のロックがないと判断した場合には（Ｓ１４０５／ＮＯ）、そのまま、デバッグ情報出力処理を終了する。
【００９１】
以上、説明したように、本実施形態に係る要旨の一つは、デッドロック判定処理において、一の実行主体に獲得されており、かつ、他の実行主体から獲得待ちされているロックであって、上記一の実行主体に獲得されてから所定時間経過しても上記他の実行主体に獲得されていないロックのみを対象として、デッドロックを引き起こしているか否かを判定することにある。これにより、本実施形態に係るオペレーティング・システム１００によれば、効率的にデッドロックを検知することが可能となる。
【００９２】
尚、本実施形態においては、情報処理装置にインストールされて使用されるオペレーティング・システムを例にして説明したが、これに限らず、複数の実行主体がそれぞれ同一の複数の情報資源にアクセスするプログラムであれば、どのようなプログラムでも適用可能である。
【００９３】
また、本実施形態においては、図１０〜図１３において説明したように、「実行主体δ→ロックｅ→実行主体ε→ロックｆ」といったように、実行主体が２個、ロックが２個であるような組み合わせリストを作成し、そのときの有向グラフにおいてループが形成されているか否かを判断する例について説明した。この他、図１５に示すように、実行主体３個、ロック３個で組み合わされる組み合わせリストを作成し、そのときの有向グラフにおいてループが形成されているか否かを判断するように構成されていても良い。図１４は、本実施形態に係る組み合わせリストの一例を示す図である。
【００９４】
このような構成の場合、図１５に示すように、組み合わせリストには、図１０で説明した実行主体δ、ロックｅ、実行主体ε、ロックｆの他に、ロックｆの「獲得待ちリスト」に格納先アドレスが登録されている実行主体の実行主体ＩＤ（以下、「実行主体λ」とする）と、実行主体λの「獲得済みリスト」に登録されているロックのロックＩＤ（以下、「ロックｇ」とする）とがその順番通りに登録される。また、このような構成の場合、デッドロックが発生すると、例えば、ロックｇと、図１０で説明したロックｄとが同一となり、有向グラフにおいて図１６に示すようなループが形成される。図１６は、本実施形態に係る有向グラフの一例を示す図である。
【００９５】
さらに、この他、図１７に示すように、さらに多くの実行主体とロックとで組み合わされる組み合わせリストを作成し、そのときの有向グラフにおいてループが形成されているか否かを判断するように構成されていても良い。図１７は、本実施形態に係る組み合わせリストの一例を示す図である。
【００９６】
このような構成の場合、組み合わせリストは、図１７に示すようになり、このような組み合わせリストにおいてデッドロックが発生すると、例えば、有向グラフにおいて図１７に示すようなループが形成される。図１８は、本実施形態に係る有向グラフの一例を示す図である。
【００９７】
尚、このように２個以上の実行主体とロックとにおける有向グラフにおいてループが形成されるときというのは、図１７に示した組み合わせリストを例に挙げると、実行主体δ、実行主体ε、実行主体λ、・・・、実行主体μ、・・・、実行主体νがそれぞれ獲得しているロックｅ、ロックｆ、ロックｇ、・・・、ロックｍ、・・・、ロックｎのうち、自身の獲得しているロックを除く他のロックの少なくともいずれかのロックの獲得を、実行主体δ、実行主体ε、実行主体λ、・・・、実行主体μ、・・・、実行主体νがそれぞれ試み、ロックｅ、ロックｆ、ロックｇ、・・・、ロックｍ、・・・、ロックｎがそれぞれ実行主体δ、実行主体ε、実行主体λ、・・・、実行主体μ、・・・、実行主体νの少なくともいずれかにより獲得待ち状態となるときである。
【符号の説明】
【００９８】
１  情報処理装置
１０  ＣＰＵ
２０  ＲＡＭ
３０  ＲＯＭ
４０  ＨＤＤ
５０  Ｉ／Ｆ
６０  ＬＣＤ
７０  操作部
８０  バス
１００  オペレーティング・システム
１０１  ロック獲得処理部
１０２  ロック解放処理部
１０３  デッドロック可能性判定処理部
１０４  デッドロック判定処理部
１０５  デバッグ情報出力処理部
１０６  実行主体管理部
１０７  情報資源管理部
１０８  ロック管理部
２００  タイマ
３００  スタック
４００  実行主体
５００  情報資源
６００  ロック
【先行技術文献】
【特許文献】
【００９９】
【特許文献１】特開平０１−１４０２５０号公報
【図１】
2015075871.tif 000003
【図２】
2015075871.tif 000004
【図３】
2015075871.tif 000005
【図４】
2015075871.tif 000006
【図５】
2015075871.tif 000007
【図６】
2015075871.tif 000008
【図７】
2015075871.tif 000009
【図８】
2015075871.tif 000010
【図９】
2015075871.tif 000011
【図１０】
2015075871.tif 000012
【図１１】
2015075871.tif 000013
【図１２】
2015075871.tif 000014
【図１３】
2015075871.tif 000015
【図１４】
2015075871.tif 000016
【図１５】
2015075871.tif 000017
【図１６】
2015075871.tif 000018
【図１７】
2015075871.tif 000019
【図１８】
2015075871.tif 000020