CPU scheduling: FCFS and shortest job first
Compare average waiting time when the scheduler runs jobs in arrival order or by shortest burst.
jobs = [("P1", 0, 8), ("P2", 1, 4), ("P3", 2, 9), ("P4", 3, 5)]
def simulate(jobs, pick):
time = 0
pending = sorted(jobs, key=lambda job: job[1])
waits = {}
order = []
while pending:
ready = [job for job in pending if job[1] <= time]
if not ready:
time = min(job[1] for job in pending)
continue
job = pick(ready)
pending.remove(job)
name, arrival, burst = job
waits[name] = time - arrival
time += burst
order.append(name)
return order, sum(waits.values()) / len(waits)
fcfs = simulate(jobs, lambda ready: min(ready, key=lambda job: job[1]))
sjf = simulate(jobs, lambda ready: min(ready, key=lambda job: (job[2], job[1])))
print(fcfs)
print(sjf)
assert sjf[1] < fcfs[1](['P1', 'P2', 'P3', 'P4'], 8.75) (['P1', 'P2', 'P4', 'P3'], 7.75)
Explanation
The CPU scheduler decides which ready process runs next. Common goals are high CPU utilization, high throughput, and low waiting time, which is the total time a process spends in the ready queue. In a non-preemptive policy a running process keeps the CPU until it finishes or blocks.
First-come, first-served (FCFS) runs jobs in arrival order. It is simple and fair in the sense of ordering, but a long job at the front delays every short job behind it, which is called the convoy effect. Shortest job first (SJF) always picks the ready job with the smallest next CPU burst. For a set of jobs that are all available at the same time, SJF gives the minimum average waiting time.
The program simulates both policies for four jobs written as (name, arrival time, burst time). The simulator advances a clock, picks a job from the ready jobs using the policy, records how long it waited, and runs it to completion. SJF improves the average waiting time from 8.75 to 7.75 time units. Real kernels cannot know the next burst in advance, so they estimate it or use other policies such as multilevel feedback queues and fair-share schedulers.
Explore the dry run
jobs = [("P1", 0, 8), ("P2", 1, 4), ("P3", 2, 9), ("P4", 3, 5)] def simulate(jobs, pick): time = 0 pending = sorted(jobs, key=lambda job: job[1]) waits = {} order = [] while pending: ready = [job for job in pending if job[1] <= time] if not ready: time = min(job[1] for job in pending) continue job = pick(ready) pending.remove(job) name, arrival, burst = job waits[name] = time - arrival time += burst order.append(name) return order, sum(waits.values()) / len(waits) fcfs = simulate(jobs, lambda ready: min(ready, key=lambda job: job[1]))sjf = simulate(jobs, lambda ready: min(ready, key=lambda job: (job[2], job[1])))print(fcfs)print(sjf)assert sjf[1] < fcfs[1]Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| At each decision the scheduler considers only jobs that have already arrived. | time = 0: ready = [P1] | — | |
| A job's waiting time is the clock when it starts minus its arrival time. | P2 starts at 8, arrived at 1: waits 7 | — | |
| SJF breaks the tie by burst length: after P1 it runs P2 (4), then P4 (5), then P3 (9). | P2 starts at 8, arrived at 1: waits 7 | — | |
| FCFS waits: 0, 7, 10, 18, an average of 35 / 4 = 8.75. | P2 starts at 8, arrived at 1: waits 7 | (['P1', 'P2', 'P3', 'P4'], 8.75) | |
| SJF waits: 0, 7, 15, 9, an average of 31 / 4 = 7.75. | P2 starts at 8, arrived at 1: waits 7 | (['P1', 'P2', 'P3', 'P4'], 8.75) (['P1', 'P2', 'P4', 'P3'], 7.75) |
Cost and common mistakes
The simulation scans the pending list at every step, so it is O(n²) for n jobs. A real scheduler would keep a priority queue.
- SJF can starve long jobs when short jobs keep arriving. Real schedulers add aging or other fairness rules.
- SJF requires knowing the next burst length, which a real operating system must predict.
- The optimality of SJF is for average waiting time over jobs that are all available. With arrivals over time, the preemptive version (shortest remaining time first) is the optimal one.
Try it yourself
Why does P3 wait 15 under SJF but only 10 under FCFS?
Reveal answer and reasoning
SJF lets the shorter jobs P2 and P4 run before the long job P3, so P3 starts at 17 instead of 12. Its wait rises, but the total waiting time of all jobs falls.