Sleep/wakeup and sleep-locks · xv6, line by line

1warm-upChoose one

wc finds the pipe empty, and piperead calls sleep_prepare(&pi->nread) on line 124. Right after that call returns, what has changed?

kernel/pipe.c

acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

wc is SLEEPING, and pi->lock has been released for it.wc’s p->chan is &pi->nread. wc is still RUNNING and still holds pi->lock.wc’s p->chan is set, and wc still holds its own p->lock until it calls sleep().wc has been put on a queue of processes waiting for the pipe.

2warm-upTrue or false, and why

True or false: in this kernel, the caller passes its condition lock to sleep, and sleep releases it before the process goes to sleep.

TrueFalse

Why?

It’s true: sleep(chan, lk) releases lk after taking p->lock, so no wakeup is lost.sleep takes only the channel; the caller keeps holding its lock while asleep.sleep takes no arguments (void sleep(void)); the caller releases its own condition lock between sleep_prepare and sleep.

3warm-upChoose one

wakeup finds a process that is SLEEPING with p->chan equal to the channel. What state does it give that process?

kernel/proc.c

574// Wake up all processes sleeping on channel chan.
575void
576wakeup(void *chan)
577{
578  struct proc *p;
579
580  for (p = proc; p < &proc[NPROC]; p++) {
581    acquire(&p->lock);
582    if (p->chan == chan) {
583      // If the process is waiting for wakeups on this channel,
584      // signal that the wakeup happened by clearing p->chan.
585      p->chan = 0;
586
587      // If this waiting process has gotten so far as to actually
588      // go to sleep, also set it back to RUNNING.
589      if (p->state == SLEEPING) {
590        p->state = RUNNABLE;
591      }
592    }
593    release(&p->lock);
594  }
595}

RUNNABLEUSEDIt stays SLEEPING; only p->chan is cleared, and the scheduler runs any process whose chan is 0.RUNNING

4warm-upChoose one

piperead sleeps on the channel &pi->nread. When pipewrite calls wakeup(&pi->nread), what does wakeup do with the integer stored at that address?

It reads nread to check whether the reader has data, and wakes the reader only if so.Nothing. It only compares the address with each process’s p->chan.It sets pi->nread to 0, which marks the channel as signalled.It increments it, counting the number of wakeups.

5warm-upChoose one

Why must piperead release pi->lock (line 125) before it calls sleep (line 126)?

kernel/pipe.c

acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

Because sleep() needs interrupts on, and releasing the lock turns them on.It isn’t required; holding it would only make other readers wait longer.So that sleep() can acquire pi->lock itself and release it at the right moment.The writer needs pi->lock to add data and wake the reader, and sched refuses to switch away while any spinlock other than p->lock is held.

6warm-upChoose all that apply

Which of these are true of a sleep-lock but not of a spinlock, in this kernel?

Interrupts stay off on the holder’s hart for as long as it is held.Its owner is recorded as a process ID.Its holder may go to sleep, for example while waiting for a disk read, without breaking any rule.A process that finds it held gives up the CPU instead of spinning.An interrupt handler may acquire it.

7warm-upMatch the pairs

Match each place that sleeps with the channel it registers on.

piperead, pipe emptypipewrite, pipe fullconsoleread, no complete line yetsys_pause, not enough ticks yetkwait, children still runningacquiresleep, lock held by someone else

8warm-upChoose one

Line 119 of piperead is a while, not an if. Why?

kernel/pipe.c

111int
112piperead(struct pipe *pi, uint64 addr, int n)
113{
int i;
struct proc *pr = myproc();
char ch;
117
acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

A return from sleep() only means something happened on the channel, or the process was killed; the pipe may still be empty, so the condition must be tested again.Because wakeup wakes only one sleeper at a time, and the loop gives the others their turn.Because sleep() returns with pi->lock released, and the while re-acquires it.Because sleep() sometimes returns on its own when a timer interrupt hits the sleeping process.

9solidPut in order

wc reads from an empty pipe whose writer is still open and goes to sleep. Put the steps in order.

kernel/pipe.c

111int
112piperead(struct pipe *pi, uint64 addr, int n)
113{
int i;
struct proc *pr = myproc();
char ch;
117
acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

release(&pi->lock)
sched() switches to this hart’s scheduler
see nread == nwrite with writeopen set, and killed() returning 0
acquire(&pi->lock)
the scheduler releases wc’s p->lock
sleep_prepare(&pi->nread): p->chan is set under p->lock
sleep(): under p->lock, p->chan is still set, so p->state = SLEEPING

10solidClick the line

A process has called sleep_prepare but not yet sleep; it is still RUNNING. Another hart calls wakeup on its channel. Click the line of wakeup that makes the process’s coming sleep() return without sleeping.

kernel/proc.c

574// Wake up all processes sleeping on channel chan.
575void
576wakeup(void *chan)
577{
578  struct proc *p;
579
580  for (p = proc; p < &proc[NPROC]; p++) {
581    acquire(&p->lock);
582    if (p->chan == chan) {
583      // If the process is waiting for wakeups on this channel,
584      // signal that the wakeup happened by clearing p->chan.
585      p->chan = 0;
586
587      // If this waiting process has gotten so far as to actually
588      // go to sleep, also set it back to RUNNING.
589      if (p->state == SLEEPING) {
590        p->state = RUNNABLE;
591      }
592    }
593    release(&p->lock);
594  }
595}

Your pick: none yet (click a line in the code)

11solidChoose one

wc is between lines 125 and 126 of pipe.c: registered on &pi->nread, pi->lock released, sleep() not yet called. On another hart, cat takes pi->lock, writes 512 bytes and calls wakeup(&pi->nread). What happens to wc?

kernel/pipe.c

acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

wakeup sets wc RUNNABLE while it is still running, so two harts may end up running it.wakeup finds no SLEEPING process on the channel and does nothing, so wc sleeps until the next write.wakeup spins on wc’s p->lock until wc has gone to sleep, then makes it RUNNABLE.wakeup clears wc’s p->chan and leaves it RUNNING; wc’s sleep() sees chan == 0 and returns at once, and the loop finds the data.

12solidChoose one

When pipewrite finds the pipe full, it calls wakeup(&pi->nread) on line 89 before it registers on &pi->nwrite and sleeps. What could happen without line 89?

kernel/pipe.c

76int
77pipewrite(struct pipe *pi, uint64 addr, int n)
78{
int i = 0;
struct proc *pr = myproc();
81
acquire(&pi->lock);
while (i < n) {
  if (pi->readopen == 0 || killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  if (pi->nwrite == pi->nread + PIPESIZE) { //DOC: pipewrite-full
    wakeup(&pi->nread);
    sleep_prepare(&pi->nwrite);
    release(&pi->lock);
    sleep();
    acquire(&pi->lock);
  } else {
    char ch;
    if (copyin(pr->pagetable, pr->sz, &ch, addr + i, 1) == -1) {
      if (i == 0)
        i = -1;
      break;
    }
    pi->data[pi->nwrite++ % PIPESIZE] = ch;
    i++;
  }
}
wakeup(&pi->nread);
release(&pi->lock);
107
return i;
109}

Nothing; line 105 wakes the reader anyway.The reader would wake, but read stale bytes, because wakeup is what makes the writes visible.The writer would panic with “sched locks”, because it still holds pi->lock.A reader asleep since the pipe was empty would never hear about the 512 bytes this write put in, and writer and reader would each sleep waiting for the other.

13solidChoose all that apply

A reader is SLEEPING in piperead, registered on &pi->nread. Which of these events can make it RUNNABLE?

Another reader of the same pipe finishing its piperead.A process writing into the same pipe with pipewrite.The pipe’s write end being closed for the last time (pipeclose with writable = 1).A timer tick on hart 0.Another process calling kill() on the reader.

14solidType a number

One call to wakeup runs on a machine where exactly one process is registered on the channel. How many times does that call execute acquire(&p->lock)?

kernel/proc.c

574// Wake up all processes sleeping on channel chan.
575void
576wakeup(void *chan)
577{
578  struct proc *p;
579
580  for (p = proc; p < &proc[NPROC]; p++) {
581    acquire(&p->lock);
582    if (p->chan == chan) {
583      // If the process is waiting for wakeups on this channel,
584      // signal that the wakeup happened by clearing p->chan.
585      p->chan = 0;
586
587      // If this waiting process has gotten so far as to actually
588      // go to sleep, also set it back to RUNNING.
589      if (p->state == SLEEPING) {
590        p->state = RUNNABLE;
591      }
592    }
593    release(&p->lock);
594  }
595}

decimal, 0x hex or 0b binary

15solidType a number

ls holds an inode’s sleep-lock and a buffer’s sleep-lock, and goes to sleep in virtio_disk_rw waiting for the disk (line 290). When sched checks mycpu()->noff on line 487, what value does it find?

kernel/virtio_disk.c

// Wait for virtio_disk_intr() to say request has finished.
while (b->disk == 1) {
  sleep_prepare(b);
  release(&disk.vdisk_lock);
  sleep();
  acquire(&disk.vdisk_lock);
}

decimal, 0x hex or 0b binary

16solidFill in the machine state

A process is writing to the console. In uartwrite it holds tx_lock (a sleep-lock) and has just returned from sleep_prepare(&tx_chan) on line 86; it is about to read LSR on line 87. What is the state of its hart?

kernel/uart.c

79void
80uartwrite(char buf[], int n)
81{
82  acquiresleep(&tx_lock);
83
84  int i = 0;
85  while (i < n) {
86    sleep_prepare(&tx_chan);
87    if (ReadReg(LSR) & LSR_TX_IDLE) {
88      WriteReg(THR, buf[i]);
89      i += 1;
90    } else {
91      sleep();
92    }
93  }
94
95  releasesleep(&tx_lock);
96}

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

17solidChoose one

holding checks a spinlock’s owner by hart (lk->cpu), but holdingsleep checks a sleep-lock’s owner by process ID (lk->pid). Why the difference?

kernel/sleeplock.c

46int
47holdingsleep(struct sleeplock *lk)
48{
49  int r;
50
51  acquire(&lk->lk);
52  r = lk->locked && (lk->pid == myproc()->pid);
53  release(&lk->lk);
54  return r;
55}

Because mycpu() may not be called while a sleep-lock is held.A sleep-lock holder may sleep while holding it and resume on a different hart, so only the process identifies the owner.Because a pid is shorter to compare than a pointer.Because sleep-locks are taken in interrupt handlers, which have no hart.

18solidPut in order

ls holds a buffer’s sleep-lock. grep calls acquiresleep on the same lock, and ls calls releasesleep only after grep is fully asleep. No third process wants the lock. Put the events in order.

kernel/sleeplock.c

21void
22acquiresleep(struct sleeplock *lk)
23{
24  acquire(&lk->lk);
25  while (lk->locked) {
26    sleep_prepare(lk);
27    release(&lk->lk);
28    sleep();
29    acquire(&lk->lk);
30  }
31  lk->locked = 1;
32  lk->pid = myproc()->pid;
33  release(&lk->lk);
34}
35
36void
37releasesleep(struct sleeplock *lk)
38{
39  acquire(&lk->lk);
40  lk->locked = 0;
41  lk->pid = 0;
42  wakeup(lk);
43  release(&lk->lk);
44}

ls: wakeup(lk) makes grep RUNNABLE
grep: re-acquires lk->lk, sees locked == 0, sets locked = 1 and pid
grep: sleep_prepare(lk) sets grep’s p->chan = lk
grep: acquire(&lk->lk), sees locked == 1
grep: sleep() marks grep SLEEPING and switches away
ls: under lk->lk, locked = 0 and pid = 0
grep: release(&lk->lk)

19solidType a number

pipewrite is about to go to sleep because the pipe is full (line 88 was true). At that moment, what is pi->nwrite - pi->nread?

kernel/pipe.c

while (i < n) {
  if (pi->readopen == 0 || killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  if (pi->nwrite == pi->nread + PIPESIZE) { //DOC: pipewrite-full
    wakeup(&pi->nread);
    sleep_prepare(&pi->nwrite);
    release(&pi->lock);
    sleep();
    acquire(&pi->lock);

decimal, 0x hex or 0b binary

20deepFill in the machine state

Hart 0 is idle in its scheduler. At the top of the loop, line 441 turns interrupts on and the pending timer interrupt is taken at once. clockintr holds tickslock and is inside wakeup(&ticks), holding one process’s p->lock. What is the state of hart 0?

kernel/trap.c

166void
167clockintr()
168{
169  if (cpuid() == 0) {
170    acquire(&tickslock);
171    ticks++;
172    wakeup(&ticks);
173    release(&tickslock);
174  }
175
176  // ask for the next timer interrupt. this also clears
177  // the interrupt request. 1000000 is about a tenth
178  // of a second.
179  w_stimecmp(r_time() + 1000000);
180}

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

21deepTrue or false, and why

True or false: once kkill has set wc’s killed flag, wc cannot go to sleep in piperead's wait loop until it has noticed the kill.

kernel/pipe.c

acquire(&pi->lock);
while (pi->nread == pi->nwrite && pi->writeopen) { //DOC: pipe-empty
  if (killed(pr)) {
    release(&pi->lock);
    return -1;
  }
  sleep_prepare(&pi->nread); //DOC: piperead-sleep
  release(&pi->lock);
  sleep();
  acquire(&pi->lock);
}

TrueFalse

Why?

A kill landing after line 120’s killed() check but before sleep() finds wc RUNNING (or RUNNABLE) and leaves p->chan set, so sleep() still puts wc to sleep.kkill clears p->chan, so the next sleep() returns at once.sleep() checks the killed flag and refuses to sleep if it is set.

22deepChoose one

uartwrite sleeps on &tx_chan without holding any spinlock: its condition is the LSR_TX_IDLE bit of a device register, and the waker is uartintr. Why can’t the “transmitter is idle” wakeup be lost?

kernel/uart.c

79void
80uartwrite(char buf[], int n)
81{
82  acquiresleep(&tx_lock);
83
84  int i = 0;
85  while (i < n) {
86    sleep_prepare(&tx_chan);
87    if (ReadReg(LSR) & LSR_TX_IDLE) {
88      WriteReg(THR, buf[i]);
89      i += 1;
90    } else {
91      sleep();
92    }
93  }
94
95  releasesleep(&tx_lock);
96}

It can be lost, but it doesn’t matter, because the next UART interrupt will wake the process.It calls sleep_prepare(&tx_chan) before reading LSR, so if the UART goes idle after that read, the interrupt’s wakeup finds it registered and clears p->chan.tx_lock is held, which keeps the UART interrupt from running until uartwrite sleeps.Interrupts are off on this hart from the LSR read until the process is asleep.

23deepChoose one

iput calls acquiresleep(&ip->lock) on line 362 while holding the spinlock itable.lock. Why doesn’t this break the rule “never sleep while holding a spinlock”?

kernel/fs.c

349void
350iput(struct inode *ip)
351{
352  acquire(&itable.lock);
353
354  // Last reference of an unlinked inode?  Capture dev/inum before ref--,
355  // since once ref hits 0, ip may be recycled by a concurrent iget()
356  // for a different inum.
357  int last = (ip->ref == 1 && ip->valid && ip->nlink == 0);
358  uint dev = ip->dev, inum = ip->inum;
359
360  if (last) {
361    // ip->ref == 1 means no other process can have ip locked.
362    acquiresleep(&ip->lock);
363    release(&itable.lock);
364
365    itrunc(ip); // free the data blocks (type stays nonzero on disk)
366    ip->valid = 0;
367
368    releasesleep(&ip->lock);
369
370    acquire(&itable.lock);
371  }
372
373  ip->ref--;
374  release(&itable.lock);
375
376  if (last)
377    ifree(dev, inum); // now clear type on disk: inum becomes allocatable
378}

acquiresleep detects that a spinlock is held and spins instead of sleeping.It runs only when ip->ref == 1, so no other process can hold or be waiting for ip->lock; acquiresleep finds it free and never sleeps.It does break the rule; this is a known bug that can deadlock under load.acquiresleep releases itable.lock before it sleeps and re-acquires it after.

24deepTrue or false, and why

True or false: in kexit, swapping lines 353 and 355, so that the process takes its own p->lock before calling wakeup(p->parent), would be harmless.

kernel/proc.c

347  acquire(&wait_lock);
348
349  // Give any children to init.
350  reparent(p);
351
352  // Parent might be sleeping in wait().
353  wakeup(p->parent);
354
355  acquire(&p->lock);
356
357  p->xstate = status;
358  p->state = ZOMBIE;
359
360  release(&wait_lock);
361
362  // Jump into the scheduler, never to return.
363  sched();
364  panic("zombie exit");

TrueFalse

Why?

The parent would see the child as ZOMBIE before the child is ready.It’s harmless: wakeup skips the calling process’s own slot.wakeup acquires every slot’s p->lock, including the caller’s own, so acquire would find this hart already holding it and panic.

25deepChoose all that apply

A process P has p->chan != 0. Which of these could be true at that moment?

P is back in user mode after a console write whose uartwrite never had to sleep.P is SLEEPING, waiting for a wakeup on that channel.A wakeup on that same channel has run since P’s most recent sleep_prepare.P is RUNNABLE because kkill woke it, and nothing has cleared chan since.P is RUNNING, between its sleep_prepare and its sleep().P is UNUSED.