CPU scheduling algorithms

Whenever a CPU core becomes free — a process blocks on I/O, finishes, or its time slice expires — the scheduler decides which Ready process runs next. This single decision, repeated constantly, shapes how responsive an interactive system feels and how efficiently a batch workload gets through. There's no single "best" algorithm — each one optimizes a different, often competing, goal.

The simplest possible policy: run processes in the order they became ready, each to completion, before moving to the next. Simple to implement, but suffers from the convoy effect — one long-running process at the front of the queue makes every process behind it wait, even ones that would finish almost instantly if run first.

Runs whichever ready process needs the least remaining CPU time. Provably minimizes average waiting time across all processes — but it requires knowing (or accurately estimating) how long each job will take in advance, which is often impossible for general-purpose interactive workloads. It also risks starvation: a long job can be repeatedly pushed behind a continuous stream of shorter ones and never actually run.

Each process gets a fixed time slice (a "quantum," commonly a few milliseconds), then is moved to the back of the queue if it hasn't finished. This is what makes an interactive desktop or a shared server feel responsive to many programs at once — no single process can hog the CPU for long, regardless of how much total work it needs. The trade-off is in choosing the quantum size: too long and it degrades toward FCFS's convoy effect; too short and context-switching overhead (lesson 4) starts eating a meaningful share of total CPU time.

Each process gets a priority value, and the scheduler always picks the highest-priority Ready process. This models real needs well (a system service handling user input should preempt a background batch job), but introduces the same starvation risk as SJF — a low-priority process can wait indefinitely behind a constant stream of higher-priority ones. The standard fix is aging: gradually increasing a waiting process's priority the longer it waits, guaranteeing it eventually runs.

Production operating systems (Linux's CFS, for instance) don't use any one textbook algorithm purely — they use adaptive schemes with multiple priority queues, where a process's effective priority shifts based on its observed behavior: a process that frequently blocks on I/O (interactive, latency-sensitive) gets boosted toward faster response, while a process that continuously burns CPU (batch/compute-heavy) gets throttled toward throughput-oriented scheduling instead. This blends round robin's fairness, priority scheduling's responsiveness, and aging's starvation protection into one adaptive system.