xv6 Kernel Enhancements

The problem

Stock xv6 is honest but naive: sbrk() eagerly maps every page it grants, so a process that asks for memory pays for all of it immediately whether it touches it or not. On top of that, the scheduler is a plain round-robin that treats a 12-second compute job and a keystroke-driven shell exactly the same.

Real kernels do neither. They overcommit memory, treating allocation as a promise: physical frames appear only on first touch, and they spill to disk under pressure. They also schedule by behavior, giving interactive tasks fast response while CPU hogs sink in priority. The goal of this project was to make xv6 do both, then measure the difference.

Interactive: fault your way through memory, then race the schedulers

Two demos, one per half of the project. The first is a live model of the paging state machine; every click goes through the same fault-resolution logic the kernel patch implements. The second runs one fixed workload under all four scheduling policies so you can watch the trade-offs happen.

How it works

Demand paging (paging/)

sbrk() grows the address space without eagerly mapping pages, so growth is pure bookkeeping. The cost is deferred to the first touch, where the trap handler distinguishes three kinds of fault and resolves each differently:

• Lazy-allocation fault. The page was promised but never backed: allocate a frame with kalloc(), map it, retry the instruction.
• Swapped-out page. The page exists but lives in the swap area: bring it back in (evicting something else first if RAM is full), fix the PTE, retry.
• Genuine segfault. The address was never part of the process: kill it.

Under memory pressure the oldest resident page (FIFO order) is written out to a swap area on disk and its PTE marked swapped (compiled in via -DP2_REPLACEMENT=1 -DP3_SWAP=1). A memstat facility exposes the paging counters to user space, and two user programs exercise the machinery: swapdemo allocates past physical memory to force eviction, and swapretouch re-touches swapped pages to force swap-ins.

Pluggable schedulers (schedulers/)

• FCFS: non-preemptive; picks the RUNNABLE process with the smallest creation tick (ctime), PID as tie-break. Classic convoy effect, minimal context switches.
• Round-Robin: the baseline xv6 policy, kept as the default, with timing bookkeeping added.
• CFS-like: per-task vruntime accumulates scaled runtime; the minimum-vruntime task runs next, with wakeup normalization so a task that slept for ages can't return with a tiny vruntime and monopolize the CPU.
• MLFQ: 4 queues with quanta 1/4/8/16 ticks, round-robin within a queue; demotion on a fully used slice, queue level retained across I/O sleeps, and a periodic priority boost every 48 ticks so nothing starves.

Scheduler-specific fields in struct proc are #ifdef-gated so each policy compiles cleanly in isolation (all four build under -Werror). Timing fields (ctime, first_run_time, end_time) derive response, turnaround and wait, and a readcount syscall counts bytes read since boot. Each variant is one build flag away: make qemu CPUS=1 SCHEDULER=FCFS|CFS|MLFQ, with CPUS=1 so the policies actually contend instead of everything scheduling instantly.

Measured comparison

From the original course benchmark runs (schedulertests, mixed CPU + sleep workload):

An honest caveat on these numbers: the original benchmark harness was lost from the course repo and has been reimplemented against the patch's interfaces, so freshly measured values differ in absolute terms (a re-run of RR with the reconstructed harness gives avg response 1 tick, avg turnaround 65 ticks). The remaining policies are queued for the same re-run; per-policy wait times are still to be re-measured.

Design decisions & trade-offs

• FIFO eviction, not LRU. FIFO is deterministic and trivially cheap (no access bits to sample, no aging pass), which makes the swap machinery easy to reason about and measure. The cost is real: FIFO happily evicts a hot page just because it's old. A clock/LRU approximation is the natural next step.
• Wakeup normalization in CFS. Without it, a task that sleeps a long time keeps its ancient (tiny) vruntime and, on waking, wins every pick until it "catches up", starving everyone else. Clamping the woken task's vruntime to the current minimum keeps sleepers responsive without letting them monopolize.
• The MLFQ boost is not optional. Demotion-only MLFQ starves any CPU-bound task once interactive tasks keep the top queues busy; the periodic boost (every 48 ticks) is the safety valve that bounds starvation.
• #ifdef-gated policy fields. Each scheduler's fields compile only for that variant, so a policy can't accidentally depend on another's state, and each of the four kernels builds clean under -Werror.

Honest scope

• The schedulers half is distributed as a patch against upstream xv6-riscv (commit 214bf4c, the revision it applies to with zero fuzz), kept alongside a full buildable tree.
• The original benchmark harness (schedulertests.c, readcount.c) was lost from the course repo and reimplemented minimally against the patch's interfaces. The RR variant is verified end-to-end (boots in QEMU, benchmark runs); the other three compile clean, with a full re-benchmark pending.
• Paging uses FIFO, not an LRU approximation, and all of this is teaching-kernel scale: the point is understanding the machinery, not competing with Linux's VM subsystem.

Try it yourself

# demand paging - full tree
cd paging
make qemu          # boot under QEMU
memstat            # paging/swap counters
swapdemo           # allocate past RAM to force eviction
swapretouch        # re-touch swapped pages to force swap-in

# schedulers - pick a policy at build time (CPUS=1 so they contend)
cd schedulers
make qemu CPUS=1                   # Round-Robin (default)
make qemu CPUS=1 SCHEDULER=FCFS
make qemu CPUS=1 SCHEDULER=CFS
make qemu CPUS=1 SCHEDULER=MLFQ
schedulertests     # benchmark the active policy