(57)【要約】マルチプロセッサ・システムにおけるプライマリ−バックアップ方式に基づく耐故障性の方法は、マルチプロセッサ・システム内のプロセッサに割り当てられるべきタスクを受け取ることと、通常のリアルタイム・スケジューリング・アルゴリズムにしたがって、タスクのプライマリ・バージョンを割り当てることと、タスクのプライマリ・バージョンの割り当ての妥当性を検査することと、オーバーローディングによってタスクのバックアップ・バージョンを割り当てることと、タスクのバックアップ・バージョンの割り当ての妥当性を検査することと、を含む。
2013533524.tif 000002
【特許請求の範囲】
【請求項１】
マルチプロセッサ・システムにおけるプライマリ−バックアップ方式に基づく耐故障性の方法は、
マルチプロセッサ・システム内のプロセッサに割り当てられるべきタスクを受け取ることと、
通常のリアルタイム・スケジューリング・アルゴリズムにしたがって、前記タスクのプライマリ・バージョンを割り当てることと、
前記タスクの前記プライマリ・バージョンの前記割り当ての妥当性を検査することと、
オーバーローディングによって前記タスクのバックアップ・バージョンを割り当てることと、
前記タスクの前記バックアップ・バージョンの前記割り当ての妥当性を検査することと、
を有する。
【請求項２】
前記プライマリ・バージョン及び前記バックアップ・バージョンの両方の前記割り当ての妥当性を検査することと前記バックアップ・バージョンの割り当てを行うこととは、アドバイザがスケジューラによって問い合わされたときに、前記アドバイザ内で実行され、前記アドバイザは前記スケジューラからは分離して設けられており、前記スケジューラは前記タスクの前記プライマリ・バージョンを割り当てる、請求項１に記載の方法。
【請求項３】
前記プライマリ・バージョンに対応するプロセッサ内で障害が発生したときに、前記バックアップ・バージョンを用いて前記障害に耐えることをさらに有する、請求項１または２に記載の方法。
【請求項４】
前記プライマリ・バージョンの前記割り当ての前記妥当性と前記バックアップ・バージョンの前記割り当ての前記妥当性との少なくとも１つが否定されたときに、対応するタスクが拒絶される、請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記タスクは少なくとも１つのタスク・セットとして管理され、各タスク・セットは、一緒にオーバーロードされるタスクの集合であり、前記タスクセットは、根付き有向木として取り扱われ、前記アドバイザは、前記タスクセットを用いて、前記通常のスケジューリング・アルゴリズムを過度に妨げないように前記バックアップ・バージョンを割り当てる、請求項２に記載の方法。
【請求項６】
前記タスクは少なくとも１つのタスク・セットとして管理され、各タスク・セットは、一緒にオーバーロードされるタスクの集合であり、
前記バックアップ・バージョンをそこにオーバーロードすることが可能なタスク・セットが存在し、かつ、所定の条件を満たすならば、前記アドバイザは、できるだけ既存のタスク・セットを詰めるよう前記既存のタスク・セットに前記バックアップ・バージョンがオーバーロードされるように前記バックアップ・バージョンをスケジューリングし、そうでなければ、前記アドバイザは、できるだけ遅い空きタイムスロットに前記バックアップ・バージョンをスケジューリングする、請求項２に記載の方法。
【請求項７】
前記アドバイザは、ユーザによって定義された時間長限界未満となるように、どのタスク・セットについてもその時間長を制御する、請求項６に記載の方法。
【請求項８】
前記タスク・セットは少なくとも１つの族として管理され、各族は、タスク・セットの集合であり、族を分解することによって障害に耐える、請求項５に記載の方法。
【請求項９】
前記タスクは少なくとも１つのタスク・セットとして管理され、各タスク・セットは、一緒にオーバーロードされるタスクの集合であり、
前記耐えることは、前記タスク・セットを再帰的に扱うことと、前記オーバーローディングを組み直すことと、を含む、請求項３に記載の方法。
【請求項１０】
プライマリ−バックアップに基づく、フォールト・トレラント・マルチプロセッサ・システムであって、
バスを介して相互に密結合した複数のプロセッサと、
タスクをスケジューリングし、スケジューリングされた前記タスクを前記プロセッサに分配するスケジューリング装置と、
前記スケジューリング装置に接続したアドバイス装置と、
を有し、
前記スケジューリング装置に前記タスクが到着したとき、前記スケジューリング装置は、通常のリアルタイム・スケジューリング・アルゴリズムにしたがって前記タスクのプライマリ・バージョンを割り当て、前記アドバイス装置に問い合わせを行い、
前記アドバイス装置が前記スケジューリング装置からの問い合わせを受け取ったとき、前記アドバイス装置は、前記タスクの前記プライマリ・バージョンの前記割り当ての妥当性を検査し、オーバーローディングによって前記タスクのバックアップ・バージョンを割り当て、前記タスクの前記バックアップ・バージョンの前記割り当ての妥当性を検査する、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプロセッサ・システムのためのプライマリ−バックアップ(primary-backup)に基づくファールト・トレラント（fault tolerant：耐故障性の）方法に関する。特に本発明は、既存のリアルタイム（実時間）・タスク・スケジューリング・アルゴリズムに基づいてフォールト・トレラント・タスク・スケジュールを生成する方法と、このようなフォールト・トレラント・方法を実行するマルチプロセッサ・システムと、に関する。
【背景技術】
【０００２】
リアルタイムアプリケーションでのタスクの重大な性質のために、システムにおいて認められたいかなるタスクも、故障が存在するときにおいてさえ、その実行を完遂することが非常に重要である。したがって、耐故障性(fault tolerance)は、リアルタイム・タスク・システムに対する重要な要件である。ハードウェアによるやり方、あるいはソフトウェアによるやり方によって、耐故障性を提供することができる（非特許文献１）。ハードウェアによるやり方は、しばしば、コスト及びエネルギーについての重い負担をシステム設計者に課す。したがって、フォールト・トレラントなシステム計画またはスケジューリングなどのソフトウェアによるやり方は、特に、ソフト・リアルタイム・タスク・システムなどの、信頼性が極めて重要であるわけではないいくつかの場合において好ましい。
【０００３】
異なるプロセッサ上にタスクの複数のバージョンをスケジューリングすることは、耐故障性を与えることを可能にする。例えば、非特許文献２において、プロセッサの障害は、有事用(contingency)あるいはバックアップのスケジュールを保持することによって、処理される。これらのスケジュールは、プロセッサの障害の事象において使用される。最適なスケジュールが存在し、かつ、その最適なスケジュールは、主に予備の（スタンバイの）タスクとして機能する「ゴースト(ghost)」タスクの付加によって強められることが、バックアップ・スケジュールを生成するために仮定される。すべてのスケジュールがそのような付加を許容するであろう、というわけではないから、この方式は、楽観的に過ぎるとみなされてきた。しかしながら、耐故障性が最適スケジュールの生成とは密接には結びついていないことは、すなわち、最適スケジュールが任意の可能なスケジューリング・アルゴリズムで生成されることは、なお意義深いことである。
【０００４】
ここ数十年間、リアルタイム・タスク・スケジューリングに対して使用されてきた重要なフォールト・トレラントのやり方の１つは、プライマリ−バックアップ・モデルである。このモデルでは、タスクの２つのバージョンが２つの異なるプロセッサ上にスケジューリングされる（非特許文献３−９）。バックアップ・バージョンは、プライマリ・バージョンが失敗したときのみ実行され、そうでなければ、プライマリ・バージョンが無事に完了したときに、スケジュールから割り当てを解除される。プライマリ−バックアップ方式に基づくスケジュールでは、バックアップ・バージョンは、時間及び空間リソースを巡って、プライマリ・バージョンと競合せざるを得ない。プライマリ−バックアップ方式とともに、オーバーローディング(overloading)技術の類もまた出現してきた。オーバーローディング技術では、フォールト・トレラント・スケジュールの中で、タスクは、他のタスクとともに同じタイムスロットを共有することが許される。
【０００５】
スケジュール可能性(schedulability)を向上するために、バックアップ−バックアップ（ＢＢ：backup-backup）オーバーローディングが使用される（非特許文献４−６）。バックアップ−バックアップ・オーバーローディングは、複数のプライマリのバックアップをプロセッサ上の同一か重なり合う時間インターバルにスケジューリングすることと定義される。しかしながら、オーバーロードされたバックアップは、より早く開始するようにスケジュールされることが可能なプライマリを排除する。非特許文献４には、タスクのプライマリを他のタスクのバックアップとともにプロセッサ上の同一か重なり合う時間インターバルにスケジュールするために、プライマリ−バックアップ（ＰＢ：primary-backup）オーバーローディングが提案されている。しかしながら、プライマリ−バックアップ・オーバーローディングの課題は、２つ目の障害発生までの時間（ＴＴＳＦ：the time to the second failure occuring）が、バックアップ−バックアップ・オーバーローディングのＴＴＳＦよりも長い、という点にある。ＴＴＳＦは、最初の障害が発生した後に２つ目の障害に耐える能力をシステムが取り戻すためにシステムが要する時間を示す、システムの回復力を示す測度である（非特許文献５）。ＴＴＳＦが小さいほど、システムはよりよい耐障害性をサポートする。バックアップ−バックアップ・オーバーローディングとプライマリ−バックアップ・オーバーローディングを折衷するために、ハイブリッド・オーバーローディングが、非特許文献８，９により導入されてきた。オーバーローディングの存在は、スケジューリングの柔軟さを大いに損ね、その一方で、オーバーローディングを介して関連するタスクの数を制限する。既存のオーバーローディングの技術は、少数のタスク（ＢＢオーバーローディングでは、少数のバックアップであり、ＰＢオーバーローディングでは、たった１個のプライマリと１個のバックアップである）のみがオーバーロードされることに制限する（非特許文献３−６）。第１に、オーバーロードされた多くのタスクを管理することが難しく、また第２に、多くのタスクをオーバーロードすることが信頼性に欠けるので、これらの制限が生じる。
【０００６】
この明細書の理解を容易にするために、以下にようにいくつかの例が示される。ｐｒiはタスクのプライマリ・バージョンを示し、ｂｋiはそのタスクのバックアップ・バージョンを示し、Ｐiはプロセッサを示すものとする。図１及び図２に３つのオーバーローディング方式が例示されている。図１の左半分は、３つのプロセッサＰ1〜Ｐ3が使用される場合に関するＢＢオーバーローディングでのタスク・スケジューリングの例を示し、一方、図１の右半分は、ＰＢオーバーローディングでのタスク・スケジューリングの例を示している。図２は、４つのプロセッサＰ1〜Ｐ4が使用される場合に関するハイブリッド・オーバーローディングの例を示している。タスクがオーバーローディングによって接続しているので、オーバーロードされたタスクを単純に“オーバーローディング・チェーン(overloading chain)”であると呼ぶことにする。図２には、２つのオーバーローディング・チェーン１２１，１２２がある。図２において、左側のチェーン１２１中のタスクｐｒ1が失敗するとすると、タスクｂｋ1，ｂｋ2，ｐｒ3は生き残るであろうし、また、ｐｒ1での故障に耐え、同時には１つのプロセッサ上で多くとも１つのタスクが実行されるであろうことを保障するために、タスクｐｒ2，ｂｋ3は削除されるであろう。チェーンの破壊の後、残っているタスクは新たな故障に耐えることができない。チェーンの最後のタスク、すなわちｂｋ2が非常に遅く終わるようにスケジュールされていると、システムは長い時間にわたって信頼できないであろう。これが、既存のオーバーローディング・チェーンが短いことの理由である。信頼性の問題を解決するもう１つの解決策は、全てのプロセッサのサブセット内にオーバーローディング・チェーンを限定することであり、それにより、サブセット内のプロセッサには新しい故障が発生しなければ、システム全体として新しい故障に耐えることが可能になる。この解決策は、非特許文献４，６において、“グルーピング技術(grouping technique)”と呼ばれ、静的グルーピング及び動的グルーピングに分類することができる。
【０００７】
この明細書すなわち本発明の文脈における故障は、ハートウェアまたはソフトウェアの問題のようななんらかの理由でプロセッサが失敗し、プロセッサが回復したか否かによらず失敗したプロセッサ内のタスクが失われることと定義される。このように、故障は、一時的なものであることも、あるいは永続的なものであることもできる。故障は、やがて、例えば故障検出器によって検出されるものとする。任意の時点において、たった１つの故障が発生するものとする。同時発生の複数の故障(concurrent faults)の場合には、グルーピング技術（非特許文献４，６）を使用して故障を取り扱うことができ、したがって、同時発生の複数の故障の場合をここでは考慮しない。
【０００８】
関連技術における、オーバーローディングを用いるプライマリ及びバックアップ方式に基づくフォールト・トレラント方法は、解決すべきいくつかの課題を有する。
【０００９】
第１の課題は、一緒にオーバーロードされることができる少数のタスクしか考えない、既存のオーバーローディング方法の悲観的な考え方からもたらされる。スーパーコンピュータ内の故障はしばしば発生するが、最初のコンピュータの誕生以来、単一のプロセッサあるいは単一のコンピュータの信頼性は大いに向上してきた。今日では、２０台、３０台あるいはそれ以上のプロセッサまたはコンピュータからなる組の中でのたった１つの故障を想定することは、不合理なことではない。なお、“１つの故障”は任意の時点における単一の故障を意味し、したがって、同時発生の複数の故障を意味しない。同時発生の複数の故障が起きた場合であっても、オーバーローディングによる利益と比べると、ソフト・リアルタイム・タスクに関しては損失はなお十分に乗り越えられるものである。リアルタイム・マルチプロセッサ・システムにおいて、時間は、タスクに対して制限され、タスクによって共有される、ある種のリソース（資源）である。複数のタスクは、時間リソースを巡って競合する。バックアップによって占められるタイムスロットは、耐障害性のための価格（コスト）となるので、特にプライマリ−バックアップ方式に基づくスケジューリングに関し、リソースの利用率を向上させることは本質的なことである。同一の３つのタスクｔ1，ｔ2，ｔ3があり、それらのプライマリｐｒ1，ｐｒ2，ｐｒ3及びバックアップｂｋ1，ｂｋ2，ｂｋ3がマルチプロセッサ・システム内でスケジューリングされるとする。オーバーローディングがないとすると、利用率は以下のようになるであろう。
【００１０】
【数１】
2013533524.tif 000003
【００１１】
もし、バックアップｂｋ1が他のバックアップｂｋ2上にオーバーロードされるとすると、利用率は以下のようになるであろう。
【００１２】
【数２】
2013533524.tif 000004
【００１３】
同様に、全てのバックアップｂｋ1，ｂｋ2，ｂｋ3が同じタイムスロットに配置されるとすると、利用率は以下になるであろう。
【００１４】
【数３】
2013533524.tif 000005
【００１５】
明らかに、オーバロードされたタスクが多いほど、利用率もより高くなる。
【００１６】
第２の課題は、より多くのタスクをオーバーロードしようとする試みから生じる。例えば、プライマリ−バックアップ・オーバーローディングでタスクを取り扱い、システムに新しいタスクを追加するとき、各オーバーロード・チェーン内の各タスクを検査して、その新しいタスクがプライマリ−バックアップ・オーバーローディングで追加されることを保証しなければならない。一緒にオーバーロードされている多数のタスクが存在すると、その検査の動作に多くの時間を要し、また、実装が込み入った複雑なものになる。しかも、必ずしも常に新しいタスクを追加することができるわけではない。例えば図１において、ＰＢオーバーローディングに新しいタスクｔ3を追加するとき、プライマリｐｒ3はバックアップｂｋ2上にオーバロードされなくてはならず、バックアップｂｋ3はプロセッサＰ2またはＰ3上に配置されなければならない。したがって、プロセッサＰ3において故障が発生し（ここでは、プロセッサＰ3の場合を考えている）、ｐｒ1とｂｋ3の両方が失われるのに十分なほど長くその故障が継続するとする。すると、最終的にプロセッサＰ1においてｂｋ2とｐｒ3との衝突が存在するので、他のタスクを削除することによっては故障に耐えることができないことが容易に分かる。
【００１７】
第３の課題は実装から生じる。プライマリ及びバックアップ方式に基づくフォールト・トレラント・タスク・スケジューリングのほとんど全ての既存のアルゴリズムは、タスク・オーバーローディングに適合するように、独立して設計されている。しかしながら、フォールト・トレラントではなく、また、プライマリ及びバックアップ方式を使用することによっては単純にはフォールト・トレラントにはすることができない、多数のリアルタイム・スケジューリング・アルゴリズムが多数存在する。既存のプライマリ及びバックアップに基づくスケジューリング・アルゴリズムを採用したとしても、多数のオーバーロードされたタスクの管理は複雑になる。プライマリｐｒ1〜ｐｒ7とそれらのバックアップｂｋ1〜ｂｋ7が８つのプロセッサＰ1〜Ｐ8上に分配されている、図３に示したオーバーロードされたタスクを考える。オーバーロードされたタスクを表示することも、これらのタスクを管理することも、故障に耐えることも、そして、オーバーロードされたタスクの関係を理解する必要があるコンピュータ・プログラム中でオーバーローディングの妥当性(validity)を保証することも、複雑である。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】I. Korean and C. M. Krishna, Fault-Tolerant Systems, Morgan Kaugmann, Elsevier, 2007.
【非特許文献２】C. M. Krishna and K. G. Shin, "On Scheduling Tasks With Quick Recovery From Failure," IEEE Trans. Computer, 35(5):448-455, 1986.
【非特許文献３】R. Al-Omari, A. K. Somani and G. Manimaran, "An adaptive scheme for fault-tolerant scheduling of soft real-time tasks in multiprocessor systems," J. Parallel and Distributed Computing, 65(5):595-608, 2005.
【非特許文献４】R. Al-Omari, A. K. Somani and G. Manimaran, "Efficient overloading techniques for primary-backup scheduling in real-time system," J. Parallel and Distributed Computing, 64(5):629-648, 2004.
【非特許文献５】S. Ghosh, R. Melhem and D. Mosse, "Fault-tolerance through scheduling of aperiodic tasks in hard real-time multiprocessor systems," IEEE Trans. Parallel Distributed Systems, 8(3):272-284, 1997.
【非特許文献６】G. Manimaran and C. Siva Ram Murthy, "A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis," IEEE Trans. Parallel Distributed Systems, 9(11):1137-1152, Nov. 1998.
【非特許文献７】K. Hashimoto, T. Tsuchiya, and T. Kikuno, "A New Fault-Tolerant Scheduling Technique for Real-Time Multiprocessor Systems," J. Systems and Software, 53(2), pp. 159.171, 2000.
【非特許文献８】W. Sun, Y. Zhang, X. Defago, et al., "Real-time Task Scheduling Using Extended Overloading Technique for Multiprocessor Systems," IEEE Int'l Symp. Distributed Simulation and Real Time Applications, pp. 95-102, 2007.
【非特許文献９】W. Sun, Y. Zhang, X. Defago, et al., "Hybrid Overloading and Stochastic Analysis for Redundant Scheduling in Real-time Multiprocessor Systems," IEEE Int'l Symp. Reliable Distributed Systems, pp. 265-274, 2007.
【非特許文献１０】J. W. S. Liu, W. K. Shih, K. J. Lin, R. Bettati and J. Y. Chung, "Imprecise Computations," Proc. IEEE, vol. 82, no. 1, pp. 83-94, Jan. 1994.
【非特許文献１１】B. Andersson, T. Abdelzaher, J. Jonsson, "Partitioned Aperiodic Scheduling on Multiprocessors," Proc. Int'l Parallel and Distributed Processing Symp., 2003.
【発明の概要】
【００１９】
上述したように、関連技術における、オーバーローディングを伴うプライマリ及びバックアップ方式に基づくフォールト・トレラント方法は、プロセッサの低い利用率、新しいタスクを付加することの困難さ、及び実装における複雑さ、という課題を有する。
【００２０】
本発明の例示的な目的は、上記の課題を解決できる、マルチプロセッサ・システムのための改良されたプライマリ−バックアップに基づくフォールト・トレラント方法を提供することにある。
【００２１】
本発明の別の例示的な目的は、上記の課題を解決できる改良されたプライマリ−バックアップに基づくフォールト・トレラント方法を実行するマルチプロセッサ・システムを提供することにある。
【００２２】
本発明の例示的な様相によれば、マルチプロセッサ・システムにおけるプライマリ−バックアップ方式に基づく耐故障性の方法は、マルチプロセッサ・システム内のプロセッサに割り当てられるべきタスクを受け取ることと、通常のリアルタイム・スケジューリング・アルゴリズムにしたがって、タスクのプライマリ・バージョンを割り当てることと、タスクのプライマリ・バージョンの割り当て（アロケーション：allocation）の妥当性を検査することと、オーバーローディングによってタスクのバックアップ・バージョンを割り当てることと、タスクのバックアップ・バージョンの割り当ての妥当性を検査することと、を有する。
【００２３】
本発明の別の例示的な様相によれば、プライマリ−バックアップに基づく、フォールト・トレラント・マルチプロセッサ・システムは、バスを介して相互に密結合した複数のプロセッサと、タスクをスケジューリングし、スケジューリングされたタスクをプロセッサに分配するスケジューリング装置と、スケジューリング装置に接続したアドバイス装置と、を有し、スケジューリング装置にタスクが到着したとき、スケジューリング装置は、通常のリアルタイム・スケジューリング・アルゴリズムにしたがってタスクのプライマリ・バージョンを割り当て、アドバイス装置に問い合わせを行い、アドバイス装置がスケジューリング装置からの問い合わせを受け取ったとき、アドバイス装置は、タスクのプライマリ・バージョンの割り当ての妥当性を検査し、オーバーローディングによってタスクのバックアップ・バージョンを割り当て、タスクのバックアップ・バージョンの割り当ての妥当性を検査する。
【００２４】
本発明の例示的な様相によれば、いくつかの単純なルールが満たされる限り任意に新しいタスクを追加する、新しいプライマリ−バックアップに基づくスケジューリング方法が提供され、任意の既存のスケジューリング・アルゴリズムをフォールト・トレラントにすることができる。既存のスケジューリング・アルゴリズムは、新しいタスク割り当てについての決定を下す前に、アドバイザ(adviser)（すなわちアドバイス装置(advising device)またはアドバイス・プロセス）に問い合わせを行う必要があるだけである。さらに、本発明の例示的な様相の方法に基づいてシステムがタスクのスケジューリングを行うとき、システムは、オーバーロードされたタスクの間の関係を理解したり覚えていたりする必要はない。したがって、リソース管理が単純化される。
【００２５】
本発明の上記の及び他の目的、特徴及び利点は、本発明の例示実施形態を示す添付の図面に基づく以下の記載から明らかになるであろう。
【図面の簡単な説明】
【００２６】
【図１】バックアップ−バックアップ（ＢＢ：backup-backup）オーバーローディング(overloading)とプライマリ−バックアップ（ＰＢ：primary-backup）オーバーローディングによるタスク・スケジューリングの例を示すタイミング図である。
【図２】ハイブリッド・オーバーローディングによるタスク・スケジューリングの例を示すタイミング図である。
【図３】例示的な、オーバーローディングの複雑な事例を示すタイミング図である。
【図４】本発明の一例示実施形態に基づくプライマリ−バックアップ・フォールト・トレラント方法が適用されるマルチプロセッサ・システムの一例を示すブロック図である。
【図５】通常のスケジューリング・アルゴリズムからその耐障害性バージョンへの移行を示す図である。
【図６】アドバイス装置（すなわちアドバイザ）の動作を示すフローチャートである。
【図７】関数ＣＰＶ（Checking Primary Validity：プライマリの妥当性を検査する）のアルゴリズムの一例を示す図である。
【図８】関数ＣＢＶ（Checking Backup Validity：バックアップの妥当性を検査する）のアルゴリズムの一例を示す図である。
【図９】手続きＦＴ（Tolerate a fault in a processor：プロセッサ内の故障に耐える）のアルゴリズムの一例を示す図である。
【図１０】手続きＲＴＨａｎｄｌｅｒ（Recursively Handle Task Sets：タスク・セットを再帰的に扱う）のアルゴリズムの一例を示す図である。
【発明を実施するための形態】
【００２７】
次に、本発明に基づく例示実施形態を説明する。
【００２８】
例示実施形態の各々は、例えば、全てのプロセッサが同一であって専用のものであるマルチプロセッサ・システムに対して適用可能である。本発明が適用されることができるマルチプロセッサ・システムは、古典的なリアルタイム・システムに限られない。分散マルチプロセッサ・システムまたは疎結合専用計算プラットホームも否定されない。しかしながら、ここでは、リソース共有がタイミング制約条件をとても難しくする典型的なＰ２Ｐ（ピア・ツー・ピア：peer-to-peer）あるいはグリッド・コンピューティング環境を考えないこととする。共有メモリあるいは密結合マルチプロセッサ・システムに対しては、通信遅延が小さいので、ここでは、タスクはプリエンティブル（preemptible：横取り可能）かつマイグレータブル（migratable：移行可能）であると仮定してもよい。各プロセッサは、ワーク−コンサービング(work-conserving)である。すなわち、いずれかのタスクが割り当てられていれば、アイドルなプロセッサが存在しない。タスクが到着しスケジューリングされる中央スケジューラーを仮定する。
【００２９】
図４は、本例示実施形態に基づくプライマリ−バックアップ・フォールト・トレラント方法が適用されるマルチプロセッサ・システムの一例を示している。図示されたマルチプロセッサ・システム１００は、ｍ個のプロセッサＰ1〜Ｐmと、プロセッサＰ1〜Ｐmを相互に密結合するバス１０１と、バス１０１に接続されて全てのプロセッサＰ1〜Ｐmに共通に設けられている共有メモリ１０２と、プロセッサＰ1〜Ｐmに対するタスク・スケジュールを生成しそれぞれのプロセッサにタスクを分配する中央スケジューラーとして機能するスケジューリング装置１０３と、スケジューリング装置１０３に接続されたアドバイス装置（すなわちアドバイザ）１０４と、を含んでいる。分散形態でプロセッサ上で実行されるべきタスクは、まず、スケジューリング装置１０３に到着し、それから、プロセッサに分配される。
【００３０】
一例において、スケジューリング装置１０３がタスクを受け取ったとき、スケジューリング装置１０３は、既存の通常のスケジューリング・アルゴリズムに基づいて、タスクのプライマリ・バージョンに対するタスク・スケジュールを生成し、タスクのバックアップ・バージョンを割り当てるようにアドバイス装置１０４に問い合わせる。あるいは、スケジューリング装置１０３は、タスクのプライマリ・バージョンとバックアップ・バージョンとをプロセッサに分配し、新しいタスクの到着に際し、その新しいタスクの割り当て（アロケーション(allocation)）に関してアドバイス装置１０４に問い合わせる。いくつかソフトウェア実装では、スケジューリング装置１０３とアドバイス装置１０４の機能は、アドバイザ・ルーチンを既存の通常のスケジューリング・アルゴリズムに単純に付加することによって実現される。
【００３１】
プライマリ−バックアップに基づくフォールト・トレラント方式の目的のために、タスクは、以下の特徴（ｉ）〜（ｖ）を有する。
【００３２】
（ｉ）  タスクは非周期的である。すなわち、タスクの到着は事前には（アプリオリには）分からない。あらゆるタスクｔiは、属性として、到着時刻（ａi）、レディ・タイム(ready time)（ｒi）、最悪ケース計算時間（ｃi）、実際の計算時間（ａｃi）及びデッドライン（ｄi）を有する。タスクの最悪ケース計算時間は、静的コード解析、または、起こり得る最悪ケースの下での実行時間の平均に基づいて、求められる。簡単のため、実際の計算時間ａｃiは、常に、最悪ケース計算時間ｃiより小さいかこれに等しいものとする。
【００３３】
（ｉｉ）  各タスクｔiは２つのバージョン、すなわちプライマリ（ｐｒi）とバックアップ（ｂｋi）を有する。２つのバージョンのすべての属性は等しいものとする。
【００３４】
（ｉｉｉ）  タスクは並列処理可能(parallelizable)ではない。これは、タスクが１つのプロセッサ上のみで実行可能であることを意味する。このことは、タスクのプライマリとバックアップの両方のコピーが、時間間隔（ｄi−ｒi）内でスケジューリング可能であるように、タスクのプライマリとバックアップの最悪ケース計算時間の和がこの時間間隔（ｄi−ｒi）より小さいかこれに等しくあるべきことを必要とする。
【００３５】
（ｉｖ）  タスクは独立である。先行する制約条件を有するタスクに対し、タスクのレディ・タイムとデッドラインとは、それらがタスク間での先行する制約条件に適合するように、修正されることができる。先行する制約条件を扱うことは、修正されたレディ・タイムとデッドラインとによって処理を進めることと等価である（非特許文献１０）。
【００３６】
（ｖ）  タスクの割り当てが決定された後に、このタスクの開始時刻と終了時刻が分かる。Ｓｔ（ｔi）が開始時刻を示し、Ｆｔ（ｔi）がタスクｔiの終了時刻を示すものとする。Ｐｒｏｃ（ｔi）が、タスクｔiがスケジューリングされているプロセッサを示すものとする。タスクの２つのコピーすなわちプライマリとバックアップとが、空間及び時間排他でスケジューリングされなければならないので、関連する文献において、以下のルールが存在する。
【００３７】
【数４】
2013533524.tif 000006
【００３８】
上記で紹介したシステム・モデルと調和する多くの実用的なシステムが存在する。説明の便宜上、ｈｔｔｐ（ハイパーテキスト・トランスファー・プロトコル(hypertext transfer protocol)）によって送られてきたクライアントのリクエストを処理し、しばしば過負荷に悩まされるマルチプロセッサ・ウェブ・サーバという１つの例をのみを紹介する。もちろん、本発明は、マルチプロセッサ・ウェブ・サーバ以外のマルチプロセッサ・システムに対しても適用することができる。ウェブ・サーバにおいて、サーバに新しいリクエストが到着したときに新しいタスクが生成される。新しいタスクは所定の時間範囲内で処理されるべきである。新しいリクエストの到着頻度が過度に増加すると、サーバは過負荷状態になるであろう。
【００３９】
リクエスト（パケット）のデッドラインを保証しようと試みるウェブ・サーバにおいて過負荷が発生したとき、サーバは、自ら認めた全てのリクエストを保証すべきであり、同時にシステム容量を完全に使用すべきである。リクエストを保証することができなければ、そのリクエストは拒絶されるべきであって、そのリクエストは他のサーバに移動する。
【００４０】
一例示実施形態に基づく、オーバーローディングを伴うプライマリ−バックアップに基づくフォールト・トレラント方式は、以下の動作及び条件（１）〜（２０）を含む。
【００４１】
（１）  タスクは、タスク・セットを介して管理される。タスク・セットの１つは、一緒にオーバーロードされるタスクの集合であると定義される。例えば図３において、１つのタスク・セットはｐｒ4，ｐｒ5，ｐｒ6を含み、もう１つのタスク・セットは、ｐｒ7，ｂｋ4，ｂｋ5，ｂｋ6を含む。タスク・セットはτで示される。
【００４２】
【数５】
2013533524.tif 000007
【００４３】
【数６】
2013533524.tif 000008
【００４４】
（４）  タスクｔiがそのプライマリ・バージョンｐｒiまたはそのバックアップ・バージョンｂｋiであろうことができるのと同様に、タスク・セットは、以下の３つの種類、すなわち、π，β，ηのいずれか１つであろうことができる。π型のタスク・セットは、タスクのプライマリ・バージョンのみを含み、β型のタスク・セットはバックアップのみを含み、η型のタスク・セットはプライマリとバックアップとを含んでいる。
【００４５】
（５）  単一のタスクもタスク・セットであり、このタスクはπ型のタスク・セットでなくてはならない。
【００４６】
（６）  図１、図２及び図３に示されるように、オーバーロードされたタスクの関係は、ちょうど、タスク・セットの関係である。関連するタスクは、タスク・セットの族(family)であるように組織化される。族はＳであると定義される。
【００４７】
（７）  族Ｓも以下の種類、すなわち、Π，Ｂ，Ｆのいずれか１つであろうことができる。Π型の族は、図１におけるような純粋なプライマリ−バックアップ（ＰＢ）オーバーローディングを示し、一方、Ｂ型の族は、図１におけるような、純粋なバックアップ−バックアップ（ＢＢ）オーバーローディングを示している。Ｆ型の族は、図３におけるような自由(free)オーバーローディングを示している。なお、“自由オーバーローディング”と“ハイブリッド・オーバーローディング”との違いは、スケジューリング及び管理においてハイブリッド・オーバーローディングがタスクの特定の関係を決定し理解する必要があることである。
【００４８】
（８）  オーバーローディングが妥当(valid)であることを保証するために、以下のように新しいルールが追加される。
【００４９】
【数７】
2013533524.tif 000009
【００５０】
（９）  この例示実施形態は、特定のタスク・スケジューリング・アルゴリズムを含んでいないが、例えば図５に示される手順のように１つのタスクから別のタスクへとタスクごとにそのスケジューリングを行うであろう既存のスケジューリング・アルゴリズムをサポートする。図５は、通常のスケジューリング・アルゴリズムの、そのフォールト・トレラント・バージョンへの移行の例を示している。図５は、通常のスケジューリング・アルゴリズムを示すフローチャート２００Ａと、この通常のスケジューリング・アルゴリズムから導出されたフォールト・トレラント・バージョンを示すフローチャート２００Ｂと、を含んでいる。
【００５１】
フローチャート２００Ａに示される通常のスケジューリング・アルゴリズムでは、まずステップ２０１において、全てのタスクが処理されたかどうかがチェックされる。処理されていれば、アルゴリズムのプロセスは終了し、そうでなければ、次に処理されるべきタスクとして、ステップ２０２において、タスクｔiが取り上げられ、プロセスはステップ２０３に進む。ステップ２０３において、タスクｔiに対する割り当て（アロケーション）が探索される。もしタスクｔiに対する割り当てが見つかれば、次にタスクｔiは、ステップ２０４において、空間的及び時間的にその割り当てにスケジューリングされ、プロセスはステップ２０１に戻る。ステップ２０３において割り当てが見つからなければ、プロセスはステップ２０１に直接戻る。
【００５２】
フローチャート２００Ｂに示されるフォールト・トレラント・バージョンのアルゴリズムでは、まずステップ２１１において、全てのタスクが処理されたかどうかがチェックされる。処理されていれば、アルゴリズムのプロセスは終了し、そうでなければ、次に処理されるべきタスクとして、ステップ２１２において、プライマリ・タスクｐｒiが取り上げられ、プロセスはステップ２１３に進む。ステップ２１３において、プライマリ・タスクｐｒiに対する割り当てが探索される。もし、プライマリ・タスクｐｒiに対する割り当てが見つかれば、次に、ステップ２１４において、アドバイザは、バックアップ・タスクｂｋiの割り当てを依頼される。もし、バックアップ・タスクｂｋiの割り当てが成功であったら、次に、ステップ２１５において、タスクｐｒiは、空間的及び時間的にその割り当てにスケジューリングされ、プロセスはステップ２１１に戻る。ステップ２１３においてプライマリ・タスクｐｒiに対する割り当てが見つからなければ、プロセスはステップ２１１に直接戻る。ステップ２１４においてバックアップ・タスクｂｋiに対する割り当てが成功でなかったら、プロセスはステップ２１３に戻る。
【００５３】
タスクがスケジューリングされているとき、フローチャート２００Ａに示されるスケジューリング・アルゴリズムは、わずかに改変されて、アドバイザに対し、スケジューリング・アルゴリズムで見つかったタスク割り当てが正しくかつフォールト・トレラントであるかを確認するように問い合わせる。図５は、アドバイザを用いることの基本的なアイデアを示している。明らかに、通常のスケジューリング・アルゴリズムにおいて大きな演算を行う必要はない。
【００５４】
（１０）  アドバイザは、プライマリの割り当てを検査し、次に、そのバックアップに対する適切な割り当てを選択する。プライマリまたはバックアップのいずれか１つがアドバイザによって受け入れられることができないとすると、そのタスクは拒絶されるべきであり、それのち、次のタスクが考慮されるであろう。割り当てのスケジューリングや探索の核心部分にはアドバイザが干渉しないので、図５のフローチャート２００Ａによってモデル化される任意のスケジューリング・アルゴリズムをフローチャート２００Ｂに示されるそのフォールト・トレラント・バージョンに移行することができる。
【００５５】
アドバイザの動作が図６に示されている。図６に示されるフローチャートにしたがって、アドバイザはまず、ステップ２２１において、タスクｐｒiの妥当性(validity)を検査する。もし割り当てが妥当でなければ、プロセスは、ステップ２２３に移行し、“いいえ(no)”を返して終了する。タスクｐｒiに対する割り当てが妥当であれば、アドバイザは、ステップ２２２において、バックアップｂｋiに関して、もう１つの別の可能な割り当てを探索する。もし割り当てが見つからなければ、プロセスは、ステップ２２３に移行し、“いいえ(no)”を返して終了する。ステップ２２２において別の割り当てが存在すれば、次に、アドバイザは、ステップ２２４において、タスクｂｋiの割り当ての妥当性を検査する。妥当でなければ、プロセスはステップ２２２に戻る。ステップ２２４において妥当であれば、アドバイザは、ステップ２２５において、空間的及び時間的にタスクｂｋiをその割り当てにスケジューリングし、プロセスは、ステップ２２６に移行し、“はい(yes)”を返して終了する。
【００５６】
（１１）  本例示実施形態においてプライマリまたはバックアップの割り当ての妥当性を検査することは、既存の技術に比べてとても簡素である。これは、上記の４つのルール、すなわち、ルール１、ルール２、ルール３及びルール４が満足されることができるか否かのみを検査することによって妥当性を保証するだけで十分であるからである。これに対し、既存の技術は、オーバーロードされたタスクの関係を理解する必要がある。妥当性を検査することの擬似コードが図７及び図８に示されている。図７は、プライマリの割り当ての妥当性の検査に用いられる関数ＣＰＶ（）を示し、一方、図８は、バックアップの割り当ての妥当性の検査に用いられる関数ＣＢＶ（）を示している。
【００５７】
（１２）  ルール４は以下の技法によって試験することができる。マルチプロセッサ・システムはｍ個のプロセッサを有すると仮定し、族Ｓが訪問したプロセッサを示すために、ｍビットの２進数ｋを族Ｓのために用いる。２進数値ｋの最上位ビット（ＭＳＢ：most significant bit）が１番目のプロセッサＰ1に対応し、引き続くプロセッサの訪問状態は２進数値での引き続くビットにおいて示されるものとする。したがって、最下位ビット（ＬＳＢ：least significant bit）は、ｍ番目のプロセッサＰmに対応する。例えば、族Ｓに含まれるタスク・セットがプロセッサＰ2，Ｐ3，Ｐ5，Ｐ6を訪問したとし、かつ、システムには８個のプロセッサＰ1〜Ｐ8があるときには、ｋ＝０１１０１１００となる。新しいタスク・セットがプロセッサＰ1に対して受け入られると、ｋ＝１１１０１１００となる。ルール４の検査のために、０１１０１１００∧１０００００００＝０か否かを検証するだけで十分である。ｋを更新するために、ｋ＝０１１０１１００∨１０００００００の演算を実行するだけで十分である。この例では、ルール４の検証は、論理“ＡＮＤ”（論理積）演算に基づいており、更新は、論理“ＯＲ”（論理和）演算に基づいている。ｋの検証と更新の演算は、簡単のために、図では省略されており、ルール４を満たすこと、とだけ言っておく。新しいタスクを加えることは、２つの分離した族Ｓ1，Ｓ2を接続するかも知れない。上記で説明した方法は、族Ｓ1と族Ｓ2とが接続できるかどうかを検査することにも好適である。
【００５８】
（１３）  アドバイザは、プライマリにとって最もふさわしい割り当てを決めるべきである。アドバイザは、バックアップをスケジューリングすることからのプライマリに対する干渉を減少させるように試みる。プライマリに対して選択されたタイムスロットがＣＰＶ（）を合格した場合に限り、そのプライマリはそのタイムスロットに割り当てられるであろう。スケジューリング・アルゴリズムがプライマリのための割り当てを探索するとき、π型のセットとη型のセットのみが考慮され、β型のセットはプライマリに関して無視される。
【００５９】
（１４）  バックアップをスケジューリングすることは、バックアップが実際には“ゴースト”であって他のものの上にオーバーロードされることができるので、プライマリをスケジューリングすることからは異なっている。もしバックアップがプライマリのスケジューリングに干渉しないであろうとすると、耐故障性はコスト不要のものであるであろう。したがって、バックアップに起因する干渉は、最小のものとなるように制御されるべきである。バックアップ・タスクｂｋiは、基本的には、［Ｆｔ（ｐｒi），ｄi］の範囲内で割り当てられるべきである。したがって、Ｐj，Ｐj≠Ｐｒｏｃ（ｐｒi）において、各タイムスロットが［Ｆｔ（ｐｒi），ｄi］であると考える必要がある（なお、この条件の下で、このバックアップの割り当ては、妥当でないかもしれず、妥当性はＣＢＶ（）によって検査される）。
【００６０】
（１５）  タスク・セットの時間長λは、
【００６１】
【数８】
2013533524.tif 000010
【００６２】
であると定義される。時間長限界Λはユーザ・パラメータである。両方の妥当性検査関数ＣＰＶ（）及びＣＢＶ（）において、時間長がチェックされるあろう。もし時間長λが時間長限界Λを超えるならば、タスクは妥当性検査を合格することができない。簡単のため、時間長をチェックすることは、関連する図面からは省略されている。
【００６３】
（１６）  アドバイザは、バックアップにとって最もふさわしい割り当てをも決めるべきである。一例示実施形態において、バックアップに対してポリシーが与えられてもよい。バックアップは、できるだけ遅い空きタイムスロットを取るように試みられるか、あるいは、バックアップは、既存のタスク・セットに割り当てられるように試みられる。もし、ＣＢＶ（）を合格した２以上のタスク・セット｛τ1，τ2，τ3…｝が存在するときは、δ(ｂｋk，τ)＝ｍａｘ｛δ(ｂｋk，τi)｜∀τi｝であれば、タスクｂｋkに対してタスク・セットτが選択される。どこにバックアップを割り当てるかを決定するためにユーザ・パラメータが使用される。
【００６４】
（１７）  ユーザ・パラメータである、詰まり具合(tightness)の重みωが導入されてもよい。タスクｂｋkがオーバーロードされることができるタスク・セットが存在しないときは、確実にδ(ｂｋk，τ)＝０であって、できるだけ遅い空きタイムスロットにバックアップはスケジューリングされる。もしδ(ｂｋk，τ)≠０ならば、次に、δ(ｂｋk，τ)がωよりも大きいかどうかがチェックされる。δ(ｂｋk，τ)＞ωならば、バックアップはタスク・セットτにオーバーロードされる。δ(ｂｋk，τ)≦ωかつ空きタイムスロットがないときも、バックアップはタスク・セットτにオーバーロードされる。δ(ｂｋk，τ)≦ωかつ空きタイムスロットがあるときは、バックアップは、その空きタイムスロットにスケジューリングされる。
【００６５】
（１８）  βのダイナミクスも導入されてもよい。タスクがタスク・セットにオーバーロードされようとするとき、オーバーローディングができるだけぎっしりと詰まったものであって、少なくとも詰まり具合の重みがω以上であることを期待する。したがって、プライマリまたはバックアップであるタスクｔkが、βであるタスク・セットにオーバーロードされようとするとき、δ(ｔk，β)を増加させるようにβは前進させられるだろう。βのこのダイナミクスはアドバイザ内に埋め込まれていてもよく、図には明示的には示されていない。
【００６６】
（１９）  故障が発生したとき、失敗したタスク・セットは、再帰アルゴリズムによって取り扱われて、故障に耐える。タスクが上記の項目（１）〜（１７）に関して完全にスケジューリングされていれば、各族Ｓは、根付き有向木である。根はβ型のタスク・セットである。全ての葉はπ型のタスク・セットである。内部頂点が存在すれば、全ての内部頂点はη型のタスク・セットである。
【００６７】
（１）〜（１８）における全ての条件及び動作は、数学的に正しいものであることが証明されている。
【００６８】
（２０）  族Ｓが崩壊するとき、タスク・セットがタスクに直接分解することはないだろう。その代わり、族Ｓは、まず、いくつかの独立した族Ｓに分解されるように試みられる。新しいＳが再組織化できない場合にのみ、タスク・セットは分離したタスクに分解させられるであろう。
【００６９】
（２１）  プライマリまたはバックアップをそのバックアップまたはプライマリにそれぞれ転換する操作である手続きｒｅｖｓ（）を導入することができる。バックアップに対する新しい割り当てを見つけることは、プロセッサを探索して、空であるかタスク・セットによって占められている割り当てを探し出すことである。なお、ＣＢＶ（）は、新しい割り当てに関して呼び出される。ＣＢＶ（）は、上記項目（１２）におけるものと同様に、２つの分離した族Ｓが接続できるかどうかをチェックしなければならない。
【００７０】
次に、上記の例示実施形態に基づくフォールト・トレラント方法によって与えられる貢献について説明する。
【００７１】
第１に、スケジュールでのタスクの関係に関する知識なしで、いくつかの単純な条件の下のみで形式張らずにタスクをオーバーロードするために、新しいオーバーローディング技術が提案される。このやり方で、プライマリ−バックアップ方式と形式張らないオーバーローディングとが、プライマリのスケジューリングから分離され、その結果、アドバイザを使用することによって、種々のリアルタイム・スケジューリング・アルゴリズムを簡単にフォールト・トレラントにすることができる。アドバイザは、タスクの割り当てがフォールト・トレラントであるかどうかの情報を伴ってタスク・スケジューラに応答することができ、その一方で、対応するバックアップを正しくスケジューリングすることができる。
【００７２】
第２に、タスク、プライマリ及びバックアップの管理が形式化され、形式張らないオーバーローディングを注意深く調べることを介して、タスク・オーバーローディングと故障に耐えることとを管理するために、一連のアルゴリズムが発展させられている。その一方で、アルゴリズムは、オーバーローディングを分解し組み直すことによって、故障に耐えたのちのオーバーローディングを修復するように、設計される。
【００７３】
上記に開示される例示実施形態の全体または部分は、以下の変形例を含むことができるが、これらに限定されるものではない。
【００７４】
変形例１：
プライマリ−バックアップに基づいてマルチプロセッサ・システムにおいて耐故障性をサポートする方法が提供される。この方法は、いくつかのキーとなるサブ方法を含み、サブ方法は、通常のリアルタイム・スケジューリング・アルゴリズムをそのフォールト・トレラント・バージョンに移行する方法と、タスク割り当てとオーバーローディングに関して通常のアルゴリズムに応えるアドバイザと、障害に耐える方法と、を含む。
【００７５】
変形例２：
変形例１に記載された、通常のリアルタイム・スケジューリング・アルゴリズムをそのフォールト・トレラント・バージョンに移行する方法が提供される。この方法は、元のアルゴリズムを変更せず、変形例１において知られているように、アドバイザまたはアドバイザ・アルゴリズムを元のスケジューリング・アルゴリズムに追加するだけである。図５のフローチャート２００Ａに示されるような形態で表現されることができる全ての通常のリアルタイム・スケジューリング・アルゴリズムは、この方法によって、フォールト・トレラント・バージョンに移行されることができる。この方法は、タスクをタスク・セットとして管理することと、タスク・セットを根付き有向木として管理することと、通常のスケジューリング・アルゴリズムを過度に妨げないようにアドバイザを用いることと、の特徴を含む。
【００７６】
変形例３：
変形例２でのタスクを管理する方法は、各タスクがタスク・セットとして管理されるように変更される。タスク・セットは、多数のタスクを含むことができる。タスク・セット内のタスクの種類に応じて、タスク・セットは異なる種類に分類されることができる。タスク・セットはまた、タスク・セットの族として知られる、異なる集合として管理される。新しいタスクを追加することは、族を拡張することと等しい。故障に耐えることは、族を分解することと等しい。タスク・セットの族は、タスク・セットの複数の分離した族に分解することができ、タスク・セットの異なる族は、タスク・セットの単一の族に結合されることができる。
【００７７】
変形例４：
タスク・セットの族は、変形例２で説明したものと同様の構造を有するフォールト・トレラント木として管理される。フォールト・トレラント木は、根付き有向木である。根、内部頂点及び葉は、タスク・セットの異なる種類である。
【００７８】
変形例５：
変形例１，２のいずれか１つに記載されたアドバイザは、オーバーローディングの妥当性の検査に関し、元の通常のアルゴリズムからの問い合わせに答え、その一方でバックアップのスケジューリングを行う。アドバイザは、単純にいくつかのルールによってオーバーローディングの妥当性を決定する処理と、バックアップをスケジューリングする処理と、を実行する。
【００７９】
変形例６：
変形例５でのオーバーローディングの妥当性を決定する方法は、図７に示されるアルゴリズムＣＰＶ（）と図８に示されるアルゴリズムＣＢＶ（）を含む。これらのアルゴリズムは、全てのルールが満たされることができるか否かを検証する、特にルール４の検証を行う、重要なステップを有する。もし、いずれかのルールを満たすことができなければ、対応するタスクは拒絶されるべきである。
【００８０】
変形例７：
変形例６でのルール４の検証は、２進数であってプロセッサの数と等しい長さを有するキーにプロセッサを符号化することを含む。ルール４を検証することは、２つの２進数に対して“ＡＮＤ（論理積）”演算を実行することである。もし、“ＡＮＤ”演算の結果が“０”であればルール４は満足され、そうでなければ満たされていない。もし、タスク・セットの族にタスク・セットが加えられるならば、２つの２進数上で実行される“ＯＲ（論理和）”演算によって、キーは更新される。タスク・セットの２つの分離した族を接続することは、この技術にも基づいている。
【００８１】
変形例８：
バックアップは、（ｉ）詰まり具合の重みに関する異なる条件に応じて、バックアップをできるだけ遅くにスケジューリングするか、あるいは、以前のタスク・セットに対してできるだけぎっしりと詰めてバックアップをオーバーローディングするか、を決定することと、（ｉｉ）変形例１に基づいてバックアップを動かすことにより、詰まり具合を最大化することと、を含む方法にしたがって、スケジューリングされる。この方法は、バックアップをできるだけ遅くにスケジューリングするか、または、できるだけ詰めてバックアップをオーバーロードするかを決定を行う。この方法は、さらに、（ｉｉｉ）ユーザによって定義された時間長限界未満となるように、いずれのタスク・セットについてもその時間長を制御することを含んでいる。
【００８２】
変形例９：
変形例１に基づく故障に耐える方法は、タスクをタスク・セットとして管理することと、各プロセッサに関して故障に耐えることと、再帰的にタスク・セットを取り扱うことと、オーバーローディングを組み直すことと、を含む。故障に耐えるアルゴリズムの一例が、手続きＦＴ（）の擬似コードを示す図９に示されている。図９に示されるアルゴリズムは、１つのプロセッサにおける故障を仮定し、ＲＴＨａｎｄｌｅｒ（再帰的にタスク・セットを取り扱うためのアルゴリズム）に対する呼び出しを含む全ての分岐条件とステップとを含んでいる。ＲＴＨａｎｄｌｅｒの擬似コードは、全ての分岐条件とステップとを含む図１０に示されている。アルゴリズムには、故障が起きたときに、タスク・セットの集合を分離した複数の集合に組み直すことを試みる方法が埋め込まれている。
【００８３】
したがって、上記の説明は、本発明の原理を図解するだけのものであると考えるべきである。さらに、数々の変更と改良とが容易に当業者の心に浮かぶであろうから、ここで示され説明された通りの構成及び動作に本発明を限定することは好ましくない。したがって、本発明の範囲内に含まれるすべての適切な変更及び等価物が用いられるであろう。
【図１】
2013533524.tif 000011
【図２】
2013533524.tif 000012
【図３】
2013533524.tif 000013
【図４】
2013533524.tif 000014
【図５】
2013533524.tif 000015
【図６】
2013533524.tif 000016
【図７】
2013533524.tif 000017
【図８】
2013533524.tif 000018
【図９】
2013533524.tif 000019
【図１０】
2013533524.tif 000020
【国際調査報告】
2013533524.tif 000021
2013533524.tif 000022