Re: Higher-level Real-time (was Re: An Invitation to the Real-Time Java Commu

[P.H.Welch@xxxxxxxxx]

Bill Foote <Bill.Foote@xxxxxxxxxxx> wrote (in "msg00363.html"):

> Oyvind Teig <Oyvind.Teig@xxxxxxxxxxxx> worte:
> > -------------------------------------------------------------------------
> >
> > The program (bottom) using Java's "synchronized" will behave=20
> > differently on Sun's JVM and Kaffe JVM, due to different=20
> > implementations / unspecified semantics of synchronized. Today,
> > scaling programs with that concept seems scary..
>
> It's not the concept that's at fault here, really.  The problem exposed
> by Peter Welch's example is that the semantic specification of synchronized
> isn't tight enough ...

I'd like to summarise some worries about the use of Java for real-time and/or
safety critical applications.  These worries may be self-inflicted because
I want to make, implement and maintain designs that are *multithreaded*.
The reason I want to use multithreading is because that's the way the world
seems to work and kicking against nature makes things needlessly complicated.
If multithreading is making things harder, we're not doing it right!

Multithreading should make things *simpler* ... ;-)


Safety and Liveness problems in Java
------------------------------------

The common design patterns we have found for working with Java's threads and
monitors seem to be aimed at *safety*.  The synchronized methods and blocks
give a simple way of ensuring exclusive access to shared objects and, so,
avoid some basic race hazards.  The standard pattern of `wait' within
a while-loop that checks the wait-condition (and a `notifyAll' whenever
someone sets up a condition on which someone else may be waiting) does
guarantee, allbeit somewhat inefficiently, that we only proceed when safe
to do so ... where "safe" means that the wait-condition has actually been
satisfied.

Despite this, race hazards remain a serious deterrent to the widespread
expoitation of multithreading in Java.  The above patterns do not deal
with the accidental sharing of objects resulting from overlooked duplication
of pointers, which is something that needs a strong -- and, ideally, machine
checked -- discipline to control.

But we also need to concern ourselves with *liveness* ... will our system
actually do anything in time for that doing to be useful?  Of course,
this also impacts on safety issues.  A car braking control system that
refuses to apply the brakes when the driver presses the pedal because
it hasn't acquired the relevant monitor lock (that's currently owned
by some smart collision detection thread) is not safe.

The example Oyvind quotes shows an alarming consequence of the lack of
specification (in `standard' Java) of how threads wait when they can't
get a resource.  The particular case involves invoking a synchronized
method that guards access to some shared resource.  Three threads
are competing to use the resource.  Running on Sun's JVM, each thread
gets its fair share of the resource.  Yet running on the perfectly
legal Kaffe JVM, one thread ("B") is permanently refused access.

Although the resource itself is overloaded and almost 100% utilised,
the JVM controlling access to that resource is almost totally idle --
yet fails to guarantee any access.  Kaffe's problem is that it seems
to *stack* threads waiting to acquire the monitor lock.  Poor old "B"
gets stuck at the bottom of the stack, with threads "A" and "C" taking
turns to sit on top of it or hold the lock.  Sun's JVM, on the other
hand, puts waiting threads in a *queue* and everyone has fair shares.

So, maybe for an embedded JVM, queueing for these locks should be
specified?  But there may be an efficiency problem in enforcing strict
FIFO semantics on a multiprocessor platform ... or there may be cache
hit-rate problems ... which maybe why the rules were never made??

But all we really need is a guarantee that, so long as our system is
deadlock-free and that each use of a locked resource lasts a finite/bounded
time, every attempt to synchronize will eventually succeed.  We don't
have this guarantee at the moment.  For practical reasons, we may need
to put a bound on this "eventually" -- perhaps that it is linearly
dependent on the number of threads synchronizing on the resource.
A queue implementation of waiting gives us this guarantee, but so also
do some weaker structures that don't necessarilly promise FIFO behaviour
(and may have an efficient distributed and cache-kind implementation).

BUT ... provision of this "will-eventually-synchronize" guarantee, whilst
necessary, is not sufficient to ensure *liveness*.

The "Wot, no chickens?" example, refered to in an "msg00290.html", shows
a greedy philsopher starving to death in Sun's JVM (which fairly queues
waiting threads), but surviving in the Kaffe one (which stacks them).
This example is more complex than the "A/B/C" one.  Once a philosopher
gets a lock on the canteen, he/she gets put on hold (i.e. executes wait)
if the favoured dish (chicken) is not available.  When the chef turns
up with more chickens, waiting philosphers get notified and have to fight
to reaquire the canteen lock.

The greedy philospher, who never thinks but is always at the canteen looking
for food, lives a life shuffling through one queue after another -- first
for the canteen lock, then on hold, then for the canteen lock, then on hold
etc.  He is always in the wrong place when the chickens turn up and his
colleagues (who spend some time away from the canteen thinking) always manage
to grab them first.

The canteen monitor class applies all the approved Java design rules: it
makes the customers wait for chickens in a while-loop and gets the chef
to notifyAll when more chickens are ready.  The processor implementing
the canteen is almost totally idle almost all the time.  The JVM running
on that processor strictly FIFOs all threads waiting to synchronize and
all threads waiting to be notified.  The customer still starves.


Which brings us to CSP
----------------------

CSP is the theory Hoare came up with *after* his work on monitors (on which
Java threads are loosely based).  It provides a formal handle on problems like
deadlock, livelock and starvation.  Its primitive operations (such as process
synchronisation) can be implemented with overheads pushing 200 nanoseconds on
modern microprocessors.  Its learning curve is almost zero (two hours?) since
its concepts -- basically networks of "components" connected by "wires"
(where each component could itself be another network) together with some
simple synchronisation primitives -- are common, but unformalised, knowledge.

CSP objects are active processes.  Monitors are passive things which cannot
prevent their methods being called when they are not in a state to receive
them -- hence the wait/notify mechanism to get around such an embarassment.
CSP processes, being active, can *refuse* to accept calls when they are
not in an appropriate state -- so there need never be any embarassment!
When a process accepts a call, its handler always has the necessary resources
to deal with it (otherwise, it would not have accepted it).

So, the CSP version of the "Wot, no chickens?" canteen keeps all its
customers at bay in *one* queue (or weak-queue).  This is much simpler
to comprehend than the monitor version which has *two* waiting areas
and, in some unfortunate circumstances, can leave a customer forever
shuffling between them.

CSP also does not have another problem that arises from the wait/notify
semantics within monitors.  When one monitor method is forced to "wait()",
it relies on another thread aquiring the monitor and executing the needed
"notify()" -- or "notifyAll()".  This means that the logic within the
monitor methods involved in this wait/notify has to be tightly coupled.
Usually, at least two methods will be involved and, sometimes, many more.
To understand how one works, we have to understand how they all work ...
they can't be studied independently.  This type of logic scales very badly!
Claim: CSP logic scales very well ... ;-)

So, what about CSP-for-Java?  The first message is that Java is quite
compatible with CSP -- it does *not* need changing.

The monitor/threads model is not really burnt into the language.  It's provided
by the "java.lang" package.  Even the keyword "synchronized" is now treated as
an implementation detail (rather than a semantic one) by the JDK1.2 "javadoc"
tool.

In the same way, the CSP model can be provided by a (100% pure Java) package.
Two libraries are available -- see the "jcsp.lang" package of JCSP [1] or
the "csp.lang" package of CTJ [2].  Both of these do the job.  The new thing
to learn is the CSP *design-pattern* for using (either of) these libraries.
Claim: this is a *much* easier design pattern to learn and apply than the one
for the monitor/thread classes.

Note that this fits happilly with Bill's comment:

> One thing to think about is the difference between "a standard" and
> "the standard."  To take the CSP example, I think that would be a
> great optional standard extension, but I think it would be bad if it
> were the only way to do real-time in Java.

We are only offering the use of a library ... its use is optional and no
language extension is needed!

The second message is that, in being 100% pure Java, the CSP primitives (in
these libraries) are implemented on top of the thread/monitor model that is
burnt into the JVM and underlying operating system.  That's fine and it works,
but suffers whatever overheads are imposed.  We *know* that the CSP primitives
can be implemented with overheads measured in nanoseconds ... what are the
prospects of extending the JVM (or bypassing it) to do that for real-time
applications?  Note that this is just an implementation/performance issue,
not a semantic one.

The third message is that research on more CSP-aware languages and their
possible pre-processing down to Java or ByteCode should be done.  Some
important benefits could then flow that might be very difficult otherwise
-- not least being the automated checking of conformance to higher-level
CSP design rules that have proven freedom from deadlock, livelock and
starvation.  All of which ought to be of interest to engineers working on
real-time and/or embedded systems.

> At a high level, I enthusiastically support the development of
> higher-level paradigms.  When a technology is ready, making a
> standard around it has obvious benefits, too.  I, personally, would
> be happy to help any group that wants to propose a higher-level
> standard extension through Sun's open process.

Claim: CSP is a mature paradigm with a serious academic pedigree and a long
industrial track record.  There's also a pretty active and experienced
user community.  It's time to talk some more?

Cheers,

Peter Welch.


Relevant URLs:
==============

[1] The JCSP library:

      http://www.hensa.ac.uk/parallel/languages/java/jcsp/

[2] The CTJ library:

      http://www.rt.el.utwente.nl/javapp/

[3] Java Threads Workshop (September, 1996):

      http://www.hensa.ac.uk/parallel/groups/wotug/java/

[4] "wot, no chickens?"

      http://www.hensa.ac.uk/parallel/groups/wotug/java/discussion/3.html

[5] WoTUG-20 conference (lots of Java/CSP):

      http://www.rt.el.utwente.nl/wotug20/

[6] WoTUG-21 conference (lots of Java/CSP):

      http://www.hensa.ac.uk/parallel/groups/wotug/wotug21/

[7] rt-java mailing list

      http://www.nist.gov/itl/div896/emaildir/rt-j/maillist.html