(57)【要約】【課題】アプリケーションプログラムに影響することなく、デッドロック状態を容易に且つ正確に検知する。【解決手段】複数のタスク間で複数の共有資源の排他制御を実行するリアルタイムＯＳであって、（ａ）複数のタスクが共有資源を共有し合うことによるデッドロック状態を検出するための管理テーブルと、共有資源の獲得待ち状態に遷移したタスクの情報と、（ｂ）当該タスクの獲得待ち状態の原因となる当該共有資源を獲得中であるタスクの情報とを、デッドロック状態を検出するための情報として管理テーブルに記録する管理情報作成部とを備えることによる。【選択図】      図１
2004341878.tif 000002
【特許請求の範囲】
【請求項１】
複数のタスク間で複数の共有資源の排他制御を実行するリアルタイムＯＳであって、
複数のタスクが前記共有資源を共有し合うことによるデッドロック状態を検出するための管理テーブルと、
前記共有資源の獲得待ち状態に遷移したタスクの情報と、当該タスクの前記獲得待ち状態の原因となる当該共有資源を獲得中のタスクの情報とを、前記デッドロック状態を検出するための情報として前記管理テーブルに記録する管理情報作成部と
を備えることを特徴とするリアルタイムＯＳ。
【請求項２】
前記管理テーブルは、前記獲得待ち状態に遷移したタスクを記録するキューの先頭を規定する待ちタスク管理テーブルと、各タスクのタスクコントロールブロックとを含み、
前記管理情報作成部は、獲得待ち状態に遷移したタスクのコントロールブロックに、当該タスクの獲得待ち状態の原因となるタスクの情報を記録すること
を特徴とする請求項１に記載のリアルタイムＯＳ。
【請求項３】
実行中のタスクがアイドル状態に遷移する段階で、前記管理テーブルの情報に基づいてデッドロックを検出するデッドロック検出部を備える請求項１または請求項２に記載のリアルタイムＯＳ。
【請求項４】
前記デッドロック検出部は、前記獲得待ち状態に遷移したタスクと前記獲得待ち状態の原因となるタスクの相関が形成するループを前記管理テーブルから検出することで、前記デッドロックを検出することを特徴とする請求項３に記載のリアルタイムＯＳ。
【請求項５】
前記管理テーブルには、前記ループを検出するためのチェックビットが格納されることを特徴とする請求項４に記載のリアルタイムＯＳ。
【請求項６】
前記デッドロック検出部は、前記デッドロックの検出時に、前記デッドロックに対するエラー処理ルーチンを動作させることを特徴とする請求項３乃至請求項５のいずれか１項に記載のリアルタイムＯＳ。
【請求項７】
前記エラー処理ルーチンには、前記デッドロック状態になったタスクに応じたエラー処理が予め組み込まれることを特徴とする請求項６に記載のリアルタイムＯＳ。
【請求項８】
複数のタスク間で複数の共有資源の排他制御を実行するリアルタイムＯＳにおいて、複数のタスクが前記共有資源を共有し合うことによるデッドロック状態を検知する方法であって、
前記共有資源の獲得待ち状態に遷移したタスクの情報と、当該タスクの前記獲得待ち状態の原因となる当該共有資源を獲得中のタスクの情報とを、前記デッドロック状態を検出するための情報として管理情報作成部が管理テーブルに記録する段階と、
実行中のタスクがアイドル状態に遷移する段階で、デッドロック検出部が前記管理テーブルの情報に基づいてデッドロックを検出する段階と
を含むことを特徴とするデッドロック検知方法。
【請求項９】
前記デッドロックを検出する段階において、前記獲得待ち状態に遷移したタスクと前記獲得待ち状態の原因となるタスクの相関が形成するループを前記デッドロック検出部が前記管理テーブルから検出することで、前記デッドロックを検出することを特徴とする請求項８に記載のデッドロック検知方法。
【請求項１０】
前記デッドロックを検出する段階において、デッドロックが検出された時に、前記デッドロック検出部が前記デッドロックに対するエラー処理ルーチンを動作させることを特徴とする請求項８または請求項９に記載のデッドロック検知方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のタスク間で複数の共有資源の排他制御を実行するリアルタイムＯＳ（Ｒｅａｌ−ｔｉｍｅ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）及びリアルタイムＯＳにおけるデッドロック検知方法に関する。
【０００２】
【従来の技術】
タスク間の同期メカニズムに共通にみられる問題であるデッドロックは、図１３に示されるようなシナリオにおいて引き起こされる。例えば、タスクＡは実行状態（１）においてセマフォＳ１を取得した後、イベントに対する待ち状態（１）に遷移するものとする。タスクＡが待ち状態（１）に遷移すると、タスクＡより優先度低いタスクＢは、実行可能状態（１）から実行状態（２）へ遷移する。そして、タスクＢは実行状態（２）においてセマフォＳ２を取得するものとする。
【０００３】
その後イベントが発生すると、タスクＡは、実行可能状態（２）を経て実行状態（３）に遷移し、セマフォＳ２の取得を試みる。しかし、セマフォＳ２は既にタスクＢが獲得中であるため、タスクＡによるセマフォＳ２の取得は拒否され、タスクＡは再度待ち状態（２）に入る。一方、実行状態（４）に遷移したタスクＢがセマフォＳ１の取得を試みたとすると、セマフォＳ１は既にタスクＡが取得中であるために、タスクＢもタスクＡと同様待ち状態（３）に遷移し、その結果、タスクＡとタスクＢはデッドロックに陥る（例えば非特許文献１参照）。
【０００４】
このようなセマフォを利用するアプリケーションプログラムに起こるデッドロックや優先度逆転の現象を解決するために、ミューテックス（Ｍｕｔｅｘ）という仕組みが考え出された。ミューテックスで採用されるアルゴリズムとして、ＯＳＥＫ／ＶＤＸ仕様に採用されている「Ｐｒｉｏｒｉｔｙ  Ｃｅｉｌｉｎｇ」や、ＰＯＳＬＩＸ（Ｐｏｒｔａｂｌｅ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ  ｆｏｒ  ＵＮＩＸ（登録商標））準拠のＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）やμＩＴＲＯＮ（Ｍｉｃｒｏ  Ｉｎｄｕｓｔｒｉａｌ  ＴＲＯＮ）４．０仕様に採用されている「Ｐｒｉｏｒｉｔｙ  Ｉｎｈｅｒｉｔａｎｃｅ」がある。一般的には、タスクがロックできるミューテックスの数を制限したり、タスクの優先度継承を行うアルゴリズムにおいて、優先度を下げる際に制約条件（オリジナルの優先度よりも低い優先度にならないといった条件）を適用したりといったことが行われる（例えば非特許文献２参照）。
【０００５】
また、ウォッチドッグ法によるデッドロック検出技術（例えば特許文献１参照）や、Ｒ操作／Ｃ操作をカーネルが管理しデッドロックを防止する技術（例えば特許文献２参照）、デッドロックを検出してそれを回復させる技術（例えば特許文献３参照）なども提案されている。
【０００６】
【特許文献１】
特開２００１−２５９４３３号公報
【０００７】
【特許文献２】
特開平９−３３０２４１号公報
【０００８】
【特許文献３】
特開平９−２５８９９５号公報
【０００９】
【非特許文献１】
ＯＳＥＫ／ＶＤＸ運営委員会，”ＯＳＥＫ／ＶＤＸ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ”，Ｖｅｒｓｉｏｎ  ２．１  ｒｅｖｉｓｉｏｎ  １，２０００年１１月１３日，ｐ．３３
【００１０】
【非特許文献２】
Ｄａｖｉｄ  Ｋａｌｉｎｓｋｙ，”Ｍｕｔｅｘｅｓ  Ｐｒｅｖｅｎｔ  Ｐｒｉｏｒｉｔｙ  Ｉｎｖｅｒｓｉｏｎｓ”，ｖｏｌ．  １１，ｎｕｍｂｅｒ  ８，１９９８年，ｐ．７６−８１
【００１１】
【発明が解決しようとする課題】
しかしながら、複数の共有資源（セマフォもしくはミューテックス）を複数のタスクが共有し合う場合、例え非特許文献２に記載の技術を用いてタスクの優先度継承を行ったとしても、タスク間の作用によりデッドロックに陥る可能性がある。
【００１２】
また、特許文献１に記載の技術を用いてデッドロックを検出する場合、各タスクの実行時間に応じた優先度グループに各タスクを配置するように調整しなければならない。また、同時に動作するタスクの数、特に長い実行時間を要するタスクの数が多くなるにつれて、デッドロックを正確に検出するのが難しくなる。
【００１３】
更にまた、特許文献２に記載に技術を用いてデッドロックを防止しようとする場合、各タスクのアプリケーションプログラムを設計・作成する際に、Ｒ操作とＣ操作のための処理をアプリケーションプログラムに組み込む必要がある上、実行されるタスクはＲ操作とＣ操作のための処理時間を要することになる。
【００１４】
本発明は、以上のような問題を鑑みてなされたものであり、アプリケーションプログラムに影響することなく、デッドロック状態を容易に且つ正確に検知できるリアルタイムＯＳ及びデッドロック検知方法を提供することを目的とする。
【００１５】
【課題を解決するための手段】
上記課題を解決するために、本発明に係るリアルタイムＯＳの特徴は、複数のタスク間で複数の共有資源の排他制御を実行するリアルタイムＯＳであって、（ａ）複数のタスクが共有資源を共有し合うことによるデッドロック状態を検出するための管理テーブルと、共有資源の獲得待ち状態に遷移したタスクの情報と、（ｂ）当該タスクの獲得待ち状態の原因となる当該共有資源を獲得中のタスクの情報とを、デッドロック状態を検出するための情報として管理テーブルに記録する管理情報作成部とを備えることにある。
【００１６】
また、本発明に係るデッドロック検知方法の特徴は、複数のタスク間で複数の共有資源の排他制御を実行するリアルタイムＯＳにおいて、複数のタスクが共有資源を共有し合うことによるデッドロック状態を検知する方法であって、（ａ）共有資源の獲得待ち状態に遷移したタスクの情報と、当該タスクの獲得待ち状態の原因となる当該共有資源を獲得中のタスクの情報とを、デッドロック状態を検出するための情報として管理情報作成部が管理テーブルに記録する段階と、（ｂ）実行中のタスクがアイドル状態に遷移する段階で、デッドロック検出部が管理テーブルの情報に基づいてデッドロックを検出する段階とを含むことにある。
【００１７】
【発明の実施の形態】
以下、本発明の実施形態を図面に基づいて説明する。
【００１８】
尚、各図面を通じて同一もしくは同等の部位や構成要素には、同一もしくは同等の参照符号を付し、その説明を省略もしくは簡略化する。
【００１９】
図１は、複数のタスク間で複数の共有資源（セマフォもしくはミューテックス）の排他制御を実行するＯＳ２１を含むソフトウェア２０と、ハードウェア１５などを備えたシステム１０の構成例を示している。
【００２０】
ＯＳ２１は、プログラムの実行を妨げる例外的な事象が発生したときにそれに対処するための例外ハンドラ（Ｅｘｃｅｐｔｉｏｎ  Ｈａｎｄｌｅｒ）３５、割り込みサービスルーチン（ＩＳＲ；Ｉｎｔｅｒｒｕｐｔ  Ｓｅｒｖｉｃｅ  Ｒｏｕｔｉｎｅ）３０、各タスク（タスクＡ，タスクＢ，…，タスクＺ）のスケジューリング等を管理するカーネル４０、各タスクＡ〜Ｚのプログラムに対しサービスを提供するＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）５０などから構成される。
【００２１】
ＡＰＩ５０は、複数のタスクが共有資源を共有し合うことによるデッドロック状態を検出するための管理テーブル５２と、共有資源の獲得待ち状態に遷移したタスクの情報と、その共有資源を獲得中であるオーナータスク（獲得待ち状態に遷移したタスクの獲得待ち状態の原因となるタスク）の情報とをデッドロック状態を検出するための情報として管理テーブル５２に記録する管理情報作成部５１とを含んでいる。
【００２２】
カーネル４０は、実行中のタスクがアイドル状態に遷移する段階で、管理テーブル５２の情報に基づいてデッドロックを検出するデッドロック検出部４１を含んでいる。
【００２３】
デッドロック検出部４１は、獲得待ち状態に遷移したタスクと獲得待ち状態の原因となるタスクの相関が形成するループを管理テーブル５２から検出することで、デッドロックを検出する。管理テーブル５２には、デッドロック検出部４１がループを検出するためのチェックビットが格納される。
【００２４】
また、デッドロック検出部４１は、デッドロックの検出時に、エラー処理ルーチン６５を動作させる。エラー処理ルーチン６５には、デッドロック状態になったタスクに応じたエラー処理が、アプリケーションプログラムの設計者によって予め記述され組み込まれている。
【００２５】
デッドロックを監視するために用いられる管理テーブル５２のサイズは、静的なシステムにおいてはシステムコンフィグレーション時に確定され、利用されるタスクのＩＤの上限（及び下限）から管理テーブル５２のサイズが決定される。
【００２６】
一方、オブジェクト（タスク、セマフォ、ミューテックスなど）の生成・削除を動的に行うシステムにおいては、管理テーブル５２は、獲得待ち状態に遷移したタスクを記録するキューの先頭を規定する待ちタスク管理テーブル（例えば、ハッシュテーブル）と、各タスクのタスクコントロールブロックとから構成される。そして、管理情報作成部５１は、獲得待ち状態に遷移したタスクのコントロールブロックに、当該タスクの獲得待ち状態の原因となるタスクの情報を記録する。
【００２７】
管理情報作成部５１による管理テーブル５２への記録は、タスクが共有資源（セマフォもしくはミューテックス）を獲得（ロック）するために呼び出すＯＳ２１の共有資源の獲得サービス内で行う。タスクによる共有資源の獲得が拒否（ブロック）され、共有資源の獲得サービスを呼び出したタスクが待ち状態に遷移する際に、待ち状態に遷移するタスクとそのタスクが獲得しようとした共有資源を獲得しているタスクを、管理情報作成部５１が管理テーブル５２に記録する。
【００２８】
デッドロック検出部４１は、システムがアイドル状態に遷移する段階で、管理テーブル５２の情報を分析してデッドロックを検出し、デッドロックを検出すると予め登録されているエラー処理ルーチン６５を実行する。尚、管理テーブル５２の情報は、デッドロックを検出するためにデッドロック検出部４１が用いる以外にも、例えば各アプリケーションプログラムに管理テーブル５２の情報を提供し、各アプリケーションプログラムが、発生したデッドロックを分析するために用いても良い。
【００２９】
［第１実施例］
第１実施例では、静的なシステムコンフィグレーションを行う環境を例にして、管理テーブル５２の構成と、ＯＳ２１によるデッドロック検出の処理の流れを示す。
【００３０】
〔管理テーブルの構成〕
共有資源である各セマフォもしくは各ミューテックスは、タスクと同様、ＯＳ２１内部では特定のＩＤで管理されている。これら各オブジェクト（タスク、セマフォ、ミューテックス等）のＩＤは、その使用される範囲（つまり上限と下限の値）が静的なシステムコンフィグレーションによって決定されるものとする。
【００３１】
図２は、複数のタスク（タスクＡ，タスクＯ，タスクＺ）が複数のミューテックス（ミューテックスＭａ，ミューテックスＭｂ，ミューテックスＭｍ）を共有し合うことによって引き起こされるデッドロックを想定した状況を例示している。図２に示した例では、縦方向にミューテックスのＩＤ、横方向にタスクのＩＤをとり、タスクによるミューテックスのロック（図２におけるマーク◎）、ロックされたミューテックスによるロック操作のブロック（図２におけるマーク◆）、及びロック操作のブロックによるタスクの待ち状態へ遷移（図２におけるマーク◇）を示している。例えば、ミューテックスＭｍはタスクＺによりロックされており、ロックされたミューテックスＭｍによりタスクＡのロック操作がブロックされ、タスクＡは待ち状態にある。同じように、ミューテックスＭｂはタスクＯによりロックされており、タスクＺはロック待ち状態にあり、ミューテックスＭａはタスクＡによりロックされており、タスクＯはロック待ち状態にある。
【００３２】
図２に示したように、あるタスクが待ち状態になり且つミューテックスをロックしている時、「Ｗａｉｔ（◇）→「ブロック（◆）」→「Ｌｏｃｋ（◎）」→…→「Ｗａｉｔ（◇）→「ブロック（◆）」→「Ｌｏｃｋ（◎）」が一巡するとデットロック状態ということになる。この様に、デッドロックは、図２のような閉じたループとして表現されることがわかる。
【００３３】
さて、図２に示したように、グラフからループを見出すことによってデッドロック状態を検出できることがわかったところで、次に、このグラフをどのようなデータ構造によって表現するかを以下に記す。
【００３４】
１つのタスクが複数のミューテックスをロックする状況もあり得るため、図２に示したデータ表現より、より簡素化したデータ構造を採用する。「ミューテックスを１つ以上ロックし、且つ、他のミューテックスに対して待ち状態であるタスク」が「どのタスクによってロックされたミューテックスを待っているか」という情報に基づいて、図３に示すような図に書き改めることができる。
【００３５】
図２に示した例ではタスクＩＤ及びミューテックスのＩＤを基にデッドロックの状態を表現したが、図３ではタスクＩＤのみによって、デッドロック状態を表現している。タスクＡがロックしようとしたミューテックスを既に他のタスクＺがロックしていれば、タスクＡはロック待ち状態になる。尚、図３における矢印は、タスクＡがタスクＺの状態に依存するという意味で用いられている。同様に、タスクＯはタスクＡがロック中のミューテックスのロック待ちになっている。つまり、タスクＯはタスクＡの状態に依存しているのである。ミューテックスをロックしているタスクＯは、複数のタスクの状態に影響するが、そのタスクＯが影響を受けるのは、タスクＡの１つのみになります。これは、１つのタスクが同時に複数のミューテックスのロック待ちにはなり得ないからである。
【００３６】
つまり、
（１）  １つのタスクは複数のミューテックスをロック可能。
【００３７】
（２）  １つのミューテックスは１つのタスクによってのみロックされ得る。
【００３８】
この条件から更に、
（３）  あるタスクがミューテックス・ロックによって作用するタスクは複数存在する。
【００３９】
（４）  一方、あるタスクがロック待ち状態となる原因となるタスク（ミューテックス・ロック操作によって作用を受けるロック待ちになるタスク）は１つである。
【００４０】
以上４条件を与えると、図３においてループにつながるどのタスク（タスクＡ，タスクＣ，タスクＯ，タスクＺ）から出発しても、必ずループに落ち込むことになる。
【００４１】
そこで、この関係を、図６に示す管理テーブル５２ａのようにテーブルデータ化する。尚、図６（ａ）は管理テーブル５２ａの一例を示し、図６（ｂ）はそのループ状態を示している。
【００４２】
タスクＩＤが０でない正の整数であれば、図６（ａ）における「ロック待ち状態のタスク（ｗａｉｔｉｎｇ）」の行は必要なく、タスクＩＤの値を管理テーブル５２ａ参照用のオフセットとして利用できる。図６（ａ）における「待ち状態の原因となるタスク（ｃａｕｓｅｄ  ｂｙ）」の行には、待ち状態にあるタスクがロックしようとしたオブジェクト（ミューテックスもしくはセマフォ）を、どのタスクがロック中であるかを記録する。待ち状態にないタスク、或いはオブジェクト（ミューテックスもしくはセマフォ）のロック待ちにないタスクについては、「ｃａｕｓｅｄ  ｂｙ」の欄にはＮｕｌｌが入る。また、管理テーブル５２ａを監視してデッドロックを検出するプログラム（デッドロック検出部４１）は、管理テーブル５２ａの検索時にチェックビット（ｃｈｅｃｋ  ｂｉｔ）を立てる。このチェックビットを、例えば３２ｂｉｔで表されるタスクＩＤの上位１ｂｉｔを用いれば、管理テーブル５２ａに必要とされるメモリ上のサイズＳは、次式で表現される。
【００４３】
サイズＳ  ＝  タスクＩＤの上限値  ×  ４ｂｙｔｅ          （１）
デッドロック監視には、ＯＳ２１のサービスルーチンや管理情報作成部５１が担う部分と、システムのアイドル状態に実行されるデッドロック検出部４１が担う部分とに大別される。管理情報作成部５１は管理テーブル５２ａに必要なシステム内部情報を記録し、デッドロック検出部４１は管理テーブル５２ａに記録されている情報からデッドロック状態を検出する。
【００４４】
〔管理情報作成部の処理〕
ＯＳ２１のサービスルーチンのうち、ミューテックスやセマフォなどの共有資源獲得に伴うロック操作に関わる管理情報作成部５１は、管理テーブル５２ａにデッドロックを検出するための情報を記録する。
【００４５】
図４は、ミューテックスのロック操作に対する管理情報作成部５１の処理例を示すフローチャートである。
【００４６】
ステップＳ０１において、あるタスクからミューテックスに対するロック操作の要求があった場合、管理情報作成部５１は、要求があったミューテックスがロック可能か否か（要求があったミューテックスが他のタスクによって既にロックされていないか否か）を判定する。判定の結果、要求があったミューテックスがロック可能である場合、管理情報作成部５１は、ステップＳ０２において、要求があったミューテックスをロックし、処理を終了する。
【００４７】
ステップＳ０１の判定の結果、要求があったミューテックスがロック可能でない場合、管理情報作成部５１は、ステップＳ０３において、ロック操作の要求を行った当該タスクのウェイト処理を行い、ステップＳ０４において、当該タスクが待ち（Ｗａｉｔ）状態に遷移するか否かを判定する。判定の結果、待ち状態に遷移しない場合は処理を終了する。
【００４８】
ステップＳ０４の判定の結果、当該タスクが待ち状態に遷移する場合、管理情報作成部５１は、ステップＳ０５において、当該タスクを待ち（Ｗａｉｔ）状態に遷移させ、ステップＳ０６において、管理テーブル５２ａにデッドロック状態を検出するために必要とされる情報を記録する。具体的には、管理情報作成部５１は以下の処理を実行する。
【００４９】
（１）  ミューテックス（或いはセマフォ）のロック待ち状態に陥るタスクのタスクＩＤを取得する。
【００５０】
（２）  待ち状態に陥るタスクがロックを試みたミューテックス（或いはセマフォ）をロックしているオーナータスクのタスクＩＤを取得する。
【００５１】
（３）  管理テーブル５２ａの中で、ロック待ち状態に陥るタスクの「ｃａｕｓｅｄ
ｂｙ」の欄にオーナータスクのタスクＩＤを記録する。
【００５２】
このように、管理テーブル５２ａに記録される管理データは、タスクが共有資源（セマフォもしくはミューテックス）のロック待ちに遷移する際に作成される。
【００５３】
図５は、ミューテックスのロック解除（Ｕｎｌｏｃｋ）操作に対する管理情報作成部５１の処理例を示すフローチャートである。
【００５４】
ステップＳ１１において、あるタスクからミューテックスに対するロック解除操作の要求があった場合、管理情報作成部５１は、要求があったミューテックスのロック待ち状態にあるタスクがあるか否かを判定する。判定の結果、ロック待ち状態のタスクがない場合、管理情報作成部５１は、ステップＳ０２において、要求があったミューテックスのロックを解除し、処理を終了する。
【００５５】
ステップＳ１１の判定の結果、ロック待ち状態にあるタスクがある場合、管理情報作成部５１は、ステップＳ１３において、ロック待ち状態にあるタスクを実行可能（Ｒｅａｄｙ）状態にし、ステップＳ１４において、管理テーブル５２ａの情報を更新する。具体的には、管理情報作成部５１は以下のようにして、待ち状態を解除されるタスクの管理データから、共有資源（セマフォもしくはミューテックス）のオーナータスクのタスクＩＤを消去する。
【００５６】
（１）  待ち状態を解除されたタスクのタスクＩＤを取得する。
【００５７】
（２）  取得したタスクＩＤの「ｃａｕｓｅｄ  ｂｙ」の欄から、オーナータスクのタスクＩＤを消去する。
【００５８】
以上のように、管理テーブル５２ａの情報は、オブジェクト（セマフォもしくはミューテックス）のオーナータスクが、オブジェクト（セマフォもしくはミューテックス）のロックを解除した場合に更新される。
【００５９】
〔デッドロック検出部の処理〕
デッドロック状態を検出するのための処理が常にＣＰＵを一定時間占有してしまうのは、例えアプリケーションのデバッグ時においても好ましいものではない。そこで、本実施形態におけるデッドロック検出部４１は、システムがアイドル状態に遷移するのを契機に１回動作させるように構成する。このような構成により、アプリケーションプログラムの設計者は、デッドロック検出部４１の存在を意識する必要がない上、デッドロック検出部４１がアプリケーションプログラムの動作タイミング等に影響を及ぼすということもない。
【００６０】
システムがアイドル状態に遷移する段階で実行されるデッドロック検出部４１は、管理テーブル５２ａの先頭からミューテックス（もしくはセマフォ）のロック待ち状態にあるタスクを検索し、図３に示したようなグラフ上のループの検出を試みる。デッドロック検出部４１による具体的な検索手順を図７のフローチャートに示す。
【００６１】
図７に示すように、ステップＳ２１において、デッドロック検出部４１は、管理テーブル５２ａの検索を開始するためにインデックスＩをゼロクリアする。
【００６２】
ステップＳ２２において、デッドロック検出部４１は、インデックスＩにアドレス長（例えば、４ｂｙｔｅ）を積算した値を管理テーブル５２ａの先頭アドレス値に加算し、それを検索アドレスに検索用のアドレス値としてセットする。
【００６３】
ステップＳ２３において、デッドロック検出部４１は、検索アドレスに基づいて管理テーブル５２ａの「ｃａｕｓｅｄ  ｂｙ」の欄からオーナータスクのタスクＩＤを読み込む。ここで、読み込んだオーナータスクＩＤの値を仮に「Ｎ」とする。
【００６４】
ステップＳ２４において、デッドロック検出部４１は、Ｎ（読み込んだオーナータスクＩＤの値）がＮｕｌｌ値であるか否か（検索アドレスが示す位置のタスクが待ち状態にあるか否か）を判定する。判定の結果、「Ｎ＝Ｎｕｌｌ」である場合、デッドロック検出部４１は、ステップＳ３２においてインデックスＩに１を加算し、ステップＳ３３において、インデックスＩが管理テーブル５２ａのタスクＩＤの上限を超えたか否かを判定する。インデックスＩが管理テーブル５２ａに格納されているタスクＩＤの上限を超えていれば処理を終了し、超えていればステップＳ２２に戻り、次のエントリ位置のタスクに関する処理を行う。
【００６５】
一方、ステップＳ２４の判定の結果、「Ｎ≠Ｎｕｌｌ」の場合、デッドロック検出部４１は、ステップＳ２５において、管理テーブル５２ａの「チェックビット（Ｃｈｅｃｋ  Ｂｉｔ）」の欄を全て「ＯＦＦ」にクリアし、検索アドレスが示す位置のチェックビット（Ｃｈｅｃｋ  Ｂｉｔ）のビットを「ＯＮ」にする。
【００６６】
次に、ステップＳ２６において、デッドロック検出部４１は、Ｎにアドレス長（例えば、４ｂｙｔｅ）を積算した値を管理テーブル５２ａの先頭アドレス値に加算し、それを検索アドレスにセットする。つまり、次にオーナータスクの検索を行うことになる。
【００６７】
ステップＳ２７において、デッドロック検出部４１は、検索アドレスに基づいて管理テーブル５２ａの「ｃａｕｓｅｄ  ｂｙ」の欄からオーナータスクのタスクＩＤを読み込む。
【００６８】
ステップＳ２８において、デッドロック検出部４１は、Ｎ（ステップＳ２７で読み込んだオーナータスクＩＤの値）がＮｕｌｌ値であるか否か（検索アドレスが示す位置のタスクが待ち状態にあるか否か）を判定する。判定の結果、「Ｎ＝Ｎｕｌｌ」である場合、ステップＳ３２に進む。
【００６９】
ステップＳ２８の判定の結果、「Ｎ≠Ｎｕｌｌ」の場合、デッドロック検出部４１は、ステップＳ２９において、チェックビット（Ｎ）のビット値を判定する。判定の結果、「チェックビット（Ｎ）＝ＯＦＦ」の場合、ステップＳ２６に戻る。
【００７０】
逆に、ステップＳ２９の判定の結果、「チェックビット（Ｎ）＝ＯＮ」の場合、ループを検出し、デッドロック状態を検知したものと判断し、所定のエラー処理ルーチン６５を実行する。
【００７１】
このように、デッドロック検出部４１は、待ち状態に遷移しているタスクのチェックビットを「ＯＮ」にし、その待ち状態の原因となっているオーナータスクの状態を検索し、そのチェックビットを調べることで、図３に示したようなループを検出する処理を実行する。先に「ＯＮ」にセットしたチェックビットを再度検出したところで、デッドロック検出部４１はループを検出したものと見なし、デッドロック状態にあると判断する。
【００７２】
尚、エラー処理ルーチン６５としては、システムダウンや特定タスクの強制的待ち状態解除などが考えられるが、アプリケーションプログラムの性質や目的に応じて設計されるべきものである。
【００７３】
以上、第１実施例について説明したように、アプリケーションプログラムに影響することなく、デッドロック状態を容易に且つ正確に検知できる管理テーブル５２ａを、静的なシステムコンフィグレーションを行うシステム１０上に作成できる。また、静的なシステムコンフィグレーションを行うシステム１０がアイドル状態に遷移する段階で、デッドロック検出部４１によるデッドロック検出処理を実行するようにしているため、デッドロックの検出を行う場合とデッドロックの検出を行わない場合とでアプリケーションプログラムの処理動作に差異が生じない。従って、アプリケーションプログラムの設計者はデッドロック検出部４１の存在を意識せずにアプリケーションプログラムの設計ができる。更に、デッドロック検出時に、アプリケーションプログラムの設計思想に応じたエラー処理ルーチン６５を実行することも出来る。
【００７４】
［第２実施例］
第２実施例では、オブジェクト（タスク、セマフォ、ミューテックス等）の管理を動的に行う環境を例にして、管理テーブル５２ｂの構成と、ＯＳ２１によるデッドロック検出の処理の流れを示す。
【００７５】
〔管理テーブルの構成〕
各オブジェクト（セマフォもしくはミューテックス）は、タスクと同様にＯＳ２１内部ではそれぞれＩＤで管理されている。このＩＤの取り得る値は、連続で且つ一定の範囲とは限らず、システム１０の動作状態に依存する。従って、図６（ａ）に示したような固定サイズの管理テーブル５２ａは採用できない。そこで、第２実施例の管理テーブル５２ｂは、図８に一例を示すように、ロック待ち状態に遷移したタスクを記録するキューの先頭を規定するハッシュテーブルと、各タスクのタスクコントロールブロック（ＴＣＢ）とから構成される。そして、管理情報作成部５１は、獲得待ち状態に遷移したタスクのコントロールブロック（ＴＣＢ）に、当該タスクの獲得待ち状態の原因となるタスク（オーナータスク）の情報を記録する。
【００７６】
管理テーブル５２ｂの基本的なデータ構造は、図６に示した管理テーブル５２ａのデータ構造に準じる。つまり、図８に示すように、管理テーブル５２ｂの情報としては、ミューテックス（若しくはセマフォ）のロック操作によりブロックされる（待ち状態に陥る）タスクＩＤ、そのタスクがロックしようとしたミューテックス（若しくはセマフォ）のオーナータスク（待ち状態の原因となるタスク）のタスクＩＤ、デッドロック検出部４１が使用するチェックビット（Ｃｈｅｃｋ  Ｂｉｔ）などから構成される。
【００７７】
ここで、タスクＩＤが正の整数である場合を想定する。一般にハッシュテーブルのサイズは２ｎが取られるが、この指数「ｎ」は、システムの設計思想に依存するため、第２実施例では規定しない。第２実施例における管理テーブル５２ｂは、オブジェクト（ミューテックスやセマフォ）のロック待ちであるタスクを記録する為のキューの先頭を規定するハッシュテーブルと、各タスクのタスクコントロールブロック（ＴＣＢ）から構成される。各タスクのタスクコントロールブロック（ＴＣＢ）にはキューを構成するための「アドレス」（次に接続されているタスクのＴＣＢを指すアドレスで、そのタスクがキューの末尾にあるとき、このアドレスはＮｕｌｌになる）と、各タスクがロックしようとしているオブジェクト（ミューテックスやセマフォ）のオーナータスク（タスクの待ち状態の原因となるタスク）のタスクＩＤと、デッドロック検出部４１が使用するチェックビット（Ｃｈｅｃｋ  Ｂｉｔ）などから構成される。
【００７８】
〔管理情報作成部の処理〕
第１実施例と同様、ＯＳ２１のサービスルーチンのうち、ミューテックスやセマフォなどの共有資源獲得に伴うロック操作に関わる管理情報作成部５１は、管理テーブル５２ｂにデッドロックを検出するための情報を記録する。この管理テーブル５２ｂに記録される管理データは、図４に示したように、タスクがオブジェクト（セマフォもしくはミューテックス）のロック待ちに遷移する際に作成される。
【００７９】
具体的には、あるタスクがミューテックス（或いはセマフォ）ロック待ち状態に陥る場合、管理情報作成部５１は以下の処理を実行する。
【００８０】
（１）  ミューテックス（或いはセマフォ）のロック待ち状態に陥るタスクのタスクＩＤを取得する。
【００８１】
（２）  待ち状態に陥るタスクがロックを試みたミューテックス（或いはセマフォ）をロックしているオーナータスクのタスクＩＤを取得する。
【００８２】
（３）  管理テーブル５２ｂの中で、ロック待ち状態に陥るタスクの部分（テーブルサイズ２ｎで割った端数がテーブル上の位置を表す。図８における「Ｎ」や「Ｍ」がそれに該当する）に接続されるキューの末尾に、待ち状態の原因となるオーナータスクのＴＣＢを接続する。この接続は、図８におけるＴＣＢのうち、「アドレス」の設定、待ち状態の原因となるオーナータスクのタスクＩＤの設定、チェックビットのクリアで完了する。
【００８３】
また、管理テーブル５２ｂの情報は、オブジェクト（セマフォもしくはミューテックス）のオーナータスクが、オブジェクト（セマフォもしくはミューテックス）のロックを解除した場合に更新される。
【００８４】
具体的には、管理情報作成部５１は以下のようにして、待ち状態を解除されるタスクの管理データから、共有資源（セマフォもしくはミューテックス）のオーナータスクのタスクＩＤを消去する。
【００８５】
（１）  待ちを解除されたタスクのタスクＩＤを取得する。
【００８６】
（２）  管理テーブル５２ｂのロック待ち状態に陥っているタスクの部分（テーブルサイズ２ｎで割った端数がテーブル上の位置を表します）に接続されるキューからタスク待ちを解除されたタスクのタスクＩＤを外す。
【００８７】
〔デッドロック検出部の処理〕
システムがアイドル状態に遷移する段階で動作するデッドロック検出部４１は、管理テーブル５２ｂからミューテックス（或いはセマフォ）のロック待ち状態にあるタスクのキューを検索し、図３に示されるようなグラフ上のループ検出を試みる。デッドロック検出部４１による具体的な検索手順を、図９〜図１２のフローチャートに例示する。
【００８８】
図９に示すフローチャートにおいて、初期条件として、チェックビット・クリアフラグとチェックビット・パターンの管理データ９０はゼロクリアされている。
【００８９】
デッドロック検出部４１は、ステップＳ４１において、チェックビット・クリアフラグを読み込み、ステップＳ４２において、チェックビット・クリアフラグがゼロであるか否かを判定する。判定の結果、チェックビット・クリアフラグがゼロでない場合はステップＳ４７に進み、チェックビット・クリアフラグがゼロである場合はステップＳ４３に進む。
【００９０】
デッドロック検出部４１は、ステップＳ４３において、チェックビット・パターンに１を加算し、更に、ステップＳ４５において、チェックビット・パターンとチェックビット・パターン上限値（「０ｘｆｆｆｆｆｆｆｆ」）との比較を行う。
【００９１】
チェックビット・パターンがその上限値に達した場合、ステップＳ４６において、チェックビット・クリアフラグに１をセットし、ステップＳ４７のチェックビットのゼロクリア処理へ進む。
【００９２】
一方、ステップＳ４５の判定の結果、チェックビット・パターンがその上限値未満である場合、ステップＳ４８のキュー検索処理へ進む。
【００９３】
つまり、図９に示した入口処理では、デッドロック検出部４１は、各ＴＣＢ内のチェックビットのゼロクリアを行うか、キューを探索しデッドロックの検出処理を行うかの判断を行っている。既にチェックビット・クリアフラグが１であった場合、デッドロック検出部４１は、各ＴＣＢ内のチェックビットのゼロクリアを行う。また、チェックビット・パターンがその上限値に達した場合、デッドロック検出部４１は、チェックビット・クリアフラグを１に設定し、各ＴＣＢ内のチェックビットのゼロクリアを行う。一方、チェックビット・クリアフラグがゼロでチェックビット・パターンが「０ｘ００００００００」〜「０ｘｆｆｆｆｆｆｆｆ」（上限値）の間であれば、デッドロック検出部４１は、キューの探索を行い、デッドロック状態の検出を試る。尚、上記各処理は、外部割り込みによって中断されることがある。
【００９４】
図１０は、ステップＳ４７におけるチェックビットのゼロクリア処理を示すフローチャートである。
【００９５】
まず、デッドロック検出部４１は、ステップＳ５１において、インデックスＮにゼロをセットし、ステップＳ５２において、ハッシュテーブルの先頭アドレスにインデックスＮを２ビット左シフトした値（オフセット）を加算したものを「読込アドレス１」にセットする。そして、デッドロック検出部４１は、ステップＳ５３において、ハッシュテーブルの「読込アドレス１」から「ＴＣＢアドレス１」をロードする。
【００９６】
デッドロック検出部４１は、ステップＳ５４において、ロードした「ＴＣＢアドレス１」の値がＮｕｌｌであるか否かを判定し、「ＴＣＢアドレス１」の値がＮｕｌｌでない（有意なアドレスが格納されている）場合、ステップＳ５５において、チェックビットをゼロクリアする。具体的には、「ＴＣＢアドレス１」に８ｂｙｔｅ（アドレス長＋タスクＩＤ長）を加算した位置へゼロを書き込むことで、チェックビットをゼロクリアする。更に、デッドロック検出部４１は、ステップＳ５６において、「ＴＣＢアドレス１」から次の「ＴＣＢアドレス１」を読み込み、ステップＳ５４の判定処理へ戻る。
【００９７】
ステップＳ５４の判定の結果、「ＴＣＢアドレス１」の値がＮｕｌｌである場合、デッドロック検出部４１は、ステップＳ５５において、インデックスＮを１加算し、ステップＳ５６において、インデックスＮの値が２ｎ（システムが持つＩＤの上限値）より小さいか否かを判定する。インデックスＮの値が２ｎより小さい場合はステップＳ５２へ戻り、インデックスＮの値が２ｎより小さくない場合はステップＳ５９へ進む。
【００９８】
デッドロック検出部４１は、ステップＳ５９において、チェックビット・クリアフラグにゼロをセットし、ステップＳ４８のキュー探索処理へ進む。
【００９９】
このように、図１０に示したチェックビットクリア処理では、デッドロック検出部４１は、ハッシュテーブルに接続されるキューを全て検索し、各ＴＣＢ内のチェックビット部分にゼロを書き込む。このチェックビットクリア処理は、チェックビット・クリアフラグが１であった場合に必ず実行される。
【０１００】
図１１及び図１２は、ステップＳ４８におけるキュー探索処理を示すフローチャートである。
【０１０１】
デッドロック検出部４１は、ステップＳ６１において、インデックスＮにゼロをセットし、ステップＳ６２において、インデックスＮを２ビット左シフトした値をハッシュテーブルの先頭アドレスに加算したものを、「読込アドレス１」にセットする。そして、デッドロック検出部４１は、ステップＳ６３において、ハッシュテーブルの「読込アドレス１」から「ＴＣＢアドレス１」をロードし、ステップＳ６４において、ロードした「ＴＣＢアドレス１」の値がＮｕｌｌであるか否かを判定する。
【０１０２】
ステップＳ６４の判定の結果、「ＴＣＢアドレス１」の値がＮｕｌｌである場合、デッドロック検出部４１は、ステップＳ６５において、インデックスＮを１加算し、ステップＳ６６において、インデックスＮの値が２ｎより小さいか否かを判定する。インデックスＮの値が２ｎより小さい場合はステップＳ６２へ戻り、インデックスＮの値が２ｎより小さくない場合は処理を終了する。
【０１０３】
ステップＳ６４の判定の結果、「ＴＣＢアドレス１」の値がＮｕｌｌでない場合、ステップＳ６７において、デッドロック検出部４１はインデックスＮ’をゼロクリアする。
【０１０４】
ステップＳ６８において、デッドロック検出部４１は、ハッシュテーブルのＮ番目に接続されるキューから、Ｎ’番目のＴＣＢを検索する。そして、デッドロック検出部４１は、ステップＳ６９において、「ＴＣＢアドレス１」に８ｂｙｔｅ（アドレス長＋タスクＩＤ長）を加算した値を「チェックビット・アドレス」にセットし、ステップＳ７０において、「チェックビット・アドレス」が示す位置のチェックビットを読み出す。
【０１０５】
デッドロック検出部４１は、ステップＳ７１において、読み出したチェックビットがチェックビット・パターンと一致するか否かを判定し、一致する場合、ステップＳ７２において、ループを検出し、デッドロック状態を検知したものと判断し、所定のエラー処理ルーチン６５を実行する。
【０１０６】
一方、ステップＳ７１の判定の結果、読み出したチェックビットがチェックビット・パターンと一致しない場合、デッドロック検出部４１は、ステップＳ７３において、「チェックビット・アドレス」にチェックビット・パターンの値を書き込み、ステップＳ７４において、「ＴＣＢアドレス１」にアドレス長（４ｂｙｔｅ）を加算した位置から、オーナータスク（待ち状態の原因となるタスク）のタスクＩＤを読み込む。
【０１０７】
そして、デッドロック検出部４１は、ステップＳ８１において、オーナータスクのタスクＩＤの値を２ｎで割った端数をインデックスＭにセットし、ステップＳ８２において、インデックスＭを２ビット左シフトした値（オフセット）をハッシュテーブルの先頭アドレスに加算したものを、「読込アドレス２」にセットする。そして、デッドロック検出部４１は、ステップＳ８３において、ハッシュテーブルのＭ番目に接続されるキューからオーナータスク（待ち状態の原因となるタスク）のタスクＩＤを検索する。
【０１０８】
ステップＳ８３の検索処理で、オーナータスク（待ち状態の原因となるタスク）のタスクＩＤが検出されなかった場合、デッドロック検出部４１は、ステップＳ８６において、インデックスＮ’を１加算し、ステップＳ６８に戻る。
【０１０９】
ステップＳ８３の検索処理で、オーナータスク（待ち状態の原因となるタスク）のタスクＩＤが検出された場合、デッドロック検出部４１は、ステップＳ８７において、オーナータスクのＴＣＢからチェックビットを読み込み、ステップＳ８８において、チェックビットがチェックビット・パターンと一致するか否かを判定する。
【０１１０】
ステップＳ８の判定の結果、チェックビットがチェックビット・パターンと一致する場合、ステップＳ８９において、デッドロック検出部４１は、ループを検出しデッドロック状態を検知したものと判断し、所定のエラー処理ルーチン６５を実行する。
【０１１１】
ステップＳ８の判定の結果、チェックビットがチェックビット・パターンと一致しない場合、デッドロック検出部４１は、ステップＳ９０において、オーナータスクのＴＣＢへチェックビット・パターンを書き込み、ステップＳ９１において、オーナータスクのＴＣＢから次のオーナータスクのタスクＩＤを読み込み、ステップＳ８１へ戻る。
【０１１２】
このように、デッドロック検出部４１は、ループを検出した場合、デッドロック状態を検知したものと判断し、予め登録されている所定のエラー処理ルーチン６５を呼び出して実行する。尚。エラー処理ルーチン６５の処理内容としては、システムダウンや特定タスクの強制的待ち状態解除などが考えられるが、第１実施例と同様に、アプリケーションの性質・目的に合わせ設計されるべきである。
【０１１３】
以上、第２実施例について説明したように、アプリケーションプログラムに影響することなく、デッドロック状態を容易に且つ正確に検知できる管理テーブル５２ｂを、オブジェクト（タスク、セマフォ、ミューテックス等）の管理を動的に行うシステム１０上に作成できる。また、オブジェクトの管理を動的に行うシステム１０において、システム１０がアイドル状態に遷移する段階でデッドロック検出部４１によるデッドロック検出処理を実行するようにしているため、デッドロックの検出を行う場合とデッドロックの検出を行わない場合とでアプリケーションプログラムの処理動作に差異が生じない。従って、アプリケーションプログラムの設計者はデッドロック検出部４１の存在を意識せずにアプリケーションプログラムの設計が出来る。更に、デッドロック検出時に、アプリケーションプログラムの設計思想に応じたエラー処理ルーチン６５を実行することも出来る。
【０１１４】
以上、第１実施例〜第２実施例について詳細に説明したが、本発明は、その精神または主要な特徴から逸脱することなく、他の色々な形で実施することができる。
【０１１５】
例えば、第１実施例〜第２実施例における管理テーブル５２ａ，５２ｂの情報は、デッドロック検出部４１が、発生したデッドロック状態を分析するために用いる以外にも、例えば各アプリケーションプログラムに管理テーブル５２ａ，５２ｂの情報を提供し、各アプリケーションプログラムがデッドロックを検出するために用いても良い。
【０１１６】
このように、前述の各実施例はあらゆる点で単なる例示に過ぎず、限定的に解釈してはならない。本発明の範囲は、特許請求の範囲によって示すものであって、明細書本文には何ら拘束されない。更に、特許請求の範囲の均等範囲に属する変形や変更は、全て本発明の範囲内のものである。
【０１１７】
【発明の効果】
本発明によれば、アプリケーションプログラムに影響することなく、デッドロック状態を容易に且つ正確に検知できるリアルタイムＯＳ及びデッドロック検知方法を提供できる。
【図面の簡単な説明】
【図１】本発明の一実施形態によるリアルタイムＯＳを備えたシステム構成例を示す概略ブロック図である。
【図２】複数のタスクが複数のミューテックスを共有し合うことによって引き起こされるデッドロックを想定した状態を例示した図である。
【図３】図２に示したデッドロック状態をタスクＩＤのみで表現した図である。
【図４】第１実施例におけるミューテックスのロック操作に対する管理情報作成部の処理手順例を示すフローチャートである。
【図５】第１実施例におけるミューテックスのロック解除操作に対する管理情報作成部の処理手順例を示すフローチャートである。
【図６】第１実施例において、図２に示したデッドロック状態を管理テーブル化した例を示した図であり、（ａ）は管理テーブルに記録される情報の一例を示し、（ｂ）はそのループ状態を示している。
【図７】第１実施例におけるデッドロック検出部の処理手順例を示すフローチャートである。
【図８】第２実施例において、図２に示したデッドロック状態を管理テーブル化した例を示した図である。
【図９】第２実施例におけるデッドロック検出部の入口処理の例を示すフローチャートである。
【図１０】第２実施例におけるデッドロック検出部のうち、チェックビットのクリア処理の例を示すフローチャートである。
【図１１】第２実施例におけるデッドロック検出部のうち、キュー検索処理の前半部を示すフローチャートである。
【図１２】第２実施例におけるデッドロック検出部のうち、キュー検索処理の後半部を示すフローチャートである。
【図１３】複数のタスクが複数のセマフォを共有し合うことによって引き起こされるデッドロックを想定した状態を例示した図である。
【符号の説明】
Ｓ１，Ｓ２…セマフォ
１０…システム
１５…ハードウェア
２０…ソフトウェア
２１…ＯＳ
４０…カーネル
４１…デッドロック検出部
５０…ＡＰＩ
５１…管理情報作成部
５２，５２ａ，５２ｂ…管理テーブル
６５…エラー処理ルーチン
９０…管理データ
Ａ，Ｂ，Ｃ，Ｏ，Ｚ…タスク
Ｍａ，Ｍｂ，Ｍｍ…ミューテックス
【図１】
2004341878.tif 000003
【図２】
2004341878.tif 000004
【図３】
2004341878.tif 000005
【図４】
2004341878.tif 000006
【図５】
2004341878.tif 000007
【図６】
2004341878.tif 000008
【図７】
2004341878.tif 000009
【図８】
2004341878.tif 000010
【図９】
2004341878.tif 000011
【図１０】
2004341878.tif 000012
【図１１】
2004341878.tif 000013
【図１２】
2004341878.tif 000014
【図１３】
2004341878.tif 000015