Thread Scheduling, and What Linux Actually Does

Nice does not set a fixed share. On the fair share scheduler it weights a share: a difference of one nice level changes a process's share of the processor by about ten per cent, so a difference of ten levels is about a factor of ten.

Read off the machine

$ chrt -p $$
pid 8's current scheduling policy: SCHED_OTHER
pid 8's current scheduling priority: 0
$ nice
0
$ chrt -m | head -6
SCHED_OTHER min/max priority	: 0/0
SCHED_FIFO min/max priority	: 1/99
SCHED_RR min/max priority	: 1/99
SCHED_BATCH min/max priority	: 0/0
SCHED_IDLE min/max priority	: 0/0
SCHED_DEADLINE min/max priority	: 0/0
$ nice -n 10 chrt -p $$ | tail -1
pid 8's current scheduling priority: 0
$ nice -n 10 nice
10

Read it against the tables above.

• The shell runs SCHED_OTHER with priority 0, which is the only priority that policy has:

an ordinary process has no real time priority at all, and its treatment comes from its nice value instead.

• The two real time policies have priorities 1 to 99. Those are genuine fixed priorities and they

sit above every ordinary process.

• SCHED_DEADLINE appears, a policy where a thread states how much processor it needs and by

when. It is outside MU's syllabus and worth knowing exists.

• nice -n 10 ran a command with a nice value of 10, and the value is inherited by what it

starts.

The kernel publishes what it counts for each thread, which is the fair share scheduler's own bookkeeping.

$ grep -E '^(nr_switches|policy|prio)' /proc/self/sched
nr_switches                                  :                    6
policy                                       :                    0
prio                                         :                  120
$ awk '/se.sum_exec_runtime/ {print "processor milliseconds used:", $3}' /proc/self/sched
processor milliseconds used: 2.947250

prio is 120, which is 120 minus the nice value of 0 in the kernel's own internal numbering where 100 is the best ordinary priority and 139 the worst. The two numbering systems, nice from -20 to 19 and the internal 100 to 139, describe the same thing: nice plus 120 is the internal number.

What the fair share scheduler does, in one section

MU's syllabus stops at the seven algorithms, and a question may ask what a real system uses. The answer, from the kernel's own documentation, is none of them exactly.

Instead of a queue in an order, the scheduler keeps for each thread the amount of processor time it has already had, weighted by its nice value, and always runs the thread that has had the least. There is no quantum in the round robin sense: a thread runs until somebody else's weighted time falls below its own.

That is shortest remaining time first turned inside out. Chapter forty eight could not implement shortest job first because it needed the future. This needs only the past, which is known exactly, and it gets much of the same effect: a thread that has used little processor time, which is what an interactive thread looks like, is always chosen first.

The name to know is that this family of schedulers is described in authorities/kernel/scheduler-sched-design-CFS.txt and its successor in authorities/kernel/scheduler-sched-eevdf.txt, both fetched from the kernel's own documentation. Neither is examinable on this paper; what is examinable is being able to say that a modern system uses a fair share scheduler based on processor time already consumed, rather than any of the seven textbook algorithms.

Distinctions that carry marks

What it does not mean

Thread scheduling is not a different set of algorithms. It is the same algorithms applied to threads, plus the question of who applies them.

A nice value of -20 does not make a process real time. It weights its share among the ordinary processes. Real time means one of the two real time policies.

SCHED_FIFO is not first come first served for the machine. It is first come first served within one priority level, and the levels are absolute.

Quick revision

• Contention scope: process contention scope means a thread competes only with its own

process's threads, scheduled by the library; system contention scope means it competes with every thread, scheduled by the kernel.

• On a one to one system, which Linux is, every thread has system contention scope and

the library schedules nothing.

• Linux policies: SCHED_OTHER for ordinary work, SCHED_FIFO and SCHED_RR for real time with

absolute priorities 1 to 99, SCHED_BATCH, SCHED_IDLE.

• A higher nice value means a lower priority, from -20 to 19, which is the opposite of

Chapter fifty's convention. One nice level is about ten per cent of a process's share.

• chrt -p shows a process's policy and priority; chrt -m shows the ranges; nice shows the

value.

• An ordinary process has no real time priority: SCHED_OTHER's only priority is 0.
• A real system uses a fair share scheduler that runs whichever thread has had the least

weighted processor time so far, which achieves much of what shortest job first wanted using only the past.

Test yourself

1. What is contention scope? Whether a thread competes for the processor only with the other

threads of its own process, which is process contention scope, or with every thread on the machine, which is system contention scope.

1. Which does Linux use, and what follows? System contention scope for every thread, because

it maps one user thread to one kernel thread. The thread library therefore does no scheduling at all.

1. Name the Linux scheduling policies and which are real time. SCHED_OTHER, SCHED_BATCH

and SCHED_IDLE are ordinary; SCHED_FIFO and SCHED_RR are real time, with priorities 1 to 99 above every ordinary process.

1. What is the difference between SCHED_FIFO and SCHED_RR? Within one priority level,

SCHED_FIFO runs a thread until it blocks or yields, and SCHED_RR gives each thread a quantum in turn.

1. What is a nice value and which direction does it run? A weighting on an ordinary process's

share of the processor, from -20 to 19, in which a higher number means a lower priority.

1. Why must a real time policy require privilege? A real time thread has absolute priority

over every ordinary process, so one that loops for ever stops the machine doing anything else.

1. What does a modern general purpose scheduler actually do? It keeps for each thread the

processor time it has already used, weighted by its nice value, and runs whichever has used the least. That needs only the past, and it gets much of the benefit shortest job first wanted from the future.