Chapter 2: Process Management and Scheduling
2.5.1 Overview
The kernel must provide a method of sharing CPU time as fairly as possible between the individual
processes while at the same time taking into account differing task priorities. There are many ways of
doing this, and all have their pros and cons, which weneed not discuss here (see [Tan07] for an overview
of potential approaches). Our focus is on the solution adopted in the Linux kernel.Theschedulefunction is the starting point to an understanding of scheduling operations. It is defined in
kernel/sched.cand is one of the most frequently invoked functions in the kernel code. The implemen-
tation of the scheduler is obscured a little by several factors:❑ On multiprocessor systems, several details (some very subtle) must be noted so that the sched-
uler doesn’t get under its own feet.
❑ Not onlypriority schedulingbut also two other soft real-time policies required by the Posix stan-
dard are implemented.
❑ gotosare used to generate optimal assembly language code. These jump backward and forward
in the C code and run counter to all principles of structured programming. However, this feature
canbe beneficial if it is used with great care, and the scheduler is one example wheregotosmake
sense.In the following overview, I consider the completely fair scheduler and neglect real-time tasks for now.
I come back to them later. An outstanding feature of the Linux scheduler is that it does not require the
concept of time slices, at least not in the traditional way. Classical schedulers compute time slices for
each process in the system and allow them to run until their time slice is used up. When all time slices of
all processes have been used up, they need to be recalculated again. The current scheduler, in contrast,
considers only the wait time of a process — that is,how long it has been sitting around in the run-queue
and was ready to be executed. The task with the gravest need for CPU time is scheduled.The general principle of the scheduler is to provide maximum fairness to each task in the system in terms
of the computational power it is given. Or, put differently, it tries to ensure that no task is treated unfairly.
Now this clearly sounds good, but what dofairandunfairwith respect to CPU time mean? Consider an
ideal computer that can run an arbitrary number of tasks in parallel: IfNprocesses are present on the
system, then each one getsN^1 of the total computational power, and all tasks really execute physically
parallel. Suppose that a task requires 10 minutes to complete its work. If 5 such tasks are simultaneously
present on a perfect CPU, each will get 20 percent of the computational power, which means that it will
be running for 50 instead of 10 minutes. However, all 5 tasks will finish their job after exactly this time
span, and none of them will have ever been inactive!This is clearly not achievable on real hardware: If a system has only a single CPU, at most one process can
be run simultaneously. Multitasking is only achievedby switching back and forth between the tasks with
high frequency. For users, who think considerably more slowly than the switching frequency, this creates
the illusion of parallel executing, but in reality, it is not. While more CPUs in the system improve the
situation and allow perfect parallel execution of a small number of tasks, there will always be situations
in which fewer CPUs than processes that are to be run are available, and the problem starts anew.If multitasking is simulated by running one processafter another, then the process that is currently
running is favored over those waiting to be picked by the scheduler — the poor waiting processes are
being treated unfairly. The unfairness is directly proportional to the waiting time.