CPU Scheduling Algorithms

TL;DR — A scheduler decides which ready task runs next on a limited resource. Classic policies optimise time: FCFS is simple but suffers the convoy effect, SJF/SRTF provably minimise average waiting time but need burst knowledge and can starve long jobs, Round Robin trades waiting time for responsiveness via a quantum q, and priority scheduling needs aging to avoid starvation. Real-time systems add deadlines: EDF is feasible whenever utilisation ≤ 1, Rate-Monotonic only up to n(2^(1/n) − 1). Every one of these is work-conserving — it never idles a ready task — which is exactly why none of them can minimise a cost that varies over time.

---

1. Simple explanation

A scheduler answers one question, over and over: several tasks are ready, one resource is free — who goes next?

Every scheduling policy is a different answer, and each answer optimises something different. There is no universally best one, because the goals conflict:

• Finish everyone as fast as possible on average, or
• keep the system feeling responsive to whoever just arrived, or
• guarantee nobody misses a hard deadline, or
• be fair, so no task waits forever.

You cannot have all four. Picking a scheduler is picking which one you care about.

Analogy — a single coffee machine in an office.

Ten people want coffee.

• Serve them in the order they queued: FCFS. Dead simple, feels fair. But if the first person is brewing a 12-cup batch for a meeting, nine people with 30-second espressos wait behind them. That's the convoy effect.
• Serve the quickest order first: SJF. The average wait across everybody drops — provably, it's the best you can do. But the person with the big batch may never get served while quick orders keep arriving. That's starvation.
• Give everyone 60 seconds, then rotate: Round Robin. Nobody waits long for a turn, so the room feels responsive. But total time goes up, because you lose seconds every time you swap cups. That's context-switch overhead.
• Serve whoever has to leave for a meeting soonest: EDF. Now you're optimising deadlines, not speed.

One more property, and it's the one nobody states out loud: the machine is never left idle while someone is waiting. That assumption is called work-conserving, and it's baked into all of the above. Section 3.5 is about what happens when you break it.

---

2. Diagram

Four schedulers, same four tasks. Arrival and burst times: P1(arrive 0, needs 7) · P2(2, 4) · P3(4, 1) · P4(5, 4)

                 0    5    10   15
                 |....|....|....|.

  FCFS       P1  ███████                    finishes 7
  (run in     P2         ████                        11
   arrival     P3             █                      12
   order)       P4              ████                 16
               → avg wait 4.75   avg response 4.75
                 P1's long burst blocks everyone: the CONVOY EFFECT

  SJF        P1  ███████                             7
  (shortest   P3         █                           8
   ready       P2          ████                     12
   first)       P4              ████                16
               → avg wait 4.00   avg response 4.00
                 P3 (1 tick) jumps the queue ahead of P2/P4 → average wait drops

  SRTF       P1  ██                 █████           16
  (preempt    P2    ██ ██                            7
   if shorter   P3      █                            5
   arrives)      P4         ████                    11
               → avg wait 3.00   avg response 0.50   ← BEST average wait (optimal)
                 P1 is preempted twice and finishes last: starvation risk

  RR q=2     P1  ██  ██      ██  █                  16
  (rotate     P2    ██   ██                          9
   every 2)     P3       █                           7
                 P4        ██  ██                   15
               → avg wait 5.00   avg response 1.50   ← BEST responsiveness
                 worst average wait, but every task starts almost immediately

Read the tradeoff off the last two rows: SRTF wins on waiting (3.00), Round Robin wins on response (1.50), and neither wins both.

---

3. How it works

3.1 The four numbers you measure

For each task, given arrival, burst (CPU time needed), and completion:

Waiting and response are different, and confusing them is the most common mistake. A task can start instantly (great response) and still finish late (bad turnaround) if it keeps getting preempted — look at P1 under Round Robin above: response 0, waiting 9.

3.2 Preemptive vs non-preemptive

• Non-preemptive — once a task starts, it runs to completion. Simple, no mid-task switching cost, but one long task blocks everything.
• Preemptive — the scheduler can suspend a running task and switch. Better responsiveness, at the price of a context switch (saving registers, program counter, and stack; often invalidating cache).

Context switches are not free. If a switch costs s and your quantum is q, the fraction of the CPU actually doing work is q / (q + s). That single ratio is why q cannot be tiny.

3.3 The classic policies

Aging is the standard starvation fix: raise a task's priority the longer it waits, so anything ignored long enough eventually rises to the top.

MLFQ (multi-level feedback queue) is what real desktop kernels approximate: several queues at different priorities, new tasks enter high, tasks that use a full quantum get demoted, tasks that block early stay high. The effect is that interactive work is treated as short and CPU-bound work drifts down — SJF-like behaviour without knowing burst times in advance.

3.4 Real-time: when deadlines are the point

Everything above optimises averages. Real-time scheduling asks a yes/no question instead: can every task meet its deadline?

For n periodic tasks where task i needs C_i of CPU every T_i period, define utilisation U = Σ C_i / T_i:

• EDF (Earliest Deadline First) — dynamic priority; always run whatever is due soonest. On one CPU, EDF meets every deadline if and only if U ≤ 1. That's optimal: no algorithm can schedule a set EDF cannot.
• RMS (Rate Monotonic) — static priority; shorter period = higher priority forever. Simpler and more predictable, but only guaranteed up to the Liu & Layland bound U ≤ n(2^(1/n) − 1), which falls from 1.000 at n=1 to 0.828 at n=2, 0.757 at n=4, and toward ln 2 ≈ 0.693 as n → ∞. So RMS can waste ~30% of the CPU.
• LLF (Least Laxity First) — run whatever has the least slack, where laxity = deadline − now − remaining_work. A task with laxity 0 must run this instant or it misses. LLF is optimal on one CPU too, but it thrashes: two tasks with equal laxity swap constantly.

Note the vocabulary here — deadline, laxity, slack, release time. It reappears verbatim in cost-based scheduling, which is where this article connects to Greedy Scheduling & Interval Selection.

3.5 Work-conserving — the assumption nobody states

Every algorithm in this article shares a property so basic it usually goes unmentioned:

A work-conserving scheduler never leaves the resource idle while a task is ready to run.

It's the right default for an operating system. An idle CPU with work queued is pure waste, and deliberately idling would be a bug.

But it also means no scheduler above can ever choose to wait for a better moment — because "waiting" means idling. And that is precisely what you must do when the cost of running changes over time:

  cost of running per unit time:   ███████░░░░░░░
                                   0  1  2  3  4  5
                                   └ expensive ┘└ cheap ┘

  WORK-CONSERVING (any OS scheduler)   task ready at t=0 → RUN AT t=0
                                       ▓▓                  no choice: idling is forbidden

  NON-WORK-CONSERVING (cost-aware)     task ready at t=0 → WAIT, run at t=3
                                             ▓▓            deliberately idle to pay less

The second row is not a scheduling algorithm from this article. It is a different problem — minimising an external time-varying cost subject to a deadline — and it needs different tools (a sliding min-cost window, or min-cost flow when tasks share capacity). That's covered in Scheduling Under a Time-Varying Cost Signal.

Takeaway: OS scheduling and cost-aware scheduling share the whole vocabulary — release time, deadline, slack, preemption — and share none of the objective. Recognising which of the two you're in is most of the work.

---

4. The math

4.1 The averages

For n tasks:

  avg turnaround = (1/n) Σ (completion_i − arrival_i)
  avg waiting    = (1/n) Σ (turnaround_i − burst_i)
  avg response   = (1/n) Σ (first_run_i − arrival_i)

4.2 Why SJF minimises average waiting time

Take n tasks all available at time 0, run non-preemptively in some order. If the order is b_1, b_2, …, b_n, then task k waits for everything before it:

  total waiting = Σ_{k=1..n} Σ_{j<k} b_j  =  Σ_{j=1..n} (n − j) · b_j

The coefficient (n − j) shrinks as j grows. To minimise the sum, pair the largest coefficient with the smallest burst — i.e. sort ascending by burst. That's SJF.

The proof is an exchange argument: if any adjacent pair is out of order (b_j > b_{j+1}), swapping them lowers the total by b_j − b_{j+1} > 0. No swap can improve a fully sorted order, so sorted is optimal. Same proof shape as activity selection in Greedy Scheduling & Interval Selection §3.4.

4.3 Round Robin's response guarantee

With n ready tasks and quantum q, a task waits at most one full cycle of the others before its first turn:

  response ≤ (n − 1) · q          and    CPU efficiency = q / (q + s)

Two forces pull opposite ways. Small q → good response, bad efficiency. Large q → Round Robin degenerates into FCFS. Real kernels land in the low milliseconds.

4.4 Real-time feasibility

  utilisation      U = Σ C_i / T_i

  EDF feasible  ⟺  U ≤ 1                        (optimal on one CPU)
  RMS feasible  ⟸  U ≤ n·(2^(1/n) − 1)          (sufficient, not necessary)

4.5 Worked example

P1(0, 7) · P2(2, 4) · P3(4, 1) · P4(5, 4) — the Gantt charts in §2, tabulated:

Verify SRTF's waiting column by hand: P1 needs 7 ticks but finishes at 16, so it waited 16 − 0 − 7 = 9. P3 arrives at 4, runs immediately, finishes at 5 — waited 0. Total waiting 9 + 1 + 0 + 2 = 12, average 3.00. That 3.00 is the floor: no scheduler can beat it on this input.

Note also that RR has the worst average waiting yet the second-best response. If your metric had been "how fast does something start," you'd have drawn the opposite conclusion about which scheduler is best. Pick the metric before the algorithm.

---

5. Real code

"""Four classic CPU schedulers, simulated. Runnable as-is."""
from collections import deque
from dataclasses import dataclass


@dataclass
class Proc:
    pid: str
    arrival: int
    burst: int


JOBS = [Proc("P1", 0, 7), Proc("P2", 2, 4), Proc("P3", 4, 1), Proc("P4", 5, 4)]


def report(name, finish, first):
    """Print per-task metrics and the three averages."""
    rows = []
    for p in JOBS:
        turnaround = finish[p.pid] - p.arrival
        rows.append((p.pid, turnaround, turnaround - p.burst, first[p.pid] - p.arrival))
    n = len(rows)
    print(f"{name:34} tat={sum(r[1] for r in rows)/n:5.2f} "
          f"wait={sum(r[2] for r in rows)/n:5.2f} resp={sum(r[3] for r in rows)/n:5.2f}")


def fcfs():
    """Non-preemptive, strictly in arrival order."""
    t, finish, first = 0, {}, {}
    for p in sorted(JOBS, key=lambda p: (p.arrival, p.pid)):
        t = max(t, p.arrival)          # CPU may idle waiting for the next arrival
        first[p.pid] = t
        t += p.burst
        finish[p.pid] = t
    report("FCFS", finish, first)


def sjf():
    """Non-preemptive: among tasks that have arrived, run the shortest."""
    t, done, finish, first = 0, set(), {}, {}
    while len(done) < len(JOBS):
        ready = [p for p in JOBS if p.arrival <= t and p.pid not in done]
        if not ready:                  # nothing here yet — jump to the next arrival
            t = min(p.arrival for p in JOBS if p.pid not in done)
            continue
        p = min(ready, key=lambda p: (p.burst, p.arrival, p.pid))
        first[p.pid] = t
        t += p.burst
        finish[p.pid] = t
        done.add(p.pid)
    report("SJF (non-preemptive)", finish, first)


def srtf():
    """Preemptive SJF, re-decided every tick on remaining time."""
    rem = {p.pid: p.burst for p in JOBS}
    t, finish, first = 0, {}, {}
    while any(v > 0 for v in rem.values()):
        ready = [p for p in JOBS if p.arrival <= t and rem[p.pid] > 0]
        if not ready:
            t += 1
            continue
        p = min(ready, key=lambda p: (rem[p.pid], p.arrival, p.pid))
        first.setdefault(p.pid, t)     # only the FIRST time it runs counts for response
        rem[p.pid] -= 1
        t += 1
        if rem[p.pid] == 0:
            finish[p.pid] = t
    report("SRTF (preemptive)", finish, first)


def round_robin(q=2):
    """Rotate through the ready queue, q ticks at a time."""
    rem = {p.pid: p.burst for p in JOBS}
    pending = sorted(JOBS, key=lambda p: (p.arrival, p.pid))
    t, i, ready, finish, first = 0, 0, deque(), {}, {}
    while i < len(pending) or ready:
        while i < len(pending) and pending[i].arrival <= t:
            ready.append(pending[i])
            i += 1
        if not ready:                  # idle until the next arrival
            t = pending[i].arrival
            continue
        p = ready.popleft()
        first.setdefault(p.pid, t)
        run = min(q, rem[p.pid])
        t += run
        rem[p.pid] -= run
        while i < len(pending) and pending[i].arrival <= t:  # arrivals during this slice
            ready.append(pending[i])
            i += 1
        if rem[p.pid] == 0:
            finish[p.pid] = t
        else:
            ready.append(p)            # requeue at the back
    report(f"Round Robin (q={q})", finish, first)


if __name__ == "__main__":
    fcfs()
    sjf()
    srtf()
    round_robin(2)

# Output:
#   FCFS                               tat= 8.75 wait= 4.75 resp= 4.75
#   SJF (non-preemptive)               tat= 8.00 wait= 4.00 resp= 4.00
#   SRTF (preemptive)                  tat= 7.00 wait= 3.00 resp= 0.50
#   Round Robin (q=2)                  tat= 9.00 wait= 5.00 resp= 1.50

Two details worth copying into your own simulators. First, first.setdefault(...) rather than first[...] = t — response time is about the first time a task runs, and a preemptive scheduler will schedule it many times. Second, the while ... pending[i].arrival <= t loop appears twice in Round Robin, before and after the slice: tasks that arrive mid-slice must be enqueued before the preempted task is requeued, or the rotation order is wrong.

---

6. Real-world example

Where each policy actually shows up:

A concrete case of the convoy effect. A shared build server runs jobs FCFS. Someone submits a 40-minute full-repo build; twelve 20-second lint jobs queue behind it. Average waiting time is roughly 20 minutes even though the total lint work is four minutes. Switching to SJF-with-aging drops average waiting an order of magnitude while still guaranteeing the big build eventually runs — that's aging preventing the starvation that pure SJF would cause.

---

7. Interview questions companies actually ask

Q1. Difference between waiting time and response time? Waiting is total time ready-but-not-running (turnaround − burst); response is time until the task first runs. Preemptive schedulers can give excellent response and poor waiting for the same task — under Round Robin above, P1 had response 0 and waiting 9.

Q2. Prove SJF minimises average waiting time. With all tasks present at t=0, total waiting = Σ (n − j)·b_j. Coefficients decrease with position, so pairing the biggest coefficient with the smallest burst minimises the sum — sort ascending. Formally, an exchange argument: swapping any adjacent out-of-order pair reduces total waiting by b_j − b_{j+1} > 0.

Q3. If SJF is optimal, why doesn't every OS use it? It needs burst times in advance, which are unknowable, and it starves long jobs. Kernels approximate it instead — MLFQ demotes tasks that consume full quanta, so short/interactive work naturally floats up without anyone predicting burst length.

Q4. What is the convoy effect? Under FCFS, one long CPU-bound task at the head makes many short tasks wait, tanking average waiting time and responsiveness. Fixed by preemption or by shortest-first ordering.

Q5. How do you pick the Round Robin quantum? Balance response ≤ (n − 1)·q against efficiency q / (q + s) where s is switch cost. Too small and you spend the CPU on context switches; too large and RR degenerates to FCFS. Rule of thumb: q well above s, and large enough that most interactive bursts finish within one quantum.

Q6. Starvation vs deadlock? Deadlock: tasks are blocked forever in a cycle of held resources — nothing progresses. Starvation: the system progresses fine, but one task never gets picked. Deadlock needs prevention/detection; starvation is usually fixed with aging or fair queuing.

Q7. EDF vs Rate Monotonic — when would you choose RMS? EDF is optimal (feasible iff U ≤ 1) but needs dynamic priorities and degrades unpredictably on overload. RMS uses fixed priorities — simpler, easier to certify, more predictable under overload (low-priority tasks fail first) — at the cost of only guaranteeing up to n(2^(1/n) − 1), about 0.69 in the limit. Safety-critical systems often take the predictability.

Q8. What does "work-conserving" mean, and when is it wrong? It means never idling the resource while work is ready. It's right whenever running is free. It's wrong when running has a time-varying cost — energy price, grid carbon intensity, surge pricing — because then deliberately idling until a cheaper hour is the correct move. That is a different problem class from OS scheduling, even though it borrows the same deadline/slack vocabulary.

Q9. Least-laxity-first — definition and weakness? laxity = deadline − now − remaining_work; run the smallest. Optimal on one CPU, but two tasks with equal laxity preempt each other repeatedly, so it thrashes. EDF gives the same guarantee with far fewer switches.

Q10. How would you schedule to minimise electricity cost rather than latency? Stop using an OS scheduler. Deadlines become feasibility constraints and the objective becomes Σ cost(t) · usage(t). For an independent task, slide its fixed-length window over the cost array and pick the cheapest feasible start. If tasks share a per-hour capacity, model it as min-cost flow for an exact optimum.

---

8. When to use / tradeoffs

Choose by the metric you actually care about:

Honest limits. These models assume burst times are known, context switches are free or a fixed s, and there is exactly one resource. Real systems violate all three: bursts are unknown (hence MLFQ), switches invalidate caches so the true cost varies with what ran before, and multicore adds affinity, migration cost, and load balancing — where EDF's neat U ≤ 1 guarantee no longer holds. Treat everything here as the right vocabulary and the right intuition, not as a formula to apply directly to a modern kernel.

---

9. Summary + related articles

• A scheduler picks the next task; which policy is "best" depends entirely on which metric you chose — waiting, response, deadlines, or fairness.
• turnaround = completion − arrival, waiting = turnaround − burst, response = first_run − arrival. Waiting ≠ response.
• FCFS is simple but convoys. SJF/SRTF provably minimise average waiting (exchange argument) but need burst times and starve long jobs. Round Robin buys response with response ≤ (n−1)q, paying q/(q+s) in efficiency. Priority needs aging. MLFQ approximates SJF without predictions.
• Real-time flips the question to feasibility: EDF is optimal at U ≤ 1; RMS only guarantees U ≤ n(2^(1/n) − 1) → ln 2.
• Every policy here is work-conserving — it never idles a ready task. So none of them can minimise a cost that varies with time; that needs a deliberately idling planner and different algorithms.

Related:

• Greedy Scheduling & Interval Selection — the exchange argument, and min-cost windows
• Scheduling Under a Time-Varying Cost Signal — the non-work-conserving case
• Carbon-Aware Scheduling of Flexible Loads — where the cost signal is grid carbon intensity
• Complexity Analysis — the O(n log n) sorting bound behind SJF
• System Basics — processes, threads, and context switching

Resources

• Silberschatz, Galvin, Gagne — Operating System Concepts, Ch. 5 "CPU Scheduling" (FCFS/SJF/RR/priority/MLFQ, worked Gantt charts).
• Arpaci-Dusseau & Arpaci-Dusseau — Operating Systems: Three Easy Pieces, "Scheduling: Introduction" and "The Multi-Level Feedback Queue" — free at https://pages.cs.wisc.edu/~remzi/OSTEP/
• Liu, C. L. & Layland, J. W. (1973). "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment." JACM 20(1), 46–61 — the origin of the RMS utilisation bound and EDF optimality.
• Linux CFS design notes — https://docs.kernel.org/scheduler/sched-design-CFS.html
• Earliest deadline first scheduling — https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling