Linux 2.6 Scheduling Algorithm Sketch

Scheduling classes:

• Real-time FIFO
• Real-time RR
• Conventional time-shared

Processes running in conventional time-shared:

• Static priority, [Tex]sp \in [100,139] \Rightarrow[/Tex] use to compute quantum duration, [Tex]Q[/Tex].
  [Tex]
  Q = \left\{ \begin{array}{ll}
  (140 - sp) \times 20 & \mbox{if sp < 120} \\
  (140 - sp) \times 5 & \mbox{if sp \geq 120}
  \end{array} \right.
  [/Tex]
• Dynamic prority, [Tex]dp = \max(100, \min(sp - bonus + 5, 139))[/Tex] where [Tex]bonus \in [0,10][/Tex]
  • Bonus is computed based on the process average sleep time. Effectively, a process sleeps more will get more bonus, utilizes CPU will decrease its bonus.
  • Use with static priority to determine if a task is interactive ([Tex]dp \leq 3 \times sp / 4 + 28[/Tex]).
  • Dynamic priority is looked up by scheduler to select a new process to run.
• Active & expired processes
  • When a process uses up a quantum, if the process is active batch, it will be transferred to expired list; if the process is active interactive, it will usually remain in active list.
  • An active interactive process will be transferred to expired list if the eldest expired process waited for a long time, or has higher static priority.

Processes running in real-time:

• Real-time priority [Tex]\in[/Tex] [1,99]
• Always favor higher priority runnable processes.
• Always active.
• Time quantum depends on static priority.
• Does not calculate dynamic priority.

Priority array:

• Maintains active and expire priority array.
• For each priority in a priority array, it maintains a list of associated processes.
• When the active priority array becomes empty, the scheduler can just swap the active and expire arrays with merely pointer assignments.

Reference:

1. Linux Kernel Development by Robert Love
2. Understanding the Linux Kernel by Daniel P. Bovet, Marco Cesati