[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: ALTing select mechanism implementation


> I see from the JCSP 1.0-rc1 API Specification for Class: Alternative
> (under description) that "select .... makes an arbitrary choice".
> I assume that arbitrary means random ...

As Stephen Maudesley pointed out, the word `arbitrary' is carefully chosen!

It goes back via occam and the transputer to CSP.  Alting introduces
non-determinism to the process that's doing it.  If the environment of
an alting process is offering several events (e.g. channel inputs, timeouts),
the alting process makes an *arbitrary* choice of one of those events.
In the original CSP, how that choice gets made is non-deterministic - i.e.
it is not under the control of that alting process (or anyone else).

So, under the formal semantics of occam, *any* way of making an ALT choice
is legal - including some random mechanism or a grossly unfair one (such as
a PRI ALT).  On the transputer, ALTs were mailnly implemenmted as PRI ALT.
This is the same for all KRoC implementations.

In JCSP, the select method of an Alternative again makes an *arbitrary*
choice.  It must not concern the programmer or user of the alting process
how that choice is made.

If that does concern you, don't use the select method - use the priSelect or
fairselect methods.  The priSelect just chooses the ready guard with lowest
index (= highest priority).  The fairSelect makes a `fair' choice.  This
is `fair' with respect to previous choices it has made.  This is possible
in JCSP (but not as an occam primitive) because an Alternative object is
bound to a fixed set of guards - so each consecutive fairSelect operates
over the same set of guards.  The fairness criteria used is a standard
paradigm used in many occam applications - the guards are round-robin
prioritised with the guard chosen last time getting lowest priority
next time.  This means that there is no way another guard will get
fairSelected *twice* ahead of you - that's fair!  And, in the worst case,
evry other ready guard will get serviced before you but you will definitely
be next.

If anyone particularly wanted a randomSelect method added, that would be
trivial to do - and the nature of the randonmness would need documenting.
But computing a random number is a heavy overhead to add to an alt - which
is why the occam ALT (on a transputer and in KRoC) is just a PRI ALT.

In JCSP, the select method is actually implemented as fairSelect - but
you don't need to know that!

> I am planning a simulation study and I'd like to exert as much control
> over it as possible as easily as possible, perhaps thereby having ALTing
> behavior reproducible (under certain conditions) when excuted by others
> on different machines with possibly different JVMs.

I don't think you should need randomness at the ALTing ends of processes
in simulation models.  The randomness is more naturally placed in the
processes generating the events that the ALTing processes service - i.e.
you get them to generate those events under some random distribution
that *you* can configure however you like.  Get the ALTing processes
to make fairSelects and it should work fine!  As in the philosophers
example in the jcsp-demos directory in the JCSP release ...