While monitors can handle both mutual exclusion and synchronization, the mechanisms for supporting these two forms of process coordination have important differences. Mutual exclusion is specified by high-level declarations indicating which procedures are entry procedures and the code for supporting it is generated by the compiler. On the other hand, process synchronization is implemented by low-level code scattered throughout the monitors that is as low-level as the semaphore code. In particular, it is subject to the problem that a wait may not be associated with a matching signal.
Path expressions overcome this problem by allowing coordination constraints to be specified by high-level declarations that are defined in a single-place, provide a unified mechanism for supporting both mutual exclusion and synchronization, and are implemented by complier-generated code. Like monitors, they extend the abstraction of a module - instead of defining entry procedures and conditions, the programmer associates a module with a path expression that defines the coordination constraints of the module.
A path expression is much like a regular expression - the ``alphabet'' consists of operation (procedures) defined by the associated module. The operators are , for concurrency, ; for sequential execution, N: (path_exp) to specify upto N concurrent activations of path_exp, and [path_exp] to specify an unbounded number of concurrent executions of path_exp. Let us illustrate the semantics of path expressions using the bounded buffer example:
{\bf module} BoundedBuffer;
{\bf export} GetBuffer, PutBuffer;
{\bf const}
size = 10;
{\bf type}
Datum = ... /* the data type of the contents of the buffer */
{\bf var}
buffer: {\bf array} 0..size-1 {\bf of} Datum;
nextIn, nextOut: 0..size-1; /* index of next datum to place in buffer or remove
*/
nonEmpty, nonFull: {\bf condition};
{\bf procedure} PutBuffer (what: Datum);
{\bf begin}
buffer [nextIn] <- what;
nextIn <- (nextIn + 1) {\bf mod} size;
{\bf end};
{\bf procedure} GetBuffer({\bf var} result: Datum);
{\bf begin}
result <- buffer[nextOut];
nextOut <- (nextOut + 1) {\bf mod} size;
{\bf end};
{\bf begin} /* initialization code */
nextIn <- 0;
nextOut <- 0;
{\bf end};
This is the same implementation as the one we saw for the monitor case
except that all code specifying coordination constraints has been removed.
An interesting consequence is that the variable
count
shared by
GetBuffer
and
PutBuffer
has disappeared,
allowing these two procedures to execute concurrently.
Let us try some path expressions to specify coordination constraints for this module. The three expressions
PutBuffer, GetBuffer [PutBuffer, GetBuffer] [PutBuffer], [GetBuffer]all specify that an arbitrary number of activations of the two procedures can be executed concurrently. Thus they do not place any constraints on the module. The expression
PutBuffer; GetBufferon the other hand specifies that each activation of GetBuffer be preceded by an execution of PutBuffer but there can be concurrent activations of this serial sequence. Thus, it ensures that the number of completed executions of GetBuffer never exceeds the number of completed executions of completed executions of PutBuffer. It does not, however, prevent multiple executions of GetBuffer or PutBuffer to be active simultaneously. The expression
1 : (PutBuffer; GetBuffer)ensures that there can only be one activation of this sequence at any one time. Thus, it ensures that the two procedures alternate (staring with PutBuffer ) and implements a bounded buffer of size 1.
The expression
N: (1: (PutBuffer); 1 : (GetBuffer))ensures that:
we can have at most one concurrent execution of PutBuffer at any one time;
we can have at most one concurrent execution of GetBuffer at any one time;
each activation of GetBuffer is preceded by an activation of PutBuffer,
the number of completed PutBuffer executions is never more than N greater than the number of completed GetBuffer operations.
Thus, it implements a bounded buffer of size N.
Path expression can also easily specify the multiple readers/ single writer constraint:
1 : ([read], write)This expression indicates that there can be an unbounded number of reads and a single write concurrently active at any time. However, it lets the reader get at potentially inconsistent information. The following constraint
1 :([read]; write)gives the stronger constraint that readers and writers do not simultaneously execute. Here we are assuming that [] means 0 or more and not 1 or more concurrent activations.
While path expressions are high-level,
they cannot specify all kinds of process coordination constraints.
For instance,
there is no way to specify a more fair readers/writers constraint that
ensures that a writer is not starved.
In general,
there is no way for specifying constraints that depend on information
other than the history of operations invoked so far.