Predicting deterministic execution times of real-time programs
Chang Yun Park · 1992
The most distinctive characteristic of a real-time system is that it requires temporal correctness. Therefore, analyzing the timing behavior of a real-time system is essential. In this dissertation, we address this problem by predicting the deterministic execution times of the programs comprising a system. Our approach is to predict a time interval, covering all execution cases, with an analytic method at the source program level. The basic prediction method is based on a formal timing schema for a source-level construct. A simple and efficient timing tool for C programs is implemented in a practical setting. Comparison with measurements shows that predictions are safe and usually tight. However, the tool produces loose predictions for some complex programs because of infeasible paths. For tighter predictions, we analyze the dynamic behavior of a program using information provided by a user. We introduce a formal path model where both a program and user execution information are represented by a set of program paths described by an extended regular expression. Infeasible paths are eliminated by intersecting the two path sets. With a well-defined practical high-level interface language, the path model can be used in an easy and efficient way. We also introduce a method to verify given user information with known program verification techniques. Extended with path analysis, a timing tool yields safe and accurate predictions for a wide range of programs. It also supports incremental refinement where overall prediction cost is scalable with respect to desired precision. As a start for deterministic timing analysis of input/output operations, we introduce a method to predict the execution time of an I/O statement. The main problems in I/O analysis are predicting waiting time for a device or data and analyzing interference caused by asynchronous execution, in a variety of implementation policies. Our approach is to develop a general framework and to apply it to a specific case in a systematic way. We provide a schema refinement rule for each implementation policy that transforms a timing schema to be more specific and thus more predictable in a target system. We also introduce formulas that compute the effect of interference in a target system. We developed methods to predict deterministic program execution times, and validated them by experiments. Predictions are safe, accurate and feasible with reasonable cost. Future work includes experimenting with large programs, analyzing concurrent programs, and reasoning about the timing properties of a system with predictions.