CPU scheduling is the selection of runnable work for execution on a central processing unit and the allocation of processor time among competing tasks. It is a central responsibility of an operating system, although related scheduling decisions also occur in language runtimes, hypervisors, and application frameworks. On a single processor, scheduling determines which task executes next; on a multiprocessor, it also helps determine where tasks execute and whether they should move between processors.
Scheduling makes interactive computing, background processing, and time-constrained control possible on shared hardware. Its objectives are not interchangeable: a policy that maximizes completed jobs per second may give poor response to an interactive request, while a policy that meets critical deadlines may deliberately reserve capacity that other work could use. Practical schedulers therefore combine selection rules, accounting mechanisms, priorities, and hardware-awareness rather than relying on a single universal algorithm.
Execution states, dispatching, and preemption
The object scheduled by a modern operating system is usually a thread, although textbooks often describe scheduling in terms of a process. A process provides an execution environment, including an address space and resources; its threads are independently executable sequences of instructions. Operating systems may use implementation-specific terms such as task or scheduling entity. A runtime can additionally schedule many user-level threads over a smaller number of operating-system threads, so application-level and kernel-level scheduling need not coincide.
A simplified execution model distinguishes running, ready, and blocked states. A running task currently occupies a processor. A ready task could execute but is waiting for processor time. A blocked task cannot proceed until an event occurs, such as completion of a disk operation or release of a synchronization object. The ready population is maintained in one or more run queues, which may use a queue, priority-indexed lists, trees, or other structures. Blocking removes a task from competition for the CPU; an event that makes it runnable places it back under scheduler control.
Scheduling policy chooses an eligible task, while dispatching performs the transfer of execution. A context switch saves sufficient state from the outgoing task and restores the incoming task’s state, including registers and the position at which execution should resume. Switching between address spaces can also require memory-management changes. These operations are distinct from a change between user mode and kernel mode: a system call may execute kernel code and return to the same thread without any scheduling change.
In nonpreemptive scheduling, a task retains the processor until it blocks, terminates, or voluntarily yields. In preemptive multitasking, the operating system can suspend a runnable task to execute another. Timer interrupts provide one mechanism for enforcing time slices, but scheduling decisions also occur when tasks wake, priorities change, or processors become available. Kernel preemption introduces further distinctions: some kernels permit preemption through much of kernel execution, while particular critical sections remain nonpreemptible.
The scheduler itself must work correctly amid concurrent state changes. A task may wake while another processor is attempting to dispatch it, and a processor may become idle during a load-balancing operation. Run-queue locks, atomic operations, and carefully defined task states prevent duplicate execution or lost wakeups. Interrupt handling and nonpreemptible regions also limit how quickly a selected task can actually run. Consequently, dispatch latency includes more than the time required to compare priorities: it includes delays imposed by the rest of the kernel and by the hardware’s execution state.
Objectives, measurements, and trade-offs
Scheduling objectives depend on the workload. Batch processing commonly emphasizes throughput and completion time. Interactive systems emphasize prompt initial responses and the ability to remain responsive under load. Servers may be judged by the distribution of request latencies rather than their average, while control systems require bounded timing behavior. These goals can conflict even when tasks have identical access rights and execute on the same hardware.
For a job arriving at time , first executing at , and completing at , response time and turnaround time are commonly defined as
Response time here means delay until first execution; application response latency may instead extend until a result reaches a user. Waiting time is the cumulative time spent runnable but not executing. In a simplified model containing only CPU service and ready-queue waiting, , where is the required CPU service. If the job also blocks for input/output, that blocked time must be accounted for separately.
CPU utilization measures how much processor capacity is occupied, while throughput measures completed work per unit time. Neither alone establishes good service. A system can show high utilization while wasting cycles on synchronization, repeated computation, or excessive context switching. It can also have excellent average throughput while a minority of requests experience very long delays. Percentiles such as the 95th and 99th are therefore important in services governed by a service-level agreement. The appropriate measurement interval also matters: a one-second average can conceal a scheduling pause that disrupts a ten-millisecond deadline.
Fairness has several meanings. Equal processor time is appropriate only when all runnable entities are intended to have equal entitlement. Weighted fairness allocates time in proportion to assigned weights. Group fairness allocates shares to users, applications, or containers rather than to individual threads. For example, equal per-thread allocation gives a program with twenty runnable threads twenty times the aggregate share of a competing single-threaded program. Whether that is desirable is a resource-policy decision, not an intrinsic property of fairness.
The time quantum illustrates a direct trade-off. Suppose a runnable task executes for a quantum , followed by switching overhead . In an idealized sequence of full quanta, the useful execution fraction is approximately . A small quantum improves opportunities for competing tasks to run but increases switching frequency. A large quantum reduces direct overhead but can lengthen waiting times. Actual costs also include disruption of the CPU cache, translation structures, and branch predictors, making the effective switching cost dependent on the workload rather than a universal constant.
Foundational scheduling algorithms
First-come, first-served scheduling selects ready jobs in arrival order and normally runs each until it blocks or finishes. Its simplicity makes it useful as a baseline, but it can produce the convoy effect: short jobs wait behind a long CPU-intensive job. Consider three jobs arriving together, with service requirements of 10, 1, and 1 time units. If the long job executes first, their completion times are 10, 11, and 12, averaging 11. If the short jobs execute first, completion times are 1, 2, and 12, averaging 5.
Shortest-job-first scheduling chooses the ready job with the smallest predicted service requirement. For a set of jobs all available at the same time, a single processor, and known service times, the nonpreemptive shortest-first ordering minimizes average completion time. Its preemptive counterpart, shortest remaining processing time, can interrupt a running job when a newly arriving job has less work remaining. Under the corresponding idealized single-processor assumptions, it minimizes mean flow time, meaning arrival-to-completion time.
These results depend on information that operating systems generally do not possess. A program’s next CPU burst may differ greatly from its previous one, and future branches or inputs may determine its total service requirement. A traditional prediction method uses exponential averaging:
where is the most recently observed CPU burst. A larger reacts more strongly to recent behavior. Prediction can approximate short-job preference, but it does not provide the optimality guarantees associated with exact knowledge. Repeated arrivals of short work can also postpone long jobs indefinitely.
Round-robin scheduling cycles through runnable tasks, giving each a time quantum before returning it to the queue if it remains runnable. With continuously runnable tasks, equal quanta , and negligible overhead, a task that has just exhausted its quantum waits approximately before its next turn. This provides regular access to execution, although actual response also depends on arrivals, blocking, priority classes, and implementation details. As the quantum becomes very large, round robin approaches first-come, first-served behavior.
These algorithms describe different responses to uncertainty and competing objectives. Arrival order avoids estimating service requirements. Shortest-first policies favor mean completion time when useful predictions exist. Round robin offers repeated execution opportunities without knowing job lengths. Their assumptions must remain explicit: a job that blocks frequently does not behave like a single uninterrupted CPU burst, and an application request may involve many threads, network operations, and storage accesses. A locally favorable CPU ordering therefore need not minimize end-to-end application latency.
Priorities, feedback, and proportional sharing
Priority scheduling chooses the highest-priority eligible runnable task. Priorities may be fixed by configuration or adjusted dynamically in response to observed behavior. A strict priority system can deny lower-priority work any execution while higher-priority tasks remain continuously runnable. This condition is called starvation. Aging counters it by increasing a waiting task’s effective priority over time, although the exact rule must be designed around the system’s service commitments. Unrestricted aging would conflict with a requirement that some work always outrank ordinary background processing.
A multilevel feedback queue uses several priority queues and moves tasks between them according to their execution history. A typical design places new work at a high priority and demotes tasks that consume their allotted CPU budget, often assigning longer quanta at lower levels. Tasks that block frequently can receive prompt service when they become runnable again. Periodic boosts prevent permanently low placement. This approximates a preference for short or interactive work without requiring advance knowledge of its total running time.
Feedback rules require careful accounting. If a scheduler demotes a task only after it consumes an entire uninterrupted quantum, a program may retain favorable treatment by yielding just before the quantum expires. Charging cumulative execution across several dispatches closes that particular loophole. Sleep behavior is also ambiguous: blocking may indicate interaction with a user, but it may instead result from unrelated synchronization or deliberate manipulation. Production policies therefore use multiple signals and constraints rather than equating every brief sleep with interactivity.
Proportional-share scheduling addresses allocation more directly. If continuously runnable tasks have weights , the intended long-run share of task is
Lottery scheduling, described by Carl Waldspurger and William Weihl in 1994, represents shares with tickets and randomly selects a winning ticket for each allocation. It provides expected proportional service, but short intervals can exhibit random variation. Stride scheduling uses deterministic progress values to approximate the same allocation goal. Virtual-time schedulers similarly advance a task’s accounting clock according to how much service it receives relative to its weight.
Priority also interacts with resource dependencies. In priority inversion, a high-priority task waits for a lock held by a lower-priority task, while unrelated intermediate-priority work delays the lock holder. Priority inheritance temporarily raises the holder’s priority so that it can finish its critical section. Priority-ceiling protocols impose additional rules that can bound blocking under specified assumptions. These mechanisms belong jointly to scheduling and synchronization: choosing the highest-priority runnable task is insufficient when the task that matters most is blocked on a resource controlled by another.
Real-time scheduling and deadline guarantees
In a real-time operating system, correctness depends partly on when computations finish. A hard real-time requirement treats a missed deadline as unacceptable under the system specification. Soft real-time workloads tolerate some misses but suffer reduced quality, as in delayed media processing. Firm real-time work has no useful value after its deadline, although an occasional miss need not cause system failure. These classifications describe requirements, not processor speed: a fast average execution time does not establish a worst-case timing guarantee.
A standard periodic-task model assigns task a worst-case execution requirement , period , and relative deadline . Its utilization is , and total utilization is . In rate-monotonic scheduling, shorter-period tasks receive higher fixed priorities. C. L. Liu and James Layland’s 1973 analysis established, for independent periodic tasks with deadlines equal to periods on one ideal preemptive processor, the sufficient schedulability bound
The bound approaches , approximately 0.693, as the task count grows. It is sufficient rather than necessary; task sets above it may remain schedulable.
Earliest-deadline-first scheduling dynamically selects the ready job with the earliest absolute deadline. For independent, preemptible periodic tasks on a single ideal processor, with deadlines equal to periods and no additional overhead or blocking, utilization not exceeding 1 is sufficient for schedulability. Different deadline assumptions require different tests. In particular, an average utilization below full capacity does not by itself guarantee that short intervals contain enough processing capacity to meet every constrained deadline.
Fixed-priority systems often use response-time analysis instead of a single utilization bound. A common recurrence is
where bounds blocking and is the set of higher-priority tasks. Iteration seeks a fixed point no greater than the task’s deadline. The summation represents interference from higher-priority releases during the response interval. Release jitter, interrupts, shared resources, and other effects require extensions to this model rather than being silently absorbed into an optimistic execution estimate.
Deadline enforcement also requires admission control and execution-budget management. A reservation mechanism can limit a task to a specified amount of execution per period, reducing interference from overrunning work. The Constant Bandwidth Server is an influential mechanism for combining budget enforcement with deadline-based scheduling. Nevertheless, a mathematical scheduler guarantee depends on the surrounding assumptions: underestimated worst-case execution time, unbounded lock holding, memory-bus interference, or uncontrolled interrupts can invalidate the analysis. Multiprocessor deadlines add further complications because a task set feasible on aggregate capacity may not fit a particular processor assignment.
Multiprocessor placement, locality, and energy
On a multiprocessor, scheduling includes both selecting tasks and assigning them to execution resources. A global design may allow ready tasks to run on any processor, while a partitioned design associates each task with a particular processor. Many general-purpose systems use per-processor run queues with periodic or event-driven load balancing. Per-processor queues reduce contention on scheduler data structures, but they can leave one processor overloaded while another is idle. Global access makes balancing easier conceptually but introduces synchronization and scalability costs.
Moving a task is not free. Processor affinity preserves a tendency, or an explicit requirement, to execute on particular CPUs. A recently running task may have useful data in local caches, so migration can increase cache misses even if it shortens ready-queue waiting. In non-uniform memory access systems, memory access cost also depends on which processor accesses which memory region. Scheduling and memory placement are therefore coupled: moving computation toward its data may help, while repeatedly moving either can produce overhead without stable benefit.
Hardware topology makes processor capacity nonuniform even when the instruction set is shared. Simultaneous multithreading exposes multiple logical processors within one physical core, but sibling threads compete for some execution and cache resources. Two logical processors therefore do not necessarily provide the throughput of two independent cores. Heterogeneous processors add cores with different performance and power characteristics. A task’s priority, computational intensity, cache behavior, and latency sensitivity can all influence whether placement on a particular core improves overall service.
Scheduling also interacts with parallel computing. A parallel program may periodically wait at barriers, making progress dependent on its slowest participating thread. If one thread is descheduled while others spin waiting for it, processors can be busy without advancing useful work. Gang scheduling attempts to run related threads together, whereas work-stealing runtimes redistribute application tasks among worker threads. Runtime placement and kernel placement form separate scheduling layers; a locally reasonable decision in one layer can undermine the other’s assumptions about worker availability.
Energy-aware scheduling considers frequency scaling, core capacity, and idle-state behavior. Consolidating work can allow unused processors to enter deeper sleep states, but higher utilization on active cores can increase latency or force higher frequencies. Spreading work may reduce individual core frequency requirements while preventing deep idle residency. Power and thermal limits can also reduce the capacity available after a task has been placed. Consequently, an energy-aware policy needs estimates of workload demand and hardware behavior; simply minimizing the number of active processors does not always minimize energy consumed per completed job.
Development and production operating systems
CPU scheduling developed alongside multiprogramming and time-sharing. Early batch systems benefited from running another job while one waited for input/output, improving expensive processor utilization. Interactive time-sharing then made response delay a central concern. The Compatible Time-Sharing System, demonstrated at MIT in 1961, and later systems such as Multics helped establish the practical importance of timer-driven allocation and differentiated service. These developments connected scheduling policy to protection, terminal interaction, and the ability to support many users concurrently.
Traditional Unix schedulers used dynamic priorities based in part on recent CPU consumption and user-adjustable niceness. The aim was to prevent sustained CPU users from monopolizing service while allowing tasks returning from sleep to receive timely attention. Such policies influenced later systems, but implementation details changed substantially across Unix families and releases. Standards such as POSIX specify interfaces and semantics for policies including FIFO and round robin without requiring every operating system to implement an identical general-purpose scheduler.
Linux illustrates the evolution from priority-oriented time slicing toward explicit service accounting. Its O(1) scheduler, used in the Linux 2.6 era before the Completely Fair Scheduler, organized runnable tasks with priority arrays so that important selection operations did not grow with the number of tasks. In 2007, Linux 2.6.23 introduced the Completely Fair Scheduler, developed by Ingo Molnár. CFS tracked weighted virtual runtime and used a red–black tree to order runnable entities, favoring those that had received less normalized service.
Linux 6.6, released in 2023, began the transition of fair-class task selection toward Earliest Eligible Virtual Deadline First, or EEVDF. The underlying algorithm was published by Ion Stoica and Hussein Abdel-Wahab in 1995. EEVDF distinguishes whether an entity is eligible for service from the virtual deadline used to select among eligible entities. Its virtual deadlines express fair-service scheduling decisions; they are not promises that application requests will complete by real-time deadlines. Linux also maintains separate scheduling classes for deadline and real-time work, so the fair-class algorithm does not govern every runnable task.
Microsoft Windows uses a preemptive, priority-driven scheduler with 32 priority levels, numbered 0 through 31. Thread priorities reflect process priority classes and thread-level settings, with dynamic adjustments for applicable classes. Higher-priority ready threads can preempt lower-priority execution, while quantum expiration governs sharing among comparable competitors. Processor groups, affinity, topology, and power management affect placement on larger or heterogeneous machines. These production examples show why a scheduler cannot be fully characterized by a textbook label: task selection, resource hierarchy, wakeup treatment, processor placement, and policy-class precedence all contribute to observable behavior.
Virtualization, isolation, and scheduler evaluation
Virtualization creates nested scheduling decisions. A guest operating system schedules its threads onto virtual CPUs, while a hypervisor or host schedules those virtual CPUs onto physical processors. A guest may therefore consider a thread running even while its virtual CPU is not executing. Some environments expose this unavailable execution time as steal time. Guest-visible CPU utilization and host-visible processor consumption can consequently answer different questions, particularly when a physical machine is oversubscribed.
Dependencies amplify the effects of nested scheduling. If a virtual CPU holding a spinlock is descheduled, another virtual CPU may spend its allocation waiting for a lock that cannot yet be released. Coordinated scheduling and virtualization-aware synchronization can reduce this problem. Applications inside containers encounter a different boundary: containers generally share the host kernel rather than receiving a complete independent guest scheduler. CPU quotas, weights, and placement controls constrain their service, but these controls have different semantics. A weight usually governs proportional competition, whereas a quota can impose a bandwidth ceiling.
Isolation must also be defined at the correct level. A container limited to half a CPU’s worth of execution over an accounting period may run quickly for part of that period and then be throttled. Its average consumption can comply with the limit while individual requests experience long pauses. Similarly, giving each user equal shares does not automatically provide each application equal shares within a user’s allocation. Hierarchical scheduling makes these relationships explicit, but interactions among hierarchy, affinity, and runnable demand can complicate the resulting distribution.
Evaluation requires workloads that expose the intended properties. Synthetic CPU-bound jobs reveal allocation shares and switching behavior, while interactive tests measure wakeup-to-execution delays. Server experiments examine request throughput and latency distributions under changing load. Real-time evaluation additionally requires analysis of worst-case execution, blocking, and interference; a long successful test run does not prove that a deadline can never be missed. Trace-driven simulation can compare policies under repeatable conditions, but its conclusions depend on whether the recorded behavior remains representative after scheduling changes.
Measurements must distinguish scheduler delay from other causes of slow execution. A thread can be delayed because it is runnable but not selected, blocked on a lock, waiting for storage, limited by memory bandwidth, or running at reduced frequency. Useful evidence includes runnable-queue delay, context-switch counts, migrations, execution-time accounting, and application completion times. Formal verification can establish properties of particular scheduler implementations or models, but the result applies only within the verified assumptions. Hardware interference, application dependencies, and multilayer resource controls remain important boundaries when interpreting either a proof or a benchmark.