Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

Besides these, the kernel defines the convenience methodcheck_preempt_currto call the

check_preempt_currmethod of the scheduling class that is associated with a given task:

kernel/sched.c

static inline void check_preempt_curr(struct rq *rq, struct task_struct *p)

Userland applications do not directly interact with scheduling classes. They only know of the constants

SCHED_xyzas defined above. It is the kernel’s job to provide an appropriate mapping between these con-

stants and the available scheduling classes.SCHED_NORMAL,SCHED_BATCH,andSCHED_IDLEare mapped

tofair_sched_class, whileSCHED_RRandSCHED_FIFOare associated withrt_sched_class.Both

fair_sched_classandrt_sched_classare instances ofstruct sched_classthat represent, respec-

tively, the completely fair and the realtime scheduler. The contents of these instances will be shown

when I discuss the respective scheduler classes in detail.

Run Queues

The central data structure of the core scheduler thatis used to manage active processes is known as the

run queue. Each CPU has its own run queue, and each active process appears on just one run queue. It is

not possible to run a process on several CPUs at the same time.^23

The run queue is the starting point for many actions of the global scheduler. Note, however, that pro-

cesses are not directly managed by the general elements of the run queue! This is the responsibility of

the individual scheduler classes, and a class-specific sub-run queue is therefore embedded in each run

queue.^24

Run queues are implemented using the following data structure. To simplify matters, I have omitted

several statistical elements that do not directly influence the work of the run queue, and also the elements

required on multiprocessor systems.

kernel/sched.c

struct rq {

unsigned long nr_running;

#define CPU_LOAD_IDX_MAX 5

unsigned long cpu_load[CPU_LOAD_IDX_MAX];

...

struct load_weight load;

struct cfs_rq cfs;

struct rt_rq rt;

struct task_struct *curr, *idle;

u64 clock;

...

};

❑ nr_runningspecifies the number of runnable processes on the queue — regardless of their pri-

ority or scheduling class.

(^23) However, threads originating from the same process can execute on different processors as task management makes no important
distinction between processes and threads.
(^24) For readers familiar with earlier versions of the kernel, it might beinteresting to know the scheduler class run queues replace the
lists ofactiveandexpiredtasks that were utilized by the previousO(1)scheduler.