An Assessment of Task Execution Time Analysis ?

Peter Puschner, Alexander Vrchoticky

Institut f?ur Technische Informatik

Technische Universit?at Wien

falex, [email protected]

Abstract: Task execution times are crucial parameters for the design of predictable real-time systems. An upper bound for the maximum execution time must be known for each task. These bounds have to be tight in order to ease schedulability, testing, and error detection and to arrive at a high resource utilization, thus possibly avoiding the need for additional nodes in a distributed system. In this work we evaluate the tightness of execution time bounds which are computed by source code analysis. Different versions of some sample tasks, which differ in the degree information about the control flow is supplied by the programmer, are investigated in a distributed computer system with known timing characteristics. The reasons for the differences between measured and calculated worst case execution times of the versions are assessed by inspection of the task execution paths and the used algorithms. As a result we discuss the possibilities to include more application specific knowledge into tasks by means of new language constructs.

Keywords: Real time computer systems, Programming languages, Computer programming, Task timing analysis, Worst case execution time.

1 Introduction

During the design of predictable hard real-time systems knowledge about the execution times of tasks has to be available as early as possible. Researchers have been developing techniques to predict the worst case execution times of tasks by static analysis of the tasks' code [Kli86, Mok89, Sha89]. However, the results gained by static analysis often grossly over-estimate the maximum execution times of the tasks in question. Therefore, systems designed using this technique often are characterized by poor resource utilization and unnecessarily long response times. The overestimation is due to infeasible paths that have high execution times but can actually never be executed. To alleviate this problem, it is necessary to allow the programmer to express knowledge about the execution of the real-time tasks that cannot be derived from the code structure itself. A first set of constructs for this purpose has been proposed in [Pus89].

?This work has been supported by the Austrian Science Foundation (Fonds zur F?orderung der wissenschaftlichen Forschung) under contract P8002-TEC

This paper is concerned with an experimental evaluation of static execution time analysis with and without such additional constructs. For a number of tasks we compare the actual execution time distribution measured during executions of the task with the bounds for the execution times derived by static analysis. The effectiveness of the proposed constructs is demonstrated by gradually incorporating them into the tasks.

The paper is structured as follows: Section 2 briefly describes the setup used for the measurements. Section 3 describes the different means of calculating execution times from the tasks code. Section 4 describes the tasks used for our evaluation and presents first results, showing how improved evaluation techniques can help gain realistic bounds on the execution times of tasks. An evaluation of our experiments follows in Section 5. The paper is concluded in Section 6.

2 Timing Measurements

The execution time of tasks is measured on a prototype MARS [Kop89] node, using external