Scheduling and swtch · xv6, line by line

1warm-upChoose one

swtch saves the registers of the thread that is stopping into a struct context. Which registers are they?

kernel/proc.h

1// Saved registers for kernel context switches.
2struct context {
uint64 ra;
uint64 sp;
5
// callee-saved
uint64 s0;
uint64 s1;
uint64 s2;
uint64 s3;
uint64 s4;
uint64 s5;
uint64 s6;
uint64 s7;
uint64 s8;
uint64 s9;
uint64 s10;
uint64 s11;
19};

ra, sp and the callee-saved registers s0–s11: 14 registers in all.ra, sp, s0–s11, plus satp and sstatus.The argument registers a0–a7 and the temporaries t0–t6.All 31 general-purpose registers, the same set the trapframe holds.

2warm-upType a number

Hart 1 is running process A. A’s timer tick makes it yield, and hart 1 next runs process B. How many calls to swtch does hart 1 make between “running A” and “running B”?

decimal, 0x hex or 0b binary

3warm-upChoose one

When sched switches away from a process, hart 1 continues in scheduler. Which memory is hart 1’s stack pointer pointing into while the scheduler scans proc[]?

Inside cpus[1], in the context field.The kernel stack of the process that just stopped.Hart 1’s own 4 KiB slice of stack0, the same stack it booted on.A page that kalloc allocated for the scheduler when the hart started.

4warm-upChoose all that apply

Which of these functions call sched directly?

5warm-upClick the line

In swtch, click the instruction at which the hart stops using the old thread’s stack and starts using the new thread’s stack.

kernel/swtch.S

globl swtch
9swtch:
      sd ra, 0(a0)
      sd sp, 8(a0)
      sd s0, 16(a0)
      sd s1, 24(a0)
      sd s2, 32(a0)
      sd s3, 40(a0)
      sd s4, 48(a0)
      sd s5, 56(a0)
      sd s6, 64(a0)
      sd s7, 72(a0)
      sd s8, 80(a0)
      sd s9, 88(a0)
      sd s10, 96(a0)
      sd s11, 104(a0)
24
      ld ra, 0(a1)
      ld sp, 8(a1)
      ld s0, 16(a1)
      ld s1, 24(a1)
      ld s2, 32(a1)
      ld s3, 40(a1)
      ld s4, 48(a1)
      ld s5, 56(a1)
      ld s6, 64(a1)
      ld s7, 72(a1)
      ld s8, 80(a1)
      ld s9, 88(a1)
      ld s10, 96(a1)
      ld s11, 104(a1)
      
      ret

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

6warm-upChoose one

A process created by fork has never run. When a scheduler first calls swtch(&c->context, &p->context) for it, where does swtch’s ret jump?

kernel/proc.c

// Set up new context to start executing at forkret,
// which returns to user space.
memset(&p->context, 0, sizeof(p->context));
p->context.ra = (uint64)forkret;
p->context.sp = p->kstack + PGSIZE;
148
return p;

Into usertrap, so that the child returns from the fork system call like its parent.To the user instruction after the parent’s ecall, in user mode.To the first instruction of forkret.To the instruction after the swtch call in sched, like every other process.

7warm-upType a number

Lines 10–23 of swtch store the old thread’s registers into its context. How many bytes do they write in total?

kernel/swtch.S

globl swtch
9swtch:
      sd ra, 0(a0)
      sd sp, 8(a0)
      sd s0, 16(a0)
      sd s1, 24(a0)
      sd s2, 32(a0)
      sd s3, 40(a0)
      sd s4, 48(a0)
      sd s5, 56(a0)
      sd s6, 64(a0)
      sd s7, 72(a0)
      sd s8, 80(a0)
      sd s9, 88(a0)
      sd s10, 96(a0)
      sd s11, 104(a0)

decimal, 0x hex or 0b binary

8warm-upTrue or false, and why

True or false: swtch ought to save and restore tp as well, and leaving it out means a process resumed on a different hart will compute mycpu wrongly.

TrueFalse

Why?

tp holds the number of the hart executing the code; a thread resumed on hart 2 must see 2, so tp must stay with the hart.tp is caller-saved, so the C compiler already saved it before calling swtch.The kernel never reads tp, so its value does not matter.

9solidChoose one

yield acquires p->lock, sets p->state = RUNNABLE, and calls sched still holding the lock. The lock is released by the scheduler only after swtch. Why must it stay held across the switch?

kernel/proc.c

499// Give up the CPU for one scheduling round.
500void
501yield(void)
502{
503  struct proc *p = myproc();
504  acquire(&p->lock);
505  p->state = RUNNABLE;
506  sched();
507  release(&p->lock);
508}

Because swtch must run with interrupts off, and holding a spinlock is the only way to keep them off.So that the process keeps its claim on this hart and is resumed on the same hart.Because sched needs the lock to find the process’s context field.So that no other hart can see RUNNABLE and start running the process while this hart is still executing on its kernel stack and saving its registers.

10solidChoose one

Each pass of scheduler's outer loop executes intr_on() immediately followed by intr_off(). What is the point of turning interrupts on for a single instruction?

kernel/proc.c

for (;;) {
  // The most recent process to run may have had interrupts
  // turned off; enable them to avoid a deadlock if all
  // processes are waiting. Then turn them back off
  // to avoid a possible race between an interrupt
  // and wfi.
  intr_on();
  intr_off();
443

It is the one place in the loop where a pending device or timer interrupt can be taken, so handlers can run and wake processes even when nothing is runnable.It turns interrupts on for the process the scheduler is about to run.It lets other harts acquire the p->locks this hart was spinning on.It lets the timer interrupt preempt the scheduler and switch to a process.

11solidChoose one

Hart 2 is idle. A timer interrupt has been pending, and it is taken right after intr_on() at line 441. What does kerneltrap do with it?

kernel/trap.c

136void
137kerneltrap()
138{
int which_dev = 0;
uint64 sepc = r_sepc();
uint64 sstatus = r_sstatus();
uint64 scause = r_scause();
143
if ((sstatus & SSTATUS_SPP) == 0)
  panic("kerneltrap: not from supervisor mode");
if (intr_get() != 0)
  panic("kerneltrap: interrupts enabled");
148
if ((which_dev = devintr()) == 0) {
  // interrupt or trap from an unknown source
  printk("scause=0x%lx sepc=0x%lx stval=0x%lx\n", scause, r_sepc(),
         r_stval());
  panic("kerneltrap");
}
155
// give up the CPU if this is a timer interrupt.
if (which_dev == 2 && myproc() != 0)
  yield();
159
// the yield() may have caused some traps to occur,
// so restore trap registers for use by kernelvec.S's sepc instruction.
w_sepc(sepc);
w_sstatus(sstatus);
164}

It panics with kerneltrap: interrupts enabled, because the scheduler had just turned interrupts on.The trap goes through uservec and usertrap, because no process is running.It calls yield, which switches to another RUNNABLE process.devintr calls clockintr, which re-arms stimecmp; since myproc() is 0, there is no yield, and the trap returns into the scheduler.

12solidType a number

An idle hart runs one full pass of scheduler's inner for loop and finds nothing RUNNABLE. How many times does it call acquire during that pass?

kernel/proc.c

  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }
  if (found == 0) {
    // nothing to run; stop running on this core until an interrupt.
    asm volatile("wfi");
  }

decimal, 0x hex or 0b binary

13solidFill in the machine state

Pid 5 was spinning in user mode on hart 1 when a timer interrupt arrived. usertrap called yield, which called sched, which called swtch. Hart 1 has just executed line 26, ld sp, 8(a1). What is hart 1’s state?

kernel/swtch.S

globl swtch
9swtch:
      sd ra, 0(a0)
      sd sp, 8(a0)
      sd s0, 16(a0)
      sd s1, 24(a0)
      sd s2, 32(a0)
      sd s3, 40(a0)
      sd s4, 48(a0)
      sd s5, 56(a0)
      sd s6, 64(a0)
      sd s7, 72(a0)
      sd s8, 80(a0)
      sd s9, 88(a0)
      sd s10, 96(a0)
      sd s11, 104(a0)
24
      ld ra, 0(a1)
      ld sp, 8(a1)
      ld s0, 16(a1)
      ld s1, 24(a1)
      ld s2, 32(a1)
      ld s3, 40(a1)
      ld s4, 48(a1)
      ld s5, 56(a1)
      ld s6, 64(a1)
      ld s7, 72(a1)
      ld s8, 80(a1)
      ld s9, 88(a1)
      ld s10, 96(a1)
      ld s11, 104(a1)
      
      ret

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

14solidFill in the machine state

Hart 0’s scheduler has just returned from acquire(&p->lock) at line 446, during a scan. What is hart 0’s state?

kernel/proc.c

for (;;) {
  // The most recent process to run may have had interrupts
  // turned off; enable them to avoid a deadlock if all
  // processes are waiting. Then turn them back off
  // to avoid a possible race between an interrupt
  // and wfi.
  intr_on();
  intr_off();
443
  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }

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

15solidChoose all that apply

Which of these are true at the instant scheduler executes the call swtch(&c->context, &p->context) on line 453?

kernel/proc.c

  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }

16solidPut in order

Pid 5 is preempted by a timer tick on hart 1 and later resumed by hart 0. Put these events in the order they must happen.

Hart 1’s scheduler releases pid 5’s p->lock (line 463)
Hart 0’s swtch loads pid 5’s context, and yield releases the lock
usertrap sees which_dev == 2 and calls yield
sched checks its four rules and copies intena into a local
Hart 0’s scheduler acquires pid 5’s p->lock, sees RUNNABLE and sets RUNNING
swtch saves pid 5’s registers and loads hart 1’s scheduler context
yield acquires pid 5’s p->lock and sets RUNNABLE

17solidChoose one

Hart 1’s scheduler switched to the process in proc[4]. A tick later that process yields, and the scheduler returns from the swtch on line 453. Which slot does it examine next?

kernel/proc.c

  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }
  if (found == 0) {
    // nothing to run; stop running on this core until an interrupt.
    asm volatile("wfi");
  }
}

proc[0]: every return from a process restarts the scan from the beginning.Whichever RUNNABLE process has waited longest.proc[4] again, because it is RUNNABLE once more.proc[5]: it continues the same for loop where it left off.

18solidMatch the pairs

Each release(&p->lock) below releases a lock that was acquired somewhere else. Match each release with the code that acquired that lock.

release(&p->lock) in scheduler, line 463, just after swtch has returnedrelease(&p->lock) in forkret, line 520release(&p->lock) at the end of yield, line 507release(&p->lock) in kkill, line 616

19solidClick the line

Once a process is running, its p->lock is free: any scheduler can lock the slot and look at it. Click the line that makes those schedulers leave the process alone.

kernel/proc.c

  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }

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

20deepChoose one

Why does scheduler turn interrupts off (line 442) before scanning, instead of leaving them on for the scan?

kernel/proc.c

for (;;) {
  // The most recent process to run may have had interrupts
  // turned off; enable them to avoid a deadlock if all
  // processes are waiting. Then turn them back off
  // to avoid a possible race between an interrupt
  // and wfi.
  intr_on();
  intr_off();
443
  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }
  if (found == 0) {
    // nothing to run; stop running on this core until an interrupt.
    asm volatile("wfi");
  }
}
470}

Because acquire requires interrupts to be off before it is called.Because wfi only works when interrupts are disabled.To stop other harts from changing proc[] while this hart scans it.So that an interrupt arriving during a fruitless scan stays pending and makes wfi return at once, instead of being handled mid-scan and leaving the hart in wfi with a process it has just woken.

21deepChoose one

Right after its swtch returns, scheduler executes mycpu()->intena = 0 (line 456). What would go wrong without that line?

kernel/proc.c

  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }

release would panic, because holding() checks intena.noff would stay at 1 forever, so the next acquire would panic.The next process the scheduler runs would start with interrupts permanently disabled.After a process that slept inside a system call (intena 1), the release at line 463 would turn interrupts on in the middle of the scan.

22deepChoose all that apply

Process P stops on hart 1 through sched and is later resumed on hart 2. Which of these are carried from hart 1 to hart 2 with P, so that P finds its own values after the switch?

23deepTrue or false, and why

True or false: when an idle hart executes wfi on line 467, its timer interrupt can still end the wait, even though sstatus.SIE is 0 at that point.

kernel/proc.c

for (;;) {
  // The most recent process to run may have had interrupts
  // turned off; enable them to avoid a deadlock if all
  // processes are waiting. Then turn them back off
  // to avoid a possible race between an interrupt
  // and wfi.
  intr_on();
  intr_off();
443
  int found = 0;
  for (p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if (p->state == RUNNABLE) {
      // Switch to chosen process.  It is the process's job
      // to release its lock and then reacquire it
      // before jumping back to us.
      p->state = RUNNING;
      c->proc = p;
      swtch(&c->context, &p->context);
454
      // Don't re-enable interrupts on release.
      mycpu()->intena = 0;
457
      // Process is done running for now.
      // It should have changed its p->state before coming back.
      c->proc = 0;
      found = 1;
    }
    release(&p->lock);
  }
  if (found == 0) {
    // nothing to run; stop running on this core until an interrupt.
    asm volatile("wfi");
  }
}
470}

TrueFalse

Why?

wfi turns sstatus.SIE back on while the hart waits.wfi resumes when an interrupt is pending and enabled in sie, whatever sstatus.SIE says; the interrupt is not taken yet, and the hart goes on to the next instruction.The timer interrupt is delivered to M-mode, which is never masked by sstatus.SIE.

24deepChoose all that apply

Suppose release(&p->lock) on line 520 were moved to become the first statement inside the if (first) block, so that init still releases it but no later fork child does. A new child, pid 9, reaches user mode on hart 1. Which of these would then happen?

kernel/proc.c

510// A fork child's very first scheduling by scheduler()
511// will swtch to forkret.
512void
513forkret(void)
514{
515  extern char userret[];
516  static int first = 1;
517  struct proc *p = myproc();
518
519  // Still holding p->lock from scheduler.
520  release(&p->lock);
521
522  if (first) {
523    first = 0;
524
525    // File system initialization must be run in the context of a
526    // regular process (e.g., because it calls sleep), and thus cannot
527    // be run from main().
528    fsinit(ROOTDEV);
529
530    // We can invoke kexec() now that file system is initialized.
531    // Put the return value (argc) of kexec into a0.
532    p->trapframe->a0 = kexec("/init", (char *[]){"/init", 0});
533    if (p->trapframe->a0 == -1) {
534      panic("exec");
535    }
536  }
537
538  // return to user space, mimicing usertrap()'s return.
539  prepare_return();
540  uint64 satp = MAKE_SATP(p->pagetable);
541  uint64 trampoline_userret = TRAMPOLINE + (userret - trampoline);
542  ((void (*)(uint64))trampoline_userret)(satp);
543}

Any other hart’s scheduler that reaches pid 9’s slot spins in acquire and never gets the lock.At pid 9’s next trap into the kernel on hart 1, the first acquire of its own p->lock (for example in killed) panics with acquire.Pid 9 runs in user mode with interrupts disabled, so it can never be preempted.Nothing goes wrong, because sret releases any spinlocks the hart holds.The scheduler that acquired the lock releases it after pid 9’s first yield.

25deepChoose one

cat called sleep from inside read, with interrupts on, on hart 1. It is woken and resumed by hart 2’s scheduler. Suppose line 496 of sched, mycpu()->intena = intena;, were deleted (line 494 kept). What changes for cat?

kernel/proc.c

479void
480sched(void)
481{
482  int intena;
483  struct proc *p = myproc();
484
485  if (!holding(&p->lock))
486    panic("sched p->lock");
487  if (mycpu()->noff != 1)
488    panic("sched locks");
489  if (p->state == RUNNING)
490    panic("sched RUNNING");
491  if (intr_get())
492    panic("sched interruptible");
493
494  intena = mycpu()->intena;
495  swtch(&p->context, &mycpu()->context);
496  mycpu()->intena = intena;
497}

sched panics with sched interruptible.Nothing changes, because swtch restores intena from cat’s context.Interrupts turn on in the middle of hart 2’s scheduler loop.cpus[2].intena stays 0 from hart 2’s scheduler, so when sleep releases p->lock, interrupts stay off for the rest of cat’s system call, until sret.