CPU Scheduling
1. Overview
A. Definition
CPU scheduling is a core operating-system resource-management technique that selects which one of the many ready-state processes/threads will occupy the CPU next, after which the dispatcher actually performs a context switch and hands over the flow of execution.
The fundamental reason modern operating systems employ CPU scheduling is multiprogramming. A single CPU can execute only one instruction at any instant, yet a process repeatedly stops during execution to issue I/O requests. If the CPU sits idle alongside a process while it waits for a disk response, this expensive compute resource is wasted. The scheduler catches these waiting intervals and hands the CPU to another ready process, so that to the user it appears as though several tasks run simultaneously, and overall throughput rises.
B. Background and Necessity
In the early batch era, jobs were run one at a time to completion in submission order, so there was effectively nothing to call scheduling. But with the arrival of time-sharing systems, many users came to share a single CPU, and problems such as "a short job trapped endlessly behind a long one" and "an interactive job that does not respond instantly" came to the fore. CPU scheduling evolved as the answer to the question of how to distribute a limited processing resource fairly and efficiently among many competing jobs. Today, from smartphones to large-scale servers and real-time controllers, in environments that simultaneously demand responsiveness, fairness, and power efficiency, the quality of the scheduler is a decisive factor governing the perceived performance of the system.
The premise that makes CPU scheduling effective is the alternation of CPU bursts and I/O bursts. Program execution alternates between "intervals that use the CPU (computation)" and "intervals that wait on I/O"; when compute-centric (CPU-bound) jobs and input/output-centric (I/O-bound) jobs are mixed and the scheduler interleaves them well, the CPU and the I/O devices stay busy at the same time, maximizing resource utilization. Good scheduling is therefore not merely a matter of "who goes first" but of reading the nature of jobs to maximize parallelism across devices.
C. Characteristics of CPU Scheduling
CPU scheduling has several intrinsic characteristics. First, frequency: the short-term scheduler is invoked every few milliseconds, so the selection algorithm itself must be lightweight, and a high selection cost becomes overhead in its own right (which is why Linux CFS also uses an O(log n) data structure). Second, unforgiving resource allocation: the CPU can be occupied by only one at a time, so a choice means waiting for everyone else. Third, predictive uncertainty: the next CPU-burst length or the timing of I/O cannot be known exactly, so estimation and adaptation based on past behavior are unavoidable. Fourth, separation of policy and mechanism: "whom to choose (policy)" and "how to switch context (dispatcher mechanism)" are designed separately, so that diverse policies can be swapped on top of the same substrate.
2. Process State Transitions and Scheduling Tiers
A process moves through various states from creation to termination, and scheduling intervenes precisely at certain junctures of these state transitions. Below is the typical five-state model.
stateDiagram-v2
[*] --> New
New --> Ready: "admit"
Ready --> Running: "dispatch(scheduler)"
Running --> Ready: "preempt(time-out/preempt)"
Running --> Waiting: "I/O-event wait"
Waiting --> Ready: "I/O completion"
Running --> Terminated: "exit"
Terminated --> [*]
Here, whether the Running→Ready (preemption) transition is possible is what distinguishes the character of a scheduling policy. If preemption is allowed, even a running process can have the CPU taken away by a more urgent job or by the expiry of its time slice; if not allowed, it holds the CPU until it voluntarily issues I/O or terminates. Also, the moment just after a Waiting→Ready transition becomes an important decision point for giving I/O-centric jobs another opportunity.
Scheduling is divided into three tiers by time scale. The structure diagram below shows the role and position of each scheduler.
flowchart LR
J["job queue(new)"] -->|"long-term scheduler<br/>sets degree of multiprogramming"| R["ready queue(ready)"]
R -->|"short-term scheduler<br/>millisecond-scale selection"| D["dispatcher"]
D --> C["CPU execution(running)"]
C -->|"I/O request"| W["wait queue(waiting)"]
W -->|"completion"| R
C -.->|"swap out"| M["medium-term scheduler<br/>regulates memory overload"]
M -.->|"swap in"| R
The dispatcher performs the following steps in sequence right after selection, and the time this whole process takes is the dispatch latency.
- Context save/restore: save the registers and PC of the departing process into its PCB, and load the state of the incoming process.
- Mode switch: switch from kernel mode to user mode.
- Address-space switch: replace the page table and TLB with those of the new process (virtual-address protection).
- Jump: branch to the restored program-counter location and resume user code.
The long-term scheduler decides which jobs to bring into memory and activate, thereby regulating the degree of multiprogramming, while the medium-term scheduler smooths load by swapping some processes out to disk under memory pressure and bringing them back later. What we usually call "CPU scheduling" is the short-term scheduler, which runs most frequently on a millisecond scale, and the role of actually switching context to the selected process falls to the dispatcher. The time the dispatcher consumes is called the dispatch latency, and if this overhead is large, scheduling more often becomes a net loss, which ties it directly to time-slice design.
3. Scheduling Performance Criteria and Preemption
The key point is that the metrics used to evaluate a scheduler are in trade-off with one another. The representative indicators are as follows.
- CPU utilization: the fraction of time the CPU works without idling. Higher is better.
- Throughput: the number of jobs completed per unit time. Batch-processing servers prize this.
- Turnaround time: the total time from job submission to completion.
- Waiting time: the sum of time spent waiting in the ready queue. This is the quantity the scheduler can directly reduce.
- Response time: the time until the first response appears after a request. This is central to interactive and real-time systems.
If a long time slice is used to raise throughput, context-switch overhead falls but responsiveness worsens; conversely, if slices are cut short, interactive response speeds up but switching cost grows and utilization falls. Therefore which metric is treated as the top priority is itself the choice of policy: a general-purpose OS seeks a balance among several metrics, while a real-time system gives absolute priority to meeting deadlines. Mapping the priority of each metric to system types gives the following.
| System Type | Top Metric | Representative Policy |
|---|---|---|
| Batch-processing server | throughput/utilization | SJF approximation |
| Time-sharing/interactive | response time | RR/MLFQ |
| Real-time control | deadline adherence | EDF/RMS |
| Mobile device | responsiveness/power efficiency | EAS-coupled scheduler |
| Category | Non-preemptive | Preemptive |
|---|---|---|
| CPU release | voluntary (on I/O/exit) | can be forcibly reclaimed |
| Responsiveness | low (long jobs monopolize) | high |
| Context-switch overhead | low | high |
| Shared-resource consistency | simple | needs race-condition/synchronization handling |
| Application | simple batch processing | time-sharing/real-time |
Preemptive scheduling gains responsiveness but pays the price of shared-data consistency. If preemption occurs while a kernel data structure is being updated, another process may read a half-updated state, so critical-section protection (semaphores/spinlocks) and the design of kernel preemption points are required together.
Meanwhile, every preemption and switch hides a context-switch cost. On a switch, the OS saves the departing process's registers, program counter, and memory-map information into its PCB (Process Control Block) and restores the incoming process's state, and during this work the CPU does no useful work at all. The larger hidden cost is cache/TLB pollution: the new process cannot use a warmed cache, so cache misses surge initially. Hence a design that gains fairness by raising scheduling frequency is justified only on a balance against this indirect cost, and this is the practical rationale for setting the time quantum at "tens of times or more the context-switch time."
4. Major Scheduling Algorithms
A. FCFS (First-Come, First-Served)
The simplest non-preemptive policy: jobs are taken from the queue in arrival order and run to completion. It has the advantages of being easy to implement and free of starvation, but the convoy effect, in which one long job at the front holds back all the shorter jobs behind it, is fatal. For example, if P1/P2/P3 with bursts of 24/3/3ms arrive in that order, the average waiting time is (0+24+27)/3 = 17ms, but in the order P2/P3/P1 it plummets to (0+3+6)/3 = 3ms. For the very same set of jobs, performance differs by more than fivefold based on order alone, and this case dramatically shows that "arrival order" is irrelevant to efficiency.
B. SJF / SRTF (Shortest Job First / Shortest Remaining Time First)
A policy that processes the job with the shortest remaining CPU burst first, and it is the optimal algorithm, mathematically proven to minimize average waiting time. The non-preemptive version is SJF, the preemptive version SRTF. In practice, however, it has the fundamental limitation that the next burst length cannot be known in advance, so it is approximated by predicting via exponential averaging of past bursts (τ(n+1)=α·t(n)+(1-α)·τ(n)). Another weakness is starvation: if short jobs keep arriving, a long job may never be selected. The mechanism that mitigates this is aging, covered later. In practice, build queues and batch-job schedulers borrow the SJF idea with priorities based on estimated execution time.
C. Priority Scheduling
Each job is assigned a priority and the higher one runs first (SJF is also a special case in which "shorter bursts mean higher priority"). Both preemptive and non-preemptive forms are possible, and it is flexible because it can differentiate system daemons, user jobs, and background jobs. The core pitfall is again indefinite blocking (starvation), and to prevent it, aging, which gradually raises the priority of long-waiting jobs, is combined in. In addition, priority inversion, in which a low-priority job holding a shared resource blocks a high-priority job, can occur, and it is countered with a priority-inheritance protocol (the reset incident of the Mars Pathfinder spacecraft is a representative case).
D. Round Robin (RR) and MLFQ
RR is the standard for time-sharing: it is a preemptive FCFS that gives each job the same time quantum and sends it to the back of the queue when the quantum is exhausted. Thanks to its fairness and predictable response time, it suits interactive systems. Performance is sensitive to quantum size: too large and it degenerates into FCFS, too small and context-switch overhead explodes. It is typically set at tens of times the switch cost (a few ms to tens of ms) and tuned "so that 80% of bursts finish within the quantum." For instance, with bursts of 24/3/3ms and a quantum of 4ms, P1 is preempted after 4ms so that P2/P3 cut in quickly, greatly improving average response time over FCFS.
The practical principles for setting the time quantum can be summarized as follows.
- Large enough relative to the switch cost: set it at tens of times the context-switch time or more, holding the overhead ratio to about 1% or below.
- Match the burst distribution: set it so that the majority (about 80%) of CPU bursts finish within one quantum, reducing unnecessary preemption.
- Differentiate by workload: small for interactive (fast response), large for compute-centric (reduced switching) — MLFQ automates this.
The Multi-Level Feedback Queue (MLFQ) is an adaptive policy that stacks several RR queues by priority and moves jobs between queues by observing their behavior. A CPU-bound job that uses up its quantum is demoted to a lower queue (longer quantum), while an I/O-bound or interactive job that gives up the CPU early is kept in an upper queue (shorter quantum, higher priority), aiming for responsiveness and throughput at once. Its strength is that it classifies jobs as if learning on its own, even without knowing their nature in advance, and it prevents starvation through periodic priority readjustment (boosting).
| Algorithm | Preemption | Avg. Wait | Starvation | Characteristics |
|---|---|---|---|---|
| FCFS | X | poor | none | simple, convoy effect |
| SJF/SRTF | optional | optimal | present | prediction needed |
| Priority | optional | variable | present | aging needed |
| RR | O | moderate | none | quantum-sensitive, fair |
| MLFQ | O | excellent | none (boosting) | adaptive, general-OS standard |
E. Comprehensive Comparison Example — Same Jobs, Different Results
To feel the differences between policies in numbers, we compare the results of running three processes that arrive simultaneously (at time 0), P1 (24ms)/P2 (3ms)/P3 (3ms), under FCFS, SJF, and RR (quantum 4ms). The table below summarizes each policy's completion time and waiting time (= completion time − burst). Note that for the same input, average waiting time differs by more than threefold depending on the policy.
| Policy | P1 compl./wait | P2 compl./wait | P3 compl./wait | Avg. Waiting Time |
|---|---|---|---|---|
| FCFS (P1→P2→P3) | 24 / 0 | 27 / 24 | 30 / 27 | 17ms |
| SJF (P2→P3→P1) | 30 / 6 | 3 / 0 | 6 / 3 | 3ms |
| RR (quantum 4) | 30 / 6 | 10 / 7 | 13 / 10 | 7.7ms |
FCFS has the worst average wait due to the convoy effect, as the long P1 blocks the front. SJF minimizes average wait (optimal) by putting short jobs first, but if short jobs keep flowing in, P1 bears the risk of falling into starvation. Although RR's average wait is inferior to SJF's, P2/P3 have short response times until they receive their first reaction (within 4ms and 8ms respectively), so perceived performance is best in an interactive environment. In other words, "small average waiting time" and "fast response" are different goals, and this example clearly shows that the choice of scheduler is precisely a decision about which metric to sacrifice and what to gain.
5. Advanced — Practical Schedulers and Multicore Trends
Real-world general-purpose OSes do not use the classic algorithms above as-is but operate sophisticated schedulers that combine fairness, scalability, and power. Linux introduced the CFS (Completely Fair Scheduler) from 2007, which, instead of time slices, accumulates the CPU time each job has received as virtual runtime (vruntime) and selects the job with the smallest vruntime from a red-black tree in O(log n), thereby approximating "an equal share of CPU for every job." From Linux 6.6 in 2024, it was replaced by EEVDF (Earliest Eligible Virtual Deadline First), which handles latency-sensitive jobs better, improving the balance of responsiveness and fairness via the concept of a virtual deadline. Windows combines a 32-level priority-based preemptive scheduler with priority boosting (a temporary bump for foreground windows or on I/O completion).
The effect of this evolution shows up in concrete figures. As Linux moved from the O(1) scheduler to CFS, the selection cost was held to logarithmic scale even with thousands of jobs running at once, improving the tail latency of large web servers, and after EEVDF's introduction there are continuing reports that frame drops in latency-sensitive jobs such as audio and games have decreased. Conversely, mishandling the scheduler collapses performance. A representative practical case is the CFS bandwidth throttling (CPU throttling) problem in Kubernetes: setting a low CPU limit on a container causes CFS to forcibly stop that container when its quota is exhausted every 100ms period, so that p99 response time spikes by hundreds of ms even when CPU is available. Many organizations, because of this phenomenon, adopt operational guidelines to remove or raise the CPU limit on latency-sensitive services, which is a real example showing that cloud performance tuning is impossible without understanding OS scheduling principles.
Heterogeneous multicore in mobile and servers adds a new dimension. ARM big.LITTLE / DynamIQ mixes high-performance cores and low-power cores, and the scheduler selects cores according to workload and power budget (EAS, Energy-Aware Scheduling) to extend battery life. Also, since load imbalance arises in multicore environments where each core has its own ready queue, the trade-off between periodic load balancing and processor affinity, which keeps jobs on a core with a warmed cache, must be managed. In virtualization and the cloud, the hypervisor reschedules vCPUs onto physical CPUs, so double scheduling and the lock-holder preemption problem also become considerations. In the real-time domain, deadline-based policies such as RMS (Rate Monotonic) and EDF (Earliest Deadline First) are used separately to guarantee deadlines of periodic tasks.
6. Considerations and Implications (Professional Engineer's Perspective)
- Application strategy — choose the policy to fit the purpose: interactive devices should prioritize response time (RR/MLFQ), batch servers throughput (SJF approximation), and real-time controllers deadline adherence (EDF/RMS). There is no single "best scheduler," and analysis of workload characteristics must come first.
- Managing trade-offs: the time quantum is the balance point between responsiveness (short) and context-switch overhead (long), and preemption gives responsiveness while causing synchronization cost and cache pollution. The capability to measure inter-metric conflicts quantitatively (utilization, p99 latency) and tune them is required.
- Institutionalizing starvation/inversion prevention: priority-based policies must always design aging and priority inheritance together to structurally block indefinite blocking and priority inversion (in mission-critical systems these lead directly to safety incidents).
- Linkage to power/sustainability: energy-aware scheduling combined with heterogeneous cores and DVFS directly affects mobile battery life and data-center power costs (green IT). Future schedulers will evolve to optimize not only performance but also performance per watt and carbon efficiency.
- Extension to related technologies: the same principles extend to containers (cgroups CPU quotas/CFS bandwidth control) and Kubernetes requests/limits, to vCPU scheduling in virtualization, and even to GPU/NPU job scheduling, so understanding OS scheduling becomes the foundation of cloud resource management.
- The need for an observation/verification framework: scheduling quality shows up not in averages but in tail latency (p99/p99.9) and scheduling latency, so an observation framework that measures the actual latency distribution with
perf sched, eBPF-based tracing, and the like, and manages it in conjunction with SLOs, must be in place for policy tuning to have a basis.
References
- Operating System Concepts (Silberschatz et al.), CPU Scheduling chapter
- Linux Kernel Documentation, "CFS Scheduler" / "Scheduler" — https://docs.kernel.org/scheduler/
- Arpaci-Dusseau, "Operating Systems: Three Easy Pieces" — Scheduling(MLFQ) — https://pages.cs.wisc.edu/~remzi/OSTEP/
In one line: CPU scheduling is a technique that selects the next job to run among those in the ready queue to draw out the efficiency of multiprogramming, in which FCFS/SJF/Priority/RR/MLFQ each weigh responsiveness, throughput, and fairness differently, and in practice it is advancing through Linux CFS/EEVDF and energy-aware, multicore scheduling.