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
- 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.
- What happens if the quantum is very large or very small? Large: it becomes FCFS. Small: context-switch overhead dominates.
- How do you pick a quantum? Larger than most CPU bursts (about 80%), much larger than the switch time.
- Does Round Robin cause starvation? No; every process gets a turn within (n − 1)(Q + s).
- What is HRRN? Non-preemptive; run the highest (W + S)/S; favours short jobs but ages long ones.
- Multilevel queue vs multilevel feedback queue? MLQ fixes a process to one queue; MLFQ moves processes by behaviour (demote CPU hogs, promote waiters).
- What is processor affinity? Soft vs hard? Keeping a process on the core with its warm cache; soft = preference, hard = pinned.
- Push vs pull migration? A periodic check pushes work off busy cores; an idle core pulls work.
- 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.
- 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.