(57)【要約】本発明は第一周期的タスクのベストケース反応時間を決定する方法に関する。この方法は、速度単調分析に基づいたシステムにおいてスケジュールすべきタスクの優先順位を決定する第一ステップを含む。この１セットのタスクがシステムにおいてスケジュール可能かどうかを決定するために、ベストケース反応時間とワーストケース反応時間が、タスクごとに決定される。ベストケース反応時間は、優先順位の低いタスクの開始時（１０２）とこの優先順位の低いタスクの終了時（１０４）の間の期間と実質的に等しい。この開始時は、この優先順位の低いタスクの解放の直後であり、この終了時は、すべての優先順位のより高いタスクの同時の解放時（１０４）に一致する。
2004513454.tif 000002
【特許請求の範囲】
【請求項１】
第一周期的タスクのベストケース反応時間を決定する方法であって：
上記第一周期的タスクが第二周期的タスクよりも低い優先順位を持っていることを決定する第一ステップ；および
上記第一周期的タスクの上記ベストケース反応時間が、上記第一周期的タスクの開始時と上記第一周期的タスクの終了時との間の期間に実質的に等しいことを決定する第二ステップを含み、上記開始時が上記第一周期的タスクの解放直後であり、上記終了時が上記第二周期的タスクの解放と一致することを特徴とする方法。
【請求項２】
上記第一周期的タスクの上記ベストケース反応時間を示すＢＲｉが、次の式を満足する最も大きい値に実質的に等しく、
【数１】
2004513454.tif 000016
ＢＣｉは上記第一周期的タスクτｉのベストコンピュータ処理時間を示し、ｈｐ（ｉ）は上記第一周期的タスクの低い優先順位よりも優先順位の高い１セットのタスクを示し、Ｔｊはｈｐ（ｉ）のタスクτｊの作動の周期を示すことを特徴とする請求項１に記載の方法。
【請求項３】
ＷＲｉが上記第一周期的タスクτｉのワーストケース反応時間を示し、上記ベストケース反応時間ＢＲｉはｋによる反復の繰り返し手順によって次の式から得られ、
【数２】
2004513454.tif 000017
ｋ＝０，１・・・であり、上記繰り返し手順は、連続する２つのｋに関して同一の値が得られたとき、終了することを特徴とする請求項２に記載の方法。
【請求項４】
上記第一周期的タスクの上記ワーストケース反応時間が、上記第一周期的タスクのワーストケースコンピュータ処理時間に基づいていることを特徴とする請求項３に記載の方法。
【請求項５】
上記第一周期的タスクの上記ワーストケース反応時間が、上記第一周期的タスクのベストケースコンピュータ処理時間に基づいていることを特徴とする請求項３に記載の方法。
【請求項６】
ＲＪｉが上記第一周期的タスクτｉの解放ジターを示し、上記解放ジターは上記第一周期的タスクの解放時の変化であり、上記解放ジターは上記ベストケース反応時間に以下の式のように負の作用を及ぼし、
【数３】
2004513454.tif 000018
ｘ＋は、０とｘの内大きいほうを表わす。
【請求項７】
第一周期的タスクのベストケース反応時間を決定するシステムであって：
上記第一周期的タスクの優先順位が第二周期的タスクの優先順位より低いことを決定する決定手段；および
上記第一周期的タスクの上記ベストケース反応時間が、上記第一周期的タスクの開始時と上記第一周期的タスクの終了時との間の期間に実質的に等しいことを決定するための反応時間手段を含み、上記開始時は上記第一周期的タスクの解放直後であり、上記終了時は上記第一周期的タスクの上記第二周期的タスクの解放と一致することを特徴とするシステム。
【請求項８】
上記システムは、次の式に従ってＢＲｉで示されたベストケース反応時間を計算するための第一計算手段をさらに含み、
【数４】
2004513454.tif 000019
ＢＣｉは上記第一周期的タスクτｉのベストケースコンピュータ処理時間を示し、ｈｐ（ｉ）は上記第一周期的タスクよりも高い優先順位を持つ１セットのタスクを示し、Ｔｊはｈｐ（ｉ）のタスクの作動の周期を示し、ＢＲｉは上記第一周期的タスクの上記ベストケース反応時間を示すことを特徴とする請求項７に記載のシステム。
【請求項９】
上記システムは、次の式によるｋによる反復の繰り返し手順に従ってＢＲｉによって示される上記ベストケース反応時間を計算するための第二計算手段をさらに含み、
【数５】
2004513454.tif 000020
ｋ＝０，１・・・であり、ＷＲｉは上記第一周期的タスクτｉのワーストケース反応時間を示し、上記繰り返し手順は、連続する２つのｋに関して同一の値が得られた時に、終了することを特徴とする請求項８に記載のシステム。
【請求項１０】
上記システムは、次の式に従ってＢＲｉで示されるベストケース反応時間を解放ジターに関して補正して計算する第三計算手段をさらに含み、
【数６】
2004513454.tif 000021
上記解放ジターは上記第一周期的タスクの解放時の変動であり、ＲＪｉは上記第一周期的タスクτｉの上記解放ジターを示し、ｘ＋は、０とｘの内大きいほうを示すことを特徴とする請求項７に記載のシステム。
【請求項１１】
請求項１乃至６の何れかの請求項に記載の方法を実行するためのコンピュータプログラム製品。
【請求項１２】
請求項１１に記載のコンピュータプログラム製品を有する記憶装置。
【請求項１３】
請求項７乃至１０の何れかの請求項に記載のシステムを有するテレビセット。
【請求項１４】
請求項７乃至１０の何れかの請求項に記載のシステムを有するセットトップボックス。
【発明の詳細な説明】
【０００１】
（発明の属する技術分野）
本発明は、第一周期的タスクのベストケース反応時間を決定する方法に関する。この方法は、第一周期的タスクの優先順位が第二周期的タスクの優先順位よりも低いことを決定するステップを含む。
【０００２】
また、本発明は、第一周期的タスクのベストケース反応時間を決定するシステムに関する。このシステムは、第一周期的タスクの優先順位が第二周期的タスクの優先順位よりも低いことを決定・判断する決定手段を含む。
【０００３】
また、本発明は、第一周期的タスクのベストケース反応時間を決定する上記方法のためのコンピュータプログラム製品に関する。
【０００４】
さらに、本発明は、記憶装置・記憶媒体や、テレビセットや、セットトップボックスに関する。
【０００５】
（従来の技術、発明が解決しようとする課題および課題を解決するための手段）
上述の方法とシステムの１つの実施形態は、記事「分配ハードリアルタイムシステムのワーストケーススケジュールテストを改善するベストケース分析」（会報、リアルタイムシステムについての第１０回ユーロマイクロワークショップ、ベルリン、１９９８年、３５から４４ページ）から理解される。ここでは、速度単調分析（ＲＭＡ）に基づいたベストケース分析技術が開示されている。ＲＭＡは、定められた優先順位のタスクが予定されるリアルタイムソフトウエアシステムのタイミング動作を特定し、理解し、分析し、予測する数学的技術である。この開示されているベストケース分析技術は、システム内の異なるタスクのベストケース反応時間の下限に基づいている。下限は、２つの方法によって見積もることができる。第一の方法では、優先順位とより高いタスクによる優先順位のより低いタスクへの占有・妨害が、考慮されない。第二の方法は、より高い優先順位による占有効果のいくつかを考慮する反復方法である。これらの方法では、優先順位のより低いタスクは、優先順位のより高いタスクの実行の終了の直後に作動されると仮定する。
【０００６】
本発明の目的は、タスクのベストケース反応時間のより厳密な下限を得るための方法を提供することである。
【０００７】
この目的を達成するために、本発明の方法は、第一周期的タスクのベストケース反応時間が、第一周期的タスクの開始時と第一周期的タスクの終了時との間の期間に実質的に等しいことを決定する第二ステップを含む。第一周期的タスクの開始時は第一周期的タスクの解放の直後であり、第一周期的タスクの終了時は、第二周期的タスクの解放時に一致する。ベストケース反応時間を決定するためのこの最適な瞬間を使用して、第二周期的タスクのような優先順位のより高いタスクによって第一周期的タスクが占有される回数を最小限にできる。さらに、第一周期的タスクの実行時間を最小にすることが可能である。ベストケース反応時間は、分配システム（ｄｉｓｔｒｉｂｕｔｅｄ　ｓｙｓｔｅｍｓ）において使用できる。この分配システムでは、あるシステムまたはプロセッサで実行されている。引き起こしタスクの出力は、別のシステムまたは別のプロセッサで実行される他の次のタスクの入力とされる。この引き起こしタスクの終了時におけるジター、即ち、時間変動は、次のタスクの解放ジターを引き起こす。従って、順に、この次のタスクによって引き起こされる別のタスクのワーストケース反応時間への影響が生じる。それゆえに、最適な瞬間によって、システムの資源利用・手段利用の改善が可能になる。タスクは、リアルタイムシステムまたは分配リアルシステムの資源・手段を利用し、このようなリアルタイム資源・手段は有限であるので、タスクの中でスケジュール可能タスクの数は、ワーストケース反応時間とベストケース反応時間によって決定される。タスクのワーストケース反応時間またはベストケース反応時間が、そのタスクのデッドラインを超えた場合、そのタスクのスケジュールを組むことはできない。スケジュールを組めないタスクは、システムの資源・手段を使用しないので、結果としてシステムの資源・手段の利用量が減らされる。
【０００８】
タスクのベストケース反応時間のより厳密な下限を得るための方法とシステムの他の実施形態は、分配リアルタスクのスケジュール組み込み可能性分析を改善するためのベストケース反応時間分析（会報、分配リアルタイムシステムについてのＩＣＤＣＳのワークショップ、２０００年、Ｂ１４からＢ２０ページ）。ここには、ＲＭＡに基づいたベスト反応時間分析方法が開示されている。ベストケースでの相対フェーズ・段階を考慮する開示された分析方法によって、タスクのベストケース反応時間の下限が得られる。タスクが、優先順位のより高いタスクによって占有される量・回数が最も少なく、このタスクの実行時間が最小である場合に、このタスクのベストケース反応時間となる。優先順位のより高いタスクによって占有される量・回数が最も少ないタスクは、ベストケースの場合、優先順位のより高いタスクの実行の終了直後に作動されるべきであり、優先順位のより高いタスクの次の作動ができるだけ遅く起こるべきである。優先順位の低いタスクと優先順位の高いタスクの相対的フェーズは、優先順位の低いタスクの作動時間に対する優先順位の高いタスクの次の作動時間によって定義される。しかしながら、得られるベストケース反応時間の下限は厳密ではない。
【０００９】
本発明に従った方法の１つの実施形態は請求項２に記載されている。タスクの内で優先順位のより高いタスクのベストケースコンピュータ処理時間と、この優先順位のより高いタスクによって占有される回数との積を使用することによって、優先順位の低いタスクのベストケース反応時間が決定できる。
【００１０】
本発明に従った方法の１つの実施形態は請求項３に記載されている。ここでは繰り返し手順が使用される。繰り返し手順では、各繰り返しの結果得られる値は、大きくても前回の繰り返しで得られた値と等しく、ＢＲｉ（ｋ＋１）がＢＲｉ（ｋ）と実質的に等しくなったとき、この手順が終了させられる。この手順によって、ＢＲｉ（ｋ＋１）の値が、第一周期的タスクのベストケース反応時間を求めるのに使用される。
【００１１】
本発明に従った方法の１つの実施形態は請求項４に記載されている。第一周期的タスクのワーストケースコンピュータ処理時間を第一周期的タスクのワーストケース反応時間の基礎として使用することによって、ベストケース反応時間の上限が得られる。この上限は、繰り返し手順の初期値として使用できる。
【００１２】
本発明に従った方法の１つの実施形態は請求項５に記載されている。第一周期的タスクのベストケースコンピュータ処理時間を第一周期的タスクのワーストケース反応時間の基礎として使用することによって、ベストケース反応時間の上限が得られる。この上限は、繰り返し手順の初期値として使用できる。
【００１３】
本発明に従った方法の１つの実施形態は請求項６に記載されている。第一周期的タスクのベストケース反応時間を決定するのに第一周期的タスクの解放ジターを考慮することによって、１セットのスケジュール可能なタスクがより効率よく決定でき、結果として、システムの資源の利用量が改善される。
【００１４】
本発明のさらなる目的は、タスクのベストケース反応時間のより厳密な下限を得るためのシステムを提供することである。この目的を達成するために、このシステムは本発明に従って第一周期的タスクのベストケース反応時間を決定する。このシステムは、第一周期的タスクのベストケース反応時間が、第一周期的タスクの開始時と第一周期的タスクの終了時との間の期間であることを決定する反応時間手段を有している。この開始時は第一周期的タスクの解放の直後であり、この終了時は第二周期的タスクの解放時に一致する。
【００１５】
本発明に従ったシステムの実施形態は請求項８から１０に記載されている。
【００１６】
本発明に従った記憶装置・記憶媒体や、テレビセットや、セットトップボックスはそれぞれ請求項１２、１３、１４に記載されている。
【００１７】
（発明の実施の形態）
本発明は添付の図面に図示された実施形態を用いて以下で説明される。
【００１８】
今日、音声や映像に要求されているような連続的なマスメディア処理は、次第にいくつかの部分で単一の機能しか持たないものに実行されるよりもむしろプログラム可能な部分によって実行されるようになってきている。リアルタイムコンピュータ処理システムにおける主な実行問題の１つは、映像フレーム処理のような１セットの周期的タスクを、速度単調分析（Ｒａｔｅ　Ｍｏｎｏｔｏｎｉｃ　Ａｎａｌｙｓｉｓ（ＲＭＡ））のような指定優先プリエンプティブスケジュール（ｆｉｘｅｄ−ｐｒｉｏｒｉｔｙ　ｐｒｅｅｍｐｔｉｖｅ　ｓｃｈｅｄｕｌｉｎｇ）を使用してデットラインを超えることなくＣＰＵなどの手段で実行できるかどうかを決定することである。ＲＭＡは、エンジニアがリアルタイムソフトウエアシステムのタイミング動作を特定し、分析し、予測することを可能にする方法とアルゴリズムの集りである。ＲＭＡ計算で使用されるいくつかの要素は、タスクの反応時間のワーストケース分析とタスクの実行と関連した優先レベルを含んでいる。任意の段階における反応時間のワーストケース分析は以下のように行われる。１セットのｎ個のタスクτ１，τ２，・・・τｎが与えられ、各タスクτｉの作動周期がＴｉであり、各タスクτｉのワーストケースコンピュータ処理時間がＷＣｉであるとすると、タスクτｉのワーストケース反応時間ＷＲｉが次の帰納的数式を満足する最小の正の値で与えられる。
【００１９】
【数７】
2004513454.tif 000003
ここでｈｐ（ｉ）はτｉより優先されるタスクのセットを表わしている。次の反復・繰り返し手順はこのワーストケース反応時間を計算するのに使用可能である。
【００２０】
【数８】
2004513454.tif 000004
ここでｋ＝０，１，・・・である。２つの連続するｋに関して同じ値が得られると、即ち、ＷＲｉ（ｋ＋１）＝ＷＲｉ（ｋ）であると、手順は停止となる。これらの反応時間が与えられ、各タスクのワーストケース反応時間がデッドラインを終えない場合、この与えられた１セットのタスクがＣＰＵなどの手段によって実行される。各タスクのデッドラインが、各タスクの周期と等しいと仮定する。（反応時間が）タスクのデッドラインを超えたとき、手順は停止させられる。しかしながら、あるタスクが分配マルチプロセッサシステムにおいて次のタスクを引き起こすと、その後、ジター（ｊｉｔｔｅｒ）やこれを引き起こしたタスクの終了時に変動が起こり結果として、次のタスクでジターが発生することになり、他のタスクのワーストケース反応時間に影響を及ぼすことになる。このジターは、タスクをパイプラインとして構成する場合にも起こる。パイプラインでは、あるタスクの出力が、次のタスクの入力とされる。ジターをできるだけ制限するために、ジターを引き起こすタスクのワーストケース反応時間とベストケース反応時間を決定する必要がある。
【００２１】
図１は、タスクτｉの最適の瞬間を表わしている。最適の瞬間１０４は、ベストケース反応時間でのタスクτｉの実行を示している。これは、タスクτｉ，τｊ，τｋの解放時間の段階が、タスクτｉの実行がこのタスクτｉが解放されるとすぐに始まり、タスクτｉの終了が優先順位の高いタスクτｊとτｋと両方の同時の解放と一致するような場合である。図１において、符号１０２はタスクのベストケース反応時間に従ったタスクτｉの解放時間であり、符号１０８はタスクτｊの解放時間であり、符号１０６はタスクτｋの解放時間であり、符号１０４は優先順位の高いタスクτｊとτｋの両方の解放時間でありタスクτｉの終了と一致する。解放時間は、矢印↓によって示されている。これは、次のように理解される。ベストケース反応時間での実行が解放されるとすぐに始まらないとき、解放が右に移動し、考慮される実行の反応時間を減少させる。このように、タスクτｉは、解放されると同時に始まる。さらに、ベストケース反応時間でタスクτｉが実行されるが、これの終了時にすべての優先順位の高いタスクが解放されるわけではない場合、考慮されているタスクτｉの実行の反応時間を増加させることなく段階・フェーズをわずかに変更することができる。そのような状況を考えると、図２に図示されるように、優先順位の高いタスクτｊの符号２０４によって示される解放時間は、考慮中のタスクτｉの実行の終了時間２０６と一致しない。時間２０６の直前ではタスクτｉが実行されているので、時間２０６と２０４との間ではτｊは作動されない。このようにならない場合では、時間２０６の直前でより優先順位の高いタスクが待ち構えている。タスクτｊの解放時間が左に２０４と２０６の区間の量だけ移動した場合、タスクτｉの実行にかかる時間・期間である２０２と２０６との間にはさらにこれを占有するものは右側から移動されてこない。他方、タスクτｊの解放時間を左に移動させることによって、この期間におけるタスクτｊによる占有を左側に移動させることになってよい。結果として、他のタスクτｋとタスクτｊによる期間２０２と２０６との間における占有量は、減少するか同じままである。タスクτｊによって優先される量によって同じ量だけ減らすことになる。ベストケース反応時間でのタスクτｉの実行が考慮されたので、後のほうの部分が占有されずに、考慮されているタスクτｉがベストケース反応時間で実行される。上述したように、すべての優先順位の高いタスクの解放が左に移動させられ、最適な瞬間が得られる。この結果として、これらの臨界瞬間の直後に、高い優先順位のタスクが最も集中的に実行され、これらの臨界瞬間の直前では、実行されるタスクが最もまばらになっている。
【００２２】
ベストケース反応時間の帰納的数式は、タスクτｉの最適な瞬間からの時間を遡ることによって得られる。タスクτｉのベストケース反応時間ＢＲｉは次の式を満足する最も大きい値として得られる。
【００２３】
【数９】
2004513454.tif 000005
ここでＢＣｊはタスクτｊのベストケースコンピュータ処理時間を示しており、ｈｐ（ｉ）はタスクτｉより優先順位の高い１セットのタスクを表わしている。ベストケース反応時間は、次の反復・繰り返し手順によって得られる。２つの連続するｋに関して値が同じになると、この繰り返し手順は停止させられる。
【００２４】
【数１０】
2004513454.tif 000006
これは、図３によって確かめられる。図３において、タスクτｉの最適な瞬間を考慮して、より優先順位の高いタスクτｊがタスクτｉ（の期間）を占めることが考慮される。タスクτｉはこれの解放時間３０２の直後に実行されているので、期間３０２と３０６との間ではタスクτｊは作動されない。このようにならない場合では、時間３０２においてより優先順位の高いタスクが起こる。結果として、時間３０２の後にタスクτｊの解放、即ち、３０６と３０４との間の期間における解放が、タスクτｉの実行を占有する。これらの占有の回数は次式で与えられる。
【００２５】
【数１１】
2004513454.tif 000007
これらの各々は寄与ＢＣｊをタスクτｉのベスト反応時間に与えて、結果として帰納的数式（１）になる。ベストケース反応時間の最も厳密な下限を得るために、この数式を満足する最も大きな値がとられる。次に、タスクτｉのベストケース反応時間の上限ＢＲｉ（ｋ）を得て、ＢＲｉ（０）＝ＷＲｉであり、次に
【００２６】
【数１２】
2004513454.tif 000008
がタスクτｊによってタスクτｉにおいて占められる数の上限を与える。（３）で与えられたような上限ＢＲｉ（ｋ＋１）は、ＢＲｉの次の上限を与える。ＢＲｉ（ｋ＋１）は最も大きい場合、前回の上限に等しい。終了すると、即ち、ＢＲｉ（ｋ＋１）＝ＢＲｉ（ｋ）になると、図３において３０２と３０４との間の期間においてより高い優先順位のタスクによって占められない時間・部分が、ベストケースコンピュータ処理時間ＢＣｉにとって十分である。このことは、３０２と３０４との間の期間における最初の部分と最後の部分でタスクτｉが実行されていることと、ベストケース反応時間が得られた値よりも小さくならないことを示している。
【００２７】
よりよい初期値を（２）において得るために、ワーストケースコンピュータ処理時間に基づいたワーストケース反応時間を、ベストケースコンピュータ処理時間に基づいたワーストケース反応時間に置き換えることができる。
【００２８】
図４は、テーブル１で与えられた例に従ってタスクτ３のベストケース反応時間を決定するための反復・繰り返しを示している。このテーブルにおいて、タスクは優先順位の高い順に与えられている。
【００２９】
【表１】
2004513454.tif 000009
この例では、ベストケースコンピュータ処理時間がワーストケースコンピュータ処理時間と等しく、図４において、分かりやすいように符号がつけられている。図４に図示されるように、符号４０２によって示される初期上限ＢＲ３（０）＝５６は、タスクτ１の実行周期１とタスクτ２の実行周期１の内にある。結果として、これらの実行はタスクτ３の実行を占有しないので、多くともタスクτ１の実行２から６とタスクτ２の実行２と３がタスクτ３の実行を占有し、結果として次の新たな上限が得られる。
【００３０】
【数１３】
2004513454.tif 000010
次に、繰り返し（ｉｉ）において、タスクτ１の実行２はタスクτ３の実行を占有しないので、多くともタスクτ１の実行３から６とタスクτ２の実行２と３がタスクτ３を占有する。結果として、新たな上限は、ＢＲ３（２）＝５＋４＊３＋２＊１１＝３９となる。これは、繰り返し（ｉｖ）まで続く。ここで、タスクτ１の実行５、６とタスクτ２の実行３は、タスクτ３のベストケースの実行を占有して結果としてＢＲ３（６）＝５＋２＊３＋１＊１１＝２２＝ＢＲ３（５）となり、繰り返しが停止させられる。ベストケース反応時間が２２であり、これの実行と占有が図５に図示されている。ここで時間５０２はタスクτ３の解放と実行開始を示しており、時間５０４は、タスクτ３の実行終了時間を示している。時間５０２と時間５０４との間の期間は、ベストケース反応時間の２２である。
【００３１】
示されるように、ベストケース実行時間はより高い優先順位のタスクによる占有を含む。さらに、いくつかの優先順位の高いタスクの実行は、さらに高い優先順位のタスクによって延期させられる。ベストケース反応時間の上限から徐々に減らされた時間で開始することは上述した例で起こっており、占有によって引き起こされた占有が含まれている。
タスクτｉのワーストケース反応時間とベストケース反応時間が与えられると、タスクτｉの終了ジターＣＪｉ、即ち、厳密な周期パターンと比較した場合における周期Ｔｉに関する実行終了時の変動の計算が可能である。即ち、次式で得られる。
ＣＪｉ＝ＷＲｉ−ＢＲｉ
終了ジターに関して、ベストケース反応時間を持つタスクの実行の直後にワーストケース反応時間を持つタスクが続く状況またはその逆の状況がありえる。これの例は図６で与えられており、２つのタスクτ１とτ２があり、τ１はτ２よりも優先される。また，周期Ｔ１＝８，周期Ｔ２＝１２，コンピュータ処理時間ＷＣ１＝ＢＣ１＝ＷＣ２＝ＢＣ２＝４である。この例に関しては、タスクτ２のベストケース反応時間とワーストケース反応時間は、それぞれＢＲ２＝時間６０２−時間６０６＝４とＷＲ２＝時間６０８−時間６１０＝８である。さらに、図６では互いの直後に終了ジターが起こっていることを図示している。タスクτ２の終了ジターは、ＣＪ２＝ＷＲ２−ＢＲ２＝８−４＝４に等しい。図６において、時間６０２と６０４はτ２の最適な瞬間を示している。
【００３２】
解放ジターに関しては、ワーストケース反応時間が以下のように得られる。図６において、時間６１０は、臨界瞬間を示している。この臨界瞬間時において、優先順位がより高いタスクτ１の周期の開始時が優先順位の低い方のタスクτ２の周期の開始時と一致している。優先順位のより高いタスクτｊのジターが臨界瞬間での解放と次の解放との間で起こる可能性があり、最初の２回の解放の間の時間はＴｊ−ＲＪｊに等しい時間になる。長さがｔである期間にわたるワーストケースの占有の回数を考えることは、あたかも長さがｔ＋ＲＪｊの期間にわたって占有が厳密に周期的であるようにタスクτｊの占有を考えることに似ている。結果として、ワーストケース反応時間は次のように計算される。
【００３３】
【数１４】
2004513454.tif 000011
ここで、ｋ＝０，１・・・である。
ベストケース反応時間の分析に及ぼされる解放ジターの影響は以下で説明される。ここで優先順位のより高いタスクτｊのジターが最適の瞬間での解放と前回の解放の間で起こる可能性を考える。これらの２つの解放の間の期間は、Ｔｊ＋ＲＪｉになる。次に長さｔの期間にわたるタスクτｊのベストケースの占有の回数を決定することは、あたかも長さがｔ−ＲＪｊである期間にわたって占有が厳密に周期的であるようにタスクτｊの占有を考えることに似ている。結果として、ベストケース反応時間は次のように計算される。
【００３４】
【数１５】
2004513454.tif 000012
ここで、ｋ＝０，１・・・である。表記ｘ＋は、０とｘの内大きいほうを表わしている。即ち、ｍａｘ［０，ｘ］を表わしており、これによって占有の回数は負にならない。
【００３５】
タスクτｉのワーストケース反応時間とベストケース反応時間とこれの解放ジターが与えられると、終了ジターＣＪｉは次式によって与えられる。
ＣＪｉ＝ＲＪｉ＋ＷＲｉ−ＢＲｉ　（４）
図７は、タスクに依存する分配マルチプロセッサシステムにおいてジターの影響を考慮する本発明の主なステップを示している。ここで、タスクの終了は、次のタスクの解放を引き起こしてよい。ステップ７０２において、すべてのタスクτｉの優先順位が決定され、その後、ステップ７０４において、すべてのタスクの解放ジターが０に設定される。即ち、ＲＪｊ＝０である。ステップ７０６において、この解放ジターを考慮してベストケース反応時間とワーストケース反応時間が、タスクが実行される各プロセッサに関してかつすべてのタスクに関して計算される。ステップ７０８において、各タスクの終了ジターが式（４）で与えられるように計算される。次に、ステップ７１０において、別のタスクによって引き起こされた各タスクの解放ジターを、この解放ジターを引き起こすタスクの終了ジターと等しくして更新する。すべてのタスクの更新された解放ジターは、その後再びステップ７０６においてベストケース反応時間とワーストケース反応時間を計算するのに使用される。ステップ７１２において、ベストケース反応時間とワーストケース反応時間が変化していないかどうか、またはこれらの反応時間がタスクのデッドラインを超えてるどうかが判断される。どちらかの停止基準が有効であれば、終了ステップ７１４へ進む。どちらの停止基準も有効でない場合、ステップ７０８へ進みこの方法が続けられる。上述の方法において、ジターとワーストケース反応時間が増加し、ベストケース反応時間が減少して再びジターを増加させるので、最終的にはこの方法は終了させられる。さらに、このことは、もし解放ジターの新たな見積もりに関してワーストケース反応時間とベストケース反応時間を再決定するならば、前回の反復で得られた最終値を初期値設定に使用できる。
【００３６】
本発明の方法の上述した実施形態の順番は限定的なものではなく、本発明によって意図されているような本発明の概念から逸脱せずに連続的接続方式（ｔｈｒｅａｄｉｎｇ　ｍｏｄｅｌｓ）、マルチプロセッサシステム、または複数の処理を同時に使用してステップの順序を変更したり、ステップを実行することが当業者によって可能である。
【００３７】
図８は、本発明に従ったシステムの実施形態の最も重要な部分を大まかに示している。システム８００は、第一コンピュータ読み取り可能コードが組み込まれた第一メモリ８０２を有している。第一メモリ８０２は、次の数式に従ってタスクτｉのベストケース反応時間ＢＲｉを計算する。
【００３８】
【数１６】
2004513454.tif 000013
ここで、ＢＣｉは、一定期間にわたるタスクτｉのベストケース反応時間を示す。ｈｐ（ｉ）は、タスクτｉよりも優先順位の高い１セットのタスクを示している。各タスクの優先順位と、各タスクを実行するプロセッサと、各タスクが使用するデータ・手段・資源がルックアップテーブル８０８に記憶される・含まれる。タスクは、分配システムで実行されてもよい。これは、例えば、画像を提示するマルチメディア端末が使用される場合であり、集中的なコンピュータ処理電力を必要とする処理はサーバで実行され、処理量がより少ない処理がマルチメディア端末で実行される。手段・資源（ｒｅｓｏｕｒｃｅ）は、ＣＰＵクロックサイクルや、ディスクドライブや、ネットワーク帯域幅や、メモリなどである。第二コンピュータ読み取り可能コードが組み込まれた第二メモリ８０４は、次の反復数式に従って上述したベストケース反応時間ＢＲｉを計算する。
【００３９】
【数１７】
2004513454.tif 000014
ここで、ｋ＝０，１・・・である。この計算は、このシステムで予定されるべき各タスクに関して実行される。タスクは、例えば、画像フレームを復号したり、復号されたフレームの画質を向上させるタスクであってよい。アプリケーションやタスクの優先順位は、見る人やアプリケーションの緊急性に依存する。眠っている赤ん坊をモニターするテレビスクリーンの隅における画像ウインドーは、その両親が見たい映画を表示する画像ウインドーよりも優先順位が低い。しかしながら、眠っている赤ん坊の心拍に異常がみられた場合、赤ん坊の画像ウインドーのほうが、映画を表示する画像ウインドーよりも優先順位が高くなる。１セットのタスクがシステム８００に予定できるかどうかを決定するために、上述したようなベストケース反応時間とワーストケース反応時間の両方を計算する必要がある。どのタスクもデットラインを超えない場合、この１セットのタスクの予定を組むことが可能になり、システムで実行される。タスクの終了が次のタスクの解放を引き起こすので、タスクはお互いに依存し合うパイプラインアーキテクチャーの場合、タスクの実行の終了時間の変化・変動を考慮しなければならない。このいわゆるベストケース反応時間に及ぼすジター効果は、第三メモリ８０６内の第三コンピュータ読み取り可能コードによって計算される。計算は、次の反復数式に従って、実行される。
【００４０】
【数１８】
2004513454.tif 000015
ここで、ＲＪｉは最初の周期的タスクτｉの解放ジターを示しており、ｘ＋は、０とｘの内大きいほうの値を示している。すべてのコンピュータ読み取り可能コードは、ホストプロセッサ８０６で実行される。このシステム８００は、コンピュータに実行されるアプリケーションとしてまたはソフトウエアを実行できる標準的なアーキテクチャーによって実行されるアプリケーションとして動作されるように意図されたソフトウエアによって実現される。このシステムは、ディジタルテレビセット８１０を動作させるのに使用可能である。ソフトウエアは、本発明に従った方法を実行するために設けられたコンピュータプログラム製品を含む記憶装置・記憶媒体８１２から更新することも可能である。記憶装置・記憶媒体は、システム８００に接続されたＣＤ読み取り部８１４によって読み取られる。
【００４１】
図９は、本発明に従ったシステムの実施形態を含むテレビセット９１０の最も重要な部分を大まかに図示している。ここで、アンテナ９００は、テレビ信号を受信する。このアンテナは、例えば、衛星放送用パラボラアンテナであってもよい。さらに、ケーブル、記憶装置・記憶媒体、インターネット、イーサネット（Ｒ）などのようなどんな装置・手段でもテレビ信号を受信するのに使用されてもよい。受信機９０２は、信号を受信する。信号は、例えば、ディジタル、アナログ、ＲＧＢまたはＹＵＢであってよい。受信機９０２のほかに、テレビセットは、プログラム可能部分９０４、例えば、プログラム可能集積回路を含む。プログラム可能部分は、本発明９０６に従ったシステムを含む。受信機９０２に受信され、プログラム可能部分と、本発明９０６と、一般的にテレビセットに含まれる図示されない他の部分によって処理された画像がテレビスクリーン９０８によって表示される。
【００４２】
図１０は、本発明に従ったシステムの実施形態を含むセットトップボックスの最も重要な部分を大まかに図示している。アンテナ１０００は、テレビ信号を受信する。このアンテナは、例えば、衛星放送用パラボラアンテナや、ケーブルや、記憶装置・記憶媒体や、インターネットや、イーサネット（Ｒ）や、またはテレビ信号を受信できる他のどんな装置・手段であってよい。セットトップボックス１００２は、信号を受信する。信号は、例えば、ディジタル、アナログ、ＲＧＢ，またはＹＵＶであってよい。セットトップボックスに通常含まれるここでは図示されない部分のほかに、セットトップボックスは本発明１００４に従ったシステムを含む。テレビセット１００６は、セットトップボックスに受信された信号から発生させられた出力信号を表示できる。セットトップボックスの出力信号がテレビセットの入力信号として使用されるので、この出力信号の解放ジターがテレビセットの入力信号の入力ジターを決定する。従って、入力信号のベストケース反応時間とワーストケース反応時間が、テレビセットがこの入力信号を処理できるかどうかを決定するのに使用される。上記出力信号は、ＶＣＲ（ビデオカセットレコーダ）、ＤＶＤ−ＲＷ、またはハードディスクやに供給されてもよい。または、上記出力信号は、テレビセットに供給される代わりにインターネットリンクに供給されてもよい。
【図面の簡単な説明】
【図１】
タスクτｉの最適な瞬間を示している。
【図２】
タスクτｉの（解放・終了の）瞬間が最適ではない状態を示している。
【図３】
優先順位のより高いタスクτｊによってタスクτｉが占有されている状態を示している。
【図４】
タスクτ３のベストケース反応時間を決定するための繰り返しを示している。
【図５】
タスクτ３のコンピュータ処理されたベストケース反応時間を示している。
【図６】
ベストケースでのタスクτ２の実行の直後にワーストケースでの実行が起こっている状態を示している。
【図７】
本発明に従った方法の主なステップを示している。
【図８】
システムの実施形態の最も重要な部分を示している。
【図９】
本発明に従ったシステムの実施形態を有するテレビセットの最も重要な部分を大まかに示している。
【図１０】
本発明に従ったシステムの実施形態を有するセットトップボックスの最も重要な部分を大まかに示している。
【図２】
2004513454.tif 000022
【図３】
2004513454.tif 000023
【図４】
2004513454.tif 000024
【図５】
2004513454.tif 000025
【図６】
2004513454.tif 000026
【国際公開パンフレット】
2004513454.tif 000027
2004513454.tif 000028
2004513454.tif 000029
2004513454.tif 000030
2004513454.tif 000031
2004513454.tif 000032
2004513454.tif 000033
2004513454.tif 000034
2004513454.tif 000035
2004513454.tif 000036
2004513454.tif 000037
2004513454.tif 000038
2004513454.tif 000039
2004513454.tif 000040
2004513454.tif 000041
2004513454.tif 000042
2004513454.tif 000043
2004513454.tif 000044
2004513454.tif 000045
2004513454.tif 000046
2004513454.tif 000047