JP6218645B2 - プログラム解析装置及びプログラム解析方法及びプログラム - Google Patents

Description

本発明は、タスクの実行時間の算出に関する。

多くの組込システムでは予め定められた時間（デッドライン）内で処理を完了する必要のあるリアルタイムタスクと、そうでない非リアルタイムタスクが存在する。
システム開発ではタスクの実行時間がデッドラインを超えないよう、タスクの最悪実行時間を算出してデッドラインを超えないことを確認している。

従来の実行時間を算出する方法として、（１）プログラムコードを静的解析してプログラムの実行経路を解析し、各実行経路の実行時間から最長の実行時間を見積もる方法と、（２）プログラムを実機またはシミュレーションによって動的に実行させて実行時間を計測する方法がある。

上記（１）の方法ではプログラムの全ての実行経路を計算しているため算出漏れがない。
しかし、プログラムの正確な実行時間を見積もるためには命令の実行数だけでなく、キャッシュヒット率やメモリ、Ｉ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）アクセス時間等、Ｈ／Ｗ（Ｈａｒｄｗａｒｅ）の挙動を考慮する必要がある。
上記（２）の方法ではＨ／Ｗの挙動も考慮することで、より正確な実行時間を算出することができるが、実行時間が最悪となる実行経路を実行しているかわからない。

特許文献１では、プログラムを解析して実行経路を出力し、各実行経路の実行時間をＨ／Ｗの挙動を考慮して算出し、限界実行時間（最悪実行時間あるいは最良実行時間）を算出している。

国際公開ＷＯ２０１３−１２８５１９号公報

しかし近年、組込システムでもキャッシュメモリが搭載されるようになり、メモリアクセス性能が向上するようになった一方で、実行時間がキャッシュミス率により変動するため、最悪実行時間の見積もりが困難となっている。
キャッシュミス率は自身のタスクの実行だけでなく、他のタスクの実行によっても影響される（正確には自身あるいは他の実行されるタスクの命令あるいはデータの配置（アドレス）によってキャッシュミス率が変わる）。
また、異なる実行優先度のリアルタイムタスクが複数存在し、優先度の高いリアルタイムタスク（Ａ）が優先度の低いリアルタイム（Ｂ）の実行を中断させて実行するようなシステムも存在する。
この場合、優先度の低いリアルタイムタスク（Ｂ）の実行中断中に、キャッシュメモリに優先度の高いリアルタイムタスク（Ａ）の命令またはデータが格納されることで、優先度の低いリアルタイムタスク（Ｂ）の命令またはデータが追い出されることがある。
リアルタイムタスク（Ｂ）が処理再開後にキャッシュメモリから追い出された命令またはデータを参照しようとした場合、キャッシュミスが発生するためメモリアクセス時間が増加する。
そのため、リアルタイムタスク（Ｂ）の実行時間は処理が途中で中断されなかった場合に比べて実行時間が増加する場合がある。

特許文献１では上記のようにタスクの実行優先度を考慮した実行時間を算出を行っていないため、優先度の低いリアルタイムタスクが他の優先度の高いリアルタイムタスクによって処理が割り込まれたことを考慮した、正確なタスクの実行時間を見積もることができないという課題がある。

この発明は、上記のような課題を解決することを主な目的とし、タスクの実行時間を正確に算出することを主な目的とする。

本発明に係るプログラム解析装置は、
複数のタスクが生成される、複数のブロックで構成されたプログラムを解析し、タスクごとに、タスクにおいて実行されるブロック群を実行順に実行パスとして抽出する実行パス抽出部と、
前記プログラム実行時のタスクの生成順序に従って、各タスクに対応する実行パスを配列させるとともに、実行パスの組合せを変化させて複数の配列パターンを生成する配列パターン生成部と、
配列パターンごとに、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出する実行時間算出部とを有することを特徴とする。

本発明によれば、プログラム実行時のタスクの生成順序に従って実行パスを配列した配列パターンごとに、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出するため、タスクの実行時間を正確に算出することができる。

実施の形態１に係る最悪実行時間判定システムの構成例を示す図。 実施の形態１に係る実行対象Ｓ／Ｗのリアルタイムタスクの処理例を示す図。 実施の形態１に係る実行パスリストの例を示す図。 実施の形態１に係るタスクスケジュールの例を示す図。 実施の形態１に係る配列パターンの例を示す図。 実施の形態１に係るタスクスケジュールの例を示す図。 実施の形態２に係る最悪実行時間判定システムの構成例を示す図。 実施の形態２に係る実行パスリストの例を示す図。 実施の形態２に係るシミュレーション対象の配列パターンを決定する方法を示す図。 実施の形態１及び２に係る最悪実行時間判定システムのハードウェア構成例を示す図。

実施の形態１．
本実施の形態では、異なる優先度のリアルタイムタスクが存在するシステムにおいて、優先度の低いタスクが優先度の高いタスクの影響も考慮した最悪実行時間をより高精度に算出し、デッドラインを超えるかどうかをより正確に判定する構成を説明する。

図１は、本実施の形態に係る最悪実行時間判定システム１０００の構成例を示す。
図１において、実行対象Ｓ／Ｗ記憶部１０は、リアルタイムタスクがデッドラインを超えるかどうかを判定する実行対象Ｓ／Ｗ（Ｓｏｆｔｗａｒｅ）を記憶する。
実行対象Ｓ／Ｗでは、２つ以上のリアルタイムタスクが存在し、各タスクに優先度が設定されている。

実行パス解析部２０は、実行対象Ｓ／Ｗを解析し、実行対象Ｓ／Ｗから各リアルタイムタスクの実行パスを算出する。
実行対象Ｓ／Ｗは、複数のブロックから構成されるプログラムであり、実行パスは、実行対象Ｓ／Ｗにおけるタスクごとの実行経路であり、タスクにおいて実行されるブロック群を実行順に連結したシークエンスである。
実行パス解析部２０は、実行パス抽出部の例に相当する。

実行パスリスト記憶部３０は、実行パスリストを記憶する。
実行パスリストは、実行パス解析部２０によって算出されたタスクごとの実行パスのリストと、各パスを実行するための条件を表す情報である。

タスクスケジュール記憶部６０は、タスクスケジュールを記憶する。
タスクスケジュールは、対象のシステムのタスクの実行スケジュール情報である。
タスクスケジュールには、タスクの生成順序が記述されるとともに、タスクごとに上限の実行時間であるデッドライン（上限時間）が記述されている。
タスクスケジュールは上限時間情報の例に相当する。
また、タスクスケジュール記憶部６０は、上限時間情報記憶部の例に相当する。

実行パス組み合わせ決定部４０は、実行パスリストとタスクスケジュールからシミュレーションする実行パスの組み合わせを決定する。
より具体的には、実行パス組み合わせ決定部４０は、タスクスケジュールに示されるタスクの生成順序に従って、各タスクに対応する実行パスを配列させるとともに、実行パスの組合せを変化させて複数の配列パターンを生成する。
実行パス組み合わせ決定部４０は、配列パターン生成部の例に相当する。

実行時間算出部１００は、実行パスの組合せである配列パターンごとに、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出する。
実行時間算出部１００は、シミュレーション部５０、変数操作部７０及びキャッシュ無効化部８０で構成される。

シミュレーション部５０は、実行対象Ｓ／Ｗのプログラムをシミュレーション実行するシミュレータである。
シミュレーション部５０は、実行対象Ｓ／Ｗの実行環境を模擬して、実行対象Ｓ／Ｗの実行時間を算出する。
シミュレーション部５０にはキャッシュメモリの動作をシミュレーションするキャッシュシミュレータも備えている。

変数操作部７０は、シミュレーション部５０にて実行パス組み合わせ決定部４０で組み合わせた実行パス通りにシミュレーションを行うために、シミュレーション中の変数値を操作する。

キャッシュ無効化部８０は、シミュレーション部５０の実行中の任意のタイミングにてシミュレーション部５０に備えるキャッシュシミュレータ内のデータを無効化する。

最悪実行時間判定部９０は、シミュレーション部５０にて実行対象Ｓ／Ｗを実行した結果、リアルタイムタスクがデッドラインを超えるかどうかを判定する。

各機能ブロックは１つあるいは複数のプログラムとして実装されていてもよいし、複数の機能ブロックが１つのプログラムとして実装されていてもよい。
実行対象Ｓ／Ｗは１つまたは複数のプログラムの実行ファイルとして存在してもよいし、メモリ上に展開されたプログラムでもよい。
実行パスリスト、タスクスケジュールはファイルとして存在してもよいし、メモリ上にのみ配置されるデータであってもよい。

次に動作について説明する。

まず、実行パス解析部２０にて実行対象Ｓ／Ｗの各タスクの実行パスのリストを算出する。
実行パスの算出例について図２のフローチャートを用いて説明する。

図２は、あるリアルタイムタスクの処理を示すフローチャートである。
図２の各ブロックは１つ以上の命令を表し、ブロック２、ブロック４は分岐命令を表し、本例ではそれぞれの成立条件をＸ＜０、Ｙ＝１とする。
このとき、タスクの実行パスは以下の３通りが考えられ、それぞれの実行パスが実行される条件は（）に記載したものとなる。
・ブロック１→ブロック２（Ｘ＜０）
・ブロック１→ブロック２→ブロック３→ブロック４→ブロック５（Ｘ＞＝０かつＹ≠１）
・ブロック１→ブロック２→ブロック３→ブロック４→ブロック６→ブロック５（Ｘ＞＝０かつＹ＝１）
従って、図２に示したタスクから得られる実行パスリストは図３のようになる。
図３では分岐条件をＸ＜０のように値の範囲で示したが、Ｘ＝−１のように条件が成立する任意の値を条件として記述してもよい。
全てのリアルタイムタスクについて上記手順を行い、各リアルタイムタスクの実行パスを算出する。

次に、実行パス組み合わせ決定部４０の動作について説明する。
実行パス組み合わせ決定部４０は、実行パス解析部２０で算出した実行パスリストをタスクスケジュールに基づいてシミュレーション実行する実行パスの組み合わせ（配列パターン）を決定する。
タスクスケジュールは、タスクの実行スケジュールを示す情報であり、リアルタイムタスクの各タスクの実行周期とデッドライン、実行優先度が格納されている。

本実施の形態の実行対象Ｓ／Ｗが動作するシステムのタスクの実行スケジュール例を図４に示す。
タスクＡ、タスクＢは、いずれもリアルタイムタスクであり、デッドラインは次のタスク実行の開始までとする。
タスクＡ、タスクＢは、いずれも予め決められた実行周期のタイミング（タスクＡはＴ１、Ｔ３、Ｔ６、タスクＢはＴ１、Ｔ６）で実行される。
図４の例では、タスクＡの実行周期はタスクＢの実行周期の半分であり、かつ、実行優先度はタスクＡのほうが高い。
そのため、タスクＢの実行中にタスクＡの実行開始タイミングとなると、プロセッサはタスクＢの実行を一時中断し、タスクＡの処理を行う（Ｔ３〜Ｔ４のタイミングが該当）。
その後、タスクＡの処理が完了するとタスクＢの処理を再開する（Ｔ４のタイミング）。

実行パスの組み合わせでは、全てのリアルタイムタスクの実行周期の最小公倍数となる期間のタスクのスケジュールを行う。
本例ではタスクＡとタスクＢの実行周期が１：２のため、タスクＡが２回、タスクＢが１回実行される場合のタスクの組み合わせを行う。

実行パス解析部２０は、算出した実行パスリストから、タスクＡの実行パスがＡ１、Ａ２、Ａ３の３通り、タスクＢの実行パスがＢ１、Ｂ２の２通りあったとすると、実行パスの組み合わせは、図５に示す１８通りが考えられる。
つまり、図４のタスクＡとタスクＢの生成順序に沿って、各タスクに対応する実行パスを配列させるとともに、実行パスの組合せを変化させて１８通りの配列パターンを生成する。
そして、シミュレーション部５０が、この１８通りの配列パターンのそれぞれの実行パスの組み合わせについてシミュレーションを実行し、実行時間を算出する。

次に、シミュレーション部５０にて実行時間を算出する動作を説明する。
シミュレーション部５０は、図５に示した１８通りの実行パスの組み合わせを１つずつ実行し、実行時間を算出する。
シミュレーション部５０は、実行対象Ｓ／Ｗを実行するためのシミュレータであり、実行対象Ｓ／Ｗが動作するシステム（ターゲットシステム）のハードウェア構成（特にキャッシュメモリのエントリの競合）を模擬し、ターゲットシステムのハードウェア仕様に基づいた命令実行時間や、キャッシュミスによるミスペナルティを考慮した実行時間を考慮して実行対象Ｓ／Ｗを実行するものとする。
このようなシミュレータは参考文献１などによって既に考えられている。
図４のようにシミュレーション部５０がタスクＡ、タスクＢをそれぞれの実行周期（タイミング）と優先度に基づいて実行する方法としては、シミュレーション部５０に備わっているターゲットシステムによるハードウェアタイマに基づいた割り込みや、実行対象Ｓ／Ｗを実行する、あるいは実行対象Ｓ／Ｗに含まれるＯＳ（Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ）によって実現する方法があり、いずれもシミュレーション部５０によるシミュレーション環境構築時に容易に実装することができる。
参考文献１：特開２０１３−２２２３９２号公報

シミュレーション部５０が指定した実行パスの組み合わせを実行するようにするために、変数操作部７０は各タスクの実行開始時（図４のようなタスクスケジューリングの場合はＴ１、Ｔ２、Ｔ３のタイミング）に各パスの実行条件が成立するようにシミュレータ内の変数値を変更する。
例えばタスクＡの実行パスＡ１〜３が図３のＮｏ．１〜３にそれぞれ対応し、図５のＮｏ．３の実行パスの組み合わせ（すなわちＡ１→Ｂ１→Ａ３）を実行する場合、変数操作部７０は図４のＴ１のタイミングでＸ＝−１を設定し、Ｔ３のタイミングでＸ＝０、Ｙ＝１を設定する。
また、タスクＢの実行パスの実行条件がタスクＡの実行パスの実行条件と同じ変数を使用する場合（例えばタスクＢがＢ１を実行する条件がＸ＝２の場合）は、タスクＢが再開するタイミング（図４の場合はＴ４のタイミング）において、再度変数の値を設定する。

キャッシュ無効化部８０は、シミュレーション部５０が実行を開始する時にシミュレーション部５０の内部に存在するキャッシュメモリ（の動作を模擬するモデル）の全てのエントリを無効化し、キャッシュにデータが何も存在していない状態にする。
これにより、シミュレーション開始時はキャッシュメモリにタスクＡの命令およびデータが存在しないため、その実行パスにおける最悪実行時間を算出することができる。

また、キャッシュ無効化部８０はシミュレーション開始時だけでなく、非リアルタイムタスクが動作する可能性のあるタイミングでもキャッシュメモリの全てのエントリを無効化する。
例えば図６のようにタスクＢがタスクＡの２回目の実行開始タイミングであるＴ１３よりも前のＴ１２のタイミングで処理を完了した場合、キャッシュ無効化部８０は２回目のタスクＡの実行開始タイミングであるＴ１３でもシミュレーション部５０の内部に存在するキャッシュメモリの全てのエントリを無効化する。
これはＴ１２からＴ１３の間に非リアルタイムタスクが動作する可能性があるためであり、非リアルタイムタスクの実行により、タスクＡのどのキャッシュデータが追い出されるか（あるいは全く追い出されないか）は実行される非リアルタイムタスクのプログラムによって変わってくるため、全てのキャッシュデータが追い出される、最悪の実行時間を算出するためである（シミュレーション部５０はＴ１２からＴ１３のときに非リアルタイムタスクのシミュレーションすることはしない）。
これにより、Ｔ１２からＴ１３の間に非リアルタイムタスクが動作し、リアルタイムタスクＡのデータが追い出されることを考慮した最悪実行時間を算出することができる。

以上のように、キャッシュ無効化部８０は、シミュレーション実行開始時またはリアルタイムタスクの実行の合間すなわち、非リアルタイムタスクが実行される可能性のあるタイミングでキャッシュメモリの全てのエントリを無効化する。

シミュレーション部５０は組み合わせを実行したときの各タスクの実行完了時刻を算出する。
例えば、図４の場合、タスクＡ（１回目）の実行完了時刻はＴ２、タスクＢの実行完了時刻はＴ５、タスクＡ（２回目）の時刻完了時刻はＴ４となる。

最悪実行時間判定部９０は、シミュレーション部５０が出力した実行完了時刻とタスクスケジュールから、タスクの実行パスの組み合わせによる各リアルタイムタスクの実行時間がデッドラインを超えないかを確認する。
具体的には、図４の場合であれば、タスクＡ（１回目）の実行完了時刻が２回目のタスクＡの実行完了時刻であるＴ３を超えていないこと、タスクＢ、タスクＡ（２回目）の実行完了時刻が次のタスクＢ、タスクＡの実行開始時刻であるＴ６を超えていないことを確認し、いずれかのタスクの実行完了時刻がデッドラインを超えていた場合は、実行対象Ｓ／Ｗはデッドラインを超えると判定する。

実行パス組み合わせ決定部４０にて算出した全ての実行パスの組み合わせについて最悪実行時間判定部９０がデッドラインを超えないと判定した場合は、実行対象Ｓ／Ｗはターゲットのシステムの上でデッドラインを超えないということができる。

以上が実施の形態１の動作である。

＜実施の形態１の効果＞
以上のように、本実施の形態では、実行パス解析部２０にて実行対象Ｓ／Ｗの全ての実行パスを解析した後、タスクスケジュールに記しているタスクの実行スケジュールに合わせてシミュレーションを行って実行時間を算出する。
このため、優先度の低いタスクＢの実行時間は優先度の高いタスクＡによる処理の中断による影響を考慮した実行時間を算出されることから、優先度の低いタスクＢがデッドラインをミスするかをより正確に判定することができる。

＜実施の形態１の変形例＞
本実施の形態では、全ての実行パスの組み合わせをシミュレーションし、各実行パスの組み合わせの実行時間がデッドラインを超えないことを判定するようにしたが、最悪実行時間判定部９０がデッドラインを超えると判断した場合は、実行対象Ｓ／Ｗがデッドラインを超えることが既に確認できているため、以降の実行パスの組み合わせのシミュレーションを実行せずに終了してもよい。
これにより、判定時間を短縮することができる。

また、本実施の形態では、シミュレーション部５０にて実行する実行パスの組み合わせの順番について記載していないが、実行パス解析部２０にて解析した実行パスの長いものを組み合わせたものから実行してもよい。
この場合、デッドラインを超える可能性の高いパスからシミュレーション実行していくので、早期にデッドラインを超えると判定される可能性がある。
このとき、先ほど説明したように、デッドラインを超えると判定されると以降のシミュレーション実行を行わずに終了すれば、判定時間をさらに短縮することができる。

ここでいう実行パスの長いものとしては、命令数の多いもの、メモリやＩ／Ｏのアクセス回数の多いもの（あるいはアクセス時間が長いもの）、命令数とメモリ、Ｉ／Ｏのアクセス時間の両方を考慮したものなどが挙げられる。
また、これらのほかにシミュレーション部５０を用いて各実行パス単体を実行したときの実行時間を算出し、その時間が長いものを実行パスの長いものとしてもよい（実施の形態２に記載）。

実施の形態２．
以上の実施の形態１では、実行パス解析部２０で算出したタスクごとの実行パスについて、タスクスケジュールに記載されているタスクの実行スケジュールに合わせた総組み合わせを実施する。
しかし、一般的にタスクごとの実行パスは多数（数十〜数百以上）存在し、そのパスをタスクの実行スケジューリングに合わせて組み合わせたときの総組み合わせ数は膨大となり、全てをシミュレーションして実行時間を算出するのは現実的ではない。
そこで、実行パスの組み合わせを決定する数を削減する実施の形態を示す。

図７は本実施の形態に係る最悪実行時間判定システム１０００の構成例を表す。
図１と同じ構成、動作を行うものについては同じ番号を振り、説明は省略する。

実施の形態２では実行パスリスト記憶部３１で記憶する実行パスリストに格納する情報が一部追加され、実行パス組み合わせ決定部４１の動作内容が異なる。
本実施の形態に係る実行パスリストを、以下では、実行パスリスト３１０と表記する。
図７では流れの説明上、２つの実行時間算出部１００が存在しているが、同一のものを想定している。

実施の形態２で実施の形態１と異なる点について説明する。

実行の形態２では、まず実行パス解析部２０にて実施の形態１と同様に実行パスのリストを算出したのち、実行時間算出部１００が、各実行パスを単体で実行したときの実行時間を算出する。
このとき、実行時間算出部１００にあるキャッシュ無効化部８０がシミュレーション部５０の内部にあるキャッシュメモリを無効状態にして実行し、常にキャッシュメモリの先にあるメインメモリからデータを取得したときの各実行パスの実行時間を算出する。
これにより、最悪の実行時間を算出することができる（実際はキャッシュメモリが有効になっているので、この時間ほど悪くなることはない）。

実行パスリスト３１０には、図８のようにキャッシュの実行パスとその実行パスを実行するための実行条件に加え、実行時間算出部１００で算出した各パスの実行時間が格納される。

実行パス組み合わせ決定部４１は実施の形態１同様、実行パスリスト３１０に格納されている実行パスとタスクスケジュールに基づいて、実行パスの組み合わせを行う。
その上で、組み合わせの中から、デッドラインを超える可能性のある実行パスの組み合わせを抽出してシミュレーション部５０で実行時間の算出を行う。

デッドラインを超える可能性のある実行パスの組み合わせの抽出方法を図９の例を用いて説明する。
例ではタスクＡとタスクＢのリアルタイムタスクが図４と同じ実行スケジュールで実行される。
タスクＡの実行周期は５０ｍｓ、タスクＢの実行周期が１００ｍｓとする。
また、タスクＡはＡ１、Ａ２、Ａ３の３種類、タスクＢはＢ１、Ｂ２の２種類の実行パスが存在し、それぞれの単体の実行時間はＡ１、Ａ２、Ａ３が５ｍｓ、２０ｍｓ、６０ｍｓ、Ｂ１、Ｂ２は３０ｍｓ、７０ｍｓであったとしている。
このとき、タスクＡとタスクＢの実行スケジュールに応じた実行パスの組み合わせは図９の１８通りになる。
ここで、実行パス組み合わせ決定部４１は、組み合わせた１８通りに対するそれぞれの単体の実行時間の合計を算出し、実行時間の合計がタスクの実行パスの組み合わせを行ったスケジューリング期間（ここでは１００ｍｓ）を超えるものに対してシミュレーション部５０にて実行時間を算出する。
図９ではＮｏ．６、９、１１、１２、１４、１５、１６、１７、１８の９個の組み合わせが該当する。

また、タスク単体の実行時間がデッドライン（実行周期）を超えているものに対してもシミュレーション部５０にて実行時間を算出する。
図９ではＮｏ．３、６、９、１２、１３〜１８の１０通りが該当する。

これらの中から重複を除いた１１通りが、シミュレーション部５０で実行時間を測定する実行パスの組み合わせとなる。

以上が実行パス組み合わせ決定部４１による実行パスの組み合わせ数を減らす動作の説明である。

＜実施の形態２の効果＞
以上のように、本実施の形態では実行パス組み合わせ決定部４１にて、デッドラインを超える可能性のある実行パスの組み合わせに限定してシミュレーションを行うことで、デッドラインを越えるかどうかの判定を行う時間を削減することができる。

＜実施の形態２の変形例＞
本実施の形態ではキャッシュメモリがない状態の各実行パスの実行時間をもとに組み合わせを減らすようにしたが、キャッシュメモリによる処理時間短縮の効果が大きい場合、実行時間が実際よりもはるかに大きくなり、ほぼ全ての組み合わせを実行する可能性がある。
そこで、キャッシュメモリを有効（使用可能な状態）にし、実行開始時にキャッシュメモリに何もない状態からシミュレーション実行したときの実行時間をもとに組み合わせを減らしてもよい。
ただし、この場合は優先度の高いタスクが途中で割り込まれたときにキャッシュから追い出されることによるキャッシュミス数増加による遅延を考慮するため、実際に算出した実行時間にマージンとなる時間を足した時間を各実行パスの実行時間とする。
マージンとなる時間は実行パスごとに一律の時間でもよいし、キャッシュヒット数、キャッシュ使用量などのキャッシュの使用特性に応じて設定してもよい。

本実施の形態の変形例としては、実施の形態１と同様、最悪実行時間判定部９０がデッドラインを超えると判断すると以降の実行パスの組み合わせのシミュレーションを実行せずに終了してもよい。これによる効果は実施の形態１と同じく、判定時間を短縮できる。

また、シミュレーション部５０にて実行する実行パスの組み合わせの順番についても、実行パス組み合わせ決定部４１が算出した実行時間の合計が最も大きいものを組み合わせたものから実行してもよい。
この場合、デッドラインを超える可能性の高いパスからシミュレーション実行していくので、早期にデッドラインを超えると判定される可能性がある。
このとき、デッドラインを超えると判定されると以降のシミュレーション実行を行わずに終了すれば、判定時間をさらに短縮することができる。

最後に、実施の形態１及び２に示した最悪実行時間判定システム１０００のハードウェア構成例を図１０を参照して説明する。
最悪実行時間判定システム１０００はコンピュータであり、最悪実行時間判定システム１０００の各要素をプログラムで実現することができる。
最悪実行時間判定システム１０００のハードウェア構成としては、バスに、演算装置９０１、外部記憶装置９０２、主記憶装置９０３、通信装置９０４、入出力装置９０５が接続されている。

演算装置９０１は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）である。
外部記憶装置９０２は、例えばＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）やフラッシュメモリ、ハードディスク装置である。
主記憶装置９０３は、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。
通信装置９０４は、例えばＮＩＣ（Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｃａｒｄ）である。
入出力装置９０５は、例えばマウス、キーボード、ディスプレイ装置等である。

プログラムは、通常は外部記憶装置９０２に記憶されており、主記憶装置９０３にロードされた状態で、順次演算装置９０１に読み込まれ、実行される。
プログラムは、図１に示す「〜部」（「〜記憶部」は除く、以下も同様）として説明している機能を実現するプログラムである。
更に、外部記憶装置９０２にはオペレーティングシステム（ＯＳ）も記憶されており、ＯＳの少なくとも一部が主記憶装置９０３にロードされ、演算装置９０１はＯＳを実行しながら、図１に示す「〜部」の機能を実現するプログラムを実行する。
また、実施の形態１及び２の説明において、「〜の判断」、「〜の判定」、「〜の抽出」、「〜の算出」、「〜の検知」、「〜の設定」、「〜の登録」、「〜の選択」、「〜の生成」等として説明している処理の結果を示す情報やデータや信号値や変数値が主記憶装置９０３にファイルとして記憶されている。

なお、図１０の構成は、あくまでも最悪実行時間判定システム１０００のハードウェア構成の一例を示すものであり、最悪実行時間判定システム１０００のハードウェア構成は図１０に記載の構成に限らず、他の構成であってもよい。

また、実施の形態１及び２に示す手順により、本発明に係るプログラム解析方法を実現可能である。

１０ 実行対象Ｓ／Ｗ記憶部、２０ 実行パス解析部、３０ 実行パスリスト記憶部、３１ 実行パスリスト記憶部、４０ 実行パス組み合わせ決定部、４１ 実行パス組み合わせ決定部、５０ シミュレーション部、６０ タスクスケジュール記憶部、７０ 変数操作部、８０ キャッシュ無効化部、９０ 最悪実行時間判定部、１００ 実行時間算出部、１０００ 最悪実行時間判定システム。

Claims (14)

1. 複数のタスクが生成される、複数のブロックで構成されたプログラムを解析し、タスクごとに、タスクにおいて実行されるブロック群を実行順に実行パスとして抽出する実行パス抽出部と、
   前記プログラム実行時のタスクの生成順序に従って、各タスクに対応する実行パスを配列させるとともに、実行パスの組合せを変化させて複数の配列パターンを生成する配列パターン生成部と、
   配列パターンごとに、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出する実行時間算出部とを有することを特徴とするプログラム解析装置。
2. 前記実行時間算出部は、
   キャッシュメモリが実装されているプログラム実行環境で配列パターンに含まれる実行パスが順に実行された場合の実行時間を実行パスごとに算出することを特徴とする請求項１に記載のプログラム解析装置。
3. 前記プログラム解析装置は、更に、
   タスクごとに、上限の実行時間が上限時間として記述される上限時間情報を記憶する上限時間情報記憶部と、
   前記実行時間算出部により算出された各実行パスの実行時間が、各実行パスのタスクの上限時間を超えていないかを判定する判定部を有することを特徴とする請求項１又は２に記載のプログラム解析装置。
4. 前記判定部は、
   前記実行時間算出部が全ての配列パターンに対して実行パスの実行時間の算出を終える前に、前記実行時間算出部により算出された各実行パスの実行時間が、各実行パスのタスクの上限時間を超えていないかを判定し、
   前記実行時間算出部は、
   前記判定部により、いずれかの配列パターンにおいて、いずれかの実行パスの実行時間が上限時間を超えていると判定された場合に、以降の実行時間の算出を取りやめることを特徴とする請求項３に記載のプログラム解析装置。
5. 前記実行時間算出部は、
   包含しているブロックの個数が多い配列パターンから順に、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出することを特徴とする請求項１又は４に記載のプログラム解析装置。
6. 前記プログラム解析装置は、更に、
   タスクごとに、上限の実行時間が上限時間として記述される上限時間情報を記憶する上限時間情報記憶部を有し、
   前記実行時間算出部は、
   単体で実行された場合の各実行パスの実行時間を算出し、
   配列パターンごとに、配列パターンに含まれる各実行パスの単体の実行時間が、各実行パスのタスクの上限時間を超えるか否かを判定し、
   配列パターンごとに、配列パターンに含まれる各実行パスの単体の実行時間を合計した合計値が、各実行パスのタスクの上限時間を合計した合計値を超えるか否かを判定し、
   いずれかの実行パスの単体の実行時間が上限値を超える配列パターン及び実行時間の合計値が上限時間の合計値を超える配列パターンの少なくともいずれかを選択し、
   選択した配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出することを特徴とする請求項１に記載のプログラム解析装置。
7. 前記実行時間算出部は、
   キャッシュメモリが実装されていないプログラム実行環境で各実行パスが単体で実行された場合の実行時間を算出することを特徴とする請求項６に記載のプログラム解析装置。
8. 前記実行時間算出部は、
   キャッシュメモリが実装されているプログラム実行環境で、各実行パスの実行開始時に前記キャッシュメモリにデータが存在しない状態で各実行パスが単体で実行された場合の実行時間を算出することを特徴とする請求項６に記載のプログラム解析装置。
9. 前記実行時間算出部は、
   選択した配列パターンのうち、配列パターンに含まれる各実行パスの単体の実行時間を合計した合計値が大きい配列パターンから順に、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出することを特徴とする請求項６に記載のプログラム解析装置。
10. 前記実行パス抽出部は、
    複数のリアルタイムタスクが生成される、複数のブロックで構成されたプログラムを解析し、リアルタイムタスクごとに、リアルタイムタスクにおいて実行されるブロック群を実行順に実行パスとして抽出し、
    前記配列パターン生成部は、
    前記プログラム実行時のリアルタイムタスクの生成順序に従って、各リアルタイムタスクに対応する実行パスを配列させるとともに、実行パスの組合せを変化させて複数の配列パターンを生成し、
    前記実行時間算出部は、
    配列パターンごとに、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出することを特徴とする請求項１に記載のプログラム解析装置。
11. 前記実行時間算出部は、
    キャッシュメモリが実装されているプログラム実行環境で、配列パターンごとに、特定の実行順序の実行パスの実行開始時に前記キャッシュメモリにデータが存在しない状態で当該実行パスが実行された場合の実行パスの実行時間を実行パスごとに算出することを特徴とする請求項１０に記載のプログラム解析装置。
12. 前記プログラム解析装置は、更に、
    タスクごとに、上限の実行時間が上限時間として記述される上限時間情報を記憶する上限時間情報記憶部と、
    前記実行時間算出部が全ての配列パターンに対して実行パスの実行時間の算出を終える前に、前記実行時間算出部により算出された各実行パスの実行時間が、各実行パスのタスクの上限時間を超えていないかを判定する判定部とを有し、
    前記実行時間算出部は、
    前記判定部により、いずれかの配列パターンにおいて、いずれかの実行パスの実行時間が上限時間を超えていると判定された場合に、以降の実行時間の算出を取りやめることを特徴とする請求項６に記載のプログラム解析装置。
13. コンピュータが、複数のタスクが生成される、複数のブロックで構成されたプログラムを解析し、タスクごとに、タスクにおいて実行されるブロック群を実行順に実行パスとして抽出する実行パス抽出ステップと、
    前記コンピュータが、前記プログラム実行時のタスクの生成順序に従って、各タスクに対応する実行パスを配列させるとともに、実行パスの組合せを変化させて複数の配列パターンを生成する配列パターン生成ステップと、
    前記コンピュータが、配列パターンごとに、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出する実行時間算出ステップとを有することを特徴とするプログラム解析方法。
14. 複数のタスクが生成される、複数のブロックで構成されたプログラムを解析し、タスクごとに、タスクにおいて実行されるブロック群を実行順に実行パスとして抽出する実行パス抽出処理と、
    前記プログラム実行時のタスクの生成順序に従って、各タスクに対応する実行パスを配列させるとともに、実行パスの組合せを変化させて複数の配列パターンを生成する配列パターン生成処理と、
    配列パターンごとに、配列パターンに含まれる実行パスが順に実行された場合の実行パスの実行時間を実行パスごとに算出する実行時間算出処理とをコンピュータに実行させることを特徴とするプログラム。

Images