4. CPU Scheduling

Whenever more threads are runnable than there are cores, something must decide who runs next — and that decision, made thousands of times a second, determines whether a machine feels responsive, completes batch work quickly, or meets a hard deadline. This chapter builds the vocabulary for judging schedulers, works through the classical algorithms and their trade-offs, extends them to multiprocessors and real-time systems, and ends with how the decisions are evaluated and what production kernels actually do. Scheduling is where the abstractions of Chapters 2 and 3 meet the finite reality of the hardware.

<a id="41-scheduling-foundations"></a>

4.1 Scheduling Foundations

Before comparing algorithms, we need to know what workloads look like, when scheduling decisions may be taken, what performs the switch, and which metrics distinguish a good decision from a bad one.

CPU-I/O Burst Cycle

Theory

Scheduling would be uninteresting if programs simply computed from start to finish. They do not. Process execution consists of an alternating cycle: a stretch of computation (a CPU burst), then a request for I/O that blocks the process (an I/O burst), then more computation, and so on until a final CPU burst ends with termination.

This structure is what makes scheduling both necessary and possible. Necessary, because when a process blocks, the CPU must be given to someone else or it idles. Possible, because bursts are short and frequent enough that the scheduler gets regular opportunities to intervene.

The empirically observed distribution of CPU burst lengths is the single most important fact in this chapter: it is exponential or hyperexponential — a very large number of very short bursts, and a small number of long ones. Most bursts are under 8 milliseconds. This shape justifies several algorithm choices later: it is why favouring short jobs works so well, why round-robin quanta are set in the low tens of milliseconds, and why a process's recent behaviour predicts its next burst.

Processes are classified by which burst dominates:

	I/O-bound	CPU-bound
Bursts	Many short CPU bursts	Few long CPU bursts
Time spent	Mostly blocked waiting	Mostly computing
Examples	Shells, editors, web servers, databases	Compilers, video encoding, simulation
Wants	Low latency — to be run promptly when ready	Throughput — long uninterrupted stretches
Effect if delayed	Device sits idle; user perceives lag	Finishes later, nobody notices immediately

A good scheduler needs a balanced mix in the ready queue. If every process is CPU-bound, devices idle; if every process is I/O-bound, the CPU idles. And the classes want opposite things, which is the central tension every algorithm in 4.2 tries to resolve.

Analogy: a CPU burst is a stretch of focused desk work; an I/O burst is waiting for a colleague to reply to an email. Most desk stretches are short, and a manager assigning work must know that some people mostly wait while others mostly type.

Example

   Execution as alternating bursts

   process: [CPU 6ms][--- I/O 40ms ---][CPU 2ms][-- I/O 25ms --][CPU 4ms] exit
             ^                          ^                        ^
             scheduler gets control at every one of these boundaries

   Burst length distribution (measured, and remarkably stable across systems)

   frequency
     |*
     |**
     |***
     |*****
     |*******
     |**********
     |***************
     |**********************
     +--------------------------------------> burst length (ms)
      0   2   4   6   8  10  12  14  16 ...

   Most bursts are SHORT. This one fact drives most scheduler design.

   Two process shapes

   I/O-bound:  [CPU][-----I/O-----][CPU][-----I/O-----][CPU][---I/O---]
   CPU-bound:  [========== CPU ==========][I/O][========== CPU =======]

# Why a mixed workload keeps both the CPU and the devices busy.
def simulate(processes, total_ms=1000):
    """processes: list of (cpu_burst_ms, io_burst_ms)"""
    cpu_busy = io_busy = 0
    for cpu, io in processes:
        cycle = cpu + io                      # one full CPU+I/O cycle
        cycles = total_ms / cycle
        cpu_busy += cycles * cpu              # demand this process places on the CPU
        io_busy  += cycles * io               # demand it places on devices
    return cpu_busy / total_ms, io_busy / total_ms

# All I/O-bound: devices saturated, CPU nearly idle.
print(simulate([(2, 40)] * 8))     # cpu ~0.38, io ~7.6 (devices oversubscribed)

# All CPU-bound: CPU saturated, devices idle.
print(simulate([(100, 5)] * 4))    # cpu ~3.8, io ~0.19

# Mixed: both resources meaningfully used.
print(simulate([(2, 40)] * 4 + [(100, 5)] * 2))

Key takeaways

• Execution alternates between CPU bursts and I/O bursts; every transition is a scheduling opportunity.
• CPU burst lengths follow an exponential distribution: very many short bursts, few long ones.
• I/O-bound processes want low latency; CPU-bound processes want long uninterrupted runs.
• A healthy system needs a mix of both so that neither the CPU nor the devices sit idle.

🧪 Practice

1. Classify these as CPU- or I/O-bound and justify each: grep over a large directory, video transcoding, an SSH session, a nightly report generator.
2. Instrument a program to print timestamps around each read() and each compute section. Plot the burst distribution and compare with the shape above.
3. Interview-style: "Why does knowing bursts are mostly short make favouring short jobs a good policy?" Hint: think about how much a long job delays a short one versus the reverse.

Preemptive vs Non-Preemptive Scheduling

Theory

A scheduling decision is required whenever the CPU becomes available. There are exactly four circumstances in which that happens:

1. A running process blocks (requests I/O, waits on a child).
2. A running process terminates.
3. A running process is interrupted and becomes ready again (typically a timer expiry).
4. A blocked process becomes ready (an I/O completed), possibly outranking the running one.

Cases 1 and 2 are unavoidable — the running process has given up the CPU by itself. A scheduler that acts only on those is non-preemptive (or cooperative): once a process has the CPU, it keeps it until it blocks or exits.

A scheduler that also acts on cases 3 and 4 is preemptive: it can take the CPU away from a process that is willing and able to continue.

The differences are consequential:

	Non-preemptive	Preemptive
CPU taken away	Never; only voluntary release	Yes, at timer ticks or on higher-priority wakeup
Response time	Unbounded — one long job blocks everyone	Bounded by the quantum
Implementation	Simple; no timer needed	Needs a timer interrupt and careful locking
Kernel data races	Few — a process runs to a safe point	Many — must protect shared structures
A buggy infinite loop	Hangs the system	Is merely a CPU hog
Used by	Early Windows/Mac, some embedded and RTOS designs, coroutines	Every general-purpose OS today

Preemption is what makes time-sharing possible (Chapter 1), and it is not free: the kernel itself becomes concurrent. If a process is preempted while executing a system call that is halfway through modifying a kernel data structure, the structure must not be observed in that state. Early UNIX solved this by simply not preempting kernel code — a system call ran to completion or to a voluntary sleep. Modern kernels are preemptible (Linux's CONFIG_PREEMPT), using explicit locking to protect critical sections, which lowers latency at the cost of considerable complexity.

Analogy: non-preemptive scheduling is a meeting where each speaker talks until finished; preemptive scheduling is a meeting with a chairperson and a timer. The second is fairer and more responsive, and requires someone with authority to interrupt.

Example

   The four decision points

   1. RUNNING -> BLOCKED     (I/O request)        non-preemptive too
   2. RUNNING -> TERMINATED  (exit)               non-preemptive too
   3. RUNNING -> READY       (timer preemption)   PREEMPTIVE ONLY
   4. BLOCKED -> READY       (I/O completion)     PREEMPTIVE ONLY (may preempt)

   Same workload, both disciplines
   P1 arrives t=0, burst 20ms   P2 arrives t=2, burst 3ms (interactive)

   NON-PREEMPTIVE
   |============== P1 (20ms) ==============|== P2 ==|
   0                                       20       23
   P2 response time: 18ms   -- it waited for a job it should have jumped

   PREEMPTIVE (quantum 5ms)
   |= P1 =|= P2 =|===== P1 ==================|
   0      5      8                           23
   P2 response time: 3ms    -- bounded by the quantum, not by P1's length

# The distinction expressed as one branch in the scheduler.
class Scheduler:
    def __init__(self, preemptive):
        self.preemptive = preemptive
        self.running = None
        self.ready = []

    def on_wakeup(self, proc):
        """A blocked process became ready (decision point 4)."""
        self.ready.append(proc)
        if self.preemptive and self.running and proc.priority > self.running.priority:
            self.preempt()        # take the CPU away from a willing runner
        # non-preemptive: the woken process simply waits its turn

    def on_timer_tick(self):
        """Decision point 3 -- exists only under preemption."""
        if not self.preemptive:
            return                # a non-preemptive scheduler ignores the timer
        self.running.ticks += 1
        if self.running.ticks >= QUANTUM:
            self.preempt()

    def on_block_or_exit(self):
        """Decision points 1 and 2 -- both disciplines must handle these."""
        self.dispatch(self.pick_next())

Key takeaways

• Scheduling decisions arise at four points; non-preemptive schedulers act only on blocking and termination.
• Preemption bounds response time and is required for time-sharing and for enforcing priorities.
• Preemption makes the kernel concurrent, requiring locks around shared kernel data structures.
• Under non-preemptive scheduling one long or looping process can monopolise or hang the system.

🧪 Practice

1. Give two systems where non-preemptive scheduling is a defensible choice, with reasons.
2. Work out both Gantt charts for: P1 (t=0, 10ms), P2 (t=1, 2ms), P3 (t=2, 2ms), preemptive vs non-preemptive with a 4ms quantum. Compare average response times.
3. Interview-style: "Why does preemption force the kernel to use locks it did not previously need?" Hint: consider a system call interrupted halfway through updating the ready queue.

Dispatcher and Dispatch Latency

Theory

It is worth separating two components that are often conflated. The scheduler decides which process runs next — it is policy. The dispatcher actually makes it run — it is mechanism. The separation matters because they are tuned independently: the scheduler is chosen for fairness or throughput, while the dispatcher is optimised purely for speed.

The dispatcher performs three steps:

1. Context switch — save the outgoing process's registers into its PCB and load the incoming one's (Chapter 2).
2. Switch to user mode — the incoming process must not resume with kernel privilege.
3. Jump to the resume point — restore the saved program counter so execution continues exactly where it stopped.

Dispatch latency is the time from the decision to stop one process until the next one is actually executing. Since it happens on every switch — thousands of times a second — it must be measured in microseconds, and it is pure overhead: no user work occurs during it.

For real-time systems a more demanding quantity matters: the total delay from an event (an interrupt signalling that a high-priority task should run) until that task executes. It has two parts:

• Conflict phase — preempting whatever is running, and releasing any resources the high-priority task needs. If the kernel is executing a non-preemptible section, this waits.
• Dispatch phase — the actual switch.

The conflict phase is the problematic one, because a long non-preemptible kernel path can delay an urgent task for milliseconds. This is the entire reason real-time kernels invest in preemption points or fully preemptible designs, and why PREEMPT_RT exists for Linux: not to make throughput better, but to bound the worst-case conflict phase.

Analogy: the scheduler is the manager deciding who works next; the dispatcher is the act of physically clearing the desk and seating the next person. Dispatch latency is how long the desk stands empty — and if the previous occupant is in the middle of something they cannot abandon, the wait is longer still.

Example

   Scheduler vs dispatcher

   [ SCHEDULER ]  policy: which one?          -> returns a PCB pointer
        |
        v
   [ DISPATCHER ] mechanism: make it run      -> context switch, user mode, jump

   Dispatch latency, decomposed

   event (interrupt: high-priority task is ready)
     |
     |<---------------- response time ----------------->|
     |                                                   |
     |<--- conflict phase --->|<-- dispatch -->|
     |                        |                |
     | preempt the running    | context switch | high-priority task
     | process; release       | + mode switch  | starts executing
     | resources it holds     |                |
     |                        |                |
     | THE PROBLEM: if the kernel is in a non-preemptible
     | section, this phase can stretch to milliseconds

   Typical magnitudes
     dispatch (switch)      : 1-5 us
     conflict, normal kernel: 0-100+ us  (unbounded in the worst case)
     conflict, PREEMPT_RT   : bounded, tens of us

/* Policy and mechanism, deliberately separated. */

/* SCHEDULER: pure policy. Swappable without touching the dispatcher. */
struct pcb *schedule(void) {
    return pick_highest_priority(&ready_queue);   /* or CFS, or round robin */
}

/* DISPATCHER: pure mechanism. Identical whatever the policy is. */
void dispatch(struct pcb *next) {
    struct pcb *prev = current;

    save_context(&prev->ctx);            /* 1. freeze the outgoing process   */
    if (prev->page_table != next->page_table)
        load_page_table(next->page_table);

    current = next;
    next->state = RUNNING;

    restore_context(&next->ctx);         /* 2. load the incoming registers   */
    return_to_user_mode(next->ctx.rip);  /* 3. drop privilege and jump       */
}

# Measure the real thing on Linux.
cyclictest -t1 -p 99 -i 1000 -l 10000   # worst-case wake-up latency (rt-tests)
perf sched latency --sort max            # per-task scheduling delay
grep PREEMPT /boot/config-$(uname -r)    # which preemption model is compiled in

Key takeaways

• The scheduler chooses (policy); the dispatcher performs the switch (mechanism).
• Dispatch latency is pure overhead incurred on every switch and must stay in the microsecond range.
• Real-time response time splits into a conflict phase and a dispatch phase.
• The conflict phase dominates the worst case, which is why real-time kernels make kernel code preemptible.

🧪 Practice

1. Explain why separating scheduler from dispatcher makes it possible to change scheduling policy without touching the context-switch code.
2. Run cyclictest on an idle machine and again under heavy disk load. Explain the difference in maximum latency.
3. Interview-style: "A real-time task must react within 100 microseconds. Which phase would you attack first, and how?" Hint: measure both phases separately before optimising either.

Scheduling Criteria

Theory

"Better scheduler" is meaningless without saying better at what. There are five standard metrics, and the essential insight is that they conflict — improving one usually degrades another, so a scheduler is a choice of which to favour.

Metric	Definition	Direction	Who cares
CPU utilisation	Fraction of time the CPU does useful work	Maximise	System owners
Throughput	Processes completed per unit time	Maximise	Batch and server operators
Turnaround time	Submission to completion (total elapsed)	Minimise	Batch users
Waiting time	Total time spent in the ready queue	Minimise	The scheduler's true lever
Response time	Submission to first output/execution	Minimise	Interactive users

Two distinctions repay attention:

• Waiting time is the metric a scheduler actually controls. Turnaround time includes the process's own CPU and I/O time, which no scheduling policy can shorten. Scheduling only changes how long a process sits in the ready queue.
• Response time is not turnaround time. An editor that shows your keystroke in 10 ms and finishes saving in 3 seconds has excellent response time and mediocre turnaround. For interactive work, response time is the metric users perceive.

Beyond averages, two further criteria matter in practice and are routinely underweighted in textbooks:

• Variance/predictability. A system with 100 ms average response time and 2-second outliers feels worse than one with a steady 150 ms. Users notice the tail, not the mean, which is why production systems track p95 and p99 rather than averages.
• Fairness and starvation-freedom. A policy that optimises average waiting time may indefinitely postpone some process. Any usable scheduler must guarantee eventual progress.

The conflicts are direct. Maximising throughput favours short jobs, which starves long ones. Minimising response time means short quanta, which raises switching overhead and lowers throughput. Guaranteeing fairness prevents the reordering that would lower average waiting time. There is no optimum, only a chosen trade-off.

Example

   The five metrics on one timeline

   P submitted     P first runs         P completes
        |               |                     |
        |<-- response ->|                     |
        |                                     |
        |<----------- turnaround ------------>|
        |                                     |
        waiting = turnaround - (CPU time + I/O time)
                = total time spent sitting in the ready queue

   Worked example: P arrives t=0, needs 5ms CPU, first runs at t=3, ends at t=12
     response   = 3 - 0  = 3ms
     turnaround = 12 - 0 = 12ms
     waiting    = 12 - 5 = 7ms   (if it did no I/O)

   Why averages mislead

   Scheduler A: 100, 100, 100, 100, 100         avg 100, p99 100
   Scheduler B:  10,  10,  10,  10, 460         avg 100, p99 460
   Identical averages. B is the one users complain about.

def metrics(procs):
    """procs: list of dicts with arrival, burst, start, finish."""
    rows = []
    for p in procs:
        turnaround = p["finish"] - p["arrival"]
        waiting    = turnaround - p["burst"]     # what scheduling controls
        response   = p["start"]  - p["arrival"]  # what users perceive
        rows.append((p["name"], turnaround, waiting, response))

    n = len(rows)
    print(f"{'proc':6}{'turn':>7}{'wait':>7}{'resp':>7}")
    for name, t, w, r in rows:
        print(f"{name:6}{t:7}{w:7}{r:7}")
    print(f"{'avg':6}{sum(r[1] for r in rows)/n:7.1f}"
          f"{sum(r[2] for r in rows)/n:7.1f}{sum(r[3] for r in rows)/n:7.1f}")

    # Always look at the tail, not only the mean.
    waits = sorted(r[2] for r in rows)
    print("p95 waiting:", waits[int(0.95 * (n - 1))])

metrics([
    {"name": "P1", "arrival": 0, "burst": 24, "start": 0,  "finish": 24},
    {"name": "P2", "arrival": 0, "burst": 3,  "start": 24, "finish": 27},
    {"name": "P3", "arrival": 0, "burst": 3,  "start": 27, "finish": 30},
])

Key takeaways

• The five standard criteria are utilisation, throughput, turnaround, waiting, and response time.
• Waiting time is what a scheduler actually controls; turnaround includes work no policy can shorten.
• Response time — time to first execution — is what interactive users perceive.
• The criteria conflict, and variance plus starvation-freedom matter as much as averages in real systems.

🧪 Practice

1. For P1 (arrives 0, burst 8, starts 0, ends 8) and P2 (arrives 1, burst 4, starts 8, ends 12), compute all three per-process metrics by hand.
2. Construct two schedules of the same three jobs where one wins on average waiting time and the other on maximum waiting time. State which you would ship.
3. Interview-style: "Which metric would you optimise for a video game, a payroll batch run, and a web API?" Hint: ask who is waiting and whether they are watching.

<a id="42-scheduling-algorithms"></a>

4.2 Scheduling Algorithms

Each algorithm below is an answer to "who runs next", and each is best understood by the specific failure of its predecessor that it was designed to fix.

First-Come First-Served

Theory

FCFS is the simplest possible policy: processes run in arrival order, and each runs to completion (or until it blocks). It is a plain FIFO queue — a new process joins the tail, the dispatcher takes from the head.

Its virtues are simplicity, obvious fairness in the queueing sense, and freedom from starvation: every process eventually reaches the head. It is trivially implementable and has essentially zero scheduling overhead.

Its defect is severe and has a name: the convoy effect. When one long CPU-bound process holds the CPU, every short process queues behind it. Worse, the I/O-bound processes that were waiting behind it now rush to the devices simultaneously, then all finish and queue up behind the long job again — so both the CPU and the devices are alternately idle while a convoy of short jobs trails one slow one. Average waiting time becomes both high and extremely sensitive to arrival order.

The order-sensitivity is the memorable part: the same three processes can have an average waiting time of 17 or of 3, depending purely on which arrives first. No other classical algorithm is this fragile.

FCFS is non-preemptive by nature, which makes it unusable as a general-purpose policy — a single infinite loop hangs the system. It survives as a component inside other schedulers (as the tie-break within one priority level) and in batch systems where turnaround matters more than response.

Analogy: a single supermarket checkout with no express lane. Someone with a full trolley arrives first and everyone behind them waits, however small their basket.

Example

   Same processes, arrival order P1, P2, P3
   P1 burst 24, P2 burst 3, P3 burst 3 (all arrive at t=0)

   |============ P1 (24) ============|= P2 =|= P3 =|
   0                                 24     27     30

   waiting:  P1 = 0    P2 = 24    P3 = 27      average = 17.0

   Reverse the arrival order: P2, P3, P1

   |= P2 =|= P3 =|============ P1 (24) ============|
   0      3      6                                 30

   waiting:  P2 = 0    P3 = 3    P1 = 6            average = 3.0

   Identical work. Average waiting time differs by 5.7x.

   The convoy effect

   CPU:    [========== long job ==========][s][s][s][s]
   disk:   idle .......................... then a burst of contention
           devices starve, then are slammed, then starve again

def fcfs(processes):
    """processes: list of (name, arrival, burst), scheduled in arrival order."""
    procs = sorted(processes, key=lambda p: p[1])   # ties broken by input order
    clock, results = 0, []

    for name, arrival, burst in procs:
        start = max(clock, arrival)      # the CPU may be idle waiting for arrival
        finish = start + burst           # run to completion: no preemption
        results.append({
            "name": name,
            "waiting": start - arrival,          # time sitting in the queue
            "turnaround": finish - arrival,
        })
        clock = finish

    avg = sum(r["waiting"] for r in results) / len(results)
    return results, avg

print(fcfs([("P1", 0, 24), ("P2", 0, 3), ("P3", 0, 3)])[1])   # 17.0
print(fcfs([("P2", 0, 3), ("P3", 0, 3), ("P1", 0, 24)])[1])   # 3.0

Key takeaways

• FCFS runs processes in arrival order to completion — a plain FIFO queue with no overhead.
• It is starvation-free and trivially simple, but non-preemptive and therefore unusable alone.
• The convoy effect makes one long job delay every short job behind it and idles the devices.
• Average waiting time depends heavily on arrival order, which no other classical algorithm suffers as badly.

🧪 Practice

1. Compute the average waiting and turnaround times for P1 (0, 10), P2 (2, 5), P3 (4, 2) under FCFS.
2. Construct an arrival order for those three that minimises average waiting time, and one that maximises it.
3. Interview-style: "Where is FCFS still the right choice inside a modern scheduler?" Hint: think about what happens between two threads of identical priority.

Shortest Job First

Theory

FCFS's problem is that a long job can precede short ones. Shortest Job First fixes it directly: when the CPU is free, run the process with the smallest next CPU burst.

SJF is provably optimal for average waiting time. The proof is an exchange argument: given any schedule where a longer job precedes a shorter one, swapping them reduces total waiting time, because the swap delays the long job by the short job's (small) burst while advancing the short job by the long job's (large) burst. Repeating until no such pair exists yields SJF. No algorithm can do better on this metric.

Two problems keep it from being directly usable:

• Burst lengths are not known in advance. Except in batch systems where users supply an estimate, the scheduler cannot know how long the next burst will be. It must be predicted, and the standard method is an exponential moving average over previous bursts: tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n), where t(n) is the most recent actual burst. With alpha = 0.5, recent history and accumulated history are weighted equally; alpha = 0 ignores recent behaviour entirely and alpha = 1 uses only the last burst. This works because bursts are strongly autocorrelated — a process that has been interactive tends to stay interactive.
• Starvation. A steady stream of short jobs can postpone a long job indefinitely. The standard remedy is aging: gradually improving the effective priority of a job as it waits.

SJF is non-preemptive in its basic form: a newly arrived short job waits for the running one to finish. The preemptive variant is the subject of the next topic.

Analogy: a supermarket express lane taken to its logical extreme — always serve whoever has the fewest items. Total waiting across all customers is minimised, and the person with the full trolley may never be served.

Example

   P1 burst 6, P2 burst 8, P3 burst 7, P4 burst 3 (all arrive t=0)

   SJF order: P4(3), P1(6), P3(7), P2(8)

   |= P4 =|=== P1 ===|==== P3 ====|===== P2 =====|
   0      3          9            16             24

   waiting:  P4 = 0   P1 = 3   P3 = 9   P2 = 16    average = 7.0
   (FCFS on the same set in the order P1..P4 gives 10.25 -- SJF is optimal)

   Burst prediction by exponential averaging (alpha = 0.5)

   actual  t(n):   6    4    6    4    13   13   13
   predict tau:   10    8    6    6     5    9   11   12
                   ^                          ^
                   initial guess              adapts upward as behaviour changes

def predict_next_burst(history, alpha=0.5, initial=10.0):
    """Exponential moving average: tau(n+1) = alpha*t(n) + (1-alpha)*tau(n)."""
    tau = initial
    predictions = [tau]
    for actual in history:
        tau = alpha * actual + (1 - alpha) * tau   # blend the newest observation
        predictions.append(tau)                    # with everything before it
    return predictions

print([round(p, 2) for p in predict_next_burst([6, 4, 6, 4, 13, 13, 13])])
# alpha=0   -> never adapts (always the initial guess)
# alpha=1   -> only the last burst matters (jumpy, over-reacts to one outlier)
# alpha=0.5 -> the usual compromise


def sjf(processes):
    """Non-preemptive SJF: pick the shortest burst among those that have arrived."""
    remaining, clock, results = list(processes), 0, []
    while remaining:
        available = [p for p in remaining if p[1] <= clock]
        if not available:                       # CPU idle until the next arrival
            clock = min(p[1] for p in remaining)
            continue
        chosen = min(available, key=lambda p: p[2])   # smallest burst wins
        name, arrival, burst = chosen
        results.append({"name": name, "waiting": clock - arrival})
        clock += burst                          # runs to completion
        remaining.remove(chosen)
    return results, sum(r["waiting"] for r in results) / len(results)

Key takeaways

• SJF selects the process with the shortest next CPU burst and is provably optimal for average waiting time.
• The next burst is unknown and must be predicted, usually by an exponential moving average over past bursts.
• Prediction works because burst lengths are autocorrelated — recent behaviour predicts near-future behaviour.
• SJF starves long jobs under a stream of short ones, which aging is introduced to fix.

🧪 Practice

1. Compute average waiting time for bursts 7, 4, 1, 4 (all arriving at t=0) under FCFS and under SJF.
2. With alpha = 0.5 and tau(0) = 10, compute the next four predictions for actual bursts 8, 7, 4, 16. Then repeat with alpha = 0.2 and comment.
3. Interview-style: "SJF is optimal — why does no general-purpose OS use it?" Hint: name two things the scheduler would need to know or guarantee that it cannot.

Shortest Remaining Time First

Theory

SRTF is preemptive SJF. The decision point is extended: whenever a new process arrives, compare its burst with the remaining time of the running process, and preempt if the newcomer is shorter.

This closes SJF's remaining gap. Under non-preemptive SJF, a 1 ms job arriving one instant after a 20 ms job starts must wait 20 ms. Under SRTF it preempts immediately and finishes in 1 ms. The result is optimal average waiting time even for dynamic arrivals — SRTF is optimal among all algorithms, preemptive or not, when burst lengths are known.

The costs are the ones preemption always brings, plus one specific to this policy:

• More context switches, each with its direct and cache-pollution cost. A stream of short arrivals can preempt a long job repeatedly.
• Worse starvation than SJF. A long job can be preempted again and again by newcomers and may never accumulate enough CPU to finish. Its remaining time shrinks only while it runs, so it never becomes competitive on its own.
• Prediction is still required, with the same uncertainty, now applied more aggressively.

SRTF is the theoretical benchmark against which practical schedulers are measured rather than a deployed policy. Its spirit survives in multilevel feedback queues (below), which approximate "favour jobs that appear short" without needing to know burst lengths, by demoting processes that consume full quanta.

Example

   P1 arrives 0 burst 8   P2 arrives 1 burst 4
   P3 arrives 2 burst 9   P4 arrives 3 burst 5

   t=0  only P1        -> run P1
   t=1  P2 (4) vs P1 remaining (7)  -> PREEMPT, run P2
   t=2  P3 (9) vs P2 remaining (3)  -> keep P2
   t=3  P4 (5) vs P2 remaining (2)  -> keep P2
   t=5  P2 done. remaining: P1=7, P3=9, P4=5 -> run P4
   t=10 P4 done. remaining: P1=7, P3=9       -> run P1
   t=17 P1 done                              -> run P3

   |P1|== P2 ==|=== P4 ===|====== P1 ======|======== P3 ========|
   0  1        5          10               17                   26

   waiting = turnaround - burst
     P1: (17-0) - 8 = 9      P2: (5-1)  - 4 = 0
     P3: (26-2) - 9 = 15     P4: (10-3) - 5 = 2
   average = 26/4 = 6.5

   Non-preemptive SJF on the same set gives 7.75 -- preemption pays.
   Note P3, the longest job, waits the most: starvation risk is visible here.

def srtf(processes):
    """Preemptive SJF, simulated one time unit at a time."""
    remaining = {p[0]: p[2] for p in processes}          # name -> time left
    arrival   = {p[0]: p[1] for p in processes}
    burst     = {p[0]: p[2] for p in processes}
    finish, clock, timeline = {}, 0, []

    while remaining:
        ready = [n for n in remaining if arrival[n] <= clock]
        if not ready:
            clock += 1                                   # CPU idle
            continue
        current = min(ready, key=lambda n: remaining[n])  # shortest REMAINING
        timeline.append(current)
        remaining[current] -= 1                           # run one unit, then
        clock += 1                                        # re-decide: this is
                                                          # where preemption
        if remaining[current] == 0:                       # happens implicitly
            finish[current] = clock
            del remaining[current]

    waits = {n: finish[n] - arrival[n] - burst[n] for n in finish}
    return waits, sum(waits.values()) / len(waits)

print(srtf([("P1",0,8), ("P2",1,4), ("P3",2,9), ("P4",3,5)])[1])   # 6.5

Key takeaways

• SRTF is preemptive SJF: a newly arrived shorter job takes the CPU from the running one.
• It is optimal for average waiting time among all algorithms when burst lengths are known.
• It costs many more context switches and worsens starvation for long jobs.
• It serves as a theoretical benchmark; multilevel feedback queues approximate its behaviour without prediction.

🧪 Practice

1. Build the Gantt chart and average waiting time for P1 (0, 7), P2 (2, 4), P3 (4, 1), P4 (5, 4) under SRTF.
2. Compare SJF and SRTF on the same set and count the context switches each requires.
3. Interview-style: "Under SRTF, can a job be starved forever? Construct the arrival pattern." Hint: consider a long job and a short job arriving slightly faster than they complete.

Priority Scheduling

Theory

Priority scheduling generalises the previous algorithms: each process carries a priority number, and the CPU goes to the highest-priority ready process. SJF is precisely priority scheduling where the priority is the inverse of the predicted burst length, and FCFS is priority scheduling where the priority is the inverse of arrival time.

Priorities come from two sources. Internal priorities are computed by the system from measurable quantities — memory use, I/O-to-CPU ratio, time limits. External priorities come from outside: who paid, which department, how important the work is deemed to be. Real systems use both.

The scheme may be preemptive (a higher-priority arrival takes the CPU immediately) or non-preemptive (it merely goes to the head of the queue).

The defining problem is indefinite blocking, or starvation: a low-priority process may never run while higher-priority work keeps arriving. The often-repeated anecdote is MIT's IBM 7094, shut down in 1973 with a low-priority job still queued from 1967 — apocryphal or not, it captures the failure exactly.

The standard remedy is aging: increase a process's priority the longer it waits. A job at priority 127 that gains one priority level every 15 minutes will reach priority 0 within about 32 hours, guaranteeing eventual execution. Aging converts a policy that can starve into one that merely delays.

A second problem, priority inversion, appears once priorities meet locks: a high-priority task waits on a lock held by a low-priority task, which is itself preempted by medium-priority tasks — so effectively the medium tasks outrank the high one. This nearly lost the Mars Pathfinder mission in 1997, and its solutions (priority inheritance and priority ceiling) are covered in Chapter 5.

Example

   P1 burst 10 pri 3   P2 burst 1 pri 1   P3 burst 2 pri 4
   P4 burst 1 pri 5    P5 burst 5 pri 2      (lower number = higher priority)

   order: P2(1), P5(2), P1(3), P3(4), P4(5)

   |P2|== P5 ==|====== P1 ======|= P3 =|P4|
   0  1        6                16     18 19

   waiting: P2=0  P5=1  P1=6  P3=16  P4=18      average = 8.2

   Starvation and its fix

   without aging:                    with aging (+1 level per 5 time units):
   pri 10 job waits ...              t=0   pri 10
   high-priority work keeps          t=5   pri 9
   arriving ...                      t=10  pri 8
   job never runs                    ...
                                     t=50  pri 0  -> guaranteed to run

   Priority inversion (previewing Chapter 5)

   LOW  task takes lock L
   HIGH task blocks waiting for L
   MED  task preempts LOW (it outranks LOW and needs no lock)
        -> HIGH is now effectively waiting behind MED. Inverted.

import heapq

def priority_schedule(processes, aging_interval=None):
    """processes: list of (name, arrival, burst, priority). Lower value = higher."""
    clock, done, pending = 0, [], list(processes)
    ready = []                                   # min-heap on effective priority

    while pending or ready:
        for p in [p for p in pending if p[1] <= clock]:
            heapq.heappush(ready, (p[3], p[1], p))   # (priority, arrival, proc)
            pending.remove(p)
        if not ready:
            clock = min(p[1] for p in pending)
            continue

        if aging_interval:                       # AGING: rebuild the heap with
            aged = []                            # improved priorities for those
            for pri, arr, p in ready:            # that have waited a long time
                waited = clock - arr
                effective = max(0, p[3] - waited // aging_interval)
                aged.append((effective, arr, p))
            heapq.heapify(aged)
            ready = aged

        _, _, chosen = heapq.heappop(ready)
        done.append({"name": chosen[0], "waiting": clock - chosen[1]})
        clock += chosen[2]                       # non-preemptive: run to the end
    return done, sum(d["waiting"] for d in done) / len(done)

Key takeaways

• Priority scheduling runs the highest-priority ready process; FCFS and SJF are special cases of it.
• Priorities may be internal (computed from behaviour) or external (assigned by policy or payment).
• Its characteristic failure is starvation of low-priority work, fixed by aging priorities upward over time.
• Priority inversion — a high-priority task blocked behind a lock held by a low-priority one — is a separate hazard requiring inheritance protocols.

🧪 Practice

1. Compute the average waiting time for P1 (burst 4, pri 3), P2 (burst 2, pri 1), P3 (burst 6, pri 2), all arriving at t=0.
2. Implement aging in the example and demonstrate that a priority-20 job eventually runs despite a stream of priority-1 arrivals.
3. Interview-style: "Describe priority inversion and how you would prevent it." Hint: the fix temporarily changes the priority of the lock holder, not the waiter.

Round Robin

Theory

Round robin is FCFS with preemption: processes are kept in a FIFO queue, and each runs for at most one time quantum before being preempted and moved to the tail. If a process blocks or finishes before its quantum expires, the next one starts immediately.

It is designed specifically for response time, and it delivers a hard guarantee: with n processes and quantum q, no process waits more than (n - 1) x q before running. Every process gets 1/n of the CPU in fair shares. There is no starvation and no need to predict burst lengths — a considerable practical advantage over SJF.

The price is average waiting time, which is usually worse than SJF's because short jobs no longer jump the queue.

Everything else about round robin depends on the quantum, and the trade-off is worth internalising:

Quantum	Effect
Very large	Degenerates into FCFS — the convoy effect returns
Very small	Excellent response, but context-switch overhead dominates and throughput collapses
Rule of thumb	10-100 ms, chosen so 80% of CPU bursts complete within one quantum

The "80% rule" ties back to 4.1: since most bursts are short, a quantum that covers most of them means most processes give up the CPU voluntarily and are never preempted at all — preemption then applies only to the genuinely long-running minority. That is exactly the behaviour you want.

A subtlety worth knowing: turnaround time is not monotonic in the quantum. Making the quantum larger can improve turnaround (fewer switches) or worsen it (more convoying), so it must be measured rather than reasoned about abstractly.

Analogy: a teacher giving each raised hand exactly two minutes before moving on. Nobody waits forever, everyone gets attention quickly, and the student with a genuinely long question needs many turns to finish.

Example

   P1 burst 24, P2 burst 3, P3 burst 3, quantum = 4

   |= P1 =|= P2 =|= P3 =|= P1 =|= P1 =|= P1 =|= P1 =|= P1 =|
   0      4      7      10     14     18     22     26     30

   waiting = finish - arrival - burst
     P1 = 30 - 0 - 24 = 6      P2 = 7 - 0 - 3 = 4      P3 = 10 - 0 - 3 = 7
   average waiting = 5.67   (FCFS on the same set: 17.0)
   response time: P2 waits only 4, not 24 -- the point of the algorithm

   Quantum sensitivity, one job of 10 units, switch cost 1 unit

   q = 12 : |========== 10 =========|                overhead 0%,  = FCFS
   q = 6  : |== 6 ==|s|== 4 ==|                       overhead ~9%
   q = 1  : |1|s|1|s|1|s|1|s|1|s|1|s|1|s|1|s|1|s|1|   overhead 50%

   The 80% rule: pick q so that ~80% of CPU bursts finish inside one quantum,
   so most processes are never preempted at all.

from collections import deque

def round_robin(processes, quantum):
    """processes: list of (name, arrival, burst)."""
    remaining = {p[0]: p[2] for p in processes}
    arrival   = {p[0]: p[1] for p in processes}
    burst     = {p[0]: p[2] for p in processes}
    pending   = sorted(processes, key=lambda p: p[1])
    queue, clock, finish, switches = deque(), 0, {}, 0

    while pending or queue:
        while pending and pending[0][1] <= clock:        # admit new arrivals
            queue.append(pending.pop(0)[0])              # to the TAIL
        if not queue:
            clock = pending[0][1]
            continue

        name = queue.popleft()                           # take from the HEAD
        slice_ = min(quantum, remaining[name])           # run at most one quantum
        clock += slice_
        remaining[name] -= slice_
        switches += 1

        while pending and pending[0][1] <= clock:        # arrivals during the
            queue.append(pending.pop(0)[0])              # slice queue BEFORE the
                                                         # preempted process
        if remaining[name] > 0:
            queue.append(name)                           # preempted: back to tail
        else:
            finish[name] = clock

    waits = {n: finish[n] - arrival[n] - burst[n] for n in finish}
    return waits, sum(waits.values()) / len(waits), switches

for q in (1, 4, 12, 100):
    w, avg, sw = round_robin([("P1",0,24), ("P2",0,3), ("P3",0,3)], q)
    print(f"quantum {q:3}: avg wait {avg:5.2f}, switches {sw}")

Key takeaways

• Round robin gives each process one quantum in FIFO order, preempting and requeueing at the tail.
• It guarantees a response time bound of (n - 1) x q and cannot starve any process.
• The quantum is the whole design: too large degenerates to FCFS, too small drowns in switching overhead.
• Choose a quantum that covers roughly 80% of CPU bursts so most processes are never preempted.

🧪 Practice

1. Build the Gantt chart for P1 (0, 5), P2 (1, 3), P3 (2, 8) with quantum 2, and compute all three metrics.
2. Run the simulation across quanta 1 through 25 and plot average waiting time. Explain why the curve is not monotonic.
3. Interview-style: "A system has a 100 ms quantum and users complain of lag. Would you shorten it? What else would you check?" Hint: consider the burst distribution and the switch cost before touching the knob.

Multilevel Queue

Theory

The previous algorithms assume a single ready queue and one policy for everyone. But different classes of process want genuinely different things — interactive jobs want response time, batch jobs want throughput, system tasks want priority — and no single policy serves them all.

A multilevel queue scheduler partitions the ready queue into several separate queues, assigns each process permanently to one based on its class, and gives each queue its own scheduling algorithm:

Queue (highest first)	Typical algorithm	Rationale
Real-time processes	Priority or FIFO	Deadlines must be met
System processes	Round robin, short quantum	Kernel work should be prompt
Interactive processes	Round robin, medium quantum	Response time matters
Batch processes	FCFS	Throughput matters; nobody is watching

A second policy is then needed to schedule between queues, and there are two choices:

• Fixed-priority preemption: no process in a lower queue runs while any higher queue is non-empty. Simple and predictable — and it starves the lower queues under sustained load.
• Time slicing between queues: each queue receives a fixed share of CPU (say 80% interactive, 20% batch) to distribute among its own members. This bounds starvation at the cost of some responsiveness for the top queue.

The defining limitation is inflexibility: assignment is permanent. A process that starts as batch stays batch even if it becomes interactive, and vice versa. Since scheduling overhead is low (the queue is chosen by class, not computed), this design is cheap — but it cannot adapt, which is exactly what the next topic fixes.

Analogy: an airport with separate first-class, priority, and economy lines, each run differently. Efficient and predictable, but you cannot move between lines no matter how your situation changes.

Example

   MULTILEVEL QUEUE (fixed assignment, fixed priority between queues)

   highest  +---------------------------------------------+
            | real-time      : priority, preemptive       |
            +---------------------------------------------+
            | system         : round robin, q = 8ms       |
            +---------------------------------------------+
            | interactive    : round robin, q = 20ms      |
            +---------------------------------------------+
   lowest   | batch          : FCFS                       |
            +---------------------------------------------+

   Rule: nothing in a lower queue runs while a higher queue has work.
   Consequence: sustained interactive load starves batch entirely.

   Alternative: time slicing between queues

   real-time  : 20% of CPU
   system     : 20%
   interactive: 40%
   batch      : 20%     <- guaranteed a share; cannot be starved

from collections import deque

class MultilevelQueue:
    """Queues are ordered highest priority first; assignment is PERMANENT."""

    def __init__(self):
        self.queues = [
            {"name": "realtime",    "q": deque(), "algo": "priority", "quantum": None},
            {"name": "system",      "q": deque(), "algo": "rr",       "quantum": 8},
            {"name": "interactive", "q": deque(), "algo": "rr",       "quantum": 20},
            {"name": "batch",       "q": deque(), "algo": "fcfs",     "quantum": None},
        ]

    def admit(self, proc, level):
        self.queues[level]["q"].append(proc)   # class decides the level, once

    def pick_next(self):
        for level in self.queues:              # strict priority: scan top down
            if level["q"]:
                proc = level["q"].popleft()
                return proc, level["quantum"]  # each queue runs its own policy
        return None, None                      # nothing runnable
        # NOTE: a process never moves between levels -- that is the limitation
        #       multilevel FEEDBACK queues remove.

Key takeaways

• Multilevel queues partition processes into classes, each with its own queue and scheduling algorithm.
• A second policy schedules between queues: strict priority, or a guaranteed time share per queue.
• Strict priority between queues starves the lower ones; time slicing bounds that at some cost to responsiveness.
• Assignment is permanent, so the scheduler cannot adapt when a process's behaviour changes.

🧪 Practice

1. Design a three-queue scheme for a desktop OS. Name each queue, its algorithm, and its quantum, with justification.
2. Show a workload under which strict priority starves the batch queue indefinitely, then fix it with time slicing.
3. Interview-style: "Why is permanent queue assignment a problem in practice?" Hint: think about a compiler that spends its first second reading files and the next minute computing.

Multilevel Feedback Queue

Theory

The multilevel feedback queue (MLFQ) is the most important algorithm in this chapter, because it approximates SJF without knowing burst lengths and adapts to changing behaviour. It is the design behind the traditional UNIX, Solaris, Windows, and macOS schedulers.

The structure is a multilevel queue, but processes move between levels based on observed behaviour. The governing rules:

1. New processes enter the highest-priority queue. Optimism: assume it is interactive until proven otherwise.
2. A process that uses its entire quantum is demoted one level. Using a full quantum is evidence of CPU-bound behaviour.
3. A process that blocks before its quantum expires stays at its level (or is promoted). Blocking early is evidence of interactive behaviour.
4. Lower queues get longer quanta. A CPU-bound job runs less often but for longer when it does, which reduces switching overhead.
5. Periodically, all processes are moved back to the top queue (aging). This prevents starvation and lets a job that has changed character be re-evaluated.

The elegance is that priority is inferred from behaviour rather than declared. A process need not announce that it is interactive; it demonstrates it by blocking quickly. Short jobs finish while still in the high-priority queues, so they behave as if SJF had scheduled them, with no prediction required.

Two failure modes drove rules 5 and a refinement:

• Starvation: without periodic promotion, a long job demoted to the bottom may never run under sustained interactive load.
• Gaming: a process that issues a trivial I/O just before its quantum expires keeps its high priority forever. The fix is accounting for total CPU time consumed at a level rather than per-quantum behaviour, so the trick no longer works.

An MLFQ is defined by its parameters: the number of queues, each queue's algorithm and quantum, the demotion rule, the promotion/aging rule, and the entry queue. It is the most configurable classical scheduler, which is both its strength and its tuning burden.

Example

   MULTILEVEL FEEDBACK QUEUE

   Q0  quantum 8ms   ---> uses full quantum? demote --+
        ^                                             |
        | periodic promotion (aging)                  v
        |                                     Q1  quantum 16ms  ---> demote --+
        |                                              ^                      |
        |                                              |                      v
        +----------------------------------------------+-------------  Q2  FCFS

   Rule: blocks early -> stays high (interactive)
         uses it all  -> sinks (CPU-bound)

   Trace: an interactive job I (3ms bursts) and a CPU-bound job C

   t=0    I enters Q0, runs 3ms, BLOCKS      -> stays in Q0
   t=3    C enters Q0, runs 8ms, quantum out -> demoted to Q1
   t=11   I ready again in Q0                -> preempts / runs first
   t=14   I blocks again                     -> stays in Q0
   t=14   C runs 16ms in Q1, quantum out     -> demoted to Q2
   ...
   Result: I keeps top priority forever without ever declaring itself
           interactive; C sinks and runs in long, efficient stretches.

from collections import deque

class MLFQ:
    def __init__(self, quanta=(8, 16, 32), boost_interval=100):
        self.queues = [deque() for _ in quanta]
        self.quanta = quanta
        self.boost_interval = boost_interval     # rule 5: anti-starvation
        self.clock = 0
        self.last_boost = 0

    def admit(self, proc):
        proc.level = 0
        self.queues[0].append(proc)              # rule 1: enter at the top

    def run_next(self):
        if self.clock - self.last_boost >= self.boost_interval:
            self.boost_all()                     # rule 5

        for level, q in enumerate(self.queues):
            if not q:
                continue
            proc = q.popleft()
            quantum = self.quanta[level]
            used = proc.run(quantum)             # returns time actually consumed

            self.clock += used
            if proc.finished:
                return proc
            if used >= quantum:                  # rule 2: consumed it all
                proc.level = min(level + 1, len(self.queues) - 1)   # DEMOTE
            # rule 3: blocked early -> level unchanged (stays interactive)
            self.queues[proc.level].append(proc)
            return proc

    def boost_all(self):
        """Move everything back to Q0: prevents starvation and re-evaluates
           processes whose behaviour has changed."""
        for level in range(1, len(self.queues)):
            while self.queues[level]:
                proc = self.queues[level].popleft()
                proc.level = 0
                self.queues[0].append(proc)
        self.last_boost = self.clock

Key takeaways

• MLFQ moves processes between priority levels based on observed behaviour rather than declared class.
• Using a full quantum demotes a process; blocking early keeps it high, so interactivity is inferred, not announced.
• Lower queues have longer quanta, so CPU-bound work runs less often but in more efficient stretches.
• Periodic promotion prevents starvation and re-evaluates processes whose behaviour has changed; per-level CPU accounting prevents gaming.

🧪 Practice

1. Trace a three-queue MLFQ (quanta 4, 8, 16) with an interactive job (2ms bursts) and a 30ms CPU-bound job. Show the level of each over time.
2. Design the "I/O just before the quantum expires" attack against rules 1-4, then explain how per-level CPU accounting defeats it.
3. Interview-style: "How does MLFQ approximate SJF without knowing burst lengths?" Hint: ask where a short job finishes, and what a long job's demotion reveals about its length.

<a id="43-advanced-scheduling"></a>

4.3 Advanced Scheduling

Real machines have many cores, hardware threads that share execution units, and sometimes deadlines that must not be missed — each of which breaks an assumption the classical algorithms made.

Multiprocessor Scheduling

Theory

Every algorithm so far assumed one CPU and answered one question: which process runs next. With multiple cores there is a second question — where it runs — and the two interact.

The first design decision is who does the scheduling:

• Asymmetric multiprocessing (AMP): one designated processor runs all kernel and scheduling code; the others run user code only. This eliminates concurrent access to scheduler data structures entirely, at the cost of making the master a bottleneck. It is now rare outside specialised embedded systems.
• Symmetric multiprocessing (SMP): every processor schedules itself, running the scheduler on its own core. This is universal today, and it forces the scheduler's own data structures to be concurrent.

That leads to the second decision — the queue organisation — which is the real trade-off:

	Single shared ready queue	Per-CPU ready queues
Load balance	Perfect and automatic	Requires explicit balancing
Lock contention	Severe: every scheduling decision contends	None on the common path
Cache behaviour	Poor: tasks bounce between cores	Good: tasks stay put
Scalability	Degrades badly past ~8 cores	Scales to hundreds of cores
Used by	Early SMP kernels	Linux, Windows, macOS today

Per-CPU queues won decisively. A shared queue means every core takes the same lock on every scheduling decision — at thousands of decisions per second per core, that lock becomes the machine's bottleneck. Per-CPU queues make the common case lock-free at the cost of needing explicit load balancing (next topic).

Modern hardware adds two complications that a naive scheduler gets wrong:

• NUMA: memory is attached to specific sockets, and accessing a remote node's memory can cost twice as much. A scheduler should place a thread on a core near the memory it uses, and the memory allocator should cooperate.
• Heterogeneous cores (ARM big.LITTLE, Intel P-cores/E-cores): cores differ in speed and efficiency. The scheduler must decide not just a core but which kind, based on the task's demands and the power budget — Linux's Energy Aware Scheduling exists for exactly this.

Example

   SINGLE SHARED QUEUE            PER-CPU QUEUES

     +---------------+              +------+ +------+ +------+ +------+
     | ready queue   |              | rq0  | | rq1  | | rq2  | | rq3  |
     +---+---+---+---+              +--+---+ +--+---+ +--+---+ +--+---+
         |   |   |                     |        |        |        |
      core0 core1 core2              core0    core1    core2    core3

   every decision takes ONE lock     no lock on the common path
   perfect balance, terrible         needs periodic balancing,
   scalability                       excellent scalability

   NUMA topology (2 sockets)

   +----------- node 0 -----------+   +----------- node 1 -----------+
   | core0 core1 core2 core3      |   | core4 core5 core6 core7      |
   | +--------------------------+ |   | +--------------------------+ |
   | |   local RAM  (~80 ns)    | |   | |   local RAM  (~80 ns)    | |
   | +--------------------------+ |   | +--------------------------+ |
   +--------------+---------------+   +--------------+---------------+
                  |    interconnect: remote access   |
                  +----------- ~140 ns --------------+

   Running a thread on node 1 while its memory lives on node 0
   costs roughly 1.7x on every memory access.

lscpu                        # sockets, cores, threads, NUMA nodes, cache sizes
numactl --hardware           # node distances: the cost matrix above, measured
cat /proc/schedstat          # per-CPU scheduler statistics, including balancing
lscpu -e                     # per-CPU max frequency: reveals P-cores vs E-cores

# Pin a workload to one NUMA node, memory included:
numactl --cpunodebind=0 --membind=0 ./benchmark

Key takeaways

• SMP is universal: every core runs the scheduler itself, so scheduler data must be concurrency-safe.
• Per-CPU ready queues replaced a single shared queue because the shared lock does not scale.
• Per-CPU queues require explicit load balancing, which a shared queue got for free.
• NUMA and heterogeneous cores mean placement matters as much as ordering: where a thread runs affects its speed.

🧪 Practice

1. Run lscpu and numactl --hardware on a machine you have. Describe its topology and where a scheduler should be careful.
2. Explain why a shared ready queue becomes a bottleneck at high core counts, with rough numbers for lock acquisitions per second.
3. Interview-style: "Why might the same benchmark be 40% slower when run without numactl pinning?" Hint: consider where the memory was allocated versus where the thread ended up.

Load Balancing and Processor Affinity

Theory

Per-CPU queues create the problem they solved contention for: queues drift out of balance, so one core is overloaded while another idles. Load balancing redistributes work; processor affinity resists moving it. They pull in opposite directions, and every SMP scheduler must reconcile them.

Balancing works in two directions:

• Push migration: a periodic task checks for imbalance and pushes threads from overloaded to idle queues.
• Pull migration (work stealing): an idle core pulls a waiting thread from a busy core's queue. This is cheaper — it costs nothing when the system is balanced, and the core doing the work is the one that was idle anyway.

Most kernels use both: pull for immediate idleness, push for periodic correction.

Affinity is the counter-pressure. When a thread runs on a core, it populates that core's L1 and L2 caches and its TLB with its working set. Migrating it discards all of that — the thread must refill caches from memory on the new core, which can cost far more than the queueing delay that motivated the move. This is the same "cache warmth" argument as context-switch cost in Chapter 2, and it is why gratuitous migration hurts.

Two forms exist:

• Soft affinity: the scheduler prefers to keep a thread on its previous core but may move it. This is the default everywhere.
• Hard affinity: the application pins a thread to a specified core set and the scheduler must comply (sched_setaffinity, taskset). Used for latency-critical work, NUMA locality, and benchmarking reproducibility.

The decision to migrate is therefore a cost comparison: migrating pays off only when the queueing delay avoided exceeds the cache-refill cost incurred. Linux formalises this with scheduling domains — a hierarchy mirroring the hardware (SMT siblings, cores sharing L2, sockets, NUMA nodes) where balancing is frequent and cheap within a domain and rare and expensive across domains. Migrating between hyperthreads of one core is nearly free; migrating across sockets abandons the caches entirely and possibly the memory locality too.

Analogy: moving a worker to a less busy desk means they must carry their reference books and re-open everything. Worth it if the new desk is much freer; not worth it for a slight difference.

Example

   Imbalance and the two remedies

   before:   rq0 [A][B][C][D]     rq1 []           rq2 [E]     rq3 []
   push:     a balancer moves D and C from rq0 outward
   pull:     idle rq1 and rq3 steal from rq0 themselves (cheaper: only the
             idle cores do work, and only when there is imbalance)
   after:    rq0 [A][B]           rq1 [C]          rq2 [E]     rq3 [D]

   Linux scheduling domains: balance often where it is cheap

   +---------------------- NUMA domain (rare, expensive) -----------------+
   |  +------- socket 0 --------+        +------- socket 1 --------+      |
   |  | +--- core0 ---+  +core1+|        | +--- core4 ---+  +core5+|      |
   |  | | HT0    HT1  |  |     ||        | | HT0    HT1  |  |     ||      |
   |  | +-------------+  +-----+|        | +-------------+  +-----+|      |
   |  |   SMT domain: balance    |        |                        |      |
   |  |   constantly (free)      |        |                        |      |
   |  +--------------------------+        +-------------------------+      |
   +----------------------------------------------------------------------+

   cost of migration:
     between SMT siblings : ~free (shared L1/L2)
     between cores, 1 die : cheap (shared L3)
     between sockets      : expensive (cold caches + possibly remote memory)

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>

int main(void) {
    cpu_set_t set;
    CPU_ZERO(&set);
    CPU_SET(2, &set);          /* restrict this thread to CPU 2 only */
    CPU_SET(3, &set);          /* ...and CPU 3: a two-core affinity mask */

    /* HARD affinity: the scheduler must now honour this. Used for
       latency-critical threads, NUMA locality, and reproducible benchmarks. */
    if (sched_setaffinity(0, sizeof set, &set) != 0)
        perror("sched_setaffinity");

    printf("running on CPU %d\n", sched_getcpu());
    return 0;
}

taskset -c 0-3 ./benchmark          # pin to cores 0-3 without changing the code
taskset -pc 1234                    # show an existing process's affinity mask
watch -n1 'grep -c . /proc/schedstat'   # observe balancing activity
perf stat -e migrations,cache-misses ./workload   # migrations vs cache cost

Key takeaways

• Per-CPU queues drift out of balance; push migration and pull migration (work stealing) correct it.
• Affinity resists migration because moving a thread abandons its warm caches and TLB entries.
• Soft affinity is a preference the scheduler may override; hard affinity pins a thread to a core set.
• Scheduling domains make balancing frequent within cheap hardware boundaries and rare across expensive ones.

🧪 Practice

1. Run a CPU-bound benchmark with and without taskset pinning, and count migrations with perf stat -e migrations.
2. Explain when migrating a thread is a net loss, using rough numbers for cache refill versus queueing delay.
3. Interview-style: "You pin all worker threads to specific cores and throughput drops. What happened?" Hint: consider what the scheduler can no longer do when load is uneven or another workload appears.

Symmetric Multithreading

Theory

Symmetric multithreading (SMT, marketed as Hyper-Threading) is a hardware technique in which one physical core presents itself as two (or more) logical processors. Each logical CPU has its own architectural state — registers, program counter, interrupt state — but the two share the core's execution resources: ALUs, floating-point units, caches, and the TLB.

The motivation is that a single instruction stream cannot keep a modern core's execution units busy. Cache misses, branch mispredictions, and dependency stalls leave functional units idle for large fractions of every cycle. With two streams available, the core issues instructions from whichever has work ready, filling those gaps.

The essential consequence for scheduling is that two logical CPUs on one core are not two real CPUs. Typical gains are 15-30% total throughput, not 100%. So the scheduler must know the topology and act on it:

• Spread before stacking. With two runnable threads and two physical cores each with two SMT siblings, put the threads on different physical cores. Placing both on one core's siblings leaves an entire core idle while the two threads fight over one core's execution units.
• Sibling contention is real. Two cache-heavy threads on one core evict each other's data from a shared L1/L2. Two threads with complementary demands (one memory-bound, one compute-bound) share well.
• Latency-critical work should not share. A real-time or latency-sensitive thread on a core whose sibling is running a compute hog sees unpredictable slowdowns.

SMT also creates a security problem: siblings share caches and execution ports, which enables cross-thread side-channel attacks. This is why some cloud providers and hardened systems disable SMT entirely, accepting the throughput loss.

Analogy: two cooks sharing one kitchen. Output rises, because one can chop while the other waits for water to boil — but it is not double, and if both need the single oven at once, they interfere.

Example

   SMT: one physical core, two logical CPUs

   +------------------- physical core 0 --------------------+
   |  logical CPU 0            logical CPU 1                |
   |  +-------------+          +-------------+              |
   |  | registers   |          | registers   |   PRIVATE    |
   |  | PC, flags   |          | PC, flags   |              |
   |  +------+------+          +------+------+              |
   |         |                        |                     |
   |         +------------+-----------+                     |
   |                      v                                 |
   |     ALUs | FPU | L1 cache | L2 cache | TLB    SHARED    |
   +--------------------------------------------------------+

   Why it helps: filling stall cycles

   one thread :  [exec][STALL: cache miss][exec][STALL][exec]
   two threads:  [ T0 ][      T1        ][ T0 ][  T1 ][ T0 ]
                 the core issues from whichever stream is ready

   PLACEMENT MATTERS: 2 threads, 2 cores x 2 SMT siblings

   BAD:   core0 [T0][T1]   core1 [  idle  ]   -> ~1.2x throughput
   GOOD:  core0 [T0][ - ]  core1 [T1][ -  ]   -> ~2.0x throughput

   Linux numbering trap: CPUs 0-3 are often core0-HT0, core1-HT0,
   core0-HT1, core1-HT1 -- so "cores 0 and 1" may or may not be siblings.
   Always check with lscpu -e before pinning.

lscpu -e=CPU,CORE,SOCKET      # which logical CPUs share a physical core
cat /sys/devices/system/cpu/cpu0/topology/thread_siblings_list   # e.g. "0,4"

# Measure the difference yourself: same two threads, two placements.
taskset -c 0,4 ./two_thread_bench    # both on ONE core's siblings (bad)
taskset -c 0,1 ./two_thread_bench    # on two distinct physical cores (good)

# Disable SMT entirely (throughput cost, but removes sibling side channels):
echo off | sudo tee /sys/devices/system/cpu/smt/control

# Reading the topology so a program can place its own threads correctly.
from pathlib import Path

def physical_cores():
    """Map physical core id -> list of logical CPUs (its SMT siblings)."""
    cores = {}
    for cpu in Path("/sys/devices/system/cpu").glob("cpu[0-9]*"):
        topo = cpu / "topology" / "core_id"
        if topo.exists():
            core_id = int(topo.read_text())
            cores.setdefault(core_id, []).append(int(cpu.name[3:]))
    return cores

# Spread first: take one logical CPU per physical core before using siblings.
layout = physical_cores()
spread = [siblings[0] for siblings in layout.values()]     # use these first
stacked = [c for sibs in layout.values() for c in sibs[1:]]  # only if needed
print("prefer:", sorted(spread), "then:", sorted(stacked))

Key takeaways

• SMT gives one physical core several logical CPUs that share execution units, caches, and TLB.
• It fills stall cycles, typically yielding 15-30% extra throughput — not double.
• The scheduler must spread threads across physical cores before stacking them onto SMT siblings.
• Siblings contend for cache and execution ports, hurting latency-critical work and enabling side-channel attacks.

🧪 Practice

1. Determine your machine's sibling pairs with lscpu -e, then run a two-thread benchmark stacked and spread. Report the ratio.
2. Explain why two memory-bound threads share a core worse than one memory-bound plus one compute-bound thread.
3. Interview-style: "Would you enable SMT on a latency-sensitive trading server?" Hint: weigh average throughput against worst-case jitter and the side-channel exposure.

Real-Time Scheduling

Theory

Everything so far optimised averages. Real-time systems invert the priority: correctness depends on when a result is produced, not merely that it is produced. A late answer is a wrong answer.

Two categories, with very different engineering consequences:

	Hard real-time	Soft real-time
Missing a deadline	System failure; may be catastrophic	Quality degrades; system continues
Guarantee needed	Provable, worst-case	Statistical, best-effort priority
Examples	Airbag deployment, flight control, pacemakers, industrial robots	Video playback, VoIP, gaming, live streaming
Requires	Bounded worst-case latency everywhere	High priority and low average latency

A hard real-time system needs guarantees from every layer, not just the scheduler: bounded interrupt latency, bounded dispatch latency (4.1), no unbounded priority inversion, no page faults (memory is locked resident), and no unpredictable caches or garbage collection. This is why general-purpose kernels are unsuitable out of the box and why dedicated RTOS designs (VxWorks, QNX, FreeRTOS, Zephyr) exist.

The scheduling model uses periodic tasks, each characterised by three numbers: period p (how often it becomes ready), processing time t (worst-case execution time), and deadline d (by when it must complete, usually d = p). The CPU utilisation of a task is t / p, and the system's total utilisation is the sum. This model is what makes analysis possible: with these parameters known, schedulability can be proved before deployment rather than tested for.

A crucial requirement is admission control: the system must refuse a task set it cannot guarantee. Accepting work that cannot be scheduled and then missing deadlines is worse than rejecting it up front.

Linux offers SCHED_FIFO and SCHED_RR (POSIX real-time classes, fixed priorities 1-99, always preempting normal tasks) and SCHED_DEADLINE (an EDF implementation with admission control). These give soft real-time behaviour on a standard kernel; hard guarantees need PREEMPT_RT or a dedicated RTOS.

Example

   Periodic task model

   task T: period p = 50ms, execution t = 20ms, deadline d = p

   |<---------- p = 50 --------->|<---------- p = 50 --------->|
   [== t = 20 ==]                [== t = 20 ==]
   ^            ^                ^
   release      must finish      next release
                by d = 50

   utilisation U = t/p = 20/50 = 0.4  (40% of the CPU reserved for T)

   Latency budget for a hard real-time response

   event -> interrupt latency -> handler -> conflict phase -> dispatch -> task
            |<---- every one of these must be BOUNDED ---->|

            If any link is unbounded (a non-preemptible kernel path,
            a page fault, a GC pause), the guarantee is void.

#define _GNU_SOURCE
#include <sched.h>
#include <sys/mman.h>
#include <stdio.h>

int main(void) {
    /* 1. Lock all memory resident: a page fault would be an unbounded delay. */
    if (mlockall(MCL_CURRENT | MCL_FUTURE) != 0)
        perror("mlockall");

    /* 2. Ask for a real-time class. SCHED_FIFO runs until it blocks or is
          preempted by something of HIGHER priority -- it is not time-sliced. */
    struct sched_param param = { .sched_priority = 80 };   /* 1..99 */
    if (sched_setscheduler(0, SCHED_FIFO, &param) != 0)
        perror("sched_setscheduler");     /* needs CAP_SYS_NICE / root */

    /* WARNING: a SCHED_FIFO task that never blocks will monopolise its core.
       Linux's rt_runtime_us throttle exists to keep such a bug from
       making the machine unrecoverable. */
    printf("policy=%d priority=%d\n", sched_getscheduler(0), param.sched_priority);
    return 0;
}

chrt -f 80 ./control_loop      # run with SCHED_FIFO priority 80
chrt -p $$                     # show the current shell's policy
cat /proc/sys/kernel/sched_rt_runtime_us   # 950000: RT tasks capped at 95%
uname -a | grep -i preempt     # is this a PREEMPT_RT kernel?

Key takeaways

• Real-time correctness depends on timing: hard systems fail if a deadline is missed, soft systems merely degrade.
• Hard guarantees require bounded latency in every layer — interrupts, kernel paths, memory, and locking.
• Tasks are modelled as periodic with period, worst-case execution time, and deadline, giving utilisation t/p.
• Admission control must reject task sets that cannot be guaranteed, rather than accepting and missing deadlines.

🧪 Practice

1. Classify as hard or soft, with justification: anti-lock braking, Netflix playback, a pacemaker, a multiplayer game server.
2. Compute total utilisation for tasks (t=10, p=30), (t=15, p=60), (t=5, p=25). Is it below 1.0? Does that guarantee schedulability?
3. Interview-style: "Why can't you get hard real-time guarantees from a standard Linux kernel?" Hint: name three sources of unbounded delay that have nothing to do with the scheduling policy.

Rate-Monotonic Scheduling

Theory

Rate-monotonic scheduling (RMS) assigns static priorities to periodic tasks by one rule: the shorter the period, the higher the priority. A task that runs every 20 ms outranks one that runs every 100 ms, permanently, regardless of urgency or importance. It is preemptive: a higher-rate task arriving preempts a lower-rate one immediately.

The rule looks arbitrary and is in fact optimal — RMS is provably the best possible static-priority algorithm for periodic tasks. If any fixed-priority assignment can schedule a task set, rate-monotonic can. The intuition is that a short-period task has less slack: it must finish sooner after each release, so delaying it is more dangerous.

Its practical value is the schedulability test, which can be checked before deployment:

U = sum(t_i / p_i)  <=  n * (2^(1/n) - 1)

This bound is sufficient but not necessary: any task set below it is guaranteed schedulable; a set above it may still be schedulable and needs exact analysis. The bound decreases with the number of tasks, converging to ln 2 ≈ 0.693. So in the worst case, roughly 31% of the CPU must be left unused to guarantee deadlines under RMS — that is the price of static priorities.

The strengths are predictability and simplicity: priorities are fixed, so behaviour is easy to analyse and to certify, and overload degrades predictably (the longest-period task misses first). The weakness is the utilisation ceiling, which EDF removes.

Analogy: a nurse always attending the patient whose vitals must be checked most frequently. Simple, predictable, and it works — provided the ward is not too full.

Example

   SCHEDULABLE: P1 (p=50, t=20), P2 (p=100, t=35)

   U = 20/50 + 35/100 = 0.40 + 0.35 = 0.75
   bound for n=2: 2 * (2^0.5 - 1) = 0.828
   0.75 <= 0.828  -> GUARANTEED schedulable

   P1 has the shorter period, so it gets the higher priority.

   0        20      50      70        100     120    150
   |=P1=====|==P2===|=P1====|===P2====|=P1====|      |
   0        20      50      70        100
     P1 runs 0-20 (deadline 50, met)
     P2 runs 20-50, preempted by P1 at 50
     P1 runs 50-70 (deadline 100, met)
     P2 resumes 70-75, completing its 35 units (deadline 100, met)

   NOT SCHEDULABLE BY RMS: P1 (p=50, t=25), P2 (p=80, t=35)

   U = 25/50 + 35/80 = 0.50 + 0.4375 = 0.9375  >  0.828 -> no guarantee

   0        25      50      75    80
   |=P1=====|==P2===|=P1====|=P2=|
   0        25      50      75   80
     P2 gets 25 units (25-50), is preempted at 50 by P1,
     resumes 75-80 for only 5 more = 30 of the 35 it needs.
     DEADLINE MISSED at t=80.

   RMS utilisation bound by task count

   n:      1      2      3      4      5     10    inf
   bound: 1.000  0.828  0.780  0.757  0.743  0.718  0.693

def rms_schedulable(tasks):
    """tasks: list of (name, period, exec_time). Returns (utilisation, bound, ok).
       The test is SUFFICIENT, not necessary: failing it does not prove
       the set is unschedulable, only that RMS cannot guarantee it."""
    n = len(tasks)
    u = sum(t / p for _, p, t in tasks)
    bound = n * (2 ** (1 / n) - 1)               # Liu and Layland bound
    return u, bound, u <= bound

def rms_priorities(tasks):
    """Rate monotonic: shorter period -> higher priority. That is the whole rule."""
    return [name for name, p, t in sorted(tasks, key=lambda x: x[1])]

set_a = [("P1", 50, 20), ("P2", 100, 35)]
set_b = [("P1", 50, 25), ("P2", 80, 35)]

for s in (set_a, set_b):
    u, bound, ok = rms_schedulable(s)
    print(f"U={u:.4f} bound={bound:.4f} -> {'guaranteed' if ok else 'NOT guaranteed'}"
          f"  priority order: {rms_priorities(s)}")

Key takeaways

• Rate-monotonic assigns static priorities by period: shorter period means higher priority, always.
• It is optimal among static-priority algorithms — if any fixed assignment works, RMS works.
• The test U <= n(2^(1/n) - 1) is sufficient but not necessary, and converges to about 69%.
• Up to 31% of CPU capacity may have to go unused to guarantee deadlines; that is the cost of static priorities.

🧪 Practice

1. Test schedulability for P1 (p=20, t=5), P2 (p=50, t=15), P3 (p=100, t=30). Assign RMS priorities.
2. Draw the Gantt chart for P1 (p=30, t=10) and P2 (p=40, t=15) over 120 time units and check every deadline.
3. Interview-style: "A task set has U = 0.75 with three tasks and fails the RMS bound. Is it definitely unschedulable?" Hint: recall exactly what a sufficient-but-not-necessary condition claims.

Earliest Deadline First

Theory

EDF replaces static priorities with dynamic ones: at every scheduling instant, run the task whose absolute deadline is nearest. Priorities are not properties of tasks; they change continuously as deadlines approach and are renewed each period.

The payoff is theoretically the strongest result in real-time scheduling: EDF is optimal for uniprocessors, and its schedulability test is simply

U = sum(t_i / p_i)  <=  1.0

If the total demand fits in the available CPU time, EDF meets every deadline. There is no wasted 31%. A task set that RMS cannot guarantee at U = 0.9375 is trivially schedulable under EDF.

The trade-offs explain why RMS is still widely used in safety-critical systems:

	Rate Monotonic	EDF
Priorities	Static, assigned once	Dynamic, recomputed continuously
Utilisation bound	~0.693 to 0.828	1.0
Runtime cost	Very low	Higher: deadline tracking and reordering
Behaviour in overload	Predictable — longest period fails first	Unpredictable — domino effect: a missed deadline makes the next task even more urgent, cascading failures
Analysis and certification	Simple, well-understood	Harder to argue about
Typical use	Avionics, automotive, certified systems	Multimedia, SCHED_DEADLINE, systems with slack

The overload behaviour is the decisive practical difference. Under RMS, if the system is overloaded, you know which task misses: the one with the longest period. Under EDF, one missed deadline shifts urgency to the next task, which may then miss, and the failure cascades unpredictably. For a certified avionics system, predictable degradation is worth more than the extra 20% of CPU.

Linux implements EDF as SCHED_DEADLINE, where each task declares a runtime, a deadline, and a period, and the kernel performs admission control — refusing tasks that would push utilisation above the guaranteed bound. That refusal is the mechanism that makes the guarantee real.

Example

   The set RMS could NOT guarantee: P1 (p=50, t=25), P2 (p=80, t=35)
   U = 0.9375 <= 1.0  -> EDF guarantees it

   t=0   P1 deadline 50, P2 deadline 80  -> P1 is nearer, run P1
   t=25  P1 done. Run P2 (deadline 80).
   t=50  P1 released, deadline 100. P2's deadline 80 is NEARER -> P2 continues
         (this is exactly where RMS preempted and lost)
   t=60  P2 done (35 units: 25-60). Deadline 80 MET.
   t=60  Run P1 (deadline 100).
   t=85  P1 done. Deadline 100 MET.

   |=== P1 ===|====== P2 ======|====== P1 ======|
   0          25               60               85
                    ^
                    P1's release at t=50 does NOT preempt, because P2's
                    deadline is sooner. Static priority could not express this.

   The domino effect under overload (U > 1.0)

   RMS overload:  the longest-period task misses. Every time. Predictable.
   EDF overload:  T1 misses -> T2 is now most urgent -> T2 misses ->
                  T3 is now most urgent -> ... cascade, order unpredictable

def edf_schedulable(tasks):
    """EDF on a uniprocessor: schedulable if and only if U <= 1.0."""
    u = sum(t / p for _, p, t in tasks)
    return u, u <= 1.0

def edf_pick(ready, now):
    """The entire policy: nearest ABSOLUTE deadline wins.
       Absolute deadline = release time of the current instance + relative deadline,
       so priorities change every period -- unlike RMS."""
    return min(ready, key=lambda task: task.absolute_deadline)

tasks = [("P1", 50, 25), ("P2", 80, 35)]
u, ok = edf_schedulable(tasks)
print(f"U={u:.4f} -> EDF: {'schedulable' if ok else 'overloaded'}")
# U=0.9375 -> schedulable   (RMS could not guarantee this same set)

/* Linux SCHED_DEADLINE: EDF with admission control built in. */
struct sched_attr attr = {
    .size           = sizeof(struct sched_attr),
    .sched_policy   = SCHED_DEADLINE,
    .sched_runtime  = 10 * 1000 * 1000,   /* 10 ms of CPU ...        */
    .sched_deadline = 30 * 1000 * 1000,   /* ... to be done within 30 ms ... */
    .sched_period   = 30 * 1000 * 1000,   /* ... every 30 ms.        */
};
/* The kernel REFUSES this call with EBUSY if admitting the task would push
   total utilisation past what it can guarantee. The refusal is the guarantee. */
if (syscall(SYS_sched_setattr, 0, &attr, 0) != 0)
    perror("sched_setattr");

Key takeaways

• EDF dynamically prioritises by nearest absolute deadline, recomputed as deadlines approach.
• It is optimal on a uniprocessor and schedulable whenever total utilisation is at most 1.0.
• It costs more at run time and behaves unpredictably in overload, cascading missed deadlines.
• RMS remains preferred for certified systems because its overload failure is predictable; Linux offers EDF as SCHED_DEADLINE with admission control.

🧪 Practice

1. Verify EDF schedulability for P1 (p=40, t=15), P2 (p=60, t=20), P3 (p=120, t=30), and compare with the RMS bound.
2. Draw the EDF Gantt chart for P1 (p=30, t=10), P2 (p=45, t=15) over 90 units, marking each absolute deadline.
3. Interview-style: "EDF achieves 100% utilisation. Why do avionics systems still use rate monotonic?" Hint: ask what happens on the first overload, and what a certification authority needs to be told.

<a id="44-evaluation-and-practice"></a>

4.4 Evaluation and Practice

Choosing between the algorithms above requires a method for comparing them, and the schedulers that actually ship are worth studying as the compromises they are.

Deterministic Modeling

Theory

Deterministic modeling is the simplest evaluation method: take a specific, fully specified workload and compute exactly what each algorithm would do with it. This is what the worked Gantt charts in 4.2 are — you fix the arrival times and burst lengths, run each algorithm on paper, and compare the resulting numbers.

Its virtues are real: it is exact (no statistical uncertainty), fast, reproducible, and explanatory — you can see precisely why one algorithm beats another on this workload, not merely that it does. It is also the right tool for teaching, for sanity-checking an implementation, and for generating regression tests.

Its limitation is equally clear: the answer applies only to that specific workload. Showing that SJF beats FCFS on one five-process example proves nothing about a production system whose arrival pattern differs. Real workloads have variable and unknown burst lengths, arrivals that depend on completions (a user only issues the next command after seeing the last result), and behaviour that changes over time.

The disciplined use is therefore to model several deliberately chosen workloads rather than one, especially adversarial cases: all-short jobs, all-long jobs, one long job among many short ones, a burst of simultaneous arrivals. An algorithm that looks good on the average case and catastrophic on a plausible edge case is not a good algorithm.

Analogy: deterministic modeling is testing a car design against one specific road. Precise, informative, and no evidence at all about how it handles the other roads.

Example

   One workload, four algorithms, computed exactly

   P1 arrives 0 burst 10   P2 arrives 1 burst 4
   P3 arrives 2 burst 2    P4 arrives 3 burst 6

   FCFS   |==== P1 ====|= P2 =|P3|=== P4 ===|
          0            10     14 16         22
          waiting: 0, 9, 12, 13          avg = 8.50

   SJF    |==== P1 ====|P3|= P2 =|=== P4 ===|
          0            10 12     16         22
          waiting: 0, 11, 8, 13           avg = 8.00

   SRTF   |P1|= P2 =|P3|=== P4 ===|=== P1 ===|
          0  1      5  7          13         22
          waiting: 12, 0, 3, 4            avg = 4.75   <- best here

   RR q=4 |= P1 =|= P2 =|P3|= P4 =|= P1 =|= P4 =|= P1 =|
          0      4      8  10     14     18     20     22
          waiting: 8, 3, 6, 9             avg = 6.50

   Conclusion: SRTF wins ON THIS WORKLOAD. Change the arrivals and the
   ranking can change -- which is exactly the method's limitation.

def compare(workload):
    """Deterministic modeling: run every algorithm on one exact workload."""
    results = {
        "FCFS":   fcfs(workload)[1],
        "SJF":    sjf(workload)[1],
        "SRTF":   srtf(workload)[1],
        "RR q=4": round_robin(workload, 4)[1],
    }
    for name, avg in sorted(results.items(), key=lambda kv: kv[1]):
        print(f"{name:8} avg waiting = {avg:.2f}")
    return results

# Model several DELIBERATELY CHOSEN workloads, not just one.
compare([("P1",0,10), ("P2",1,4), ("P3",2,2), ("P4",3,6)])   # mixed
compare([("P1",0,2),  ("P2",0,2), ("P3",0,2), ("P4",0,2)])   # all short
compare([("P1",0,50), ("P2",1,1), ("P3",2,1), ("P4",3,1)])   # convoy case

Key takeaways

• Deterministic modeling computes exact results for one fully specified workload.
• It is fast, reproducible, and shows why an algorithm wins, which makes it ideal for teaching and testing.
• Its conclusions do not generalise: a different arrival pattern can reverse the ranking.
• Use several workloads, including adversarial ones, rather than a single representative case.

🧪 Practice

1. Compute average waiting time under FCFS, SJF, and RR (q=3) for P1 (0, 8), P2 (1, 4), P3 (2, 9), P4 (3, 5).
2. Construct a workload on which FCFS beats SJF for average response time, and explain the mechanism.
3. Interview-style: "Your benchmark shows algorithm A is 20% better. What would you check before deploying it?" Hint: ask how the benchmark's arrival pattern compares with production traffic.

Queueing Analysis

Theory

Deterministic modeling needs an exact workload. Queueing analysis needs only its statistical description, which is far easier to obtain from a running system: an arrival rate and a service rate. It then predicts average queue lengths and waiting times mathematically.

The central result is Little's Law, which is remarkable for how few assumptions it makes:

n = lambda x W

where n is the average number of items in the system, lambda the average arrival rate, and W the average time each item spends in the system. It holds for any stable system regardless of arrival distribution, service distribution, or scheduling discipline — which makes it the most broadly useful formula in performance work. Given any two quantities, you get the third: a server handling 50 requests/second with an average of 5 requests in flight has an average response time of 100 ms.

For a single-server queue with Poisson arrivals and exponential service times (an M/M/1 queue), utilisation rho = lambda / mu gives:

average number in system   n = rho / (1 - rho)
average time in system     W = 1 / (mu - lambda)

The critical insight is the shape of that curve: waiting time grows without bound as utilisation approaches 1. At 50% utilisation the queue holds 1 item; at 90% it holds 9; at 99% it holds 99. Doubling utilisation from 45% to 90% multiplies queueing delay roughly tenfold. This is the mathematical reason capacity planning targets 60-80% utilisation rather than 95% — the last few percent of capacity cost enormous latency.

The limitations are the assumptions. Real arrivals are bursty rather than Poisson, service times are not exponential, and queueing networks with feedback are hard to solve in closed form. Queueing analysis therefore gives excellent intuition and approximate answers, and should not be trusted for precise predictions.

Example

   The utilisation wall (M/M/1)

   rho (utilisation)  |  avg items in system  |  latency multiplier
   -------------------+-----------------------+--------------------
        0.10          |         0.11          |        1.1x
        0.50          |         1.00          |        2.0x
        0.70          |         2.33          |        3.3x
        0.80          |         4.00          |        5.0x
        0.90          |         9.00          |       10.0x
        0.95          |        19.00          |       20.0x
        0.99          |        99.00          |      100.0x

   latency
     |                                              *
     |                                          *
     |                                     *
     |                              *
     |                   *
     |        *
     |  *  *
     +--------------------------------------------> utilisation
     0        0.5              0.8    0.9   0.95  1.0
                                       ^
                            plan to operate here, not further right

   Little's Law in practice

   A queue holds 40 requests on average; arrivals are 200/second.
   W = n / lambda = 40 / 200 = 0.2 s  -> average latency is 200 ms.
   No assumption about the scheduler was needed to say that.

def littles_law(n=None, arrival_rate=None, wait=None):
    """n = lambda * W. Supply any two; get the third.
       Holds for ANY stable system: no distribution assumptions required."""
    if n is None:          return arrival_rate * wait
    if arrival_rate is None: return n / wait
    return n / arrival_rate

def mm1(arrival_rate, service_rate):
    """Single server, Poisson arrivals, exponential service."""
    if arrival_rate >= service_rate:
        raise ValueError("unstable: the queue grows without bound")
    rho = arrival_rate / service_rate                  # utilisation
    n   = rho / (1 - rho)                              # avg items in system
    w   = 1 / (service_rate - arrival_rate)            # avg time in system
    return {"utilisation": rho, "avg_in_system": n, "avg_time": w}

# A server that can handle 100 req/s, at increasing load:
for lam in (50, 70, 80, 90, 95, 99):
    r = mm1(lam, 100)
    print(f"load {lam:3}/s  rho={r['utilisation']:.2f}  "
          f"queue={r['avg_in_system']:6.2f}  latency={r['avg_time']*1000:7.1f} ms")
# The jump from 90 to 99 req/s -- 10% more work -- costs 10x the latency.

Key takeaways

• Queueing analysis predicts average behaviour from arrival and service rates rather than an exact workload.
• Little's Law (n = lambda x W) holds for any stable system, independent of distributions and scheduling policy.
• Waiting time rises without bound as utilisation approaches 100%, which is why systems are planned for 60-80%.
• Its assumptions (Poisson arrivals, exponential service) rarely hold exactly, so treat results as intuition, not prediction.

🧪 Practice

1. A service receives 120 requests/second and holds 18 on average. Compute the average response time using Little's Law.
2. Using the M/M/1 model with a service rate of 200/s, compute latency at 100, 160, 180, and 195 requests/second. Comment on the trend.
3. Interview-style: "Management wants to run servers at 95% CPU to save money. What is your response?" Hint: quantify the latency multiplier and what a small traffic spike then does.

Simulation and Benchmarking

Theory

When mathematical models are too restrictive and paper analysis too narrow, the remaining options are to simulate the scheduler on synthetic or recorded workloads, or to benchmark a real implementation on real hardware.

Simulation implements the algorithm and drives it with generated events, keeping a clock and statistics. It sits between the two previous methods in fidelity and cost. The critical question is the workload source:

• Randomly generated from a distribution: easy, and only as valid as the distribution chosen. Exponential burst lengths (4.1) are a defensible starting point.
• Trace-driven: recorded from a real system, capturing actual arrival patterns, correlations, and bursts. Far more credible, and the standard when accuracy matters.

Trace-driven simulation has one subtlety worth knowing: a trace is a recording of what happened under the scheduler that produced it. Feeding it to a different scheduler is not fully sound, because real arrivals depend on completions — a user issues the next command only after the previous one returns. Traces are still the best available input, but the feedback loop they omit is a real source of error.

Benchmarking runs actual software on actual hardware and is the only method that captures cache effects, NUMA behaviour, interrupt load, and lock contention — the things that dominate real performance and that no model represents. It is also the most expensive, the least controllable, and the hardest to interpret, because so many variables move at once.

Sound practice regardless of method:

• Measure distributions, not just means — report p50, p95, p99, and max.
• Run long enough to reach steady state, and discard the warm-up period.
• Repeat runs and report variance; a single run of a concurrent system means little.
• Change one variable at a time, and keep the rest of the machine quiet.
• Beware the observer effect: heavy tracing changes the behaviour being measured.

Example

   The four evaluation methods

   method            | cost   | fidelity | generality | captures hardware?
   ------------------+--------+----------+------------+-------------------
   deterministic     | lowest | exact    | very low   | no
   queueing analysis | low    | approx   | high       | no
   simulation        | medium | good     | medium     | no
   benchmarking      | high   | real     | low        | yes

   Report the distribution, not the mean

   Scheduler A: p50 = 20ms  p95 =  25ms  p99 =  30ms  max =  40ms
   Scheduler B: p50 = 12ms  p95 = 100ms  p99 = 800ms  max = 3000ms

   B has the better average. A is the one users will prefer.

import random, statistics

def simulate_rr(quantum, n_procs=1000, mean_burst=8.0, seed=42):
    """Trace-free simulation: bursts drawn from an exponential distribution,
       which matches the shape observed in 4.1."""
    rng = random.Random(seed)
    bursts = [rng.expovariate(1 / mean_burst) for _ in range(n_procs)]
    switch_cost = 0.05                        # 50 us per context switch

    clock, waits, remaining = 0.0, [0.0] * n_procs, list(bursts)
    arrival = [0.0] * n_procs                 # all arrive at t=0 for simplicity
    finished = 0

    while finished < n_procs:
        for i in range(n_procs):
            if remaining[i] <= 0:
                continue
            slice_ = min(quantum, remaining[i])
            clock += slice_ + switch_cost      # overhead charged every slice
            remaining[i] -= slice_
            if remaining[i] <= 0:
                waits[i] = clock - arrival[i] - bursts[i]
                finished += 1

    waits.sort()
    return {
        "quantum": quantum,
        "mean": statistics.mean(waits),
        "p50": waits[len(waits) // 2],
        "p95": waits[int(0.95 * len(waits))],   # ALWAYS report the tail
        "p99": waits[int(0.99 * len(waits))],
    }

for q in (1, 2, 4, 8, 16, 64):
    r = simulate_rr(q)
    print(f"q={r['quantum']:3}  mean={r['mean']:8.1f}  "
          f"p50={r['p50']:8.1f}  p95={r['p95']:8.1f}  p99={r['p99']:8.1f}")

# Benchmarking the real thing.
perf sched record -- ./workload     # capture actual scheduling events
perf sched latency --sort max       # per-task max scheduling delay
hackbench -l 1000 -g 20             # scheduler stress benchmark
sysbench cpu --threads=16 run       # repeat it; report variance, not one run

Key takeaways

• Simulation implements the algorithm against generated or recorded workloads; trace-driven input is the more credible.
• A trace records behaviour under the scheduler that produced it, so replaying it elsewhere omits the arrival feedback loop.
• Benchmarking is the only method that captures cache, NUMA, interrupt, and locking effects.
• Always report distributions and tails, run to steady state, repeat runs, and change one variable at a time.

🧪 Practice

1. Run the simulation across quanta 1 to 64 and plot mean and p99 waiting time. Explain why they do not improve together.
2. Add a 10% fraction of very long jobs to the burst distribution and rerun. Which percentile moves most, and why?
3. Interview-style: "Why can a trace-driven simulation mislead you about an interactive workload?" Hint: think about when the next request in the trace was actually issued, and what it depended on.

Linux CFS Scheduler

Theory

Linux's Completely Fair Scheduler, introduced in 2.6.23 (2007), took a different approach from the multilevel feedback queues that preceded it. Rather than approximating fairness with priority levels and quanta, CFS models an ideal multitasking CPU that runs all n runnable tasks simultaneously at 1/n of its speed, and then tracks how far each task has fallen behind that ideal.

The mechanism is virtual runtime (vruntime): the CPU time a task has consumed, weighted by its priority. The rule is then a single sentence — always run the task with the lowest vruntime — which is the one that has received least of its fair share. As it runs, its vruntime advances and it eventually stops being the minimum, at which point another task is selected.

The properties follow neatly:

• No fixed time slices. A task runs until it is no longer the most deprived. The effective slice is derived from the number of runnable tasks and a target latency (sched_latency_ns, default 24 ms, subject to min_granularity so slices never become absurdly small under heavy load).
• Priorities are weights, not levels. Nice values map to weights (nice 0 = 1024, each nice step is a factor of about 1.25), and vruntime advances more slowly for higher-weight tasks, so they naturally get more CPU. Each nice level is roughly a 10% change in CPU share.
• I/O-bound tasks are favoured automatically. A task that sleeps accumulates no vruntime, so on waking it is far behind and is scheduled promptly — interactivity emerges from the fairness rule rather than from a heuristic. (A sleeper's vruntime is floored to the minimum in the queue so it cannot hoard unbounded credit.)
• Selection is O(log n) using a red-black tree keyed by vruntime, with the leftmost node cached so picking the next task is O(1).

CFS also supports group scheduling via cgroups: fairness can be applied between groups (users, containers, services) before being applied within them, so 100 threads in one container cannot outcompete 1 thread in another. This is the basis of container CPU limits.

Worth knowing for currency: CFS was replaced as the default by EEVDF (Earliest Eligible Virtual Deadline First) in Linux 6.6. EEVDF keeps the virtual-time fairness accounting but adds an explicit per-task latency requirement and picks among eligible tasks by virtual deadline, improving latency for tasks that need it without special-case heuristics.

Example

   The vruntime rule

   red-black tree keyed by vruntime; leftmost = least service received = run next

                       [vruntime 24]
                      /             \
              [18]                    [31]
             /    \                  /    \
        [12]      [20]          [27]      [40]
        /
   [ 8 ] <-- leftmost: RUN THIS ONE (cached, so selection is O(1))

   After it runs for delta, its vruntime advances by:

        delta_vruntime = delta x (NICE_0_WEIGHT / task_weight)

   nice  weight   effect on vruntime advance    relative CPU share
   ----  ------   -------------------------     ------------------
    -5    3121    advances 3x SLOWER            ~3x more CPU
     0    1024    baseline                      baseline
    +5     335    advances 3x FASTER            ~3x less CPU

   Why sleepers get scheduled promptly, with no heuristic

   CPU-bound task A: runs constantly, vruntime climbs to 5000
   Interactive B:    sleeps 200ms, vruntime stays at 4800
   B wakes -> B has the lower vruntime -> B runs immediately.
   Interactivity falls out of the fairness rule itself.

   Slice length is derived, not fixed

   target latency 24ms, 4 runnable tasks  -> ~6ms each
   target latency 24ms, 48 runnable tasks -> would be 0.5ms, so
   min_granularity (~3ms) takes over and the period stretches instead.

/* The core of CFS, reduced to its essentials. */

/* 1. Charge the running task for the time it just used, scaled by weight. */
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;

    curr->sum_exec_runtime += delta_exec;          /* real time consumed */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    /* calc_delta_fair scales by NICE_0_LOAD / se->load.weight:
       a heavier (lower nice) task accrues vruntime more slowly, so it
       stays "behind" longer and therefore receives more CPU.        */
    curr->exec_start = now;
}

/* 2. Pick the task with the smallest vruntime -- the leftmost tree node. */
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq) {
    return rb_entry(cfs_rq->rb_leftmost, struct sched_entity, run_node);
    /* Cached leftmost pointer makes selection O(1); insertion is O(log n). */
}

/* 3. Slice length is COMPUTED from the number of runnable tasks. */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    u64 period = __sched_period(cfs_rq->nr_running);   /* target latency,
                                                          stretched if crowded */
    return period * se->load.weight / cfs_rq->load.weight;   /* weighted share */
}

cat /proc/sys/kernel/sched_latency_ns          # target latency (default 24ms)
cat /proc/sys/kernel/sched_min_granularity_ns  # floor on a slice
cat /proc/<pid>/sched                          # this task's vruntime and stats
nice -n 10 ./background_job                    # lower weight: ~2.5x less CPU
systemd-run --scope -p CPUWeight=200 ./job     # cgroup group scheduling

Key takeaways

• CFS models an ideal CPU giving every task 1/n of the machine, and always runs the task furthest behind.
• Virtual runtime is CPU time weighted by priority; nice values change the rate at which it accrues.
• Interactivity emerges from the rule itself — sleepers accumulate no vruntime and are scheduled promptly on waking.
• Selection uses a red-black tree with a cached leftmost node; group scheduling extends fairness to cgroups and containers.

🧪 Practice

1. Run two CPU-bound loops, one under nice -n 0 and one under nice -n 5, and measure the CPU share each receives with top. Compare with the 1.25-per-level weight ratio.
2. Read /proc/<pid>/sched for a busy process and an idle one. Explain the difference in vruntime.
3. Interview-style: "How does CFS give an interactive process good response time without detecting that it is interactive?" Hint: ask what happens to vruntime while a task sleeps.

Windows and Solaris Scheduling

Theory

Comparing two other production schedulers shows how differently the same problem can be solved, and that all of them are variations on multilevel feedback with system-specific heuristics.

Windows uses a preemptive, priority-driven scheduler with 32 priority levels, split into two ranges:

• Levels 16-31: real-time. Fixed priorities, never adjusted by the system. Round robin within each level.
• Levels 1-15: variable (dynamic). These are adjusted at run time. Level 0 is reserved for the zero-page thread.

A thread's base priority comes from combining its process priority class (Idle, Below Normal, Normal, Above Normal, High, Realtime) with its relative thread priority (Lowest through Highest). What makes it work interactively is the set of priority boosts applied by the kernel:

Boost trigger	Effect
I/O completion	Boost by a device-specific amount (disk +1, keyboard +6, sound +8)
Waking from a wait on an event or semaphore	Small boost, decaying by one level per quantum
Foreground window's threads	Quantum tripled (not the priority)
Starvation detected by the balance set manager	Temporary boost to 15 with a doubled quantum, for a thread ready 300+ ticks

The boosts decay one level per quantum until the base priority is reached — a thread never drops below its base. The anti-starvation boost is an explicit patch for the priority scheduler's known failure mode.

Solaris organises threads into scheduling classes, each with its own policy and a dispatch table that is data, not code:

Class	Purpose
RT (real-time)	Highest, fixed priority
SYS (system)	Kernel threads, fixed priority, never time-sliced
TS (time sharing)	Default: MLFQ via dispatch table
IA (interactive)	Like TS, with a boost for the window with focus
FSS (fair share)	Share-based allocation between projects — the ancestor of cgroup fairness
FX (fixed priority)	Fixed, application-controlled

The TS/IA dispatch table encodes the MLFQ rules as tunable data: for each of 60 priority levels it lists the quantum, the new priority if the quantum is used up (lower), and the new priority if the thread returns from sleep (higher). Changing scheduling behaviour is editing a table rather than modifying the kernel — an unusually clean expression of the policy/mechanism separation from 4.1.

The common thread across Linux, Windows, and Solaris: all three are variations on multilevel feedback, all favour I/O-bound work, all include an explicit anti-starvation mechanism, and all separate real-time from normal classes.

Example

   WINDOWS: 32 priority levels

   31 +---------------------------+
      |  REAL-TIME (16-31)        |  fixed; never boosted or decayed
   16 +---------------------------+
   15 |  VARIABLE (1-15)          |  boosted on I/O completion and wakeup,
      |                           |  decaying one level per quantum
      |    base priority  ------  |  <- never falls below this
    1 +---------------------------+
    0 |  zero-page thread         |

   Boost and decay of an interactive thread (base 8)

   priority
     14 |        *                       disk I/O completes: +1
     13 |          *                     keyboard input: +6
     12 |            *
     ...|              *   *
      8 |------------------- * * * * *   returns to base, never below
        +--------------------------------> time (one decay per quantum)

   SOLARIS: the TS dispatch table (data, not code)

   priority | quantum | pri if quantum used up | pri after sleep
   ---------+---------+------------------------+-----------------
      0     |  200ms  |          0             |       50
      5     |  200ms  |          0             |       50
     10     |  160ms  |          0             |       51
     ...    |         |                        |
     50     |   40ms  |         40             |       58
     59     |   20ms  |         49             |       59
              ^         ^                        ^
     high priority =   using it all demotes;   sleeping promotes:
     SHORT quantum     CPU-bound sinks         interactive rises

   The three production schedulers side by side

                   | Linux (CFS/EEVDF) | Windows           | Solaris
   ----------------+-------------------+-------------------+------------------
   Core idea       | virtual-time      | 32 priority       | classes with
                   | fairness          | levels + boosts   | dispatch tables
   Interactivity   | emerges from      | explicit boosts   | table promotes
                   | vruntime          | per device type   | on sleep
   Anti-starvation | fairness is       | balance set       | table + FSS
                   | inherent          | manager boost     |
   Real-time       | SCHED_FIFO/RR/    | levels 16-31      | RT class
                   | DEADLINE          |                   |
   Group fairness  | cgroups           | job objects       | FSS class
   Tuning          | sysctl knobs      | registry/API      | edit the table

# Linux
chrt -p $$ ; nice -n 5 ./job ; cat /proc/sys/kernel/sched_latency_ns

# Windows (PowerShell)
# Get-Process chrome | Select-Object Name, PriorityClass
# (Get-Process notepad).PriorityClass = "AboveNormal"

# Solaris / illumos
# priocntl -l                    # list scheduling classes and priority ranges
# dispadmin -c TS -g             # dump the time-sharing dispatch table
# priocntl -s -c FSS -p 20 -i pid

Key takeaways

• Windows uses 32 levels split into fixed real-time (16-31) and dynamically boosted variable priorities (1-15).
• Windows boosts on I/O completion and wakeup, decaying one level per quantum but never below the base priority.
• Solaris expresses its multilevel feedback policy as an editable dispatch table, cleanly separating policy from mechanism.
• All three production schedulers are multilevel-feedback variants that favour I/O-bound work, guard against starvation, and isolate real-time classes.

🧪 Practice

1. Build the comparison table yourself for Linux, Windows, and Solaris across: default policy, interactivity mechanism, anti-starvation, and real-time support.
2. Explain why Windows boosts keyboard I/O completion (+6) far more than disk I/O completion (+1).
3. Interview-style: "What advantage does Solaris get from putting its scheduling policy in a table rather than in code?" Hint: recall the policy/mechanism separation, and ask who can change behaviour without a recompile.

---

<a id="5-synchronization"></a>