Expert · Module 27 · Lesson 3 of 5
Linux red-black trees
How the Linux run queue uses a cached red-black tree: weight-scaled virtual runtime that gives nice 5 its smaller share, the vruntime floor for new tasks, and what EEVDF changed in Linux 6.6.
By the end you can
- Explain how a cached red-black tree makes the scheduler's pick cheap and each switch O(log n)
- Predict how nice weights scale virtual runtime growth and the CPU share each task receives
- Describe what EEVDF changed in Linux 6.6 and which parts of the machinery stayed
Builds on Red-black trees.
01 · A question first
The Linux scheduler must always know which runnable task to run next, and it may not sort them to find out. CFS has answered with the leftmost node of a red-black tree whose nodes carry a weighted virtual clock: a nice 5 task's clock runs about three times faster, which is exactly how it loses. This lesson does that arithmetic on real kernel constants.
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- The pick that cannot sort
- Cached minima and other citizens
- The trace above: weights, not priorities
- The floor under new tasks
- What EEVDF changed
- What a switch costs
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem