Table of Contents
With the increasing size and complexity of hard real-time systems, developers are beginning to move away from C. Despite its status as the most popular language in real-time computing, it is relatively low-level, error-prone, and difficult to scale to large systems.
A growing number of real-time developers and researchers are considering Java as an alternative. This much newer language offers direct benefits: Compilers for Java catch many errors that C compilers miss; the language definition specifically addresses safety and security issues; and the high-level nature of Java makes it more productive, maintainable, and portable than C.
For real-time systems, Java is an immature but viable platform. Commercial implementations of the Real-time Specification for Java (RTSJ) are available from aicas and Sun, and real-time garbage collectors, such as Metronome, are showing promise. Boeing is using real-time Java to guide drone aircraft, and the United States Navy will use it in next-generation battleships.
In spite of these advances, an essential element is missing. Even when a real-time Java implementation provides deterministic scheduling, priority inversion avoidance, and a real-time garbage collector, no guarantee on the timeliness of the system can be made without knowledge of the worst-case execution time (WCET) for each task. To understand why this knowledge is so important, consider the major real-time scheduling algorithms shown in Figure 1.1. All of these algorithms require knowledge of the WCET.
Figure 1.1. Real-time scheduling algorithms require worst-case execution time (the C variables) to determine whether deadlines can be met.
While most real-time practitioners are aware of its significance, the job of calculating this WCET is often perfunctory or even neglected. A common tactic in industry is to perform a series of tests under varying conditions and attempt to extrapolate the actual WCET from the resulting measurements. While this approach works well for average response time, worst-case response time is not amenable to measurement. An unexpected set of input data could cause the system to react more slowly than was measured during testing, as illustrated in Figure 1.2.
Figure 1.2. This histogram of execution time for a fictional real-time task illustrates the weakness of measurement when dealing with worst-case execution time.
A more dependable and systematic approach to finding the WCET involves a static analysis. Given the executable code for a task and the processor on which it will run, static analysis provides an upper bound on the time taken to execute the task. Figure 1.3 shows a high-level sketch of this process for a trivial example.
Figure 1.3. This trivial example shows how static analysis places an upper bound on worst-case execution time.
In the non-trivial real world, static analysis is not so simple. The traditional real-time Java environment offers many sources of unpredictability that result in alarmingly pessimistic WCET values. For instance, just-in-time compilation, a common technique for improving average performance in Java virtual machines, causes the first few executions of a task to be slow while subsequent executions are fast. Static analysis must account for this variance, leading to very large estimations of WCET. Developers are faced with unsettling choices: Turning off just-in-time compilation would merely slow down every execution, while reducing the WCET to the expected (average) running time would be unsafe and defeat the very purpose of analysis.
Modern processors are another enemy of tight WCET analysis. Large pipelines, branch prediction, and sophisticated multi-level caching have greatly improved average throughput at the expense of worst-case throughput. In Figure 1.3, for example, setting flag to true might trigger a cache miss. The WCET analysis must therefore include the lengthy cache servicing time even if its occurrence is rare. Although prior work has focused on modeling the processor to place a tighter bound on this cache interference, the technique remains challenging, particularly for data caches.