Like any time-sharing system, Linux achieves the magical effect of an apparent simultaneous execution of multiple processes by switching from one process to another in a very short time frame. Process switching itself was discussed in Chapter 3; this chapter deals with scheduling, which is concerned with when to switch and which process to choose.
The chapter consists of three parts. Section 11.1 introduces the choices made by Linux to schedule processes in the abstract. Section 11.2 discusses the data structures used to implement scheduling and the corresponding algorithm. Finally, Section 11.3 describes the system calls that affect process scheduling.
The scheduling algorithm of traditional Unix operating systems must fulfill several conflicting objectives: fast process response time, good throughput for background jobs, avoidance of process starvation, reconciliation of the needs of low- and high-priority processes, and so on. The set of rules used to determine when and how to select a new process to run is called scheduling policy .
Linux scheduling is based on the time-sharing technique already introduced in Section 6.3: several processes run in "time multiplexing” because the CPU time is divided into "slices,” one for each runnable process.[72] Of course, a single processor can run only one process at any given instant. If a currently running process is not terminated when its time slice or quantum expires, a process switch may take place. Time-sharing relies on timer interrupts and is thus transparent to processes. No additional code needs to be inserted in the programs to ensure CPU time-sharing.
The scheduling policy is also based on ranking processes according to their priority. Complicated algorithms are sometimes used to derive the current priority of a process, but the end result is the same: each process is associated with a value that denotes how appropriate it is to be assigned to the CPU.
In Linux, process priority is dynamic. The scheduler keeps track of what processes are doing and adjusts their priorities periodically; in this way, processes that have been denied the use of the CPU for a long time interval are boosted by dynamically increasing their priority. Correspondingly, processes running for a long time are penalized by decreasing their priority.
When speaking about scheduling, processes are traditionally classified as " I/O-bound” or “CPU-bound.” The former make heavy use of I/O devices and spend much time waiting for I/O operations to complete; the latter are number-crunching applications that require a lot of CPU time.
An alternative classification distinguishes three classes of processes:
- Interactive processes
These interact constantly with their users, and therefore spend a lot of time waiting for keypresses and mouse operations. When input is received, the process must be woken up quickly, or the user will find the system to be unresponsive. Typically, the average delay must fall between 50 and 150 milliseconds. The variance of such delay must also be bounded, or the user will find the system to be erratic. Typical interactive programs are command shells, text editors, and graphical applications.
- Batch processes
These do not need user interaction, and hence they often run in the background. Since such processes do not need to be very responsive, they are often penalized by the scheduler. Typical batch programs are programming language compilers, database search engines, and scientific computations.
- Real-time processes
These have very stringent scheduling requirements. Such processes should never be blocked by lower-priority processes and should have a short guaranteed response time with a minimum variance. Typical real-time programs are video and sound applications, robot controllers, and programs that collect data from physical sensors.
The two classifications we just offered are somewhat independent. For instance, a batch process can be either I/O-bound (e.g., a database server) or CPU-bound (e.g., an image-rendering program). While real-time programs are explicitly recognized as such by the scheduling algorithm in Linux, there is no way to distinguish between interactive and batch programs. To offer a good response time to interactive applications, Linux (like all Unix kernels) implicitly favors I/O-bound processes over CPU-bound ones.
Programmers may change the scheduling priorities by means of the system calls illustrated in Table 11-1. More details are given in Section 11.3.
Table 11-1. System calls related to scheduling
|
System call |
Description |
|---|---|
|
|
Change the priority of a conventional process. |
|
|
Get the maximum priority of a group of conventional processes. |
|
|
Set the priority of a group of conventional processes. |
|
|
Get the scheduling policy of a process. |
|
|
Set the scheduling policy and priority of a process. |
|
|
Get the priority of a process. |
|
|
Set the priority of a process. |
|
|
Relinquish the processor voluntarily without blocking. |
|
|
Get the minimum priority value for a policy. |
|
|
Get the maximum priority value for a policy. |
|
|
Get the time quantum value for the Round Robin policy. |
Most system calls shown in the table apply to real-time processes, thus allowing users to develop real-time applications. However, Linux does not support the most demanding real-time applications because its kernel is nonpreemptive (see the later section Section 11.2.3).
As mentioned in the first chapter, Linux
processes are
preemptive
. If a process enters the
TASK_RUNNING state, the kernel checks whether its
dynamic priority is greater than the priority of the currently
running process. If it is, the execution of
current is interrupted and the scheduler is
invoked to select another process to run (usually the process that
just became runnable). Of course, a process may also be preempted
when its time quantum expires. As mentioned in Section 6.3, when this occurs, the
need_resched field of the current process is set,
so the scheduler is invoked when the timer interrupt handler
terminates.
For instance,
let’s consider a scenario in which only two
programs—a text editor and a compiler—are being executed.
The text editor is an interactive program, so it has a higher dynamic
priority than the compiler. Nevertheless, it is often suspended,
since the user alternates between pauses for think time and data
entry; moreover, the average delay between two keypresses is
relatively long. However, as soon as the user presses a key, an
interrupt is raised and the kernel wakes up the text editor process.
The kernel also determines that the dynamic priority of the editor is
higher than the priority of current, the currently
running process (the compiler), so it sets the
need_resched field of this process, thus forcing
the scheduler to be activated when the kernel finishes handling the
interrupt. The scheduler selects the editor and performs a process
switch; as a result, the execution of the editor is resumed very
quickly and the character typed by the user is echoed to the screen.
When the character has been processed, the text editor process
suspends itself waiting for another keypress and the compiler process
can resume its execution.
Be aware that a preempted process is not suspended, since it remains
in the TASK_RUNNING state; it simply no longer
uses the CPU.
Some real-time operating systems feature preemptive kernels, which means that a process running in Kernel Mode can be interrupted after any instruction, just as it can in User Mode. The Linux kernel is not preemptive, which means that a process can be preempted only while running in User Mode; nonpreemptive kernel design is much simpler, since most synchronization problems involving the kernel data structures are easily avoided (see Section 5.2).
The quantum duration is critical for system performances: it should be neither too long nor too short.
If the quantum duration is too short, the system overhead caused by process switches becomes excessively high. For instance, suppose that a process switch requires 10 milliseconds; if the quantum is also set to 10 milliseconds, then at least 50 percent of the CPU cycles will be dedicated to process switching.[73]
If the quantum duration is too long, processes no longer appear to be executed concurrently. For instance, let’s suppose that the quantum is set to five seconds; each runnable process makes progress for about five seconds, but then it stops for a very long time (typically, five seconds times the number of runnable processes).
It is often believed that a long quantum duration degrades the response time of interactive applications. This is usually false. As described in Section 11.1.1 earlier in this chapter, interactive processes have a relatively high priority, so they quickly preempt the batch processes, no matter how long the quantum duration is.
In some cases, a quantum duration that is too long degrades the responsiveness of the system. For instance, suppose two users concurrently enter two commands at the respective shell prompts; one command is CPU-bound, while the other is an interactive application. Both shells fork a new process and delegate the execution of the user’s command to it; moreover, suppose such new processes have the same priority initially (Linux does not know in advance if an executed program is batch or interactive). Now if the scheduler selects the CPU-bound process to run, the other process could wait for a whole time quantum before starting its execution. Therefore, if such duration is long, the system could appear to be unresponsive to the user that launched it.
The choice of quantum duration is always a compromise. The rule of thumb adopted by Linux is choose a duration as long as possible, while keeping good system response time.
[72] Recall that stopped and suspended processes cannot be selected by the scheduling algorithm to run on the CPU.
[73] Actually, things could be much worse than this; for example, if the time required for the process switch is counted in the process quantum, all CPU time is devoted to the process switch and no process can progress toward its termination.