Operating Systems · Cluster
Scheduling
Policy, fairness, and latency under load.
- 01 Run Queues and the Cost of a Context Switch How the kernel tracks which threads can run, why each CPU keeps its own queue, and what a switch actually costs beyond saving and restoring registers.
- 02 Tick Accounting and How a Slice Is Measured Timer interrupts, sampled versus switch-time accounting, and why the kernel charges time at coarse granularity to the thread that happened to be running.
- 03 Multi-Level Feedback Queues and Priority Decay How a set of priority queues plus a demotion rule approximates shortest-job-first without knowing job lengths, and the gaming and starvation problems that follow.
- 04 Virtual Runtime and Weighted Fair Queuing Why fair schedulers compare virtual clocks rather than wall time, how nice values become weights, and what granularity does to the fairness guarantee.
- 05 Load Balancing and Thread Migration on Symmetric Multiprocessors How per-CPU run queues are kept in balance without a global lock, when a thread is worth moving, and why affinity and NUMA topology constrain the answer.
- 06 Priority Inversion and Inheritance How a low-priority lock holder can stall a high-priority thread, why inheritance repairs the ordering, and what it costs in unlock complexity and chained blocking.
- 07 POSIX Real-Time Priority Classes and the Bandwidth Cap What SCHED_FIFO and SCHED_RR actually guarantee, why an unprivileged process cannot use them freely, and how a runtime cap keeps a runaway real-time thread from hanging the machine.
- 08 EDF, Utilization Bounds, and Schedulability Tests Why earliest-deadline-first reaches full utilization on one CPU, how the density test differs from the utilization test, and what breaks when deadlines exceed periods.
- 09 Hierarchical Fair Share and Lag Accounting How group scheduling keeps one container from multiplying its share by spawning threads, what lag measures, and why the bound is per-level rather than global.
- 10 Deadline Servers and Admission Control How a constant-bandwidth server gives any thread a deadline without trusting its behaviour, and why the admission test is what turns a priority into a guarantee.