============================================================================== | A P P E N D I X 7 | ============================================================================== //{{{ stamp Date: Fri, 24 May 96 18:39:15 BST From: phw Message-Id: <9605241739.AA15815@mint.ukc.ac.uk> To: occam-com@ukc.ac.uk Subject: multi-CHAN_OF_INT ??? //}}} 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.