CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 3 min read

Virtual runtime

In plain words: Stride scheduling has the key insight that Linux uses: keep a counter per process that grows as the process runs, and always run the process with the smallest counter. Linux calls the counter virtual runtime (vruntime). It grows by the real time the process ran, scaled by its weight: a heavy process's counter grows slowly, so it is picked often, and a light process's counter grows fast, so it is picked less often.

The weight comes from the process's nice value, the number from -20 to 19 that Level 1 introduced and that a user can set with nice and renice (a higher number is "nicer": it asks for less). A table in the kernel gives each nice value a weight, and one step in nice changes the weight by about 25 per cent. Some entries:

nice -20 -10 -5 0 5 10 15 19
weight 88761 9548 3121 1024 335 110 36 15

The weight of nice 0 is 1,024. The update rule is

vruntime grows by (real run time) × 1,024 ÷ weight

A worked example, made up to show the idea. X has nice 0 (weight 1,024) and Y has nice 5 (weight 335). If X runs for 10 ms, its vruntime grows by 10. If Y runs for 10 ms, its vruntime grows by 10 × 1,024 ÷ 335, about 30.6. Y's counter climbs three times as fast, so the scheduler picks Y only one time in about three. The shares come out as 1,024 ÷ 1,359 = 75.3 per cent for X and 24.7 per cent for Y.

A test checks this on the real machine. Two spinning programs are pinned to one processor, with nice values 0 and 10 (and also 0 and 5). Each runs for 5 seconds, and the CPU time of each is measured:

nice 0 and nice 0 : 2.47 s and 2.48 s   shares 50.0 % / 50.0 %
nice 0 and nice 5 : 3.76 s and 1.23 s   shares 75.3 % / 24.7 %
nice 0 and nice 10: 4.47 s and 0.48 s   shares 90.2 % /  9.8 %

The expected shares from the weights are 50.0 / 50.0, 75.3 / 24.7 (1,024 ÷ 1,359) and 90.3 / 9.7 (1,024 ÷ 1,134). The measured shares agree within 0.1 percentage points.

The kernel also shows the counters. For the nice 0 and nice 5 pair, /proc/<pid>/sched after 4 seconds printed:

nice 0:  se.vruntime 2952.8   se.sum_exec_runtime 2949.2   se.load.weight 1048576
nice 5:  se.vruntime 2964.1   se.sum_exec_runtime  969.9   se.load.weight  343040

The two virtual runtimes are almost equal, 2952.8 and 2964.1 ms, while the real run times differ by a factor of 3 (2949 against 970 ms). That is the fairness goal in numbers: the scheduler equalises the virtual time, and the real time then divides according to the weights. The printed weights are scaled by 1,024, so 1048576 ÷ 1024 = 1,024 and 343040 ÷ 1024 = 335.

Virtual runtime

The virtual runtime of a task is a counter that grows with the time the task has run, divided by its weight (scaled so that nice 0 counts at real speed), and the scheduler prefers the task whose counter is smallest, so that tasks of any weight receive time in proportion to their weights.

Example: a task with nice 5 runs 10 ms and its virtual runtime grows by about 30.6, while a nice 0 task running 10 ms grows by 10.

Check yourself: 1. What happens to vruntime growth when the weight doubles? 2. Compute the share of a nice 10 task competing with a nice 0 task. 3. Why were the two vruntime values nearly equal in the test?