Package 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 invalid input: '<' 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

Constructors
Constructor
Description
`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

Modifier and Type
Method
Description
`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 Details

### 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 Details

### 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.