Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

0

500

1000

1500

2000

2500

3000

3500

0 100 200 300 400 500 600 700 800 900 1000

Virtual time interval (milliseconds)

Real time interval (milliseconds)

Nice 0 (prio 120)

Nice +5 (prio 125)

Nice −5 (prio 115)

1

10

100

1000

10000

100000

1 10 100 1000

Nice 0 (prio 120)

Nice +10 (prio 130)

Nice +19 (prio 139)

Nice −10 (prio 110)

Nice −20 (prio 100)

Figure 2-18: Relation between real and virtual time for processes depending on their

priority/nice level.

Finally, the kernel needs to setmin_vruntime. Care is taken to ensure that the value is increasing mono-
tonically.

kernel/sched_fair.c

/*

* maintain cfs_rq->min_vruntime to be a monotonically increasing

* value tracking the leftmost vruntime in the tree.

*/

if (first_fair(cfs_rq)) {

vruntime = min_vruntime(curr->vruntime,

__pick_next_entity(cfs_rq)->vruntime);

} else

vruntime = curr->vruntime;

cfs_rq->min_vruntime =

max_vruntime(cfs_rq->min_vruntime, vruntime);

}

first_fairis a helper function that checks if the tree has a leftmost element, that is, if any process is
waiting on the tree to be scheduled. If so, the kernel obtains itsvruntime, which is the smallest of all
elements in the tree. If no leftmost element is in the tree because it is empty, the virtual run time of the
current process is used instead. To ensure that the per-queuemin_vruntimeis monotonic increasing, the
kernel sets it to the larger of both values. This means that the per-queuemin_vruntimeis only updated if
it is exceeded by thevruntimeof one of the elements on the tree. With this policy, the kernel ensures that
min_vrtimecan only increase, but never decrease.