Interactive worst-case execution time analysis of hard real-time systems.

摘要

Hard real-time systems are already common in aerospace, automobiles, and industrial robotics, and they will become even more prevalent with the emergence of new domains such as computer-assisted surgery. Perpetual concerns over safety and overall mission success require a guarantee that these increasingly complex systems perform as designed.;One technique involves a static analysis to place an upper bound on the worst-case execution time (WCET) of hard real-time software. Without knowledge of WCET, the timing behavior of a program cannot be guaranteed. Although substantial research has been applied to the problem of WCET analysis, virtually all prior work has focused on increasing accuracy without regard to speed. The resulting implementations are often too slow to be integrated into the development cycle, requiring WCET analysis to be postponed until a final validation phase. Fixing timing errors after the code has been written is expensive, time-consuming, and may necessitate a redesign of the system.;A new approach, interactive WCET analysis, would prevent such problems. Its novelty lies in making timeliness a fundamental concern of system design from the moment the first line of code is written. Rather than waiting until an implementation is complete before starting the analysis, it incorporates knowledge of worst-case time into the development cycle continuously and dynamically, allowing early detection and removal of timing errors.;This dissertation proposes a variety of methods for making WCET analysis interactive. It begins with a simplification of the problem by relying on Java-based microprocessors to eliminate many sources of unpredictability. It then presents contributions in a bottom-up fashion, starting with a technique for annotating control flow graphs with decompiled source code. These graphs are used to map the results of WCET analysis to source code as it is written, a process known as interactive back-annotation. Additional contributions include compiler support for type-safe WCET annotations, statically analyzable collection classes, and a fast tree-based analysis algorithm with method cache support. Each contribution is implemented within a suite of extensible, modular, open-source tools that demonstrate how interactive WCET analysis can be integrated into a traditional software development environment.