9.2 Code: Sleep and wakeup

Xv6’s sleep (2703) and wakeup (2734) implement the interface used in the example above. The basic idea is to have sleep mark the current process as SLEEPING and then call sched to release the CPU; wakeup looks for a process sleeping on the given wait channel and marks it as RUNNABLE.

sleep acquires p->lock (2714) and only then releases the condition lock lk. The fact that sleep holds one or the other of these locks at all times is what prevents a concurrent wakeup (which must acquire and hold both) from acting, and thus prevents a lost wake-up. Now that sleep holds just p->lock, it can put the process to sleep by recording the wait channel, changing the process state to SLEEPING, and calling sched (2718-2721). In a moment it will be clear why it’s critical that p->lock is not released (by scheduler) until after the process is marked SLEEPING.

At some point, a process will acquire the condition lock, set the condition that the sleeper is waiting for, and call wakeup(chan). It’s important that wakeup is called while holding the condition lock11 1 Strictly speaking it is sufficient if wakeup merely follows the acquire (that is, one could call wakeup after the release).. wakeup loops over the process table (2734). It acquires the p->lock of each process it inspects. When wakeup finds a process in state SLEEPING with a matching chan, it changes that process’s state to RUNNABLE. The next time scheduler runs, it will see that the process is ready to be run.

⬇

                      1
                      
                      
                      
                          piperead() {


                      2
                      
                      
                      
                            acquire(&pipe->lock);


                      3
                      
                      
                      
                            while(no data in pipe->buffer) {


                      4
                      
                      
                      
                              sleep(&pipe, &pipe->lock) {


                      5
                      
                      
                      
                                // in sleep()


                      6
                      
                      
                      
                                acquire(&p->lock)


                      7
                      
                      
                      
                                release(&pipe->lock)


                      8
                      
                      
                      
                                p->state = SLEEPING


                      9
                      
                      
                      
                                ...


                      10
                      
                      
                      
                                swtch() {


                      11
                      
                      
                      
                                  // in scheduler()


                      12
                      
                      
                      
                                  release(&p->lock)


                      13
                      
                      
                      
                                  ...
Holding pipe->lockHolding p->lock
Figure 9.1: Overlapping locks to avoid lost wake-up

Why do the locking rules for sleep and wakeup ensure that a process that’s going to sleep won’t miss a concurrent wakeup? The going-to-sleep process holds either the condition lock or its own p->lock or both from before it checks the condition until after it has marked itself as SLEEPING; see Figure 9.1. The process calling wakeup needs to aquire both locks. The waker might acquire the locks first, which means it will make the condition true before the consuming thread checks the condition, and the consuming thread won’t need to call sleep(); or the waker’s acquire()s might have to wait until the consuming thread has completely finished going to sleep and releases the locks, in which case the waker will then see that the consuming thread is marked SLEEPING and will wake it up.

Sometimes multiple processes are sleeping on the same channel; for example, more than one process reading from a pipe. A single call to wakeup will wake them all up. One of them will run first and acquire the lock that sleep was called with, and (in the case of pipes) read whatever data is waiting. The other processes will find that, despite being woken up, there is no data to be read. From their point of view the wakeup was “spurious,” and they must sleep again. For this reason sleep is always called inside a loop that re-checks the condition, as in P above.

No harm is done if two uses of sleep/wakeup accidentally choose the same channel: they will see spurious wakeups, but looping as described above will tolerate this problem. Much of the charm of sleep/wakeup is that it is both lightweight (no need to create special data structures to act as wait channels) and provides a layer of indirection (callers need not know which specific process they are interacting with).