CPU Scheduling &
Performance Evaluation

Five things want the CPU right now: T_ui, B_sync, P_audio, T_save, P_backup. Ask "which scheduling order is fastest?" and the honest answer is: fastest for whom? P_audio wants an answer in the next instant or its audio glitches. P_backup doesn't care when it finishes, only that it eventually does. "Best" isn't one thing here — which is exactly why this section exists before Section 2.2 compares five different answers to the same question.

What a scheduler knows about each job

Every scheduling decision is made from the same small set of facts about each waiting job:

• Arrival Time (AT) — when the job entered the ready queue.
• Burst Time (BT) — how long it needs the CPU. Real jobs alternate CPU bursts with I/O bursts (Chapter 1's T_save is the example: a short CPU burst to compute a diff, then an I/O burst while the disk write completes) — a scheduling algorithm only ever sees the CPU side of that alternation.
• Priority — a number expressing how urgent a job is, where relevant.

From those facts alone, every one of this chapter's algorithms decides who runs next. The difference between them is entirely in the rule for choosing — never in what they're allowed to know.

The metrics, formally

Worked example: reading the metrics off one schedule

Run the five jobs in arrival order — First-Come-First-Served, the simplest possible rule — and the metrics above stop being formulas and become a table.

Figure 1 · one schedule, every metric

Take P_audio as the worked line: it arrives at AT=2 needing only BT=1 unit of CPU, but T_ui and B_sync are already ahead of it in arrival order, so it doesn't run until t=10 and finishes at CT=11. TAT = 11−2 = 9. WT = 9−1 = 8: it waited eight times longer than the work it actually needed. Since nothing preempts anything under FCFS, response time and waiting time are identical for every job here — that stops being true the moment Section 2.2 introduces preemption, which is exactly why RT and WT are tracked separately from the start.

Practice 2.1

1. A job has AT=3, and under some schedule it finishes at CT=15 having needed BT=7 units of CPU. Compute its TAT and WT.
   Show solution

   TAT = CT − AT = 15 − 3 = 12. WT = TAT − BT = 12 − 7 = 5.

2. Variation. Under a preemptive algorithm, that same job is first given the CPU at t=6, then finishes at CT=15 as before. What is its Response Time, and is it the same number as its Waiting Time?
   Show solution

   RT = (first allocation) − AT = 6 − 3 = 3. This is not the same as WT (5) — RT only counts the wait until the job first starts running, while WT counts every unit spent waiting across the job's entire lifetime, including any time spent waiting again after being preempted. RT ≤ WT always, and under a non-preemptive algorithm they're equal, exactly as seen for every job in the FCFS worked example above.

3. Interpretation. A system reports 100% CPU utilization all day. Does that mean the scheduler is doing a good job?
   Show solution

   Not necessarily — 100% utilization only says the CPU is never idle, which a badly-chosen algorithm can achieve just as easily as a good one (FCFS hit 100% in the worked example above while still making P_audio wait 8× its own burst time). Utilization measures whether the CPU is busy, not whether it's busy doing the right thing first — that's what waiting time, turnaround time, and response time are for.

4. Synthesis. Explain why a scheduling algorithm can only ever use AT, BT, and priority to make its decision — connecting this back to Chapter 1's PCB/TCB fields.
   Show solution

   Those three facts are what actually gets recorded per schedulable entity: arrival is implicit in when its control block was created or re-queued, burst time is estimated or tracked via prior CPU usage in the TCB/task_struct's scheduling fields, and priority is a field the PCB or TCB stores directly (Chapter 1, Section 1.3). A scheduler can't act on information that isn't in some control block somewhere — which is exactly why "we don't know the burst time in advance" (Section 2.2) is a real, structural limitation and not just a textbook caveat.

Every algorithm below sees the exact same ready queue from the hero and Section 2.1: T_ui, B_sync, P_audio, T_save, P_backup, with the same arrival times and burst times. Only the rule for choosing changes. Watching one dataset produce five different schedules is the fastest way to see what each rule actually optimises for — and what it costs to get there.

First-Come, First-Served (FCFS)

Rule: whoever arrives first runs first, to completion. No cutting, ever — a single checkout line. Non-preemptive. Section 2.1 already walked this one in full: average waiting time 6.20, and P_audio — a job that only needed 1 unit of CPU — waited 8 units for it.

Shortest Job First (SJF) — non-preemptive

Rule: among the jobs currently waiting, run whichever has the smallest total burst time — but once started, let it run to completion regardless of what arrives afterward. Non-preemptive. On the spine data, SJF drops average waiting time from FCFS's 6.20 to 5.00: P_audio still has to wait for T_ui to finish (SJF can't interrupt it), but then jumps ahead of the much longer B_sync and T_save.

Shortest Remaining Time First (SRTF) — preemptive SJF

Rule: the same "shortest wins" idea, but re-decided at every arrival: if a newly-arrived job needs less time than whatever is currently running has left, the new job preempts it. Preemptive. This is where the dataset actually shows a preemption happen: T_ui starts at t=0 needing 4 units total. At t=2, with 2 units of T_ui left, P_audio arrives needing only 1 — strictly less — and takes the CPU. T_ui resumes at t=3 and finishes its last 2 units at t=5. Ties in SRTF are broken by earliest arrival, and if still tied, by name — the convention this chapter uses throughout, since real textbooks aren't consistent about it.

Average waiting time drops again, to 4.80 — the best of every algorithm in this chapter. This isn't a coincidence of this dataset: SRTF is provably optimal for minimising average waiting time among all scheduling algorithms, for a fixed set of arrival and burst times. The intuition: any time a longer job runs while a shorter one waits, that shorter job's wait could only have been reduced by running it first, and SRTF always makes exactly that choice, continuously.

Round Robin (RR)

Rule: every job gets a fixed slice of CPU time — a quantum (here, q=3) — and if it isn't finished when the quantum ends, it goes to the back of the ready queue. Preemptive, but by the clock rather than by burst length. Convention used throughout this chapter: if a job's quantum expires at the exact instant a new job arrives, the new arrival is placed in the ready queue before the just-preempted job re-joins it.

RR is the one algorithm here that makes average waiting time worse, not better — 8.80, the highest of all five, because every job now waits behind partial slices of every other job instead of running straight through. What RR buys instead is response time: 3.40, the best of all five, because no job ever waits more than one quantum-length's worth of other jobs before its first turn.

Priority Scheduling — non-preemptive

Rule: the highest-priority ready job runs next, to completion. This chapter uses lower number = higher priority throughout (matching Linux's nice value convention from Chapter 1). A preemptive variant also exists — a higher-priority arrival interrupts whatever is running — but isn't worked here.

With P_audio at priority 1 (an audio glitch is worse than a delayed sync) and P_backup at priority 5 (a backup job has nowhere urgent to be), average waiting time comes out to 5.20 — close to SJF's 5.00, because on this dataset priority order happens to roughly track burst-time order. That's a coincidence of these particular numbers, not a general property: priority and burst time measure completely different things.

Figure 2 · the same five jobs, five rules

No row wins on every column, and that's the point of this whole section: SRTF wins on turnaround and waiting time by provable construction, RR wins on response time by design, and both wins come at a cost the other pays. "Which algorithm is best" is only ever answerable once you've said best by which metric — the exact question Section 2.1 opened with.

Practice 2.2

1. Using the spine dataset, verify by hand that SJF's schedule gives T_save a waiting time of 2, then check your answer against Figure 2.
   Show solution

   Under SJF, order is T_ui(0-4), P_audio(4-5), T_save(5-10), B_sync(10-16), P_backup(16-25). T_save: CT=10, AT=3, BT=5. TAT = 10−3 = 7. WT = 7−5 = 2. Matches Figure 2's SJF table.

2. Variation. If P_backup's burst time were 3 instead of 9 (everything else unchanged), would SRTF's schedule change at all before t=4? Why or why not?
   Show solution

   No. P_backup doesn't arrive until t=4, and SRTF's decisions before t=4 only depend on jobs that have already arrived (T_ui, B_sync, P_audio, T_save) and their remaining times — none of which involve P_backup at all. A job's own burst time can never affect the schedule before that job has arrived; this is worth checking precisely because it's easy to assume changing one number ripples backward through a Gantt chart, and it never does.

3. Interpretation. A report claims "we switched from FCFS to Round Robin and average turnaround time got worse." Is that evidence RR was implemented incorrectly?
   Show solution

   No — this chapter's own numbers show exactly that pattern (FCFS avg TAT 11.20 vs. RR's 13.80). RR trades average turnaround and waiting time for better response time and fairness; a worse average TAT after switching to RR is the expected, documented trade-off, not a bug. The right follow-up question is whether response time improved to justify it — which, here, it did (6.20 → 3.40).

4. Synthesis. P_audio has the highest priority (1) and also the shortest burst time (1) in this dataset. Design a small variation to the dataset where Priority scheduling and SJF would clearly disagree about which job runs first.
   Show solution

   Give P_backup priority 1 instead of 5, keeping its burst time at 9 (the longest in the set). SJF would still run it last (longest remaining burst); Priority scheduling would now run it first among ready jobs, the moment it arrives — directly contradicting SJF's choice. This is the general point Section 2.2 makes about this dataset's near-agreement: priority and burst time are independent axes, and any dataset can be built to make them agree, disagree, or anything between.

Every algorithm in Section 2.2 was judged on averages — average waiting time, average response time. P_audio doesn't care about averages. It needs its next buffer refill by a specific instant, or the user hears a click. A real-time system isn't asking "how fast, on average" — it's asking "did every deadline get met, every single time, guaranteed."

The periodic task model

Real-time scheduling theory models recurring work as a set of periodic tasks: task i releases new work every Ti time units (its period) and needs Ci units of CPU time to finish that work (its execution time) — by convention, before the next release, which is its deadline. P_audio refilling its buffer every 4 time units is exactly this: a period of 4, needing 1 unit of CPU each time.

Two ways to assign priority

Worked example: one task set, two outcomes

Three tasks, so the RMS bound is 3(21/3−1) ≈ 0.7798. Our utilization, 0.9583, is well above it — RMS's simple test can't guarantee this task set is schedulable. EDF's bound is just U ≤ 1; at 0.9583, EDF is guaranteed.

Figure 4 · guaranteed isn't the same as inconclusive

Practice 2.3

1. A task has period 5 and execution time 2. A second has period 20 and execution time 4. Compute the total utilization and check it against the 2-task RMS bound.
   Show solution

   U = 2/5 + 4/20 = 0.4 + 0.2 = 0.6. The 2-task RMS bound is 2(21/2−1) ≈ 0.8284. Since 0.6 ≤ 0.8284, RMS guarantees this task set is schedulable — no simulation needed.

2. Variation. Using this chapter's worked task set, if T_save's execution time dropped from 3 to 2 (period unchanged at 8), does the total utilization now satisfy the RMS bound?
   Show solution

   New U = 0.25 + 0.3333 + 2/8 (0.25) = 0.8333. The bound is still 0.7798, so 0.8333 is still above it — RMS's simple test remains inconclusive, though closer to the line. (A full re-simulation would be needed to say for certain whether this smaller task set now meets every deadline.)

3. Interpretation. A task set has utilization 1.05. What can you conclude about its schedulability under EDF, and under RMS?
   Show solution

   Under EDF: definitely not schedulable — EDF's bound is necessary and sufficient, so U>1 guarantees deadlines will be missed no matter how work is ordered. Under RMS: also definitely not schedulable, since RMS can never do better than EDF (EDF is optimal); if the optimal algorithm can't meet every deadline, no fixed-priority scheme can either.

4. Synthesis. Explain why EDF's dynamic priority recalculation connects to Chapter 1's Section 1.4 in a way RMS's static priority never does.
   Show solution

   Every time EDF re-evaluates which job has the nearest deadline and switches to it, that's a genuine context switch, paying whatever real microsecond cost Chapter 1 measured. RMS's priorities are fixed at design time, so while it still context-switches between jobs, it never pays a cost for the act of deciding priority itself the way a naive EDF implementation recomputing deadlines on every tick might. This is part of why EDF's theoretical optimality doesn't automatically translate into being cheaper to run.

Every algorithm in Section 2.2 applies one rule to every job, uniformly. But P_audio and P_backup aren't really the same kind of thing — one is a quick interactive burst, the other is patient batch work. Real systems separate work like this into different classes and treat each class differently, rather than forcing one algorithm to serve every kind of job equally badly.

Multilevel Queue (MLQ): fixed classes, fixed rules

A Multilevel Queue splits the ready queue into several separate, permanent queues — say, a system queue, an interactive queue, and a batch queue — each with its own scheduling algorithm (the interactive queue might run Round Robin; the batch queue, FCFS). The queues themselves are served by fixed priority (drain the interactive queue completely before touching the batch queue) or by a fixed CPU-percentage split between them.

Multilevel Feedback Queue (MLFQ): classes that adapt

A Multilevel Feedback Queue keeps the multiple-queues idea but removes the rigidity: jobs move between queues based on how they actually behave, not on a fixed assignment. First described by Fernando Corbató in 1962 for CTSS (work later recognised with the Turing Award), MLFQ or its direct descendants have shown up in most major operating systems since — older Linux schedulers (before the current CFS design), classic Solaris, and the Windows NT kernel scheduler are all MLFQ-derived.

Rule 4's "however many times it gave up the CPU" clause exists for a specific, sneaky reason: without it, a job could deliberately give up the CPU one tick before its quantum expires, over and over, and never get demoted — gaming the scheduler into treating pure CPU-bound work as if it were interactive forever. Rule 4 closes that loophole by tracking the total time used at a level, not just whether any single visit used the full quantum.

Figure 3 · who's watching TV and who's doing the dishes

A small trace, isolating just T_save and P_backup against a 3-queue MLFQ — Q0 (quantum 2), Q1 (quantum 4), Q2 (FCFS, the bottom). T_save only ever needs a 1-unit CPU burst before it blocks for its autosave I/O (Chapter 1, Section 1.5) — well under Q0's quantum, so by Rule 4 it never gets demoted. P_backup is pure CPU-bound batch work with nowhere to be; it uses its full quantum every time, and sinks a level each visit.

Practice 2.4

1. A job in Q1 (quantum 4) uses only 3 units before voluntarily yielding for I/O. Under Rule 4, does it get demoted to Q2?
   Show solution

   No. Rule 4 only demotes a job once it has used its full allotment at a level. 3 units used out of a 4-unit quantum means it yielded early, so by the same logic as T_save in Figure 3, it stays at Q1.

2. Variation. Suppose P_backup is cunning and yields voluntarily after exactly 1.9 units every time it's given a 2-unit quantum at Q0, repeating this forever. Under the simple version of Rule 4 (only checking whether the current visit used the full quantum), what happens? What does the real Rule 4 (tracking cumulative usage) do instead?
   Show solution

   Under the simple, single-visit-only version, P_backup never technically uses its "full" quantum on any one visit, so it would never be demoted — effectively gaming its way into permanent top-priority treatment despite being purely CPU-bound. The real Rule 4 tracks cumulative time used at a level across all visits; once those 1.9-unit visits add up to a full quantum's worth (just over one visit and change), it gets demoted anyway. This is exactly the loophole Rule 4 was written to close.

3. Interpretation. Without Rule 5 (the periodic priority boost), could a job in Q2 wait forever?
   Show solution

   Yes — if new jobs keep entering at Q0 (Rule 3) faster than Q0 and Q1 ever empty out, a Q2 job can starve indefinitely, for exactly the same structural reason Priority scheduling can starve a low-priority job in Section 2.2. Rule 5 is MLFQ's version of ageing: instead of gradually raising priority, it periodically resets everyone to the top, guaranteeing every job gets a turn at least once per period S.

4. Synthesis. Explain why T_ui would behave like T_save in an MLFQ, not like P_backup — using Chapter 1's description of what T_ui actually does.
   Show solution

   T_ui spends most of its life waiting for keystrokes and only briefly computes to update the display, then blocks again waiting for input (Chapter 1, hero). Each of those CPU bursts is short and ends in a voluntary yield, exactly the pattern that keeps T_save pinned at Q0 in Figure 3. MLFQ rewards this pattern automatically, without ever being told "this is an interactive thread" — it only ever sees the behaviour.