図面 (/)

技術 システムのリアルタイム分析のための方法

出願人 インヒロンゲーエムベーハー
発明者 フランクスロムカカーステンアルベルツ
出願日 2006年3月3日 (13年4ヶ月経過) 出願番号 2007-557434
公開日 2008年8月14日 (10年11ヶ月経過) 公開番号 2008-532150
状態 拒絶査定
技術分野 デバッグ/監視
主要キーワード 最小時間差 最大時間間隔 リアルタイム状態 仕事負荷 実行要素 最短時間間隔 例示的実施 最小時間間隔
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2008年8月14日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (0)

図面はありません

課題・解決手段

本発明は、タスクτ)を処理するためのシステム、特に、技術システムリアルタイム分析のための方法に関する。タスク(τ)の処理によって定められるジョブシステムエクスペンスを生じる。特に迅速かつ正確な方法を創出するために、間隔(I、Iτ1、Iτnτ)がリアルタイムに処理不可能であると考えられた場合はこの方法による近似が取り消されて、システムエクスペンスがタスク(τ)の少なくとも1つのジョブのための近似値の代わりに考慮される。

概要

背景

組み込み型リアルタイムシステムや組み込み型のコンピュータシステム等の技術システムの多くは、制限時間又は期限によっても指定された所定の時間間隔内にタスクを処理すること、すなわち、リアルタイムに処理可能であることが要求される。このシステムによって処理されるタスクを総称して、以下「タスクシステム」と呼ぶ。

リアルタイム分析はリアルタイムシステムの発展を自動化するために用いることができる。さらに、タスクシステムをシステムが処理しながら、リアルタイム分析を実行することが可能である。この処理中にシステムが所定のリアルタイム状態を保つことができないと判定された場合、例えば、制限されてはいるが基本的には確実にタスクシステムを処理するための方法を採用することができる。このような方法は、例えば、個々のタスクを他のシステム又はシステムの構成要素に転送して、個々のタスクを処理することでありうる。個々のタスクの処理を延期して、別のタスクを優先させることも可能である。

リアルタイム分析のための方法は必要かつ十分である方法に分けることができる。必要である方法では、所定のタスクシステムに対してエラーを生じさせることなくシステムを一貫して分類することができる。一方、十分な方法では、システムが実際は所定のリアルタイム状態を保ちながらタスクシステムを処理することができるにもかかわらず、システムが所定のタスクシステムに対してリアルタイムに処理可能ではないと誤って特定される場合であろう。

コンピュータ処理装置のためのリアルタイム分析のための必要である方法は、エスバルア(S.Baruah)、エイ・モック(A.Mok)、エル・ロジエール(L.Rosier)著、「プリーティブリスケジューリングハードリアルタイムスポディックタスクスオンワンプロセッサ(Preemtively Scheduling Hard−Real−Time Sporadic Tasks on One Processor)」、プロシーディングオブザ リアル−タイム システムズシンポジウム(Proceedings of the Real−Time Systems Symposium)、1990年、p.182−190より公知である。この方法では、所定のタスクシステムのための最大テスト間隔、すなわち、最大時間間隔がまず算出される。その後、テスト間隔に挿入される時間間隔は所定の基準に従って選択され、タスクがこの時間間隔内で処理されるために必要な演算時間が処理装置によって算出される。この演算時間は時間間隔の長さと比較される。タスクシステムは、演算時間がこの時間間隔より長いとき、リアルタイムに処理可能とは分類されない。システムが、選択された時間間隔でリアルタイム処理可能な場合、テスト間隔に挿入されるさらなる時間間隔が調査される。この手順が、システムがリアルタイムで処理可能でないと判定されるか、基準を満たす時間間隔全てが調査されるまで、続けれられる。この方法では、テスト間隔内にあるこれらの時間間隔のみを調査する必要がある。しかしながら、この方法の実行時間が不必要に延長されるために、多くの時間間隔が不必要に調査されることがありうる。

ジェイ・エイ・スタンコヴィック(J.A.Stankovic)、エムスプリ(M.Spuri)、ケイラマリザム(K.Ramamritham)、ジー・シー・ブタッツォ(G.C.Buttazzo)著、「デッドラインスケジューリングフォーリアル−タイムシステムズ EDFアンドリレーティッドアルゴリズムズ(Deadline Scheduling for Real−Time Systems EDF and Related Algorithms)」、クルヴェールアカミックパブリッシャーズ(Kluwer Academic Publishers)、ボストンドッドレヒト(Dodrecht)/ロンドン、、1998年、p.42−50により公知の方法は、調査すべき時間間隔の数を、バルア(Baruah)らによる方法に比べて少なくすることができる。システムの演算時間を変更できる時間間隔のみを考慮している。この方法の短所は、実行時間がタスクシステムの大きさに依存していることだけではなく、期間、期限又は実行時間等のタスクのパラメータ間の関係に依存していることである。カルステンアルベルス(Karsten Albers)、フランク・スロムカ(Frank Slomka)著、「アンイベントシステムドリブンプロクシメイションフォー ザ アナリシスオブリアル−タイム システムズ(An Event System driven Approximation for the Analysis of Real−Time Systems)」、IEEE プロシーディングズ オブ ザシックスティーンス ユーロミクロカンフェレンスオンリアル−タイム システムズ 2004 (ECRTS‘04)(IEEE Proceedings of the 16th Euromicro Conference on Real−Time Systems 2004)、カターニア(Catania)、イタリア、p.187−195から公知であるが、短期間のタスクと長期間のタスクの両方を含むタスクシステムのリアルタイム分析は、スタンコビッチ(Stankovich)らによる方法では実行時間が長くなってしまう。さらに、システムの高程度の作業負荷のタスクシステムでは、非常に多くの時間間隔を調査する必要がある。このためこの方法では実行時間が長くなってしまう。

リアルタイム分析のための十分かつ効果的である方法は、エム・デヴィ(M.Devi)著、「アンインプルーブスケジューラビリティテストフォーユニプロセッサペリオディックタスクシステムズ(An Improved Schedulability Test for Uniprocessor Periodic Task Systems)、IEEE プロシーディングズオブザフィフティーンス ユーロミクロカンフェレンスオンリアル−タイムシステムズ、2003(IEEE Proceedings of the 15th Euromicro Conference on Real−Time Systems 2003)から公知である。この方法は上述の方法をさらに発展させたものである。この方法での実行時間は基本的にタスクシステムの大きさにのみ依存している。このような方法はまた、「ポリノミナルで複雑な方法(method with polynominal complexity)」として知られている。しかしながら、デヴィ(Devi)による方法では、実際にはタスクシステムのためにリアルタイム処理可能であるシステムがそのように認識されず、誤って分類されることがありうる。例えば、これは、システムの最適な利用を可能にするタスクシステムの場合である。

エス・チャクラルティ(S.Chakraborty)、エス・キュンツリ(S.Kunzli)、エル・スィエレ(L.Thiele)著、「アプロクシメイトスケジューラビリティーアナリシス(Approximate Schedulability Analysis)」、トゥエンティーサードIEEEリアル−タイムシステムズシンポジウム(23rd IEEE Real−Time Systems Symposium)(RTSS)、IEEEプレス(IEEE Press)、2002年、159−168から、リアルタイム分析のためのさらなる方法が公知である。この方法は最大エラーを確実に特定できる近似方法である。リアルタイムの処理可能性を調査するため、時間間隔の確実に特定された数を調査する。エラーの最大数は時間間隔の数に依存する。この時間間隔は、最小の時間間隔をいずれの場合も所定量だけ順次増加させることによって保たれうる。時間間隔毎に、時間間隔内で処理すべきタスクを処理するシステムによって要求される演算時間が正確に計算される。演算時間は、次回の最短時間間隔内でシステムが利用できるシステムのキャパシティと比較されてタスクを処理する。この比較に基づいて、システムがリアルタイム処理可能かどうかが判定される。この方法の短所は、多大な時間間隔がもはや十分に補償できないエラーがこの比較によって生じることである。システムの多くが、特定のタスクシステムをリアルタイム処理可能でないと誤って分類される。さらなる短所は、選択された最大エラーが小さい場合、この方法の実行時間は、正しい方法での実行時間より長くなってしまうということである。従来技術により公知の上述の方法では、この方法が実行される前にこの方法での精度又はエラーを算出する必要がある。特定のタスクシステムにとってあまりに大きいエラーが選択されると、システムがリアルタイムに処理可能でないと誤って分類される可能性がある。選択されたエラーがあまりに小さいと、これにより、かなりの時間と労力が必要となり、実行時間が長くなりすぎる。
エス・バルア(S.Baruah)、エイ・モック(A.Mok)、エル・ロジエール(L.Rosier)著、「プリームティブリースケジューリングハード−リアル−タイムスポラディック タスクスオンワンプロセッサ(Preemtively Scheduling Hard−Real−Time Sporadic Tasks on One Processor)」、プロシーディングズオブザ リアル−タイム システムズ シンポジウム(Proceedings of the Real−Time Systems Symposium)、1990年、p.182−190
ジェイ・エイ・スタンコヴィック(J.A.Stankovic)、エム・スプリ(M.Spuri)、ケイ・ラマムリザム(K.Ramamritham)、ジー・シー・ブタッツォ(G.C.Buttazzo)著、「デッドラインスケジューリングフォー リアル−タイム システムズ EDFアンドリレーティッドアルゴリズムズ(Deadline Scheduling for Real−Time Systems EDF and Related Algorithms)」、クルヴェールアカデミックパブリッシャーズ(Kluwer Academic Publishers)、ボストン/ドッドレヒト(Dodrecht)/ロンドン、、1998年、p.42−50
カルステン・アルベルス(Karsten Albers)、フランク・スロムカ(Frank Slomka)著、「アンイベントシステムドリブンアプロクシメイションフォー ザ アナリシス オブ リアル−タイム システムズ(An Event System driven Approximation for the Analysis of Real−Time Systems)」、IEEE プロシーディングズ オブ ザシックスティーンス ユーロミクロカンフェレンス オン リアル−タイム システムズ 2004 (ECRTS‘04)(IEEE Proceedings of the 16th Euromicro Conference on Real−Time Systems 2004)、カターニア(Catania)、イタリア、p.187−195
エム・デヴィ(M.Devi)著、「アンインプルーブド スケジューラビリティテストフォーユニプロセッサペリオディック タスク システムズ(An Improved Schedulability Test for Uniprocessor Periodic Task Systems)、IEEE プロシーディングズ オブ ザフィフティーンス ユーロミクロ カンフェレンス オン リアル−タイム システムズ、2003(IEEE Proceedings of the 15th Euromicro Conference on Real−Time Systems 2003)
エス・チャクラボルティ(S.Chakraborty)、エス・キュンツリ(S.Kunzli)、エル・スィエレ(L.Thiele)著、「アプロクシメイト スケジューラビリティー アナリシス(Approximate Schedulability Analysis)」、トゥエンティーサード IEEE リアル−タイム システムズ シンポジウム(23rd IEEE Real−Time Systems Symposium)(RTSS)、IEEE プレス(IEEE Press)、2002年、159−168

概要

本発明は、タスク(τ)を処理するためのシステム、特に、技術システムのリアルタイム分析のための方法に関する。タスク(τ)の処理によって定められるジョブシステムエクスペンスを生じる。特に迅速かつ正確な方法を創出するために、間隔(I、Iτ1、Iτnτ)がリアルタイムに処理不可能であると考えられた場合はこの方法による近似が取り消されて、システムエクスペンスがタスク(τ)の少なくとも1つのジョブのための近似値の代わりに考慮される。なし

目的

本発明の目的は従来技術の短所を回避することである。特に、格別に早く正確な方法をリアルタイム分析のために提供するものである。

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

ステムリアルタイム分析のための方法であって、タスクτ)が前記システムによって処理され、タスク(τ)の前記処理によって規定されるジョブシステムエクスペンスを生じ、前記方法はa)タスク(τ)が前記システムによって処理される時間間隔(Iact)を特定するステップと、b)前記タスク(τ)を処理するための前記時間間隔(I、Iτ1、...Iτnτ)内に有効であるシステムエクスペンスのための限界値(GWact)を算出するステップと、c)前記時間間隔(I、Iτ1、...Iτnτ)内に発生する前記ジョブの結果として生じる前記ジョブの総システムエクスペンス(Ract)を算出するステップであり、前記総システムエクスペンス(Ract)を算出するために、i)第1の量(TestList)を成すジョブのために前記システムエクスペンスが用いられ、ii)第2の量(ApproxList)を成すジョブのために何れの場合にも前記システムエクスペンスに対する近似値が用いられ、前記近似値は対応する前記システムエクスペンスより大きい、ステップとb)前記算出された総システムエクスペンス(Ract)と前記限界値(GWact)とを比較し、i)前記時間間隔(Iact)は、前記総システムエクスペンス(Ract)が前記限界値(GWact)を超えない場合、リアルタイムで処理可能であるとみなされ、ii)前記総システムエクスペンス(Ract)が前記限界値(GWact)を超える場合、前記第2の量(ApproxList)のタスク(τ)の少なくとも1つのジョブのための前記総システムエクスペンス(Ract)をさらに算出するように、前記第2の量(ApproxList)が、無でなければ、減らされて、前記システムエクスペンスを前記近似値のかわりに考慮し、かつ少なくともc)及びd)によるステップが繰り返し実行され、iii)前記第2の量(ApproxList)が無であり、前記総システムエクスペンス(Ract)が前記限界値(GWact)を超える場合、前記システムの前記リアルタイム処理可能性があるとはみなされない、ステップとを備える、方法。

請求項2

前記総システムエクスペンス(Ract)が前記限界値(GWact)より低い場合、前記第2の量(ApproxList)を増加させる、請求項1に記載の方法。

請求項3

変更可能なテスト限界(Tmax(τ))が少なくとも1つのタスク(τ)に割り当てられ、前記テスト限界(Tmax(τ))が前記時間間隔(Iact)内で超過するタスク(τ)には、前記タスク(τ)の前記ジョブの前記近似値が用いられ、前記総システムエクスペンス(Ract)が、前記限界値(GWact)よりも高い場合、タスクのための少なくとも1つのテスト限界(Tmax(τ))を、前記第2の量(ApproxList)を減少させるように、変更する、請求項1又は2に記載の方法。

請求項4

前記総システムエクスペンス(Ract)が前記限界値(GWact)よりも低い場合、前記第2の量(ApproxList)のタスク(τ)の前記テスト限界Iτnτを、前記第2の量(ApproxList)を増加させるように、変更する、請求項3に記載の方法。

請求項5

少なくとも1つの数値を、好ましくは2倍にするなどして、増加させ、前記第2の量(ApproxList)を減少させる、かつ/又は少なくとも1つの数値を減少させて、前記第2の量(ApproxList)を増加させる、請求項1乃至4のいずれかに記載の方法。

請求項6

前記総システムエクスペンス(Ract)が前記限界値(GWact)よりも大きい場合、前記総システムエクスペンス(Ract)が前記限界値(GWact)よりも小さい既に調査済みの時間間隔(Iold)で前記方法を継続する、請求項1乃至5のいずれかに記載の方法。

請求項7

前記時間間隔(Iact)内の前記総システムエクスペンス(Ract)が前記限界値(GWact)より大きい場合、前記時間間隔(Iact)内で前記方法を継続する、請求項1乃至6のいずれかに記載の方法。

請求項8

前記タスクの特性である、実際の前記システムエクスペンスのレベル又は前記方法の全体のエラー内の前記近似システムエクスペンスのエラーの占有率を考慮にいれて、前記第2の量(ApproxList)を減少させる、請求項1乃至7のいずれかに記載の方法。

請求項9

前記リアルタイム処理可能性が、時間間隔(I、Iτ1、...Iτnτ)について連続して昇順で調査される、請求項1乃至8のいずれかに記載の方法。

請求項10

前記タスク(τ)が、前記総システムエクスペンス(Ract)の前記算出中に、分類される、請求項1乃至9のいずれかに記載の方法。

請求項11

少なくとも1つのタスク(τ)が前記システムによって繰り返し処理される、請求項1乃至10のいずれかに記載の方法。

請求項12

少なくとも1つのタスク(τ)が最少時間差又は周期的にある期間(pi)で処理される、請求項1乃至11のいずれかに記載の方法。

請求項13

前記システムエクスペンスは、前記タスク(τ)を処理するのに必要な処理時間に基づいて算出される、請求項1乃至12のいずれかに記載の方法。

請求項14

前記システムエクスペンスは、最大必要処理時間の上限に基づいて算出される、請求項1乃至12のいずれかに記載の方法。

請求項15

前記システムエクスペンスは、前記タスク(τ)を処理するのに必要な前記システム、好ましくはCPUの実行要素仕事負荷に基づいて、算出される、請求項1乃至12のいずれかに記載の方法。

請求項16

前記限界値(GWact)は前記時間間隔(Iact)内で利用可能である前記システムのキャパシティに基づいて、算出される、請求項1乃至15のいずれかに記載の方法。

請求項17

前記総システムエクスペンス(Ract)は、開始時点及び終了時点を有する離散時間間隔(I、Iτiτ)で算出され、前記終了時点は、タスク(τ)のジョブが遅くとも処理されていなくてはならない制限時間(dact、di)の終了時である、請求項1乃至16のいずれかに記載の方法。

請求項18

ジョブの前記近似値は前記システムの特定の仕事負荷に基づいて算出される、請求項1乃至17のいずれかに記載の方法。

請求項19

前記特定の仕事負荷は、前記タスク(τ)の前記処理時間および前記期間(pi)からの商として算出される、請求項1乃至18のいずれかに記載の方法。

請求項20

前記特定の仕事負荷が、前記時間間隔(Iact)より小さい間隔で、考慮される、請求項18又は19に記載の方法。

請求項21

前記タスク(τ)は前記制限時間(dact、di)の前記終了時が時間内で最も近い前記システムによって最初に処理される、請求項1乃至20のいずれかに記載の方法。

請求項22

前記タスク(τ)は優先順位によって指定される所定の順番で前記システムによって処理される、請求項1乃至21のいずれかに記載の方法。

請求項23

前記タスク(τ)はイベントフローモデルで記載される、請求項1乃至22のいずれかに記載の方法。

請求項24

であるアルゴリズムが用いられる、請求項1乃至23のいずれかに記載の方法。

請求項25

であるアルゴリズムが用いられる、請求項1乃至23のいずれかに記載の方法。

請求項26

請求項1乃至25のいずれかに記載の前記方法をコンピュータシステムで実行するコンピュータによって読み取り可能なプログラム手段を備えたコンピュータプログラムプロダクト

請求項27

請求項1乃至25のいずれかに記載の前記方法をコンピュータシステムで実行するコンピュータによって読み取り可能であり、内部に記憶されたプログラムを備えたデジタル記憶媒体

請求項28

デジタル記憶媒体を備えたコンピュータシステムであり、前記デジタル記憶媒体は請求項1乃至25のいずれかに記載の前記方法を実行するために前記コンピュータシステムによっって実行可能である、前記媒体内に記憶されたプログラムコード手段を有する、コンピュータシステム。

技術分野

0001

本発明は、システム、特に、技術システムリアルタイム分析のための方法に関する。

背景技術

0002

組み込み型リアルタイムシステムや組み込み型のコンピュータシステム等の技術システムの多くは、制限時間又は期限によっても指定された所定の時間間隔内にタスクを処理すること、すなわち、リアルタイムに処理可能であることが要求される。このシステムによって処理されるタスクを総称して、以下「タスクシステム」と呼ぶ。

0003

リアルタイム分析はリアルタイムシステムの発展を自動化するために用いることができる。さらに、タスクシステムをシステムが処理しながら、リアルタイム分析を実行することが可能である。この処理中にシステムが所定のリアルタイム状態を保つことができないと判定された場合、例えば、制限されてはいるが基本的には確実にタスクシステムを処理するための方法を採用することができる。このような方法は、例えば、個々のタスクを他のシステム又はシステムの構成要素に転送して、個々のタスクを処理することでありうる。個々のタスクの処理を延期して、別のタスクを優先させることも可能である。

0004

リアルタイム分析のための方法は必要かつ十分である方法に分けることができる。必要である方法では、所定のタスクシステムに対してエラーを生じさせることなくシステムを一貫して分類することができる。一方、十分な方法では、システムが実際は所定のリアルタイム状態を保ちながらタスクシステムを処理することができるにもかかわらず、システムが所定のタスクシステムに対してリアルタイムに処理可能ではないと誤って特定される場合であろう。

0005

コンピュータ処理装置のためのリアルタイム分析のための必要である方法は、エスバルア(S.Baruah)、エイ・モック(A.Mok)、エル・ロジエール(L.Rosier)著、「プリーティブリスケジューリングハードリアルタイムスポディックタスクスオンワンプロセッサ(Preemtively Scheduling Hard−Real−Time Sporadic Tasks on One Processor)」、プロシーディングオブザ リアル−タイム システムズシンポジウム(Proceedings of the Real−Time Systems Symposium)、1990年、p.182−190より公知である。この方法では、所定のタスクシステムのための最大テスト間隔、すなわち、最大時間間隔がまず算出される。その後、テスト間隔に挿入される時間間隔は所定の基準に従って選択され、タスクがこの時間間隔内で処理されるために必要な演算時間が処理装置によって算出される。この演算時間は時間間隔の長さと比較される。タスクシステムは、演算時間がこの時間間隔より長いとき、リアルタイムに処理可能とは分類されない。システムが、選択された時間間隔でリアルタイム処理可能な場合、テスト間隔に挿入されるさらなる時間間隔が調査される。この手順が、システムがリアルタイムで処理可能でないと判定されるか、基準を満たす時間間隔全てが調査されるまで、続けれられる。この方法では、テスト間隔内にあるこれらの時間間隔のみを調査する必要がある。しかしながら、この方法の実行時間が不必要に延長されるために、多くの時間間隔が不必要に調査されることがありうる。

0006

ジェイ・エイ・スタンコヴィック(J.A.Stankovic)、エムスプリ(M.Spuri)、ケイラマリザム(K.Ramamritham)、ジー・シー・ブタッツォ(G.C.Buttazzo)著、「デッドラインスケジューリングフォーリアル−タイムシステムズ EDFアンドリレーティッドアルゴリズムズ(Deadline Scheduling for Real−Time Systems EDF and Related Algorithms)」、クルヴェールアカミックパブリッシャーズ(Kluwer Academic Publishers)、ボストンドッドレヒト(Dodrecht)/ロンドン、、1998年、p.42−50により公知の方法は、調査すべき時間間隔の数を、バルア(Baruah)らによる方法に比べて少なくすることができる。システムの演算時間を変更できる時間間隔のみを考慮している。この方法の短所は、実行時間がタスクシステムの大きさに依存していることだけではなく、期間、期限又は実行時間等のタスクのパラメータ間の関係に依存していることである。カルステンアルベルス(Karsten Albers)、フランク・スロムカ(Frank Slomka)著、「アンイベントシステムドリブンプロクシメイションフォー ザ アナリシスオブリアル−タイム システムズ(An Event System driven Approximation for the Analysis of Real−Time Systems)」、IEEE プロシーディングズ オブ ザシックスティーンス ユーロミクロカンフェレンスオンリアル−タイム システムズ 2004 (ECRTS‘04)(IEEE Proceedings of the 16th Euromicro Conference on Real−Time Systems 2004)、カターニア(Catania)、イタリア、p.187−195から公知であるが、短期間のタスクと長期間のタスクの両方を含むタスクシステムのリアルタイム分析は、スタンコビッチ(Stankovich)らによる方法では実行時間が長くなってしまう。さらに、システムの高程度の作業負荷のタスクシステムでは、非常に多くの時間間隔を調査する必要がある。このためこの方法では実行時間が長くなってしまう。

0007

リアルタイム分析のための十分かつ効果的である方法は、エム・デヴィ(M.Devi)著、「アンインプルーブスケジューラビリティテストフォーユニプロセッサペリオディックタスクシステムズ(An Improved Schedulability Test for Uniprocessor Periodic Task Systems)、IEEE プロシーディングズオブザフィフティーンス ユーロミクロカンフェレンスオンリアル−タイムシステムズ、2003(IEEE Proceedings of the 15th Euromicro Conference on Real−Time Systems 2003)から公知である。この方法は上述の方法をさらに発展させたものである。この方法での実行時間は基本的にタスクシステムの大きさにのみ依存している。このような方法はまた、「ポリノミナルで複雑な方法(method with polynominal complexity)」として知られている。しかしながら、デヴィ(Devi)による方法では、実際にはタスクシステムのためにリアルタイム処理可能であるシステムがそのように認識されず、誤って分類されることがありうる。例えば、これは、システムの最適な利用を可能にするタスクシステムの場合である。

0008

エス・チャクラルティ(S.Chakraborty)、エス・キュンツリ(S.Kunzli)、エル・スィエレ(L.Thiele)著、「アプロクシメイトスケジューラビリティーアナリシス(Approximate Schedulability Analysis)」、トゥエンティーサードIEEEリアル−タイムシステムズシンポジウム(23rd IEEE Real−Time Systems Symposium)(RTSS)、IEEEプレス(IEEE Press)、2002年、159−168から、リアルタイム分析のためのさらなる方法が公知である。この方法は最大エラーを確実に特定できる近似方法である。リアルタイムの処理可能性を調査するため、時間間隔の確実に特定された数を調査する。エラーの最大数は時間間隔の数に依存する。この時間間隔は、最小の時間間隔をいずれの場合も所定量だけ順次増加させることによって保たれうる。時間間隔毎に、時間間隔内で処理すべきタスクを処理するシステムによって要求される演算時間が正確に計算される。演算時間は、次回の最短時間間隔内でシステムが利用できるシステムのキャパシティと比較されてタスクを処理する。この比較に基づいて、システムがリアルタイム処理可能かどうかが判定される。この方法の短所は、多大な時間間隔がもはや十分に補償できないエラーがこの比較によって生じることである。システムの多くが、特定のタスクシステムをリアルタイム処理可能でないと誤って分類される。さらなる短所は、選択された最大エラーが小さい場合、この方法の実行時間は、正しい方法での実行時間より長くなってしまうということである。従来技術により公知の上述の方法では、この方法が実行される前にこの方法での精度又はエラーを算出する必要がある。特定のタスクシステムにとってあまりに大きいエラーが選択されると、システムがリアルタイムに処理可能でないと誤って分類される可能性がある。選択されたエラーがあまりに小さいと、これにより、かなりの時間と労力が必要となり、実行時間が長くなりすぎる。
エス・バルア(S.Baruah)、エイ・モック(A.Mok)、エル・ロジエール(L.Rosier)著、「プリームティブリースケジューリングハード−リアル−タイムスポラディック タスクスオンワンプロセッサ(Preemtively Scheduling Hard−Real−Time Sporadic Tasks on One Processor)」、プロシーディングズオブザ リアル−タイム システムズ シンポジウム(Proceedings of the Real−Time Systems Symposium)、1990年、p.182−190
ジェイ・エイ・スタンコヴィック(J.A.Stankovic)、エム・スプリ(M.Spuri)、ケイ・ラマムリザム(K.Ramamritham)、ジー・シー・ブタッツォ(G.C.Buttazzo)著、「デッドラインスケジューリングフォー リアル−タイム システムズ EDFアンドリレーティッドアルゴリズムズ(Deadline Scheduling for Real−Time Systems EDF and Related Algorithms)」、クルヴェールアカデミックパブリッシャーズ(Kluwer Academic Publishers)、ボストン/ドッドレヒト(Dodrecht)/ロンドン、、1998年、p.42−50
カルステン・アルベルス(Karsten Albers)、フランク・スロムカ(Frank Slomka)著、「アンイベントシステムドリブンアプロクシメイションフォー ザ アナリシス オブ リアル−タイム システムズ(An Event System driven Approximation for the Analysis of Real−Time Systems)」、IEEE プロシーディングズ オブ ザシックスティーンス ユーロミクロカンフェレンス オン リアル−タイム システムズ 2004 (ECRTS‘04)(IEEE Proceedings of the 16th Euromicro Conference on Real−Time Systems 2004)、カターニア(Catania)、イタリア、p.187−195
エム・デヴィ(M.Devi)著、「アンインプルーブド スケジューラビリティテストフォーユニプロセッサペリオディック タスク システムズ(An Improved Schedulability Test for Uniprocessor Periodic Task Systems)、IEEE プロシーディングズ オブ ザフィフティーンス ユーロミクロ カンフェレンス オン リアル−タイム システムズ、2003(IEEE Proceedings of the 15th Euromicro Conference on Real−Time Systems 2003)
エス・チャクラボルティ(S.Chakraborty)、エス・キュンツリ(S.Kunzli)、エル・スィエレ(L.Thiele)著、「アプロクシメイト スケジューラビリティー アナリシス(Approximate Schedulability Analysis)」、トゥエンティーサード IEEE リアル−タイム システムズ シンポジウム(23rd IEEE Real−Time Systems Symposium)(RTSS)、IEEE プレス(IEEE Press)、2002年、159−168

発明が解決しようとする課題

0009

本発明の目的は従来技術の短所を回避することである。特に、格別に早く正確な方法をリアルタイム分析のために提供するものである。

0010

前記目的は請求項1及び請求項26乃至28の構成によって達成される。本発明の有利な実施形態が請求項2乃至25の構成によって説明される。

課題を解決するための手段

0011

本発明によれば、以下のステップが、システムのリアルタイム分析のための方法に適用され、タスクが上記システムによって処理され、タスクの前記処理によって規定されるジョブシステムエクスペンスを生じ、上記方法は
a)タスクが上記システムによって処理される時間間隔を特定するステップと、
b)上記タスクを処理するための上記時間間隔内に有効であるシステムエクスペンスのための限界値を算出するステップと、
c)上記時間間隔内に発生する上記ジョブの結果として生じる上記システムエクスペンスの総システムエクスペンスを算出するステップであり、上記総システムエクスペンスを算出するために、
i)第1の量を成すジョブのために上記システムエクスペンスが用いられ、
ii)第2の量を成すジョブのために何れの場合にも前記システムエクスペンスに対する近似値が用いられ、
上記近似値は対応する上記システムエクスペンスより大きい、ステップと
b)上記算出された総システムエクスペンスと上記限界値とを比較し、
i)上記時間間隔は、上記総システムエクスペンスが上記限界値を超えない場合、リアルタイムで処理可能であるとみなされ、
ii)上記総システムエクスペンスが上記限界値を超える場合、上記第2の量のタスクの少なくとも1つのジョブのための上記総システムエクスペンスをさらに算出するように、上記第2の量が、無でなければ、減らされて、上記システムエクスペンスを上記近似値のかわりに考慮し、かつ少なくともc)及びd)によるステップが繰り返し実行され、
iii)上記第2の量が無であり、上記総システムエクスペンスが上記限界値を超える場合、上記システムの上記リアルタイム処理可能性があるとはみなされない、ステップとを備える。

0012

本発明による上記方法では、上記システムエクスペンスが上記第1の量のジョブのために用いられ、近似値が上記第2の量のジョブのために用いられる。ジョブの上記システムエクスペンスの上記近似値は上記ジョブの上記システムエクスペンスに基づいて算出することができる。上記システムエクスペンスは、上記システムの処理時間、演算時間又は仕事負荷でありうる。上記第2の量が無でない場合、上記方法が近似の方法である。上記方法の精度は上記第2の量の基数に依存する。上記方法の上記精度すなわち「近似の度合い」は精密な方法に対する上記近似の方法の偏差の度合いである。上記近似の度合いが上がるにしたがって、上記近似の方法を実行する労力、例えば、実行時間も一般的に増加する。本発明による上記方法では、上記近似の度合いを上記方法の間、動的に変化させることができる。上記近似の度合いの増加は、d)ii)によるステップにおいて上記第2の量を減らすことによって達成することができる。上記第1又は第2の量の減少/増加は上記第1又は第2の量の基数の減少/増加であるとみなされる。

0013

上記方法の上記実行時間をできるだけ少なく保つために、上記方法の開始時において既に、できるだけ大きな上記第2の量の上記基数が選出されている。この結果、上記方法は近似の度合いが低く、労力のレベルが低く、実行時間が短い状態で始まる。上記近似の度合いは、上記方法が実行されている間に上記第2の量を減少させることによって動的に増加させることができる。上記第2の量を減少させる結果、上記システムエクスペンスが上記近似値の代わりに用いられて、上記第2の量の少なくとも1つのジョブのための上記総システムエクスペンスを算出する。すなわち、上記第2の量の少なくとも1つのジョブが上記第1の量に割り当てられて、その結果、上記第1の量が増加する。c)及びd)によるステップを繰り返し実行することで、上記ジョブの上記システムエクスペンスがその近似値の代わりに用いられる。上記近似値は上記システムエクスペンスより大きいため、上記総システムエクスペンスは上記近似値に含まれるエラーによって減らすことができる。総システムエクスペンスを減らした結果、これらを上記限界値より小さくすることが可能となる。この場合、上記タスクシステムは調査された上記時間間隔で上記システムによってリアルタイムに処理可能であると分類されうる。上記総システムエクスペンスが上記限界値より高い場合、減少させても、上記第2の量を再び減らし上記第1の量をさらに増やすことができる。上記リアルタイム処理可能性を、上記減少させた第2の量と上記増加された第1の量に基づいて上記時間間隔内で再び調査することができる。上記近似の度合いが動的に高められるこの手順は繰り返し続けることができる。一方、所定の近似の度合いで、上記システムは、上記限界値を最初に超過した場合、上記タスクシステムについてリアルタイム処理可能でないと既に分類されている。本発明による上記方法で、タスクシステムはより高い信頼度で正確に分類されうる。さらに、上記近似の度合いを動的に変更可能であるため、上記方法の労力及び実行時間を大幅に削減することができる。

0014

上記システムは特に、相互に接続された1つ以上のコンピュータ、電子回路及び制御装置等を有する組み込み型のリアルタイムシステム又はコンピュータシステム等の技術システムである。

0015

本発明の実施形態によれば、上記総システムエクスペンスが上記限界値より小さい場合、上記第2の量を増加させる。上記第2の量を増加する場合、近似のジョブの数が増える。この結果、上記近似の度合いを低くして、上記方法の実行時間を減らすことが出来る。上記方法を、より迅速に効率的に実行することが出来る。

0016

本発明のさらなる実施形態によれば、変更可能なテスト限界が少なくとも1つのタスクに割り当てられ、上記テスト限界が上記時間間隔内で超過するタスクには、上記タスクの上記ジョブの上記近似値が用いられ、上記総システムエクスペンスが、上記限界値よりも高い場合、タスクのための少なくとも1つのテスト限界を、上記第2の量を減少させるように、変更する。上記テスト限界に基づいて、上記近似値の上記総システムエクスペンスに対する比率を制限又は変更することができる。上記比率は、例えば、現在のエラー又は現在の近似の度合いを算出するのに用いられ、ユーザに送ることができる。上記第2の量の基数及び結果として得られる上記近似の度合いは、上記テスト限界を増加又は減少させることで特に簡単な態様で変更することができるであろう。上記(複数の)テスト限界を増加させることで、上記近似の度合いを上げることができる。有利なことに、タスクの上記テスト限界は上記タスクのジョブの数を表す。上記テスト限界は、対応する数のジョブが上記量の上記時間間隔内にある場合、到達される。全てのタスクに対して同一のテスト限界、例えば、同一数のジョブを選択することは、少なくとも初期段階では、特に有利である。一方、ユーザは上記方法の開始時の初期の最大数のエラーを特定すること及び上記テスト限界をこれに基づいて算出することも可能となる。上記総システムエクスペンスが上記限界値より低い場合、最初の量のタスクの上記テスト限界を、上記第2の量を増加させるように変更することができる。上記方法のために必要な上記実行時間及び上記労力を減少させることができる。

0017

テスト限界等の少なくとも1つの数値を、好ましくは2倍にするなどして、増加させ、上記第2の量を減少させる、かつ/又はテスト限界等の少なくとも1つの数値を減少させて、上記第2の量を増加させることが好ましい。上記数値の変更は、例えば、所定の演算処理によって特に迅速で簡単な態様で達成することができる。

0018

本発明のある実施形態によれば、上記総システムエクスペンスが上記限界値よりも大きい場合、上記総システムエクスペンスが上記限界値よりも小さい既に調査済みの時間間隔で上記方法を継続する。こうすることで、上記総システムエクスペンスが上記限界値より小さい任意の時間間隔を選択することができる。この実施形態では、既に調査された時間間隔から得られる結果を用いることができる。最初から上記方法を繰り返し実行することを回避することができる。上記方法は特に迅速で効率的な態様で実行することができる。

0019

本発明のある実施形態によれば、上記タスクの特性である、実際の上記システムエクスペンスのレベル又は上記方法の全体のエラー内の上記近似システムエクスペンスのエラーの占有率を考慮にいれて、上記第2の量を減少させる。最大システムエクスペンスを生じるジョブの上記近似を取り消すことができる。同様に、上記近似をまず、エラーの最大占有率をもつジョブに対して取り消すことができる。このように、上記総システムエクスペンスを最大可能量だけ減らすことができる。

0020

本発明の特に好ましい実施形態によれば、上記リアルタイム処理可能性が、時間間隔について連続して昇順で調査される。時間間隔がリアルタイムで処理可能である場合、全ての短い時間間隔がリアルタイムで処理可能であるとみなされうる。調査された時間間隔の中で上記総システムエクスペンスが上記限界値を越える場合、上記方法を、近似の度合いを高くして同じ時間間隔の中で継続することができる。上記時間間隔が昇順で調査される場合、上記総システムエクスペンスを、例えば、上記システムエクスペンス及び上記近似値を加算することで、特に簡易に定めることができる。

0021

本方法のさらなる実施形態によれば、上記タスクが、上記総システムエクスペンスを算出するために、分類される。このような手順は、これらが異なった優先レベルにある場合、特に有用である。

0022

本発明のある実施形態によれば、少なくとも1つのタスクが上記システムによって繰り返し処理される。少なくとも1つのタスクが、最短時間間隔又は周期的にある期間で処理されることが好ましい。

0023

本発明のさらなる実施形態によれば、上記システムエクスペンスは、上記タスクを処理するのに必要な処理時間に基づいて算出される。上記システムエクスペンスは、最大必要処理時間の上限に基づいて算出されることも可能である。

0024

さらに、上記システムの上記システムエクスペンスを、上記ジョブを処理するのに必要な上記システム、好ましくはCPUの実行要素の仕事負荷に基づいて、算出することができる。

0025

本発明のある実施形態によれば、上記限界値は上記時間間隔内で利用可能である上記システムのキャパシティに基づいて算出される。例えば、処理装置又はCPUの能力の助けで上記限界値を算出することができる。能力が一定であることが想定される場合、上記限界値は、上記時間間隔の長さに上記能力を乗算して算出することができる。この算出処理において、長さが2倍の時間間隔が、2倍にされた上記限界値に割り当てられる。上記限界値に割り当てられた上記時間間隔内で上記CPUによって処理可能であるある量のシステムエクスペンスを用いて上記限界値を表現することも可能である。さらに、異なる時間間隔で、異なる限界値を用いることができる。この結果、変動する能力を持った処理装置をよりよく及びより精密に設計できる。異なった限界値をわずかな時間間隔に割り当てることも可能である。上記限界値は昇順で、やはり増加する時間間隔に割り当てられることが好ましい。ある時間間隔のために算出される限界値を用いて、より長い時間間隔、例えば、次回の最長間隔の上記限界値を算出することが出来る。固定の限界値を用いる方法と比較すると、追加の算出時間を短くして、かなり精密な分析が可能となる。

0026

本発明のある実施形態によれば、開始時点及び終了時点を有する離散時間間隔の上記総システムエクスペンスが算出され、上記終了時点は、タスクのジョブが遅くとも処理されていなくてはならない制限時間の終了時である。離散時間間隔においては、演算を簡単な数値システムで行うことができる。多大な浮動小数点演算は不要である。わかっている制限時間が終了時点として用いられる場合、上記時間間隔は特に簡単な態様で算出されうる。上記時間間隔の同一の開始時点では、上記終了時点をジョブ、例えば、近似されていないジョブの制限時間と等しくすることが必要なだけである。

0027

本発明のある実施形態によれば、ジョブの上記近似値は上記システムの特定の仕事負荷に基づいて算出される。上記特定の仕事負荷は、上記タスクの上記処理時間および上記期間からの商として算出されうる。上記特定の仕事負荷が、上記時間間隔より小さい間隔で、考慮されることも可能である。

0028

本発明の特に好ましい実施形態によれば、上記タスクは上記制限時間の上記終了時が時間内で最も近い上記システムによって最初に処理される。上記システムは上記タスクを優先順位によって予め決められた順番で処理することも可能である。さらに、上記タスクをイベントのフローモデルによって記載することができる。

0029

本発明のある実施形態によれば、以下のアルゴリズムが用いられる。

0030

本発明のさらなる実施形態は以下のアルゴリズムを提供する。

0031

ここで、τrevは、対応するシステムエクスペンスが、各近似値の代わりにさらなるアルゴリズム周期で考慮されるタスクの量を示す。

0032

本発明のさらなる規定によれば、本発明による上記方法をコンピュータシステムで実行するためにコンピュータによって読み取り可能なプログラムコード手段を備えたコンピュータプログラムプロダクトを提供する。さらに、本発明による上記方法を実行するコンピュータによって読み取り可能であり、内部に記憶されたプログラムを備えたデジタル記憶媒体が提供される。さらに、デジタル記憶媒体を備えたコンピュータシステムが、本発明による上記方法を実行するために、コンピュータが実行可能であり、上記媒体内に記憶されたプログラムコード手段を備える。

0033

上記コンピュータプログラムプロダクト、上記デジタル記憶媒体及び上記コンピュータシステムの利点は、上述の方法の利点から得ることができる。

発明を実施するための最良の形態

0034

本発明による方法を例示的実施形態を参照に詳細にわたって以下に説明する。

0035

第一の例では、システムのリアルタイム分析のための近似方法を考える。nを自然数とすると、n個のタスクτを持ったタスクシステムτnが供給される。タスクτを処理するためにシステムが必要とする演算時間は、タスクτετnの処理の結果として生じるシステムエクスペンスとして用いられる。所定の最大時間間隔Imaxより短い時間間隔Iを調査する。時間間隔Iは共通の開始時点を持つ。時間間隔Iの終了時点はタスクシステムτnのタスクτのジョブの制限時間dτの終了によって決まる。すなわち、このジョブは遅くとも終了時点までに処理されていなくてはならない。タスクτnτについては、時間間隔Iτ1⊂…, ⊂Iτnτ⊆Imaxが選択される。時間間隔Iτ1,...は、1、2、・・・等で構成される。または、Iτnτは、タスクτのジョブの数nτで構成される。各タスクτ毎に、タスクτのパラメータに依存し、Tmax(τ)⊂Imaxが以下のように適用されるテスト限界Tmax(τ)がさらに算出される。総演算時間が算出されるとき、タスクτにおけるジョブの実際の演算時間が時間間隔I⊂Tmax(τ)として用いられる。Tmax(τ)⊂I⊂Imaxとなる時間間隔Iに対しては、この演算時間より大きい近似値が演算時間として用いられる。同様に、タスクシステムにおける各タスク毎に、対応する時間間隔が選択される。近似方法の数量nτ及びエラーは相互に依存している。選択された時間間隔は昇順に調査される。いずれの場合も、生じるジョブを処理するのにシステムが必要とする総演算時間が算出され、その後総演算時間は各時間間隔における演算時間の限界値と比較される。この総演算時間が限界値より小さい場合、システムはリアルタイム処理可能である。Tmax(τ)⊂Iτ'nτが適用される、タスクτ'の時間間隔Iτ'nτの分析中に、タスクτのジョブの近似された演算時間が比例的に考慮される。この分析は、最大時間間隔Imaxに到達するかこれを超えるまで続けられる、すなわち、上述のようにタスクシステムτnのタスクのために選択された時間間隔の全てが調査されるまで続けられる。演算時間の近似値であるが故に、総演算時間の算出中に間違いが発生する。そのため、算出された総演算時間は、例えば、正確な方法で算出されうるシステムが実際に必要な演算時間より大きい場合もある。

0036

この方法の実行時間及び調査される時間間隔の数を出来るだけ小さくするために、タスクτ当たりの時間間隔の最大値nτを小さくして、すなわち、テスト限界Tmax(τ)を短くして、例えば、nτ=1で開始する。エラーを含む総演算時間は、調査された時間間隔で利用可能な演算時間のための限界値を越える場合、テスト限界Tmax(τ)を変更するか大きくし、それに対応して時間間隔の最大値nτを少なくとも1つのタスクτのために大きくする。引き続いて、時間間隔のリアルタイム処理可能性が再び調査され、総システムエクスペンスが再計算されて、限界値と比較される。総システムエクスペンスが限界値より小さい場合、次回の最大時間間隔が調査されうる。総システムエクスペンスが連続して限界値を超える場合、1つ以上のテスト限界Tmax(τ)を変更することができる。タスクτのテスト限界Tmax(τ)は、Tmax(τ)=Imaxという条件が満たされるまで連続して変更されうる。この条件が満たされ、総システムエクスペンスが限界値を連続して超える場合、このシステムはリアルタイム処理可能でない。

0037

テスト限界Tmax(τ)は、例えば、数値nτを2倍にすることで大きくすることができる。この方法では、これらの変更が正確に行われることが重要であり、少なくとも1つのテスト限界Tmax(τ)は調査された時間間隔の終了時点を越えるよう変更される。これにより、演算時間の近似値が時間間隔で用いられるジョブの数に影響を与える。近似ジョブの数が減少する場合、総演算時間及びもはや近似されないジョブのエラーの割合は減少する。その結果、近似の度合いが増加することにより、算出される総演算時間を短縮することができる。この短縮によって、算出される総演算時間は限界値より小さくなる場合がある。これが達成されたら、タスクシステムは、調査された時間間隔で受諾されうる。

0038

この方法の第2の例示的実施形態において、時間間隔Iは昇順で調査される。調査された時間間隔Iはリアルタイムに処理可能であると分類される場合、これより短い全ての時間間隔Iもまた同様である。調査された時間間隔Iがリアルタイムに処理可能でないと分類される場合、システムエクスペンスが、タスクτの少なくとも1つの近似ジョブの近似値の代わりに用いられる。ここで、既に調査された時間間隔Iを繰り返し調査すると十分である。リアルタイム分析を短い時間間隔Iで続けること又は最初から繰り返すことは不可欠というわけではない。

0039

方法は以下のように実現されうる。

0040

この方法において、タスクシステムτnの特定の仕事負荷Uを以下のように算出することができる。



ここで、τi、i=1、2、・・・はタスクシステムτnからのタスクであり、ciは、例えば、システムによってタスクτiを処理するのに必要な演算時間等のシステムコストであり、piはタスクτiの期間又は最小時間差である。

0041

第1のステップとして、特定の仕事負荷Uは値1を超えているか否かについて調査する。この場合、タスクシステムはリアルタイム処理可能ではなく、リアルタイム分析を終了できる。

0042

第2のステップとして、1つ以上の最大テスト間隔Imaxが定められる。さらに、この方法を実行するために必要な変数、例えば、現在の時間間隔Iactのための累積現在演算時間Ractとしての総システムエクスペンス、が初期化される。現在の時間間隔Iactより以前の時間間隔はIoldと呼ぶ。タスクシステムτnのタスクτiの各最初の時間間隔In1がテストリスト、TestList、に加えられる。最初の時間間隔In1は個々のタスクτiの最初のジョブの制限時間dτから得られる。さらに、時間間隔の許可数Anzが算出される。この方法の最初には、数Anzが1に設定されて、近似されるジョブのタスクτのリスト、ApproxList、には何も無いことが好ましい。

0043

第3のステップとして、以下の指示が、テストリストTestListに何も無くなるまで繰り返し行われるか、又は、最大テスト間隔を達成するか超えるまで、すなわち、例えば、Iact≧Imaxとなるなど以下が適用される場合に、繰り返し行われる。

0044

第1の指示として、現在の時間間隔Iactが算出される。現在の時間間隔IactはテストリストTestListからの最小時間間隔と等しくされる。最小時間間隔はテストリストTestListから削除される。この時間間隔が別のタスクτiのためテストリストTestListに2回以上含まれていたら、1回のエントリのみ削除される。τactは現在の時間間隔Iactに属するタスクのことである。次の指示として、演算時間Ractは以下の式を用いて算出される。



ここで、Uapproxは近似のタスクの特定の仕事負荷のことである。Uapproxは以下の式を用いて算出することができる。



Uapproxは変数の中にも格納され、必要に応じてリアルタイム分析中に更新することができる。

0045

さらなる指示では、累積された現在の演算時間Ractが、現在の時間間隔Iactの限界値GWactと比較される。限界値GWactは、例えば、現在の時間間隔Iactの間隔の長さと等しくされうる。

0046

第1の場合、演算時間Ractが限界値GWact以下である場合、時間間隔Iactのためのリアルタイム・エビデンスが提供されている。その後の指示で、現在のタスクτactのテスト限界Tmax(τact)に到達したか又は超えたか否かが調査される。テスト限界Tmax(τact)は時間間隔の現在の許可数Anzに依存する。周期的なタスクでは、この調査は以下の式を用いて実行されうる。



ここで、dactは現在の制限時間であり、pactはタスクτactの期間である。テスト限界Tmax(τact)に到達すると、次の指示で、タスクτactが近似タスクのリストApproxListに加えられる。必要に応じて、Uapproxが更新される。

0047

テスト限界Tmax(τact)にまだ到達していない場合は、タスクτactのために次回の最大時間間隔InextがテストリストTextListに加えられる。周期的なタスクでは、時間間隔Inextを以下のように算出することができる。



第1のケースにおける最後の指示として、最後の受諾時間間隔Ioldの値が現在の時間間隔Iactの値に設定される。

0048

一方、第2のケースにおいて、演算時間Ractは限界値GWactより大きく、リストApproxListに何も無い場合、システムはリアルタイム処理可能でない。リストApproxListが空でない場合、算出された演算時間Ractを段階的に減らすよう試みられる。これは以下のように達成することができる。

0049

最初に、数値Anzを増加させる。例えば、数値Anzは2倍にしてもよい。この増加により、リストApproxListに含まれる1つ以上のタスクがもはや近似されないか否かについて調査される。このもはや近似されないタスクが算出される。これらのタスクは、数値Anzを増加した結果、現在の時間間隔Iactより大きいテスト限界Tmax(τ)を何に割り当てるかについて、判定される。このようにして判定されたタスクはリストApproxListから削除されて、Iactより大きい次回の時間間隔がリストTestListに加えられる。演算時間Ractは上述のように判定されたもはや近似されないタスクによって減らされる。周期的なタスクでは、エラーは以下のように時間間隔Iで算出されうる。



ここで、di、piおよびciは制限時間、期間及びシステムエクスペンスであり、例えば、タスクシステムτnのタスクτiの演算時間を示す。このようにして算出されたエラーは演算時間Ractから減算される。減少した演算時間R'actが継続して限界値GWactより大きい場合、数値Anzはまだ十分に増加されていない。数値Anzを、例えば再び2倍にするなどしてさらに増加させる。数値の増加は、減少した演算時間R'actが限界値GWact以下となるか、又はリストApproxListに何も無くなるまで繰り返される。数値Anzを増加した結果、演算時間R'actが限界値GWactより小さくなる場合、この方法は第1のケースでのように続けられる。数値Anzが増加する毎に、演算時間R'actが限界値GWactよりも大きくなる場合、システムはタスクシステムτnについてリアルタイム処理可能ではない。

0050

第3の例示的実施形態において、近似の度合いをさらに小さくすることができる。近似の度合いを、この方法の実行時間を最短にできるため、タスクシステムτnの要求に動的に適合させることが可能となる。例えば、時間間隔毎に、タスクの最大値を近似することができる。ここで、以下の方法を適用することができる。

0051

時間間隔は昇順に調査される。調査された時間間隔の演算時間Ractが限界値GWactより小さいと判定される場合、数値Anzを小さくして、近似値がシステムエクスペンスのために用いられるタスクの数を増加させる。すなわち、少なくとも1つのタスクτのためのテスト限界Tmax(τ)が、タスクτが時間間隔Iact又はInewで近似されるように変更される。

0052

第4の例示的実施形態において、タスクτが出来る限り早く、例えば、各場合において、最初の時間間隔Iτ1の後に、近似される。この近似は、上述のように、再び取り消すことができる。近似が取り消されると、この近似を出来る限り早く、例えば、次回の時間間隔に、再導入することを試みることが出来る。近似の取り消しの結果このようになる場合、この方法で、時間間隔をテストリストTestListに挿入することのみ可能となる。この方法により、広範囲にわたる近似が可能となり、早さと正確さも得られる。

0053

第4の例示的実施形態は、例えば、以下のように実現されうる。

0054

各個々のタスクτの最初のジョブの結果として各々得られる最初の時間間隔Iτ1はテストリストTestListに加えられる。テストリストTestListの時間間隔Iτ1はその後昇順で処理される、すなわち、システムのリアルタイム処理可能性がこれらの間隔につき調査される。タスクの全てのさらなる時間間隔Iがまず近似される、すなわち、これらはテストリストTestListに含まれない。リアルタイム・エビデンスが時間間隔Iτ1で失敗する場合、上述のように近似は段階的に取り消される。調査された時間間隔Iのリアルタイム・エビデンスが提供されるまで、又はさらなるタスクが近似されえなくなるまでこれが行われる。さらなるタスクが近似されえない場合、タスクシステムはリアルタイム処理可能ではない。タスクの近似の取り消しにより、このタスクτの時間間隔Iτi、i>2、がテストリストTestListに加えられる。時間間隔Iτiは、テストが失敗した時間間隔以降のタスクτの次回の最大時間間隔に相当することが好ましい。次回の最大時間間隔は動的エラーでのリアルタイム分析と同様の態様で算出することができる。ある時間間隔で、全てのタスクが近似される、かつ/又はリアルタイムRactが限界値GWactより大きい場合にリアルタイム分析は終了する。

0055

各例示的実施形態において、この方法における特に短い実行時間が、調査するべき時間間隔の数をかなり削減する結果、得られる。近似の度合いが、例えば、動的に適応されうるという事実により、特に厳密にシステムのリアルタイム処理可能性を分析することが可能となる。

0056

本発明による方法は、コンピュータシステム等のシステム、特に、技術システムによって、タスクシステムの処理と平行して実行することができる。タスクシステムにおけるタスクがリアルタイムに処理可能か否かについての調査を事前に行うことができる。例えば、リアルタイム状態を特定のその後の時点で満たすことができないと判定される場合、個々のタスクを他のシステムの構成要素又は他のシステムに転送してより迅速にそのタスクを処理することが可能である。このように転送することで、リアルタイム状態をその後の時点で満たすことができるという利点を有する。個々のタスクの処理を遅延させることも可能となる。例えば、システムを安全に動作させるために又はシステムを緊急に動作させるために不可欠とは限らないタスクの処理を遅延させることができる。システムの機能性を向上させることができる。

0057

本発明による方法はまた、いくつかの相互に作用する構成要素を有するシステムで用いることもできる。この構成要素のリアルタイム処理可能性に関する方法で取得した情報を用いて、適切な態様で個々の構成要素に対するタスクの処理を計画又は判定することができる。構成要素の相互作用を最適化及び向上することができる。

0058

さらに、本発明による方法を用いて、組み込み型のリアルタイムシステム又はコンピュータシステム等の技術システム、電子回路、又は制御装置等を発達させることができる。

符号の説明

0059

τnタスクシステム
τタスク
τ' さらなるタスク
Anz数値
ciエクスペン
dτ、di 制限時間
GWact限界値
I時間間隔
Iτiτタスクτのi番目の時間間隔
Iτnτ タスクτの最大時間間隔
Imax 最大時間間隔
Iact 現在の時間間隔
Iold 以前の時間間隔
nτ 制限時間の数
pi 期間
R演算時間
Ract 現在の演算時間
Tmax(τ) テスト限界

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ