CPU Scheduling

A machine has a fixed number of CPUs and usually many more tasks that want to run. The scheduler is the part of the kernel that decides, for each CPU and at each moment, which task runs. A task is the unit it schedules: a process with a single thread, or one thread of a process with several (chapter 3).

In this chapter, we will learn how the Completely Fair Scheduler, the default of Linux 5.15, makes that decision. We will first see how the scheduler gets control of a CPU at all, and follow a switch from one task to the next. Then we will measure how it divides a CPU between busy processes of different priorities with schedfacts, and write cfs, a model of its central rule that produces the measured shares.

When the scheduler runs

A task that is running holds its CPU, and the kernel is not executing. The scheduler can act only when control passes to the kernel. That happens in 3 ways.

The timer interrupt is what makes it impossible for a task to keep a CPU for ever. A program in an endless loop makes no system calls, and it is still interrupted, 250 times per second on our machine. Taking the CPU from a task that did not offer it is called preemption.

The kernel counts both kinds of switch for every task. This is a shell loop that had been running for a second on a busy machine:

$ grep ctxt /proc/577022/status
voluntary_ctxt_switches:	0
nonvoluntary_ctxt_switches:	37

The loop did not sleep once, and was preempted 37 times. A program that waits for input shows the opposite pattern.

From one task to the next

1. Task A is running on a CPU. The timer interrupt arrives, and the processor enters the kernel on A’s behalf.
2. The kernel charges A for the time it has run since it was last charged.
3. It checks whether A has had its share for now. If so, it sets a flag on A that asks for a reschedule.
4. On the way back to user mode, the kernel sees the flag and calls the scheduler.
5. The scheduler picks the next task, B, from the run queue: the set of tasks that are ready to run on this CPU.
6. The kernel performs a context switch. It saves the registers of A in A’s task_struct, loads the registers of B, and switches to B’s address space. A’s state remains complete, so it will continue later as if nothing had happened.
7. The return to user mode now resumes B. A waits in the run queue.

Steps 2, 3 and 5 are the scheduling policy: how much each task is charged, when it has had enough, and who is next. The rest of the chapter is about those 3 decisions.

Classes and policies

Linux has several schedulers side by side, called scheduling classes. Each task belongs to one, selected by its policy. When a CPU needs a task, the kernel asks the classes in a fixed order and takes the first task offered.

$ chrt -p 577022
pid 577022's current scheduling policy: SCHED_OTHER
pid 577022's current scheduling priority: 0

SCHED_OTHER is the policy of every task that has not asked for something else, and it belongs to the fair class. The real-time policies are for tasks that must run within a bounded time of becoming runnable, such as audio processing, and they require privilege, because a real-time task in an endless loop keeps its CPU from every ordinary task. The rest of this chapter concerns the fair class.

The requirement

The goal of the fair class is stated in terms of an ideal: if n tasks of equal priority are runnable on a CPU, each should receive 1/n of it, and a task of higher priority should receive a proportionally larger part. A real CPU runs a single task at a time, so the scheduler approximates the ideal by switching between tasks and keeping account of what each has received.

The priority of a task in the fair class is its nice value, an integer from -20 to 19. A higher value means a lower priority: the task is “nicer” to the others. The nice command and the setpriority system call set it, and only a privileged process may set a negative value. The kernel converts the nice value to a weight with a fixed table, in which nice 0 has weight 1024 and each step changes the weight by about 25%. The share of a task is its weight divided by the sum of the weights of all runnable tasks on the CPU.

A share is relative. A task of nice 19 that is alone on a CPU receives all of it. The nice value has an effect only when tasks compete.

Measuring shares

schedfacts starts 2 busy processes, restricts both to CPU 0 with taskset, and sets their nice values with nice. Restricting them to the same CPU makes them compete: on an idle machine with 8 CPUs each would otherwise get a CPU of its own. After 2 seconds the program reads the CPU time of each from /proc/<pid>/stat. It needs only the standard libraries.

$ cargo new schedfacts

spin starts a busy shell loop, and cpuTime reads the time a process has spent on a CPU. The kernel reports it in clock ticks of 10 ms, in separate fields for the time spent in user mode and in kernel mode.

Listing 6.1 The imports of schedfacts, in Go. code/go/schedfacts/main.go

import (
	"fmt"
	"log"
	"os"
	"os/exec"
	"strconv"
	"strings"
	"time"
)

Listing 6.2 The imports of schedfacts, in Rust. code/rust/schedfacts/src/main.rs

use std::fs;
use std::io;
use std::process::{Child, Command};
use std::thread;
use std::time::Duration;

Listing 6.3 Starting a busy process on CPU 0, and reading its CPU time, in Go. code/go/schedfacts/main.go

// spin starts a busy shell loop, restricted to CPU 0 and with
// the given nice value.
func spin(nice int) (*exec.Cmd, error) {
	child := exec.Command("taskset", "-c", "0", "nice", "-n", strconv.Itoa(nice), "sh", "-c", "while :; do :; done")

	return child, child.Start()
}

// cpuTime returns the CPU time a process has used, in clock ticks: fields 14
// and 15 of /proc/<pid>/stat, the time in user mode and in kernel mode.
func cpuTime(pid int) (int, error) {
	stat, err := os.ReadFile(fmt.Sprintf("/proc/%d/stat", pid))

	if err != nil {
		return 0, err
	}

	fields := strings.Fields(string(stat[strings.LastIndexByte(string(stat), ')')+1:]))

	if len(fields) < 13 {
		return 0, fmt.Errorf("/proc/%d/stat: too few fields", pid)
	}

	var user, kernel int

	if _, err := fmt.Sscan(fields[11], &user); err != nil {
		return 0, err
	}

	if _, err := fmt.Sscan(fields[12], &kernel); err != nil {
		return 0, err
	}

	return user + kernel, nil
}

Listing 6.4 Starting a busy process on CPU 0, and reading its CPU time, in Rust. code/rust/schedfacts/src/main.rs

/// Starts a busy shell loop, restricted to CPU 0 and with the
/// given nice value.
fn spin(nice: i32) -> io::Result<Child> {
    Command::new("taskset")
        .args(["-c", "0", "nice", "-n", &nice.to_string()])
        .args(["sh", "-c", "while :; do :; done"])
        .spawn()
}

/// Returns the CPU time a process has used, in clock ticks: fields 14 and 15
/// of `/proc/<pid>/stat`, the time in user mode and in kernel mode.
fn cpu_time(pid: u32) -> io::Result<u64> {
    let stat = fs::read_to_string(format!("/proc/{pid}/stat"))?;
    let rest = stat.rsplit_once(')').map_or("", |(_, rest)| rest);

    let ticks: Vec<u64> = rest
        .split_whitespace()
        .skip(11)
        .take(2)
        .filter_map(|field| field.parse().ok())
        .collect();

    match ticks.as_slice() {
        [user, kernel] => Ok(user + kernel),
        _ => Err(io::ErrorKind::InvalidData.into()),
    }
}

share lets a process of nice 0 compete with a process of a given nice value, and prints the percentage each received. The percentages are rounded to the nearest 5, since a measurement over 2 seconds varies by a few ticks between runs.

Listing 6.5 Measuring the division of a CPU, in Go. code/go/schedfacts/main.go

// stop ends a busy process and collects it.
func stop(child *exec.Cmd) {
	child.Process.Kill()
	child.Wait()
}

// share lets a process of nice 0 and a process of the given nice value
// compete for CPU 0 for 2 seconds and prints the share of CPU time each
// received, rounded to the nearest 5%.
func share(nice int) error {
	first, err := spin(0)

	if err != nil {
		return err
	}

	defer stop(first)

	second, err := spin(nice)

	if err != nil {
		return err
	}

	defer stop(second)

	time.Sleep(2 * time.Second)

	a, err := cpuTime(first.Process.Pid)

	if err != nil {
		return err
	}

	b, err := cpuTime(second.Process.Pid)

	if err != nil {
		return err
	}

	percent := (200*a/(a+b) + 5) / 10 * 5
	fmt.Printf("nice 0 and nice %d on 1 CPU: %d%% and %d%%\n", nice, percent, 100-percent)

	return nil
}

Listing 6.6 Measuring the division of a CPU, in Rust. code/rust/schedfacts/src/main.rs

/// Ends a busy process and collects it.
fn stop(mut child: Child) -> io::Result<()> {
    child.kill()?;
    child.wait()?;

    Ok(())
}

/// Lets a process of nice 0 and a process of the given nice value compete for
/// CPU 0 for 2 seconds and prints the share of CPU time each received,
/// rounded to the nearest 5%.
fn share(nice: i32) -> io::Result<()> {
    let first = spin(0)?;
    let second = spin(nice)?;

    thread::sleep(Duration::from_secs(2));

    let times = cpu_time(first.id()).and_then(|a| Ok((a, cpu_time(second.id())?)));

    stop(first)?;
    stop(second)?;

    let (a, b) = times?;
    let percent = (200 * a / (a + b) + 5) / 10 * 5;

    println!(
        "nice 0 and nice {nice} on 1 CPU: {percent}% and {}%",
        100 - percent
    );

    Ok(())
}

nice 0 and nice 0 on 1 CPU: 50% and 50%
nice 0 and nice 5 on 1 CPU: 75% and 25%
nice 0 and nice 10 on 1 CPU: 90% and 10%

The shares predicted from the table are 1024/2048 = 50%, 1024/1359 = 75.3% and 1024/1134 = 90.3%. The measurement agrees with all of them.

Virtual runtime

The scheduler needs a rule that produces these shares without computing them. It keeps a number for each task, the virtual runtime or vruntime, and follows 2 rules.

1. When a task has run for a time t, its vruntime increases by t × 1024 / weight.
2. The task with the smallest vruntime runs next.

For a task of weight 1024, vruntime is the real time it has run. A task of weight 335 is charged about 3.06 ms for each millisecond, and a task of weight 3121 is charged about 0.33 ms.

To see why this produces the shares, take a task A of weight 1024 and a task C of weight 335. Rule 2 always runs the one that is behind, so their vruntimes stay close together. Suppose both have advanced by 300 ms of vruntime. A was charged at the real rate, so it ran for 300 ms. C was charged 3.06 ms per millisecond, so it ran for 98 ms. The ratio 300 to 98 is the ratio of the weights, 1024 to 335. Equal progress in virtual time means weighted progress in real time.

The kernel’s structures

The scheduling data of a task is a struct sched_entity, embedded in its task_struct as the field se. Each CPU has a struct cfs_rq, the run queue of the fair class. These are the definitions in Linux 5.15, from include/linux/sched.h and kernel/sched/sched.h, reduced to the fields we use.

struct load_weight {
        unsigned long weight;                  /* 1024 for nice 0 */
        u32 inv_weight;                        /* precomputed 2^32 / weight */
};

struct sched_entity {
        struct load_weight load;
        struct rb_node run_node;               /* its node in the run queue's tree */
        unsigned int on_rq;                    /* 1 while it is in the run queue */
        u64 exec_start;                        /* when it was last put on a CPU */
        u64 sum_exec_runtime;                  /* real CPU time received, in ns */
        u64 vruntime;                          /* virtual runtime, in ns */
        /* ... */
};

struct cfs_rq {
        struct load_weight load;               /* sum of the weights in the queue */
        unsigned int nr_running;               /* number of runnable entities */
        u64 min_vruntime;                      /* a floor that only increases */
        struct rb_root_cached tasks_timeline;  /* the tree, ordered by vruntime */
        struct sched_entity *curr;             /* the entity on the CPU */
        /* ... */
};

Rule 2 needs a data structure that returns its smallest element and accepts insertions, both quickly. A red-black tree does each in time proportional to the logarithm of the number of tasks, and the kernel keeps a pointer to the leftmost node, so finding the next task takes constant time.

The length of a slice

How long a task runs before the scheduler chooses again is also derived from the weights. The scheduler aims to run every runnable task once within a period called the scheduling latency, and gives each task the part of the period that corresponds to its weight. With more tasks the parts become shorter, down to a minimum, so that the cost of switching does not dominate. The defaults in Linux 5.15 are a latency of 6 ms and a minimum of 0.75 ms, both multiplied by a factor that grows with the number of CPUs: 4 on a machine with 8 or more CPUs, giving 24 ms and 3 ms here.

An example with the 3 tasks of this chapter makes the rule concrete. A and B have weight 1024 and C has weight 335, a total of 2383. In a period of 24 ms, A receives 24 × 1024 / 2383 = 10.3 ms, B the same, and C receives 24 × 335 / 2383 = 3.4 ms.

Modelling the scheduler

The weights are the kernel’s table sched_prio_to_weight. The model uses a fixed slice of 1 ms, which is enough to reproduce the shares.

Listing 6.7 The imports of cfs, in Go. code/go/cfs/main.go

import (
	"container/heap"
	"fmt"
	"strings"
)

Listing 6.8 The imports of cfs, in Rust. code/rust/cfs/src/main.rs

use std::collections::BTreeSet;

Listing 6.9 Weights and tasks, in Go. code/go/cfs/main.go

// weights is the kernel's table sched_prio_to_weight: the weight of each nice
// value from -20 to 19. Each step of nice changes the weight by about 25%.
var weights = [40]int64{
	88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916,
	9548, 7620, 6100, 4904, 3906, 3121, 2501, 1991, 1586, 1277,
	1024, 820, 655, 526, 423, 335, 272, 215, 172, 137,
	110, 87, 70, 56, 45, 36, 29, 23, 18, 15,
}

// slice is the time a task runs before the scheduler chooses again, in
// nanoseconds.
const slice = 1_000_000

// A task is one schedulable entity. vruntime is its virtual runtime in
// nanoseconds, and slices counts how often it has run.
type task struct {
	name     string
	weight   int64
	vruntime int64
	slices   int
}

func newTask(name string, nice int) *task {
	return &task{name: name, weight: weights[nice+20]}
}

Listing 6.10 Weights and tasks, in Rust. code/rust/cfs/src/main.rs

/// The kernel's table `sched_prio_to_weight`: the weight of each nice value
/// from -20 to 19. Each step of nice changes the weight by about 25%.
const WEIGHTS: [u64; 40] = [
    88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916, 9548, 7620, 6100, 4904,
    3906, 3121, 2501, 1991, 1586, 1277, 1024, 820, 655, 526, 423, 335, 272, 215, 172, 137, 110, 87,
    70, 56, 45, 36, 29, 23, 18, 15,
];

/// The time a task runs before the scheduler chooses again, in nanoseconds.
const SLICE: u64 = 1_000_000;

/// One schedulable entity. `vruntime` is its virtual runtime in nanoseconds,
/// and `slices` counts how often it has run.
struct Task {
    name: &'static str,
    weight: u64,
    vruntime: u64,
    slices: u64,
}

impl Task {
    fn new(name: &'static str, nice: i32) -> Task {
        Task {
            name,
            weight: WEIGHTS[(nice + 20) as usize],
            vruntime: 0,
            slices: 0,
        }
    }
}

The run queue orders tasks by vruntime. The Go version is a binary heap from container/heap, and the Rust version is a BTreeSet of keys. Both give the operations rule 2 needs.

Listing 6.11 The run queue, in Go. code/go/cfs/main.go

// A queue holds the runnable tasks ordered by virtual runtime, with the name
// as a tie-break. It implements heap.Interface. The kernel keeps the same
// order in a red-black tree and takes the leftmost node.
type queue []*task

func (q queue) Len() int      { return len(q) }
func (q queue) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *queue) Push(t any)   { *q = append(*q, t.(*task)) }

func (q queue) Less(i, j int) bool {
	if q[i].vruntime != q[j].vruntime {
		return q[i].vruntime < q[j].vruntime
	}

	return q[i].name < q[j].name
}

func (q *queue) Pop() any {
	old := *q
	last := old[len(old)-1]
	*q = old[:len(old)-1]

	return last
}

Listing 6.12 The run queue, in Rust. code/rust/cfs/src/main.rs

/// The runnable tasks, ordered by virtual runtime with the name as a
/// tie-break. `runnable` holds the order and `tasks` holds the tasks, indexed
/// by the number in the key. The kernel keeps the same order in a red-black
/// tree and takes the leftmost node.
#[derive(Default)]
struct Scheduler {
    tasks: Vec<Task>,
    runnable: BTreeSet<(u64, &'static str, usize)>,
    min_vruntime: u64,
}

impl Scheduler {
    fn enqueue(&mut self, id: usize) {
        let task = &self.tasks[id];

        self.runnable.insert((task.vruntime, task.name, id));
    }
}

tick applies both rules. minVruntime follows the vruntime of the task at the front of the queue.

Listing 6.13 Running the task with the smallest vruntime, in Go. code/go/cfs/main.go

// A scheduler is a run queue and the smallest virtual runtime it has seen,
// which only increases.
type scheduler struct {
	runnable    queue
	minVruntime int64
}

// tick runs the task with the smallest virtual runtime for one slice and
// returns it. The task is charged slice * 1024 / weight, so a task of weight
// 1024 is charged real time and a heavier task is charged less.
func (s *scheduler) tick() *task {
	t := heap.Pop(&s.runnable).(*task)

	t.vruntime += slice * 1024 / t.weight
	t.slices++

	heap.Push(&s.runnable, t)
	s.minVruntime = max(s.minVruntime, s.runnable[0].vruntime)

	return t
}

// wake makes a task runnable. With place set, a task that slept is moved
// forward to the queue's minimum, so that it cannot claim the time it did
// not use while it slept.
func (s *scheduler) wake(t *task, place bool) {
	if place {
		t.vruntime = max(t.vruntime, s.minVruntime)
	}

	heap.Push(&s.runnable, t)
}

Listing 6.14 Running the task with the smallest vruntime, in Rust. code/rust/cfs/src/main.rs

impl Scheduler {
    /// Runs the task with the smallest virtual runtime for one slice and
    /// returns its number. The task is charged `SLICE * 1024 / weight`, so a
    /// task of weight 1024 is charged real time and a heavier task is charged
    /// less.
    fn tick(&mut self) -> Option<usize> {
        let (_, _, id) = self.runnable.pop_first()?;
        let task = &mut self.tasks[id];

        task.vruntime += SLICE * 1024 / task.weight;
        task.slices += 1;

        self.enqueue(id);

        if let Some(&(leftmost, _, _)) = self.runnable.first() {
            self.min_vruntime = self.min_vruntime.max(leftmost);
        }

        Some(id)
    }

    /// Makes a task runnable and returns its number. With `place` set, a task
    /// that slept is moved forward to the queue's minimum, so that it cannot
    /// claim the time it did not use while it slept.
    fn wake(&mut self, mut task: Task, place: bool) -> usize {
        if place {
            task.vruntime = task.vruntime.max(self.min_vruntime);
        }

        self.tasks.push(task);
        self.enqueue(self.tasks.len() - 1);

        self.tasks.len() - 1
    }
}

share repeats the measurement on the model: a task of nice 0 against a task of another nice value, for 2000 slices.

Listing 6.15 The shares on the model, in Go. code/go/cfs/main.go

// share runs a task of nice 0 against a task of the given nice value for
// 2000 slices and prints each task's share, rounded to the nearest 5%.
func share(nice int) {
	s := &scheduler{}
	first, second := newTask("A", 0), newTask("B", nice)

	s.wake(first, true)
	s.wake(second, true)

	for range 2000 {
		s.tick()
	}

	percent := (200*first.slices/(first.slices+second.slices) + 5) / 10 * 5
	fmt.Printf("nice 0 and nice %d on 1 CPU: %d%% and %d%%\n", nice, percent, 100-percent)
}

Listing 6.16 The shares on the model, in Rust. code/rust/cfs/src/main.rs

/// Runs a task of nice 0 against a task of the given nice value for 2000
/// slices and prints each task's share, rounded to the nearest 5%.
fn share(nice: i32) {
    let mut scheduler = Scheduler::default();

    let first = scheduler.wake(Task::new("A", 0), true);
    let second = scheduler.wake(Task::new("B", nice), true);

    for _ in 0..2000 {
        scheduler.tick();
    }

    let (a, b) = (
        scheduler.tasks[first].slices,
        scheduler.tasks[second].slices,
    );
    let percent = (200 * a / (a + b) + 5) / 10 * 5;

    println!(
        "nice 0 and nice {nice} on 1 CPU: {percent}% and {}%",
        100 - percent
    );
}

order prints which task runs in each of the first 12 slices when A and B have nice 0 and C has nice 5.

Listing 6.17 The order of the first slices, in Go. code/go/cfs/main.go

// order prints which task runs in each of the first 12 slices.
func order() {
	s := &scheduler{}

	for _, t := range []*task{newTask("A", 0), newTask("B", 0), newTask("C", 5)} {
		s.wake(t, true)
	}

	var names []string

	for range 12 {
		names = append(names, s.tick().name)
	}

	fmt.Printf("A and B at nice 0, C at nice 5: %s\n", strings.Join(names, " "))
}

Listing 6.18 The order of the first slices, in Rust. code/rust/cfs/src/main.rs

/// Prints which task runs in each of the first 12 slices.
fn order() {
    let mut scheduler = Scheduler::default();

    for task in [Task::new("A", 0), Task::new("B", 0), Task::new("C", 5)] {
        scheduler.wake(task, true);
    }

    let mut names = Vec::new();

    for _ in 0..12 {
        if let Some(id) = scheduler.tick() {
            names.push(scheduler.tasks[id].name);
        }
    }

    println!("A and B at nice 0, C at nice 5: {}", names.join(" "));
}

A task that wakes up

A task that sleeps is removed from the run queue, and its vruntime stops increasing. After a long sleep its vruntime is far below that of the tasks that kept running. Under rule 2 alone it would then run without interruption until it had caught up, and every other task would stop for that time. A task that had slept for an hour could claim the CPU for many minutes.

The scheduler prevents this when the task wakes: it raises the task’s vruntime to the min_vruntime of the queue. The task is treated as if it had kept pace while it slept. It competes on equal terms from the moment it wakes and receives no credit for the time it did not use.

Listing 6.19 Waking a task with and without placement, in Go. code/go/cfs/main.go

// sleeper lets A and B run for 200 slices, wakes C with a virtual runtime of
// 0, and counts how many of the next 30 slices C receives.
func sleeper(place bool) int {
	s := &scheduler{}

	s.wake(newTask("A", 0), true)
	s.wake(newTask("B", 0), true)

	for range 200 {
		s.tick()
	}

	c := newTask("C", 0)
	s.wake(c, place)

	for range 30 {
		s.tick()
	}

	return c.slices
}

Listing 6.20 Waking a task with and without placement, in Rust. code/rust/cfs/src/main.rs

/// Lets A and B run for 200 slices, wakes C with a virtual runtime of 0, and
/// counts how many of the next 30 slices C receives.
fn sleeper(place: bool) -> u64 {
    let mut scheduler = Scheduler::default();

    scheduler.wake(Task::new("A", 0), true);
    scheduler.wake(Task::new("B", 0), true);

    for _ in 0..200 {
        scheduler.tick();
    }

    let c = scheduler.wake(Task::new("C", 0), place);

    for _ in 0..30 {
        scheduler.tick();
    }

    scheduler.tasks[c].slices
}

nice 0 and nice 0 on 1 CPU: 50% and 50%
nice 0 and nice 5 on 1 CPU: 75% and 25%
nice 0 and nice 10 on 1 CPU: 90% and 10%
A and B at nice 0, C at nice 5: A B C A B A B A B C A B
C wakes with its old virtual runtime: it receives 30 of the next 30 slices
C wakes and is placed at the minimum: it receives 10 of the next 30 slices

Several CPUs

Everything so far concerned a single CPU. A machine with several CPUs has a run queue for each, with its own tree and its own lock, so that the CPUs can schedule without waiting for each other. A task is in the queue of exactly 1 CPU at a time.

Separate queues can become uneven, with tasks waiting on one CPU while another is idle. Load balancing corrects this: periodically, and whenever a CPU runs out of tasks, the kernel compares the queues and moves tasks from a loaded CPU to a lighter one. Moving has a cost, because the task’s data is in the caches of the CPU it leaves, so the balancer prefers to leave a task where it last ran.

A program can restrict the CPUs a task may use, its affinity, with sched_setaffinity or the taskset command. schedfacts used this to force its 2 processes onto the same CPU.

$ taskset -p 577022
pid 577022's current affinity mask: ff

The mask ff has 8 bits set: the task may run on any of the 8 CPUs.

Inspecting the scheduler on a live system

A high count of involuntary switches means the task wants more CPU than it gets. A high count of voluntary switches means it mostly waits.

The complete programs

Listing 6.21 The complete schedfacts, in Go. code/go/schedfacts/main.go

// Command schedfacts measures how the scheduler divides a CPU between busy
// processes of different nice values. It starts the processes on the same
// CPU, lets them compete, and reads the CPU time each one received.
//
// Run it from code/go with:
//
//	go run ./schedfacts
package main

import (
	"fmt"
	"log"
	"os"
	"os/exec"
	"strconv"
	"strings"
	"time"
)


// spin starts a busy shell loop, restricted to CPU 0 and with
// the given nice value.
func spin(nice int) (*exec.Cmd, error) {
	child := exec.Command("taskset", "-c", "0", "nice", "-n", strconv.Itoa(nice), "sh", "-c", "while :; do :; done")

	return child, child.Start()
}

// cpuTime returns the CPU time a process has used, in clock ticks: fields 14
// and 15 of /proc/<pid>/stat, the time in user mode and in kernel mode.
func cpuTime(pid int) (int, error) {
	stat, err := os.ReadFile(fmt.Sprintf("/proc/%d/stat", pid))

	if err != nil {
		return 0, err
	}

	fields := strings.Fields(string(stat[strings.LastIndexByte(string(stat), ')')+1:]))

	if len(fields) < 13 {
		return 0, fmt.Errorf("/proc/%d/stat: too few fields", pid)
	}

	var user, kernel int

	if _, err := fmt.Sscan(fields[11], &user); err != nil {
		return 0, err
	}

	if _, err := fmt.Sscan(fields[12], &kernel); err != nil {
		return 0, err
	}

	return user + kernel, nil
}


// stop ends a busy process and collects it.
func stop(child *exec.Cmd) {
	child.Process.Kill()
	child.Wait()
}

// share lets a process of nice 0 and a process of the given nice value
// compete for CPU 0 for 2 seconds and prints the share of CPU time each
// received, rounded to the nearest 5%.
func share(nice int) error {
	first, err := spin(0)

	if err != nil {
		return err
	}

	defer stop(first)

	second, err := spin(nice)

	if err != nil {
		return err
	}

	defer stop(second)

	time.Sleep(2 * time.Second)

	a, err := cpuTime(first.Process.Pid)

	if err != nil {
		return err
	}

	b, err := cpuTime(second.Process.Pid)

	if err != nil {
		return err
	}

	percent := (200*a/(a+b) + 5) / 10 * 5
	fmt.Printf("nice 0 and nice %d on 1 CPU: %d%% and %d%%\n", nice, percent, 100-percent)

	return nil
}


func main() {
	for _, nice := range []int{0, 5, 10} {
		if err := share(nice); err != nil {
			log.Fatal(err)
		}
	}
}

Listing 6.22 The complete schedfacts, in Rust. code/rust/schedfacts/src/main.rs

//! Measures how the scheduler divides a CPU between busy processes of
//! different nice values. It starts the processes on the same CPU, lets them
//! compete, and reads the CPU time each one received.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p schedfacts
//! ```

use std::fs;
use std::io;
use std::process::{Child, Command};
use std::thread;
use std::time::Duration;

/// Starts a busy shell loop, restricted to CPU 0 and with the
/// given nice value.
fn spin(nice: i32) -> io::Result<Child> {
    Command::new("taskset")
        .args(["-c", "0", "nice", "-n", &nice.to_string()])
        .args(["sh", "-c", "while :; do :; done"])
        .spawn()
}

/// Returns the CPU time a process has used, in clock ticks: fields 14 and 15
/// of `/proc/<pid>/stat`, the time in user mode and in kernel mode.
fn cpu_time(pid: u32) -> io::Result<u64> {
    let stat = fs::read_to_string(format!("/proc/{pid}/stat"))?;
    let rest = stat.rsplit_once(')').map_or("", |(_, rest)| rest);

    let ticks: Vec<u64> = rest
        .split_whitespace()
        .skip(11)
        .take(2)
        .filter_map(|field| field.parse().ok())
        .collect();

    match ticks.as_slice() {
        [user, kernel] => Ok(user + kernel),
        _ => Err(io::ErrorKind::InvalidData.into()),
    }
}

/// Ends a busy process and collects it.
fn stop(mut child: Child) -> io::Result<()> {
    child.kill()?;
    child.wait()?;

    Ok(())
}

/// Lets a process of nice 0 and a process of the given nice value compete for
/// CPU 0 for 2 seconds and prints the share of CPU time each received,
/// rounded to the nearest 5%.
fn share(nice: i32) -> io::Result<()> {
    let first = spin(0)?;
    let second = spin(nice)?;

    thread::sleep(Duration::from_secs(2));

    let times = cpu_time(first.id()).and_then(|a| Ok((a, cpu_time(second.id())?)));

    stop(first)?;
    stop(second)?;

    let (a, b) = times?;
    let percent = (200 * a / (a + b) + 5) / 10 * 5;

    println!(
        "nice 0 and nice {nice} on 1 CPU: {percent}% and {}%",
        100 - percent
    );

    Ok(())
}

fn main() -> io::Result<()> {
    for nice in [0, 5, 10] {
        share(nice)?;
    }

    Ok(())
}

Listing 6.23 The complete cfs, in Go. code/go/cfs/main.go

// Command cfs models the Completely Fair Scheduler: every runnable task has a
// virtual runtime, the scheduler always runs the task with the smallest one,
// and a task's virtual runtime advances more slowly the larger its weight.
//
// Run it from code/go with:
//
//	go run ./cfs
package main

import (
	"container/heap"
	"fmt"
	"strings"
)


// weights is the kernel's table sched_prio_to_weight: the weight of each nice
// value from -20 to 19. Each step of nice changes the weight by about 25%.
var weights = [40]int64{
	88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916,
	9548, 7620, 6100, 4904, 3906, 3121, 2501, 1991, 1586, 1277,
	1024, 820, 655, 526, 423, 335, 272, 215, 172, 137,
	110, 87, 70, 56, 45, 36, 29, 23, 18, 15,
}

// slice is the time a task runs before the scheduler chooses again, in
// nanoseconds.
const slice = 1_000_000

// A task is one schedulable entity. vruntime is its virtual runtime in
// nanoseconds, and slices counts how often it has run.
type task struct {
	name     string
	weight   int64
	vruntime int64
	slices   int
}

func newTask(name string, nice int) *task {
	return &task{name: name, weight: weights[nice+20]}
}


// A queue holds the runnable tasks ordered by virtual runtime, with the name
// as a tie-break. It implements heap.Interface. The kernel keeps the same
// order in a red-black tree and takes the leftmost node.
type queue []*task

func (q queue) Len() int      { return len(q) }
func (q queue) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *queue) Push(t any)   { *q = append(*q, t.(*task)) }

func (q queue) Less(i, j int) bool {
	if q[i].vruntime != q[j].vruntime {
		return q[i].vruntime < q[j].vruntime
	}

	return q[i].name < q[j].name
}

func (q *queue) Pop() any {
	old := *q
	last := old[len(old)-1]
	*q = old[:len(old)-1]

	return last
}


// A scheduler is a run queue and the smallest virtual runtime it has seen,
// which only increases.
type scheduler struct {
	runnable    queue
	minVruntime int64
}

// tick runs the task with the smallest virtual runtime for one slice and
// returns it. The task is charged slice * 1024 / weight, so a task of weight
// 1024 is charged real time and a heavier task is charged less.
func (s *scheduler) tick() *task {
	t := heap.Pop(&s.runnable).(*task)

	t.vruntime += slice * 1024 / t.weight
	t.slices++

	heap.Push(&s.runnable, t)
	s.minVruntime = max(s.minVruntime, s.runnable[0].vruntime)

	return t
}

// wake makes a task runnable. With place set, a task that slept is moved
// forward to the queue's minimum, so that it cannot claim the time it did
// not use while it slept.
func (s *scheduler) wake(t *task, place bool) {
	if place {
		t.vruntime = max(t.vruntime, s.minVruntime)
	}

	heap.Push(&s.runnable, t)
}


// share runs a task of nice 0 against a task of the given nice value for
// 2000 slices and prints each task's share, rounded to the nearest 5%.
func share(nice int) {
	s := &scheduler{}
	first, second := newTask("A", 0), newTask("B", nice)

	s.wake(first, true)
	s.wake(second, true)

	for range 2000 {
		s.tick()
	}

	percent := (200*first.slices/(first.slices+second.slices) + 5) / 10 * 5
	fmt.Printf("nice 0 and nice %d on 1 CPU: %d%% and %d%%\n", nice, percent, 100-percent)
}


// order prints which task runs in each of the first 12 slices.
func order() {
	s := &scheduler{}

	for _, t := range []*task{newTask("A", 0), newTask("B", 0), newTask("C", 5)} {
		s.wake(t, true)
	}

	var names []string

	for range 12 {
		names = append(names, s.tick().name)
	}

	fmt.Printf("A and B at nice 0, C at nice 5: %s\n", strings.Join(names, " "))
}


// sleeper lets A and B run for 200 slices, wakes C with a virtual runtime of
// 0, and counts how many of the next 30 slices C receives.
func sleeper(place bool) int {
	s := &scheduler{}

	s.wake(newTask("A", 0), true)
	s.wake(newTask("B", 0), true)

	for range 200 {
		s.tick()
	}

	c := newTask("C", 0)
	s.wake(c, place)

	for range 30 {
		s.tick()
	}

	return c.slices
}


func main() {
	for _, nice := range []int{0, 5, 10} {
		share(nice)
	}

	order()

	fmt.Printf("C wakes with its old virtual runtime: it receives %d of the next 30 slices\n", sleeper(false))
	fmt.Printf("C wakes and is placed at the minimum: it receives %d of the next 30 slices\n", sleeper(true))
}

Listing 6.24 The complete cfs, in Rust. code/rust/cfs/src/main.rs

//! Models the Completely Fair Scheduler: every runnable task has a virtual
//! runtime, the scheduler always runs the task with the smallest one, and a
//! task's virtual runtime advances more slowly the larger its weight.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p cfs
//! ```

use std::collections::BTreeSet;

/// The kernel's table `sched_prio_to_weight`: the weight of each nice value
/// from -20 to 19. Each step of nice changes the weight by about 25%.
const WEIGHTS: [u64; 40] = [
    88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916, 9548, 7620, 6100, 4904,
    3906, 3121, 2501, 1991, 1586, 1277, 1024, 820, 655, 526, 423, 335, 272, 215, 172, 137, 110, 87,
    70, 56, 45, 36, 29, 23, 18, 15,
];

/// The time a task runs before the scheduler chooses again, in nanoseconds.
const SLICE: u64 = 1_000_000;

/// One schedulable entity. `vruntime` is its virtual runtime in nanoseconds,
/// and `slices` counts how often it has run.
struct Task {
    name: &'static str,
    weight: u64,
    vruntime: u64,
    slices: u64,
}

impl Task {
    fn new(name: &'static str, nice: i32) -> Task {
        Task {
            name,
            weight: WEIGHTS[(nice + 20) as usize],
            vruntime: 0,
            slices: 0,
        }
    }
}

/// The runnable tasks, ordered by virtual runtime with the name as a
/// tie-break. `runnable` holds the order and `tasks` holds the tasks, indexed
/// by the number in the key. The kernel keeps the same order in a red-black
/// tree and takes the leftmost node.
#[derive(Default)]
struct Scheduler {
    tasks: Vec<Task>,
    runnable: BTreeSet<(u64, &'static str, usize)>,
    min_vruntime: u64,
}

impl Scheduler {
    fn enqueue(&mut self, id: usize) {
        let task = &self.tasks[id];

        self.runnable.insert((task.vruntime, task.name, id));
    }
}

impl Scheduler {
    /// Runs the task with the smallest virtual runtime for one slice and
    /// returns its number. The task is charged `SLICE * 1024 / weight`, so a
    /// task of weight 1024 is charged real time and a heavier task is charged
    /// less.
    fn tick(&mut self) -> Option<usize> {
        let (_, _, id) = self.runnable.pop_first()?;
        let task = &mut self.tasks[id];

        task.vruntime += SLICE * 1024 / task.weight;
        task.slices += 1;

        self.enqueue(id);

        if let Some(&(leftmost, _, _)) = self.runnable.first() {
            self.min_vruntime = self.min_vruntime.max(leftmost);
        }

        Some(id)
    }

    /// Makes a task runnable and returns its number. With `place` set, a task
    /// that slept is moved forward to the queue's minimum, so that it cannot
    /// claim the time it did not use while it slept.
    fn wake(&mut self, mut task: Task, place: bool) -> usize {
        if place {
            task.vruntime = task.vruntime.max(self.min_vruntime);
        }

        self.tasks.push(task);
        self.enqueue(self.tasks.len() - 1);

        self.tasks.len() - 1
    }
}

/// Runs a task of nice 0 against a task of the given nice value for 2000
/// slices and prints each task's share, rounded to the nearest 5%.
fn share(nice: i32) {
    let mut scheduler = Scheduler::default();

    let first = scheduler.wake(Task::new("A", 0), true);
    let second = scheduler.wake(Task::new("B", nice), true);

    for _ in 0..2000 {
        scheduler.tick();
    }

    let (a, b) = (
        scheduler.tasks[first].slices,
        scheduler.tasks[second].slices,
    );
    let percent = (200 * a / (a + b) + 5) / 10 * 5;

    println!(
        "nice 0 and nice {nice} on 1 CPU: {percent}% and {}%",
        100 - percent
    );
}

/// Prints which task runs in each of the first 12 slices.
fn order() {
    let mut scheduler = Scheduler::default();

    for task in [Task::new("A", 0), Task::new("B", 0), Task::new("C", 5)] {
        scheduler.wake(task, true);
    }

    let mut names = Vec::new();

    for _ in 0..12 {
        if let Some(id) = scheduler.tick() {
            names.push(scheduler.tasks[id].name);
        }
    }

    println!("A and B at nice 0, C at nice 5: {}", names.join(" "));
}

/// Lets A and B run for 200 slices, wakes C with a virtual runtime of 0, and
/// counts how many of the next 30 slices C receives.
fn sleeper(place: bool) -> u64 {
    let mut scheduler = Scheduler::default();

    scheduler.wake(Task::new("A", 0), true);
    scheduler.wake(Task::new("B", 0), true);

    for _ in 0..200 {
        scheduler.tick();
    }

    let c = scheduler.wake(Task::new("C", 0), place);

    for _ in 0..30 {
        scheduler.tick();
    }

    scheduler.tasks[c].slices
}

fn main() {
    for nice in [0, 5, 10] {
        share(nice);
    }

    order();

    println!(
        "C wakes with its old virtual runtime: it receives {} of the next 30 slices",
        sleeper(false)
    );
    println!(
        "C wakes and is placed at the minimum: it receives {} of the next 30 slices",
        sleeper(true)
    );
}

References

• sched(7), nice(2), sched_setaffinity(2) and chrt(1), Linux manual pages: https://man7.org/linux/man-pages/man7/sched.7.html
• CFS Scheduler, Linux kernel documentation: https://www.kernel.org/doc/html/v5.15/scheduler/sched-design-CFS.html
• kernel/sched/fair.c, kernel/sched/core.c and include/linux/sched.h, Linux 5.15: https://elixir.bootlin.com/linux/v5.15/source/kernel/sched/fair.c