|
CSP for Java (JCSP) 1.0-rc7 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jcsp.lang.Alternative
This enables a process to wait passively for and choose
between a number of Guard
events.
Shortcut to the Constructor and Method Summaries.
Alternative
class enables a CSProcess
to wait passively for and
choose between a number of Guard
events. This is known as
ALT
ing.
Note: for those familiar with the occam multiprocessing
language, this gives the semantics of the ALT
and
PRI
ALT
constructs, extended with a built-in implementation
of the classical FAIR
ALT
.
The Alternative
constructor takes an array of guards. Processes
that need to Alt over more than one set of guards will need a separate
Alternative
instance for each set.
Six types of Guard
are provided in jcsp.lang
:
AltingChannelInput
: object channel input --
ready if unread data is pending in the channel.
AltingChannelInputInt
: integer channel input --
ready if unread data is pending in the channel.
AltingChannelAccept
: CALL channel accept --
ready if an unaccepted call is pending on the channel.
AltingBarrier
: barrier synchronisation --
ready if all enrolled processes are offering to synchronise.
CSTimer
: timeout --
ready if the timeout has expired (timeout
values are absolute time values, not delays)
Skip
: skip --
always ready.
By invoking one of the following methods, a process may passively wait for
one or more of the guards associated with an Alternative
object
to become ready. The methods differ in the way they choose which guard
to select in the case when two or more guards are ready:
select
waits for one or more of the guards
to become ready. If more than one become ready, it makes an
arbitrary choice between them (and corresponds to the
occam ALT
).
priSelect
also waits for one or more of
the guards to become ready. However, if more than one becomes ready,
it chooses the first one listed (and corresponds to the
occam PRI
ALT
). Note: the use of
priSelect
between channel inputs and a skip guard (at lowest
priority) gives us a polling operation on the readiness
of those channels.
fairSelect
also waits for one or more
of the guards to become ready. If more than one become ready, it
prioritises its choice so that the guard it chose the last time
it was invoked has lowest priority this time. This corresponds
to a common occam idiom used for real-time applications.
If fairSelect
is used
in a loop, a ready guard has the guarantee that no other guard will be
serviced twice before it will be serviced. This enables
an upper bound on service times to be calculated and ensures that no
ready guard can be indefinitely starved.
Finally, each guard may be pre-conditioned with a run-time test to decide if it should be considered in the current choice. This allows considerable flexibilty -- for example, we can decide whether timeouts shoud be set, channels refused or polling enabled depending on the run-time state of the Alting process.
import jcsp.lang.*; public class FairPlex implements CSProcess { private final AltingChannelInput[] in; private final ChannelOutput out; public FairPlex (final AltingChannelInput[] in, final ChannelOutput out) { this.in = in; this.out = out; } public void run () { final Alternative alt = new Alternative (in); while (true) { final int index = alt.fairSelect (); out.write (in[index].read ()); } } }Note that if
priSelect
were used above, higher-indexed channels would be
starved if lower-indexed channels were continually demanding service.
If select
were used, no starvation analysis is possible.
The select
mechanism should only be used when starvation is not an issue.
import jcsp.lang.*; public class FairPlexTime implements CSProcess { private final AltingChannelInput[] in; private final ChannelOutput out; private final long timeout; public FairPlexTime (final AltingChannelInput[] in, final ChannelOutput out, final long timeout) { this.in = in; this.out = out; this.timeout = timeout; } public void run () { final Guard[] guards = new Guard[in.length + 1]; System.arraycopy (in, 0, guards, 0, in.length); final CSTimer tim = new CSTimer (); final int timerIndex = in.length; guards[timerIndex] = tim; final Alternative alt = new Alternative (guards); boolean running = true; tim.setAlarm (tim.read () + timeout); while (running) { final int index = alt.fairSelect (); if (index == timerIndex) { running = false; } else { out.write (in[index].read ()); } } } }Note that if
priSelect
were used above, higher-indexed guards would be
starved if lower-indexed guards were continually demanding service -- and
the timeout would never be noticed.
If select
were used, no starvation analysis is possible.
To demonstrate FairPlexTime
, consider:
import jcsp.lang.*; import jcsp.plugNplay.Printer; class FairPlexTimeTest { public static void main (String[] args) { final One2OneChannel[] a = One2OneChannel.create (5); final One2OneChannel b = new One2OneChannel (); new Parallel ( new CSProcess[] { new Regular (a[0], 0, 5), new Regular (a[1], 1, 5), new Regular (a[2], 2, 5), new Regular (a[3], 3, 5), new Regular (a[4], 4, 5), new FairPlexTime (a, b, 10000), new Printer (b, "FairPlexTimeTest ==> ", "\n") } ).run (); } }where
Regular
(documented as an example in the CSTimer
class) attempts to output an Integer
(defined by its second parameter) to
the channel (defined by its first parameter) at a regular interval (defined by its
third parameter in msecs). If you are using a relatively slow JVM (such as
JDK1.1.x
), the input channels to FairPlexTime
will always be
ready. Faster JVMs (such as JDK1.2
) are able to clear all input
channels leaving the timeout guard selectable. Either way, all channels are
fairly serviced and the eventual timeout (after 10 seconds) is processed.
If FairPlexTime
had used alt.priSelect
instead of
alt.fairSelect
and a slow JVM is used, the higher indexed channels
would not get serviced and neither would the timeout. Try it and see! Notice
the different behaviour if you freeze screen output (with ctl-s) and, then,
resume it (with ctl-q). The moral is that fairSelect
frees
us from worries such as the speed of our JVM and its scheduling behaviour.
Sometimes, of course, we need to use priSelect
to impose a specific
(as opposed to fair) choice that overcomes the external scheduling of events.
For example, if we were concerned that the timeout in FairPlexTime
should
be responded to immediately and unconcerned about the fair servicing of its
channels, we could put its CSTimer
as the first element of its Guard
array and use a priSelect
.
Regulate
process controls the flow of traffic from its in
to
out
channels. It produces a constant rate of output flow, regardless of
the rate of its input. At the end of each timeslice defined by the required output
rate, it outputs the last object input during that timeslice. If nothing has come
in during a timeslice, the previous output will be repeated (note: this will be a
null
if nothing has ever arrived). If the input flow is greater than
the required output flow, data will be discarded.
The interval (in msecs) defining the output flow rate is given by a constructor
argument; but it can be reset at any time by sending a new interval (as a Long
)
down the reset
channel.
Note: this example shows how simple it is to program time-regulated functionality
like that performed by java.awt.Component.repaint
.
import jcsp.lang.*; public class Regulate implements CSProcess { private final AltingChannelInput in, reset; private final ChannelOutput out; private final long initialInterval; public Regulate (final AltingChannelInput in, final AltingChannelInput reset, final ChannelOutput out, final long initialInterval) { this.in = in; this.reset = reset; this.out = out; this.initialInterval = initialInterval; } public void run () { final CSTimer tim = new CSTimer (); final Guard[] guards = {reset, tim, in}; // prioritised order final int RESET = 0; // index into guards final int TIM = 1; // index into guards final int IN = 2; // index into guards final Alternative alt = new Alternative (guards); Object x = null; // holding object long interval = initialInterval; long timeout = tim.read () + interval; tim.setAlarm (timeout); while (true) { switch (alt.priSelect ()) { case RESET: interval = ((Long) reset.read ()).longValue (); timeout = tim.read (); // fall through case TIM: out.write (x); timeout += interval; tim.setAlarm (timeout); break; case IN: x = in.read (); break; } } } }
To demonstrate Regulate
, consider:
class RegulateTest { public static void main (String[] args) { final One2OneChannel a = new One2OneChannel (); final One2OneChannel b = new One2OneChannel (); final One2OneChannel c = new One2OneChannel (); final One2OneChannel reset = One2OneChannel.create (new OverWriteOldestBuffer (1)); new Parallel ( new CSProcess[] { new Numbers (a), // generate numbers new FixedDelay (250, a, b), // let them through every quarter second new Regulate (b, reset, c, 1000), // initially sample every second new CSProcess () { public void run () { Long[] sample = {new Long (1000), new Long (250), new Long (100)}; int[] count = {10, 40, 100}; while (true) { for (int cycle = 0; cycle < sample.length; cycle++) { reset.write (sample[cycle]); System.out.println ("\nSampling every " + sample[cycle] + " ms ...\n"); for (int i = 0; i < count[cycle]; i++) { Integer n = (Integer) c.read (); System.out.println ("\t==> " + n); } } } } } } ).run (); } }The reader may like to consider the danger of deadlock in the above system if the
reset
channel were not an overwriting one.
PRI
ALT
ing
the channels we wish to poll against a SKIP
guard:
import jcsp.lang.*; public class Polling implements CSProcess { private final AltingChannelInput in0; private final AltingChannelInput in1; private final AltingChannelInput in2; private final ChannelOutput out; public Polling (final AltingChannelInput in0, final AltingChannelInput in1, final AltingChannelInput in2, final ChannelOutput out) { this.in0 = in0; this.in1 = in1; this.in2 = in2; this.out = out; } public void run() { final Skip skip = new Skip (); final Guard[] guards = {in0, in1, in2, skip}; final Alternative alt = new Alternative (guards); while (true) { switch (alt.priSelect ()) { case 0: ... process data pending on channel in0 ... break; case 1: ... process data pending on channel in1 ... break; case 2: ... process data pending on channel in2 ... break; case 3: ... nothing available for the above ... ... so get on with something else for a while ... ... then loop around and poll again ... break; } } } }The above technique lets us poll any
Guard
events, including
timeouts. If we just want to poll channels for input events, see
the pending
methods of the various
``...2One...
'' channels for a more direct and efficient way.
Note: polling is an often overused technique. Make sure your design would
not be better suited with a blocking ALT and with the `something else' done by
a process running in parallel.
The
Contrast the above programming of the canteen as a CSP process rather
than a monitor. A monitor cannot refuse a callback when noone has the lock,
even though it may not be in a state to process it. In the above, a
On the other hand, the above The `Wot-no-Chickens?' Canteen
This examples demonstrates the use of pre-conditions on the ALT
guards. The Canteen
process buffers a supply of chickens. It can
hold a maximum of 20 chickens. Chickens are supplied on the supply
line in batches of, at most, 4. Chickens are requested by hungry philosophers
who share the request
line to the Canteen
. In response to
such requests, one chicken is delivered down the deliver
line.
Canteen
refuses further supplies if it has no room for the maximum
(4) batch supply. The Canteen
refuses requests from the philosophers
if it has no chickens.
import jcsp.lang.*;
public class Canteen implements CSProcess {
private final AltingChannelInput supply; // from the cook
private final AltingChannelInput request; // from a philosopher
private final ChannelOutput deliver; // to a philosopher
public Canteen (final AltingChannelInput supply,
final AltingChannelInput request, final ChannelOutput deliver) {
this.supply = supply;
this.request = request;
this.deliver = deliver;
}
public void run() {
final Guard[] guard = {supply, request};
final boolean[] preCondition = new boolean[guard.length];
final int SUPPLY = 0;
final int REQUEST = 1;
final Alternative alt = new Alternative (guard);
final int maxChickens = 20;
final int maxSupply = 4;
final int limitChickens = maxChickens - maxSupply;
final Integer oneChicken = new Integer (1); // ready to go!
int nChickens = 0; // invariant : 0 <= nChickens <= maxChickens
while (true) {
preCondition[SUPPLY] = (nChickens <= limitChickens);
preCondition[REQUEST] = (nChickens > 0);
switch (alt.priSelect (preCondition)) {
case SUPPLY:
nChickens += ((Integer) supply.read ()).intValue (); // <= maxSupply
break;
case REQUEST:
Object dummy = request.read (); // we have to still input the signal
deliver.write (oneChicken); // preCondition ==> (nChickens > 0)
nChickens--;
break;
}
}
}
}
supply
method would have to cope with its being called when there is no room to take the supply.
A request
method would have to be dealt with even though there may be no chickens
to deliver. Monitors manage such problems by putting their callers on hold
(wait
), but that means that their methods have to rely on each other to get
out of any resulting embarassment (using notify
).
And that means that the logic of those methods has to be tightly coupled, which
makes reasoning about them hard. This gets worse the more interdependent methods
the monitor has.
Canteen
process simply refuses service on
its supply
and request
channels if it can't cope, leaving
the supplying or requesting processes waiting harmlessly on those channels.
The service responses can assume their run-time set pre-conditions and have
independent -- and trivial -- logic. When circumstances permit,
the blocked processes are serviced in the normal way.
Implementation Footnote
This Alternative
class and the various channel classes
(e.g. One2OneChannel
) are mutually dependent monitors -- they see instances
of each other and invoke each others' strongly interdependent methods. This logic
is inspired by the published algorithms and data structures burnt into the microcode
of the transputer some 15 years ago (1984). Getting this logic `right'
in the context of Java monitors is something we have done (n + 1)
times,
only to find it flawed n
times with an unsuspected race-hazard months
(sometimes years) later. Hopefully, we have it right now ... but a proof
of correctness is really needed!
synchronized
keyword and the wait
, notify
and
notifyAll
methods of the Object
class) has been built.
This has been used for the formal verification of the JCSP implementation
of channel read
and write
, along with the correctness of
2-way channel input Alternative
s.
Details and references are listed under
`A CSP Model
for Java Threads' on the JCSP web-site.
[The proof uses the FDR
model checker. Model checkers do not easily allow verification of results containing
free variables - such as the correctness of the n-way Alternative
.
An investigation of this using formal transformation of one system of CSP equations
into another, rather than model checking is being considered.]
The transputer designers always said that getting its microcoded scheduler logic right was one of their hardest tasks. Working directly with the monitor concept means working at a similar level of difficulty for application programs. One of the goals of JCSP is to protect users from ever having to work at that level, providing instead a range of CSP primitives whose ease of use scales well with application complexity -- and in whose implementation those monitor complexities are correctly distilled and hidden.
Guard
,
AltingChannelInput
,
AltingChannelInputInt
,
AltingChannelAccept
,
AltingBarrier
,
CSTimer
,
Skip
Field Summary | |
protected Object |
altMonitor
The monitor synchronising the writers and alting reader |
Constructor Summary | |
Alternative(Guard[] guard)
Construct an Alternative object operating on the Guard
array of events. |
Method Summary | |
int |
fairSelect()
Returns the index of one of the ready guards. |
int |
fairSelect(boolean[] preCondition)
Returns the index of one of the ready guards whose preCondition index
is true. |
int |
priSelect()
Returns the index of one of the ready guards. |
int |
priSelect(boolean[] preCondition)
Returns the index of one of the ready guards whose preCondition
index is true. |
int |
select()
Returns the index of one of the ready guards. |
int |
select(boolean[] preCondition)
Returns the index of one of the ready guards whose preCondition
index is true. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
protected Object altMonitor
Constructor Detail |
public Alternative(Guard[] guard)
Alternative
object operating on the Guard
array of events. Supported guard events are channel inputs
(AltingChannelInput
and AltingChannelInputInt
),
CALL channel accepts (AltingChannelAccept
),
barriers (AltingBarrier
),
timeouts (CSTimer
) and skips (Skip
).
guard
- the event guards over which the select operations will be made.Method Detail |
public final int select()
public final int priSelect()
public final int fairSelect()
public final int select(boolean[] preCondition)
preCondition
index is true. The method will block until one of these guards becomes
ready. If more than one is ready, an arbitrary choice is made.
Note: the length of the preCondition
array must be the
same as that of the array of guards with which this object was constructed.
preCondition
- the guards from which to selectpublic final int priSelect(boolean[] preCondition)
preCondition
index is true. The method will block until one of these guards becomes
ready. If more than one is ready, the one with the lowest index is selected.
Note: the length of the preCondition
array must be the
same as that of the array of guards with which this object was constructed.
preCondition
- the guards from which to selectpublic final int fairSelect(boolean[] preCondition)
preCondition
index
is true. The method will block until one of these guards becomes ready.
Consequetive invocations will service the guards `fairly' in the case
when many guards are always ready. Implementation note: the last
guard serviced has the lowest priority next time around.
Note: the length of the preCondition
array must be the
same as that of the array of guards with which this object was constructed.
preCondition
- the guards from which to select
|
CSP for Java (JCSP) 1.0-rc7 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |