(57)【要約】本発明は、タスク（τ）を処理するためのシステム、特に、技術システムのリアルタイム分析のための方法に関する。タスク（τ）の処理によって定められるジョブはシステムエクスペンスを生じる。特に迅速かつ正確な方法を創出するために、間隔（Ｉ、Ｉτ1、Ｉτｎτ）がリアルタイムに処理不可能であると考えられた場合はこの方法による近似が取り消されて、システムエクスペンスがタスク（τ）の少なくとも１つのジョブのための近似値の代わりに考慮される。【選択図】なし【特許請求の範囲】
【請求項１】
システムのリアルタイム分析のための方法であって、タスク（τ）が前記システムによって処理され、タスク（τ）の前記処理によって規定されるジョブがシステムエクスペンスを生じ、前記方法は
ａ）タスク（τ）が前記システムによって処理される時間間隔（Ｉact）を特定するステップと、
ｂ）前記タスク（τ）を処理するための前記時間間隔（Ｉ、Ｉτ1、．．．Ｉτｎτ）内に有効であるシステムエクスペンスのための限界値（ＧＷact）を算出するステップと、
ｃ）前記時間間隔（Ｉ、Ｉτ1、．．．Ｉτｎτ）内に発生する前記ジョブの結果として生じる前記ジョブの総システムエクスペンス（Ｒact）を算出するステップであり、前記総システムエクスペンス（Ｒact）を算出するために、
ｉ）第１の量（ＴｅｓｔＬｉｓｔ）を成すジョブのために前記システムエクスペンスが用いられ、
ｉｉ）第２の量（ＡｐｐｒｏｘＬｉｓｔ）を成すジョブのために何れの場合にも前記システムエクスペンスに対する近似値が用いられ、
前記近似値は対応する前記システムエクスペンスより大きい、ステップと
ｂ）前記算出された総システムエクスペンス（Ｒact）と前記限界値（ＧＷact）とを比較し、
ｉ）前記時間間隔（Ｉact）は、前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）を超えない場合、リアルタイムで処理可能であるとみなされ、
ｉｉ）前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）を超える場合、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）のタスク（τ）の少なくとも１つのジョブのための前記総システムエクスペンス（Ｒact）をさらに算出するように、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）が、無でなければ、減らされて、前記システムエクスペンスを前記近似値のかわりに考慮し、かつ少なくともｃ）及びｄ）によるステップが繰り返し実行され、
ｉｉｉ）前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）が無であり、前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）を超える場合、前記システムの前記リアルタイム処理可能性があるとはみなされない、ステップとを備える、方法。
【請求項２】
前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）より低い場合、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）を増加させる、請求項１に記載の方法。
【請求項３】
変更可能なテスト限界（Ｔmax（τ））が少なくとも１つのタスク（τ）に割り当てられ、前記テスト限界（Ｔmax（τ））が前記時間間隔（Ｉact）内で超過するタスク（τ）には、前記タスク（τ）の前記ジョブの前記近似値が用いられ、前記総システムエクスペンス（Ｒact）が、前記限界値（ＧＷact）よりも高い場合、タスクのための少なくとも１つのテスト限界（Ｔmax（τ））を、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）を減少させるように、変更する、請求項１又は２に記載の方法。
【請求項４】
前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）よりも低い場合、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）のタスク（τ）の前記テスト限界Ｉτｎτを、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）を増加させるように、変更する、請求項３に記載の方法。
【請求項５】
少なくとも１つの数値を、好ましくは２倍にするなどして、増加させ、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）を減少させる、かつ／又は少なくとも１つの数値を減少させて、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）を増加させる、請求項１乃至４のいずれかに記載の方法。
【請求項６】
前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）よりも大きい場合、前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）よりも小さい既に調査済みの時間間隔（Ｉold）で前記方法を継続する、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記時間間隔（Ｉact）内の前記総システムエクスペンス（Ｒact）が前記限界値（ＧＷact）より大きい場合、前記時間間隔（Ｉact）内で前記方法を継続する、請求項１乃至６のいずれかに記載の方法。
【請求項８】
前記タスクの特性である、実際の前記システムエクスペンスのレベル又は前記方法の全体のエラー内の前記近似システムエクスペンスのエラーの占有率を考慮にいれて、前記第２の量（ＡｐｐｒｏｘＬｉｓｔ）を減少させる、請求項１乃至７のいずれかに記載の方法。
【請求項９】
前記リアルタイム処理可能性が、時間間隔（Ｉ、Ｉτ1、．．．Ｉτｎτ）について連続して昇順で調査される、請求項１乃至８のいずれかに記載の方法。
【請求項１０】
前記タスク（τ）が、前記総システムエクスペンス（Ｒact）の前記算出中に、分類される、請求項１乃至９のいずれかに記載の方法。
【請求項１１】
少なくとも１つのタスク（τ）が前記システムによって繰り返し処理される、請求項１乃至１０のいずれかに記載の方法。
【請求項１２】
少なくとも１つのタスク（τ）が最少時間差又は周期的にある期間（ｐi）で処理される、請求項１乃至１１のいずれかに記載の方法。
【請求項１３】
前記システムエクスペンスは、前記タスク（τ）を処理するのに必要な処理時間に基づいて算出される、請求項１乃至１２のいずれかに記載の方法。
【請求項１４】
前記システムエクスペンスは、最大必要処理時間の上限に基づいて算出される、請求項１乃至１２のいずれかに記載の方法。
【請求項１５】
前記システムエクスペンスは、前記タスク（τ）を処理するのに必要な前記システム、好ましくはＣＰＵの実行要素の仕事負荷に基づいて、算出される、請求項１乃至１２のいずれかに記載の方法。
【請求項１６】
前記限界値（ＧＷact）は前記時間間隔（Ｉact）内で利用可能である前記システムのキャパシティに基づいて、算出される、請求項１乃至１５のいずれかに記載の方法。
【請求項１７】
前記総システムエクスペンス（Ｒact）は、開始時点及び終了時点を有する離散時間間隔（Ｉ、Ｉτｉτ）で算出され、前記終了時点は、タスク（τ）のジョブが遅くとも処理されていなくてはならない制限時間（ｄact、ｄi）の終了時である、請求項１乃至１６のいずれかに記載の方法。
【請求項１８】
ジョブの前記近似値は前記システムの特定の仕事負荷に基づいて算出される、請求項１乃至１７のいずれかに記載の方法。
【請求項１９】
前記特定の仕事負荷は、前記タスク（τ）の前記処理時間および前記期間（ｐi）からの商として算出される、請求項１乃至１８のいずれかに記載の方法。
【請求項２０】
前記特定の仕事負荷が、前記時間間隔（Ｉact）より小さい間隔で、考慮される、請求項１８又は１９に記載の方法。
【請求項２１】
前記タスク（τ）は前記制限時間（ｄact、ｄi）の前記終了時が時間内で最も近い前記システムによって最初に処理される、請求項１乃至２０のいずれかに記載の方法。
【請求項２２】
前記タスク（τ）は優先順位によって指定される所定の順番で前記システムによって処理される、請求項１乃至２１のいずれかに記載の方法。
【請求項２３】
前記タスク（τ）はイベントのフローモデルで記載される、請求項１乃至２２のいずれかに記載の方法。
【請求項２４】
【数１】
2008532150.tif 000010
であるアルゴリズムが用いられる、請求項１乃至２３のいずれかに記載の方法。
【請求項２５】
【数２】
2008532150.tif 000011
であるアルゴリズムが用いられる、請求項１乃至２３のいずれかに記載の方法。
【請求項２６】
請求項１乃至２５のいずれかに記載の前記方法をコンピュータシステムで実行するコンピュータによって読み取り可能なプログラム手段を備えたコンピュータプログラムプロダクト。
【請求項２７】
請求項１乃至２５のいずれかに記載の前記方法をコンピュータシステムで実行するコンピュータによって読み取り可能であり、内部に記憶されたプログラムを備えたデジタル記憶媒体。
【請求項２８】
デジタル記憶媒体を備えたコンピュータシステムであり、前記デジタル記憶媒体は請求項１乃至２５のいずれかに記載の前記方法を実行するために前記コンピュータシステムによっって実行可能である、前記媒体内に記憶されたプログラムコード手段を有する、コンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、システム、特に、技術システムのリアルタイム分析のための方法に関する。
【背景技術】
【０００２】
組み込み型のリアルタイムシステムや組み込み型のコンピュータシステム等の技術システムの多くは、制限時間又は期限によっても指定された所定の時間間隔内にタスクを処理すること、すなわち、リアルタイムに処理可能であることが要求される。このシステムによって処理されるタスクを総称して、以下「タスクシステム」と呼ぶ。
【０００３】
リアルタイム分析はリアルタイムシステムの発展を自動化するために用いることができる。さらに、タスクシステムをシステムが処理しながら、リアルタイム分析を実行することが可能である。この処理中にシステムが所定のリアルタイム状態を保つことができないと判定された場合、例えば、制限されてはいるが基本的には確実にタスクシステムを処理するための方法を採用することができる。このような方法は、例えば、個々のタスクを他のシステム又はシステムの構成要素に転送して、個々のタスクを処理することでありうる。個々のタスクの処理を延期して、別のタスクを優先させることも可能である。
【０００４】
リアルタイム分析のための方法は必要かつ十分である方法に分けることができる。必要である方法では、所定のタスクシステムに対してエラーを生じさせることなくシステムを一貫して分類することができる。一方、十分な方法では、システムが実際は所定のリアルタイム状態を保ちながらタスクシステムを処理することができるにもかかわらず、システムが所定のタスクシステムに対してリアルタイムに処理可能ではないと誤って特定される場合であろう。
【０００５】
コンピュータの処理装置のためのリアルタイム分析のための必要である方法は、エス・バルア（Ｓ．Ｂａｒｕａｈ）、エイ・モック（Ａ．Ｍｏｋ）、エル・ロジエール（Ｌ．Ｒｏｓｉｅｒ）著、「プリームティブリー  スケジューリング  ハード−リアル−タイム  スポラディック  タスクス  オン  ワン  プロセッサ（Ｐｒｅｅｍｔｉｖｅｌｙ  Ｓｃｈｅｄｕｌｉｎｇ  Ｈａｒｄ−Ｒｅａｌ−Ｔｉｍｅ  Ｓｐｏｒａｄｉｃ  Ｔａｓｋｓ  ｏｎ  Ｏｎｅ  Ｐｒｏｃｅｓｓｏｒ）」、プロシーディングズ  オブ  ザ  リアル−タイム  システムズ  シンポジウム（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  Ｓｙｍｐｏｓｉｕｍ）、１９９０年、ｐ．１８２−１９０より公知である。この方法では、所定のタスクシステムのための最大テスト間隔、すなわち、最大時間間隔がまず算出される。その後、テスト間隔に挿入される時間間隔は所定の基準に従って選択され、タスクがこの時間間隔内で処理されるために必要な演算時間が処理装置によって算出される。この演算時間は時間間隔の長さと比較される。タスクシステムは、演算時間がこの時間間隔より長いとき、リアルタイムに処理可能とは分類されない。システムが、選択された時間間隔でリアルタイム処理可能な場合、テスト間隔に挿入されるさらなる時間間隔が調査される。この手順が、システムがリアルタイムで処理可能でないと判定されるか、基準を満たす時間間隔全てが調査されるまで、続けれられる。この方法では、テスト間隔内にあるこれらの時間間隔のみを調査する必要がある。しかしながら、この方法の実行時間が不必要に延長されるために、多くの時間間隔が不必要に調査されることがありうる。
【０００６】
ジェイ・エイ・スタンコヴィック（Ｊ．Ａ．Ｓｔａｎｋｏｖｉｃ）、エム・スプリ（Ｍ．Ｓｐｕｒｉ）、ケイ・ラマムリザム（Ｋ．Ｒａｍａｍｒｉｔｈａｍ）、ジー・シー・ブタッツォ（Ｇ．Ｃ．Ｂｕｔｔａｚｚｏ）著、「デッドライン  スケジューリング  フォー  リアル−タイム  システムズ  ＥＤＦ  アンド  リレーティッド  アルゴリズムズ（Ｄｅａｄｌｉｎｅ  Ｓｃｈｅｄｕｌｉｎｇ  ｆｏｒ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  ＥＤＦ  ａｎｄ  Ｒｅｌａｔｅｄ  Ａｌｇｏｒｉｔｈｍｓ）」、クルヴェール  アカデミック  パブリッシャーズ（Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ）、ボストン／ドッドレヒト（Ｄｏｄｒｅｃｈｔ）／ロンドン、、１９９８年、ｐ．４２−５０により公知の方法は、調査すべき時間間隔の数を、バルア（Ｂａｒｕａｈ）らによる方法に比べて少なくすることができる。システムの演算時間を変更できる時間間隔のみを考慮している。この方法の短所は、実行時間がタスクシステムの大きさに依存していることだけではなく、期間、期限又は実行時間等のタスクのパラメータ間の関係に依存していることである。カルステン・アルベルス（Ｋａｒｓｔｅｎ  Ａｌｂｅｒｓ）、フランク・スロムカ（Ｆｒａｎｋ  Ｓｌｏｍｋａ）著、「アン  イベント  システム  ドリブン  アプロクシメイション  フォー  ザ  アナリシス  オブ  リアル−タイム  システムズ（Ａｎ  Ｅｖｅｎｔ  Ｓｙｓｔｅｍ  ｄｒｉｖｅｎ  Ａｐｐｒｏｘｉｍａｔｉｏｎ  ｆｏｒ  ｔｈｅ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ）」、ＩＥＥＥ  プロシーディングズ  オブ  ザ  シックスティーンス  ユーロミクロ  カンフェレンス  オン  リアル−タイム  システムズ  ２００４  （ＥＣＲＴＳ‘０４）（ＩＥＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １６th  Ｅｕｒｏｍｉｃｒｏ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  ２００４）、カターニア（Ｃａｔａｎｉａ）、イタリア、ｐ．１８７−１９５から公知であるが、短期間のタスクと長期間のタスクの両方を含むタスクシステムのリアルタイム分析は、スタンコビッチ（Ｓｔａｎｋｏｖｉｃｈ）らによる方法では実行時間が長くなってしまう。さらに、システムの高程度の作業負荷のタスクシステムでは、非常に多くの時間間隔を調査する必要がある。このためこの方法では実行時間が長くなってしまう。
【０００７】
リアルタイム分析のための十分かつ効果的である方法は、エム・デヴィ（Ｍ．Ｄｅｖｉ）著、「アン  インプルーブド  スケジューラビリティ  テスト  フォー  ユニプロセッサ  ペリオディック  タスク  システムズ（Ａｎ  Ｉｍｐｒｏｖｅｄ  Ｓｃｈｅｄｕｌａｂｉｌｉｔｙ  Ｔｅｓｔ  ｆｏｒ  Ｕｎｉｐｒｏｃｅｓｓｏｒ  Ｐｅｒｉｏｄｉｃ  Ｔａｓｋ  Ｓｙｓｔｅｍｓ）、ＩＥＥＥ  プロシーディングズ  オブ  ザ  フィフティーンス  ユーロミクロ  カンフェレンス  オン  リアル−タイム  システムズ、２００３（ＩＥＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １５th  Ｅｕｒｏｍｉｃｒｏ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒeａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  ２００３）から公知である。この方法は上述の方法をさらに発展させたものである。この方法での実行時間は基本的にタスクシステムの大きさにのみ依存している。このような方法はまた、「ポリノミナルで複雑な方法（ｍｅｔｈｏｄ  ｗｉｔｈ  ｐｏｌｙｎｏｍｉｎａｌ  ｃｏｍｐｌｅｘｉｔｙ）」として知られている。しかしながら、デヴィ（Ｄｅｖｉ）による方法では、実際にはタスクシステムのためにリアルタイム処理可能であるシステムがそのように認識されず、誤って分類されることがありうる。例えば、これは、システムの最適な利用を可能にするタスクシステムの場合である。
【０００８】
エス・チャクラボルティ（Ｓ．Ｃｈａｋｒａｂｏｒｔｙ）、エス・キュンツリ（Ｓ．Ｋuｎｚｌｉ）、エル・スィエレ（Ｌ．Ｔｈｉｅｌｅ）著、「アプロクシメイト  スケジューラビリティー  アナリシス（Ａｐｐｒｏｘｉｍａｔｅ  Ｓｃｈｅｄｕｌａｂｉｌｉｔｙ  Ａｎａｌｙｓｉｓ）」、トゥエンティーサード  ＩＥＥＥ  リアル−タイム  システムズ  シンポジウム（２３rd  ＩＥＥＥ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  Ｓｙｍｐｏｓｉｕｍ）（ＲＴＳＳ）、ＩＥＥＥ  プレス（ＩＥＥＥ  Ｐｒｅｓｓ）、２００２年、１５９−１６８から、リアルタイム分析のためのさらなる方法が公知である。この方法は最大エラーを確実に特定できる近似方法である。リアルタイムの処理可能性を調査するため、時間間隔の確実に特定された数を調査する。エラーの最大数は時間間隔の数に依存する。この時間間隔は、最小の時間間隔をいずれの場合も所定量だけ順次増加させることによって保たれうる。時間間隔毎に、時間間隔内で処理すべきタスクを処理するシステムによって要求される演算時間が正確に計算される。演算時間は、次回の最短時間間隔内でシステムが利用できるシステムのキャパシティと比較されてタスクを処理する。この比較に基づいて、システムがリアルタイム処理可能かどうかが判定される。この方法の短所は、多大な時間間隔がもはや十分に補償できないエラーがこの比較によって生じることである。システムの多くが、特定のタスクシステムをリアルタイム処理可能でないと誤って分類される。さらなる短所は、選択された最大エラーが小さい場合、この方法の実行時間は、正しい方法での実行時間より長くなってしまうということである。従来技術により公知の上述の方法では、この方法が実行される前にこの方法での精度又はエラーを算出する必要がある。特定のタスクシステムにとってあまりに大きいエラーが選択されると、システムがリアルタイムに処理可能でないと誤って分類される可能性がある。選択されたエラーがあまりに小さいと、これにより、かなりの時間と労力が必要となり、実行時間が長くなりすぎる。
【非特許文献１】エス・バルア（Ｓ．Ｂａｒｕａｈ）、エイ・モック（Ａ．Ｍｏｋ）、エル・ロジエール（Ｌ．Ｒｏｓｉｅｒ）著、「プリームティブリー  スケジューリング  ハード−リアル−タイム  スポラディック  タスクス  オン  ワン  プロセッサ（Ｐｒｅｅｍｔｉｖｅｌｙ  Ｓｃｈｅｄｕｌｉｎｇ  Ｈａｒｄ−Ｒｅａｌ−Ｔｉｍｅ  Ｓｐｏｒａｄｉｃ  Ｔａｓｋｓ  ｏｎ  Ｏｎｅ  Ｐｒｏｃｅｓｓｏｒ）」、プロシーディングズ  オブ  ザ  リアル−タイム  システムズ  シンポジウム（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  Ｓｙｍｐｏｓｉｕｍ）、１９９０年、ｐ．１８２−１９０
【非特許文献２】ジェイ・エイ・スタンコヴィック（Ｊ．Ａ．Ｓｔａｎｋｏｖｉｃ）、エム・スプリ（Ｍ．Ｓｐｕｒｉ）、ケイ・ラマムリザム（Ｋ．Ｒａｍａｍｒｉｔｈａｍ）、ジー・シー・ブタッツォ（Ｇ．Ｃ．Ｂｕｔｔａｚｚｏ）著、「デッドライン  スケジューリング  フォー  リアル−タイム  システムズ  ＥＤＦ  アンド  リレーティッド  アルゴリズムズ（Ｄｅａｄｌｉｎｅ  Ｓｃｈｅｄｕｌｉｎｇ  ｆｏｒ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  ＥＤＦ  ａｎｄ  Ｒｅｌａｔｅｄ  Ａｌｇｏｒｉｔｈｍｓ）」、クルヴェール  アカデミック  パブリッシャーズ（Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ）、ボストン／ドッドレヒト（Ｄｏｄｒｅｃｈｔ）／ロンドン、、１９９８年、ｐ．４２−５０
【非特許文献３】カルステン・アルベルス（Ｋａｒｓｔｅｎ  Ａｌｂｅｒｓ）、フランク・スロムカ（Ｆｒａｎｋ  Ｓｌｏｍｋａ）著、「アン  イベント  システム  ドリブン  アプロクシメイション  フォー  ザ  アナリシス  オブ  リアル−タイム  システムズ（Ａｎ  Ｅｖｅｎｔ  Ｓｙｓｔｅｍ  ｄｒｉｖｅｎ  Ａｐｐｒｏｘｉｍａｔｉｏｎ  ｆｏｒ  ｔｈｅ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ）」、ＩＥＥＥ  プロシーディングズ  オブ  ザ  シックスティーンス  ユーロミクロ  カンフェレンス  オン  リアル−タイム  システムズ  ２００４  （ＥＣＲＴＳ‘０４）（ＩＥＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １６th  Ｅｕｒｏｍｉｃｒｏ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  ２００４）、カターニア（Ｃａｔａｎｉａ）、イタリア、ｐ．１８７−１９５
【非特許文献４】エム・デヴィ（Ｍ．Ｄｅｖｉ）著、「アン  インプルーブド  スケジューラビリティ  テスト  フォー  ユニプロセッサ  ペリオディック  タスク  システムズ（Ａｎ  Ｉｍｐｒｏｖｅｄ  Ｓｃｈｅｄｕｌａｂｉｌｉｔｙ  Ｔｅｓｔ  ｆｏｒ  Ｕｎｉｐｒｏｃｅｓｓｏｒ  Ｐｅｒｉｏｄｉｃ  Ｔａｓｋ  Ｓｙｓｔｅｍｓ）、ＩＥＥＥ  プロシーディングズ  オブ  ザ  フィフティーンス  ユーロミクロ  カンフェレンス  オン  リアル−タイム  システムズ、２００３（ＩＥＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １５th  Ｅｕｒｏｍｉｃｒｏ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒeａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  ２００３）
【非特許文献５】エス・チャクラボルティ（Ｓ．Ｃｈａｋｒａｂｏｒｔｙ）、エス・キュンツリ（Ｓ．Ｋuｎｚｌｉ）、エル・スィエレ（Ｌ．Ｔｈｉｅｌｅ）著、「アプロクシメイト  スケジューラビリティー  アナリシス（Ａｐｐｒｏｘｉｍａｔｅ  Ｓｃｈｅｄｕｌａｂｉｌｉｔｙ  Ａｎａｌｙｓｉｓ）」、トゥエンティーサード  ＩＥＥＥ  リアル−タイム  システムズ  シンポジウム（２３rd  ＩＥＥＥ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ  Ｓｙｍｐｏｓｉｕｍ）（ＲＴＳＳ）、ＩＥＥＥ  プレス（ＩＥＥＥ  Ｐｒｅｓｓ）、２００２年、１５９−１６８
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は従来技術の短所を回避することである。特に、格別に早く正確な方法をリアルタイム分析のために提供するものである。
【００１０】
前記目的は請求項１及び請求項２６乃至２８の構成によって達成される。本発明の有利な実施形態が請求項２乃至２５の構成によって説明される。
【課題を解決するための手段】
【００１１】
本発明によれば、以下のステップが、システムのリアルタイム分析のための方法に適用され、タスクが上記システムによって処理され、タスクの前記処理によって規定されるジョブがシステムエクスペンスを生じ、上記方法は
ａ）タスクが上記システムによって処理される時間間隔を特定するステップと、
ｂ）上記タスクを処理するための上記時間間隔内に有効であるシステムエクスペンスのための限界値を算出するステップと、
ｃ）上記時間間隔内に発生する上記ジョブの結果として生じる上記システムエクスペンスの総システムエクスペンスを算出するステップであり、上記総システムエクスペンスを算出するために、
ｉ）第１の量を成すジョブのために上記システムエクスペンスが用いられ、
ｉｉ）第２の量を成すジョブのために何れの場合にも前記システムエクスペンスに対する近似値が用いられ、
上記近似値は対応する上記システムエクスペンスより大きい、ステップと
ｂ）上記算出された総システムエクスペンスと上記限界値とを比較し、
ｉ）上記時間間隔は、上記総システムエクスペンスが上記限界値を超えない場合、リアルタイムで処理可能であるとみなされ、
ｉｉ）上記総システムエクスペンスが上記限界値を超える場合、上記第２の量のタスクの少なくとも１つのジョブのための上記総システムエクスペンスをさらに算出するように、上記第２の量が、無でなければ、減らされて、上記システムエクスペンスを上記近似値のかわりに考慮し、かつ少なくともｃ）及びｄ）によるステップが繰り返し実行され、
ｉｉｉ）上記第２の量が無であり、上記総システムエクスペンスが上記限界値を超える場合、上記システムの上記リアルタイム処理可能性があるとはみなされない、ステップとを備える。
【００１２】
本発明による上記方法では、上記システムエクスペンスが上記第１の量のジョブのために用いられ、近似値が上記第２の量のジョブのために用いられる。ジョブの上記システムエクスペンスの上記近似値は上記ジョブの上記システムエクスペンスに基づいて算出することができる。上記システムエクスペンスは、上記システムの処理時間、演算時間又は仕事負荷でありうる。上記第２の量が無でない場合、上記方法が近似の方法である。上記方法の精度は上記第２の量の基数に依存する。上記方法の上記精度すなわち「近似の度合い」は精密な方法に対する上記近似の方法の偏差の度合いである。上記近似の度合いが上がるにしたがって、上記近似の方法を実行する労力、例えば、実行時間も一般的に増加する。本発明による上記方法では、上記近似の度合いを上記方法の間、動的に変化させることができる。上記近似の度合いの増加は、ｄ）ｉｉ）によるステップにおいて上記第２の量を減らすことによって達成することができる。上記第１又は第２の量の減少／増加は上記第１又は第２の量の基数の減少／増加であるとみなされる。
【００１３】
上記方法の上記実行時間をできるだけ少なく保つために、上記方法の開始時において既に、できるだけ大きな上記第２の量の上記基数が選出されている。この結果、上記方法は近似の度合いが低く、労力のレベルが低く、実行時間が短い状態で始まる。上記近似の度合いは、上記方法が実行されている間に上記第２の量を減少させることによって動的に増加させることができる。上記第２の量を減少させる結果、上記システムエクスペンスが上記近似値の代わりに用いられて、上記第２の量の少なくとも１つのジョブのための上記総システムエクスペンスを算出する。すなわち、上記第２の量の少なくとも１つのジョブが上記第１の量に割り当てられて、その結果、上記第１の量が増加する。ｃ）及びｄ）によるステップを繰り返し実行することで、上記ジョブの上記システムエクスペンスがその近似値の代わりに用いられる。上記近似値は上記システムエクスペンスより大きいため、上記総システムエクスペンスは上記近似値に含まれるエラーによって減らすことができる。総システムエクスペンスを減らした結果、これらを上記限界値より小さくすることが可能となる。この場合、上記タスクシステムは調査された上記時間間隔で上記システムによってリアルタイムに処理可能であると分類されうる。上記総システムエクスペンスが上記限界値より高い場合、減少させても、上記第２の量を再び減らし上記第１の量をさらに増やすことができる。上記リアルタイム処理可能性を、上記減少させた第２の量と上記増加された第１の量に基づいて上記時間間隔内で再び調査することができる。上記近似の度合いが動的に高められるこの手順は繰り返し続けることができる。一方、所定の近似の度合いで、上記システムは、上記限界値を最初に超過した場合、上記タスクシステムについてリアルタイム処理可能でないと既に分類されている。本発明による上記方法で、タスクシステムはより高い信頼度で正確に分類されうる。さらに、上記近似の度合いを動的に変更可能であるため、上記方法の労力及び実行時間を大幅に削減することができる。
【００１４】
上記システムは特に、相互に接続された１つ以上のコンピュータ、電子回路及び制御装置等を有する組み込み型のリアルタイムシステム又はコンピュータシステム等の技術システムである。
【００１５】
本発明の実施形態によれば、上記総システムエクスペンスが上記限界値より小さい場合、上記第２の量を増加させる。上記第２の量を増加する場合、近似のジョブの数が増える。この結果、上記近似の度合いを低くして、上記方法の実行時間を減らすことが出来る。上記方法を、より迅速に効率的に実行することが出来る。
【００１６】
本発明のさらなる実施形態によれば、変更可能なテスト限界が少なくとも１つのタスクに割り当てられ、上記テスト限界が上記時間間隔内で超過するタスクには、上記タスクの上記ジョブの上記近似値が用いられ、上記総システムエクスペンスが、上記限界値よりも高い場合、タスクのための少なくとも１つのテスト限界を、上記第２の量を減少させるように、変更する。上記テスト限界に基づいて、上記近似値の上記総システムエクスペンスに対する比率を制限又は変更することができる。上記比率は、例えば、現在のエラー又は現在の近似の度合いを算出するのに用いられ、ユーザに送ることができる。上記第２の量の基数及び結果として得られる上記近似の度合いは、上記テスト限界を増加又は減少させることで特に簡単な態様で変更することができるであろう。上記（複数の）テスト限界を増加させることで、上記近似の度合いを上げることができる。有利なことに、タスクの上記テスト限界は上記タスクのジョブの数を表す。上記テスト限界は、対応する数のジョブが上記量の上記時間間隔内にある場合、到達される。全てのタスクに対して同一のテスト限界、例えば、同一数のジョブを選択することは、少なくとも初期段階では、特に有利である。一方、ユーザは上記方法の開始時の初期の最大数のエラーを特定すること及び上記テスト限界をこれに基づいて算出することも可能となる。上記総システムエクスペンスが上記限界値より低い場合、最初の量のタスクの上記テスト限界を、上記第２の量を増加させるように変更することができる。上記方法のために必要な上記実行時間及び上記労力を減少させることができる。
【００１７】
テスト限界等の少なくとも１つの数値を、好ましくは２倍にするなどして、増加させ、上記第２の量を減少させる、かつ／又はテスト限界等の少なくとも１つの数値を減少させて、上記第２の量を増加させることが好ましい。上記数値の変更は、例えば、所定の演算処理によって特に迅速で簡単な態様で達成することができる。
【００１８】
本発明のある実施形態によれば、上記総システムエクスペンスが上記限界値よりも大きい場合、上記総システムエクスペンスが上記限界値よりも小さい既に調査済みの時間間隔で上記方法を継続する。こうすることで、上記総システムエクスペンスが上記限界値より小さい任意の時間間隔を選択することができる。この実施形態では、既に調査された時間間隔から得られる結果を用いることができる。最初から上記方法を繰り返し実行することを回避することができる。上記方法は特に迅速で効率的な態様で実行することができる。
【００１９】
本発明のある実施形態によれば、上記タスクの特性である、実際の上記システムエクスペンスのレベル又は上記方法の全体のエラー内の上記近似システムエクスペンスのエラーの占有率を考慮にいれて、上記第２の量を減少させる。最大システムエクスペンスを生じるジョブの上記近似を取り消すことができる。同様に、上記近似をまず、エラーの最大占有率をもつジョブに対して取り消すことができる。このように、上記総システムエクスペンスを最大可能量だけ減らすことができる。
【００２０】
本発明の特に好ましい実施形態によれば、上記リアルタイム処理可能性が、時間間隔について連続して昇順で調査される。時間間隔がリアルタイムで処理可能である場合、全ての短い時間間隔がリアルタイムで処理可能であるとみなされうる。調査された時間間隔の中で上記総システムエクスペンスが上記限界値を越える場合、上記方法を、近似の度合いを高くして同じ時間間隔の中で継続することができる。上記時間間隔が昇順で調査される場合、上記総システムエクスペンスを、例えば、上記システムエクスペンス及び上記近似値を加算することで、特に簡易に定めることができる。
【００２１】
本方法のさらなる実施形態によれば、上記タスクが、上記総システムエクスペンスを算出するために、分類される。このような手順は、これらが異なった優先レベルにある場合、特に有用である。
【００２２】
本発明のある実施形態によれば、少なくとも１つのタスクが上記システムによって繰り返し処理される。少なくとも１つのタスクが、最短時間間隔又は周期的にある期間で処理されることが好ましい。
【００２３】
本発明のさらなる実施形態によれば、上記システムエクスペンスは、上記タスクを処理するのに必要な処理時間に基づいて算出される。上記システムエクスペンスは、最大必要処理時間の上限に基づいて算出されることも可能である。
【００２４】
さらに、上記システムの上記システムエクスペンスを、上記ジョブを処理するのに必要な上記システム、好ましくはＣＰＵの実行要素の仕事負荷に基づいて、算出することができる。
【００２５】
本発明のある実施形態によれば、上記限界値は上記時間間隔内で利用可能である上記システムのキャパシティに基づいて算出される。例えば、処理装置又はＣＰＵの能力の助けで上記限界値を算出することができる。能力が一定であることが想定される場合、上記限界値は、上記時間間隔の長さに上記能力を乗算して算出することができる。この算出処理において、長さが２倍の時間間隔が、２倍にされた上記限界値に割り当てられる。上記限界値に割り当てられた上記時間間隔内で上記ＣＰＵによって処理可能であるある量のシステムエクスペンスを用いて上記限界値を表現することも可能である。さらに、異なる時間間隔で、異なる限界値を用いることができる。この結果、変動する能力を持った処理装置をよりよく及びより精密に設計できる。異なった限界値をわずかな時間間隔に割り当てることも可能である。上記限界値は昇順で、やはり増加する時間間隔に割り当てられることが好ましい。ある時間間隔のために算出される限界値を用いて、より長い時間間隔、例えば、次回の最長間隔の上記限界値を算出することが出来る。固定の限界値を用いる方法と比較すると、追加の算出時間を短くして、かなり精密な分析が可能となる。
【００２６】
本発明のある実施形態によれば、開始時点及び終了時点を有する離散時間間隔の上記総システムエクスペンスが算出され、上記終了時点は、タスクのジョブが遅くとも処理されていなくてはならない制限時間の終了時である。離散時間間隔においては、演算を簡単な数値システムで行うことができる。多大な浮動小数点演算は不要である。わかっている制限時間が終了時点として用いられる場合、上記時間間隔は特に簡単な態様で算出されうる。上記時間間隔の同一の開始時点では、上記終了時点をジョブ、例えば、近似されていないジョブの制限時間と等しくすることが必要なだけである。
【００２７】
本発明のある実施形態によれば、ジョブの上記近似値は上記システムの特定の仕事負荷に基づいて算出される。上記特定の仕事負荷は、上記タスクの上記処理時間および上記期間からの商として算出されうる。上記特定の仕事負荷が、上記時間間隔より小さい間隔で、考慮されることも可能である。
【００２８】
本発明の特に好ましい実施形態によれば、上記タスクは上記制限時間の上記終了時が時間内で最も近い上記システムによって最初に処理される。上記システムは上記タスクを優先順位によって予め決められた順番で処理することも可能である。さらに、上記タスクをイベントのフローモデルによって記載することができる。
【００２９】
本発明のある実施形態によれば、以下のアルゴリズムが用いられる。                                                                              
【数３】
2008532150.tif 000002
【００３０】
本発明のさらなる実施形態は以下のアルゴリズムを提供する。
【数４】
2008532150.tif 000003
【００３１】
ここで、τrevは、対応するシステムエクスペンスが、各近似値の代わりにさらなるアルゴリズム周期で考慮されるタスクの量を示す。
【００３２】
本発明のさらなる規定によれば、本発明による上記方法をコンピュータシステムで実行するためにコンピュータによって読み取り可能なプログラムコード手段を備えたコンピュータプログラムプロダクトを提供する。さらに、本発明による上記方法を実行するコンピュータによって読み取り可能であり、内部に記憶されたプログラムを備えたデジタル記憶媒体が提供される。さらに、デジタル記憶媒体を備えたコンピュータシステムが、本発明による上記方法を実行するために、コンピュータが実行可能であり、上記媒体内に記憶されたプログラムコード手段を備える。
【００３３】
上記コンピュータプログラムプロダクト、上記デジタル記憶媒体及び上記コンピュータシステムの利点は、上述の方法の利点から得ることができる。
【発明を実施するための最良の形態】
【００３４】
本発明による方法を例示的実施形態を参照に詳細にわたって以下に説明する。
【００３５】
第一の例では、システムのリアルタイム分析のための近似方法を考える。ｎを自然数とすると、ｎ個のタスクτを持ったタスクシステムτnが供給される。タスクτを処理するためにシステムが必要とする演算時間は、タスクτετnの処理の結果として生じるシステムエクスペンスとして用いられる。所定の最大時間間隔Ｉmaxより短い時間間隔Ｉを調査する。時間間隔Ｉは共通の開始時点を持つ。時間間隔Ｉの終了時点はタスクシステムτnのタスクτのジョブの制限時間ｄτの終了によって決まる。すなわち、このジョブは遅くとも終了時点までに処理されていなくてはならない。タスクτｎτについては、時間間隔Ｉτ1⊂…, ⊂Ｉτｎτ⊆Ｉmaxが選択される。時間間隔Ｉτ1，．．．は、１、２、・・・等で構成される。または、Ｉτｎτは、タスクτのジョブの数ｎτで構成される。各タスクτ毎に、タスクτのパラメータに依存し、Ｔmax（τ）⊂Ｉmaxが以下のように適用されるテスト限界Ｔmax（τ）がさらに算出される。総演算時間が算出されるとき、タスクτにおけるジョブの実際の演算時間が時間間隔Ｉ⊂Ｔmax（τ）として用いられる。Ｔmax（τ）⊂Ｉ⊂Ｉmaxとなる時間間隔Ｉに対しては、この演算時間より大きい近似値が演算時間として用いられる。同様に、タスクシステムにおける各タスク毎に、対応する時間間隔が選択される。近似方法の数量ｎτ及びエラーは相互に依存している。選択された時間間隔は昇順に調査される。いずれの場合も、生じるジョブを処理するのにシステムが必要とする総演算時間が算出され、その後総演算時間は各時間間隔における演算時間の限界値と比較される。この総演算時間が限界値より小さい場合、システムはリアルタイム処理可能である。Ｔmax（τ）⊂Ｉτ'ｎτが適用される、タスクτ'の時間間隔Ｉτ'ｎτの分析中に、タスクτのジョブの近似された演算時間が比例的に考慮される。この分析は、最大時間間隔Ｉmaxに到達するかこれを超えるまで続けられる、すなわち、上述のようにタスクシステムτnのタスクのために選択された時間間隔の全てが調査されるまで続けられる。演算時間の近似値であるが故に、総演算時間の算出中に間違いが発生する。そのため、算出された総演算時間は、例えば、正確な方法で算出されうるシステムが実際に必要な演算時間より大きい場合もある。
【００３６】
この方法の実行時間及び調査される時間間隔の数を出来るだけ小さくするために、タスクτ当たりの時間間隔の最大値ｎτを小さくして、すなわち、テスト限界Ｔmax（τ）を短くして、例えば、ｎτ＝１で開始する。エラーを含む総演算時間は、調査された時間間隔で利用可能な演算時間のための限界値を越える場合、テスト限界Ｔmax（τ）を変更するか大きくし、それに対応して時間間隔の最大値ｎτを少なくとも１つのタスクτのために大きくする。引き続いて、時間間隔のリアルタイム処理可能性が再び調査され、総システムエクスペンスが再計算されて、限界値と比較される。総システムエクスペンスが限界値より小さい場合、次回の最大時間間隔が調査されうる。総システムエクスペンスが連続して限界値を超える場合、１つ以上のテスト限界Ｔmax（τ）を変更することができる。タスクτのテスト限界Ｔmax（τ）は、Ｔmax（τ）＝Ｉmaxという条件が満たされるまで連続して変更されうる。この条件が満たされ、総システムエクスペンスが限界値を連続して超える場合、このシステムはリアルタイム処理可能でない。
【００３７】
テスト限界Ｔmax（τ）は、例えば、数値ｎτを２倍にすることで大きくすることができる。この方法では、これらの変更が正確に行われることが重要であり、少なくとも１つのテスト限界Ｔmax（τ）は調査された時間間隔の終了時点を越えるよう変更される。これにより、演算時間の近似値が時間間隔で用いられるジョブの数に影響を与える。近似ジョブの数が減少する場合、総演算時間及びもはや近似されないジョブのエラーの割合は減少する。その結果、近似の度合いが増加することにより、算出される総演算時間を短縮することができる。この短縮によって、算出される総演算時間は限界値より小さくなる場合がある。これが達成されたら、タスクシステムは、調査された時間間隔で受諾されうる。
【００３８】
この方法の第２の例示的実施形態において、時間間隔Ｉは昇順で調査される。調査された時間間隔Ｉはリアルタイムに処理可能であると分類される場合、これより短い全ての時間間隔Ｉもまた同様である。調査された時間間隔Ｉがリアルタイムに処理可能でないと分類される場合、システムエクスペンスが、タスクτの少なくとも１つの近似ジョブの近似値の代わりに用いられる。ここで、既に調査された時間間隔Ｉを繰り返し調査すると十分である。リアルタイム分析を短い時間間隔Ｉで続けること又は最初から繰り返すことは不可欠というわけではない。
【００３９】
方法は以下のように実現されうる。
【００４０】
この方法において、タスクシステムτnの特定の仕事負荷Ｕを以下のように算出することができる。
【数５】
2008532150.tif 000004
ここで、τi、ｉ＝１、２、・・・はタスクシステムτnからのタスクであり、ｃiは、例えば、システムによってタスクτiを処理するのに必要な演算時間等のシステムコストであり、ｐiはタスクτiの期間又は最小時間差である。
【００４１】
第１のステップとして、特定の仕事負荷Ｕは値１を超えているか否かについて調査する。この場合、タスクシステムはリアルタイム処理可能ではなく、リアルタイム分析を終了できる。
【００４２】
第２のステップとして、１つ以上の最大テスト間隔Ｉmaxが定められる。さらに、この方法を実行するために必要な変数、例えば、現在の時間間隔Ｉactのための累積現在演算時間Ｒactとしての総システムエクスペンス、が初期化される。現在の時間間隔Ｉactより以前の時間間隔はＩoldと呼ぶ。タスクシステムτnのタスクτiの各最初の時間間隔Ｉn1がテストリスト、ＴｅｓｔＬｉｓｔ、に加えられる。最初の時間間隔Ｉn1は個々のタスクτiの最初のジョブの制限時間ｄτから得られる。さらに、時間間隔の許可数Ａｎｚが算出される。この方法の最初には、数Ａｎｚが１に設定されて、近似されるジョブのタスクτのリスト、ＡｐｐｒｏｘＬｉｓｔ、には何も無いことが好ましい。
【００４３】
第３のステップとして、以下の指示が、テストリストＴｅｓｔＬｉｓｔに何も無くなるまで繰り返し行われるか、又は、最大テスト間隔を達成するか超えるまで、すなわち、例えば、Ｉact≧Ｉmaxとなるなど以下が適用される場合に、繰り返し行われる。
【００４４】
第１の指示として、現在の時間間隔Ｉactが算出される。現在の時間間隔ＩactはテストリストＴｅｓｔＬｉｓｔからの最小時間間隔と等しくされる。最小時間間隔はテストリストＴｅｓｔＬｉｓｔから削除される。この時間間隔が別のタスクτiのためテストリストＴｅｓｔＬｉｓｔに２回以上含まれていたら、１回のエントリのみ削除される。τactは現在の時間間隔Ｉactに属するタスクのことである。次の指示として、演算時間Ｒactは以下の式を用いて算出される。
【数６】
2008532150.tif 000005
ここで、Ｕapproxは近似のタスクの特定の仕事負荷のことである。Ｕapproxは以下の式を用いて算出することができる。
【数７】
2008532150.tif 000006
Ｕapproxは変数の中にも格納され、必要に応じてリアルタイム分析中に更新することができる。
【００４５】
さらなる指示では、累積された現在の演算時間Ｒactが、現在の時間間隔Ｉactの限界値ＧＷactと比較される。限界値ＧＷactは、例えば、現在の時間間隔Ｉactの間隔の長さと等しくされうる。
【００４６】
第１の場合、演算時間Ｒactが限界値ＧＷact以下である場合、時間間隔Ｉactのためのリアルタイム・エビデンスが提供されている。その後の指示で、現在のタスクτactのテスト限界Ｔmax（τact）に到達したか又は超えたか否かが調査される。テスト限界Ｔmax（τact）は時間間隔の現在の許可数Ａｎｚに依存する。周期的なタスクでは、この調査は以下の式を用いて実行されうる。
【数８】
2008532150.tif 000007
ここで、ｄactは現在の制限時間であり、ｐactはタスクτactの期間である。テスト限界Ｔmax（τact）に到達すると、次の指示で、タスクτactが近似タスクのリストＡｐｐｒｏｘＬｉｓｔに加えられる。必要に応じて、Ｕapproxが更新される。
【００４７】
テスト限界Ｔmax（τact）にまだ到達していない場合は、タスクτactのために次回の最大時間間隔ＩnextがテストリストＴｅｘｔＬｉｓｔに加えられる。周期的なタスクでは、時間間隔Ｉnextを以下のように算出することができる。
【数９】
2008532150.tif 000008
第１のケースにおける最後の指示として、最後の受諾時間間隔Ｉoldの値が現在の時間間隔Ｉactの値に設定される。
【００４８】
一方、第２のケースにおいて、演算時間Ｒactは限界値ＧＷactより大きく、リストＡｐｐｒｏｘＬｉｓｔに何も無い場合、システムはリアルタイム処理可能でない。リストＡｐｐｒｏｘＬｉｓｔが空でない場合、算出された演算時間Ｒactを段階的に減らすよう試みられる。これは以下のように達成することができる。
【００４９】
最初に、数値Ａｎｚを増加させる。例えば、数値Ａｎｚは２倍にしてもよい。この増加により、リストＡｐｐｒｏｘＬｉｓｔに含まれる１つ以上のタスクがもはや近似されないか否かについて調査される。このもはや近似されないタスクが算出される。これらのタスクは、数値Ａｎｚを増加した結果、現在の時間間隔Ｉactより大きいテスト限界Ｔmax（τ）を何に割り当てるかについて、判定される。このようにして判定されたタスクはリストＡｐｐｒｏｘＬｉｓｔから削除されて、Ｉactより大きい次回の時間間隔がリストＴｅｓｔＬｉｓｔに加えられる。演算時間Ｒactは上述のように判定されたもはや近似されないタスクによって減らされる。周期的なタスクでは、エラーは以下のように時間間隔Ｉで算出されうる。
【数１０】
2008532150.tif 000009
ここで、ｄi、ｐiおよびｃiは制限時間、期間及びシステムエクスペンスであり、例えば、タスクシステムτnのタスクτiの演算時間を示す。このようにして算出されたエラーは演算時間Ｒactから減算される。減少した演算時間Ｒ'actが継続して限界値ＧＷactより大きい場合、数値Ａｎｚはまだ十分に増加されていない。数値Ａｎｚを、例えば再び２倍にするなどしてさらに増加させる。数値の増加は、減少した演算時間Ｒ'actが限界値ＧＷact以下となるか、又はリストＡｐｐｒｏｘＬｉｓｔに何も無くなるまで繰り返される。数値Ａｎｚを増加した結果、演算時間Ｒ'actが限界値ＧＷactより小さくなる場合、この方法は第１のケースでのように続けられる。数値Ａｎｚが増加する毎に、演算時間Ｒ'actが限界値ＧＷactよりも大きくなる場合、システムはタスクシステムτnについてリアルタイム処理可能ではない。
【００５０】
第３の例示的実施形態において、近似の度合いをさらに小さくすることができる。近似の度合いを、この方法の実行時間を最短にできるため、タスクシステムτnの要求に動的に適合させることが可能となる。例えば、時間間隔毎に、タスクの最大値を近似することができる。ここで、以下の方法を適用することができる。
【００５１】
時間間隔は昇順に調査される。調査された時間間隔の演算時間Ｒactが限界値ＧＷactより小さいと判定される場合、数値Ａｎｚを小さくして、近似値がシステムエクスペンスのために用いられるタスクの数を増加させる。すなわち、少なくとも１つのタスクτのためのテスト限界Ｔmax（τ）が、タスクτが時間間隔Ｉact又はＩnewで近似されるように変更される。
【００５２】
第４の例示的実施形態において、タスクτが出来る限り早く、例えば、各場合において、最初の時間間隔Ｉτ1の後に、近似される。この近似は、上述のように、再び取り消すことができる。近似が取り消されると、この近似を出来る限り早く、例えば、次回の時間間隔に、再導入することを試みることが出来る。近似の取り消しの結果このようになる場合、この方法で、時間間隔をテストリストＴｅｓｔＬｉｓｔに挿入することのみ可能となる。この方法により、広範囲にわたる近似が可能となり、早さと正確さも得られる。
【００５３】
第４の例示的実施形態は、例えば、以下のように実現されうる。
【００５４】
各個々のタスクτの最初のジョブの結果として各々得られる最初の時間間隔Ｉτ1はテストリストＴｅｓｔＬｉｓｔに加えられる。テストリストＴｅｓｔＬｉｓｔの時間間隔Ｉτ1はその後昇順で処理される、すなわち、システムのリアルタイム処理可能性がこれらの間隔につき調査される。タスクの全てのさらなる時間間隔Ｉがまず近似される、すなわち、これらはテストリストＴｅｓｔＬｉｓｔに含まれない。リアルタイム・エビデンスが時間間隔Ｉτ1で失敗する場合、上述のように近似は段階的に取り消される。調査された時間間隔Ｉのリアルタイム・エビデンスが提供されるまで、又はさらなるタスクが近似されえなくなるまでこれが行われる。さらなるタスクが近似されえない場合、タスクシステムはリアルタイム処理可能ではない。タスクの近似の取り消しにより、このタスクτの時間間隔Ｉτi、ｉ>２、がテストリストＴｅｓｔＬｉｓｔに加えられる。時間間隔Ｉτiは、テストが失敗した時間間隔以降のタスクτの次回の最大時間間隔に相当することが好ましい。次回の最大時間間隔は動的エラーでのリアルタイム分析と同様の態様で算出することができる。ある時間間隔で、全てのタスクが近似される、かつ／又はリアルタイムＲactが限界値ＧＷactより大きい場合にリアルタイム分析は終了する。
【００５５】
各例示的実施形態において、この方法における特に短い実行時間が、調査するべき時間間隔の数をかなり削減する結果、得られる。近似の度合いが、例えば、動的に適応されうるという事実により、特に厳密にシステムのリアルタイム処理可能性を分析することが可能となる。
【００５６】
本発明による方法は、コンピュータシステム等のシステム、特に、技術システムによって、タスクシステムの処理と平行して実行することができる。タスクシステムにおけるタスクがリアルタイムに処理可能か否かについての調査を事前に行うことができる。例えば、リアルタイム状態を特定のその後の時点で満たすことができないと判定される場合、個々のタスクを他のシステムの構成要素又は他のシステムに転送してより迅速にそのタスクを処理することが可能である。このように転送することで、リアルタイム状態をその後の時点で満たすことができるという利点を有する。個々のタスクの処理を遅延させることも可能となる。例えば、システムを安全に動作させるために又はシステムを緊急に動作させるために不可欠とは限らないタスクの処理を遅延させることができる。システムの機能性を向上させることができる。
【００５７】
本発明による方法はまた、いくつかの相互に作用する構成要素を有するシステムで用いることもできる。この構成要素のリアルタイム処理可能性に関する方法で取得した情報を用いて、適切な態様で個々の構成要素に対するタスクの処理を計画又は判定することができる。構成要素の相互作用を最適化及び向上することができる。
【００５８】
さらに、本発明による方法を用いて、組み込み型のリアルタイムシステム又はコンピュータシステム等の技術システム、電子回路、又は制御装置等を発達させることができる。
【符号の説明】
【００５９】
τn            タスクシステム
τ              タスク
τ'            さらなるタスク
Ａｎｚ          数値
ｃi            エクスペンス
ｄτ、ｄi        制限時間
ＧＷact        限界値
Ｉ              時間間隔
Ｉτiτ          タスクτのｉ番目の時間間隔
Ｉτｎτ          タスクτの最大時間間隔
Ｉmax          最大時間間隔
Ｉact          現在の時間間隔
Ｉold          以前の時間間隔
ｎτ            制限時間の数
ｐi            期間
Ｒ              演算時間
Ｒact          現在の演算時間
Ｔmax（τ）    テスト限界
【国際調査報告】
2008532150.tif 000012
2008532150.tif 000013
2008532150.tif 000014
2008532150.tif 000015