Appearance
2.3.3 — How Linux Schedules
The photo-upload service shares a server with a nightly backup that keeps several cores busy for an hour. 2.3.2 ended with that problem: during the backup, uploads that normally take 50 ms took two seconds. The fix is one word in front of the backup command:
sh
nice -n 10 ./nightly-backup.shWith that change, uploads go back to about 50 ms, and the backup still finishes, a little later. This page explains exactly why that works. It covers five things:
- how Linux decides which thread runs, with real numbers;
- what the
nicenumber actually changes; - how real-time threads jump the queue;
- how many cores share the work;
- and the famous failure where priorities turned upside down on Mars.
1. Classes first, then fairness within a class
Linux sorts every thread into a scheduling class. The classes are checked in a fixed order, and a class gets the CPU only if every class above it has nothing ready to run.
| Order | Class | Who is in it |
|---|---|---|
| 1 | deadline | threads with a declared deadline |
| 2 | real-time | SCHED_FIFO and SCHED_RR threads |
| 3 | normal | almost everything, including our service |
| 4 | idle | work that should run only when nothing else wants the CPU |
(There is also a special top class the kernel uses internally to stop a core, which ordinary programs never see.)
Nearly every thread you will ever write is in the normal class. Sections 2 to 4 are about how threads inside that class share the CPU. Section 5 covers the real-time classes, which work very differently.
2. The fair scheduler: run whoever has had the least
From 2007 to 2023, Linux shared the CPU between normal threads with the Completely Fair Scheduler, or CFS, written by Ingo Molnár. Its core idea is easy to say and is still the right picture of how Linux behaves.
Track how much CPU each thread has had. Always run the thread that has had the least.
The amount each thread has had is called its virtual runtime, or vruntime. When a thread runs for some time, its vruntime goes up. The scheduler keeps the ready threads sorted by vruntime and always picks the one at the front, the one with the smallest number. As that thread runs, its number climbs. Soon another thread has a smaller number, and the scheduler switches to it.
Follow three equal threads, X, Y and Z, starting at zero. Say each turn lasts 3 ms.
| Step | Runs | vruntime after (X, Y, Z) | Smallest next |
|---|---|---|---|
| 1 | X | 3, 0, 0 | Y (tie with Z) |
| 2 | Y | 3, 3, 0 | Z |
| 3 | Z | 3, 3, 3 | X |
| 4 | X | 6, 3, 3 | Y |
Every thread gets a turn, and over time they all get exactly the same share. That is the sense in which it is "completely fair". There are no fixed time slices handed out in advance. A thread simply runs until it is no longer the one most behind.
Finding the smallest quickly
With thousands of ready threads, scanning all of them to find the smallest vruntime on every decision would be too slow. So CFS keeps them in a red-black tree, a kind of self-balancing search tree (4.13.2). A search tree keeps items in sorted order, so the smallest is always at the far left. "Self-balancing" means the tree keeps itself short, so inserting or removing a thread takes about \log_2 n steps for n threads, read "log base two of n". With 4,000 threads that is about 12 steps, not 4,000.
What about a thread that has been asleep?
Our upload service sleeps almost all the time, waiting for photos. Its vruntime barely grows. So when it wakes up, its number is far smaller than the backup's, and it is picked at once. That is good: the service responds quickly.
But it creates a problem. If a thread slept for an hour, its vruntime would be an hour behind. When it woke, it would hog the CPU for a long time, "catching up" on the hour it missed. To stop that, when a thread wakes up, CFS sets its vruntime to nearly the smallest vruntime currently in the tree, if its own is lower. A waking thread still goes to the front of the line, so it responds quickly, but it cannot cash in hours of saved-up credit.
3. What nice actually changes: weights
Equal shares are not always wanted. The backup should get less than the upload service. Linux expresses this with the nice value, a number from −20 to +19 that every thread has. The default is 0.
The name is a small joke. A higher nice value means you are being nicer to everyone else, by taking less CPU for yourself. So +19 is the lowest priority and −20 is the highest. Any user may make their own programs nicer. Only the administrator may make a program less nice than 0.
Under the fair scheduler, nice does not set a fixed rank. It sets a weight. Each nice value has a weight in a table inside the kernel. Here are some entries:
| Nice | Weight |
|---|---|
| −10 | 9,548 |
| −5 | 3,121 |
| 0 | 1,024 |
| 5 | 335 |
| 10 | 110 |
| 19 | 15 |
Each step of 1 changes the weight by about 1.25 times. The table was designed that way so that one nice step changes a thread's CPU share by about 10 %.
The weight changes how fast vruntime grows. When a thread runs for a real time \Delta t, read "delta t", meaning "a small amount of time", its vruntime grows by
\Delta\text{vruntime} = \Delta t \times \frac{1024}{\text{weight}}
Read that aloud as "the vruntime goes up by the real time it ran, multiplied by 1024 divided by its weight". For a nice-0 thread, the weight is 1024, so the fraction is 1, and vruntime grows at the same speed as real time. For a nice-10 thread, the weight is 110, so the fraction is 1024 ÷ 110 ≈ 9.3. Its vruntime grows about 9.3 times faster than real time.
Worked: the upload service and the backup
Put one upload thread at nice 0 next to one backup thread at nice 10, both always ready to run. Start both at vruntime 0, and say the scheduler can switch every 1 ms.
| Real time | Who runs | Upload vruntime | Backup vruntime |
|---|---|---|---|
| 0–1 ms | upload | 1.0 | 0 |
| 1–2 ms | backup | 1.0 | 9.3 |
| 2–11 ms | upload, 9 turns | 10.0 | 9.3 |
| 11–12 ms | backup | 10.0 | 18.6 |
| 12–21 ms | upload, 9 turns | 19.0 | 18.6 |
Each time the backup runs for 1 ms, its vruntime jumps by 9.3. The upload thread then needs about 9 ms of real time to catch up. So the pattern settles into roughly 9 ms of upload for every 1 ms of backup.
The exact shares come straight from the weights. Each thread gets its weight divided by the total weight:
\text{upload's share} = \frac{1024}{1024 + 110} \approx 90.3\% \qquad \text{backup's share} = \frac{110}{1134} \approx 9.7\%
That is why nice -n 10 fixed the uploads. Whenever the upload service has work, it gets over 90 % of the contested core. And when the upload service is asleep, which is most of the time, the backup gets the whole core, because there is nobody else to share with. Nice does not slow the backup down when the machine is quiet. It only decides who wins when both want the CPU at once.
Doing it from TypeScript
Node can set the nice value of any process the user owns. Here the upload service starts its thumbnail program at nice 10, so heavy thumbnail work never slows uploads down.
ts
// nice-thumbnailer.ts — run thumbnail work at a lower priority than the upload service
import { spawn } from "node:child_process";
import { getPriority, setPriority } from "node:os";
const child = spawn(process.execPath, ["-e", "setTimeout(() => {}, 500)"]); // a stand-in thumbnailer
console.log("service priority: ", getPriority()); // (1)
setPriority(child.pid!, 10); // (2)
console.log("thumbnailer priority:", getPriority(child.pid!)); // (3)
// Prints:
// service priority: 0
// thumbnailer priority: 10(1)With no argument,getPriorityreads this process's own nice value. It is 0, the default.(2)setPrioritysets the nice value of the child. On Linux and macOS this is the same nice value thenicecommand sets. On Windows, where the output above was produced, Node maps it onto Windows's own priority levels, and 10 becomes "below normal".(3)Reading it back confirms the change. Making a process less nice than 0 would fail with a permission error unless the service ran as an administrator, which is the rule from earlier in this section.
4. EEVDF: fairness plus deadlines
In Linux 6.6, released in October 2023, the fair scheduler's way of choosing the next thread was replaced by an algorithm called EEVDF, which stands for "earliest eligible virtual deadline first". It is still the normal class, and it still uses vruntime and the same weights. Sections 2 and 3 remain the right picture of how much CPU each thread gets. What changed is who goes next, and the change is about response time.
CFS had one weakness. It made sure every thread got its fair share over time. But it had no direct way to say "this thread needs its turn soon". A thread that needed a little CPU very often could still wait behind others.
EEVDF adds two ideas to fix that.
- Eligible. A thread is eligible if it has received no more than its fair share so far. A thread that has had more than its share must wait until the others catch up.
- Virtual deadline. Each thread also has a requested slice, the length of time it wants to run at a stretch. Its virtual deadline is its eligible time plus its slice, scaled by its weight. Among the eligible threads, the scheduler always picks the one with the earliest deadline.
The effect is that a thread asking for a short slice gets an earlier deadline, so it is picked sooner. It still cannot take more than its fair share overall, because it stops being eligible once it is ahead. So EEVDF keeps the fairness of CFS and adds a way for responsive work to go first. If you see EEVDF named in a kernel version note, that is all it means.
5. Real-time threads: absolute priority
Some work cannot wait at all. A thread playing audio must deliver the next block of sound every few milliseconds, or you hear a click. A thread controlling a robot arm must react within a fixed time. For these, a fair share is not good enough. They need a guarantee.
That is what the real-time classes are for. A real-time thread has a priority from 1 to 99. Any ready real-time thread always beats every normal thread, whatever its nice value. Two policies decide what happens among real-time threads of the same priority:
SCHED_FIFO(first in, first out): the thread runs until it blocks, finishes, or a higher-priority real-time thread wants the CPU. It is never forced to share with equals.SCHED_RR(round-robin): the same, except that threads of equal priority take turns with time slices.
On Linux the command chrt sets these. For example, chrt -f 50 ./audio-player runs a program as SCHED_FIFO at priority 50. Only the administrator may do this.
This is a dangerous tool. A real-time thread stuck in a loop would take a core forever, because nothing in the normal class can ever preempt it. To stop one bug from freezing the whole machine, Linux by default limits all real-time threads together to 95 % of each second, leaving 5 % for normal threads. It is a safety net, not permission to be careless.
The deadline class goes one step further. A thread there declares three numbers: how much CPU it needs ("2 ms"), in what period ("every 10 ms"), and by when within that period ("finished within 5 ms"). The kernel admits the thread only if it can actually keep that promise alongside every other deadline thread, and then schedules them by whichever deadline is nearest, an algorithm called earliest deadline first. It is used for industrial control, audio and video systems.
The lesson for the photo-upload service is the one from 2.3.2's drill. Do not make a web service real-time. It does not need guaranteed deadlines, and a real-time service with a bug can starve the very system services it depends on, such as the logging daemon or the network. A lower nice value for the competing work is the right tool.
6. Many cores: one queue per core
Everything so far assumed one core. A real server has 8, 32 or 128. Linux keeps a separate run queue for every core, each with its own sorted set of ready threads. A core only looks at its own queue when it needs the next thread.
Why not one shared queue for all cores? Because every core would have to lock that one queue every time it chose a thread, thousands of times a second, and they would spend their time waiting for each other. Separate queues mean the cores almost never need to coordinate.
Separate queues create a new job, load balancing. If core 0 has ten ready threads and core 3 has none, core 3 is wasted. So every few milliseconds, and whenever a core runs out of work, the kernel moves threads from busy queues to idle ones.
Moving a thread has a cost. The thread's recent data is in the old core's caches (1.6). On the new core it starts with cold caches. So the scheduler prefers to keep a thread on the core it last ran on, and moves it only when the imbalance is worth it. Large servers make this harder still: memory is split into regions attached to different groups of cores, and reaching memory attached to another group is slower. The scheduler tries to keep a thread near its memory too.
You can override the choice. CPU affinity ties a thread to a chosen set of cores. On Linux, taskset -c 2,3 ./thumbnailer runs the thumbnailer only on cores 2 and 3. People use this to keep noisy work away from a latency-sensitive service, or to keep a thread's caches warm.
Containers share the CPU with quotas
In a container, the limit "this container may use 2 CPUs" is not done with nice values. It is done with a cgroup quota: the container's threads may use at most 200 ms of CPU time in every 100 ms period, counted across all cores. When the container uses up its quota early in a period, the kernel stops scheduling all its threads until the next period begins. This is called throttling. A service that is throttled shows sudden, regular pauses in its response times, even though the machine as a whole is not busy. 14.1.3 explains cgroups, and the symptom is worth recognising.
7. Priority inversion: when priorities turn upside down
In July 1997, NASA's Mars Pathfinder lander began resetting itself, again and again, a few days after it landed. The cause was a scheduling failure with a name every engineer should know: priority inversion.
The lander's computer ran several threads at different priorities. It happens in three steps.
- A low-priority thread, which collected weather data, took a lock on a shared data area. A lock lets only one thread use something at a time; 2.4.2 explains locks.
- A high-priority thread, which managed the shared data area, needed the same lock. It had to wait for the low-priority thread to finish and release it.
- Meanwhile a medium-priority thread, for communications, became ready. It did not need the lock at all. But it was higher than the low-priority thread, so the scheduler ran it instead. The low-priority thread could not run, so it could not release the lock, so the high-priority thread kept waiting.
So the high-priority thread was in effect stuck behind the medium one. Its priority had been turned upside down, "inverted". A watchdog timer noticed that the high-priority work was not getting done and reset the whole computer.
The engineers on Earth reproduced the fault in a copy of the lander and fixed it by switching on an option in the lander's operating system called priority inheritance. With it, a thread holding a lock temporarily takes on the priority of the highest thread waiting for that lock. The low-priority weather thread would inherit high priority the moment the high thread started waiting. Medium could no longer preempt it. It would finish quickly, release the lock, drop back to low priority, and the high thread would run. They uploaded the change to Mars, and the resets stopped.
Linux offers the same protection. Its locks for real-time work support priority inheritance, so a real-time thread waiting for a lock held by a normal thread lifts that thread up until the lock is free. The general lesson outlives Mars: priorities and locks interact in ways that are not obvious, and whenever a scheduler meets shared resources, look for a way for a low-priority holder to block a high-priority waiter.
What the interviewer will push on
"How does the Linux scheduler decide which thread runs next?" They are checking whether you know the idea behind CFS: every normal thread has a virtual runtime, the scheduler runs the one with the smallest, and the threads are kept in a red-black tree so finding the smallest is fast. A strong answer mentions that since Linux 6.6 the choice is made by EEVDF, which keeps the fair shares and adds deadlines for faster response.
"What does nice do, exactly?" The tell is saying it sets a weight, not a fixed rank: a nice-10 thread's vruntime grows about 9.3 times faster than a nice-0 thread's, so it gets about 10 % of a contested core. And it changes nothing when the machine is otherwise idle.
"Why might a sleeping thread not get a huge burst when it wakes?" Because the scheduler raises a waking thread's vruntime to near the current minimum. It gets to run soon, but cannot cash in credit for the time it slept.
"What is priority inversion and how is it fixed?" They want the three-thread story, ideally with Mars Pathfinder, and priority inheritance as the fix.
"My container uses only 30 % CPU on average, but has latency spikes every 100 ms. Why?" This is a senior question. The answer is cgroup CPU throttling: bursts use the whole quota early in a period, and every thread then waits for the next period.
Something to volunteer that nobody asks for: Linux keeps one run queue per core rather than one shared queue, so cores almost never wait for each other. The price is load balancing, and the scheduler moves threads reluctantly because each move leaves them with cold caches.
Recall
- Linux sorts threads into scheduling classes: deadline, then real-time, then normal, then idle. A class runs only when every class above it has nothing ready.
- Normal threads are shared fairly. The Completely Fair Scheduler tracks each thread's virtual runtime and always runs the smallest, keeping threads in a red-black tree. Waking threads are placed near the minimum so they respond fast without hogging. Since Linux 6.6, EEVDF chooses among eligible threads by earliest virtual deadline.
- The nice value (−20 highest to +19 lowest) sets a weight; vruntime grows by real time × 1024 ÷ weight. Nice 0 against nice 10 shares a contested core about 90 % to 10 %.
- Real-time threads (
SCHED_FIFO,SCHED_RR, priority 1–99) always beat normal threads; Linux caps them at 95 % of each second. Do not make ordinary services real-time. - Each core has its own run queue; load balancing moves threads reluctantly; CPU affinity pins them. Containers are limited by cgroup quotas and get throttled. Priority inversion is fixed by priority inheritance.
Self-test: Why does a nice-10 thread get about a tenth of a contested core? Why did nice -n 10 not slow the backup down at 3 a.m. when no uploads arrived? What does EEVDF add to CFS? Why can a buggy SCHED_FIFO thread not freeze a Linux machine completely? Tell the Mars Pathfinder story in three steps, and its fix.
Quiz Bank
FoundationalWhat does the nice value do, and which direction is higher priority?
The nice value is a number from −20 to +19 on every thread, defaulting to 0. A higher number means nicer to others, so lower priority: +19 is the lowest and −20 the highest. Any user may raise the nice value of their own processes; only the administrator may lower it below 0.
Under Linux's fair scheduler it sets a weight, about 1.25 times per step, so each step changes a thread's share of a contested core by about 10 %. It only matters when threads compete; a nice process on an idle machine still gets the whole core.
FoundationalWhy does Linux keep a separate run queue for each CPU core?
With one shared queue, every core would have to lock that queue each time it picked a thread, thousands of times a second, and the cores would spend their time waiting for each other. With one queue per core, each core chooses from its own queue without coordinating. The cost is that queues can become uneven, so the kernel runs load balancing periodically and when a core goes idle, moving threads from busy queues to idle ones. It moves them reluctantly, because a moved thread starts with cold caches.
AppliedA nice-0 thread and a nice-10 thread are both always runnable on one core. What share of the core does each get, and why?
Their weights are 1024 and 110. Each thread's vruntime grows by real time × 1024 ÷ its weight, so the nice-0 thread's vruntime grows at the speed of real time, and the nice-10 thread's grows about 9.3 times faster. Since the scheduler always runs the thread with the smaller vruntime, the nice-10 thread runs for 1 ms, jumps 9.3 ms ahead, and then the nice-0 thread runs for about 9 ms to catch up.
The shares are each weight divided by the total: 1024 ÷ 1134 ≈ 90.3 % and 110 ÷ 1134 ≈ 9.7 %.
InterviewWhat does Linux's fair scheduler do, and how does it choose the next task?
It gives every normal thread a fair share of CPU over time, weighted by its nice value. It tracks each thread's virtual runtime, the CPU it has received scaled by its weight, and runs the thread with the smallest. As that thread runs its vruntime rises until another is smaller, and the scheduler switches. Ready threads are kept in a red-black tree ordered by vruntime, so the smallest is found and threads are inserted in about \log_2 n steps.
A thread waking from sleep is placed near the current minimum vruntime, so it runs soon without claiming credit for the time it slept. Since Linux 6.6, the choice among threads is made by EEVDF. It keeps the same weighted fairness. Among the threads that have not exceeded their share, it picks the one with the earliest virtual deadline. That improves response for threads that need short, frequent turns.
InterviewDescribe priority inversion, why it is dangerous, and how it is fixed.
Priority inversion happens when a high-priority thread waits for a lock held by a low-priority thread, and a medium-priority thread that needs no lock keeps preempting the low-priority one. The low-priority thread cannot run to release the lock, so the high-priority thread is in effect blocked by the medium one.
It is dangerous in real-time systems because critical work can miss its deadline for as long as the medium work runs. It caused NASA's Mars Pathfinder to keep resetting in 1997. The fix is priority inheritance: a thread holding a lock temporarily takes the priority of the highest thread waiting for it, finishes quickly, releases the lock and drops back. An alternative is a priority ceiling, where taking a lock raises the holder to a preset high priority.
StaffA latency-sensitive service in a container averages 30 percent of its CPU limit but shows response-time spikes of tens of milliseconds at regular intervals. Explain the likely cause and options.
The likely cause is cgroup CPU throttling. A container's CPU limit is a quota per period, for example 200 ms of CPU per 100 ms period for "2 CPUs". The average over a minute can be low while short bursts are high: a burst of requests across many threads can use the entire quota in the first 20 ms of a period. The kernel then stops scheduling all of the container's threads until the next period, and every request in flight waits, producing regular spikes. The container's cgroup statistics show the number of throttled periods and the throttled time, which confirms it.
The options:
- Raise the limit, or remove it and rely on CPU requests for fair sharing.
- Reduce how many threads can burst at once. Size worker pools to the container's limit, not to the host's core count, which many runtimes detect wrongly.
- Smooth the work out over time.
Moving the service to a lower nice value would not help, because throttling is a quota on the whole group, not a contest within the normal class.
Scenario Drill
DrillThe thumbnail program and the upload service run on the same 4-core server. During a burst of uploads, thumbnails pile up and upload requests slow down. Using this page, design the scheduling setup.
First separate the two kinds of work by priority. Start the thumbnail program with a higher nice value, for example 10, using nice or os.setPriority. Whenever an upload thread and a thumbnail thread both want a core, the upload gets about 90 % of it, so requests stay fast. When uploads are quiet, thumbnails use all the spare CPU, so nothing is wasted.
Second, bound the thumbnail work. Give it a pool of about three threads on a 4-core machine, leaving one core's worth of room for the service, rather than one thread per photo. Optionally pin the thumbnail program to cores 1 to 3 with CPU affinity, so its caches stay warm and core 0 stays free for request handling.
Do not make the upload service real-time. It needs good response, not guaranteed deadlines, and a bug in a real-time service could starve logging and networking. If thumbnails still pile up, the honest conclusion is that four cores are not enough for the peak, and the fix is more machines or a separate thumbnail service, not cleverer scheduling.
Next: threads share memory, and this chapter kept warning that sharing is dangerous. 2.4.1 shows the danger at its smallest: two threads adding one to the same counter, and losing updates, because one line of code is really three CPU instructions.