org.jcsp.lang
Class Crew

java.lang.Object
  org.jcsp.lang.Crew

public class Crew
extends Object

This provides a Concurrent Read Exclusive Write (CREW) lock for synchronising fair and secure access to a shared resource.

Shortcut to the Constructor and Method Summaries.

Description

Concurrent Read Exclusive Write

Parallel processes must ensure controlled access to shared resources whose state can change as a side-effect of that access. Otherwise, there will be race hazards resulting from arbitrary interleaving of that access between competing processes. For example, a reader of a resource may observe partially updated (and, hence, invalid) state because of the activities of a concurrent writer. Or two writers may interfere with each other's updating to leave a resource in an invalid state (as well as confusing themselves).

Where possible, each resource should be kept wrapped up in a process and accessed via a channel interface - this will always be safe. However, this also serialises access to the resource so that it can be used by only one process at a time, regardless of whether that usage is read-only or read-write. This is an example of Exclusive Read Exclusive Write (EREW).

[Note: the above assumes the resource process has only a serial implementation. A parallel implementation, of course, will allow parallel access along parallel channels. However, if that parallel implementation needs to share state, that shared state is itself a resource and we have only deferred the problem of secure parallel access.]

Parallel reader operations on a resource do not lead to race hazards, so long as no writer is present, and many applications need to be able to exploit this. Parallel writer operations are always dangerous and must be suppressed. This principle is known as Concurrent Read Exclusive Write (CREW).

Design Pattern

Suppose many processes hold a reference to a shared object. Associate that shared object with a shared Crew lock, reference to which must also be given to each of those processes.

For example, suppose Resource is a class whose methods may be classified as either readers (i.e. cause no state change) or writers (i.e. cause state change). Whenever we construct a Resource, construct an associated Crew lock:

   Resource resource = new Resource (...);
   Crew resourceCrew = new Crew ();
 

Each process holding a reference to resource must also be given a reference to resourceCrew. Invocations of reader methods must be sandwiched between a claim and release of the reader lock within resourceCrew:

   resourceCrew.startRead(); // this will block until no writer is present
   ...                       // invoke reader methods of resource
   resourceCrew.endRead();   // releases this reader's lock on resource
 

Invocations of writer methods must be sandwiched between a claim and release of the writer lock within resourceCrew:

   resourceCrew.startWrite(); // this will block until no reader
                              // or writer is present
   ...                        // invoke writer (or reader) methods
                              // of resource
   resourceCrew.endWrite();   // releases this writer's lock on resource
 

This pattern enables fair and secure access to a shared resource according to CREW rules. Concurrent readers will be allowed, so long as no writer is present. A single writer will be allowed, so long as no readers nor other writers are present. So long as each read or write operation is finite, readers will not be blocked indefinitely by writers and vice-versa (but see the Cautionary Note).

Access Sequences for the Worried

Java is a language that allows the throwing and catching of exceptions (and a return from a method invocation anywhere). This means that the normal sequential flow of control is not necessarilly what happens: what-you-see-is-NOT-what-you-get, a worrying property. If an uncaught exception is thrown (or a return executed) from the resource-using part of either of the above access sequences, the corresponding Crew lock would not be released. To protect ourselves from this, embed the access sequence within a try-finally clause - for example:

   try {
     resourceCrew.startRead(); // this will block until no writer is present
     ...                       // invoke reader methods of resource
   } finally {
     resourceCrew.endRead();   // releases this reader's lock on resource
   }
 

and:

   try {
     resourceCrew.startWrite(); // this will block until no reader
                                // or writer is present
     ...                        // invoke writer (or reader)
                                // methods of resource
   } finally {
     resourceCrew.endWrite ();  // releases this writer's lock on resource
   }
 

Now, the lock will always be released whether the reader/writer section exits normally or exceptionally. This asymmetric pattern is not very pretty, but is a classic application of the try-finally facility.

Binding the Shared Resource to its CREW Lock

In JCSP, shared references may be passed to processes through constructors, through mutator (set...) methods (but only, of course, before and in between runs) or through channels (when running).

If a resource and its lock are held in separate objects (as above), passing them both to the processes that share them is a little tedious and error prone. It is better to combine them into a single object.

One way is to define the Resource class to extend Crew. Then, we only need to distribute the Resource object and its access is protected by inherited methods - for example:

   resource.startRead ();        // this will block until no writer is present
   ...                           // invoke reader methods of resource
   resource.endRead ();          // releases this reader's lock on resource
 

However, this may not be possible (since our design may require Resource to extend something else).

Alternatively, we could declare (or extend) Resource to contain an additional Crew attribute. Again, we need only distribute the Resource object. The sharing processes recover the associated lock:

   Crew resourceCrew = resource.getCrew ();
 

and can use the original access sequences.

However, this Crew class offers the option of doing this the other way around, so that no modifications are needed on the application Resource. Pass the Resource object to the Crew constructor and a reference will be saved as an attribute of the Crew object. For example:

   Crew resourceCrew = new Crew (new Resource (...));
 

Processes to which this resourceCrew object are distributed can recover the original resource by invoking getShared - for example:

   Resource resource = (Resource) resourceCrew.getShared ();
 

and can again use the original access sequences.

CREW-synchronised Methods

The safest way to ensure adherence to the design pattern is to burn the correct access sequence into each reader and writer method. For example, extend Resource to contain a private Crew field and override each method to sandwich its invocation between the appropriate synchronisations:

 class ResourceCrew extends Resource {
 
   private final Crew crew = new Crew ();
 
   public Thing readerMethod (...) {
     crew.startRead ();      // this will block until no writer is present
     Thing result = super.readerMethod (...);
     crew.endRead ();        // releases this reader's lock on resource
     return result;
   }
 
   public void writerMethod (...) {
     crew.startWrite ();     // this will block until no reader
                             // or writer is present
     super.writerMethod (...);
     crew.endWrite ();       // releases this writer's lock on resource
   }
 
   ...  etc. for all other methods.
 
 }
 

Now, parallel processes can safely share references to an instance of ResourceCrew. Invocations of its reader and writer methods will be automatically CREW-synchronised.

Notes:

• this is similar to declaring all class methods to be synchronized (which guarantees EREW-synchronisation for parallel access to its instances);
• it may have been better to have designed Resource like this in the first place (rather than extending it as in the above);
• the above access sequences may need to be of the defensive variety;
• a disadvantage of this approach is that we do not have the capability of grouping a sequence of reader or reader/writer methods within a single CREW-synchronisation envelope.

Alternatives to CREW for Shared Objects

The proliferation of references in object-oriented design is a common source of error, even for single-threaded systems. For concurrent object-oriented design, we must be especially careful if we are to avoid the perils of race hazard.

Protocols other than CREW may be applied to ensure the safe parallel use of these references. For instance, if the shared reference is to an immutable object (like String), no special action is needed - this is Concurrent Read (CR).

On the other hand, if a reference to a mutable object (A) is passed between processes over channels, the sender may agree not to refer to A (nor to any objects referred to within A) in the future - unless, of course, the original reference to A is passed back. In this way, the reference acts as a unique token, possesion of which must be held before access is allowed. See also Paraplex for a double buffering adaptation of this.

Such patterns give us safe, secure and dynamic forms of Exclusive Read Exclusive Write (EREW) sharing which, along with the dynamic CREW provided by this class, complement the static control automatically conferred by the CSP process model. We just have to know when each is appropriate and apply them with due care.

Implementation Note

Channels, which are a specialisation of the multiway CSP event, are a fundamental primitive for synchronising the actions of concurrent processes. Common patterns of use have given rise to higher-level synchronisation paradigms that (when applicable) are easier and, therefore, safer to use than the raw primitives. This CREW lock is an example of this. [Another is the CALL channel.]

The implementation is given here because it is short and simple - an example of the power of expression (and provability) that follows from the CSP/occam model. Correct implementation of a CREW lock has been notoriously difficult. See, for example, Hoare's short but rather tricky solution from his paper, `Monitors: an Operating System Structuring Concept' [C.A.R.Hoare, CACM, 17(10) pp. 549-557, October 1974] - a paper often quoted as one of the sources for the Java monitor model. In contrast, this CSP version is easy and that easiness is important.

Each Crew object spawns off a private and anonymous CrewServer process with which it interacts only via channels:

All accessing processes (i.e. the startRead/startWrite methods) communicate down the any-1 request channel, identifying themselves as either a READER or WRITER:

   public void startRead () {
     request.write (CrewServer.READER);
   }
 
   public void startWrite () {
     request.write (CrewServer.WRITER);
     writerControl.write (0);
     // wait for all current readers to finish
   }
 

For startRead, this is all that happens - CrewServer will refuse the communication if there is a writer present. When accepted, there will be no writer present and the reader has permission to read the shared resource.

The startWrite communication will also be refused if another writer is present. If there are readers present, it is accepted. This has to be the case since, as far as the CrewServer is aware, it might have been from a startRead. So, acceptance of this communication does not yet give the writer permission to start writing - but it does let CrewServer know that a writer wants to write. To get that permission, the writer performs a second communication on writerControl - see above.

After accepting a writer request, CrewServer refuses further communications on request and writerControl until all readers have finished - which they do by signalling on readerRelease:

   public void endRead () {
     readerRelease.write (0);
   }
 

Refusing the request channel parks newly arriving readers and writers safely. When all existing readers have gone away, CrewServer accepts the outstanding communication on writerControl, which gives the waiting writer permission to write. CrewServer then waits for a second communication on writerControl, which is the signal from the writer that it has finished writing:

   public void endWrite () {
     writerControl.write (0);
   }
 

before returning to its initial state (listening on request and readerRelease).

The logic is easier to explain in JCSP:

 package org.jcsp.lang;
 
 class CrewServer implements CSProcess {      // this is not a public class
 
   public static final int READER = 0;
   public static final int WRITER = 1;
 
   private final AltingChannelInputInt request;
   private final ChannelInputInt writerControl;
   private final AltingChannelInputInt readerRelease;
 
   public CrewServer (final AltingChannelInputInt request,
                      final ChannelInputInt writerControl,
                      final AltingChannelInputInt readerRelease) {
     this.request = request;
     this.writerControl = writerControl;
     this.readerRelease = readerRelease;
   }
 
   public void run () {
     int nReaders = 0;
     Guard[] c = {readerRelease, request};
     final int READER_RELEASE = 0;
     final int REQUEST = 1;
     Alternative alt = new Alternative (c);
     while (true) {
       // invariant : (nReaders is the number of current readers) and
       // invariant : (there are no writers)
       switch (alt.priSelect ()) {
         case READER_RELEASE:
           readerRelease.read ();         // always let a reader finish reading
           nReaders--;
         break;
         case REQUEST:
           switch (request.read ()) {
             case READER:
               nReaders++;                // let a reader start reading
             break;
             case WRITER:
               for (int i = 0; i < nReaders; i++) {
                 readerRelease.read ();   // wait for all readers to go away
               }
               nReaders = 0;
               writerControl.read ();     // let the writer start writing
               writerControl.read ();     // wait for writer to finish writing
             break;
           }
         break;
       }
     }
   }
 
 }
 

Note that a CrewServer cannot be misused by reader and writer processes. It is private to each Crew lock and operated correctly by the methods of that lock. Given this correct operation, it is trivial to establish the declared loop invariant. All readers and writers start by communicating on the request channel so, so long as that is fairly serviced and that no read or write lasts forever, processes cannot be indefinitely blocked (e.g. readers by writers or writers by readers).

Cautionary Note

Fair servicing of readers and writers in the above depends on fair servicing of the any-1 request and readerRelease channels. In turn, this depends on the fair servicing of requests to enter a synchronized block (or method) by the underlying Java Virtual Machine (JVM). Java does not specify how threads waiting to synchronize should be handled. Currently, Sun's standard JDKs queue these requests - which is fair. However, there is at least one JVM that puts such competing requests on a stack - which is legal but unfair and can lead to infinite starvation. This is a problem for any Java system relying on good behaviour from synchronized, not just for JCSP's any-1 channels or Crew locks.

Author:

P.H.Welch

Constructor Summary

Crew()
Construct a lock for CREW-guarded operations on a shared resource.

Crew(Object shared)
Construct a lock for CREW-guarded operations on a shared resource.

Method Summary

void	endRead() This must be invoked after any read operations on the associated shared resource.
void	endWrite() This must be invoked after any write operations on the associated shared resource.
protected void	finalize() Finalize method added to terminate the process that it spawned.
Object	getShared() This returns the shared resource associated with this lock by its constructor.
void	startRead() This must be invoked before any read operations on the associated shared resource.
void	startWrite() This must be invoked before any write operations on the associated shared resource.

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Crew

public Crew()

Construct a lock for CREW-guarded operations on a shared resource.

Crew

public Crew(Object shared)

Construct a lock for CREW-guarded operations on a shared resource.

Parameters:

shared - the shared resource for which this lock is to be used (see getShared).

Method Detail

finalize

protected void finalize()
                 throws Throwable

Finalize method added to terminate the process that it spawned. The spawned process holds no references to this object so this object will eventually fall out of scope and gets finalized.

Overrides:

finalize in class Object

Throws:

Throwable

startRead

public void startRead()

This must be invoked before any read operations on the associated shared resource.

endRead

public void endRead()

This must be invoked after any read operations on the associated shared resource.

startWrite

public void startWrite()

This must be invoked before any write operations on the associated shared resource.

endWrite

public void endWrite()

This must be invoked after any write operations on the associated shared resource.

getShared

public Object getShared()

This returns the shared resource associated with this lock by its constructor. Note: if the parameterless constructor was used, this will return null.

Returns:

the shared resource associated with this lock.