Transcript Doing Firm-Real-Time With J2SE APIs

Doing Firm-Real-Time With
J2SE APIs
By
Kelvin Nilsen, CTO, NewMonics
Delvin Defoe
Center for Distributed Object Computing
Department of Computer Science and Engineering
Washington University
November 14, 2003
Firm real-time vs Soft real-time
 Soft real-time
 “Qué será será”
 Whatever will be, will be
Friday November 14, 2003
Delvin Defoe
2
Firm real-time vs Soft real-time
 Firm real-time
 Disciplined development in which
software engineers carefully analyze
 Deadlines
 Resource requirements
 schedulability
Friday November 14, 2003
Delvin Defoe
3
Firm real-time vs Hard real-time
 Hard real-time
 Resource requirements are determined
using theoretical analysis
 Proven through Mathematical analysis to
meet all deadlines
Friday November 14, 2003
Delvin Defoe
4
Firm real-time vs Hard real-time
 Firm real-time
 Resource requirements are determined
empirically
 Measure behavior of individual
components
 This provides statistical confidence BUT
no absolute guarantees
Friday November 14, 2003
Delvin Defoe
5
Real-Time Specification for Java
 RTSJ is a set of extensions that can
be combined with any existing Java
platforms – J2ME, J2SE, J2EE
 Allows development of real-time
software in Java
Friday November 14, 2003
Delvin Defoe
6
Limitations of RTSJ
 RTSJ Implementations run only with J2ME
and only with LINUX OS
 RTSJ-style RT threads
 Restricted to a set of the J2ME libraries
 Cannot use automatic GC
 Must adhere to strict memory usage guidelines
to obtain RT threading behavior
Friday November 14, 2003
Delvin Defoe
7
Limitations of RTSJ – cont’d
 RTSJ developers cannot invoke offthe-shelf Java software components
from their RT threads
 RT RTSJ components are generally
not portable across OS or between
different compliant RTSJ
implementations
Friday November 14, 2003
Delvin Defoe
8
Alternative to RTSJ - PERC
 A clean room implementation of the J2SE
standards
 It supports J2SE libraries except AWT and
Swing
 Targeted to developers attracted to the
high-level benefits of Java
 Has RT requirements from 1 to 10+ ms
Friday November 14, 2003
Delvin Defoe
9
PERC Virtual Machine features
 Allows each implementation to define
basis for RT development
 Number of priorities
 Synchronization semantics
 Wait queue ordering
 Library compatibility
Friday November 14, 2003
Delvin Defoe
10
PERC Virtual Machine features
 Allows each implementation to define
basis for RT development
 Workload admission test algorithms
 RT scheduling
 I/O interruption semantics
Friday November 14, 2003
Delvin Defoe
11
More PERC VM features
 Run-time system controls scheduling of
Java threads to ensure consistent fixedpriority dispatching and inheritance across
all platforms
 Offers paced RT GC with high reliability
achieved through accurate scanning and
automatic defragmentation of memory
heap
 Delivers of Java’s WORA
Friday November 14, 2003
Delvin Defoe
12
Implementation Choices and
Semantic Guarantees
 Real-Time garbage Collection
 Threading Behavior and Priority
Inheritance
 Improved Timer Services
 The VM Management API
Friday November 14, 2003
Delvin Defoe
13
Real-Time Garbage Collection
 Requirements that must be satisfied by any RT GC
 The collection task must be quickly ‘preemptable’.
Typical VMs require 10s of seconds of CPU time to
perform a complete GC pass
 For RT systems that must dynamically allocate
memory (under RT constraints) the GC progress must
be paced against the applications ongoing need for
memory allocations.
 Requires that GC bounded and incremental so that
after preemption GC resumes where left off
Friday November 14, 2003
Delvin Defoe
14
PERC GC
 Mostly stationary Garbage Collection
 Divides efforts into 1000s of small
uninterruptible increments of work
 When GC resumes following preemption
by a higher priority application thread, it
resumes where it left off
Friday November 14, 2003
Delvin Defoe
15
Incremental Copying garbage
Collection
From-space
To-space
A
C’
B’
B
C
A’
Relocated Reserved
New
Objects B and C are relocated so their valid copies are B’ and C’
Friday November 14, 2003
Delvin Defoe
16
Incremental Mark-and-Sweep GC
 Mark Phase
 Mark each reachable object by linking it onto
scan list
 GC repeatedly removes leading object, L, from
scan-list by advancing scan-list header pointer
 GC scans each of L’s pointer fields in order and
marks the objects it references
Friday November 14, 2003
Delvin Defoe
17
Incremental Mark-and-Sweep GC
 Mark Phase
 GC leaves scan link field of L unchanged
to remember L has been marked
 Scanning of individual objects is
incremental
 Mark phase ends when no more objects
on scan list
Friday November 14, 2003
Delvin Defoe
18
Incremental Mark-and-Sweep GC
 Sweep phase
 Sweep through memory from low to high address
 For each address examined GC knows that it is either
 Start of marked object
 Start of unmarked object or

start of a free segment
Friday November 14, 2003
Delvin Defoe
19
Incremental Mark-and-Sweep GC
 Sweep phase
 Unique bit patterns in object headers
differentiate those address types
 Header info. also identifies the size of
each object, enabling process to skip
over internals of memory segments
Friday November 14, 2003
Delvin Defoe
20
Sweep phase
 Treats each situation differently
 If looking at marked object it clears the mark
field for next GC pass
 If looking at free segment it coalesces it with
previous object (if that object is a free segment)
 If looking at unmarked object it converts it into
a free segment and coalesces it with previous
object
 Coalescing is done in constant time
Friday November 14, 2003
Delvin Defoe
21
Problem with incremental M/S GC
 Application threads that preempt GC may
rearrange relationship between objects
before relinquishing to GC
 This can potentially confuse interrupted GC
 Solution:
 Application thread executes a write barrier
 If GC was marking when it was preempted, the
application thread will automatically mark
referenced object each time it overwrites a
pointer field
Friday November 14, 2003
Delvin Defoe
22
Mostly Stationary Garbage
Collection

Hybrid of Incremental Copying and Incremental Mark-andSweep GC

Divides memory allocation pool into multiple equal-sized
regions

At start of each GC pass selects two regions to serve as
from-space and to-space


These regions defragmented using incremental Copying
technique
Unused memory in other regions is reclaimed using
Incremental M/S technique which does not relocate objects
Friday November 14, 2003
Delvin Defoe
23
Pacing of Garbage Collection

Attribute unique to PERC GC

Total effort required to complete GC is bounded by a
configuration-dependent constant, regardless of how much
memory has been recently allocated or discarded, and
independent of how many times the GC is preempted by
the application

This enables straightforward scheduling of GC to
periodically reclaim all of the dead memory in the system

VM API allows GC scheduling parameters to be adjusted on
the fly to accommodate changes in system workload –
Garbage collection pacing
Friday November 14, 2003
Delvin Defoe
24
Threading Behavior and Priority
Inheritance
 PERC threads behave the same on all
platforms
 PERC VM implements sync. lock not OS
 PERC VM takes full control over which PERC
thread at any instant
 Support priority inheritance
Friday November 14, 2003
Delvin Defoe
25
Improved Timer Services
 PERC VM provides programmers with
precise control over time-constrained Java
Software components
 com.newmonics.util.Timer class offers different
semantics from java.util.Timer
 Notion of time is not affected by OS RT clock
drifts or modified by human operators
 Notion of time is maintained internal to PERC
VM
Friday November 14, 2003
Delvin Defoe
26
Improved Timer Services
 PERC VM associates a
com.newmonics.pvm.PercThread object with each
java.lang.Thread
 Provides access to additional time-related info. for
threads
 Provides sleepUntil() and waitUntil() methods which
can be used to implement non-drifting periodic and
absolute timeouts
 PERC VM allows developer to set tick period and the
duration of each tick
Friday November 14, 2003
Delvin Defoe
27
The VM Management API
 In the case of embedded systems PERC
makes it possible for software agents to self
configure the embedded system
 The GC pacing agent in PERC 4.1 is an
example of one such agent
 It monitors trends in allocation rates, live
memory retention, and object longevity
 Uses this info. to govern the rate at which GC is
performed
Friday November 14, 2003
Delvin Defoe
28
The VM Management API
 The GC pacing agent in PERC 4.1 is
an example of one such agent
 Objectives are to dedicate to GC exactly
the amount of CPU time it needs and no
more
 In overload situations, it raises alert
signals rather than interfering with
higher priority RT threads
Friday November 14, 2003
Delvin Defoe
29
Relevant Application Domains
 Network Elements
 Automation
 Commercial Telematics
Friday November 14, 2003
Delvin Defoe
30
Limitations of PERC
 Not recommended for hard real-time
applications
 Typical PERC-based deployments are
about 3 times as large as and run at
about 1/3 the speed of equivalent C
programs
Friday November 14, 2003
Delvin Defoe
31
Future Work
 Extend PERC to include hard-real-time Java
technologies
 Add the capability to asynchronously interrupt a
particular thread’s execution to the PERC run-time
environment
 Add the ability to establish time and space partitions
for particular RT software components
 Add an appropriate firm-real-time scheduling
framework on top of firm-real-time Java technologies
Friday November 14, 2003
Delvin Defoe
32
Questions?
Friday November 14, 2003
Delvin Defoe
33