CPU Scheduling (FCFS, SJF, SRTF, Round Robin, Priority)

Why scheduling?

A computer runs many programs (processes) at once, but each CPU core can execute only one at a time. Processes that are ready to run wait in the ready queue. The CPU scheduler decides which one runs next — and that choice changes how long everyone waits.

Key terms

Term	Meaning
Arrival time (AT)	When the process enters the ready queue
Burst time (BT)	How much CPU time it needs
Completion time (CT)	When it finishes
Turnaround time (TAT)	CT − AT (total time in the system)
Waiting time (WT)	TAT − BT (time spent waiting in the queue)
Response time	First time it gets the CPU − AT
Preemptive	The scheduler may interrupt a running process

The 3D model draws a Gantt chart: each block is one time unit of CPU, coloured by process. Above it you see the CPU and the ready queue; on the right, each process’s remaining time.

The algorithms

First Come, First Served (FCFS)

Run processes in order of arrival; never interrupt. Simple and fair in order, but a long job at the front makes everyone wait — the convoy effect.

Shortest Job First (SJF)

When the CPU becomes free, pick the ready process with the smallest burst time. Non-preemptive. It gives the minimum average waiting time, but needs burst times in advance (usually estimated) and can starve long jobs.

Shortest Remaining Time First (SRTF)

The preemptive version of SJF: whenever a process arrives with less remaining time than the running one, it takes over.

Round Robin (RR)

Each process gets a time quantum (here q = 2). If it isn’t finished, it goes to the back of the queue. Great response time and fairness — the standard for interactive systems. A tiny quantum causes too many context switches; a huge one turns RR into FCFS.

Priority scheduling

Each process has a priority (here a smaller number = more important); the best one runs first. Risk: starvation — fixed with aging (gradually increasing the priority of waiting processes).

Worked example (FCFS)

Process	AT	BT	CT	TAT = CT − AT	WT = TAT − BT
P1	0	5	5	5	0
P2	1	3	8	7	4
P3	2	8	16	14	6
P4	3	6	22	19	13
P5	4	2	24	20	18

Average waiting time = (0 + 4 + 6 + 13 + 18) / 5 = 8.2. Run SJF in the model and compare.

Code

def fcfs(procs):
    """procs: list of (name, arrival, burst) sorted by arrival"""
    t, out = 0, []
    for name, at, bt in procs:
        t = max(t, at)            # CPU may be idle until the process arrives
        t += bt                   # run to completion
        tat = t - at
        out.append((name, t, tat, tat - bt))
    return out

def round_robin(procs, q=2):
    from collections import deque
    procs = sorted(procs, key=lambda p: p[1])
    remaining = {n: bt for n, _, bt in procs}
    t, i, queue, finish = 0, 0, deque(), {}
    while len(finish) < len(procs):
        while i < len(procs) and procs[i][1] <= t:
            queue.append(procs[i][0]); i += 1
        if not queue:
            t = procs[i][1]; continue
        n = queue.popleft()
        run = min(q, remaining[n])
        for _ in range(run):                      # let newcomers join during the slice
            t += 1
            while i < len(procs) and procs[i][1] <= t:
                queue.append(procs[i][0]); i += 1
        remaining[n] -= run
        if remaining[n] == 0: finish[n] = t
        else: queue.append(n)
    return finish

ps = [("P1", 0, 5), ("P2", 1, 3), ("P3", 2, 8), ("P4", 3, 6), ("P5", 4, 2)]
print(fcfs(ps))
print(round_robin(ps))

Choosing a scheduler

Goal	Good choice
Simplicity, batch jobs	FCFS
Lowest average waiting time	SJF / SRTF
Interactive, fair response	Round Robin
Important tasks first	Priority (+ aging)

Real operating systems combine ideas: Linux’s CFS gives each process a fair share of CPU time, and Windows uses multilevel feedback queues with priorities.

Common mistakes

• Forgetting idle time when no process has arrived yet.
• In Round Robin, getting the order wrong when a new process arrives at the same moment a quantum ends (most textbooks put the newcomer first).
• Computing waiting time as CT − BT instead of TAT − BT.