CPU Scheduling in OS: FCFS, SJF, SRTF, Round Robin

The CPU scheduler decides which process in the ready queue runs next. A process alternates between CPU bursts (computing) and I/O bursts (waiting for a disk, the network or the user); whenever the running process blocks or is interrupted, the scheduler has to choose again. The choice decides how long everyone waits, so it is the most-asked computation topic in operating systems. This note defines the measures, then runs one example through every standard algorithm.

Scheduling criteria

Scheduling decisions happen when a process (1) switches from running to waiting, (2) is interrupted from running back to ready, (3) moves from waiting to ready, or (4) terminates. A non-preemptive scheduler only decides in cases 1 and 4: once a process has the CPU it keeps it until it blocks or ends. A preemptive scheduler can also take the CPU away in cases 2 and 3.

The dispatcher carries the decision out: it performs the context switch, switches to user mode and jumps into the chosen process. The time it takes is the dispatch latency.

The example used throughout

Four processes, times in milliseconds. For priority scheduling a smaller number means higher priority (a convention; always check which one a question uses).

The total burst is 16, and the CPU is never idle, so every schedule below ends at time 16. Ties are broken by earlier arrival.

First-Come, First-Served (FCFS)

The ready queue is a FIFO queue: whoever arrived first runs first, to completion. It is non-preemptive, simple and fair in the sense of order, but one long process makes everyone behind it wait.

P3 needs one millisecond but waits seven: the convoy effect, where short processes queue behind a long one, and the I/O devices sit idle because the I/O-bound processes cannot run to issue their next request.

Shortest Job First (SJF)

When the CPU is free, run the ready process with the shortest next CPU burst. Non-preemptive SJF is provably optimal for average waiting time when all processes are available at once, because moving a short job ahead of a long one reduces the short job's wait more than it increases the long one's.

The catch is that the OS does not know the next burst. It predicts it with an exponential average of past bursts: τ(n+1) = α·t(n) + (1 − α)·τ(n), where t(n) is the burst just measured and τ(n) the previous guess. With α = 0.5, an initial guess of 10 and measured bursts of 6 and then 4, the predictions are 0.5·6 + 0.5·10 = 8 and then 0.5·4 + 0.5·8 = 6. SJF can also starve a long job if short ones keep arriving.

Shortest Remaining Time First (SRTF)

SRTF is preemptive SJF: whenever a process arrives, compare its burst with the remaining time of the running process and switch if the newcomer is shorter.

1. Only P1 has arrived, so it runs until P2 arrives at 2 and the times are compared again.
2. At 2, P2 arrives. P2 has the least time left, 4 (others: P1 5), so it preempts P1 and runs until P3 arrives at 4 and the times are compared again.
3. At 4, P3 arrives. P3 has the least time left, 1 (others: P1 5, P2 2), so it preempts P2 and runs until it finishes at 5.
4. At 5, P4 arrives. P2 has the least time left, 2 (others: P1 5, P4 4), so it runs until it finishes at 7.
5. At 7, P4 has the least time left, 4 (others: P1 5), so it runs until it finishes at 11.
6. At 11 only P1 is left, so it runs until it finishes at 16. Average waiting 12/4 = 3 ms, the lowest of any algorithm on this example.

SRTF gives the lowest average waiting time of any algorithm here, which is what theory predicts, but it makes the most context switches and has the same starvation risk as SJF.

Priority scheduling

Each process has a priority and the CPU goes to the highest-priority ready process. SJF is the special case where priority is the predicted burst.

1. Non-preemptive: P1 is alone at 0 and keeps the CPU to 7; then the ready processes go by priority, P2 (1), P4 (2), P3 (4). Average waiting 22/4 = 5.5 ms.
2. Preemptive: P2 (priority 1) takes the CPU from P1 the moment it arrives at 2. Average waiting 20/4 = 5 ms. In both, P3, the lowest priority, waits 11 — with more high-priority work arriving it could wait for ever, which aging prevents.

P3, the lowest priority, waits 11 ms in both versions, and under a steady stream of higher-priority work it could wait forever: that is starvation (indefinite blocking). The fix is aging: raise a process's priority the longer it waits, so it is eventually served.

Round Robin (RR)

Round Robin is FCFS with preemption by a timer. Each process runs for at most one time quantum q, then goes to the back of the ready queue. It is the basis of time-sharing, because no process waits more than (n − 1)·q before its next turn when n processes are ready.

With q = 2, and the usual convention that a process arriving at the instant a quantum expires joins the queue before the preempted process:

1. Each process runs at most 2 ms, then rejoins the queue. 0–2: P1 runs one quantum of 2 and goes to the back of the queue, behind P2, which arrived at 2 as the quantum expired.
2. 2–4: P2 runs one quantum of 2 and goes to the back of the queue, behind P3, which arrived at 4 as the quantum expired.
3. 4–6: P1 runs one quantum of 2 and goes to the back of the queue, behind P4, which arrived at 5 during the slice.
4. 6–7: P3 runs its last 1 ms and finishes, so it leaves the queue for good.
5. 7–9: P2 runs its last quantum and finishes, so it leaves the queue for good.
6. 9–11: P4 runs one quantum of 2 and goes to the back of the queue.
7. 11–13: P1 runs one quantum of 2 and goes to the back of the queue.
8. 13–15: P4 runs its last quantum and finishes, so it leaves the queue for good.
9. 15–16: P1 runs its last 1 ms and finishes, so it leaves the queue for good. Average waiting 20/4 = 5 ms; no process ever waited more than 6 ms for its next turn.

Choosing the quantum. If q is larger than every burst, RR becomes FCFS. If q is tiny, most CPU time goes into context switches. A common textbook rule of thumb is that most CPU bursts (around 80%) should be shorter than q, while q stays much longer than a context switch. Average waiting time does not change smoothly with q either:

Multilevel queue and multilevel feedback queue

A multilevel queue splits the ready queue into several queues by process type, for example system, interactive and batch, each with its own algorithm (RR for interactive, FCFS for batch). Queues are served in fixed priority order, or each gets a share of CPU time. A process stays in its queue for life.

A multilevel feedback queue (MLFQ) lets processes move between queues based on behaviour. A typical setup:

• Queue 0: RR with q = 8. Every new process starts here.
• Queue 1: RR with q = 16. A process that used its whole quantum in queue 0 drops here.
• Queue 2: FCFS, for processes that used their whole quantum in queue 1 too.

A lower queue runs only when all higher queues are empty. Short, interactive processes finish or block within a quantum and stay high; long CPU-bound ones sink. Aging moves a process that has waited too long back up. An MLFQ is defined by the number of queues, each queue's algorithm, and the rules for moving up and down.

Real kernels are not one textbook algorithm. Linux's CFS scheduler, succeeded by EEVDF in kernel 6.6, shares CPU time between tasks in proportion to their weights instead of using fixed queues, while Windows uses preemptive scheduling over 32 priority levels.

Comparing the algorithms

The same four processes under each algorithm:

Round Robin loses on waiting time to SJF and SRTF but nearly matches SRTF on response time, without needing to know any burst length.

Simulating FCFS and Round Robin

This program replays the FCFS and Round Robin schedules above and prints the averages, using the same queueing rule for arrivals at a quantum boundary.

#include <algorithm>
#include <cstdio>
#include <deque>
#include <string>
#include <vector>
using namespace std;

const vector<string> NAMES = {"P1", "P2", "P3", "P4"};
const vector<int> ARRIVAL = {0, 2, 4, 5};  // sorted by arrival
const vector<int> BURST = {7, 4, 1, 4};
const int N = 4;

void report(const string& name, const vector<string>& gantt, const vector<int>& finish) {
    double waiting = 0, turnaround = 0;
    for (int i = 0; i < N; i++) {
        int tat = finish[i] - ARRIVAL[i];
        turnaround += tat;
        waiting += tat - BURST[i];
    }
    string line;
    for (size_t k = 0; k < gantt.size(); k++) line += (k ? " | " : "") + gantt[k];
    printf("%s: %s\n", name.c_str(), line.c_str());
    printf("%s average waiting %.2f, turnaround %.2f\n", name.c_str(), waiting / N, turnaround / N);
}

string slice(int i, int from, int to) {
    return NAMES[i] + " " + to_string(from) + "-" + to_string(to);
}

void fcfs() {
    vector<string> gantt;
    vector<int> finish(N);
    int time = 0;
    for (int i = 0; i < N; i++) {
        time = max(time, ARRIVAL[i]);
        gantt.push_back(slice(i, time, time + BURST[i]));
        time += BURST[i];
        finish[i] = time;
    }
    report("FCFS", gantt, finish);
}

void roundRobin(int quantum) {
    vector<string> gantt;
    vector<int> left = BURST, finish(N);
    deque<int> ready;
    int next = 0, time = 0;
    while (next < N || !ready.empty()) {
        if (ready.empty()) time = max(time, ARRIVAL[next]);
        while (next < N && ARRIVAL[next] <= time) ready.push_back(next++);
        int i = ready.front();
        ready.pop_front();
        int run = min(quantum, left[i]);
        gantt.push_back(slice(i, time, time + run));
        time += run;
        left[i] -= run;
        // arrivals during the slice queue ahead of the preempted process
        while (next < N && ARRIVAL[next] <= time) ready.push_back(next++);
        if (left[i] > 0) ready.push_back(i);
        else finish[i] = time;
    }
    report("RR q=" + to_string(quantum), gantt, finish);
}

int main() {
    fcfs();
    roundRobin(2);
    return 0;
}

import java.util.*;

public class Main {
    static final String[] NAMES = {"P1", "P2", "P3", "P4"};
    static final int[] ARRIVAL = {0, 2, 4, 5}; // sorted by arrival
    static final int[] BURST = {7, 4, 1, 4};
    static final int N = NAMES.length;

    static void report(String name, List<String> gantt, int[] finish) {
        double waiting = 0, turnaround = 0;
        for (int i = 0; i < N; i++) {
            int tat = finish[i] - ARRIVAL[i];
            turnaround += tat;
            waiting += tat - BURST[i];
        }
        System.out.println(name + ": " + String.join(" | ", gantt));
        System.out.println(String.format(Locale.ROOT, "%s average waiting %.2f, turnaround %.2f",
                name, waiting / N, turnaround / N));
    }

    static void fcfs() {
        List<String> gantt = new ArrayList<>();
        int[] finish = new int[N];
        int time = 0;
        for (int i = 0; i < N; i++) {
            time = Math.max(time, ARRIVAL[i]);
            gantt.add(NAMES[i] + " " + time + "-" + (time + BURST[i]));
            time += BURST[i];
            finish[i] = time;
        }
        report("FCFS", gantt, finish);
    }

    static void roundRobin(int quantum) {
        List<String> gantt = new ArrayList<>();
        int[] left = BURST.clone(), finish = new int[N];
        ArrayDeque<Integer> ready = new ArrayDeque<>();
        int next = 0, time = 0;
        while (next < N || !ready.isEmpty()) {
            if (ready.isEmpty()) time = Math.max(time, ARRIVAL[next]);
            while (next < N && ARRIVAL[next] <= time) ready.add(next++);
            int i = ready.poll();
            int run = Math.min(quantum, left[i]);
            gantt.add(NAMES[i] + " " + time + "-" + (time + run));
            time += run;
            left[i] -= run;
            // arrivals during the slice queue ahead of the preempted process
            while (next < N && ARRIVAL[next] <= time) ready.add(next++);
            if (left[i] > 0) ready.add(i);
            else finish[i] = time;
        }
        report("RR q=" + quantum, gantt, finish);
    }

    public static void main(String[] args) {
        fcfs();
        roundRobin(2);
    }
}

from collections import deque

NAMES = ["P1", "P2", "P3", "P4"]
ARRIVAL = [0, 2, 4, 5]  # sorted by arrival
BURST = [7, 4, 1, 4]
N = len(NAMES)


def report(name, gantt, finish):
    turnaround = [finish[i] - ARRIVAL[i] for i in range(N)]
    waiting = [turnaround[i] - BURST[i] for i in range(N)]
    print(f"{name}: {' | '.join(gantt)}")
    print(f"{name} average waiting {sum(waiting) / N:.2f}, turnaround {sum(turnaround) / N:.2f}")


def fcfs():
    gantt, finish, time = [], [0] * N, 0
    for i in range(N):
        time = max(time, ARRIVAL[i])
        gantt.append(f"{NAMES[i]} {time}-{time + BURST[i]}")
        time += BURST[i]
        finish[i] = time
    report("FCFS", gantt, finish)


def round_robin(quantum):
    gantt, finish, left = [], [0] * N, BURST[:]
    ready, nxt, time = deque(), 0, 0
    while nxt < N or ready:
        if not ready:
            time = max(time, ARRIVAL[nxt])
        while nxt < N and ARRIVAL[nxt] <= time:
            ready.append(nxt)
            nxt += 1
        i = ready.popleft()
        run = min(quantum, left[i])
        gantt.append(f"{NAMES[i]} {time}-{time + run}")
        time += run
        left[i] -= run
        # arrivals during the slice queue ahead of the preempted process
        while nxt < N and ARRIVAL[nxt] <= time:
            ready.append(nxt)
            nxt += 1
        if left[i] > 0:
            ready.append(i)
        else:
            finish[i] = time
    report(f"RR q={quantum}", gantt, finish)


def main():
    fcfs()
    round_robin(2)


main()

const NAMES = ["P1", "P2", "P3", "P4"];
const ARRIVAL = [0, 2, 4, 5]; // sorted by arrival
const BURST = [7, 4, 1, 4];
const N = NAMES.length;

function report(name, gantt, finish) {
  let waiting = 0, turnaround = 0;
  for (let i = 0; i < N; i++) {
    const tat = finish[i] - ARRIVAL[i];
    turnaround += tat;
    waiting += tat - BURST[i];
  }
  console.log(`${name}: ${gantt.join(" | ")}`);
  console.log(`${name} average waiting ${(waiting / N).toFixed(2)}, turnaround ${(turnaround / N).toFixed(2)}`);
}

function fcfs() {
  const gantt = [], finish = new Array(N).fill(0);
  let time = 0;
  for (let i = 0; i < N; i++) {
    time = Math.max(time, ARRIVAL[i]);
    gantt.push(`${NAMES[i]} ${time}-${time + BURST[i]}`);
    time += BURST[i];
    finish[i] = time;
  }
  report("FCFS", gantt, finish);
}

function roundRobin(quantum) {
  const gantt = [], finish = new Array(N).fill(0), left = BURST.slice(), ready = [];
  let next = 0, time = 0;
  while (next < N || ready.length > 0) {
    if (ready.length === 0) time = Math.max(time, ARRIVAL[next]);
    while (next < N && ARRIVAL[next] <= time) ready.push(next++);
    const i = ready.shift();
    const run = Math.min(quantum, left[i]);
    gantt.push(`${NAMES[i]} ${time}-${time + run}`);
    time += run;
    left[i] -= run;
    // arrivals during the slice queue ahead of the preempted process
    while (next < N && ARRIVAL[next] <= time) ready.push(next++);
    if (left[i] > 0) ready.push(i);
    else finish[i] = time;
  }
  report(`RR q=${quantum}`, gantt, finish);
}

function main() {
  fcfs();
  roundRobin(2);
}

main();

FCFS: P1 0-7 | P2 7-11 | P3 11-12 | P4 12-16
FCFS average waiting 4.75, turnaround 8.75
RR q=2: P1 0-2 | P2 2-4 | P1 4-6 | P3 6-7 | P2 7-9 | P4 9-11 | P1 11-13 | P4 13-15 | P1 15-16
RR q=2 average waiting 5.00, turnaround 9.00

Common mistakes

• Computing waiting time as start time − arrival time under a preemptive algorithm. That is response time; waiting time is turnaround − burst and counts every stretch in the ready queue.
• Comparing a newcomer under SRTF with the running process's original burst instead of its remaining time.
• Forgetting idle gaps: if no process has arrived yet, the CPU idles and the timeline jumps to the next arrival.
• Reading a larger priority number as higher priority without checking the question's convention.
• In Round Robin, putting the preempted process ahead of a process that arrived at the same instant; most textbooks queue the newcomer first, and the answer changes if you do not.
• Saying Round Robin cannot starve because it is fair, then claiming the same for SJF. SJF and priority scheduling can starve; FCFS and RR cannot.

Interview questions

Why is SJF optimal, and why is it not used directly? Running the shortest job first minimizes the total time everyone else spends waiting behind it, which gives the minimum average waiting time for a fixed set of jobs. It is impractical because the next CPU burst is unknown, so it must be predicted, and long jobs can starve.

What is the difference between SJF and SRTF? SJF is non-preemptive: a chosen process runs its whole burst. SRTF is its preemptive version: a newly arrived process with a shorter burst than the running process's remaining time takes the CPU.

How does the time quantum affect Round Robin? A very large quantum turns RR into FCFS and hurts response time. A very small quantum gives quick responses but wastes CPU time on context switches. The quantum should be large compared with the context-switch time and longer than most CPU bursts.

What is starvation, and how does aging solve it? Starvation is a ready process waiting indefinitely because others are always preferred, as with a low-priority process in priority scheduling. Aging raises a process's priority the longer it waits, so it eventually reaches the top and runs.

What is the difference between a multilevel queue and a multilevel feedback queue? In a multilevel queue a process is assigned to one queue permanently. In a multilevel feedback queue it moves: using a whole quantum pushes it down, and waiting too long (aging) can move it up, so the scheduler learns which processes are interactive.

Which algorithms are preemptive? SRTF, Round Robin and preemptive priority scheduling. FCFS and SJF are non-preemptive, and multilevel queues are usually preemptive between queues.

What is the difference between turnaround time and response time? Turnaround time runs from arrival to completion and matters for batch jobs. Response time runs from arrival to the first moment on the CPU and matters for interactive programs, where the user wants to see something start.

Next, read Process Synchronization, or practise these computations in the Operating Systems (Intermediate) skill test.