SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 23
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 23 of 90

CPU scheduling 3: Round Robin, HRRN, multilevel queues and real-time

Round Robintime quantum and its effectcontext-switch overhead numericalsHRRN and response ratiomultilevel queue schedulingmultilevel feedback queue (MLFQ)multiprocessor schedulingload balancingprocessor affinityreal-time scheduling (rate monotonic, earliest deadline first)Linux CFSscheduling simulation in code

These are the notes for CS Fundamentals for Placements, episode 23, the last of three CPU-scheduling episodes. SRTF (episode 22) gives the best average waiting time, but it needs to know the future and can starve long jobs, and it does nothing for a user who wants a keypress handled now. Today you invent Round Robin with its time quantum, learn how context-switch overhead decides the quantum, HRRN and the response ratio, multilevel queue and multilevel feedback queue (MLFQ) scheduling, multiprocessor scheduling (load balancing, processor affinity), real-time scheduling (rate monotonic, earliest deadline first), and what Linux actually does (CFS, EEVDF). Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: the Python code was run with Python 3.13 on 2 November 2026, exactly as in the SyntaxPilot compiler.

Refresher: AT arrival time, BT burst time (CPU time needed), CT completion time, TAT = CT − AT, WT = TAT − BT, RT (response time) = first time on the CPU − AT. A context switch saves one process's state and loads another's; it costs time and does no useful work (episode 17). A timer interrupt is a hardware alarm that hands control back to the OS.

The six problems

Problem What it teaches
Everyone wants a turn now Round Robin, time quantum, circular ready queue
How long is a turn? Quantum trade-off, context-switch overhead numericals
Short first, but no starving HRRN, response ratio
Different kinds of work Multilevel queue, multilevel feedback queue
Many cores SMP, per-core queues, load balancing, processor affinity
Hard deadlines Periodic tasks, rate monotonic, EDF; Linux CFS and EEVDF

Problem 1: everyone wants a turn now (Round Robin)

Real-life example: the pani puri vendor. Customers stand around the stall with their plates. The vendor never gives one person six puris in a row: one puri to each, in turn. Still hungry? Wait for the next round, which comes soon.

Pani puri stall Round Robin
Customers in a circle Ready queue, served as a circular first-in-first-out (FIFO) queue
One puri each Time quantum (time slice): a small fixed amount of CPU time, typically 10-100 ms
Wait for the next round If unfinished when the quantum ends, a timer interrupt preempts the process and it goes to the back of the queue

If a process finishes (or blocks for I/O) before its quantum ends, it gives up the CPU early and the next process starts at once. With n processes and quantum Q, no process waits more than (n − 1)·Q for its next turn, so response time is good. Round Robin is preemptive and starvation-free.

Round Robin simulator (Q = 2)

from collections import deque
procs = [("P1", 0, 5), ("P2", 1, 3), ("P3", 2, 1), ("P4", 3, 2)]
Q = 2                               # time quantum
left = {n: bt for n, at, bt in procs}

time, i, queue, gantt, ct = 0, 0, deque(), "", {}
def admit():                        # newly arrived -> back of the queue
    global i
    while i < len(procs) and procs[i][1] <= time:
        queue.append(procs[i][0])
        i += 1
admit()
while left:
    name = queue.popleft()
    run = min(Q, left[name])        # one slice, or less if it finishes
    gantt += f"| {name} {time}-{time + run} "
    time += run
    left[name] -= run
    admit()                         # arrivals join before the preempted one
    if left[name]:
        queue.append(name)          # unfinished: back of the line
    else:
        del left[name]
        ct[name] = time
print(gantt + "|")
wt = {n: ct[n] - at - bt for n, at, bt in procs}
print("WT:", wt, " avg =", sum(wt.values()) / len(wt))

Output:

| P1 0-2 | P2 2-4 | P3 4-5 | P1 5-7 | P4 7-9 | P2 9-10 | P1 10-11 |
WT: {'P1': 6, 'P2': 6, 'P3': 2, 'P4': 4}  avg = 4.5

A deque (double-ended queue, from Python's collections) lets us take from the front and add to the back quickly. (This simulator assumes the CPU is never idle; add an idle step like episode 21's if arrivals can leave gaps.)

By hand: write the queue after every slice

Time Runs Queue after the slice Note
0-2 P1 P2 P3 P1 P2, P3 arrived during the slice
2-4 P2 P3 P1 P4 P2 P4 arrived at 3
4-5 P3 P1 P4 P2 P3 done (needed only 1)
5-7 P1 P4 P2 P1
7-9 P4 P2 P1 P4 done
9-10 P2 P1 P2 done
10-11 P1 — P1 done

Convention: a process that arrives at the same moment a slice ends joins the queue before the preempted process (the standard GATE convention; follow the question if it says otherwise).

P AT BT CT TAT WT RT
P1 0 5 11 11 6 0
P2 1 3 10 9 6 1
P3 2 1 5 3 2 2
P4 3 2 9 6 4 4

Average WT = 18/4 = 4.5, average TAT = 29/4 = 7.25, average RT = 7/4 = 1.75. Waiting is a bit worse than SRTF (3.0), but response time is far better, which is what interactive users feel.

Problem 2: how long is a turn? (quantum and overhead)

Every switch costs time. Here one switch wastes 1 unit, and we try Q = 1, 4, 100 on one long job (24) and two short ones (3), all arriving at 0.

def rr(bursts, Q, CS):              # all arrive at 0; CS = switch cost
    left, time, switches = list(bursts), 0, 0
    finish = [0] * len(bursts)
    while any(left):
        for k in range(len(left)):
            if left[k] == 0:
                continue
            run = min(Q, left[k])
            time += run
            left[k] -= run
            if left[k] == 0:
                finish[k] = time
            others = [x for j, x in enumerate(left) if j != k and x]
            if others:              # someone else runs next: a switch
                time += CS
                switches += 1
    print(f"Q={Q:3}  switches={switches:2}  avg TAT={sum(finish) / 3:5.1f}"
          f"  useful CPU={sum(bursts) / time:.0%}")

jobs = [24, 3, 3]                   # one long job, two short ones
for Q in [1, 4, 100]:
    rr(jobs, Q, CS=1)               # each switch wastes 1 unit

Output:

Q=  1  switches= 9  avg TAT= 23.7  useful CPU=77%
Q=  4  switches= 3  avg TAT= 17.7  useful CPU=91%
Q=100  switches= 2  avg TAT= 28.0  useful CPU=94%
Quantum Effect
Very large (≥ every burst) Round Robin becomes FCFS (convoy effect: avg TAT 28)
Very small Most time goes to context switches (23% wasted at Q = 1)
Just right Rule of thumb: about 80% of CPU bursts shorter than Q

Overhead formulas (all processes use their full quantum)

  • CPU efficiency = Q / (Q + s), where s = context-switch time.
  • Maximum time before a process's next turn = (n − 1)(Q + s) for n processes.
  • To guarantee each process its next turn within T: (n − 1)(Q + s) ≤ T → Q ≤ T/(n − 1) − s.

Example: Q = 4, s = 1, n = 5 → efficiency 4/5 = 80%, maximum wait (5 − 1)(4 + 1) = 20.

Problem 3: short first, but no starving (HRRN)

Round Robin ignores job length; SJF uses it but starves long jobs. Real-life example: a fair bank manager lets a quick deposit go before a two-hour loan file, but if the loan customer has already waited two hours, it's his turn.

Highest Response Ratio Next (HRRN), non-preemptive:

Response ratio = (W + S) / S, where W = time waited so far, S = service (burst) time.

The ratio is always ≥ 1. Short jobs get high ratios quickly; a long job's ratio keeps growing as it waits, so it cannot starve.

Numerical

P AT BT
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2
  • A runs 0-3. At 3 only B has arrived: B runs 3-9.
  • At 9: C (5 + 4)/4 = 2.25, D (3 + 5)/5 = 1.6, E (1 + 2)/2 = 1.5 → C runs 9-13.
  • At 13: D (7 + 5)/5 = 2.4, E (5 + 2)/2 = 3.5 → E runs 13-15, then D 15-20.
P CT TAT WT
A 3 3 0
B 9 7 1
C 13 9 5
D 20 14 9
E 15 7 5

Average TAT = 40/5 = 8, average WT = 20/5 = 4. Cost: like SJF, HRRN needs burst estimates.

Problem 4: different kinds of work (multilevel queues)

Real-life example: separate windows at a railway reservation hall.

Window Queue Typical algorithm
Emergency / staff quota (always first) System processes highest priority
Senior citizens (quick service) Interactive (foreground) processes, the ones a user is typing into Round Robin, small quantum
General, bulk bookings Batch (background) processes, no user waiting FCFS

Multilevel queue scheduling: the ready queue is split into several queues; each process is permanently assigned to one (by type, memory size, priority); each queue has its own algorithm. Between queues:

  • Fixed priority: a lower queue runs only if all higher queues are empty (lower queues can starve).
  • Time slicing between queues: e.g. 80% of CPU time to interactive (RR), 20% to batch (FCFS).

Problems: lower queues can starve; a process can't change queue when its behaviour changes; and the OS must know in advance what kind each process is.

Multilevel feedback queue (MLFQ)

Real-life example: customer-support tiers. Every call starts at tier 1 with 5 minutes; unsolved calls escalate to tier 2 with more time; the hardest go to engineers who take as long as needed; a ticket waiting too long is bumped up.

MLFQ lets processes move between queues based on behaviour:

  • New processes enter the top queue (small quantum).
  • A process that uses its whole quantum is CPU-hungry: demote it one level.
  • A process that gives up the CPU early (waits for I/O, like an editor) stays high, so interactive jobs get fast response.
  • Aging: a process waiting too long in a low queue is promoted, so nothing starves.

An MLFQ is defined by: the number of queues, the algorithm of each queue, when to demote, when to promote, and which queue a new process enters. Example (classic textbook setup): Q0 RR with quantum 8, Q1 RR with quantum 16, Q2 FCFS; a lower queue runs only when higher ones are empty. A 30-unit job gets 8 in Q0, 16 in Q1, its last 6 in Q2.

Mini project: an MLFQ simulator

from collections import deque

QUANTA = [8, 16, None]              # Q0, Q1: Round Robin; Q2: FCFS
jobs = {"A": 30, "B": 6, "C": 20}   # all arrive at 0, burst times
queues = [deque(jobs), deque(), deque()]
left, time = dict(jobs), 0

while any(queues):
    level = next(i for i, q in enumerate(queues) if q)   # highest non-empty
    name = queues[level].popleft()
    q = QUANTA[level]
    run = left[name] if q is None else min(q, left[name])
    print(f"t={time:3}  Q{level}  {name} runs {run}")
    time += run
    left[name] -= run
    if left[name] == 0:
        print(f"        {name} finishes at {time}")
    else:                           # used its whole quantum: demote
        queues[min(level + 1, 2)].append(name)

Output:

t=  0  Q0  A runs 8
t=  8  Q0  B runs 6
        B finishes at 14
t= 14  Q0  C runs 8
t= 22  Q1  A runs 16
t= 38  Q1  C runs 12
        C finishes at 50
t= 50  Q2  A runs 6
        A finishes at 56

The short job B finished in its first turn; the long job A sank to the bottom. Extensions to try: arrivals over time, preempting a lower queue when a higher one gets a job, and aging (promote anything that waited more than 40 units).

Problem 5: many cores (multiprocessor scheduling)

Real-life example: supermarket billing counters.

Supermarket Multicore scheduling
One shared line for all counters, or a line per counter Common ready queue vs per-core run queues
One supervisor decides everything Asymmetric multiprocessing: one master core makes all scheduling decisions
Every counter calls its own next customer Symmetric multiprocessing (SMP): each core schedules itself (what most modern operating systems use)
Manager moves people to an idle counter Load balancing: keep work evenly spread
Your items are half scanned; moving means starting over Processor affinity: keep a process on the core whose cache holds its data
  • Push migration: a periodic task checks loads and pushes processes from busy cores to idle ones.
  • Pull migration: an idle core pulls a waiting process from a busy core.
  • Soft affinity: the OS tries to keep a process on the same core but may move it. Hard affinity: the program pins itself to specific cores (on Linux, sched_setaffinity / taskset).
  • Load balancing and affinity pull in opposite directions: moving a process balances load but leaves its cache "cold" (its data is not in the new core's cache yet, episode 10).
  • On NUMA machines (non-uniform memory access, episode 11), moving a process to a far socket also makes its memory slower.

Problem 6: hard deadlines (real-time scheduling)

A real-time system must finish work on time (episode 15: hard real-time = a missed deadline is a failure, e.g. an airbag; soft real-time = a missed deadline lowers quality, e.g. video).

Periodic task: released every period p, needs CPU time c each time; its deadline is the end of its period. CPU utilisation U = Σ c/p. If U > 1, no algorithm can meet all deadlines.

Algorithm Priorities Guarantee (single core)
Rate monotonic (RM) Fixed: shorter period = higher priority All deadlines met if U ≤ n(2^(1/n) − 1) (n = 2: 0.828; n → ∞: about 0.693)
Earliest Deadline First (EDF) Dynamic: the soonest deadline runs All deadlines met if U ≤ 1 (optimal)

The RM bound is sufficient, not necessary: a task set above it may still be schedulable, you just have to check (simulate up to the least common multiple of the periods).

RM vs EDF, simulated

tasks = {"P1": (50, 25), "P2": (80, 35)}   # name: (period, CPU time)
POLICY = "RM"                       # RM: shorter period = higher priority

left, deadline, missed = {}, {}, 0
for t in range(400):                # simulate 400 time units
    for name, (period, cpu) in tasks.items():
        if t % period == 0:         # a new instance is released
            if left.get(name, 0) > 0:
                print(f"t={t}: {name} MISSED its deadline!")
                missed += 1
            left[name], deadline[name] = cpu, t + period
    ready = [n for n in tasks if left.get(n, 0) > 0]
    if not ready:
        continue                    # CPU idle this unit
    if POLICY == "RM":
        name = min(ready, key=lambda n: tasks[n][0])     # fixed priority
    else:
        name = min(ready, key=lambda n: deadline[n])     # earliest deadline
    left[name] -= 1
U = sum(c / p for p, c in tasks.values())
print(f"{POLICY}: U = {U}, deadlines missed = {missed}")

Output with POLICY = "RM":

t=80: P2 MISSED its deadline!
RM: U = 0.9375, deadlines missed = 1

Output with POLICY = "EDF":

EDF: U = 0.9375, deadlines missed = 0

Why RM missed: U = 25/50 + 35/80 = 0.5 + 0.4375 = 0.9375 > 0.828. P1 runs 0-25, P2 25-50, P1's second instance (higher priority) takes 50-75, P2 gets only 75-80: 30 of its 35 units by its deadline 80. EDF: at 50, P2's deadline (80) is earlier than P1's (100), so P2 keeps the CPU and finishes at 60; P1 still finishes by 85 < 100. (For comparison, P1 (50, 20) and P2 (100, 35) give U = 0.75 ≤ 0.828: RM meets every deadline.)

What Linux actually does

From the Linux kernel documentation (docs.kernel.org, fetched 2 November 2026):

  • CFS, the Completely Fair Scheduler, merged in Linux 2.6.23, models an "ideal, precise multi-tasking CPU" that runs every task at once at an equal share of its speed. Since real hardware runs one task at a time per core, CFS tracks each task's virtual runtime (vruntime): CPU time received, scaled by the number of tasks. Runnable tasks are kept in a red-black tree (a self-balancing sorted binary tree) ordered by vruntime, and CFS always runs the leftmost task, the one that has had the least CPU. As a task runs its vruntime grows and it moves right, so every task eventually reaches the left: no starvation.
  • nice values run from −20 (most favourable) to 19 (least favourable) (nice(1) man page). In CFS they act as weights: a lower nice value makes vruntime grow more slowly, so the task gets a bigger share, but nobody gets zero.
  • EEVDF (Earliest Eligible Virtual Deadline First): Linux began transitioning to EEVDF in version 6.6. Each task has a lag (how much CPU it is owed compared with its fair share: positive = owed, negative = has had more than its share). Tasks with lag ≥ 0 are eligible; each gets a virtual deadline, and the scheduler runs the eligible task with the earliest virtual deadline. It combines two ideas from this episode: fair shares and earliest deadline first.

Sources: https://docs.kernel.org/7.2/scheduler/sched-design-CFS.html, https://docs.kernel.org/7.2/scheduler/sched-eevdf.html, https://man7.org/linux/man-pages/man1/nice.1.html.

The whole chain

Step Problem Invention
1 Everyone wants a turn now Round Robin
2 How long is a turn? Quantum trade-off, Q/(Q + s)
3 Short first without starving HRRN, (W + S)/S
4 Different kinds of work Multilevel queue → MLFQ
5 Many cores SMP, load balancing vs affinity
6 Deadlines RM, EDF; Linux CFS → EEVDF

All scheduling algorithms (episodes 21-23)

Algorithm Preemptive? Starvation? Needs burst time? Best for
FCFS No No No Simplicity, batch
SJF No Yes Yes Min avg WT (non-preemptive)
SRTF Yes Yes Yes Min avg WT overall
Priority Either Yes (fix: aging) No Urgent work first
Round Robin Yes No No Time-sharing, response time
HRRN No No Yes Balance short-first and fairness
Multilevel queue Depends Yes (fixed priority) No Mixed workloads
MLFQ Yes No (with aging) No (it learns) General-purpose OSes
RM / EDF Yes — Yes (c, p) Real-time deadlines

Common mistakes

Mistake What you see Why Fix
Putting the preempted process before new arrivals a different RR Gantt chart Wrong queue convention New arrivals first, unless told otherwise
Giving a full quantum to a job with less left idle CPU in the chart A slice is min(Q, remaining) Finish early, next one starts
HRRN with burst time on top ratios below 1 Formula flipped (W + S)/S, always ≥ 1
"U < 1, so RM always works" t=80: P2 MISSED its deadline! RM's bound is lower RM: U ≤ n(2^(1/n) − 1); EDF: U ≤ 1
Thinking a tiny quantum is always better useful CPU=77% at Q = 1 Context switches cost time Q larger than most bursts
Counting a switch when the same process continues alone too many switches Nothing to switch to Count only real changes

Practice

1. Round Robin, Q = 2: P1 (AT 0, BT 4), P2 (1, 5), P3 (2, 2), P4 (3, 1). Find the average WT.

Solution

Queue trace: P1 0-2 → [P2 P3 P1]; P2 2-4 → [P3 P1 P4 P2]; P3 4-6 (done); P1 6-8 (done); P4 8-9 (done); P2 9-12 (done). Gantt: | P1 0-2 | P2 2-4 | P3 4-6 | P1 6-8 | P4 8-9 | P2 9-12 |. CT = 8, 12, 6, 9; WT = 4, 6, 2, 5; average = 17/4 = 4.25 (the simulator prints avg = 4.25).

2. Q = 5, switch time s = 1, n = 6 processes. Find CPU efficiency and the maximum wait for a next turn.

Solution

Efficiency = 5/6 = 83.3%. Maximum wait = (6 − 1)(5 + 1) = 30.

3. MLFQ with Q0 = RR 8, Q1 = RR 16, Q2 = FCFS. Where does a 40-unit job run?

Solution

8 units in Q0 (then demoted), 16 in Q1 (demoted), the last 16 in Q2.

4. Is P1 (p = 20, c = 5), P2 (p = 30, c = 10) schedulable by rate monotonic?

Solution

U = 5/20 + 10/30 = 0.25 + 0.333 = 0.583 ≤ 0.828 (two-task bound), so yes, RM meets every deadline (and so does EDF).

5. HRRN: at time 10, X has waited 6 and needs 3; Y has waited 9 and needs 9. Who runs?

Solution

X: (6 + 3)/3 = 3. Y: (9 + 9)/9 = 2. X runs.

6. Why do interactive processes stay in the top queue of an MLFQ?

Solution

They usually block for I/O (a keypress, a click) before their small quantum ends, so they never use a full quantum and are never demoted. CPU-bound jobs use full quanta and sink.

Quick quiz

Process AT BT
P1 0 5
P2 0 4
P3 0 2

Round Robin, Q = 3: what is the average waiting time? A. 5 B. 5.33 C. 6 D. 6.33

Answer

C. 6. Gantt: P1 0-3, P2 3-6, P3 6-8, P1 8-10, P2 10-11. WT: P1 = 10 − 5 = 5, P2 = 11 − 4 = 7, P3 = 8 − 2 = 6. Average = 18/3 = 6.

Interview questions

  1. Explain Round Robin. Each ready process gets one time quantum in turn; unfinished processes are preempted by the timer and go to the back of the queue.
  2. What happens if the quantum is very large or very small? Large: it becomes FCFS. Small: context-switch overhead dominates.
  3. How do you pick a quantum? Larger than most CPU bursts (about 80%), much larger than the switch time.
  4. Does Round Robin cause starvation? No; every process gets a turn within (n − 1)(Q + s).
  5. What is HRRN? Non-preemptive; run the highest (W + S)/S; favours short jobs but ages long ones.
  6. Multilevel queue vs multilevel feedback queue? MLQ fixes a process to one queue; MLFQ moves processes by behaviour (demote CPU hogs, promote waiters).
  7. What is processor affinity? Soft vs hard? Keeping a process on the core with its warm cache; soft = preference, hard = pinned.
  8. Push vs pull migration? A periodic check pushes work off busy cores; an idle core pulls work.
  9. Rate monotonic vs EDF? RM: fixed priority by period, guaranteed up to n(2^(1/n) − 1); EDF: dynamic, earliest deadline, guaranteed up to U = 1.
  10. How does Linux schedule normal tasks? CFS: run the task with the smallest vruntime from a red-black tree; since 6.6 Linux has been moving to EEVDF (lag and virtual deadlines).

Glossary

Term Meaning in plain words Example
Round Robin (RR) Preemptive: each ready process gets one quantum in turn pani puri, one each
Time quantum / time slice The fixed CPU time per turn Q = 2
Circular queue A FIFO queue where the preempted process goes to the back the circle of customers
Deque Double-ended queue: fast add/remove at both ends collections.deque
Context-switch overhead Time spent switching, doing no useful work 1 unit per switch
CPU efficiency Useful time ÷ total time = Q/(Q + s) 80%
HRRN Highest Response Ratio Next, non-preemptive bank manager
Response ratio (W + S)/S: waiting plus service, over service (5 + 4)/4 = 2.25
Service time Burst time, the CPU time a job needs S = 4
Multilevel queue (MLQ) Several ready queues, each process fixed to one railway windows
Foreground / interactive process A process a user is waiting on an editor
Background / batch process No user waiting a nightly backup
Fixed-priority between queues A lower queue runs only if all higher are empty system first
Time slicing between queues Each queue gets a share of CPU time 80% / 20%
Multilevel feedback queue (MLFQ) Queues plus rules that move processes between them support tiers
Demotion Moving a CPU-hungry process to a lower queue used its whole quantum
Promotion (aging) Moving a long-waiting process up no starvation
Multiprocessor scheduling Scheduling on several CPUs/cores billing counters
Asymmetric multiprocessing One master core makes all scheduling decisions one supervisor
Symmetric multiprocessing (SMP) Every core schedules itself each counter calls "next"
Per-core run queue A separate ready queue for each core a line per counter
Load balancing Keeping work evenly spread across cores manager moves people
Push migration A periodic task moves work off busy cores —
Pull migration An idle core takes work from a busy one —
Processor affinity Preferring to keep a process on the same core half-scanned items
Soft / hard affinity A preference / a rule (pinning) taskset
Cold cache A cache that doesn't hold the process's data yet after migration
NUMA Non-uniform memory access: some memory is closer to some cores multi-socket servers
Real-time system Must meet deadlines airbag
Hard / soft real-time Missing a deadline is a failure / lowers quality airbag / video
Periodic task Released every period p, needs c each time sensor every 50 ms
Period (p) Time between releases; also the deadline 50
Utilisation U Σ c/p 0.9375
Rate monotonic (RM) Fixed priority: shorter period = higher P1 over P2
Liu-Layland bound n(2^(1/n) − 1): RM is safe below it 0.828 for 2
Earliest Deadline First (EDF) Dynamic priority: soonest deadline runs P2 (80) over P1 (100)
Deadline miss A task instance not finished by its deadline P2 at t = 80
CFS Completely Fair Scheduler, Linux 2.6.23 smallest vruntime
vruntime Virtual runtime: CPU received, scaled by the number of tasks —
Red-black tree Self-balancing sorted binary tree CFS run queue
nice value User-set weight, −20 (most favourable) to 19 nice -n 10
EEVDF Earliest Eligible Virtual Deadline First, Linux 6.6 onward lag + virtual deadline
Lag CPU time a task is owed compared with its fair share positive = owed

Summary

  • Round Robin gives each process one quantum in turn; great response time, no starvation; new arrivals join before the preempted process.
  • Too small a quantum wastes CPU on switches (efficiency Q/(Q + s)); too large becomes FCFS; aim for ~80% of bursts below Q.
  • HRRN runs the highest (W + S)/S: short jobs first, long jobs can't starve.
  • Multilevel queues separate kinds of work; MLFQ moves processes by behaviour (demote CPU hogs, promote waiters) and learns burst lengths.
  • On multicore: SMP, per-core queues, load balancing (push/pull) vs processor affinity (warm caches).
  • Real-time: RM (fixed, U ≤ n(2^(1/n) − 1)) vs EDF (dynamic, U ≤ 1). RM missed a deadline at U = 0.9375; EDF met them all.
  • Linux: CFS (vruntime, red-black tree, since 2.6.23) and, from 6.6, EEVDF (lag, virtual deadlines).

Next episode: Synchronization 1: race conditions, the critical-section problem and Peterson's solution.