CPU scheduling decides which Ready process gets the CPU next. A good scheduler maximises CPU utilisation and throughput while minimising waiting time, turnaround time and response time. Schedulers are non-preemptive (a process keeps the CPU until it blocks or finishes) or preemptive (the OS can take the CPU away).
The metrics you must know
Burst time: CPU time a process needs. Waiting time: time in the Ready queue. Turnaround time: completion − arrival. Response time: arrival to first run. Most questions ask you to compute average waiting or turnaround time.
The core algorithms
| Algorithm | Idea | Preemptive? |
|---|---|---|
| FCFS | first come, first served | No |
| SJF | shortest job first | No |
| SRTF | shortest remaining time first | Yes |
| Round Robin | fixed time slice each, cyclic | Yes |
| Priority | highest priority first | either |
⚡ The edge
- SJF gives the minimum average waiting time — but needs burst times in advance and can starve long jobs. Round Robin is the fair, responsive choice for time-sharing, tuned by the time quantum.
- A tiny RR quantum means many context switches (overhead); a huge quantum makes RR behave like FCFS.
Worked example
Three processes arrive together with burst times 4, 3, 5. Find the average waiting time under FCFS.
- FCFS runs them in order. P1 waits 0; P2 waits 4 (after P1); P3 waits 4+3 = 7.
- Average waiting time = (0 + 4 + 7) / 3 = 11/3.
- So the average waiting time is about 3.67 units.
Answer: Average waiting time = 11/3 ≈ 3.67
Worked example
'Why can SJF cause starvation, and how is it fixed?'
- SJF always picks the shortest job, so if short jobs keep arriving, a long job may never be chosen.
- That indefinite postponement is starvation.
- The fix is aging: gradually raise a waiting process's priority so it eventually runs.
Answer: SJF starves long jobs when short ones keep arriving; aging fixes it.
⚠ Watch out
- Turnaround = waiting + burst and turnaround = completion − arrival — mixing these breaks the arithmetic.
- FCFS suffers the convoy effect: one long job delays many short ones behind it.
- Round Robin's performance hinges entirely on the time quantum.