OEP

167

Title

Extended Barrier Synchronisation

Summary

Enable special code to be triggered on completion of a barrier (optionally before the processes are released).

Owner

Peter Welch <p.h.welch@kent.ac.uk>

Status

Proposed

Date-Proposed

2008-03-08

Keywords

EXTENDED BARRIER SYNC

Motivation

Currently, an occam-pi BARRIER enables many processes to synchronise, but no data is exchanged. Often, this is used to phase appropriate access to shared resources by many processes. An example is to allocate CREW permissions on shared data, where the CREW allocation changes between phases. This can be used to exchange data between all the synchronising processes. Another example is to divide observations/negotiations on neighbourhoods of some shared environment (represented safely by server processes) from agreed updates to those neighbourhoods.

Aspects of this, as well as other capabilities, can be more neatly managed through extended barrier synchronisation.

Mechanism A

This adopts the same idea and syntax as the extended rendezvous on channel input, already present in occam-pi. Suppose b is a BARRIER (from which we have not resigned), then:

SYNC b
  ...  some action

makes the process wait until all processes enrolled on the barrier have also synchronised (as normal), but then the indented some action process is run before this and all the other synchronising processes may continue. If more than one of these processes have such extended actions, these actions proceed in parallel after all processes have reached their SYNC and they must all terminate before all processes may continue.

Note that the above semantics are easily achieved with two ordinary barrier synchronisations:

SEQ
  SYNC b
  ...  some action
  SYNC b

But all enrolled processes will have to be programmed to do the double synchronisation, even when they have no extended action to perform. In fact, this is a common pattern.

One advantage of that new syntax is that only processes that have the need for an extended action need the extended synchronisation structure – so errors are harder to make. Another advantage is that this can be implemented so that only those processes with extended actions engage in the second barrier – with maximum savings when there is only one of them (which may be common).

Caution

Accidental indenting of the line following a SYNC would lead to an extended barrier rendezvous, which would not be good!

For extended rendezvous on channel inputs, this is prevented by an explicit syntax for channel input:

in ?? x
  ...  some action

An accidental indentation following an ordinary channel input (with a single question-mark) would be rejected by the compiler.

So, it would be safer to do the same here and have an explicit syntax for extended barrier synchronisation:

EXTENDED SYNC b
  ...  some action

Mechanism B

This proposes a syntax that triggers just one process to perform an action between barrier completion and the release of the barrier synchronising processes.

[In Java 1.5, java.util.concurrent.CyclicBarrier introduces some of the capabilities below.]

Barriers are extended to have a tail – this is an ordinary channel, attached to the barrier, with a free (unshared) reading-end. When all enrolled processes have committed to SYNC on the barrier, a TRUE (or anything) is signalled down its tail channel before the processes are released.

The special action is performed by a process waiting on that channel-end. If the process is not waiting (e.g. it was ALTing on the channel-end from the barrier but is currently servicing something else), then barrier completion is blocked. If the process accepts the barrier signal with an extended channel input, its response has to be completed before the barrier processes are released. The signal could be forwarded to any number of other processes (possibly within an extended channel rendezvous) to require multiple parallel actions to be completed before the barrier is allowed to complete. The signal could be forwarded (possibly within an extended channel rendezvous) via another channel with a shared reading-end to let a range of servers compete over which of them performs the barrier triggered action. Such behaviours are determined solely by the barrier-tail handling process – there is freedom to devise all sorts of schemes.

Explicit Syntax

Declaring a barrier:

EXTENDED BARRIER b:

introduces the reading-end of a tail channel, written b?. This must be attached to just one receiving process – the barrier cannot complete without the signal it generates on the channel being accepted. Synchronisation on the barrier by enrolled processes is written as normal (SYNC b). That's all.

Note: the barrier tail, b?, is not something that can be obtained from a given barrier, b. It comes into existence through the extended barrier declaration – it is not the result of a post-fix operator, ?, on the barrier. This prevents multiple processes which have been passed a barrier parameter from also getting the tail.

Implicit Syntax

There are no special barriers for extended synchronisations. We just declare an ordinary barrier:

BARRIER b:

If the process declaring this barrier makes no reference to a tail, b?, then no tail exists and barrier synchronisations are the normal ones.

As with the explicit extended barrier declaration above, if the declaring process passes on just the barrier to another process through either a parameter or a channel (if the barrier is MOBILE), the receiving process cannot extract the tail.

Only if the declaring process references the tail, does the tail exist and all barrier synchronisations signal down it before they can complete. The reference could be through setting up a handling process in-line or passing the tail-end to an invocation of a separately declared handling process.

Mobile Barriers and Tails

The simplest rule is that a tail channel-end is mobile if, and only if, the barrier is mobile. Remember that b and b? are separate items, so they can be separately communicated. Probably, the barrier tail-end should not be SHARED – i.e. communicating it loses it.

Discussion

As Adam and Carl point out, Mechanism B is easily obtained as a special pattern of Mechanism A. We simply enroll one extra process on the barrier and get it to signal down a channel in an extended synchronisation:

PROC barrier.ping (BARRIER b, CHAN BOOL ping!)
  WHILE TRUE
    EXTENDED SYNC b
      ping ! TRUE
:

Now the barrier and barrier-tail are explicitly distinct items.

So, Mechanism A is more general than Mechanism B and, therefore, looks preferable. But there are two other reasons for Mechanism B.

First, it gives a language binding to a particular pattern of Mechanism A, enabling us to reason at the level of that pattern. Otherwise, we have to know the idiom to realise the relationship between the barrier, the ping channel and the process handling the ping. When drawing network diagrams, I would want to use (and have used) special icons for barrier-with-tail synchronisation explicitly connecting together all participants. Drawing just the barrier synchronising processes linked via the barrier, with one of them being the above barrier.ping connected to the handling process, only connects the participants indirectly. Of course, we can still draw the special barrier-with-tail icons, but it may be nice to have a direct syntax for expressing them. It depends on how useful this pattern really is.

Here's a fairly generic use for the pattern. The barrier-tail-handling process is an extra participant in the barrier synchronisation – the barrier can't complete until all enrolled processes synchronise and that process accepts the tail signal. But it has an extra capability:

The second reason is stronger. But it concerns the use of extended synchronisation with partial barriers. So, first we need an OEP/171 for that!

OEP/167 (last edited 2008-03-10 13:58:45 by phw)