CPU Scheduling Fundamentals

CPU scheduling is the operating system's method for selecting, from among all processes in the ready queue, which one will be given the CPU next. It is a policy question — a decision about priorities and goals — layered on top of the mechanism question already answered by context switching: how do you actually save one process's state and load another's? The scheduler answers "who's next?" The dispatcher is the module that answers "how do we get them running?" — it performs the context switch, restores the memory-management state, and transfers control to the chosen process's next instruction, typically by executing a jump to the location stored in its saved program counter. The reason scheduling exists at all is the CPU burst / I/O burst cycle. Process execution consists of alternating segments: a burst of pure CPU computation, followed by a burst of I/O wait (disk, network, keyboard), followed by another CPU burst, and so on, until the process terminates. Empirically, CPU burst lengths follow a distribution with many short bursts and a few long ones (often modeled as roughly exponential in shape). This matters enormously: it means most processes are usually not using the CPU (they are blocked on I/O), so a scheduler that lets a CPU-bound process monopolize the core wastes the opportunity to run many short, I/O-bound processes that are ready and waiting. A scheduling decision must be made at exactly four points in a process's lifecycle, corresponding to specific state transitions: 1. Running → Waiting: the process issues an I/O request or waits on an event (e.g., a semaphore). 2. Running → Ready: an interrupt (typically a timer) forces the process to give up the CPU. 3. Waiting → Ready: an I/O completion or event makes a previously blocked process runnable again, and it may (in preemptive schemes) contend for the CPU immediately. 4. Terminated: the process finishes and releases the CPU voluntarily. Transitions 1 and 4 are unavoidable — the running process is leaving the CPU no matter what the scheduler decides. Scheduling here is non-preemptive (or cooperative): the OS only chooses a replacement, it never forces the current process out. Transitions 2 and 3 are where the scheduler has real teeth: it can forcibly interrupt a running process to give the CPU to someone else. Scheduling that uses transitions 2 and 3 is called preemptive. Almost all modern general-purpose operating systems (Linux, Windows, macOS, Android, iOS) use preemptive scheduling, because it is the only way to bound how long any single process can hold the CPU and guarantee reasonable response times for interactive and real-time work.

The scheduling subsystem is really two cooperating pieces with very different jobs and very different frequencies of execution.

The scheduler (short-term / CPU scheduler) runs whenever a scheduling decision is triggered — at the four transition points above. Its job is purely to select a process from the ready queue according to some policy (FCFS order, priority, remaining time, etc. — the specific algorithms build on this article). It does not touch hardware registers or memory maps; it just returns "run process P next."

The dispatcher takes that decision and makes it physically true. It must: 1. Save the context (registers, program counter, stack pointer) of the process being removed from the CPU, if it is not already saved by an earlier trap/interrupt handler. 2. Switch the memory-management context if needed (page tables, TLB flush or ASID reload). 3. Switch to kernel/user mode as appropriate. 4. Restore the context of the newly chosen process. 5. Jump to the resumed location (its saved program counter), returning control to user mode. The time this entire sequence takes is called dispatch latency. It is pure overhead: no user-visible work happens during a dispatch, and this time is deducted from the CPU's useful throughput. A well-engineered dispatcher tries to make this cost as small and as predictable as possible, because in real-time systems the worst-case dispatch latency is itself a correctness constraint. ``` // Simplified scheduling + dispatch cycle, executed on every // scheduling-relevant event (timer interrupt, I/O completion, // blocking call, process exit). function on_scheduling_event(event): current = running_process() switch event.type: case TIMER_INTERRUPT: if scheduling_policy.is_preemptive(): ready_queue.enqueue(current) current.state = READY else: return // ignore tick, keep running case IO_REQUEST or BLOCKING_WAIT: current.state = WAITING wait_queue[event.device].enqueue(current) case IO_COMPLETION(proc): proc.state = READY ready_queue.enqueue(proc) if scheduling_policy.is_preemptive() and priority(proc) > priority(current): ready_queue.enqueue(current) // preempt now current.state = READY else: return // let current keep running case PROCESS_EXIT: current.state = TERMINATED free_resources(current) // A new decision is needed whenever the CPU is free // (exit) or the current process was just made non-running. if current.state != RUNNING: next = scheduler.select(ready_queue) // policy plugged in here dispatch(current, next)

function dispatch(prev, next): t_start = clock() save_context(prev) // registers, PC, SP -> PCB if prev.address_space != next.address_space: switch_memory_map(next) // page table base, flush/reload TLB restore_context(next) // PCB -> registers, PC, SP next.state = RUNNING t_end = clock() dispatch_latency = t_end - t_start // pure overhead, minimize this resume_execution(next) // jump to next.PC ``` The pseudocode makes the preemptive/non-preemptive fork explicit: on a `TIMER_INTERRUPT`, a non-preemptive policy simply returns and lets the current process keep running (the interrupt only updates accounting, e.g. incrementing a burst counter); a preemptive policy forces the process back into the ready queue. Similarly, on `IO_COMPLETION`, a preemptive policy can immediately steal the CPU back from a lower-priority running process, while a non-preemptive policy always lets the current process finish its burst uninterrupted.

Time complexity of the scheduling decision itself. The scheduler's job — selecting a process from the ready queue — has a cost that depends entirely on the queue's data structure and the policy, not on some inherent property of "scheduling." A naive linear scan of an unsorted ready list to find, say, the highest-priority process costs $O(n)$ where $n$ is the number of ready processes. A ready queue implemented as a balanced binary heap keyed by priority or virtual runtime (as in Linux's Completely Fair Scheduler, which uses a red-black tree) reduces selection and re-insertion to $O(\log n)$. A plain FIFO queue (used for round-robin or FCFS) gives $O(1)$ enqueue/dequeue. This article deliberately does not commit to one policy — the complexity is a property of the algorithm layered on top, covered in later scheduling articles — but the queue mechanics discussed here bound what is achievable.

Time cost of the dispatcher. Dispatch latency has a fixed hardware/software floor: saving and restoring registers is $O(1)$ (a constant number of registers), but switching address spaces can cost more — a full TLB flush followed by cold-cache refills can cost hundreds to thousands of cycles depending on architecture, and this cost is not asymptotic in $n$, it's a constant-but-nontrivial overhead per switch. This is why operating systems care about context-switch frequency, not just the existence of switches: preemptive scheduling with a very short timer quantum increases fairness and responsiveness but multiplies this fixed per-switch cost, directly reducing CPU throughput available for actual process work. If a quantum of length $q$ requires dispatch overhead $d$, the fraction of CPU time wasted on switching is at least

which shows the fundamental tradeoff honestly: shrinking $q$ to improve responsiveness necessarily grows this wasted fraction, since $d$ (dominated by hardware costs) cannot shrink at will. Real systems choose $q \gg d$ by one to two orders of magnitude (e.g., $d$ on the order of microseconds, $q$ on the order of milliseconds) to keep this overhead under roughly 1%.

Correctness argument. The state machine's correctness rests on one invariant: at every instant, at most one process per CPU core is in the RUNNING state, and every process is in exactly one of {Ready, Running, Waiting, Terminated} (plus New). The scheduling event handler above preserves this invariant because every transition explicitly moves a process out of RUNNING before another can enter it — `dispatch(prev, next)` only ever runs after `prev`'s state has already been updated away from RUNNING in the calling code, and `next.state = RUNNING` is set exactly once per dispatch call. The four-decision-point enumeration is exhaustive precisely because these correspond to the only edges leaving the RUNNING state in the process lifecycle graph (to Waiting, to Ready via preemption, to Terminated) plus the one edge that can trigger a need for a new decision (Waiting → Ready, when the newly-ready process might outrank the currently running one). No other event can legally change who occupies the CPU, so checking these four points is both necessary and sufficient for a correct scheduler implementation.

Tradeoff honesty. Non-preemptive scheduling has zero risk of race conditions on shared kernel data structures modified by the running process itself (nobody can interrupt you mid-update), which is why very old and very simple embedded schedulers use it — but it gives no guarantee on response time: one runaway CPU-bound process can freeze the whole system. Preemptive scheduling fixes responsiveness but reintroduces exactly the concurrency hazards that context switching and synchronization primitives (locks, disabling interrupts during critical kernel sections) must then guard against. There is no free lunch: preemption buys fairness and responsiveness at the cost of more frequent dispatch overhead and more delicate kernel synchronization.

Consider three processes arriving with the CPU bursts and I/O bursts below, on a system where dispatch latency is $d = 0.1$ ms. We trace what happens under a non-preemptive policy versus a preemptive one, using simple "run until you'd naturally yield vs. force a switch on timer tick" behavior to make the preemption/non-preemption distinction concrete (this is not yet a full algorithm like SJF or Round Robin — those are covered separately — this is purely to see the four decision points fire).

Non-preemptive trace (each process, once dispatched, runs its full burst uninterrupted until it blocks on I/O or terminates):

Total elapsed time: 14.3 ms, with two dispatch overheads paid (0.2 ms total) — because only two involuntary switches after the first ready arrival were needed once each process is running until it naturally yields the CPU. Note P1 waited from 9 ms to 12.2 ms (3.2 ms) even though it was ready, purely because non-preemptive scheduling refused to interrupt P3.

Preemptive trace (same workload, but here we allow the scheduler to preempt at I/O-completion time if it chooses — assume a policy that always favors a newly-ready process with a shorter remaining burst, which is legal to apply because the system is preemptive, foreshadowing later algorithms):

Total elapsed: 14.4 ms with three dispatch overheads paid (0.3 ms total) — preemption cost more total dispatch overhead here, but P1 finished at 11.1 ms instead of 14.3 ms, a large win in turnaround time for that process, at the cost of P3 being delayed. This is exactly the tradeoff the complexity section predicted: preemption trades some throughput (extra switches) for better responsiveness on select processes — the concrete algorithms that decide whom to favor (Shortest Job First, Round Robin, priority scheduling) are the natural next topic once this cost/benefit shape is understood.

Every general-purpose operating system kernel — Linux, Windows NT, macOS/XNU, the various BSDs — implements exactly this scheduler/dispatcher split, and every one of them is preemptive at the process/thread level for this reason. Real-time operating systems (VxWorks, QNX, FreeRTOS) obsess over minimizing and bounding dispatch latency, because a real-time task missing its deadline due to unpredictable switch overhead is a system failure, not just a slowdown. Hypervisors (KVM, Xen, VMware ESXi) run a second layer of scheduling on top — scheduling entire virtual CPUs the same way a kernel schedules processes — making these same four decision points and the preemptive/non-preemptive distinction recur one level up the stack. Mobile operating systems (Android, iOS) tune preemption aggressiveness and quantum length specifically to keep UI threads responsive even while background work runs, a direct application of the responsiveness/throughput tradeoff derived above. Understanding this foundation is what makes it possible to evaluate concrete policies — covered next under Scheduling Performance Metrics and First-Come First-Served Scheduling — on a common, honest basis.

Ask the tutor: How does the Linux Completely Fair Scheduler decide which ready process to dispatch, and how does its red-black tree keep that decision at O(log n)?