Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

granularityare multiplied by the correction factor 1+log 2 (nr_cpus), wherenr_cpusrepre-

sents the number of available CPUs. However, they must not exceed 200 ms.sysctl_sched_

wakeup_granularityis also increased by the factor, but is not bounded from above.

New CPU selected?

sched_exec

sched_balance_self

sched_migrate_task

Figure 2-28: Code flow diagram forsched_exec.

2.8.2 Scheduling Domains and Control Groups

In the previous discussion of the scheduler code, we have often come across the situation that the sched-

uler does not deal directly with processes, but withschedulable entities. This allows for implementing

group scheduling: Processes are placed into different groups, and the scheduler is first fair among these

groups and then fair among all processes in the group. This allows, for instance, granting identical shares

of the available CPU time to each user. Once the scheduler has decided how much time each user gets,

the determined interval is then distributed between the users’ processes in a fair manner. This naturally

implies that the more processes a user runs, the less CPU share each process will get. The amount of time

for the user in total is not influenced by the number of processes, though.

Grouping tasks between users is not the only possibility. The kernel also offerscontrol groups,which

allow — via the special filesystemcgroups— creating arbitrary collections of tasks, which may even be

sorted into multiple hierarchies. The situation is illustrated in Figure 2-29.

Schedulable

entity

task

Figure 2-29: Overview of fair group scheduling: The available CPU time is first distributed fairly

among the scheduling groups, and then between the processes in each group.

To reflect the hierarchical situation within the kernel,struct sched_entityis augmented with an ele-

ment that allows for expressing this hierarchy:

<sched.h>

struct sched_entity {

...

#ifdef CONFIG_FAIR_GROUP_SCHED

struct sched_entity *parent;

...

#endif

...

}