7.5 Sleep and wakeup
Scheduling and locks help conceal the actions of one thread
from another,
but we also need abstractions that help
threads intentionally interact.
For example, the reader of a pipe in xv6 may need to wait
for a writing process to produce data;
a parent’s call to wait may need to
wait for a child to exit; and
a process reading the disk needs to wait
for the disk hardware to finish the read.
The xv6 kernel uses a mechanism called sleep and wakeup
in these situations (and many others).
Sleep allows a kernel thread to
wait for a specific event; another thread can call wakeup
to indicate that threads waiting for a specified event should resume.
Sleep and wakeup are often called
sequence coordination
or
conditional synchronization
mechanisms.
Sleep and wakeup provide a relatively low-level synchronization interface. To motivate the way they work in xv6, we’ll use them to build a higher-level synchronization mechanism called a semaphore [2] that coordinates producers and consumers (xv6 does not use semaphores). A semaphore maintains a count and provides two operations. The “V” operation (for the producer) increments the count. The “P” operation (for the consumer) waits until the count is non-zero, and then decrements it and returns. If there were only one producer thread and one consumer thread, and they executed on different CPUs, and the compiler didn’t optimize too aggressively, this implementation would be correct:
100 struct semaphore {101 struct spinlock lock;102 int count;103 };104105 void106 V(struct semaphore *s)107 {108 acquire(&s->lock);109 s->count += 1;110 release(&s->lock);111 }112113 void114 P(struct semaphore *s)115 {116 while(s->count == 0)117 ;118 acquire(&s->lock);119 s->count -= 1;120 release(&s->lock);121 }
The implementation above
is expensive. If the producer acts
rarely, the consumer will spend most
of its time spinning in the
while
loop hoping for a non-zero count.
The consumer’s CPU could probably find more productive work than
busy waiting
by repeatedly
polling
s->count.
Avoiding busy waiting requires
a way for the consumer to yield the CPU
and resume only after
V
increments the count.
Here’s a step in that direction, though as we
will see it is not enough.
Let’s imagine a pair of calls,
sleep
and
wakeup,
that work as follows.
sleep(chan)
waits for an event designated by the value of
chan,
called the
wait channel.
sleep
puts the calling process to sleep, releasing the CPU
for other work.
wakeup(chan)
wakes all processes that are in calls
to sleep with the same
chan
(if any), causing their
sleep
calls to return.
If no processes are waiting on
chan,
wakeup
does nothing.
We can change the semaphore implementation to use
sleep
and
wakeup (changes highlighted in yellow):
200 void201 V(struct semaphore *s)202 {203 acquire(&s->lock);204 s->count += 1;205 wakeup(s);206 release(&s->lock);207 }208209 void210 P(struct semaphore *s)211 {212 while(s->count == 0)213 sleep(s);214 acquire(&s->lock);215 s->count -= 1;216 release(&s->lock);217 }
P
now gives up the CPU instead of spinning, which is nice.
However, it turns out not to be straightforward to design
sleep
and
wakeup
with this interface without suffering
from what is known as the lost wake-up problem.
Suppose that
P
finds that
s->count
==
0
on line 212.
While
P
is between lines 212 and 213,
V
runs on another CPU:
it changes
s->count
to be nonzero and calls
wakeup,
which finds no processes sleeping and thus does nothing.
Now
P
continues executing at line 213:
it calls
sleep
and goes to sleep.
This causes a problem:
P
is asleep waiting for a V call
that has already happened.
Unless we get lucky and the producer calls
V again, the consumer will wait
forever even
though the count is non-zero.
The root of this problem is that the
invariant that
P
sleeps only when
s->count
==
0
is violated by
V
running at just the wrong moment.
An incorrect way to protect the invariant would be to
move the lock acquisition (highlighted in yellow below) in
P
so that its check of the count and its call to sleep
are atomic:
300 void301 V(struct semaphore *s)302 {303 acquire(&s->lock);304 s->count += 1;305 wakeup(s);306 release(&s->lock);307 }308309 void310 P(struct semaphore *s)311 {312 acquire(&s->lock);313 while(s->count == 0)314 sleep(s);315 s->count -= 1;316 release(&s->lock);317 }
One might hope that this version of
P
would avoid the lost wakeup because the lock prevents
V
from executing between lines 313 and 314.
It does that, but it also deadlocks:
P
holds the lock while it sleeps,
so V will block forever waiting for the lock.
We’ll fix the preceding scheme by changing
sleep’s
interface:
the caller must pass the condition lock to
sleep
so it can release the lock after
the calling process is marked as asleep and waiting on the
sleep channel.
The lock will force a concurrent
V
to wait until P has finished putting itself to sleep,
so that the
wakeup
will find the sleeping consumer and wake it up.
Once the consumer is awake again
sleep
reacquires the lock before returning.
Our new correct sleep/wakeup scheme is usable as follows (change
highlighted in yellow):
400 void401 V(struct semaphore *s)402 {403 acquire(&s->lock);404 s->count += 1;405 wakeup(s);406 release(&s->lock);407 }408409 void410 P(struct semaphore *s)411 {412 acquire(&s->lock);413 while(s->count == 0)414 sleep(s, &s->lock);415 s->count -= 1;416 release(&s->lock);417 }
The fact that
P
holds
s->lock
prevents
V
from trying to wake it up between
P’s
check of
s->count
and its call to
sleep.
However,
sleep
must release
s->lock
and put the consuming process to sleep
in a way that’s atomic from the point of view of wakeup,
in order to avoid lost wakeups.