Scheduling

The kernel runs threads from one stride queue over every budget with a runnable thread. Each budget has a pass; the lowest pass runs next, for a slice of at most 1 ms, and running raises the pass in inverse proportion to the budget’s free weight. There is no priority: init, the steward and the drivers are scheduled by weight like everyone else. A waking budget joins at no less than the queue’s current minimum, a wake never preempts, and every run is charged, however short it is and however it ends.

Purpose

CPU is a resource like pages, and a hostile budget must not get more of it than its share, nor delay anyone else beyond its weight. The scheduler has two jobs: hold every budget to its weight whatever pattern of running, sleeping, exiting and budget churn it tries, and keep the steward and the drivers responsive enough that a person can end a session under load. It does both with one mechanism and no exceptions, so the rule that contains a hostile agent is the same rule that serves the steward.

Interface

One flat stride queue

Every budget with a runnable thread is in one queue, whatever its class. There is no priority, no second queue and no flag that jumps it. The kernel runs the queued budget with the lowest pass, and running raises its pass by its runtime times STRIDE (2^20) divided by its weight. So over any stretch in which budgets stay runnable, each gets CPU in proportion to its weight. On several harts each hart picks the lowest-pass budget that has a runnable thread no hart is running, so a budget runs on as many harts as it has runnable threads. Its stride state stays one per budget: each hart charges its own runner, under the kernel lock, to the budget’s one pass. A reconcile keeps a budget queued while any hart runs it.

The weight the queue uses is the budget’s free weight: its weight limit less what its children carved (R7 (carving)). Carving moves share to the child and never duplicates it. Weights are 32-bit and matter only relative to each other. At boot the kernel gives root 1,000,000; system gets a quarter (250,000) and users the rest less 1,000 (INIT_WEIGHT), which root keeps so that a process in it has free weight (budgets). Below that, the budget that carves a child chooses the child’s weight.

Class (system or user) decides trust, never order (budgets). A system-class server doing a user’s work waits its turn like the user.

Within a budget, threads take turns. Each pick runs the budget’s next runnable thread that no hart is running, after the one it last picked, in (pid, tid) order, wrapping. sched-round-robin holds one budget’s four threads, two processes of two, to that order on one hart: each thread notes when the CPU comes back to it after a gap of over half a slice, and over twelve rounds the four run the cycle their first runs set, in (pid, tid) order from the cursor, each once a round, wrapping, with their counts within a tenth of each other (over 100 ms, rv64: 25, 24, 24 and 24 slices, counts 589,056, 570,624, 564,480 and 568,832; rv32: 24, 24, 23 and 23 slices, counts 199,936, 201,984, 198,912 and 193,280). The code is kernel/src/sched.rs, which keeps each budget’s scheduling state in the budget’s own frame, and libs/stride, which holds the arithmetic, the ranks and the order of steps. libs/stride is #![forbid(unsafe_code)] and has no dependencies.

Preemption points

The running thread keeps the CPU until one of these:

• its slice ends: SLICE_US (1,000 µs) from its return to user mode after the pick;
• it blocks, exits, faults or is killed;
• a budget deadline fires.

Nothing else takes the CPU. A timeout expiring or an interrupt firing only makes a thread runnable; it runs when the queue next picks it. The hart timer is always armed for the earliest of the slice end, the next timeout and the next budget deadline (timer).

On several harts a timeout is answered at whichever kernel entry first comes after it is due, on any hart: a timer interrupt, another budget’s call, or kmain‘s own. That entry deschedules no runner whose slice has not ended for its own reason (its slice’s end, a block, an exit, a fault or a deadline): the woken thread first runs at a pick, an idle hart’s or one after a runner left for such a reason. sched-wake-no-preempt proves it at one hart nap by nap, each against the slice that follows it; sched-wake-no-preempt-harts judges it at two, each wake at the entry that made it, its naps’ ends stepped through the slices’ phases, and needs at least twenty of its hundred and twenty wakes answered where they could have preempted, mid-slice or at another budget’s call (57 to 101 at a call on rv64 and 65 to 74 on rv32, five runs a width alone and three with the timer’s placement, whose one hart armed for a sleeper’s timeout moves where a wake is answered run to run; the floor is a third of the least). Whether a slice ended at a timer interrupt the oracle decides itself, from the decision’s inputs the trace records (its end and now), so a slice that ends during the entry’s own expiry counts as ended, as the kernel ends it. Under icount a wake comes mid-slice on rv64 (1 to 61 across runs; 26 to 35 before the placement) but at most four times on rv32 (0 to 4), whose armed hart takes its interrupt only at its next turn, after the other hart’s call has answered the timeout; so sched-wake-no-preempt-harts-mttcg, the same program where the harts run at once, needs five mid-slice. How many come is the host’s race: 49 to 55 on rv64 and 48 to 57 on rv32 with the two harts on eight host cores (three runs a width), 41 to 74 alone on the quiet core set with the placement, 69 to 75 beside other cases, as few as 5 beside a whole bench’s load, and as few as 3 with the two vCPU threads and QEMU’s I/O thread sharing two cores, so the case runs on the quiet core set, and a read at the floor is re-run alone before it is believed. A kernel built with wake-preempts, whose timeout wake preempts the entering thread as a deadline does, fails both on both widths, in recorded negative runs (on rv32 under icount: a wake took hart 0 from budget 37).

A device interrupt only wakes too. sched-irq-wake runs a driver stand-in on the goldfish RTC’s alarm beside an equal-weight spinner, so every alarm interrupts the spinner mid-slice, and the oracle requires each device interrupt that claimed its source and woke the driver to return to the spinner, which runs to its slice’s end before the driver is picked (irq_wake_no_preempt): 60 of 60 alarms on both widths, on one hart. It also refuses a device interrupt that began no destruction and returned otherwise than to user mode. No kernel feature makes a device wake preempt, so the check’s negative is its floor: asked for 61 proofs of 60 alarms it fails, naming the 60 (a recorded run).

A budget deadline preempts whatever runs, because the destruction lifts passes and removes budgets, so the queue must be picked again. A thread that entered the kernel just as the deadline fired takes its trap again when it next runs. sched-deadline-preempt makes empty budgets due 1.3 ms ahead, one at a time, beside a spinner, so the deadlines fall at every phase of the two runners’ slices, and the oracle requires every timer interrupt that destroyed another budget by its deadline to leave for kmain with its runner requeued and the hart’s next event a pick, never to return to the runner (deadline_preempts): 94 preemptions on rv64 and 80 on rv32 over 2.5 s, every one mid-slice (the checked build’s audits after each destruction take most of the window: 78 audits, 356 ms, in the first 300 ms tried). The deadlines a runner’s own call finds due preempt it too, outside the trace’s interrupt brackets, and are not counted. Asked for 200 the check fails, naming the 94 (a recorded run).

The kernel itself is never preempted. It runs with interrupts off (sstatus.SIE clear) and takes the timer and device interrupts only from user mode or while idle, so a system call or a destruction runs to its end. Picking is done by kmain, the kernel’s own loop (PID 1). It runs its pick through a private S-mode ecall into the kernel’s trap handler, which saves kmain’s context as it saves a thread’s.

So a slice’s end picks again. When nothing is due for kmain’s expiry to answer first and no other thread of the running budget waits for a hart, the trap picks where it is (sched::repick): the stride takes the steps of the round trip through kmain, in its order (Harts::repick), the budget charged and requeued behind its equals, the entry reconciled, the queue picked. If the pick is the same budget its thread runs on, a new slice from its return, with no switch to kmain and back; if it is another budget’s thread, the trap switches into it there (sched::switch_here), with the steps of kmain‘s switch: the thread it ran made ready, the pick’s address space and thread activated, instruction fetch fenced, one return, which deschedules the budget switched from and starts the pick’s slice. Only a slice’s end that finds something due, or whose budget has another thread waiting for a hart, goes through kmain, as every one did before. The differential takes slice ends through it at 1, 2 and 4 harts and requires each to leave the queue as the round trip leaves it, its thread counted as the process table counts it there, and to pick what the model picks. The trace records the requeue and the pick, and the hart’s new runner at the return when it switched (H), no change of it when the thread ran on; the oracle counts the thread as waiting only at a slice’s end that picked its own budget again (the scheduler oracle). sched-timer-entry bounds what a slice’s end costs the kernel: two spinners and nothing else, so every timer interrupt from user mode ends a slice, and the oracle bounds their lock sections, trap to return, net of the checked build’s audits at one hart: the p99 at 2,000 ticks, the steady entry, which measures 951 on rv64 and 1,452 on rv32 (five runs a width alone, p50 949 and 1,424; 930 and 1,415 before the timer’s placement read the harts’ runners at each re-arm, 15 and 26 ticks, and 945 and 1,441 before its one-hart rule for an item whose payer runs nowhere asked every hart’s arming, 6 more: the hart timer), and the longest at 5,000, the cold first preemptions of a phase, 3,552 and 4,452 (at two harts, where icount’s one clock counts the other hart’s instructions too, they are recorded: p99 5,447 and 7,378). In a release build the slice’s end of a thread that only computes, alone on its hart, is about 4,200 kernel instructions on rv64 and 6,700 on rv32 (QEMU’s exec log), about 3.4 and 5.4 % of a hart at the 1 ms slice; through kmain it was 9,000 and 13,000. One that switches to another budget’s thread, two such threads sharing a hart, is about 7,050 and 10,600 (the same log, sched-timer-entry’s program), 5.6 and 8.5 % of a hart; through kmain it was 8,500 and 12,200.

The current minimum and ties

A budget wakes when it goes from no runnable thread to one. Its pass becomes max(own pass, floor). The floor is the current minimum: the lowest pass among queued budgets, the running ones included, each once, at the pass it was last charged. The floor only rises, and it holds while the queue is empty. So a budget that slept while others ran, or through an idle gap, comes back at the floor and not with credit it banked while away. The floor is raised only when it can have moved (a budget at it was charged or left, or wakes filled an empty queue), from ranks the queue keeps beside its slots, each written where the queue changes a queued budget’s pass or tie; the pick compares the same ranks. Neither reads a budget’s frame, which stays the record: a checked kernel audits the ranks against the frames with the marks’ audit. So a slice end’s scheduler work is under 3 µs per queued budget (2.4 µs measured in a checked build, “Charging”), the frame reads it makes being its hart’s running budget’s own.

On several harts the floor leaves out a capped budget, one whose weight’s share of the harts is more than it has runnable threads. Running every thread it has, its pass lags, and counting it would hold the floor below the budgets that share the other harts, so a waker would enter far behind them and take their harts until it caught up. The cap is found as the shares are: in descending weight per runnable thread, a budget is capped if w x H > k x W (H the harts, k its runnable threads, waiting or on a hart, W the queued budgets’ free weight), and the next is tested with the capped one’s harts and weight taken out. Only a budget capped already, or one every thread of which runs on a hart, is tested: a budget with a thread waiting for a hart is not taking the harts its weight would give it, so it stays in the floor and its weight in W. A budget a switch takes off its hart with its own thread requeued (its slice ended or it was preempted) counts that thread as running: its own requeue is no wait, but a sibling still waiting after a block is. A queued budget whose last thread just ended, which the entry’s reconcile takes out, counts for neither, unless no queued budget has a thread: then the floor rises to the lowest pass, as at one hart. At one hart no budget is ever capped. When every queued budget is capped, fewer runnable threads than harts, the floor rises to the highest of their passes instead of holding: uncontested time banks for no one, so a budget waking then cannot take the others’ harts later for time no budget wanted. A budget that stops being capped is lifted by what the floor rose while it was capped: it cannot bank what it had no thread to run. Its lift target starts at min(own pass, floor) when it is capped and follows the floor from there, so a lag it had then it keeps, and the target needs no hold while a thread of it waits: the capped budgets’ threads total at most H - 1, so they all run at once and a capped thread never waits long enough to be owed, and one lagging below the floor outranks every budget that is not capped. Without these limits a carve could cap an equal-weight victim while its thread waited behind the carver’s two on both harts, and the carve’s return lifted it to the carver’s pass, erasing what it had waited: 82 times in sched-budget-churn-shell‘s window at two harts on rv64, 7.4 ms of its hart time each, and the victim kept 398 of 1000 (568 with them). The model’s carve waiter scenario is that pattern (R12UncapForfeitsWait); heavy capped has a capped budget whose own slice ends fall inside the others’ and gain it nothing; contracts hold that a budget with no thread raises the floor to no pass of its own (R12EmptyHoldsFloor) and that a heavy budget is capped by the raise its own slice end makes (R12RequeueWaitsForCap), but not by a block while its sibling waits (R12BlockLeavesAsRequeued). With more than one hart online the queue keeps each budget’s free weight, its threads no hart runs (as the kernel’s settle counts them), its harts and the pass a lift would take it to beside its slot, counted afresh as a hart comes online and kept by no scan at one hart, so every floor raise finds the cap set in one scan, keeping the top H - 1 by w / k, linear in the queue, with no frame read but a lifted budget’s. A checked kernel audits the set, with the marks’ audit, against water-filling done its own way over every queued budget.

A pick takes the lowest rank, (pass, tie, id). At an equal pass:

1. a waker ranks ahead of a budget that was requeued;
2. of two wakers, the later kernel entry’s ranks first;
3. within one entry, the lower budget id first (ids are the kernel’s, I12 (ids never reused));
4. requeued budgets run in the order they were requeued.

The tie key encodes this. Each wake takes front - 1, and one entry’s wakes are processed in descending id, so the lowest id ends frontmost. Each requeue of a still-runnable budget takes back + 1. Both counters reset when the queue empties. Wakes are reconciled once per kernel entry: as the kernel leaves, budgets that lost their last runnable thread leave the queue and budgets that gained one wake. The reconcile visits only the budgets whose runnable state changed in the entry, with the same wakes and leaves, the wakes in the same order: each budget counts its ready threads, and a change of a process’s ready threads marks the process, whose count then moves to its budget. Leaves have no order a pick can see. Ranking later wakers first starves nobody: a waker that has run is charged, its pass rises above the floor, and it no longer ties.

bench:sched-ties runs a kernel built with the scheduling trace (R23). The bench’s own oracle (tools/testbench/src/sched_oracle.rs) rebuilds the order from the trace’s events with its own reading of the four clauses and checks every pick, keeps its own floor, and requires every pass never to fall but at a weight change, which it recomputes (the lead follows the weight). In the guest, two groups of three each wake in one entry, by one destruction each, and each group runs lowest id first. The oracle alone judges which group runs first: a slice end between the waker’s two destructions may run the earlier group before the later one wakes.

flowchart TD
    K["kernel entry: a call, an interrupt,<br/>a timeout, a slice end, a deadline"] --> D{"does the running<br/>thread leave the CPU?"}
    D -- "no: a wake never preempts" --> REC
    D -- "yes: it blocked, exited, faulted,<br/>its slice ended or a deadline fired" --> F["charge: t = rem + ticks x STRIDE<br/>pass += t / w, rem = t mod w<br/>(at least 1 tick)"]
    F --> S{"still has a<br/>runnable thread?"}
    S -- yes --> RQ["requeue behind its equals<br/>(tie = back + 1)"]
    S -- no --> LV[leave the queue]
    RQ --> REC
    LV --> REC
    REC["reconcile: each budget that gained a<br/>runnable thread wakes, highest id first,<br/>pass = max(own, floor), tie = front - 1"] --> FL["floor = max(floor, lowest queued pass)"]
    FL --> R{"a pick due: the thread left,<br/>or its slice ended?"}
    R -- no --> RUN[the hart's running thread resumes]
    R -- yes --> P["the queue picks the lowest (pass, tie, id)<br/>and runs that budget's next thread<br/>after its cursor, for up to 1 ms<br/>(at a slice's end the trap picks where it is;<br/>otherwise kmain does)"]

Figure: the pass and wake rule at one kernel entry. w is the budget’s free weight.

Charging

Runtime is counted in timebase ticks at the trap boundary. There are two ways into user mode (resuming a thread, returning from a call) and one way out (the trap handler). On every trap from user mode the kernel adds the user time since that hart’s last return to the pending runtime of the budget whose thread it ran. So no path runs user code unaccounted, whatever ends the run.

Pending runtime is folded into the pass at a deschedule, before a weight change, at a destruction, and when work is billed to a budget that is not running:

t = rem + ticks x STRIDE;   pass += t / w;   rem = t mod w      (w: the free weight)

• The remainder is exact, so a run split into pieces costs what one run would, at any weight. Without it a weight above STRIDE would round a one-tick run to nothing.
• A deschedule charges at least MIN_CHARGE (1 tick), so a run too short for the clock to see is not free.
• One fold counts at most RUNTIME_CAP (2^40 ticks), so the product fits 64 bits on rv32 and rv64 alike. The pass is a 128-bit number that is only added to and compared, so it never wraps.
• A weight change (a carve, or a carve returned) folds first, so runtime is charged at the weight it ran at, and then rescales what the budget owes to the new weight (the lead follows the weight).

Kernel time is billed as well:

• a system call’s time is its caller’s;
• an expired timeout is billed to its thread’s budget, and a deadline’s destruction as below, each with its share of the walk that found it. The timer is armed for a timeout only when its thread blocks; a wait that ends before its timeout leaves it early, and the walk that finds the wait gone is billed to that thread’s budget. The rest of an entry that found either, the timer’s own handling included, is billed to the budget it found last: the budget it interrupted pays for none of it. Each bill closes its interval at the tick that opens the next, so a bill’s own handling is in the interval after it and no part of a timeout’s expiry is nobody’s (residual risks). A timer interrupt that found neither is the budget’s its hart runs when it ends that budget’s slice, and nobody’s otherwise;
• an interrupt’s handling is billed to the owner of its device object (R5 (interrupts)), the budget it is charged to: system, which the boot charges every device to, whoever holds the handle (sched-irq-wake’s oracle requires every device interrupt that claimed its source to charge the budget the program marks, system, and lets it charge only that and, for its return, the budget it interrupted: 60 alarms charged system 286,980 ticks on rv64 and 208,903 on rv32 in the checked build, 4,783 and 3,482 each, and the interrupted spinner 19,476 and 31,488 for their returns); one with no device object, to nobody; a device interrupt that claims nothing, its source claimed first by another hart, is billed as a timer interrupt that ends no slice: the rest of it after its expiry is the budget its expiry billed last, or nobody’s, never the budget it interrupted; so is one a deadline took at its entry: the expiry every entry answers first destroyed a budget, and the entering thread gave up the hart before the controller was asked (preemption points), leaving the source pending for the next entry. The trace records it with no claim, the destruction inside it and a preempting return, and the oracle accepts a missing claim only so marked (the real steward’s two-hart traces, where a deadline passes while the other hart holds the lock, carry one or two a run; one hart’s none);
• kmain’s pick and switch into a budget are paid by the budget picked, whatever ended the run before: a block or an exit is paid by its actor, a timer entry’s handling by the budget it served, and the pick that follows by the budget it picks (a pick that cannot run leaves the next pick owing it; a pick of nothing is nobody’s);
• idle time is nobody’s.

A slice end that switches budgets costs about 0.056 ms of kernel time on rv64 and 0.085 ms on rv32 in the release build under QEMU (about 7,050 and 10,600 instructions, two spinners sharing a hart), billed to the budget picked after it: the trap, one SBI timer call, the deschedule, the reconcile, the pick and the switch, made where the trap is (preemption points), with under 3 µs of it per queued budget (the checked, traced build measures 2.4 µs per queued budget per slice end from three to seventeen queued, net of its audits, over a fixed 175 µs). At a 1 ms slice the nine spinners of bench:sched-large-weight-release do 0.91 (rv64) and 0.87 (rv32) of the useful work the 10 ms build does; the case requires 0.85, the fixed part being the rest. A count of user work still falls short of the window: in the checked build, bench:sched-share‘s three spinners count 975 (rv64) and 964 (rv32) of 1000 of what the loop’s rate alone would fill, the rest being what a slice end that switches budgets costs over a lone spinner’s, the checked build’s audits among it (the marks’ audit after about every slice end, the queue’s ranks audited with it), so the case judges each spinner’s share of what the three counted (600 of 1000 for the weight-300 spinner on both widths, against its 600; 585 and 578 of the window), not of the window. It reports the sum beside, with no verdict; bench:sched-share-release requires the release build’s sum to reach 960.

The top of a destruction returns its carve to its parent before any of the destruction’s work is billed. So the parent, often the caller of budget_destroy, pays for the destruction at the weight it has once the child is gone, not at the sliver it kept while the child held the rest. In bench:sched-destroy-billing a parent that kept 10 of 1000 destroys the child holding 990 and is back on the CPU within twice the destruction’s cost and four slices; billed at 10, it would wait for seconds.

Every destruction’s whole cost is billed to someone. For budget_destroy and budget_reap that is the caller, as the call’s own kernel time. For a deadline it is the top’s parent, after its carve returns, or the nearest ancestor with free weight above 0 if the parent has none; root always has. No part of a destruction is billed to nobody (R10 (destruction)). On a deadline the kernel names the payer once the carve is back, and bills it after the subtree is gone for everything from the walk that found the deadline. In bench:deadline-flood-billed a creator floods its own budget with empty weight-0 budgets on short deadlines: its count falls as the flood grows from 16 to 64 a round, and an equal-weight victim keeps its half. With the bill planted out, the victim fell to 137 of 1000.

The frames a call or a destruction frees are zeroed outside the kernel lock by the hart that freed them while every hart is idle (memory), and that time is part of the work: when the hart takes the lock back it is billed to the budgets that were paying when the frames were freed (the caller, the destroyer, a deadline’s payer), split by frames. No thread’s slice pays for it, since no hart zeroes on its way to user mode; a frame an allocation zeroes because it found no free one is that allocation’s own kernel time. A payer destroyed before the bill does not take its share to nobody: its destruction lifts the share to its own payer with the rest of the dying budget’s debt (R10), root’s alone excepted.

The trace checks every timer interrupt from user mode (bench:sched-timer-flood): after its expiry it charges only the budget it found last, an expired item’s or a wait’s that ended before its timeout, and with neither, only the budget it interrupted, when it ends that budget’s slice. Against 30 sleepers a microsecond apart, the same with 64 staggered budget deadlines, and two waits answered at once 15 ms before their timeouts, the victim gets 473, 473 and 477 of 1000 net on rv64 and 468, 469 and 481 on rv32, and no timer interrupt is nobody’s. The last case requires interrupts that found the attacker’s waits ended early inside the victim’s window, so the check cannot pass for want of them: 73 on rv64 and 19 to 20 on rv32. Its attacker holds no other timed wait that times out within the window: one due at every expiry walk of its process would reset the timer’s hint each slice, and a hint 15 ms ahead would never come. A sleep of a microsecond has passed before its call would block, so it arms nothing; when every call armed the timer, each such sleep made an interrupt that found nothing. With the rest of each timer interrupt billed to the budget it interrupted (timer-tail-billed, the recorded negative run), the check fails on both widths: the victim pays for the attacker’s waits that ended early.

A server that works for a caller spends its own budget’s CPU: no time is donated (Residual risks). CPU charging is separate from page charging (R6 (charging)). The model charges runtime, and three kinds of kernel work billed to a payer: a deadline’s destruction (R12DeadlineWorkUnbilled), a timer’s expiry of the timeouts it ends (R12TimerWorkUnbilled), and the pick and switch into a budget (R12SwitchBilledToPrevious). Billing other kernel work is the kernel’s alone, and the boot cases are its only check.

Against threads that each run nine tenths of a slice and exit, beside a main thread polling on a 1 ms timeout (sched-exit-churn‘s first share), the victim got 439 of 1000 net on rv64 and 432 on rv32 while it paid the pick and switch at each of its own slice ends, about 90 µs at the 1 ms slice, a tenth of what it was charged, and while each expiry of the attacker’s poll left about 50 µs, its bills’ own handling, to nobody. Billed as above it gets 492 and 487.

Inheritance

A child budget enters at e = max(floor, parent's pass), and keeps e as its entry. A running parent is charged first. So a child never starts behind the parent it came from, and making a child buys no turn.

When a budget is destroyed (R10 (destruction): descendants first, bottom-up), its own work since entry moves to its parent:

W = (pass - max(e, floor))+ x w_child + rem_child
parent's pass = max(parent's pass, floor) + W / w_parent      (the remainder carried)

w_parent is the parent’s free weight after the child’s carve has returned. A parent below the floor starts from the floor, without its remainder: it cannot bank what it did not run. Only work after entry counts, so creating and destroying a budget that never ran moves nothing. The child’s debt adds to the parent’s own lead instead of hiding under it, so a parent that spins and churns children pays for both.

bench:sched-budget-churn runs a churner that creates a weight-1 child, lets it run a slice and destroys it, over and over (blocked, spinning, by a deadline, and through fresh intermediates), against an equal-weight victim who keeps half; the oracle recomputes every lift from the trace. Its last variant, a shell that keeps giving a child half its weight and taking it back with no run between, leaves the victim at least half, and the recomputed lifts show that creating and destroying moved nothing. Its victim’s share has no ceiling: the shell pays at its halved weight for what it runs while carved, its own calls included (running while carved down), so how far above half the victim gets follows the kernel’s speed.

Running while carved down

A budget that runs while most of its weight is carved away accrues its lead at the small weight it kept, and owes that runtime at whatever weight it has later (the lead follows the weight). A destroyed child’s work is lifted at the child’s weight at its destruction, whatever the child kept while it ran. That only over-charges the budget that carved; it never under-charges, so no share is gained by carving. In bench:sched-carve-inflation a spinning budget that carves spinning children, one deep and four deep, gets at most half against an equal victim.

A budget that holds a process keeps free weight above 0. A carve that would take its last free weight gets InvalidArgument, and so does process_create into a budget whose weight is all carved (R7).

The lead follows the weight

What a budget owes is runtime, and a weight change keeps it exactly. Every weight change, a carve and a carve returned alike, folds at the old weight and then converts the budget’s lead and remainder to the new weight, the same way a lift converts a child’s work:

W = (pass - floor)+ x w_old + rem
pass = floor + W / w_new;   rem = W mod w_new

So a carve raises the lead by the ratio of the weights and its return lowers it by the same ratio, and a carve returned with no run between leaves the budget where it was. If the carve raised the floor (the budget had the lowest pass), the return converts from the higher floor and the budget ends a little higher: over-charged, never ahead. Both directions are needed: rescaling only on a return would let a budget carve just before a burst and return just after, and its lead would shrink at the return without having grown at the carve. A budget at or below the floor owes only its remainder, and waking would lift it to the floor anyway. At a destruction the carve returns first, so the parent’s lead is converted before the child’s work is lifted onto it at the parent’s restored weight (inheritance). A budget at weight 0 holds no process, and what it owes is stated at weight 1 meanwhile, so it is carried exactly through 0: carving everything away and then getting back only part of it is the same as the one carve from the old weight to the new.

libs/stride’s rescale is the conversion; the model makes the same one, and the bench’s oracle recomputes every weight change a traced kernel records, the one place it lets a pass fall. A host test checks that a carve and its return leave pass and remainder unchanged. In bench:sched-carve-return a budget of weight 1000 carves 999 away at the start of a slice, runs on the 1 it kept until nine tenths of the slice into it, and takes the weight back: from then on it gets 496 to 499 of 1000 against an equal victim. With the remainder alone rescaled, as before, it got 0.

Responsiveness

No wake latency follows from weight. Unless a hart is idle, a wake waits out a running thread’s slice, a waking budget keeps a pass above the floor if it has one, and several budgets can tie at the floor. So wakeup is prompt but not bounded, and responsiveness is a measured target under a named workload, not a bound derived from the queue.

The workload (tests/programs/src/bin/sched-latency.rs): a driver stand-in (weight 1000, from system) that waits for the goldfish RTC’s alarm interrupt; a steward stand-in (1000, from system) that sleeps on timeouts, destroys leases by hand after a timeout (its decision) and waits for other leases’ deadlines; and N spinning sessions of weight 100 from users, for N = 1, 4 and 16. At N = 16 a spinning server of weight 1000 joins them. Each run takes 200 wakes and 50 destructions of each kind, on QEMU, on rv64 and rv32.

Targets are guest instructions. The case runs under -icount shift=3,sleep=off with the RTC on the same clock (-rtc clock=vm; tests/sched-latency.toml): every guest instruction advances virtual time by 2^3 ns, and idle time skips to the next timer deadline. So 1 ms is 125,000 instructions, and each target below is that many instructions; the milliseconds are for reading. Host load does not change a result.

Targets exclude the checked build’s audits. The case is a checked build, since the trace needs one (R23). A checked build runs full audit scans after each destruction and at each process-object free, and a release build compiles none of them. It also checks the reconcile’s marks. Each reconcile asserts that every budget it visited is queued exactly when it has a ready thread. At most once a slice, and whenever the hart is about to idle, a full walk of every live process must find the runnable budgets the marks hold. So a mark missed in one entry is found within a slice of the next reconcile that visits a budget, or at the next idle. A miss that a later change undoes before then is not seen, and costs a budget a turn late or lost, never a wrong thread run. Each target counts the kernel a release build runs, a share as well as a window, so an audit neither fills a window nor moves the schedule. The audit time inside each window, a share’s included, is subtracted, from the trace’s audit records, and reported beside it (checked builds). The scheduler does not see an audit either: its time is charged to no budget, and its hart’s running slice’s end and the start of the kernel time being billed both move forward by its length, so the thread that ran it is picked and preempted as in a release build (sched::audit). With two full handle tables live, the audits are about 24 ms after a destruction and 8 ms at a free.

Measured at seed 3 with the 1 ms slice in the checked, traced build, p99 in µs, net / gross (audit time inside the windows): the audits hold the deadline notice, which waits out the audit after its own destruction, and little else. They are the sixth sweep’s seed 3, the seed the gate pins; the earlier sweeps’ figures stay as measured.

The run’s 49,535 audits total 12.7 s (rv64), and its 50,037 total 15.3 s (rv32), of the hart; R10 itself has none inside it, which the oracle asserts. Beside each destruction’s R10 time the oracle reports its threads’ time: the processes’ threads ending inside it, their pumps included (the trace’s T and t records), at seed 3 a p99 of 54 µs on rv64 and 60 µs on rv32. In the containment gate, with two full leases live at a deadline’s end (seed 13, at one hart), the deadline notice’s p99 is 25,794 µs net and 95,579 µs gross on rv64, with 1,158,114 µs of audit inside its windows, and 26,197 µs net and 97,703 µs gross on rv32; the sweep is on containment. With the audit after a destruction left unstamped (audit-unstamped, the recorded negative run), it is 84,710 µs net on rv64: the target misses, since the oracle subtracts only what the trace shows it. With each audit’s time billed to the budget that ran it and counted against its slice (audit-billed, the second recorded negative run), it is 44,761 and 45,577 µs net: the target misses. The steward stand-in spends its slice on the audit at the first killed notice, is requeued, and the victim and a hostile budget run a slice each before it takes the second.

A share is judged from the same trace: what the kernel charged the budget in the window, against what it charged every budget, never a count, since under icount a count is the machine’s instructions (checked builds). An audit is charged to no budget, so every share is net of the audits, and on several harts net of the lock waits too. In a checked build only, a hart’s wait for the kernel lock behind another hart’s audit is billed to no one either, and the waiter’s slice’s end moves by it (the trace’s y). That changes the schedule as well as the bill: an excused waiter keeps its slice, stays on its hart and meets the next audit. At two harts deadline-flood-billed-traced’s victim, whose creator’s destructions each run a 20 ms audit, moved from 875 to 413 of 1000 on rv64 with it, from one mode of its share to the other; with the lift target (“The current minimum and ties”) it kept 482 to 877, by where the destructions landed; with a destruction armed on the creator’s hart it keeps 919 to 924 or 507 to 530 under icount, by which hart’s entry first reaches a deadline that passed during the destruction before it, and 762 to 802 where the harts run at once (residual risks, timer). Each is owed its water-filling share, which at one hart is its weight’s; the victims of churn, floods and gaming are owed at least theirs. Measured at 1 ms in the checked build, of 1000, rv64 / rv32:

sched-large-weight‘s users and sched-server-busy judge a ratio of counts between budgets alike, which the machine’s rate leaves as it is: the least user gets 992 and 988 per 1000 of the users’ mean, against a floor of 900, and the server’s work for A is 351 and 363 per 1000 of the users’ mean (one hart, rv64 then rv32).

The gate runs one pinned seed. The guest’s boot RNG seed decides the PIDs the kernel draws, which shift instruction counts and so the phase of every later event; with it pinned, a run repeats exactly, and the case prints the seed so that a failure replays. One seed hides the spread, so a sweep of about 16 seeds measures it. A target that the stride rank decides (how many spinners’ slices a waking budget with a lead lands behind) is the sweep’s worst case plus a stated margin. The sweep’s seeds and worst case are recorded here with the target they set.

In instructions: 15 ms is 1,875,000, 25 ms is 3,125,000, 30 ms is 3,750,000, 40 ms is 5,000,000, 50 ms is 6,250,000, 95 ms is 11,875,000, 125 ms is 15,625,000, and one 1 ms slice is 125,000.

At 2 harts the targets above are gated; at 4 they are recorded (gate_harts). Under icount with several harts the clock counts every running hart’s instructions: the harts take turns on one host thread, so a millisecond is still 125,000 instructions, now of the whole machine, and a hart that halts gives its turns to the others. Measured at the pinned seed 3 in the checked, traced build, p99 in µs, net / gross:

Every target is met at two harts on both widths, and over a 16-seed sweep there too: the worst net p99s over the sweep’s N = 1, 4 and 16 are, rv64 then rv32, 11.5 and 13.0 ms for the driver wake, 18.2 and 26.5 ms for the steward timer wake, 6.8 and 13.7 ms for its decision wake and 5.4 and 12.0 ms for the deadline notice, and a lease’s end at most 9.8 and 16.6 ms; the worst p50 is 7.2 ms (rv32’s timer wake at N = 16). At four, every p99 is met, and one p50 is not: rv32’s driver wake at N = 16, 17.2 ms against 15 ms; rv64’s is 12.6 ms. At four harts a wake can wait for the kernel lock behind three sections (residual risks). sched-lock-contention holds the lock’s order under R12’s costliest call at two and four harts, and gates the driver’s wake there, both targets at two harts and the p50 at four (R78).

A slice end adds its own kernel time (charging). In the release build that is about 7,050 instructions on rv64 and 10,600 on rv32 when it switches budgets (4,200 and 6,700 when the same thread runs on), so a 1 ms slice takes about 1.06 ms and 1.09 ms on the hart with two runnable budgets, each further queued budget adding under 3 µs. The checked, traced build takes longer, its slice end growing by 2.4 µs per queued budget net of its audits: the median gap between slice ends, the marks’ audit included, is about 1.22 ms under three, 1.30 ms under nine and 1.39 ms under seventeen (rv64). A round of N budgets’ slices is N such periods, not N ms.

The decision wake is measured by the stand-in itself (time_now against its own deadline), and the post-check reads its sample windows, net of audits, while R10’s time comes from the kernel’s trace: that half of the lease-end sum is the program’s own report, not the kernel’s.

With the real steward. steward-latency measures the same quantities from the steward itself: alice’s session holds N live leases, the probe’s own lease or the kernel’s deadline lease among them beside N - 1 spinning agents (Redoubt.Agents.Echo spin, each a beamlet VM of 5,248 pages on a lease), N = 1, 2, 3, 4 and 16, D = 16 of each kind per round and 8 at N = 16; a round’s deadline leases run one at a time beside the spinners, each a sample of its own lease grouped at N, the deadline lease twice that round’s worst launch over both widths at one and two harts, rounded up to a second, so the deadline falls on a running VM and never inside the launch (a deadline runs from the time the steward sets as the launch’s batch starts, and a lease shorter than its launch dies before its VM runs, budgets): N = 1 8 s, N = 2 10 s, N = 3 11 s, N = 4 and N = 16 14 s (2 × 3.84 / 4.47 / 5.09 / 6.62 / 6.64 s; N = 2 rounds to 10 not 9 because the probe tells its own lease by 9 s, so no measured lease may be 9 s). Each deadline lease is followed by a sleep of the lease plus a second — the margin over the kernel’s R10 destruction (≤ 30 ms) that frees alice’s pages — both the guest’s clock under icount, so the next lease is requested only after the previous is gone, which also holds the N = 16 carve, where alice’s share leaves room for one measured lease beside the fifteen spinners. One at a time, not a burst: deadline_notice is a single lease’s notice latency (the sponsor told — the steward’s lease_ended send to its session returned — less the deadline; target 40 ms; the send adds 10 to 14 ms to the dequeue it was once sampled at, measured as the first notice of each burst below with the shell idle; the table’s deadline notice row is re-measured at the send, 14 to 32 ms where the dequeue read 8 to 16). A burst of D deadlines firing together hands the steward D Exited events at once, and the sponsor is told of the last of them about D times the core’s decision of one exit after the first, every notice of the burst sent before any exit’s bookkeeping: measured by steward-deadline-burst (six leases on one shared deadline, both widths) and steward-deadline-burst-16 (sixteen, rv64), each lease’s notice the send’s return less that lease’s own deadline; the first 0.43 to 0.96 s gross (32 to 149 ms net of the checked build’s audits) after it — the kernel destroying the six or sixteen VM budgets at its one entry at the deadline before any exit notice goes out, each within R10, and the loop then taking the reports together — then each send returning 13 to 77 ms after the previous, the decision of the next exit; the worst of six 0.91 to 1.12 s gross after its deadline (0.13 to 0.16 s net), the worst of sixteen 1.42 to 1.47 s (0.33 to 0.43 s net), one run per column at the seed, every notice’s line printed by the session; the cases assert twice the worst rounded up, 3 s at both sizes, and every line; the exits’ bookkeeping follows the sends, 17 to 297 ms of effects and then 0.17 to 0.78 s of console lines at the loop’s next turn. With the bookkeeping between the sends they returned 40 to 145 ms apart, the loop’s work for one exit (18 ms of its own time in a 41 ms gap on a traced boot, the checked kernel’s audits the rest), the worst of six 1.13 to 1.43 s and of sixteen 1.8 to 2.5 s. The sends themselves once set the pace: beamlet’s serve thread forwarded each to the session’s VM by a send that waited for the VM to take it, a VM busy in Erlang took one per scheduler turn, and the sends returned 40 to 300 ms apart, the last of six 1.5 to 1.8 s and of sixteen 2.1 to 2.8 s after the deadline, one of six or of sixteen lost at the steward’s bound on rv64 at one hart; under that gate the steward’s ordering (its notices ahead of the exits’ bookkeeping, 16 ms of the 1.4 s then, kept now) and the shell’s listener (receiving and queueing, printing in another process) were each built, measured and found to move nothing, and a block trace placed the wait in that forward, which the thread’s queue removes (the steward, beamlet). What the sponsor sees is the shell’s print of each notice, 250 to 370 ms a line through the relay. The deadline inside a launch: these rounds have the steward idle at each deadline, and a launch in flight once held the serve loop inside a synchronous start_agent (2-6 s), so a deadline that fired during one waited behind it. steward-launch-overlap stages that overlap (a lease’s deadline one second inside another lease’s launch, five times a boot, both widths; judged only when the trace shows the deadline inside the launch’s arrival-to-answer window, else a failing verdict): with the launch on the loop the notice came 0.36 to 0.58 s net after the deadline (0.76 to 1.5 s gross, the launch’s remainder: rv64 at one hart, two harts, rv32 at one); with the steward’s launch thread running the launch while the loop serves, the sponsor is told 16 to 36 ms net after it (p99 20 / 36 / 19 ms on the same three boots, target 40 ms met), the loop’s worst wait on the thread’s install lock 33 µs, 5.2 ms and 50 µs (the steward). What still holds the loop inside a lease’s batch is its mints at the shared servers, within SERVER_US (4 s; 1.66 s worst measured): a deadline inside a mint waits for it, a residual on the steward’s page. The case measures the per-notice quantity, one lease at a time. The trace ring (256 MiB, 8,388,608 records) is per boot, and a single boot of all five rounds overran it at two harts, a boot of N = 1 to 4 too (the rounds record about 1.0 / 2.2 / 2.4 / 3.1 / 1.5 M at N = 1 / 2 / 3 / 4 / 16, and on rv32 N = 1 to 3 alone fill 6.0 M at two harts), so the rounds run as three boots judged on their own rings: steward-latency runs N = 1, 2 and 3, steward-latency-n4 the round at N = 4 and steward-latency-n16 the round at N = 16, on rv64 alone (below). The probe ends each boot’s window on the latency-done marker the case writes after its last round, so one build serves a three-round boot and a one-round boot alike. The steward’s test-only probe arms its timer at the last point before the receive that waits on it, prints its wake, its decision wake and its budget_destroy call to return, and the kernel’s deadline notice, as the stand-in prints them; the post-check judges them net of audits with the targets above, unchanged, and R10 from the trace. The load shapes differ: the stand-in’s spinners were plain budgets of weight 100 under users, the steward’s are lease VMs under alice’s share, each a sizes.agent budget; the measured quantities are per lease end, whatever carries the load. The steward runs at the workload’s weight, 1,000 under system, the image’s own, so the targets are measured at the weight the image runs the steward at. A lease’s end is measured to its destruction and the notice to the sponsor: the servers’ records are freed after, off the measured path. N = 4 is measured at one hart since every shared server’s budget became its manifest entry’s (serving), and the round at N = 16 runs since the per-account caps’ lease term is derived from the manifest as the context cap is (the steward): the case’s alice is sized for it by the carve, 213,542 pages, 104 processes and weight 2,200 over two label sets, so her unlabelled share of 106,770 pages, 52 processes and weight 1,100 holds two sessions, the console’s and the SSH session that drives the rounds (2 × 11,393 pages), and sixteen leases of 5,248 pages, 2 processes and weight 50, their own pages beside (2 × 11,393 + 16 × 5,249 = 106,770), and her home’s quota, 18 MiB, sixteen project carves of 1 MiB; the servers’ caps follow (erofsd:system 2 × 5 + 18 connections, the home and /boot 5 + 18, and 21 parked calls at the home: what the share carves at once and a spare, littlefsd). N = 3 was not reached while a cleanup step a busy server did not take was dropped, leaking a State there until the eighth was refused; the step is parked and retried at the server’s next answer now (steward), and the round runs on both widths at one and two harts; the parked after 4 attempts line, which appeared one to four times a run for a lease’s disconnect at erofsd:system under the two spinners while the loop made the attempts, appears in neither width’s run now that the steward’s own thread makes them. Measured at seed 3, one run each, net µs p50/p99 at N = 1 / 2 / 3 / 4 / 16; each lease destroyed is a VM budget of 5,248 pages, and the gross figures beside the deadline notice and the destroy call carry 300-500 ms of the checked build’s audits after such a destruction (subtracted, as every target is net):

Each boot’s trace fit its ring with nothing dropped: 4,841,622 / 2,876,371 / 1,022,850 records of 8,388,608 for the boots at N = 1 to 3 / 4 / 16 on rv64 at one hart, 5,525,840 / 3,711,105 / 1,363,142 at two; 5,005,142 / 2,963,667 on rv32 at one hart, 5,979,365 / 3,932,389 at two. The real steward meets every target on rv64 at one and two harts, N = 1 to 16, and on rv32 at one hart, N = 1 to 4, each column one run at seed 3 with the cleanup steps on the steward’s own thread (steward): the timer wake’s p99 at N = 3 and 4 is 2.6 and 5.2 ms on rv64, 1.2 and 1.5 ms on rv32, and the reply-to-receive p99 in those rounds 11.5 and 11.0 ms, 10.6 and 12.4 ms, with no 100 ms retry in any sample. At N = 16 on rv64 at one hart the timer wake meets its targets, 0.6 ms at p50 and 1.4 at p99 (54.5 and 57.3 ms when the round first ran, from the tree before the thread, where the wake waited behind whole slices of the fifteen spinner VMs: the cleanup steps’ turn, not the spinners’, was the slice it waited for), and at two harts the N = 16 round’s thirty-one launches are all served, with no parked after line in either run: the refusal of a 29th launch at erofsd:system behind eight parked disconnects, seen once at two harts before the thread, does not recur. Before the thread, the loop ran the cleanup steps at its top within its 100 ms send bound, and one sample of sixteen in the N = 3 and 4 rounds (78 and 93 ms on rv64, 69 and 93 on rv32; the next largest under 4 and 24 ms) held one attempt at a disconnect the busy erofsd:system did not take, so the p99 (50 ms) was missed by construction; the same retry showed in those rounds’ reply-to-receive p99 (124 and 65 ms, 135 and 64) and at N = 4 in the decision wake’s (89 and 66 ms, within its 95), where the lease the probe ends waited behind that turn, and at two harts on rv64 as the N = 3 timer wake’s one miss (148 ms, 112 in the reply-to-receive row).

A lease’s launch is a measured call, and its bound follows the measurement. The steward’s served start_agent line gives the launch from the call’s arrival to its answer: the batch that carves the lease, mints its connections and reads its program from the verified system volume, run beside the sponsor’s other leases spinning. The worst of each round’s launches, one run at the seed:

The launch was the one steward call past the client library’s 5 s bound for a short call, and that 5 s was the VM’s own ceiling on a call’s timeout, MAX_CALL_MS, a guess (beamlet): on rv32 the round at N = 4 at one hart and N = 3 at two died on the match of {:error, :timeout}, and the measure then available, the gap between consecutive AgentStarted audit lines less the session’s sleep, overstated the launch under load by the shell VM’s own share and its sleep’s lag (6.8 s against 3.1 s served, beside fifteen on rv64 at one hart). The bound is derived once, over both widths at one and two harts, from every round the runs reached: twice the worst launch served beside the spinners the case runs, 6.64 s on rv32 at two harts, the N = 16 round’s fifteenth spinner launched beside fourteen (a launch between the table’s columns; 5.851 s at one hart beside three, when the 5 s bound ended that round), 2 × 6.64 s = 13.28 s, rounded up to 14 s, the client’s launch_timeout/0 and the VM’s MAX_CALL_MS one number (the steward); the rounds reached with it show launches up to 6.64 s, within it. The launch is compute: beside spinners of its own weight the launching VM’s share of the harts is theirs divided, 3.0 s beside three on rv64 at one hart against 1.7 s alone, and a block trace (block-trace) of the wedge before the bound showed the steward’s every call out returned within 1.43 s, its only long waits receives on its own endpoint, and the read path’s servers (erofsd:system, verity:system, blkd:system) running whenever a reader asked; verityd’s data cache and read-ahead (verityd) cut its blkd reads by two thirds without moving the launch. With the bound the rv32 rounds run: at one hart N = 1 to 4 meet every target, and at two harts N = 1 to 4 complete for the first time, their rows not judged, since that boot ends in the round after them before the reset dumps the trace the oracle judges from (below); they are judged when a run reaches the reset. The one-hart rv32 column’s rows at N = 1 to 4 are this run’s; the launch’s own spread beside three spinners on rv32 at one hart is 2.76 to 5.85 s over the thirteen launches of the round the bound was derived from, with no step of the steward’s differing between them.

Two rv32 rows are findings, not targets met. With the deadline lease derived from the launch every round completes on rv64 at one and two harts and on rv32 at one hart up to N = 4, each boot’s reset dumping a trace the oracle judges whole (dropped 0); before it, the round’s five-second leases, sized as twice a two-hart launch when that launch was 2.5 s, died inside their own launch on rv32 (5.2 s beside fifteen spinners at one hart, 5.7 to 6.3 s at two), at one hart with no deadline-notice sample and at two harts with a Launch the kernel refused NotPermitted, the deadline passed before the process was made. The round at N = 16 still does not complete on rv32 when it was measured: beside fifteen spinners one spinner VM exited 1 before the round’s first deadline notice, after which the samples grouped at N = 15 around the dead VM (the deadline notice’s p99 over the eight that lived about 45 ms, on a round that had lost a VM). The cause was found and closed on the read path: not the drain rate but admission, the file servers’ fid cap of 32 fair-shared with every connection’s root fid in the share, so that at sixteen connections of one account (two sessions’ and fourteen leases’) no VM of the account could load a module, and the spinner launched last died inside its start module’s read (erofsd); the root is a fixed cost outside the share now and the caps are derived from the connections, and sixteen agents of one account launch and load all their modules on both widths at one and two harts and every one exits 0 (bench:lease-code-load, on the host’s clock: under the virtual clock the guest, idle for an instant with no nearer timer, reached the oldest live lease’s deadline, the test bench). steward-latency-n16 still runs on rv64 alone: its rv32 round was not re-measured with the cap, and the column says so until it is. At two harts on rv32 the N = 1 to 3 boot reaches the reset and is judged for the first time, and the N = 2 round misses the timer wake’s p50, 31.8 ms against 15 (its p99 35.2 ms, met), the same within 30 µs over five boots (31,855, 31,835, 31,825, 31,832 and 31,831 µs), every other target of the boot met with dropped 0 and the kernel lock waited for in 249 of 1000 ticks; N = 1 is 5.6 ms and N = 3 4.2 ms, so the miss is the one-spinner round’s: a kernel lock-contention finding at two harts (a wake can wait for the kernel lock there, R78 and residual risks), to be taken up on its own — why the round with one spinner, then a fix or a stated residual. The table carries the rv32 two-hart rows with their numbers, and rv32 is gated at one hart until it lands, rv64 at both. The a device interrupt returned without its claim rejection of the rv32 two-hart trace, one run in two at this seed before, met neither rv32 two-hart boot here. Before the steward’s console lines were queued and written through one kept fid at the loop’s turn (steward), the steward reached its wait with the console round trips of the reply it had just given on its pass (each line an attach, open, write and close at consoled), the timer wake’s p50 missed on every width and hart count (23 to 61 ms), and at two harts the decision wake’s p50 and the deadline notice’s p99 missed too; the reply-to-receive gap was 34-56 ms at one hart and 94-162 at two. Now a call’s records go before its reply, one write each, and the gap (the last row, recorded, no target) is the loop’s own work and the reply’s hand-over to the caller, with no console call in it. The two-hart figures are gated as the stand-in’s are, and the rv32 two-hart row’s miss of the timer wake’s p50 at N = 2, every sample near 40 ms with the one spinner’s VM live before the round at N = 3 ran, is the finding above, judged now. The same finding at one hart on rv32, one cell: the decision wake at N = 1 is a bare 30 ms receive timeout that sleeps 53 to 62 ms with exactly one lease VM running (the round’s own, just launched and spinning) and wakes 1 to 3 ms late beside a second, the steward doing nothing in the window; it measured 24,235 / 28,493 µs with the launch on the steward’s loop, 0.8 ms under the 25 ms p50, and 30,376 / 33,376 with the launch on the steward’s launch thread (the steward), whose report lands the loop’s receive about 10 ms earlier against the VM’s first run; the same tree with the launch put back on the loop measured 23,300 / 31,843, so the thread moved the phase of a pathological wake, not the wake (the 20 ms timer wake at N = 1 is 2.2 to 3 ms late with the thread, 0.8 without, within its 15 ms). The cell is recorded, not judged (record= on the case, the target unmoved; the table above carries both numbers), the one-runnable-VM timeout wake being the scheduler finding above: a sleeper’s timeout that does not end the running VM’s slice, the timer apparently armed for the slice’s end rather than the nearest timeout, visible only when nothing else switches. Landing the phase under by putting process_start back on the loop would be designing to pass an anomalous wake, and is not done. The cases stay out of the whole run, by name, until the two-hart rows pass on both widths. The destructions judged are those before the probe’s LATENCY-END (99 in the N = 1 to 3 boot, 165 over the three); the sixteen after it in each boot (the marker-file exits reaping the leases) are recorded and not judged.

The sweep (2026-09-27, seeds 1 to 16, on rv64 and rv32, TESTBENCH_QEMU_SEED; the gate runs seed 3, this sweep’s worst, and no gate sets the variable). The steward decision wake, p50 / p99 in µs at N = 1, 4 and 16, and a lease’s end (the worst decision-wake p99 plus R10’s p99 from the trace):

The worst case is rv64 at N = 16: decision-wake p50 17,904 µs (every seed within 4 µs of it) and p99 103,984 µs (seed 3); R10’s p99 is 26,379 µs (rv64) and 27,407 µs (rv32) on every seed. The targets were 15 ms (p50) and 50 ms (p99) before the sweep, which rv64 missed on every seed; the sweep sets them at the worst case plus a margin of a tenth, rounded up to 5 ms: p50 17.9 x 1.1 = 19.7, so 20 ms; p99 104 x 1.1 = 114.4, so 115 ms. Every other measure met its fixed target on every seed; their worst p99s were driver wake 33.3 ms, steward timer wake 34.2 ms and deadline notice 23.7 ms (all rv32), and the server’s share never fell below 380 of 1000.

The second sweep (2026-09-29, the same seeds and widths) followed a change that found process objects by index instead of scanning frames. The change made most destructions cheaper, which moved the workload’s timeline: the last lease destructions at N = 16 now overlap the live sessions. There, taking a lease’s exit notice inside R10 frees its process object, and that object’s handle sweep walks every live process’s handle pages. The N = 16 deadline notice and R10’s kernel time, p99 in µs, and a lease’s end:

The worst are the deadline notice at 48,851 µs (rv32, seed 15) and R10 at 35,421 µs (rv32, seed 6). Their targets became the worst case plus a tenth, rounded up to 1 ms: 48.9 x 1.1 = 53.7, so 54 ms, and 35.4 x 1.1 = 39.0, so 39 ms. The lease end’s bound moved with R10’s, to 154 ms; its worst is 105.8 ms. The difference from 30 ms was the handle-sweep term of budget destruction’s cost. A destruction now follows the dying subtree and folds that sweep into one pass, so the term is gone and the targets are back at 30 and 40 ms above (budgets). Every other measure met its target on every seed. The gate stays on seed 3.

The third sweep (2026-09-29, the same seeds and widths) followed a change that frees a page table once it maps nothing. It found the first sweep’s rv64 median was one phase, not a property of rv64: the N = 16 decision wake’s p50 is about 7 ms on most seeds and about 18 ms on some, on either width (rv64 on seeds 6, 7, 11, 12 and 16, rv32 on seeds 5 and 9). The decision wake, p50 / p99 in µs, and a lease’s end:

The worst are p50 18,529 µs (rv32, seed 9) and p99 82,463 µs (rv64, seed 13). By the same rule, a tenth over the worst rounded up to 5 ms: p50 18.5 x 1.1 = 20.4, so 25 ms; p99 82.5 x 1.1 = 90.7, so 95 ms. The lease end’s bound follows, to 95 + 39 = 134 ms; its worst is 116.6 ms. Every other measure met its target on every seed. The gate stays on seed 3, which is no longer the worst seed; the targets come from the sweep, not from the seed the gate runs.

The fourth sweep (2026-09-30, the same seeds and widths) followed a destruction that walks what it destroys instead of every object frame (budgets), which cheapens R10 and moves the phase of every later event. R10 and the deadline notice return to the 30 ms and 40 ms they had before the second sweep. The decision wake’s worst p50 is 18,541 µs (rv32, seed 11) and its worst p99 82,497 µs (rv64, seed 6); a tenth over the worst rounded up to 5 ms sets the p50 at 25 ms and the p99 at 95 ms. A lease’s end follows to 95 + 30 = 125 ms. Every other measure met its target on every seed; the gate stays on seed 3. The decision wake, p50 / p99 in µs at N = 1, 4 and 16, and a lease’s end (the worst decision-wake p99 plus R10’s p99 from the trace):

The fifth sweep (2026-09-30, the same seeds and widths) followed a destruction that closes only the handles chained to what it destroys and frees the dying tables whole (budgets). R10’s p99 is 5,462 µs on rv64 and 5,723 µs on rv32 at most, on every seed, and the deadline notice’s worst p99 is 27,089 µs (rv64, seed 7). The decision wake’s worst p50 is 7,606 µs (rv32, seed 5) and its worst p99 50,993 µs (rv64, seed 15); a lease’s worst end is 56,454 µs. The targets stay where the fourth sweep set them. The steward now sets each by-deadline lease’s deadline 300 ms ahead, not 150: a budget’s deadline is fixed at its creation, before the spawn, and at N = 16 the spawn takes about 150 ms, so on one seed every lease ended before its process started and the notice took no sample. The lead is the fixture’s; the notice is measured from the deadline, and its target stays 40 ms. The decision wake, p50 / p99 in µs at N = 1, 4 and 16, and a lease’s end:

The worst are p50 18,541 µs (rv32, seed 11) and p99 82,497 µs (rv64, seed 6); R10’s p99 is 22,812 µs (rv64, seed 6) and the deadline notice’s is 37,450 µs (rv32, seed 15), both inside 30 and 40 ms. The lease end’s worst is 104,318 µs, inside 125 ms.

The sixth sweep (2026-10-05, seeds 1 to 20, on rv64 and rv32) followed the 1 ms slice. Every seed passes on both widths. The N = 16 decision wake, p50 / p99 in µs, and a lease’s end (the worst decision-wake p99 plus R10’s p99); at N = 1 and N = 4 the decision wake stays under 1 ms and under 3 ms on every seed:

The worst are p50 11,688 µs (rv32, seed 11) and p99 18,591 µs (rv32, seed 16). R10’s p99 is at most 4,223 µs (rv32), the deadline notice’s at most 12,738 µs (rv32, seed 18), the driver wake’s 23,924 µs (rv64, seed 2) and the timer wake’s 26,937 µs (rv32, seed 12). The lease end’s worst is 22,812 µs. The targets stay where the fourth sweep set them; every measure is well inside them.

The cluster workload (tests/programs/src/bin/sched-cluster.rs) measures the same driver and timer wakes where retained stride debt bites: sixteen weight-100 spinners released by one common timeout, a busy weight-1000 server, and 200 attempts each from the two weight-1000 stand-ins, at fixed 80 ms slots and programmed offsets of 100, 300, 600 and 850 µs. Its whole window is on the kernel clock (time_now, µs): one reading T gives start H = T + 200 ms, release R = H + 50 ms and end F = R + 16 s, sent to every child and printed from the same values. H only anchors R: nothing waits for it, so the server counts from its go to F and the spinners from R to F, each span as printed. The spinners, the server and a stand-in’s spin to a slot run in fixed chunks and read time_now between them; that work is billed alike in a candidate and its control. Each attempt reads B before arming, fixes L = B + delay before it arms, and reads P after the wake (the driver also reads E and the RTC’s service time s between them); its envelope is [L, U) with U = P + 1, which holds all of P’s floored microsecond. The clocks run at one rate and a timeout never ends before its deadline (time, timeouts), so the physical span from the deadline to the service lies inside the envelope, and the envelope’s length, net of the audit time the trace certifies inside it (checked builds), is an upper bound on the wake’s non-audit latency. The bench requires R <= L <= P and U <= F for every attempt, and judges the same p50 <= 15 ms and p99 <= 50 ms on all 200 envelopes of each stand-in. Before that, the trace must show at least 25 wakes per stand-in in each category, five at each offset: zero lead, a zero-intent attempt whose wake’s pass is at the floor the oracle replays, and positive lead, a positive-intent attempt whose wake’s pass is above it. A wake that is neither joins no category but still counts in the percentiles, and how many spinners ranked before each wake is reported beside the categories. A met target proves the bound; a missed one alone does not prove the latency is over it. So the known-bad control (the 10 ms slice) must miss an envelope target and have a driver lower witness, the RTC’s service lateness less the union of every audit’s outer bin [u, v + 1) inside the envelope, above the matching target, on each width. A control that misses only on the envelope demonstrates nothing, and so does one whose positive-lead wakes are not behind the cluster: it needs at least 25 per stand-in with eight or more spinners ranked before them, which under a 1 ms slice a weight-1000 waker never has, since it is picked within one of its own slices of the lowest spinner. A control can also fail to take its samples: a stand-in that comes back after a zero-intent attempt’s target has passed cannot arm it, and the construction stops there. That counts as the demonstrated miss only when the oracle classifies it from the console and the trace: the attempt is zero-intent and not the first, the stand-in’s earlier attempts joined the trace as blocked waits, and B less the target, less the certified audit time between them, is over the p99 target. Any other construction failure, a smaller miss, or a run without its trace is no control. The control is sched-cluster-old-control: the same program and gates with the oracle’s cluster_old_control, run by name only, on the kernel built with its test-only slice-10ms, which keeps the old 10 ms slice. It expects the trace rather than the program’s pass, so a failure the guest reports still reaches the oracle. The RTC lateness is reported beside each envelope, not as its length.

Measured at seed 3 in the checked, traced build, envelope net p50 / p99 in µs, the targets 15,000 / 50,000:

The certified audit credit inside the envelopes was 288 ms and 320 ms on rv64, 384 ms and 376 ms on rv32; the driver’s lower witness p99 was 10,902 and 17,195 µs. At most ten spinners ranked before a positive-lead wake. The control fails as required on both widths, by the classified miss: on rv64 both stand-ins could not take attempt 1, B exceeding its target by 104,188 and 109,853 µs (102,676 and 106,472 µs net of audits); on rv32 the timer could not take attempt 1, by 71,624 µs (69,515 net), and the driver missed attempt 2 by a net 29,843 µs, under the target.

The case fails on any missed. bench:sched-latency-tcg runs the same workload in host time and only reports, with the oracle still checking every pick.

On hardware (the softcores) the same workload is measured in cycles, from rdcycle or mtime at the stated clock rate. That is a characterisation of the board, not a gate.

Authority

Status: built · tested: bench:sched-carve-inflation, bench:legacy-gone, host:redoubt-model::scheduler_contracts_hold

• Weight is the only lever. No call sets a pass, a rank, a priority or a slice, and there is no yield: a thread gives up the CPU by blocking, for instance in a receive with a timeout.
• Weight is carved. A budget’s weight comes out of its parent’s free weight at budget_create, by whoever holds a handle to the parent (R7), and goes back when the child is destroyed. A budget’s free weight rises only when a child it carved is destroyed.
• Ties are the kernel’s. The budget ids that break ties are assigned by the kernel and never reused; no caller chooses one.
• kmain’s switch is not a call. Its tag lies outside the call table; a user-mode ecall with it gets InvalidArgument like any unknown number (ABI).
• Passes are not readable. No call returns another budget’s pass or rank. The scheduling trace would, which is why the production kernel has none (R23).

Security properties

R12 (scheduling)

A budget’s CPU follows its free weight, in one queue with no priority, on every hart. While it has a runnable thread, a budget gets at least its weight’s share of the harts the runnable budgets share, but never more harts than it has runnable threads; what it cannot use goes to the others in proportion to their weights, so spreading its threads across harts gains it nothing. The shares are of hart time, as the kernel charges it, each hart’s runner by that hart’s clock; a hart runs at a rate that does not depend on what the others run on real harts and on a strict barrel (the FPGA platform), but not under QEMU’s icount, whose clock counts every running hart’s instructions, so what a budget’s loop counts there is a share of the machine’s instructions. No pattern of spinning, sleeping and waking, exiting or faulting, creating, carving and destroying budgets, or arming timeouts and deadlines gets it more. The rule’s parts are the sections above: free weight, the preemption points, the wake rule and ranks, charging and inheritance. A slice is the picked thread’s user time: it starts when the thread returns to user mode, so the kernel’s work between the pick and that return, however long, never uses it up, and a picked thread runs its slice unless a budget deadline fires at the return.

A system call’s kernel time is bounded by a constant plus a term linear in the pages it maps or the objects it names. It never depends on the extent of an address area or on what other processes hold. map_anon‘s search is linear in the fixed-size area it searches, a constant, and never in len (bench:map-anon-search-bound). A RAM frame is taken from the free-frame bitmap and given back to it, so backing a page, a page table or an object costs no search of RAM, however much of it is in use (bench:scan-bounds). A term linear in a fixed kernel constant (MAX_PROCESS_COUNT, the platform’s interrupt count, MAX_DMA_DEVICES, a fixed table size) is a constant. A term linear in RAM frames or kernel-object frames is not. Billing it to the caller does not excuse it, because every wake waits for it. R10 (destruction) walks only the dying subtree, its owner lists, the dying processes’ own tables and page tables, and the chains of the handles held outside it (budgets), so it is no exception. Delivery visits only the endpoint’s own receivers, groups and notices, so it is no exception either. What a call looks up by PID or by interrupt number it finds in an index the kernel keeps as objects are made and freed: a process object in one of MAX_PROCESS_COUNT slots, an IRQ object in one of MAX_IRQS (1024, the PLIC’s sources; a boot naming a higher interrupt stops). PID 1 is the kernel’s, which has no process object, so processes take PIDs 2 to MAX_PROCESS_COUNT (511): process_create’s PID draw looks at most at those 510 slots, an owed exit notice is sought among at most 510 process objects, and an interrupt finds its object in one lookup; a checked build proves each index against a scan of every object frame. A checked build checks the delivery lists. At each kernel exit that changed one, it starts from every thread and its open calls, checking each list it meets whole and the totals by kind. After each destruction, at each process-object free and before the hart idles, it starts from every budget and endpoint instead, so a list no waiting thread belongs to is checked there. In bench:scan-bounds, after one budget fills 20,000 pages with endpoints, process_create with its exit notice and an interrupt take what they took on an empty system; with the old scans, the first took 1.2 s against 22 ms. So do a one-page map_anon, a budget_create and a process_create rolled back for want of pages, on both widths; a kernel built with alloc-first-fit, which takes each frame by the first-fit scan of RAM the bitmap replaced, fails the case on both widths in a recorded negative run (a one-page map_anon: 1174 µs against 374 µs on rv64, 1274 against 474 on rv32). Beyond the memory calls, bench:call-bounds makes endpoint_create, mint, close, thread_create and thread_exit, call and reply, a receive of a queued message, time_now and budget_usage sixteen times each on an empty system and again after a hostile budget has filled its handle table (4,093 handles), made two thousand endpoints and parked 190 threads in send at the victim’s endpoint and 60 in timed waits; the kernel’s time for each is its lock section from a hold-trace kernel, net of the checked build’s audits, and the oracle holds each call’s longest section after the fill to twice its longest before, or 100 ticks. Each call reads alike on both sides, in ticks before and after on rv64 (rv32): endpoint_create 1,359 and 1,313 (1,932 and 1,843), mint 1,036 and 1,113 (1,440 and 1,553), close 425 and 433 (560 and 578), thread_create 770 and 778 (1,170 and 1,201), call 10,625 and 10,638 (10,054 and 10,127), reply 3,243 and 3,192 (3,311 and 3,378), time_now 280 and 288 (394 and 414), budget_usage 872 and 881 (899 and 917); two grow with the caller’s own objects, as the rule allows: receive reads 9,585 and 11,380 (8,070 and 10,033), a fifth more with the caller’s own endpoint’s queue filled by the hostile’s 190 senders, one reading at 190, not a slope, and bounded because a receive’s pump reads the endpoint’s own lists only, never every thread (worst-walk bounds the pump); and thread_exit by half with 250 threads in the process, 1,045 and 1,519 (1,421 and 2,012).

It is attacked three ways:

• Boot cases, in virtual time, judge what the kernel charged each budget over a window, net of the harts’ lock waits, against its water-filling share of the harts, within 50 per thousand, at one hart and two (checked builds): spinners at 100, 100 and 300; near-slice, 20 µs and long-sleep bursts; a sleeper waking into an idle gap; threads and processes that exit or fault just before their slice ends; budget churn; carving; 30 sleepers a microsecond apart, 64 staggered deadlines, and waits ended before their timeouts; a system server flooded by one user; a weight-1000 server among eight users of 100. On two, three and four harts, sched-capped runs the model’s scenarios: a heavy budget with one thread on two harts while others join, a second cap at three, a capped budget gaining a thread, and one budget spread over four harts; at two and three harts the shares are recorded under icount and judged where the harts run at once (sched-capped-mttcg, QEMU’s turns below). A kernel whose floor counts the capped budgets (sched-capped-holds-floor, a debug-only feature whose queue audit reads the same broken rule) passes every rank the oracle checks, and fails late join’s shares at two harts, on both widths: B gets 52 of 1000 (rv64) and 56 (rv32) against 250 while C takes its hart (bench:sched-capped-holds-floor, a case that must fail), and 30 and 31 where the harts run at once (a recorded run each).
• The differential drives libs/stride, wired as the kernel wires it, and the model’s scheduler through 3,000 random sequences of creations, destructions (leaf, on a hart, and whole subtrees), wakes, blocks, runs and preemptions, at 1, 2 and 4 harts, and requires every pass, entry, remainder, tie, queue membership, floor, cap set and pick to agree after every step. A model with any of 30 scheduling rules broken must disagree.
• The model’s mutations: each R12* variant breaks one part, and scheduler_fairness (eleven scenarios, each with an independent check) or the scheduler contracts must catch it (model).

R78 (fair kernel entry)

Status: built · tested: bench:smp-boot, bench:smp-lock-wait, bench:sched-lock-contention, bench:sched-lock-contention-4, bench:sched-lock-contention-4-mttcg, bench:irq-boot-hart-only, host:testbench::lock_waits_take_the_lock_in_ticket_order

On several harts, kernel entry is fair across them: the one kernel lock is a FIFO ticket lock, so a hart that arrives at the kernel waits behind at most MAX_HARTS - 1 kernel sections, never for ever. The rule exists for R12. A test-and-set lock is unfair: a hart can lose the lock to later arrivals indefinitely, and the budget running on that hart loses its share with it, so one budget’s harts can starve another’s of kernel entry, which no pattern of calls may do. FIFO bounds the wait by the hart count, and the bound is part of how R12’s shares are judged across harts (several harts).

The lock (kernel/src/cell.rs, TicketLock) draws a ticket with a relaxed fetch_add, waits until serving reads it (acquire), and releases by serving + 1. A hart waits halted, not spinning: it marks itself in the lock’s halted set, reads serving again and, if its turn has not come, halts (wfi) until an interrupt is pending; the release sends each marked hart the reschedule interrupt (through the firmware, SBI), and the woken hart reads serving again. The halt waits for the reschedule interrupt alone: the timer’s and a device’s are masked in sie for it (arch::halt_for_ipi), since a hart without the lock cannot take them, and one pending would end every halt at once and turn the wait into a spin. A hart whose awaited interrupt is already pending runs no wfi at all: the architecture lets wfi return at once then, but QEMU halts the hart regardless and, under icount, runs it again only after every other hart’s turn (arch::halt_masking), which cost an idle hart woken by sched-lock-contention-4’s alarm 28.5 ms. A checked build counts the halts it skips, and sched-lock-contention requires some at two and at four harts (95 to 182 a run). A hart halted in kmain’s idle is not in the lock’s set and no release wakes it; since a timeout whose payer runs nowhere is armed on one hart (the hart timer), the machine at rest no longer hands the lock around for its sleeps: at the prompt the lock changed hands 5 to 6 times a second with every hart halted, each hand-off an interrupt, and changes hands 1.7 to 1.9 times a second with the rule, each for a woken thread’s own work (bench:launch-idle). The mark, the read, the release’s store and its read of the set are sequentially consistent, so either the release sees the mark or the waiter sees the new ticket: no hart halts past its turn. Under QEMU’s icount, where the harts take turns on one host thread and the clock counts every running hart’s instructions, a spinning hart would spend its turns and the guest’s time while the holder waited for them, and a halted one gives them up. Spinning cost every case at two harts: ipc-client’s 1000 lend round trips took 17.4 s on rv64 and 20.0 s on rv32 against 2.0 s at one hart, and take 2.1 s on both widths halted; sched-latency’s N = 16 driver wake p99 was 345 ms, and is 6.3 ms (gross, rv64). On real harts the halt costs one interrupt at each contended release: without icount, at two harts, the same round trips take 546 ms halted against 505 ms spinning on rv64 (+8 %) and 563 against 508 ms on rv32 (+11 %), each a mean of five runs alone; a spin of 300 turns before the halt took back most of that on rv32 and little on rv64, and cost 7.5 % under icount, so there is none. The halt is the Zawrs hook: a wrs.nto reservation wait on serving would stall the hart with no interrupt, but QEMU runs wrs.nto, like the pause hint, as a no-op that keeps the hart’s turn. The lock is taken once at trap entry and released before the return to user mode or an idle wait. A checked build asserts, at every acquisition, that the hart waited behind fewer sections than harts were started (the draw, the read and the release are sequentially consistent there, so the count can only under-count); bench:smp-boot prints the most any hart waited (one section at two harts, three at four, on both widths). Under the ticket lock the count cannot exceed the harts less one by construction, so the assertion is structural for the real lock, and the test-and-set negative below is the one attack. It is attacked by a kernel built with the ticket lock replaced by test-and-set (sched-test-and-set-entry, a debug-only kernel feature like the tie fault, below; not a model mutation, since the model has one hart): with it, smp-boot fails at the FIFO assertion at two and at four harts on both widths, in a recorded negative run. The one-hart kernel is the uncontended case of the same lock.

bench:smp-lock-wait holds the halt: two threads of one process make 20,000 system calls each at once on two harts, every call contended, then one thread makes all 40,000 alone, and the calls at once may take at most three times as long. Halted they take 1.87 s against 1.26 s on rv64 and 4.87 s against 1.97 s on rv32: each hand-off of the lock is an interrupt through the firmware, dearer on rv32. A kernel whose waiting hart spins (sched-spin-entry, a debug-only kernel feature) fails it on both widths in a recorded negative run: 250 s against 1.25 s on rv64, 170 s against 1.97 s on rv32.

bench:sched-lock-contention holds the order in time, under R12’s costliest call: on every hart but one a budget asks in a loop for a map_anon refused after a search of the whole area (map-anon-search-bound’s worst case, 9.6 ms of kernel time in a checked build), beside sched-latency’s driver stand-in. A kernel built with lock-trace records each wait’s ticket, and the oracle requires the waits to take the lock in ticket order, each drawn behind fewer sections than harts (the scheduler oracle): at two harts 1433 waits on rv64 and 1436 on rv32, each behind at most one section; at four harts (sched-lock-contention-4, three such budgets) 2240 and 2548, behind at most three. The driver’s wake is gated on the responsiveness targets at two harts, and on its p50 at four. Every started hart takes device interrupts (boot), so the alarm reaches the idle hart, which draws its ticket behind the search in progress and runs the driver itself: net of the audits its p50/p99 is 8.5/10.6 ms on rv64 and 8.5/10.4 ms on rv32 at two harts, against 15 and 50 ms. The wakes are bimodal, under 2 ms when the alarm falls between two searches and about 10 ms inside one, and the p50 is whichever mode holds half of them (another run read 1.5 and 1.7 ms). With the boot hart alone taking device interrupts they were 18.5/19.2 and 18.3/19.1 ms: the alarm waited out the boot hart’s search, and the woken hart drew its ticket after the searcher’s next call. bench:irq-boot-hart-only is that kernel (irq-boot-hart-only, a debug-only feature) under the same targets, which the post-check must fail (20.2 ms gross p50 on both widths: its hammer lands on the boot hart); a checked build’s count at power-off shows its boot hart claiming all 201 and the other hart’s context taking none (no claim, and no claim that found nothing). The count is each hart’s: its claims, its claims that found nothing (it trapped for an alarm another hart claimed first) and their sum, the alarms its context took. The idle hart wins the claims, and which hart idles follows the boot’s timing (claims 200 and 1 in one sched-lock-contention run; 29, 4, 168, 0 and 196, 1, 2, 2 in two sched-lock-contention-4 runs), so the cases require what does not: sched-lock-contention and sched-lock-contention-4 that a hart other than the boot hart took ten or more alarms, and sched-lock-contention-4-mttcg that every hart did. At four harts under icount the p50 (4.3 ms on rv64 and 5.3 ms on rv32 in one run) and the p99 (59.1 and 58.7 ms) wait for QEMU’s turns and are recorded there, not gated (residual risks): rv32’s p50 moved between 5 and 22 ms when a slice’s end was made cheaper. It is judged where the harts run at once: bench:sched-lock-contention-4-mttcg runs the same program under QEMU’s multi-threaded TCG, in host time, and judges the driver wake’s net p50 and p99 in searches of the same run alone, which the program times before its children start (one search alone): at most three at p50 and eight at p99. A ratio, because the host’s speed moves both sides, and a wake waits behind at most three searches and the one in progress. Twenty runs alone on q’s quiet cores read a p50 of 1.6 to 1.9 searches and a p99 of 2.0 to 3.0, but for one run of each width at 6.1 (rv64) and 5.1 (rv32); twenty on the general cores read p99s of 3.8 to 6.2 and 3.2 to 5.1 (a search alone about 1.5 to 1.9 ms and 1.3 ms). The p99 bound, at twice the four-search claim, cannot see a wake one or two searches longer: the irq-boot-hart-only kernel under the same case reads p99s of 5.4 to 7.1 searches and passes it. Its p50, 3.7 to 4.9 searches against IRQ1’s 1.6 to 1.9, fails the p50 bound in all four recorded runs, so the p50 is the gate that sees that regression. The 15 and 50 ms targets are gated too, but on this host’s TCG a search takes a fifth of its 9.6 ms of virtual time, so they hold for the twin as well (p99 7.5 to 10.9 ms); on hardware, where a search is its virtual length, the same count holds 50 ms while R12’s costliest call stays under about 12 ms, and the twin’s would not.

R23 (no test channels)

The production kernel carries no test-only diagnostic channel. The scheduling trace is one: a record of every budget’s id and pass at every wake, requeue, pass change, pick and lift, which tells whoever reads the console who runs when. It exists only under the Cargo feature sched-trace, and no default build enables it:

• the kernel’s default features are print-panics alone, and ./build adds only the board (qemu-virt);
• every trace site in kernel/src/{sched,budget,mem,main,message,process,redoubt,time}.rs and kernel/src/arch/riscv/irq.rs sits under #[cfg(feature = "sched-trace")], so with the feature off the ring, its records and its SCHED-TRACE console lines are not compiled;
• the bench turns it on per case (kernel_features), only for the cases whose sched_oracle post-check reads the trace printed at system_reset: the share cases (sched-share, sched-large-weight, sched-idle-gap, sched-sleep-gaming, sched-capped, sched-budget-churn, sched-budget-churn-shell, sched-exit-churn, sched-timer-flood, sched-carve-return, sched-carve-inflation, deadline-flood-billed-traced), sched-ties, sched-debt-lift, sched-lift-delay, sched-wake-no-preempt, sched-wake-no-preempt-harts, sched-wake-no-preempt-harts-mttcg, sched-irq-wake, sched-deadline-preempt, sched-cluster, sched-cluster-old-control, sched-latency, sched-latency-tcg, sched-lock-contention, sched-lock-contention-4, sched-timer-entry, irq-boot-hart-only, kernel-containment, endpoint-destroy-full, smp-fence and worst-walk.

The bench checks it on the binary (bench-no-trace): a build case builds the production kernel, the release profile with qemu-virt alone as ./build does, and fails on the first of SCHED-TRACE (the trace’s console lines) and 5sched5trace (the mangled path of its module, redoubt_kernel::sched::trace, which every symbol of it carries and the kept symbol table would show) found anywhere in its bytes. bench-trace-scan-catches plants the trace, a checked kernel built with sched-trace, under the same scan and must fail on the console line (at offset 0x37ba1 on rv64 and 0x3b69e on rv32, in the ring’s SCHED-TRACE-END ... dropped text); and bench-test-only-refused asks the release profile for sched-trace and must fail on the kernel’s refusal below, in the compiler’s words.

The other diagnostic features are off by default in the same way: walk-trace, which implies the trace and brackets each receive’s pump, timer expiry and reconcile in it, for worst-walk alone; lock-trace, which implies the trace and records after each wait for the kernel lock its ticket and the sections ahead of it when drawn (k), for irq-boot-hart-only; hold-trace, which implies lock-trace and records each section of the kernel lock at its release, its ticks, cause and audits (h, j), for sched-lock-contention, sched-lock-contention-4, sched-timer-entry and call-bounds; block-trace, which implies the trace and records each thread’s block at the one place a thread blocks (@: the budget, its wait kind and the endpoint it waits on), each wait’s end (~: the budget, the wait kind, whether it timed out or was answered without blocking, and the endpoint, so a block’s length and what ended it are read) and each budget’s creation (#: the new budget’s id, its parent’s and the creating process’s PID, so a session’s or a lease’s budget is read off the trace as the one the steward carves at its login rather than inferred), for no case: a diagnostic run by hand, which told a budget waiting to receive a call that never came from one blocked in a call out (responsiveness), and placed a burst of the steward’s notices between beamlet’s serve thread and its VM (the steward); irq-boot-hart-only, whose boot hart alone takes device interrupts, for R78’s negative case at two harts; sched-inject-tie-fault, a debug-only break of the tie rule that implies the trace; sched-capped-holds-floor, whose floor counts the capped budgets, for R12’s negative case at two harts; sched-test-and-set-entry, which replaces the kernel lock by test-and-set, and sched-spin-entry, which makes a hart wait for it spinning, each for one of R78’s recorded negative runs; audit-unstamped, which leaves the audit after a destruction out of the trace, and audit-billed, which bills each audit’s time to the budget that ran it and counts it against its slice, each for one recorded negative run (responsiveness); audit-wait-billed, which bills a hart’s wait behind another hart’s audit to its runner, for one recorded negative run (residual risks); timer-tail-billed, which bills the rest of a timer interrupt after its expiry, and its return, to the budget it interrupted, for one recorded negative run (charging); alloc-first-fit, the first-fit frame scan, for one recorded negative run (R12); slice-10ms, the old 10 ms slice, for the cluster’s known-bad control (responsiveness); and debug-print, which prints every pick’s PID and thread and every trap. dma-reset-deaf is a test-only fault, not a channel (devices), and so are handle-chain-fault and process-chain-fault, a handle installed without its stamp entry or its process object entry for the chain audit to catch (budgets), sum-probe, a stray kernel load that must fault (R24 (SUM and MXR clear)), and panic-in-print, a panic inside print! (boot). Each of these implies the feature test-only, which the kernel refuses to compile without debug assertions, so the release build ./build makes cannot carry one; a checked build, as ./build --debug makes, still can.

Failure and restart

• A thread exits, faults or is killed on the CPU: its budget is descheduled and charged what it ran, at least one tick, like any other deschedule.
• A budget is destroyed: bottom-up, each budget is charged what it ran, its work is lifted into its parent, and it leaves the queue. A budget destroyed on the CPU (its deadline, with nothing descheduling it first) is charged, and the CPU is free.
• A deadline ends the entering process: the trap handler resumes whatever is current and uses nothing of the dead process (I14 (no call panics the kernel)).
• The picked thread died since the pick: kmain does not run it and picks again.
• Nothing is runnable: kmain idles, billing stops, and the floor holds for the next waker.
• Arithmetic cannot stop the kernel. Passes are 128-bit and never wrap; a lift saturates rather than overflow. The queue has one slot per process, and a queued budget has a runnable thread, so it cannot fill; if it ever did, a budget would be left out rather than anything stopping (a debug assertion in checked builds).
• A restarted server in a fresh budget enters like any child, at max(floor, parent's pass), and carries no credit from the one that died. Restarted in the same budget, it keeps that budget’s pass.

Residual risks

• Two bills still leave their own handling to nobody. An interrupt’s handling is measured, billed to its device’s owner, and then the interrupted budget’s billing restarts, so the bill’s own work is between the two; and a deadline’s destruction is billed to its payer inside the destruction, so what follows that bill until the expiry’s next interval is nobody’s. Each is a bill’s own handling, about 25 µs in a checked rv64 build, once per interrupt or destruction. A traced kernel measures all the kernel time no budget is charged, these two and what the rules leave to nobody (a walk that finds nothing, a pick of nothing, a timer interrupt that ends no slice), as a share of its time net of audits (nobody N of 1000, checked builds); an interrupt’s bill leaves out an audit its handling runs, as billing does. Of 1000, rv64 then rv32: 14 and 26 in sched-exit-churn, which has neither an interrupt’s bill nor a deadline’s destruction, so that is all time the rules leave to nobody; 27 and 44 in sched-latency, which can also show the interrupt’s gap; and 17 and 35 in sched-timer-flood, 29 and 47 in sched-budget-churn and 61 and 84 in kernel-containment, which can also show the destruction’s. The two gaps are at most that. The counters read the billing’s clock and decide nothing: like the audits, they move no schedule.

• Server work is paid by the server’s weight. Work a server does for a user is paid by the server’s weight, not the requester’s; the steward’s work, by the steward. No time is donated, so a user who floods a server takes that server’s share away from the server’s other callers, never more. In bench:sched-server-busy, by ratio of counts, the server’s work for one user is at most what each other user runs, and the other users run alike. The flooding user’s calls are kernel time that no count measures, so the case does not check that it takes no more than its own share. Its trace did show that: the flooding user charged 229 of 1000, against 257 for each other user and 258 for the server. Servers therefore bound the work of one request, and the steward, whose weight is large, bounds its per-request work and relies on its per-(account, label set) caps (steward).

• Wakeup is prompt but not bounded. Unless a hart is idle, a wake waits out a running slice, may keep a larger pass, and may tie. Human control rests on a measured steward lease-termination latency, not a proven bound, until something needs a real-time rule (TENETS).

• The steward decision wake is late by whole slices. A wake never preempts: at N = 16 the steward stand-in waits out a running slice, then the slices of any budgets that rank ahead of it. With the 1 ms slice (the sixth sweep above) its p50 falls in a few modes, depending on where its timeout lands against the running slices: about 1.6 ms or 3.2 ms on rv64, and about 8.2, 10.0 or 11.7 ms on rv32. Its p99 is a wake that lands behind several of the sixteen budgets, so it falls in steps of about 1.6 ms (rv64) and 1.7 ms (rv32), one slice and what runs between them: from 6.5 to 14.6 ms on rv64 and from 11.7 to 18.6 ms on rv32 (seed 16). The exact chain from a seed to its mode was not traced. The targets (25 and 95 ms) were set from the sweeps under the 10 ms slice and stay; a lease’s end from the steward’s decision is at most 22.8 ms in the sweep against its 125 ms. A pinned seed repeats one run; a change that moves the phase can land on a worse one than the sweep saw, which the margin covers and a new sweep re-measures.

• Fair kernel entry is bounded by count, not time. On several harts, R78 bounds the wait for the kernel lock by MAX_HARTS - 1 kernel sections, each as long as the call or destruction holding it: a long section delays every waiting hart by its length, which is one more reason R12 bounds a call’s kernel time. So one budget’s kernel work under the one lock costs the other harts up to its own length, bounded by count, not by share: the wait is the waiting hart’s runner’s time, billed to it and counted against its slice, and no billing gives it back. A checked build’s audit is the one exception: like the audit’s own hart, a hart waiting behind it is billed none of the part it waited through, and its slice’s end moves by it (checked builds). A traced kernel records each wait from user mode and the oracle reports them as a share of the harts’ time, lock waits N of 1000, beside nobody, with the ticks behind audits. Shares across harts are judged net of the billed waits, and the one share the lock still decides is judged at one hart (below). Taking them out has a blind spot: the judge subtracts each wait from the budget the hart’s runner record names, so a kernel that billed a wait to the wrong budget, or to none, would pass it, and no case checks the billing of a wait itself. Judged gross, with the billed waits counted as the waiter’s, every share that passes net passes too: sched-exit-churn’s victim against threads that exit, the one that once did not (403 and 445 before the lift target), reads 508 on rv64 and 495 on rv32 gross against 571 and 603 net, at least 450. The shares stay net, so the blind spot stays. Gross sits nearer water-filling where the waits are short: sched-timer-flood‘s three shares read 498 to 500 gross against 522 to 586 net. At two harts the waits are 103 to 228 of 1000 in the share cases (rv64 then rv32: sched-exit-churn 228 and 216, sched-timer-flood 213 and 207, sched-budget-churn 110 and 103, sched-share 140 and 196) and 234 and 286 in the containment gate; behind audits are 85 to 89 % of the waits in sched-budget-churn-shell and deadline-flood-billed-traced, whose creators’ destructions each run a 20 ms audit, and 6 to 48 % in the other share cases. With hold-trace the oracle splits them by what they waited behind (the scheduler oracle): a wait in sched-share is mostly the lock standing free, about 0.5 ms each, while the woken waiter, halted, takes its turn under icount. What made the sections long, measured at two harts: the destruction’s audit; a scan of all of RAM at every process’s end, 7 ms, billed as work until it became an audit; a fault’s report, which printed the process’s map a line a page holding the lock (837 ms for 4096 pages); and zeroing a frame a checked word at a time, five times a plain store loop. The wait for a shootdown’s acknowledgements stays under the lock: it totals 0.9 ms over the whole containment gate at two harts (memory). A wake behind R12’s costliest call waits at most the section in progress at two harts (sched-lock-contention, R78): the idle hart takes the device’s interrupt and draws its ticket behind it.

• Timer work billed to one budget can still take another’s hart. A timeout’s or a deadline’s work is billed to its payer, and its interrupt is armed on the payer’s hart where the payer runs, so a one-thread victim on two harts, whom no pick can repay, no longer destroys a flood of its neighbour’s budgets (before: up to 17 % of its window in deadline-flood-billed-traced, by where the destructions landed). What still lands elsewhere, a payer that runs nowhere or ties, an item noted away from its payer’s hart, a passed item served by the first entry (a flood’s next deadline, passing while the payer’s hart destroys the one before, at the victim’s own slice end), is counted and bounded at 10 of 1000 of the victim’s charges in three host-clock cases; under icount which entry comes first is QEMU’s turn order, and the icount cases report the count without a bound (timer).

• A burst of timeouts is served by one hart. Timeouts whose payers run nowhere are armed on one hart, so sixteen sleepers waking together are served there in turn while another hart idles: bench:sched-latency’s timer wake p99 at N = 16 rose 1.6 and 3.7 ms at two harts, every target met. The trigger for handing the items beyond the first to an idle hart is on the timer page (timer).

• A hart waits for QEMU’s turns. Under icount the harts take turns on one host thread, and a hart in a kernel section keeps its turn to the section’s end. A device’s line that rises while the idle hart is halted wakes it on time in virtual time, but the hart runs only when the running hart’s turn ends, and then draws its ticket behind up to three sections. In sched-lock-contention-4 that leaves the driver wake’s p99 at 59.1 ms on rv64 and 58.7 ms on rv32 (other runs read 49.7 and 40.6), and its p50 at 5 or 22 ms on rv32 as the kernel’s timing moves which turn the wake lands behind, so both are recorded there, not gated: every long idle halt began with nothing pending, and the kernel cannot shorten another hart’s turn. On harts that run at once the woken hart draws its ticket at the rise, and the four-hart p50 and p99 are judged there, under QEMU’s multi-threaded TCG (R78). Turns move shares too: at two harts on rv32, QEMU ends the heavy budget’s hart’s turn inside its slice end’s time billed to nobody (the checked build’s audit, or kmain’s expiry walk) at every slice, about 2,600 ticks a slice, so sched-capped’s late join reads 449 of 1000 against 500 (434 at icount shift 4) and the oracle’s nobody share is 71 of 1000 where it was 30. The two-hart shares are recorded there and judged in sched-capped-mttcg (497 to 501 over five runs a width). Turns fix the order harts take the kernel lock too: in sched-capped’s second cap at three harts no timeout fires in the window, every interrupt is a slice end of the hart’s own runner, and the three slice ends meet at the lock every slice in one order, so the heavy budget on the last hart waits 1.3 to 2.3 slice-end sections (6,300 to 6,600 ticks each in the checked, traced build) at every slice, 23 to 45 % of its hart, and reads 276 to 340 of 1000 against 333 (two misses in five runs alone on main, three in five on a kernel differing only in the phase the threads come onto their harts with); the three-hart shares are recorded there and judged in sched-capped-mttcg at three harts (327 to 329 over five runs a width, each heavy budget’s lock waits about 1.1M ticks of 60M). Turns decide where a timeout is answered too: a hart’s timer armed for it fires in the hart’s next turn, by which the other hart’s call has answered it, so on rv32 sched-wake-no-preempt-harts has at most one wake mid-slice under icount (0 or 1 in ten runs, and 79 of its interrupts finding nothing due in one); it records them, and sched-wake-no-preempt-harts-mttcg judges them (41 to 78 on rv64 and 41 to 75 on rv32 over ten runs a width).

• Every hart pays for each device interrupt. An unmasked source raises the external interrupt on every hart’s context, so each hart in user mode or idle when it rises traps, and all but one take the kernel lock for a claim that finds nothing; a hart in the kernel at the rise returns to a source already claimed and masked, and does not trap (sched-lock-contention-4-mttcg requires every hart to take ten or more of its 200 alarms; under icount a hammer in a search at every rise took none, so sched-lock-contention-4 requires only another hart’s). Under multi-threaded TCG at four harts every alarm traps the other three (518 to 577 such entries in a run of 200 alarms, twenty runs), each holding the lock about 31 µs (p50; 50 µs at p90): at most three are ahead of a wake, about 0.15 ms of a p99 of 4 to 12 ms. So it is not routed: sending each source to one idle hart (a busy hart’s threshold above the sources’ priority while one idles) is the remedy if it comes to matter.

• Some cases keep one hart. A case that does not keep its hart count runs at the count the bench is given (--smp); these keep theirs (keep_smp), each for one of four reasons: a proof that reads one hart’s slices; where a checked build’s audits fall; a count with no trace, which under icount is the machine’s instructions, not a hart’s time; or a scenario that measures one queue’s rounds. The lock waits, and then the cap set’s lifts, once kept three more: sched-budget-churn-shell, deadline-flood-billed-traced and sched-exit-churn‘s victim against threads that exit are judged at two harts since the lift target (“The current minimum and ties”) and the waits behind other harts’ audits billed to no one (above). Each kept property has a case at two harts that covers it, or says none:

  Case	Class	Why	At two harts
  sched-wake-no-preempt	one hart’s slices	its proof reads each nap against the slice that follows it, which needs every timeout answered by a timer interrupt mid-slice; at two harts most are answered at a slice’s end or at another budget’s call	sched-wake-no-preempt-harts
  sched-deadline-preempt	one hart’s slices	the deadline’s timer comes on its payer’s hart; on two the other runner has a hart of its own, so which budget an expiry interrupts is QEMU’s turn order	none
  call-bounds	one hart’s sections	under icount a lock section on several harts counts the other hart’s instructions too, as sched-timer-entry’s	none
  sched-irq-wake	one hart’s slices	its proof reads each device interrupt against the runner’s slice that follows it; on two the idle hart takes the wake, and there is nothing to preempt	sched-wake-no-preempt-harts (timeouts’ wakes, at the entry that answers them)
  sched-round-robin	one hart’s turns	the round-robin is among the threads no hart runs, and on several harts a budget’s threads run at once	none
  sched-large-weight	audits	its users’ hart switches budgets each slice and takes most audits, charged to no one, so the server reads 572 of 1000 on rv32 against 450 to 550	sched-share (its 300 holds a hart)
  deadline-flood-billed	a count	a release build with no trace	deadline-flood-billed-traced and sched-timer-flood
  sched-share-release	a count	a release build with no trace	sched-share
  sched-large-weight-release	a count	a release build with no trace	sched-share
  sched-lift-delay	one queue’s rounds	the capped launcher runs on a hart of its own and the peers spread over more than a round	sched-debt-lift
  sched-carve-return	one queue’s rounds	V is capped at two budgets on two harts, so U alone sets the floor and never leads it	sched-carve-inflation
  sched-cluster, sched-cluster-old-control	one queue’s rounds	the envelope is calibrated against one runner’s slice period	sched-latency’s targets

  kernel-containment runs at two harts but judges its bystander’s share at one (@1): at two it reads 450 and 567 of 1000 on rv64 (two builds) and 557 on rv32, against 450 to 550 (464 and 442 before the lift target). The bystander is never lifted and takes no other budget’s billed work on its hart; what moves it is the lock: its waits behind the agents’ kernel sections, 26.6 million ticks against the agents’ subtree’s 19.6 million on rv32, cost its hart time that no billing gives back, which R12 does not promise (above), and shift which budgets run beside it. Every other verdict and target of the gate holds at two harts (containment). bench-poweroff-missing keeps one hart too, a bound of the bench’s own. sched-latency-tcg runs at two harts: the kernel’s lines wait, whole, for a program’s line in progress (the console’s one writer). sched-capped (two, three and four harts), sched-capped-mttcg (two and three), sched-lock-contention (two), sched-lock-contention-4 (four), sched-wake-no-preempt-harts and sched-wake-no-preempt-harts-mttcg (two) keep the counts they are about.

• A call within one budget crosses harts. A wake sends an idle hart the reschedule interrupt even when the woken thread’s budget runs elsewhere, so a server and its client in one budget hand each call and reply across two harts, each hand-off an interrupt and a wait for the lock, where one hart would run them in turn. Under icount, ipc-client’s 1000 lend round trips against log-server in system take 2.07 s at two harts against 2.02 s at one (rv64; 2.06 and 2.01 s on rv32), since a hart waiting for the lock halts (R78). No rule keeps a woken thread on its waker’s hart. A call’s or a destruction’s kernel time delays every wake on the machine, which is why R12 bounds a call’s kernel time whoever pays for it. R10’s time dominates lease termination and follows the dying subtree and the handles that depend on it, so its target and the deadline notice’s are 30 and 40 ms, not the 39 and 54 ms a whole-frame scan had (budgets). Ending a DMA driver adds up to RESET_US (1 ms) of reset polling for each device it held, at most MAX_DMA_DEVICES (16) (devices).

• A destroyed lineage’s debt is carried onto its siblings as the parent’s lead. Debt lifted onto a shared parent is normalized to the parent’s weight, and a sibling created under it enters at the parent’s pass; the oracle recomputes every lift. A fresh lift delays the sibling by the child’s lead, in slices of the other runnable budgets (the peers), times the peers’ weight over the parent’s weight; the sibling’s own weight does not enter. In a checked build a child that ran to the end of a slice leads by 1.4 peer slices, so under a parent of a peer’s weight the next child waits 1.4 rounds, and under a parent of a tenth of it 14. bench:sched-lift-delay measures it in a checked build in virtual time, under sixteen weight-20 peers, with parents of weight 20, 10 and 2 and siblings of weight 2, 5 and 1. The oracle computes the delay from the lift’s records as the child’s work over the parent’s weight over a round’s pass step: 1.4, 2.8 and 14.0 rounds on rv64 (1.4, 2.8 and 13.8 on rv32), and no other budget is picked more than 1, 3 and 14 times before the sibling’s first run (2, 3 and 14 on rv32). The oracle requires that count to be less than a round from the prediction and from the sibling’s lead at its wake, and the floor to have moved less than half a round between the lift and the wake (under 0.3 rounds on rv64, 0.32 on rv32), so each phase’s lead at the wake is within half a round of the prediction. Under a parent as wide as users the lift is a few thousandths of a slice. The lead fades as the floor rises, so a sibling made later waits less; with peers of weight 100 the floor passed the lift of a weight-100 parent while the launcher started the sibling, so the case uses weight-20 peers, which the launcher outweighs. bench:sched-debt-lift checks that a sibling created after a weight-1 lineage’s destruction runs before any other budget is picked twice, which its raw debt, unlifted, would have cost about six rounds. Rounding loses under one pass unit per destroyed budget, and the loss falls on the budget that churns.

• Scheduling is observable. rdtime is readable in user mode, so a thread that times its own gaps learns how busy the machine is. Timing channels are out of scope (TENETS).

• Measured on QEMU. The targets are guest instructions under icount; no hardware run is measured, and a hardware run will characterise in cycles, not gate. A target set from a sweep holds for the seeds swept, not for every seed. The queue and its accounting are judged at 1, 2 and 4 harts; the targets are gated at 1 and 2 and recorded at 4 (several harts). The cases that read the trace run a kernel built with it, which has a record at every queue event and 64 MiB less RAM for the budget tree, taken from the top of RAM below the DMA pool so the frames below sit where a release kernel’s do.

Why

• Weights, not priorities. A server ahead of everyone would let one user make littlefsd or keyd do expensive work while no user budget runs. Large weights from the boot manifest (init) keep init, the steward and the drivers responsive without that; a driver that spins while others are runnable is a bug for the bench to find, not a mode to support.
• Free weight. Carving is how budgets delegate, so a child’s share must come out of its parent’s; counting the limit instead would let a tree of carves multiply its share.
• The floor. Without it a sleeper keeps a stale low pass and dominates when it wakes. With it, a waker is still prompt: it joins at the front of the current minimum.
• Wake-first, deterministic ties. A budget that just woke has usually waited, and one that was requeued has just run. Fixed clauses over kernel ids let an independent oracle check every pick.
• No preemption on wake. One preemption source, the timer, keeps accounting to a single point and makes a flood of wakes cost nothing extra. The price is that wake latency is measured, not derived.
• Instructions, a pinned seed and a sweep. Host time makes a gate depend on the machine it runs on; guest instructions do not. A pinned seed makes a failure replay exactly, and the sweep keeps the pinned seed from hiding a worse phase. The lease-end target stays the sum of its two parts, so a slower wake cannot hide inside the destruction’s allowance, or the reverse.
• Ticks, an exact remainder, one tick at least. Whole microseconds would let a run under 1 µs go free, and a large weight would round short runs to nothing. Counting at the trap boundary means no exit path runs unaccounted.
• Additive, normalized inheritance from entry. Otherwise a budget sheds debt by destroying the child that ran, or a light grandchild’s raw pass stalls an unrelated sibling, or an honest parent pays twice for the wait it gave the child.
• No time donation. A server thread running on its caller’s budget could be stopped mid-call by that caller’s lease and hold the server’s locks for good. Servers pay for their own CPU until measured priority inversion says otherwise (beyond).
• No trace in production. A per-pick record of every budget is a cross-principal channel that the containment claims do not cover, so it exists only in test builds.