CPU Scheduling Algorithms
How the OS picks which process runs next. FCFS, SJF, Round Robin and priority scheduling are worked through on the same four processes, with average waiting and turnaround times computed by code.
A CPU scheduling algorithm decides which ready process runs next: FCFS runs in arrival order, SJF runs the shortest burst first, Round Robin gives each process a fixed time slice, and priority scheduling runs the most important first. The detail interviewers expect: SJF gives the lowest average waiting time when all jobs arrive together, but can starve long jobs.
A CPU scheduler decides which ready process gets the CPU next. FCFS runs in arrival order, SJF runs the shortest job first and minimises average waiting time, Round Robin gives each process a fixed time slice, and priority scheduling runs the most important first. Each trades fairness, response time and throughput differently.
- Turnaround time is completion time minus arrival time, and waiting time is turnaround minus the time actually spent running on the CPU.
- On four processes with bursts 8, 4, 9 and 5, FCFS gave an average waiting time of 8.75, non-preemptive SJF gave 7.75, and Round Robin with quantum 3 gave 13.5.
- The convoy effect in FCFS scheduling happens when a long CPU-bound job at the front of the queue makes short jobs wait behind it.
- In Round Robin scheduling, a very large quantum makes it behave like FCFS and a very small quantum wastes CPU time on context switches.
- Starvation in priority scheduling, where a low-priority process never runs, is prevented by aging, which raises a process's priority the longer it waits.
- Linux used the Completely Fair Scheduler for years and replaced it with EEVDF starting in kernel 6.6.
01What the scheduler is optimising
When several processes are ready, the scheduler picks one. The definitions you need:
Turnaround time is completion time minus arrival time. Waiting time is turnaround minus the time spent actually running, so it is the time spent in the ready queue. Response time is the time from arrival to the first time the process gets the CPU. Throughput is how many processes finish per unit of time.
Batch systems care about throughput and turnaround. Interactive systems care about response time, since a user notices a slow click far more than a slow report. There is no algorithm that is best at everything.
02The example used throughout
A burst time is how long the process needs the CPU. All times below are in arbitrary units.
Process Arrival Burst
P1 0 8
P2 1 4
P3 2 9
P4 3 5I wrote a small simulator for each algorithm and ran it on this data. The numbers in the sections below are its output, so you can verify them by drawing the Gantt chart by hand.
03First Come First Served (FCFS)
FCFS is a plain queue and does not interrupt a running process. Order: P1 (0 to 8), P2 (8 to 12), P3 (12 to 21), P4 (21 to 26).
Waiting times are P1 0, P2 7, P3 10, P4 18, so the average waiting time is 8.75, and the average turnaround is 15.25.
The problem is the convoy effect. A long CPU-bound job at the front makes short jobs queue behind it, so average waiting time can be poor and interactive jobs feel sluggish.
04Shortest Job First (SJF)
Non-preemptive SJF: P1 starts at 0 because it is the only one there. At time 8, P2 (4), P3 (9) and P4 (5) are waiting. It picks P2, then P4, then P3. Order: P1, P2, P4, P3.
Waiting times are P1 0, P2 7, P4 9, P3 15. The average waiting time is 7.75, better than FCFS's 8.75, and the average turnaround is 14.25.
SJF has the lowest average waiting time of any non-preemptive algorithm when all jobs are available at once; with staggered arrivals, as here, it is a strong heuristic rather than a guarantee. Its problems are practical. The OS does not know in advance how long a job will run, so real systems estimate from past behaviour. And a stream of short jobs can starve a long one forever. The preemptive version (Shortest Remaining Time First) switches whenever a shorter job arrives.
05Round Robin
Round Robin is made for interactive systems. With a quantum of 3, no process waits more than a few slices before it runs again, so response time is good.
On our data, with a new arrival queued ahead of a process that has just used up its slice, the finishing times are P2 at 16, P4 at 21, P1 at 23 and P3 at 26. The average waiting time is 13.5 and average turnaround is 20, much worse than FCFS or SJF on this batch-style data. That is the price. Round Robin is not trying to minimise waiting. It is trying to give everyone a turn quickly.
The quantum matters. A very large quantum turns Round Robin into FCFS. A very small one wastes time on context switches. A common guidance is to choose a quantum so that most short interactions finish within one slice, while keeping switching overhead a small fraction of the slice.
06Priority scheduling, starvation and aging
Each process has a priority, and the scheduler picks the highest. Priorities can come from the system (a real-time task beats a background one) or from the user (nice values on Linux).
The danger is starvation: a steady supply of high-priority jobs means a low-priority job never runs. The standard fix is aging, which slowly raises the priority of a process the longer it waits.
Real operating systems combine ideas. A multilevel feedback queue uses several queues with different priorities and quanta, and moves a process between them based on its behaviour: a process that uses its whole slice drops down, one that blocks on I/O stays high. Linux used the Completely Fair Scheduler for years, which tracks how much CPU time each task has received and runs the one that has had the least, and replaced it with EEVDF starting in kernel 6.6.
07Common interview questions
Q: Which algorithm gives the minimum average waiting time?
A: SJF, and SRTF if preemption is allowed, but both need to know burst times in advance.
Q: What is the convoy effect?
A: Short processes stuck behind a long one in FCFS, which increases average waiting time.
Q: What is starvation and how is it prevented?
A: A process never gets the CPU because others always win. Aging, which raises priority with waiting time, prevents it.
Q: How does the quantum affect Round Robin?
A: Too large and it behaves like FCFS. Too small and context switching eats the CPU.
Q: Preemptive versus non-preemptive?
A: Preemptive schedulers can take the CPU away from a running process (timer interrupt, higher priority arrival). Non-preemptive ones wait until it finishes or blocks.