Transcript Document

Towards Programming Safety
Critical Systems in Java
Bent Thomsen
Aalborg University
Joint work with:
• Martin Schoeberl
– Institute of Computer Engineering
Vienna University of Technology, Austria
• Hans Søndergaard
– Vitus Bering University College
• Stephan Korsholm
– Polycom (former KIRK telecom) and CISS
• Anders P. Ravn, Thomas Bøgholm, Henrik KraghHansen, Petur Olsen, Kim G. Larsen, Rene R. Hansen
and Lone Leth Thomsen
– CISS/Department of Computer Science
Aalborg University
2
Computers today
A computer is a grey box full of black smoke.
When the black smoke escapes the computer
does not work any more
Anonymous CS student
3
Some have a broader view
4
But what about these?
5
Especially this one
• JOP - Java Optimized Processor
6
Embedded Systems
• Computer purchased as part of some other piece of
equipment
– Typically dedicated software (may be user
customizable)
– Often replaces previously electromechanical
components
– Often no “real” keyboard
– Often limited display or no general purpose
display
7
Real-time Systems Landscape
• Interaction software
– Psychology
• Signal processing
– Compute as much as possible within deadline
• Media processing
– QoS, graceful degradation
• Control software
– Catastrophic consequences of missed
deadlines
8
High Integrity Embedded RealTime Systems
•
•
•
•
•
Implemented in hardware
Customized components
Hardware specific software
Poor reusability
Specially trained programmers
– Assembler and C (and C++) dominate
embedded systems programming
– Still at lot of Ada programming going on
9
What is the problem?
• Sheer number of systems
• Poor programmer productivity
– Fewer and fewer C/C++ programmers
10
How to increase Programmer
Productivity?
3 ways of increasing programmer productivity:
1. Process (software engineering)
– Controlling programmers
– Good process can yield up to 20% increase
2. Tools (verification, static analysis, program generation)
– Good tools can yield up to 10% increase
3. Better designed Languages --- the center of the universe!
– Core abstractions, mechanisms, services,
guarantees
– Affect how programmers approach a task (C vs.
SML)
11
– New languages can yield 700% increase
Why Java
•
•
•
•
•
•
•
Easy to learn
Early (first) programming language
Object oriented
Industrial strength
Platform independent
Concurrent
(Almost) Well-defined semantics
12
Java is all around us
Java-enabled Handsets
1,600
Units (in million)
1,400
1,200
1,000
1B
installed
base in
2006
800
600
400
200
0
2004
2005
Installed Base
2006
2007
2008
Annual Shipment
13
Even in space
14
Java Disadvantages wrt. Real-time
• Unpredictable performance
– Scheduling
– Memory
– Control and data flow
• Automatic garbage collection
• Dynamic class loading
15
Real-Time Specification for Java
•
•
•
•
RTSJ for short
First JSR request (JSR-001)
Still not completely finished
Implementations
– Timesys RI
– OVM (Purdue)
– PERCS (AONIX),
– JamaicaVM (AICAS)
– McKinack (SUN) based on Hotspot
– Websphere (IBM) based on J9
16
RTSJ Guiding Principles
•
•
•
•
•
Backward compatibility to standard Java
Write Once, Run Anywhere
Reflects current real-time practice
Predictable execution
No Syntactic extension
– But subtle changes to semantics
• Allow implementation flexibility
17
RTSJ Overview
•
•
•
•
•
•
•
•
Clear definition of scheduler
Priority inheritance protocol
NoHeapRealtimeThread
BoundAsyncEventHandler
Scoped memory to avoid GC
Low-level access through raw memory
High resolution time and timer
Targeted at larger systems
– implementation from Sun requires a dual
UltraSparc III or higher with 512 MB memory
18
and the Solaris 10 operating system
RTSJ Subset
• Ravenscar Java
– Name from Ravenscar Ada
– Based in Puschner & Wellings paper
•
•
•
•
•
•
Profile for high integrity applications
RTSJ compatible
No dynamic thread creation
Simplified scoped memory
Targeted at Java 2 Micro Edition
Implementations?
– Partial on aJ-100 at CISS/AAU
19
Observation
There is essentially only one way to get a
more predictable language:
• Namely to select a set of features which
makes it controllable.
• Which implies that a set of features can be
deselected as well
20
The bottom up approach
1.
2.
3.
4.
5.
6.
7.
take the Java language and its associated VM
provide low level access to physical memory (and
interrupts),
add an interface to a scheduler which is some mechanism
that gives predictability to thread execution, and which
implements some policy that is specified through release
and scheduling parameters,
add an interface to some memory areas controlled by
mechanisms that may give more predictable allocation of
objects,
add some mechanism to make synchronization more
predictable,
add new classes of asynchronous events and their handlers,
and internal event generators called timers related to clocks,
and try to come to terms with asynchronous transfer of
control and termination.
21
Life is complicated enough
• apart from 1 and 2, the remaining ”enhancements”
complicate life for a programmer
• source program for an application becomes a mixture of
– application specific requirements
• (deadlines, periods, binding of external events, and program logic),
– parameters for controlling policies of the underlying middleware
mechanisms
• (cost, priority, importance, event queue sizes, memory area sizes),
– parameters for tuning or sidestepping the mechanisms
• (miss handlers, timers).
22
Our Target Community
Real-Time
Computing
SC Java
Control
Engineering
Control in Real-Time Computing
Real-Time Programming Techniques
in Control System Implementation
23
A typical embedded program
Cruise control:
Loop
Read the sensors;
Compute speed;
if speed too high
Compute pressure for brake pedal;
if speed too low
Compute pressure for accelerator;
Transmit the outputs to actuators;
24
FOSS WineScan Case Study
FTIR instrument
Interfero
-gram
enclosed in a
Thermobox

FTIR technology: Fourier Transform Infrared Spectroscopy
25
Interferometer functional
requirements
The instrument
• Temperature reading and regulation
 thermobox, cuvette, interferometer,
IR-source
 reading: 5 times/sec
 regulation: 1 time/sec
• Interferometer measurement
 move the mirror and read IR-detector
 every 333 µs
 up to 3200 times in a scan
 an interferometer measurement
 32 scans
Thermobox
26
Our approach
• the Java language and machine supported
by existing RT mechanisms and policies
• low level access to hardware, since
hardware abstraction layers are yet in the
future
• plus periodic and sporadic threads with
application specific parameters, including
program logic
27
The Aim
•
•
•
•
•
An easy to use framework
Simplified program analysis
Easy to implement on embedded systems
Minimum implementation details
J2ME programmers should be able to
learn to use SC Java in a day
28
SC Java Programming Model
Initialized: An RT application is in the Initialized state until
the initialization code of the RealTimeSystem has
run to completion and its start method has not been
invoked. Application threads and passive objects are
created and initialized here. Threads are not started.
Mission: An RT application is in the Mission state when
it has returned from its start method which starts all
threads.
Stop: An RT application is in the Stop state when it has
returned from the stop method which waits for threads
to perform their optional cleanup.
29
Difference to RTSJ
• No Initializer Thread
– Done as part of main method
• No WaitForNextperiod
– Scheduler does this
• No priorities
– Programmer Specify deadline and periods
– Scheduler calculates priorities
30
Only few concepts
•
•
•
•
•
Periodic Threads
Sporadic Threads
RunTimeSystem
Relative Time
Immortal and Raw Memory
31
Schedulable Entities
All schedulable entities (periodic and sporadic) are
represented by threads.
The abstract class RealtimeThread has two methods:
• run()
– the run logic to be executed every time the thread is activated
• cleanup()
– a clean-up method to be executed if the system should be shut
down or stopped
Initialize is done in main()
32
The Class Diagram
33
The RealtimeThread Class
34
PeriodicThread
35
SporadicThread
36
The Runtime System
37
An example
38
Implementations of SC Java
• On Ajile aJ-100 and JOP
– Use existing schedulers and threads
• On Mechatronic Brick and Polycom (Kirk)
– Currently experimenting with JamVM
• Implementation on RTSJ underway
39
What about Program Analysis?
• Traditional approaches to analysis of RT
systems are hard and conservative
• Alternatives via:
– Java PathFinder
– SARTS
• WCET and Schedulability on JOP
40
Utilisation-Based Analysis
• A simple sufficient but not necessary
schedulability test exists
N
Ci
1/ N
U 
 N (2
 1)
i 1 Ti
U  0.69 as N  
Where C is WCET and T is period
41
Response Time Equation
 Ri 
Ri  Ci    C j
jhp ( i ) T
 j
Where hp(i) is the set of tasks with priority higher than task i
Solve by forming a recurrence relationship:
win 1
 win 
 Ci   
Cj

jhp ( i )
 Tj 
0
1
2
n
w
,
w
,
w
,...,
w
,.. is monotonically non decreasing
The set of values i i i
i
When win  win 1 the solution to the equation has been found, wi0
must not be greater that Ri (e.g. 0 or Ci )
42
Java PathFinder
Java Code
Bytecode
void add(Object o) {
buffer[head] = o;
head = (head+1)%size;
}
Object take() {
…
tail=(tail+1)%size;
return buffer[tail];
}
JAVAC
0:
1:
2:
5:
8:
9:
10:
iconst_0
istore_2
goto
#39
getstatic
aload_0
iload_2
aaload
JVM
Model
Checker
Special
JVM
43
SARTS
• WCET and Schedulability analyzer for Java
programs written in the SCJ profile (PRTJ)
• Assumes correct Loop bounds annotations
• Generated code to be executed on JOP
• Generates Timed Automata
• Control flow graph with timing information
• Uppaal Model-checker checks for deadlock
44
SARTS Overview
45
Java to UPPAAL
46
Timed Automata templates
• Translation of Basic
Blocks into states and
transitions
• Patterns for:
–
–
–
–
–
Loops
Monitor statements
If statements
Method invoke
Sporadic task release
47
Simple models of RM scheduler
• Predefined models
– Scheduler
– Periodic Task
– Sporadic Task
48
Periodic Task/Sporadic Task
49
SARTS can do better than utilisation test
• Example
• One periodic task
• Two sporadic tasks
– Mutually exclusive
50
SARTS can do better than utilisation test
•
•
•
•
•
Period: 240
Minimum inter-arrival time: 240
Periodic cost: 161
Sporadic cost: 64
Utilisation test fails:
51
Time Line
52
real-time sorting machine
53
SARTS future work
•
•
•
•
•
Cache analysis
Different scheduling strategies
Memory usage analysis
Multicore
IDE integration
54
Java Objects Project
•
•
•
•
•
•
•
•
CISS/DPT CS AAU
Vitus Bering Denmark
Polycom (Kirk telecom A/S)
Wirtek A/S
Mechatronic Brick ApS
Aalborg Industries A/S
Prevas A/S
Teknologisk Institut
J
B
J
O 55
Project Objectives
•
•
•
•
•
Porting JVM on various hardware platforms
WCET and other prgl. analysis
Integration into IDE (eclipse)
Legacy programming (not JNI)
Applications, applications …
56
The missing parts
• Standard Libraries
• Generalised phases
• Generalised WCET analysis
– Works for JOP!
• Memory usage analysis
• Memory mechanisms
– Immortal and local (with weak references) memory
57
Standard Library
• Problems with existing libraries:
– Use a lot of dynamic allocations
– Bad for WCET and memory usage
– Focus on improved average performance
• Javolution
– Reuse memory
– Focus on WCET, but no guarantees
– Focus on predictability
58
Standard Library
• Canteen
–
–
–
–
–
–
Implements List, Set and Map
WCET analysis possible
Does not throw exceptions
No memory allocation in mission phase
Support for generics
Use standard interfaces (almost)
59
Generalised Phases
• JSR 302 proposal by The Open Group:
60
Generalised Mode Change
61
Mode Change Requirements
Requirements the transition from mode mi to the next mode mj must
satisfy:
R1. When a Mode Change Request (MCR) has occurred, a transition
from mode mi to mode mj must take place
R2. Continuing tasks belonging to both mode mi and mode mj are
permitted
R3. A mix of old tasks from mode mi and new tasks from mode mj must
not be concurrently active
R4. All real-time requirements of the system must be met (deadlines,
periods, etc.)
R5. The mode changes of the system must happen within a bounded
time δt
62
Mode Change Contract
C1. Each mode m in {m1,..,mn} has a fixed set of periodic or sporadic
tasks τ(m) which are individually schedulable under a given
scheduling discipline
C2. A specific event, MCR, is designated as request to change from a
current mode mi to a new mode mj
C3. When a MCR occurs, the task set τ(mi) of the current mode mi
remains active till a time-interval, Δt idle, within a delay δt(mi) after
MCR, after which the task set τ(mj) of mode mj is active
C4. Periodic and sporadic tasks that occur in both mi and mj remain
periodic and sporadic over the mode change
63
64
SC Java Programming Model
• Periodic/sporadic tasks with constant period,
hard deadline, and known WCET
• Just a model:
– Does not fit all control problems
– Overly restrictive for many control problems
65
JSR 302
• Safety Critical Java Technology
• This specification creates a J2ME capability,
based on the Real-Time Specification for Java
(JSR-1), containing minimal features necessary
for safety critical systems capable of
certification, e.g., DO-178B
66