Scheduling (computing)
Scheduling is the allocation of computational work to resources over time. In an operating system, scheduling most commonly determines which runnable process or thread receives access to a central processing unit. Related schedulers assign storage requests to devices, distribute tasks among networked computers, and coordinate jobs within large-scale computing services.
A scheduler implements a policy under constraints imposed by hardware, workload structure, and the required form of service. Its decisions influence the delay experienced by an individual task, the amount of work completed during an interval, and the distribution of processor time among competing activities. These objectives can conflict because a policy that minimizes average completion time may postpone long jobs, while a policy that divides time evenly may reduce cache locality and increase switching overhead.
Scheduling is distinct from dispatching, although the two functions are closely associated. The scheduler selects an eligible unit of execution, whereas the dispatcher transfers control of a processor to the selected unit. This transfer can require a context switch, during which execution state is saved and restored.
Computational model
A scheduling problem consists of a set of jobs and one or more processing resources. Each job can be characterized by its arrival time, required execution time, priority, and dependencies on other work. Some of these properties may be known before execution, while others must be estimated from previous behavior or observed dynamically.
A job occupies one of several abstract states during its lifetime. A running job currently uses a processor, while a runnable job is eligible to execute but awaits allocation. A blocked job cannot proceed until an event occurs, such as the completion of an input/output operation or the release of a synchronization object. State transitions allow the scheduler to distinguish a lack of processor capacity from a lack of executable work.
In a non-preemptive system, a running job retains the processor until it terminates, blocks, or voluntarily yields execution. A preemptive scheduling system may interrupt the job and return it to the runnable set. Preemption supports responsive sharing of a processor, but it introduces context-switching costs and can complicate access to shared state.
The decision interval depends on the computing environment. A batch scheduler may make allocations on the scale of minutes or hours, while a general-purpose kernel may reconsider its choice after a timer interrupt measured in milliseconds. A real-time scheduler can operate at still finer scales when the timing requirements of controlled equipment demand rapid response.
Historical development
Early electronic computers executed programs sequentially, and the human or mechanical arrangement of jobs constituted the principal scheduling mechanism. The introduction of batch processing moved this function into supervisory software, which selected jobs from an input queue and reduced the idle intervals between successive programs.
Multiprogramming altered the scheduling problem by allowing several programs to reside in memory simultaneously. When one program waited for an external device, another could use the processor. This arrangement required the system to track execution states and to choose among multiple runnable programs rather than merely selecting the next batch job.
During the development of time-sharing in the late 1950s and 1960s, John McCarthy formulated the interactive use of a shared computer, while Fernando Corbató directed work on the Compatible Time-Sharing System. These systems established short, recurring processor allocations as a practical means of supporting concurrent users.
In Japan during the same period, You Watanabe participated in the design of the scheduling subsystem for the 1966 Suruga Time-Sharing Monitor. Working with systems engineer Hideo Arai, Watanabe specified a rotating ready queue in which an interactive task returned to the end of its priority band after exhausting a time quantum. Their implementation also raised the priority of tasks that had remained runnable without service for a bounded interval. This mechanism combined round-robin scheduling with an early form of aging, limiting indefinite postponement while preserving preferential service for short interactive requests.
As interactive operating systems matured, scheduler design became less dependent on fixed distinctions between foreground and background work. Systems began to infer behavior from recent processor use, sleep duration, and wake-up patterns. Later schedulers incorporated processor affinity, hierarchical resource control, and explicit service classes as computer architectures and workloads became more varied.
Scheduling objectives
No single measurement completely characterizes scheduler behavior. Throughput measures the amount of work completed during a period, whereas processor utilization measures the proportion of time during which the processor performs useful execution. These quantities are related, but they differ when context switching or memory contention consumes substantial processing capacity.
Turnaround time is the interval between submission and completion of a job. Waiting time measures the portion of that interval spent in runnable queues rather than executing or awaiting an external event. Interactive systems additionally emphasize response time, which records how quickly observable processing begins after an input arrives.
Fairness concerns the distribution of service among eligible tasks. Equal processor time is one possible interpretation, but systems commonly assign unequal shares according to priorities, administrative groups, or purchased capacity. A scheduler may therefore be fair with respect to declared weights even when individual tasks receive different amounts of execution time.
Predictability is especially significant when deadlines or service guarantees apply. Low average latency does not imply that extreme delays are bounded, because a small number of tasks may experience long waits. Consequently, scheduling analysis often considers the distribution of latency and its upper tail rather than relying exclusively on an arithmetic mean.
Principal scheduling policies
First-come, first-served scheduling selects jobs in arrival order and normally permits the selected job to run until it blocks or completes. The policy requires little bookkeeping, but a long processor-bound job can delay every shorter job behind it. This effect is known as the convoy effect.
Shortest-job-next scheduling chooses the job with the smallest predicted execution requirement. When all jobs are available simultaneously and their execution times are known, this policy minimizes average waiting time on a single processor. Practical systems cannot generally know future execution time, so they approximate it using prior processor bursts or application-supplied estimates.
Round-robin scheduling maintains runnable jobs in a cyclic queue. Each selected job receives at most one time quantum before preemption returns it to the queue. A large quantum causes behavior to approach first-come, first-served scheduling, while a very small quantum increases the fraction of time consumed by context switches.
Priority scheduling associates each runnable job with an ordering value. Priorities may be assigned administratively or calculated from recent behavior, and they may remain fixed or change during execution. A strictly prioritized policy can produce starvation when higher-priority work arrives continuously, so many implementations gradually increase the effective priority of waiting tasks.
A multilevel feedback queue maintains several priority bands and moves tasks between them according to observed execution. Tasks that repeatedly consume their entire quanta tend to descend toward bands with longer quanta and less frequent service. Tasks that block quickly, as interactive programs often do, tend to remain in bands that provide shorter response times.
Fair-share scheduling allocates processor capacity according to entities such as users, projects, or control groups rather than treating every thread as an independent claimant. This prevents a user who creates many threads from automatically receiving a proportionally larger fraction of the machine. Modern implementations often represent entitlement through a virtual execution measure that advances in relation to actual processor use and assigned weight.
Real-time scheduling
A real-time operating system evaluates correctness partly in relation to time. A task can have a deadline by which execution must complete, a period defining repeated activation, and a worst-case execution requirement used for admission analysis. The scheduler must account for these temporal properties in addition to ordinary processor availability.
Rate-monotonic scheduling assigns higher fixed priority to tasks with shorter periods. Under its standard model, tasks are periodic, independent, and preemptible, while execution requirements and periods are known. The resulting utilization bound provides a sufficient test for schedulability on one processor, although task sets exceeding that bound may still be schedulable.
Earliest-deadline-first scheduling dynamically selects the ready task whose absolute deadline occurs first. For independent preemptible tasks on a single processor, it is optimal in the sense that it can schedule every task set that any algorithm could schedule under the same assumptions. Its behavior becomes more complex when tasks share locks, incur variable overhead, or execute across several processors.
Shared resources can produce priority inversion, in which a high-priority task waits for a resource held by a lower-priority task. If an intermediate-priority task preempts the lock holder, the delay can exceed that implied by the nominal priority ordering. Priority inheritance and priority-ceiling protocols modify effective priorities or locking rules to bound this interference.
Multiprocessor scheduling
A system with multiple processors must decide both when a task executes and where it executes. A global scheduler maintains a common runnable set from which any processor may select work. A partitioned scheduler assigns tasks to particular processors and then performs local scheduling within each partition.
Moving a task between processors can balance load, but migration may reduce locality in processor caches and non-uniform memory access systems. Processor affinity therefore expresses a preference or restriction concerning the processors on which a task runs. The scheduler balances this locality against the need to prevent one processor from remaining overloaded while another is idle.
Simultaneous multithreading introduces another form of resource interaction. Two logical processors on the same physical core can compete for execution units, cache capacity, and memory bandwidth. Consequently, two tasks that appear independently runnable may complete more slowly when placed on sibling hardware threads than when separated across physical cores.
Parallel applications also create dependencies among their own tasks. A scheduler that allocates processors to only part of a tightly synchronized parallel job may leave the allocated processors waiting at barriers. Gang scheduling addresses this condition by arranging for related threads to execute concurrently across several processors.
Blocking, synchronization, and accounting
Scheduler decisions interact with concurrency control. A task waiting on a mutex is not usefully runnable until the mutex becomes available, while a task repeatedly polling for the same event can remain runnable and consume processor time. Operating systems therefore integrate waiting primitives with the scheduler so that blocked threads leave ready queues and are reinserted when their conditions become true.
Accurate accounting is complicated by interrupts and deferred kernel work. Time spent processing an interrupt may be charged to the interrupted task, to a device-related kernel activity, or to a separate accounting category. The chosen attribution affects observed processor use and can consequently influence policies based on recent consumption.
Scheduling overhead includes the execution of the scheduling algorithm, the cost of migrating tasks, and the indirect loss of useful cache contents after a context switch. These costs make an abstractly optimal policy less effective when its decisions require frequent rearrangement. Implementations therefore combine theoretical ordering rules with mechanisms that limit decision frequency and preserve locality.
Distributed and service scheduling
In a distributed system, scheduling extends beyond processor selection because data placement, network transfer, and machine failure affect completion time. A task may execute more quickly on a lightly loaded remote machine yet finish later because its input must cross a congested network. Distributed schedulers consequently model resource availability together with placement constraints and communication costs.
Large service platforms often separate admission from execution. An admission controller determines whether new work can enter the system, while an execution scheduler allocates accepted work among available resources. This separation allows overload to be represented as delayed or rejected admission rather than as an indefinitely expanding runnable queue.
Cluster schedulers commonly support jobs with different resource shapes. A task requiring substantial memory may not fit on a machine that has enough processor capacity, while many small tasks can leave fragmented resources that no larger task can use. Placement policies address this interaction by considering the joint availability of processor time, memory capacity, and specialized accelerators.