The effectiveness of any operating system is proportional to its ability to fairly schedule all contending processes. The process scheduler is the core component of the kernel, which computes and decides when and for how long a process gets CPU time. Ideally, processes require a timeslice of the CPU to run, so schedulers essentially need to allocate slices of processor time fairly among processes.

A scheduler typically has to:

Linux, which was primarily developed for desktop systems, has unassumingly evolved into a multi-dimensional operating system with its usage spread across embedded devices, mainframes, and supercomputers to room-sized servers. It has also seamlessly accommodated the ever-evolving diverse computing platforms such as SMP, virtualization, and real-time systems. The diversity of these platforms is brought forth by the kind of processes that run on these systems. For instance, a highly interactive desktop system may run processes that are I/O bound, and a real-time system thrives on deterministic processes. Every kind of process thus calls for a different kind of heuristic when it needs to be fairly scheduled, as a CPU-intensive process may require more CPU time than a normal process, and a real-time process would require deterministic execution. Linux, which caters to a wide spectrum of systems, is thus confronted with addressing the varying scheduling challenges...

Conventionally, the runqueue contains all the processes that are contending for CPU time on a given CPU core (a runqueue is per-CPU). The generic scheduler is designed to look into the runqueue whenever it is invoked to schedule the next best runnable task. Maintaining a common runqueue for all the runnable processes would not be a possible since each scheduling class deals with specific scheduling policies and priorities.

The kernel addresses this by bringing its design principles to the fore. Each scheduling class defined the layout of its runqueue data structure as best suitable for its policies. The generic scheduler layer implements an abstract runqueue structure with common elements that serves as the runqueue interface. This structure is extended with pointers that refer to class-specific runqueues. In other words, all scheduling classes embed their runqueues into the main runqueue structure. This is a classic design hack, which lets every scheduler class choose an appropriate...

The process of scheduling starts with a call to the generic scheduler, that is, the schedule() function, defined in <kernel/sched/core.c>. This is perhaps one of the most invoked routines in the kernel. The functionality of schedule() is to pick the next best runnable task. The pick_next_task() of the schedule() function iterates through all the corresponding functions contained in the scheduler classes and ends up picking the next best task to run. Each scheduler class is linked using a single linked list, which enables the pick_next_task() to iterate through these classes.

Considering that Linux was primarily designed to cater to highly interactive systems, the function first looks for the next best runnable task in the CFS class if there are no higher-priority runnable tasks in any of the other classes (this is done by checking whether the total number of runnable tasks (nr_running) in the runqueue is equal to the total number of runnable tasks in the...

The decision of which process to run depends on the priority of the process. Every process is labelled with a priority value, giving it an immediate position in terms of when it will be given CPU time. Priorities are fundamentally classified into dynamic and static priorities on *nix systems. Dynamic priorities are basically applied to normal processes dynamically by the kernel, considering various factors such as the nice value of the process, its historic behavior (I/O bound or processor bound), lapsed execution, and waiting time. Static priorities are applied to real-time processes by the user and the kernel does not change their priorities dynamically. Processes with static priorities are thus given higher priority when scheduling.

Let's now go deeper into each scheduling class and understand the operations, policies, and heuristics it engages in managing scheduling operations adeptly and elegantly for its processes. As mentioned earlier, an instance of struct sched_class must be provided by each scheduling class; let's look at some of the key elements from that structure: