--- title: 'Scheduling Algorithms' source: 'https://academia.sh/en/courses/operating-system-concepts/scheduling-algorithms' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:22+00:00' license: 'CC BY-SA 4.0' --- # Scheduling Algorithms Four schedulers, the same workload: non-preemptive FIFO gives 194, round-robin 197, priority 195, fair-share 192 time units; when the quantum drops from 4 to 1, duration rises to 206 and context switches to 36; the ranking changes under the second workload, and no policy is found to be best under both. 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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.**