CPU Scheduling — The Trade Between Fairness and Responsiveness
In a nutshell
A scheduler is a policy that decides what to give up among conflicting goals: throughput, waiting time, response time, and fairness.
Why this was needed
When there are more runnable processes than cores, someone has to wait. Depending on the order in which they are run, the average waiting time for the same set of jobs can differ by several times. Take a famous example.
Suppose three processes have CPU bursts of 24, 3, and 3, and all arrive at the same time.
- Running them in the order P1, P2, P3 gives waiting times of 0, 24, and 27, with an average of 17.
- Running them in the order P2, P3, P1 gives waiting times of 6, 0, and 3, with an average of 3.
The same work finishes in the same total time, yet the average waiting time differs by more than a factor of 5. This phenomenon, in which short jobs queue up behind a long one, is called the convoy effect, and it is the typical weakness of FCFS, which serves processes in order of arrival.
How it works
The characteristics of the main algorithms can be summarized as follows.
| Algorithm | Preemption | Starvation | Strength | Weakness |
|---|---|---|---|---|
| FCFS | No | No | Simple | Convoy effect |
| SJF | No | Yes | Optimal average waiting time | Cannot know the next burst |
| SRTF | Yes | Yes | Better response than SJF | Needs prediction, more switches |
| Priority | Both | Yes | Can reflect policy | Starvation, needs aging |
| Round robin | Yes | No | Even response time | Hard to choose the quantum |
| Multilevel feedback queue | Yes | Possible | Most flexible | Many parameters |
It can be proven that SJF is optimal for average waiting time, but it has a fatal problem: you cannot know the length of the next CPU burst in advance. So real implementations predict it with an exponential average of past bursts. The next prediction is alpha times the most recent measured value plus (1 minus alpha) times the previous prediction, and alpha is usually 0.5.
In round robin, the choice of time quantum is everything. If the quantum is too large it becomes the same as FCFS, and if it is too small the cost of context switches eats into the actual working time. As a rule of thumb, you choose a quantum such that 80 percent of CPU bursts finish within it.
The Linux CFS approaches the problem from a slightly different angle. It tracks the virtual runtime (vruntime) of each task and runs the task with the smallest value next. vruntime is the actual running time divided by a weight, and the weight comes from the nice value. A low nice value (a high priority) gives a large weight, so vruntime increases slowly and the task is selected more often. The structure is managed with a red-black tree, so insertion and deletion take logarithmic time, and the next task to run is always the leftmost node.
What it looks like in the field
This concept appears directly when you set CPU limits in a container environment. The cgroup CPU shares (shares/weight) correspond to CFS weights and set the ratio when there is contention, while the CPU quota sets an upper bound on the time that can be used per period. People often confuse the two and ask, "I lowered the share, so why is it still using all the CPU?" A share matters only under contention and does not block an idle CPU.
The quota side has a different trap. An application with many threads can use up its quota early in a period and then be stopped entirely for the rest of it, which is throttling. If you see the symptom of low average CPU utilization but spikes only in the tail of response latency, look at the throttle counters first.
Waiting that does not use the CPU is far more common
So far we have talked about processes that are ready to run competing for the CPU. On a real server, however, most of the time a process waits is not its turn on the CPU but time spent waiting for input and output to finish. If you cannot make this distinction, you will misdiagnose performance problems wholesale.
The load average is the classic place for misunderstanding. The Linux load average counts not only runnable processes but also processes waiting for disk I/O. So a situation with CPU utilization of 20% and a load average of 30 can occur normally. Adding CPUs has no effect then, and what you need to look at is the disk or network side.
Looking at a process's state makes this distinction visible. R means running or waiting for its turn, and D means an uninterruptible wait. If the D state lasts long, the process cannot be killed even by a signal, which is how processes that cannot even be terminated pile up when storage stalls.
And waiting itself affects scheduling. A process that wakes up after a long wait has not used the CPU in the meantime, so its vruntime, as described above, is small, and it runs with priority as soon as it wakes. This is why interactive programs feel responsive. While waiting for a key press, its vruntime does not grow, so when input arrives it runs ahead of processes that were only computing.
Translated into diagnostic order, it goes like this. When responses are slow, do not stop at looking at CPU utilization. First determine whether the run queue is long, whether the I/O wait is long, or whether you are caught in the throttling described above. The three have completely different causes and responses, and a single CPU graph on a dashboard cannot tell them apart.
What to check in the quiz that follows
Check whether you can calculate why the average waiting time changes just by changing the order for the same set of jobs, and how CFS's vruntime expresses priority.