Example: Linux Scheduling

• The Linux scheduler is a pre-emptive, priority-based algorithm with two separate priority ranges:
  • a real-time range from 0 to 99
  • and a nice value ranging from 100 to 140.
• These two ranges map into a global priority scheme whereby numerically lower values indicate higher priorities.
• Linux assigns higher-priority tasks longer time quanta and lower-priority tasks shorter time quanta. The relationship between priorities and time-slice length is shown in Fig. 12.

  Figure 12: The relationship between priorities and time-slice length.

  
• A runnable task is considered eligible for execution on the CPU as long as it has time remaining in its time slice. When a task has exhausted its time slice, it is considered expired and is not eligible for execution again until all other tasks have also exhausted their time quanta.
• The kernel maintains a list of all runnable tasks in a runqueue data structure. Because of its support for SMP, each processor maintains its own runqueue and schedules itself independently.
• Each runqueue contains two priority arrays -active and expired.
  • The active array contains all tasks with time remaining in their time slices,
  • and the expired array contains all expired tasks.

  Figure 13: List of tasks indexed according to priority.

  
• Each of these priority arrays contains a list of tasks indexed according to priority (see Fig. 13).
  • The scheduler chooses the task with the highest priority from the active array for execution on the CPU. On multiprocessor machines, this means that each processor is scheduling the highest-priority task from its own runqueue structure.
  • When all tasks have exhausted their time slices (that is, the active array is empty), the two priority arrays are exchanged; the expired array becomes the active array, and vice versa.