CPU scheduling: FCFS and shortest job first
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.
Python
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]