Real-time Java on Linux

by Robert Staudinger

Email: robert@stereolyzer.net

Abstract

The goal of this diploma thesis is the development of a virtual machine (e-machine) for the execution of TDL e-code based on a real time capaple extension of the Java Virtual Machine (JVM). The aplicability of the realtime extension (package javax.realtime) has to be analyzed as part of the diploma thesis. Further research has to be conducted regarding the possible development of distributed realtime applications. If so, at leased a limited prototype of a distributed e-machine hast to be implemented. A java based prototype is provided for the diploma thesis as a starting point. This prototype however does not fulfill any realtime requirements.

Table of contents

List of figures 2

1 Introduction 2

2 Basic Principles of Realtime Systems 2

2.1 Definition and Classification 2

2.2 Synchronization of Resource Access 3

2.3 Task Scheduling 3

2.3.1 Definitions and Explanations 3

2.3.2 Scheduling Algorithms 3

2.4 The Time Triggered Architecture (TTA) 4

3 The POSIX Real-time Specification 4

4 Realtime Linux 4

4.1 Approaches 4

4.2 Implementations 4

4.2.1 Timesys Linux 4

4.2.2 RTLinux 4

4.2.3 RTAI 4

5 The Realtime Specification for Java (RTSJ) 5

5.1 Thread Scheduling and Dispatching 6

5.2 Memory Management 6

5.3 Synchronization and Resource Sharing 7

5.4 Asynchronous Event Handling and Timing 7

5.5 Asynchronous Transfer of Control (ATC) 7

5.6 Asynchronous Thread Termination 7

6 Real-time Java Implementations 7

6.1 Timesys RTJ 7

6.2 jRate 7

7 Benchmarks 7

Bibliography 7

List of figures

Threading Class Hierarchy 5

Memory Management Class Hierarchy 5

Synchronization Class Hierarchy 6

Asynchronous Event Handling and Timing Class Hierarchy 7

1 Introduction

Realtime applications and platforms - for example in control systems - already have a long tradition in the world of computing. The first proposal for operating a computer in realtime was published in 1950. This proposal built on the assuption that analog-computing technology would be used. The first realtime computers were developed in 1954 to serve airborne operation. It provided an automated flight and weapon control system.

From the 1960s realtime systems were used in industrial environments. In the 1970 the availability of microprocessors and fast memory shifted attention to the problem of writing reliable and dependable computer control software.

2 Basic Principles of Realtime Systems

2.1 Definition and Classification

It is not possible to find a single valid definition for Realtime Systems. Therefore two examples are given. The Oxford Dictionary of Computing defines them as:

Definition 1. "A system in which the time at which the output is produced is significant. This is usually because the input corresponds to some movement in the physical world, and the output has to relate to that same movement. The lag (delay) from the input time to output time must be sufficiently small for acceptable timeliness".

This definition covers a wide range of possible applications which could involve everything from manually operated workstation computers to industrial applications and aircraft control systems. The Journal of Systems and Control Engineering defines Realtime Systems as:

Definition 2. "Real-Time Systems are those which must produce correct responses within a definite time limit. Should computer responses exceed these time bounds then performance degradation and/or malfunctions results"

Apart from highlevel definitions it is possible to classify Realtime Systems by the way they interact with their environment. The following classes of systems can be distinguished by how a systems' internal processes synchronize with the environment:

Clock based:
operations are carried out following a previously known time schedule.
Event based:
actions are triggereded in response to occurring events which don't follow a schedule. Neither time nor order of the events is previously known.
Polling:
similar to event based but the system periodically fetches data from its sensors and reacts in order to the given input state.
Interactive based:
a rather loosely defined class of Realtime Systems. The requirement is for the system to complete a given task within a predetermined time limit. An example would be an automated teller machine which requires user interaction to complete a series of tasks ( process ). If, for example, there is no more user interaction for more than 5 minutes an insered card might be kept within the teller machine.

A further possibility of classification is the division by time constraints. While for example video processing applications might satisfy the user by meeting certain average requirements time critical industry control systems have to comply to deterministic standards for every isolated operation like reading a single sensor value. These two examples already define two main categories:

Soft Realtime:
in soft realtime systems occasional failure to meet a deadline does not result in critical malfunction. Average response times define the quality of such a system.
Hard Realtime:
hard realtime systems have to satisfy the specified deadline on each and every operation. A single miss can leave the system in an inconsistent state and result in wrong output or system reaction.

2.2 Synchronization of Resource Access

Multithreading environments are useful to decouple different activities. Sometimes those decoupled entities of execution need to access common resources like memory or I/O channels which can only be used mutually exclusive at any given time. They are competing for access to the mentioned resources. Protocols are needed to resolve that situation in predictable ways and to ensure that resource usage by non-critical activities does not interfere with the needs of critical operations.

To explain the Priority Inheritance Protocol uses a low priority thread L which should hold a lock on a resource which a high priority thread H wants to access. The problem is resolved by inheriting the higher priority of thread H to the lower priority thread L if L is holding a lock on a shared resource which H wants to lock.

On the other hand the Priority Ceiling Emulation Protocol (also known as Highest Locker Protocol) uses monitors to guard access to shared resources. A priority is assigned to each monitor. This known priority is the highest priority of any thread which could attempt to enter the monitor. As soon as a thread enters mutually exclusive code its priority is raised to the priority of the monitor. So the thread will not be preempted by any other thread that could attempt to enter the monitor and mutually exclusive access is guaranteed. The case of a thread with a higher priority than the ceiling entering the monitor is considered an error. In the case of the Realtime Java Specification an exception has to be thrown.

2.3 Task Scheduling

2.3.1 Definitions and Explanations

Static: Schedule determined a priori

Dynamic: Schedule determined at run-time

Priority Driven: Each task assigned a priority

Fixed priority assignment: Priorities assigned statically

Preemptive: Higher priority task preempts lower priority task

2.3.2 Scheduling Algorithms

Polled Loop
Interrupt-based Systems
Earliest Deadline First (EDF)
Earliest Nextstart First (ENF)
Minimal Processing Time First
Rate Monotonic Scheduling (RMS)
Deadline Monotonic Scheduling (DMS)
Foreground-Background Scheduling
Task Pair Scheduling
Minimum Earliest Start ? ENF
Minimum Laxity First

2.4 The Time Triggered Architecture (TTA)

from here

3 The POSIX Real-time Specification

4 Realtime Linux

4.1 Approaches

4.2 Implementations

4.2.1 Timesys Linux

4.2.2 RTLinux

4.2.3 RTAI

5 The Realtime Specification for Java (RTSJ)

The Realtime for Java Expert Group (RTJEG) identified seven guiding principles when working out the RTSJ.

Applicability to particular Java Environments:
The RTSJ should be applicable and implementable for any version of the Java Runtime Environment (JRE) such as Micro Edition and Standard Edition.
Backward Compatibility:
Applications developped for a non realtime Java Environment should still be able to run in a Real-time JRE.
Write Once, Run Anywhere:
WORA should be an important principle for the development of the RTSJ but binary compatibility should not be maintained at the expense of predictable execution.
Current Practice vs. Advanced Features:
Current realtime practice should be addressed but future implementations shoud be allowed to implement advanced features.
Predicatable Execution:
In all tradeoffs predictable execution should be the first priority, even if this has negative effect on general purpose computing performance.
No Syntactic Extension:
Syntactic extensions to the Java language and new keywords should be avoided to ease the development of tools.
Allow Variation in Implementation Decisions:
A certain degree of freedom in the choice of implementation details like particular algorighms should be possible to allow implementations which are able to meet certain requirements.

From these basic principles eight areas of extended semantics have been defined which are relevant to realtime programming tasks. These areas will be discussed in detail in the following sections.

5.1 Thread Scheduling and Dispatching

The RTSJ introduces the interface Schedulable to facilitate the creation of asynchronously executeable sequences of machine instructions. Common names for such sequences include threads, tasks, modules and blocks.

Instances implementing the interface Scheduler are designed to manage schedulable objects. The initial and default scheduling algorithm which is required by the RTSJ is the PriorityScheduler. This scheduler is fixed-priority preemptive and has to support at least 28 unique priority levels.

Figure 1. Threading Class Hierarchy

5.2 Memory Management

In Standard Java a so called Garbage Collector (GC) runs as a separate thread of execution. From time to time the gc thread preempts the execution of application code and returns memory areas which are no longer in use to the operating system. This behaviour makes it impossible to write real-time applications because it is not predictable when the gc will become active.

The RTSJ intoduces several extensions which enable the programmer to take care about the memory which is used by the real-time application by making it possible to allocate objects which are not under the control of the GC. This is achieved by the introduction of a concept called Memory Area. The gc however must be able to scan these memory areas in order to check for references to any objects under its control when freeing unused memory. Memory areas can be grouped into four basic categories.

Scoped Memory:
For objects which have a lifetime determined by syntactic scope like for example local variables. Once a scope is created it can be entered programmatically or associated to an instance of RealtimeThread . It is also possible to nest scopes but objects allocated within a certain scope cannot be assigned to variables outside that particular scope because of lifetime constraints. When a scope is left all the objects within are freed and the previously occupied memory is returned to the system.
Physical Memory:
To facilitate the creation of objects in predetermined areas of memory. This feature could be used to manage a certain group of objects is fast memory parts of an embedded system.
Immortal Memory:
The use of immportal memory makes it possible to create objects which exist until the end of the application. Immortal Memory is a shared resource among an applications threads.
Heap Memory:
The lifetime of objects on the heap is determined by visibility and under the control of the GC.

Figure 2. Memory Management Class Hierarchy

By using memory areas it is also possible to define memory allocation budgets for threads. This makes it possible to limit a threads overall memory consumption and maximum allocation rates by specifying these parameters at thread creation.

5.3 Synchronization and Resource Sharing

The RTSJ facilitates the creation of serializable resource access logic by extending the semantics of the java keyword synchronized. In addition to that a set of wait-free classes make it possible for threads which have higher execution eligibility than the GC to prevent priority inversion.

Figure 3. Synchronization Class Hierarchy

Threads which are waiting to mutually exclusive lock a resource must be dispatched in order of their respective priority. If the current scheduling policy allows threads with the same priority they are awakened in FIFO order. The defines the following criteria for the implementation of wait queues:

The implementation of the synchronized primitive has to ensure that unbounded priority inversion does not occur in any case. The priority inheritance protocol has to be implemented by default. As a second policy the priority ceiling emulation protocol (also known as highest locker protocol) is specified by the RTSJ and can be implemented on systems which offer support for it.

5.4 Asynchronous Event Handling and Timing

The RTSJ defines a number of classes which can be utilized to implement program logic which executes triggered by asynchronous events. The event itself as well as the code which is to be executed as a reaction is represented by objects. Scheduling and dispatching of those blocks of codes is implemented by a scheduler in a manner comparable to threading. Possible types of events include

Figure 4. Asynchronous Event Handling and Timing Class Hierarchy

For time driven events the abstract class Timer and its subclasses PeriodicTimer and OneShotTimer represent time driven events. Timers are in turn driven by instances of Clock.

5.5 Asynchronous Transfer of Control (ATC)

ATC is a concept which makes it possible to programmatically react to drastic changes in the real world. This makes it possible to efficiently react to unanticipated changes in a programs environment. To guarantee that an application and the hardware it is running on are continuing in a consistant state threads which permit ATC must indicate their susceptibility to this concept. Otherwise the transfer of control is deferred until control is in an ATC-enabled block. This ensured backward compatibility with legacy code. But even in ATC-enabled threads the programmer might ensure that certain blocks of code are completed. Therefore the semantics of the synchronized keyword have been extended to prevent ATC. In addition to that it is not possible to give back control to the point where ATC has been triggered.

5.6 Asynchronous Thread Termination

Older versions of the JRE could leave shared objects in an inconsistant state when terminating threads using the method stop(). That's stop() is now deprecated and might be removed in newer versions. Utilizing destroy() to terminate a thread can lead to deadlocks if the destroyed thread had been holding a lock and although the method has not been declared deprecated yet its use is discouraged.

The RTSJ introduces the interrupt() method as a safe way to asynchronously terminate a thread by using a combination of asynchronous event handling and ATC.

6 Real-time Java Implementations

6.1 Timesys RTJ

6.2 jRate

7 Benchmarks

Bibliography

[1]
Bollella, Greg et al. The Real-Time Specification for Java . Addison-Wesley, One Lake Street, Upper Saddle River, NJ 07458, 2000.
[2]
Han, Maung Aung et al. Thread scheduling and dispatching. 2001. CIS 642: Seminar in Real-time Systems, Thread Scheduling and Dispatching.ppt.
[3]
Kopetz, Hermann. Time triggered architecture. ERCIM News No. 52 , January 2003. http://www.ercim.org/publication/Ercim N ews/enw52/EN52.pdf.
[4]
TODO. Oxford Dictionary of Computing . TODO, Oxford, 2000.