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;

{\bf monitor} List;

{\bf export} AddChar;

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

/* an entry procedure */
{\bf entry procedure} AddChar [item: char];
{\bf begin}
    a[n++] $<$- item;
{\bf end}; 

/* initialization code */
{\bf begin}
    n $<$- 0;
{\bf end};

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

We need not worry that some other piece of code implements the shared data,

Thus shared data can be manipulated only by invoking the procedures exported by the monitor. The monitor ensures that only one entry procedure accesses data at a time.

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 in a condition queue associated with the signal. It is removed from this queue when some other process does a signal on the condition. 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.

We can use a monitor or to implement the bounded buffer problem (also called the producer-consumer 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:

{\bf monitor} 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;
    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: {\bf condition};

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

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

{\bf begin} /* initialization code */
    count $<$- 0;
    nextIn $<$- 0;
    nextOut $<$- 0;
{\bf 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:

{\bf while not} $<$ok to proceed$>$ {\bf do}
    {\bf wait} c

{\bf if not} $<$ok to proceed$>$ {\bf then}
    {\bf wait} c

{\bf if} count = 0 {\bf then}
    {\bf wait} nonEmpty

{\bf while} count = 0 {\bf do}
    {\bf 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.

Java implements a simplified version of these hint-based monitor semantics. 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. A monitor, however, is associated with a single condition variable and queue, in which both signalled and new processes are placed. Java supports both signal (called notify ) and broadcast (called notifyAll ) operations.

in either case, 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 notify operations with timeouts.