CPU Scheduling Algorithms

The Waiting Room Analogy

Every service queue has a policy. A deli counter says "take a number" — first come, first served. A dentist might schedule the shortest appointment first to maximize patient flow. A co-working space gives everyone a 10-minute slot on the printer, then rotates. A VIP lounge sends priority members to the front.

CPU scheduling algorithms are those queue policies applied to processes competing for the CPU. Each solves a different problem, and each introduces its own tradeoffs.

1. First-Come, First-Served (FCFS)

Policy: The process that arrives first gets the CPU first. Non-preemptive — once a process starts, it runs to completion (or until it blocks on I/O).

Example

Gantt Chart (arrival order: P1, P2, P3):

Waiting Times:

• P1: 0 ms
• P2: 24 ms
• P3: 27 ms
• Average: 17 ms

The Convoy Effect

The major problem with FCFS: if a long CPU-bound process arrives first, all short processes pile up behind it. This is the convoy effect — short jobs are stuck behind a slow "convoy leader," just like cars behind a slow truck on a single-lane road. Average waiting time skyrockets.

2. Shortest Job First (SJF)

Policy: Always run the process with the shortest next CPU burst. Provably optimal for minimizing average waiting time.

Non-Preemptive SJF Example

Same processes, but now scheduled shortest-first:

Gantt Chart:

Waiting Times:

• P1: 6 ms
• P2: 0 ms
• P3: 3 ms
• Average: 3 ms (vs 17 ms for FCFS — dramatic improvement)

The Prediction Problem

SJF requires knowing the next CPU burst length in advance. Processes do not declare their burst time. In practice, the OS predicts it using an exponential average of past burst lengths:

τ(n+1) = α × t(n) + (1−α) × τ(n)

Where t(n) is the actual last burst, τ(n) is the previous prediction, and α (typically 0.5) controls how much weight recent history gets.

Preemptive SJF: Shortest Remaining Time First (SRTF)

If a new process arrives with a shorter burst than the currently running process, the scheduler preempts the current process and switches to the shorter one. This further minimizes average waiting time but adds context-switch overhead.

3. Round Robin (RR)

Policy: Each process gets a fixed time quantum (slice) of CPU time, then is preempted and placed at the back of the ready queue. Fair, preemptive, and designed for interactive systems.

Example — Time Quantum = 4 ms

Processes: P1 (burst=24), P2 (burst=3), P3 (burst=3), P4 (burst=12)

All arrive at time 0.

Wait — let's trace carefully:

• t=0–4: P1 runs (4 ms used, 20 remaining)
• t=4–7: P2 runs (3 ms burst complete — finishes)
• t=7–10: P3 runs (3 ms burst complete — finishes)
• t=10–14: P4 runs (4 ms used, 8 remaining)
• t=14–18: P1 runs (4 ms used, 16 remaining)
• t=18–22: P4 runs (4 ms used, 4 remaining)
• t=22–26: P1 runs (4 ms used, 12 remaining)
• t=26–30: P4 runs (4 ms used — P4 finishes at t=30)
• t=30–34: P1 runs (4 ms used, 8 remaining)
• t=34–38: P1 runs (4 ms used, 4 remaining)
• t=38–42: P1 runs — P1 finishes at t=42

Effect of Time Quantum Size:

Rule of thumb: 80% of CPU bursts should be shorter than the time quantum.

4. Priority Scheduling

Policy: Each process has a priority number. The CPU is always given to the highest-priority process. Can be preemptive or non-preemptive. Convention varies: some systems use lower number = higher priority (Linux, Unix); others use higher number = higher priority.

Example

Gantt Chart (non-preemptive, all arrive at t=0):

Average Waiting Time: (0 + 1 + 6 + 16 + 18) / 5 = 8.2 ms

Starvation Problem

If high-priority processes continuously arrive, low-priority processes may never run. A process submitted on Monday might still be waiting on Friday. This is starvation.

Solution: Aging. Gradually increase the priority of waiting processes over time. A process waiting for 15 minutes gets a priority boost. After long enough waiting, even a low-priority process becomes high-priority and eventually runs.

Algorithm Comparison Table

Choosing the Right Algorithm

• Batch systems (payroll, backups): FCFS or SJF — throughput matters, interactivity does not
• Interactive systems (desktop, shell): Round Robin — every user gets a response within one quantum cycle
• Real-time systems (embedded, medical): Priority with hard deadlines — correctness requires timely execution
• General-purpose OS (Linux, Windows): Multilevel feedback queue combining multiple algorithms for different process types

In practice, no real OS uses a single pure algorithm. Linux's CFS (Completely Fair Scheduler) and Windows' multilevel priority scheduler both combine elements of Round Robin, priority scheduling, and dynamic priority adjustment to handle the diversity of real workloads.