Totally nailed down (probably)

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

//{{{}}}

//{{{  CHAN_OF_INT for multiple readers/writers

Just in case the semantics of "notify" do not guarantee that the notified
thread is enqueued back on the monitor before the "notify" method returns,
here is a patch to CHAN_OF_INT that seals the associated security leak.

We don't need another flag ... but we do need another "wait"/"notify"
synchronisation between the reader and writer threads in case the reader
gets to the rendezvous first.  Curiously, this speeds up the cycle time
reported by ComsTime ... ?!!

//{{{  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 ...");
          }
          //}}}
          notify ();                       // schedule the writer to finish
        } 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 a reading thread to rendezvous ...");
          }
          //}}}
        } else {
          channel_empty = true;            // second to the rendezvous
          notify ();                       // schedule the waiting reader thread
          //{{{  wait ();                    // let the reader regain this monitor
          try {
            wait ();                       // let the reader regain this monitor
          } catch (InterruptedException e) {
            System.out.println ("CHAN_OF_INT: InterruptedException exception raised" +
              " whilst waiting for a reading thread to regain this monitor ...");
          }
          //}}}
        }
      }
    }
  }
  //}}}

}
//}}}

//}}}

//{{{  explanation of patch

If the reader is second to the rendezvous, there is no problem.

If the writer is second to the rendezvous, it writes to "channel_hold", resets
"channel_empty" and notifies the waiting reader thread.

//{{{  previously

Previously, the writer just exited, releasing the "write_monitor" which allows
another writer to compete with the reader we just notified for "this" monitor.
The reader must get in first to complete its read.  If another writer wins
this competition, the data for the reader is lost.

So long as the "notify" gets the notified thread back on the monitor queue
before "notify" exits, the reader will be ahead of any competing writer.

//}}}
//{{{  fixing the competition

In case this behaviour for "notify" isn't guaranteed, the writer does not now
exit, but follows up the "notify" with a "wait".  This releases the channel
monitor but retains the "write_monitor", leaving the reader to gain the channel
monitor in its own time and with no competition.  The reader gains the channel
monitor, notifies the waiting writer, completes its read and releases the
channel monitor and "read_monitor".

Then, either another reader or the notified original writer gains the channel
monitor.  In the former case, that reader is first to the next rendezvous and
executes a "wait" ... which lets in the original writer (from the previous
rendezvous).  All the original writer does is exit, releasing the channel
monitor and the "write_monitor" ... it doesn't matter if a reader got in
first.  Only one reader can get in first, because it doesn't let go of the
"read_monitor".

Phew!

//}}}
//{{{  another tiny assumption about Java semantics

This fix does assume that a sequence of statements in a synchronised section
of code that includes a "notify" (but does not include a "wait") is atomic
with respect to other sections synchronised on the same monitor -- i.e. that
the "notify" does not release the monitor temporarilly.

I think that's a safe assumption ...

//}}}

//}}}
//{{{  performance !!!

The peculiar thing is that adding this extra wait/notify synchronisation
(whenever the reader is first to the rendezvous) reduces the overheads
reported by the ComsTime benchmark ... from around 9 ms per cycle to
around 8 ms per cycle.

Weird ... I suppose it's some artifact of the Java interpreter ... ?

//}}}
//{{{  fly Java?

I wonder how CHAN_OF_INT might be proven formally to have the good behaviour
informally argued above?

Given the difficulty in finding even informal definitions of what the primitive
thread methods mean and the complete absence of any hint of a formal semantics,
verification doesn't seem to be anywhere on the agenda.  Yet Java is supposed
to have been motivated originally for use in embedded applications ...

With the advent of Java compilers and Sun's Java processors, the use of Java
for safety-critical systems is on its way ...

So, who wants to fly with a `Java-aware' avionics system?

What if your only alternative is one developed in C++?

//}}}
//{{{  brief discussion

//{{{  Java has to catch up with occam

Playing with occam channels and buffers in Java has been interesting and fun,
but has shown how hard it is to reason about multi-threaded Java codes that
have inter-thread dependencies that need coordination.  The "synchronized"
qualifier and "suspend/resume/yield" and "wait/notify" methods that Java gives
us operate at a very low level.  It is very easy to misuse them, even when
trying to be careful, and end up with systems that have uncontrolled race
hazards.  These are problems from the past and it's a shame to have to be
haunted by them again ... the advances of occam have been disregarded.

We have been making a start at retro-fitting some occam engineering on top
of Java, but there's a lot of catching up still to do!

//}}}
//{{{  preserve determinism where possible

Incidentally, I think we need to keep channels/buffers that are to be used
for multi-reader/writer communication distinct from those for a single reader
and writer.  The former, which have some relationship with occam3 SHARED and
CALL channels, introduce non-determinism.  The latter, which correspond to
occam2 CHAN communication, do not and have a significantly simpler semantics.
How best to access the explicit non-determinism of occam ALTs needs more
work, but Gerald Hilderink's demonstrations (in his FTP-able paper) are an
excellent start.

//}}}
//{{{  higher level problems and opportunities

Then, we can start to worry about higher-level problems (such as deadlock and
livelock) and opportunities (such as allowing greater scope for parallelism
through dynamic-but-secure data sharing and combining operators).  Actually,
we have to do this work on top of an occam (or BSP?) context ... things look
too undisciplined in Java for this kind of research ... retro-fit occam4 back
on Java later ...

//}}}

//}}}

Peter.

//}}}