Preparing for the Lab Quiz

← Back to the Lab 1 Guide

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.

💡 No need to memorize code. The quiz tests concepts. Any code it asks about is code you meet again and again while you implement the lab.

What the quiz covers

The quiz covers the Trace Code section of q4-spec.md on branch q4, and may also cover your implementation:

  1. The two paths of a timer interrupt, and how the kernel switches between the two trap handlers.
  2. The hardware clock: how long a tick is, when the hardware raises a timer interrupt, and how clockintr() asks for the next one.
  3. 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.
  4. 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 pointTraps fromWhat it doesstvec set to it by
uservec (kernel/trampoline.S)user modesaves 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 modealready 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:

  1. In the job's own code, in user mode. The trap enters at uservec.
  2. 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 at kernelvec. 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.
  3. In the scheduler loop, because no process is RUNNABLE. The loop waits with the instruction wfi while interrupts are off, so the interrupt stays pending until the loop turns interrupts on at its top. Then it enters at kernelvec, and myproc() 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():

kernel/trap.cLines 165 to 180 in q4 · clockintr()purple = TODO
165void
166clockintr()
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.

Try itComment out the line that writes 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 stateTextbook nameMeaning
USEDNewallocproc() has reserved the entry, but the process cannot run yet.
RUNNABLEReadyCan run and waits for the CPU.
RUNNINGRunningOn the CPU now.
SLEEPINGWaitingWaits for an event, such as the end of a pause().
ZOMBIETerminatedHas exited, but its parent has not collected it with wait() yet.
PathCall chainWhat happensLog line
1 · New → Readyuserinit / kfork → allocprocallocproc() 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 → Runningscheduler → sched_pick → swtchsched_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 → Readyusertrap / kerneltrap → sched_timer → sched → swtchshould_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 → Waitingsys_pause → sleep_prepare → sleep → schedsys_pause() sets p->wake_tick. sleep() sets SLEEPING, calls sched_sleep() (the end of a CPU burst), then sched().sleep
5 · Waiting → Readyclockintr → sched_tick → sched_wakeupAt 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 → Terminatedsys_exit → kexit → schedkexit() 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:

kernel/proc.cLines 437 to 486 in q4 · scheduler()
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.
444void
445scheduler(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.

ThreadWhat runsLocks
Asleep() 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
schedulerIts earlier swtch() returns. It sets c->proc = 0 and releases A's lock.A's lock released in the scheduler
schedulerInterrupts 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
BB'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

kernel/proc.cLines 488 to 513 in q4 · sched()
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.
495void
496sched(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}
PanicMeaning
sched p->lockThe caller does not hold p->lock.
sched locksThe caller holds another lock as well.
sched RUNNINGp->state is still RUNNING, but the caller must set the new state first.
sched interruptibleInterrupts 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:

kernel/proc.cLines 564 to 579 in q4 · sleep()
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.
567void
568sleep(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:

kernel/sysproc.cLines 67 to 92 in q4 · sys_pause()
67uint64
68sys_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. schedtest builds the same workload from the same seed on every branch. Run schedtest 42 on q0 to q4 and 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?