The immediate resumption requirement

The definition of signalC(cond) requires that it unblock the first process blocked on the queue for cond. When this occurs, the signaling process (say p) can now continue to execute the next statement after signalC(cond), while the unblocked process (say q) can execute the next statement after the waitC(cond) that caused it to block. But this is not a valid state, since the specification of a monitor requires that at most one process at a time can be executing statements of a monitor operation. Either p or q will have to be blocked until the other completes its monitor operation. That is, we have to specify if signaling processes are given precedence over waiting processes, or vice versa, or perhaps the selection of the next process is arbitrary. There may also be processes blocked on the entry to the monitor, and the specification of precedence has to take them into account.

Note that the terminology is rather confusing, because the waiting processes are processes that have just been released from being blocked, rather than processes that are waiting because they are blocked.

The following diagram shows the states that processes can be in: waiting to enter the monitor, executing within the monitor (but only one), blocked on condition queues, on a queue of processes just released from waiting on a condition, and on a queue of processes that have just completed a signal operation:

Let us denote the precedence of the signaling processes by S, that of the waiting processes by W and that of the processes blocked on the entry by E. There are thirteen different ways of assigning precedence, but many of them make no sense. For example, it does not make sense to have E greater than either W or S', because that would quickly cause starvation as new processes enter the monitor before earlier ones have left. The classical monitor specifies that \(E < S < W\) and later we will discuss the specification E = W < S that is implemented in Java. See [15] for an analysis of monitor definitions.

The specification \(E < S < W\) is called the immediate resumption requirement (IRR), or signal and urgent wait. It means that when a process blocked on a condition variable is signaled, it immediately begins executing ahead of the signaling process. It is easy to see the rationale behind IRR. Presumably, the signaling process has changed the state of the monitor (modified its variables) so that the condition now holds; if the waiting process resumes immediately, it can assume the condition does hold and continue with the statements in its operation. For example, look again at the monitor that simulates a semaphore (Algorithm 7.2). The Sem.signal operation increments s just before executing the signalC(notZero) statement; if the Sem.wait operation resumes immediately, it will find s to be nonzero, the condition it was waiting for.

Similarly, in Algorithm 7.3, the monitor solution for the producer-consumer problem, append(v, Buffer) immediately precedes signalC(notEmpty), ensuring that the buffer is not empty when a consumer process is unblocked, and the statement w < head(Buffer) immediately precedes signalC(notFull), ensuring that the buffer is not full when a producer process is unblocked. With immediate resumption there is no need to recheck the status of the buffer.

Without the IRR, it would be possible for the signaling process to continue its execution, causing the condition to again become false. Waiting processes would have to recheck the boolean expression for the condition in a while loop:

The disadvantage of the IRR is that the signaling process might be unnecessarily delayed, resulting in less concurrency than would otherwise be possible. However, if—as in our examples—signalC(cond) is the last statement in a monitor operation, there is no need to block the execution of the process that invoked the operation.