Wait, What?
A CPU scheduler is solving an optimisation problem whose inputs keep changing while the algorithm is running.
At any instant there may be interactive tasks waiting for fast response, batch jobs needing throughput, background work that should not starve, real-time tasks with deadlines and multiple CPU cores with uneven load. The scheduler cannot know the future perfectly, so it combines measurable state, policy and prediction.
This makes scheduling one of the best topics for learning professional algorithm judgement: the “best” algorithm changes when the objective changes.
Quick Answer
Learn CPU scheduling through the route ready/running/blocked states → workload traces → turnaround/response/waiting time → FCFS → SJF → shortest remaining time → Round Robin → quantum trade-offs → priority scheduling → starvation/aging → MLFQ → fairness → virtual runtime → CFS → lag and virtual deadlines → EEVDF → real-time EDF → multicore load balancing → measurement and tail latency. A beginner should be able to draw a Gantt chart and compute response and turnaround time. A professional should be able to identify the workload objective, explain preemption costs, reproduce starvation and fairness cases, and evaluate a modern scheduler using latency distributions rather than one average.
1. Begin With Process States
A runnable task is not necessarily running. A task can be ready for CPU time, currently executing, blocked on I/O or sleeping. Scheduling chooses among runnable tasks; I/O completion and wakeups continuously change the candidate set.
2. Define the Metrics Before Choosing the Algorithm
- Turnaround time: completion time minus arrival time.
- Response time: time from arrival to the task’s first run.
- Waiting time: time spent ready but not running.
- Throughput: jobs completed per unit time.
- Fairness: how CPU service is distributed across competing tasks.
- Deadline success: whether time-constrained work completes within its requirement.
3. FCFS Is Simple—and Teaches the Convoy Effect
First-Come, First-Served runs jobs in arrival order. It is easy to implement and explain, but one long CPU-bound task can force many short jobs to wait behind it. The resulting convoy effect shows why fairness of arrival order is not the same as good response time.
4. SJF Optimises a Metric Under an Unrealistic Oracle
Shortest Job First can minimise average turnaround under strong assumptions when job lengths are known. The problem is that a general-purpose operating system usually does not know future CPU demand exactly. This gap between theoretical optimum and missing information motivates predictive schedulers.
5. Preemption Changes the Problem
Shortest-Remaining-Time variants allow a newly arrived short job to preempt a longer running job. This can improve response and turnaround for short work but increases context switching and can postpone long tasks.
6. Round Robin Shares Time
Round Robin gives each runnable task a quantum, then rotates it to the back of the queue if it still needs CPU time. It is a foundational time-sharing algorithm because it makes the trade-off between response and switching overhead visible.
7. Quantum Size Is a Systems Parameter
A very large quantum approaches FCFS behaviour. A very small quantum improves responsiveness in the abstract but can waste time on context switches, cache disruption and scheduler overhead. The right quantum depends on hardware and workload.
8. Priority Scheduling Introduces Starvation
If high-priority work continually arrives, low-priority work may never run. Aging or dynamic priority adjustment can restore progress. This is a recurring algorithm design lesson: every ordering rule should be tested against adversarial or skewed arrivals.
9. MLFQ Tries to Infer Behaviour From History
Multi-Level Feedback Queue uses multiple priority queues and changes a task’s priority according to observed CPU behaviour. Interactive or I/O-bound jobs can receive fast service, while long CPU-bound jobs migrate downward.
Operating Systems: Three Easy Pieces gives a detailed treatment of MLFQ, including starvation and scheduler-gaming failure modes. See OSTEP: Multi-Level Feedback Queue.
10. MLFQ Rules Are Policy, Not Natural Law
Different MLFQ designs choose different queue counts, time slices, allotments, boost intervals and I/O accounting. Students should stop asking “what is the MLFQ algorithm?” as though there were only one immutable parameter set.
11. Workload Prediction Can Be Useful Without Being Perfect
Schedulers often infer likely near-future behaviour from past CPU bursts, sleep patterns or task class. The general principle is to make prediction error visible and to avoid a policy that catastrophically punishes tasks when the prediction is wrong.
12. CFS Reframed Fairness Around Virtual Runtime
Linux’s Completely Fair Scheduler historically approximated an ideal processor that shares service among runnable tasks. It tracked per-task virtual runtime and selected work that had received less normalised service.
The Linux kernel’s current CFS design documentation explains this virtual-runtime model and notes that CFS is making room for EEVDF. See Linux Kernel: CFS Scheduler.
13. Data Structures Matter at Scheduler Scale
CFS used a time-ordered red-black tree for runnable entities, letting the scheduler efficiently choose the leftmost task by virtual runtime. The scheduler is therefore both a policy and a data-structure problem.
14. EEVDF Adds Eligibility, Lag and Virtual Deadlines
Linux has transitioned its fair-class scheduling toward Earliest Eligible Virtual Deadline First (EEVDF). The kernel documentation describes a lag value representing whether a task is owed CPU time; eligible tasks receive virtual deadlines, and the earliest virtual deadline is selected.
See Linux Kernel: EEVDF Scheduler.
15. Fairness and Latency Are Coupled
Giving every task identical treatment is not always experienced as fair. Latency-sensitive work may need shorter service quanta or earlier opportunities while CPU-bound jobs need protection from starvation. Modern schedulers encode this tension rather than choosing a single scalar objective.
16. Sleeping Tasks Are a Hard Edge Case
A task that sleeps frequently should not be able to manipulate accounting simply by leaving and re-entering the run queue. The current EEVDF documentation discusses lag handling for sleeping tasks, including deferred-dequeue behaviour and lag decay.
17. Real-Time Scheduling Is a Different Contract
General-purpose fairness asks who should run next for good overall service. Real-time scheduling asks whether tasks with runtime, period and deadline requirements can be admitted and scheduled without missing deadlines.
18. EDF Makes Deadlines the Ordering Key
Earliest Deadline First selects the ready job with the earliest deadline. Under its assumptions, EDF has strong schedulability properties, but real systems must combine it with admission control and bandwidth isolation.
Linux’s SCHED_DEADLINE documentation describes EDF augmented with Constant Bandwidth Server mechanisms and runtime/period/deadline parameters.
19. Multicore Scheduling Adds Placement
With multiple CPUs, the system must decide not only which task runs next but also where it runs. Migration can improve load balance yet damage cache locality. NUMA systems add memory-placement effects.
20. Affinity Can Be Performance-Relevant
Keeping a task on the same CPU can preserve warm caches, while moving it can relieve imbalance. Professional scheduler evaluation therefore considers both dispatch policy and placement policy.
21. Context Switching Is Not Free
A scheduling simulation that charges zero cost for preemption can choose unrealistically tiny quanta. Include dispatch overhead, cache effects and migration penalties when moving from classroom model to systems experiment.
22. Create a Workload Trace Before Writing Code
Use five jobs with arrival times, CPU bursts and I/O events. Draw FCFS, SJF/SRTF and Round Robin timelines. Compute response and turnaround. Then add one long job and a stream of short arrivals to expose starvation/fairness differences.
23. Simulate Before Touching Kernel Configuration
A discrete-event simulator is a safer learning environment than changing a live machine’s scheduler. Model arrival, dispatch, preemption, block, wakeup and completion events. Validate the simulator with tiny schedules that can be solved by hand.
24. Measure Distributions, Not One Average
Record p50, p95 and p99 response/latency, throughput, context-switch rate, CPU utilisation, run-queue length, migrations and starvation/max-wait cases. A policy with a slightly better mean but extreme tail delays may be unacceptable for interactive systems.
25. Common Learning Failure States
- Choosing an algorithm before defining the objective.
- Assuming job length is known in advance.
- Calling Round Robin fair without considering weights or blocked tasks.
- Ignoring context-switch cost.
- Treating MLFQ as one fixed parameter set.
- Confusing priority with deadline.
- Assuming CFS and EEVDF are simple textbook Round Robin variants.
- Benchmarking only CPU-bound jobs.
- Ignoring multicore placement and cache affinity.
- Tuning a live production scheduler before building a controlled model.
26. A Beginner-to-Professional Learning Ladder
- Level 1: draw process-state transitions and FCFS timelines.
- Level 2: compute waiting, response and turnaround.
- Level 3: trace SJF/SRTF and Round Robin.
- Level 4: demonstrate starvation and aging.
- Level 5: simulate MLFQ and explain every priority change.
- Level 6: implement a discrete-event scheduler simulator.
- Level 7: study virtual runtime and CFS data structures.
- Level 8: trace EEVDF eligibility, lag and virtual deadlines.
- Level 9: add multicore placement, migration and affinity costs.
- Level 10: evaluate a scheduler under interactive, batch, mixed and adversarial workloads.
27. Teach With Prediction, Not Only Timelines
Before revealing the next scheduled task, ask the learner to predict it and justify the metric or invariant used. Then run the simulation, investigate the result, modify a quantum or priority rule, and create a workload designed to break the policy.
This Predict–Run–Investigate–Modify–Make sequence aligns with PRIMM, a structured programming-pedagogy approach designed to move learners from reading and reasoning toward independent creation.
28. Use Subgoal Labels for Scheduler Simulations
Label a scheduling step as update arrivals → update runnable set → apply policy → dispatch/preempt → advance time → account service → process block/wakeup/completion → collect metrics. This makes the hidden state transitions explicit for novices.
Research on subgoal-labelled worked examples reports improved programming problem-solving and reduced failure/withdrawal in introductory contexts. See Margulieux, Morrison & Decker (2020).
29. Connect to Existing eduKateSengkang Algorithm Work
Use Load-Balancing Algorithms for distributing requests across servers and Cache-Replacement Algorithms for choosing which resident item to evict. CPU scheduling owns a different decision: which runnable task receives processor service next, for how long and on which CPU.
30. Current Professional Direction
Linux now also exposes sched_ext, an extensible scheduler class whose behaviour can be defined with BPF programs, making scheduler experimentation more accessible while retaining fallback safety. Advanced study includes EEVDF internals, real-time scheduling, CBS, NUMA balancing, energy-aware scheduling, heterogeneous cores, cgroup weights, scheduler tracing and formal schedulability analysis. The governing question remains: who runs next, what objective justifies that choice, and what happens to everyone who was not chosen?
31. Scheduler Evaluation Needs Workload Families
Test at least four families: CPU-bound batch work, interactive short-burst work, I/O-heavy work and mixed/adversarial arrivals. Add a bursty overload case. A scheduler that looks excellent on identical CPU-bound tasks may perform poorly when wakeups, blocking and latency-sensitive threads dominate. Report the workload generator alongside the results so a benchmark can be reproduced.
32. Fairness Needs a Defined Unit
Is fairness equal CPU time, weighted CPU share, equal slowdown, bounded waiting or deadline satisfaction? These are different objectives. CFS-style virtual runtime and EEVDF-style lag/deadline mechanisms encode particular notions of service fairness. Before saying a scheduler is unfair, state the service entitlement and time horizon over which fairness is being measured.
33. Energy and Heterogeneous Cores Complicate “Run the Next Task”
Modern systems may have cores with different performance/efficiency characteristics and power states. Placement can affect energy use, thermal headroom and completion time. The scheduling problem therefore extends beyond ordering a single run queue. A professional model should separate local dispatch from load balancing, affinity, capacity awareness and energy policy.
34. A Professional Exercise: Reproduce a Tail-Latency Regression
Build a simulator with one long CPU-bound task and periodic latency-sensitive tasks. Compare FCFS, Round Robin, MLFQ and a simplified fair/deadline model. Keep average CPU utilisation similar while varying quantum or service entitlement. Plot p50 and p99 response time. The exercise shows why an average can remain stable while user-visible responsiveness degrades sharply.
35. Final Learning Check
Without notes, explain the convoy effect, the SJF oracle problem, the Round Robin quantum trade-off, MLFQ starvation/gaming, CFS virtual runtime, EEVDF lag and virtual deadlines, and why multicore migration can hurt even when it improves balance. If the explanations do not mention a metric or workload, they are not yet professional explanations.
eduKate Sengkang 