(57)【要約】  本発明は、システム、特にさまざまなタスクが設けられたコンピュータシステムの実時間を解析する方法であって、タスクは繰り返し実行され、タスクの実行は、タスクの起動によりトリガーされ、これはタスクのイベントを示し、複数の記述的エレメントが前記イベントの時間相関をイベントストリームとして記述するために設けられ、イベントストリームはイベントの最大時間密度および／又は最小時間密度を検出することができ、少なくとも、イベントストリームの量が割り当てられ、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の時間相関を記述するさらなる記述的エレメントを有する方法を提供する。
2012518215.tif 000002
【特許請求の範囲】
【請求項１】
システム、特にさまざまなタスクが設けられたコンピュータシステムの実時間を解析するための、コンピュータに組み込まれる方法であって、
前記タスクは繰り返し実行され、
タスクの実行は、前記タスクの起動によりトリガーされ、これは前記タスクのイベントを示し、
複数の記述的エレメントが前記イベントの時間相関をイベントストリームとして記述するために設けられ、
前記イベントストリームは前記イベントの最大時間密度および／又は最小時間密度を検出することができ、
少なくとも、イベントストリームの量が割り当てられ、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の時間相関を記述するさらなる記述的エレメントを有することを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、
前記少なくとも１つのさらなる記述的エレメントが限定イベントストリームを記述することを特徴とする方法。
【請求項３】
請求項１又は２に記載の方法であって、
前記さらなる記述的エレメントもしくは限定イベントストリームの少なくとも１つが、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の最大時間相関を記述し、
少なくとも時間インターバル（ｄｔ）において前記限定イベントストリームにより許容されるイベントの量である時間インターバル（ｄｔ）のイベント量が、ｄｔにおいて非限定イベントストリームにより許容されるイベントの総量より少ないことを特徴とする方法。
【請求項４】
請求項１、２、３のいずれかに記載の方法であって、
前記さらなる記述的なエレメント又は限定イベントストリームの少なくとも１つが、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の最小時間相関を記述し、
少なくとも時間インターバル（ｄｔ）に対し、ｄｔにおいて前記限定イベントストリームにより許容されるイベントの量が、ｄｔにおいて前記非限定イベントストリームにより許容されるイベントの量を上回ることを特徴とする方法。
【請求項５】
先に記載された請求項のいずれかに記載の方法であって、
前記システムには少なくとも１つのコンポーネント又はリソースが割り当てられ、前記コンポーネントの少なくとも１つには少なくとも２つのタスクが割り当てられることを特徴とする方法。
【請求項６】
先に記載された請求項のいずれかに記載の方法であって、
少なくとも２つのタスクが１つのグループに含まれ、グループの前記タスクはリソースに割り当てられ、前記リソースにおいて競合する前記タスクもしくはこのグループのタスクは、異なる時間においてのみ前記リソースにおける処理を行い、前記システムは前記リソースが前記グループの所定のタスクに割り当てられる時間点を決定する方法を有することを特徴とする方法。
【請求項７】
先に記載された請求項のいずれかに記載の方法であって、
前記限定イベントストリームの少なくとも１つが少なくとも２つの限定イベントストリームに割り当てられ、それらはそれぞれ異なるタスクを起動し、
これらのタスクは少なくとも１つの結合グループに割り当てられ、
コストがそれぞれ、１つのイベントのための前記タスクによる前記リソースの一時的な使用をキャプチャする前記タスクに割り当てられ、
さらに、
前記タスクにより結合して要求される前記コストを決定するステップ、を有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記割り当てられたイベントの量を考慮して前記限定イベントストリームの残りの結果を決定するステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれぞれ割り当てられるイベントの量から全体コストを検出するステップ、を有することを特徴とする方法。
【請求項８】
システム、特に複数の異なるタスクが設けられたコンピュータシステムの実時間を解析するための、コンピュータに組み込まれる方法であって
前記タスクは繰り返し実行され、
タスクの実行は、前記タスクの起動によりトリガーされ、これは前記タスクのイベントを示し、
１又は複数の記述的エレメントが前記イベントの時間相関をイベントストリームとして記述するために設けられ、
前記イベントストリームは前記イベントの最大時間密度および／又は最小時間密度を検出することができ、
少なくとも、イベントストリームの量が割り当てられ、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の時間相関を記述するさらなる記述的エレメントを有し、
前記限定イベントストリームの少なくとも１つが少なくとも２つの限定イベントストリームに割り当てられ、それらはそれぞれ異なるタスクを起動し、
これらのタスクは少なくとも１つの結合グループに割り当てられ、
タスクには、それぞれ１つのイベントのための前記タスクによる前記リソースの一時的な使用をキャプチャする各コストが割り当てられ、
さらに、
前記タスクにより結合して要求される前記コストを決定するステップ、を有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記割り当てられたイベントの量を考慮して前記限定イベントストリームの残りの結果を決定するステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれぞれ割り当てられるイベントの量から全体コストを検出するステップ、を有することを特徴とする方法。
【請求項９】
請求項７又は８に記載の方法であって、
少なくとも２つのイベントストリームに、２つの異なる限定イベントストリームが割り当てられ、さらに、
前記タスクにより結合して要求される前記コストを決定するステップを有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定され、イベントの最小量はそれぞれ前記限定イベントストリームにより許容されるものであるステップ、
前記限定イベントストリームの残りのイベントを決定するステップであって、実際に割り当てられたイベントの量が考慮されるステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定され、他の限定イベントストリームが前記タスクに割り当てられるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられる、もしくはイベント量が前記グループの全てのタスクに割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれらにそれぞれ割り当てられるイベントの量から全体コストを決定するステップ、を有することを特徴とする方法。
【請求項１０】
先に記載された請求項のいずれかに記載の方法であって、
前記限定イベントストリームが、時間インターバルにおけるイベントの密度を記述するポイントの量に割り当てられ、前記限定イベントストリームは、イベントに対し異なるポイントの量を要求する少なくとも２つの限定イベントストリームに割り当てられる
ことを特徴とする方法。
【請求項１１】
先に記載された請求項のいずれかに記載の方法であって、
第１のタスクの前記起動が第２のタスクにより実行されることができ、
これらの起動の時間相関は、イベントストリーム（出力される前記第１のタスクのイベントストリーム、入力される前記第２のタスクのイベントストリーム）によってもキャプチャ可能であることを特徴とする方法。
【請求項１２】
先に記載された請求項のいずれかに記載の方法であって、
少なくとも２つのリソースが前記システムに割り当てられ、
タスクの第１のグループが第１のリソースに割り当てられ、タスクの第２のグループが第２のリソースに割り当てられ、
前記第１のグループの少なくとも２つのタスクがそれぞれ前記第２のグループのタスクを直接、もしくは複数のタスクを経由して起動する方法であって、
出力される前記第１のタスクのイベントストリームに対し、少なくとも限定イベントストリームを決定するステップ、
入力される前記第２のタスクのイベントストリームに対し、少なくとも第２のタスクに対する起動が第１のタスクにより直接実行されない限り、少なくとも限定イベントストリームを決定するステップ、
前記第２のタスクの、前記入力されるイベントストリームの前記限定イベントストリームを考慮して、前記第２のタスクにより結合的に要求されるコストを検出するステップ、
を有することを特徴とする方法。
【請求項１３】
請求項１２に記載の方法であって、少なくとも１つの前記第２のタスクの前記限定イベントストリームを決定するために、前記第１のタスクの前記限定イベントストリームが使用されることを特徴とする方法。
【請求項１４】
先に記載された請求項のいずれかに記載の方法であって、
前記タスクは、ＣＰＵ又は電気回路モジュールにより実行可能なユニットであることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータに組み込まれる方法であって、プログラムモジュール（タスク）および／又は電気回路モジュールを有する複合分散システムの実時間応答の解析方法に関する。
【背景技術】
【０００２】
このようなシステムは、プログラムモジュール（タスク）および／又は電気回路モジュールの形の、複数のコンポーネントからなる。コンポーネントは互いに通信を行いデータの処理もしくは変換を行う。さらに、そのようなシステムは、データを検出するセンサー、ユーザとの対話を行うモジュール、環境や他のシステムへ物理的な影響を及ぼすアクチュエータ、ユーザや環境に対し情報を伝達する出力メディアを有してもよい。
【０００３】
特定のコンポーネント（実行リソース）は、部分的に、１以上のプログラムモジュールを順に実行してもよい。より多くのモジュールが実行される場合、順序やそれぞれの実行時間は、シーケンスプランニングもしくはスケジューリングの手法により各モジュールに割り当てられる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
現在実行できるスケジューリング手法として静的スケジューリング法や動的スケジューリング法がある。静的スケジューリング法では、実行されるモジュールに対する実行順序や実行時間の割り当ては静的に決定される。動的スケジューリング法では、実行されるモジュールに対する実行順序や実行時間の割り当ては、動作時間を考慮する所定の方法により決定される。動作時間は処理されるデータ、他のモジュールによる実行、環境、および／又はユーザとの相互作用に依存する。
【０００５】
このようなシステムやコンポーネントは、それらが正しい結果や制御決定が求められるだけでなく、検出期間や、結果を出力するタイミングに関する要求も課せられるために、時間制約が厳しいことがある。そのような要求の例として、結果の決定のための最大待ち期間や、数値又はセンサー又は入力データの変化への保証応答時間がある。しかしながら、このような要求は規則的なタイムラグや一定のタイムフレームにおける新たな演算を求めることがある。
【０００６】
モジュールはお互いに、通信リンク経由で、起動及び／又は非同期的なデータのやり取りを行うことがある。この通信もしくは起動のリンクのモデリングのために、多数のイベントモデルが開発されている。このような関係は、例えば単一周期、１周期およびジッタ、イベントストリーム［Gresser: Echtzeitnachweis Ereignisgesteuerter Realzeitsysteme, Munchen 1993,（ここで参照することで包含されるとする）］、又は階層イベントストリーム（WO 2008/003427参照）によりモデル化されることがある。他にも多くのイベントモデルが利用可能である。
【０００７】
実時間システムの解析に関しては、可能な限り実際のシステムにおける処理に近づけることが重要である。実際の組み込みシステムにおいては、多くのコンポーネントやタスクは暗黙のうちに、実行シナリオとは別に非常に強い相互関係がある。この相互関係は互いの依存関係を考慮することなくして無視することはできない。このように、実時間解析は、実際のシステムよりも長い最大反応時間（応答時間）といった、より保守的な結果を生成しうる。
【０００８】
一連の依存関係は、既存の実時間解析において考慮される。しかしながら、所望のタイプの依存関係を正確に考慮しようとすると常に、解析アルゴリズムの、特定の拡張が必要になる。その結果、解析において新たなタイプの依存関係を考慮することは非常に複雑な処理になる。さらに、既存の実時間解析方法は、依存関係の一部しか対応していない。
【０００９】
よって、実際の実時間解析から依存関係の決定やモデリングを切り離すメカニズムを持つことは非常に有利なことである。その結果、実時間解析においては、抽象的な依存関係モデルが決定されうる全ての依存関係を考慮するためには、この抽象的な依存関係モデルを考慮しなくてはならない。
【００１０】
本発明によれば、このようなメカニズムである、イベントストリームを制限する方法を提案する。
【課題を解決するための手段】
【００１１】
第１の側面によれば、本発明は、システム、特にさまざまなタスクが設けられたコンピュータシステムの実時間を解析するための、コンピュータに組み込まれる方法であって、前記タスクは繰り返し実行され、タスクの実行は、前記タスクの起動によりトリガーされ、これは前記タスクのイベントを示し、複数の記述的エレメントが前記イベントの時間相関をイベントストリームとして記述するために設けられ、前記イベントストリームは前記イベントの最大時間密度および／又は最小時間密度を検出することができ、少なくとも、イベントストリームの量が割り当てられ、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の時間相関を記述するさらなる記述的エレメントを有することを特徴とする方法が提供される。
【００１２】
前記少なくとも１つのさらなる記述的エレメントは、限定イベントストリームを記述する。
【００１３】
前記さらなる記述的エレメントもしくは限定イベントストリームの少なくとも１つが、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の最大時間相関を記述し、少なくとも時間インターバル（ｄｔ）において前記限定イベントストリームにより許容されるイベントの量である時間インターバル（ｄｔ）のイベント量が、ｄｔにおいて非限定イベントストリームにより許容されるイベントの総量より少ないことが好ましい。
【００１４】
前記さらなる記述的なエレメント又は限定イベントストリームの少なくとも１つが、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の最小時間相関を記述し、少なくとも時間インターバル（ｄｔ）に対し、ｄｔにおいて前記限定イベントストリームにより許容されるイベントの量が、ｄｔにおいて前記非限定イベントストリームにより許容されるイベントの量を上回る。
【００１５】
前記システムには少なくとも１つのコンポーネント又はリソースが割り当てられ、前記コンポーネントの少なくとも１つには少なくとも２つのタスクが割り当てられることが好ましい。
【００１６】
少なくとも２つのタスクが１つのグループに含まれることが好ましく、グループの前記タスクはリソースに割り当てられ、前記リソースにおいて競合する前記タスクもしくはこのグループのタスクは、異なる時間においてのみ前記リソースにおける処理を行い、前記システムは前記リソースが前記グループの所定のタスクに割り当てられる時間点を決定する方法を有する。
【００１７】
本発明の好適な実施形態によれば、前記限定イベントストリームの少なくとも１つが少なくとも２つの限定イベントストリームに割り当てられ、それらはそれぞれ異なるタスクを起動し、これらのタスクは少なくとも１つの結合グループに割り当てられ、コストがそれぞれ、１つのイベントのための前記タスクによる前記リソースの一時的な使用をキャプチャする前記タスクに割り当てられ、
さらに、
前記タスクにより結合して要求される前記コストを決定するステップ、を有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記割り当てられたイベントの量を考慮して前記限定イベントストリームの残りの結果を決定するステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれぞれ割り当てられるイベントの量から全体コストを検出するステップ、を有する。
【００１８】
第２の側面によれば、本発明は、システム、特に複数の異なるタスクが設けられたコンピュータシステムの実時間を解析するための、コンピュータに組み込まれる方法であって
前記タスクは繰り返し実行され、
タスクの実行は、前記タスクの起動によりトリガーされ、これは前記タスクのイベントを示し、
１又は複数の記述的エレメントが前記イベントの時間相関をイベントストリームとして記述するために設けられ、
前記イベントストリームは前記イベントの最大時間密度および／又は最小時間密度を検出することができ、
少なくとも、イベントストリームの量が割り当てられ、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の時間相関を記述するさらなる記述的エレメントを有し、
前記限定イベントストリームの少なくとも１つが少なくとも２つの限定イベントストリームに割り当てられ、それらはそれぞれ異なるタスクを起動し、
これらのタスクは少なくとも１つの結合グループに割り当てられ、
タスクには、それぞれ１つのイベントのための前記タスクによる前記リソースの一時的な使用をキャプチャする各コストが割り当てられ、
さらに、
前記タスクにより結合して要求される前記コストを決定するステップ、を有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記割り当てられたイベントの量を考慮して前記限定イベントストリームの残りの結果を決定するステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれぞれ割り当てられるイベントの量から全体コストを検出するステップ、を有する方法を提供する。
【００１９】
本発明の両側面によれば、少なくとも２つのイベントストリームに、２つの異なる限定イベントストリームが割り当てられ、さらに、
前記タスクにより結合して要求される前記コストを決定するステップを有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定され、イベントの最小量はそれぞれ前記限定イベントストリームにより許容されるものであるステップ、
前記限定イベントストリームの残りのイベントを決定するステップであって、実際に割り当てられたイベントの量が考慮されるステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定され、他の限定イベントストリームが前記タスクに割り当てられるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられる、もしくはイベント量が前記グループの全てのタスクに割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれらにそれぞれ割り当てられるイベントの量から全体コストを決定するステップ、を有する。
【００２０】
前記限定イベントストリームは、時間インターバルにおけるイベントの密度を記述するポイントの量に割り当てられることが好ましく、前記限定イベントストリームは、イベントに対し異なるポイントの量を要求する少なくとも２つの限定イベントストリームに割り当てられる。
【００２１】
第１のタスクの前記起動は第２のタスクにより実行されることができ、これらの起動の時間相関は、イベントストリーム（出力される前記第１のタスクのイベントストリーム、入力される前記第２のタスクのイベントストリーム）によってもキャプチャ可能である。
【００２２】
少なくとも２つのリソースが前記システムに割り当てられることが好ましく、タスクの第１のグループが第１のリソースに割り当てられ、タスクの第２のグループが第２のリソースに割り当てられ、前記第１のグループの少なくとも２つのタスクがそれぞれ前記第２のグループのタスクを直接、もしくは複数のタスクを経由して起動する方法であって、
出力される前記第１のタスクのイベントストリームに対し、少なくとも限定イベントストリームを決定するステップ、
入力される前記第２のタスクのイベントストリームに対し、少なくとも第２のタスクに対する起動が第１のタスクにより直接実行されない限り、少なくとも限定イベントストリームを決定するステップ、
前記第２のタスクの、前記入力されるイベントストリームの前記限定イベントストリームを考慮して、前記第２のタスクにより結合的に要求されるコストを検出するステップ、
を有する。
【００２３】
少なくとも１つの前記第２のタスクの前記限定イベントストリームを決定するために、前記第１のタスクの前記限定イベントストリームが使用される。
【００２４】
前記タスクは、ＣＰＵ又は電気回路モジュールにより実行可能なユニットであることが好ましい。
【００２５】
一般的に、システムにおけるイベントストリームの量は、さらなる記述エレメント、好ましくは限定イベントストリームに割り当てられる。この限定イベントストリームにより、限定ストリームに割り当てられた全ての限定されたイベントストリームの互いに相関のある要求が記述される。例えばインターバル１０ｍｓに対し最大量である５つのイベントストリームが、イベントストリームＥＳ＿ＡおよびＥＳ＿Ｂが割り当てられた限定イベントストリームＥＳ＿ＡＢに割り当てられ、最大量とはイベントの最大量を示す場合、これは実際のシステムにおいて、ＥＳ＿ＡおよびＥＳ＿Ｂの下層のシミュレーションが、１０ｍｓのインターバルにおいて、５イベント以上を統合できないことを示している。このことは、例えば次のような場合に特に顕著である。任意の１０ｍｓにおけるＥＳ＿Ａに６つのイベントが割り当てられ、任意の（別の）１０ｍｓにおけるＥＳ＿Ｂに７つのイベントが割り当てられ、すなわち１インターバルにおけるＥＳ＿ＡおよびＥＳ＿Ｂの合計が限定イベントストリームＥＳ＿ＡＢの値を超えている場合である。限定イベントストリームは、そのようなインターバルが少なくとも１つ存在する場合にのみ有利である。もしいずれのインターバルにおいても、同一インターバルにおいて限定イベントストリームに割り当てられるイベントの合計が限定イベントストリームの値を超えない場合、この限定イベントストリームは、解析に対して効果を有しない。
【００２６】
最大イベントストリームに対する限定イベントストリームに対応して、最小イベント外リームに対する限定イベントストリームが設定されることがある。最小限定イベントストリームは、少なくとも１つのインターバルにおいて割り当てられるイベントストリームの数を超える場合のみ有利である。
【００２７】
限定イベントストリームにより記述される依存性の一例として、２つもしくはそれ以上のタスク、例えば結合実行リソースの間の競合から得られるものがある。各タスク単体について、タスクから出力されるイベントの最高可能密度、すなわちタスクが割り当てられたインターバルに対し、タスクから出力されるイベントストリームの最大値は、スケジューリング方法の結合実行リソースの最高可能比率を生成する。しかしながら、第２のタスクに結合実行リソースのそのような高い比率が割り当てられないことがよくある。これは第２のタスクの出力されたイベントストリームの最大ではない値がこれらのインターバルを発生させていることを意味している。こうして、出力された第１のタスクのイベントストリームおよび出力された第２のタスクのイベントストリームの最大値が一致しないことがよくある。この関係は、競合状態の観点から、個々に出力されたイベントストリームの最大の可能な一致度を記述する限定イベントストリームにより記述される。
【００２８】
限定イベントストリームは、時間インターバルに代えてイベント量やエネルギー量に合わせて設定されてもよい。これは、限定イベントストリームおよび割り当てられた限定イベントストリームは同種の値に基づくものにあるという点で重要である。
【００２９】
限定イベントストリームにおいて、例えば重み係数等の点の量は時間インターバルに割り当てられることがあり、その場合、どれだけの点が当該限定イベントストリームの１以上のイベントに費やされる必要があるかは限定イベントストリームの観点から決定される。費やされる点の量は、限定イベントストリームに割り当てられる異なる限定イベントストリームに対して異なる値になる。こうして、例えば異なる限定イベントストリームの別々のランク付けや、イベント毎の変数複雑度のモデル化が可能になる。
【００３０】
有利な実施形態においては、前述のメカニズムは特定の依存タイプに適用される。ここで、タスクの第１のグループは第１のリソースに割り当てられ、タスクの第２のグループは第２のリソースに割り当てられ、ここで第１のグループの少なくとも２つのタスクが、第２のグループの第１のタスクを、直接又はいくつかのタスク経由で、それぞれ起動する。以下のステップが必要とされる。
第１のタスクの出力されたイベントストリームに対する限定イベントストリームを少なくとも決定するステップ。
少なくとも第２のタスクに対する起動が直接行われない場合に、第２のタスクの入力されるイベントストリームに対する限定ストリームを少なくとも決定するステップ。
第２のタスクの入力されるイベントストリームの限定イベントストリームを考慮して第２のタスクの、結合所要コストを検出するステップ。
【００３１】
限定イベントストリームは、依存性を考慮した解析方法により自動的に検出することが可能であり、リアルタイム解析を実行するユーザにより設定されてもよい。
【００３２】
タスクが代替的にのみ起動可能な場合、限定イベントストリームにより記述可能な依存性は、別の種類のものである。これは、例えば所定のデータや、データの処理やさまざまなアクチュエータの制御を考慮した、代替物の選択を必要とする処理結果に応じて発生する。
【００３３】
このような代替物の他の例として、エンジン制御ユニットがある。ここでは、例えば次のイグニションポイントを適切に計算するために、さまざまな速度レンジにおいて、他のタスクが起動される。
【００３４】
これら代替のタスクのために限定イベントストリームを使用することで、実時間解析の全てのステップにおいて、ただ１つの代替物、例えば各場合における最も複雑なものが確実に考慮される。
【００３５】
詳細な記述が以下に示される。
【図面の簡単な説明】
【００３６】
【図１】いくつかの異なる依存性を有する分散システムの例を示す。
【図２】競合する依存性を記述する限定イベントストリームの例を示す。
【図３】競合するタスクに対する限定イベントストリームのインターバルの計算を示す。
【図４】限定イベントストリームを用いた、最悪条件における応答時間に対する優先タスクの寄与の計算を示す。
【図５】イベントストリームΘＦ，ΘＨ、およびΘＪのインターバルの改善のパーセンテージを示す。
【発明を実施するための形態】
【００３７】
世代が進むにつれて、組み込みシステムに対する要求は高まっている。例えば車は、世代を追うごとにより多くのソフトウエア機能を有し、その結果、組み込みシステムはより複雑化している。新型の車は、いくつものバスで接続された７０個に達するＥＣＵを有している。エンジンマネジメントシステムやエンジンシステム等、多くの機能は実時間制約が課せられている。
【００３８】
産業用ソフトウエア開発者により広く受け入れられた実時間解析において、タスクの最悪条件での応答時間に対する厳しい制約は重要なものである。連関するタスクセットの依存性を考慮することは、優れたアプローチである。本発明は、実時間解析において、異なるタイプの依存性を統合する新たな全体論的モデルを提供する。本発明に係る一般的なモデルは、優先度の固定されたシステムのスケジューラビリティ解析に統合することが可能である。
【００３９】
図１に、典型的な分散システムを示す。このシステムは２つのＣＰＵと、１つのＢＵＳを有する。この例では、各リソースに対する優先度スケジューリングが固定されているとする。このシステムは、プロセッサにおいて実行される８つのタスクおよびバスを有する。優先度は、図に示されるように割り当てられている。タスクの起動状態はイベントストリームΘで表現される。
【００４０】
図１のシステムを解析するためには、各タスクの最悪条件における応答時間を計算する必要がある。その一般的な方法としては、システムの起動状態を記述する全てのタスクおよびイベントストリームが互いに独立であると仮定する方法がある。これは、イベントが最悪条件における応答時間解析の間に最大密度で発生することを意味する。なぜならシステム内の対応関係が考慮されていないためである。実時間解析の結果は、タスク間の干渉が常に最大と仮定したものであり、非常に厳しい結果が得られる。
【００４１】
より厳しい応答時間制約を得るため、本発明では２つの依存性を導入する。第１の依存性は、同一のコンポーネントにより実行されるタスクが、該コンポーネントにおいて競合する状況を記述する、競合ベース依存性である。このような競合は、ここで示される状況のように、これらのタスクが互いに独立でないと仮定された場合に、特定のイベントが同一の密度では発生しないという影響がある。例えば、図１のΘＧとΘＨがこれに相当する。
【００４２】
第２の依存性が、異なるイベントストリームからのイベントは、互いにシフトされた時間において発生しなければならないことを記述するオフセットベース依存性である。例えばもし、図１のイベントストリームΘＢとΘＣについて考慮する場合、イベントストリーム間で相関が存在すると仮定される。この依存性を導入する目的は、本発明に係るアプローチの汎用性を示すことである。
【００４３】
導入されるこれら２つの依存性は、実時間解析に対するより厳しい制約を導き出す。そしてこれら２つの両者が組み込まれることが望ましい。従来の技術では、タスク間の依存性の記述のための汎用アプローチとしての全体論的モデルは存在しなかった。
【００４４】
以下に、後に議論される実時間解析に必要なモデルについて記述する。
【００４５】
タスクモデル：Γは１つのリソースΓ＝｛τ１，．．．，τｎ｝におけるタスクのａである。タスクはτ＝｛ｃ＋，ｃ−，Φ，Θ｝という４つの要素からなる集合である。ｃ＋は最悪条件での実行時間であり、ｃ−は最良条件における実行時間であり、Φはスケジューリングの優先度（数が小さくなれば優先度は高くなる）であり、Θはイベントストリームによるタスクの起動を示す。τｉｊをタスクτｉを実行するｊ番目のジョブとする。
【００４６】
タスクの各ジョブはその実行の最後にイベントを生成し、他のタスクに対する通知を行うと仮定する。
【００４７】
イベントストリームモデル：イベントストリームモデルは、イベント制約機能に対し、有効な汎用ノーテーションを生成する。
【００４８】
本発明においては、イベント制約機能η（Δｔ，Θ）は全てのインターバルΔｔに対して、長さΔｔの任意のインターバルのイベントストリームΘから生じるイベントの数の上界を生成する。このように、イベント制約機能は準追加的な機能であり、これはインターバルΔｔ，Δｔ’のそれぞれに対し、以下の条件（１）を適用することを意味する。
η（Δｔ＋Δｔ’，Θ）≦η（Δｔ，Θ）＋η（Δｔ’，Θ）      （１）
【００４９】
η（Δｔ，Θ），η（Δｔ’，Θ）は、任意のΔｔもしくはΔｔ’のなかで可能なイベント数の最大値を返す。Δｔ＋Δｔ’におけるイベントは、ΔｔもしくはΔｔ’において発生しなくてはならない。従ってこの条件は成立する。
【００５０】
本発明においては、イベントストリームΘはイベントエレメントΘの集合とも定義される。イベントエレメントのそれぞれは期間ｐとオフセットａにより与えられる（Θ＝（ｐ，ａ））。
【００５１】
実際のシステムにおいて最悪条件でのイベントの密度が不明である場合、密度の上界をイベントストリームの記述に使用できる。そして任意のイベントシーケンスのモデル化が可能である。そして準追加的条件が成立するイベントシーケンスのみが、有効なイベントストリームである。
【００５２】
イベントシーケンスΘおよびインターバルΔｔのイベント制約機能は以下のように示される。
2012518215.tif 000003
【００５３】
逆関数として以下のインターバル関数が定義され、これによりイベントの数およびイベントストリームに対し、これらのイベントが発生可能な最小インターバルが与えられる。
【００５４】
イベント数およびΘに対するインターバル関数は以下のように与えられる。
Δｔ＋（ｎ，Θ）＝ｍｉｎ｛Δｔ｜η（Δｔ，Θ）＝ｎ｝      （３）
【００５５】
イベントストリームのいくつかの例が、“Karsten Albers, Frank Bodmann, and Frank Slomka: Hierarchical event streams and event dependency graphs: A new computational model for embedded real-time systems. In ECRTS ’：06 Processings of the 18th Euromicro Conference on Real-Time Systems, pages 97-106, Washington, DC, USA, 2006. IEEE Computer Society”に示されている。（ここで参照することで包含されるとする。）
【００５６】
既に議論されてきた組み込み実時間システムを拡張するために、限定イベントストリームは以下のとおり記述される。
【００５７】
本発明においては、限定イベントストリームは、イベントストリームの集合に対しイベントの最大発生数を定義するイベントストリームと定義される。限定イベントストリームは、
2012518215.tif 000004
と定義される。Θは限定イベントストリームを記述し、
2012518215.tif 000005
は限定イベントストリームが成立するイベントストリームの集合を示す。限定イベントストリームは以下の条件を満たす。
2012518215.tif 000006
【００５８】
例１：イベントストリーム間に相関がなければ、
2012518215.tif 000007
と定義される。
【００５９】
例２：図１は、限定イベントストリームの例を示す。ΘＢ＝ΘＣ＝｛（２０，０）｝、およびこれら２つのイベントストリーム間のオフセットを１０ｔ．ｕと仮定する。イベントの累積的発生はイベントストリーム
2012518215.tif 000008
で記述される。イベントストリームが互いに独立と見なされれば、インターバルΔｔ＝５で２つのイベントが得られる。しかし限定イベントストリームは、インターバルΔｔにおいていくつの累積的イベントが発生しうるかを記述している。この依存性により、インターバルΔｔにおいて１つのイベントしか得られない。
【００６０】
次に、限定イベントストリームがいかにして算出されるかを記述する。
【００６１】
本発明においては、Δβ：Δｔ←ｎは、所与のイベントストリーム
2012518215.tif 000009
の関係から得られる、依存関係のある所与の数のイベントから、最小時間インターバルを割り当てる限定インターバル関数と定義される。そして限定イベントストリーム
2012518215.tif 000010
は、次式で決定される。
2012518215.tif 000011
【００６２】
なお、
2012518215.tif 000012
およびΔβ（ｎ）は、依存性のタイプに応じて具体的に数式化される抽象的数式である。
【００６３】
以下において、本発明に係る競合ベースの依存性が記述される。図１に、タスク間のこの種の依存性が例示的に記述される。タスクτ４およびτ５は同一のリソースにより実行される。これは、これらが当該リソースにおいて競合することを意味する。タスクτ４もしくはτ５の解析において行われる関連処理において、外部イベントストリームΘＧおよびΘＨは独立して考慮される。
【００６４】
図２は、競合依存性を記述する限定イベントストリームの例を示す。時間軸の上の矢印は入力されるイベントを示す。時間軸の下の矢印はタスクにより生成されるイベントを示す。ガントチャートのパート１では、競合しないタスクの場合が考慮されている。タスクの第１のジョブは、２つの外部イベントがほぼ同時に発生しうる形でスケジュールされている。次のイベントは第１ジョブの第１イベントの後、可能な限り早く生成される。独立である場合、次の２つのイベントは、ほぼ同時に発生する。しかしこれは、τ４およびτ５が同一のプロセッサにより実行されるためにジョブはタスク毎に実行されなければならないため、不可能である。これは下側のガントチャートに示されており、これはイベントの正確な発生を記述している。タスクの干渉があるため、外部イベントストリームの考慮を互いに独立に考慮したのでは不十分である。この干渉は限定イベントストリームによりモデル化が可能である。
【００６５】
図２に示されるように、２つの累積的外部イベントは同時に生成されうる。これは、より高い優先度を有するタスクは、第２のタスクに対し、その終了の直前に干渉するという事実に基づいている。その結果、２つのイベントはほぼ同時に発生する。これは、ｎ個のイベントが同時に発生しうるｎ個のタスクについてもあてはまる。
【００６６】
１個のタスクに対し、少なくとも（ｎ−１）・ｃ−個の実行要求がｎ個のイベントを生成するために実行される必要があると結論づけることができる。
【００６７】
限定イベントストリームを算出するために、ｎ個のイベント間の最小距離が、競合ベースの依存性について限定インターバルを定式化することによって決定される。
【００６８】
ΓＲが、同一のプロセッサを共有するｍ個のタスクの部分集合として規定され、
2012518215.tif 000013
をｎ個のイベントの分散の集合として規定する。ここで各タスクτｉ∈ΓＲがｎｉ個のイベントを生成し、限定インターバル関数は以下のように得られる。
2012518215.tif 000014
【００６９】
これは、ｎ個のイベントがより小さい距離で発生しうると仮定されることから証明される。このことは、最小の組み合わせの１つが、より短い距離の結果を生じさせることを意味する。その結果、インターバル関数Δｔ＋（ｎｉ，Θτｉ）もしくは
2012518215.tif 000015
は、より短い距離を生成する。インターバル関数Δｔ＋（ｎｉ，Θτｉ）がより短い距離を生成すると仮定すると、その結果、イベントがイベントストリームにおける定義よりも短い距離で発生する。しかしこれはイベントストリームの定義と矛盾する。従って、最良ケースの実行時間総計は、より短距離で発生しなければならない。このような状況は、考慮されている実行時間の１つが仮定に含まれるものより短い場合にのみ発生しうるが、これは、既に全てのタスクについて最良ケースの実行時間が規定されていることと矛盾する。
【００７０】
本発明では、ｎ個のイベントに対し、それらが発生する最小インターバルを提供する処理を導入する。この処理が図３に示される。本発明では、Δｔ＋（ｎ，Θ）を効率的に算出するためにイベントストリームの正規化が導入される。
【００７１】
図３において、アウターループが上の最小オペレーション（４行目から１０行目）により考慮される全ての組み合わせに渡って繰り返される。５行目は、各イベントストリームの全てのインターバルを、ｍａｘ（Δｔ＋（ｎｉ，Θτｉ））により実行されたと見なす。内部ループ（７行目から９行目）は、
2012518215.tif 000016
といった最良ケース実行時間により生成される最小距離を算出する。最後に、インターバルの最小値が決定され、ｎ個の累積的イベントが発生しうる最小インターバルが返される（１０行目）。
【００７２】
本発明に係るアプローチの汎用性を示すために、Rodolfo Pellizzoni and Giuseppe Lipari (Improved schedulability analysis of real-time transactions with earliest deadline scheduling. In RTAS ’05: Proceeding of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, pages 66-75, Washington, DC, USA, 2005. IEEE Computer Society; (ここで参照することで包含されるとする))による遷移モデルにおいて発生するオフセットに関する問題に適用する。このアプローチは動的オフセットもカバーするものであるが、ここでは例としてのタスクシュミレーション間の静的オフセットのみについて考慮する。
【００７３】
本発明において、オフセットａを有する２つの厳密な周期的タスクτ１およびτ２について、イベントτ１およびτ２の間の最小距離ａ‘のみを算出するものとする。この最小距離は、タスクのピリオドの最小公約数ｘ＝ｇｃｄ（ｐτ１，ｐτ２）を用いて、ａ’＝ｍｉｎ（ｍｏｄ（ａ，ｘ），ｍｏｄ（−ａ，ｘ））により算出される。そして以下に示す限定インターバル関数を参照する。
Δβ（ｎ）＝ｍｉｎ（Δｔ＋（ｎ，｛（ｐτ１，０），（ｐτ２，ａ′）｝），Δｔ＋（ｎ，｛（ｐτ１，ａ′），（ｐτ２，０）｝））      （５）
【００７４】
ここで、イベントストリームを
2012518215.tif 000017
経由で直接設定できる。ｍｏｄ（ａ，ｘ）≦ｍｏｄ（−ａ，ｘ）である場合、限定イベントストリームは
2012518215.tif 000018
である。ｍｏｄ（−ａ，ｘ）＜ｍｏｄ（ａ，ｘ）である場合、限定イベントストリームは
2012518215.tif 000019
である。タスクが２つ以上である場合にも、このアプローチは限定インターバル関数を計算するのに適用できる。
【００７５】
限定イベントストリームを使用するためには、実時間解析、特に最悪ケース応答時間解析に対し、新しい概念を適用する必要がある。限定イベントストリームを考慮する場合、インターバルΔｔにおけるタスクの最悪ケースのコントリビューションの大きさを決定しなければならない。
【００７６】
インターバルΔｔにおけるタスクの最大コントリビューションは、最大の最悪ケースにおけるタスクの実行が可能な限り発生した場合に発生し、そして限定イベントストリームまでの、最小の最悪ケースにおけるタスクの実行時間まで、可能な限り２番目に大きな実行時間を有するタスクは、他のさらなるタスクの発生を禁止すると仮定する。
【００７７】
このことは、この仮定により与えられるものとは別のディストリビューションが存在すると仮定することで証明されうる。従って、この仮定によるパターンに従わないイベントが少なくとも１つ存在する必要がある。タスクのコントリビューションを増すために、イベントは、最悪ケースの実行時間が仮定よりも大きいタスクをトリガーしなくてはならない。しかしこれは、最悪ケースの実行時間がより大きい全てのタスクに対し、既に呼び出しの最大数を仮定しているため、矛盾している。
【００７８】
応答時間解析は以下のように定義される。条件∀τ∈Γ：ｒ＋（τ）≦ｄτが成立する場合、タスクの集合は実行可能であって、実時間解析は成功する。イベントストリームを考慮した、タスクの最悪ケース応答時間は、以下のように算出される。
2012518215.tif 000020
【００７９】
優先度がより高いタスクにより生成される実行量は、イベント境界関数に最悪ケース実行時間を乗じることで算出される。不動点反復による方法により、最悪ケース応答時間は全てのジョブｋに対し算出できる。
【００８０】
2012518215.tif 000021
を組み込むために、図４のアルゴリズムが作成された。式６の残りの部分は変更されない。
【００８１】
このアルゴリズムは、考慮されているインターバルΔｔ、解析中のタスクのジョブナンバーｋ、検査対象であるタスクτ、必要な限定イベントストリームの集合
2012518215.tif 000022
、およびτより優先度が高い全てのタスクを有するΓＨＰを、パラメータとして持っている。このアルゴリズムはタスクをそれらの最悪ケースの実行時間でソートし（８行目）、全ての限定イベントストリームに対し、このストリームがΔｔ内で許容するイベントの最大量を蓄積する（９行目）。解析中のタスクτの呼び出し数は、対応する限定イベントストリームから必ず減じられる（１０行目）。ループ（１１行目から１６行目）では、優先度がより高い全てのタスクが考慮される。最悪ケースの実行時間が最も長いタスクが最初に考慮される。このアルゴリズムはタスクのイベントストリームにより該タスクに対する呼び出しの最大量を決定し（１２行目）、イベントストリームが存在すれば、その限界を決定する（１３行目）。これらの最小値はΔｔ内でのタスクの最大コントリビューションを算出するのに使用される（１４行目）。第２のループ（１５行目から１６行目）は、対応する限定イベントストリームを、使用されたイベントの分だけ減ずる。従って、これらのループはタスクに渡って、限定イベントストリームの量を分配する。この処理が、Δｔ内のより優先度の高いタスクの最悪ケースのコントリビューションを導き出す。
【００８２】
なお、応答時間解析の複雑さは依然、疑似多項的である。限定イベントストリームの算出の複雑さは、考慮されている依存性の種類による。競合ベースの依存性の問題の算出は、その複合的な複雑さにより困難なものになりうる。しかしながら解析は、この問題の影響を受けない。従って限定イベントストリームの上界を見出すことは、実行時間性能の向上を示唆するものである。
【００８３】
この新たなアプローチの意義が、以下の事例により示される。検査対象であるシステムは図１に示され、既に記述されている。表１はシステムのパラメータを示し、テーブル２はイベントストリームを示す。我々はこのシステムを、そのフォローが容易で、かつ新たな手順の全体を示されているため選択した。
2012518215.tif 000023
表１  図１に示される分散システムのパラメータ
【００８４】
システムのイベントストリームを算出するために、本発明では“Steffen Kollmann, Karsten Albers, and Frank Slomka. Effects of simultaneous stimulation on the event stream densities of fixed-priority systems. In Spects ’08: Proceedings of the International Simulation Multi-Conference. IEEE, June 2008”(ここで参照することで包含されるとする)により示されるアプローチを使用してもよい。結果として得られるシステムのイベントストリームは表２に示される。これにより、依存性を用いて算出されたイベントストリームと、依存性を用いずに算出されたイベントストリームとの比較を行う。イベントストリームΘＢとΘＣの間の静的オフセットを１００ｔ．ｕ．と仮定する。
2012518215.tif 000024
表２  分散システムの全てのイベントストリーム。結果は、本アプローチの適用および非適用のうえで算出される。
【００８５】
依存性の有る外部イベントストリームを決定するには、システムの限定イベントストリームを算出する必要がある。我々は２つのイベントストリーム
2012518215.tif 000025
および
2012518215.tif 000026
のみについて考慮する。
2012518215.tif 000027
はΘＢとΘＣとの間のオフセットを記述する。
2012518215.tif 000028
はΘＧとΘＨとの間の競合ベースの依存性を記述する。
2012518215.tif 000029
表３  算出された限定イベントストリームの結果
【００８６】
イベントストリームの算出後、システム解析の改善点をより詳細に確認した。まず、いくつかのイベントストリームおよびシステムの密度の改善を確認した。これについては表４および図５に示す。
2012518215.tif 000030
表４  イベントストリームΘＦ，ΘＨ，およびΘＪに対するアプローチの改善を示す。Θは依存性を考慮したインターバルを示し、Θ‘は依存性を考慮しないインターバルを示す。改善は％で示す。
【００８７】
依存性は、イベントストリームの密度に影響を有するのみならず、最悪ケースの応答時間にも直接的に影響を及ぼす。タスクτ３の最悪ケースの応答時間は、１５０ｔ．ｕ．から８０ｔ．ｕ．に減少している。このことは、依存性を考慮した解析の結果は、この場合、依存性を考慮しない解析の結果に比較して４６．６６％厳しいものであることを意味している。タスクτ６は、依存性を考慮しない場合２５５ｔ．ｕ．、依存性を考慮した場合２０５ｔ．ｕ．の最悪ケースの応答時間を有し、すなわち最悪ケースの応答時間において１９．６％減少している。
【００８８】
この例は、依存性が実時間解析を改善することを示している。これにより我々は汎用的なアプローチにおいて、異なる依存性がいかに容易に組み合わせられるかを示した。
【００８９】
本発明は、分散実時間システムにおけるタスク依存性に対する全体論的モデルを実現する可能性を提供する。新たなアプローチは、固定優先度システムに適用された。２種の依存性が記述され、これらが新たに定義された限定イベントストリームによりどのように記述されるか示された。これにより、新たな種類の依存性が導入された。その効果として、本発明は実時間解析から依存性の複雑さを取り除いた。
【００９０】
本発明は、図面および上記記述により詳細に示され記述された。これらの説明および記述は、例示的なものもしくは一例であって、限定的なものではない。そして後述する請求項の範囲で、通常の技術による変更や改良が行われてもよいことが理解されるべきである。特に本発明は、上記および後述される別の実施形態の特徴の組み合わせが付されたさらなる実施例をも含む。
【００９１】
さらに、請求項において「有する」という語は、他の要素やステップを除外するものではなく、英文請求項における不定冠詞「ａ」「ａｎ」は複数であることを除外するものではない。単一のユニットが、クレームで言及されている複数の特徴の機能を満たしていてもよい。また、英文請求項において特に属性や数値と組み合わせて使用される「essentially （実質的に）」「about （おおよそ）」「approximately （約）」等の語は、厳密なその属性、もしくは厳密なその値をそれぞれ含む。クレーム内のあらゆる参照符号は、発明の範囲を限定するものとして解釈されるべきではない。
【図１】
2012518215.tif 000031
【図２】
2012518215.tif 000032
【図３】
2012518215.tif 000033
【図４】
2012518215.tif 000034
【図５】
2012518215.tif 000035
【手続補正書】
【提出日】平成22年12月14日(2010.12.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
システム、特にさまざまなタスクが設けられたコンピュータシステムの実時間を解析するための、コンピュータに組み込まれる方法であって
前記タスクは繰り返し実行され、
タスクの実行は、前記タスクの起動によりトリガーされ、これは前記タスクのイベントを示し、
複数の記述的エレメントが前記イベントの時間相関をイベントストリームとして記述するために設けられ、
前記イベントストリームは前記イベントの最大時間密度および／又は最小時間密度を検出することができ、
少なくとも、イベントストリームの量が割り当てられ、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の時間相関を記述するさらなる記述的エレメントを有することを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、
前記少なくとも１つのさらなる記述的エレメントが限定イベントストリームを記述することを特徴とする方法。
【請求項３】
請求項１又は２に記載の方法であって、
前記さらなる記述的エレメントもしくは限定イベントストリームの少なくとも１つが、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の最大時間相関を記述し、
少なくとも時間インターバル（ｄｔ）において前記限定イベントストリームにより許容されるイベントの量である時間インターバル（ｄｔ）のイベント量が、ｄｔにおいて非限定イベントストリームにより許容されるイベントの総量より少ないことを特徴とする方法。
【請求項４】
請求項１、２、３のいずれかに記載の方法であって、
前記さらなる記述的なエレメント又は限定イベントストリームの少なくとも１つが、少なくとも２つのイベントストリームによりキャプチャされるイベント全体の最小時間相関を記述し、
少なくとも時間インターバル（ｄｔ）に対し、ｄｔにおいて前記限定イベントストリームにより許容されるイベントの量が、ｄｔにおいて前記非限定イベントストリームにより許容されるイベントの量を上回ることを特徴とする方法。
【請求項５】
先に記載された請求項のいずれかに記載の方法であって、
前記システムには少なくとも１つのコンポーネント又はリソースが割り当てられ、前記コンポーネントの少なくとも１つには少なくとも２つのタスクが割り当てられることを特徴とする方法。
【請求項６】
先に記載された請求項のいずれかに記載の方法であって、
少なくとも２つのタスクが１つのグループに含まれ、グループの前記タスクはリソースに割り当てられ、前記リソースにおいて競合する前記タスクもしくはこのグループのタスクは、異なる時間においてのみ前記リソースにおける処理を行い、前記システムは前記リソースが前記グループの所定のタスクに割り当てられる時間点を決定する方法を有することを特徴とする方法。
【請求項７】
先に記載された請求項のいずれかに記載の方法であって、
前記限定イベントストリームの少なくとも１つが少なくとも２つの限定イベントストリームに割り当てられ、それらはそれぞれ異なるタスクを起動し、
これらのタスクは少なくとも１つの結合グループに割り当てられ、
コストがそれぞれ、１つのイベントのための前記タスクによる前記リソースの一時的な使用をキャプチャする前記タスクに割り当てられ、
さらに、
前記タスクにより結合して要求される前記コストを決定するステップ、を有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記割り当てられたイベントの量を考慮して前記限定イベントストリームの残りの結果を決定するステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれぞれ割り当てられるイベントの量から全体コストを検出するステップ、を有することを特徴とする方法。
【請求項８】
請求項１に記載の方法であって、
前記限定イベントストリームの少なくとも１つが少なくとも２つの限定イベントストリームに割り当てられ、それらはそれぞれ異なるタスクを起動し、
これらのタスクは少なくとも１つの結合グループに割り当てられ、
タスクもはそれぞれ、前記タスクによる１イベントそれぞれに対するリソースの一時的な使用を検出する各コストに割り当てられ、
さらに、
前記タスクにより結合して要求される前記コストを決定するステップ、を有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記割り当てられたイベントの量を考慮して前記限定イベントストリームの残りの結果を決定するステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定されるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれぞれ割り当てられるイベントの量から全体コストを検出するステップ、を有することを特徴とする方法。
【請求項９】
請求項７又は８に記載の方法であって、
少なくとも２つのイベントストリームに、２つの異なる限定イベントストリームが割り当てられ、さらに、
前記タスクにより結合して要求される前記コストを決定するステップを有し、
該ステップは、
限定イベントストリームの前記イベントを最も高いコストを有する前記タスクに割り当てるステップであって、ここで割り当てられる前記イベントの量が、前記タスクを起動する前記イベントストリームにより限定され、イベントの最小量はそれぞれ前記限定イベントストリームにより許容されるものであるステップ、
前記限定イベントストリームの残りのイベントを決定するステップであって、実際に割り当てられたイベント量が考慮されるステップ、
前記限定イベントストリームの前記残りのイベントを次に高いコストを有する前記タスクに割り当てるステップであって、次に、前記割り当てられるイベントの量が前記タスクを起動する前記イベントストリームにより限定され、他の限定イベントストリームが前記タスクに割り当てられるステップ、
前記ステップを前記限定イベントストリームの全てのイベントが割り当てられる、もしくはイベント量が前記グループの全てのタスクに割り当てられるまで繰り返すステップ、
個々のタスクのコストおよびそれらにそれぞれ割り当てられるイベントの量から全体コストを決定するステップ、を有することを特徴とする方法。
【請求項１０】
先に記載された請求項のいずれかに記載の方法であって、
前記限定イベントストリームが、時間インターバルにおけるイベントの密度を記述するポイントの量に割り当てられ、前記限定イベントストリームは、イベントに対し異なるポイントの量を要求する少なくとも２つの限定イベントストリームに割り当てられる
ことを特徴とする方法。
【請求項１１】
先に記載された請求項のいずれかに記載の方法であって、
第１のタスクの前記起動が第２のタスクにより実行されることができ、
これらの起動の時間相関は、イベントストリーム（出力される前記第１のタスクのイベントストリーム、入力される前記第２のタスクのイベントストリーム）によってもキャプチャ可能であることを特徴とする方法。
【請求項１２】
先に記載された請求項のいずれかに記載の方法であって、
少なくとも２つのリソースが前記システムに割り当てられ、
タスクの第１のグループが第１のリソースに割り当てられ、タスクの第２のグループが第２のリソースに割り当てられ、
前記第１のグループの少なくとも２つのタスクがそれぞれ前記第２のグループのタスクを直接、もしくは複数のタスクを経由して起動する方法であって、
出力される前記第１のタスクのイベントストリームに対し、少なくとも限定イベントストリームを決定するステップ、
入力される前記第２のタスクのイベントストリームに対し、少なくとも第２のタスクに対する起動が第１のタスクにより直接実行されない限り、少なくとも限定イベントストリームを決定するステップ、
前記第２のタスクの、前記入力されるイベントストリームの前記限定イベントストリームを考慮して、前記第２のタスクにより結合的に要求されるコストを検出するステップ、
を有することを特徴とする方法。
【請求項１３】
請求項１２に記載の方法であって、少なくとも１つの前記第２のタスクの前記限定イベントストリームを決定するために、前記第１のタスクの前記限定イベントストリームが使用されることを特徴とする方法。
【請求項１４】
先に記載された請求項のいずれかに記載の方法であって、
前記タスクは、ＣＰＵ又は電気回路モジュールにより実行可能なユニットであることを特徴とする方法。
【国際調査報告】
2012518215.tif 000036