Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

number crunchers, while these in turn differ considerably from multimedia systems. In fact, the scheduler

code has seen two complete rewrites in recent years:

1. During the development series 2.5, a so-calledO(1) scheduler replaced the previous sched-
   uler. One particular property of this scheduler was that it could perform its work in constant
   time independent of the number of processes that were running on a system. The design
   broke quite radically with the previously employed scheduling architecture.


2. Thecompletely fair schedulerwas merged during the development of kernel 2.6.23. The new
   code again marked a complete departure from previous principles by abandoning, for
   instance, many heuristics that were required in previous schedulers to ensure that
   interactive tasks would respond quickly. The key feature of this scheduler is that it tries
   to resemble ideal fair scheduling as close as possible. Besides, it cannot only schedule
   individual tasks, but works with more generalscheduling entities. This allows, for instance,
   for distribution the available time between all processes of different users, and then among
   the processes of each user.
   I discuss the implementation of this scheduler below in detail.

Before we concern ourselves with how scheduling is implemented in the kernel, it is useful to discuss the

states that a process may have.

2.2 Process Life Cycle

A process is not always ready to run. Occasionally, it has to wait for events from external sources

beyond its control — for keyboard input in a text editor, for example. Until the event occurs, the process

cannot run.

The scheduler must know the status of every process in the system when switching between tasks; it

obviously doesn’t make sense to assign CPU time to processes that have nothing to do. Of equal impor-

tance are the transitions between individual process states. For example, if a process is waiting for data

from a peripheral device, it is the responsibility of the scheduler to change the state of the process from

waiting to runnable once the data have arrived.

A process may have one of the following states:

❑ Running— The process is executing at the moment.

❑ Waiting— The process is able to run but is not allowed to because the CPU is allocated to

another process. The scheduler can select the process, if it wants to, at the next task switch.

❑ Sleeping— The process is sleeping and cannot run because it is waiting for an external event.

The schedulercannotselect the process at the next task switch.

The system saves all processes in a process table — regardless of whether they are running, sleeping, or

waiting. However, sleeping processes are specially ‘‘marked‘‘ so that the scheduler knows they are not

ready to run (see how this is implemented in Section 2.3). There are also a number of queues that group

sleeping processes so that they can be woken at a suitable time — when, for example, an external event

that the process has been waiting for takes place.