Keeping the box alive: PiROS scheduling & preemption

A build log of one optimisation thread in PiROS — from a purely cooperative scheduler to hardware-timer preemption — written to be read, argued with, and added to. It is deliberately honest about the dead ends, because the dead ends are where the learning is.

What problem is this really about? An operating system runs many things at once on one CPU. If one of those things gets stuck in a loop and never voluntarily gives the CPU back, does the whole machine freeze — console, network, everything? On a server you never want the answer to be "yes." This document is the story of making the answer "no," and of discovering that "no" is harder than it looks.

Glossary

Written for the range from curious hobbyist to systems engineer. Skim it, or jump back when a term bites.

• Kernel — the core of the OS that owns the hardware and arbitrates between programs. It is the only code allowed to touch the raw machine.
• Ring 0 / Ring 3 — the x86 CPU's privilege levels. Ring 0 is fully privileged (the kernel). Ring 3 is unprivileged (user programs / "tools"). A ring‑3 program that tries a privileged instruction is trapped and killed rather than allowed to hurt the system.
• Process vs. task — in PiROS a task is a unit the scheduler can run. Some tasks are kernel tasks (they run kernel code — e.g. the serial console, the SSH server). A process is a task that also has its own address space and runs a sandboxed ring‑3 program (a spawned service). The distinction turns out to be the whole ballgame later on.
• Address space — the private map of "virtual address → physical memory" a program sees. Each process gets its own, so one program cannot even name another's memory. Switching between address spaces means reloading the CPU's page‑table pointer, CR3.
• CR3 — the x86 register holding the physical address of the current address space's top‑level page table. Writing CR3 switches the whole memory view. Cheap to write, but it flushes cached translations, so it isn't free.
• l4 / PML4 — the top‑level page table (Page Map Level 4). In PiROS each task records its l4: l4 == 0 means "kernel address space" (a kernel task), and l4 != 0 means "this process's own address space." You will see l4 == 0 and l4 != 0 used constantly below as shorthand for "kernel task" vs. "real process."
• Context switch — saving one task's CPU registers/stack and loading another's, so the CPU resumes the second task exactly where it left off. The primitive that makes multitasking possible.
• Scheduler — the kernel code that decides which task runs next and performs the context switch.
• Cooperative scheduling — tasks keep the CPU until they voluntarily call yield, typically because they'd otherwise block waiting for I/O. Simple, lock‑friendly, and a perfect fit for polled I/O — but a task that never yields starves everything.
• Preemptive scheduling — a hardware timer interrupts the running task and hands control to the scheduler whether the task likes it or not. This is what stops a runaway from freezing the machine.
• Quantum — the slice of time a task is allowed to run before the timer preempts it.
• Runaway / hung process — a task stuck in a loop (or wedged) that never yields. The thing preemption exists to survive.
• Interrupt — a hardware signal that makes the CPU stop what it's doing, jump to a handler, and (usually) return afterwards. The timer raises one periodically.
• IF flag — the CPU's "interrupts enabled" bit in the FLAGS register. When IF = 0, maskable interrupts (like the timer) are held pending, not delivered. PiROS runs kernel code with IF = 0 and ring‑3 code with IF = 1 — so the timer only ever fires while a user program is running, never in the middle of kernel code holding a lock. This single design choice shapes everything here.
• iretq — the x86 "return from interrupt" instruction. It atomically restores the saved registers and (for a return to ring 3) re‑enables interrupts and drops privilege. The exact instant a pending interrupt can pounce.
• Syscall — a controlled doorway from a ring‑3 program into the kernel (in PiROS, the int 0x80 software interrupt). How a tool asks the kernel to read a file, write output, exit, etc.
• PIT (8254) — the legacy Programmable Interval Timer. A simple chip that raises an interrupt at a fixed frequency. Periodic: it fires on a fixed cadence and you cannot easily stop a single tick.
• LAPIC — the Local Advanced Programmable Interrupt Controller, built into every modern x86 core. Among other things it contains a far more flexible timer than the PIT.
• One‑shot vs. periodic timer — a periodic timer re‑arms itself and keeps firing. A one‑shot fires exactly once and then disarms itself until you deliberately re‑arm it. The difference between the two is the hinge this entire story turns on.
• TSC‑deadline mode — a LAPIC timer mode where you write an absolute future value of the CPU's cycle counter (the TSC) and the timer fires once when the counter reaches it. The cleanest possible one‑shot. Present on real hardware; not emulated by QEMU's software CPU.
• EOI (End Of Interrupt) — the acknowledgement you must send to the interrupt controller so it will deliver the next interrupt. When you send it, relative to a context switch, matters enormously.
• Pending interrupt — an interrupt that has been raised by hardware but not yet delivered because IF = 0. It is latched and will fire the instant IF becomes 1. The villain of the second half of this story.
• Livelock — not a crash and not a deadlock: the system is "busy" and making interrupt after interrupt, but no useful forward progress ever happens. A task that is preempted at its very first instruction, resumed, and immediately preempted again, forever.
• QEMU / TCG — QEMU is the machine emulator PiROS is developed on. TCG is its pure‑software CPU (used when no hardware acceleration like KVM/HVF is available, e.g. on a Mac). TCG faithfully emulates most of the CPU — but not every optional feature, which becomes a plot point.

Where we started: cooperative, on purpose

PiROS began life single‑core with a cooperative scheduler, and that was a considered choice, not a shortcut.

Almost everything PiROS does that could block — reading the serial console, accepting a TCP connection, waiting for a disk sector — is polled. The natural shape of polled I/O is: check if the thing is ready; if not, hand the CPU to someone else and try again later. That "hand the CPU to someone else" is exactly a cooperative yield. So the servers (the SSH daemon, background services) yield precisely when they would otherwise be waiting, and the console gets its turn. No timer, no locks held across switches, no re‑entrancy hazards. For an I/O‑bound system it is simple and it is correct.

The alternative we deferred: full preemptive scheduling from day one. We rejected it early because preemption drags in real complexity — chiefly, an interrupt can now land in the middle of kernel code, so any lock a preempted task was holding can deadlock the task that preempts it. The cooperative model sidesteps that entirely (a task only ever switches at a point it chose, where it holds no locks). We wrote the design note to ourselves at the time: "Real fix = timer preemption, but mind the locks."

The flaw we knew we were accepting: one CPU‑bound task that never yields freezes the entire box. Cooperative scheduling has no answer to a runaway. And a "provable‑runtime" OS whose selling point is that it safely runs other people's signed code cannot have "one bad loop takes down the server" as a known failure mode. So preemption went on the list — with eyes open.

The goal, stated plainly

A hung or runaway program must not be able to kill the machine. You should still be able to reach the box — console or SSH — and, ideally, stop the offender.

Everything below is in service of that one sentence.

First move: partial preemption with the legacy PIT

The first working step used the PIT, the simplest timer available, at ~100 Hz. Because PiROS runs the kernel with IF = 0, the timer only ever fires while a ring‑3 program is executing — never inside kernel code — so a timer‑driven context switch can never interrupt a lock holder. That property is what made preemption tractable at all.

But we did not enable it for everything at once. We enabled it only for kernel‑context tasks (l4 == 0): the console, the SSH server, and the short‑lived tools they run inline. Preempting those is safe because resuming them needs no address‑space switch. We explicitly skipped preempting real processes (l4 != 0), because early testing showed that preempting a spawned process left it "never advancing past its entry" — a symptom we didn't yet understand. The guard was a single line: preempt only if this isn't a real process.

Why ship a partial fix? Because it already bought something real and testable: a runaway tool typed at the console could no longer freeze the box. We proved it — set a deliberate infinite‑loop program spinning on the console, and the SSH server still answered a login on the network. The box stayed alive under a runaway. That was genuine progress, and shipping it kept the change small and the failure surface understood.

What we left broken, and admitted to: a runaway process — a spawned service, l4 != 0 — would still freeze the box, because we weren't preempting it. That was the boss fight, and we named it as the remaining work.

The boss fight: why a preempted process "never advanced"

Turning on preemption for real processes reproduced the old symptom immediately, so we stopped guessing and instrumented it. A deliberate runaway was spawned as a genuine process and every single preemption of it was traced.

The findings were sharp and, at first, baffling:

• The box did not crash. The console still answered ps; the SSH server still answered logins. So nothing was being corrupted in a destructive way — an important clue that ruled out a whole class of theories.
• The process was wedged at its very first instruction. Its instruction pointer was frozen at the program's entry point (_start, a push that sets up the stack), and every preemption — we watched hundreds in a row — caught it at that exact address. It printed zero output. It never advanced one instruction.
• No page fault. No exception. The resume was via the normal context‑switch path, not a re‑entry from scratch.
• One oddity in the saved CPU flags: the RF (Resume Flag) was stuck set — the bit the CPU uses when it is about to re‑attempt an instruction it was pulled off of.

Putting that together: the process returned to ring 3 with a perfectly valid register state, and then a timer interrupt fired before it could execute a single instruction — every single time. That is a textbook livelock: resume → instant re‑preempt → resume → instant re‑preempt, forever, all at the entry point.

We ruled out, with evidence, several tempting explanations:

• Signature/verification loop. A collaborator's excellent hunch was a circular dependency — a check waiting on the thing it's checking. We chased it and cleared it: PiROS verifies a program's signature once, at spawn, and caches the result; nothing re‑verifies on a context switch. The instinct ("something is waiting on itself") was directionally perfect, though — it is a livelock, just at the CPU/interrupt level rather than a software lock.
• Address‑space corruption. The saved frame was sane (correct ring‑3 code segment, a valid user stack pointer). Not corruption.
• A slow address‑space switch. The CR3 write is a single instruction; not the stall.

So the code looked correct. The bug was a runtime timing detail, and printf‑tracing had taken us as far as it could.

The two questions that cracked it

The breakthrough came from two pointed diagnostic questions:

1. What mode is your timer in — periodic, one‑shot, or TSC‑deadline? **2. Are you writing the End‑Of‑Interrupt at the start or the end of your handler?**

The answers, read straight from the code, were: the PIT, periodic, with EOI at the very start of the handler, before the context switch. And that combination is the livelock.

Here is the mechanism, spelled out:

1. The timer fires. The handler immediately sends EOI — telling the interrupt controller "I'm done, you may deliver the next one" — and then performs a context switch to another task.
2. But the PIT is periodic and free‑running. It keeps ticking throughout the switch and throughout the other task's run.
3. Because the kernel runs with IF = 0, one of those ticks gets latched as pending.
4. When we finally switch back to the preempted process and it executes iretq to return to ring 3, IF becomes 1 — and the pending tick is delivered that instant, before the process runs one instruction.
5. Go to 1.

This also explained a note left by an earlier attempt: "tried moving EOI to the end of the handler — didn't help." Of course it didn't. The handler switches stacks in the middle (it resumes a different task), so the EOI that eventually runs belongs to a different task's handler than the interrupt that's pending. A periodic timer plus a stack‑switching interrupt handler cannot keep the interrupt‑to‑EOI pairing straight. You cannot fix this by moving one write. The periodic model is the problem.

Crucially — this was not the CR3 switch, not memory corruption, not the verification system. It was the shape of the clock.

The fix: make the clock a one‑shot

The cure follows directly from the diagnosis. Replace the periodic PIT with the LAPIC timer used as a one‑shot.

A one‑shot timer fires once and then hardware‑disarms itself. It physically cannot tick again — cannot latch a pending interrupt — until we deliberately re‑arm it. So it cannot fire during a context switch. We re‑arm it only when a task is about to run, EOI to the LAPIC, and the resumed task always gets a genuine, full quantum of forward progress. The livelock's fuel — a stray pending tick generated while we were busy switching — simply stops existing.

Two flavours of one‑shot, chosen automatically at boot:

• TSC‑deadline mode where the CPU advertises it (real cloud hardware): arm by writing an absolute future cycle‑counter value. The cleanest form.
• LAPIC initial‑count mode everywhere else: arm by writing a countdown value that decrements a divided bus clock to zero.

Why the fallback isn't optional. We discovered — by probing CPUID on the running machine — that QEMU's pure‑software CPU (TCG, which is what you get on a Mac with no hardware acceleration) reports tsc-deadline = false but x2apic = true. TCG simply doesn't emulate TSC‑deadline. So the dual path is not belt‑and‑braces: it's the difference between the development/CI environment working at all and not. The cloud box gets TSC‑deadline; the emulator gets the initial‑count one‑shot; both are one‑shots, so the livelock fix holds either way.

A couple of gotchas were paid in blood along the way, and are worth recording:

• The LAPIC lives in memory‑mapped I/O at physical 0xFEE00000. Reaching it needs the kernel's direct map of physical memory, which only exists after memory initialisation. Our first attempt armed the timer too early in boot and faulted on the raw physical address. Fix: move timer setup to run after memory::init.
• The LAPIC's "spurious" interrupt vector must have a handler that does nothing (and, specifically, must not be acknowledged with an EOI). One tiny handler, added.

The result, measured: a runaway spawned as a real process went from zero forward progress (wedged at its entry) to actively running — it emitted 8,694 progress heartbeats where before it emitted none — while the box stayed fully responsive. The console answered ps in well under a second, and a complete SSH login (with its TLS‑grade handshake and crypto) succeeded, over the network, while the runaway burned an entire core. The core goal — a runaway service can't kill the box — was, for processes, met.

The twist: tuning the quantum, and finding a hole

With process preemption working, an obvious follow‑up: tune the quantum down for snappier response, and re‑measure.

The measurements were the first surprise:

Identical. Shrinking the quantum 100× changed nothing. The reason is instructive: under this workload the cadence is bounded not by the timer at all but by the cooperative round‑robin itself — specifically by kernel tasks (the idle SSH server) busy‑waiting before they yield, rather than sleeping the CPU. The timer quantum is simply not the responsiveness knob here; the busy‑wait is. (That's a separate, known piece of debt: idle should hlt the CPU or be interrupt‑driven, not spin.)

That would have been a tidy, mildly disappointing finding — "tuning doesn't help, the box is already sub‑second" — except that chasing why dragged a much more serious problem into the light.

The regression. To test responsiveness we finally ran the most basic thing imaginable — an actual console command that finishes and exits (echo, ls, cat) — and it hung the shell. Worse, it hung on the exact commit we'd already published as "validated."

How had that slipped through? Because none of the earlier tests had ever run an exiting console tool. The runaway used for testing is an infinite loop — it never exits. ps and whoami are kernel builtins, not ring‑3 tools. So the one everyday case — load a small program, run it to completion, return to the prompt — had genuinely never been exercised under the new preemption. That is a real testing lesson, recorded here rather than hidden: your regression suite has to include the boring path.

Tracing it showed the same fingerprint as the original bug — a console tool wedged at its entry (push %rbx), preempted 200+ times, never advancing — but with a critical difference: it happened for kernel‑context tasks (l4 == 0) and not for real processes (l4 != 0, which now resumed cleanly). The immediate‑re‑preempt livelock had a second home we hadn't found, and it lived in the exact category of task — the console — you least want to freeze.

What we tried, and what it cost

Being honest about the dead ends, because they narrow the search for whoever picks this up next:

• **Re‑arm before the switch → re‑arm after the switch.** The theory: the countdown was being spent during the switch, so start it when the task actually resumes. Sound reasoning; didn't fix it.
• Arm only at the ring‑3 boundary. Disarm the timer on entering the kernel (so kernel time never counts), and arm it only at the three points where control actually returns to ring 3 (entering a fresh tool, returning from a syscall, resuming after a preemption), never on a plain cooperative yield. The cleanest model of "the timer is a stopwatch for ring‑3 CPU only." Still didn't fix the l4 == 0 case.
• A very large quantum (1,000,000). If the pending tick is a race against the switch, a big enough quantum should win the race. It did for processes; it did not for console tools — they wedged even at the largest quantum. That was the decisive data point: for l4 == 0 this is not a quantum‑size race and not a re‑arm‑timing bug. It is something more specific about how a pending LAPIC tick is delivered at the ring‑3 iretq for a kernel task — and pinning it down needs a single‑stepping debugger (gdb against QEMU), not more print statements.

Two hypotheses were also cleared by inspection, so nobody re‑runs them: the console task's trap stack does not overlap its own execution stack (they are separate dedicated stacks), and there is no page fault involved.

Where it stands now, and the honest trade‑off

We stopped digging on the root cause and shipped a decision that is defensible on its own terms:

Preempt only ring‑3 processes (l4 != 0). Leave kernel‑context tasks (l4 == 0) cooperative.

The reasoning is more than damage control — it's arguably the right design:

• The console and the SSH server are trusted, cooperative code that yields on I/O. They are not the thing that runs away. Not preempting them is fine, and it makes console tools work again (verified: echo > file, cat, ls, ps all complete normally).
• A spawned service is the untrusted, potentially‑runaway code that this whole effort exists to contain — and it is preempted, and it survives (SSH login completes while a runaway process burns CPU).

The cost, stated without spin:

So we traded the console‑runaway case (rare: a human typing a broken loop into the shell) for the service‑runaway case (the real operational concern) — and, along the way, un‑broke the everyday tools that a bad "preempt everything" had silently taken down.

Open threads, kept on the record:

1. The l4 == 0 immediate‑re‑preempt root cause. A pending LAPIC tick delivered at the ring‑3 iretq before a kernel‑hosted tool executes. Cracking it (with gdb) would restore full coverage — console runaways included — with no trade‑off.
2. Real responsiveness. The lever isn't the quantum; it's replacing the idle busy‑wait polls with hlt / interrupt‑driven wakeups. That's the change that would make the box feel instant under load.

Lessons worth keeping

• The shape of the clock matters more than its speed. Periodic vs. one‑shot was the entire difference between a livelock and a fix. We spent effort tuning a number (the quantum) that turned out to be irrelevant, while the qualitative property (one‑shot, self‑disarming) was everything.
• A "validated" build is only validated for what you actually ran. The most basic path — run a program, let it exit — was the one path never tested, and it was the one that broke. Boring cases belong in the suite.
• Emulators are not the target hardware. TSC‑deadline exists on the cloud box and not in TCG. Assuming the emulator's CPU equals real silicon would have shipped a fix that only works in production and mysteriously livelocks in CI, or vice‑versa.
• Ship the understood partial fix; name what's still broken. Every stage here left the box in a better, well‑characterised state, with the remaining hole written down rather than papered over. That's what let each step be small enough to reason about.

Update — the debugger session: the l4 == 0 livelock is fixable, and the wall behind it

We took open thread #1 into a debugger. The short version: the l4 == 0 livelock is fixable, the fix is clean — and it revealed that the real blocker to full preemption is open thread #2, the polling model, not anything about the timer hardware.

The fix for l4 == 0 is a strict LAPIC guard: the preemption timer is armed only while ring‑3 code runs. On every entry into the kernel (a context switch, a syscall) it is disarmed (initial‑count = 0); it is re‑armed only as the last act before iretq drops back to ring 3. That makes the countdown a stopwatch for ring‑3 CPU time alone, so a tick can never latch while we're parked in the kernel with interrupts off and then ambush the next task's iretq. With it in place, console tools run‑and‑exit and a console‑typed runaway is survivable — under full preemption, no trade‑off.

The wall it exposed: with l4 == 0 fixed and every ring‑3 task preemptible, a spawned process (l4 ≠ 0) that runs away made the box unresponsive again — this time by starving the interactive tasks of the core, not by a livelock. The classic two‑level "interactive‑before‑batch" scheduler (prefer tasks that yield voluntarily over ones that burn a whole quantum) kept console tools alive but did not rescue SSH under a process runaway.

So we opened the box in the debugger (QEMU's monitor — there's no gdb on the dev Mac, but info lapic and gva2gpa answer the same questions). Two natural hardware suspects, both ruled out:

The real picture: at the wedge the CPU is CPL = 0 with interrupts off, spinning in the UART receive poll — kernel code — and the timer reads initial_count = 0, i.e. correctly disarmed, because we are in kernel time. So it is not a hardware or interrupt bug at all. It is the polling model: the console (serial::receive) and the SSH server (accept) never block when idle — there is no serial or NIC interrupt, and no hlt — they busy‑poll‑and‑yield, so they are always "ready." The guard correctly confines the timer to ring‑3 time; with two always‑ready kernel busy‑pollers competing for the core, a ring‑3 process gets squeezed to nothing (a runaway hogs without fairness, or starves with it), and the box burns its wall‑clock in kernel polls.

The conclusion that redirects the work: the LAPIC guard and the two‑level fairness are both correct designs — together they proved that PiROS has no genuine idle. Until an idle console/sshd blocks (a serial‑RX interrupt, a NIC interrupt, or hlt‑with‑timer‑wake) instead of spinning, there is no clean way to give a ring‑3 process a fair slice. Interrupt‑driven / blocking idle is the real next milestone — start with the serial‑RX IRQ, the smallest piece and the one the console needs — after which the guard and the fairness scheduler slot straight in.

What shipped (v1.2.0 / r15): the conservative, verified state — preempt only spawned processes (l4 ≠ 0). A runaway service is contained (the box stays reachable); console tools are unchanged; a console‑typed runaway is the one documented gap. The full‑preemption‑plus‑fairness work is kept as a patch, waiting on blocking idle.

This page will grow as the open threads close.