Process Scheduling Algorithms in Operating Systems

Process scheduling determines which process runs on which CPU core at any given moment. The scheduling policy has a direct, measurable impact on system performance — affecting throughput, response time, fairness, and power consumption. A poorly chosen scheduler can make a fast CPU feel sluggish under interactive workloads, while a well-tuned scheduler keeps desktop environments responsive, servers handling thousands of concurrent requests, and real-time systems meeting strict deadlines.

The Scheduling Landscape

The OS scheduler operates at multiple timescales. The long-term scheduler (job scheduler) controls the degree of multiprogramming — how many processes are active in memory. The medium-term scheduler swaps processes between memory and swap space to control memory pressure. The short-term scheduler (CPU scheduler), invoked on every timer interrupt (typically every 4–10 ms on Linux), selects the next process to run on an available CPU core.

The scheduling decision points are: when a process switches from running to waiting (I/O request), from running to ready (timer interrupt), from waiting to ready (I/O completion), or when a process terminates. Preemptive schedulers can interrupt a running process at any time; non-preemptive schedulers wait for the process to voluntarily yield the CPU. Modern general-purpose OSes use preemptive scheduling to guarantee responsiveness.

Context Switching Overhead

When the scheduler selects a different process, the kernel must save the current process’s register state (program counter, stack pointer, general-purpose registers, segment selectors, floating-point state) and restore the next process’s saved state. This context switch also invalidates the TLB (unless Process Context Identifiers are used), so subsequent memory accesses encounter TLB misses until the cache warms up.

A context switch takes approximately 1–10 microseconds on modern hardware, depending on the complexity of the register state and TLB flushing required. At 4 ms scheduling quanta, a context switch represents 0.025% to 0.25% overhead. With very small time slices (1 ms or less), context switching overhead can consume a significant fraction of CPU time — the reason Linux’s default time slice is approximately 6 ms on desktop systems.

Scheduling Algorithms

First-Come, First-Served (FCFS)

FCFS processes requests in arrival order. A non-preemptive algorithm, it is simple to implement — a FIFO queue — but suffers from the convoy effect: a single long-running CPU-bound process blocks behind it, short interactive processes accumulate, and average waiting time increases dramatically. Consider three processes arriving at time 0: P1 (24 time units), P2 (3), P3 (3). Under FCFS, average waiting time = (0 + 24 + 27) / 3 = 17 time units. With the optimal order (P2, P3, P1), average waiting time = (0 + 3 + 6) / 3 = 3 time units. FCFS is not used as the primary scheduler in any modern general-purpose OS.

Shortest Job First (SJF)

SJF selects the process with the shortest next CPU burst. This algorithm is provably optimal for minimizing average waiting time (a proof by Kleinrock, 1975). The problem is that future burst lengths cannot be known in advance — the OS can only estimate them using exponential averaging of past burst lengths. SJF can also cause starvation if short processes continuously arrive and prevent long processes from ever running. Non-preemptive SJF is rarely used; the preemptive variant — Shortest Remaining Time First (SRTF) — is fairer but still impractical.

Round Robin (RR)

Round Robin assigns each process a fixed time quantum and cycles through the ready queue in order. After a process has executed for the quantum length, the timer interrupt fires, and the scheduler moves the process to the back of the queue and dispatches the next process. RR is the foundation of time-sharing systems — it provides predictable latency for interactive processes and fairness across all processes.

The quantum size is the critical parameter. A very small quantum (1 ms) maximizes responsiveness but spends excessive time on context switching. A very large quantum (100 ms) approaches FCFS behavior. Modern systems use a quantum of approximately 4–15 ms. Linux’s CFS does not use a fixed quantum but instead enforces a target latency (the time within which every runnable process receives at least one time slice), defaulting to approximately 6 ms on desktop configurations.

Priority Scheduling

Each process is assigned a priority. The scheduler always runs the highest-priority ready process. Priorities can be static (assigned once at creation) or dynamic (adjusted over time). Starvation — where low-priority processes never run — is the primary problem. The standard mitigation is aging: gradually increase the priority of waiting processes until they become eligible.

Windows uses 32 priority levels (0–31), with real-time priorities 16–31 reserved for time-critical threads. The Windows scheduler boosts the priority of a thread in the foreground process when it receives window input, ensuring interactive responsiveness. Linux assigns dynamic priorities via the nice value (−20 to +19), where lower nice values indicate higher priority. CFS translates nice values into weight factors that determine proportional CPU allocation.

Multilevel Queue Scheduling

The ready queue is partitioned into separate queues, each with its own scheduling algorithm. A common configuration has a foreground queue (interactive processes, RR with small quantum) and a background queue (batch processes, FCFS). Processes are permanently assigned to a queue based on their type. Queue scheduling (deciding which queue to serve next) runs as fixed-priority preemption (foreground always before background) or as time-sliced across queues.

Multilevel Feedback Queue (MLFQ)

MLFQ is the most sophisticated of the classical algorithms. Processes can move between queues based on their observed behavior. A process that uses its full quantum without yielding is moved to a lower-priority queue (it is CPU-bound). A process that yields before its quantum expires (it is I/O-bound or interactive) is moved to a higher-priority queue. MLFQ balances responsiveness for interactive processes with throughput for batch processes without requiring advance knowledge of process behavior. The BSD Unix scheduler and early Linux schedulers used MLFQ variants.

The Linux Completely Fair Scheduler (CFS)

CFS, designed by Ingo Molnár and merged in Linux 2.6.23, replaced the earlier O(1) scheduler. CFS’s model is fundamentally different from the classical algorithms. Rather than maintaining a ready queue, CFS maintains a time-ordered red-black tree of runnable processes, keyed by virtual runtime (vruntime) — the amount of time a process has run, normalized by its priority weight.

CFS always runs the process with the smallest vruntime (the leftmost node in the tree). Over any time window, each process receives CPU time proportional to its weight. A nice value of 0 gives default weight; nice −20 gives approximately 15× the weight of nice +19.

The target latency (configurable via /sys/kernel/sched_latency_ns) defines the time within which every runnable process runs at least once. On systems with few processes, each process runs for a longer slice; on systems with many processes, slices are shorter, ensuring bounded latency. The minimum granularity (sched_min_granularity_ns, default 750 μs) prevents excessive context switching with very short slices.

In the current kernel (6.x), a new CFS feature called EEVDF (Earliest Eligible Virtual Deadline First) scheduler has been merged as optional, designed to better handle latency-sensitive workloads by tracking both vruntime and deadlines.

Scheduling Metrics and Benchmarking

The standard scheduling metrics are:

• CPU utilization: The fraction of time the CPU is executing (not idle). Target: as close to 100% as possible without degrading response time.
• Throughput: Processes completed per unit time. Higher is better.
• Turnaround time: Time from process submission to completion. Relevant for batch workloads.
• Waiting time: Total time a process spends in the ready queue. The algorithm that minimizes average waiting time (SJF) does not necessarily minimize turnaround or maximize throughput.
• Response time: Time from process submission to the first response (first output). The critical metric for interactive applications.

No single algorithm optimizes all metrics simultaneously. A scheduler optimized for throughput (long batches uninterrupted) penalizes response time. A scheduler optimized for response time (frequent preemptions) reduces throughput due to context switch overhead.

FAQ

How does the scheduler handle multiple CPU cores?

Linux maintains per-CPU run queues. Each CPU pulls processes from its own queue. When load is imbalanced (some CPUs idle while others are busy), the load balancer runs periodically and when a CPU becomes idle, pulling processes from the busiest CPU’s queue. NUMA-aware scheduling places processes on local CPU cores and migrates them only when necessary, maintaining memory locality.

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

A preemptive scheduler can interrupt a running process at any time (typically on a timer interrupt) and switch to another process. A non-preemptive scheduler waits for the running process to voluntarily yield the CPU (by blocking on I/O, calling sched_yield(), or terminating). Preemptive schedulers provide guaranteed response times and prevent a single process from monopolizing the CPU. All modern general-purpose OSes use preemptive scheduling.

How does the scheduler handle real-time processes?

Linux supports two real-time scheduling policies: SCHED_FIFO (first-in, first-out, runs until it blocks or yields) and SCHED_RR (round robin with priority levels). Real-time priorities range from 1 (lowest RT) to 99 (highest). Real-time processes always run before any normal (SCHED_OTHER) process. A CPU-bound SCHED_FIFO process at priority 99 can starve all other processes, including kernel threads — the RT_RUNTIME_GLOBAL mechanism limits real-time CPU consumption to prevent system lockups.

What is the scheduling overhead on a typical Linux system?

At default settings, the scheduler timer interrupt fires every 4 ms (CONFIG_HZ=250). At each tick, the scheduler may run if the current process has exhausted its time slice. The combined overhead of timer interrupt + potential context switch is approximately 1–5 μs per tick. On a fully loaded CPU with 250 context switches per second, scheduling overhead consumes roughly 0.1% of CPU time.

How do I/O-bound and CPU-bound processes interact in the scheduler?

I/O-bound processes spend most of their time waiting (blocked on I/O) and require low response time when they become ready. CPU-bound processes use their full time slice. In MLFQ schedulers, I/O-bound processes naturally rise to higher-priority queues because they yield before the quantum expires. In CFS, I/O-bound processes accumulate less vruntime than their CPU-bound counterparts, so they’re selected more frequently by the scheduler.

The Synchronization and Concurrency Guide covers the interactions between scheduling and lock acquisition. The Memory Management Guide explains how page faults and memory pressure interact with scheduling decisions. The complete Linux scheduler implementation is in kernel/sched/ in the kernel source tree; the documentation in Documentation/scheduler/ provides authoritative detail on parameters and tuning knobs. Silberschatz, Galvin, and Gagne, Operating System Concepts (10th ed.), Chapter 5, covers scheduling algorithms comprehensively.