CPU Scheduling Algorithms: FCFS, SJF, SRTF, Round Robin

By Engr. Henry Akpan

Who Gets the Processor Next?

A computer may have dozens of programs ready to run but only a few processor cores. The operating system's scheduler decides which process runs next and for how long. Its choices decide whether your music stutters, how long a print job waits, and how quickly the whole system finishes its work. CPU scheduling algorithms are a core topic in operating systems courses (CSC 3xx) and a favourite exam question: given a table of processes, draw the Gantt chart and calculate waiting and turnaround times. This tutorial explains the key measures, then simulates First-Come First-Served, Shortest Job First, Shortest Remaining Time First, Priority and Round Robin scheduling in Python, comparing their results on the same workload. All outputs come from running the code.

Key Terms

  • Arrival time: when the process becomes ready to run.
  • Burst time: how much CPU time it needs.
  • Completion time: when it finishes.
  • Turnaround time = completion time − arrival time: the total time from arrival to finish.
  • Waiting time = turnaround time − burst time: the time spent ready but not running.
  • Response time: the time from arrival until the process first gets the CPU (important for interactive programs).
  • Preemptive schedulers can interrupt a running process; non-preemptive ones let it run until it finishes.

We use the same five processes throughout. Each has a name, arrival time, burst time and priority (a lower number means higher priority).

from collections import deque

PROCS = [  # (name, arrival, burst, priority)
    ("P1", 0, 8, 3),
    ("P2", 1, 4, 1),
    ("P3", 2, 9, 4),
    ("P4", 3, 5, 2),
    ("P5", 4, 2, 5),
]

def report(name, timeline, procs=PROCS):
    """timeline: list of (process, start, end) slices."""
    finish = {}
    first = {}
    for p, s, e in timeline:
        finish[p] = e
        first.setdefault(p, s)
    chart = " ".join(f"{p}[{s}-{e}]" for p, s, e in timeline)
    tat = {p: finish[p] - a for p, a, b, _ in procs}
    wt = {p: tat[p] - b for p, a, b, _ in procs}
    rt = {p: first[p] - a for p, a, b, _ in procs}
    n = len(procs)
    print(f"{name}\n  {chart}")
    print(f"  avg waiting {sum(wt.values()) / n:.1f}, avg turnaround {sum(tat.values()) / n:.1f}, "
          f"avg response {sum(rt.values()) / n:.1f}")
    return wt

The report function prints a text Gantt chart (each slice as process[start-end]) and the averages, and works for every algorithm below.

First-Come, First-Served (FCFS)

The simplest algorithm: run processes in order of arrival, each to completion. It is non-preemptive and easy to implement with a queue.

def fcfs(procs):
    t, timeline = 0, []
    for p, a, b, _ in sorted(procs, key=lambda x: x[1]):
        t = max(t, a)                     # CPU may sit idle until the process arrives
        timeline.append((p, t, t + b))
        t += b
    return timeline

wt = report("FCFS", fcfs(PROCS))
print(" ", wt)

Output:

FCFS
  P1[0-8] P2[8-12] P3[12-21] P4[21-26] P5[26-28]
  avg waiting 11.4, avg turnaround 17.0, avg response 11.4
  {'P1': 0, 'P2': 7, 'P3': 10, 'P4': 18, 'P5': 22}

FCFS is fair in the sense of "first come, first served", but short jobs stuck behind long ones wait a long time: P5 needs only 2 units but waits 22. This is the convoy effect.

Shortest Job First (SJF, Non-Preemptive)

Whenever the CPU becomes free, run the waiting process with the shortest burst. This minimises the average waiting time among non-preemptive algorithms.

def sjf(procs):
    pending = sorted(procs, key=lambda x: x[1])
    t, timeline = 0, []
    while pending:
        ready = [p for p in pending if p[1] <= t]
        if not ready:
            t = pending[0][1]
            continue
        job = min(ready, key=lambda x: (x[2], x[1]))   # shortest burst, then earliest arrival
        pending.remove(job)
        timeline.append((job[0], t, t + job[2]))
        t += job[2]
    return timeline

report("SJF", sjf(PROCS))

Output:

SJF
  P1[0-8] P5[8-10] P2[10-14] P4[14-19] P3[19-28]
  avg waiting 8.2, avg turnaround 13.8, avg response 8.2

At time 0 only P1 has arrived, so it runs to completion (non-preemptive). At time 8, P5 is the shortest waiting job, then P2, P4 and P3. Average waiting drops from 11.4 to 8.2. The drawbacks: the scheduler must know burst times in advance (real systems estimate them from past behaviour), and long jobs can starve if short jobs keep arriving.

Shortest Remaining Time First (SRTF, Preemptive SJF)

The preemptive version: whenever a new process arrives, if its burst is shorter than the remaining time of the running process, it takes over the CPU. We simulate one time unit at a time:

def srtf(procs):
    remaining = {p: b for p, a, b, _ in procs}
    arrival = {p: a for p, a, b, _ in procs}
    t, timeline = 0, []
    while any(remaining.values()):
        ready = [p for p in remaining if remaining[p] > 0 and arrival[p] <= t]
        if not ready:
            t += 1
            continue
        p = min(ready, key=lambda x: (remaining[x], arrival[x]))
        if timeline and timeline[-1][0] == p and timeline[-1][2] == t:
            timeline[-1] = (p, timeline[-1][1], t + 1)      # extend the current slice
        else:
            timeline.append((p, t, t + 1))
        remaining[p] -= 1
        t += 1
    return timeline

report("SRTF", srtf(PROCS))

Output:

SRTF
  P1[0-1] P2[1-5] P5[5-7] P4[7-12] P1[12-19] P3[19-28]
  avg waiting 6.6, avg turnaround 12.2, avg response 4.4

P2 arrives at time 1 needing 4 units, less than P1's remaining 7, so it preempts P1. SRTF gives the lowest possible average waiting time of all, but it shares SJF's need to know burst times and its risk of starvation, and frequent switching has a cost (each context switch takes time to save and restore a process's state).

Priority Scheduling

Each process has a priority, and the scheduler runs the highest-priority ready process. Here is the non-preemptive version:

def priority_np(procs):
    pending = sorted(procs, key=lambda x: x[1])
    t, timeline = 0, []
    while pending:
        ready = [p for p in pending if p[1] <= t]
        if not ready:
            t = pending[0][1]
            continue
        job = min(ready, key=lambda x: (x[3], x[1]))       # lowest number = highest priority
        pending.remove(job)
        timeline.append((job[0], t, t + job[2]))
        t += job[2]
    return timeline

report("Priority (non-preemptive)", priority_np(PROCS))

Output:

Priority (non-preemptive)
  P1[0-8] P2[8-12] P4[12-17] P3[17-26] P5[26-28]
  avg waiting 10.6, avg turnaround 16.2, avg response 10.6

Priorities let important work (system tasks, real-time audio) go first. The danger is starvation of low-priority processes; the usual fix is ageing, gradually raising the priority of processes that have waited a long time.

Round Robin (RR)

Each process gets a fixed time quantum. If it hasn't finished when its quantum expires, it is preempted and goes to the back of the ready queue. Round Robin is designed for time-sharing: every process gets a turn regularly, which keeps interactive programs responsive.

def round_robin(procs, quantum):
    procs = sorted(procs, key=lambda x: x[1])
    remaining = {p: b for p, a, b, _ in procs}
    queue, timeline, t, i = deque(), [], 0, 0
    while i < len(procs) or queue:
        while i < len(procs) and procs[i][1] <= t:      # admit arrivals
            queue.append(procs[i][0]); i += 1
        if not queue:
            t = procs[i][1]
            continue
        p = queue.popleft()
        run = min(quantum, remaining[p])
        timeline.append((p, t, t + run))
        t += run
        remaining[p] -= run
        while i < len(procs) and procs[i][1] <= t:      # arrivals during this slice go first
            queue.append(procs[i][0]); i += 1
        if remaining[p]:
            queue.append(p)
    return timeline

report("Round Robin, quantum 3", round_robin(PROCS, 3))

Output:

Round Robin, quantum 3
  P1[0-3] P2[3-6] P3[6-9] P4[9-12] P1[12-15] P5[15-17] P2[17-18] P3[18-21] P4[21-23] P1[23-25] P3[25-28]
  avg waiting 14.6, avg turnaround 20.2, avg response 4.6

Round Robin has a higher average waiting time than SJF on this workload, but much better response time (4.6 against 8.2): every process starts running soon after it arrives. The quantum matters a lot. A very large quantum turns RR into FCFS; a very small one causes so many context switches that overhead dominates. Typical quanta are 10 to 100 milliseconds, much longer than a context switch.

Convention note: when a new process arrives at the same moment a quantum expires, this simulation puts the newcomer in the queue before the preempted process. Some textbooks do the opposite, which can change the chart, so always state the rule you use in an exam.

Comparing CPU Scheduling Algorithms

  • FCFS: simple, no starvation, but poor average waiting time (convoy effect).
  • SJF / SRTF: best average waiting and turnaround; need burst estimates; long jobs may starve.
  • Priority: honours importance; needs ageing to avoid starvation.
  • Round Robin: fair and responsive for interactive systems; performance depends on the quantum.

Real operating systems combine these CPU scheduling algorithms. Multilevel feedback queues use several round-robin queues at different priorities and move processes between them based on behaviour, favouring short, interactive tasks. Linux's scheduler tracks how much CPU time each process has had and runs the one that has had the least relative to its share.

Summary

  • Turnaround = completion − arrival; waiting = turnaround − burst; response = first run − arrival.
  • FCFS runs jobs in arrival order; SJF picks the shortest job; SRTF preempts for a shorter remaining time.
  • Priority scheduling needs ageing to prevent starvation.
  • Round Robin gives each process a time quantum in turn, trading some average waiting time for better response.
  • Simulating CPU scheduling algorithms in code is a reliable way to check Gantt charts and averages.

Related Tutorials