Skip to content

Prep: The Context Switch and the Scheduler — 35k · 36k

Session: Fri Oct 23, 1h30 · Exercises: 35k_context_switch, 36k_scheduling · Prep time: ~20 min · Lecture: Week 9 · Processes, the Context Switch, and Scheduling

Back from break

This session's lecture was Tue Oct 13, before Midterm 1 and fall break. Before class, reread Week 9 · This week, then all of Friday · 35k The context switch and Friday · 36k Round robin. Three ideas matter most today: a context is only 14 registers, because the switch is entered by an ordinary call; the switch saves into one context and loads from the other, so its ret lands where the loaded ra points; and round robin keeps its place in a cursor that moves just past each pick.

What you will build

First the mechanism: a context is the fourteen registers ra, sp and s0–s11, laid out by #[repr(C)], and the switch routine freezes the running context, thaws another, and rets into a different thread. Half of that assembly is given; you write the other half. Then the policy: a round-robin picker that scans the process table from a rotation cursor, skips anything not Runnable, wraps around, and drives the double switch. The harness checks that a switch round-trips (control comes back after the call) and that three runnable processes plus one sleeping one run interleaved, one turn each per rotation, instead of one running to completion.

Concepts you need

Read before class

What Time
Week 9 · This week, then Friday · 35k The context switch, all three sections 5 min
Week 9 · Friday · 36k Round robin, all three sections 3 min
Week 9 · For the exam: The vocabulary and The scheduling survey. Not needed today; on Midterm 2 2 min
RISC-V guide: The caller/callee split and Loads, stores, and offsets 3 min

Mental model

Two contexts ping-pong through a generic switch(old, new), a call that comes back somewhere else.

L = { ra: ?,    sp: ? }             # the loop; saved by its first switch
P = { ra: ping, sp: page + 4096 }   # forged: entry, top of a fresh page

loop:  switch(&L, &P)           # save into L, load P, ret lands at ping
ping:  s3 = 7; switch(&P, &L)   # save into P, load L, ret lands after loop's call
loop:  switch(&L, &P)           # ret lands inside ping's own call; s3 is 7 again

ret jumps to the ra loaded just before, so the routine "returns" into whichever context it loaded. Every transition in rv6 (yield, block, exit) is this move, always via the scheduler's own context, so the picking code never stands on a stack about to be freed.

Check yourself

  1. Why does a context hold ra, sp, and s0–s11 but no t or a registers and no program counter?
    AnswerThe caller spilled any t/a value it still needed before the call, so saving sp reaches them. A suspended thread is always paused inside the switch call, so ra is its resume address.
  2. States are [Runnable, Sleeping, Runnable, Sleeping, Runnable] and the cursor is 3; next four picks and final cursor? What if the cursor is set to the winner instead?
    AnswerPicks 4 (cursor 0), 0 (cursor 1), 2 (cursor 3), 4 (cursor 0). Cursor-equals-winner picks slot 4 forever, starving the other two.
  3. A forged context sets sp to the base of its fresh page rather than base + 4096. What goes wrong, and when?
    AnswerStacks grow downward, so the first push writes below the page. Nothing faults at the switch; the corruption surfaces later, in unrelated code.

What "done" looks like

oslings run is green, then oslings submit before you leave. Not green? Submit anyway — the tests that pass earn their share — then finish it at a make-up session (office hours, on the class network) for three quarters, or anywhere else for half, and submit again.

If you finish early

Work Week 9 · Problem 3: Trace a switch through a hub and Problem 4: Predict the round-robin order; Week 9 · The vocabulary and The scheduling survey are Midterm 2 material. Then read chapter 7, "Scheduling," of the xv6 book, or start the next prep page, Prep: Spinlocks and Semaphores.