CPU scheduling: FCFS and SJF
45 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A placement paper gives you four or five processes and asks for the average waiting time under FCFS and SJF. The examiner is checking your Gantt chart and three formulas, because one wrong cell spoils the whole average.
Terms: arrival, burst, waiting, turnaround and response time
Waiting time is the time a process spends in the ready queue without running; it equals turnaround time minus burst time.
The program below takes one process (arrives at 2, needs 5 ms, first runs at 6, finishes at 14) and applies the three formulas to it.
Example 1 · The three formulas for one process
arrival, burst, first_run, completion = 2, 5, 6, 14
turnaround = completion - arrivalwaiting = turnaround - burstresponse = first_run - arrival
print(f"Turnaround = {completion} - {arrival} = {turnaround}")print(f"Waiting = {turnaround} - {burst} = {waiting}")print(f"Response = {first_run} - {arrival} = {response}")Turnaround = 14 - 2 = 12 Waiting = 12 - 5 = 7 Response = 6 - 2 = 4
What this code does
- The process was in the system for 12 ms but ran for only 5, so it waited 7 ms in total.
- Response time (4) is smaller than waiting time (7) because the process was preempted after it started and waited again later.
Arrival time is when a process enters the ready queue, burst time is the CPU time it needs and completion time is when it finishes. From these: turnaround time (TAT) = completion − arrival, the total time in the system; waiting time = turnaround − burst; response time = first run − arrival, how long before it starts at all.
Write the three formulas at the top of your rough sheet before you start: every numerical uses them. Revise: Processes and threads (opens in a new tab)
FCFS with a Gantt chart and the convoy effect
Convoy effect is a queue of short processes stuck behind one long process, which raises the average waiting time sharply.
The program below runs FCFS on four processes and prints each start, finish, turnaround and waiting time, the Gantt chart and the averages. A second program then shows the convoy effect.
Example 2 · FCFS simulator with a Gantt chart
from dataclasses import dataclass
@dataclassclass Proc: name: str arrival: int burst: int
ps = [Proc("P1", 0, 8), Proc("P2", 1, 4), Proc("P3", 2, 9), Proc("P4", 3, 5)] # sorted by arrivaltime = total_wait = total_tat = 0gantt = "0"for p in ps: time = max(time, p.arrival) # CPU may be idle until arrival start = time time += p.burst tat = time - p.arrival wait = tat - p.burst total_tat += tat total_wait += wait gantt += f" [{p.name}] {time}" print(f"{p.name}: start {start}, finish {time}, TAT {tat}, WT {wait}")print("Gantt:", gantt)print(f"Average WT = {total_wait / len(ps):.2f}, average TAT = {total_tat / len(ps):.2f}")P1: start 0, finish 8, TAT 8, WT 0 P2: start 8, finish 12, TAT 11, WT 7 P3: start 12, finish 21, TAT 19, WT 10 P4: start 21, finish 26, TAT 23, WT 18 Gantt: 0 [P1] 8 [P2] 12 [P3] 21 [P4] 26 Average WT = 8.75, average TAT = 15.25
What this code does
max(time, p.arrival)handles a gap: if the next process has not arrived yet, the CPU sits idle until it does.- Average waiting is 35 ÷ 4 = 8.75. P4 waits 18 ms for a 5 ms job because of the long jobs ahead of it.
Example 3 · The convoy effect in numbers
def average_wait(bursts): # all arrive at time 0 time = total_wait = 0 for b in bursts: total_wait += time time += b return total_wait / len(bursts)
print("Long job first (24, 3, 3): avg WT =", average_wait([24, 3, 3]))print("Short jobs first (3, 3, 24): avg WT =", average_wait([3, 3, 24]))Long job first (24, 3, 3): avg WT = 17.0 Short jobs first (3, 3, 24): avg WT = 3.0
What this code does
- Same three jobs, same total work. Only the order changed, and the average wait fell from 17 to 3.
- This is why FCFS is weak when one long job arrives first, and why SJF exists.
First-come, first-served (FCFS) runs processes in order of arrival, each to completion. It is simple and fair in order, but non-preemptive: once a process starts, it keeps the CPU until it finishes. The convoy effect is its weakness, like scooters stuck behind a slow truck on a one-lane road.
FCFS cannot starve a process, because every process reaches the front of the queue. Its problem is long waits, not endless ones.
Find the bug
Find the first wrong line
Each working has one root mistake. Click the first wrong line.
FCFS for P1 (arrives 0, burst 4) and P2 (arrives 6, burst 2).
Round 1 of 2SJF and SRTF with worked averages
SJF (shortest job first) picks the ready process with the smallest burst time and runs it to completion; its preemptive form is SRTF.
The program below runs non-preemptive SJF and preemptive SRTF on the same four processes as before and prints each Gantt chart and average waiting time.
Example 4 · SJF and SRTF simulators
from dataclasses import dataclass
@dataclassclass Proc: name: str arrival: int burst: int
def sjf(ps): """Non-preemptive: when the CPU is free, run the shortest arrived job to completion.""" time, finish, gantt = 0, {}, "0" while len(finish) < len(ps): ready = [p for p in ps if p.name not in finish and p.arrival <= time] if not ready: time += 1 # CPU idle continue p = min(ready, key=lambda p: p.burst) # min keeps the earlier-listed one on ties time += p.burst finish[p.name] = time gantt += f" [{p.name}] {time}" return finish, gantt
def srtf(ps): """Every millisecond, run the arrived job with the least remaining time.""" left = {p.name: p.burst for p in ps} time, finish, gantt, last = 0, {}, "0", "" while len(finish) < len(ps): ready = [p for p in ps if left[p.name] > 0 and p.arrival <= time] now = min(ready, key=lambda p: left[p.name]).name if ready else "idle" if now != last and time > 0: gantt += f" [{last}] {time}" last = now time += 1 if now != "idle": left[now] -= 1 if left[now] == 0: finish[now] = time return finish, gantt + f" [{last}] {time}"
def report(title, ps, finish, gantt): tats = [finish[p.name] - p.arrival for p in ps] waits = [t - p.burst for t, p in zip(tats, ps)] print(f"{title}: {gantt}") print(f" avg waiting = {sum(waits) / len(ps):.2f}, avg turnaround = {sum(tats) / len(ps):.2f}")
ps = [Proc("P1", 0, 8), Proc("P2", 1, 4), Proc("P3", 2, 9), Proc("P4", 3, 5)]finish, gantt = sjf(ps)report("SJF ", ps, finish, gantt)finish, gantt = srtf(ps)report("SRTF", ps, finish, gantt)SJF : 0 [P1] 8 [P2] 12 [P4] 17 [P3] 26 avg waiting = 7.75, avg turnaround = 14.25 SRTF: 0 [P1] 1 [P2] 5 [P4] 10 [P1] 17 [P3] 26 avg waiting = 6.50, avg turnaround = 13.00
What this code does
sjfpicks the shortest arrived job only when the CPU is free;srtfre-checks every millisecond, so a newly arrived short job can take the CPU.- On the same data, FCFS averaged 8.75, SJF 7.75 and SRTF 6.50 waiting time.
minkeeps the earlier-listed (earlier-arrived) process on ties.
SJF gives the lowest average waiting time of all non-preemptive methods when every burst is known. Shortest remaining time first (SRTF) is the preemptive form: when a new process arrives with less remaining time than the running one, the running one goes back to the ready queue.
The catch for both: real systems do not know burst times in advance, so they estimate them from past bursts, and long jobs can starve (wait for a very long time). On a tie, pick the process that arrived first unless the question says otherwise.
Predict the output
Total waiting time
Three jobs arrive at time 0 with bursts 6, 2 and 4. Pick the total waiting time.
Round 1 of 2
SJF runs the shortest job first.
Preemptive vs non-preemptive scheduling
Preemptive scheduling lets the OS take the CPU away from a running process, for example when a shorter or higher-priority job arrives or its time slice ends.
In non-preemptive scheduling a process gives up the CPU only when it finishes or waits for I/O. The charts below show four processes (bursts 8, 4, 9 and 5) with and without preemption.
Non-preemptive SJF: 0 [P1] 8 [P2] 12 [P4] 17 [P3] 26SRTF (preemptive): 0 [P1] 1 [P2] 5 [P4] 10 [P1] 17 [P3] 26At t=1, P2 (4 left) beats P1 (7 left), so P1 is preempted.Preemption helps short jobs and response time. The price is more context switches, and shared data must be protected because a process can be interrupted at any moment. Revise: Synchronisation and semaphores (opens in a new tab)
Order of execution
How SRTF decides
Put the SRTF decisions for the chart above in order.
Worked numeric example with exact averages
Gantt chart is a timeline bar that shows which process held the CPU in each interval, from which every completion time is read.
The program below runs FCFS, SJF and SRTF on five processes: P1 (arrives 0, burst 3), P2 (2, 6), P3 (4, 4), P4 (6, 5) and P5 (8, 2). It prints each chart and its averages.
Example 5 · Worked example: FCFS, SJF and SRTF on five processes
from dataclasses import dataclass
@dataclassclass Proc: name: str arrival: int burst: int
def sjf(ps): """Non-preemptive: when the CPU is free, run the shortest arrived job to completion.""" time, finish, gantt = 0, {}, "0" while len(finish) < len(ps): ready = [p for p in ps if p.name not in finish and p.arrival <= time] if not ready: time += 1 # CPU idle continue p = min(ready, key=lambda p: p.burst) # min keeps the earlier-listed one on ties time += p.burst finish[p.name] = time gantt += f" [{p.name}] {time}" return finish, gantt
def srtf(ps): """Every millisecond, run the arrived job with the least remaining time.""" left = {p.name: p.burst for p in ps} time, finish, gantt, last = 0, {}, "0", "" while len(finish) < len(ps): ready = [p for p in ps if left[p.name] > 0 and p.arrival <= time] now = min(ready, key=lambda p: left[p.name]).name if ready else "idle" if now != last and time > 0: gantt += f" [{last}] {time}" last = now time += 1 if now != "idle": left[now] -= 1 if left[now] == 0: finish[now] = time return finish, gantt + f" [{last}] {time}"
def report(title, ps, finish, gantt): tats = [finish[p.name] - p.arrival for p in ps] waits = [t - p.burst for t, p in zip(tats, ps)] print(f"{title}: {gantt}") print(f" avg waiting = {sum(waits) / len(ps):.2f}, avg turnaround = {sum(tats) / len(ps):.2f}")
ps = [Proc("P1", 0, 3), Proc("P2", 2, 6), Proc("P3", 4, 4), Proc("P4", 6, 5), Proc("P5", 8, 2)]time, fcfs, gantt = 0, {}, "0"for p in ps: time = max(time, p.arrival) + p.burst fcfs[p.name] = time gantt += f" [{p.name}] {time}"report("FCFS", ps, fcfs, gantt)report("SJF ", ps, *sjf(ps))report("SRTF", ps, *srtf(ps))FCFS: 0 [P1] 3 [P2] 9 [P3] 13 [P4] 18 [P5] 20 avg waiting = 4.60, avg turnaround = 8.60 SJF : 0 [P1] 3 [P2] 9 [P5] 11 [P3] 15 [P4] 20 avg waiting = 3.60, avg turnaround = 7.60 SRTF: 0 [P1] 3 [P2] 4 [P3] 8 [P5] 10 [P2] 15 [P4] 20 avg waiting = 3.20, avg turnaround = 7.20
What this code does
- Check: in every row, average TAT − average WT = 4.00, the average burst (20 ÷ 5). Use this check in the exam to catch arithmetic slips.
- SRTF preempts P2 at time 4: P2 still needs 5 ms and the new P3 needs only 4. At 8, P5 (2 ms) beats P2 and P4 (5 ms each); at 10 the tie between P2 and P4 goes to P2, which arrived first.
FCFS completions are 3, 9, 13, 18 and 20, so its average waiting time is 4.6. Non-preemptive SJF runs P5 before P3 and P4 at time 9 and gets 3.6; SRTF lowers it to 3.2. Use the same routine for any numerical:
- Draw the Gantt chart, marking every arrival.
- Read off each completion time.
- TAT = completion − arrival; WT = TAT − burst.
- Average each column and check: average TAT − average WT = average burst.
Predict the output
The quick check
Use the check from the steps above.
Five processes: total turnaround 46 ms and total burst 20 ms. What is the average waiting time?
Next step
Check your understanding
12 quick questions