CPU Scheduling: FCFS, SJF, SRTF, Round Robin, and Priority

When more processes are ready than there are CPUs, the scheduler decides who runs next. The policy it uses shapes throughput, latency, and fairness. Interviewers expect you to compute waiting and turnaround times by hand, compare algorithms, and reason about their failure modes.

The vocabulary you must nail

• Arrival time (AT): when a process enters the ready queue.
• Burst time (BT): CPU time the process needs for this run.
• Completion time (CT): when it finishes.
• Turnaround time (TAT): CT − AT — total time from arrival to completion.
• Waiting time (WT): TAT − BT — time spent ready but not running.
• Response time (RT): first time it gets the CPU − AT — critical for interactivity.
• Throughput: processes completed per unit time.

A subtle but favorite distinction: response time measures how quickly a job starts getting served; turnaround measures how quickly it finishes. Interactive systems optimize response time; batch systems optimize turnaround and throughput.

Preemptive vs non-preemptive

• Non-preemptive: once a process gets the CPU it keeps it until it finishes or blocks (FCFS, SJF).
• Preemptive: the scheduler can forcibly take the CPU back (SRTF, Round Robin, preemptive Priority). Preemption enables responsiveness but costs context switches.

First-Come, First-Served (FCFS)

The simplest policy: a FIFO queue. Whoever arrives first runs first, to completion. It is non-preemptive.

Strength: trivial, fair in arrival order, no starvation.

Weakness — the convoy effect: one long job at the front makes every short job behind it wait. If a 100-unit job arrives just before three 1-unit jobs, the short jobs wait ~100 units each, wrecking average waiting time even though total work is small.

Shortest Job First (SJF) and Shortest Remaining Time First (SRTF)

SJF (non-preemptive): among processes that have arrived, run the one with the smallest burst time. SJF is provably optimal for minimizing average waiting time among non-preemptive policies.

SRTF (preemptive SJF): whenever a new process arrives, compare its burst to the remaining time of the running process; if the newcomer is shorter, preempt. SRTF minimizes average waiting time overall but preempts frequently.

The catch — starvation: in a busy system a stream of short jobs can indefinitely delay a long job. And you cannot know the future — real schedulers estimate the next burst with an exponential average of past bursts: τ(n+1) = α·t(n) + (1−α)·τ(n), where t(n) is the last measured burst and α (often 0.5) weights recent history.

Round Robin (RR)

RR is FCFS with preemption on a time quantum. Each process runs for at most one quantum q, then goes to the back of the ready queue. It is the workhorse of time-sharing systems.

The quantum is the key tuning knob:

• Too large: RR degenerates into FCFS (the convoy effect returns).
• Too small: excessive context switches waste CPU on overhead.
• Rule of thumb: set q so ~80% of bursts finish within one quantum; typical values are 10–100 ms.

RR gives excellent response time and no starvation, at the cost of higher average turnaround than SJF.

Priority scheduling

Each process gets a priority; the CPU goes to the highest-priority ready process. It can be preemptive or non-preemptive, and priorities can be static or dynamic.

The problem — starvation of low-priority jobs. The fix — aging: gradually raise the priority of a job the longer it waits, guaranteeing it eventually runs. A famous anecdote: an MIT machine shut down in 1973 was found to have a low-priority job that had been waiting since 1967.

Priority inversion is a related trap: a high-priority task waits on a lock held by a low-priority task, which itself is preempted by a medium-priority task — effectively the medium task blocks the high one. The classic remedy is priority inheritance (the lock holder temporarily inherits the waiter's priority). This bug famously affected the 1997 Mars Pathfinder mission.

Worked comparison

Consider four processes; step through each algorithm's Gantt chart below:

Trace the FCFS case by hand to build intuition. Order of completion is P1, P2, P3, P4 (by arrival):

| Process | AT | BT | CT | TAT = CT−AT | WT = TAT−BT | |---------|----|----|----|-------------|-------------| | P1 | 0 | 7 | 7 | 7 | 0 | | P2 | 2 | 4 | 11 | 9 | 5 | | P3 | 4 | 1 | 12 | 8 | 7 | | P4 | 5 | 4 | 16 | 11 | 7 |

Average waiting time under FCFS = (0 + 5 + 7 + 7) / 4 = 4.75. Under SRTF the short P3 preempts and averages drop noticeably — that is the payoff of shortest-remaining-time, and the widget lets you confirm it.

Multilevel and MLFQ

Real systems combine policies. A multilevel queue partitions processes into fixed classes (e.g., system, interactive, batch), each with its own algorithm. A multilevel feedback queue (MLFQ) lets processes move between queues: a job that uses its whole quantum drops to a lower-priority, longer-quantum queue (assumed CPU-bound), while a job that yields early stays high (assumed interactive). MLFQ approximates SJF without knowing burst times in advance and is close to what Linux, Windows, and macOS actually do.

Comparison at a glance

| Algorithm | Preemptive | Optimizes | Starvation | Weakness | |-----------|-----------|-----------|------------|----------| | FCFS | No | Simplicity | No | Convoy effect | | SJF | No | Avg waiting | Yes | Needs burst estimate | | SRTF | Yes | Avg waiting | Yes | Frequent preemption | | Round Robin | Yes | Response time | No | Turnaround; quantum tuning | | Priority | Either | Importance | Yes (fix: aging) | Priority inversion |

Common follow-ups

• "Which minimizes average waiting time?" SRTF (preemptive SJF) overall; SJF among non-preemptive policies.
• "Why not always use SJF?" You cannot know future burst lengths, and it starves long jobs.
• "How do you pick the RR quantum?" Large enough that most bursts complete in one slice, small enough for responsiveness — balance overhead against latency.
• Gotcha: turnaround time is never less than burst time, and waiting time is never negative. If your arithmetic produces those, recheck the Gantt chart.