In a hard real-time system, it is important to complete a task before its deadline. In order to guarantee the reliability of a real-time system, when developing a system, we have to confirm that the worst case execution time (WCET) of a real-time task always meets a deadline. In a current development method mostly used at the industries, a task is run using various test cases so that WCET is estimated. However, by this method, it cannot guarantee that it is the true WCET. Moreover, in the system by which multiple real-time tasks are run, the execution of a task has preemption delay. In order for a system to always meet a deadline in any conditions, it is necessary to calculate the WCET of a task and preemption delay using reliable methods, and to examine schedulability analysis.

In this thesis, we propose a method of calculating the WCET in all the execution paths of a task in the analysis of a source code. And, we predict the timing of preemption using OS which can control interrupts, and propose the method of calculating for preemption delay in a preemptive multitask environment. With this method, it's decided correctly whether the schedule of the given task set is possible.

The WCET is calculated combining the measurement result of the execution time for each basic block of a program using a real machine and the simulation result. Since an analyzer uses Register Transfer Language (RTL) used as expression inside Gnu Compiler Collection (GCC), the WCET is calculated by various architectures. In order to calculate for preemption delay, it is assumed that periodic tasks are only running in a real-time OS in which interrupt except for timer interrupt do not occur. In such an environment, the preemption is not caused to arbitrary timing but the preemption point is known before execution. The reload time of cache is calculated from the available number cache entries at a preemption point, ant this is considered as preemption delay.

The prediction method of WCET is evaluated on architectures, Pentium-M and XScale processor. In Pentium-M processor, the estimated WCET is 1.12 to 1.36 times longer than the actual WCET. In XScale, the estimated WCET is 1.06 to 1.18 times longer than the actual WCET. In SH, the estimated WCET is 1.02 to 1.14 times longer than the actual WCET. Linux is extended in order to perform a real-time schedule. Schedulability analysis of task sets is evaluated using the proposed method. The result of this study that reliable schedulability analysis is possible in order to estimate the WCET and preemption delay correctly.

組み込みシステムをはじめとする実時間システムの信頼性を保証することは、情報技術を基盤とする安心・安全な社会を構築するために必須の技術である。実時間システムの信頼性の最も基本的な要件は、各実時間タスクが定められたデッドラインまでに実行を完了すること(スケジューリング可能性)である。すなわち、実時間タスクの最悪実行時間が常にデッドラインを満たすことを保証しなければならない。タスクを様々なテストケースで実行し最悪実行時間を見積もる手法では、全ての実行パスを考慮していないため、真に最悪な実行時間が得られるとは限らない。また、複数の実時間タスクが動くシステムでは、プリエンプションがもたらす性能悪化も考慮に入れなければならない。本論文では、実時間タスクの最悪実行時間とプリエンプションによる遅延を予測する手法を提案するとともに、実際に実時間システムを解析するツールを開発し、提案手法の評価を行っている。より具体的には、ソースコードを解析することにより全実行パスを考慮して最悪実行時間を求める手法と、プリエンプションのタイミングを予測しプリエンプションによる遅延を正確に求める手法を提案している。

本論文の第1章では、以上で述べたような本論文の背景と動機が述べられている。

第2章では、最悪実行時間の解析の基本原理と従来手法について述べられている。

第3章において、最悪実行時間を予測する手法が詳述されている。最悪実行時間は、プログラムの基本ブロック毎の実行時間を実機により用いて測定した結果と、フロー解析器によるシミュレーションにより予測したメモリ参照時間を組み合わせて求められる。フロー解析器は、Gnu Compiler Collection(GCC)の中間表現であるRegister Transfer Language(RTL)を利用して実装されているため、様々なアーキテクチャに対応できる移植性を有している。最悪実行時間の予測手法の有効性および移植性を示すために、Pentium-MとXScaleとSHアーキテクチャ上で評価が行われている。Pentium-Mの場合、予測最悪実行時間は実際の実行時間の1.12~1.36倍であった。XScaleの場合、実際の実行時間の1.06~1.18倍程度であった。SHの場合、実際の実行時間の1.02~1.14倍程度であった。

第4章において、プリエンプションによる遅延を求める手法が詳述されている。タイマー割り込み以外の割り込みが発生せず、その上で動くタスクは周期タスクのみであると仮定した環境において、プリエンプションの発生位置を事前に特定し、各々のプリエンプション位置において有効なキャッシュエントリ数からキャッシュの再ロード時間を求めることにより、プリエンプション遅延が求められる。

第5章では関連研究と本研究の比較が行われ、第6章で本論文のまとめと将来の課題が述べられている。

以上をまとめると、本研究は、タスクの最悪実行時間とプリエンプション遅延を正確に見積もることにより、実時間システムのスケジューリング可能性の検証の精度を大きく向上させることに成功している。また、開発したツールは高い移植性を有しており、様々なアーキテクチャに対応可能である。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。