Module Condition

Condition variables.

Condition variables are useful when several threads wish to access a shared data structure that is protected by a mutex (a mutual exclusion lock).

A condition variable is a communication channel. On the receiver side, one or more threads can indicate that they wish to wait for a certain property to become true. On the sender side, a thread can signal that this property has become true, causing one (or more) waiting threads to be woken up.

For instance, in the implementation of a queue data structure, if a thread that wishes to extract an element finds that the queue is currently empty, then this thread waits for the queue to become nonempty. A thread that inserts an element into the queue signals that the queue has become nonempty. A condition variable is used for this purpose. This communication channel conveys the information that the property "the queue is nonempty" is true, or more accurately, may be true. (We explain below why the receiver of a signal cannot be certain that the property holds.)

To continue the example of the queue, assuming that the queue has a fixed maximum capacity, then a thread that wishes to insert an element may find that the queue is full. Then, this thread must wait for the queue to become not full, and a thread that extracts an element of the queue signals that the queue has become not full. Another condition variable is used for this purpose.

In short, a condition variable c is used to convey the information that a certain property P about a shared data structure D, protected by a mutex m, may be true.

Condition variables provide an efficient alternative to busy-waiting. When one wishes to wait for the property P to be true, instead of writing a busy-waiting loop:

     Mutex.lock m;
     while not P do
       Mutex.unlock m; Mutex.lock m
     done;
     <update the data structure>;
     Mutex.unlock m
   

one uses Condition.wait in the body of the loop, as follows:

     Mutex.lock m;
     while not P do
       Condition.wait c m
     done;
     <update the data structure>;
     Mutex.unlock m
   

The busy-waiting loop is inefficient because the waiting thread consumes processing time and creates contention of the mutex m. Calling Condition.wait allows the waiting thread to be suspended, so it does not consume any computing resources while waiting.

With a condition variable c, exactly one mutex m is associated. This association is implicit: the mutex m is not explicitly passed as an argument to Condition.create. It is up to the programmer to know, for each condition variable c, which is the associated mutex m.

With a mutex m, several condition variables can be associated. In the example of the bounded queue, one condition variable is used to indicate that the queue is nonempty, and another condition variable is used to indicate that the queue is not full.

With a condition variable c, exactly one logical property P should be associated. Examples of such properties include "the queue is nonempty" and "the queue is not full". It is up to the programmer to keep track, for each condition variable, of the corresponding property P. A signal is sent on the condition variable c as an indication that the property P is true, or may be true. On the receiving end, however, a thread that is woken up cannot assume that P is true; after a call to Condition.wait terminates, one must explicitly test whether P is true. There are several reasons why this is so. One reason is that, between the moment when the signal is sent and the moment when a waiting thread receives the signal and is scheduled, the property P may be falsified by some other thread that is able to acquire the mutex m and alter the data structure D. Another reason is that spurious wakeups may occur: a waiting thread can be woken up even if no signal was sent.

Here is a complete example, where a mutex protects a sequential unbounded queue, and where a condition variable is used to signal that the queue is nonempty.

     type 'a safe_queue =
       { queue : 'a Queue.t; mutex : Mutex.t; nonempty : Condition.t }

     let create () =
       { queue = Queue.create(); mutex = Mutex.create();
         nonempty = Condition.create() }

     let add v q =
       Mutex.lock q.mutex;
       let was_empty = Queue.is_empty q.queue in
       Queue.add v q.queue;
       if was_empty then Condition.broadcast q.nonempty;
       Mutex.unlock q.mutex

     let take q =
       Mutex.lock q.mutex;
       while Queue.is_empty q.queue do Condition.wait q.nonempty q.mutex done;
       let v = Queue.take q.queue in (* cannot fail since queue is nonempty *)
       Mutex.unlock q.mutex;
       v
   

Because the call to Condition.broadcast takes place inside the critical section, the following property holds whenever the mutex is unlocked: if the queue is nonempty, then no thread is waiting, or, in other words, if some thread is waiting, then the queue must be empty. This is a desirable property: if a thread that attempts to execute a take operation could remain suspended even though the queue is nonempty, that would be a problematic situation, known as a deadlock.