Text preview for : Mesa_4.0_Process_Update_May78.pdf part of xerox Mesa 4.0 Process Update May78 xerox mesa 4.0_1978 Mesa_4_Documentation Mesa_4.0_Process_Update_May78.pdf
Back to : Mesa_4.0_Process_Update_M | Home
Inter-Office Memorandum
To Mesa Users Date May 31, 1978
From Dave Redell, Dick Sweet Location Palo Alto
Subject Mesa 4.0 Process Update Organization SO~/SO
XEROX
Filed on: [IRIS]
Mesa provides language support for concurrent execution of mUltiple processes. This allows
programs that are inherently parallel in nature to be clearly expressed. The language also
provides facilities for synchronizing such processes by means of entry to monitors and
waiting on condition variables.
The next section discusses the forking and joining of concurrent process. Later sections deal
with monitors, how their locks are specified, and how they are entered and exited. Condition
variables are discussed, along with their associated operations.
10.1. Concurent execution, FORK and JOIN.
The FORK and JOIN statements allow parallel execution of two procedures. Their use also
requires the new data type PROCESS. Since the Mesa process facilities provide considerable
flexibility, it is easiest to understand them by first looking at a simple example.
10.1.1. A Process Example
Consider an application with a front-end routine providing interactive composition and
editing of input lines:
ReadLine: PROCEDURE [s: STRING] RETURNS [CARDINAL] =
BEGIN
c: CHARACTER;
s.length +- 0;
DO
c +- ReadChar[];
IF ControICharaCler[c] THEN DoAclion[c]
ELSE AppendChar[s,c];
IF c = CR THEN RETURN [s.length];
END LOOP;
END;
The call
n +- ReadLine[buffer];
will collect a line of user type-in up to a CR and put it in some string named buffer. Of
fVlesa 4.0 Process Update 2
course, the caller cannot get anything else accomplished during the type-in of the line. If
there is anything else that needs doing, it can be done concurrently with the type-in by
forking to ReadLine instead of calling it:
P .. FORK ReadLine[buffer];
n .. JOIN p;
This allows the statements labeled user typing (clearly, the concurrent computation should not reference the string buffer).
The FORK construct spawns a new process whose result type matches that of ReadLine.
(ReadLine is referred to as the "root procedure" of the new process.)
p: PROCESS RETURNS [CARDINAL];
Later, the results are retrieved by the JOIN statement, which also deletes the spawned process.
Obviously, this must not occur until both processes are ready (Le. have reached the JOIN and
the RETURN, respectively); this rendevous is synchronized automatically by the process
facility.
Note that the types of the arguments and results of ReadLine are always checked at compile
time, whether it is called or forked.
The one major difference between calling a procedure and forking to it is in the handling of
signals; see section 10.5.1 for details.
10.1.2. Process Language Constructs
The declaration of a PROCESS is similar to the declaration of a PROCEDURE, except that only
the return record is specified. The syntax is formally specified as follows:
TypeConstructor .. -... I ProcessTC
ProcessTC ::= PROCESS ReturnsClause
ReturnsClause .. - empty I RETURNS ResultList -- from sec. 5.1.
ResultList .. - FieldList -- from sec. 5.1.
Suppose that f is a procedure and p a process. In order to fork f and assign the resulting
process to p, the ReturnClause of f and that of p must be compatible, as described in sec 5.2.
The syntax for the FORK and JOIN statements is straightforward:
Statement .. - ... I JoinCall
Expression ::= ... I ForkCall I JoinCall
ForkCall .. - FORKCall
JoinCall ::= JOIN Call
Call .. - (see sections 5.4 and 8.2.1)
The ForkCall always returns a value (of type PROCESS) and thus a FORK cannot stand alone as
a statement. Unlike a procedure call, which returns a RECORD, the value of the FORK cannot
be discarded by writing an empty extractor. The action specified by the FORK is to spawn a
Mesa 4.0 Process Update 3
process parallel to the current one, and to begin it executing the named procedure.
The JoinCali appears as either a statement or an expression, depending upon whether or not
the process being joined has an empty ReturnsClause. It has the following meaning: When
the forked procedure has executed a RETURN and the JOIN is executed (in either order),
the returning process is deleted, and
the joining process receives the results, and continues execution.
A catchphrase can be attached to either a FORK or JOIN by specifying it in the Call. Note,
nowever, that such a catchphrase does not catch signals incurred during the execution of the
procedure; see section 10.5.1 for further details.
There are several other important similarities with normal procedure calls which are worth
noting: .
The types of all arguments and results are checked at compile time.
There is no intrinsic rule against multiple activations (calls and/or forks) of the
same procedure coexisting at once. Of course, it is always possible to write
procedures which will work incorrectly if used in this way, but the mechanism itself
does not prohibit such use.
One expected pattern of usage of the above mechanism is to place a matching FORK/JOIN pair
at the beginning and end of a single textual unit (Le. procedure, compound statement, etc.) so
that the computation within the textual unit occurs in parallel with that of the spawned
process. This style is encouraged, but is not mandatory; in fact, the matching FORK and JOIN
need not even be done by the same process. Care must be taken, of course, to insure that
each spawned process is joined only once, since the result of joining an already deleted
process is undefined. Note that the spawned process always begins and ends its life in the
same textual unit (Le. the target procedure of the FORK).
While many processes will tend to follow the FORK/JOIN paradigm, there will be others whose
role is better cast as continuing provision of services, rather than one-time calculation of
results. Such a "detached" process is never joined. If its lifetime is bounded at all, its
deletion is a private matter, since it involves neither synchronization nor delivery of results.
No language features are required for this operation; see the runtime documentation for the
description of the system procedure provided for detaching a process.
10.2. Monitors
Generally, when two or more processes are cooperating, they need to interact in more
complicated ways than simply forking and joining. Some more general mechanism is needed
to allow orderly, synchronized interaction among processes. The interprocess synchronization
mechanism provided in Mesa is a variant of monitors adapted from the work of Hoare,
Brinch Hansen, and Dijkstra. The underlying view is that interaction among processes always
reduces to carefully synchronized access to shared data, and that a proper vehicle for this
interaction is one which unifies:
- the synchronization
- the shared data
- the body of code which performs the accesses
Mesa 4.0 Process Update 4
The Mesa monitor facility allows considerable flexibility in its use. Before getting into the
details, let us first look at a slightly over-simplified description of the mechanism and a
simple example. The remainder of this section deals with the basics of monitors (more
complex uses are described in section lOA); WAIT and NOTIFY are described in section 10.3.
10.2.1. An overview of Monitors
A monitor is a module instance. It thus has its own data in its global frame, and its own
procedures for accessing that data. Some of the procedures are public, allowing calls into the
monitor from outside. Obviously, conflicts could arise if two processes were executing in the
same monitor at the same time. To prevent this, a monitor lock is used for mutual exclusion
(i.e. to insure that only one process may be in each monitor at anyone time). A call into a
monitor (to an entry procedure) implicitly acquires its lock (waiting if necessary), and
returning from the monitor releases it. The monitor lock serves to guarantee the integrity of
the global data, which is expressed as the monitor invariant -- i.e an assertion defining what
constitutes a "good state" of the data for that particular monitor. It is the responsibility of
every entry procedure to restore the monitor invariant before returning, for the benefit of
the next process entering the monitor.
Tpings are complicated slightly by the possibility that one process may enter the monitor and
find that the monitor data, while in a good state, nevertheless indicates that that process
cannot continue until some other process enters the monitor and improves the situation. The
WAIT operation allows the first process to release the monitor lock and await the desired
condition. The WAIT is performed on a condition variable, which is associated by agreement
with the actual condition needed. When another process makes that condition true, it will
perform a NOTIFY on the condition variable, and the waiting process will continue from
where it left off (after reacquiring the lock, of course.)
For example, consider a fixed block storage allocator providing two entry procedures:
Allocate and Free. A caller of Allocate may find the free storage exhausted and be obliged
to wait until some caller of Free returns a block of storage.
StorageAllocator: MONITOR =
BEGIN
StorageAvail abl e: CONDITION;
FreeList: POINTER;
Allocate: ENTRY PROCEDURE RETURNS [p: POINTER] =
BEGIN
WHILE FreeList =
NIL DO
WAIT StorageAvail abl e
END LOOP;
p ... FreeList; FreeList ... p.next;
END;
Free: ENTRY PROCEDURE [p: POINTER] =
BEGIN
p.next ... FreeList; FreeList ... p;
NOTIFY StorageAvailable
END;
END.
~esa 4.0 Process Update 5
Note that it is clearly undesirable for two asynchonous processes to be executing in the
StorageAllocator at the same time. The use of entry procedures for Allocate and Free
assures mutual exclusion. The monitor lock is released while wAITing in All ocate in order to
allow Free to be called (this also allows other processes to call Allocate as well, leading to
several processes waiting on the queue for StorageAvaiiable).
10.2.2. Monitor Locks
The most basic component of a monitor is its monitor lock. A monitor lock is a predefined
type, which can be thought of as a small record:
MONITORLOCK: TYPE = PRIVATE RECORD [locked: BOOLEAN, queue: Queue];
The monitor lock is private; its fields are never accessed explicitly by the Mesa programmer.
Instead, it is used implicitly to synchronize entry into the monitor code, thereby authorizing
access to the monitor data (and in some cases, other resources, such as I/O devices, etc.) The
next section describes several kinds of monitors which can be constructed from this basic
mechanism. In all of these. the idea is the same: during entry to a monitor, it is necessary to
acquire the monitor lock by:
1. waiting (in the queue) until: locked = FALSE,
2. setting: locked'" TRUE.
10.2.3. Declaring monitor modules, ENTRY and INTERNAL procedures
In addition to a collection of data and an associated lock, a monitor contains a set of
procedure that do operations on the data. Monitor modules are declared much like program
or definitions modules; for example:
M: MONITOR [arguments] =
BEGIN
END.
The procedures in a monitor module are of three kinds:
Entry procedures
Internal procedures
External procedures
Every monitor has one or more entry procedures; these acquire the monitor lock when called,
and are declared as:
P: ENTRY PROCEDURE [arguments] = ...
The entry procedures will usually comprise the set of public procedures visible to clients of
the monitor module. (There are some situations in which this is not the case; see external
procedures, below). The usual Mesa default rules for PUBLIC and PRIVATE procedures apply.
Many monitors will also have internal procedures: common routines shared among the
Mesa 4.0 Process Update 6
several entry procedures. These execute with the monitor lock held, and may thus freely
access the monitor data (including condition variables) as necessary. Internal procedures
should be private, since direct calls to them from outside the monitor would bypass the
acquisition of the lock (for monitors implemented as multiple modules, this is not quite
right; see section 10.4, below). internal procedures can be called only from an entry
procedure or another internal procedure. They are declared as follows:
Q: INTERNAL PROCEDURE [arguments] = .