1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
/*
* Copyright (c) 2017 Richard Braun.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*/
#include <stdbool.h>
#include <lib/list.h>
#include "condvar.h"
#include "mutex.h"
#include "thread.h"
/*
* Structure used to bind a waiting thread and a condition variable.
*
* The purpose of this structure is to avoid adding the node to the thread
* structure. Instead, it's allocated from the stack and only exists while
* the thread is waiting for the condition variable to be signalled.
*
* When another thread signals the condition variable, it finds threads
* to wake up by accessing the condition variable list of waiters.
*
* The awaken member records whether the waiting thread has actually been
* awaken, to guard against spurious wake-ups.
*
* Preemption must be disabled when accessing a waiter.
*/
struct condvar_waiter {
struct list node;
struct thread *thread;
bool awaken;
};
static void
condvar_waiter_init(struct condvar_waiter *waiter, struct thread *thread)
{
waiter->thread = thread;
waiter->awaken = false;
}
static bool
condvar_waiter_awaken(const struct condvar_waiter *waiter)
{
return waiter->awaken;
}
static bool
condvar_waiter_wakeup(struct condvar_waiter *waiter)
{
if (condvar_waiter_awaken(waiter)) {
return false;
}
thread_wakeup(waiter->thread);
waiter->awaken = true;
return true;
}
void
condvar_init(struct condvar *condvar)
{
list_init(&condvar->waiters);
}
void
condvar_signal(struct condvar *condvar)
{
struct condvar_waiter *waiter;
bool awaken;
thread_preempt_disable();
list_for_each_entry(&condvar->waiters, waiter, node) {
awaken = condvar_waiter_wakeup(waiter);
if (awaken) {
break;
}
}
thread_preempt_enable();
}
void
condvar_broadcast(struct condvar *condvar)
{
struct condvar_waiter *waiter;
/*
* Note that this broadcast implementation, a very simple and naive one,
* allows a situation known as the "thundering herd problem" [1].
*
* Remember that a condition variable is always associated with a mutex
* when waiting on it. This means that, when broadcasting a condition
* variable on which many threads are waiting, they will all be awaken,
* but only one of them acquires the associated mutex. All the others
* will sleep, waiting for the mutex to be unlocked. This unnecessary
* round of wake-ups closely followed by sleeps may be very expensive
* compared to the cost of the critical sections around the wait, and
* that cost increases linearly with the number of waiting threads.
*
* Smarter but more complicated implementations can avoid this problem,
* e.g. by directly queuing the current waiters on the associated mutex.
*
* [1] https://en.wikipedia.org/wiki/Thundering_herd_problem
*/
thread_preempt_disable();
list_for_each_entry(&condvar->waiters, waiter, node) {
condvar_waiter_wakeup(waiter);
}
thread_preempt_enable();
}
void
condvar_wait(struct condvar *condvar, struct mutex *mutex)
{
struct condvar_waiter waiter;
struct thread *thread;
thread = thread_self();
condvar_waiter_init(&waiter, thread);
thread_preempt_disable();
/*
* Unlocking the mutex associated with the condition variable after
* acquiring the condition variable (done here by disabling preemption)
* is what makes waiting "atomic". Note that atomicity isn't absolute.
* Here, the wait is atomic with respect to concurrent signals.
*
* Signalling a condition variable is always safe in the sense that
* it is permitted and won't make the system crash, but signals may be
* "missed" if the associated mutex isn't locked when signalling.
*/
mutex_unlock(mutex);
list_insert_tail(&condvar->waiters, &waiter.node);
do {
thread_sleep();
} while (!condvar_waiter_awaken(&waiter));
list_remove(&waiter.node);
thread_preempt_enable();
/*
* Unlike releasing the mutex earlier, relocking the mutex may be
* done before or after releasing the condition variable. In this
* case, it may not be done before because acquiring the condition
* variable is achieved by disabling preemption, which forbids
* sleeping, and therefore locking a mutex, but another implementation
* may use a different synchronization mechanism.
*
* It's also slightly better to relock outside the previous critical
* section in order to make it shorter.
*/
mutex_lock(mutex);
}
|
