9. A Look at the Linux Scheduler

9.1. A Bit of History

Prior to kernel version 2.6.23, Linux employed a scheduler that combined priority queues with a heuristic that altered a process’s priority based on the amount of a time slice it used. CPU-bound processes would consume their entire slice and would drop in priority. Conversely, I/O-bound processes would often block before consuming an entire time slice and so their priority would be increased. This was meant to allow for interactive processes to stay in the high priority queues and batch processing jobs (really anything that was CPU-bound) to drop. This scheduler had a number of heuristics that were used in decision making that were also exposed as tunable parameters, but the biggest feature it boasted was that it had O(1) run time. In other words, the time to select the next process was constant, regardless of how many runnable processes there were in the system.

9.2. The Completely Fair Scheduler (CFS)

The Linux Kernel documentation has the whole story here. The completely fair scheduler was a from-scratch redesign of the Linux scheduler; it did away with priority queues and with all1 heuristics and tunables found in the O(1) scheduler. CFS introduced keeping a counter for the amount of runtime each task has received and this counter is used to decide on the next task to run. Instead of priority queues CFS places all tasks in a red-black tree sorted on their accumulated runtime with tasks on the left having less accumulated run time than tasks on the right. When the system needs a new task to run, the left most task is selected. This change allows CFS to completely avoid the starvation of CPU bound tasks that could occur with the previous scheduler.

---

1

CFS still has a single tunable than can be exposed, but the kernel must be configured with SCHED_DEBUG selected.