Operating Systems Notes: Scheduling Tradeoffs

Why scheduling is a tradeoff, not a catalog

CPU scheduling looks like a catalog of named algorithms until you have to defend a choice in an interview or a design review. Round robin, priority queues, multilevel feedback: each one optimizes something and quietly taxes something else. The hard part is not remembering definitions. It is knowing which cost you are willing to pay for a given workload.

I used to memorize policies by name and hope the question mapped onto a flashcard. That fell apart the first time someone asked why a fair-looking round robin still felt laggy, or why a "fast" shortest-job approach could starve interactive work. The framing that stuck is simpler. Modern schedulers are balancing acts among three goals:

1. Throughput
2. Responsiveness
3. Fairness

When I evaluate a policy now, I start with the target workload first instead of picking an algorithm by name. The rest of this note expands that checklist and puts common policies next to the tradeoffs they force.

Throughput improves with longer time slices

Throughput is how much useful work the machine finishes per unit time. Useful work is code that advances a job. Everything else is overhead:

• Saving registers
• Switching address spaces
• Warming caches again
• Picking the next runnable task

That overhead is why longer time slices tend to raise throughput. If you let a CPU-bound job run for tens of milliseconds instead of a few hundred microseconds, you pay the context-switch tax less often and stay in a hot working set longer. Batch jobs finish more wall-clock work per second even if interactive clicks feel worse.

First-come, first-served (FCFS)

FCFS is the extreme version of this idea. A job runs until it blocks or exits. Context switches are rare, so for a stream of long CPU-bound tasks the machine can look very efficient.

• Benefit: High useful CPU utilization for batchy, long-running work.
• Cost: A short job stuck behind a long one. Average waiting time blows up, and the system feels stuck even though the CPU is busy doing "useful" work for someone else.

Shortest-job-first (SJF)

Non-preemptive SJF pushes the same idea harder: finish short work first so the queue clears faster on paper. Average turnaround often improves versus FCFS when lengths are known and batchy.

• Benefit: Better average turnaround when runtimes are predictable.
• Cost: You need good runtime estimates, and a steady trickle of short jobs can delay a long one forever if you ignore fairness.

Preemption vs throughput

Preemption does not automatically destroy throughput, but frequent preemption does. Every forced switch bets that responsiveness is worth the lost cycles.

When I hear "maximize throughput," I ask:

• Is the workload mostly long CPU bursts?
• How expensive is a context switch on this hardware?
• Are occasional long waits acceptable?

Batch analytics on quiet machines can live with longer slices. A shared laptop usually cannot treat raw throughput as the primary scoreboard.

Responsiveness improves with shorter time slices

Responsiveness is how quickly the system reacts when something becomes runnable: a keystroke handler, a UI thread, a short RPC on a busy host. Users experience this as latency, not as jobs completed per hour.

Shorter time slices help because a newly ready interactive task does not wait behind a full long burst. Preemptive schedulers make that possible. The timer interrupt fires, the running task is paused, and something else can run. Without preemption, a CPU hog can hold the core until it voluntarily yields, which is unacceptable for interactive systems.

Round robin

Round robin is the classic teaching example. Each runnable task gets a quantum, then goes to the back of the ready queue.

• Benefit: Simple fairness among CPU-bound peers, and bounded waiting when the quantum is reasonable.
• Cost: The quantum is easy to get wrong.

A tiny quantum feels snappy in theory but burns time in switches and cache misses, so everything feels busy but slow. A huge quantum starts to resemble FCFS: good throughput for long runners, sluggish response when many tasks share the CPU.

Preemptive priority

Preemptive priority scheduling goes further when you can label work correctly. A foreground UI at high priority preempts a background encode, and the click feels instant.

• Benefit: Targeted latency where it matters.
• Cost: Misuse. If too much work is marked "high," you recreate contention at the top. If low-priority work never runs, you have a fairness problem dressed up as performance.

Multilevel feedback queues (MLFQ)

MLFQ tries to learn the distinction instead of trusting static labels. Interactive-looking jobs get short slices; jobs that keep burning CPU sink to lower queues with longer slices.

• Benefit: A practical compromise without perfect priorities up front.
• Cost: More knobs: quantum lengths, demotion rules, and guards against gaming or oscillation.

When I hear "make it feel responsive," I ask:

• What is the p99 target?
• How bursty are arrivals?
• Can we preempt?

Short slices and preemption are tools, not free wins. The quantum should be small enough that interactive work gets on CPU soon, and large enough that we are not mostly scheduling ourselves.

Fairness requires explicit accounting

Fairness means runnable work gets a reasonable share of CPU over time, not that every task is equal in every instant. Without accounting, latency tricks become starvation, and "important" work crowds everything else out until averages look healthy and the tail looks broken.

Priority without aging

Priority scheduling without aging is the usual cautionary tale. High-priority tasks keep arriving, low-priority ones sit ready forever, and throughput still looks fine because the CPU never idles.

• Benefit: Predictable service for the top class.
• Cost: Unbounded wait for everyone else unless you boost neglected tasks over time.

Round robin and I/O-bound work

Round robin feels fair when tasks are similar and CPU-bound. It is less fair when I/O behavior differs.

An I/O-bound task may use only a fraction of its quantum, then wait a full rotation for another short burst. Pure RR does not fix that unless you add something like priority boosting after I/O completion, which real systems often do.

Share-based accounting

Share-based ideas (weighted fair queuing, lottery scheduling, or Linux CFS at a high level) make the accounting explicit. Each task or group gets a weight, and consumed CPU should track those weights over a window.

• Benefit: A vocabulary for multi-tenant fairness. Background jobs do not vanish, and noisy neighbors are limited by share.
• Cost: Complexity, and choosing the right unit. Fair among threads is not fair among users or containers. The wrong unit makes a fairness story that does not match the product.

When I hear "keep it fair," I ask:

• Fair among which entities?
• Over what time horizon?
• What starvation case do we refuse to accept?

Fairness almost never falls out of a latency optimization by accident. Measure who is runnable and not running, then put a rule in the policy that forces progress.

Putting the checklist against real policies

In practice I walk a policy through the three questions in order, then match it to the workload.

Workload examples

Compile farm / batch

I lean toward longer slices and less aggressive preemption. Throughput matters more than keystroke latency, and fairness may mean equal shares across tenants. FCFS or large-quantum RR can be enough; MLFQ is often optional complexity.

Desktop / latency-sensitive host

I want preemption and a bias toward short work: small RR quanta, priority for interactive classes, or MLFQ-style feedback. I accept more switch overhead for stable response times, then use accounting so background work still moves.

Mixed systems

Most of reality. Expect a hybrid: short slices near interactive work, longer slices for batch classes, and shares or aging so low priority cannot die quietly. Named algorithms are building blocks inside that story, not the story itself.

Side-by-side tradeoffs

Policy	Buys you	Costs you
FCFS	Throughput for long CPU-bound streams	Response time under varied job lengths
Round robin	Tunable middle ground	Tiny quantum burns overhead; huge quantum risks lag
Preemptive priority	Targeted latency when labels are honest	Starvation without aging or shares
SJF / SRTF	Better average turnaround with good estimates	Fairness and estimation risk when estimates are wrong
MLFQ	Blend of response and throughput	More knobs and failure modes

What I check in interviews

In study and interview prep, I keep the checklist close:

• Does this policy buy throughput with longer slices, and what waiting-time cost does that create?
• Does it buy responsiveness with shorter slices or preemption, and what switch overhead does that create?
• Does it buy fairness with real accounting, and which entity is the unit of fairness?

Start from the workload, name the metric you optimize first, then pick the algorithm that pays the costs you can live with.