# Concurrent Programming

- Module Processes
- Module Semaphores

## Module Processes

The module `Processes` provides a basic set of facilities for use in concurrent programs. These can be used on their own, or in conjunction with those from the module `Semaphores` which provide for potentially parallel parts of the program to exclude one another from regions of interaction.

A concurrent program consists of a number of processes, each of which may potentially run in parallel with the others but is distinguishable from them. At any one time, a process may be in one of four states: It may be ready, that is, eligible to use the processor but not actually doing so. It may be current, that is, actually using the processor. It may be passive, that is, ineligible to use the processor until another process makes it eligible. Lastly, it may be waiting, that is, ineligible to use the processor until the occurrence of one of a set of events for which it is waiting.

At all times there must be at least one process using the processor, or, if no process is eligible, there must be at least one process waiting for some external event.

Two general styles of use are envisaged, and both may be present in a single program.

In the first style (using `Switch`), the model is of a set of closely coupled processes, which explicitly choose which of them is to run next, and which pass information between themselves as part of the choice. The intention is to provide a higher level coroutine-like facility between processes of the same urgency.

In the second style (using `Activate` and `SuspendMe`), the processes are written to be less dependent on one another, and the choice of which of them runs is left to an internal scheduler, which is invoked whenever one process is suspended or another one is reactivated. This internal scheduler makes use of the fact that each process has an associated static `urgency', specified by an `INTEGER` parameter when it is first created. The scheduler ensures that it cannot be the case that a process eligible to use the processor has an urgency greater than one of the processes currently doing so. The `main process' (the parent program) is given a default urgency of zero; for other processes, the more positive the value of urgency, the more urgent is the process.

Those processes that suspend themselves to wait for external events must first associate themselves with one or more sources of such events. The International Standard does not prescribe how events occur, or what the sources of events must be, other than to require that they be mapped in an implementation-defined way to values of the pervasive type `CARDINAL`, and to require that a source of events cannot be connected to more than one process simultaneously.

NOTES:

- There is no requirement that pre-emptive scheduling be employed, although an implementation is free to incorporate such scheduling if this is desired.
- Although the International Standard applies to single-processor machines, if a pre-emptive (time-sliced) scheduler is present there may conceptually be more than one `current' process; the description above is phrased so as to emphasize this.
- A program that uses the module `Processes` should not make explicit use of coroutines (except, perhaps, in the implementation of `Processes` itself).
- This is a partial specification: Various of the procedures in the modules `Processes` and `Semaphores` have semantics expressed in terms of preconditions. Their behaviour in situations where these preconditions are not met is deliberately not specified; in particular, the raising of exceptions is not required. This is a deliberate decision that allows to achieve maximum efficiency in the implementation of these modules.

The exceptions raised by `Processes` are identified by the values of the enumeration type `ProcessesExceptions`:

    TYPE
      ProcessesExceptions = (passiveProgram, processError);

The detection of the exception `processError` is implementation-defined.

After the module is initialized, there is exactly one process, known as the `main process'. This process have an urgency of `0` and a parameter of `NIL`; initially, it is not associated with any source of events.

CHANGE:

This module is not based on the module `Processes` described in Programming in Modula-2.

- Types of Processes
- The Procedures of Processes
- Create - Create new process
- Start - Start new process
- StopMe - Terminate calling process
- SuspendMe - Suspend calling process
- Activate - Activate process
- SuspendMeAndActivate - Suspend current process and activate another
- Switch - Switch to another process
- Wait - Wait for event
- Attach - Associate event source
- Detach - Dissociate event source
- IsAttached - Query event source
- Handler - Query event handler
- Me - Query current process id
- MyParam - Query current process parameter
- UrgencyOf - Query process urgency
- IsProcessesException - Query exceptional state
- ProcessesException - Query exception id

### Types of Processes

    TYPE
      ProcessId;
        (* Used to identify processes *)
      Parameter = SYSTEM.ADDRESS;
        (* Used to pass data between processes *)
      Body = PROC;
        (* Used as the type of a process body *)
      Urgency = INTEGER;
        (* Used by the internal scheduler *)
      Sources = CARDINAL;
        (* Used to identify event sources *)

### The Procedures of Processes

The semantics of certain of the procedures of `Processes` require that a process be selected from the set of processes that are eligible to run, and be scheduled for execution. The selection algorithm shall guarantee that no process eligible to use the processor has an urgency greater than one of the processes currently doing so.

NOTES:

- The procedures in this category are `Start`, `StopMe`, `SuspendMe`, `Activate`, `SuspendMeAndActivate` and `Wait`.
- The urgency of a process is specified, when it is created, by a value of the type `INTEGER`, and cannot be changed dynamically. The more positive the value of urgency, the more urgent the process.

Certain of the procedures of `Processes` require that a process be associated with a source of external events. There shall be an implementation-defined mapping of values of the type `CARDINAL` to such sources of events.

A source of events shall not be associated with more than one process at any instant.

NOTES:

- The International Standard does not prescribe how events occur, or what the sources of events must be, other than in terms of this implementation-defined mapping.
- The International Standard does not specify the consequences if a value (of the type `Sources`) that is not mapped to a source of events is passed as an actual parameter to any of the procedures `Attach`, `Detach`, `IsAttached` or `Handler`.

### Create - Create new process

    PROCEDURE Create (procBody: Body;
                      extraSpace: CARDINAL;
                      procUrg: Urgency;
                      procParams: Parameter;
                      VAR procId: ProcessId);

Module `Processes`

The procedure `Create` creates a new process. An unique value of the type `ProcessId` is assigned to `procId` as an identity for the process. The urgency and parameters for the created process are those given by `procUrg` and `procParams` respectively. `extraSpace` specifies the amount of workspace (in units of `SYSTEM.LOC`) that is required by the process, above any fixed overhead needed by the implementation of `Processes`.

The process will be ineligible to run (i.e. it is created in the passive state). When the process is first activated, it will start execution by invoking the procedure that is denoted by `procBody`.

The usage made of the workspace is implementation-dependent.

If the end of this procedure body is reached, or if a return statement is executed in the procedure body, then the effect will be the same as calling the protection domain exit procedure (if any), followed by an explicit call of `StopMe`.

NOTES:

- The process will be activated when another process makes it eligible by calling `Switch` or `Activate` or `SuspendMeAndActivate`.
- The standard library makes no provision to handle exceptions generated by created processes, which must handle all exceptions themselves if it is wished to avoid exceptional termination of a program.

### Start - Start new process

    PROCEDURE Start (procBody: Body;
                     extraSpace: CARDINAL;
                     procUrg: Urgency;
                     procParams: Parameter;
                     VAR procId: ProcessId);

Module `Processes`

The procedure `Start` have an identical effect to the procedure `Create`, except that the created process will be eligible to run immediately (i.e. it is created in the ready state).

### StopMe - Terminate calling process

    PROCEDURE StopMe ();

Module `Processes`

If the calling process is not associated with any source of events, the procedure `StopMe` causes the calling process to be terminated and removed from the system. The procedure does not return; the calling process will not again become eligible to run. If there are no other processes, then normal termination of the program is initiated. If there are other processes eligible to run, then one of them is selected for execution. The exception `passiveProgram` is raised if there are other processes, but none of them is eligible to run and none of them is waiting for an event to occur.

NOTES:

- If the main process stops, the other processes will continue to run.
- The behaviour of `StopMe` in situations where the calling process is associated with a source of events is implementation-dependent.

### SuspendMe - Suspend calling process

    PROCEDURE SuspendMe ();

Module `Processes`

The procedure `SuspendMe` causes the calling process to become ineligible to run (i.e. to enter the passive state). If there are other processes eligible to run, then one of them is selected for execution. The exception `passiveProgram` is raised if no other process is eligible to run and no other process is waiting for an event to occur.

NOTE:

The suspended process can be reactivated when another process again makes it eligible by calling `Switch` or `Activate` or `SuspendMeAndActivate`.

### Activate - Activate process

    PROCEDURE Activate (procId: ProcessId);

Module `Processes`

If the process identified by `procId` is passive or waiting, the procedure `Activate` causes that process to become eligible to run (i.e. to enter the ready state); otherwise it have no effect.

NOTE:

If the designated process was suspended by a call of `Wait`, it will become ready in the same way as if the event had occurred. Thus, if the procedure `Activate` (or `SuspendMeAndActivate`) is used to reactivate a waiting process, further checking will usually be required in that process to determine whether or not the event for which it was waiting had actually taken place.

### SuspendMeAndActivate - Suspend current process and activate another

    PROCEDURE SuspendMeAndActivate (procId: ProcessId);

Module `Processes`

If the process identified by `procId` is passive, waiting, or is the calling process, the procedure `SuspendMeAndActivate` causes the calling process to become ineligible to run (i.e. to enter the passive state), and causes the process identified by `procId` to become eligible to run (i.e. to enter the ready state); otherwise the call have no effect.

NOTE

`SuspendMeAndActivate(procId)` effectively performs an atomic (i.e. `indivisible') sequence of the calls `SuspendMe()` and `Activate(procId)`. If applied to the identity of the calling process, the effect is to force a scheduling operation.

### Switch - Switch to another process

    PROCEDURE Switch (procId: ProcessId; VAR info: Parameter);

Module `Processes`

If the calling process has an urgency no greater than that of the process identified by `procId`, the procedure `Switch` causes the calling process to become ineligible to run (i.e. to enter the passive state), and resumes execution of the process identified by `procId`. The exception `processError` occurs (but need not be raised) if this process is already eligible to run. `info` is passed as a parameter to the process identified by `procId`. If the calling process is reactivated as a result of another process calling `Switch`, then `info` is assigned the value passed by that other call. If the calling process is reactivated as a result of another process calling `Activate` or `SuspendMeAndActivate`, then `info` is assigned the value `NIL`.

NOTE:

`Switch` is intended to allow a high-level coroutine facility for use within concurrent programs. Several consequences follow:

1. The process that is resumed will only be able to retrieve the parameter passed to it as `info` if it was ineligible to run by virtue of itself having called `Switch`.
2. The behaviour of `Switch` in situations where the urgency of the calling process is greater than the urgency of the process identified by `procId` is implementation-dependent.
3. While a call of `Switch` may be used instead of `Activate` to activate a process, `p`, of a higher urgency than the caller, `p` will not be able to use `Switch` if it wishes to reactivate that caller; it will be obliged to use `Activate` or `SuspendMeAndActivate`.
4. If the designated process was suspended by a call of `Wait`, it will become ready in the same way as if the event had occurred. Thus, if the procedure `Switch` (or `Activate` or `SuspendMeAndActivate`) is used to reactivate a waiting process, further checking will usually be required in that process to determine whether or not the event for which it was waiting had actually taken place.

### Wait - Wait for event

    PROCEDURE Wait ();

Module `Processes`

The procedure `Wait` causes the calling process to become ineligible to run (i.e. to enter the waiting state) if it is associated with a source of events. If there are other processes eligible to run, then one of them is selected for execution.

NOTES:

- One of the ready processes is selected for execution to replace the caller of `Wait`. This is on the assumption that, if there are ready processes that are not executing, the scheduler imposes a fixed upper limit on the number of executing processes.
- The process will remain ineligible to run until an event occurs from one of the sources to which it is attached, or until it is made eligible by another process calling `Switch` or `Activate` or `SuspendMeAndActivate`.
- If a process waiting for an event is reactivated by virtue of a call being made by another process to `Switch` or `Activate` or `SuspendMeAndActivate`, it will become ready in the same way as if the event had occurred. Thus, in such situations, further checking will usually be required to determine whether or not the event for which it was waiting had actually taken place.
- The behaviour of `Wait` if the calling process has not been attached to a source of events, or if another process is attached to the event source after the calling process has called `Wait` is implementation-dependent. In such circumstances the calling process may never again become eligible to run, and the system could deadlock.

### Attach - Associate event source

    PROCEDURE Attach (eventSource: Sources);

Module `Processes`

The procedure `Attach` associates the source of events given by `eventSource` with the calling process. If the source of events is already associated with a process, then that association is first broken.

### Detach - Dissociate event source

    PROCEDURE Detach (eventSource: Sources);

Module `Processes`

The procedure `Detach` dissociates the source of events given by `eventSource` from the program.

NOTE:

`Detach` has no effect if the program is not associated with `eventSource`.

### IsAttached - Query event source

    PROCEDURE IsAttached (eventSource: Sources): BOOLEAN;

Module `Processes`

The function procedure `IsAttached` returns `TRUE` if and only if the source of events given by `eventSource` is associated with one of the processes in the program.

### Handler - Query event handler

    PROCEDURE Handler (eventSource: Sources): ProcessId;

Module `Processes`

If the source of events identified by `eventSource` is associated with a process, the function procedure `Handler` is the identity of that process.

NOTE:

The value of the call `Handler(eventSource)` is implementation-dependent in the situation where the value of `eventSource` is not mapped to any real source of events.

### Me - Query current process id

    PROCEDURE Me (): ProcessId;

Module `Processes`

The function procedure `Me` returns the identity of the calling process.

### MyParam - Query current process parameter

    PROCEDURE MyParam (): Parameter;

Module `Processes`

The function procedure `MyParam` returns the value of the parameter denoted by `procParams` at the time the process was created.

### UrgencyOf - Query process urgency

    PROCEDURE UrgencyOf (procId: ProcessId): Urgency;

Module `Processes`

The function procedure `UrgencyOf` returns the urgency of the process identified by `procId`.

NOTE:

This urgency of a process is statically assigned when the process is created; it is not possible for a process to alter its urgency dynamically.

### IsProcessesException - Query exceptional state

    PROCEDURE IsProcessesException (): BOOLEAN;

Module `Processes`

If the calling coroutine is in the state of exceptional execution because of the raising of a `Processes` exception, the function procedure `IsProcessesException` returns `TRUE`; otherwise it retruns `FALSE`.

### ProcessesException - Query exception id

    PROCEDURE ProcessesException (): ProcessesExceptions;

Module `Processes`

If the calling coroutine is in the state of exceptional execution because of the raising of a `Processes` exception, the function procedure `ProcessesException` returns the value that identifies the raised exception; otherwise the language exception `exException` is be raised.

## Module Semaphores

The module `Semaphores` provides facilities for potentially parallel parts of a program (i.e. processes) to exclude one another from regions of interaction by using the semaphore mechanism first proposed by Dijkstra. The semaphores provided by the module are general or counting semaphores (as opposed to binary semaphores).

The hidden type `SEMAPHORE` is used to identify semaphores.

    TYPE
      SEMAPHORE;

Each semaphore have a unique identity. Associated with each semaphore there is a non-negative count, and a set of zero or more processes waiting for it to become free. A semaphore is said to be `free' if its associated count is non-zero.

After the module has been initialized, no semaphores are in existence.

NOTES:

- For convenience, the semantics of this module are illustrated in terms of the semantics of the `Processes` module. However, there is no requirement that an implementation provide `Processes` in addition to providing `Semaphores`.
- The behaviour of the procedures `Destroy`, `Claim`, `Release` and `CondClaim` in situations where the actual parameter passed is not a valid semaphore (i.e. is not the identity of a semaphore allocated by a call to `Create`) is implementation-dependent.

- Create - Create new semaphore
- Destroy - Destroy semaphore
- Claim - Claim semaphore
- Release - Unclaim semaphore
- CondClaim - Claim semaphore safely
- IsSemaphoresException - Query exceptional state

### Create - Create new semaphore

    PROCEDURE Create (VAR s: SEMAPHORE; initialCount: CARDINAL);

Module `Semaphores`

The procedure `Create` creates a new semaphore, if there are sufficient resources to do so, and assigns its identity to `s`; otherwise the `Semaphores` exception is raised. The count associated with the semaphore is initialized to `initialCount`, and there will then be no process waiting for the semaphore to be free.

### Destroy - Destroy semaphore

    PROCEDURE Destroy (VAR s: SEMAPHORE);

Module `Semaphores`

Provided that no process is waiting for the semaphore identified by the value of `s` to become free, the procedure `Destroy` removes that semaphore and recovers the resources used to implement it.

The variable `s` is set to a value that is invalid for semaphore operations.

NOTE:

The behaviour of `Destroy(s)` in situations where there are processes waiting for `s` to become free is implementation-dependent.

### Claim - Claim semaphore

    PROCEDURE Claim (s: SEMAPHORE);

Module `Semaphores`

The procedure `Claim` claims the semaphore identified by `s`. If the count associated with `s` is non-zero, then it is decremented, and the calling process continues execution; otherwise the calling process becomes ineligible to run, and is added to the set waiting for `s` to become free.

### Release - Unclaim semaphore

    PROCEDURE Release (s: SEMAPHORE);

Module `Semaphores`

The procedure `Release` unclaims the semaphore identified by `s`. If no process is waiting on `s`, the count associated with `s` is incremented; otherwise one process is selected from those waiting for `s` to become free; this process is removed from the waiting set, and becomes eligible to run (i.e. enter the ready state).

NOTES:

- No requirement is imposed about which of the waiting processes is chosen for activation.
- Preemption occurs if the newly eligible process has an urgency greater than that of the calling process.

### CondClaim - Claim semaphore safely

    PROCEDURE CondClaim (s: SEMAPHORE): BOOLEAN;

Module `Semaphores`

If the call `Claim(s)` would have caused the calling process to become ineligible to run, the procedure `CondClaim` returns `FALSE`, and the count associated with `s` is unchanged. Otherwise the count associated with `s` is decremented, and the procedure returns `TRUE`.

NOTE:

The calling process is never suspended as a result of calling `CondClaim`.

### IsSemaphoresException - Query exceptional state

    PROCEDURE IsSemaphoresException (): BOOLEAN;

Module `Semaphores`

If the calling coroutine is in the state of exceptional execution because of the raising of the `Semaphores` exception, the procedure `IsSemaphoresException` returns `TRUE`; otherwise it returns `FALSE`.