Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

2.5.4 Core Scheduler

As mentioned above, scheduler implementation is based on two functions — the periodic scheduler and

the main scheduler function. These distribute CPU time on the basis of the priorities of the available

processes; this is why the overall method can also be referred to aspriority scheduling— although this is

a very general term, naturally. I discuss how priority scheduling is implemented in this section.

The PeriodicScheduler

The periodic scheduler is implemented inscheduler_tick. The function is automatically called by the

kernel with the frequencyHZif system activity is going on. If no processes are waiting to be scheduled, the

tick can also be turned off to save power on computers where this is a scarce resource, for instance, lap-

tops or small embedded systems. The mechanism underlying periodic actions is discussed in Chapter 15.

The function has two principal tasks.

1. To manage the kernel scheduling-specific statistics relating to the whole system and to the
   individual processes. The main actions performed involve incrementing counters and are of
   no particular interest to us.


2. To activate the periodic scheduling method of the scheduling class responsible for the cur-
   rent process.

kernel/sched.c

void scheduler_tick(void)

{

int cpu = smp_processor_id();

struct rq *rq = cpu_rq(cpu);

struct task_struct *curr = rq->curr;

...

__update_rq_clock(rq)

update_cpu_load(rq);

The first part of the function deals with updating the run queue clock. This is delegated to

__update_rq_clock, which essentially advances theclocktime stamp of the current instance ofstruct

rq. The function has to deal with some oddities of hardware clocks, but these are not relevant for our

purposes.update_cpu_loadthen deals with updating thecpu_load[]history array of the run queue.

This essentially shifts the previously stored load values one array position ahead, and inserts the present

run queue load into the first position. Additionally, the function introduces some averaging to ensure

that the contents of the load array do not exhibit large discontinuous jumps.

Thanks to the modular structure of the scheduler, the main work is really simple, as it can be completely

delegated to the scheduler-class-specific method:

kernel/sched.c

if (curr != rq->idle)

curr->sched_class->task_tick(rq, curr);

}

Howtask_tickis implemented depends on the underlying scheduler class. The completely fair sched-

uler, for instance, will in this method check if a process has been running for too long to avoid large

latencies, but I discuss this in detail below. Readers familiar with the old time-slice-based scheduling