(57)【特許請求の範囲】
【請求項１】
時分割で２つのタスクを実行するための方法であって、
・連続フレームの各々の反復シーケンス（ＲＳＦ）内の各タスクをオフラインで、各々のタスクと関連付けられた時間基準で分解するステップであって、各フレーム（Ｆ）が実行時間（Ｄ）を有する原子演算と関連付けられ、ｉ）前記原子演算が開始してよい開始日、ｉｉ）前記原子演算が終了しなければならない期日（Ｅ）、及びｉｉｉ）前記原子演算の実行時間よりも少ない前記フレームの持続時間に等しい時間マージン（Ｔ）を定めるステップと、
・前記２つのタスクの内の第１のタスクのＲＳＦの現在のフレーム（Ｆａｉ）ごとに、検証ステップを行うステップであって、前記検証ステップは、
‐前記２つのタスクの内の第２のタスクのＲＳＦの連続フレームのグループを決定することであって、前記グループの各フレームが前記現在のフレームに重なることと、
‐前記現在のフレームの原子演算（Ｄａｉ）が、前記現在のフレームの原子演算の及び前記連続フレームのグループの原子演算の開始日及び期日を守りつつ、前記連続フレームのグループのあらゆる２つの連続する原子演算の間に完了することができることをチェックすることと、
を含むステップと、
・前記検証ステップが、前記現在のフレームの原子演算が完了することができると判定する場合、前記２つのタスクの実行を許し、前記原子演算（Ｄａ３、Ｄｂ２）の期日、開始日、及び終了から成る重要な日付のグループ内の各日付で評価された以下のケース、つまり
‐各タスクの原子演算が開始することができる場合、より短い期日を有する原子演算を実行することと、
‐前記２つのタスクの内の一方のみの原子演算が開始することができる場合、その実行時間が、前記２つのタスクの内の他方のＲＳＦの次のフレームの開始日まで残っている時間に加え、前記次のフレームと関連付けられた時間マージンより少ない場合にのみその原子演算を実行することと、
に従って、前記２つのタスクの原子演算をスケジューリングするステップと、
を含む、方法。
【請求項２】
各フレームが、前記フレームの期日の後、又は前記フレームの開始日の前に位置する予備時間間隔（Ｒ）をさらに備え、前記２つのタスクの内の何れか一方のＲＳＦの予備時間間隔が、前記２つのタスクの内の他方のＲＳＦ内において原子演算を実行するために前記時間マージンに付加される、請求項１に記載の方法。
【請求項３】
前記検証ステップが、
・前記第１のタスクのＲＳＦのフレーム（Ｆａｉ）ごとに、以下の条件：
［Ａ．１］Ｄａｉ≦Ｔｂｊ＋１
［Ｂ．１］Ｄａｉ≦Ｒｂｊ＋Ｔｂｊ＋１、且つ、Ｄｂｊ≦Ｔａｉ、及び
［Ｃ．１］Ｄｂｊ≦Ｔａｉ
を前記第２のタスクのＲＳＦのフレーム（Ｆｂｊ）ごとに評価するステップであって、
式中、Ｄ、Ｔ及びＲが、ＲＳＦ識別子及び前記シーケンス内のフレーム番号でインデックスを付けられた、実行時間、時間マージン、及び予備時間であるステップと、
・前記フレーム（Ｆａｉ及びＦｂｊ）が交換された状態で前記評価するステップを反復するステップと、
・３つの条件「Ａ．１］、［Ｂ．１］及び［Ｃ．１］が任意の組（ｉ、ｊ）について満たされる場合に前記タスクの実行を許可するステップと、
を含む、請求項２に記載の方法。
【請求項４】
前記検証ステップが、
・前記条件［Ａ．１］が偽である場合、以下の条件：
［Ａ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２、且つ、Ｄａｉ＋Ｄｂｊ＋１≦Ｔａｉ＋Ｔｂｊ＋１
を評価するステップと、
・前記条件［Ｂ．１］が偽である場合、以下の条件：
［Ｂ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２、且つ、Ｄｂｊ＋Ｄａｉ＋Ｄｂｊ＋１≦Ｔａｉ＋Ｔｂｊ＋１
を評価するステップと、
・前記条件［Ｃ．１］が偽である場合、以下の条件：
［Ｃ．２］Ｄｂｊ≦Ｔａｉ＋ｍｉｎ［Ｔｂｊ−Ｄａｉ，Ｒａｉ，Ｒａｉ−１］
を評価するステップと、
・条件「Ａ．１」又は［Ａ．２］及び［Ｂ．１］又は［Ｂ．２］及び［Ｃ．１］又は［Ｃ．２］が各組（ｉ、ｊ）について満たされる場合、前記タスクの実行を許可するステップと、
を含む、請求項３に記載の方法。
【請求項５】
前記フレームの持続時間を決定する時間基準が、前記時間マージン（Ｔ）及び前記予備時間間隔（Ｒ）が、前記フレーム（Ｆａｉ）については１倍乃至ｚａ倍に変動し、前記フレーム（Ｆｂｊ）については１倍乃至ｚｂ倍に変動するように可変であり、前記ｚａが、前記フレーム（Ｆａｉ）に対応する反復シーケンス（ＲＳＦａ）について導入される係数であり、前記ｚｂが、前記フレーム（Ｆｂｊ）に対応する反復シーケンス（ＲＳＦｂ）について導入される係数であり、前記検証ステップが、
・前記条件［Ａ．１］が偽である場合、以下の条件：
［Ａ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２、且つ、ｍｉｎ［ｑｌ（ｚｂ・（Ｔｂｊ＋Ｒｂｊ）＋（ｚｂ−１）Ｄｂｊ），Ｄａｉ］＋Ｄｂｊ＋１≦Ｔａｉ（式中、ｑｌ＝（Ｄａｉ−Ｔｂｊ＋１）／（Ｔｂｊ＋Ｒｂｊ））
を評価するステップと、
・前記条件［Ｂ．１］が偽である場合、以下の条件：
［Ｂ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２、且つ、Ｄｂｊ＋ｍｉｎ［ｑｌ（ｚｂ・Ｔｂｊ＋（ｚｂ−１）Ｄｂｊ）＋ｚｂ・Ｒｂｊ，Ｄａｉ］＋Ｄｂｊ＋１≦Ｔａｉ（式中、ｑ１＝（Ｄａｉ−Ｒｂｊ−Ｔｂｊ＋１）／Ｔｂｊ）
を評価するステップと、
・前記条件［Ｃ．１］が偽である場合、以下の条件：
［Ｃ．２］Ｄｂｊ≦Ｔａｉ＋ｍｉｎ［Ｔｂｊ−Ｄａｉ，Ｒａｉ，Ｒａｉ−１］
を評価するステップと、
・条件［Ａ．１］又は［Ａ．２］及び［Ｂ．１］又は［Ｂ．２］及び［Ｃ．１］又は［Ｃ．２］が各組（ｉ、ｊ）について満たされる場合に、前記タスクの実行を許可するステップと、
をさらに含む、請求項３に記載の方法。
【請求項６】
前記検証ステップが、
・前記条件［Ｂ．１］が偽である場合、前記条件［Ｂ．２］の前に以下の条件：
［Ｂ．１．１］Ｄａｉ≦Ｔｂｊ＋Ｒｂｊ＋Ｔｂｊ＋１、且つ、Ｄｂｊ−１≦Ｔ１＋ｍｉｎ［Ｔｂｊ−１＋Ｄｂｊ−１＋Ｒｂｊ−１‐Ｔ１‐Ｄａｉ−１，Ｒａｉ−２］（式中、ｑｌ＝（Ｄａｉ−Ｒｂｊ−Ｔｂｊ＋１）／Ｔｂｊ、且つ、Ｔ１＝Ｔａｉ−１−（１−ｑｌ）Ｔｂｊ＋Ｒａｉ−１）
を評価するステップと、
・条件［Ａ．１］又は［Ａ．２］及び［Ｂ．１］又は［Ｂ．２］及び［Ｃ．１］又は［Ｃ．２］が各組（ｉ、ｊ）について満たされる場合に、前記タスクの実行を許可するステップと、
を含む、請求項５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信網においてのように、リソースの制御された割当てが重要である他のシステムだけではなく、運輸（自動車、鉄道、船舶、宇宙）、産業自動化、エネルギーの分野でも使用される制御システム及び監視システム等のマルチタスクリアルタイムクリティカルシステムに関する。本発明は高水準の実装性能が必要とされるリアルタイムシステムと、システムの各タスクに割り当てられるハードウェアリソースの使用に関して高レベルの保証が必要とされるクリティカルシステムの両方に関する。
【背景技術】
【０００２】
クリティカルリアルタイムシステム、つまり演算の遅れた実行によるいかなる期日違反も許容しないシステムでは、タスクな多くの場合静的スケジューリング方法によって実行される。実行リソースに対する必要性の静的な一時割当ては次いでオフラインで構築され、このことはリソース、特にプロセッサの使用に関してタスク間のタスクの時間的な独立性を明示している。この手法は、例えば記事［「安全クリティカルリアルタイムシステムにおける適時性をモデル化し、保証するための方法及び技法」、Ｃ．Ａｕｓｓａｇｕｅｓ、Ｖ．Ｄａｖｉｄ、第４回ＩＥＥＥコンプレックスコンピュータシステム国際会議、１９９８年］、並びに特許出願第ＷＯ２００６−０５０９６７号及びＵＳ第２０１０-０１９９２８０号に説明されている。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、この手法はすべての活動の単一の順序付け計画だけを検討することを必要とし、したがって期日を決定するための単一の時間基準だけを検討する。これは、クロックを使用してクロックの期日を決定するタスク、及び可変速度オブジェクトの位置を使用して可変速度オブジェクトの期日を決定するタスク等、相関関係のない時間基準のタスクの場合、単一のプロセッサに対する干渉のない実装を困難にする。これは、共通の時間基準によって計時される２つの順序付け計画を、該順序制御計画がタスク間の干渉のない単一の順序付け計画で構成できるように構築することを暗示するだろう。これは、各状況の最悪の事態を考慮するためにリソースが広く特大である場合にだけ実際に達成可能である。
【０００４】
いくつかのリアルタイムシステムが一定のマージンの中で期日違反を許容できるために「クリティカル」と定義されない高水準性能を有するいくつかのリアルタイムシステムでは、異なる時間基準によって計時される２つの順序付け計画の構成は、動的スケジューリングアルゴリズムによって実行される。係るアルゴリズムは、例えば［「ハードリアルタイム環境でのマルチプログラミングのためのスケジューリングアルゴリズム、Ｃ．Ｌｉｕ、Ｊ．Ｌａｙｌａｎｄ、ＡＣＭジャーナル、第２０巻、第１号、４６−６１ページ」］及び［「リアルタイムコンピューティングの基礎：スケジューリング及びリソース管理」、Ａｎｄｒｅ  Ｍ．  Ｖａｎ  Ｔｉｂｏｒｇ、Ｇａｒｙ  Ｍ．  Ｋｏｏｂ編集、１９９１年、Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ］及び［「安全クリティカルリアルタイムシステムで適時性をモデル化し、保証するための方法及び技法」、Ｃ．Ａｕｓｓａｇｕｅｓ、Ｖ．Ｄａｖｉｄ、第４回ＩＥＥＥコンプレックスコンピュータシステム国際会議、１９９８年］にも説明されている。
【０００５】
これらのアルゴリズムを用いる場合強制排除は不可避である。つまり、オペレーティングシステムはより緊急の演算を実行するために進行中の演算を中断できる。スケジューリングは動的であるので、強制排除の数及び持続時間は特定できず、各強制排除はコンテキストの切替えを実行するためにオーバヘッドを導入する。これがタスク間の干渉を生じさせ、これによりシステムはサイジングするのがより困難となり、より予測不可能になり、複雑なプロセッサアーキテクチャで再現可能ではない。また、係るシステムの設計者は、２つの異なる時間基準を有するシステムでのタスク優先順位又は期日を適切に設定するために困難に遭遇する。アプリケーションパラメータの値に応じた実行必要性の変動等の選ばれたオプションは、このようにして構築されたシステムを非常に複雑且つ制御不可能にする。
【課題を解決するための手段】
【０００６】
したがって、２つの計画の時間基準が異なっていても、干渉なく２つの順序付け計画を時分割で実行できる技術の必要性がある。
【０００７】
この必要性は、タスクと関連付けられた時間基準で連続フレームの反復シーケンスで各タスクをオフラインで分解するステップであって、各フレームが実行必要性を有する原子演算と関連付けられ、演算が開始する開始日及び演算が終了しなければならない期日を定義し、それによって各フレームが演算が開始する時間マージンを定義する、分解するステップと、演算の開始日及び期日を尊重しつつ、反復シーケンスの内の第１の反復シーケンスのフレームごとに、対応する演算が、第１の反復シーケンスのフレームに重なる第２の反復シーケンスのフレームのグループのあらゆる２つの連続演算の間で実行できることを検証するステップと、検証が満たされる場合、２つのタスクの実行を許すステップとを含む、２つのタスクを時分割で実行するための方法を提供することによって対応される。
【０００８】
２つのタスクの演算は次いで以下の場合に従ってスケジューリングされ、それぞれの重要な日付で評価され、重要な日付は各期日、各開始日、及び演算が終了するたびに発生する。つまり、２つの演算が開始できる場合、より短い期日を有する演算を実行し、単一の演算が開始できる場合、該演算の実行の必要性が、他のシーケンスの次のフレームと関連付けられた時間のマージンが加えられた他のシーケンスの該次のフレームの開始日までに残っている時間に満たない場合にだけ該演算を実行する。
【０００９】
各フレームは、フレームの期日後又はフレームの開始日前に位置する、ゼロであることがある予備の時間間隔をさらに含むことがあり、反復シーケンスの内のいずれか１つの予備の時間間隔は他の反復シーケンスの演算を実行するために使用されてよい。
【００１０】
検証ステップは以下の
・第１の反復シーケンスのフレームＦａｉごとに、第２の反復シーケンスの各フレームＦｂｊの以下の条件を評価するステップであって、
［Ａ．１］Ｄａｉ≦Ｔｂｊ＋１
［Ｂ．１］Ｄａｉ≦Ｒｂｊ＋Ｔｂｊ＋１
及びＤｂｊ≦Ｔａｉ、並びに
［Ｃ．１］Ｄｂｊ≦Ｔａｉ、
上式では、Ｄ、Ｔ、及びＲは、反復シーケンス識別子及びシーケンスのフレーム番号でインデックスが付けられた、実行必要性、時間マージン、及び予備時間である、評価するステップと、
・フレームＦａｉ及びＦｂｊが交換された状態で条件評価を繰り返すステップと、
・３つの条件［Ａ．１］、［Ｂ．１］、及び［Ｃ．１］が任意の組（ｉ、ｊ）について満たされる場合にタスクの実行を許可するステップと
を含むことがある。
【００１１】
検証ステップは、以下の追加の
・条件［Ａ．１］が偽である場合、以下の条件
［Ａ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びＤａｉ＋Ｄｂｊ＋１≦Ｔａｉ＋Ｔｂｊ＋１
を評価するステップと、
・条件［Ｂ．１］が偽である場合、以下の条件
［Ｂ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びＤｂｊ＋Ｄａｉ＋Ｄｂｊ＋１≦Ｔａｉ＋Ｔｂｊ＋１
を評価するステップと、
・条件［Ｃ．１］が偽である場合、以下の条件
［Ｃ．２］Ｄｂｊ≦Ｔａｉ＋ｍｉｎ［Ｔｂｊ−Ｄａｉ，Ｒａｉ，Ｒａｉ−１］
を評価するステップと、
・条件［Ａ．１］又は［Ａ．２］及び［Ｂ．１］又は［Ｂ．２］及び［Ｃ．１］又は［Ｃ．２］が組（ｉ、ｊ）ごとに満たされる場合に実行を許可するステップと
を含んでよい。
【００１２】
フレームの持続時間を決定する時間基準は、時間マージンＴ及び予備時間ＲがフレームＦａの場合ｚａに係数１分変化し、フレームＦｂの場合ｚｂに係数１分、変化し得るように可変であってよい。検証ステップは、次いで
・条件［Ａ．１］が偽である場合、以下の条件
［Ａ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びｍｉｎ［ｑl（ｚｂ・（Ｔｂｊ＋Ｒｂｊ）＋（ｚｂ−１）Ｄｂｊ)，Ｄａｉ]＋Ｄｂｊ＋１≦Ｔａｉ
上式ではｑｌ＝（Ｄａｉ−Ｔｂｊ＋１)/(Ｔｂｊ＋Ｒｂｊ)
を評価するステップと、
・条件［Ｂ．１］が偽である場合、以下の条件
［Ｂ．２］Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びＤｂｊ＋ｍｉｎ［  ｑｌ（ｚｂ・Ｔｂｊ＋（ｚｂ−１）Ｄｂｊ)＋ｚｂ・Ｒｂｊ, Ｄａｉ]＋Ｄｂｊ＋１≦Ｔａｉ
上式ではｑｌ＝（Ｄａｉ−Ｒｂｊ−Ｔｂｊ＋１)/Ｔｂｊ
を評価するステップと、
・条件［Ｃ．１］が偽である場合、以下の条件
［Ｃ．２］Ｄｂｊ≦Ｔａｉ＋ｍｉｎ［  Ｔｂｊ−Ｄａｉ，Ｒａｉ，Ｒａｉ−１］
を評価するステップと、
・条件［Ａ．１］又は［Ａ．２］及び［Ｂ．１］又は［Ｂ．２］及び［Ｃ．１］又は［Ｃ．１］が組（ｉ、ｊ）について満たされる場合、タスクの実行を許可するステップと
をさらに含んでよい。
【００１３】
検証ステップは、以下の
・条件［Ｂ．１］が偽である場合、条件［Ｂ．２］の前に以下の条件
［Ｂ．１．１］Ｄａｉ≦Ｔｂｊ＋Ｒｂｊ＋Ｔｂｊ＋１
及びＤｂｊ−１≦Ｔｌ＋ｍｉｎ［  Ｔｂｊ−１＋Ｄｂｊ−１＋Ｒｂｊ−１−Ｔｌ−Ｄａｉ−ｌ，Ｒａｉ−２］
上式ではｑｌ＝（Ｄａｉ−Ｒｂｊ−Ｔｂｊ＋１）／Ｔｂｊ及びＴｌ＝Ｔａｉ−１−（１−ｑｌ）Ｔｂｊ＋Ｒａｉ−１
を評価するステップと、
・条件［Ａ．１］又は［Ａ．２］及び［Ｂ．１］又は［Ｂ．１．１］及び［Ｃ．１］又は［Ｃ．２］が組（ｉ、ｊ）ごとに満たされる場合、タスクの実行を許可するステップと
をさらに含んでよい。
【００１４】
他の優位点及び特徴は、例示的な目的だけに提供され、添付図面中に表される本発明の特定の実施形態の以下の説明からより明確になるだろう。
【図面の簡単な説明】
【００１５】
【図１】タスクの順序付け計画を構成するために使用されるフレームの連続シーケンスの例を示す図である。
【図２】反復シーケンスのフレームの構造、及びフレームで演算を開始する異なる可能性を示す図である。
【図３Ａ】フレームの２つの反復シーケンスを時分割する異なる可能性を示し、図３Ｃはエラー状態を示す図である。
【図３Ｂ】フレームの２つの反復シーケンスを時分割する異なる可能性を示し、図３Ｃはエラー状態を示す図である。
【図３Ｃ】フレームの２つの反復シーケンスを時分割する異なる可能性を示し、図３Ｃはエラー状態を示す図である。
【図４Ａ】２つのシーケンスの構成のバリデーション基準を確立するための第１の想定に従った２つのシーケンスの時分割状況を示す図である。
【図４Ｂ】２つのシーケンスの構成のバリデーション基準を確立するための第１の想定に従った２つのシーケンスの時分割状況を示す図である。
【図４Ｃ】２つのシーケンスの構成のバリデーション基準を確立するための第１の想定に従った２つのシーケンスの時分割状況を示す図である。
【図５Ａ】２つのシーケンスの構成のバリデーション基準を確立するための第２の想定に従って２つのシーケンスの時分割状況を示す図である。
【図５Ｂ】２つのシーケンスの構成のバリデーション基準を確立するための第２の想定に従って２つのシーケンスの時分割状況を示す図である。
【図６】２つのシーケンスの構成のバリデーション基準を確立するための第３の想定に従った２つのシーケンスの時分割状況を示す図である。
【図７】図５Ａの状況で別の有効性条件を確立するためのフレームの連続の例を示す図である。
【図８】代替の有効性条件を確立することを許す、第３の想定に従った２つのシーケンスの追加の実行状況を示す図である。
【発明を実施するための形態】
【００１６】
リアルタイムタスクは、次々と実行される演算の基本プロセスのシーケンスとして見なされてよく、各演算はタスクと関連付けられた時間基準での期日を有する。クリティカルリアルタイムシステムでは、期日は必須である。つまり、その期日を超える演算は、例えばエラー状態及びシステム停止を引き起こすだろう。以下に説明される技法は、相関関係のない時間基準でも複数のタスクがシステム上で時分割で実行され得る点で性能のレベルを改善するために係るシステムに適用できる。
【００１７】
図１は、フレームの反復シーケンスＲＳＦにタスクを分解することを示し、各フレームＦはタスクの順次演算に割り当てられる。タスクはループの反復シーケンスＲＳＦを実行することによって実装される。
【００１８】
図２は、フレームＦの時間構造を示す。フレームの開始は、演算が開始し得る日付である。フレームは演算を完了する必要のある期日Ｅを定める。演算は原子的であると見なされる。つまり、演算は別の演算を実行するために一時停止できない。期日Ｅは、ゼロであってよい任意選択の予備タイムスロットＲ分、フレームの最後に先行してよい。時間間隔Ｄはフレームと関連付けられた演算の実行必要性である。実行必要性Ｄは、例えば演算を実行するために必要とされるプロセッサクロックサイクルの数に相当する‐したがって、実行必要性Ｄはターゲットシステムのプロセッサの特性に応じた固定時間として表されてよい。間隔Ｔは、フレームの開始と演算を実行するための期日Ｅとの間の時間マージンに相当する。
【００１９】
このようにして、図２に示されるように、演算は、間隔Ｔが演算の最後と期日との間にあるフレームの開始と、演算がまさに期日Ｅで終了するフレームの開始後の時間Ｔとの間のどこで始まってもよい。中間状況の場合、ｑＴはａ演算の最後と期日との間の間隔を示し、０≦ｑ≦１であり、（１−ｑ）Ｔはフレームの始まりと演算の始まりとの間の相補的な間隔を示す。
【００２０】
予備間隔Ｒの合計は、例えば、プログラマが入力／出力等の非リアルタイム演算を実施するためにシステムに割り当てる時間である。
【００２１】
クリティカルリアルタイムシステムで時分割で実行される必要のある２つのタスクは、このようにしてフレームの反復シーケンスに分解される。タスクが干渉なく実行可能であるため、つまり演算の原子性を尊重するためには、２つのシーケンスのフレームの制約、つまり期日及びフレーム開始を尊重しつつ、一方のシーケンスの各演算が他方のシーケンスの２つの連続演算間でいつでも実行できるようにシーケンスを構成することが求められる。
【００２２】
図３Ａから図３Ｃは、２つのシーケンスＲＳＦａ及びＲＳＦｂを展開する間に遭遇することがある多様な状況を示す。簡略にするために、予備間隔Ｒがゼロであると想定される。
【００２３】
図３Ａでは、例として、シーケンスＲＳＦａは、それぞれのパラメータ（Ｄａ１＝３、Ｔａ１＝６）、（Ｄａ２＝４、Ｔａ２＝１）、及び（Ｄａ３＝１、Ｔａ３＝１）の３つのフレームＦａ１からＦａ３を含み、時間値は正規化された単位で表される。シーケンスＲＳＦｂは、フレームＦａ１の開始の３単位後に始まり、それはそれぞれのパラメータ（Ｄｂ１＝４、Ｔｂ１＝５）及び（Ｄｂ２＝３、Ｔｂ２＝４）の２つのフレームＦｂ１及びＦｂ２を含む。
【００２４】
演算Ｄａ１は対応するフレームの開始の１単位後に始まる。演算Ｄａ１の最後で、演算Ｄａ２はまだ開始できないが、演算Ｄｂ１は開始されてよい。演算Ｄｂ１の最後で、演算は実行のために準備完了していない。フレームＦａ２の開始、ここでは期日Ｅａ１は演算Ｄａ２を開始するために待機される。演算Ｄａ２の最後で、演算Ｄｂ２は実行可能であるが、演算Ｄｂ２は開始されるべきではない。実際に、演算Ｄｂ２がただちに起動されると、演算Ｄｂ２はまさに期日Ｅａ３で終了し、それによって演算Ｄａ３はその期日前に実行できないだろう。この状況では、フレームＦａ３の始まりは演算Ｄａ３を起動するために待機される。最後に、演算Ｄｂ２は演算Ｄａ３の最後で開始できる。
【００２５】
図３Ｂでは、演算Ｄａ１がフレームの始まり３単位後に開始する点を除き、同じパラメータが保存される。演算Ｄｂ１及び演算Ｄａ２は、対応するフレームの制約を尊重しつつ、図３Ａに関して２単位分遅延する。演算Ｄａ２はまさにその期日Ｅａ２で終了する。
【００２６】
図３Ｃでは、演算Ｄａ１がフレームの始まり４単位後にここで開始する点を除き、同じパラメータが保存される。演算Ｄｂ１及び演算Ｄａ２は、図３Ａに関して３単位分遅延する。演算Ｄｂ１は、その期日Ｅｂ１を尊重しつつ依然として実行できるが、演算Ｄａ２はその期日Ｅａ２に違反する。
【００２７】
本明細書に参照される技法に共通した第１のステップは、時分割で実行するための２つのタスクについて、シーケンスの始まりの間の遅延に関わりなく、図３Ａ又は図３Ｂの状況で解くことができる２つの連続シーケンスＲＳＦａ及びＲＳＦｂの構成を含む。この構成は静的である。つまり、プログラマによってオフラインで達成される。
【００２８】
第２のステップは、任意の２つのシーケンスが互換性があること、つまり任意の２つのシーケンスが、図３Ａ及び図３Ｂにおいてのように、各演算をその制約の中で実行できるように解くことができることを検証することを含む。
【００２９】
この互換性の検証は、プログラマが試行錯誤でシーケンスを構成するために設計された開発ツールに実装されてよい。また、該互換性の検証は、好ましくは実行のために２つの反復シーケンスによって定められたシーケンス計画のロード時に、リアルタイムシステム自体で実施される。システムは、次いでシーケンスが互換性がないとして検出される場合に演算を拒絶するように構成されてよい。
【００３０】
第３のステップは、リアルタイムシステムで２つのシーケンスの演算をスケジューリングすることを含む。図が示すように、第１のシーケンスの演算を第２のシーケンスの演算と交互にする又は演算が実行のために準備が完了したときに演算を開始することは、正しい演算を達成するためには十分ではない。スケジューリングはそれぞれの重要な日付で評価される以下の場合に従って達成されてよい。重要な日付は２つのシーケンスのフレームの始まり、期日、及び演算終了として定められてよい。予備のタイムスロットＲ（図２）がゼロであるとき、提示されている例においてのように、期日はフレーム開始と一致する。シーケンスの内の第１のシーケンスと関連付けられた所与の重要な日付の場合、用語「同時並行フレーム」は、第２のシーケンスの現在のフレームを示す。
１）演算は開始できない。これは、演算が（図３Ａの期日Ｅｂ１でのように）すでに進行中であるときに、又は図３Ａの演算Ｄｂ１に関して同時並行フレームの演算とその期日との間に実行する演算の最後で発生する。この場合、次の重要な日付が待たれる。
２）２つの演算が開始できる。これは通常、図３Ａ及び図３Ｂの期日Ｅａ２での場合のように演算が同時並行フレームで待機中にフレームを開始するときに起こる。最短の期日を有する演算が次いで実行される（図３Ａ及び図３ＢのＤａ３）。ケースは、２つの同時並行フレームが同時に開始するときにも発生する。
３）単一の演算が開始できる。これは通常、演算（Ｄａ１）の最後で、又は同時並行フレームの演算が終了した（Ｅａ１、図３Ａ）ときにフレームの始まりで起こる。演算は、その実行必要性が、この同時並行フレームと関連付けられた時間マージンが加えられた、次の同時並行フレームの開始まで残っている時間に満たないまたは同じである場合にだけ実行される。例えば、図３Ａでは、演算Ｄａ２は期日Ｅａ１で開始する準備が完了し、フレームＦｂ２の始まり及びＴｂ２＝４まで３単位が残されている。演算Ｄａ２は、Ｄａ２＝４＜３＋４であるため開始される。
【００３１】
それ以外の場合、次の重要な日付が状況を再評価するために待たれる。例えば、図３Ａでは、演算Ｄｂ２は演算Ｄａ２の最後で実行のために準備が完了している。しかしながら、フレームＦａ３の始まり及びＴａ３まで１単位が残されている。したがって、Ｄｂ２＝３＞１＋１である。
【００３２】
互換性基準は、ここでリアルタイムシステム用の順序付け計画で使用される任意の２つの反復シーケンスＲＳＦａ及びＲＳＦｂの間で定められる。
【００３３】
包括的な互換性チェックは、１クロックサイクルの粒度で演算のそのフレームにおける位置、及び互いに対するシーケンスのすべての考えられる位置のすべての考えられる組合せを調べて、同時並行演算を課されている制約に従って実行できるかどうかを評価することを含むだろう。
【００３４】
係る包括的な検証は、妥当な時間内に達成するのは困難だろう。タスクの実行可能コードに伴って順序付け計画をロードするときに、リアルタイムシステムでオンラインで評価できる簡略された基準が求められる。このために、３つの一般的な想定が、他のシーケンスの各フレームに関してシーケンスの内の１つの各フレームの位置決めに関して検討される。想定ごとに、所与のフレームＦａｉの演算がフレームＦａｉに重なる同時並行フレームＦｂｊ、Ｆｂｊ＋１．．．によって残される使用可能なスロットの中で実行できることが検証される。２つのフレームＦａｉ及びＦｂｊは、検証が以下の３つの想定のそれぞれにて満たされるときに互換性があると見なされる。
・想定（Ａ）：所与のフレームＦａｉは、第１の同時並行フレームＦｂｊの演算Ｄｂｊが実行を完了すると、開始する。
・想定（Ｂ）：第１の同時並行フレームの演算は実行中である。
・想定（Ｃ）：同時並行フレームの演算は開始していない。
【００３５】
想定ごとに、フレームの相対位置とは無関係である基準が求められる。このために、一般的にはスロットを見つけて演算を実行するために使用される未知の時間間隔が過小評価され、期日とのコンプライアンスをチェックするために使用される未知の時間間隔は過大評価される。
【００３６】
図４Ａから図４Ｃは、想定（Ａ）に基づいて互換性基準を構成するために使用されてよい例示的なフレームを示す。所与のフレームＦａｉは、同時並行フレームの演算Ｄｂｊが完了すると、この同時並行フレームＦｂｊの間に開始する。フレームＦａｉは次の同時並行フレームＦｂｊ＋１に重なる。フレームＦａｉの始まりについて知られていることすべては、それが演算Ｄｂｊの最後に続く間隔ｑＴｂｊに位置し、０≦ｑ≦１である点である。
【００３７】
図４Ａでは、フレームＦａｉはフレームＦｂｊ＋１の前に終了する。演算Ｄａｊは間隔ｑＴｂｊ＋Ｔｂｊ＋１で演算Ｄｂｊの最後から起動できるだろう。ただし、ｑは未知且つ任意であるので、ｑ＝０で最悪の事態が検討され、それにより演算ＤａｊはフレームＦｂｊ＋１の始まりで開始する。このようにして、演算Ｄａｊは、
Ｄａｉ＜Ｔｂｊ＋１      ［Ａ．１］
の場合に実行できる。
【００３８】
図４Ｂでは、演算Ｄａｊは要件Ａ．１を満たしていない。その結果、フレームＦｂｊ＋１及びＦｂｊ＋２にまたがって演算Ｄａｊを実行することが試される。つまり、フレームＦａｉ
は３つのフレームＦｂｊからＦｂｊ＋２に重なる。これは、間隔Ｔｂｊ＋１及びＴｂｊ＋２の合計が十分であることを保証するための条件と、期日Ｅａｉが満たされることを保証するための条件の両方を満たすことを暗示する。
Ｄａｉ≦Ｔｂｊ＋１＋Ｔｂｊ＋２
ＡＮＤ
ｑＴｂｊ＋Ｄｂｊ＋１＋Ｄａｉ≦Ｄａｉ＋Ｔａｉ、したがってｑＴｂｊ＋Ｄｂｊ＋１≦Ｔａｉ
【００３９】
期日を尊重するための最悪の事態はｑ＝１であり、不等式の左側の数を増加する。したがって、期日Ｅａｉは、すべてのケースで、
Ｔｂｊ＋Ｄｂｊ＋１≦Ｔａｉ
の場合に満たされる。
【００４０】
ただし、同じ変数の２つの極値を使用し、同じコンテキストで最悪の事態の状況を検討することは現実的ではない。事実上、変数ｑの値の一定の範囲は、図４Ａの状況でリアルシステムの動作を検討するときに排除できる。
【００４１】
図４Ｃは、図４Ａの状況でのリアルシステムの動作を示す。いったん演算Ｄｂｊが終了すると、フレームパラメータのオンライン知識を有するシステムが、
Ｄａｉ≦ｑＴｂｊ＋Ｔｂｊ＋１
である限り、つまり、スケジューリング方法の条件３）が満たされる場合、フレームＦａｉの始まりで演算Ｄａｉを起動する。
【００４２】
上記の不等式で等性を達成するためにｑｌをｑの制限値とする。
Ｄａｉ＝ｑｌＴｂｊ＋Ｔｂｊ＋１、したがってｑｌ＝（Ｄａｉ−Ｔｂｊ＋１）／Ｔｂｊ
【００４３】
ｑ≧ｑｌの場合、リアルシステムの実行が図４Ｃに従って起こること、及び図４Ｂの状況が除外されるべきであることは確かである。図４Ｂの最悪の事態は次いでｑ＝ｑｌであり、それによって
ｑｌＴｂｊ＋Ｄｂｊ＋１≦Ｔａｉ、したがってｑｌをその値で置換することによって、
Ｄａｉ−Ｔｂｊ＋１＋Ｄｂｊ＋１≦Ｔａｉ、又はＤａｉ＋Ｄｂｊ＋１≦Ｔａｉ＋Ｔｂｊ＋１
【００４４】
値ｑｌを計算するために使用される式はｌに制限されない。ｑｌが１を超える場合、それは実際的な意味を成さない。したがって、値ｑｌは１で制限される。
【００４５】
図４Ｂの状況から生じる条件は、このようにして
Ｄａｉ≦Ｔｂｊ＋１＋Ｔｂｊ＋２
ＡＮＤ        ［Ａ．２］
ｑｌＴｂｊ＋Ｄｂｊ＋１≦Ｔａｉ
である。
【００４６】
条件Ａ．１は、フレームＦａｉが少なくとも２つの連続フレームＦｂに重なる状況で検証可能である。条件Ａ．２は、フレームＦａｉが少なくとも３つの連続フレームＦｂに重なる状況で検証可能である。同様に、条件Ａ．３及び以下は、フレームＦａｉが少なくとも４つ以上の連続フレームＦｂに重なる状況で検証可能であるが、係る条件を満たす尤度は急速に落ちることが分かってよい。条件Ａ．１及びＡ．２（並びに適用可能な場合、Ａ．３及び以下）は代替である。つまり、これらの条件のいずれか１つが他の想定のバリデーションにジャンプするために満たされることで十分である。
【００４７】
図５Ａ及び図５Ｂは、想定（Ｂ）に基づいて互換性基準を構成するために使用されてよいフレームの例を示す。フレームＦａｉは同時並行フレームＦｂｊの間に開始する。一方、このフレームの同時並行演算Ｄｂｊは継続中である。図示される最悪の事態では、演算Ｄｂｊがちょうど開始する。状況は、持続時間Ｄｂｊが期日Ｅａｉとのコンプライアンスを検証するために考慮される点を除き、図４Ａ及び図４Ｂの状況に類似している。
【００４８】
図５Ａによると、
Ｄａｉ≦Ｔｂｊ＋１であり、期日Ｅａｉを尊重するためには、Ｄｂｊ＋Ｄａｉ≦Ｄａｉ＋Ｔａｉであり、したがって、Ｄｂｊ≦Ｔａｉである。
【００４９】
図４ｂの状況から生じる条件は、このようにして
Ｄａｉ≦Ｔｂｊ＋１
ＡＮＤ        ［Ｂ．１］
Ｄｂｊ≦Ｔａｉ
である。
【００５０】
図５Ｂから、図４Ｂにおいてと同じ論拠に従って、
Ｄａｉ≦Ｔｂｊ＋１＋Ｔｂｊ＋２
ＡＮＤ        ［Ｂ．２］
Ｄｂｊ＋ｑｌＴｂｊ＋Ｄｂｊ＋１≦Ｔａｉ
【００５１】
条件Ａ．１に関して、条件Ｂ．１は、フレームＦａｉが少なくとも２つの連続フレームＦｂに重なる状況で検証可能である。条件Ｂ．２は、フレームＦａｉが少なくとも３つの連続フレームＦｂに重なる状況で検証可能である。同様に、条件Ｂ．３及び以下は、フレームＦａｉが少なくとも４つ以上の連続フレームＦｂに重なる状況で検証可能であるが、係る条件を満たす尤度は急速に落ちることが分かってよい。条件Ｂ．１及びＢ．２（並びに適用可能な場合、Ａ．３及び以下）は代替である。つまり、これらの条件のいずれか１つが他の想定のバリデーションにジャンプするために満たされることで十分である。
【００５２】
図６は、想定（Ｃ）に基づいた互換性基準の構成で使用できる例示的なフレームを示す。想定（Ｃ）との関連で、演算Ｄｂｊがまだ実行されていないことが仮定される。フレームＦａｉの期日がフレームＦｂｊの期日の後に達する場合、図５Ａ及び図５Ｂの状況と同じ状況に遭遇され、演算Ｄｂｊがちょうど開始する。したがって、想定（Ｃ）の下では、フレームＦａｉの期日がフレームＦｂｊの期日の前に発生するケースだけが分析される。
【００５３】
演算Ｄａｉと演算Ｄｂｊの両方とも、フレームＦａｉの始まりでの実行に準備が完了している。演算Ｄａｉ−１がフレームＦａｉの始まりでその期日で終了するときに、例えば図示されるように、スケジューリング条件３）は満たされていないため、演算Ｄｂｊがそのフレームの始まりで開始されていなかったと想定されてよい。期日Ｅａｉは最短であるので、演算Ｄａｉは最初に起動される。演算Ｄｂｊは、演算Ｄａｉの最後に起動される。想定（Ｃ）の範囲内の最悪の事態では、フレームＦａｉ及びＦｂｊの期日は一致し、このことは
Ｄｂｊ≦Ｔａｉ  ［Ｃ．１］
を暗示する。
【００５４】
提供されているスケジューリングプロセスはこのように進行しないだろうが、この同じ不等式は、演算ＤｂｊがフレームＦａｉの始まりで開始すると想定して得られる。演算Ｄａｉがその期日の前に終了するためには、不等式Ｄｂｊ＋Ｄａｉ≦Ｄａｉ＋Ｔａｉが検証される、つまり上記と同じ不等式である。
【００５５】
各フレームＦａｉはこのようにして各フレームＦｂｊに比較され、フレームＦｂｊの期日が満たされていることを検証することはないが、フレームＦａｉの期日が満たされていることを保証する。これが第１の検証合格を形成する。検証を完了するための第２の合格は、次いで各フレームＦｂｊを各フレームＦａｉに比較し、それによってフレームＦｂｊの期日が満たされることを保証することによって上記演算を繰り返すことである。
【００５６】
それぞれＮａフレーム及びＮｂフレームを有する２つの反復シーケンスＲＳＦａ及びＲＳｆｂの互換性の検証は、以下の疑似コードによって要約されてよい。この疑似コードでは、代替条件は不等式の左側で式ｍｉｎ（ｘ，ｙ）に、及び不等式の右側でｍａｘ（ｘ，ｙ）に集約され、必要な条件は不等式の右側の式ｍｉｎ（ｘ，ｙ）に及び不等式の左側のｍａｘ（ｘ，ｙ）に集約される。条件Ａ．３及びＢ．３は、上述されたように、フレームＦａｉが４つのフレームＦｂｊからＦｂｊ＋３に重なるイベントを反映するために提供される。フレームシーケンスは無限に反復可能であるので、インデックスｉ及びｊに対する演算は、インデックスの最大値（ｉの場合Ｎａ、及びｊの場合Ｎｂ）を法として実行される。
【００５７】
０とＮｂ−１の間のｊごとに以下を行う。
０とＮｂ−１の間のｊごとに以下を行う。
［Ａ．１］
Ｄａｉ≦Ｔｂｊ＋１の場合、その結果［Ｂ．１］で続行する。
［Ａ．２］
ｑｌ：＝（Ｄａｉ−Ｔｂｊ＋１)／Ｔｂｊ
ｑｌ＞１又はＴｂｊ＝０の場合、その結果ｑｌ：＝１である
Ｄａｉ≦Ｔｂｊ＋１＋Ｔｂｊ＋２
及びｑｌＴｂｊ＋Ｄｂｊ＋１≦Ｔａｉの場合、
その結果［Ｂ．１］で続行する
［Ａ．３］
Ｄａｉ≦Ｔｂｊ＋２＋Ｔｂｊ＋３
及びｑｌＴｂｊ＋Ｄｂｊ＋１＋Ｄｂｊ＋２＋ｍｉｎ［Ｔｂｊ＋１、Ｄａｉ］≦Ｔａｉの場合、
その結果［Ｂ．１］で続行し、
故障コードをもってループを終了する
［Ｂ．１］
Ｄａｉ≦Ｔｂｊ＋１
及びＤｂｊ≦Ｔａｉの場合、
その結果、［Ｄ］で続行する
［Ｂ．１．１］
ｑｌ：＝（Ｄａｉ‐Ｔｂｊ＋１)／Ｔｂｊ
ｑｌ＞１又はＴｂｊ＝０の場合、その結果ｑｌ：＝１となり、［Ｂ．２］で続行する
Ｔｌ：Ｔａｉ‐１‐（１−ｑｌ）Ｔｂｊ
Ｄｂｊ−１≦ Ｔｌの場合
その結果［Ｃ．１］で続行する
［Ｂ．２］
Ｄａｉ≦Ｔｂｊ＋１＋Ｔｂｊ＋２
及びＤｂｊ＋ｑｌＴｂｊ＋Ｄｂｊ＋１≦Ｔａｉの場合、
その結果［Ｃ．１］で続行する
［Ｂ．３］
Ｄａｉ≦Ｔｂｊ＋２＋Ｔｂｊ＋３
及びＤｂｊ＋ｑｌＴｂｊ＋Ｄｂｊ＋１＋ｍｉｎ[Ｔｂｊ＋１,Ｄａｉ]＋Ｄｂｊ＋２≦Ｔａｉの場合、
その結果［Ｃ．１］で続行し、
故障コードをもってループを終了する
［Ｃ．１］
Ｄｂｊ≦Ｔａｉの場合、
その結果［Ｄ］で続行し、
故障コードをもってループを終了する
［Ｄ］次にｊ
次にｉ
【００５８】
検証を完了するために、上記に示されたように、このループは繰り返され、フレームＦａ及びＦｂを切り替えてよい。
【００５９】
このループでは、上述されたことに関して代替策に従って、条件Ｂ．２の評価を進める前に条件Ｂ．１．１が評価される。
【００６０】
図７は、条件Ｂ．１．１の確立を示すフレームの例示的な連続を示す。フレームＦａｉ及びＦｂｊは図４Ａでのように同じ条件にあるが、フレームＦｂｊ＋１の始まりで演算Ｄａｉを開始する代わりに、演算Ｄａｉは演算Ｄｂｊの直後に開始してよく、ｑ＝ｑｌでこれを可能にする一般的な条件は従前のフレームＦａｉ−１及びＦｂｊ−１で求められると仮定される。条件Ｂ．１．１は、条件Ｂ．１のように、フレームＦａｉが３つのフレーム以上に重なる状況よりも発生する可能性が高い状況に対応して、フレームＦａｉが２個のフレーム（Ｆｂｊ及びＦｂｊ＋１）に重なるという仮定に基づいている。
【００６１】
上記に示されたように、フレームは非リアルタイムタスクを実行するためにシステムが要することがある予備時間Ｒを含んでよい。係る予備時間はリアルタイム演算を実行するために使用されてよい。それは他方のシーケンスの演算Ｄの実行を促進するために一方のシーケンスの時間マージンTを増加させるが、それは期日を満たすための条件を堅牢にすることがある。
【００６２】
非ゼロ予備時間Ｒは特に条件Ｃ．１を緩和してよい。
【００６３】
図８は、条件Ｃ．１が満たさないとき、つまりＤｂｊ＞Ｔａｉのとき、緩和された制約を確立するための例示的なフレームの連続を示す。仮定Ｃの下で演算Ｄｂｊは、フレームＦａｉの始まりでまだ開始していないと想定される。最短の期日を有する演算ＤａｉはフレームＦａｉのまさに始まりで開始される。フレームＦｂｊはフレームＦａｉの前に開始し、それはフレームＦａｉ−１の間隔Ｒａｉ−１の間に想定される。フレームＦｂｊの始まりとフレームＦａｉの始まりとの間の間隔はｋＲａｉ−１と示され、０≦ｋ≦１である。
【００６４】
演算ＤｂｊがそのフレームＦｂｊの始まりで予定されていなかった場合、それは
Ｄｂｊ＞ｋＲａｉ−１＋Ｔａｉ
を意味する。
【００６５】
ｋの限度値はｋｌと示され、したがってＤｂｊ＝ｋｌＲａｉ−１＋Ｔａｉであり、したがってｋｌ＝（Ｄｂｊ−Ｔａｉ）／Ｒａｉ−ｌである。ｋ＞ｋｌの場合、演算ＤｂｊをフレームＦａｉの始まりの前にスケジューリングできることは確実である−このケースは想定Ｃに適合しないため、このケースは検討されるべきではない。０とｋｌの間のｋの値だけが検討される。
【００６６】
演算Ｄａｉが実行可能となるためには、演算Ｄａｉは条件Ｄａｉ≦Ｔｂｊ−ｋＲａｉ−ｌを満たす必要がある。最悪の事態はｋ＝ｋｌであり、それによって
Ｄａｉ≦Ｔｂｊ−ｋｌＲａｉ−ｌ、つまりｋｌをその値で置換すると、
Ｄａｉ≦Ｔｂｊ−（Ｄｂｊ−Ｔａｉ）、又は
Ｄｂｊ≦Ｔａｉ＋Ｔｂｊ−Ｄａｉ
【００６７】
係数ｋｌは最大限でも１に等しく、このことは以下によって表される。
Ｄｂｊ−Ｔａｉ≦Ｒａｉ−１、又は
Ｄｂｊ≦Ｔａｉ＋Ｒａｉ−１
【００６８】
最後に、演算Ｄａｉ＋１の実行を抑制しないために、演算ＤｂｊはフレームＦａｉ＋ｌに重なってはならない。これは、以下の場合に満たされる。
Ｄｂｊ≦Ｔａｉ＋Ｒａｉ
【００６９】
これは以下の条件、つまり条件Ｃ．１の代替策につながる。
Ｄｂｊ≦Ｔａｉ＋Ｔｂｊ−Ｄａｉ
ＡＮＤ
Ｄｂｊ≦Ｔａｉ＋Ｒａｉ−１          ［Ｃ．２］
ＡＮＤ
Ｄｂｊ≦Ｔａｉ＋Ｒａｉ
【００７０】
以下の疑似コードは、予備時間Ｒを考慮に入れる。
【００７１】
０とＮｂ−１の間のｉごとに以下を行う。
０とＮｂ−１の間のｊごとに以下を行う。
［Ａ．１］
Ｄａｉ≦Ｔｂｊ＋１の場合、その結果［Ｂ．１］で続行する
［Ａ．２］
ｑｌ：＝（Ｄａｉ−Ｔｂｊ＋１)／（Ｔｂｊ＋Ｒｂｊ）
ｑｌ＞１  又は  Ｔｂｊ＝０の場合、その結果ｑｌ：＝１である
Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びｑｌ（Ｔｂｊ＋Ｒｂｊ）＋Ｄｂｊ＋１≦Ｔａｉの場合、
その結果［Ｂ．１］で続行する
［Ａ．３］
Ｄａｉ≦Ｔｂｊ＋２＋Ｒｂｊ＋２＋Ｔｂｊ＋３
及びＤｂｊ＋１＋ｑｌ（Ｔｂｊ＋Ｒｂｊ）
＋Ｄｂｊ＋２＋ｍｉｎ［  Ｔｂｊ＋１＋Ｒｂｊ＋１，Ｄａｉ］≦Ｔａｉの場合、
その結果［Ｂ．１］で続行し、
故障コードをもってループを終了する
［Ｂ．１］
Ｄａｉ≦Ｒｂｊ＋Ｔｂｊ＋１
及びＤｂｊ≦Ｔａｉの場合、
その結果、［Ｃ．２］で続行する
ｑｌ：＝（Ｄａｉ‐Ｒｂｊ−Ｔｂｊ＋１)／Ｔｂｊ
ｑｌ＞１  又は  Ｔｂｊ＝０の場合、その結果ｑｌ：＝１となり、［Ｂ．２］で続行する
［Ｂ．１．１］
Ｔｌ：＝Ｔａｉ‐１‐（１−ｑｌ）Ｔｂｊ＋Ｒａｉ‐１
Ｄｂｊ−１≦Ｔｌ＋ｍｉｎ［  Ｔｂｊ−１＋Ｄｂｊ−１＋Ｒｂｊ−１−Ｔｌ−Ｄａｉ−１，Ｒａｉ−２］の場合
その結果［Ｃ．１］で続行する
［Ｂ．１．２］
Ｄｂｊ−１＋Ｒｂｊ−１≦Ｔｌ
及びＤａｉ−１≦Ｔｂｊ−２＋Ｒｂｊ−２＋Ｔｂｊ−１
及びＴｂｊ−２＋Ｄｂｊ−２＋Ｒｂｊ−２＋Ｔｂｊ−１＋Ｄｂｊ−１＋Ｒｂｊ−１≦Ｒａｉ‐２＋Ｔｌ＋Ｄａｉ‐１の場合、
その結果［Ｃ．１］で続行する
［Ｂ．２］
Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びＤｂｊ＋ｑｌＴｂｊ＋Ｒｂｊ＋Ｄｂｊ＋１≦Ｔａｉの場合、
その結果［Ｃ．１］で続行する
［Ｂ．３］
Ｄａｉ≦Ｔｂｊ＋２＋Ｒｂｊ＋２＋Ｔｂｊ＋３
及びＤｂｊ＋ｑｌＴｂｊ＋Ｒｂｊ
＋Ｄｂｊ＋１＋ｍｉｎ[  Ｔｂｊ＋１＋Ｒｂｊ＋１，Ｄａｉ]
＋Ｄｂｊ＋２≦Ｔａｉの場合、
その結果［Ｃ．１］で続行し、
故障コードをもってループを終了する
［Ｃ．１］
Ｄｂｊ≦Ｔａｉの場合、
その結果［Ｄ］で続行する
［Ｃ．２］
Ｄｂｊ≦Ｔａｉ＋ｍｉｎ［  Ｔｂｊ−Ｄａｉ，Ｒａｉ,Ｒａｉ‐１］
その結果［Ｄ］で続行し、
故障コードでループを終了する
［Ｄ］次にｊ
次にｉ
【００７２】
この疑似コードに表示される条件Ｂ．１．２は、フレームＦａｉ−２及びＦｂｊ−２に対する検索を拡大する、条件Ｂ．１．１に関してと同じ方式を使用して決定される。
【００７３】
いままで、２つのタスクを計時するための時間基準は等時性であった、つまりシーケンスの一方の間隔の持続時間が他方のシーケンスの間隔に関して可変ではなかったと仮定されていた。実際には、可変速度で移動する要素の位置にインデックスが付けられたタスクのような相関関係のない時間基準を使用して２つのタスクを構成することが必要となることがある。
【００７４】
このケースを扱うために、変動性係数ｚ＞１が反復シーケンスごとに導入され、ｚａ及びｚｂはそれぞれシーケンスＲＳＦａ及びＲＳＦｂごとに導入される。係数ｚａ及びｚｂは固定され、２つのシーケンスの間隔Ｔ及びＲの最大停止を表す。従前の関係性で使用された表記が間隔の最小値を表すと想定すると、値Ｔ及びＲのそれぞれはこのようにして２つの値Ｔ又はｚＴ及びＲ又はｚＲを推定してよい。実行必要性Ｄは、実行必要性Ｄがシステムクロックだけに依存するため一定のままである。
【００７５】
間隔が演算を実行するためのスロットを見つけるために使用される従前の関係性では、その過小評価された値Ｔ又はＲが維持される。間隔が期日とのコンプライアンスをチェックするために使用されるとき、その過大評価された値ｚＴ又はｚＲが使用される。以下の疑似コードが次いで得られる。
【００７６】
０とＮｂ−１の間のｉごとに以下を行う。
０とＮｂ−１の間のｊごとに以下を行う。
［Ａ．１］
Ｄａｉ≦Ｔｂｊ＋１の場合、その結果［Ｂ．１］で続行する
［Ａ．２］
ｑｌ：＝（Ｄａｉ−Ｔｂｊ＋１)／（Ｔｂｊ＋Ｒｂｊ）
ｑｌ＞１又はＴｂｊ+Ｒｂj＝０の場合、その結果ｑｌ：＝１である
Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びｍｉｎ［ｑｌ（ｚｂ・（Ｔｂｊ＋Ｒｂｊ）＋（ｚｂ−１）Ｄｂｊ），Ｄａｉ］＋Ｄｂｊ＋１≦Ｔａｉの場合、
その結果［Ｂ．１］で続行する
［Ａ．３］
Ｄａｉ≦Ｔｂｊ＋２＋Ｒｂｊ＋２＋Ｔｂｊ＋３
及びＤｂｊ＋１＋ｍｉｎ［  ｑｌ（ｚｂ・（Ｔｂｊ＋Ｒｂｊ）＋（ｚｂ−１）Ｄｂｊ），Ｄａｉ］
＋Ｄｂｊ＋２＋ｍｉｎ［  ｚｂ・（Ｔｂｊ＋１＋Ｒｂｊ＋１）＋（ｚｂ−１）Ｄｂｊ＋１，Ｄａｉ］≦Ｔａｉの場合、
その結果［Ｂ．１］で続行し、
故障コードをもってループを終了する
［Ｂ．１］
Ｄａｉ≦Ｒｂｊ＋Ｔｂｊ＋１
及びＤｂｊ≦Ｔａｉの場合、
その結果、［Ｃ．２］で続行する
［Ｂ．１．１］
ｑｌ：＝（Ｄａｉ‐Ｒｂｊ−Ｔｂｊ＋１)／Ｔｂｊ
ｑｌ＞１又はＴｂｊ＝０の場合、その結果ｑｌ：＝１となり、［Ｂ．２］で続行する
Ｔｌ：＝Ｔａｉ‐１‐（１−ｑｌ）Ｔｂｊ＋Ｒａｉ‐１
Ｄｂｊ−１≦Ｔｌ＋ｍｉｎ［  Ｔｂｊ−１＋Ｄｂｊ−１＋Ｒｂｊ−１‐Ｔｌ−Ｄａｉ−１，Ｒａｉ−２］の場合
その結果［Ｃ．１］で続行する
［Ｂ．１．２］
Ｄｂｉ−１＋ｚｂ・Ｒｂｊ−１≦Ｔｌ
及びＤａｉ−１≦Ｔｂｊ−２＋Ｒｂｊ−２＋Ｔｂｊ−１
及びｚｂ・（Ｔｂｊ−２＋Ｄｂｊ−２＋Ｒｂｊ−２＋Ｔｂｊ−１＋Ｄｂｊ−１＋Ｒｂｊ−１）≦Ｒａｉ‐２＋Ｔｌ＋Ｄａｉ‐１の場合、
その結果［Ｃ．１］で続行する
［Ｂ．２］
Ｄａｉ≦Ｔｂｊ＋１＋Ｒｂｊ＋１＋Ｔｂｊ＋２
及びＤｂｊ＋ｍｉｎ［  ｑｌ（ｚｂ・Ｔｂｊ＋（ｚｂ−１）Ｄｂｊ）＋ｚｂ・Ｒｂｊ，Ｄａｉ］
＋Ｄｂｊ＋１≦Ｔａｉの場合、
その結果［Ｃ．１］で続行する
［Ｂ．３］
Ｄａｉ≦Ｔｂｊ＋２＋Ｒｂｊ＋２＋Ｔｂｊ＋３
及びＤｂｊ＋ｍｉｎ［  ｑｌ（ｚｂ・Ｔｂｊ＋（ｚｂ−１）Ｄｂｊ）＋ｚｂ・Ｒｂｊ，Ｄａｉ］
＋Ｄｂｊ＋１＋ｍｉｎ[  ｚｂ・（Ｔｂｊ＋１＋Ｒｂｊ＋１）＋（ｚｂ−１）Ｄｂｊ＋１，Ｄａｉ]
＋Ｄｂｊ＋２≦Ｔａｉの場合、
その結果［Ｃ．１］で続行し、
故障コードをもってループを終了する
［Ｃ．１］
Ｄｂｊ≦Ｔａｉの場合、
その結果［Ｄ］で続行する
［Ｃ．２］
Ｄｂｊ≦Ｔａｉ＋ｍｉｎ［  Ｔｂｊ−Ｄａｉ，Ｒａｉ，Ｒａｉ‐１］
その結果［Ｄ］で続行し、
故障コードでループを終了する
［Ｄ］次にｊ
次にｉ
【００７７】
上述されたスケジューリングプロセスのケース３）では、検討する時間のマージンは最低値、つまりＴであり、ｚＴではない。
【００７８】
上記に提示された原理は時分割で実行するための２つのタスクを用いて説明されてきたが、原理は任意の数のタスクに適用する。確かに、説明された方法は２つの互換性のあるタスクに単一の順序付け計画を構成することを実際的に可能にする。このようにして得られた順序付け計画は第３の互換性のあるタスク用の順序付け計画等を用いて、同じ技法を使用し、再び構成されてよい。
【図１】
0006441349.tif 000002
【図２】
0006441349.tif 000003
【図３Ａ】
0006441349.tif 000004
【図３Ｂ】
0006441349.tif 000005
【図３Ｃ】
0006441349.tif 000006
【図４Ａ】
0006441349.tif 000007
【図４Ｂ】
0006441349.tif 000008
【図４Ｃ】
0006441349.tif 000009
【図５Ａ】
0006441349.tif 000010
【図５Ｂ】
0006441349.tif 000011
【図６】
0006441349.tif 000012
【図７】
0006441349.tif 000013
【図８】
0006441349.tif 000014