Step 1 of 16

Every hart ends its boot in the same loop

At boot, hart 0 built the kernel and the other harts waited for it (Tour 3: main: one hart builds the kernel, the others wait). Then all three reached line 44 and called scheduler, which never returns. From that moment the machine has three scheduler threads, one per hart, each running on its own boot stack: add sp, sp, a0 at kernel/entry.S:17 gave hart i the 4096 bytes ending at stack0 + 4096 × (i + 1).

Calling scheduler does not change stacks. Its frame goes on the same slice of stack0, just below main’s, and since neither function ever returns, that slice is the hart’s scheduler stack for as long as the machine runs (The stacks of xv6). In this build the slices are 0x80007890–0x80008890 (hart 0), 0x80008890–0x80009890 (hart 1) and 0x80009890–0x8000a890 (hart 2). Unlike a process’s kernel stack, a slice has no guard page below it: if hart 2’s stack overflowed, it would silently overwrite hart 1’s slice.

There is no “master” scheduler and no run queue. The only shared structure is the process table proc[], and each scheduler decides for itself what its hart runs next. This is the simplest design that can work on several CPUs, and it puts all the weight on one question: what stops two harts from picking the same process?

The answer is a lock in each process, p->lock, and it is the subject of this tour.

Step 2 of 16

A scheduler belongs to one hart forever

scheduler computes c = mycpu() once and keeps it for its whole infinite life. Unlike a process, which may resume on any hart, the scheduler thread never moves: it is switched away from and switched back to only on its own hart, through c->context. So caching c is safe here, though it would be a bug in process code.

c->proc = 0 records that no process is running on this hart. myproc reads this field; anything that asks “which process am I?” while the scheduler runs gets 0.

Step 3 of 16

The struct each hart fights over

proc[] holds 64 of these (NPROC), 360 bytes each in this build, starting at 0x8000fdd0. Every scheduler reads every slot on every pass.

The comment on line 85 is the contract: state, chan, killed, xstate and pid may only be used while holding that process’s own lock. For the scheduler, state is the one that matters:

One lock per process, rather than one lock for the whole table, means hart 1 working on proc[4] never delays hart 2 working on proc[9].

Step 4 of 16

A new process becomes visible only when complete

On hart 0, pid 4 is finishing its first fork. allocproc claimed proc[4] for the child, pid 5, and marked it USED, not RUNNABLE. While kfork copied memory and open files into it, every scheduler that looked at proc[4] saw USED and walked past.

Only now, with the child complete, does kfork take the child’s lock and set RUNNABLE. This is the moment pid 5 joins the competition. The lock makes the write visible to the other harts together with everything written before it: a scheduler that sees RUNNABLE (under the same lock) also sees the finished trapframe, page table and context (memory barrier (fence)).

Step 5 of 16

The idle hart sleeps with interrupts off

Hart 1 got here on its previous pass: it scanned all 64 slots, found nothing RUNNABLE, and found stayed 0. Rather than rescan millions of times a second, it executes wfi: “wait for interrupt”. On QEMU the hart stops executing until an interrupt is pending; the spec lets wfi return early, and the loop would still be correct if it did, just wasteful.

Interrupts are off at this point (line 442 turned them off). That seems backwards: how can an interrupt wake a hart that has interrupts disabled? The RISC-V rule is that wfi resumes when an interrupt is pending and locally enabled in sie, regardless of the global sstatus.SIE bit. So the timer still wakes hart 1. The interrupt is not taken yet; it stays pending, and wfi simply finishes.

Now hart 1’s timer fires. wfi completes, the for (;;) loop goes around, and execution reaches the top of the loop again.

Step 6 of 16

Open the window, let the interrupt in

intr_on sets sstatus.SIE. The timer interrupt has been pending since the wfi, so the hart traps at once, before the next instruction (in the build, csrsi sstatus,2 is immediately followed by csrci sstatus,2, and the trap is taken between them).

Why have this window at all? The scheduler holds no locks here, and this is the only place in its own loop where it lets interrupts be handled. If every process were sleeping, waiting for a disk read or a key press, those devices’ interrupts must be able to run, call wakeup and make something RUNNABLE. A scheduler that never enabled interrupts would wait forever for a wakeup that could never be delivered to it. Line 441 is safe because noff is 0 there; an interrupt can only ever be taken at such a moment, since whenever noff > 0, SIE is off (Locks and interrupt state).

Step 7 of 16

A tick inside the scheduler does not yield

The trap came from supervisor mode, so stvec sent it to kernelvec, which saved the scheduler’s registers on the scheduler’s own stack and called kerneltrap. There is no separate interrupt stack in xv6: addi sp, sp, -256 (kernel/kernelvec.S:14) simply pushes a frame onto whatever stack sp points into, and here that is hart 1’s slice of stack0. Measured in this build with gdb:

hart 1's scheduler stack (stack0 slice, top 0x80009890)
  start         16 bytes, never popped (start left by mret)
  main
  scheduler     sp was 0x80009810
  kernelvec     256-byte register frame, sp = 0x80009710
  kerneltrap    ◄─ sp

devintr sees a timer interrupt; clockintr re-arms hart 1’s stimecmp (hart 1 does not count ticks) and returns 2.

In usertrap, a tick means yield. Here line 157 adds a condition: myproc() != 0. The scheduler is not a process. It has no p->lock to take and no p->state to set; there is nothing to yield to, since the scheduler is where yielding leads. So the tick is just acknowledged, and kernelvec returns into the scheduler at the instruction after csrsi.

Said in terms of stacks: myproc() == 0 is exactly the case “this trap landed on a scheduler stack”. A tick that lands on a process’s kernel stack (a system call in progress, Tour 8: Traps taken inside the kernel) does yield, and leaves its kernelvec frame buried in that process’s kernel stack until it is resumed. A tick on the scheduler stack is handled, its frame popped, and the scan goes on.

(Tour 8: Traps taken inside the kernel covers traps taken in the kernel.)

Step 8 of 16

Close the window before scanning

intr_off clears sstatus.SIE, and the scan runs with interrupts off. The reason is the wfi at the end of the loop. If interrupts were on during the scan:

With interrupts off, the interrupt at t2 stays pending instead of being handled, wfi at t3 returns immediately because something is pending, and the next pass handles it in the window and then finds that process.

This version of the loop dates from November 2024 (commit f7b14e5, “maybe fix a race between interrupt and wfi”). Before it, the scheduler turned interrupts on at the top of the loop and left them on during the scan (except while holding each p->lock), then turned them on again just before wfi, leaving exactly the window in the table.

Step 9 of 16

The scan, one lock at a time

The scan visits proc[0] to proc[63] in order. For each slot it takes p->lock, looks at state, and (if it is not RUNNABLE) releases the lock at line 463. That is 64 acquire/release pairs per pass, even for unused slots, because the rule (kernel/proc.h:85) is that state is only touched under p->lock: if the scheduler finds RUNNABLE, it must still hold the lock when it writes RUNNING, and the lock’s barriers guarantee it also sees everything written before RUNNABLE. Taking the lock for every slot, even unused ones, keeps the rule simple.

Hart 1 finds proc[0], proc[1] and proc[2] SLEEPING, and proc[3] (pid 4) RUNNING on hart 0. Then it reaches proc[4]. Each of these acquires finds interrupts already off (line 442), so push_off records intena = 0 and the release at line 463 leaves them off (Locks and interrupt state).

The scheduler never holds two process locks at once. That matters: the schedulers on three harts are constantly taking the same 64 locks, and a thread that held one lock while waiting for another could form a cycle with another hart doing the opposite. Holding one at a time makes deadlock among schedulers impossible.

Step 10 of 16

Two harts reach proc[4] at once

Harts 1 and 2 both call acquire(&proc[4].lock). Inside, each executes one amoswap.w.aq: atomically write 1 to locked and get the old value back. The memory system performs the two swaps one after the other, in some order. Hart 1’s swap happens to come first, gets 0, and leaves the loop: it owns the lock. Hart 2’s swap gets 1 and repeats, spinning.

This single instruction is the whole arbitration. No scheduler asks another; whoever swaps first owns proc[4] for the next few instructions, and the other waits. Tour 15: Spinlocks from the hardware up builds spinlocks up from this instruction.

Line 41 records lk->cpu = &cpus[1], which holding will later use to check ownership.

Step 11 of 16

Hart 1 claims pid 5 and switches to it

state is RUNNABLE. Still holding the lock, hart 1:

1. sets state = RUNNING (line 451), so that every later reader sees “taken”;
2. sets c->proc = p (line 452), so that myproc on hart 1 returns pid 5;
3. calls swtch (line 453), which saves the scheduler’s registers in cpus[1].context and loads pid 5’s.

Pid 5 has never run, so its context, prepared by allocproc, sends it to forkret with an empty kernel stack: context.sp is the top of KSTACK(4) (kernel/proc.c:147). Inside swtch, ld sp, 8(a1) (kernel/swtch.S:26) is where hart 1 leaves its scheduler stack for that page. The first thing forkret does is release proc[4].lock, the lock hart 1’s scheduler is holding right now. A lock taken by one thread and released by another: Tour 13: swtch and the lock handed across a context switch explains why that is the right design.

The check (RUNNABLE?) and the claim (RUNNING) happen inside one critical section. That is what makes them a single decision.

Step 12 of 16

Hart 2 gets the lock, and sees RUNNING

On hart 1, pid 5’s forkret releases proc[4].lock. Hart 2’s spinning amoswap finally returns 0. Hart 2 reads state: RUNNING. Not for it. It releases the lock and moves on to proc[5]: pid 6, made RUNNABLE by pid 4’s second fork on hart 0 a moment ago. Hart 2 claims and runs pid 6.

Here is the race the lock prevents, if state were read and written without it:

With the lock, t1 and t2 for hart 2 cannot fall between hart 1’s t1 and t2. And because the lock stays held until pid 5 is actually running (and is taken again before pid 5 stops), hart 2 can never see RUNNABLE for a process that is still on a CPU.

Step 13 of 16

A scheduler comes back and keeps its place

0.1 s later, pid 5 (spinning in user mode) takes a tick on hart 1 and yields, as in Tour 11: From a timer tick to a context switch. Hart 1’s scheduler returns from the swtch on line 453, still inside the loop iteration for proc[4]. The swtch that pid 5’s sched called put hart 1 back on its scheduler stack, at exactly the sp saved in cpus[1].context when the scheduler switched away; pid 5’s kernel stack keeps its usertrap → yield → sched frames until some hart resumes it. It clears intena (line 456: pid 5 left its own value in cpus[1], and the scheduler wants 0 so that its release leaves interrupts off, Locks and interrupt state) and c->proc, and releases the lock that pid 5’s yield acquired. found = 1.

Then the loop continues with proc[5], not with proc[0]. The scan position is the fairness mechanism. The process that just ran is now behind the scan position, so every other RUNNABLE process further along gets considered before it is considered again. When the scan reaches the end, the outer loop restarts at proc[0] (after the interrupt window; there is no wfi, because found is 1).

This is round-robin, but per hart: each of the three schedulers has its own scan position, and they move independently.

Step 14 of 16

How fair is it?

Here is one plausible run of the preempt test after all three children exist. Ticks on different harts are not synchronized, so the order is illustrative:

No RUNNABLE process can starve: a hart cannot pass a RUNNABLE slot without taking it, and every busy hart returns to its scheduler about once a tick. But each returning hart takes the next RUNNABLE process after its scan position, not the one that has waited longest, so with many processes waiting, one may wait several ticks: roughly (number waiting ÷ number of harts). In this test at most one process is waiting at a time, so the next tick on any hart picks it up.

But xv6 makes no stronger promise. There are no priorities, and no record of how long a process has run: a process that sleeps 1 ms before its tick and one that ran the full 100 ms are treated alike. When a process yields, the next scheduler to reach its slot may be another hart’s, so it can be running again almost immediately; a process that yields is not guaranteed to wait. A real operating system’s scheduler adds all of that. xv6’s job is to show the mechanism, and the mechanism is this loop.

Step 15 of 16

When the table is empty, the hart rests

Later, pid 4 kills its children and reaps them, usertests prints OK and ALL TESTS PASSED and exits, and the shell goes back to reading the console. Every process is SLEEPING. Each hart’s scan finds nothing, and each executes wfi.

Now the three harts stall, waking ten times a second for their own ticks, scanning 64 slots, and stalling again. When you type a line and press Enter, each key’s UART interrupt goes through the PLIC to whichever hart claims it; on the newline consoleintr calls wakeup, the shell becomes RUNNABLE, and the hart that handled the interrupt usually finds it on its very next scan, since its interrupt window was where the interrupt was handled.

Without wfi, xv6 would still work. An idle hart would spin through the table continuously, taking and releasing 64 locks in a loop, and an emulator such as QEMU would burn host CPU time for every idle hart (with its default one-thread-per-hart emulation, about a whole host core each). The wfi was added for exactly that reason: the commit that introduced it is titled “wfi to save CPU time on Athena”, MIT’s shared machines.

Step 16 of 16

What three independent loops add up to

The preempt test exercises everything in this tour: three schedulers, a shared table, processes that never yield on their own, and a parent that needs a CPU.

The key ideas:

• No central scheduler. Each hart runs scheduler over the same proc[]. The only coordination between harts is per-process locks.
• Ownership is decided by acquire. Testing RUNNABLE and setting RUNNING under p->lock makes “this hart runs this process” a single indivisible decision; the lock’s hand-off across swtch (Tour 13: swtch and the lock handed across a context switch) keeps it true until the process has fully left its CPU.
• One lock at a time. Schedulers never hold two process locks, so they cannot deadlock with each other.
• Interrupts only in the window. The scheduler scans with interrupts off and opens a two-instruction window per pass, so wakeups from interrupts are not lost to a badly timed wfi.
• Fair enough. Round-robin per hart, with a quantum of at most one tick (the rest of the hart’s current 0.1 s timer interval): no starvation, no priorities.