1Condition(3) OCaml library Condition(3)
2
6 Condition - Condition variables.
7
9 Module Condition
10
12 Module Condition
13 : sig end
14 Condition variables.
17 Condition variables are useful when several threads wish to access a
19 shared data structure that is protected by a mutex (a mutual exclusion
20 lock).
21 A condition variable is a communication channel. On the receiver side,
23 one or more threads can indicate that they wish to wait for a certain
24 property to become true. On the sender side, a thread can signal that
25 this property has become true, causing one (or more) waiting threads to
26 be woken up.
27 For instance, in the implementation of a queue data structure, if a
29 thread that wishes to extract an element finds that the queue is cur‐
30 rently empty, then this thread waits for the queue to become nonempty.
31 A thread that inserts an element into the queue signals that the queue
32 has become nonempty. A condition variable is used for this purpose.
33 This communication channel conveys the information that the property
34 "the queue is nonempty" is true, or more accurately, may be true. (We
35 explain below why the receiver of a signal cannot be certain that the
36 property holds.)
37 To continue the example of the queue, assuming that the queue has a
39 fixed maximum capacity, then a thread that wishes to insert an element
40 may find that the queue is full. Then, this thread must wait for the
41 queue to become not full, and a thread that extracts an element of the
42 queue signals that the queue has become not full. Another condition
43 variable is used for this purpose.
44 In short, a condition variable c is used to convey the information that
46 a certain property P about a shared data structure D, protected by a
47 mutex m , may be true.
48 Condition variables provide an efficient alternative to busy-waiting.
50 When one wishes to wait for the property P to be true, instead of writ‐
51 ing a busy-waiting loop:
52 Mutex.lock m;
53 while not P do
54 Mutex.unlock m; Mutex.lock m
55 done;
56 <update the data structure>;
57 Mutex.unlock m
58 one uses Condition.wait in the body of the loop, as follows:
60 Mutex.lock m;
61 while not P do
62 Condition.wait c m
63 done;
64 <update the data structure>;
65 Mutex.unlock m
66 The busy-waiting loop is inefficient because the waiting thread con‐
68 sumes processing time and creates contention of the mutex m . Calling
69 Condition.wait allows the waiting thread to be suspended, so it does
70 not consume any computing resources while waiting.
71 With a condition variable c , exactly one mutex m is associated. This
73 association is implicit: the mutex m is not explicitly passed as an ar‐
74 gument to Condition.create . It is up to the programmer to know, for
75 each condition variable c , which is the associated mutex m .
76 With a mutex m , several condition variables can be associated. In the
78 example of the bounded queue, one condition variable is used to indi‐
79 cate that the queue is nonempty, and another condition variable is used
80 to indicate that the queue is not full.
81 With a condition variable c , exactly one logical property P should be
83 associated. Examples of such properties include "the queue is nonempty"
84 and "the queue is not full". It is up to the programmer to keep track,
85 for each condition variable, of the corresponding property P. A signal
86 is sent on the condition variable c as an indication that the property
87 P is true, or may be true. On the receiving end, however, a thread
88 that is woken up cannot assume that P is true; after a call to Condi‐
89 tion.wait terminates, one must explicitly test whether P is true.
90 There are several reasons why this is so. One reason is that, between
91 the moment when the signal is sent and the moment when a waiting thread
92 receives the signal and is scheduled, the property P may be falsified
93 by some other thread that is able to acquire the mutex m and alter the
94 data structure D. Another reason is that spurious wakeups may occur: a
95 waiting thread can be woken up even if no signal was sent.
96 Here is a complete example, where a mutex protects a sequential un‐
98 bounded queue, and where a condition variable is used to signal that
99 the queue is nonempty.
100 type 'a safe_queue =
101 { queue : 'a Queue.t; mutex : Mutex.t; nonempty : Condition.t }
102 let create () =
104 { queue = Queue.create(); mutex = Mutex.create();
105 nonempty = Condition.create() }
106 let add v q =
108 Mutex.lock q.mutex;
109 let was_empty = Queue.is_empty q.queue in
110 Queue.add v q.queue;
111 if was_empty then Condition.broadcast q.nonempty;
112 Mutex.unlock q.mutex
113 let take q =
115 Mutex.lock q.mutex;
116 while Queue.is_empty q.queue do Condition.wait q.nonempty q.mutex done;
117 let v = Queue.take q.queue in (* cannot fail since queue is nonempty *)
118 Mutex.unlock q.mutex;
119 v
120 Because the call to Condition.broadcast takes place inside the critical
122 section, the following property holds whenever the mutex is unlocked:
123 if the queue is nonempty, then no thread is waiting, or, in other
124 words, if some thread is waiting, then the queue must be empty. This
125 is a desirable property: if a thread that attempts to execute a take
126 operation could remain suspended even though the queue is nonempty,
127 that would be a problematic situation, known as a deadlock.
128 type t
134 The type of condition variables.
137 val create : unit -> t
141 create() creates and returns a new condition variable. This condition
144 variable should be associated (in the programmer's mind) with a certain
145 mutex m and with a certain property P of the data structure that is
146 protected by the mutex m .
147 val wait : t -> Mutex.t -> unit
151 The call wait c m is permitted only if m is the mutex associated with
153 the condition variable c , and only if m is currently locked. This
154 call atomically unlocks the mutex m and suspends the current thread on
155 the condition variable c . This thread can later be woken up after the
156 condition variable c has been signaled via Condition.signal or Condi‐
157 tion.broadcast ; however, it can also be woken up for no reason. The
158 mutex m is locked again before wait returns. One cannot assume that the
159 property P associated with the condition variable c holds when wait re‐
160 turns; one must explicitly test whether P holds after calling wait .
161 val signal : t -> unit
165 signal c wakes up one of the threads waiting on the condition variable
168 c , if there is one. If there is none, this call has no effect.
169 It is recommended to call signal c inside a critical section, that is,
171 while the mutex m associated with c is locked.
172 val broadcast : t -> unit
176 broadcast c wakes up all threads waiting on the condition variable c .
179 If there are none, this call has no effect.
180 It is recommended to call broadcast c inside a critical section, that
182 is, while the mutex m associated with c is locked.
183OCamldoc 2023-07-20 Condition(3)