Step 1 of 16 · commit 1: Add tickets, settickets and cputime

Tickets live with the fields p->lock protects

The first commit adds the knob and the measuring instrument, and changes no behaviour: the scheduler still ignores tickets.

Where the fields go is a locking decision. struct proc is divided by the comments above the fields: those that need p->lock, the one that needs wait_lock, and those private to the process. tickets goes in the first group (line 91). It is written by the process itself (settickets) and read by schedulers on other harts, which choose among processes they do not own; any field read across harts needs a lock, and the scheduler already holds p->lock when it looks at a process (Locks and interrupt state). The comment records the one exception the design uses later: after creation only the process itself writes its tickets, so the process may read its own field without the lock (question 6).

cputime and runstart (lines 92-93) are the instrument: the scheduler writes them around swtch, under the process’s lock, and the process reads them through a system call. Defaults are in param.h: DEFTICKETS (10) for a process that never set any, MAXTICKETS (100) as the upper bound settickets accepts.

Step 2 of 16 · commit 1: Add tickets, settickets and cputime

settickets, under the caller's own lock

The system call checks the range first (lines 123-124), with no lock: n is a local copy of the argument. Then it swaps old for new under the caller’s p->lock and returns the old count, which is how a program (or the test) can read its tickets without a second system call.

Recorded with gdb on the finished branch, where this function is unchanged: stridetest (pid 3) on hart 2 calling settickets(7), stopped at line 127. noff 1 (the p->lock), intena 1: usertrap turned interrupts on before the system call (kernel/trap.c:66), so the release on line 128 will turn them back on. sstatus read 0x200000020: SIE (bit 1) clear while the lock is held.

Step 3 of 16 · commit 1: Add tickets, settickets and cputime

The instrument, CPU time per process

Before changing the scheduler, the lab gives it a meter. Line 458 reads the time CSR just before swtch to the process; line 460 runs when the process has switched back (by yielding, sleeping or exiting) and adds the time it spent away from the scheduler to p->cputime. Both happen under the process’s lock, which the scheduler holds on both sides of swtch (Locks and interrupt state). allocproc sets cputime to 0 (line 128).

sys_cputime (in sysproc.c, after settickets) returns p->cputime plus the part of the current slice already used, r_time() - p->runstart: the caller is running, so its runstart is the moment its current slice began. It reads both under its own lock.

Why a kernel counter? A user program can count its own work (iterations of a loop), but that measures CPU received only if every hart runs at the same speed. On QEMU each hart is a host thread, and its speed varies with what else the computer is doing; Measure shows the counts straying by several percent while the kernel’s numbers stay put. The time CSR is the same clock on every hart (QEMU’s 10 MHz timebase), so CPU time measured with it does not depend on which hart ran the process.

The cost is two CSR reads per switch. Everything later in the lab is measured with it, round robin included.

Step 4 of 16 · commit 1: Add tickets, settickets and cputime

fork passes the tickets on

kfork already re-takes the child’s lock at the very end to make it RUNNABLE (kernel/proc.c:300-kernel/proc.c:302 in the original). The child’s tickets are set in the same critical section, before any scheduler can see the child as RUNNABLE: the moment another hart can pick it, its tickets are right.

The value comes from the parent, read without the parent’s lock. That is the exception recorded in proc.h: after creation only a process writes its own tickets, and the parent is busy here, in kfork. Taking the parent’s lock would mean holding two p->locks (child and parent), and nothing in the kernel defines an order between two p->locks.

allocproc gives every new process DEFTICKETS first (line 127); for a fork child line 305 overwrites it. The only process that keeps the default is init, created by userinit without a parent. exec does not touch tickets at all, so nice 3 cmd works: nice sets its own tickets and becomes cmd.

Recorded on the finished branch at the equivalent line (gdb, stridetest’s first fork: hart 2, pid 3 creating pid 4, noff 1, intena 1).

Step 5 of 16 · commit 2: Add stridetest and nice

The test: CPU time in a window

Each spinner runs a busy loop in chunks of 50,000 iterations; after each chunk it asks the kernel for the time (uptime, in ticks). The first time it sees the clock inside the window [wstart, wend) it reads its CPU time (line 50); when the window has ended it reads it again (line 56). The difference is the CPU this process received during the window, measured by the kernel; its share of all spinners’ CPU time is what the checks use. Both readings are taken within one chunk (well under a millisecond of CPU) of the window’s edges.

The chunks finished inside the window are counted too (line 52) and printed beside the CPU shares, as information. They are what a user program would naturally measure, and Measure shows how much they stray on QEMU.

x is volatile so that the compiler cannot delete the loop. A process that is not running reads nothing, and when it next runs after wend it leaves at its first look at the clock. Every spinner reports one 16-byte struct result on a pipe; the parent reads six of them. Six results fit in the pipe’s 512-byte buffer, so no writer waits for space in the middle of its write, and pipewrite holds the pipe’s lock for the whole of it: the results cannot interleave.

Step 6 of 16 · commit 2: Add stridetest and nice

Sleepers that really sleep

measure forks the spinners and, for the sleeper and newcomer checks, an alarm process. The sleeper (line 100) and the parent (line 112, before it forks the newcomer) block in read on the go pipe; the alarm waits until the window starts and writes one byte.

The comment on lines 77-79 explains why the sleeper does not simply call pause until the window. A sleeper that did would show no burst at all on the stride kernel: sys_pause waits on &ticks and is woken at every tick (kernel/sysproc.c:83), so a “sleeping” process was picked, and charged, again and again (question 4). A process blocked in read is woken exactly once. The alarm itself may use pause: its own share does not matter.

In the newcomer check the parent is the one asleep, so the newcomer is forked by a process that slept for 30 ticks. That is the case commit 3 gets wrong: its fork copies the parent’s pass.

Step 7 of 16 · commit 2: Add stridetest and nice

The checks, and round robin's result

The share check runs six spinners with 1, 1, 2, 2, 3 and 3 tickets. With six, no process ever deserves more than one hart (a 3-ticket process deserves 3/12 of the CPU, 0.75 of a hart on three harts), so the ideal shares, 167, 333 and 500 per mille for the three pairs, hold on 1 to 4 harts. Each pair’s share of CPU time must be within 20% (line 203). The sleeper and newcomer checks (lines 214-232) use equal tickets and compare the late process’s CPU time with the average of the other five, between 0.67 and 1.5.

On this commit the scheduler still ignores tickets, and the test says so (3 harts):

stridetest: share: tickets 1: cpu 333 per mille (ideal 167); chunks 332 per mille
stridetest: share: tickets 2: cpu 339 per mille (ideal 333); chunks 344 per mille
stridetest: share: tickets 3: cpu 326 per mille (ideal 500); chunks 323 per mille
stridetest: share: FAIL
stridetest: sleeper: cpu 1603 ms, the others 1482 ms on average (ratio 108/100)
stridetest: sleeper: OK
stridetest: newcomer: cpu 1403 ms, the others 1522 ms on average (ratio 92/100)
stridetest: newcomer: OK

Round robin keeps no history, so it cannot be unfair to a sleeper: the late checks pass. They are there for what comes next. Every check is computed from the CPU times; the chunk shares are not checked, and the final line, ALL OK or SOME FAILED, covers the checks only.

Step 8 of 16 · commit 3: Run the runnable process with the smallest pass

The scan: look at everyone, one lock at a time

The loop body changes shape. The original ran each RUNNABLE process as soon as it met it (kernel/proc.c:447). Now the scan only looks: for each slot it takes the lock, reads the state and the pass, remembers the slot if it is RUNNABLE with a smaller pass than the best so far, and releases the lock before moving on (lines 457-464). Ties go to the earlier slot, because only a strictly smaller pass replaces the best.

One lock at a time, never two (the comment on lines 452-454): no lock-order question can arise among p->locks, whatever the other harts do (question 3). The price is that bestpass and best are only a record of what was true while each lock was held.

If nothing is RUNNABLE, the hart waits for an interrupt (wfi) and then starts over, as the original did. The intr_on(); intr_off(); at the top is unchanged: interrupts are off during the whole scan, so intena is 0 for every acquire here (Locks and interrupt state).

Step 9 of 16 · commit 3: Run the runnable process with the smallest pass

Re-check under the lock, charge, run

Now the scheduler acts on what it saw. It takes the candidate’s lock again and checks the state again (line 474): another hart may have picked the same process in between, or it may have exited or gone to sleep. If it is no longer RUNNABLE, the lock is released (line 494) and the outer loop scans again. Without this test, two harts run one process at once (clinic 3, where it killed every boot).

If it is still RUNNABLE, the pass may no longer be the smallest (another process may have woken up), and the code does not care: it runs it anyway. That is the “approximate minimum” of question 3, corrected by the next pick.

Line 476 is the whole of stride scheduling’s accounting: add STRIDE1 / tickets to the pass, under the lock, before swtch. Lines 481-492 are commit 1’s: the switch, with the CPU-time readings around it. The candidate’s lock is held across swtch and released by the process, exactly as before (Locks and interrupt state).

Recorded with gdb on the finished branch at the charging line: hart 1 picked pid 6 (1 ticket) at pass 9,317,318, holding pid 6’s lock, noff 1, intena 0, on hart 1’s scheduler stack.

Step 10 of 16 · commit 3: Run the runnable process with the smallest pass

Commit 3's fork copies the parent's pass

Commit 3 gives a child its parent’s pass (line 306), the natural first idea: the child continues where its parent is. (proc.h gets uint64 pass next to tickets, and param.h gets STRIDE1, 1 << 20.)

The test shows what is wrong with it, and with leaving a sleeper’s pass alone (3 harts):

stridetest: share: OK
stridetest: sleeper: cpu 2901 ms, the others 1220 ms on average (ratio 237/100)
stridetest: sleeper: FAIL
stridetest: newcomer: cpu 2903 ms, the others 1221 ms on average (ratio 237/100)
stridetest: newcomer: FAIL

Shares are right now. But the sleeper’s pass stood still for 30 ticks while the others advanced, so when it woke it had the smallest pass by far and ran without a break: 2.9 seconds of CPU in a 3-second window, where the others got about 1.2 each. The newcomer is the child of a parent that slept in read, so it inherited the same stale pass and the same burst. Both are “not competing for a while, then competing”, and the next commit treats them alike.

Step 11 of 16 · commit 4: Start new and woken processes at virtual time

Virtual time, and a lock of its own

vtime.now is the largest pass with which any process has been picked. Because each pick is the smallest pass a scheduler found, vtime.now follows the front of the queue: where a process that has been competing all along would be now.

catchup (lines 41-48) is called whenever a process becomes RUNNABLE after not competing, and raises its pass to virtual time if it is behind. It never lowers a pass: a process that used a whole stride and slept for a moment is ahead, and stays ahead.

The lock is the interesting part. vtime.now is written by every hart’s scheduler and read by wakeup on any hart, so it needs one. Every caller already holds a p->lock, and catchup takes nothing else while holding vtime.lock: the comment on line 32 records its place in the lock order, after p->lock, as a leaf. A leaf lock cannot be part of a cycle. The alternative, computing the current minimum at wakeup time, would need every other process’s lock while holding this one’s (question 5).

The state shown is the recorded wakeup of the next steps, one level deeper: inside catchup the waking hart holds the pipe’s lock, the sleeper’s p->lock and vtime.lock, noff 3.

Step 12 of 16 · commit 4: Start new and woken processes at virtual time

The scheduler moves virtual time

Just before charging, the scheduler raises virtual time to the pass the chosen process had (lines 500-503), under vtime.lock, nested inside the chosen process’s p->lock. The order matters: virtual time is the pass before the charge, the position of the front of the queue. Raising it after adding the stride would put virtual time one slice ahead of the front, and every waking process would start one slice behind the processes already competing.

“Never let it go back” (the > on line 501) keeps virtual time monotonic even though the three harts pick at slightly different passes: in the recorded trace, a hart picked a 3-ticket process at 9,317,314 while virtual time was already 9,317,318, and virtual time stayed where it was.

The nesting is the one recorded in the lock-order comment: p->lock then vtime.lock. The scheduler holds no other lock here, and wakeup nests them the same way, so the two can never wait for each other in opposite orders.