A Survey of Worst-Case Execution Time Analysis for Real-Time Java
---
paper_title: Real-Time Euclid: A language for reliable real-time systems

paper_content:

Real-Time Euclid, a language designed specifically to address reliability and guaranteed schedulability issues in real-time systems, is introduced. Real-Time Euclid uses exception handlers and import/export lists to provide comprehensive error detection, isolation, and recovery. The philosophy of the language is that every exception detectable by the hardware or the software must have an exception-handler clause associated with it. Moreover, the language definition forces every construct in the language to be time- and space-bounded. Consequently, Real-Time Euclid programs can always be analyzed for guaranteed schedulability of their processes. Thus, it is felt that Real-Time Euclid is well-suited for writing reliable real-time software.
---
paper_title: The real-time specification for Java

paper_content:

New languages, programming disciplines, operating systems, and software engineering techniques sometimes hold considerable potential for real-time software developers. A promising area of interest-but one fairly new to the real-time community-is object-oriented programming. Java, for example, draws heavily from object orientation and is highly suitable for extension to real-time and embedded systems. Recognizing this fit between Java and real-time software development, the Real-Time for Java Experts Group (RTJEG) began developing the real-time specification for Java (RTSJ) in March 1999 under the Java Community Process. This article explains RTSJ's features and the thinking behind the specification's design. The goal of the RTJEG, of which the authors are both members, was to provide a platform-a Java execution environment and application program interface (API)-that lets programmers correctly reason about the temporal behavior of executing software.
---
paper_title: Portable worst-case execution time analysis using Java Byte Code

paper_content:

Addresses the problem of performing worst-case execution time (WCET) analysis of Java Byte Code (JBC), which may be generated from different compilers and from different source languages. The motivation for the framework presented is to provide WCET analysis which is portable and therefore more likely to be used in an industrial context. Two issues are addressed in this paper: how to extract data flow and control flow information from JBC programs, and how to provide a compiler-/language-independent mechanism to introduce WCET annotations in the source code. We show that an annotation mechanism based on calls to a static class with empty methods result in similar code when generated by Java or Ada compilers.
---
paper_title: Real-Time Euclid: A language for reliable real-time systems

paper_content:

Real-Time Euclid, a language designed specifically to address reliability and guaranteed schedulability issues in real-time systems, is introduced. Real-Time Euclid uses exception handlers and import/export lists to provide comprehensive error detection, isolation, and recovery. The philosophy of the language is that every exception detectable by the hardware or the software must have an exception-handler clause associated with it. Moreover, the language definition forces every construct in the language to be time- and space-bounded. Consequently, Real-Time Euclid programs can always be analyzed for guaranteed schedulability of their processes. Thus, it is felt that Real-Time Euclid is well-suited for writing reliable real-time software.
---
paper_title: Portable worst-case execution time analysis using Java Byte Code

paper_content:

Addresses the problem of performing worst-case execution time (WCET) analysis of Java Byte Code (JBC), which may be generated from different compilers and from different source languages. The motivation for the framework presented is to provide WCET analysis which is portable and therefore more likely to be used in an industrial context. Two issues are addressed in this paper: how to extract data flow and control flow information from JBC programs, and how to provide a compiler-/language-independent mechanism to introduce WCET annotations in the source code. We show that an annotation mechanism based on calls to a static class with empty methods result in similar code when generated by Java or Ada compilers.
---
paper_title: Asynchronous Transfer of Control in the RTSJ-compliant Java Processor

paper_content:

Asynchronous Transfer of Control (ATC) is a crucial mechanism for real-time applications, and is currently provided in the Real-Time Specification for Java (RTSJ). This paper proposes a framework to implement ATC in the RTSJ-compliant Java processor based on the instruction optimization method proposed in our previous work [1]. Because most of the processing is done before bytecode execution in this method, the implementation using our framework is straightforward. Moreover, its Worst Case Execution Time (WCET) is more predictable.
---
paper_title: Real-time objects on the bare metal: an efficient hardware realization of the Java/sup TM/ Virtual Machine

paper_content:

Combining the design-time efficiency of object oriented development with the runtime efficiency of direct hardware support for object oriented execution, aJile Systems has developed a low-power hardware implementation of the Java Virtual Machine for real time and embedded applications. AJile's hardware provides direct support for the entire JVM instruction set and thread model, obviating the need for a Java interpreter or Just-in-Time (JIT) compiler, as well as the traditional Real-Time Operating System (RTOS). AJile's hardware technology also supports multiple JVM contexts executing on the same CPU, enhancing safety and security by guaranteeing space and time allotments for multiple Java applications. Combined with a Java 2 Micro Edition (J2ME) runtime and a back-end target build tool, these technologies constitute an efficient platform for the development of real time embedded applications entirely in Java.
---
paper_title: The real-time specification for Java

paper_content:

New languages, programming disciplines, operating systems, and software engineering techniques sometimes hold considerable potential for real-time software developers. A promising area of interest-but one fairly new to the real-time community-is object-oriented programming. Java, for example, draws heavily from object orientation and is highly suitable for extension to real-time and embedded systems. Recognizing this fit between Java and real-time software development, the Real-Time for Java Experts Group (RTJEG) began developing the real-time specification for Java (RTSJ) in March 1999 under the Java Community Process. This article explains RTSJ's features and the thinking behind the specification's design. The goal of the RTJEG, of which the authors are both members, was to provide a platform-a Java execution environment and application program interface (API)-that lets programmers correctly reason about the temporal behavior of executing software.
---
paper_title: Gain time reclaiming in high performance real-time Java systems

paper_content:

The run-time characteristics of Java, such as high frequency of method invocation, dynamic dispatching and dynamic loading, make Java more difficult than other object-oriented programming languages, such as C++, for conducting Worst-Case Execution Time (WCET) analysis. To offer a more flexible way to develop object-oriented real-time applications in the realtime Java environment without loss of predictability and performance, we propose a novel gain time reclaiming framework integrated with WCET analysis. This paper demonstrates how to improve the utilisation and performance of the whole system by reclaiming gain time at run-time. Our approach shows that integrating WCET with gain time reclaiming can not only provide a more flexible environment, but it also does not necessarily result in unsafe or unpredictable timing behaviour.
---
paper_title: Low-level analysis of a portable Java byte code WCET analysis framework

paper_content:

To support portability, worst-case execution time (WCET) analysis of Java byte code is performed at two levels - machine-independent program flow analysis at a higher level and machine-dependent timing analysis of individual program constructs at a lower level. This paper contributes a WCET analysis that computes worst-case execution frequencies of Java byte codes within the software being analysed and accounts for platform-dependent information, i.e. the processor's pipeline. The main part of the approach is platform-independent; only a limited analysis is needed on a per-platform basis.
---
paper_title: XRTJ: An Extensible Distributed High-Integrity Real-Time Java Environment

paper_content:

Despite Java’s initial promise of providing a reliable and cost-effective platform-independent environment, the language appears to be unfavourable in the area of high-integrity systems and real-time systems. To encourage the use of Java in the development of distributed high-integrity real-time systems, the language environment must provide not only a well-defined specification or subset, but also a complete environment with appropriate analysis tools. We propose an extensible distributed high-integrity real-time Java environment, called XRTJ, that supports three attributes, i.e., predictable programming model, dependable static analysis environment, and reliable distributed run-time environment. The goal of this paper is to present an overview of our on-going project and report on its current status. We also raise some important issues in the area of distributed high-integrity systems, and present how we can deal with them by defining two distributed run-time models where safe and timely operations will be supported.
---
paper_title: WCET analysis of reusable portable code

paper_content:

Traditional worst-case execution-time analysis (WCET analysis) computes upper bounds for the execution times of code. This analysis uses knowledge about the execution contest of the code and about the target architecture. In contrast, the WCET analysis for reusable and portable code has to abstract from parameters that are unknown until the code is finally used. The analysis is done in two steps. The first step computes abstract WCET information to support the reuse and portability of the WCET information. The second step uses the abstract WCET information to compute concrete WCET bounds when the application context and the timing parameters of the target system are known. The paper describes each of the two analysis steps. It demonstrates how WCET information can be made portable and reusable.
---
paper_title: HIDOORS - a high integrity distributed deterministic Java environment

paper_content:

This paper presents the design of HIDOORS, an integrated development environment suitable for embedded distributed real-time systems, based on the Java programming language. HIDOORS will cover all the life-cycle of real-time software development with extensions to existing tools (UML modeling, Java compiler Java Virtual Machine, and a worst case execution time analysis tool) that will all be integrated into a single integrated development environment. The system will also assist the developer in distributing the application, by providing faster RMI and a distributed event manager that provides strict timing guarantees. This paper is written at the beginning of HIDOORS development, and as such, it presents only, the defined objectives and the early, architecture of the system; further developments will be the Subject of future works.
---
paper_title: WCET analysis for a Java processor

paper_content:

In this paper we propose a solution for a worst-case execution time (WCET) analyzable Java system: a combination of a time predictable Java processor and a tool that performs WCET analysis of Java bytecode. We present a Java processor, called JOP, designed for time-predictable execution of real-time tasks. JOP is an implementation of the Java virtual machine (JVM) in hardware. The execution time of bytecodes, the instructions of the JVM, is known cycle accurate for JOP. Therefore, JOP simplifies the low-level WCET analysis. A method cache, that fills whole Java methods into the cache, is analyzable with respect to the WCET. The WCET analysis tool is based on integer linear programming. The tool performs the low-level analysis at the bytecode level and integrates the method cache analysis for a two block cache.
---
paper_title: Portable worst-case execution time analysis using Java Byte Code

paper_content:

Addresses the problem of performing worst-case execution time (WCET) analysis of Java Byte Code (JBC), which may be generated from different compilers and from different source languages. The motivation for the framework presented is to provide WCET analysis which is portable and therefore more likely to be used in an industrial context. Two issues are addressed in this paper: how to extract data flow and control flow information from JBC programs, and how to provide a compiler-/language-independent mechanism to introduce WCET annotations in the source code. We show that an annotation mechanism based on calls to a static class with empty methods result in similar code when generated by Java or Ada compilers.
---
paper_title: Hard real-time garbage collection in the Jamaica virtual machine

paper_content:

Java's automatic memory management is the main reason that prevents Java from being used in hard real-time environments. We present the garbage collection mechanism that is used by the Jamaica Virtual Machine, an implementation of the Java Virtual Machine Specification. This mechanism differs significantly from existing implementations in the way threads are implemented, root references are found and in the object layout that is used. The implementation provides hard real-time guarantees while it allows unrestricted use of the Java language. Even dynamic allocation of normal garbage collected Java objects is possible with hard real-time guarantees.
---
paper_title: An interactive environment for real-time software development

paper_content:

Object-oriented languages, in particular Java, are beginning to make their way into embedded real-time software development. This is not only for the safety and expressiveness of the source language; the mobility and dynamic loading of Java bytecode make it particularly useful in embedded real-time systems. However using such languages in real-time systems makes it more difficult to predict the worst-case execution time of tasks. Such predictions are necessary for predictable task scheduling in the developed system. Garbage collection, common in object-oriented languages, must be considered; to schedule garbage collection safely, we must know how much memory it has to handle. Dynamic binding in conjunction with dynamic loading of code also needs treatment. We show how techniques for predicting time and memory demands of object-oriented programs are integrated into the Skanerost development environment. The environment explicitly targets an iterative development process, which is particularly important in real-time software development since time and memory demands cannot be determined until the code is written. Design changes due to timing problems become more costly as development progresses, and Skanerost allows such problems to be detected early.
---
paper_title: ANALYZING EXECUTION-TIME OF OBJECT-ORIENTED PROGRAMS USING ABSTRACT INTERPRETATION

paper_content:

As a result of the industrial deployment of real-time systems, there is an increasing demandfor methods to perform safe and tight calculation of the worst case execution time (WCET) ofprograms. The ...
---
paper_title: An effective instruction optimization method for embedded real-time Java processor

paper_content:

A method to optimize instructions in embedded real-time Java processors is proposed. It can reduce the CPI (cycles per instruction) and simplify the implementation of complex instructions, as well as make the WCET (worst case execution time) of the optimized instructions more predictable. Because this method optimizes instruction itself it can be used together with other architectural optimization methods such as pipeline or out-of-order execution etc.
---
paper_title: Addressing dynamic dispatching issues in WCET analysis for object-oriented hard real-time systems

paper_content:

There is a trend towards using object-oriented programming languages to develop hard real-time applications. However some object-oriented features, such as dynamic dispatching and dynamic loading, are prohibited from being used in hard realtime systems because they are either unpredictable and/or un-analysable. Arguably, these restrictions could make applications very limited and unrealistic since they could eliminate the major advantages of object-oriented programming. This paper demonstrates how we can address the dynamic dispatching issues in Worst-Case Execution Timing (WCET) analysis with minimum annotations. The major contributions include: discussing the major issues involved in using and restricting dynamic binding features; weakening the restriction of using dynamic dispatching; presenting how to estimate tighter and safer WCET value in object-oriented hard real-time systems. Our approach shows that allowing the use of dynamic dispatching can not only provide a more flexible way to develop object-oriented hard real-time applications, but also does not necessarily result in unpredictable timing analysis.
---
paper_title: Addressing dynamic dispatching issues in WCET analysis for object-oriented hard real-time systems

paper_content:

There is a trend towards using object-oriented programming languages to develop hard real-time applications. However some object-oriented features, such as dynamic dispatching and dynamic loading, are prohibited from being used in hard realtime systems because they are either unpredictable and/or un-analysable. Arguably, these restrictions could make applications very limited and unrealistic since they could eliminate the major advantages of object-oriented programming. This paper demonstrates how we can address the dynamic dispatching issues in Worst-Case Execution Timing (WCET) analysis with minimum annotations. The major contributions include: discussing the major issues involved in using and restricting dynamic binding features; weakening the restriction of using dynamic dispatching; presenting how to estimate tighter and safer WCET value in object-oriented hard real-time systems. Our approach shows that allowing the use of dynamic dispatching can not only provide a more flexible way to develop object-oriented hard real-time applications, but also does not necessarily result in unpredictable timing analysis.
---

Title: A Survey of Worst-Case Execution Time Analysis for Real-Time Java

Section 1: Introduction
Description 1: This section introduces the importance of worst-case execution time (WCET) analysis in real-time systems and the current challenges faced by practitioners in the industry.

Section 2: The Challenge of WCET Analysis
Description 2: This section discusses why influential research on WCET analysis hasn't been widely adopted, including the complexities of modern CPU architectures.

Section 3: Implementation Difficulties
Description 3: This section provides details on the difficulties in implementing WCET analysis tools, highlighting issues at both hardware and software levels.

Section 4: Java as a Catalyst
Description 4: This section explains why Java has become a popular platform for real-time systems and outlines key events and innovations that have made real-time Java viable.

Section 5: Bytecode as an Intermediate Representation
Description 5: This section covers the proposal to use Java bytecode as an intermediate representation for WCET tools and discusses the challenges and initial research in this area.

Section 6: High-level Analysis for the Java Language
Description 6: This section examines research into high-level WCET analysis for Java, including techniques and tools that extend traditional compiler theory to Java.

Section 7: Low-level WCET Analysis for Java Bytecode
Description 7: This section delves into approaches for low-level WCET analysis of Java bytecode, focusing on frameworks that address bytecode portability and timing models.

Section 8: WCET Analysis for Java-specific Processors
Description 8: This section explores processor architectures designed specifically for real-time systems, such as the Java Optimized Processor (JOP), and their implications for WCET analysis.

Section 9: Other Work in WCET Analysis for Java
Description 9: This section presents additional work in WCET analysis for Java that does not fall into the main categories, including development environments and optimization frameworks.

Section 10: Conclusion
Description 10: This section summarizes the state of WCET analysis for Java, including open problems and future directions for research.