Transcript Document

Real-Time Java
Angelo Corsaro
[email protected]
Department of Computer Science
Washington University
One Brookings Drive Box 1045
St. Louis MO, 63130 USA
Outline
 Introduction
 Real-Time Java Basics
 Generative Programming
 Performances
 Concluding Remarks
State of the Art
 Most of the real-time embedded systems are currently developed
in C, and increasingly also in C++
 While writing in C/C++ is more productive than
assembly code, they are not the most productive or
error-free programming languages
 C++ is a feature rich, complex language with a steep learning
curve, which makes it hard to find and retain experienced real-time
embedded developers who are trained to use it well
 It is becoming increasingly difficult to find C/C++ programmers
or to retain them
 Companies are starting to struggle with the maintenance costs pf
C/C++ applications
State of the Art
 Java is gaining wide acceptance in different application domains
thanks to its:
 Safety
 Simplicity
 Productivity
 It is becoming relatively easy to find well trained Java
Programmers
 There is the diffused and increasing perception that Java is “Fun”
and C/C++ is not
 Due to its productivity and maintainability, Java is becoming more
and more appealing to the embedded and (soft) real-time market.
Java Limitations

Conventional Java is unsuitable for developing real-time
systems
 The scheduling of Java threads is purposely
under-specified (so to allow easy
implementation of JVM on as many platform as
possible)
 The GC can preempt for unbounded amount of time
Java Threads
 Java provides coarse-grained control over memory allocation, and
it does not provide access to raw memory
 Java does not provide high resolution time, nor access to signals,
e.g. POSIX Signals
Java Limitations

Conventional Java is unsuitable for developing real-time
systems
 The scheduling of Java threads is purposely
under-specified (so to allow easy
implementation of JVM on as many platform as
possible)
 The GC can preempt for unbounded amount of time
Java Threads
 Java provides coarse-grained control over memory allocation, and
it does not provide access to raw memory
 Java does not provide high resolution time, nor access to signals,
e.g. POSIX Signals
What’s the real problem in making Java
Real-Time?
Java and Garbage Collection
 One of the main hurdle for making Java usable in Real-Time
systems comes from its garbage collected nature
 While developer like the facilities provided by the GC, they
cannot afford the unpredictability that they introduce
 At one extreme some Garbage Collectors (GC) work in a stop
the world and collect fashion
Garbage Collection
Processors
P2
P1
time
 Recently, some Garbage Collection algorithms have been
proposed that reasonably bound the delay experienced by the
mutator, however these require either extra hardware, or double
extra heap space or both
Java and Garbage Collection
 The Expert Group that designed the Real-Time Specification for
Java, was faced with the problem of providing automatic
memory management which would be usable by real-time
applications
 Based on the state of the art of GC algorithms, the Expert
Group decided to provide a safe way of circumventing the GC,
while maintaining automatic memory management
 To make the problem more challenging, one of the
requirements was that no extension to the language syntax
was allowed
 As described next, the Expert Group based its solution on
Memory Regions
Road Map
 Introduction
 Real-Time Java Basics
Real-Time Java

The Real-Time Specification for Java (RTSJ) extends Java in the following
areas:
 New memory management models that can be used in lieu of garbage collection
 Access to physical memory
 Stronger semantics on thread and their scheduling
 Asynchronous Event handling mechanism
 Scheduling Service
 Timers and Higher time resolution
Real-Time Java

The Real-Time Specification for Java (RTSJ) extends Java in the following
areas:
 New memory management models that can be used in lieu of garbage collection
 Access to physical memory
 Stronger semantics on thread and their scheduling
 Asynchronous Event handling mechanism
 Scheduling Service
 Timers and Higher time resolution
Real-Time Java

The Real-Time Specification for Java (RTSJ) extends Java in the following
areas:
 New memory management models that can be used in lieu of garbage collection
 Access to physical memory
 Stronger semantics on thread and their scheduling
 Asynchronous Event handling mechanism
 Scheduling Service
 Timers and Higher time resolution

The RTSJ does not extend syntactically the Java language, but simply
strengthen the semantics of certain Java features, and adds libraries
classes
RTSJ Memory Model

RTSJ extends the Java memory model by providing memory areas other
than the Heap

The model used by the RTSJ is inspired to Memory Regions

These memory areas are characterized by
 Lifetime of the object allocated within the memory area, and
 The allocation time

Objects allocated in the ImmortalMemory are guaranteed to exist as long as
the JVM

Objects allocated in Scoped Memories are not garbage collected; instead a
reference counted mechanism is used to detect when all the objects
allocated in the scope can be reclaimed
Scoped Memory Access Rules
 The rules that govern the access to the scoped memory are the
following:
 Only Real-Time Threads can allocate memory in a region different
than the heap
 A new allocation context or scope is entered by calling the
MemoryArea.enter() method or by starting a new real-time thread
whose constructor was given a reference to a scoped memory
instance
 Once a scoped memory is entered all the subsequent use of the new
operator will allocate memory from the current scope
 When the scope is exited by returning from the MemoryArea.enter()
all subsequent use of the new operator will allocate memory from the
enclosing scope
 A Real-Time Thread thread is associated with a scope stack
containing all the memory areas that the thread has entered but not
yet exited
Scoped Memory Behaviour Rules
 The rules that govern the scoped memory behaviour are the
following:
 Each instance of the class ScopedMemory has to maintain a
reference count of the number of threads active in that instance
 When the reference count of the ScopedMemory drops to zero, all
the objects in the area are considered unreachable and candidates
for reclamation
 Each ScopedMemory has at most one parent defined as follows. For
a ScopedMemory pushed on a scope stack its parent is the first
ScopedMemory below in on the stack if it exists the primordial
scope otherwise. A scope that is not pushed on any stack ha no
parent
Single Parent Rule
 The RTSJ defines the single parent rule so to make sure that a
thread can only enter scopes that will live at least as much as
the outer scopes
 The single parent rule is enforced at the point in which a realtime thread tries to enter a scoped memory.
 Traditional algorithms have O(n) time complexities, Corsaro
and Cytron have recently shown how to perform this test in
O(1)
Memory Reference Rules

The RTSJ imposes a set of rules
that govern the validity of
references across memory areas:
 A reference to an object allocated in
a ScopedMemory cannot be allocated
in the Java heap or in the Immortal
memory
 A reference to an object allocated in
a ScopedMemory m can be stored in
an object allocated in a
ScopedMemory p only if p is a
descendant scope of m

Memory reference checks are
performed potentially at each store
so the algorithm used to performs
the checks should be predictable
and efficient
Scoped Memory: An Example
import javax.realtime.*
public class SMSample {
public static void main(String[] args) {
Runnable logic = new Runnable() {
public void run() {
MemoryArea ma2 = new LTMemory(128 * 1024, 128 * 1024);
Runnable nestedLogic = new Runnable(){
public void run() {A a = new A();}
};
m2.enter(nestedLogic);
}
};
MemoryArea ma1 = new LTMemory(512 * 1024, 512 s* 1024);
RealtimeThread rtThread =
new RealtimeThread(null, null, null, ma1, null, logic);
rtThread.start()
}
}
Memory Reference Checking

Every compliant JVM has to perform
memory reference checks in order to
maintain Java safety, avoiding memory
leaks and dangling pointers

Some memory reference checking can
be eliminated at compile time by pointer
escape analysis

Undecidability issues imply that some,
perhaps many, checks still need to be
performed at run-time

Poor implementation of these checks
could adversely impact performances
and predictability

Solution available on literature were not
suitable for many reasons, mostly
because they would lead to problem in
code timing analysis
Memory Reference Checking

Recently, Corsaro and Cytron have proposed an algorithm based on
type theory for performing this test in O(1), as opposed to the O(n)
solution available in literature
Real-Time Threads

The RTSJ extends the Java threading
model with two new types of thread
 RealtimeThread
 NoHeapRealtimeThread

NoHeapRealtimeThread cannot refer to
any object allocated on the heap. This
make it possible for this kind of thread
to preempt the GC

Real-Time Threads provide facilities for
periodic computations

For a Real-Time Thread it is possible to specify
 Release Parameters
 Scheduling Parameteres
 Memory Parameters

Thread execution is managed by the associated scheduler
Event Handling

The RTSJ defines mechanisms to
bind the execution of program logic
to the occurrence of internal and/or
external events

The RTSJ provides a way to
associate an asynchronous event
handler to some application-specific
or external events.

The AsyncEventHandler class, does not have a thread permanently
bound to it—nor is it guaranteed that there will be a separate thread for
each AsyncEventHandler

The BoundAsyncEventHandler class has a real-time thread associated
with it permanently
Scheduling

The RTSJ provides a policy
independent scheduling framework

Only Schedulable entities are
considered for scheduling and
feasibility purpose

The responsibility of the scheduling
framework are:
 Schedule Schedulable Entities
 Performing Feasibility Analysis

 Schedule appropriate handlers in
 Scheduling Parameteres
 Release Parameters
 Memory Parameters
case of error


Different schedulers can potentially
be used within a running
applications
The default scheduler is a PriorityPreemptive scheduler that
distinguish 28 different priorities
Schedulable entities are
characterized by:

Erroneous situations are handled
by event handler associated with
Release Parameters:
 Overrun Handler
 Deadline Miss Handler
Time and Timers

Real-time embedded systems
often use timers to perform
certain actions at a given time
in the future, as well as at
periodic future intervals

The RTSJ provides two types of
Timers
 OneShotTimer, which generates
an event at the expiration of its
associated time interval, and
 PeriodicTimer, which generates
events periodically

Along with timers the RTSJ provides a set
of classes to represent and manipulate
high resolution time, and specifically
 Absolute Time
 Relative Time
 Rational Time
Outline
 Introduction
 Real-Time Java Basics
 Generative Programming
Does One Size Fits All?

While the RTSJ represents an ambitious
step toward improving the state of the
art in embedded and real-time system
development, there are a number of
open issues

The RTSJ was designed with generality
in mind, while this is a laudable goal,
generality is often at odds with the
resource constraints of embedded
systems
Does One Size Fits All?

While the RTSJ represents an ambitious
step toward improving the state of the
art in embedded and real-time system
development, there are a number of
open issues

The RTSJ was designed with generality
in mind, while this is a laudable goal,
generality is often at odds with the
resource constraints of embedded
systems

Providing developers with an overly general API can actually increase the
learning curve and introduce accidental complexity in the API itself

For example, the scheduling API in RTSJ was designed to match any
scheduling algorithm, including RMS, EDF, LLF, RED, MUF, etc.

While this generality covers a broad range of alternatives it may be overly
complicated for an application that simply needs a priority preemptive
scheduler
Can we do any better then this?
Can we provide the needed flexibility and
extensibility, without putting undue
burden on developers?
The Answer is…
Generative Programming
 Generative Programming aims at building
generative models for families of systems and
generate concrete systems from these models
 Generative Programming brings the benefit of Economies of Scope to
software engineering, where less time and effort are needed to
produce a greater variety of products
Generative Programming
 Generative Programming aims at building
generative models for families of systems and
generate concrete systems from these models
 Generative Programming brings the benefit of Economies of Scope to
software engineering, where less time and effort are needed to
produce a greater variety of products
Classical Approach
Design Space
One System
Generative Programming
 Generative Programming aims at building
generative models for families of systems and
generate concrete systems from these models
 Generative Programming brings the benefit of Economies of Scope to
software engineering, where less time and effort are needed to
produce a greater variety of products
Classical Approach
Generative Programming Approach
Design Space
One System
A Family of
Systems
Design Space
Generative Programming
If we consider the RTSJ scheduling API
example, for instance, application developers
that need a simple priority preemptive scheduler
could use generative programming to specify this
as a requirement. The outcome of the generation
process would then be a Realtime Java platform
that exposed only the API needed for a prioritybased scheduler and whose implementation was
also optimized for priority-based schedulers.

Generative Programming (GP)
makes it possible to develop
Software Systems that are
amenable to customization of
behavior and protocols (e.g.,
APIs), via automatic code
generation and composition

Using a GP approach, the
development of middleware,
such as RTSJ or Real-time
CORBA, need not lead to a single
implementation. Instead, it can
provide a set of components and
configuration knowledge that can
be used to generated a specific
implementation based on userdefined specifications
jRate:The Chameleonic RTSJ
 jRate’s is an extension of the GCJ runtime
system that provides a subset of the RTSJ
features such as:





Realtime Threads
Scoped Memory
Asynchrony
Timers
jRate’s goals:


Use a Generative Programming approach to provide a “Chameleonic” Real-Time
Java, which can adapt to its target environment in term of API and functionalities
AOP techniques will be used to produce an untangled, and “pick what you need”
RTSJ implementation



AspectJ, C++ Templates, Python, will be used to do AOP in the Java and C++ portion of
jRate respectively
Provide higher level programming model to developers
Provide advanced scheduling services
Generative Real-Time Java
A Real-Time Java
Specification
Real-Time Java
Specific Concepts
and Features
Configuration
Knowledge
Generated
Real-Time Java Platform
Outline
 Introduction
 Real-Time Java Basics
 Generative Programming
 Performances
RTJPerf & Tested Platforms




RTJPerf is a benchmarking suite for RTSJ compliant platforms that focuses on
Time-efficiency performance indexes.
RTJPerf provides a series of tests based on synthetic workload
RTJPerf currently covers the following RTSJ areas:
 Memory
 Threading
 Asynchrony
 Timers
RTSJ Reference Implementation, developed by TimeSys
 Provides all the mandatory RTSJ features


jRate, an Open Source RTSJ-based extension of the
GCJ runtime system
Currently provide only a subset of the mandatory RTSJ
features
All test were run on a Pentium III 766MHz running TimeSys Linux/GPL
Allocation Time Test
Objective:
 Determine the allocation time for different kind of ScopedMemory
provided by the RTSJ
Technique:
 Allocate vector of characters for different sizes ranging from 32 to 16K
bytes
Tested Platform:
 RTSJ RI
 jRate
Test Parameters:
 1,000 Sample for each chunk size were collected
Test Statistics 1/3
Test Statistics 2/3
Test Statistics 3/3

As the size of the chunk allocated increases the speedup of jRate’s CTMemory over the
RI LTMemory can be as much as 95.

The CTMemory speedup over the LTMemory grows linearly with the size of the chunk
being allocated
Dispatch Delay Latency
Objective:
 Measure the time elapsed from when an event is fired up to when its
associated handler is invoked
Technique:
 Associate an handler with and AsynchEvent, fire repeatedly in lock
step mode the event. Measure the time elapsed between the firing
of the event and the handler activation
Tested Platforms:
 RTSJ RI, jRate
Test Parameters:
 2,000 samples of the dispatch delay time were collected
Sample Trace

jRate’s AsynchEventHandler
and
BoundAsynchEventHandler
have similar performances

The sample trace shows a
very predictable dispatch
delay for jRate

RI’s
BoundAsynchEventHandler
provide a quite good dispatch
delay latency, but is less
predictable


RI’s AsynchEventHandler expose a strange behaviour (caused
perhaps by a resource leaks associated with thread management)
The Dispatch Latency grows linearly with the number of event fired
Test Statistics

jRate’s handlers have worst
cases performances very close
to the average and 99% case

jRate’s handler behavior quite
predictable, as the low std. dev.
indicates

RI’s BoundAsynchEventHandler
has a 99% behaviour that is
very close to the average case
while the worst case behaviour
is a little bit off.

RI’s AsynchEventHandler
exposes an odd behaviour (as
shown previously), so its data is
not very representative
Concluding Remarks

Real-Time Java is a quite intriguing technology, but there is still quite a bit
of R&D to be done in order to make it sound

Many aero-spatial companies and federal research institution have placed
big bets on Real-Time Java, some of these are:
 BOEING
 NASA
 Air Force Research Laboratory
 DARPA

Generative Programming techniques are an interesting topic, and more
research is needed in this area in order to understand:
 GP Pattern and Pattern Languages
 GP Methodologies
 GP Techniques and Tools

jRate provide a vast playground for experimenting with Real-Time Java
features as well as with GP

GP provides a good balance between flexibility and performance/efficiency
References

jRate Web:
 http://tao.doc.wustl.edu/~corsaro/jRate

Papers on jRate:
 http://tao.doc.wustl.edu/~corsaro/papers.html

Real-Time Java Expert Group
 http://www.rtj.org

Reference Implementation
 http://www.timesys.com

Mailing List
 [email protected]

Related Work





GCJ (http://gcc.gnu.org)
FLEX Compiler, MIT
OVM Virtual Machine, Purdue University
JamaicaVM, European Space Agency
PERC, NewMonics