9.1 Overview
The sleep/wakeup interface looks like:
1 void sleep(void *chan, struct spinlock *lk)2 void wakeup(void *chan)
sleep() marks the calling process as SLEEPING
(not RUNNABLE) and releases the CPU by context-switching
to the scheduler, so that other processes can run.
The chan argument is called the wait channel.
wakeup(chan) wakes up all processes (if any)
that have called sleep(chan, ...) with the same chan
value. sleep and wakeup treat chan
as an opaque 64-bit value; the only thing they do with it is compare for
equality. The usual pattern is for callers to pass the address of
some convenient object as the chan argument.
Kernel code calls sleep to wait for some
condition to become true. For example, the kernel code
that reads from a pipe calls sleep if the pipe buffer is
currently empty; the condition in this case is the pipe buffer
becoming non-empty (due to another process writing to the pipe).
sleep and wakeup do not know what the
condition is: only the calling code knows. The usual pattern is for
the caller to first check the condition, and call sleep
if it is not true; code that later makes the
condition true calls wakeup.
Here’s a sketch of how the xv6 kernel pipe code uses
sleep and wakeup:
1 piperead(pipe){2 acquire(&pipe->lock);3 while(there’s no data in pipe->buffer){4 // ZZZ5 sleep(&pipe, &pipe->lock);6 }7 remove the data from the pipe;8 release(&pipe->lock);9 }1011 pipewrite(pipe){12 acquire(&pipe->lock);13 append data to pipe->buffer;14 wakeup(&pipe);15 release(&pipe->lock);16 }’
This code uses the address of the pipe data structure as the wait channel.
What is the lk argument to sleep?
In all uses of sleep/wakeup
the condition involves shared data, used by both the
thread that sleeps and the thread that calls wakeup, so
there always turns out to be a lock that protects the condition. That lock is
called the condition lock. In the pipe code above, both
functions use the pipe and its buffer while holding the pipe lock,
which in this case is also the condition lock. It’s a rule that any code
that calls sleep or wakeup must hold the
condition lock, and that the lock must be passed to sleep
as the second argument.
The reason that the condition lock must be held when sleep
is called, and that it must be passed to sleep, is to
prevent the possibility that another thread might call
wakeup between the check of the condition
and the call to sleep. A call to
wakeup at that point would find no sleeping process to
wake up; the wakeup would simply return.
But then the call to sleep might never wake up,
since the wakeup intended for it has already happened.
This undesirable situation is called a lost wake-up.
In the pipe example above, the lost wake-up being avoided is the
possibility that a thread on another CPU might call pipewrite
at the point marked ZZZ,
between piperead’s check of the condition and its call to
sleep. The fact that piperead holds the pipe
lock during the time between when it checks the condition and calls
sleep prevents pipewrite from executing, and
thus prevents a lost wake-up.
sleep() releases the condition lock so that the code calling wakeup() can proceed. sleep() also context-switches to the scheduler in order to let other threads run while it is waiting. The implementation performs these two steps in a way that is atomic (indivisible) with respect to wakeup(), to prevent lost wake-ups.