Compare FCFS, SJF, SRTF and Round Robin with a worked example.
Short answer: FCFS runs jobs in arrival order (simple, but short jobs wait behind long ones). SJF picks the shortest next CPU burst (optimal average waiting time if bursts are known, non-pre-emptive). SRTF is the pre-emptive version: a newly arrived job pre-empts the current one if its burst is shorter than the remaining time. Round Robin gives each job a fixed time slice in turn (fair, good response time; performance depends on the quantum).
Example processes (times in ms)
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
Waiting time = finish − arrival − burst.
FCFS
| P1 0-8 | P2 8-12 | P3 12-21 | P4 21-26 |
Waiting: P1 0, P2 7, P3 10, P4 18 → average 8.75 ms.
SJF (non-pre-emptive): at t = 0 only P1 is there, so it runs to completion. At t = 8 the shortest is P2 (4), then P4 (5), then P3 (9).
| P1 0-8 | P2 8-12 | P4 12-17 | P3 17-26 |
Waiting: P1 0, P2 7, P4 9, P3 15 → average 7.75 ms.
SRTF (pre-emptive SJF): at t = 1, P2 (4) is shorter than P1's remaining 7, so P2 pre-empts.
| P1 0-1 | P2 1-5 | P4 5-10 | P1 10-17 | P3 17-26 |
Waiting: P1 17−0−8 = 9, P2 0, P3 15, P4 2 → average 6.5 ms (the best of the four).
Round Robin, quantum 4 ms (new arrivals join the queue before a pre-empted job is re-queued)
| P1 0-4 | P2 4-8 | P3 8-12 | P4 12-16 | P1 16-20 | P3 20-24 | P4 24-25 | P3 25-26 |
Finish: P1 20, P2 8, P3 26, P4 25. Waiting: P1 12, P2 3, P3 15, P4 17 → average 11.75 ms, worse average waiting, but every job got the CPU within 12 ms of arriving (best worst-case response).
Comparison
| Algorithm | Pre-emptive | Avg waiting | Starvation? | Notes |
|---|---|---|---|---|
| FCFS | no | poor (convoy effect) | no | simplest |
| SJF | no | optimal among non-pre-emptive | yes, for long jobs | needs burst prediction |
| SRTF | yes | optimal | yes | more context switches |
| RR | yes | often worse | no | response time bounded by (n−1) × quantum |
| Priority | either | depends | yes, fixed by aging | RTOS default |
Predicting bursts: real schedulers do not know burst lengths, so SJF uses an exponential average of previous bursts: τ(n+1) = α·t(n) + (1−α)·τ(n).
Related: SETF (shortest elapsed time first) picks the job that has run the least so far. It needs no prediction and favours new and short jobs, the idea behind multilevel feedback queues: new jobs start at high priority and sink as they use CPU time.
Quantum choice for RR: too small → overhead dominates; too large → becomes FCFS. A rule of thumb: 80% of CPU bursts should be shorter than the quantum.