FCFS, SJF & SRTF Scheduling

By the end of this lesson you will be able to schedule a set of processes with FCFS, SJF and SRTF by hand and with Python, and explain why the shortest-job methods give lower waiting times.

You will use one set of four processes all the way through, so the comparison at the end is fair. Keep a notebook open and draw each Gantt chart yourself before you run the code. That habit is exactly what an exam needs.

FCFS: first come, first served

First Come, First Served (FCFS) runs processes in the order they arrive. It is non-preemptive: a process keeps the CPU until its burst is done. It works like a single ticket counter at a railway station: whoever joins the line first is served first, however long their booking takes.

Step 1: draw it by hand. P1 runs 0 to 6. P2 arrived at 1, so it runs 6 to 14. P3 runs 14 to 16. P4 runs 16 to 19.

Step 2: run the simulation and compare.

procs = [("P1", 0, 6), ("P2", 1, 8), ("P3", 2, 2), ("P4", 4, 3)]   # (name, arrival, burst)

def fcfs(procs):
    chart, clock = [], 0
    for name, at, bt in sorted(procs, key=lambda p: p[1]):
        if clock < at:                       # CPU idle until it arrives
            chart.append(("idle", clock, at))
            clock = at
        chart.append((name, clock, clock + bt))
        clock += bt
    return chart

def report(procs, chart):
    end = {n: e for n, s, e in chart if n != "idle"}
    total_wt = 0
    for name, at, bt in procs:
        tat = end[name] - at
        wt = tat - bt
        total_wt += wt
        print(f"{name}: CT={end[name]:2} TAT={tat:2} WT={wt:2}")
    print(f"Average WT = {total_wt / len(procs):.2f}")

chart = fcfs(procs)
print(chart)
report(procs, chart)

[('P1', 0, 6), ('P2', 6, 14), ('P3', 14, 16), ('P4', 16, 19)]
P1: CT= 6 TAT= 6 WT= 0
P2: CT=14 TAT=13 WT= 5
P3: CT=16 TAT=14 WT=12
P4: CT=19 TAT=15 WT=12
Average WT = 7.25

Look at P3. It needs only 2 units but waits 12, stuck behind the long P2. When many short processes queue behind one long CPU-bound process, it is called the convoy effect, like a line of scooters stuck behind a slow truck on a narrow ghat road.

FCFS is simple and never starves anyone, but its average waiting time is often poor. The code also handles idle time: if the next process has not arrived yet, the chart gets an idle block.

SJF: shortest job first

Shortest Job First (SJF) picks, among the processes that have already arrived, the one with the smallest burst time. This version is non-preemptive: once chosen, a job runs to the end. Ties are broken by earlier arrival.

Step 1: draw it by hand. At time 0 only P1 has arrived, so P1 runs 0 to 6. At time 6, P2 (8), P3 (2) and P4 (3) are all waiting. The shortest is P3, which runs 6 to 8. Then P4 runs 8 to 11, and P2 runs 11 to 19.

Step 2: check with the code.

procs = [("P1", 0, 6), ("P2", 1, 8), ("P3", 2, 2), ("P4", 4, 3)]

def sjf(procs):
    waiting = sorted(procs, key=lambda p: p[1])
    chart, clock = [], 0
    while waiting:
        ready = [p for p in waiting if p[1] <= clock]
        if not ready:                          # nothing has arrived yet
            nxt = waiting[0][1]
            chart.append(("idle", clock, nxt)); clock = nxt
            continue
        job = min(ready, key=lambda p: (p[2], p[1]))   # shortest burst, then earliest arrival
        waiting.remove(job)
        chart.append((job[0], clock, clock + job[2]))
        clock += job[2]
    return chart

def report(procs, chart):
    end = {n: e for n, s, e in chart if n != "idle"}
    total_wt = 0
    for name, at, bt in procs:
        wt = end[name] - at - bt
        total_wt += wt
        print(f"{name}: CT={end[name]:2} WT={wt:2}")
    print(f"Average WT = {total_wt / len(procs):.2f}")

chart = sjf(procs)
print(chart)
report(procs, chart)

[('P1', 0, 6), ('P3', 6, 8), ('P4', 8, 11), ('P2', 11, 19)]
P1: CT= 6 WT= 0
P2: CT=19 WT=10
P3: CT= 8 WT= 4
P4: CT=11 WT= 4
Average WT = 4.50

The average wait falls from 7.25 to 4.50. When all jobs are available together, SJF gives the minimum possible average waiting time of any non-preemptive schedule. Moving a short job ahead of a long one helps the short job more than it hurts the long one.

SRTF: shortest remaining time first

Shortest Remaining Time First (SRTF) is the preemptive version of SJF. Whenever a new process arrives, the scheduler compares its burst with the remaining time of the running process. If the newcomer is shorter, it takes over the CPU.

Step 1: trace it by hand, one event at a time.

1. Time 0: only P1, so P1 runs.
2. Time 1: P2 (8) arrives; P1 has 5 left, which is shorter, so P1 continues.
3. Time 2: P3 (2) arrives; P1 has 4 left. P3 is shorter, so P1 is preempted and P3 runs 2 to 4.
4. Time 4: P3 is done and P4 (3) arrives. P1 has 4 left, P4 has 3, so P4 runs 4 to 7.
5. Time 7: P1 (4 left) beats P2 (8), so P1 runs 7 to 11. Then P2 runs 11 to 19.

Step 2: the simulation steps forward one time unit at a time, which is the easiest correct way to code a preemptive scheduler.

procs = [("P1", 0, 6), ("P2", 1, 8), ("P3", 2, 2), ("P4", 4, 3)]

def srtf(procs):
    left = {n: bt for n, at, bt in procs}
    arrival = {n: at for n, at, bt in procs}
    chart, clock = [], 0
    while any(left.values()):
        ready = [n for n in left if left[n] > 0 and arrival[n] <= clock]
        name = min(ready, key=lambda n: (left[n], arrival[n])) if ready else "idle"
        if chart and chart[-1][0] == name:      # same process keeps running
            chart[-1] = (name, chart[-1][1], clock + 1)
        else:
            chart.append((name, clock, clock + 1))
        if name != "idle":
            left[name] -= 1
        clock += 1
    return chart

chart = srtf(procs)
print(chart)
first = {}
for n, s, e in chart:
    first.setdefault(n, s)
end = {n: e for n, s, e in chart}
total_wt = 0
for name, at, bt in procs:
    wt = end[name] - at - bt
    total_wt += wt
    print(f"{name}: CT={end[name]:2} WT={wt:2} RT={first[name] - at}")
print(f"Average WT = {total_wt / len(procs):.2f}")

[('P1', 0, 2), ('P3', 2, 4), ('P4', 4, 7), ('P1', 7, 11), ('P2', 11, 19)]
P1: CT=11 WT= 5 RT=0
P2: CT=19 WT=10 RT=10
P3: CT= 4 WT= 0 RT=0
P4: CT= 7 WT= 0 RT=0
Average WT = 3.75

The average drops again, to 3.75. SRTF gives the minimum average waiting time of all schedules for a given set of arrivals, but it pays with extra context switches.

The catch: nobody knows the future

SJF and SRTF need each process's next burst length, which the OS cannot know in advance. Real systems predict it from past bursts with exponential averaging:

next_guess = alpha * last_actual_burst + (1 - alpha) * previous_guess

Here alpha (between 0 and 1) says how much to trust the latest burst. With alpha = 0.5, recent and older history count equally.

alpha, guess = 0.5, 8
for actual in [4, 10, 6, 5]:
    print(f"guessed {guess}, actual {actual}")
    guess = alpha * actual + (1 - alpha) * guess
print("next guess:", guess)

guessed 8, actual 4
guessed 6.0, actual 10
guessed 8.0, actual 6
guessed 7.0, actual 5
next guess: 6.0

Common mistakes

• Choosing a job that has not arrived yet. SJF chooses only among processes whose arrival time is less than or equal to the current time.
• Treating SJF as preemptive. Plain SJF lets the chosen job finish; the preemptive version is SRTF.
• Comparing the newcomer with the original burst in SRTF. Compare with the running process's remaining time.

Key points

• FCFS runs jobs in arrival order; it is simple and fair but suffers from the convoy effect.
• SJF runs the shortest ready job to completion and minimises average waiting time among non-preemptive schedules.
• SRTF preempts when a shorter job arrives and gives the lowest average waiting time overall.
• SJF and SRTF can starve long jobs.
• Real systems predict burst lengths with exponential averaging.

procs = [("P1", 0, 3), ("P2", 8, 4), ("P3", 9, 2)]
print(fcfs(procs))
print(sjf(procs))

[('P1', 0, 3), ('idle', 3, 8), ('P2', 8, 12), ('P3', 12, 14)]
[('P1', 0, 3), ('idle', 3, 8), ('P2', 8, 12), ('P3', 12, 14)]