The Runtime Theory
mediumApplicationDSA#operating-systems#scheduling#concurrency

How does the scheduler decide which thread runs next?

Tests whether you know a real scheduler, not 'the OS picks the highest priority'. A strong answer describes CFS-style runqueues, vruntime weighting, and wakeup preemption.

The Runtime Theory Team2 min readasked at google · reddit · netflix · apple

This question tests whether you understand the data structure, not the policy slogan. The interviewer wants the runqueue and the fairness mechanism — not "it runs the most important one."

The mental model: the scheduler only ever decides one thing: which runnable thread gets the CPU next. Runnable threads live on a per-CPU runqueue. Sleeping threads aren't on it at all. The decision is: pick the entry with the smallest vruntime.

Walk through the mechanism on Linux's CFS and its EEVDF evolution. Each thread accumulates vruntime — actual CPU time, scaled by the inverse of its weight, where weight comes from the nice value. A nice 0 thread gains vruntime at the wall-clock rate; a nice 5 (lower priority) thread gains it faster, so it sinks toward the back; a nice -20 thread gains it slower, so it keeps winning. The runqueue is kept sorted, so "next" is a lookup, not a scan.

When a thread's slice expires, the scheduler sets TIF_NEED_RESCHED and the actual switch happens at the next safe point — typically when returning from the timer interrupt or a syscall back to user mode. The slice isn't fixed: CFS derives it from a target latency (e.g. 6ms) divided by the number of runnable threads, so interactive threads get responsive turnarounds while the machine stays fair.

Preemption is not only tick-driven. When a thread becomes runnable — a mutex unlock, a socket receive, a timer expiry — the wakeup path (try_to_wake_up) enqueues it on a runqueue. If the new arrival is allowed to preempt (its vruntime is small enough, or it's a real-time thread), the current thread gets TIF_NEED_RESCHED immediately, and control switches on the way back to user mode. That's why wakeup latency, not tick length, is the real responsiveness measure.

Tradeoffs and edge cases worth naming:

  • Per-CPU runqueues keep the hot path lock-local; a periodic load balancer moves threads between CPUs, which costs cache warmth — so affinity (pinning) exists.
  • SMP: a thread's vruntime is normalized across CPUs; load balancing compares runqueue lengths and thread weights.
  • Real-time classes (SCHED_FIFO/RR) bypass the fairness machinery entirely — no vruntime, fixed priority order.
  • The idle task runs when the runqueue is empty and does the CPU's power management.

A strong closing line: the scheduler keeps runnable threads sorted by weighted CPU time, picks the least-served one, and preempts at safe return-to-user points — the entire discipline is "proportional progress."

This answer walks

Follow-ups they'll push on

  1. 01How does the nice value change how often a thread runs?
  2. 02When does preemption actually happen — at the tick, or somewhere else?
  3. 03What does a scheduler do when a thread blocks on I/O?

More interviews in this topic

hard · operating systemsExplain what happens when the system runs out of memorymedium · operating systemsHow do containers isolate processes without virtualization?medium · operating systemsWhat is a context switch and what does it cost?

One dispatch a week

The trace behind each question, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.