Scheduling Algorithms

The previous four lessons measured how execution units are set up: how many address spaces, how many copied pages, how many affected units. Once setup is done, one question remains, asked again at every time unit — which of the ready units will run.

The component that makes this decision is the scheduler, and how the decision is made is a measurable difference. This lesson runs the same five-process workload under four separate policies, then repeats the same comparison on a second workload. The lesson’s result is not the selection of a single policy; it is showing that no policy is best under every workload.

• PT31. The scheduler chooses one of the ready units at every time unit. A unit that is not ready is in a wait step and cannot be chosen.
• PT32. Non-preemptive FIFO does not release a process until it either finishes or enters a wait step; among the ready ones it chooses whichever became ready earliest.
• PT33. The round-robin policy is preemptive: a process runs for at most 4 time units, then gives up the core. This duration is called a time slice, or quantum for short.
• PT34. The priority policy chooses the ready process with the highest priority; priorities are part of the workload, and they differ under the second workload.
• PT35. The fair-share policy chooses the ready process that has used the least core so far.
• PT36. The quantities measured: duration (time units until all work finishes), context switch count, idle core steps, average turnaround (arrival to finish), and average wait (time units ready but unable to run).
• PT37. The second workload’s seed is 20260219. It gives the same five-process structure but a different mix of steps and different priorities.
• PT38. The resolution is 2 time units. A 1-unit difference between two policies counts as unmeasured and does not enter the ranking.

Two Workloads

The two seeds produce the same structure but give a different mix. The difference lies in the split between compute steps and wait steps, and this is exactly what determines the schedulers’ behavior.

# This machine is a SIMULATOR. No real scheduler is called; all
# durations are time units in the model.
SEED = 20260218
SECOND_SEED = 20260219
PROCESS_COUNT = 5
STEP_COUNT = 12
WAIT_DURATION = 30
CONTEXT_COST = 2
VIRTUAL_PAGE = 16


def generator(seed):
    """Deterministic pseudo-random generator. The same seed gives the same sequence."""
    d = seed

    def advance(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return advance


def workload(seed=SEED):
    """A step is either ("COMPUTE", virtual_page) or ("WAIT", duration)."""
    r = generator(seed)
    jobs = []
    for i in range(PROCESS_COUNT):
        steps = []
        for _ in range(STEP_COUNT):
            if r(10) < 3:
                steps.append(("WAIT", WAIT_DURATION))
            else:
                base = (i * 3) % VIRTUAL_PAGE
                steps.append(("COMPUTE", (base + r(4)) % VIRTUAL_PAGE))
        jobs.append({"name": f"P{i+1}", "step": steps,
                      "priority": 1 + r(3), "arrival": i * 4})
    return jobs


JOBS = workload()
print("workload  compute steps  wait steps  priorities")
for seed in (SEED, SECOND_SEED):
    y = workload(seed)
    h = sum(1 for i in y for t, _ in i["step"] if t == "COMPUTE")
    print(f"{seed}  {h:10d}  {PROCESS_COUNT * STEP_COUNT - h:13d}"
          f"  {[i['priority'] for i in y]}")

workload  compute steps  wait steps  priorities
20260218          39             21  [3, 2, 1, 3, 2]
20260219          46             14  [1, 2, 3, 1, 1]

The second workload is more compute-heavy: 46 of the 60 steps hold the core, versus 39 in the first. This is a harder job for the scheduler, because more processes are now contending for the core. Priorities have also changed, and only a single process now has priority 3.

Four Policies, the Same Workload

The implementation below gathers all four policies into a single body. The only difference between them is two lines: which one is chosen from the ready set, and whether a process’s quantum being used up is checked at all.

# On top of the first block: JOBS and CONTEXT_COST come from there.
INFINITY = 10**9


def schedule(jobs, policy="fifo", quantum=4, cores=1,
             context_cost=CONTEXT_COST):
    """policy: fifo (non-preemptive) | round-robin | priority | fair
    Every core runs at most one step per time unit."""
    state = [{"name": i["name"], "step": list(i["step"]), "position": 0, "arrival": i["arrival"],
              "ready": i["arrival"], "usage": 0, "finish": None,
              "priority": i["priority"]} for i in jobs]
    share_limit = INFINITY if policy == "fifo" else quantum
    cores_ = [{"job": None, "previous": None, "share": 0, "block": 0}
              for _ in range(cores)]
    t, context_switches, idle_steps = 0, 0, 0

    def not_done(d):
        return d["position"] < len(d["step"])

    while any(not_done(d) for d in state) or any(d["finish"] is None or d["finish"] > t
                                               for d in state):
        for c in cores_:                       # release
            d = c["job"]
            if d is not None and (not not_done(d) or d["ready"] > t or c["share"] >= share_limit):
                c["job"] = None
        for c in cores_:                       # assignment
            if c["block"] or c["job"] is not None:
                continue
            held = [x["job"] for x in cores_ if x["job"] is not None]
            ready = [d for d in state if not_done(d) and d["ready"] <= t and d not in held]
            if not ready:
                continue
            if policy == "priority":
                chosen = min(ready, key=lambda d: (-d["priority"], d["ready"], d["name"]))
            elif policy == "fair":
                chosen = min(ready, key=lambda d: (d["usage"], d["ready"], d["name"]))
            else:
                chosen = min(ready, key=lambda d: (d["ready"], d["name"]))
            if c["previous"] is not None and c["previous"] is not chosen:
                context_switches += 1
                c["block"] = context_cost
            c["job"] = chosen
            c["previous"] = chosen
            c["share"] = 0
        for c in cores_:                       # execution
            if c["block"]:
                c["block"] -= 1
                continue
            d = c["job"]
            if d is None:
                idle_steps += 1
                continue
            kind, value = d["step"][d["position"]]
            if kind == "WAIT":
                d["position"] += 1
                d["ready"] = t + value
                c["job"] = None
                idle_steps += 1
                if not not_done(d):                  # if the last step is a wait, the job finishes then
                    d["finish"] = t + value
            else:
                d["position"] += 1
                d["usage"] += 1
                d["ready"] = t + 1
                c["share"] += 1
                if not not_done(d):
                    d["finish"] = t + 1
                    c["job"] = None
        t += 1
    for d, i in zip(state, jobs):
        wt = sum(v for kind, v in i["step"] if kind == "WAIT")
        d["wait"] = d["finish"] - d["arrival"] - d["usage"] - wt
    return {"duration": t, "context_switches": context_switches, "idle_core_steps": idle_steps,
            "total_work": sum(d["usage"] for d in state),
            "avg_turnaround": round(sum(d["finish"] - d["arrival"] for d in state) / len(state), 2),
            "avg_wait": round(sum(d["wait"] for d in state) / len(state), 2),
            "finish": {d["name"]: d["finish"] for d in state}}


POLICIES = ("fifo", "round-robin", "priority", "fair")
print("scheduler      duration  switches  idle.core  avg.turnaround  avg.wait")
for y in POLICIES:
    s = schedule(JOBS, y)
    print(f"  {y:12s} {s['duration']:4d}  {s['context_switches']:5d}  {s['idle_core_steps']:6d}"
          f"  {s['avg_turnaround']:13.2f}  {s['avg_wait']:10.2f}")
print()
print("quantum sweep (round-robin)")
print("quantum  duration  switches  avg.wait")
for d in (1, 2, 4, 8, 16):
    s = schedule(JOBS, "round-robin", quantum=d)
    print(f"{d:5d}  {s['duration']:4d}  {s['context_switches']:5d}  {s['avg_wait']:11.2f}")

scheduler      duration  switches  idle.core  avg.turnaround  avg.wait
  fifo          194     22     111         148.40       14.60
  round-robin   197     25     108         153.80       20.00
  priority      195     21     114         149.00       15.20
  fair          192     25     103         153.00       19.20

quantum sweep (round-robin)
quantum  duration  switches  avg.wait
    1   206     36        33.00
    2   202     29        26.60
    4   197     25        20.00
    8   194     22        14.60
   16   194     22        14.60

The four policies’ durations lie between 192 and 197; the largest gap between them is 5 time units, that is, 2.6 percent of the total duration. This is an important reading: scheduler choice is not a major lever in this workload. The actual determining factor is the workload’s own wait steps, which take 630 time units.

The preemptive policy takes 3 time units longer than non-preemptive FIFO and makes 3 more context switches. Average wait rises from 14.60 to 20.00. What round-robin provides — no process holding the core for long — is paid for in duration.

It Gets Worse as the Quantum Shrinks

The sweep is the direct measure of this payment. As the quantum drops from 4 to 1, duration rises from 197 to 206, context switches from 25 to 36, average wait from 20.00 to 33.00. Giving up the core at nearly every step means spending more time on context switching than on the steps themselves: 36 switches take 72 time units, while the workload’s total compute steps come to 39.

At the other end the sweep stops. Quantum 8 and quantum 16 give exactly the same result: 194, 22, 14.60. The reason is clear — in this workload no process runs more than eight compute steps in a row, so above quantum 8 preemption is never triggered at all. This workload’s resolution runs out at quantum 8; a comparison at larger quanta gives no new information. The 194 and 22 at quantum 8 are exactly the non-preemptive FIFO numbers, and that is exactly how it should be: a round-robin policy in which preemption is never triggered is the non-preemptive policy.

What Total Duration Hides

Looking at total duration alone, the four policies stand close to one another. Where the policies actually diverge is not the total but the distribution: the same 192-to-197 duration can be divided among the processes in very different ways.

# On top of the previous blocks: JOBS, schedule and POLICIES.
print("scheduler      P1   P2   P3   P4   P5   widest spread")
for y in POLICIES:
    s = schedule(JOBS, y)
    t = [s["finish"][i["name"]] - i["arrival"] for i in JOBS]
    print(f"  {y:12s} " + " ".join(f"{x:4d}" for x in t) + f" {max(t) - min(t):13d}")
print()
print("processes with priority 3:", [i["name"] for i in JOBS if i["priority"] == 3])
print("processes with priority 1:", [i["name"] for i in JOBS if i["priority"] == 1])
for y in ("fifo", "priority"):
    s = schedule(JOBS, y)
    high = [s["finish"][i["name"]] - i["arrival"] for i in JOBS if i["priority"] == 3]
    low = [s["finish"][i["name"]] - i["arrival"] for i in JOBS if i["priority"] == 1]
    print(f"{y:10s} high priority avg. {sum(high) / len(high):6.2f}"
          f" | low priority avg. {sum(low) / len(low):6.2f}")

scheduler      P1   P2   P3   P4   P5   widest spread
  fifo          103  112  176  173  178            75
  round-robin   111  120  175  185  178            74
  priority      103  112  187  169  174            84
  fair          127  115  170  180  173            65

processes with priority 3: ['P1', 'P4']
processes with priority 1: ['P3']
fifo       high priority avg. 138.00 | low priority avg. 176.00
priority   high priority avg. 136.00 | low priority avg. 187.00

The last column shows what the fair-share policy does: the gap between the fastest and slowest process’s turnaround times is 65 time units, the narrowest of the four policies. Under the priority policy the same gap is 84, the widest. The measure of fairness is not total duration but this gap, and the fair-share policy narrows it by 19 units.

What the priority policy gains for whom can also be counted. The two processes with priority 3 finish at an average of 138.00 time units under non-preemptive FIFO and at 136.00 under the priority policy: a gain of 2 time units, exactly at the edge of the resolution. The process with priority 1, meanwhile, slips from 176.00 to 187.00 — an 11-time-unit loss. Granting priority gains the favored processes a barely measurable amount while charging the unfavored one a measurable price.

Does the Ranking Hold Up Under a Second Workload

A ranking measured under a single workload is a fact that belongs to that workload. For a result to become a rule, it has to be tested under a second workload too.

# On top of the previous blocks: workload, schedule, POLICIES and SECOND_SEED.
RESULT = {y: [schedule(workload(s), y)["duration"] for s in (SEED, SECOND_SEED)]
         for y in POLICIES}
BEST = [min(RESULT[y][k] for y in POLICIES) for k in (0, 1)]
print("scheduler      20260218  gap  20260219  gap")
for y in POLICIES:
    a, b = RESULT[y]
    print(f"  {y:12s} {a:8d} {a - BEST[0]:5d} {b:9d} {b - BEST[1]:5d}")
print()
for k, seed in enumerate((SEED, SECOND_SEED)):
    best = [y for y in POLICIES if RESULT[y][k] == BEST[k]]
    worst = [y for y in POLICIES if RESULT[y][k] == max(RESULT[z][k] for z in POLICIES)]
    print(f"{seed}: best {best} | worst {worst}")
print("best under both workloads:",
      [y for y in POLICIES if RESULT[y][0] == BEST[0] and RESULT[y][1] == BEST[1]])
print("pairs below resolution (gap < 2):",
      [(y, z, k) for k in (0, 1) for i, y in enumerate(POLICIES)
       for z in POLICIES[i + 1:] if abs(RESULT[y][k] - RESULT[z][k]) < 2])

scheduler      20260218  gap  20260219  gap
  fifo              194     2       189     0
  round-robin       197     5       202    13
  priority          195     3       196     7
  fair              192     0       195     6

20260218: best ['fair'] | worst ['round-robin']
20260219: best ['fifo'] | worst ['round-robin']
best under both workloads: []
pairs below resolution (gap < 2): [('fifo', 'priority', 0), ('priority', 'fair', 1)]

Which Result Holds Up

The output’s last four lines bound every claim this lesson makes.

The result that holds up: round-robin’s fairness is paid for in duration. The round-robin policy is worst under both workloads — 5 time units behind the best under the first, 13 behind under the second. The gap triples under the second workload, because preemption is triggered more often in a compute-heavy workload. This result points the same way in both measurements and can be written down.

The result that does not hold up: fair-share’s superiority. The fair-share policy is best under the first workload and 6 time units behind the best under the second. The same policy is first under one workload and not the other; the statement “fair-share is best” is therefore an unmeasured claim and cannot be made.

The list of policies best under both workloads is empty. This is the lesson’s main result: a scheduler’s superiority is a property not of itself but of the workload’s composition. Non-preemptive FIFO comes out first under the compute-heavy second workload, because there the processes have few wait steps, and running them without splitting shortens the total.

The last line shows how resolution works in practice. In the first workload, the 1-unit gap between non-preemptive FIFO (194) and priority (195) is below resolution; in the second, so is the 1-unit gap between priority (196) and fair-share (195). These pairs cannot be separated; writing a ranking between them would present an unmeasured difference as a measured one.

Summary

• The scheduler decides which ready unit runs at every time unit; the four policies make this decision differently in terms of preemption and selection criterion.
• Under the same workload the four policies’ duration lies between 192 and 197; the largest gap is 5 time units, or 2.6 percent. Scheduler choice is not a major lever in this workload.
• It gets worse as the quantum shrinks: at quantum 1, duration is 206, context switches 36, average wait 33.00. Quantum 8 and 16 give the same result; this workload’s resolution runs out at quantum 8.
• The round-robin policy is worst under both workloads (197 and 202); its fairness is paid for in duration, and this result holds in both measurements.
• No policy is best under both workloads: fair-share is first under the first, non-preemptive FIFO is first under the second. Superiority is a property of the workload’s composition, not of the policy.
• 1-unit differences below resolution count as unmeasured; two pairs therefore stay unseparated, and no ranking is written between them.

Next Step

Throughout this topic, units were treated as separate from one another: each executing its own steps, the scheduler moving back and forth between them. One assumption was never tested — the assumption that splitting a unit’s step does not change the result. The course’s next topic breaks this assumption and proves a single sentence: when two units of the same program touch the same data, correct output does not mean a correct program.