CPU Scheduling

CPU scheduling is the operating-system function that decides which ready process or thread runs on a processor next, balancing goals such as responsiveness, throughput, fairness, and meeting deadlines.

Definition

CPU scheduling is the policy and mechanism by which an operating system selects, from among the runnable processes or threads, which one to allocate the processor to and for how long, in order to optimize chosen performance and fairness objectives.

Scope

This topic covers scheduling policies and their evaluation: first-come-first-served, shortest-job-first, round-robin, priority, and multilevel feedback queues; preemptive versus non-preemptive scheduling; the criteria of CPU utilization, throughput, turnaround, waiting, and response time; and scheduling on multiprocessors and for real-time systems. It excludes the representation of the tasks being scheduled (process and thread management) and synchronization (concurrency).

Core questions

• By what criteria is scheduling quality measured?
• How do common scheduling algorithms differ in fairness and efficiency?
• When should the scheduler preempt a running task?
• How is scheduling adapted for multiprocessors and real-time deadlines?

Key concepts

• first-come-first-served
• shortest-job-first
• round-robin and time quantum
• priority scheduling
• multilevel feedback queues
• preemptive vs non-preemptive
• turnaround, waiting, and response time
• starvation and aging
• real-time scheduling

Key theories

Scheduling objectives and trade-offs

No single policy optimizes all goals: shortest-job-first minimizes average waiting time but can starve long jobs, round-robin bounds response time at some throughput cost, and priority schemes risk starvation, so schedulers balance throughput, fairness, and responsiveness for their workload.

Mechanisms

The scheduler runs when a process blocks, yields, or its time quantum expires, choosing the next task from the ready queue according to its policy. Round-robin gives each task a time slice in turn; priority and multilevel feedback queues order tasks by importance and observed behavior, using aging to prevent starvation. Preemptive schedulers can interrupt a running task to switch to a higher-priority one, which is essential for interactivity and real-time deadlines.

Clinical relevance

Scheduling directly shapes the user experience and system efficiency: it determines whether interactive applications feel responsive, whether batch workloads complete quickly, and whether real-time tasks meet deadlines. Schedulers in production systems such as Linux balance these competing goals across many cores and diverse workloads.

History

Scheduling problems arose with multiprogramming and time-sharing in the 1960s, when round-robin and priority schemes were developed to share processors. Real-time scheduling theory, including rate-monotonic and earliest-deadline-first analyses, was formalized in the 1970s, and modern multicore schedulers extended these ideas to many processors.

Debates

Fairness versus throughput and priority

Schedulers must reconcile fairness among tasks with maximizing throughput and honoring priorities; aggressive prioritization improves important tasks but risks starving others, while strict fairness can underuse the system, so practical schedulers tune the balance.

Key figures

• Edsger W. Dijkstra
• Abraham Silberschatz
• Andrew S. Tanenbaum
• C. L. Liu
• James W. Layland

Seminal works

• silberschatz2018
• tanenbaum2014os

Frequently asked questions

What is the difference between preemptive and non-preemptive scheduling?

Non-preemptive scheduling lets a running task keep the processor until it blocks or finishes. Preemptive scheduling can forcibly take the processor away — for example when its time slice expires or a higher-priority task becomes ready — which improves responsiveness and is required for real-time guarantees.

What is starvation, and how is it prevented?

Starvation occurs when a task never gets scheduled because higher-priority tasks continually take precedence. It is commonly prevented by aging, which gradually raises the priority of long-waiting tasks so they eventually run.