|
CSP for Java (JCSP) 1.0-rc2 |
||||||||
| 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.
Guard events. This is known as ALTing.
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.
Five 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.
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.
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.
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 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.
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 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.
On the other hand, the above 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.
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.
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;
}
}
}
}
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! An effort to do this (via a CSP model of Java's
synchronisation primitives) is under way.
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,
CSTimer,
Skip| Constructor Summary | |
Alternative()
Deprecated. Use Alternative (Guard[] guard). |
|
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(AltingChannelInput[] c)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. |
int |
select(AltingChannelInput[] c,
boolean skip)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. Skip selects are now handled by Skip guards and we can have more than one. When used with priSelect, the priority of each skip guard can be individually set. |
int |
select(AltingChannelInput[] c,
boolean[] preCondition)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. |
int |
select(AltingChannelInput[] c,
boolean[] preCondition,
boolean skip)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. Skip selects are now handled by Skip guards and we can have more than one. When used with priSelect, the priority of each skip guard can be individually set. |
int |
select(AltingChannelInput[] c,
boolean[] preCondition,
long msecs)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. Timeouts are now handled by CSTimer guards and we can have more than one. When used with priSelect, the priority of each timeout guard can be individually set. |
int |
select(AltingChannelInput[] c,
boolean[] preCondition,
long msecs,
int nsecs)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. Timeouts are now handled by CSTimer guards and we can have more than one. When used with priSelect, the priority of each timeout guard can be individually set. Currently, the nsecs option for timeouts is not supported in the new model. |
int |
select(AltingChannelInput[] c,
long msecs)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. Timeouts are now handled by CSTimer guards and we can have more than one. When used with priSelect, the priority of each timeout guard can be individually set. |
int |
select(AltingChannelInput[] c,
long msecs,
int nsecs)
Deprecated. Construct the Alternative with the guards pre-loaded and use the select, priSelect or fairSelect methods without guard (i.e. AltingChannelInput) parameters. Timeouts are now handled by CSTimer guards and we can have more than one. When used with priSelect, the priority of each timeout guard can be individually set. Currently, the nsecs option for timeouts is not supported in the new model. |
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 |
| Constructor Detail |
public Alternative(Guard[] guard)
Guard
array of events. Supported guard events are channel inputs
(AltingChannelInput and AltingChannelInputInt),
CALL channel accepts (AltingChannelAccept),
timeouts (CSTimer) and skips (Skip).
guard - the event guards over which the select operations will be made.public Alternative()
| Method Detail |
public final int select()
public final int priSelect()
public final int fairSelect()
public final int select(boolean[] preCondition)
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)
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)
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 int select(AltingChannelInput[] c)
c - the Channels to be selected from
public int select(AltingChannelInput[] c,
long msecs)
c - the Channels to be selected frommsecs - the time in milli-seconds to wait for a Channel to become ready
public int select(AltingChannelInput[] c,
long msecs,
int nsecs)
c - the Channels to be selected frommsecs - the time in milli-seconds to wait for a Channel to become readynsecs - the extra time above msecs to wait in nano-seconds
public int select(AltingChannelInput[] c,
boolean skip)
NOTE: This method enables the development of a polling programs which can consume extra processor time. Try to use one of the other select methods.
c - the Channels to be selected fromskip - A Boolean indicating whether the method should block until data is ready
public int select(AltingChannelInput[] c,
boolean[] preCondition)
NOTE: The c and preCondition arrays must be of the same size.
c - the Channels to be selected frompreCondition - the preConditions for the Channels
public int select(AltingChannelInput[] c,
boolean[] preCondition,
long msecs)
NOTE: The c and preCondition arrays must be of the same size.
c - the Channels to be selected frompreCondition - the preConditions for the Channelsmsecs - the time in milli-seconds to wait for a Channel to become ready
public int select(AltingChannelInput[] c,
boolean[] preCondition,
long msecs,
int nsecs)
NOTE: The c and preCondition arrays must be of the same size.
c - the Channels to be selected frompreCondition - the preConditions for the Channelsmsecs - the time in milli-seconds to wait for a Channel to become readynsecs - the extra time above msecs to wait in nano-seconds
public int select(AltingChannelInput[] c,
boolean[] preCondition,
boolean skip)
NOTE: The c and preCondition arrays must be of the same size.
NOTE: This method enables the development of a polling programs which can consume extra processor time. Try to use one of the other select methods.
c - the Channels to be selected frompreCondition - the preConditions for the Channelsskip - A Boolean indicating whether the method should block until data is ready
|
CSP for Java (JCSP) 1.0-rc2 |
||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||