Preparing for the Lab Quiz
What the lab quiz (4 of the lab's 7 points) covers. You do not need it to write the code or pass the tests.
What the quiz covers
The quiz covers the Trace Code section of q4-spec.md on branch q4, and may also cover your implementation:
- The two paths of a timer interrupt, and how the kernel switches between the two trap handlers.
- The hardware clock: how long a tick is, when the hardware raises a timer interrupt, and how
clockintr()asks for the next one. - The six paths of the state diagram: for each path, which processes are in the ready queue, how their order is decided, how the scheduler picks one, and how the context switch happens.
- Your own code in every task: which job runs next, when the running job stops, and why.
The Two Paths of a Timer Interrupt
The CPU runs in one of two modes. In user mode it runs a user program, such as the loop in burn(). In kernel mode it runs kernel code, such as the system call cputicks(). A trap stops what the CPU is doing and jumps into the kernel, in kernel mode. An interrupt is one kind of trap, and a system call is another.
Each process has its own kernel stack, p->kstack. The kernel runs on it while it works for that process. When a trap comes from user mode, the user registers are saved in p->trapframe so that the program can continue later. The scheduler loop belongs to no process and runs on a stack of its own.
Where a trap enters: the register stvec
The register stvec holds the address the CPU jumps to on a trap. xv6 has two entry points, one per mode, and changes stvec whenever the CPU changes mode:
| Entry point | Traps from | What it does | stvec set to it by |
|---|---|---|---|
uservec (kernel/trampoline.S) | user mode | saves the user registers in p->trapframe, switches to p->kstack, calls usertrap() | prepare_return(), just before the kernel returns to user space |
kernelvec (kernel/kernelvec.S) | kernel mode | already on a kernel stack: saves the registers there and calls kerneltrap() | usertrap(), as its first step |
Both handlers call devintr(), which finds out which device interrupted. For the timer it calls clockintr() and returns 2. So the two paths are:
After devintr() returns 2, usertrap() or kerneltrap() calls sched_timer(). clockintr() has already called sched_tick(), so the tick is always counted before the stop decision.
Where the timer can find the CPU
A job in burn() calls cputicks() again and again, so a timer interrupt finds the CPU in one of three places:
- In the job's own code, in user mode. The trap enters at
uservec. - Inside the system call
cputicks(), in kernel mode.usertrap()turns interrupts on before it runs a system call, so the timer can interrupt it. The trap enters atkernelvec. If the job gives up the CPU here, it does so in the middle of the system call, which continues when the job runs again. - In the scheduler loop, because no process is
RUNNABLE. The loop waits with the instructionwfiwhile interrupts are off, so the interrupt stays pending until the loop turns interrupts on at its top. Then it enters atkernelvec, andmyproc()returns 0: there is no process to stop.
The Hardware Clock
The CPU has a counter, time, that grows at a fixed rate. In QEMU's virt machine the timebase-frequency is 10000000: time grows by 10 million per second.
A second register, stimecmp, sets the alarm. The hardware raises a supervisor timer interrupt when time reaches stimecmp, and the interrupt stays pending as long as time is at least stimecmp. The kernel sets the first alarm in timerinit() (kernel/start.c). After that, every interrupt sets the next one at the end of clockintr():
| 165 | void |
| 166 | clockintr() |
| 167 | { |
| 168 | if (cpuid() == 0) { |
| 169 | acquire(&tickslock); |
| 170 | ticks++; |
| 171 | wakeup(&ticks); |
| 172 | release(&tickslock); |
| 173 | // TODO (trap): tell the scheduler that a tick has passed. |
| 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 | } |
Writing stimecmp does two jobs. It asks for the next interrupt 1000000 counts later, which is 1000000 / 10000000 = 0.1 s, one tick. And because the new value is in the future, the interrupt is no longer pending.
stimecmp, run make qemu, and explain what you see. Undo the change afterwards.The Six Paths of the State Diagram
xv6 keeps every process in the array proc[], and p->state holds its state. The xv6 names differ from the usual textbook names:
| xv6 state | Textbook name | Meaning |
|---|---|---|
USED | New | allocproc() has reserved the entry, but the process cannot run yet. |
RUNNABLE | Ready | Can run and waits for the CPU. |
RUNNING | Running | On the CPU now. |
SLEEPING | Waiting | Waits for an event, such as the end of a pause(). |
ZOMBIE | Terminated | Has exited, but its parent has not collected it with wait() yet. |
| Path | Call chain | What happens | Log line |
|---|---|---|---|
| 1 · New → Ready | userinit / kfork → allocproc | allocproc() finds an UNUSED entry, gives it the next pid and makes it USED. kfork() copies the parent, then sets RUNNABLE and enter_tick = ticks: the child joins the end of the ready queue. | none |
| 2 · Ready → Running | scheduler → sched_pick → swtch | sched_pick() calls the picker and returns its job locked. scheduler() sets RUNNING, resets slice_used and wait_ticks, sets c->proc and switches to the job. | run |
| 3 · Running → Ready | usertrap / kerneltrap → sched_timer → sched → swtch | should_preempt() says stop. The yield code makes the job RUNNABLE (at the end of its queue for requeue) and sched() switches to the scheduler. | requeue or preempt |
| 4 · Running → Waiting | sys_pause → sleep_prepare → sleep → sched | sys_pause() sets p->wake_tick. sleep() sets SLEEPING, calls sched_sleep() (the end of a CPU burst), then sched(). | sleep |
| 5 · Waiting → Ready | clockintr → sched_tick → sched_wakeup | At every tick, sched_tick() wakes each sleeper whose wake_tick has come. sched_wakeup() sets RUNNABLE, enter_tick = ticks and wait_ticks = 0. | wake, or new for a job leaving schedstart() |
| 6 · Running → Terminated | sys_exit → kexit → sched | kexit() closes the files, gives the children to init, wakes the parent, sets ZOMBIE and calls sched(). It never returns. The parent's wait() later frees the entry. | exit |
For each path, the quiz asks four things. Which processes are in the ready queue: every RUNNABLE entry of proc[]. How their order is decided: by the fields your picker compares. How the scheduler picks one: the loop below. How the context switch happens: the next section.
The Scheduler Loop and the Context Switch
A process's kernel stack and a set of saved registers, p->context, form its kernel thread. The scheduler loop runs in the CPU's scheduler thread, on its own stack, with its registers saved in cpu->context.
swtch(old, new) in kernel/swtch.S saves the return address ra, the stack pointer sp and the registers s0–s11 in old, and loads them from new. So its final ret returns into the other thread, where that thread last called swtch.
xv6 never switches directly from one process to another. A process calls sched(), which switches to the scheduler thread. The scheduler thread then picks the next process and switches to it:
| 437 | // Per-CPU process scheduler. |
| 438 | // Each CPU calls scheduler() after setting itself up. |
| 439 | // Scheduler never returns. It loops, doing: |
| 440 | // - choose a process to run. |
| 441 | // - swtch to start running that process. |
| 442 | // - eventually that process transfers control |
| 443 | // via swtch back to the scheduler. |
| 444 | void |
| 445 | scheduler(void) |
| 446 | { |
| 447 | struct proc *p; |
| 448 | struct cpu *c = mycpu(); |
| 449 | |
| 450 | c->proc = 0; |
| 451 | for (;;) { |
| 452 | // The most recent process to run may have had interrupts |
| 453 | // turned off; enable them to avoid a deadlock if all |
| 454 | // processes are waiting. Then turn them back off |
| 455 | // to avoid a possible race between an interrupt |
| 456 | // and wfi. |
| 457 | intr_on(); |
| 458 | intr_off(); |
| 459 | |
| 460 | int found = 0; |
| 461 | if ((p = sched_pick()) != 0) { |
| 462 | // Switch to chosen process. It is the process's job |
| 463 | // to release its lock and then reacquire it |
| 464 | // before jumping back to us. |
| 465 | p->state = RUNNING; |
| 466 | p->slice_used = 0; |
| 467 | p->wait_ticks = 0; |
| 468 | schedlog(p, SEV_RUN); |
| 469 | c->proc = p; |
| 470 | swtch(&c->context, &p->context); |
| 471 | |
| 472 | // Don't re-enable interrupts on release. |
| 473 | mycpu()->intena = 0; |
| 474 | |
| 475 | // Process is done running for now. |
| 476 | // It should have changed its p->state before coming back. |
| 477 | c->proc = 0; |
| 478 | found = 1; |
| 479 | release(&p->lock); |
| 480 | } |
| 481 | if (found == 0) { |
| 482 | // nothing to run; stop running on this core until an interrupt. |
| 483 | asm volatile("wfi"); |
| 484 | } |
| 485 | } |
| 486 | } |
From A to B, step by step
Process A calls pause() and goes to sleep. Process B, which slept earlier and has been woken, runs next.
| Thread | What runs | Locks |
|---|---|---|
| A | sleep() acquires A's lock, sets SLEEPING, calls sched_sleep() and sched(). swtch() saves A's registers in A->context and loads cpu->context. | A's lock taken in A |
| scheduler | Its earlier swtch() returns. It sets c->proc = 0 and releases A's lock. | A's lock released in the scheduler |
| scheduler | Interrupts on and off again, so a pending interrupt is taken. sched_pick() returns B, locked. B becomes RUNNING, run is logged, c->proc = B, and swtch() loads B->context. | B's lock taken in the scheduler |
| B | B's registers were saved inside its own earlier sched(), so swtch() returns there, on B's kernel stack. sleep() releases B's lock, and B continues in sys_pause(). | B's lock released in B |
Why p->lock is held across swtch
p->state and p->context must change together. If the lock were released before swtch(), the process would be RUNNABLE while its registers are only half saved, and on a computer with several CPUs another CPU could start to run it. So the lock is acquired in one thread and released in another, as the table shows.
Holding a lock also keeps interrupts off: acquire() turns them off, and they stay off until the CPU has released every lock it holds. Without this, a timer interrupt could try to take a lock that the interrupted code already holds, and wait forever.
What sched() checks
| 488 | // Switch to scheduler. Must hold only p->lock |
| 489 | // and have changed proc->state. Saves and restores |
| 490 | // intena because intena is a property of this |
| 491 | // kernel thread, not this CPU. It should |
| 492 | // be proc->intena and proc->noff, but that would |
| 493 | // break in the few places where a lock is held but |
| 494 | // there's no process. |
| 495 | void |
| 496 | sched(void) |
| 497 | { |
| 498 | int intena; |
| 499 | struct proc *p = myproc(); |
| 500 | |
| 501 | if (!holding(&p->lock)) |
| 502 | panic("sched p->lock"); |
| 503 | if (mycpu()->noff != 1) |
| 504 | panic("sched locks"); |
| 505 | if (p->state == RUNNING) |
| 506 | panic("sched RUNNING"); |
| 507 | if (intr_get()) |
| 508 | panic("sched interruptible"); |
| 509 | |
| 510 | intena = mycpu()->intena; |
| 511 | swtch(&p->context, &mycpu()->context); |
| 512 | mycpu()->intena = intena; |
| 513 | } |
| Panic | Meaning |
|---|---|
sched p->lock | The caller does not hold p->lock. |
sched locks | The caller holds another lock as well. |
sched RUNNING | p->state is still RUNNING, but the caller must set the new state first. |
sched interruptible | Interrupts are on. |
Sleep, Wakeup and the Lost Wakeup
A process that must wait for an event sleeps: it sets its state to SLEEPING and gives up the CPU with sched(). When the event happens, other kernel code calls wakeup(chan). The channel chan is an address that names the event.
Sleeping takes two steps. sleep_prepare(chan) stores chan in p->chan. Later, sleep() sleeps only if p->chan is still set:
| 564 | // Put the thread to sleep. Assumes sleep_prepare() was called before. |
| 565 | // If the channel registered by sleep_prepare() has been woken up in |
| 566 | // the meantime, do not go to sleep, and instead return immediately. |
| 567 | void |
| 568 | sleep(void) |
| 569 | { |
| 570 | struct proc *p = myproc(); |
| 571 | |
| 572 | acquire(&p->lock); |
| 573 | if (p->chan != 0) { |
| 574 | p->state = SLEEPING; |
| 575 | sched_sleep(p); |
| 576 | sched(); |
| 577 | } |
| 578 | release(&p->lock); |
| 579 | } |
wakeup(chan) clears p->chan in every process waiting on chan, and calls sched_wakeup() for each one that is already SLEEPING. pause() shows why the two steps matter:
| 67 | uint64 |
| 68 | sys_pause(void) |
| 69 | { |
| 70 | int n; |
| 71 | uint ticks0; |
| 72 | |
| 73 | argint(0, &n); |
| 74 | if (n < 0) |
| 75 | n = 0; |
| 76 | acquire(&tickslock); |
| 77 | ticks0 = ticks; |
| 78 | while (ticks - ticks0 < n) { |
| 79 | if (killed(myproc())) { |
| 80 | release(&tickslock); |
| 81 | return -1; |
| 82 | } |
| 83 | // sched_tick() wakes us exactly when ticks reaches wake_tick. |
| 84 | myproc()->wake_tick = ticks0 + n; |
| 85 | sleep_prepare(&myproc()->wake_tick); |
| 86 | release(&tickslock); |
| 87 | sleep(); |
| 88 | acquire(&tickslock); |
| 89 | } |
| 90 | release(&tickslock); |
| 91 | return 0; |
| 92 | } |
sys_pause() must release tickslock before it sleeps, because the timer interrupt needs that lock to advance ticks. A tick can arrive between release(&tickslock) and sleep(). If that tick is the one the process waits for, sched_tick() clears p->chan, and sleep() returns at once instead of sleeping. Without the first step, that wakeup would find no process waiting, and the process would then go to sleep after its event had already happened: a lost wakeup. After an event that comes only once, nothing would ever wake it.
Each job of a test starts with the system call schedstart(), which sleeps on the same channel as pause() until the job's start tick. When that sleep ends, sched_wakeup() logs new instead of wake.
How to Prepare
- Understand each policy. For every task, be ready to say which job runs next, when the running job gives up the CPU, and why. Take a small public test, write down the log you expect interrupt by interrupt, and compare it with the test's step-by-step view in the guide.
- Follow a timer interrupt all the way to
sched(). Start from the hardware that raises it and go step by step until the CPU switches to the scheduler thread. At each step, know which function runs, what it does and which locks are held. - Trace the code yourself. For every item in the Trace Code section of
q4-spec.md, open the files and follow the calls. This page explains the paths, but the quiz asks about the code. - Compare the policies.
schedtestbuilds the same workload from the same seed on every branch. Runschedtest 42onq0toq4and compare the charts and the turnaround tables. Which jobs wait longest under each policy? How soon does a short job that arrives late finish? Which policy switches between jobs most often?