Scheduling Fairness from CPUs to Load Balancers

By the end of this lesson, you will be able to...

• Define a CPU-scheduling promise in terms of response, progress, or share instead of vague fairness.

• Compare FIFO, short time slices, and priority with a trace of runnable tasks.

• Recognize starvation, convoying, and overload from queue and latency evidence, then transfer the model carefully to a worker dispatcher.

Idea in one sentence: A scheduler cannot make scarce CPU time fair in every sense; it must choose whose waiting, progress, or share it will protect.

Core Insight

Imagine a laptop with one busy CPU core. Two kinds of work want it:

• an editor is processing keystrokes and should feel responsive;
• a build is compiling many files and should make steady progress.

At 10:00:00, a compiler thread begins a long CPU-bound phase. A moment later the editor becomes runnable after a keystroke. If the compiler keeps the CPU until it voluntarily stops, the editor waits even though its next step is tiny. The machine is not broken. It has a policy problem: it must decide which runnable thread gets the scarce execution resource next.

It is tempting to call any scheme that gives each thread a turn “fair.” That works only if the promise is equal turns. A user may instead need low response time. The build may instead need guaranteed progress. A service host may need one group of tasks not to consume all CPU. Those promises can conflict.

The useful question is therefore not “which scheduler is fairest?” It is: what outcome must this host protect, what work is eligible to run, and what evidence would show the promise is failing? The trade-off is unavoidable: protecting one kind of waiting can reduce another kind of progress.

The Boundary: Runnable Is Not the Same as Existing

The scheduler does not choose among every process on a machine. It chooses among work that can use a CPU now. A thread waiting for disk I/O, a lock, a timer, or a network reply is not currently runnable in the same sense as the editor and compiler. It must first be woken by the condition it needs.

In plain English:

A CPU scheduler decides who gets the next piece of execution time among work that is ready to execute.

In our situation:

The editor thread and compiler thread are runnable. A third thread waiting for a file read is blocked, so giving it a CPU would not make the read finish.

Technical name:

The run queue is the scheduler's working set of runnable tasks. Scheduling is a policy for selecting from that set; it is not a cure for I/O waits, lock contention, or memory pressure.

Linux documents the scheduler as the kernel component that selects which runnable thread executes next. Its available policies and exact implementation are operating-system-specific. The traces below are a teaching model, not a claim that every Linux version or operating system stores queues in exactly this form.

This boundary matters for diagnosis. If the editor is slow while the CPU is mostly idle and its thread is blocked on I/O, changing CPU fairness may do nothing. If several tasks are runnable and the core is saturated, queueing and policy become plausible explanations.

The Naive Design: Let the Current Task Finish

The simplest policy is effectively first-come, first-served: run the current CPU-bound task until it blocks, exits, or yields. It has an attractive property. There is little switching overhead, and a long calculation gets uninterrupted cache-friendly execution.

It also creates a visible failure.

time        runnable tasks              CPU runs          editor result
10:00.000   compiler                    compiler          --
10:00.005   compiler, editor             compiler          key waits
10:00.050   compiler, editor             compiler          key still waits
10:00.120   editor                       editor            character appears

The illustrative 115 ms wait is not caused by the editor needing 115 ms of CPU. It needs perhaps a few milliseconds after it is selected. It waits because the policy let an earlier task occupy the resource without a bound.

This pattern is called a convoy: short or interactive work queues behind long work. FIFO is reasonable when jobs have similar duration and response time is unimportant. It becomes a poor fit when a small urgent action can arrive behind a long CPU-bound one.

Three Designs, Three Different Promises

Before choosing an algorithm, state the promise. The same host cannot optimize every column at once.

The table is deliberately about promises, not brand names. Linux exposes normal, real-time, and deadline scheduling policies; for example, SCHED_RR gives a runnable real-time thread a bounded quantum before it goes to the end of its equal-priority queue. A general lesson about fairness should not assume that a policy name means the same behavior across all operating systems or deployment settings.

A Worked Trace: Protect Response Without Losing Build Progress

Return to one CPU core. The following numbers are illustrative. Each small time slice is 4 ms; the real quantum is implementation-dependent.

tasks
  E = editor: needs 2 ms of CPU after each keystroke
  B = build: needs 40 ms of CPU in total

at t=0 ms:    B is runnable
at t=5 ms:    E becomes runnable
at t=17 ms:   E becomes runnable again

With run-to-completion, B may consume all 40 ms before E first runs. E's first action completes at about 42 ms. B finishes early, but the human-facing work waits a long time.

With equal round-robin slices, the scheduler can make the following choices:

The ordering inside a real scheduler is more nuanced than this toy trace. The point is visible: a bounded turn converts unbounded waiting into a policy-controlled delay. The build still progresses, but it periodically gives the CPU back to the scheduling decision.

Now add a third task, A, a background analytics job. Suppose the host uses strict priority: editor work is high priority, build work is normal, analytics is low. At a quiet moment, A runs. During a sustained stream of editor activity, A can repeatedly lose. That is starvation: a task remains runnable but receives no useful service because more preferred work is always available.

The correction is not automatically “remove priority.” The host may genuinely need to protect responsiveness. It needs a progress rule as well: a bounded share, aging for old waiting work, a quota, or a separate resource group. Which is appropriate depends on the promise. A developer build and desktop editor may share a machine differently from a media pipeline with deadline requirements.

So far, we have separated three outcomes that everyday speech often merges into fairness: equal turns, low response time, and eventual progress. A good design names the one it protects and measures the other two for unacceptable harm.

What Fairness Can and Cannot Repair

Scheduling only allocates CPU time that actually exists. It does not create capacity and it does not make a blocked task runnable.

Consider these two observations:

case A: CPU is 98% busy; several tasks are runnable; editor latency rises
case B: CPU is 15% busy; editor thread is waiting for storage I/O; latency rises

Case A supports investigating competition on the run queue: too much CPU demand, an unsuitable priority, or an unfair group share. Case B points first toward the I/O and memory path from the previous lesson. The same symptom, slow interaction, can have a different resource cause.

Likewise, a “fair” share can still be unacceptable. Giving a video encoder and a control loop half the CPU each may be equal by allocation, but the control loop may miss a required response deadline. Conversely, allowing an urgent task to preempt everything can keep it responsive while leaving batch work with an unbounded backlog.

The design review therefore needs two kinds of limits:

• admission or capacity limits: do not promise more CPU work than the host can complete in the required time;
• progress limits: do not let a high-priority or noisy workload consume all available execution indefinitely.

Linux's deadline policy illustrates why this distinction matters: it uses runtime, deadline, and period parameters and performs an admission check rather than treating a deadline as a wish. The implementation details are outside this track; the transferable point is that a guarantee must be matched to measured capacity.

Signals That Test the Scheduling Story

Do not diagnose a fairness failure from CPU percentage alone. Start with a claim and collect evidence that can reject it.

Metrics and names vary by system. The reasoning does not: distinguish demand, runnable delay, actual CPU time, and time blocked on another resource. If every class is growing a queue, a more clever picker cannot substitute for admission control, shedding work, adding capacity, or changing the work itself.

A Controlled Transfer: From a CPU Run Queue to a Worker Dispatcher

A load balancer or worker dispatcher also chooses where the next unit of work goes. That is a useful analogy, but it is not the same mechanism. A CPU scheduler selects runnable threads on one host; a dispatcher may make decisions with delayed load reports, variable service times, network failure, and several independent queues.

The transfer works at the policy level:

CPU scheduler:     choose a runnable thread for scarce CPU time
worker dispatcher: choose a destination for scarce worker capacity

Round-robin distribution can look equal while a slow worker has a long queue. Strict priority can protect checkout requests while starving exports. A queue-aware dispatcher can reduce visible waiting, but stale observations can make many dispatchers choose the same apparently empty worker.

Use the analogy to ask better questions: Which work is eligible? What resource is scarce? Which outcome is protected? How is progress guaranteed? Then return to the actual boundary. Network retries, worker health, and distributed queue coordination belong to a systems-design or distributed-systems investigation; they are not hidden details of CPU scheduling.

Check Your Understanding

Check: A host is 95% CPU busy. An interactive process and a batch process are both runnable. The interactive process gets a small CPU burst every 200 ms, and the batch process otherwise runs continuously. Is the policy fair?

Think first, then reveal.

Answer: It is fair only relative to a stated promise. It may provide good batch throughput and some interactive progress, but 200 ms may be an unacceptable response bound for the interactive task. Measure response latency and the batch's completion rate; equal existence on the run queue is not enough.

Check: A low-priority report job has waited ten minutes, but its thread is blocked on a database reply for nine of those minutes. Is this evidence of CPU starvation?

Think first, then reveal.

Answer: Not by itself. Starvation concerns runnable work that keeps losing CPU service. First separate the one minute of runnable delay from the nine minutes blocked on the external condition.

Practice: Write a Scheduling Promise

A CI host runs interactive deployment checks and long test suites on four CPU cores. During busy periods, deployment checks must begin within 150 ms, while test suites may finish later but must not stop progressing for an hour.

Propose a scheduling promise and the smallest evidence set you would inspect. Do not choose a Linux policy name; describe the outcome first.

A good answer should mention:

• a protected response bound for deployment checks and a progress bound or share for tests;
• the fact that the promise applies when these tasks are runnable, not while they wait on I/O or locks;
• response latency, runnable delay or queue pressure, CPU time by class, and test backlog or age;
• what you would do if all classes are already accumulating delay because the host has insufficient capacity.

Resources

• [ARTICLE] sched(7): overview of CPU scheduling — Focus: Read the distinction between runnable threads, policies, priorities, round-robin quanta, and deadline admission.
• [ARTICLE] Linux scheduler nice design — Focus: See why scheduler weights and interactive behavior are policy choices rather than a single universal fairness measure.
• [BOOK] Operating Systems: Three Easy Pieces, CPU Scheduling — Focus: Compare response time, turnaround time, round-robin, and the convoy effect with small traces.
• [ARTICLE] Control Group v2: CPU controller — Focus: Connect fairness claims to resource groups and their configured CPU weights or limits.

Key Takeaways

• A scheduler chooses among runnable work; it cannot directly repair a task blocked on I/O, a lock, or a remote dependency.
• “Fair” must name a protected result such as response time, recurring progress, or a CPU share.
• Time slices reduce unbounded waiting, while strict priority can create starvation unless the design also preserves progress.
• Diagnose with runnable delay, CPU time, response latency, and backlog or age—not CPU percentage alone.
• A worker dispatcher shares the policy shape of scheduling, but its networked and distributed failure modes are a separate boundary.