Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Scheduling

You can access the slides 🖼️ for this lecture.

Here we discuss scheduling, and we zoom in on the current scheduler used by Linux, the Completely Fair Scheduler (CFS).

What is OS Scheduling?

The OS scheduler in the kernel is the entity that decides what tasks should run on the CPU cores, when, and for how long. Recall that with Linux the schedulable entities are threads: we will use that term interchangeably with tasks here. Most modern operating systems support running multiple tasks at the same time; this is called multitasking. When the number of tasks is greater than the number of CPU cores, which is almost always the case in modern systems, several tasks are multiplexed in time on the same CPU core. Context switching between two tasks on a core happens very quickly, giving the user the illusion that tasks are executing in parallel.

Scheduling has several key objectives:

  • Throughput: we want to run as many tasks as possible, and to minimise the overhead of running scheduling code such as context switches.
  • Latency or responsiveness: when a task becomes ready to run, for example following an event such as the user pressing a button, we want it to be scheduled on the CPU as early as possible.
  • Fairness: if we have several tasks with the same priority in the system, each should get an equal share of CPU time.
  • Scalability: we want our scheduler to support a large number of 1) tasks and 2) cores.

Main Scheduler Classes

As you may know, there are two main classes of schedulers:

  • The first one is cooperative scheduling. With a cooperative scheduler, a task won’t stop running until it decides to yield the CPU with a system call, or terminates. In that situation, the OS simply cannot enforce fairness. We could for example have a malicious task never yielding and monopolising all CPU cycles: that’s a denial of service and availability is compromised.
  • The second class of schedulers is preemptive multitasking. With it, the kernel can interrupt the execution of a task; this is called preemption. Preemption can happen in various situations, for example when a task expires the amount of CPU time it was allocated by the scheduler, or when a task with a higher priority becomes ready to run. This is obviously more suitable from the security point of view with adversarial workloads.

Traditional Scheduling Algorithms

You may have already learnt in the past about some of the traditional scheduling algorithms:

  • First-Come, First-Served (FCFS) or First-In, First-Out (FIFO): tasks simply run in the order they become ready until they yield or finish.
  • Round-Robin: tasks run for a fixed amount of time, named a quantum, in a round-robin manner.
  • Priority Scheduling: the scheduler considers priorities to rank tasks and select the one that needs to run the most.
  • Multilevel Feedback Queues: tasks are divided into different priority queues, and certain types of tasks are favoured.

All of these algorithms have their pros and cons, and are great for learning about scheduling. However, none of these approaches is really efficient with modern workloads on modern machines.

We need a better scheduler for modern systems, for 2 main reasons. First, the last two decades have seen a growing number of cores integrated in CPUs. For example, it is very likely that you are reading these lectures on a computer with multiple cores. This is a scalability issue: scheduling algorithms designed to work on a single core are generally not directly compatible with CPUs having multiple cores, and other algorithms working on a handful of cores may not work that well when that number increases.

Second, the characteristics of the workloads running on modern machines have become increasingly heterogeneous. Computers run batch or background tasks that are CPU- and memory-bound, and run for a long time. Examples of such tasks are encoding videos, training ML models, etc. These jobs want to run as much as possible to keep caches warm, but they are also OK with being preempted. Conversely, we also have interactive tasks, such as text editors or video games. These are latency-sensitive: they do not need a lot of CPU cycles but need to respond quickly to certain events such as mouse clicks or pressing a key on the keyboard. Finally, in some scenarios we also have real-time tasks. These need to be schedulable in bounded time, so we can get particular guarantees. For example, soft real-time workloads such as video decoding or processing generally have quality of service requirements, e.g., keeping the frame rate above a particular threshold. Hard real-time workloads must offer safety guarantees, for example if a car’s motion sensors detect an object on the road, the brakes must be activated swiftly. All of these impose particular requirements on the scheduler.

Batch vs. Interactive Tasks

Here we have an illustration of two tasks running on a system:

One task is a video encoder, a background throughput-oriented job. The other is an interactive latency-sensitive application, a text editor. If we have a scheduler ensuring complete fairness, we would get something like what can be seen at the top, with the same amount of CPU time given to each task. That would be suboptimal, because in reality these two tasks have different needs. Indeed, the text editor only needs to run for a few CPU cycles when the user presses a key on the keyboard. The video encoder needs to run as much as possible, but is OK to be preempted by the text editor whenever needed. As a result, a scheduler realising the behaviour seen at the bottom of the illustration would be much more efficient: the goal of modern schedulers is to maintain good performance for both types of jobs, including in situations when they run alongside each other.

Linux’s Scheduler: CFS

Linux’s first scheduler dates back to the 1990s and scaled poorly to high numbers of tasks and cores. It was replaced in 2003 by the O(1) scheduler, which had the ability to take constant-time scheduling decisions, independently of the number of tasks and cores in the system. It scaled well, but had some issues with latency-sensitive interactive tasks.

The current scheduler on Linux is the Completely Fair Scheduler, CFS. It was introduced in Linux 2.6.23 in 2007.

CFS: Core Idea

To understand how CFS works, first assume a CPU with only a single core for the sake of simplicity. CFS defines a fixed time interval during which each thread in the system must run at least once. This interval is split into timeslices, 1 per thread. The length of the timeslice for each thread is proportional to the thread’s weight, which is basically its priority, also named the nice value in Linux.

The scheduler keeps track of how much time each thread spends on the CPU. That time, divided by the thread’s weight, gives what is called the vruntime for that thread.

CFS decides to preempt a thread running on the CPU when that thread exceeds its timeslice and there are other threads ready to run. A running thread is also preempted when another thread with a smaller vruntime wakes up.

CFS Runqueues

To achieve these scheduling decisions, CFS organises all threads that are ready to run into a runqueue, which is a red-black tree:

Each node in the tree is a thread ready to run. They are sorted in the tree by increasing order of vruntime. This way, it is easy for CFS to pick the next task to run: it always corresponds to the leftmost node. Using a red-black tree also allows CFS to have low performance overheads. Indeed, things like inserting and removing nodes, rebalancing and recoloring the tree, are realised with O(log n) complexity.

On a multicore CPU, CFS has 1 runqueue (1 red-black tree) per core in the system. This way, the vast majority of scheduling decisions can be made locally in a per-core manner. They do not necessitate inter-core communication, which would require synchronisation with mechanisms such as locks, and would slow things down too much.

Still, the per-core runqueues must be kept balanced: we don’t want to end up in situations with 1 core having many high-priority threads and the other cores with just a few low-priority threads in their runqueues. To address that problem, CFS implements a relatively complex load balancing algorithm, that moves threads between the runqueues of different cores to balance things. This algorithm considers the threads’ priorities, the number of threads in each runqueue, but also the system’s topology, including the cache hierarchy, hyperthreading, and NUMA nodes. Indeed, there is a cost in migrating a thread away: for example, it will have to rebuild its local cache state on the target core.

vruntime Explained

The vruntime value for each thread, which is used to rank them in the runqueue, is weighted by their nice value. A thread’s nice value is basically an inverted priority metric: the higher the nice value, the nicer the thread is, i.e. the more it is OK to let other threads run. The way the vruntime is computed for each thread ensures that long-running CPU-intensive threads will see their vruntime increase faster, giving more chances to run for I/O bound/interactive threads, that do not run much, when these become ready.

Preemption and Context Switches

With Linux, preemption works as follows. When the scheduler decides that the currently-running thread should be preempted, it sets a per-CPU flag to indicate that. Remember that this happens when the running thread exceeds its timeslice, or when a thread with a higher priority (with CFS, a lower vruntime) wakes up and becomes ready to run. The thread in question is not immediately preempted. Instead, the flag is checked by the kernel before returning to user space, for example following a system call, exception, or hardware interrupt. If the flag is set, preemption happens and a context switch is performed. The kernel switches the CPU context to that of the target thread. We have seen previously how a context switch is done: the content of the CPU registers is dumped to memory to save the execution context of the task being scheduled out, and the CPU registers’ content is set with the execution context of the task being scheduled in. That includes a control register that indicates which page table should be used; in effect, this switches the address space to that of the target thread.

Security Aspects

There are some security aspects to scheduling. An attacker taking control of a user-space application can issue scheduling-related system calls and manipulate some scheduling parameters. They could set a higher priority or a prioritised scheduling policy on malicious threads, in order to compromise the availability of other applications.

The solution to that issue is to prevent untrusted users from accessing scheduling parameters. We will see later approaches for filtering the system calls that can be issued by an application that is not trusted. There are also additional CPU isolation mechanisms, in particular a subsystem called control groups on Linux, which is used by containers. Control groups allow setting CPU quotas for threads, which are independent of the scheduling policy used. We will talk about control groups in more detail when we cover virtualisation.