Parallel Clauses & Semaphores

Prefixing a collateral clause with PAR declares that its units may be executed in parallel:

35.1 PAR clauses

Prefixing a collateral clause with PAR declares that its units may be executed in parallel:

A plain collateral clause permits arbitrary interleaving; PAR additionally requires that the units be able to proceed concurrently (so they can synchronize with each other via semaphores).

PAR (task a, task b, task c)
PAR BEGIN producer, consumer END

35.2 Semaphores

ALGOL 68 adopted Dijkstra's semaphores:

SEMA s = LEVEL n — a semaphore with initial value n.

DOWN s — wait until the level is positive, then decrement (Dijkstra's P).

UP s — increment, possibly releasing a waiting unit (Dijkstra's V).

LEVEL s (monadic on a SEMA) — current level.

35.3 Mutual exclusion

BEGIN
   SEMA mutex = LEVEL 1;
   INT counter := 0;
   PROC worker = (INT times) VOID:
      FOR i TO times DO
         DOWN mutex;
         counter +:= 1;          # critical section #
         UP mutex
      OD;
   PAR (worker(1000), worker(1000), worker(1000));
   print(("counter = ", whole(counter, 0), newline))   # 3000 #
END

35.4 Producer–consumer with a bounded buffer

BEGIN
   INT size = 4;
   [0 : size - 1] INT buffer;
   INT head := 0, tail := 0;
   SEMA free slots = LEVEL size, filled = LEVEL 0, lock = LEVEL 1;

   PROC producer = VOID:
      FOR i TO 10 DO
         DOWN free slots;
         DOWN lock;
         buffer[tail] := i * i;
         tail := (tail + 1) MOD size;
         UP lock;
         UP filled
      OD;

   PROC consumer = VOID:
      FOR i TO 10 DO
         DOWN filled;
         DOWN lock;
         INT v = buffer[head];
         head := (head + 1) MOD size;
         UP lock;
         UP free slots;
         print((whole(v, 0), " "))
      OD;

   PAR (producer, consumer);
   print(newline)
END

35.5 Implementation notes

a68g implements PAR with operating-system threads on platforms that support POSIX threads; on builds without thread support, parallel clauses may be executed sequentially or rejected — check a68g --version/the manual for your build.

The Revised Report's model is deliberately minimal (no monitors, channels or futures). Later languages built richer models on the same ideas: Concurrent Pascal (monitors), Ada (tasks and rendezvous), occam/Go (channels).

Shared variables updated outside semaphore-protected sections are a data race — the Report leaves the result undefined.