"マルチプロセッサシステムにおけるプライマリ-バックアップ方式に基づく耐故障性の方法は、マルチプロセッサシステム内のプロセッサに割り当てられるべきタスクを受け取ることと、通常のリアルタイムスケジューリングアルゴリズムにしたがって、前記タスクのプライマリバージョンを割り当てることと、前記タスクの前記プライマリバージョンの前記割り当ての妥当性を検査することと、オーバーローディングによって前記タスクのバックアップバージョンを割り当てることと、前記タスクの前記バックアップバージョンの前記割り当ての妥当性を検査することと、を有する。前記プライマリバージョン及び前記バックアップバージョンの両方の前記割り当ての妥当性を検査することと前記バックアップバージョンの割り当てを行うこととは、アドバイザがスケジューラによって問い合わされたときに、前記アドバイザ内で実行され、前記アドバイザは前記スケジューラからは分離して設けられており、前記スケジューラは前記タスクの前記プライマリバージョンを割り当てる、請求項1に記載の方法。前記プライマリバージョンに対応するプロセッサ内で障害が発生したときに、前記バックアップバージョンを用いて前記障害に耐えることをさらに有する、請求項1または2に記載の方法。前記プライマリバージョンの前記割り当ての前記妥当性と前記バックアップバージョンの前記割り当ての前記妥当性との少なくとも1つが否定されたときに、対応するタスクが拒絶される、請求項1乃至3のいずれか1項に記載の方法。前記タスクは少なくとも1つのタスクセットとして管理され、各タスクセットは、一緒にオーバーロードされるタスクの集合であり、前記タスクセットは、根付き有向木として取り扱われ、前記アドバイザは、前記タスクセットを用いて、前記通常のスケジューリングアルゴリズムを過度に妨げないように前記バックアップバージョンを割り当てる、請求項2に記載の方法。前記タスクは少なくとも1つのタスクセットとして管理され、各タスクセットは、一緒にオーバーロードされるタスクの集合であり、前記バックアップバージョンをそこにオーバーロードすることが可能なタスクセットが存在し、かつ、所定の条件を満たすならば、前記アドバイザは、できるだけ既存のタスクセットを詰めるよう前記既存のタスクセットに前記バックアップバージョンがオーバーロードされるように前記バックアップバージョンをスケジューリングし、そうでなければ、前記アドバイザは、できるだけ遅い空きタイムスロットに前記バックアップバージョンをスケジューリングする、請求項2に記載の方法。前記アドバイザは、ユーザによって定義された時間長限界未満となるように、どのタスクセットについてもその時間長を制御する、請求項6に記載の方法。前記タスクセットは少なくとも1つの族として管理され、各族は、タスクセットの集合であり、族を分解することによって障害に耐える、請求項5に記載の方法。前記タスクは少なくとも1つのタスクセットとして管理され、各タスクセットは、一緒にオーバーロードされるタスクの集合であり、前記耐えることは、前記タスクセットを再帰的に扱うことと、前記オーバーローディングを組み直すことと、を含む、請求項3に記載の方法。プライマリ-バックアップに基づく、フォールトトレラントマルチプロセッサシステムであって、バスを介して相互に密結合した複数のプロセッサと、タスクをスケジューリングし、スケジューリングされた前記タスクを前記プロセッサに分配するスケジューリング装置と、前記スケジューリング装置に接続したアドバイス装置と、を有し、前記スケジューリング装置に前記タスクが到着したとき、前記スケジューリング装置は、通常のリアルタイムスケジューリングアルゴリズムにしたがって前記タスクのプライマリバージョンを割り当て、前記アドバイス装置に問い合わせを行い、前記アドバイス装置が前記スケジューリング装置からの問い合わせを受け取ったとき、前記アドバイス装置は、前記タスクの前記プライマリバージョンの前記割り当ての妥当性を検査し、オーバーローディングによって前記タスクのバックアップバージョンを割り当て、前記タスクの前記バックアップバージョンの前記割り当ての妥当性を検査する、システム。次に、本発明に基づく例示実施形態を説明する。例示実施形態の各々は、例えば、全てのプロセッサが同一であって専用のものであるマルチプロセッサシステムに対して適用可能である。本発明が適用されることができるマルチプロセッサシステムは、古典的なリアルタイムシステムに限られない。分散マルチプロセッサシステムまたは疎結合専用計算プラットホームも否定されない。しかしながら、ここでは、リソース共有がタイミング制約条件をとても難しくする典型的なP2Pピアツーピア:peertopeerあるいはグリッドコンピューティング環境を考えないこととする。共有メモリあるいは密結合マルチプロセッサシステムに対しては、通信遅延が小さいので、ここでは、タスクはプリエンティブルpreemptible:横取り可能かつマイグレータブルmigratable:移行可能であると仮定してもよい。各プロセッサは、ワーク-コンサービングである。すなわち、いずれかのタスクが割り当てられていれば、アイドルなプロセッサが存在しない。タスクが到着しスケジューリングされる中央スケジューラーを仮定する。図4は、本例示実施形態に基づくプライマリ-バックアップフォールトトレラント方法が適用されるマルチプロセッサシステムの一例を示している。図示されたマルチプロセッサシステム100は、m個のプロセッサP1~Pmと、プロセッサP1~Pmを相互に密結合するバス101と、バス101に接続されて全てのプロセッサP1~Pmに共通に設けられている共有メモリ102と、プロセッサP1~Pmに対するタスクスケジュールを生成しそれぞれのプロセッサにタスクを分配する中央スケジューラーとして機能するスケジューリング装置103と、スケジューリング装置103に接続されたアドバイス装置すなわちアドバイザ104と、を含んでいる。分散形態でプロセッサ上で実行されるべきタスクは、まず、スケジューリング装置103に到着し、それから、プロセッサに分配される。一例において、スケジューリング装置103がタスクを受け取ったとき、スケジューリング装置103は、既存の通常のスケジューリングアルゴリズムに基づいて、タスクのプライマリバージョンに対するタスクスケジュールを生成し、タスクのバックアップバージョンを割り当てるようにアドバイス装置104に問い合わせる。あるいは、スケジューリング装置103は、タスクのプライマリバージョンとバックアップバージョンとをプロセッサに分配し、新しいタスクの到着に際し、その新しいタスクの割り当てアロケーションに関してアドバイス装置104に問い合わせる。いくつかソフトウェア実装では、スケジューリング装置103とアドバイス装置104の機能は、アドバイザルーチンを既存の通常のスケジューリングアルゴリズムに単純に付加することによって実現される。プライマリ-バックアップに基づくフォールトトレラント方式の目的のために、タスクは、以下の特徴i~vを有する。iタスクは非周期的である。すなわち、タスクの到着は事前にはアプリオリには分からない。あらゆるタスクtiは、属性として、到着時刻ai、レディタイムri、最悪ケース計算時間ci、実際の計算時間aci及びデッドラインdiを有する。タスクの最悪ケース計算時間は、静的コード解析、または、起こり得る最悪ケースの下での実行時間の平均に基づいて、求められる。簡単のため、実際の計算時間aciは、常に、最悪ケース計算時間ciより小さいかこれに等しいものとする。ii各タスクtiは2つのバージョン、すなわちプライマリpriとバックアップbkiを有する。2つのバージョンのすべての属性は等しいものとする。iiiタスクは並列処理可能ではない。これは、タスクが1つのプロセッサ上のみで実行可能であることを意味する。このことは、タスクのプライマリとバックアップの両方のコピーが、時間間隔di-ri内でスケジューリング可能であるように、タスクのプライマリとバックアップの最悪ケース計算時間の和がこの時間間隔di-riより小さいかこれに等しくあるべきことを必要とする。ivタスクは独立である。先行する制約条件を有するタスクに対し、タスクのレディタイムとデッドラインとは、それらがタスク間での先行する制約条件に適合するように、修正されることができる。先行する制約条件を扱うことは、修正されたレディタイムとデッドラインとによって処理を進めることと等価である非特許文献10。vタスクの割り当てが決定された後に、このタスクの開始時刻と終了時刻が分かる。Sttiが開始時刻を示し、Fttiがタスクtiの終了時刻を示すものとする。Proctiが、タスクtiがスケジューリングされているプロセッサを示すものとする。タスクの2つのコピーすなわちプライマリとバックアップとが、空間及び時間排他でスケジューリングされなければならないので、関連する文献において、以下のルールが存在する。上記で紹介したシステムモデルと調和する多くの実用的なシステムが存在する。説明の便宜上、httpハイパーテキストトランスファープロトコルによって送られてきたクライアントのリクエストを処理し、しばしば過負荷に悩まされるマルチプロセッサウェブサーバという1つの例をのみを紹介する。もちろん、本発明は、マルチプロセッサウェブサーバ以外のマルチプロセッサシステムに対しても適用することができる。ウェブサーバにおいて、サーバに新しいリクエストが到着したときに新しいタスクが生成される。新しいタスクは所定の時間範囲内で処理されるべきである。新しいリクエストの到着頻度が過度に増加すると、サーバは過負荷状態になるであろう。リクエストパケットのデッドラインを保証しようと試みるウェブサーバにおいて過負荷が発生したとき、サーバは、自ら認めた全てのリクエストを保証すべきであり、同時にシステム容量を完全に使用すべきである。リクエストを保証することができなければ、そのリクエストは拒絶されるべきであって、そのリクエストは他のサーバに移動する。一例示実施形態に基づく、オーバーローディングを伴うプライマリ-バックアップに基づくフォールトトレラント方式は、以下の動作及び条件1~20を含む。1タスクは、タスクセットを介して管理される。タスクセットの1つは、一緒にオーバーロードされるタスクの集合であると定義される。例えば図3において、1つのタスクセットはpr4,pr5,pr6を含み、もう1つのタスクセットは、pr7,bk4,bk5,bk6を含む。タスクセットはτで示される。4タスクtiがそのプライマリバージョンpriまたはそのバックアップバージョンbkiであろうことができるのと同様に、タスクセットは、以下の3つの種類、すなわち、π,β,ηのいずれか1つであろうことができる。π型のタスクセットは、タスクのプライマリバージョンのみを含み、β型のタスクセットはバックアップのみを含み、η型のタスクセットはプライマリとバックアップとを含んでいる。5単一のタスクもタスクセットであり、このタスクはπ型のタスクセットでなくてはならない。6図1、図2及び図3に示されるように、オーバーロードされたタスクの関係は、ちょうど、タスクセットの関係である。関連するタスクは、タスクセットの族であるように組織化される。族はSであると定義される。7族Sも以下の種類、すなわち、Π,B,Fのいずれか1つであろうことができる。Π型の族は、図1におけるような純粋なプライマリ-バックアップPBオーバーローディングを示し、一方、B型の族は、図1におけるような、純粋なバックアップ-バックアップBBオーバーローディングを示している。F型の族は、図3におけるような自由オーバーローディングを示している。なお、自由オーバーローディングとハイブリッドオーバーローディングとの違いは、スケジューリング及び管理においてハイブリッドオーバーローディングがタスクの特定の関係を決定し理解する必要があることである。8オーバーローディングが妥当であることを保証するために、以下のように新しいルールが追加される。9この例示実施形態は、特定のタスクスケジューリングアルゴリズムを含んでいないが、例えば図5に示される手順のように1つのタスクから別のタスクへとタスクごとにそのスケジューリングを行うであろう既存のスケジューリングアルゴリズムをサポートする。図5は、通常のスケジューリングアルゴリズムの、そのフォールトトレラントバージョンへの移行の例を示している。図5は、通常のスケジューリングアルゴリズムを示すフローチャート200Aと、この通常のスケジューリングアルゴリズムから導出されたフォールトトレラントバージョンを示すフローチャート200Bと、を含んでいる。フローチャート200Aに示される通常のスケジューリングアルゴリズムでは、まずステップ201において、全てのタスクが処理されたかどうかがチェックされる。処理されていれば、アルゴリズムのプロセスは終了し、そうでなければ、次に処理されるべきタスクとして、ステップ202において、タスクtiが取り上げられ、プロセスはステップ203に進む。ステップ203において、タスクtiに対する割り当てアロケーションが探索される。もしタスクtiに対する割り当てが見つかれば、次にタスクtiは、ステップ204において、空間的及び時間的にその割り当てにスケジューリングされ、プロセスはステップ201に戻る。ステップ203において割り当てが見つからなければ、プロセスはステップ201に直接戻る。フローチャート200Bに示されるフォールトトレラントバージョンのアルゴリズムでは、まずステップ211において、全てのタスクが処理されたかどうかがチェックされる。処理されていれば、アルゴリズムのプロセスは終了し、そうでなければ、次に処理されるべきタスクとして、ステップ212において、プライマリタスクpriが取り上げられ、プロセスはステップ213に進む。ステップ213において、プライマリタスクpriに対する割り当てが探索される。もし、プライマリタスクpriに対する割り当てが見つかれば、次に、ステップ214において、アドバイザは、バックアップタスクbkiの割り当てを依頼される。もし、バックアップタスクbkiの割り当てが成功であったら、次に、ステップ215において、タスクpriは、空間的及び時間的にその割り当てにスケジューリングされ、プロセスはステップ211に戻る。ステップ213においてプライマリタスクpriに対する割り当てが見つからなければ、プロセスはステップ211に直接戻る。ステップ214においてバックアップタスクbkiに対する割り当てが成功でなかったら、プロセスはステップ213に戻る。タスクがスケジューリングされているとき、フローチャート200Aに示されるスケジューリングアルゴリズムは、わずかに改変されて、アドバイザに対し、スケジューリングアルゴリズムで見つかったタスク割り当てが正しくかつフォールトトレラントであるかを確認するように問い合わせる。図5は、アドバイザを用いることの基本的なアイデアを示している。明らかに、通常のスケジューリングアルゴリズムにおいて大きな演算を行う必要はない。10アドバイザは、プライマリの割り当てを検査し、次に、そのバックアップに対する適切な割り当てを選択する。プライマリまたはバックアップのいずれか1つがアドバイザによって受け入れられることができないとすると、そのタスクは拒絶されるべきであり、それのち、次のタスクが考慮されるであろう。割り当てのスケジューリングや探索の核心部分にはアドバイザが干渉しないので、図5のフローチャート200Aによってモデル化される任意のスケジューリングアルゴリズムをフローチャート200Bに示されるそのフォールトトレラントバージョンに移行することができる。アドバイザの動作が図6に示されている。図6に示されるフローチャートにしたがって、アドバイザはまず、ステップ221において、タスクpriの妥当性を検査する。もし割り当てが妥当でなければ、プロセスは、ステップ223に移行し、いいえを返して終了する。タスクpriに対する割り当てが妥当であれば、アドバイザは、ステップ222において、バックアップbkiに関して、もう1つの別の可能な割り当てを探索する。もし割り当てが見つからなければ、プロセスは、ステップ223に移行し、いいえを返して終了する。ステップ222において別の割り当てが存在すれば、次に、アドバイザは、ステップ224において、タスクbkiの割り当ての妥当性を検査する。妥当でなければ、プロセスはステップ222に戻る。ステップ224において妥当であれば、アドバイザは、ステップ225において、空間的及び時間的にタスクbkiをその割り当てにスケジューリングし、プロセスは、ステップ226に移行し、はいを返して終了する。11本例示実施形態においてプライマリまたはバックアップの割り当ての妥当性を検査することは、既存の技術に比べてとても簡素である。これは、上記の4つのルール、すなわち、ルール1、ルール2、ルール3及びルール4が満足されることができるか否かのみを検査することによって妥当性を保証するだけで十分であるからである。これに対し、既存の技術は、オーバーロードされたタスクの関係を理解する必要がある。妥当性を検査することの擬似コードが図7及び図8に示されている。図7は、プライマリの割り当ての妥当性の検査に用いられる関数CPVを示し、一方、図8は、バックアップの割り当ての妥当性の検査に用いられる関数CBVを示している。12ルール4は以下の技法によって試験することができる。マルチプロセッサシステムはm個のプロセッサを有すると仮定し、族Sが訪問したプロセッサを示すために、mビットの2進数kを族Sのために用いる。2進数値kの最上位ビットMSB:mostsignificantbitが1番目のプロセッサP1に対応し、引き続くプロセッサの訪問状態は2進数値での引き続くビットにおいて示されるものとする。したがって、最下位ビットLSB:leastsignificantbitは、m番目のプロセッサPmに対応する。例えば、族Sに含まれるタスクセットがプロセッサP2,P3,P5,P6を訪問したとし、かつ、システムには8個のプロセッサP1~P8があるときには、k=01101100となる。新しいタスクセットがプロセッサP1に対して受け入られると、k=11101100となる。ルール4の検査のために、01101100∧10000000=0か否かを検証するだけで十分である。kを更新するために、k=01101100∨10000000の演算を実行するだけで十分である。この例では、ルール4の検証は、論理AND論理積演算に基づいており、更新は、論理OR論理和演算に基づいている。kの検証と更新の演算は、簡単のために、図では省略されており、ルール4を満たすこと、とだけ言っておく。新しいタスクを加えることは、2つの分離した族S1,S2を接続するかも知れない。上記で説明した方法は、族S1と族S2とが接続できるかどうかを検査することにも好適である。13アドバイザは、プライマリにとって最もふさわしい割り当てを決めるべきである。アドバイザは、バックアップをスケジューリングすることからのプライマリに対する干渉を減少させるように試みる。プライマリに対して選択されたタイムスロットがCPVを合格した場合に限り、そのプライマリはそのタイムスロットに割り当てられるであろう。スケジューリングアルゴリズムがプライマリのための割り当てを探索するとき、π型のセットとη型のセットのみが考慮され、β型のセットはプライマリに関して無視される。14バックアップをスケジューリングすることは、バックアップが実際にはゴーストであって他のものの上にオーバーロードされることができるので、プライマリをスケジューリングすることからは異なっている。もしバックアップがプライマリのスケジューリングに干渉しないであろうとすると、耐故障性はコスト不要のものであるであろう。したがって、バックアップに起因する干渉は、最小のものとなるように制御されるべきである。バックアップタスクbkiは、基本的には、[Ftpri,di]の範囲内で割り当てられるべきである。したがって、Pj,Pj≠Procpriにおいて、各タイムスロットが[Ftpri,di]であると考える必要があるなお、この条件の下で、このバックアップの割り当ては、妥当でないかもしれず、妥当性はCBVによって検査される。15タスクセットの時間長λは、であると定義される。時間長限界Λはユーザパラメータである。両方の妥当性検査関数CPV及びCBVにおいて、時間長がチェックされるあろう。もし時間長λが時間長限界Λを超えるならば、タスクは妥当性検査を合格することができない。簡単のため、時間長をチェックすることは、関連する図面からは省略されている。16アドバイザは、バックアップにとって最もふさわしい割り当てをも決めるべきである。一例示実施形態において、バックアップに対してポリシーが与えられてもよい。バックアップは、できるだけ遅い空きタイムスロットを取るように試みられるか、あるいは、バックアップは、既存のタスクセットに割り当てられるように試みられる。もし、CBVを合格した2以上のタスクセット{τ1,τ2,τ3...}が存在するときは、δ=max{δ|∀τi}であれば、タスクbkkに対してタスクセットτが選択される。どこにバックアップを割り当てるかを決定するためにユーザパラメータが使用される。17ユーザパラメータである、詰まり具合の重みωが導入されてもよい。タスクbkkがオーバーロードされることができるタスクセットが存在しないときは、確実にδ=0であって、できるだけ遅い空きタイムスロットにバックアップはスケジューリングされる。もしδ≠0ならば、次に、δがωよりも大きいかどうかがチェックされる。δ>ωならば、バックアップはタスクセットτにオーバーロードされる。δ≦ωかつ空きタイムスロットがないときも、バックアップはタスクセットτにオーバーロードされる。δ≦ωかつ空きタイムスロットがあるときは、バックアップは、その空きタイムスロットにスケジューリングされる。18βのダイナミクスも導入されてもよい。タスクがタスクセットにオーバーロードされようとするとき、オーバーローディングができるだけぎっしりと詰まったものであって、少なくとも詰まり具合の重みがω以上であることを期待する。したがって、プライマリまたはバックアップであるタスクtkが、βであるタスクセットにオーバーロードされようとするとき、δを増加させるようにβは前進させられるだろう。βのこのダイナミクスはアドバイザ内に埋め込まれていてもよく、図には明示的には示されていない。19故障が発生したとき、失敗したタスクセットは、再帰アルゴリズムによって取り扱われて、故障に耐える。タスクが上記の項目1~17に関して完全にスケジューリングされていれば、各族Sは、根付き有向木である。根はβ型のタスクセットである。全ての葉はπ型のタスクセットである。内部頂点が存在すれば、全ての内部頂点はη型のタスクセットである。1~18における全ての条件及び動作は、数学的に正しいものであることが証明されている。20族Sが崩壊するとき、タスクセットがタスクに直接分解することはないだろう。その代わり、族Sは、まず、いくつかの独立した族Sに分解されるように試みられる。新しいSが再組織化できない場合にのみ、タスクセットは分離したタスクに分解させられるであろう。21プライマリまたはバックアップをそのバックアップまたはプライマリにそれぞれ転換する操作である手続きrevsを導入することができる。バックアップに対する新しい割り当てを見つけることは、プロセッサを探索して、空であるかタスクセットによって占められている割り当てを探し出すことである。なお、CBVは、新しい割り当てに関して呼び出される。CBVは、上記項目12におけるものと同様に、2つの分離した族Sが接続できるかどうかをチェックしなければならない。次に、上記の例示実施形態に基づくフォールトトレラント方法によって与えられる貢献について説明する。第1に、スケジュールでのタスクの関係に関する知識なしで、いくつかの単純な条件の下のみで形式張らずにタスクをオーバーロードするために、新しいオーバーローディング技術が提案される。このやり方で、プライマリ-バックアップ方式と形式張らないオーバーローディングとが、プライマリのスケジューリングから分離され、その結果、アドバイザを使用することによって、種々のリアルタイムスケジューリングアルゴリズムを簡単にフォールトトレラントにすることができる。アドバイザは、タスクの割り当てがフォールトトレラントであるかどうかの情報を伴ってタスクスケジューラに応答することができ、その一方で、対応するバックアップを正しくスケジューリングすることができる。第2に、タスク、プライマリ及びバックアップの管理が形式化され、形式張らないオーバーローディングを注意深く調べることを介して、タスクオーバーローディングと故障に耐えることとを管理するために、一連のアルゴリズムが発展させられている。その一方で、アルゴリズムは、オーバーローディングを分解し組み直すことによって、故障に耐えたのちのオーバーローディングを修復するように、設計される。上記に開示される例示実施形態の全体または部分は、以下の変形例を含むことができるが、これらに限定されるものではない。変形例1:プライマリ-バックアップに基づいてマルチプロセッサシステムにおいて耐故障性をサポートする方法が提供される。この方法は、いくつかのキーとなるサブ方法を含み、サブ方法は、通常のリアルタイムスケジューリングアルゴリズムをそのフォールトトレラントバージョンに移行する方法と、タスク割り当てとオーバーローディングに関して通常のアルゴリズムに応えるアドバイザと、障害に耐える方法と、を含む。変形例2:変形例1に記載された、通常のリアルタイムスケジューリングアルゴリズムをそのフォールトトレラントバージョンに移行する方法が提供される。この方法は、元のアルゴリズムを変更せず、変形例1において知られているように、アドバイザまたはアドバイザアルゴリズムを元のスケジューリングアルゴリズムに追加するだけである。図5のフローチャート200Aに示されるような形態で表現されることができる全ての通常のリアルタイムスケジューリングアルゴリズムは、この方法によって、フォールトトレラントバージョンに移行されることができる。この方法は、タスクをタスクセットとして管理することと、タスクセットを根付き有向木として管理することと、通常のスケジューリングアルゴリズムを過度に妨げないようにアドバイザを用いることと、の特徴を含む。変形例3:変形例2でのタスクを管理する方法は、各タスクがタスクセットとして管理されるように変更される。タスクセットは、多数のタスクを含むことができる。タスクセット内のタスクの種類に応じて、タスクセットは異なる種類に分類されることができる。タスクセットはまた、タスクセットの族として知られる、異なる集合として管理される。新しいタスクを追加することは、族を拡張することと等しい。故障に耐えることは、族を分解することと等しい。タスクセットの族は、タスクセットの複数の分離した族に分解することができ、タスクセットの異なる族は、タスクセットの単一の族に結合されることができる。変形例4:タスクセットの族は、変形例2で説明したものと同様の構造を有するフォールトトレラント木として管理される。フォールトトレラント木は、根付き有向木である。根、内部頂点及び葉は、タスクセットの異なる種類である。変形例5:変形例1,2のいずれか1つに記載されたアドバイザは、オーバーローディングの妥当性の検査に関し、元の通常のアルゴリズムからの問い合わせに答え、その一方でバックアップのスケジューリングを行う。アドバイザは、単純にいくつかのルールによってオーバーローディングの妥当性を決定する処理と、バックアップをスケジューリングする処理と、を実行する。変形例6:変形例5でのオーバーローディングの妥当性を決定する方法は、図7に示されるアルゴリズムCPVと図8に示されるアルゴリズムCBVを含む。これらのアルゴリズムは、全てのルールが満たされることができるか否かを検証する、特にルール4の検証を行う、重要なステップを有する。もし、いずれかのルールを満たすことができなければ、対応するタスクは拒絶されるべきである。変形例7:変形例6でのルール4の検証は、2進数であってプロセッサの数と等しい長さを有するキーにプロセッサを符号化することを含む。ルール4を検証することは、2つの2進数に対してAND論理積演算を実行することである。もし、AND演算の結果が0であればルール4は満足され、そうでなければ満たされていない。もし、タスクセットの族にタスクセットが加えられるならば、2つの2進数上で実行されるOR論理和演算によって、キーは更新される。タスクセットの2つの分離した族を接続することは、この技術にも基づいている。変形例8:バックアップは、i詰まり具合の重みに関する異なる条件に応じて、バックアップをできるだけ遅くにスケジューリングするか、あるいは、以前のタスクセットに対してできるだけぎっしりと詰めてバックアップをオーバーローディングするか、を決定することと、ii変形例1に基づいてバックアップを動かすことにより、詰まり具合を最大化することと、を含む方法にしたがって、スケジューリングされる。この方法は、バックアップをできるだけ遅くにスケジューリングするか、または、できるだけ詰めてバックアップをオーバーロードするかを決定を行う。この方法は、さらに、iiiユーザによって定義された時間長限界未満となるように、いずれのタスクセットについてもその時間長を制御することを含んでいる。変形例9:変形例1に基づく故障に耐える方法は、タスクをタスクセットとして管理することと、各プロセッサに関して故障に耐えることと、再帰的にタスクセットを取り扱うことと、オーバーローディングを組み直すことと、を含む。故障に耐えるアルゴリズムの一例が、手続きFTの擬似コードを示す図9に示されている。図9に示されるアルゴリズムは、1つのプロセッサにおける故障を仮定し、RTHandler再帰的にタスクセットを取り扱うためのアルゴリズムに対する呼び出しを含む全ての分岐条件とステップとを含んでいる。RTHandlerの擬似コードは、全ての分岐条件とステップとを含む図10に示されている。アルゴリズムには、故障が起きたときに、タスクセットの集合を分離した複数の集合に組み直すことを試みる方法が埋め込まれている。したがって、上記の説明は、本発明の原理を図解するだけのものであると考えるべきである。さらに、数々の変更と改良とが容易に当業者の心に浮かぶであろうから、ここで示され説明された通りの構成及び動作に本発明を限定することは好ましくない。したがって、本発明の範囲内に含まれるすべての適切な変更及び等価物が用いられるであろう。"