CPU Scheduling Algorithms: Complete Beginner's Guide

CPU scheduling is how the operating system decides which process gets the processor and for how long. With one CPU (or a few cores) and dozens of waiting processes, the scheduler picks an order that keeps the system responsive, fair and efficient. The scheduling algorithm is the rule it uses to choose.

It matters because scheduling decides the feel of a computer. A good scheduler keeps your video call smooth while a backup runs; a bad one makes everything stutter. In servers and real-time systems, scheduling choices directly decide throughput and whether deadlines are met.

Key Concepts

• Process: a running program, with an arrival time (when it becomes ready) and a burst time (CPU time it needs).
• Turnaround time: total time from arrival to completion. Waiting time: time spent in the ready queue without the CPU.
• Preemptive vs non-preemptive: a preemptive scheduler can interrupt a running process; a non-preemptive one lets it finish its burst.
• FCFS (First-Come, First-Served): runs in arrival order. Simple, but a long job blocks everyone behind it (convoy effect).
• SJF (Shortest Job First): runs the shortest burst next, minimising average waiting time — but long jobs can starve.
• Round Robin: gives each process a fixed time slice (quantum) in rotation. Fair and responsive; too large a quantum behaves like FCFS, too small wastes time on context switches.
• Priority scheduling: runs the highest-priority process first; needs aging (raising waiters' priority over time) to avoid starvation.

Formulas

• Turnaround time = Completion time − Arrival time, in milliseconds or any consistent unit.
• Waiting time = Turnaround time − Burst time — the metric schedulers most often minimise.
• Average waiting time = (sum of waiting times) ÷ (number of processes). Lower is better for a given workload.
• Assumes burst times are known (in practice the OS estimates them) and a single CPU.

Worked Example

FCFS scheduling with P1 (arrives 0, burst 5), P2 (arrives 1, burst 3), P3 (arrives 2, burst 4). Compute waiting times and the average.

1. Order: P1, P2, P3. Completions: P1 = 5, P2 = 8, P3 = 12.
2. Turnarounds: P1 = 5 − 0 = 5; P2 = 8 − 1 = 7; P3 = 12 − 2 = 10.
3. Waiting: P1 = 5 − 5 = 0; P2 = 7 − 3 = 4; P3 = 10 − 4 = 6. Average = 10 / 3 ≈ 3.33 ms.

P1 never waits, but P3 waits 6 ms — stuck behind P1's long burst. That is the convoy effect in numbers, and exactly what SJF and Round Robin soften.

Common Misconceptions

• "Shortest Job First is always best." It minimises average waiting only when all jobs are available and bursts known — otherwise it risks starving long jobs.
• "A bigger Round Robin quantum is always better." A huge quantum degenerates into FCFS; a tiny one drowns the CPU in context switches. Tuning the quantum is the art.
• "Scheduling only matters on servers." Your phone's scheduler juggles the UI, radio, sensors and apps every millisecond — that smoothness is scheduling too.

Real-World Applications

• Desktop and mobile OSes use multilevel feedback queues (refined Round Robin) to keep interfaces snappy.
• Servers tune schedulers for throughput and fairness across thousands of requests.
• Real-time systems (airbags, factory robots) use deadline-driven schedulers where a miss is a failure.

CPU scheduling is the OS's traffic control for the processor: FCFS is fair but convoy-prone, SJF is efficient but can starve, Round Robin shares fairly via time slices, and priority scheduling serves the urgent first. Measure any of them with turnaround and waiting time.