multi-CHAN_OF_INT ???

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

//{{{}}}

Here's an updated CHAN_OF_INT class that provides a 1-1 synchronising occam
channel and is secure for multiple readers/writers.  It uses the same trick
mailed previously for securing multiple readers/writers for a shared buffer.

The original CHAN_OF_INT, that is only secure for a single reader/writer,
has simply been extended by the addition of an extra synchronisation for
a reader_monitor/writer_monitor.

//{{{  CHAN_OF_INT.java

//{{{  imports
import java.lang.InterruptedException;
//}}}

//{{{  class MONITOR {
class MONITOR {
}
//}}}

//{{{  public class CHAN_OF_INT {
public class CHAN_OF_INT {

  //{{{  COMMENT documentation
  //
  //CHAN_OF_INT extends an occam CHAN OF INT for multiple readers and writers.
  //
  //There is full synchronisation between a reading and writing thread.  Any
  //thread may read or write on this channel.  Readers and writers are queued
  //separately.  A reader only completes when it gets to the front of its queue
  //and finds a writer.  A writer only completes when it gets to the front of
  //its queue and finds a reader.
  //
  //There is no logical buffering of data in the channel.  However, each int
  //is actually copied three times with this implementation!
  //
  //}}}

  //{{{  local state
  
  int channel_hold;                // buffer (not detectable to users)
  
  boolean channel_empty = true;    // synchronisation flag
  
  MONITOR read_monitor =           // all readers multiplex through this
    new MONITOR ();
  
  MONITOR write_monitor =          // all writers multiplex through this
    new MONITOR ();
  
  //}}}

  //{{{  public int read () {
  public int read () {
    synchronized (read_monitor) {
      synchronized (this) {
        if (channel_empty) {
          channel_empty = false;           // first to the rendezvous
          //{{{  wait ();                    // wait for the writer thread
          try {
            wait ();                       // wait for the writer thread
          } catch (InterruptedException e) {
            System.out.println ("CHAN_OF_INT: InterruptedException exception raised" +
              " whilst waiting for a writing thread to rendezvous ...");
          }
          //}}}
        } else {
          channel_empty = true;            // second to the rendezvous
          notify ();                       // schedule the waiting writer thread
        }
        return channel_hold;
      }
    }
  }
  //}}}
  //{{{  public void write (int n) {
  public void write (int n) {
   synchronized (write_monitor) {
     synchronized (this) {
        channel_hold = n;
        if (channel_empty) {
          channel_empty = false;           // first to the rendezvous
          //{{{  wait ();                    // wait for the reader thread
          try {
            wait ();                       // wait for the reader thread
          } catch (InterruptedException e) {
            System.out.println ("CHAN_OF_INT: InterruptedException exception raised" +
              " whilst waiting for an reading thread to rendezvous ...");
          }
          //}}}
        } else {
          channel_empty = true;            // second to the rendezvous
          notify ();                       // schedule the waiting reader thread
        }
      }
    }
  }
  //}}}

}
//}}}


//}}}
//{{{  performance

ComsTime reports similar overheads for this multi-reader/writer CHAN_OF_INT
as it did for the multi-reader/writer BUFFER_OF_INT (about 9 ms per cycle).

//}}}
//{{{  small fly in the ointment ???

This fly was present in the earlier CHAN_OF_INT (single reader/writer), but
isn't (I don't think) a danger in the BUFFER_OF_INT ...

The algorithm relies on some more Java semantics ... whose nature, apparently,
we have to guess:

//{{{  another question on Java semantics ???

Thread A synchronizes on monitor X and executes a wait on X, releasing the
monitor.

Then, thread B synchronizes on monitor X and executes a notify on X, which
puts thread A back on the queue for monitor X.

Now, can I assume that A *is* back on the X-queue *before* the notify method
finishes execution?

That would be a reasonable semantics to have for notify, but it's conceivable
that an implementation of notify might merely start the process of putting the
waiting thread on the X-queue ... so that it happens some time in the future.

//}}}
//{{{  a negative answer would be a disaster for CHAN_OF_INT !!!

A negative answer would be a disaster for CHAN_OF_INT!

Consider the "notify" at the end of the "write" method.  This is supposed
to reschedule the waiting reader thread back on to the "this" monitor.

I assume that this happens *before* "notify" finishes execution.

Otherwise, "notify" exits and this "write" method exits.  That releases the
"write_monitor", allowing another writer thread (it could actually be the
same writer thread again) on to the "this" monitor queue.  If that writer
thread is before the reader thread we notified earlier (and this can't
happen if it is queued before notify finishes), it will overwrite the
"channel_hold" data before the notified reader reads it!  Oh, dear ...

//}}}
//{{{  but not for BUFFER_OF_INT !!!

In BUFFER_OF_INT, it doesn't matter if further writers get in before the
blocked reader that had been notified.  The further writers can't overwrite
the data that the notified reader hasn't yet read and we are safe.

The worst that can happen is that writers fill up the buffer ... whereupon
they have to leave the buffer monitor unclaimed for the notified reader
to claim at leisure.

//}}}
//{{{  I think the answer is yes ???

I feel fairly confident the answer to the question is yes ... I've tested
ComsTime pretty hard with this version of CHAN_OF_INT and it probably would
have fallen over by now otherwise ... but how to find out for sure ... would
you be happy in an airplane whose avionics relied on this?!!

Paddy suggested comp.lang.java ... but there's far too much there ... there's
so much trivia that, if there is anything worthwhile, who can't find it!

CHAN_OF_INT could probably be fixed if the answer turned out negative, but
we would need another flag and associated wait/notify ... messy!

//}}}

This Java threads semantics is *much* harder than it seems ... the code is
so simple ... but what does it really mean ... ???

//}}}

Roll on occam3,

Peter.