============================================================================== | A P P E N D I X 8 | ============================================================================== //{{{ stamp Date: Mon, 27 May 96 16:11:05 BST From: phw To: occam-com@ukc.ac.uk Subject: Totally nailed down (probably) //}}} //{{{ 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. //}}}