org.jcsp.nxt.lang
Class Barrier

java.lang.Object
  org.jcsp.nxt.lang.Barrier

All Implemented Interfaces:

java.io.Serializable

public class Barrier
extends java.lang.Object
implements java.io.Serializable

This enables barrier synchronisation between a set of processes.

Shortcut to the Constructor and Method Summaries.

Description

A channel is a CSP event in which only two processes (the reader and the writer) synchronise. A barrier is a CSP event in which any number of processes may synchronise. Any process synchronising on a barrier will be blocked until all processes associated with that barrier have synchronised. A process may not back off an attempted synchronisation - i.e. barriers cannot be used as guards in an Alternative.

A process network may contain many barriers - each being associated with a different subset of processes. These subsets may overlap and change at run-time. JCSP does not currently provide a checked way of associating a process with a particular barrier. That could be done, but would carry a syntactic and run-time overhead currently not thought worthwhile. Associating a barrier with its correct set of processes is a design issue and it is left to the designer to ensure correct useage.

Note: this notion of barrier corresponds to the EVENT synchronisation primitive added to the KRoC occam language system.

Deterministic Barriers

If the set of processes associated with a barrier remains fixed, barrier synchronisation introduces no non-determinism. So, a parallel system made up of processes, barriers (with fixed barrier sets) and 1-1 channels (with no ALTing on the channels and an exclusive read/write access discipline for all communicated objects) is deterministic - its semantics are independent of scheduling.

For fixed barrier sets, construct each barrier initialised to the number of processes to be associated with it and share it out amongst those processes.

For example, here is a fixed set of 10 processes synchronising on a shared barrier:

To synchronise on a barrier, a process just needs to invoke its sync method.

Non-Deterministic Barriers

A process may choose at any time to enroll or resign from any barrier it can see. It should not, of course, enroll on a barrier with which it is already associated - nor resign from a barrier with which it isn't! Because these operations are internal choices of individual processes and because they have an impact on the synchronisation properties of their environment, the resulting system is non-deterministic.

In the above example, Worker processes cycle between working and resting states, making their own decisions about when to switch. When working, they enroll in a barrier shared with a TimeKeeper process - when resting, they resign from this barrier. Whilst working and after they have enrolled, they execute a sequence of work units triggered by synchronisations on the barrier.

The TimeKeeper synchronises on the barrier at a regular rate (once per second) and, thus, coordinates the activities of all working Workers. A work unit can only start at the beginning of one of the TimeKeeper's time slots and each Worker can only perform one work unit per time slot. Should any work unit overrun a time slot, subsequent units (for all Workers) will have a late start. However, the system is stable - so long as there is some slack in the system (i.e. units do not generally overrun), the original schedule will be recovered.

Overheads

Free use of additional synchronisations to gain special control (such as in the above) depends on the overheads being not so great as to render that control pointless.

Going back to the original example, the entire barrier synchronisation could be discarded by dropping the TimeKeeper and making each Worker responsible for its own time schedule. However, setting n timeouts (where each setting has O(n) overheads) needs to be compared against setting 1 timeout (by the TimeKeeper) together with a (n+1)-way barrier synchronisation.

For the current implementation, the enroll and resign operations - together with most of the syncs - have unit time costs. The final sync, which releases all the other (n) processes blocked on the barrier, takes O(n) time. The unit time costs for this implementation are comparable with those of a synchronized method invocation followed by an Object.wait.

[Note: CSP synchronisation primitives can be implemented with much lighter overheads. For example, the KRoC occam equivalent to this Barrier (its EVENT) has (sub-microsecond) unit time costs for all its operations, including the final sync. Future work on JCSP may look towards this standard.]

Author:

P.H.Welch, Alex Panayotopoulos

See Also:

Serialized Form

Constructor Summary

Barrier()
Construct a barrier initially associated with no processes.

Barrier(int nEnrolled)
Construct a barrier (initially) associated with nEnrolled processes.

Method Summary

void	reset(int nEnrolled) Reset this barrier to be associated with nEnrolled processes.
void	resign() Disassociate the invoking process from this barrier.
void	sync() Synchronise the invoking process on this barrier.

Methods inherited from class java.lang.Object

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

Constructor Detail

Barrier

public Barrier()

Construct a barrier initially associated with no processes.

Barrier

public Barrier(int nEnrolled)

Construct a barrier (initially) associated with nEnrolled processes.

Parameters:

nEnrolled - the number of processes (initially) associated with this barrier.

Method Detail

reset

public void reset(int nEnrolled)

Reset this barrier to be associated with nEnrolled processes. This must only be done at a time when no processes are active on the barrier.

Parameters:

nEnrolled - the number of processes reset to this barrier.

sync

public void sync()

Synchronise the invoking process on this barrier. Any process synchronising on this barrier will be blocked until all processes associated with the barrier have synchronised (or resigned).

resign

public void resign()

Disassociate the invoking process from this barrier. Note that if the resigner is the last process associated with the barrier not to have invoked a sync, its resignation completes the barrier (as though it has invoked a sync) and releases all the remaining associated processes.