Extension labs · lab 8 · Scheduling · ★★★☆☆

Stride scheduling with nice

The scheduler in this tree gives every runnable process the same treatment: each of the three harts walks the process table in slot order and runs whatever is RUNNABLE, one timer tick at a time. A compile job and an editor get the same share of the CPU, and there is no way to ask for more or less.

In this lab you give each process a number of tickets and replace round robin with stride scheduling: a process with twice the tickets should get twice the CPU, and the schedule should be deterministic, not a lottery. The rule fits in one sentence. The questions start when you try to apply it on three harts at once. How do you find “the process with the smallest value” when three schedulers scan the same table, each holding one lock at a time? What value should a process have when it wakes up after a long sleep, or when it has just been created? When should a process be charged for the CPU it uses? What happens when the counter wraps? And what can a proportional-share scheduler promise at all when there are as many harts as processes?

The reference solution is five small commits. You will measure round robin and stride scheduling side by side, on 1, 2 and 3 harts, with a CPU-time counter the kernel keeps for every process, and break the design five ways on purpose: one break leaves a process running on two harts at once, and in another two schedulers deadlock and the third hart hangs behind them.

Read first: Tour 11: From a timer tick to a context switch, Tour 12: One scheduler per hart, Tour 13: swtch and the lock handed across a context switch, Tour 14: pause(n) and the tick counter, Tour 16: sleep and wakeup, and the lost-wakeup problem, Tour 20: fork, Tour 45: One complete time slice on three harts, Tour 50: noff and intena through a sleep, a yield and an interrupt · Locks and interrupt state, The stacks of xv6

What this lab teaches

Where the original scheduler makes its choice, and what share of the CPU round robin really gives each process on three harts (measured).
How a per-process counter that advances at a rate inversely proportional to tickets turns a ratio into a deterministic schedule, and what integer division does to it.
How to choose a minimum over a table that three schedulers scan at once, when each entry has its own lock: what can change between looking and acting, and which lock orders are safe.
When a process should be charged for a time slice, and how the timer and sleeping interact with that choice.
What a process that was not competing for the CPU (asleep, or new) should start from, why that needs shared state, and which lock protects it.
How fork, exec and the scheduler share a field that one process writes and other harts read.
How fast a counter of virtual time can really grow, and how many bits it needs.
What proportional share can and cannot mean when no process can use more than one hart.
Why a user program’s own count of work done is a poor measure of the CPU it received on an emulator, and what to measure instead.

The reference branch

ext/08-stride in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 5 commits.

git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-stride 06aad25   # start your own
git diff 06aad25 origin/ext/08-stride   # only when you want the answer

1. The spec

Tickets. Every process has a number of tickets, its claim on the CPU relative to the other processes that want to run. A new system call sets it:

int settickets(int n);   // 1 <= n <= 100; returns the old ticket count, or -1

A process that never called settickets has 10 tickets. A child of fork has its parent’s tickets, and exec keeps them. A user command nice runs a command with a given number of tickets (nice 3 stridetest 1 2). (In this lab nice takes a ticket count, so a larger number means more CPU, the opposite of Unix niceness.)

A measuring instrument. The kernel keeps, for every process, the CPU time it has used: the scheduler reads the time CSR when it switches to a process and when the process switches back, and adds the difference. A second system call returns it:

uint64 cputime(void);    // CPU time used by the caller, in time CSR units, including
                         // the slice it is running in (10,000,000 per second on QEMU)

Stride scheduling. Each process has a stride, STRIDE1 / tickets for a large constant STRIDE1, and a pass. The scheduler runs the RUNNABLE process with the smallest pass and advances that process’s pass by its stride for the time slice it runs. A process with three times the tickets advances a third as fast, so it is chosen three times as often.

Constraints.

The scheduler still runs on every hart at once, as scheduler does now. Nothing may deadlock, and no process may ever run on two harts at the same time.
A process that slept for a long time, or was just created, while others ran must neither get a burst of CPU to “make up” for lost time nor wait behind everyone else.
Ctrl-P shows each process’s tickets and pass.
usertests -q must print ALL TESTS PASSED on 3 harts.

The test program, stridetest, prints one line per check, plus measurements:

$ stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 166 per mille (ideal 167); chunks 155 per mille
stridetest: share: tickets 2: cpu 327 per mille (ideal 333); chunks 328 per mille
stridetest: share: tickets 3: cpu 506 per mille (ideal 500); chunks 516 per mille
stridetest: share: OK
stridetest: sleeper: cpu 1601 ms, the others 1481 ms on average (ratio 108/100)
stridetest: sleeper: OK
stridetest: newcomer: cpu 1599 ms, the others 1480 ms on average (ratio 108/100)
stridetest: newcomer: OK
stridetest: ALL OK

tickets: settickets rejects 0, -3 and 101, returns the old count, and a child of fork, and a program after exec, have the parent’s tickets.
share: six CPU-bound processes with 1, 1, 2, 2, 3 and 3 tickets. Each reads its cputime() when it first sees the clock inside a window of 50 ticks (about 5 s) and again when the window has ended; its share of all six processes’ CPU time in the window is its share of the CPU. The two processes with t tickets should get t/6 of it between them, within 20%. With six processes every process wants more than its share on 1, 2, 3 or 4 harts, so the ideal is the same on all of them.
sleeper and newcomer: six processes with equal tickets. One of them sleeps through the first 30 ticks (sleeper) or is only created after them (newcomer). During the next 30 ticks its CPU time must be between 0.67 and 1.5 times the average of the other five.

Each process also counts “chunks” (50,000 iterations of a busy loop) finished inside the window. The chunk shares are printed beside the CPU shares for information and are not checked: on QEMU a chunk takes more or less time depending on how fast the host runs each hart (see Measure). stridetest t1 t2 ... runs one spinning process per ticket count, prints the shares and checks nothing.

2. Think first

Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.

1What does round robin give, and where is the choice made?

Six CPU-bound processes run on the original kernel, on three harts. Before any code: what share of the CPU does each get? Then find the line where the original scheduler decides which process runs next. What, exactly, decides it, and what would a scheduler that respects tickets need to know at that moment that this one does not?

Check yourself

1warm-upChoose one

On the original kernel, three harts run six CPU-bound processes. Nothing else is runnable. Which statement best describes the shares?

Processes in low slots get more, because every scan starts at proc[0].Shares depend on how long ago each process last ran, like a priority that grows while waiting.Each hart keeps running the same process, so three get a whole hart and three get nothing.About one sixth each: every RUNNABLE process gets one time slice per trip of a hart’s scan.

2Stride and pass, by hand

The spec defines the rule: run the RUNNABLE process with the smallest pass, then add its stride, STRIDE1 / tickets. Try it on paper before writing any code. Three processes on one hart, A with 1 ticket, B with 2, C with 3, all starting at pass 0, ties going to the earlier slot (A, then B, then C). Take STRIDE1 = 6. Write down the first six picks and the passes after each. What pattern repeats? Then: in the kernel, how big should STRIDE1 be, and what does integer division do to the ratios?

Check yourself

1warm-upPut in order

One hart, STRIDE1 = 6. A has 1 ticket, B 2, C 3; all passes start at 0; ties go to the earlier slot (A before B before C). Put the first six picks in order.

A runs: pass 0 → 6
B runs: pass 0 → 3
B runs: pass 3 → 6
C runs: pass 2 → 4
C runs: pass 4 → 6
C runs: pass 0 → 2

2solidType a number

In the reference, STRIDE1 is 1 << 20. What is the stride of a process with 3 tickets, as the kernel computes it?

decimal, 0x hex or 0b binary

3Finding the minimum on three harts

Every hart runs its own scheduler loop over the same proc[], and each entry is protected by its own p->lock (Locks and interrupt state). To find the smallest pass, a scheduler has to look at every RUNNABLE process. Design the loop. Which locks are held while you look, and while you decide? What can another hart do to “your” minimum between the moment you saw it and the moment you start it? What would you check, and what would you do if the check fails? Is the result still the true minimum?

Check yourself

1solidChoose one

A scheduler scans with one lock at a time, finds init (pid 1, the only RUNNABLE process at boot) as its minimum, takes init’s lock again and runs it without checking its state. What happens on three harts?

Nothing: the second hart waits on init’s lock until init is no longer RUNNABLE, then skips it.init runs twice in a row on the same hart, which is harmless.Two harts can switch to init, which then runs on both at once on one kernel stack.The second hart panics in acquire, because the first hart holds the lock.

2deepTrue or false, and why

True or false: a scheduler that keeps its current best candidate’s p->lock while it acquires the locks of the later slots, always scanning from slot 0 to slot 63, can deadlock with another hart running the same scheduler.

TrueFalse

Why?

Interrupts are off in the scheduler, so no other hart can take a p->lock at the same time.A hart that already holds a p->lock is allowed to acquire it again.Every hart acquires p->locks in increasing slot order while holding only a lower slot, and no other code holds two p->locks, so no cycle can form.

4When is a process charged?

A process’s pass must advance when it uses the CPU. You could add the stride when the scheduler picks it, before swtch, or when it gives the CPU back (in yield, or on every way of leaving: yield, sleep, exit). Which do you choose, and which lock protects the update? Consider how long a time slice really is in this tree, and a process that runs for a millisecond and then sleeps, over and over.

Check yourself

1solidChoose one

In the reference (charge one stride per pick), process P with 5 tickets calls pause(30) while five CPU-bound processes with 5 tickets each keep three harts busy. What happens to P’s pass during the 30 ticks?

It advances by exactly 30 ticks’ worth of the machine’s virtual time, because sleep charges for time slept.It keeps pace with the others: pause makes P RUNNABLE at every tick, and each pick charges it a stride.It does not change: a sleeping process is never charged.It drops back to 0, because a sleeping process is reset.

5What pass should a new or woken process start from?

While a process sleeps, the others’ passes keep growing; its own stays put. When it wakes, what should its pass be? Consider keeping it, setting it to 0, and setting it to “the current minimum”. Then the same question for a process created by fork. For each choice, predict what the process and the others experience. Finally: where would the information you need live, and which locks are held at the moment you need it?

The reference design

Keep the old pass (commit 3 of the reference does this): the sleeper wakes with the smallest pass by far and runs without a break until it has caught up, while everyone else waits. stridetest measured it on commit 3: during the 30 ticks after waking, the sleeper used 2.37 and 2.38 times the average CPU time of the other five (two runs), a whole hart to itself. Commit 3 also gives a child its parent’s pass, and the parent had been asleep in read, so the newcomer got the same burst (2.37 both times).

Pass 0 for a new process is worse, and in a surprising way (clinic 1): new processes start far behind the old ones, and any process that sleeps and wakes up is then stuck behind all of them.

The current minimum is the right value, but computing it at that moment is the problem: wakeup holds the sleeper’s p->lock, and its callers hold more (tickslock in clockintr, a pipe’s lock in pipewrite). Scanning every other process’s p->lock from there would hold two p->locks at once, in no fixed order, on every wakeup.

The reference keeps virtual time instead: one variable, vtime.now, “the largest pass with which any process has been picked”. Every scheduler raises it when it picks (the pick is the minimum it found, so vtime.now follows the front of the queue), and catchup(p), called by kfork, wakeup and kkill where a process becomes RUNNABLE, raises p->pass to vtime.now if it is lower. A process that slept briefly and is still ahead keeps its pass. vtime has its own spinlock: it is written by three schedulers and read by wakeups on any hart, always while a p->lock is held, and nothing is acquired while holding it. That makes it a leaf after p->lock in the lock order (Locks and interrupt state). On commits 4 and 5 the sleeper and the newcomer used 1.08 times the others’ average in four quiet runs, and 0.99 to 1.13 in 24 runs measured while the computer was busy with other work.

“Largest pass picked” is a choice with a cost on several harts: when there are no more runnable processes than harts, passes diverge (question 8), and the maximum follows the fastest-moving one.

Check yourself

1deepFill in the machine state

The stridetest sleeper (pid 12) sleeps in read on a pipe. Another process writes to the pipe; pipewrite calls wakeup, which finds the sleeper and is about to call catchup on it (line 644 of the reference’s proc.c). Fill in the state of the waking hart at that moment.

Privilege modeActive stackInterrupts (sstatus.SIE)noffintena

2solidChoose one

A variant of the reference starts every new process at pass 0 (it leaves out catchup in kfork) but keeps catchup in wakeup. The machine has been up for a while. What did stridetest’s sleeper and newcomer get?

Nothing: both waited until the new spinners had caught up with virtual time, which was after the window.Their fair share, because all six spinners are new and start at 0 together.A burst: a process starting at pass 0 has the smallest pass and runs without a break.A kernel panic, because a pass of 0 is invalid.

6Tickets across fork and exec, and who may read them

settickets writes p->tickets; the scheduler on any hart reads it to compute a stride; kfork must give the child the parent’s tickets. Which lock protects p->tickets? In kfork the code holds the child’s p->lock when it sets the child up. Can it take the parent’s lock to read the parent’s tickets? Must it? And what should exec do?

Check yourself

1solidChoose all that apply

In the reference, which of these can change some process’s p->tickets?

7How fast does a pass grow?

A pass only grows, and so does virtual time. Estimate how fast. Start with a CPU-bound process with 1 ticket alone on its hart, picked once per 0.1 s tick, each pick adding STRIDE1 = 1 << 20. Then ask whether that is really the fastest: what else makes the scheduler pick a process? How long until a 32-bit unsigned pass wraps, and a 64-bit one? What happens to the scheduler when a pass wraps, and could you keep 32 bits and still be correct?

Check yourself

1solidType a number

A 1-ticket process runs alone on a hart and is picked once per timer tick (10 per second). Each pick adds 1 << 20 to its 32-bit unsigned pass, starting at 0. After how many seconds does the pass wrap (to the nearest second)?

decimal, 0x hex or 0b binary

8What can stride scheduling promise on three harts?

Run stridetest 1 2 3 in your head on three harts: three CPU-bound processes with 1, 2 and 3 tickets. What shares do you expect? Then predict their passes after a few seconds, and what that does to virtual time.

Check yourself

1solidChoose one

On the reference, three harts, stridetest 1 2 3 (three CPU-bound processes with 1, 2 and 3 tickets, nothing else running). What shares were measured?

The 1-ticket process starves, because its pass grows fastest.About 1/6, 2/6 and 3/6.The 3-ticket process gets a hart; the other two share the remaining two in a 1:2 ratio.About one third each.

3. Build it

Start.

git checkout -b my-stride 06aad25

Milestones, in an order that keeps the system bootable after each one.

Tickets, settickets and a CPU-time counter. Add tickets to struct proc (with the fields protected by p->lock), DEFTICKETS and MAXTICKETS to param.h, the system call (number, table entry, usys.pl, user.h), a default in allocproc and a copy in kfork. Add the measuring instrument too: two fields, a reading of the time CSR before and after the scheduler’s swtch to a process, and cputime(). Do it now, before you change the scheduler, so that you can measure round robin with the same instrument. Test: usertests -q.
The test and nice. Write user/stridetest.c and user/nice.c and add both to UPROGS. Run stridetest on round robin and keep the output: tickets: OK, share: FAIL, and the sleeper and newcomer checks pass. This is the contrast for everything that follows.
Pick the smallest pass. Add pass and STRIDE1, rewrite the scan in scheduler (keeping the CPU-time lines around swtch), charge the pick. Test: stridetest (share should pass; watch the sleeper and newcomer lines), usertests -q. If the kernel panics or hangs before the first prompt, go to clinic 3.
Virtual time. Add the shared value and its lock, and move processes that become RUNNABLE after not competing up to it. Test: stridetest (all OK), usertests -q, stridetest again.
Make it visible. Print tickets, pass and virtual time from procdump. Type Ctrl-P during stridetest 1 2 3 and during stridetest 1 1 2 2 3 3, and explain the passes.

Also run on one hart (QEMU -smp 1) and on two: with one hart nothing runs in parallel, so the share is purely the scheduler’s doing, and bugs that need two harts (clinics 3 and 4) disappear, which is itself worth seeing.

Debugging advice. To use gdb, start QEMU with make qemu-gdb (it adds -S and a gdb port of its own, which it writes into .gdbinit) and run ${TOOLPREFIX}gdb kernel/kernel in another terminal. TOOLPREFIX is your RISC-V toolchain’s prefix, the same one xv6’s Makefile detects (riscv64-unknown-elf-, riscv64-linux-gnu- or riscv64-elf-); set it with export TOOLPREFIX=riscv64-unknown-elf- or whichever you have. On Debian/Ubuntu/WSL, gdb-multiarch also works as the debugger.

A hang with no output: interrupt the running QEMU from gdb (Ctrl-C) and run info threads and thread apply all bt. Harts spinning in acquire called from scheduler are a lock order problem (clinic 4). Print the lock of each slot: proc[i].lock.locked and (char *)proc[i].lock.cpu - (char *)cpus (divide by 128, the size of struct cpu, to get the holder’s hart).
A panic at boot after hart 2 starting, such as sched locks or acquire, with a scheduler change: suspect one process running on two harts (clinic 3). In gdb, two harts with the same cpus[i].proc prove it.
Shares that look wrong: trust cputime(), not a count of loop iterations (Measure shows why). To watch the schedule itself, a gdb breakpoint at the charging line with a command list that prints best->pid, best->tickets, best->pass and vtime.now, then continues, gives the sequence of picks without stopping the machine for long.
pause is not a sleep for this lab’s purposes: it wakes every tick (question 4). Make test processes that must really sleep block in read on a pipe.

4. Debugging clinic

Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.

1New processes start at pass 0

kfork leaves the child’s pass at the 0 that allocproc set, instead of moving it up to virtual time; woken processes are still moved up:

   acquire(&np->lock);
   np->tickets = p->tickets;
-  catchup(np);
   np->state = RUNNABLE;
   release(&np->lock);

It looks harmless: a new process “has used no CPU yet”.

What happened when we ran it

$ stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 167 per mille (ideal 167); chunks 164 per mille
stridetest: share: tickets 2: cpu 325 per mille (ideal 333); chunks 335 per mille
stridetest: share: tickets 3: cpu 507 per mille (ideal 500); chunks 499 per mille
stridetest: share: OK
stridetest: sleeper: cpu 0 ms, the others 1810 ms on average (ratio 0/100)
stridetest: sleeper: FAIL
stridetest: newcomer: cpu 0 ms, the others 1802 ms on average (ratio 0/100)
stridetest: newcomer: FAIL
stridetest: SOME FAILED
$
1 sleep  init tickets 10 pass 3355424
2 sleep  sh tickets 10 pass 15309206
vtime 15204349

2Woken processes keep their old pass

wakeup makes a sleeper RUNNABLE without moving it up to virtual time (new processes still get catchup):

       if (p->state == SLEEPING) {
-        catchup(p);
         p->state = RUNNABLE;
       }

What happened when we ran it

$ stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 166 per mille (ideal 167); chunks 151 per mille
stridetest: share: tickets 2: cpu 326 per mille (ideal 333); chunks 319 per mille
stridetest: share: tickets 3: cpu 506 per mille (ideal 500); chunks 529 per mille
stridetest: share: OK
stridetest: sleeper: cpu 2920 ms, the others 1228 ms on average (ratio 237/100)
stridetest: sleeper: FAIL
stridetest: newcomer: cpu 1600 ms, the others 1481 ms on average (ratio 108/100)
stridetest: newcomer: OK
stridetest: SOME FAILED
[...]
stridetest: sleeper: cpu 2905 ms, the others 1222 ms on average (ratio 237/100)
stridetest: sleeper: FAIL
stridetest: newcomer: cpu 1598 ms, the others 1483 ms on average (ratio 107/100)
stridetest: newcomer: OK

3The candidate is not re-checked under its lock

After the scan, the scheduler takes the chosen process’s lock and runs it, without checking that it is still RUNNABLE:

     acquire(&best->lock);
-    if (best->state == RUNNABLE) {
+    {
       // Advance virtual time to best's pass, then charge best

What happened when we ran it

# boots 1 and 3
xv6 kernel is booting

hart 1 starting
hart 2 starting
panic: sched locks

# boot 2
xv6 kernel is booting

hart 2 starting
hart 1 starting
panic: scause=0xpanic: 8r000701eelease sepc=0x
3fffffd

# boot 4
xv6 kernel is booting

hart 1 starting
hart 2 starting
usertrap(): unexpected scause 0xc pid=1
scause=0xc sepc=0x8000fe30 stval=0x8000fe30
  panic:           sepc=0x50505050k5050504 stval=ernel0x50505trap0505050
504

# boot 5, gdb attached after the panic
xv6 kernel is booting

hart 1 starting
hart 2 starting
panic: sched locks
[...]
  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [running]) panic (s=s@entry=0x800071b0 "sched locks") at kernel/printk.c:144
  2    Thread 1.2 (CPU#1 [running]) acquire (lk=0x800211f8 <disk+296>) at kernel/spinlock.c:37
  3    Thread 1.3 (CPU#2 [running]) acquire (lk=lk@entry=0x8000fe30 <proc>) at kernel/spinlock.c:37

Thread 3 (Thread 1.3 (CPU#2 [running])):
#0  acquire (lk=lk@entry=0x8000fe30 <proc>) at kernel/spinlock.c:37
#1  0x000000008000207e in wakeup (chan=0x80015e60 <bcache+24>) at kernel/proc.c:635
#2  0x0000000080005d16 in virtio_disk_intr () at kernel/virtio_disk.c:327
#3  0x00000000800026a8 in devintr () at kernel/trap.c:201
#4  0x0000000080002802 in kerneltrap () at kernel/trap.c:149
#5  0x0000000080005768 in kernelvec () at kernel/kernelvec.S:38
[...]

Thread 2 (Thread 1.2 (CPU#1 [running])):
#0  acquire (lk=0x800211f8 <disk+296>) at kernel/spinlock.c:37
#1  0x0000000080005c34 in virtio_disk_rw (b=b@entry=0x80015e60 <bcache+24>, write=write@entry=0) at kernel/virtio_disk.c:290
#2  0x0000000080002dec in bread (dev=dev@entry=1, blockno=blockno@entry=1) at kernel/bio.c:98
#3  0x0000000080003704 in readsb (dev=1, sb=0x8001e508 <sb>) at kernel/fs.c:35
#4  fsinit (dev=dev@entry=1) at kernel/fs.c:44
#5  0x00000000800019a0 in forkret () at kernel/proc.c:582
[...]

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  panic (s=s@entry=0x800071b0 "sched locks") at kernel/printk.c:144
#1  0x0000000080001f90 in sched () at kernel/proc.c:542
#2  0x0000000080002030 in sleep () at kernel/proc.c:623
#3  0x0000000080005c34 in virtio_disk_rw (b=b@entry=0x80015e60 <bcache+24>, write=write@entry=0) at kernel/virtio_disk.c:290
#4  0x0000000080002dec in bread (dev=dev@entry=1, blockno=blockno@entry=1) at kernel/bio.c:98
#5  0x0000000080003704 in readsb (dev=1, sb=0x8001e508 <sb>) at kernel/fs.c:35
#6  fsinit (dev=dev@entry=1) at kernel/fs.c:44
#7  0x00000000800019a0 in forkret () at kernel/proc.c:582
[...]
$1 = (struct proc *) 0x8000fe30 <proc>
$2 = (struct proc *) 0x8000fe30 <proc>
$3 = (struct proc *) 0x0
[...]
$11 = {locked = 1, name = 0x80007680 "virtio_disk", cpu = 0x8000fb30 <cpus+256>}

Five boots, five deaths, all before the first prompt. The kernel never reached init: starting sh.

gdb shows why in boot 5. $1 and $2 are cpus[0].proc and cpus[1].proc: both harts are running the same process, proc[0] at 0x8000fe30, which is pid 1. And both harts are inside forkret → fsinit → readsb → bread → virtio_disk_rw, the first process’s very first steps. Here is how. At boot, init is the only RUNNABLE process and all three schedulers scan the table continuously. Two harts’ scans see init RUNNABLE. One takes init’s lock first, sets RUNNING and switches to it. The other waits on the lock; init releases it at the top of forkret (kernel/proc.c:520 in the original), and the second hart gets it, sets RUNNING again and switches to init’s saved context. That context was never updated (init has not switched out yet), so it still says what allocproc put there: ra = forkret, sp = the top of init’s kernel stack. The second hart starts a second copy of forkret on the same kernel stack; static int first is still 1 for both, so both run fsinit.

From there the two copies overwrite each other’s stack frames and saved registers, and what breaks first varies: sched found noff not 1 (panic: sched locks, boots 1, 3 and 5; in boot 5 hart 0 is the one that panicked, hart 1 is the other copy, and hart 2’s disk interrupt waits for init’s lock), or init took an instruction page fault in user mode while the kernel jumped to 0x8000fe30, the address of proc[0], as if it were code (boot 4). In boots 2 and 4 two harts printed at once: after panicking is set, printk no longer takes its lock, so two messages interleave character by character (in boot 2 a panic: release and a kerneltrap report; in boot 4 the second line of the usertrap() message and panic: kerneltrap).

The window looks tiny (between release at the end of the scan and acquire of the candidate), but at boot it is hit almost every time, because idle harts do nothing but scan. The re-check costs one comparison. The general rule: what you saw under a lock you have released is a hint; act only on what you see under the lock you hold.

4Keeping the candidate’s lock, with scans that start at different slots

The scan keeps the best candidate’s lock (so nobody can take the candidate away, and no re-check is needed), and, to break ties fairly, each hart starts its next scan after the slot it last ran:

best = 0;
for (int i = 0; i < NPROC; i++) {
  p = &proc[(first + i) % NPROC];
  acquire(&p->lock);
  if (p->state == RUNNABLE && (best == 0 || p->pass < best->pass)) {
    if (best)
      release(&best->lock);
    best = p; // keep its lock: nobody can take it from us
  } else {
    release(&p->lock);
  }
}
...
first = (best - proc + 1) % NPROC; // break ties round robin

What happened when we ran it

$ stridetest
stridetest: tickets: OK
[... nothing more; after 5 minutes gdb was attached:]
  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [running]) acquire (lk=lk@entry=0x80010730 <proc+2304>) at kernel/spinlock.c:37
  2    Thread 1.2 (CPU#1 [running]) acquire (lk=lk@entry=0x80010a30 <proc+3072>) at kernel/spinlock.c:37
  3    Thread 1.3 (CPU#2 [running]) acquire (lk=lk@entry=0x80010730 <proc+2304>) at kernel/spinlock.c:37

Thread 3 (Thread 1.3 (CPU#2 [running])):
#0  acquire (lk=lk@entry=0x80010730 <proc+2304>) at kernel/spinlock.c:37
#1  0x0000000080001e64 in scheduler () at kernel/proc.c:481
#2  0x0000000080000ea0 in main () at kernel/main.c:44

Thread 2 (Thread 1.2 (CPU#1 [running])):
#0  acquire (lk=lk@entry=0x80010a30 <proc+3072>) at kernel/spinlock.c:37
#1  0x0000000080001e64 in scheduler () at kernel/proc.c:481
#2  0x0000000080000ea0 in main () at kernel/main.c:44

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  acquire (lk=lk@entry=0x80010730 <proc+2304>) at kernel/spinlock.c:37
#1  0x00000000800020cc in wakeup (chan=chan@entry=0x800078c0 <ticks>) at kernel/proc.c:635
#2  0x0000000080002696 in clockintr () at kernel/trap.c:172
#3  0x0000000080002716 in devintr () at kernel/trap.c:215
#4  0x0000000080002758 in usertrap () at kernel/trap.c:69
#5  0x0000003ffffff09c in ?? ()
[...]
proc[5] pid 8 state 3 lock 0 held by cpus+2147419600 name stridetest
proc[6] pid 9 state 3 lock 1 held by cpus+128 name stridetest
proc[7] pid 10 state 4 lock 0 held by cpus+2147419600 name stridetest
proc[8] pid 11 state 3 lock 1 held by cpus+256 name stridetest

5A 32-bit pass

pass, bestpass and vtime.now are uint (32 bits) instead of uint64. To see the wrap at once rather than after a while (question 7), the experiment also starts virtual time 20 strides before 2^32:

-  uint64 pass;          // stride scheduling: CPU used, in virtual time
+  uint pass;            // stride scheduling: CPU used, in virtual time
...
-} vtime;
+} vtime = {.now = 0xffffffff - 20 * STRIDE1}; // EXPERIMENT: start 20 strides before the wrap

What happened when we ran it

$
1 sleep  init tickets 10 pass 4277456056
2 run    sh tickets 10 pass 4278294912
vtime 4278190055
stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 166 per mille (ideal 167); chunks 160 per mille
stridetest: share: tickets 2: cpu 326 per mille (ideal 333); chunks 331 per mille
stridetest: share: tickets 3: cpu 506 per mille (ideal 500); chunks 507 per mille
stridetest: share: OK
stridetest: sleeper: cpu 0 ms, the others 1803 ms on average (ratio 0/100)
stridetest: sleeper: FAIL
stridetest: newcomer: cpu 0 ms, the others 1800 ms on average (ratio 0/100)
stridetest: newcomer: FAIL
stridetest: SOME FAILED
$
1 sleep  init tickets 10 pass 4277456056
2 run    sh tickets 10 pass 89844
vtime 4294952283
stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 666 per mille (ideal 167); chunks 673 per mille
stridetest: share: tickets 2: cpu 333 per mille (ideal 333); chunks 326 per mille
stridetest: share: tickets 3: cpu 0 per mille (ideal 500); chunks 0 per mille
stridetest: share: FAIL
stridetest: sleeper: cpu 0 ms, the others 1802 ms on average (ratio 0/100)
stridetest: sleeper: FAIL
stridetest: newcomer: cpu 0 ms, the others 1802 ms on average (ratio 0/100)
stridetest: newcomer: FAIL
stridetest: SOME FAILED

5. The reference solution

Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:

Open the reveal tour →

Or read the commits

c7b3ffb Add tickets, settickets and cputime
kernel/param.h
@@ -11,4 +11,6 @@
1111#define NBUF (MAXOPBLOCKS * 3) // size of disk block cache
1212#define FSSIZE 2000 // size of file system in blocks
1313#define MAXPATH 128 // maximum file path name
1414#define USERSTACK 1 // user stack pages
15#define DEFTICKETS 10 // tickets of a process that never set any
16#define MAXTICKETS 100 // most tickets settickets() allows
kernel/proc.c
@@ -123,8 +123,10 @@ allocproc(void)
123123
124124found:
125125 p->pid = allocpid();
126126 p->state = USED;
127 p->tickets = DEFTICKETS;
128 p->cputime = 0;
127129
128130 // Allocate a trapframe page.
129131 if ((p->trapframe = (struct trapframe *)kalloc()) == 0) {
130132 freeproc(p);
@@ -297,8 +299,11 @@ kfork(void)
297299 np->parent = p;
298300 release(&wait_lock);
299301
300302 acquire(&np->lock);
303 // The child inherits the parent's tickets. Only p itself writes
304 // p->tickets, so reading it here without p->lock is safe.
305 np->tickets = p->tickets;
301306 np->state = RUNNABLE;
302307 release(&np->lock);
303308
304309 return pid;
@@ -449,9 +454,11 @@ scheduler(void)
449454 // to release its lock and then reacquire it
450455 // before jumping back to us.
451456 p->state = RUNNING;
452457 c->proc = p;
458 p->runstart = r_time();
453459 swtch(&c->context, &p->context);
460 p->cputime += r_time() - p->runstart;
454461
455462 // Don't re-enable interrupts on release.
456463 mycpu()->intena = 0;
457464
kernel/proc.h
@@ -87,8 +87,11 @@ struct proc {
8787 void *chan; // If non-zero, sleeping on chan
8888 int killed; // If non-zero, have been killed
8989 int xstate; // Exit status to be returned to parent's wait
9090 int pid; // Process ID
91 int tickets; // CPU share; after creation, written only by the process itself
92 uint64 cputime; // time run so far, in time CSR units (scheduler)
93 uint64 runstart; // time CSR when the scheduler last switched to it
9194
9295 // wait_lock must be held when using this:
9396 struct proc *parent; // Parent process
9497
kernel/syscall.c
@@ -102,8 +102,10 @@ extern uint64 sys_unlink(void);
102102extern uint64 sys_link(void);
103103extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106extern uint64 sys_settickets(void);
107extern uint64 sys_cputime(void);
106108
107109// An array mapping syscall numbers from syscall.h
108110// to the function that handles the system call.
109111static uint64 (*syscalls[])(void) = {
@@ -129,8 +131,10 @@ static uint64 (*syscalls[])(void) = {
129131 [SYS_link] = sys_link,
130132 [SYS_mkdir] = sys_mkdir,
131133 [SYS_close] = sys_close,
132134 [SYS_sync] = sys_sync,
135 [SYS_settickets] = sys_settickets,
136 [SYS_cputime] = sys_cputime,
133137 // clang-format on
134138};
135139
136140void
kernel/syscall.h
@@ -20,4 +20,6 @@
2020#define SYS_link 19
2121#define SYS_mkdir 20
2222#define SYS_close 21
2323#define SYS_sync 22
24#define SYS_settickets 23
25#define SYS_cputime 24
kernel/sysproc.c
@@ -109,4 +109,36 @@ sys_uptime(void)
109109 xticks = ticks;
110110 release(&tickslock);
111111 return xticks;
112112}
113
114// Set this process's share of the CPU to n tickets (1..MAXTICKETS).
115// Return the old number of tickets, or -1 if n is out of range.
116uint64
117sys_settickets(void)
118{
119 int n, old;
120 struct proc *p = myproc();
121
122 argint(0, &n);
123 if (n < 1 || n > MAXTICKETS)
124 return -1;
125 acquire(&p->lock);
126 old = p->tickets;
127 p->tickets = n;
128 release(&p->lock);
129 return old;
130}
131
132// Return the CPU time this process has used, in time CSR units
133// (10,000,000 per second on QEMU), including the current slice.
134uint64
135sys_cputime(void)
136{
137 uint64 t;
138 struct proc *p = myproc();
139
140 acquire(&p->lock);
141 t = p->cputime + (r_time() - p->runstart);
142 release(&p->lock);
143 return t;
144}
user/user.h
@@ -24,8 +24,10 @@ int getpid(void);
2424char *sys_sbrk(int, int);
2525int pause(int);
2626int uptime(void);
2727int sync(void);
28int settickets(int);
29uint64 cputime(void);
2830
2931// ulib.c
3032int stat(const char *, struct stat *);
3133char *strcpy(char *, const char *);
user/usys.pl
@@ -42,4 +42,6 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("settickets");
47entry("cputime");
4b3f0b4 Add stridetest and nice
Makefile
@@ -149,8 +149,10 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_stridetest\
154 $U/_nice\
153155
154156fs.img: mkfs/mkfs README $(UPROGS)
155157 mkfs/mkfs fs.img README $(UPROGS)
156158
user/nice.c
@@ -0,0 +1,22 @@
1// nice: run a command with a given number of tickets.
2// nice tickets command [args...]
3// (Unlike Unix nice, the number is a ticket count: more is faster.)
4
5#include "kernel/types.h"
6#include "user/user.h"
7
8int
9main(int argc, char *argv[])
10{
11 if (argc < 3) {
12 fprintf(2, "usage: nice tickets command [args...]\n");
13 exit(1);
14 }
15 if (settickets(atoi(argv[1])) < 0) {
16 fprintf(2, "nice: bad ticket count %s\n", argv[1]);
17 exit(1);
18 }
19 exec(argv[2], argv + 2);
20 fprintf(2, "nice: exec %s failed\n", argv[2]);
21 exit(1);
22}
user/stridetest.c
@@ -0,0 +1,272 @@
1// stridetest: is the CPU shared in proportion to tickets?
2//
3// stridetest run the checks
4// stridetest t1 t2 ... measure only: one spinning process per
5// ticket count; prints shares, checks nothing
6//
7// A spinning process asks the kernel for its CPU time (cputime) when
8// it first sees the clock (uptime) inside the measurement window and
9// again when the window has ended. Its share of the CPU time of all
10// spinners is its share of the CPU; the checks use that.
11//
12// It also counts "chunks" of a busy loop finished inside the window.
13// They are printed for information only: on QEMU a chunk takes more
14// or less time depending on how fast the host runs each hart.
15
16#include "kernel/types.h"
17#include "user/user.h"
18
19#define CHUNK 50000 // loop iterations between two looks at the clock
20#define MAXSPIN 8
21
22struct result {
23 int i; // which spinner
24 int chunks; // chunks finished inside the window
25 uint64 cpu; // CPU time used inside the window (time CSR units)
26};
27
28int wstart, wend; // the measurement window, in ticks
29
30// Spin until tick `wend`. Measure the CPU time used and count the
31// chunks finished inside [wstart, wend). Send the result to fd and
32// exit.
33void
34spin(int i, int fd)
35{
36 struct result r = {i, 0, 0};
37 volatile int x = 0;
38 uint64 t0 = 0;
39 int now, inside = 0;
40
41 for (;;) {
42 for (int k = 0; k < CHUNK; k++)
43 x++;
44 now = uptime();
45 if (now >= wend)
46 break;
47 if (now >= wstart) {
48 if (!inside) {
49 inside = 1;
50 t0 = cputime();
51 }
52 r.chunks++;
53 }
54 }
55 if (inside)
56 r.cpu = cputime() - t0;
57 write(fd, &r, sizeof(r));
58 exit(0);
59}
60
61int
62xfork(void)
63{
64 int pid = fork();
65 if (pid < 0) {
66 printf("stridetest: fork failed\n");
67 exit(1);
68 }
69 return pid;
70}
71
72// Run n spinners with the given tickets. The window starts `warm`
73// ticks from now and lasts `len` ticks. Spinner `sleeper` (or -1)
74// sleeps until the window starts; spinner `newcomer` (or -1) is not
75// forked until then. Fill in res[].
76//
77// Both really sleep, in read() on a pipe. (pause() would not do:
78// it wakes up at every tick to look at the clock.) An alarm process
79// writes to the pipe when the window starts.
80void
81measure(int n, int *tickets, int warm, int len, int sleeper, int newcomer,
82 struct result *res)
83{
84 int out[2], go[2];
85 struct result r;
86 char c;
87
88 if (pipe(out) < 0 || pipe(go) < 0) {
89 printf("stridetest: pipe failed\n");
90 exit(1);
91 }
92 wstart = uptime() + warm;
93 wend = wstart + len;
94 for (int i = 0; i < n; i++) {
95 if (i == newcomer)
96 continue;
97 if (xfork() == 0) {
98 settickets(tickets[i]);
99 if (i == sleeper)
100 read(go[0], &c, 1);
101 spin(i, out[1]);
102 }
103 }
104 if (sleeper >= 0 || newcomer >= 0) {
105 if (xfork() == 0) {
106 pause(wstart - uptime());
107 write(go[1], "g", 1);
108 exit(0);
109 }
110 }
111 if (newcomer >= 0) {
112 read(go[0], &c, 1);
113 if (xfork() == 0) {
114 settickets(tickets[newcomer]);
115 spin(newcomer, out[1]);
116 }
117 }
118 close(out[1]);
119 for (int i = 0; i < n; i++) {
120 if (read(out[0], &r, sizeof(r)) != sizeof(r)) {
121 printf("stridetest: short read\n");
122 exit(1);
123 }
124 res[r.i] = r;
125 }
126 close(out[0]);
127 close(go[0]);
128 close(go[1]);
129 while (wait(0) > 0)
130 ;
131}
132
133// settickets checks its argument and returns the old value;
134// fork and exec keep the tickets.
135int
136ticketstest(void)
137{
138 int ok = 1, old, st;
139 char *argv[] = {"stridetest", "-t", 0};
140
141 if (settickets(0) != -1 || settickets(-3) != -1 || settickets(101) != -1) {
142 printf("stridetest: tickets: a bad count was accepted\n");
143 ok = 0;
144 }
145 old = settickets(7);
146 if (settickets(7) != 7) {
147 printf("stridetest: tickets: settickets did not return the old count\n");
148 ok = 0;
149 }
150 if (fork() == 0)
151 exit(settickets(1));
152 wait(&st);
153 if (st != 7) {
154 printf("stridetest: tickets: fork child had %d tickets, not 7\n", st);
155 ok = 0;
156 }
157 if (fork() == 0) {
158 exec("/stridetest", argv);
159 exit(-1);
160 }
161 wait(&st);
162 if (st != 7) {
163 printf("stridetest: tickets: after exec %d tickets, not 7\n", st);
164 ok = 0;
165 }
166 settickets(old);
167 printf("stridetest: tickets: %s\n", ok ? "OK" : "FAIL");
168 return ok;
169}
170
171// Per mille of `part` in `total`.
172int
173permille(uint64 part, uint64 total)
174{
175 return total ? part * 1000 / total : 0;
176}
177
178// Six processes with 1, 1, 2, 2, 3 and 3 tickets. However many harts
179// (up to 4), each process wants more CPU than its share, so the
180// shares should be 1/6, 2/6 and 3/6 for the three ticket counts.
181int
182sharetest(void)
183{
184 int tickets[6] = {1, 1, 2, 2, 3, 3};
185 struct result res[6];
186 uint64 cpu = 0, chunks = 0;
187 int ok = 1;
188
189 measure(6, tickets, 5, 50, -1, -1, res);
190 for (int i = 0; i < 6; i++) {
191 cpu += res[i].cpu;
192 chunks += res[i].chunks;
193 }
194 printf("stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks\n");
195 for (int t = 1; t <= 3; t++) {
196 struct result *a = &res[2 * t - 2], *b = &res[2 * t - 1];
197 int share = permille(a->cpu + b->cpu, cpu);
198 int ideal = (t * 1000 + 3) / 6; // rounded
199 printf("stridetest: share: tickets %d: cpu %d per mille (ideal %d); "
200 "chunks %d per mille\n",
201 t, share, ideal, permille(a->chunks + b->chunks, chunks));
202 // within 20% of the ideal share
203 if (5 * (share - ideal) > ideal || 5 * (ideal - share) > ideal)
204 ok = 0;
205 }
206 printf("stridetest: share: %s\n", ok ? "OK" : "FAIL");
207 return ok;
208}
209
210// Six processes with equal tickets; process 0 either sleeps through
211// the first 30 ticks (sleeper) or is only created after them
212// (newcomer). In the next 30 ticks it should get about as much CPU
213// as each of the others, not a burst to make up for lost time.
214int
215latetest(char *what, int sleeper, int newcomer)
216{
217 int tickets[6] = {5, 5, 5, 5, 5, 5};
218 struct result res[6];
219 uint64 others = 0;
220 int ratio, ok;
221
222 measure(6, tickets, 30, 30, sleeper, newcomer, res);
223 for (int i = 1; i < 6; i++)
224 others += res[i].cpu;
225 ratio = others ? res[0].cpu * 5 * 100 / others : 0;
226 ok = ratio >= 67 && ratio <= 150;
227 printf("stridetest: %s: cpu %d ms, the others %d ms on average "
228 "(ratio %d/100)\n",
229 what, (int)(res[0].cpu / 10000), (int)(others / 5 / 10000), ratio);
230 printf("stridetest: %s: %s\n", what, ok ? "OK" : "FAIL");
231 return ok;
232}
233
234int
235main(int argc, char *argv[])
236{
237 int tickets[MAXSPIN], n, sum = 0, ok = 1;
238 struct result res[MAXSPIN];
239 uint64 cpu = 0, chunks = 0;
240
241 if (argc == 2 && strcmp(argv[1], "-t") == 0)
242 exit(settickets(1)); // the exec part of ticketstest
243
244 if (argc > 1) {
245 n = argc - 1;
246 if (n > MAXSPIN)
247 n = MAXSPIN;
248 for (int i = 0; i < n; i++) {
249 tickets[i] = atoi(argv[i + 1]);
250 sum += tickets[i];
251 }
252 measure(n, tickets, 5, 50, -1, -1, res);
253 for (int i = 0; i < n; i++) {
254 cpu += res[i].cpu;
255 chunks += res[i].chunks;
256 }
257 for (int i = 0; i < n; i++)
258 printf("stridetest: %d tickets: cpu %d ms, %d per mille "
259 "(%d if shared by tickets); chunks %d per mille\n",
260 tickets[i], (int)(res[i].cpu / 10000), permille(res[i].cpu, cpu),
261 tickets[i] * 1000 / sum, permille(res[i].chunks, chunks));
262 printf("stridetest: measured only, nothing checked\n");
263 exit(0);
264 }
265
266 ok &= ticketstest();
267 ok &= sharetest();
268 ok &= latetest("sleeper", 0, -1);
269 ok &= latetest("newcomer", -1, 0);
270 printf("stridetest: %s\n", ok ? "ALL OK" : "SOME FAILED");
271 exit(0);
272}
848eab5 Run the runnable process with the smallest pass
kernel/param.h
@@ -13,4 +13,5 @@
1313#define MAXPATH 128 // maximum file path name
1414#define USERSTACK 1 // user stack pages
1515#define DEFTICKETS 10 // tickets of a process that never set any
1616#define MAXTICKETS 100 // most tickets settickets() allows
17#define STRIDE1 (1 << 20) // a process's stride is STRIDE1 / tickets
kernel/proc.c
@@ -302,8 +302,9 @@ kfork(void)
302302 acquire(&np->lock);
303303 // The child inherits the parent's tickets. Only p itself writes
304304 // p->tickets, so reading it here without p->lock is safe.
305305 np->tickets = p->tickets;
306 np->pass = p->pass;
306307 np->state = RUNNABLE;
307308 release(&np->lock);
308309
309310 return pid;
@@ -425,16 +426,18 @@ kwait(uint64 addr)
425426
426427// Per-CPU process scheduler.
427428// Each CPU calls scheduler() after setting itself up.
428429// Scheduler never returns. It loops, doing:
429// - choose a process to run.
430// - choose a process to run: the RUNNABLE one with the
431// smallest pass (stride scheduling).
430432// - swtch to start running that process.
431433// - eventually that process transfers control
432434// via swtch back to the scheduler.
433435void
434436scheduler(void)
435437{
436 struct proc *p;
438 struct proc *p, *best;
439 uint64 bestpass;
437440 struct cpu *c = mycpu();
438441
439442 c->proc = 0;
440443 for (;;) {
@@ -445,35 +448,51 @@ scheduler(void)
445448 // and wfi.
446449 intr_on();
447450 intr_off();
448451
449 int found = 0;
452 // Find the RUNNABLE process with the smallest pass. Look at
453 // one process at a time, under its own lock, so that this
454 // scan never holds two p->locks.
455 best = 0;
456 bestpass = 0;
450457 for (p = proc; p < &proc[NPROC]; p++) {
451458 acquire(&p->lock);
452 if (p->state == RUNNABLE) {
453 // Switch to chosen process. It is the process's job
454 // to release its lock and then reacquire it
455 // before jumping back to us.
456 p->state = RUNNING;
457 c->proc = p;
458 p->runstart = r_time();
459 swtch(&c->context, &p->context);
460 p->cputime += r_time() - p->runstart;
461
462 // Don't re-enable interrupts on release.
463 mycpu()->intena = 0;
464
465 // Process is done running for now.
466 // It should have changed its p->state before coming back.
467 c->proc = 0;
468 found = 1;
459 if (p->state == RUNNABLE && (best == 0 || p->pass < bestpass)) {
460 best = p;
461 bestpass = p->pass;
469462 }
470463 release(&p->lock);
471464 }
472 if (found == 0) {
465 if (best == 0) {
473466 // nothing to run; stop running on this core until an interrupt.
474467 asm volatile("wfi");
468 continue;
469 }
470
471 // Another CPU may have taken best since we looked at it,
472 // so check again. If it is gone, scan again.
473 acquire(&best->lock);
474 if (best->state == RUNNABLE) {
475 // Charge it one stride for the time slice it is about to get.
476 best->pass += STRIDE1 / best->tickets;
477
478 // Switch to chosen process. It is the process's job
479 // to release its lock and then reacquire it
480 // before jumping back to us.
481 best->state = RUNNING;
482 c->proc = best;
483 best->runstart = r_time();
484 swtch(&c->context, &best->context);
485 best->cputime += r_time() - best->runstart;
486
487 // Don't re-enable interrupts on release.
488 mycpu()->intena = 0;
489
490 // Process is done running for now.
491 // It should have changed its p->state before coming back.
492 c->proc = 0;
475493 }
494 release(&best->lock);
476495 }
477496}
478497
479498// Switch to scheduler. Must hold only p->lock
kernel/proc.h
@@ -90,8 +90,9 @@ struct proc {
9090 int pid; // Process ID
9191 int tickets; // CPU share; after creation, written only by the process itself
9292 uint64 cputime; // time run so far, in time CSR units (scheduler)
9393 uint64 runstart; // time CSR when the scheduler last switched to it
94 uint64 pass; // stride scheduling: CPU used, in virtual time
9495
9596 // wait_lock must be held when using this:
9697 struct proc *parent; // Parent process
9798
09b524b Start new and woken processes at virtual time
kernel/proc.c
@@ -25,8 +25,29 @@ extern char trampoline[]; // trampoline.S
2525// memory model when using p->parent.
2626// must be acquired before any p->lock.
2727struct spinlock wait_lock;
2828
29// Stride scheduling's virtual time: the largest pass with which
30// any process has been picked to run. A process that was not
31// competing for the CPU (new, or asleep) starts again from here.
32// Taken after p->lock, and nothing is taken while holding it.
33struct {
34 struct spinlock lock;
35 uint64 now;
36} vtime;
37
38// p is becoming RUNNABLE after not competing for the CPU. Don't
39// let it start behind virtual time, or it would run without a
40// break until it had caught up. Caller must hold p->lock.
41static void
42catchup(struct proc *p)
43{
44 acquire(&vtime.lock);
45 if (p->pass < vtime.now)
46 p->pass = vtime.now;
47 release(&vtime.lock);
48}
49
2950// Allocate a page for each process's kernel stack.
3051// Map it high in memory, followed by an invalid
3152// guard page.
3253void
@@ -50,8 +71,9 @@ procinit(void)
5071 struct proc *p;
5172
5273 initlock(&pid_lock, "nextpid");
5374 initlock(&wait_lock, "wait_lock");
75 initlock(&vtime.lock, "vtime");
5476 for (p = proc; p < &proc[NPROC]; p++) {
5577 initlock(&p->lock, "proc");
5678 p->state = UNUSED;
5779 p->kstack = KSTACK((int)(p - proc));
@@ -125,8 +147,9 @@ found:
125147 p->pid = allocpid();
126148 p->state = USED;
127149 p->tickets = DEFTICKETS;
128150 p->cputime = 0;
151 p->pass = 0;
129152
130153 // Allocate a trapframe page.
131154 if ((p->trapframe = (struct trapframe *)kalloc()) == 0) {
132155 freeproc(p);
@@ -302,9 +325,9 @@ kfork(void)
302325 acquire(&np->lock);
303326 // The child inherits the parent's tickets. Only p itself writes
304327 // p->tickets, so reading it here without p->lock is safe.
305328 np->tickets = p->tickets;
306 np->pass = p->pass;
329 catchup(np);
307330 np->state = RUNNABLE;
308331 release(&np->lock);
309332
310333 return pid;
@@ -471,9 +494,14 @@ scheduler(void)
471494 // Another CPU may have taken best since we looked at it,
472495 // so check again. If it is gone, scan again.
473496 acquire(&best->lock);
474497 if (best->state == RUNNABLE) {
475 // Charge it one stride for the time slice it is about to get.
498 // Advance virtual time to best's pass, then charge best
499 // one stride for the time slice it is about to get.
500 acquire(&vtime.lock);
501 if (best->pass > vtime.now)
502 vtime.now = best->pass;
503 release(&vtime.lock);
476504 best->pass += STRIDE1 / best->tickets;
477505
478506 // Switch to chosen process. It is the process's job
479507 // to release its lock and then reacquire it
@@ -612,8 +640,9 @@ wakeup(void *chan)
612640
613641 // If this waiting process has gotten so far as to actually
614642 // go to sleep, also set it back to RUNNING.
615643 if (p->state == SLEEPING) {
644 catchup(p);
616645 p->state = RUNNABLE;
617646 }
618647 }
619648 release(&p->lock);
@@ -636,8 +665,9 @@ kkill(int pid)
636665 if (p->pid == pid) {
637666 p->killed = 1;
638667 if (p->state == SLEEPING) {
639668 // Wake process from sleep().
669 catchup(p);
640670 p->state = RUNNABLE;
641671 }
642672 release(&p->lock);
643673 return 0;
33b8c1d Show tickets, pass and virtual time on Ctrl-P
kernel/proc.c
@@ -753,7 +753,9 @@ procdump(void)
753753 state = states[p->state];
754754 else
755755 state = "???";
756756 printk("%d %s %s", p->pid, state, p->name);
757 printk(" tickets %d pass %lu", p->tickets, p->pass);
757758 printk("\n");
758759 }
760 printk("vtime %lu\n", vtime.now);
759761}

6. Verify and measure

On the branch (ext/08-stride, 5 commits), built with the project toolchain and run on 3 harts (-smp 3 -m 128M):

$ stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 166 per mille (ideal 167); chunks 155 per mille
stridetest: share: tickets 2: cpu 327 per mille (ideal 333); chunks 328 per mille
stridetest: share: tickets 3: cpu 506 per mille (ideal 500); chunks 516 per mille
stridetest: share: OK
stridetest: sleeper: cpu 1601 ms, the others 1481 ms on average (ratio 108/100)
stridetest: sleeper: OK
stridetest: newcomer: cpu 1599 ms, the others 1480 ms on average (ratio 108/100)
stridetest: newcomer: OK
stridetest: ALL OK
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED
$ stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 166 per mille (ideal 167); chunks 171 per mille
stridetest: share: tickets 2: cpu 326 per mille (ideal 333); chunks 325 per mille
stridetest: share: tickets 3: cpu 506 per mille (ideal 500); chunks 503 per mille
stridetest: share: OK
stridetest: sleeper: cpu 1602 ms, the others 1481 ms on average (ratio 108/100)
stridetest: sleeper: OK
stridetest: newcomer: cpu 1600 ms, the others 1479 ms on average (ratio 108/100)
stridetest: newcomer: OK
stridetest: ALL OK

And on one hart (-smp 1):

$ stridetest
stridetest: tickets: OK
stridetest: share: 6 processes with 1 1 2 2 3 3 tickets, 50 ticks
stridetest: share: tickets 1: cpu 159 per mille (ideal 167); chunks 161 per mille
stridetest: share: tickets 2: cpu 320 per mille (ideal 333); chunks 315 per mille
stridetest: share: tickets 3: cpu 519 per mille (ideal 500); chunks 523 per mille
stridetest: share: OK
stridetest: sleeper: cpu 600 ms, the others 480 ms on average (ratio 124/100)
stridetest: sleeper: OK
stridetest: newcomer: cpu 599 ms, the others 480 ms on average (ratio 124/100)
stridetest: newcomer: OK
stridetest: ALL OK

usertests -q passing shows that the new scheduler runs everything the old one did, including the tests that fork many processes, kill sleepers and exhaust the process table. stridetest before and after it shows the scheduler still divides the CPU by tickets after thousands of processes have come and gone. Every commit was built, and usertests -q printed ALL TESTS PASSED on 3 harts at commits 2, 3, 4 and 5 (commit 1’s kernel is byte-identical to commit 2’s).

The margin. The share check uses the kernel’s CPU-time counter, so what else the computer is doing barely matters. In 24 runs of stridetest at the head, measured while the computer was heavily busy with other work, all 24 printed ALL OK; the 1-ticket pair’s share was 163 to 166 per mille (the check allows 134 to 200), the 2-ticket pair’s 325 to 329 and the 3-ticket pair’s 506 to 507. The chunk shares of the 1-ticket pair in the same runs ranged from 153 to 173.

Shares, round robin against stride (per mille of the CPU time of all spinners in the 50-tick window, per ticket count, from the kernel’s counter; ideal 167 / 333 / 500). Round robin is commit 2 of the branch: tickets exist, the scheduler ignores them.

kernel	harts	1 ticket	2 tickets	3 tickets
round robin	3	333, 346	339, 326	326, 326
round robin	1	339	319	340
stride	3	159-166	326-333	506
stride, 24 runs on a busy computer	3	163-166	325-329	506-507
stride	2	159	330	509
stride	1	159	320	519

(Stride on 3 harts: six quiet runs on commits 3, 4 and 5, which schedule CPU-bound processes identically.) CPU time is handed out in whole slices of about 100 ms, so a 50-tick window cannot split exactly 1:2:3: on one hart, the six processes of stridetest 1 1 2 2 3 3 used 400, 400, 800, 800, 1,301 and 1,301 ms, that is 8, 16 and 26 slices per pair where 8.3, 16.7 and 25 would be exact.

Three processes with 1, 2 and 3 tickets (stridetest 1 2 3, CPU time in the window):

kernel	harts	1 ticket	2 tickets	3 tickets
round robin	1	1,701 ms (339)	1,602 ms (320)	1,702 ms (340)
stride	1	801 ms (160)	1,601 ms (319)	2,604 ms (520)
stride	2	1,601 ms (160)	3,402 ms (340)	5,003 ms (499)
stride	3	5,001 ms (333)	5,003 ms (333)	5,005 ms (333)

On 3 harts there is nothing to share: each process has a hart (question 8). On 2 harts the 3-ticket process deserves exactly one hart, the most it can use, and gets all of it.

Late processes (CPU time of the sleeper or newcomer divided by the others’ average, 3 harts):

kernel	sleeper	newcomer
round robin (commit 2)	1.08, 0.99	0.92, 1.00
stride, pass kept or copied (commit 3)	2.37, 2.38	2.37, 2.37
stride with virtual time (commits 4, 5), quiet	1.08 (4 runs)	1.08 (4 runs)
the same, 24 runs on a busy computer	0.99-1.09	1.07-1.13
woken pass kept (clinic 2)	2.37, 2.37	1.08, 1.07
new pass 0 (clinic 1)	0	0

The reference’s 1.08 is a small advantage of about one slice: a woken or new process starts exactly at virtual time, level with the front of the queue, and ties go to the earlier slot. On one hart, where the window holds only about five slices per process, the same one slice makes 1.24.

Why count CPU time and not work. Counting chunks of a busy loop is what a user program would naturally do. In the 24 busy runs above, the chunk share of the 1-ticket pair ranged from 153 to 173 per mille while its CPU share stayed at 163 to 166, and in 83 runs of a version of the test that checked chunk shares, they went as low as 132. The scheduler was exact; the chunks were not. Two things make chunks stray. Each QEMU hart is a host thread whose speed depends on what else the computer runs; on a busy computer, stridetest 1 2 3 once gave chunk shares of 277, 357 and 365 per mille although each process had a hart to itself. And the twelve picks of a stride round fall on the three harts in a repeating pattern, so the 1-ticket processes run on only some harts: in one recorded trace both ran on hart 0 for 20 of 21 picks, in another only on harts 1 and 2. Their chunk count then measures the speed of fewer harts than the other pairs’ does. The time CSR is the same 10 MHz clock on every hart, so CPU time measured with it does not care which hart ran the process.

How fast virtual time can grow. With a scratch program on a copy of the branch, two 1-ticket processes passing a byte back and forth through pipes made 20,299 and 20,961 round trips in 100 ticks; virtual time rose from 4,299,137 to 21,349,741,335 and then to 43,379,484,233, about 2.1 to 2.2 billion per second, one stride per round trip (question 7).

The schedule, recorded. A gdb breakpoint at the charging line printed every pick without stopping the machine for long (reveal, “Re-check under the lock”): one STRIDE1 of virtual time, 9,317,318 to 10,365,894, contained twelve picks on three harts, one per ticket.

7. Go further

Charge for time used. The kernel already measures each slice for cputime. Add stride × used / slice instead of a whole stride, and measure an interactive process (one that sleeps after a millisecond) against CPU-bound neighbours before and after. Look at the pause case of question 4 again.
Infeasible weights. On three harts, stridetest 1 2 3 cannot give 3/6 to one process. Cap each process’s effective tickets at what one hart can deliver, and keep the passes of processes that run alone from drifting (Ctrl-P showed 43.0 million against 17.5 million). Compare with how Linux’s CFS handles a task whose weight exceeds a CPU.
Per-hart run queues. The scan of all 64 slots under 64 locks, on every pick, on every hart, is the cost of one shared table. Give each hart its own queue of RUNNABLE processes sorted by pass, and work out what moving a process between queues needs (lab 18 did the same for free pages).
A 32-bit pass that survives the wrap. Keep uint, compare with (int)(a - b) < 0, and find out what must hold for every two passes ever compared to stay within 2^31 of each other: question 7 shows that drifting passes on three harts break it within minutes, so the infeasible-weight fix above is a prerequisite. Then run clinic 5’s experiment against it.
Lottery scheduling. Replace the minimum with a random draw weighted by tickets and compare the variance of the shares over short windows with stride’s.