Package org.jcsp.lang

Class Alternative

java.lang.Object
org.jcsp.lang.Alternative

public class Alternative extends Object
This enables a process to wait passively for and choose between a number of Guard events.

Shortcut to the Constructor and Method Summaries.

Description

The Alternative class enables a CSProcess to wait passively for and choose between a number of 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.

Eight 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.
  • AltingChannelOutput: object channel output -- ready if a reading process can take the offered data (symmetric channels only).
  • AltingChannelOutputInt: integer channel output -- ready if a reading process can take the offered data (symmetric channels only).
  • AltingChannelAccept: CALL accept -- ready if an unaccepted call is pending.
  • 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.

Examples

A Fair Multiplexor

This example demonstrates a process that fairly multiplexes traffic from its array of input channels to its single output channel. No input channel will be starved, regardless of the eagerness of its competitors.
 import org.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.

A Fair Multiplexor with a Timeout and Poisoning

This example demonstrates a process that fairly multiplexes traffic from its input channels to its single output channel, but which timeouts after a user-settable time. Whilst running, no input channel will be starved, regardless of the eagerness of its competitors. The process also illustrates the poisoning of channels, following the timeout.
 import org.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 ());
       }
     }
     System.out.println ("\n\r\tFairPlexTime: timed out ... poisoning all channels ...");
     for (int i = 0; i < in.length; i++) {
       in[i].poison (42);                       // assume: channel immunity < 42
     }
     out.poison (42);                           // assume: channel immunity < 42
 
   }
 
 }
 
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.

Sometimes 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 above should be responded to immediately and unconcerned about the fair servicing of its channels, we should put its CSTimer as the first element of its Guard array and use priSelect.

To demonstrate FairPlexTime, consider:

 import org.jcsp.lang.*;
 import org.jcsp.plugNplay.*;
 
 class FairPlexTimeTest {
 
   public static void main (String[] args) {
 
     final One2OneChannel[] a = Channel.one2OneArray (5, 0);     // poisonable channels (zero immunity)
     final One2OneChannel b = Channel.one2One (0);               // poisonable channels (zero immunity)

     final long timeout = 5000;                                  // 5 seconds
 
     new Parallel (
       new CSProcess[] {
         new Generate (a[0].out (), 0),
         new Generate (a[1].out (), 1),
         new Generate (a[2].out (), 2),
         new Generate (a[3].out (), 3),
         new Generate (a[4].out (), 4),
         new FairPlexTime (Channel.getInputArray (a), b.out (), timeout),
         new Printer (b.in (), "FairPlexTimeTest ==> ", "\n")
       }
     ).run ();
 
   }
 
 }
 
where
Generate sends its given Integer down its output channel as often as it can. This results in continuous demands on FairPlexTime by all its clients and demonstrates its fair servicing of those demands.

The Generate and Printer are programmed to deal with being poisoned. Here is the run() method for Generate:

 public void run() {
   try {
     while (true) {
       out.write (N);
     }
   } catch (PoisonException p) {
     // the 'out' channel must have been posioned ... nothing left to do!
   }
 }
 
In general, there will be things to do – especially if there is more than one channel. For example, here is the catch block at the end of the run() method for Delta (which has a single input channel-end, in, and an array of output channel-ends, out):
   } catch (PoisonException p) {
     // don't know which channel was posioned ... so, poison them all!
     int strength = p.getStrength ();   // use same strength of poison
     in.poison (strength);
     for  (int i = 0; i < out.length; i++) {
       out[i].poison (strength);
     }
   }
 

A Simple Traffic Flow Regulator

The Regulate process controls the rate of flow of traffic from its input to output 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. This can be changed 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.

 package org.jcsp.plugNplay;

 import org.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 = Channel.one2One ();
     final One2OneChannel b = Channel.one2One ();
     final One2OneChannel c = Channel.one2One ();
 
     final One2OneChannel reset = Channel.one2one (new OverWriteOldestBuffer (1));
 
     new Parallel (
       new CSProcess[] {
         new Numbers (a.out ()),                               // generate numbers
         new FixedDelay (250, a.in (), b.out ()),              // let them through every quarter second
         new Regulate (b.in (), reset.in (), c.out (), 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.

Polling

Sometimes, we want to handle incoming channel data if it's there, but get on with something else if all is quiet. This can be done by PRI ALTing the channels we wish to poll against a SKIP guard:
 import org.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 `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.

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.

 import org.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;
       }
     }
 
   }
 
 }
 

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.

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!

To this end, a formal (CSP) model of Java's monitor primitives (the 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 Alternatives. 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.

See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected Object
    The monitor synchronising the writers and alting reader
    private boolean
    This indicates whether an AltingBarrier is one of the Guards.
    private int
    The index of a selected AltingBarrier.
    private boolean
    This flag is set by a successful AltingBarrier enable/disable.
    private int
    This is the index variable used during the enable/disable sequences.
    private static final int
     
    private int
    The index of the guard with highest priority for the next select.
    private final Guard[]
    The array of guard events from which we are selecting.
    private static final int
     
    private long
    If one or more guards were CSTimers, this holds the earliest timeout.
    private final int
     
    private static final int
     
    private int
    The index of the selected guard.
    private int
    The state of the ALTing process.
    private int
    If one or more guards were CSTimers, this holds the index of the one with the earliest timeout.
    private boolean
    This flag is set if one of the enabled guards was a CSTimer guard.
    private static final int
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    Alternative(Guard[] guard)
    Construct an Alternative object operating on the Guard array of events.
  • Method Summary

    Modifier and Type
    Method
    Description
    private void
    Disables the guards for selection.
    private void
    disableGuards(boolean[] preCondition)
    Disables the guards for selection.
    private final void
    Enables the guards for selection.
    private final void
    enableGuards(boolean[] preCondition)
    Enables the guards for selection.
    final int
    Returns the index of one of the ready guards.
    final int
    fairSelect(boolean[] preCondition)
    Returns the index of one of the ready guards whose preCondition index is true.
    final int
    Returns the index of one of the ready guards.
    final int
    priSelect(boolean[] preCondition)
    Returns the index of one of the ready guards whose preCondition index is true.
    (package private) void
    This is the wake-up call to the process ALTing on guards controlled by this object.
    final int
    Returns the index of one of the ready guards.
    final int
    select(boolean[] preCondition)
    Returns the index of one of the ready guards whose preCondition index is true.
    (package private) void
    This is a call-back from an AltingBarrier.
    (package private) void
    setTimeout(long msecs)
    This is the call-back from enabling a CSTimer guard.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • altMonitor

      protected Object altMonitor
      The monitor synchronising the writers and alting reader
    • enabling

      private static final int enabling
      See Also:
    • waiting

      private static final int waiting
      See Also:
    • ready

      private static final int ready
      See Also:
    • inactive

      private static final int inactive
      See Also:
    • state

      private int state
      The state of the ALTing process.
    • guard

      private final Guard[] guard
      The array of guard events from which we are selecting.
    • favourite

      private int favourite
      The index of the guard with highest priority for the next select.
    • selected

      private int selected
      The index of the selected guard.
    • NONE_SELECTED

      private final int NONE_SELECTED
      See Also:
    • barrierPresent

      private boolean barrierPresent
      This indicates whether an AltingBarrier is one of the Guards.
    • barrierTrigger

      private boolean barrierTrigger
      This flag is set by a successful AltingBarrier enable/disable.
    • barrierSelected

      private int barrierSelected
      The index of a selected AltingBarrier.
    • enableIndex

      private int enableIndex
      This is the index variable used during the enable/disable sequences. This has been made global to simplify the call-back (setTimeout) from a CSTimer that is being enabled. That call-back sets the timeout, msecs and timeIndex variables below. The latter variable is needed only to work around the bug that Java wait-with-timeouts sometimes return early.
    • timeout

      private boolean timeout
      This flag is set if one of the enabled guards was a CSTimer guard.
    • msecs

      private long msecs
      If one or more guards were CSTimers, this holds the earliest timeout.
    • timeIndex

      private int timeIndex
      If one or more guards were CSTimers, this holds the index of the one with the earliest timeout.
  • Constructor Details

  • Method Details

    • select

      public final int select()
      Returns the index of one of the ready guards. The method will block until one of the guards becomes ready. If more than one is ready, an arbitrary choice is made.
    • priSelect

      public final int priSelect()
      Returns the index of one of the ready guards. The method will block until one of the guards becomes ready. If more than one is ready, the one with the lowest index is selected.
    • fairSelect

      public final int fairSelect()
      Returns the index of one of the ready guards. The method will block until one of the 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.
    • enableGuards

      private final void enableGuards()
      Enables the guards for selection. If any of the guards are ready, it sets selected to the ready guard's index, state to ready and returns. Otherwise, it sets selected to NONE_SELECTED and returns.
    • disableGuards

      private void disableGuards()
      Disables the guards for selection. Sets selected to the index of the ready guard, taking care of priority/fair choice.
    • setTimeout

      void setTimeout(long msecs)
      This is the call-back from enabling a CSTimer guard. It is part of the work-around for Java wait-with-timeouts sometimes returning early. It is still in the flow of control of the ALTing process.
    • setBarrierTrigger

      void setBarrierTrigger()
      This is a call-back from an AltingBarrier. It is still in the flow of control of the ALTing process.
    • schedule

      void schedule()
      This is the wake-up call to the process ALTing on guards controlled by this object. It is in the flow of control of a process writing to an enabled channel guard.
    • select

      public final int select(boolean[] preCondition)
      Returns the index of one of the ready guards whose 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.

      Parameters:
      preCondition - the guards from which to select
    • priSelect

      public final int priSelect(boolean[] preCondition)
      Returns the index of one of the ready guards whose 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.

      Parameters:
      preCondition - the guards from which to select
    • fairSelect

      public final int fairSelect(boolean[] preCondition)
      Returns the index of one of the ready guards whose 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.

      Parameters:
      preCondition - the guards from which to select
    • enableGuards

      private final void enableGuards(boolean[] preCondition)
      Enables the guards for selection. The preCondition must be true for an guard to be selectable. If any of the guards are ready, it sets selected to the ready guard's index, state to ready and returns. Otherwise, it sets selected to NONE_SELECTED and returns.

    • disableGuards

      private void disableGuards(boolean[] preCondition)
      Disables the guards for selection. The preCondition must be true for an guard to be selectable. Sets selected to the index of the ready guard, taking care of priority/fair choice.