Skip to content
All projects

Operating systems course, 2025

xv6 Kernel

Two assignments inside xv6, MIT's teaching Unix kernel. New process system calls, and a tournament-tree lock that stretches Peterson's algorithm to 16 processes, with a bracket you can watch run.

The tournament-tree visualizer with eight processes racing up a bracket of locks. P6 holds every lock on its path and is in the critical section, while P3 and P5 wait at locks below it.
  • New system calls in the kernel, including forkn, which creates up to 16 children in one call or none at all.
  • A tournament tree that turns two-process Peterson locks into one lock for 16 processes, using only the bits of each process's index.
  • An interactive bracket that runs the same algorithm step by step, checked over 12,000 random runs.

What it is

xv6 is a small Unix-like kernel that MIT wrote for teaching. It’s real enough to have processes, a scheduler, a file system and system calls, and small enough to read end to end. It runs on RISC-V, so here it boots inside QEMU.

These are two assignments from the Operating Systems course at Ben-Gurion University in 2025. The first, new process system calls, was mine alone. The second was a pair assignment on synchronization: my partner wrote the kernel’s Peterson lock, and I wrote the tournament tree that builds on it.

New system calls

A system call is the one doorway from a user program into the kernel, so adding one touches every layer: the user-space stub, the dispatch table, argument fetching and the kernel code itself.

forkn(n, pids) creates n children in a single call. Each child gets a number from 1 to n back, so it knows which part of the work is its own. The parent gets every child’s PID. The interesting part is failure: every child is fully prepared first and only marked runnable once all of them exist. If the eighth one can’t be created, the first seven are freed before any of them ever runs.

waitall is the other half. It sleeps until every child has exited, then returns all their exit statuses at once.

Exit messages. exit now takes a short message as well as a status, and wait hands it to the parent. The message has to be copied twice: from the dying child into the kernel’s process table, then out into the parent’s memory, because by the time the parent asks, the child’s address space is gone.

bigarray puts it together. It splits the sum of 65,536 numbers across six children made by one forkn, and each child returns its partial sum as its exit status. The parent collects them with waitall.

A test program checks every error path, including the all or nothing promise: with only 10 free process slots, forkn(16) must fail and forkn(10) must still work. GitHub Actions boots the kernel in QEMU and runs it on every push.

One lock for 16 processes

Peterson’s algorithm is a lock for exactly two processes that needs nothing but shared memory. Each side raises an “interested” flag and records that it arrived last. A side waits only while the other one is interested and it’s still the last to have arrived.

To share one lock among 16 processes, my part builds a knockout bracket out of these two-process locks. The 15 locks form a binary tree. Each process starts at a lock at the bottom, and only the winner of each lock moves up to the next. Whoever wins the root lock is in the critical section.

Sixteen processes mid-run: P3 holds all four locks on its path and is in the critical section, while the others contend for locks below it.

A process’s path is written in its index. No table says which lock a process uses at each level or which side of it is its own. Both come from the bits of its number: shift the index right to find the lock, and read one bit to get the side, the highest bit at the root and the lowest at the leaf. Process 5 (101 in binary) in an 8-process tree plays side 1 at the bottom, side 0 one level up and side 1 at the root.

Up to take, down to give back. A process takes its locks from the leaf to the root and releases them from the root back down.

The visualizer

The bracket runs the same algorithm in the browser, and its code sits in the same repo as the C it simulates. A random scheduler picks one process at a time to take a single step, which is how real processes interleave. You can watch flags go up, see who arrived last at each lock, and follow any process to see its bits choose its path.

Before trusting it, I ran the simulation 12,000 times with different random schedules: 3,000 runs each for 2, 4, 8 and 16 processes. Every run finished, every process got into the critical section exactly once, and no run ever had two processes inside at the same time.

Getting the error paths right

In a kernel, the code that runs only when something fails matters as much as the code that runs every time, and it’s the part normal runs never test. Three error paths needed particular care:

  • Release locks before anything can fail. waitall holds the kernel’s wait_lock while it collects exit statuses, and copying the results out to the parent can fail. It releases the lock before any copy can fail. Otherwise the next wait would try to take the lock again and stop the whole kernel with panic: acquire. A test passes a bad pointer on purpose to prove it.
  • Keep the IDs you were given. The tournament tree doesn’t assume the kernel hands out lock IDs 0, 1, 2 and so on, which only holds when no other lock exists. It stores the IDs it actually got.
  • Undo everything on failure. When forkn gives up halfway, the children it prepared already hold references to the parent’s open files and directory. The cleanup drops them before freeing the children, so a failed call leaves nothing behind.