The CPU Scheduler – Part 1

The previous two chapters delved pretty deep into aspects of Linux memory management, with a focus on how exactly you, as a kernel/driver developer, can efficiently dynamically allocate and deallocate kernel memory (besides the APIs, we covered interesting stuff like MGLRU, DAMON, and the OOM killer!).

In this chapter and the next, you will dive into the details regarding a key OS topic – that is, CPU (or task) scheduling on the Linux OS. I will try and keep the learning both conceptual and hands-on, by asking (and answering) typical questions and performing common tasks related to scheduling. Understanding how CPU scheduling works at the level of the OS is not only important from a kernel (and driver) developer viewpoint, it will also automatically make you a better system architect, even for user space applications.

We shall begin by covering essential background material; this will include the notion of the Kernel Schedulable Entity...

Technical requirements

I assume that you have gone through Online Chapter, Kernel Workspace Setup, and have appropriately prepared a guest Virtual Machine (VM) running Ubuntu 22.04 LTS (or a later stable release) and installed all the required packages. If not, I highly recommend you do this first.

To get the most out of this book, I strongly recommend you first set up the workspace environment, including cloning this book’s GitHub repository for the code and working on it in a hands-on fashion. The repository can be found here: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E.

Learning about the CPU scheduling internals – part 1 – essential background

Let’s take a quick look at the essential background information we require to understand CPU scheduling on Linux.

Note that, in this book, we do not intend to cover material that competent (user space) system programmers on Linux should already be well aware of; this includes basics such as process (or thread) states, basic information on what real time is, the POSIX scheduling policies, and so on. This (and more) has been covered in some detail in my earlier book, Hands-On System Programming with Linux, published by Packt in October 2018. Nevertheless, we do touch upon some of the basics here.

What is the KSE on Linux?

As you learned in Chapter 6, Kernel Internals Essentials – Processes and Threads, in the Organizing processes, threads, and their stacks – user and kernel space section, every (user mode) thread alive on the system is bestowed with...

Visualizing the flow

Multicore systems have led to processes – well, threads really (both user - and kernel-space ones) – executing concurrently on different processors. This is useful for gaining higher throughput and thus performance, but it also causes synchronization headaches when they work with shared writable data (we shall deal in depth with the really important topic of kernel synchronization in this book’s last two chapters).

So, for example, on a hardware platform with, say, six processor cores, we can expect processes (threads) to execute in parallel on them; this is nothing new. Is there a way, though, to actually see which processes or threads are executing on which CPU core – that is, a way to visualize a processor timeline? It turns out there are indeed a few ways to do so. In the following sections, we will look at a couple of interesting ways: with the gnome-system-monitor GUI program, perf, as well as other possibilities.

Using...

Learning about the CPU scheduling internals – part 2

This section delves into kernel CPU scheduling internals in some detail, the emphasis being on the core aspect of modern design, modular scheduling classes.

Understanding modular scheduling classes

Ingo Molnar, a key kernel developer (along with others), redesigned the internal structure of the kernel scheduler, introducing a new approach called scheduling classes (this was back in October 2007 with the release of the 2.6.23 kernel).

As a side note, the word class in scheduler classes isn’t a coincidence; many Linux kernel features are intrinsically, and quite naturally, designed with an object-oriented nature. The C language, of course, does not allow us to express this directly in code (hence the preponderance of structures with both data and function pointer members, emulating a class). Nevertheless, the design is very often object-oriented (as you shall quite clearly see with the driver model...

Querying a given thread’s scheduling policy and priority

In this section, you’ll learn how to query the scheduling policy and priority of any given thread on the system via the command line. (But what about programmatically querying and setting the same? We defer that discussion to Chapter 11, The CPU Scheduler – Part 2, in the Querying and setting a thread’s scheduling policy and priority section.)

We learned that, on Linux, the thread is the KSE; it’s what gets scheduled and runs on the processor. Also, Linux has several choices for the scheduling policy (or algorithm) to use. Both the scheduling policy and priority is assigned on a per-thread basis, with the default policy always being SCHED_OTHER and the default real-time priority being 0 (in other words, it’s a non-real-time thread; see Table 10.1).

On a given Linux system, we can always see all processes alive (via a simple ps -A), or, with GNU ps, even every thread alive (one...

Learning about the CPU scheduling internals – part 3

Let’s begin by exploring the topic of preemption.

Preemptible kernel

Please visualize this hypothetical situation: you’re running on a system with just one CPU core. An analog clock app is running on the GUI along with a C program, a.out, whose one line of code is (groan) while (1);. So, what do you think: will the CPU - hogger while 1 process indefinitely hog the CPU, thus causing the GUI clock app to stop ticking (will its second hand stop moving altogether)?

A little thought (and experimentation) will reveal that, indeed, the GUI clock app keeps ticking in spite of the naughty CPU hogger app! This is really the whole point of having an OS-level scheduler: it can, and does, preempt (kick out!) the CPU-hogging user space process. (We briefly discussed the CFS algorithm previously; CFS will cause the aggressive CPU-bound process to accumulate a huge vruntime value and thus move more to the right...

Summary

In this chapter, you learned about several areas and facets of the versatile Linux kernel’s CPU (or task) scheduler. Firstly, you saw how the actual KSE is a thread and not a process. We also learned that, in a monolithic OS like Linux, there is no “scheduler” thread within the kernel: scheduling is performed by a process context thread – the current thread – running the scheduling code paths, itself context-switching to the next task when done (thereby kicking itself off the processor – of course, the timer interrupt softirq housekeeping code paths have a key role to play in scheduler-related housekeeping as well!).

We then gained an appreciation of the available scheduling policies that the OS implements. Next, you understood that to support multiple CPUs in a superbly scalable fashion, the kernel powerfully mirrors this with a design that employs one runqueue per CPU core per modular scheduling class (again, the cgroups framework...

Questions

As we conclude, here is a list of questions for you to test your knowledge regarding this chapter’s material: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E/blob/main/questions/ch10_qs_assignments.txt. You will find some of the questions answered in the book’s GitHub repo: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E/tree/main/solutions_to_assgn.

Further reading

To help you delve deeper into the subject with useful materials, we provide a rather detailed list of online references and links (and, at times, even books) in a Further reading document in this book’s GitHub repository, available here: https://github.com/PacktPublishing/Linux-Kernel-Programming_2E/blob/main/Further_Reading.md.

Learn more on Discord

To join the Discord community for this book – where you can share feedback, ask questions to the author, and learn about new releases – follow the QR code below:

https://packt.link/SecNet