Understanding the Linux Kernel, Second Edition

The Scheduling Algorithm

The Linux scheduling algorithm works by dividing the CPU time into epochs . In a single epoch, every process has a specified time quantum whose duration is computed when the epoch begins. In general, different processes have different time quantum durations. The time quantum value is the maximum CPU time portion assigned to the process in that epoch. When a process has exhausted its time quantum, it is preempted and replaced by another runnable process. Of course, a process can be selected several times from the scheduler in the same epoch, as long as its quantum has not been exhausted—for instance, if it suspends itself to wait for I/O, it preserves some of its time quantum and can be selected again during the same epoch. The epoch ends when all runnable processes have exhausted their quanta; in this case, the scheduler algorithm recomputes the time-quantum durations of all processes and a new epoch begins.

Each process has a base time quantum , which is the time-quantum value assigned by the scheduler to the process if it has exhausted its quantum in the previous epoch. The users can change the base time quantum of their processes by using the nice( ) and setpriority( ) system calls (see Section 11.3 later in this chapter). A new process always inherits the base time quantum of its parent.

The INIT_TASK macro sets the value of the initial time quantum of process 0 (swapper) to DEF_COUNTER; that macro is defined as follows:

#define DEF_COUNTER ( 10 ...