Shortest Job First, its preemptive version Shortest Remaining Time First, and priority scheduling are the three algorithms after FCFS that every operating-systems course asks about. This page works the standard textbook examples (from Silberschatz's Operating System Concepts) with Gantt charts and every time you'd be asked for.
The formulas, for each process:
turnaround time = completion time − arrival time
waiting time = turnaround time − burst time
response time = first time on the CPU − arrival time
SJF (non-preemptive): shortest burst first
All four processes arrive at time 0, with bursts P1 = 6, P2 = 8, P3 = 7, P4 = 3. SJF runs the shortest available burst to completion, then picks again.
| P4 | P1 | P3 | P2 |
0 3 9 16 24
| Process | Burst | Completion | Turnaround | Waiting |
|---|---|---|---|---|
| P1 | 6 | 9 | 9 | 3 |
| P2 | 8 | 24 | 24 | 16 |
| P3 | 7 | 16 | 16 | 9 |
| P4 | 3 | 3 | 3 | 0 |
Average waiting time = (3 + 16 + 9 + 0) ÷ 4 = 7. FCFS in the order P1, P2, P3, P4 gives 10.25 for the same processes. SJF gives the minimum average waiting time of any non-preemptive schedule; the catch is that real systems don't know burst lengths in advance and have to predict them.
SRTF (preemptive SJF): shortest remaining time
Now the processes arrive at different times: P1 (arrives 0, burst 8), P2 (1, 4), P3 (2, 9), P4 (3, 5). SRTF re-decides whenever a process arrives: if the newcomer's burst is shorter than what the running process has left, it takes over.
| P1 | P2 | P4 | P1 | P3 |
0 1 5 10 17 26
- At 1, P2 arrives needing 4; P1 has 7 left, so P2 preempts it.
- At 2 and 3, P3 (9) and P4 (5) arrive, but P2's remaining time is smaller, so P2 finishes at 5.
- At 5, P4 (5) beats P1 (7) and P3 (9). Then P1, then P3.
| 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 |
Average waiting time = (9 + 0 + 15 + 2) ÷ 4 = 6.5. Non-preemptive SJF on the same processes runs P1 to completion first (it's the only one there at time 0) and averages 7.75.
Priority scheduling (non-preemptive)
All arrive at 0. A lower number means a higher priority (the textbook convention; some courses use the opposite, so check).
| Process | Burst | Priority |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
| P2 | P5 | P1 | P3 | P4 |
0 1 6 16 18 19
| Process | Completion | Turnaround | Waiting |
|---|---|---|---|
| P1 | 16 | 16 | 6 |
| P2 | 1 | 1 | 0 |
| P3 | 18 | 18 | 16 |
| P4 | 19 | 19 | 18 |
| P5 | 6 | 6 | 1 |
Average waiting time = (6 + 0 + 16 + 18 + 1) ÷ 5 = 8.2.
The weakness is starvation: a low-priority process can wait forever if higher-priority work keeps arriving. The usual fix is aging, gradually raising the priority of processes that have waited a long time.
Ties and conventions
- Equal bursts or priorities: break the tie by arrival time, then by process number (first come, first served).
- Preemptive priority works like SRTF but compares priorities: a newly arrived higher-priority process takes the CPU.
- Idle time: if no process has arrived yet, the CPU is idle; show it as a gap in the Gantt chart.
Common mistakes
- Using SJF's order with SRTF's arrivals. In non-preemptive SJF, a process that started keeps the CPU even when a shorter one arrives.
- Subtracting from 0 instead of the arrival time for turnaround in SRTF.
- Mixing up "high priority" and "high number". State which convention you use.
- Forgetting that waiting time includes every gap, not just the time before the first run, for preempted processes like P1 in SRTF.
Check your own answers
The CPU scheduling calculator runs FCFS, SJF, SRTF, priority (preemptive and non-preemptive) and round robin on your processes, draws the Gantt chart and gives completion, turnaround, waiting and response times with the averages. For time slices, see the round robin example.
Use the Memory Allocation Calculator to compare memory-allocation examples in the same operating systems course.