Re: CSP/JCSP Tutorial at PDPTA 2001

["P.H.Welch" <P.H.Welch@xxxxxxxxx>]

Owen,

Thank you for your questions ... they are all very good!  Here's my stab
at answering them.

> 1.  There does not appear to be support for internal choice?  Why not?  Was
>     it a decision to remove determinism?

Adrian has answered this pretty well.  JCSP follows the lead set by occam
as a programming vehicle for implementing CSP designs.  As such, it takes
a similar view to occam as to what bits of CSP are practical (i.e. can be
efficiently realised) and also throws in a few extras (such as timers,
priorities, fairness etc.).  Thrown out are the ability for more than one
process to include the same event in an external choice - only one party
can do this per event.  So, only the input ends of channels can be used
as JCSP Guards - you can't ALT over output events.  Similarly, JCSP does
not allow barriers, buckets or CREW-locks as ALT Guards.  In practice,
this means that the CSP designs directly implementable using JCSP (or
occam) must conform to those limitations.  Again, in many years of large-
scale industrial practice, those limitations have not been a problem.

As Adrian said, I too think you meant "non-determinism" in your question.
Non-determinism is introduced in CSP by the internal choice operator, |~|,
and by hiding, \.  External choice, [], is "deterministic" since the
envoronment of a process performing one can determine which choice is
made - simply by offering only one of the events in the choice set.

However, external and internal choice are related.  For example, if the
environment offers more than one event in the (external) choice set,
then it becomes an internal choice as to what happens - e.g.:

  ( ( (a --> A) [] (b --> B) ) || a --> SKIP !! b --> SKIP ) \ {a, b}

is semantically (traces-failures-divergences) equivalent to:

  ( (A || b --> SKIP) |~| (B || a --> SKIP) ) \ {a, b}

In the former, we have an external choice between events a and b, that is
in an environment offering both a and b, outside of which a and b are hidden
- i.e. no other processes can get involved.

This reduces to the latter, which is an internal choice between the result
of either of the (previously external) choices being made.

The former is directly programmable in occam or JCSP.  The result is the
same as the latter internal choice - even though neither occam nor JCSP
provide internal choice primitives.

Strictly speaking, the occam ALT and JCSP Alternative.select() give us
neither external not internal choice - but a mixture of both.  For example,
an ALT/Alternative.select() between *different* channel inputs is a CSP
external choice, [].  An ALT/Alternative.select() between SKIP guards is
an internal choice (non-deterministic |~|).  An ALT/Alternative.select()
between the *same* channel inputs (usually with differing pre-conditions,
all of which say are TRUE - note: this is not directly expressible in CSP
but is a powerful programming add-on for occam/JCSP) is an internal choice.
A timer guard introduces non-determinism.  And an ALT/Alternative.select()
with *different* channel inputs is an external choice, but if the environment
offers several we are back with an internal choice (as shown above).

So, non-determinism occurs in the semantics of occam/JCSP ... even though
neither provides the |~| primitive.  Both, of course, provide the hiding
primitive indirectly through their normal block-structure scoping rules
for object (e.g. channel, barrier) visibility.  And, as Adrian says, we
don't need this |~| primitive when we program - only when building models
and refining them.

Talking of refinement ... the non-determistic semantics of certain occam/JCSP
systems (e.g. the examples above) can be implemented in an arbitrary and
deterministic way.  Computers being computers (which cannot generate real
random numbers), they *are* implemented in an arbitrary and deterministic
way.  But the occam/JCSP programmer does not need to know - and *must not*
rely on that mechanics should he/she find out!

For instance, the JCSP Alternative.select() is actually implemented by
the purely deterministic Alternative.fairSelect().  We could have chosen
the Alternative.priSelect() - which occam does - but fairness seemed
a reasonable way (and is not noticeably more expensive than the PRI ALT).
So, repeated select() operations on an Alternative holding just SKIP
guards - semantically an internal choice between them all - will actually
cycle its choices over them all.  That's a correct implementation.  But,
of course, there are other correct implementations - the semantics is
non-determinstic.  You mustn't rely on it.  Future releases may do it
differently - e.g. by priSelect or random choice or, unfairly, by always
choosing the third one!

> 2.  Are there internal mechanisms for ensuring that parallel processes are
> indeed parallel, and remove processes that aren't?  Put another way,
> something like MS Word may easily have 500 GUI objects, would they all be
> separate parallel processes (hence threads)?
>         My thoughts were that non-parallel processes wouldn't be in sync
>         with any of the other processes, and would therefore terminate
>         naturally, but this doesn't answer the rephrased question.

I'm not sure what you're getting at here ... but I think it's the scare
that if you build a 500-widget GUI with JCSP, you will end up with 500
JCSP processes and, with the current implementation, 500 threads ... which
might rule it out for small-memory devices.  I'll answer this anyway!

The jcsp.awt package was put together for demonstration purposes - it's
not supposed to be the last word on how to support GUI/graphics in JCSP.

However, the claim is that CSP concurrency designs are simple and scalable
ways to build complex systems - and standard Java GUI/graphics are such
a strange mix of magic and mystery - that the challenge was irresistable.

So, I do claim that the process model for widgets is a rather good one.
Like all CSP designs, it fits with our intuition and we don't have magic
and mystery and nasty surprises.  Each widget, therefore, is a process.
To configure it (e.g. to set its colour, logo, settings), you send it
the relevant command down a channel.  If the widget produces an output
response (e.g. from a button click, mouse entry, slider movement), then
details of that action are output from the widget down a channel.
Each widget has internal concurrency - it can handle configuration
input and GUI event output at the same time.  So, an application will
not deadlock if the same (application) process tries to configure
a widget to which it is listening.

To the CSP designer, such process widgets are so easy to work.  If we
were doing this in occam (and KRoC will release a GUI/graphics library
with the same process model - hopefully in the next 6 months), there
would be no problem with a 500 widget application.  The memory overheads
for an occam process are at most 6 words (often less depending on what
the process does) - so that's less than 24 Kbytes overhead (assuming
2 processes per widget).

But it's a bit more for Java!  The current JCSP implementation uses one
Java Thread per JCSP process.  Jim Moores, from Kent, has just demonstrated
the feasibility of incorporating his CCSP/occam kernel into a JVM to
provide direct support for all JCSP synchronisation primitives - it acts
alongside the usual Java monitor/threads kernel so standard Java codes
are not broken.  This might push up the memory overheads per process to
10 words (compared to occam's 6) - but compares well with what is required
for a Java Thread!  It will also reduce by an order of magnitude the
run-time costs of JCSP synchronisation (which are the same as the overheads
of standard thread/monitor synchronisation (in case you are able to program
these safely!).  [Note: occam's run-time costs for process synchronisation
will be an order of magnitude lower still.]

So, that's for the future - what can be done now?

Current JCSP widgets don't use any sub-processes (threads) to write output
events down its channels - this is simply done by the JVM "event thread".
[Note: this is why GUI applications are advised to make sure widget events
are always taken (e.g. by using overwriting channels of some kind - if you
are unsure how fast your application processes will get around to accepting
them).]

Current JCSP widgets do use a process (thread) to input and invoke
configuration commands.  These process is a simple loop that just waits
at the start of the loop body to input a command and then executes it.
There is an obvious transformation of this to serial code - in which
the writer to the channel simply executes the command directly on the
widget.  [In the case of the non-thread-safe Swing widgets, of course,
this has to be an invokeLater() command that's handed over to the Event
Thread for serial execution.]

So, JCSP programmers could set up their "active" widgets with event channel
outputs in the normal way, not set configuration channels and pass those
widgets (which are sub-classes of their java.awt equivalents) to the
configuring processes that need them.  And, of course, don't include
those widgets in any Parallel constructs - they don't need starting!

But that's not very CSPish and breaks the rules on object visibility
that we need to keep under control to avoid race hazards.

So, here's a comporomise.  We still have a channel interface for configuring
widgets and JCSP processes doing so remain unchanged (they write commands
down ChannelOutput channels as at present).

But the channels we give those application processes are:

  One2OneConfigureChannel / Any2OneConfigureChannel   (proposed)

The above only implement the ChannelOutput interface.  Their constructors
take an appropriate (widget) process to which they become permanantly
attached.  The channel's implementation of a write(command) simply invokes
the command on its attached process.

The above is only safe, of course, if the attached process is not actually
running!  And that is what we would have.  So, the only changes to JCSP
codes would be to use the One2OneConfigureChannel/Any2OneConfigureChannel
channels instead of One2OneChannel/Any2OneChannel, construct them suitably
and omit the widget processes from the PAR.  The behaviour would be
exactly the same (traces-failures-divergences semantics) as before ...
but the GUI widgets would require *no* Java threads.  [We could do the
same trick for occam ;)].

This serialisation trick need not be confined to widget processes - but to
any processes that are simple servers of channel inputs that merely update
internal state and perform no other synchronisations.

I need to think about this some more to get it right ... and it will need
some changes to the current JCSP API (all those different "configure"
interfaces in jcsp.awt need to be replaced with, ideally, just one simple
"configure" interface) ... so the changes should simplfy things as well
as optimise them.  That's called a win-win ;) !

> 3.  How does the garbage collector, which runs in a separate thread,
> interact with the objects in the processes and the objects themselves.
>         My thoughts were that garbage collection worked the same way as
>         in regular Java programs.  Or is there more to it?

There is no conflict here.  JCSP runs on any standard JVM.  The normal
behaviour of garbage collection is unaffected by JCSP processes, which
are in any case (for now) implemented by standard Java threads.  JCSP
logic is unaffected by garbage collection - garbage collection has no
impact on the semantics of Java programs (apart from performance issues
relating to running out of memory without gc and the run-time costs of
gc itself).

> 4.  One of your concerns about Java Monitors is that the thread model is not
> a thread-per-object model.  On the other hand, each process has its own
> thread.  One collegue indicated that there is now a CORBA-supporting Java
> that adheres to the thread-per-object model.  How would that affect JCSP?
> Or how would JCSP be different then?

I'm concerned about the overuse of raw objects - we can't defend against
their methods being invoked by anything that can see them.  When that
happens and the object is in an inappropriate state to respond correctly,
you either have to drop it (e.g. return an error status or raise an exception)
or wait on some condition variable.  The former leads to busy-polling and
livelock - the latter to incomprehensible code.  With processes (i.e. objects
in control of their own life), we can defend them against untimely access.

There are lots of other problems with large systems of objects.  The most
serious of these is the proliferation of object references that escape
around the system - the results being that all data quickly becomes
globally visible (regardless of object encapsulation in so-called private
fields).  That's bad for serial programming and race-hazard-deadly with
concurrency.

I don't understand about "CORBA-supporting Java that adheres to the
thread-per-object model".  Is this Java?  There's a big semantic
difference to a plain passive object and one with a thread in it.  Unless,
of course, that thread is doing the same trivial service loop that the JCSP
widgets currently perform!  But I'm suggesting serialing that out ... is
this CORBA-supporting Java parallelising it in?  If so, why?

Assuming there is a good reason and assuming it doesn't change the semantics
of objects, then it would not affect JCSP.  If there's a tremendous
efficiency reason behind this (I can't see how?), then there would be
some short-cuts that a special JCSP implementation would be able to make
for such a platform.

Hope this helps!

Peter.