skip to content

Why do preemptive schedulers give tasks a bounded time slice, and how do priorities interact with fairness when many tasks are runnable at once?

level: middleimportance: should knowfreq 42%

answer

  1. quantum: throughput vs waiting time
  2. target latency / N, floored by min granularity
  3. priority = who next, not how long
  4. strict priority starves; aging or shares fix it
  5. inversion: low holds lock, medium preempts, high waits

basics

~20 s

A time slice bounds how long one task can hold a core, trading throughput for responsiveness: long slices amortize switch cost, short slices cut waiting time for others. Priorities bias the choice of who runs next; strict priority can starve low-priority work, so schedulers add aging or proportional shares.

solid answer

~50 s

The time slice — the quantum — is the knob between two goals. A **long** quantum amortizes switch and cache re-warm cost over more useful work, maximizing throughput. A **short** quantum means every runnable task waits less before its turn, which lowers latency and makes the system feel responsive. Neither extreme is right, so schedulers pick a target latency and divide it among runnable tasks, shrinking the effective slice as more become runnable — with a floor, so switching does not consume the machine. **Priorities** answer *who next*, not *how long*. Strict priority is simple and predictable but starves the bottom: as long as a high-priority task is runnable, low-priority work never runs. Real schedulers soften this with **aging** (waiting raises effective priority) or by treating priority as a **share of CPU** rather than absolute precedence, so a low-priority task still progresses, just slowly. Priority also interacts badly with locks: a low-priority holder can block a high-priority waiter — priority inversion — which is why priority inheritance exists.

code

text · 10 lines
text
# each task accumulates virtual time as it runs
vruntime += actual_runtime / weight      # heavier weight -> slower accumulation

pick_next():
    return runnable task with smallest vruntime

slice(task) = max(target_latency * weight / total_weight, min_granularity)

# a neglected task's vruntime stays small, so it is chosen eventually:
# nothing starves, and weight buys proportional CPU, not absolute precedence

go deeper

for a junior

Explain the quantum as the limit on how long one task holds the CPU, and priority as who is picked next; name starvation as the risk of strict priority.

for a middle

Give the quantum tradeoff quantitatively (overhead versus worst-case wait), and contrast strict priority, aging and proportional shares.

for a senior

Discuss fairness hierarchies across groups, why priority is advisory, and priority inversion with inheritance or ceilings as the fix.

for a principal

Frame it as a service-level decision — target latency, weights per tenant or container, isolation of latency-critical from batch work — and argue that saturation problems are queueing problems, not priority problems.

## What the quantum is for In a preemptive system, the scheduler grants a running task a **time slice** (quantum). When it expires, a timer interrupt returns control to the scheduler, which may pick someone else. The quantum length is a direct tradeoff: - **Longer quantum** → fewer switches per second → less time in save/restore and, more importantly, less cache re-warming → higher throughput. But a task at the back of the queue waits up to (number of runnable tasks − 1) × quantum before it runs at all. - **Shorter quantum** → every runnable task gets a turn sooner → lower and more even latency, better interactivity. But switch overhead becomes a larger share of the machine, and at the extreme the system spends its time switching instead of computing. A useful way to see it: with N runnable tasks and quantum q, worst-case wait before your turn is about (N−1)·q, while overhead is roughly (switch cost)/(q + switch cost). You cannot minimize both; you choose a point. Modern schedulers usually express the choice as a **target latency**: "every runnable task should get the CPU within L". The slice becomes roughly L/N, shrinking as more tasks pile up — bounded below by a **minimum granularity** so that a hundred runnable tasks do not reduce slices to a switch's width. This is the general form of the idea; the specific implementation is an operating-system concern. ## Priorities: choosing who, not how long Priority orders the run queue. Three families are worth distinguishing: **Strict (fixed) priority.** Always run the highest-priority runnable task; equal priorities round-robin among themselves. Predictable and analyzable, which is why real-time systems use it — you can reason about worst-case response for the top tasks. Its flaw is **starvation**: lower-priority work runs only in the gaps, and if the top is always busy, there are no gaps. **Priority with aging.** A task's *effective* priority rises the longer it waits and falls while it runs. This preserves responsiveness for urgent work while guaranteeing that everyone eventually runs. Interactive tasks — which block often and use little CPU — naturally float up, while CPU-hungry batch tasks sink, which is exactly what a desktop or a mixed server workload wants. **Proportional share / weighted fair.** Priority becomes a **weight**: a task with weight 4 receives roughly four times the CPU of a task with weight 1 over any reasonable window. The scheduler tracks accumulated service (often as a virtual time that advances faster for lighter-weight tasks) and always runs whoever is furthest behind their entitlement. Nothing starves — the neglected task's deficit keeps growing until it is chosen. This is the model behind most general-purpose schedulers and behind container CPU shares. ## Fairness of what, exactly? "Fair" needs a subject. Equal CPU time per *thread* means a process with 100 threads takes 100 times the CPU of a single-threaded one. So schedulers commonly apply the fairness rule hierarchically — fair among groups (users, containers, cgroups), then fair within each group. The lesson for design: creating more threads is not a legitimate way to obtain more CPU, and if it is on your platform, that is a fairness bug in the configuration. ## Priority inversion Priorities interact badly with mutual exclusion. A low-priority task holds a lock; a high-priority task needs it and blocks; a medium-priority task, which needs nothing, preempts the low-priority holder. Now the high-priority task waits behind a medium-priority task indefinitely, its priority effectively inverted. Standard remedies: - **Priority inheritance**: while holding a lock a task temporarily inherits the highest priority among its waiters, so it is scheduled promptly and releases quickly. - **Priority ceiling**: a lock carries a priority; acquiring it raises the holder to that level immediately. - **Avoidance**: do not share locks across widely different priority bands; use lock-free structures or message passing at those boundaries. ## Practical consequences - **Do not reach for priority to fix throughput problems.** Priority redistributes a fixed resource; if the machine is saturated, raising one task's priority just moves the pain, and can starve something you needed. - **Expect priority to be advisory.** Its meaning varies by platform and is often weak or ignored, so building correctness on relative priorities is fragile. Design for correctness under any interleaving and use priority only as a performance hint. - **A latency problem is often a queueing problem.** If a task waits too long, the fix is usually fewer runnable tasks or less work per task, not a nudge to the priority number. - **Watch the interaction with lock hold times.** Long critical sections plus priority differences is where inversion bites; shortening the critical section fixes more than tuning priorities.

  • What goes wrong if the time slice is made very small in the name of responsiveness?
    Switch overhead becomes a growing share of every slice — not just the register save/restore, but cache and branch-predictor re-warming that may not even complete before the next preemption. Throughput drops and, past a point, latency worsens too because useful work per unit time collapses. That is why schedulers enforce a minimum granularity under load.
  • Describe priority inversion and one standard fix.
    A high-priority task blocks on a lock held by a low-priority task, and a medium-priority task that needs no lock preempts the holder — so the high-priority task waits behind medium-priority work indefinitely. Priority inheritance fixes it by temporarily raising the lock holder to the highest priority among its waiters, so it runs, finishes and releases. Priority ceilings do the same preemptively by attaching a level to the lock.
  • A team proposes raising their service's thread priority to fix latency on a saturated machine. What is your response?
    Priority redistributes a fixed amount of CPU; it does not create any. On a saturated machine the gain comes directly out of whatever loses, which may be something that service depends on. The better lever is reducing runnable work — fewer threads, less CPU per request, or more capacity — and priority meaning is platform-dependent enough that correctness should never rest on it.

A quantum is how long each speaker gets before the moderator moves on: long turns waste less time on handovers, short turns mean nobody waits an hour to be heard. Priority is who the moderator calls first — and without a rule that waiting raises your chance, the quiet ones never speak.

saying these in an interview costs you the question

  • Treating higher priority as more CPU capacity rather than a redistribution of a fixed resource.
  • Believing strict priority scheduling cannot starve lower-priority work.
  • Thinking priority controls the length of a time slice rather than the order of selection.
  • Assuming fairness is per-thread, so spawning more threads legitimately earns more CPU.
  • Relying on priority ordering for correctness instead of treating it as an advisory performance hint.

context

resolving links…