(57)【特許請求の範囲】
【請求項１】
資源を共有する複数のタスクを実行するホストと、
デッドロックチェック装置と
を備え、
前記ホストは、前記タスクのそれぞれにプライオリティを定め、
前記デッドロックチェック装置は、
前記タスクのうちの一のタスクが、前記資源の一を待つ待ち状態に入ることにより発生するデッドロックを検出する検出部と、
前記デッドロックが検出されたとき、前記タスクのうちから、ロックしている資源を解放する候補となる少なくとも一以上の資源解放候補タスクを、前記プライオリティに基づいて選択する資源解放候補タスク選択部と、
前記タスクのうちから、前記資源を解放する資源解放タスクを選択する資源解放タスク選択部と
を含み、
前記資源解放タスク選択部は、前記一のタスクが前記資源解放候補に一致するとき、前記一のタスクを、前記資源解放タスクとして選択し、且つ、
前記一のタスクが前記資源解放候補に一致しないとき、前記資源解放候補タスクの処理の進行程度と、前記一のタスクの処理の進行程度とに基づいて、前記資源解放候補タスクと前記一のタスクとのいずれかを、前記資源解放タスクとして選択する
計算機システム。
【請求項２】
請求項１に記載の計算機システムにおいて、
前記資源解放タスク選択部は、前記資源解放候補タスクの数に基づいて、前記資源解放タスクを選択する
計算機システム。
【請求項３】
請求項２に記載の計算機システムにおいて、
前記資源解放タスク選択部は、前記資源解放候補タスクの数が、所定の基準数以上であるとき、前記資源解放候補タスクの処理の進行程度と前記一のタスクの処理の進行程度とに基づいて、前記資源解放タスクを選択し、且つ、前記資源解放候補タスクの数が、前記基準数より小さいとき、前記資源解放候補タスクを前記資源解放タスクとして選択する
計算機システム。
【請求項４】
資源を共有しながら複数のタスクを実行するホスト群と、
デッドロックチェック装置と
を備え、
前記ホスト群は、前記タスクのそれぞれにプライオリティを定め、
前記デッドロックチェック装置は、
前記タスクのうちの一のタスクが、前記資源の一を待つ待ち状態に入ることにより発生するデッドロックを検出する検出部と、
前記デッドロックが検出されたとき、前記タスクのうちから、ロックしている資源を解放する候補となる少なくとも一以上の資源解放候補タスクを、前記プライオリティに基づいて選択する資源解放候補タスク選択部と、
前記タスクのうちから、前記資源を解放する資源解放タスクを選択する資源解放タスク選択部と
を含み、
前記資源解放タスク選択部は、前記一のタスクが前記資源解放候補に一致するとき、前記一のタスクを、前記資源解放タスクとして選択し、且つ、
前記一のタスクが前記資源解放候補に一致しないとき、前記資源解放候補タスクの処理の進行程度と、前記一のタスクの処理の進行程度とに基づいて、前記資源解放候補タスクと前記一のタスクとのいずれかを、前記資源解放タスクとして選択する
マルチプロセッサシステム。
【請求項５】
（ａ）資源を共有する複数のタスクを実行するステップと、
（ｂ）前記タスクのそれぞれにプライオリティを定めるステップと、
（ｃ）前記タスクのうちの一のタスクが、前記資源の一を待つ待ち状態に入ることにより発生するデッドロックを検出するステップと、
（ｄ）前記デッドロックが検出されたとき、前記タスクのうちから、ロックしている資源を解放する候補となる少なくとも一以上の資源解放候補タスクを、前記プライオリティに基づいて選択するステップと、
（ｅ）前記一のタスクが前記資源解放候補に一致するとき、前記一のタスクを、前記資源を解放する資源解放タスクとして選択し、且つ、
前記一のタスクが前記資源解放候補に一致しないとき、前記資源解放候補タスクの処理の進行程度と、前記一のタスクの処理の進行程度とに基づいて、前記資源解放候補タスクと前記一のタスクとのいずれかを、前記資源解放タスクとして選択するステップと
を備えている
デッドロック解除方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、疎結合マルチプロセッサシステムに関する。本発明は、特に、デッドロックを解消するデッドロック解除処理が行われる疎結合マルチプロセッサシステムに関する。
【０００２】
【従来の技術】
複数の計算機が資源（Ｒｅｓｏｕｒｃｅ）を共有して処理を実行する疎結合マルチプロセッサシステムが広く使用されている。疎結合マルチプロセッサシステムでは、複数のタスクが、複数の計算機によって同時的に実行される。
【０００３】
疎結合マルチプロセッサシステムでは資源が共有されているため、タスクの処理に必要な資源が、そのタスクの処理に即時に使用可能であるとは限らない。例えば、一のタスクの処理に、ある資源が必要とするときに、その資源が、他のタスクによって使用されていたとする。この場合、その一のタスクの処理は、その資源が空くまで待たされる。
【０００４】
以下では、あるタスクＡが、ある資源ｘを使用することを、タスクＡが資源ｘをロックすると表現する。また、あるタスクがある資源をロックしている状態をロック状態という。更に、あるタスクが、ある資源が空くまで待っている状態を、待ち状態という。タスクＡが、ある資源ｘが空くまで待っているとき、タスクＡは、資源ｘを待つ待ち状態にあると表現する。
【０００５】
このような疎結合マルチプロセッサシステムでは、いわゆる、「デッドロック」と呼ばれる状態が発生することがある。例えば、タスクＡが資源ｘをロックしており、且つ、資源ｙを待つ待ち状態にあるとする。更に、このとき、タスクＢが資源ｙをロックしているとする。このとき、タスクＢが資源ｘを待つ待ち状態になると、タスクＡ、Ｂは永遠に完了しない。即ち、デッドロックが発生する。デッドロックは、輪と表現されることがある。即ち、「デッドロックが発生する」ことは、「輪が発生する」と表現されることがある。
【０００６】
ある一のタスクがある一の資源を待つ待ち状態に入ることにより、デッドロックの輪は、多重に発生することがある。例えば、図９（ａ）に示されているように、タスクＡは、資源ｘを待つ待ち状態にあり、且つ、資源ｚをロックしているとする。また、タスクＢは、資源ｙを待つ待ち状態にあり、且つ、資源ｚをロックしているとする。タスクＣが資源ｘと資源ｙとをロックしているとする。
【０００７】
このときに、図９（ｂ）に示されているように、タスクＣが資源ｚを待つ待ち状態に入ると、２つのデッドロックの輪９０１、９０２が発生する。タスクＡは、資源ｘを待つ待ち状態にあり、且つ、資源ｚをロックしている。資源ｘをロックしているタスクＣが、タスクＣが資源ｚを待つ待ち状態に入ると、輪９０１が完成し、デッドロックが発生する。更に、タスクＢは、資源ｙを待つ待ち状態にあり、且つ、資源ｚをロックしている。資源ｙをロックしているタスクＣが、タスクＣが資源ｚを待つ待ち状態に入ると、輪９０２が発生する。このように、タスクＣが資源ｚを待つ待ち状態に入ることにより、２つの輪９０１、９０２が発生する。ある一のタスクがある一の資源を待つ待ち状態に入ることにより、更に多くのデッドロックの輪が発生し得る。
【０００８】
デッドロックは、デッドロックに関与するいずれか一のタスクが資源をロックすることを中止し、そのタスクが使用している資源が強制的に解放されることにより解消される。上述の例では、タスクＡが資源ｘを解放するか、タスクＢが資源ｙを解放するか、又は、タスクＣが資源ｘ及び資源ｙを解放すれば、デッドロックは解消される。
【０００９】
デッドロックに関与するタスクのうち、どのタスクが資源を解放するかは、タスクの処理の効率に多大な影響を与える。あるタスクがロックしている資源を強制的に解放することは、そのタスクがその資源を使用して行っている処理を強制的に中断することを意味する。状況によっては、資源を解放したタスクの一部、又は全部をやり直す必要がある場合もある。どのタスクが資源を開放するかは、適切に定められる必要がある。
【００１０】
デッドロックを解除することによりシステムに与える影響を小さくすることを目的としたデッドロック解除方式が、公開特許公報（特開平２−４０７６１）に開示されている。公知のそのデッドロック解除方式では、タスクのそれぞれに、プライオリティ（優先度）が定められている。デッドロックの輪の中にあるタスクのうち、プライオリティが最も低いタスクが、ロックしている資源を解放する。これにより、重要度が高いタスクが中断されることが避けられている。
【００１１】
しかし公知のそのデッドロック解除方式では、多重にデッドロックが発生したときに、多数のタスクが、ロックしている資源を強制的に解放する事態が発生しうる。最悪の場合、デッドロックを解除するために、発生したデッドロックの数と同じ数のタスクが資源を解放する場合がある。
【００１２】
例えば、図９に示されている例について考える。タスクＡとタスクＢのプライオリティがいずれも、タスクＣのプライオリティよりも低いとする。この場合、公知のデッドロック解除方式では、輪９０１を解除するために、タスクＡが資源を解放するタスクとして選択される。更に、輪９０２を解除するために、タスクＢが資源を解放するタスクとして選択される。このように、タスクＡとタスクＢは、ロックしている資源を強制的に解放させられ、タスクＡとタスクＢとの処理が強制的に中断される。
【００１３】
多数のタスクの処理が中断することにより、全体として、タスクの処理効率が低下する場合がある。例えば、上述の例において、タスクＡとタスクＢとの処理のほとんど完了に近づいており、且つ、タスクＣの処理が初期段階にある場合を考える。この場合に、プライオリティが高いタスクＣの処理を行うために、タスクＡとタスクＢとが、強制的に資源を解放させられ、その処理が中断されることになる。このとき、タスクＡとタスクＢの処理を再度行うことが必要となると、システム全体で考えた場合、タスクの処理効率が低下する。
【００１４】
上述の例では、資源を解放するタスクは２つであるが、更に多数のタスクが資源を強制的に解放させられることもあり得る。
【００１５】
デッドロックを解除する場合、必要以上に多くのタスクに資源を解放させずに、デッドロックが解消されることが好ましい。
【００１６】
【発明が解決しようとする課題】
本発明の目的は、タスクの処理効率の低下を防ぎながら、デッドロックが解消される疎結合マルチプロセッサシステムを提供することにある。
【００１７】
本発明の他の目的は、必要以上に多くのタスクに資源を解放させずに、デッドロックが解消される疎結合マルチプロセッサシステムを提供することにある。
【００１８】
本発明の更に他の目的は、タスクの進行程度に応じて、資源を解放するタスクが選択される疎結合マルチプロセッサシステムを提供することにある。
【００１９】
【課題を解決するための手段】
以下に、［発明の実施の形態］で使用される番号・符号を用いて、課題を解決するための手段が説明される。これらの番号・符号は、［特許請求の範囲］の記載と［発明の実施の形態］の記載との対応関係を明らかにするために付加されている。但し、付加された番号・符号は、［特許請求の範囲］に記載されている発明の技術的範囲の解釈に用いてはならない。
【００２０】
本発明による疎結合マルチプロセッサシステムは、複数の資源を共有しながら複数のタスクを実行するホスト群（２００）と、デッドロックチェック装置（１０１）とを備えている。ホスト群（２００）は、タスクのそれぞれにプライオリティを定める。デッドロックチェック装置（１０１）は、検出部（１０３）と、資源解放タスク選択部（１０３）とを含む。検出部（１０３）は、複数のタスクのうちの一のタスクが、資源のうちの一を待つ待ち状態に入ることにより発生するデッドロックを検出する。資源解放タスク選択部（１０３）は、デッドロックが検出されたとき、タスクそれぞれの処理の進行程度と、タスクそれぞれに定められたプライオリティとに基づいて、既述の複数のタスクのうちから、ロックしている資源を解放する資源解放タスクを選択する。
【００２１】
本発明による疎結合マルチプロセッサシステムは、資源を共有しながら複数のタスクを実行するホスト群（２００）と、デッドロックチェック装置（１０１）とを備えている。ホスト群（２００）は、タスクのそれぞれにプライオリティを定める。デッドロックチェック装置（１０１）は、検出部（１０３）と、資源解放候補タスク選択部（１０３）と、資源解放タスク選択部（１０３）とを含む。検出部（１０３）は、複数のタスクのうちの一のタスクが、資源の一を待つ待ち状態に入ることにより発生するデッドロックを検出する。資源解放候補タスク選択部（１０３）は、デッドロックが検出されたとき、タスクのうちから、ロックしている資源を解放する候補となる少なくとも一以上の資源解放候補タスクを、タスクに定められたプライオリティに基づいて選択する。資源解放タスク選択部（１０３）は、タスクのうちから、資源を解放する資源解放タスクを選択する。資源解放タスク選択部（１０３）は、前記一のタスクが資源解放候補タスクに一致するとき、前記一のタスクを、資源解放タスクとして選択する。また、資源解放タスク選択部（１０３）は、前記一のタスクが前記資源解放候補に一致しないとき、前記資源解放候補タスクの処理の進行程度と、前記一のタスクの処理の進行程度とに基づいて、前記資源解放候補タスクと前記一のタスクとのいずれかを、前記資源解放タスクとして選択する。
【００２２】
このとき、資源解放タスク選択部（１０３）は、資源解放候補タスクの数に基づいて、前記資源解放タスクを選択することが好ましい。
【００２３】
前記資源解放タスク選択部（１０３）は、前記資源解放候補タスクの数が、所定の基準数以上であるとき、前記資源解放候補タスクの処理の進行程度と前記一のタスクの処理の進行程度とに基づいて、前記資源解放タスクを選択し、且つ、前記資源解放候補タスクの数が、前記基準数より小さいとき、前記資源解放候補タスクを前記資源解放タスクとして選択することが好ましい。
【００２４】
本発明による疎結合マルチプロセッサシステムは、資源を共有しながら複数のタスクを実行するホスト群（２００）と、デッドロックチェック装置（１０１）とを備えている。ホスト群（２００）は、前記タスクのそれぞれにプライオリティを定める。デッドロックチェック装置（１０１）は、検出部（１０３）と、資源解放候補タスク選択部（１０３）と、資源解放タスク選択部（１０３）とを含む。検出部（１０３）は、タスクのうちの一のタスクが、前記資源の一を待つ待ち状態に入ることにより発生するデッドロックを検出する。資源解放候補タスク選択部（１０３）は、デッドロックが検出されたとき、前記タスクのうちから、前記資源を解放する候補である少なくとも一以上の資源解放候補タスクを、前記プライオリティに基づいて選択する。資源解放タスク選択部（１０３）は、資源解放候補タスクと、前記一のタスクとのいずれかを、前記資源を解放する資源解放タスクとして選択する。このとき、資源解放タスク選択部（１０３）は、前記資源解放候補タスクの数に基づいて、前記資源解放タスクを選択する。
【００２５】
資源解放タスク選択部（１０３）は、前記資源解放候補タスクの数が、所定の基準数より小さいとき、前記資源解放候補タスクを前記資源解放タスクとして選択することが好ましい。
【００２６】
前記デッドロックの輪は複数であることがある。このとき、資源解放タスク選択部（１０３）は、デッドロックのそれぞれについて、前記タスクのうちの前記デッドロックに関与する関与タスクから、前記プライオリティが最も低いものを前記資源解放候補タスクの一として選択することが好ましい。
【００２７】
本発明によるデッドロック解除方法は、（ａ）複数の資源を共有しながら複数のタスクを実行するステップと、
（ｂ）前記タスクのそれぞれにプライオリティを定めるステップと、
（ｃ）前記タスクのうちの一のタスクが、前記資源の一を待つ待ち状態に入ることにより発生するデッドロックを検出するステップと、
（ｄ）前記デッドロックが検出されたとき、ロックしている資源を解放する資源解放タスクを、前記タスクそれぞれの処理の進行程度と前記プライオリティとに基づいて、前記タスクのうちから選択するステップ
とを備えている。
【００２８】
【発明の実施の形態】
以下、添付図面を参照しながら、本発明による疎結合マルチプロセッサシステムの実施の一形態を説明する。
【００２９】
本発明による疎結合マルチプロセッサシステムの実施の一形態では、図１に示されているように、デッドロックチェック装置１０１が複数のホスト２００ともに設けられている。ホスト２００のそれぞれは、デッドロックチェック装置１０１に接続されている。ホスト２００は、複数のタスクを実行する。そのタスクは、資源を共有する。資源とは、タスクを実行するために必要なハードウエア、及びソフトウエアをいう。但し、図１には、その資源は、図示されていない。タスクのそれぞれには、ホスト２００により、プライオリティが設定される。
【００３０】
ホスト２００は、登録／削除要求信号６００を発信する。登録／削除要求信号６００は、どのタスクが、どの資源をロックしているロック状態にあるか、又は、どのタスクが、どの資源を待つ待ち状態にあるかをデッドロックチェック装置１０１に知らせるための信号である。
【００３１】
以下において、どのタスクが、どの資源をロックしているロック状態に入ろうとしているかを知らせることをロック要求といい、どのタスクが、どの資源を待つ待ち状態に入ろうとしているかをデッドロックチェック装置１０１に知らせることを、待ち要求ということがある。
【００３２】
ホスト２００は、あるタスクが、ある資源をロックすると登録／削除要求信号６００を発信して、ロック状態の発生をデッドロックチェック装置１０１に知らせる。即ち、ホスト２００は、登録／削除要求信号６００を発信して、ロック要求を行う。このときホスト２００は、ロック状態になったタスクについて処理進行ポイントを定め、登録／削除要求信号６００によってデッドロックチェック装置１０１に知らせる。処理進行ポイントとは、タスクの処理の進行程度を表すポイントであり、タスクの処理の進行程度が進むほど、大きな値を取る。処理進行ポイントは、タスクの処理の開始時には小さな値をとり、タスクの処理の後半では、大きな値をとる。ロック要求は、処理進行ポイントとともにデッドロックチェック装置１０１に登録される。
【００３３】
更に、ホスト２００は、あるタスクが、ある資源を待つ待ち状態に入ろうとすると、登録／削除要求信号６００を発信して、待ち状態の発生をデッドロックチェック装置１０１に知らせる。即ち、ホスト２００は、登録／削除要求信号６００を発信して、待ち要求を行う。このときホスト２００は、待ち状態になったタスクについて処理進行ポイントを定め、登録／削除要求信号６００によってデッドロックチェック装置１０１に知らせる。待ち要求は、処理進行ポイントとともにデッドロックチェック装置１０１に登録される。
【００３４】
また、ホスト２００は、あるタスクがある資源を解放したとき、即ち、あるタスクがある資源をロックするロック状態から脱したとき、登録／削除要求信号６００を発信して、ロック状態が終了したことをデッドロックチェック装置１０１に知らせる。デッドロックチェック装置１０１は、ロック状態が終了したことを知ると、そのロック状態に対応するロック要求の登録を削除する。
【００３５】
更に、ホスト２００は、あるタスクが、ある資源を待つ待ち状態から脱すると、登録／削除要求信号６００を発信して、待ち状態が終了したことをデッドロックチェック装置１０１に知らせる。デッドロックチェック装置１０１は、待ち状態が終了したことを知ると、その待ち状態に対応する待ち要求の登録を削除する。
【００３６】
以下では、デッドロックチェック装置１０１がロック要求又は待ち要求の登録の要求を行う契機となったタスクを要求元タスクと呼ぶこととする。即ち、タスクＡが資源ｘをロックするロック状態になったとする。ホスト２００は、タスクＡが資源ｘをロックするロック状態になったことを通知する待ち要求を行う。このような場合に、タスクＡは、要求元タスクと呼ばれる。同様に、タスクＡが資源ｘを待つ待ち状態になったとする。ホスト２００は、タスクＡが資源ｘを待つ待ち状態になったことを通知する待ち要求を行う。このような場合に、タスクＡは、要求元タスクと呼ばれる。
【００３７】
更に、ホスト２００がロック要求又は待ち要求の削除の要求を行う契機となったタスクも同様に、要求元タスクと呼ばれる。
【００３８】
図３は、ホスト２００が発信する登録／削除要求信号６００のフォーマットを示す。登録／削除要求信号６００は、種別６０１、タスクＩＤ６０２、資源ＩＤ６０３、プライオリティ情報６０４、状態情報６０５、ポイント情報６０６を伝送する。種別６０１は、登録／削除要求信号６００がロック要求又は待ち要求の登録を要求しているのか、若しくは、ロック要求又は待ち要求の登録の削除を要求しているのかを示す。タスクＩＤ６０２は、ロック要求又は待ち要求の対象であるタスクのＩＤ番号である。資源ＩＤ６０３は、ロック要求又は待ち要求の対象である資源のＩＤ番号である。プライオリティ６０４は、登録又は削除の対象であるタスクのプライオリティを示す。状態６０５は、登録又は削除の対象がロック状態なのか待ち状態なのかを示す。処理進行ポイント６０６は、ロック要求又は待ち要求の対象であるタスクの処理進行ポイントを示す。処理進行ポイント６０６は、登録又は削除の対象であるタスクの処理の進行程度に応じて定められる。
【００３９】
登録／削除要求信号６００を受け取るデッドロックチェック装置１０１は、図２に示されているように、入出力制御部１０２、デッドロックチェック制御部１０３、記憶部１０４を含む。入出力制御部１０２、デッドロックチェック制御部１０３、記憶部１０４は、互いに接続されている。記憶部１０４は、デッドロックチェックテーブル１４１とプッシュアウトテーブル１４２とを記憶する。デッドロックチェックテーブル１４１には、どのタスクがどの資源をロックしているロック状態にあるかが登録され、更に、どのタスクが、どの資源を待つ待ち状態にあるかが登録される。プッシュアウトテーブル１４２には、資源を解放する候補となるタスクが一時的に登録される。
【００４０】
入出力制御部１０２は、登録／削除要求信号６００を受信する。入出力制御部１０２は、登録／削除要求信号６００を参照し、ホスト２００が発する登録／削除要求信号６００が待ち要求であるのか否かを検出する。入出力制御部１０２は、登録／削除要求信号６００が待ち要求であることを検出すると、デッドロックチェックを行うことを指示するデッドロックチェック指示信号６１０をデッドロックチェック制御部１０３に出力する。デッドロックチェックは、入出力制御部１０２が、待ち要求を検出する毎に行われる。
【００４１】
更に、入出力制御部１０２は、登録／削除要求信号６００を参照して、デッドロックチェックテーブル１４１にロック要求を登録する。「デッドロックチェックテーブル１４１にロック要求を登録する」とは、デッドロックチェックテーブル１４１に、どのタスクがどの資源をロックしているロック状態にあるかを登録することを意味する。更に入出力制御部１０２は、登録／削除要求信号６００を参照して、デッドロックチェックテーブル１４１に待ち要求を登録する。「デッドロックチェックテーブル１４１に待ち要求を登録する」とは、デッドロックチェックテーブル１４１に、どのタスクが、どの資源を待つ待ち状態にあるかを登録することを意味する。
【００４２】
図４は、デッドロックチェックテーブル１４１のフォーマットを示す。デッドロックチェックテーブル１４１は、タスクテーブル３５０、要求テーブル３６０、及び資源テーブル３７０を含む。タスクテーブル３５０には、タスクエントリ４００が登録されている。要求テーブル３６０には、要求エントリ４２０が登録されている。資源テーブル３７０には、資源エントリ４１０が登録されている。
【００４３】
タスクエントリ４００には、図５（ａ）に示されているように、タスクのタスクＩＤ４０１と、そのタスクのプライオリティ４０２とが登録されている。入出力制御部１０２により登録／削除要求信号６００からタスクＩＤ６０２が抽出され、抽出されたタスクＩＤ６０２は、タスクＩＤ４０１としてタスクエントリ４００に登録される。更に、入出力制御部１０２により、登録／削除要求信号６００からプライオリティ６０４が抽出され、抽出されたタスクＩＤ６０２は、プライオリティ４０２としてタスクエントリ４００に登録される。
【００４４】
資源エントリ４１０には、図５（ｃ）に示されているように、タスクがロックしている資源又はタスクを待たせている資源の資源ＩＤ４１１が登録されている。入出力制御部１０２により登録／削除要求信号６００から資源ＩＤ６０３が抽出され、抽出された資源ＩＤ６０３が資源ＩＤ４１１として資源エントリ４１０に登録される。
【００４５】
要求エントリ４２０には、状態４２１と、処理進行ポイント４２２と、Ｓポインタ４２３と、Ｒポインタ４２４とが登録されている。
【００４６】
状態４２１は、要求エントリ４２０が、ロック要求（Ｈ）であるのか、待ち要求（Ｗ）であるのかの別を示す。入出力制御部１０２により、登録／削除要求信号６００から状態６０５が抽出され、状態４２１として要求エントリ４２０に登録される。
【００４７】
処理進行ポイント４２２は、登録されたタスクの処理進行ポイントである。登録／削除要求信号６００から処理進行ポイント６０６が抽出され、処理進行ポイント４２２として要求エントリ４２０に登録される。
【００４８】
Ｓポインタ４２３は、記憶部１０４のうちの、要求エントリ４２０に対応するタスクエントリ４００が記憶されている部分のアドレスを示す。
【００４９】
Ｒポインタ４２４は、記憶部１０４のうちの、要求エントリ４２０に対応するタスクエントリ４００が記憶された部分のアドレスを示す。
【００５０】
デッドロックチェック制御部１０３は、入出力制御部１０２からデッドロックチェック指示信号６１０を受信すると、上述の構成を有するデッドロックチェックテーブル１４１を参照して、デッドロックチェックを行う。デッドロックが発生している場合、デッドロックチェック制御部１０３は、デッドロックチェックテーブル１４１に基づいて、資源を解放するタスクを決定する。
【００５１】
より詳細には、資源を解放するタスクは、以下のようにして決定される。あるタスクが待ち状態になり、ホスト２００からの待ち要求があったとする。まず、デッドロックチェック制御部１０３は、プッシュアウトテーブル１４２には、デッドロックに関与するタスクそれぞれのプライオリティに基づいて、資源を解放する候補となるタスクを定める。デッドロックチェック制御部１０３は、資源を解放する候補となるタスクを、一時的にプッシュアウトテーブル１４２に登録する。デッドロックに関与するタスクのうち、最もプライオリティが低いタスクが、資源を解放する候補としてプッシュアウトテーブル１４２に登録される。デッドロックが多重に発生している場合には、デッドロックの輪ごとにプライオリティが最も低いタスクが定められ、定められたタスクがプッシュアウトテーブル１４２に登録される。デッドロックが多重に発生している場合、プッシュアウトテーブル１４２には、複数のタスクが登録されることになる。
【００５２】
図６は、プッシュアウトテーブル１４２の構成を示す。プッシュアウトテーブル１４２には、資源を解放する候補であるタスクのそれぞれについて、そのタスクのタスクＩＤ、そのタスクがロックしている資源の資源ＩＤ、そのタスクのプライオリティ、及びそのタスクの処理進行ポイントとが登録される。
【００５３】
プッシュアウトテーブル１４２に登録されたタスクの数が、所定の基準数ｎ未満である場合、プッシュアウトテーブル１４２に登録されたタスクが資源を解放するタスクであると定められる。
【００５４】
プッシュアウトテーブル１４２に登録されたタスクの数が、所定の基準数ｎ以上である場合、プッシュアウトテーブル１４２に登録されたタスクの処理進行ポイントの平均値と、ホスト２００からの待ち要求の契機となった要求元タスクの処理進行ポイントとが比較される。その平均値が要求元タスクの処理進行ポイント以下であれば、プッシュアウトテーブル１４２に登録されたタスクが資源を解放するタスクであると定められる。一方、その平均値が、要求元タスクの処理進行ポイントよりも大きければ、要求元タスクが資源を解放するであると定められる。プッシュアウトテーブル１４２に登録されたタスクの数が、所定の基準数ｎ以上であり、且つ、プッシュアウトテーブル１４２に登録されたタスクの処理の進行程度が大きい場合には、プッシュアウトテーブル１４２に登録されたタスクは、資源を解放するタスクとは定められない。これにより、処理が進行している数多くのタスクが、強制的に中断されることが防がれる。処理のやり直しに多くの処理量が必要となる事態が発生しにくい。
【００５５】
図７は、本発明による疎結合マルチプロセッサシステムの動作を示すフローチャートである。
【００５６】
ホスト２００が実行しているタスクが、ある資源をロックしてロック状態になる、又は、ある資源に対する待ち状態になると、ホスト２００は、登録／削除要求信号６００を発信して、デッドロックチェック装置１０１に対してロック要求又は待ち要求を行う。デッドロックチェック装置１０１の入出力制御部１０２は、登録／削除要求信号６００を受けとって、ロック要求又は待ち要求をデッドロックチェックテーブル１４１に登録する（Ｓ７０１）。より詳細には、以下のようにして、ロック要求又は待ち要求がデッドロックチェックテーブル１４１に登録される。
【００５７】
入出力制御部１０２は、要求テーブル３６０に要求エントリ４２０を一つ作成する。更に入出力制御部１０２は、登録／削除要求信号６００に含まれる状態６０５と処理進行ポイント６０６とを要求エントリ４２０に登録する。更に、登録／削除要求信号６００のタスクＩＤ６０２が示すタスクＩＤと同一のタスクＩＤを有するタスクエントリ４００がタスクテーブル３５０に登録されていない場合、入出力制御部１０２は、タスクテーブル３５０にタスクエントリ４００を新たに一つ作成する。この場合、入出力制御部１０２は、作成されたタスクエントリ４００に、登録／削除要求信号６００のタスクＩＤ６０２と、処理進行ポイント６０６とを登録する。
【００５８】
更に、登録／削除要求信号６００の資源ＩＤ６０３が示す資源ＩＤと同一の資源ＩＤを有する資源エントリ４１０が資源テーブル３７０に登録されていない場合、入出力制御部１０２は、資源テーブル３７０に資源エントリ４１０を新たに一つ作成する。この場合、入出力制御部１０２は、作成された資源エントリ４１０に、登録／削除要求信号６００の資源ＩＤ６０３を登録する。
【００５９】
以上の過程により、ロック要求又は待ち要求が、デッドロックチェックテーブル１４１に登録される。
【００６０】
続いて、新たにロック要求又は待ち要求のいずれが登録されたのかが判断される（Ｓ７０２）。その判断は、登録／削除要求信号６００の状態６０５を参照して行われる。新たにロック要求が登録された場合には、ロック要求が登録された旨が、ロック要求を行ったホスト２００に通知され、処理は正常終了する（Ｓ７０７）。
【００６１】
新たに待ち要求が登録された場合には、入出力制御部１０２は、デッドロックチェック制御部１０３にデッドロックチェック指示信号６１０を送信する。デッドロックチェック制御部１０３は、デッドロックチェックテーブル１４１を参照してデッドロックチェックを行う（Ｓ７０３）。
【００６２】
図４において、要求エントリ４２０−１が新たに登録されたとする。即ち、タスクＴ３の資源Ｒ３に対する待ち要求（Ｗ３）が新たに登録されたとする。資源Ｒ３は、タスクＴ１によるロック状態（Ｈ１）にある。タスクＴ１は、資源Ｒ１に対する待ち状態にある（Ｗ１）。資源Ｒ１は、待ち要求の契機となった要求元タスクであるタスクＴ３によりロックされている。即ち、デッドロックの輪３６１が発生している。同様に、タスクＴ３の資源Ｒ３に対する待ち要求（Ｗ３）により、デッドロックの輪３６２も発生している。
【００６３】
デッドロックの輪が発生している場合、デッドロックチェック制御部１０３は、発生しているデッドロックの輪のうちの一の輪を選択する。更に、そのデッドロックの輪に関与しているタスクの中で、最もプライオリティが低いタスクを選択する（Ｓ７０４）。更に、デッドロックチェック制御部１０３は、そのタスクが、新たになされた待ち要求の契機となった要求元タスクであるのか否かを判断する（Ｓ７０５）。デッドロックチェック制御部１０３は、選択されたタスクが要求元タスクでない場合、選択されたタスクをプッシュアウトテーブル１４２に登録する（Ｓ７０６）。プッシュアウトテーブル１４２には、選択されたタスクのタスクＩＤ、そのタスクがロックしている資源の資源ＩＤ、そのタスクのプライオリティ、及び、そのタスクの処理進行ポイントが登録される。更に、デッドロックチェック制御部１０３は、選択されたタスクを、デッドロックチェックテーブル１４１から削除する（Ｓ７０６）。選択されたタスクがデッドロックチェックテーブル１４１から削除されることにより、一のデッドロックの輪が、暫定的に解消される。
【００６４】
デッドロックの輪が全て解消されているかが再度チェックされる（Ｓ７０３）。他のデッドロックの輪が発生していれば、その輪についても、同様に、そのデッドロックの輪に関与しているタスクの中で、最もプライオリティが低いタスクが選択される（Ｓ７０５）。選択されたタスクが、新たになされた待ち要求の契機となった要求元タスクでない場合（Ｓ７０５）、そのタスクがプッシュアウトテーブル１４２に登録され、更に、デッドロックチェックテーブル１４１から削除される（Ｓ７０６）。プッシュアウトテーブル１４２に登録されたタスクは、資源を解放する候補であるタスクである。このように、デッドロックの輪のそれぞれについて、資源を解放する候補であるタスクが、プライオリティに基づいて選択され、プッシュアウトテーブル１４２に登録される。
【００６５】
一方、新たになされた待ち要求の契機となった要求元タスクが、デッドロックの輪に関与するタスクの中で最もプライオリティが低いタスクである場合、その要求元タスクが、資源を解放するタスクであると決定される。新たになされた待ち要求がデッドロックチェックテーブル１４１から削除される（Ｓ７１０）。デッドロックチェックテーブル１４１は、待ち要求がある以前の状態に戻る。このとき、プッシュアウトテーブル１４２にタスクが登録されている場合（Ｓ７１１）、そのタスクは、デッドロックチェックテーブル１４１に復旧される（Ｓ７１２）。更に、デッドロックチェック制御部１０３は、入出力制御部１０２を介して、待ち要求を行ったホスト２００に、待ち要求の登録ができなかった旨の終了報告を行う（Ｓ７１３）。要求元タスクが待ち状態に入ることが拒絶され、デッドロックは解消される。
【００６６】
全てのデッドロックの輪が暫定的に解消される、又は、全くデッドロックの輪が発生していない場合、更に、プッシュアウトテーブル１４２にタスクが登録されているか否かが判断される（Ｓ７０８）。プッシュアウトテーブル１４２に全くタスクが登録されていない場合とは、そもそもデッドロックが発生していない場合である。デッドロックチェック制御部１０３は、待ち要求が正常に登録されたことを、待ち要求を行ったホスト２００に入出力制御部１０２を介して通知する。
【００６７】
一方、プッシュアウトテーブル１４２にタスクが登録されている場合、プッシュアウト処理が行われる（Ｓ７１４）。図８は、プッシュアウト処理（Ｓ７１４）を示す。まず、デッドロックチェック制御部１０３は、プッシュアウト対象のタスク数、即ち、プッシュアウトテーブル１４２に登録されているタスクの数がｎ以上であるか否かを判断する（Ｓ８１５）。プッシュアウト対象のタスク数がｎ未満であるとき、デッドロックチェック制御部１０３は、プッシュアウトテーブル１４２に登録された資源を解放するタスクであると決定する、即ち、デッドロックチェック制御部１０３は、プッシュアウトテーブル１４２に登録されたタスクがプッシュアウトされると決定する（Ｓ８１６）。デッドロックチェック制御部１０３は、入出力制御部１０２を介して、プッシュアウトテーブル１４２に登録されたタスクがプッシュアウトされることをホスト２００に通知する。その通知をうけたホスト２００は、プッシュアウトテーブル１４２に登録されたタスクに、強制的に資源を解放させる。更に、デッドロックチェック制御部１０３は、入出力制御部１０２を介して、待ち要求を行ったホストに、待ち要求が正常に行われたことを通知する（Ｓ８１７）。プライオリティに基づいて選択された、資源を解放するタスクの候補が、所定の基準数ｎよりも少ない場合には、プライオリティに基づいて選択されたタスクが資源を解放するタスクとなる。
【００６８】
一方、プッシュアウト対象のタスク数がｎ以上であるとき、即ち、プッシュアウトテーブル１４２に登録されているタスクの数がｎ以上であるとき、デッドロックチェック制御部１０３は、プッシュアウトテーブル１４２に登録されているタスクの処理進行ポイントの平均値ＡＶＧを算出する（Ｓ８１８）。更に、平均値ＡＶＧが、待ち要求の契機となった要求元タスクの処理進行ポイント以上であるか否かが判断される（Ｓ８１９）。
【００６９】
平均値ＡＶＧが、要求元タスクの処理進行ポイントよりも小さい場合、デッドロックチェック制御部１０３は、プッシュアウトテーブル１４２に登録されたタスクがプッシュアウトされると決定する（Ｓ８１６）。即ち、プライオリティに基づいて、資源を解放する候補として選択されたタスクの処理の進行程度が小さい場合、その数が多くても、プライオリティに基づいて選択されたタスクが、資源を解放するタスクと定められる。デッドロックチェック制御部１０３は、入出力制御部１０２を介して、プッシュアウトテーブル１４２に登録されたタスクがプッシュアウトされることをホスト２００に通知する。その通知をうけたホスト２００は、プッシュアウトテーブル１４２に登録されたタスクに、強制的に資源を解放させる。更に、デッドロックチェック制御部１０３は、入出力制御部１０２を介して、待ち要求を行ったホストに、待ち要求が正常に行われたことを通知する（Ｓ８１７）。
【００７０】
一方、平均値ＡＶＧが、要求元タスクの処理進行ポイント以上である場合、要求元タスクが、資源を解放するタスクであると選択される。プッシュアウトテーブル１４２に登録されたタスクは、デッドロックテーブル１４１に戻される（Ｓ８２０）。更に、新たになされた待ち要求がデッドロックチェックテーブル１４１から削除される（Ｓ８２１）。これにより、デッドロックチェックテーブル１４１は、待ち要求がある以前の状態に戻る。更に、デッドロックチェック制御部１０３は、入出力制御部１０２を介して、待ち要求を行ったホスト２００に、待ち要求の登録ができなかった旨の終了報告を行う（Ｓ８２２）。
【００７１】
以上に説明されているように、本実施の形態では、待ち要求が発生する毎に、デッドロックチェックが行われる。デッドロックチェックにより、デッドロックの発生が検出されると、発生したデッドロックの輪のそれぞれについて、そのデッドロックの輪に関与するタスクのうち最もプライオリティが低いタスクが、資源を解放する候補となるタスクとして選択される。選択されたタスクは、プッシュアウトテーブル１４２に登録される。資源を解放する候補は、複数選択され得る。
【００７２】
資源を解放する候補としてプッシュアウトテーブル１４２に登録されたタスクの数が所定の基準数ｎよりも小さいとき、プッシュアウトテーブル１４２に登録されたタスクが資源を解放するタスクと決定される。一方、資源を解放する候補としてプッシュアウトテーブル１４２に登録されたタスクの数が所定の基準数ｎ以上である場合、プッシュアウトテーブル１４２に登録されたタスクの処理進行ポイントの平均と、待ち要求の契機となった要求元タスクの処理進行ポイントとが比較され、前者が、後者よりも大きいときは、待ち要求の登録が拒否される。
【００７３】
このように、本実施の形態では、必要以上に多くのタスクに資源を解放させずに、デッドロックが解消される。更に、プッシュアウトテーブル１４２に登録されたタスクと、要求元タスクとの処理進行ポイントが、資源を解放するタスクの選択に使用され、処理が進行しているタスクが資源を解放するタスクとして選択されることが防がれている。
【００７４】
【発明の効果】
本発明により、タスクの処理効率の低下を防ぎながら、デッドロックが解消される疎結合マルチプロセッサシステムが提供される。
【００７５】
また、本発明により、必要以上に多くのタスクに資源を解放させずに、デッドロックが解消される疎結合マルチプロセッサシステムが提供される。
【００７６】
また、本発明により、タスクの進行程度に応じて、資源を解放するタスクが選択される疎結合マルチプロセッサシステムが提供される。
【図面の簡単な説明】
【図１】図１は、本発明による実施の一形態の疎結合マルチプロセッサシステムを示す。
【図２】図２は、デッドロックチェック装置１０１の構成を示す。
【図３】図３は、登録／削除要求信号６００のフォーマットを示す。
【図４】図４は、デッドロックチェックテーブル１４１のフォーマットを示す。
【図５】図５（ａ）、（ｂ）、（ｃ）は、それぞれ、タスクエントリ４００、資源エントリ４１０、及び要求エントリ４２０のフォーマットを示す。
【図６】図６は、プッシュアウトテーブル１４２のフォーマットを示す。
【図７】図７は、本発明による実施の一形態の疎結合マルチプロセッサシステムの動作を示す。
【図８】図８は、プッシュアウト処理（Ｓ７１４）を示す。
【図９】図９は、一の待ち要求により多重のデッドロックが発生することを説明する図である。
【符号の説明】
１０１：デッドロックチェック装置
１０２：入出力制御部
１０３：デッドロックチェック制御部
１０４：記憶部
１４１：デッドロックチェックテーブル
１４２：プッシュアウトテーブル
２００：ホスト
６００：登録／削除要求信号
６１０：デッドロックチェック指示信号
３５０：タスクテーブル
３６０：要求テーブル
３７０：資源テーブル
４００：タスクエントリ
４１０：資源エントリ
４２０：要求エントリ
【図１】
0003567911.tif 000002
【図２】
0003567911.tif 000003
【図３】
0003567911.tif 000004
【図４】
0003567911.tif 000005
【図５】
0003567911.tif 000006
【図６】
0003567911.tif 000007
【図７】
0003567911.tif 000008
【図８】
0003567911.tif 000009
【図９】
0003567911.tif 000010