How does Linux's fair-share CPU scheduler (CFS, and EEVDF since kernel 6.6) turn a task's nice value into an actual share of CPU time?

## Proportional share, not priority levels A classic priority scheduler runs the highest-priority runnable task and only descends when nothing above is runnable — which starves the bottom. Linux's normal policy, `SCHED_OTHER`, is deliberately not that. It is a **weighted fair-share** scheduler: every runnable task gets CPU, and the nice value determines only what fraction. ## From nice to weight The kernel holds a fixed lookup table mapping each of the 40 nice values to a weight. Nice 0 has weight **1024**; each step towards -20 multiplies the weight by roughly 1.25, and each step towards 19 divides it by roughly 1.25. So nice -1 is about 1277 and nice 1 about 820. The entitlement of a runnable task is then: ``` share = weight(task) / sum of weight(t) for all runnable t on that CPU ``` The 1.25 ratio was chosen for a memorable property: with two competing CPU-bound tasks, a one-step nice difference moves about **10%** of the CPU from one to the other. Two tasks at nice 0 and nice 1 split roughly 55/45. Two tasks five steps apart split roughly 75/25, because 1.25^5 is about 3. ## Virtual runtime: the bookkeeping trick The scheduler cannot afford to recompute fractions constantly, so it keeps a per-task **virtual runtime** (vruntime). When a task runs for some real nanoseconds, its vruntime advances by that time scaled by `1024 / weight`: - A nice 0 task's virtual clock runs at real speed. - A favoured (low-nice, high-weight) task's virtual clock runs *slower* than real time, so it looks like it has consumed less and gets picked again sooner. - A de-prioritised task's virtual clock races ahead, so it falls behind in the ordering. CFS ("Completely Fair Scheduler", the default from 2.6.23 to 6.5) then had one rule: run the runnable task with the smallest vruntime, kept in a red-black tree keyed by vruntime. Fairness fell out of the arithmetic. ## What EEVDF changed in Linux 6.6 CFS controlled *how much* CPU each task got but had only indirect, heuristic control over *when* a waking task ran — the source of long-standing latency complaints and a pile of tunables. Linux 6.6 replaced the pick logic with **EEVDF** (Earliest Eligible Virtual Deadline First): - Each task accumulates **lag**: how far its actual service is from its fair-share entitlement. A task that has received less than its share has positive lag and is *eligible*. - Each task is assigned a virtual **deadline** derived from its allotted slice and its weight. - The scheduler runs the eligible task with the earliest virtual deadline. The weights and the resulting long-run shares are unchanged — nice still means exactly what it meant. What changed is that short, latency-sensitive tasks get served promptly without needing to be renice'd, and several CFS-era tuning knobs became irrelevant. The remaining scheduler tunables live under `/sys/kernel/debug/sched/` on kernels built with scheduler debugging, not in the general sysctl namespace. ## Why there is no fixed time slice Interviewers often ask "what is the Linux time slice?" expecting a number. There isn't one. The slice a task receives is computed from a target period, its weight, and the number of runnable tasks on that CPU, floored at a minimum granularity so that a hundred runnable tasks do not produce microsecond slices and a context-switch storm. Add more runnable tasks and every slice shrinks; give a task more weight and its slice grows. ## The practical consequences - **Nice never starves anything.** Even a nice 19 CPU hog keeps getting a small share, which is why nice is unsuitable for "this must never touch the CPU while the important thing runs". For that you need real-time policies or hard resource controls. - **Shares are relative to the competitors present.** A nice -5 task competing with one other task looks powerful; the same task competing with fifty gets its slice diluted like everyone else. - **Blocked tasks are not counted.** A task sleeping on I/O contributes no weight, so shares are computed over the *runnable* set, which changes constantly. - **Weights compose hierarchically.** When tasks are grouped by the scheduler, nice redistributes CPU among the tasks inside a group first, and the group's own weight decides how much the group gets overall — which is why a nice value can look ineffective across a boundary. ## What an interviewer is checking That you can say "proportional share by weight, tracked as virtual runtime" rather than "higher priority runs first", that you know a nice step is worth roughly 10% of contested CPU rather than an absolute guarantee, and ideally that you know the pick algorithm became EEVDF in 6.6 without the nice semantics changing.