Condition variables

A monitor implicitly enforces mutual exclusion to its variables, but many problems in concurrent programming have explicit synchronization requirements. For example, in the solution of the producer-consumer problem with a bounded buffer (Section 6.7), the producer must be blocked if the buffer is full and the consumer must be blocked if the buffer is empty. There are two approaches to providing synchronization in monitors. In one approach, the required condition is named by an explicit condition variable (sometimes called an event). Ordinary boolean expressions are used to test the condition, blocking on the condition variable if necessary; a Separate statement is used to unblock a process when the condition becomes true. The alternate approach is to block directly on the expression and let the implementation implicitly unblock a process when the expression is true. The classical monitor uses the first approach, while the second approach is used by protected objects (Section 7.10). Condition variables are one of the synchronization constructs in pthreads, although they are not part of an encapsulating structure like monitors.

Simulating semaphores

Let us see how condition variables work by simulating a solution to the critical section problem using semaphores:

We refrain from giving line numbers for the statements in the monitor because each operation is executed as a single atomic operation.

The monitor implementation follows directly from the definition of semaphores. The integer component of the semaphore is stored in the variable s and the condition variable cond implements the queue of blocked processes. By convention, condition variables are named with the condition you want to be true. waitC(notZero) is read as wait for notZero to be true, and signalC(notZero) is read as signal that notZero is true. The names waitC and signalC are intended to reduce the possibility of confusion with the similarly-named semaphore statements.

If the value of s is zero, the process executing Sem.wait—the simulated semaphore operation—executes the monitor statement waitC(notZero). The process is said to be blocked on the condition:

A process executing waitC blocks unconditionally, because we assume that the condition has been tested for in a preceding if statement; since the entire monitor operation is atomic, the value of the condition cannot change between testing its value and executing waitC. When a process executes a Sem.signal operation, it unblocks the first process (if any) blocked on that condition.

Operations on condition variables

With each condition variable is associated a FIFO queue of blocked processes. Here is the definition of the execution of the atomic operations on condition variables by an arbitrary process p:

Process p is blocked on the queue cond. Process p leaves the monitor, releasing the lock that ensures mutual exclusion in accessing the monitor.

If the queue cond is nonempty, the process at the head of the queue is unblocked. There is also an operation that checks if the queue is empty:

Since the state of the process executing the monitor operation waitC becomes blocked, it is clear that it must release the lock to enable another process to enter the monitor (and eventually signal the condition). In the case of the signalC operation, the unblocked process becomes ready and there is no obvious requirement for the signaling operation to leave the monitor (see Section 7.5).

The following table summarizes the differences between the monitor operations and the similarly-named semaphore operations:

Correctness of the semaphore simulation

When constructing a state diagram for a program with monitors, all the statements of a monitor operation can be considered to be a single step because they are executed under mutual exclusion and no interleaving is possible between the statements. In Algorithm 7.2, each state has four components: the control pointers of the two processes p and q, the value of the monitor variable s and the queue associated with the condition variable notZero. Here is the state diagram assuming that the value of s has been initialized to 1:

Consider, first, the transition from the state (p2: Sem.signal, ql: Sem.wait, 0, <>) at the top center of the diagram to the state (p2: Sem.signal, blocked, 0, < q >) at the upper right. Process q executes the Sem.wait operation, finds that the value of s is 0 and executes the waitC operation; it is then blocked on the queue for the condition variable notZero.

Consider, now, the transition from (p2: Sem.signal, blocked, 0, < g >) to the state (p1: Sem.wait, q2: Sem.signal, 0, <>) at the lower left of the diagram. Process p executes the Sem.signal operation, incrementing s, and then signalC will unblock process q. As we shall discuss in Section 7.5, process q immediately resumes the execution of its Sem.wait operation, so this can be considered as part of the same atomic statement. q will decrement s back to zero and exit the monitor. Since signalC(nonZero) is the last statement of the Sem.signal operation executed by process p, we may also consider that that process exits the monitor as part of the atomic statement. We end up in a state where process q is in its critical section, denoted in the abbreviated algorithm by the control pointer indicating the next invocation of Sem.signal, while process p is outside its critical section, with its control pointer indicating the next invocation of Sem.wait.

There is no state of the form (p2: Sem.signal, q2: Sem.signal, ..., ...) in the diagram, so the mutual exclusion requirement is satisfied.

The state diagram for a monitor can be relatively simple, because the internal transitions of the monitor statements can be grouped into a single transition.