Lesson 2 · Processes, threads, and CPU scheduling

CPU Scheduling Algorithms

Every ready process wants the CPU and only one can have it. A scheduling algorithm is the rule that picks, and each rule optimises a different metric — throughput, waiting time, response time, or fairness — at the cost of the others.

What Schedulers Are Measured On

Before comparing CPU scheduling algorithms — also written cpu scheduling algorithms in os, or process scheduling algorithms — it helps to fix the metrics, because no algorithm wins on all of them. Turnaround time is completion minus arrival — the total wall-clock a job took. Waiting time is turnaround minus the actual CPU burst, so it is time spent purely queueing.

Response time is arrival to first execution, not completion, and it is the metric an interactive user actually feels. A text editor that starts painting in 10 ms feels instant even if it takes a second to finish. Throughput is jobs completed per unit time, and CPU utilisation is the fraction of time the CPU is doing work rather than idling.

These conflict directly. Minimising average waiting time means always running the shortest job, which starves long ones. Maximising throughput means minimising switches, which destroys response time. A general-purpose OS deliberately picks a compromise none of the textbook algorithms represents.

One more distinction runs through everything below. Non-preemptive scheduling only reconsiders when the running process blocks or exits; preemptive scheduling can take the CPU away mid-burst. Preemption is what makes a system responsive, and it is why a runaway loop cannot freeze a modern machine.

The operating system process scheduling algorithms below are compared on one job set, so the differences are arithmetic rather than opinion. Each of these CPU scheduling algorithms examples uses P1=6, P2=2 and P3=4 arriving together.

Turnaround: arrival to completion
Waiting: turnaround minus CPU burst
Response: arrival to first run — what users feel
Preemptive scheduling is what stops one loop owning the machine

First-Come, First-Served

Process scheduling in OS begins with the simplest rule. FCFS runs processes in arrival order until each finishes. It is non-preemptive, needs nothing but a FIFO queue, and is trivially fair in the sense that nobody jumps the line.

Its failure has a name: the convoy effect. Put one 100 ms CPU-bound job at the front of ten 1 ms jobs and every short job waits the full 100 ms. Average waiting time explodes, and the machine feels frozen even though the CPU is 100% busy.

The worked case on this page uses P1=6, P2=2, P3=4 arriving together. FCFS gives waiting times 0, 6, 8 — average 4.67 — and P2, a 2-unit job, waited three times its own length before starting.

It is still the right choice in one place: batch systems where nobody is watching and only throughput matters. FCFS has zero scheduling overhead and no preemption cost, so it maximises useful work per second. It is the wrong choice anywhere a human is waiting.

FCFS with P1=6, P2=2, P3=4 all arriving at t=0 — the standard worked layout
Job	Burst	Start	Completion	Turnaround	Waiting
P1	6	0	6	6	0
P2	2	6	8	8	6
P3	4	8	12	12	8
Average	—	—	—	8.67	4.67

Non-preemptive, arrival order, one FIFO queue
Convoy effect: one long job delays everything behind it
Zero overhead — no switches beyond the unavoidable
Correct for batch, wrong for interactive

Key reference

Terms, operations, and practical uses

Metrics

TurnaroundArrival to completion.
WaitingTurnaround minus the actual CPU burst.
ResponseArrival to first execution — what a user feels.
ThroughputJobs completed per unit time.

Non-preemptive

FCFSArrival order; suffers the convoy effect.
SJFOptimal average waiting time, needs unknowable burst lengths.
Convoy effectOne long job at the front delays every short job behind it.

Preemptive

SRTFPreemptive SJF; better still, and starves long jobs harder.
Round robinFixed quantum then rotate; 10-100 ms keeps overhead near 1%.
QuantumToo long becomes FCFS, too short burns CPU on switching.
AgingRaises a waiting process's priority so it cannot starve.

Code example

Four CPU scheduling algorithms on one job set

from collections import deque

# Four scheduling policies on the same three jobs. Total work is 12 units
# either way -- the only thing a scheduler controls is the order.
JOBS = [('P1', 6), ('P2', 2), ('P3', 4)]
PRIORITY = {'P1': 1, 'P3': 2, 'P2': 3}        # lower number = higher priority

def run(sequence):
    """Return (first_cpu, completion) times for a list of (name, slice)."""
    first, done, t = {}, {}, 0
    for name, length in sequence:
        first.setdefault(name, t)             # response = first time on CPU
        t += length
        done[name] = t
    return first, done

def averages(sequence):
    burst = dict(JOBS)
    first, done = run(sequence)
    wait = {n: done[n] - burst[n] for n in done}   # wait = turnaround - burst
    n = len(burst)
    return sum(wait.values()) / n, sum(first.values()) / n

fcfs = list(JOBS)                                   # arrival order
sjf = sorted(JOBS, key=lambda j: j[1])              # shortest burst first
prio = sorted(JOBS, key=lambda j: PRIORITY[j[0]])   # highest priority first

rr, ready = [], deque(JOBS)                         # preemptive, quantum 2
while ready:
    name, left = ready.popleft()
    slice_ = min(2, left)
    rr.append((name, slice_))
    if left - slice_:
        ready.append((name, left - slice_))         # unfinished goes to the back

fw, _ = averages(fcfs)
sw, _ = averages(sjf)
_, rr_resp = averages(rr)
pw, _ = averages(prio)
print(f"FCFS wait {fw:.2f} | SJF wait {sw:.2f} "
      f"| RR response {rr_resp:.2f} | Priority wait {pw:.2f}")

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <deque>
#include <algorithm>
#include <iomanip>
using namespace std;
// Four scheduling policies on the same three jobs. Total work is 12 units
// either way -- the only thing a scheduler controls is the order.
struct Job {
    string name;
    int burst;
};
// Returns {average waiting time, average response time} for a run sequence.
pair<double, double> averages(const vector<pair<string,int>>& seq,
const map<string,int>& burst) {
    map<string,int> first, done;
    int t = 0;
    for (auto& s : seq) {
        if (!first.count(s.first)) first[s.first] = t; // first time on CPU
        t += s.second;
        done[s.first] = t;
    }
    double w = 0, r = 0;
    for (auto& b : burst) {
        w += done[b.first] - b.second; // turnaround - burst
        r += first[b.first];
    }
    return {w / burst.size(), r / burst.size()};
}
int main() {
    vector<Job> jobs {
        {
            "P1", 6
        }, {"P2", 2}, {"P3", 4}
    };
    map<string,int> burst, priority {
        {
            "P1",1
        },{"P3",2},{"P2",3}
    };
    for (auto& j : jobs) burst[j.name] = j.burst;
    vector<pair<string,int>> fcfs, sjf, prio, rr;
    for (auto& j : jobs) fcfs.push_back({j.name, j.burst}); // arrival order
    sjf = fcfs;
    sort(sjf.begin(), sjf.end(), [](auto& a, auto& b){ return a.second < b.second; });
    prio = fcfs;
    sort(prio.begin(), prio.end(), [&](auto& a, auto& b){
    return priority[a.first] < priority[b.first]; });
    deque<pair<string,int>> ready(fcfs.begin(), fcfs.end()); // quantum 2
    while (!ready.empty()) {
        auto [name, left] = ready.front();
        ready.pop_front();
        int slice = min(2, left);
        rr.push_back({name, slice});
        if (left - slice) ready.push_back({name, left - slice});
    }
    cout << fixed << setprecision(2)
    << "FCFS wait " << averages(fcfs, burst).first
    << " | SJF wait " << averages(sjf, burst).first
    << " | RR response " << averages(rr, burst).second
    << " | Priority wait " << averages(prio, burst).first << "\n";
}

import java.util.*;
class Main {
    // Four scheduling policies on the same three jobs. Total work is 12 units
    // either way -- the only thing a scheduler controls is the order.
    record Slice(String name, int len) {
    }
    // Returns {average waiting time, average response time} for a run sequence.
    static double[] averages(List<Slice> seq, Map<String,Integer> burst) {
        Map<String,Integer> first = new HashMap<>(), done = new HashMap<>();
        int t = 0;
        for (Slice s : seq) {
            first.putIfAbsent(s.name(), t); // first time on CPU
            t += s.len();
            done.put(s.name(), t);
        }
        double w = 0, r = 0;
        for (var e : burst.entrySet()) {
            w += done.get(e.getKey()) - e.getValue(); // turnaround - burst
            r += first.get(e.getKey());
        }
        return new double[]{ w / burst.size(), r / burst.size() };
    }
    public static void main(String[] args) {
        List<Slice> fcfs = List.of(new Slice("P1", 6), new Slice("P2", 2),
        new Slice("P3", 4)); // arrival order
        Map<String,Integer> burst = new LinkedHashMap<>();
        for (Slice s : fcfs) burst.put(s.name(), s.len());
        Map<String,Integer> priority = Map.of("P1", 1, "P3", 2, "P2", 3);
        List<Slice> sjf = new ArrayList<>(fcfs);
        sjf.sort(Comparator.comparingInt(Slice::len));
        List<Slice> prio = new ArrayList<>(fcfs);
        prio.sort(Comparator.comparingInt(s -> priority.get(s.name())));
        List<Slice> rr = new ArrayList<>(); // quantum 2
        Deque<Slice> ready = new ArrayDeque<>(fcfs);
        while (!ready.isEmpty()) {
            Slice cur = ready.pollFirst();
            int slice = Math.min(2, cur.len());
            rr.add(new Slice(cur.name(), slice));
            if (cur.len() - slice > 0)
            ready.addLast(new Slice(cur.name(), cur.len() - slice));
        }
        System.out.printf("FCFS wait %.2f | SJF wait %.2f "
        + "| RR response %.2f | Priority wait %.2f%n",
        averages(fcfs, burst)[0], averages(sjf, burst)[0],
        averages(rr, burst)[1], averages(prio, burst)[0]);
    }
}

InputP1=6, P2=2, P3=4 all arrive at t=0; quantum 2; priorities P1>P3>P2

OutputFCFS wait 4.67 | SJF wait 2.67 | RR response 2.00 | Priority wait 5.33

Example

Run the example step by step

Output

Shortest Job First and Shortest Remaining Time

SJF picks the ready process with the smallest next CPU burst. It is provably optimal for average waiting time — no other non-preemptive algorithm beats it — which is a genuinely strong result.

It is also unimplementable, because the next burst length is not knowable in advance. Real schedulers approximate it by predicting from history, usually an exponential average where each new estimate blends the last prediction with the last actual burst.

SRTF is the preemptive form: when a new job arrives with a shorter remaining time than the running one, it preempts. This lowers average waiting further still, at the cost of more context switches.

Both starve long jobs. A steady arrival of short jobs means a long one may never run, and unlike round robin there is no mechanism that eventually forces its turn. This is why SJF appears in textbooks and estimators appear in production, but pure SJF appears in neither.

Provably optimal average waiting time
Requires burst lengths nobody can know in advance
SRTF is the preemptive variant, better and switch-heavier
Both starve long jobs with no built-in remedy

Round Robin and the Quantum

Of all the scheduling algorithms in operating system courses cover, round robin is the one interactive systems are built on. Round robin gives every ready process a fixed time quantum, then preempts and moves it to the back of the queue. It is FCFS plus preemption, and it is the foundation of interactive scheduling.

The quantum is the entire design decision. Too long and it degenerates into FCFS — a 5-second quantum makes a 6-unit job effectively non-preemptive. Too short and context-switch overhead dominates: at a 0.1 ms quantum with 10 µs switches, 10% of the CPU is spent switching rather than computing.

The working rule is that the quantum should exceed the majority of CPU bursts, so most processes block or finish before being preempted, while staying short enough that the queue cycles faster than a human notices. Typical values of 10–100 ms keep switching cost near 1%.

The tracer on this page runs the same three jobs under both policies. Round robin costs two extra context switches and finishes P2 at time 4 instead of 8 — worse total throughput, dramatically better response. That trade is the whole reason interactive systems exist.

Round robin, quantum 2, on the same jobs. Timeline: P1 P2 P3 P1 P3 P1
Job	Burst	Response	Completion	Turnaround	Waiting
P1	6	0	12	12	6
P2	2	2	4	4	2
P3	4	4	10	10	6
Average	—	2.00	—	8.67	4.67

Fixed quantum, preempt, rotate to the back
Too long becomes FCFS; too short burns CPU on switching
10–100 ms keeps overhead near 1%
Buys response time by spending throughput

Priority Scheduling and Starvation

Not all OS scheduling algorithms treat every process as equal. Priority scheduling runs the highest-priority ready process, with priorities assigned statically (by role — a real-time audio thread outranks a backup job) or dynamically (adjusted from observed behaviour). Round robin is simply priority scheduling where every process has equal priority.

The defining problem is starvation: a low-priority process may never run while higher-priority work keeps arriving. The standard fix is aging — gradually raising the priority of a process the longer it waits, guaranteeing it eventually reaches the front.

A related hazard is priority inversion, where a high-priority task blocks on a lock held by a low-priority task, which is itself preempted by a medium-priority task. The high-priority task is now effectively waiting behind medium-priority work. This stalled the Mars Pathfinder rover in 1997; the fix is priority inheritance, temporarily raising the lock holder to the priority of whoever is waiting.

Priority is also where scheduling meets policy. Linux nice values run -20 to 19, and only privileged users may lower a value — otherwise every program would declare itself the most important on the machine.

Highest priority first; round robin is the equal-priority case
Starvation is the failure mode; aging is the fix
Priority inversion needs inheritance, not just higher numbers
Raising your own priority must be privileged

Multilevel Queues and What Linux Actually Does

CPU scheduling in operating system practice ends up combining several of the rules above. Multilevel queue scheduling splits processes into separate queues by class — interactive, batch, system — each with its own policy and its own share of CPU. It works, but the classification is fixed: a process assigned to the batch queue stays there even when it starts behaving interactively.

Multilevel feedback queues remove that limit by letting processes move between queues. A new process starts in the highest-priority queue with a short quantum. Use the whole quantum and you drop a level, getting a longer quantum but lower priority; block before the quantum expires and you stay or rise.

That single heuristic identifies interactive work without ever being told which processes are interactive. A text editor blocks on input constantly, so it stays high; a compile loop burns full quanta, so it sinks. This is why MLFQ underpinned traditional Unix and Windows schedulers.

Linux's CFS reaches the same goal differently. Rather than queues and quanta it tracks each task's virtual runtime — CPU consumed, weighted by nice value — in a red-black tree, and always dispatches whichever task has the smallest. A task that blocked has accumulated little vruntime, so it naturally runs next; interactivity emerges from the accounting rather than a rule. Linux 6.6 replaced CFS with EEVDF, which adds an explicit deadline to bound latency rather than only balancing shares.

The six policies compared on the axes exams ask about
Algorithm	Preemptive	Optimises	Starvation risk	Main weakness
FCFS	No	Nothing in particular	None	Convoy effect
SJF	No	Average waiting time	Long jobs	Burst length is unknowable
SRTF	Yes	Average waiting time	Long jobs	More context switches
Round robin	Yes	Response time	None	Quantum choice is critical
Priority	Either	Important work first	Low priority	Needs aging; priority inversion
Multilevel feedback	Yes	Both, adaptively	Mitigated by aging	Many parameters to tune

Multilevel queue: fixed classes, fixed policies
Multilevel feedback: processes move, so interactivity is inferred
CFS runs whichever task has least weighted runtime
EEVDF adds latency deadlines on top of fair sharing