Monitors

Provided by Programming Languages such as Concurrent Pascal, Modula, Modula-2, Mesa, and Java.

Like a Module: Declares data (access to which is to be mutually excluded), procedures that manipulate these data, and an initialization code. The procedures can be exported to other modules which may import them.

Unlike a Module in following respect: Can declare certain procedures as entry procedures, which have the property that no matter how many processes are running, only one process is allowed to execute an entry procedure at a time. Thus if a monitor declares two entry procedures e1 and e2, then while e1 is being executed by a process, another process cannot call e1 or e2. A process that invokes an entry procure while the monitor is `busy' (that is some other process is executing an entry procedure in it) is put on an entry queue.

List Problem

The following program shows the use of monitors to implement the `list' problem, explained earlier, involving two processes that add items to a list;

monitor List;

export AddChar;

var
    /* shared data */
    n: integer;
    a: array 0..1 of char;

/* an entry procedure */
entry procedure AddChar [item: char];
begin
    a[n++] <- item;
end; 

/* initialization code */
begin
    n <- 0;
end;

Monitors provide a `higher-level' solution to the mutual exclusion problem than semaphores:

We need not worry that some other piece of code accesses the shared data and thus must be made a critical region.

It is possible to determine the criticial regions by looking only at the headers of the monitor procedures.

A process does not have to remember the final signal operation.

Bounded Buffer Problem

Monitors, as described so far, provide a solution to the mutual exclusion problem, but not the synchronization problem. To accommodate a solution to the latter, they are associated with conditions associated with the wait and signal operations. A call to wait places the process that calls it in a condition queue associated with the signal. It is removed from this queue when some other process does a signal on the condition. Before calling wait, a process must restore the invariant of the monitor as the the call frees the monitor for other processes to enter.

Thus, a signal is like a semaphore in that it is associated with a queue in which processes may wait for signals. The difference is that it is a more lightweight mechanism not associated with a count variable. Any state associated with a condition must be explicitly managed by the monitor programmer. (Does it make sense to support conditions as an alternative to semaphores in a world without monitors?)

We can use a monitor or to implement the bounded buffer problem stated as follows:
Any number of producer and consumer processes are running. A producer puts data in a buffer whose size is finite (hence a bounded buffer). A consumer removes data from this buffer. A producer blocks when the buffer is full and a consumer blocks when the buffer is empty.

The following is a monitor solution to this problem:

monitor BoundedBuffer;

export GetBuffer, PutBuffer;

const
    size = 10;
type
    Datum = ... /* the data type of the contents of the buffer */
var
    buffer: array 0..size-1 of Datum;
    count: 0..size; /* number of elements in buffer */
    nextIn, nextOut: 0..size-1; /* index of next datum to place in buffer or remove
*/
    nonEmpty, nonFull: condition;

entry procedure PutBuffer (what: Datum);
begin
    if count = size then 
        wait nonFull;
    end;
    buffer [nextIn] <- what;
    nextIn <- (nextIn + 1) mod size;
    count <- count + 1;
    signal nonEmpty
end;

entry procedure GetBuffer(var result: Datum);
begin
    if count = 0 then
        wait nonEmpty
    end;
    result <- buffer[nextOut];
    nextOut <- (nextOut + 1) mod size;
    count <- count -1;
    signal nonFull;
end;

begin /* initialization code */
    count <- 0;
    nextIn <- 0;
    nextOut <- 0;
end}

A producer waits on the signal nonFull before adding new data, and signals nonEmpty when it successfully adds data. Conversely, a consumer waits on nonEmpty before consuming new data, and signals nonFull when it successfully adds new data.

Assume that a consumer is waiting on a condition, and a producer does a signal. When is the consumer allowed to execute? If immediately, then we may have two processes in the monitor at the same time, and our careful mutual exclusion is ruined. If later, then some other process may have taken the last datum, and the assumption made by the first consumer that an execution of the wait nonEmpty statement guarantees a non-empty buffer is wrong.

Not all definitions of monitors in the literature agree on the answers to these questions. The following is a common approach. We associate a monitor with an urgent queue. Thus a monitor is associated with an entry queue, a condition queue for each condition, and an urgent queue. Processes that are blocked are placed in these queues. Here are the rules that govern the placement and removal of processes from these queues:

New processes wait in the entry queue.

When a process exits a monitor (that is, finishes execution of an entry procedure), a process from the urgent queue is allowed to execute if the queue is not empty. Otherwise, a process from the entry queue is removed if the queue is not empty.

A process that does a wait enters the appropriate condition queue.

When a process executes signal, the signalled condition queue is inspected. If some process is waiting on the queue, the signaller enters the urgent queue and some waiting process is allowed to execute. If no process is waiting in that queue, then the signaller proceeds without leaving the monitor. The signal is ignored.

All queues are ordered first in, first out.

These rules ensure that a waiting consumer is unblocked immediately when a producer signals NonEmpty, and the producer is blocked in the urgent queue until the consumer has taken the datum. We have maintained the rule that at most one process occupies the monitor.

People who use monitors have noticed that the signal operation is almost always the last operation in an entry procedure. The above rules will often make the signaller wait in the urgent queue and then return to the monitor just to get out of it. Thus these rules, while they work, are often inefficient. Thus some people require that signal must be the last operation executed in an entry procedure.

Another alternative is to make the signal operation a hint to a waiting process; it causes execution of some process waiting on the condition to resume at some convenient future time. There is no guarantee that some other process will not enter the monitor before the waiting process. Under these semantics, the waiting process has to reestablish the condition for which it was waiting still holds when it wakes up. The proper pattern for usage is:

while not <ok to proceed> do
    wait c

if not <ok to proceed> then
    wait c

if count = 0 then
    wait nonEmpty

while count = 0  do
    wait nonEmpty

The last alternative results in an extra evaluation of the <ok to proceed> predicate after the wait. In return there are fewer process switches compared to the first alternative, and it is more flexible than the second alternative. Moreover, it allows dequeueing of all processes waiting on a signal. (why?). Thus a special operation broadcast can be defined on signals.

The queues maintained under the hint semantics are the same as above except that it is the signalled process that goes into the urgent queue rather than the signalling process.

In the Mesa solution, a separate module must be defined for each bounded buffer. Java overcomes this problem by allowing a single class to be defined for all instances of a synchronized resource.

In Java, a class may declare certain methods to be declared as entry procedures (by using the keyword synchronized ). Each instance of a class with entry procedures behaves as a monitor. Java implements a simplified version of these hint-based monitor semantics. A Java object, is associated with a single condition variable and queue. It supports both signal (called notify ) and broadcast (called notifyAll ) operations. In either case, the notification is a hint, and the notified process is supposed to check for itself if its condition has been satisfied. (How would you implement the bounded buffer problem with these semantics?) To address deadlocks, Java also supports wait operations with timeouts.

Why did we not have analogous semantic problems with the semaphore signal operation?

Yet another issue in monitors is nested monitor calls - what if an entry procedure in one monitor calls an entry procedure in another monitor? If the first monitor remains occupied as the process enters the entry queue of the second monitor, deadlocks can occur. Therefore some designs require that the first monitor be freed for other processs to enter, but this approach requires the process to restore the invariant of the first monitor before entering the second monitor.