2.2FCFS, SJF and SRTF
The idea
FCFS runs processes in arrival order. SJF picks the shortest burst; SRTF is the preemptive form that preempts when a newcomer is shorter than the remaining time.
Think of it like this: The express lane at a supermarket: let the people with few items go first and the average wait falls, but someone with a full trolley may wait forever.
Why it exists
Short jobs make the average waiting time smaller: SJF/SRTF are provably optimal for it. FCFS is simple but suffers the convoy effect.
How it works
- FCFS: sort by arrival, run each to completion.
- SJF: when the CPU frees, choose the ready process with the shortest burst.
- SRTF: at every arrival, compare the new burst with the remaining time of the running process.
- Ties: use arrival order.
Worked example: P1(0,8) P2(1,4) P3(2,9) P4(3,5), SRTF
Run P1 to 1, P2 (4) preempts to 5, P4 (5) to 10, P1 (7 left) to 17, P3 to 26. Waiting: P1 9, P2 0, P3 15, P4 2, average 6.5.
Now play with it
- →Select SRTF and read the average waiting time: 6.5.
- →Switch to FCFS and see it go up (8.75). Load the convoy preset to see why.
| Process | Arrival | Burst | Completion | Turnaround | Waiting | Response |
|---|---|---|---|---|---|---|
| P1 | 0 | 8 | 17 | 17 | 9 | 0 |
| P2 | 1 | 4 | 5 | 4 | 0 | 0 |
| P3 | 2 | 9 | 26 | 24 | 15 | 15 |
| P4 | 3 | 5 | 10 | 7 | 2 | 2 |
Turnaround = completion − arrival. Waiting = turnaround − burst. Response = first run − arrival. Ties go to the earlier arrival, then the earlier row. In round robin, a process that arrives while another runs joins the queue before the preempted one.
| Policy | Preemptive? | Starvation? | Notes |
|---|---|---|---|
| FCFS | no | no | convoy effect |
| SJF | no | yes (long jobs) | minimum average waiting among non-preemptive |
| SRTF | yes | yes (long jobs) | minimum average waiting overall, needs burst prediction |
| Priority | either | yes (low priority) | fix with aging |
| Round robin | yes | no | good response time |
Check yourself
Which policy gives the minimum average waiting time for a known set of bursts?
Exam notes (the dense version)
FCFS: first come first served, non-preemptive, simple but suffers the convoy effect (short jobs stuck behind a long one). SJF: shortest next burst first, non-preemptive, gives the minimum average waiting time among non-preemptive policies. SRTF: the preemptive version: when a new process arrives with a burst shorter than the remaining time of the running one, it preempts. Both can starve long jobs, and the burst length must be predicted (exponential averaging).
Previous year questions: CPU Scheduling (13)
PYQs are grouped by topic, so this is the full set for CPU Scheduling; try the ones that match this subtopic. Open all 13 on the topic page.