Monitor (synchronization) - Waiting and Signaling

Waiting and Signaling

For many applications, mutual exclusion is not enough. Threads attempting an operation may need to wait until some condition holds true. A busy waiting loop

while not( ) do skip

will not work, as mutual exclusion will prevent any other thread from entering the monitor to make the condition true.

The solution is condition variables. Conceptually a condition variable is a queue of threads, associated with a monitor, on which a thread may wait for some condition to become true. Thus each condition variable is associated with an assertion . While a thread is waiting on a condition variable, that thread is not considered to occupy the monitor, and so other threads may enter the monitor to change the monitor's state. In most types of monitors, these other threads may signal the condition variable to indicate that assertion is true in the current state.

Thus there are two main operations on condition variables:

• wait c is called by a thread that needs to wait until the assertion is true before proceeding. While the thread is waiting, it does not occupy the monitor.
• signal c (sometimes written as notify c) is called by a thread to indicate that the assertion is true.

As an example, consider a monitor that implements a semaphore. There are methods to increment (V) and to decrement (P) a private integer s. However, the integer must never be decremented below 0; thus a thread that tries to decrement must wait until the integer is positive. We use a condition variable sIsPositive with an associated assertion of .

monitor class Semaphore { private int s := 0 invariant s >= 0 private Condition sIsPositive /* associated with s > 0 */ public method P { if s = 0 then wait sIsPositive assert s > 0 s := s - 1 } public method V { s := s + 1 assert s > 0 signal sIsPositive } }

When a signal happens on a condition variable that at least one other thread is waiting on, there are at least two threads that could then occupy the monitor: the thread that signals and any one of the threads that is waiting. In order that at most one thread occupies the monitor at each time, a choice must be made. Two schools of thought exist on how best to resolve this choice. This leads to two kinds of condition variables which will be examined next:

• Blocking condition variables give priority to a signaled thread.
• Nonblocking condition variables give priority to the signaling thread.