--- title: 'Operating System Concepts' source: 'https://academia.sh/en/courses/operating-system-concepts' language: en updated: '2026-08-17T04:39:39+00:00' license: 'CC BY-SA 4.0' lessons: 15 outcomes: - 'Explains the distinction between process and thread through scheduling and context-switch cost' - 'Recognizes concurrency faults and counts the price of the mutual exclusion tools' - 'Measures the effect of virtual memory and file system abstractions on program behavior' --- # Operating System Concepts Measuring the steps charged by processes and threads, scheduling, concurrency faults, virtual memory, garbage collection and input/output models. ## Processes and Threads The process concept, forking, threads, the trade-off between isolation and sharing, and a comparison of scheduling algorithms. ### The Process Concept Source: https://academia.sh/en/courses/operating-system-concepts/process-concept A process as a running instance of a program, and the steps that sharing costs: a process running alone takes 99 time units, but when five processes share the same machine the result is 194 time units and 22 context switches; 44 of those 194 time units go to context switching, which is more than the 39 time units spent on the work itself. The Algorithms course closed by measuring a solution's cost by **its own step count**: comparison count, edges traversed, characters scanned. That measure carried a silent assumption — that the algorithm has the machine to itself. This assumption does not hold in production. The same algorithm runs on the same machine alongside other work, sharing the processor, memory, and disk with it. What this course measures is **sharing itself**. An abstraction's number is not the convenience it provides but **the steps it costs**; an abstraction whose cost is not counted counts as unmeasured. The first abstraction is the process, and the first cost is the steps a processor spends moving back and forth between multiple processes. - **PT1.** The machine is modeled within the lesson. The code below is a **simulator**: no real process is created, no kernel call is made, no real time is measured. - **PT2.** All durations are **time units**. They are not seconds, and are not converted to seconds. - **PT3.** The workload is **five processes**; each process has **twelve steps**. A step is either a **compute step** (takes one time unit, touches one virtual page) or a **wait step** (takes 30 time units, does not use the core). - **PT4.** The seed is **20260218**. The same seed gives the same workload; every number here is reproducible. - **PT5.** The machine has **a single core**. In every time unit, the core executes at most one step. - **PT6.** **The cost of a context switch is 2 time units.** During those two units, the core executes no process's step at all. - **PT7.** Address space, stack, and heap were established in the memory layout lesson of the How Computers Work course; they are **not redefined** here, only counted. - **PT8.** The measurement's **resolution is 2 time units**. A 1-unit difference between two setups **counts as unmeasured**. #### Process: A Running Program A program is a sequence of bytes sitting on disk; a **process** is a running instance of that program. The difference is that a process has something the program does not: **state**. A process's state covers the counter of the step it is on, the current content of its stack, the descriptors it holds open, and its own address space. This state has to be kept somewhere, because when the processor leaves one process for another and later returns, it must resume from **exactly** where it left off. The structure that holds this state is the **process table**: one entry per process, and in each entry the fields needed to resume the process. When two processes are run from the same program, what results is two separate states. Both execute the same instructions, but at different steps, with different data, and without touching each other's memory. This separation is **isolation**, and its cost will be counted in later lessons of this course. A **multitasking operating system** gives the impression that multiple processes are advancing at the same time, even on a single-core machine. The source of that impression is the core switching between processes often enough. From a process's point of view these switches are invisible: it is written as if it executed its own steps without interruption. Measurement breaks this impression, because every switch takes up room on the core and adds to the total duration. #### The Modeled Workload The first block builds the workload. A process is represented as a list of steps; compute steps hold the core, wait steps do not. ```python # This machine is a SIMULATOR. There is no real process, kernel call, or # time measurement; all durations are time units in the model. SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_DURATION = 30 # how many time units an I/O step takes CONTEXT_COST = 2 # the cost of one context switch (time units) 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("process arrival priority compute wait time alone") for i in JOBS: h = sum(1 for t, _ in i["step"] if t == "COMPUTE") b = STEP_COUNT - h print(f" {i['name']:4s} {i['arrival']:5d} {i['priority']:8d} {h:6d} {b:8d}" f" {h + b * WAIT_DURATION:15d}") print("total compute steps:", sum(1 for i in JOBS for t, _ in i["step"] if t == "COMPUTE")) ``` ``` process arrival priority compute wait time alone P1 0 3 9 3 99 P2 4 2 9 3 99 P3 8 1 7 5 157 P4 12 3 7 5 157 P5 16 2 7 5 157 total compute steps: 39 ``` The last column is the **baseline**: how long a process would take if it were alone on the machine. For P1 this is $9 + 3 \times 30 = 99$ time units. The number is the sum of the process's own steps and depends on nothing else. This is exactly the measure used in the Algorithms course. #### Sharing Itself Is Work When five processes use the same core, the core has to make a choice: which one runs. The component that makes this choice is the **scheduler**. The implementation below will be used in every scheduling measurement in this course; here it runs only in **non-preemptive FIFO** mode, meaning a process does not give up the core until it either finishes or enters a wait step. ```python # On top of the first block: JOBS, CONTEXT_COST and STEP_COUNT 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}} ALONE = [schedule([dict(i, arrival=0)], "fifo") for i in JOBS] SHARED = schedule(JOBS, "fifo") print("baseline (five processes back to back, no sharing at all):", sum(s["duration"] for s in ALONE), "time units,", sum(s["context_switches"] for s in ALONE), "context switches") print("setup (five processes sharing the same machine) :", SHARED["duration"], "time units,", SHARED["context_switches"], "context switches") print() print("process alone shared difference") for i, s in zip(JOBS, ALONE): p = SHARED["finish"][i["name"]] - i["arrival"] print(f" {i['name']:4s} {s['duration']:10d} {p:11d} {p - s['duration']:5d}") print("average turnaround:", SHARED["avg_turnaround"], "| average wait:", SHARED["avg_wait"]) ``` ``` baseline (five processes back to back, no sharing at all): 669 time units, 0 context switches setup (five processes sharing the same machine) : 194 time units, 22 context switches process alone shared difference P1 99 103 4 P2 99 112 13 P3 157 176 19 P4 157 173 16 P5 157 178 21 average turnaround: 148.4 | average wait: 14.6 ``` Two numbers are true at the same time and point in opposite directions. **Total duration drops:** running the five processes back to back with no interleaving at all takes 669 time units, while the shared run finishes at 194. The gain comes from handing the core to another process while one is waiting. **Individual duration rises:** no process reaches its own baseline; the baseline of 157 for P5 rises to 178. The difference averages **14.60 time units per process**, and this is time a process spends on other processes' work, not its own. #### A Process's Three States The difference column above leaves a question: what is a process doing in those extra time units when it is not doing its own work. The answer is that a process is, at every moment, in one of three states. **Running** is the state where the process currently holds the core. **Blocked** is the state where the process is in a wait step and cannot run even if the core is idle. **Ready** is the state where the process is able to run but the core belongs to someone else. ```python # On top of the previous blocks: JOBS, SHARED and WAIT_DURATION come from there. print("process running blocked ready(queued) turnaround") total_ready = 0 for i in JOBS: running = sum(1 for t, _ in i["step"] if t == "COMPUTE") blocked = sum(v for t, v in i["step"] if t == "WAIT") turnaround = SHARED["finish"][i["name"]] - i["arrival"] ready = turnaround - running - blocked total_ready += ready print(f" {i['name']:4s} {running:10d} {blocked:12d} {ready:16d} {turnaround:11d}") print("average ready time:", round(total_ready / len(JOBS), 2)) ``` ``` process running blocked ready(queued) turnaround P1 9 90 4 103 P2 9 90 13 112 P3 7 150 19 176 P4 7 150 16 173 P5 7 150 21 178 average ready time: 14.6 ``` The first two columns belong to the baseline and are unaffected by sharing: both a process's compute step count and its wait duration are properties of its own program. The column sharing produces is the third one. Ready time is zero by definition for a process running alone; once five processes share, it rises to a value between 4 and 21, averaging **14.60 time units**. This is the **process-visible** form of the steps the process abstraction costs. The process itself sees neither the context switches nor the process table; the only thing it sees is its own execution pausing to wait now and then. P1's ready time is 4, P5's is 21; the difference comes from arrival order, and **arriving early means waiting less**. That this order is a choice, and that different choices produce different ready times, will be measured in this topic's lesson on scheduling. #### The Breakdown of the 194 Time Units To see where the cost lies, the total duration has to be broken into its components. The process table itself is also counted here; its definition belongs to the How Computers Work course, and the question here is how many fields it carries. ```python # On top of the first two blocks: JOBS, SHARED and CONTEXT_COST come from there. FIELD = ("name", "step", "position", "arrival", "ready", "usage", "finish", "priority", "wait") print("process table:", len(JOBS), "entries x", len(FIELD), "fields =", len(JOBS) * len(FIELD), "fields") print() work_steps = SHARED["total_work"] context_steps = SHARED["context_switches"] * CONTEXT_COST print("breakdown of the 194 time units") print(" compute steps :", work_steps) print(" context switches :", context_steps, f"({SHARED['context_switches']} x {CONTEXT_COST})") print(" idle core steps :", SHARED["idle_core_steps"]) print(" total :", work_steps + context_steps + SHARED["idle_core_steps"]) print(" context / compute ratio:", round(context_steps / work_steps, 4)) ``` ``` process table: 5 entries x 9 fields = 45 fields breakdown of the 194 time units compute steps : 39 context switches : 44 (22 x 2) idle core steps : 111 total : 194 context / compute ratio: 1.1282 ``` This lesson's most important line is the second to last. The five processes' **actual work is 39 time units**; the **context switching** spent to get that work done is **44 time units**. The steps the abstraction costs are **larger** than the steps it carries — the ratio is 1.1282. The remaining 111 units are idle core steps: while every process is in a wait step, the core has no work to do. This is not a flaw of the scheduler; the workload's 21 wait steps take 630 time units in total, and only a portion of that can be interleaved. The way to reduce idle steps is not a better scheduler but **more processes** — and every new process also increases the number of context switches. The process table's 45 fields are why context switching is not free: at every switch, one entry's fields are saved and another's are restored. This course's counter models those two operations as 2 time units. #### Summary - A process is a running instance of a program; what distinguishes it from the program is the state it carries, and that state is held in the process table. - In this workload, a process running alone takes exactly as long as its own steps: 99 time units for P1, 157 for P3. This is the baseline. - When five processes share the same machine, the total duration drops from 669 to **194 time units**, but no process's individual duration reaches its baseline; the average wait is **14.60 time units**. - The cost of sharing is **22 context switches**, taking 44 time units; this is **more** than the workload's actual work of 39 time units. - A process is at every moment running, blocked, or ready; the only new state sharing produces is **ready**, and in this workload it averages 14.60 time units. - The 194 time units break down exactly into 39 compute steps, 44 context-switch units, and 111 idle core steps; every abstraction's cost is visible in this breakdown. #### Next Step This lesson supplied five processes ready-made. On a real machine, processes do not spring from nothing: each is created by another process and inherits things from its creator at the moment of creation. The next lesson takes up forking and counts a single question: setting up a new process means **copying how many pages**. ### Process Forking Source: https://academia.sh/en/courses/operating-system-concepts/process-forking A new process derived from an existing one, and measuring what it inherits: four forks carry 64 virtual pages with eager copying, drop to 15 pages with copy-on-write, leaving 49 pages copied for nothing, and copy-on-write loses its advantage once the page fault cost rises to 4 time units. The previous lesson supplied five processes ready-made; they were sitting there when the machine started. On a real machine no process is born this way. Every process is created by another, already-running process, and it inherits things from its creator at the moment of creation. This derivation operation is called **forking**. The measurable form of the question is this: when a process is copied, how many virtual pages must be copied. The process abstraction's isolation guarantee demands its price exactly here, because two processes being unable to touch each other's memory is only guaranteed if there are two separate address spaces. - **PT9.** Forking derives a new process from an existing one. The one that forks is the **parent**, the one derived is the **child**; the relationship forms a tree. - **PT10.** In this lesson the tree is fixed: P1 forks to produce P2 and P3, P2 forks to produce P4 and P5. There are **four forks** in total. - **PT11.** A process's address space is **16 virtual pages** (the `VIRTUAL_PAGE` value from the shared definition). Copying one page takes **1 time unit**. - **PT12.** Marking a page read-only is flipping a bit, and in this model it takes **0 time units**. This is a choice, and the result is sensitive to it; the sensitivity is swept within the lesson. - **PT13.** The set of pages a child touches is read from the workload's compute steps. Every touch counts as a write; this is a **pessimistic upper bound** for copy-on-write. - **PT14.** Running child processes, pipelines, and job control were covered at a usage level in the Shell Programming course; they are **not repeated** here. This lesson only counts forking's inheritance and cost. - **PT15.** The measurement's resolution is **2 time units**. A difference below this counts as unmeasured, and is written as such. #### Forking's Three Separate Behaviors Forking looks like a single operation, but it treats a process's state in three separate ways, and these three must not be confused with one another. **Copying.** The address space belongs to the child. If the parent changes a page after the copy, the child does not see it; if the child changes one, the parent does not see it. This is the behavior that provides isolation, and it is also the **only one with a cost**. **Inheritance.** Some fields pass to the child by value: priority, working directory, resource limits. The child can change these afterward, and the change does not affect the parent, but the starting value comes from the parent. **Sharing.** Some structures remain a single object, and both processes see the same object. The read position an open **file descriptor** points to is like this: when the parent reads and advances, the child reads from where it left off. Sharing has zero cost, but it also has no isolation. The three must be kept separate, because the question to ask when hunting a bug is different for each. In a copied field, the parent's later change **never** reaches the child; in an inherited field, the child's starting value is the parent's, but everything after is independent; in a shared object, **every** operation by either process affects the other. When unexpected behavior appears after a fork, the first task is to determine which of these three sets the state in question falls into. The child is a process independent of its parent; even if the parent finishes first, the child keeps running. Its process table entry belongs to it and carries the nine fields from the previous lesson. Forking's cost is therefore two items: a process table entry and an address space. The entry is fixed and small; the address space is not fixed, and that is what this lesson measures. #### The Workload and the Fork Tree The first block rebuilds exactly the same workload as the previous lesson. The second block models forking and counts two copying methods. ```python # This machine is a SIMULATOR. There is no real process, kernel call, or # time measurement; all durations are time units in the model. SEED = 20260218 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("process arrival priority compute steps") for i in JOBS: h = sum(1 for t, _ in i["step"] if t == "COMPUTE") print(f" {i['name']:4s} {i['arrival']:5d} {i['priority']:8d} {h:12d}") ``` ``` process arrival priority compute steps P1 0 3 9 P2 4 2 9 P3 8 1 7 P4 12 3 7 P5 16 2 7 ``` #### What It Copies, What It Inherits, What It Shares The `fork` function below produces the child's process table entry. The comments beside each field show which of the three behaviors is at work; the last line proves sharing through object identity. ```python # On top of the first block: JOBS, VIRTUAL_PAGE and STEP_COUNT come from there. COPY_COST = 1 # how many time units it takes to copy one virtual page DESCRIPTOR = [0, 1, 2] # the descriptor list each process holds at startup TREE = [("P2", "P1"), ("P3", "P1"), ("P4", "P2"), ("P5", "P2")] TABLE = {i["name"]: dict(i, descriptor=list(DESCRIPTOR)) for i in JOBS} TOUCHED = {i["name"]: sorted({v for t, v in i["step"] if t == "COMPUTE"}) for i in JOBS} def fork(name, parent_name, method="eager"): """Produces the child's process table entry and counts the pages copied.""" p = TABLE[parent_name] child = {"name": name, # new: the child's own identity "arrival": TABLE[name]["arrival"], # new "step": list(TABLE[name]["step"]), # the child's steps after forking "priority": p["priority"], # inheritance: comes from the parent "descriptor": p["descriptor"]} # sharing: the same list object page = VIRTUAL_PAGE if method == "eager" else len(TOUCHED[name]) return child, page for method in ("eager", "cow"): page = sum(fork(name, pa, method)[1] for name, pa in TREE) print(f"{method:9s} copying: {len(TREE)} forks, {page:2d} pages," f" {page * COPY_COST:2d} time units") print() print("child touched pages count eager cow copied for nothing") for name, pa in TREE: d = len(TOUCHED[name]) print(f" {name:4s} {str(TOUCHED[name]):20s} {d:4d} {VIRTUAL_PAGE:8d} {d:9d}" f" {VIRTUAL_PAGE - d:16d}") print("total pages copied for nothing:", sum(VIRTUAL_PAGE - len(TOUCHED[name]) for name, _ in TREE)) print() c, _ = fork("P2", "P1") print("inheritance: priority", TABLE["P1"]["priority"], "->", c["priority"]) print("sharing : is the descriptor list the same object:", c["descriptor"] is TABLE["P1"]["descriptor"]) print("renewed : name", c["name"], "| arrival", c["arrival"]) ``` ``` eager copying: 4 forks, 64 pages, 64 time units cow copying: 4 forks, 15 pages, 15 time units child touched pages count eager cow copied for nothing P2 [3, 4, 5, 6] 4 16 4 12 P3 [6, 7, 8, 9] 4 16 4 12 P4 [9, 11, 12] 3 16 3 13 P5 [12, 13, 14, 15] 4 16 4 12 total pages copied for nothing: 49 inheritance: priority 3 -> 3 sharing : is the descriptor list the same object: True renewed : name P2 | arrival 4 ``` **Eager copying** produces the entire address space at the moment of forking: for four forks, $4 \times 16 = 64$ pages. **Copy-on-write** copies no page at the moment of forking; it marks every page read-only and produces only that page the first time a write to it is attempted. In this workload the four children touch 15 distinct pages in total, so the pages copied drop from 64 to 15. The remaining 49 pages are pages **copied for nothing**: the eager method produces them, and the child touches none of them. The ratio is clear on a per-process basis — P4 touches only 3 of its address space's 16 pages, and the remaining 13 are copied and discarded unread. #### Inheritance Works Along the Chain Because forking builds a tree, inheritance does not stop at a single step. P4 is derived from P2, and P2 is derived from P1; so P4's starting priority traces all the way back to P1. Once the whole tree is built, what this does can be counted. ```python # On top of the previous blocks: JOBS, TREE, TABLE and fork. PARENT = dict(TREE) def build_tree(method="eager"): """Forks the whole tree starting from root P1; priority is inherited along the chain.""" built, page = {"P1": dict(TABLE["P1"])}, 0 for name, pa in TREE: c, p = fork(name, pa, method) c["priority"] = built[pa]["priority"] # inheritance chain built[name] = c page += p return built, page BUILT, PAGES = build_tree() DEPTH = {"P1": 0} print("process parent depth own priority inherited priority") for i in JOBS: name = i["name"] if name in PARENT: DEPTH[name] = DEPTH[PARENT[name]] + 1 print(f" {name:4s} {PARENT.get(name, '-'):>8s} {DEPTH[name]:9d}" f" {TABLE[name]['priority']:15d} {BUILT[name]['priority']:18d}") print("tree depth:", max(DEPTH.values()), "| leaves:", sum(1 for a in DEPTH if a not in PARENT.values())) print("distinct values in own priorities:", len({TABLE[a]["priority"] for a in DEPTH}), "| in inherited:", len({BUILT[a]["priority"] for a in DEPTH})) ``` ``` process parent depth own priority inherited priority P1 - 0 3 3 P2 P1 1 2 3 P3 P1 1 1 3 P4 P2 2 3 3 P5 P2 2 2 3 tree depth: 2 | leaves: 3 distinct values in own priorities: 3 | in inherited: 1 ``` The last line is inheritance's silent consequence. The workload's own priority values carry three separate levels; once the tree is built by forking, all of them collapse to the root's value, 3, and the number of distinct levels drops to 1. For a scheduler that looks at priority, this means every process becomes indistinguishable. Inheritance's cost is zero in pages but not in information. A child has to explicitly set its own priority afterward; if it does not, it runs with its parent's. The tree's depth in this setup is 2, and its leaf count is 3. Depth matters because it gives the length of the inheritance chain: a child at depth $d$ can have starting values that came from $d$ steps away, and the only way to see this is to walk the tree backward. #### Copying, Set Against the Work Itself Whether these numbers are large can only be judged by placing them next to the workload's actual work. The same five processes' total compute steps come to 39 time units. ```python # On top of the previous blocks: JOBS, TREE, TOUCHED, VIRTUAL_PAGE, COPY_COST. MARK_COST = 0 # marking a page read-only is flipping a bit COMPUTE = sum(1 for i in JOBS for t, _ in i["step"] if t == "COMPUTE") TOUCHED_PAGES = sum(len(TOUCHED[name]) for name, _ in TREE) EAGER_PAGES = len(TREE) * VIRTUAL_PAGE print("workload's total compute steps :", COMPUTE) print("eager copying / compute step ratio :", round(EAGER_PAGES / COMPUTE, 4)) print("cow copying / compute step ratio :", round(TOUCHED_PAGES / COMPUTE, 4)) print() print("page fault cost eager cow winner") for fault in range(7): h = EAGER_PAGES * COPY_COST y = EAGER_PAGES * MARK_COST + TOUCHED_PAGES * (fault + COPY_COST) if abs(h - y) < 2: winner = "unmeasurable" else: winner = "cow" if y < h else "eager" print(f"{fault:19d} {h:8d} {y:9d} {winner}") ``` ``` workload's total compute steps : 39 eager copying / compute step ratio : 1.641 cow copying / compute step ratio : 0.3846 page fault cost eager cow winner 0 64 15 cow 1 64 30 cow 2 64 45 cow 3 64 60 cow 4 64 75 eager 5 64 90 eager 6 64 105 eager ``` The first ratio is this lesson's harshest number: eager forking is **1.641 times more expensive** than all of the five processes' compute work. The cost of setting up new processes is larger than the work those processes will do. Under copy-on-write the ratio drops to 0.3846, meaning copying takes less than a third of the work. This ratio depends on the workload and must be stated as such: if each process had a hundred and two steps instead of twelve, the denominator would grow and the ratio would fall. What is measured is not forking's absolute expense but that, **in short-lived processes**, setup cost exceeds the work. #### When Copy-on-Write Loses Copy-on-write is not free; while it defers copying, it adds two new items. The first is marking all 64 pages read-only at the moment of forking. The second is that every deferred copy starts with a **page fault**: the write attempt is trapped, control passes to the kernel, the page is produced, and the instruction re-executes. Page faults are measured on their own terms in this course's memory and storage topic; here they are only a cost parameter. The sweep shows that the advantage is not absolute. Up to a page fault cost of 3 time units, copy-on-write is ahead; **at 4 time units eager copying takes the lead**, and the gap continues to widen. The result is this lesson's counterpart to the course's second claim: **an abstraction sometimes makes things worse.** Copy-on-write winning depends on both the child touching few pages **and** trapping being cheap; if either one breaks down, the gain disappears. Row 3 of the table also shows how the resolution should be read. There, eager gives 64 and cow gives 60; the 4-time-unit gap between them is above the resolution (2 time units) and counts. Had the gap been 1, the row would be written as unmeasurable, because in this model a 1-time-unit advantage expresses a rounding, not a result. Two extreme cases sharpen this dependency. If the child loads its own program right after forking and replaces its address space entirely, all 64 of the pages the eager method copied go to waste. Conversely, if the child writes to all 16 pages, copy-on-write still copies 64 pages and additionally costs 64 page faults on top — 128 time units instead of 64 in this workload. #### Summary - Forking derives a new process from an existing one and splits process state into three: copied address space, inherited values, shared objects. - The only behavior with a cost is copying; inheritance is a value assignment and sharing is pointing to the same object, and both cost zero pages. - In this tree, four forks carry 64 virtual pages under the eager method and 15 under copy-on-write; the 49-page difference is copied for nothing. - Eager forking is 1.641 times the five processes' total compute work; setting up a process can be more expensive than the work the processes will do. - Inheritance chains along the tree: in this tree the five processes' three distinct priority levels collapse to a single level after inheritance, becoming indistinguishable to a scheduler that looks at priority. - Once the page fault cost rises to 4 time units, copy-on-write loses its advantage; deferred copying is not cheaper under every condition. #### Next Step Forking's cost is the cost of isolation: pages are multiplied so that two processes cannot touch each other's memory. If isolation is given up, this cost disappears too. The next lesson takes up execution units that share the same address space but keep their own stacks, and compares two numbers: the difference in copied pages and context switches between doing the same work with processes versus with threads. ### Threads Source: https://academia.sh/en/courses/operating-system-concepts/threads Shared address space and independent stacks: the same five-unit job, when set up with processes, needs 15 extra virtual pages even with copy-on-write, but drops to 4 stack pages with threads; duration falls from 194 to 186 time units and the context switch count stays unchanged at 22; the gain is 4.12 percent in time and 73.33 percent in memory. The previous lesson measured that forking's cost is the cost of isolation: pages were multiplied so that two processes could not touch each other's memory. This opens a natural question. If parts of the same program **want** to touch each other's memory, what is copying for. The answer to this question is the **thread**: an execution unit that shares the address space but keeps its own stack. This lesson runs the same workload from the previous two lessons under two setups and places two numbers side by side — copied pages, and the time units context switching costs. - **PT16.** A thread is an execution unit inside a process. It **shares** its address space with the process's other threads and keeps its own **stack** separate. - **PT17.** Every new thread requests **1 virtual page** for its stack. This is a choice; if the page count grows, the thread's extra cost grows with it. - **PT18.** A **process** context switch also changes the address space, and takes **2 time units** (the `CONTEXT_COST` value from the shared definition). - **PT19.** In a **thread** context switch the address space stays the same; in this model its cost is **1 time unit**. The result is sensitive to this choice, and the sensitivity is swept within the lesson. - **PT20.** The workload, seed, and scheduler are **the same** as in the previous two lessons. The only thing that changes is how the units are set up; the work is the same work. - **PT21.** The **correctness** consequences of a shared address space are not measured in this lesson. Race conditions and mutual exclusion are the concern of the course's concurrency topic. - **PT22.** The measurement's resolution is **2 time units**. #### The Same Work, Two Setups Five execution units will do the same work. In the process setup, each unit runs in its own address space and pays the forking cost from the previous lesson. In the thread setup, the five units run in a **single address space**; there is no page to copy, but each unit requests its own stack. ```python # This machine is a SIMULATOR. No real thread, lock, or concurrency library # is called; all durations are time units in the model. SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_DURATION = 30 CONTEXT_COST = 2 # process context switch: the address space changes too THREAD_CONTEXT_COST = 1 # thread context switch: the address space stays the same VIRTUAL_PAGE = 16 STACK_PAGE = 1 # every thread needs one virtual page for its own stack 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() TOUCHED = {i["name"]: {v for t, v in i["step"] if t == "COMPUTE"} for i in JOBS} NEW = [i["name"] for i in JOBS[1:]] # the four units besides the first PROCESS_EAGER = len(NEW) * VIRTUAL_PAGE PROCESS_COW = sum(len(TOUCHED[a]) for a in NEW) THREAD = len(NEW) * STACK_PAGE print("same work, three setups:", len(JOBS), "execution units,", len(set().union(*TOUCHED.values())), "distinct virtual pages") print() print("setup address space copied pages extra stack pages total extra pages") print(f" process (eager) {len(JOBS):11d} {PROCESS_EAGER:17d} {0:17d} {PROCESS_EAGER:16d}") print(f" process (cow) {len(JOBS):11d} {PROCESS_COW:17d} {0:17d} {PROCESS_COW:16d}") print(f" thread {1:11d} {0:17d} {THREAD:17d} {THREAD:16d}") ``` ``` same work, three setups: 5 execution units, 15 distinct virtual pages setup address space copied pages extra stack pages total extra pages process (eager) 5 64 0 64 process (cow) 5 15 0 15 thread 1 0 4 4 ``` The difference on the memory side is sharp. Five processes need 15 extra virtual pages even in the best case; five threads need 4, and these are not copies of the address space but stack pages. **No copy at all is made** to reach shared data: the 15-virtual-page shared area sits as a single copy, and all five units see that same copy. #### What It Keeps Separate, What It Shares Why a thread's context switch is cheaper can be seen by counting the state it carries. This course's first lesson counted that the process table carries nine fields. Not all nine of those fields belong to the execution unit itself: some describe the unit's own progress, and some describe the address space it sits in. ```python # On top of the first block: JOBS comes from there. PER_UNIT = ("name", "position", "ready", "usage", "finish", "wait") # unit-specific SHARED_FIELDS = ("step", "arrival", "priority") # address-space level n = len(JOBS) process_fields = n * (len(PER_UNIT) + len(SHARED_FIELDS)) thread_fields = n * len(PER_UNIT) + len(SHARED_FIELDS) print("unit-specific fields:", PER_UNIT) print("shared fields :", SHARED_FIELDS) print() print(f"process setup : {n} entries x {len(PER_UNIT) + len(SHARED_FIELDS)} fields = {process_fields} fields") print(f"thread setup : {n} x {len(PER_UNIT)} + {len(SHARED_FIELDS)} = {thread_fields} fields") print("field difference carried at a context switch:", process_fields - thread_fields, f"| {round(100 * (process_fields - thread_fields) / process_fields, 2)} percent reduction") ``` ``` unit-specific fields: ('name', 'position', 'ready', 'usage', 'finish', 'wait') shared fields : ('step', 'arrival', 'priority') process setup : 5 entries x 9 fields = 45 fields thread setup : 5 x 6 + 3 = 33 fields field difference carried at a context switch: 12 | 26.67 percent reduction ``` Six of the nine fields are unit-specific: its name, the step it is on, when it becomes ready to run, how much core it has used, when it finishes. Three are at the address-space level, and a single copy suffices. The process setup holds these three fields five times, the thread setup once; the total drops from 45 fields to 33, a **26.67 percent** reduction. This is the reason for the time difference in the next section. A context switch's cost is proportional to the size of the state saved and restored; in a thread switch, the address-space-level fields stay in place, **untouched**. #### Two Prices for a Context Switch The time side is not as sharp as the memory side, and this is the actual thing the lesson needs to measure. The scheduler makes the **same decisions** in both setups; since the workload does not change, which unit runs when does not change either. The only thing that changes is the price of a switch. ```python # On top of the first block: JOBS, CONTEXT_COST, THREAD_CONTEXT_COST, # PROCESS_COW and THREAD 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}} SETUPS = (("process", CONTEXT_COST, PROCESS_COW), ("thread", THREAD_CONTEXT_COST, THREAD), ("free baseline", 0, 0)) MEASURE = {name: schedule(JOBS, "fifo", context_cost=b) for name, b, _ in SETUPS} print("setup switch cost switches duration avg.turnaround extra pages") for name, b, page in SETUPS: s = MEASURE[name] print(f" {name:15s} {b:13d} {s['context_switches']:7d} {s['duration']:5d}" f" {s['avg_turnaround']:15.2f} {page:9d}") proc, thread = MEASURE["process"], MEASURE["thread"] print() print("from process to thread") print(" extra pages :", PROCESS_COW, "->", THREAD, f"| {round(100 * (PROCESS_COW - THREAD) / PROCESS_COW, 2)} percent reduction") print(" duration :", proc["duration"], "->", thread["duration"], f"| {round(100 * (proc['duration'] - thread['duration']) / proc['duration'], 2)} percent reduction") print(" switches :", proc["context_switches"], "->", thread["context_switches"], "| unchanged") print() print("context switch cost sensitivity") print("cost duration avg.wait") for b in range(5): s = schedule(JOBS, "fifo", context_cost=b) print(f"{b:5d} {s['duration']:5d} {s['avg_wait']:12.2f}") ``` ``` setup switch cost switches duration avg.turnaround extra pages process 2 22 194 148.40 15 thread 1 22 186 142.80 4 free baseline 0 22 178 137.20 0 from process to thread extra pages : 15 -> 4 | 73.33 percent reduction duration : 194 -> 186 | 4.12 percent reduction switches : 22 -> 22 | unchanged context switch cost sensitivity cost duration avg.wait 0 178 3.40 1 186 9.00 2 194 14.60 3 202 20.20 4 211 26.80 ``` The third row is the baseline: if context switching were free, this workload would finish in 178 time units. The 16 units between 194 and 178 are the steps sharing costs in the process setup, and it is exactly $22 \times 2$. The thread setup halves this item: 186, that is, the baseline plus $22 \times 1$. **The number of context switches does not change.** Both setups have 22 switches, because the workload decides when a switch happens, not the type of the unit. Threads do not reduce switches; **they make every switch cheaper**. #### Where the Gain Is, Where It Isn't The size of the gain differs sharply between the two sides. In memory, extra pages drop from 15 to 4, a **73.33 percent** reduction. In time, duration drops from 194 to 186, a **4.12 percent** reduction. Eight time units is above the resolution (2 units), so it is measured and real — but it is small next to the memory gain. **A thread's gain in this workload is not in time, it is in memory.** The time gain grows only as the context-switch rate rises; the sweep shows this — once the cost climbs to 4, the same workload takes 211 time units. The difference at setup time is larger than the difference during the run. By the previous lesson's cost measure — copying one virtual page costs 1 time unit — setting up four processes takes 64 time units with the eager method and 15 with copy-on-write; setting up four threads takes 4 stack pages, that is, 4 time units. In short-lived units, the item that determines total cost is not the run but the **setup**, and there the ratio is 15 to 4. The reason the gain stays small is the composition of the workload: 21 of the 60 steps are wait steps, and wait steps take 630 time units. The 44 units going to context switching stays small next to that magnitude. In a compute-heavy workload the ratio flips, and a thread's time gain becomes pronounced. #### The Other Side of Sharing There is an item that does not appear in the table, and it has to be written down for the lesson to be honest. In the process setup, the five units cannot see each other's memory; in the thread setup, all five see and can modify the **entire** 15-virtual-page shared area. The way to avoid copying runs through making the copy unnecessary — that is, through removing isolation. Separate stacks do not limit this visibility. Stack separation prevents two units from accidentally overwriting each other's local variables; it does not protect data in the shared area. The shared area is there precisely to be shared, and the thread setup's entire gain comes from it; the thing that needs protecting and the source of the gain are **the same 15 pages**. This is not an extra page cost; it is a **correctness** cost, and it cannot be measured in pages. The problem that arises when two units write to the same page at the same time is addressed on its own terms in this course's concurrency topic. This topic's next lesson counts the other end of the trade-off: how many units a single step that corrupts shared state affects. #### Summary - A thread is an execution unit that shares its address space with the process's other threads and keeps its own stack separate. - The same five-unit job needs 15 extra virtual pages when set up with processes, even with copy-on-write; 4 stack pages suffice with threads, a 73.33 percent reduction. - The number of context switches is 22 in both setups; the type of unit changes not the switch count but the switch's price. - Duration drops from 194 to 186 time units. The 8-unit difference is above the resolution and is measured; but it is 4.12 percent, small next to the memory gain. - The cost sweep shows the result depends on a choice: duration is 178 at a context cost of 0 and 211 at a cost of 4. - Sharing has a cost that cannot be measured in pages: five threads see the entire shared area, and isolation disappears. #### Next Step There are now two setups and two numbers in hand: threads want fewer pages and a bit less time, while processes give isolation. To make a choice, isolation needs a number of its own. The next lesson produces that number: it measures how many execution units a single step that corrupts shared state spreads to, and sets that against how many pages isolation costs. ### Choosing Between Processes and Threads Source: https://academia.sh/en/courses/operating-system-concepts/choosing-between-processes-and-threads Counting the trade-off between isolation and sharing: in a single address space, five threads form a single component through shared pages, and any corrupted page spreads to all five units; in a process setup the same corruption stays confined to one unit; the spread ratio is 5.0, and the cost of bringing it down to 1.0 is 15 copied pages. The previous lesson placed two setups side by side and measured that threads are cheap: 4 extra virtual pages instead of 15, 186 time units instead of 194. Choosing threads by looking only at these numbers would mean ignoring a column that is not in the table. What the process setup gave in return was **isolation**, and no choice can be made until isolation, too, has a number. This lesson produces that number. The question is: how many execution units does a single step that corrupts shared state affect. The answer differs between the two setups by a factor of five, and this is this topic's counterpart to the course's second claim — **an abstraction sometimes makes things worse**, because the cheapness of sharing also means corruption spreads cheaply. - **PT23.** Five execution units run the same workload used in the previous two lessons. Each unit touches specific virtual pages; the touch set is read from the workload's compute steps. - **PT24.** **Corruption** is a unit writing an incorrect value to a page. It is a single step, and it happens once over the course of the measurement. - **PT25.** **Direct impact** is the number of units that touch the corrupted page. - **PT26.** **Spread** is the number of units the corruption reaches through shared pages: a unit that reads the corrupted data also writes a corrupted value to its own pages. This is a modeling choice, and it is in the **pessimistic** direction. - **PT27.** Units in the same address space are considered linked through a shared page. Spread is the **connected component** of this graph. - **PT28.** There is **no edge** between units in separate address spaces. This is the definition of isolation: one process's write cannot reach another's page. - **PT29.** The component computation uses directly the traversal established in the Data Structures course's lesson on depth-first search; the procedure is **not retold** here. - **PT30.** Time is **not measured** in this lesson. The two quantities measured are **affected units** and **copied pages**. #### The Two Ends of the Trade-off At one end is **total sharing**: five units run in a single address space, no page is copied, every unit sees every page. At the other end is **total isolation**: five separate address spaces, four forks, copied pages, and units that cannot touch each other's memory. There is no continuous range between these two ends; **the number of address spaces is an integer**, and the choice is how many address spaces the units are divided among. The five units can be set up in one, two, three, or five spaces. Every division produces two numbers, and these two numbers move in opposite directions. The term trade-off is not used loosely here. Both quantities arise from the same cause: avoiding a copy also means avoiding the separation the copy provides. There is no way to have both in a single setup, and every number in this lesson is read within that constraint. #### The Shared Page Map The measurement requires knowing which unit touches which page. The workload already determines this; the first block produces the map. ```python # This machine is a SIMULATOR. No real process or thread is created; # all numbers are produced inside the model. SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_DURATION = 30 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() NAMES = [i["name"] for i in JOBS] TOUCHED = {i["name"]: {v for t, v in i["step"] if t == "COMPUTE"} for i in JOBS} print("unit virtual pages touched count") for a in NAMES: print(f" {a:4s} {str(sorted(TOUCHED[a])):22s} {len(TOUCHED[a]):4d}") print("distinct pages:", len(set().union(*TOUCHED.values()))) print() print("page units touching it") for s in range(VIRTUAL_PAGE): touching = [a for a in NAMES if s in TOUCHED[a]] if len(touching) >= 2: print(f"{s:5d} {' '.join(touching)}") ``` ``` unit virtual pages touched count P1 [0, 1, 2, 3] 4 P2 [3, 4, 5, 6] 4 P3 [6, 7, 8, 9] 4 P4 [9, 11, 12] 3 P5 [12, 13, 14, 15] 4 distinct pages: 15 page units touching it 3 P1 P2 6 P2 P3 9 P3 P4 12 P4 P5 ``` The map looks narrow: only four of the 15 pages are used by more than one unit, and none is used by more than two. Looking only at direct impact, sharing's risk seems small — two units in the worst case. #### How Far Corruption Spreads Direct impact is misleading, because corruption does not stop there. P1 and P2 share page 3, P2 and P3 share page 6, P3 and P4 share page 9, P4 and P5 share page 12. Four shared pages build a **chain** linking all five units end to end. ```python # On top of the first block: NAMES, TOUCHED and VIRTUAL_PAGE come from there. def component(group): """Units in the same address space are linked through shared pages. The set corruption spreads to is this graph's connected component.""" neighbor = {a: [b for b in group if b != a and TOUCHED[a] & TOUCHED[b]] for a in group} seen, comps = set(), [] for a in group: if a in seen: continue stack, cluster = [a], [] while stack: # depth-first search d = stack.pop() if d in seen: continue seen.add(d) cluster.append(d) stack.extend(neighbor[d]) comps.append(sorted(cluster)) return comps def setup(groups): """groups: each one a set of unit names sharing one address space.""" comps = [b for g in groups for b in component(g)] eager = (len(groups) - 1) * VIRTUAL_PAGE cow = sum(len(set().union(*(TOUCHED[a] for a in g))) for g in groups[1:]) return {"address_spaces": len(groups), "components": len(comps), "largest_component": max(len(b) for b in comps), "eager": eager, "cow": cow} PARTITIONS = [[NAMES], [NAMES[:3], NAMES[3:]], [NAMES[:2], NAMES[2:4], NAMES[4:]], [[a] for a in NAMES]] print("address spaces components largest component eager copy cow copy") for g in PARTITIONS: k = setup(g) print(f"{k['address_spaces']:11d} {k['components']:8d} {k['largest_component']:17d}" f" {k['eager']:14d} {k['cow']:15d}") print("component in a single address space:", component(NAMES)) ``` ``` address spaces components largest component eager copy cow copy 1 1 5 0 0 2 2 3 16 6 3 3 2 32 10 5 5 1 64 15 component in a single address space: [['P1', 'P2', 'P3', 'P4', 'P5']] ``` The last line is this lesson's core. In a single address space, the five units form a **single component**; even though no pair of units shares a page directly, all of them are linked through the chain. P1 and P5 have no page in common at all, but a value P1 corrupts reaches P3 through P2, P4 through P3, and from there P5. #### The Effect of a Single Step Counting the spread page by page makes the difference between direct impact and spread visible. ```python # On top of the previous blocks: NAMES, TOUCHED, VIRTUAL_PAGE and component. SPREAD = {a: b for b in component(NAMES) for a in b} print("corrupted page process model thread direct thread spread") totals = [0, 0, 0] for s in sorted(set().union(*TOUCHED.values())): touching = [a for a in NAMES if s in TOUCHED[a]] spread = len({b for a in touching for b in SPREAD[a]}) totals = [totals[0] + 1, totals[1] + len(touching), totals[2] + spread] print(f"{s:15d} {1:14d} {len(touching):15d} {spread:14d}") print("totals over 15 pages:", totals[0], "|", totals[1], "|", totals[2]) print("spread / process model ratio:", round(totals[2] / totals[0], 4)) ``` ``` corrupted page process model thread direct thread spread 0 1 1 5 1 1 1 5 2 1 1 5 3 1 2 5 4 1 1 5 5 1 1 5 6 1 2 5 7 1 1 5 8 1 1 5 9 1 2 5 11 1 1 5 12 1 2 5 13 1 1 5 14 1 1 5 15 1 1 5 totals over 15 pages: 15 | 19 | 75 spread / process model ratio: 5.0 ``` The last column is **5 no matter which page is corrupted**. Where the corruption starts does not matter; in a single address space, every path leads everywhere. In the process model the same column is a constant 1, because there is no edge. **The spread ratio is 5.0**, and this is exactly the unit count. Direct impact totals 19, spread totals 75. The 56-unit-page gap between them is exactly the risk that an analysis looking only at the narrow-looking map would **miss**. Reducing the number of shared pages does not close this gap; the **chain** has to be cut, and the only way to cut the chain is a separate address space. A crash is this table's extreme case. If a thread makes the address space unusable, the affected units are directly 5; there is no intermediate step. If a process does the same thing, it is 1, and the remaining four units keep running. What isolation buys is exactly this difference: the difference between four out of five units staying up and none of them staying up. #### Taking Isolation Partially The partition table's two columns move in opposite directions and form a curve. As the address space count rises from 1 to 5, the largest component drops from 5 to 1; copied pages rise from 0 to 15 (from 0 to 64 with the eager method). The intermediate points show this exchange does not have to be taken all at once: two address spaces bring the largest component down from 5 to 3 with 6 copied pages. The **first** 6 copied pages reduce spread by two units; the **last** 5 copied pages reduce it by only one. **Isolation's first unit is cheaper than its last.** This means the choice is not "all or nothing." A group of units that trust each other can share a single address space, and an untrusted group can be placed in a separate one. What decides where the partition falls is not the shared page map but **which corruption is acceptable**. #### Cutting the Chain Cheaply The partition table changes the address space count. There is a cheaper path: keep a single address space, and multiply only the **shared pages**. Since it is four pages that build the chain, is cutting them enough. ```python # On top of the previous blocks: NAMES, TOUCHED and VIRTUAL_PAGE. SHARED = [s for s in range(VIRTUAL_PAGE) if sum(1 for a in NAMES if s in TOUCHED[a]) >= 2] def cut_components(cut): """A cut page is copied per unit; it no longer forms an edge.""" remaining = {a: TOUCHED[a] - set(cut) for a in NAMES} neighbor = {a: [b for b in NAMES if b != a and remaining[a] & remaining[b]] for a in NAMES} seen, clusters = set(), [] for a in NAMES: if a in seen: continue stack, cluster = [a], [] while stack: d = stack.pop() if d in seen: continue seen.add(d) cluster.append(d) stack.extend(neighbor[d]) clusters.append(sorted(cluster)) return clusters print("shared pages:", SHARED) print() print("cut pages extra copies components largest component") for k in range(len(SHARED) + 1): b = cut_components(SHARED[:k]) print(f"{str(SHARED[:k]):14s} {k:9d} {len(b):8d} {max(len(x) for x in b):17d}") print() print("separate-address-space cost for the same result:", sum(len(TOUCHED[a]) for a in NAMES[1:]), "copied pages") ``` ``` shared pages: [3, 6, 9, 12] cut pages extra copies components largest component [] 0 1 5 [3] 1 2 4 [3, 6] 2 3 3 [3, 6, 9] 3 4 2 [3, 6, 9, 12] 4 5 1 separate-address-space cost for the same result: 15 copied pages ``` The number is striking: **4 copied pages** reach the same result that separate address spaces reached with 15. Every cut page shrinks the largest component by exactly one unit, and on the fourth cut the component count rises to 5. This cheapness has three conditions, and all three must be written down. First, the map must be **known in advance**; which page is shared can only be stated once the entire workload is known. Second, the cut is **not enforced by hardware**; if a unit mistakenly writes to an uncut page, the chain returns. Third, a cut page is **no longer shared** — in a design that communicates through shared data, cutting breaks the work. The separate address space's 15 pages buy exactly these three conditions: no map is needed, the rule is enforced by hardware, and it cannot be broken by mistake. Isolation's **11 extra pages** are a price paid to a mechanism, not to knowledge or care. #### The Selection Rule When three numbers are placed side by side, the rule writes itself. The **baseline** is a single unit in a single address space: 0 copied pages, 1 affected unit, no spread. The **setup** is five units running in one address space: still 0 copied pages, but 1 component and a spread of 5. The **cost** is the 15 copied pages paid to bring that spread down to 1 — 64 with the eager method. The decision looks at the nature of the work. If the units continuously share the same data, separate address spaces cut the sharing too, and the work becomes impossible; in that case threads are unavoidable, and protection has to be sought at another layer. If the units do independent work, 15 pages is a cheap price for bringing spread down to a fifth. The previous lesson's time gain of 8 time units is a small item next to this table; **choosing threads for their speed is the weakest reason measured here.** #### Summary - The choice between isolation and sharing is the question of how many address spaces the units are divided among, and it produces two numbers: copied pages and affected units. - In this workload only four of the 15 virtual pages are used by more than one unit; direct impact is 2 in the worst case. - Four shared pages chain the five units together: in a single address space the component count is 1, and spread is 5 no matter which page is corrupted. The spread ratio is 5.0. - In a process setup the same corruption stays confined to 1 unit; this is the difference isolation buys, at a cost of 15 copied pages (64 with the eager method). - Partial isolation works, and it is not linear: two address spaces bring the largest component from 5 to 3 with 6 pages, while the last 5 pages gain only 1 unit. - A thread's time gain of 8 time units is small next to this trade-off; the choice cannot be defended on speed. #### Next Step Up to here, the question was how the units are set up: how many address spaces, how many copied pages, how many affected units. Once setup is done, one question remains, and it has to be asked again at every time unit: which of the ready units will run. The next lesson takes up the scheduler that makes this decision, runs the same workload under four separate policies, and shows that none of them is best under every workload. ### Scheduling Algorithms Source: https://academia.sh/en/courses/operating-system-concepts/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 grows by a factor of `13/5 = 2.6` 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.** ## Concurrency Race conditions, mutual exclusion tools, deadlock and starvation, memory visibility on multiple cores, and a comparison of three concurrency models. ### Race Conditions Source: https://academia.sh/en/courses/operating-system-concepts/race-conditions All interleavings of the read-increment-write triplet, the number of interleavings that produce a wrong result, and how the scheduler's quantum makes the error invisible. The previous lesson measured the scheduler's cost in time: as the quantum shrank, context switching increased and the run took longer. There, the quantum was a **performance** setting. This lesson brings out a second face of the same setting — the quantum also determines **in which orders** the steps of two threads can interleave, and therefore whether the program **produces a correct result** at all. This is where the course must pay off its most valuable claim: **a correct output does not mean a correct program.** The measurement below shows this once, in numbers. The machine being measured is, again, the machine from the shared definition; no real thread is ever created, and no real time is measured. #### One Increment Is Three Steps Incrementing a shared counter is a single line in the source text. It is not a single step in execution: the value is **read**, **incremented** by one, and **written** back. The scheduler can switch to another thread between these three steps. **CC1.** A counter increment is three separate steps; execution can be split between them. **CC2.** There are two threads, each incrementing the counter once; the expected result is **2**. **CC3.** Reads and writes are instantaneous; two steps never coincide in the same time unit. Execution can always be described by an **interleaving** — a single ordering of the two step sequences. The shared definition's `counter_run` routine takes an interleaving and returns the counter value it produces. An interleaving is a sequence of 0s and 1s showing which thread advances at each step. ```python def counter_run(pattern: list[int]) -> int: """Two threads each do read-increment-write once. pattern: who advances at each step.""" counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter # read elif s == 1: local[who] = local[who] + 1 # increment else: counter = local[who] # write stage[who] = s + 1 return counter def interleavings(a: int, b: int) -> list[list[int]]: """All interleavings of two sequences of length a and b.""" if a == 0: return [[1] * b] if b == 0: return [[0] * a] left = [[0] + s for s in interleavings(a - 1, b)] right = [[1] + s for s in interleavings(a, b - 1)] return left + right for name, pattern in (("sequential", [0, 0, 0, 1, 1, 1]), ("fully interleaved", [0, 1, 0, 1, 0, 1]), ("partial", [0, 0, 1, 1, 1, 0])): print(f"{name:18s} {pattern} -> counter {counter_run(pattern)}") everything = interleavings(3, 3) correct = [d for d in everything if counter_run(d) == 2] wrong = len(everything) - len(correct) print() print(f"interleavings {len(everything)} | correct {len(correct)} | wrong {wrong} " f"| wrong ratio {wrong / len(everything):.4f}") print("correct ones:", correct) ``` ``` sequential [0, 0, 0, 1, 1, 1] -> counter 2 fully interleaved [0, 1, 0, 1, 0, 1] -> counter 1 partial [0, 0, 1, 1, 1, 0] -> counter 1 interleavings 20 | correct 2 | wrong 18 | wrong ratio 0.9000 correct ones: [[0, 0, 0, 1, 1, 1], [1, 1, 1, 0, 0, 0]] ``` Two three-step sequences have **20** interleavings. Only **2** of them produce the expected result; **18**, that is **ninety percent** of the execution orders, leave the counter at 1. The two interleavings that do produce the correct result are already saying the same thing: one thread finishes completely before the other begins. #### Where the Loss Happens It is enough to trace the interleaving `[0, 1, 0, 1, 0, 1]` step by step. The first thread reads the counter and sees **0**. The second thread also reads and sees **0** as well — the first thread's write has not happened yet. Both set their local copy to 1. The first writes, and the counter becomes 1; the second writes, and the counter becomes 1 again. The second write **overwrote** the first thread's result. This is called a **race condition**: the result depending on the order of the steps rather than on the work itself. The programmer does not choose the order of the steps; the scheduler does. This is why a race condition is a defect that cannot be seen by reading the source text — the source text has only **one** increment line, and that line is correct. The region where the counter breaks is called the **critical section**: the sequence of steps in which two threads must never both be present at the same time. Here, the critical section is three steps. #### Two Distinct Defects The situation above stacks two defects on top of each other, and the two must not be confused. A **data race** is two unordered accesses to the same memory location where at least one is a write. It is a structural property: it is detected by looking at the accesses, not at the result. A **race condition**, by contrast, is the result depending on step order; it is a correctness property. The counter example has both at once. But one does not require the other. If a container is locked on every access, there is no data race; yet if the sequence "check whether it is empty, and if not, take an element" consists of two separately locked operations, another thread can take the last element between the two, and the result still depends on order. The data race is gone; the race condition remains. The practical consequence of this distinction is: **protecting each access separately is not enough.** What needs protection is not the access but **the span over which an invariant could be violated** — the boundary of the critical section is drawn by the programmer, not by a tool. #### The Quantum Constrains Interleaving The scheduler from the previous lesson does not switch threads at every step; it holds a thread for the length of the **quantum** and releases it once the quantum is used up. So not all 20 interleavings are reachable. **CC4.** The scheduler switches only at quantum boundaries; there is no preemption within a quantum. **CC5.** What is measured is not a probability but whether an interleaving is **reachable**: that interleaving either can or cannot be produced by this scheduler. The shared definition's `quantum_interleavings` routine counts the interleavings producible with a given quantum. ```python def counter_run(pattern: list[int]) -> int: counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def quantum_interleavings(steps: int, quantum: int) -> list[list[int]]: """Interleavings reachable when the scheduler switches only every `quantum` steps.""" result = [] def walk(remaining_a, remaining_b, current, sequence): if not remaining_a and not remaining_b: result.append(list(sequence)) return for candidate in (0, 1): remaining = remaining_a if candidate == 0 else remaining_b if not remaining: continue n = min(quantum, remaining) if candidate != current else min(quantum, remaining) sequence.extend([candidate] * n) walk(remaining_a - n if candidate == 0 else remaining_a, remaining_b - n if candidate == 1 else remaining_b, candidate, sequence) del sequence[len(sequence) - n:] walk(steps, steps, None, []) distinct = [] for d in result: if d not in distinct: distinct.append(d) return distinct print("quantum reachable wrong wrong ratio") for quantum in (1, 2, 3, 4, 5): reachable = quantum_interleavings(3, quantum) wrong = sum(1 for d in reachable if counter_run(d) != 2) print(f" {quantum:3d} {len(reachable):9d} {wrong:5d} " f"{wrong / len(reachable):11.4f}") print() print("quantum 2 reachable:") for d in quantum_interleavings(3, 2): print(" ", d, "-> counter", counter_run(d)) print("quantum 3 reachable:") for d in quantum_interleavings(3, 3): print(" ", d, "-> counter", counter_run(d)) ``` ``` quantum reachable wrong wrong ratio 1 20 18 0.9000 2 6 4 0.6667 3 2 0 0.0000 4 2 0 0.0000 5 2 0 0.0000 quantum 2 reachable: [0, 0, 0, 1, 1, 1] -> counter 2 [0, 0, 1, 1, 0, 1] -> counter 1 [0, 0, 1, 1, 1, 0] -> counter 1 [1, 1, 0, 0, 0, 1] -> counter 1 [1, 1, 0, 0, 1, 0] -> counter 1 [1, 1, 1, 0, 0, 0] -> counter 2 quantum 3 reachable: [0, 0, 0, 1, 1, 1] -> counter 2 [1, 1, 1, 0, 0, 0] -> counter 2 ``` At quantum 1, the scheduler can switch at every step, and **all 20 interleavings** are reachable; the wrong ratio is **0.9000**. At quantum 2, the reachable interleavings drop to **6**, wrong is **4**, and the ratio is **0.6667**. At quantum 3, the reachable interleavings drop to **2**, and **none of them are wrong**. #### The Error Did Not Disappear, It Became Invisible The two interleavings that remain at quantum 3 are `[0, 0, 0, 1, 1, 1]` and `[1, 1, 1, 0, 0, 0]`. Both run one thread's three steps uninterrupted. Because the quantum is **greater than or equal to** the critical section, no switch can land in the middle of the critical section. How this result is read is the course's distinguishing point. The program **has not changed**: the counter is still unprotected, the increment is still three steps, the critical section is still open. The only thing that changed is **the scheduler's setting**. If run a thousand times at quantum 3, it would print 2 a thousand times; these runs produce **no evidence at all** that the program is correct — they only show that the error is unreachable at that setting. The setting is not a guarantee. Drop to quantum 2, and the wrong result **comes back immediately**: 4 of the 6 interleavings are broken. If the critical section grows from three steps to four, quantum 3 is no longer enough either. And once a second core — the subject of the next lesson — is added, the quantum's protection disappears entirely, because the two threads then genuinely advance at the same time. The rule that follows is this: **the existence of a concurrency error is tested not by output but by the set of reachable interleavings.** Output is a sample; the set is proof. #### Run Count Is Not Proof The quantum is not the only way to forbid a switch; making it **rare** produces the same result. A real critical section is a few steps, and a real quantum is thousands of steps; the probability of a switch landing on exactly those few steps is small. Small does not mean absent, but it **erases the observation**. **CC6.** The switch probability is per step and constant throughout the run; sampling changes not the reachable set but how often that set is visited. The measurement below counts this. At every step, the scheduler switches to the other thread with a certain probability; two thousand runs are performed and the wrong results are counted. The generator is the shared definition's generator, with the same seed; the result is deterministic. ```python SEED = 20260218 def generator(seed): """Deterministic pseudo-random generator. The same seed gives the same sequence.""" d = seed def next_val(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_val def counter_run(pattern: list[int]) -> int: counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def sample_run(r, per_ten_thousand: int) -> list[int]: """The scheduler switches to the other thread with probability `per_ten_thousand` at each step.""" remaining, who, pattern = {0: 3, 1: 3}, 0, [] while remaining[0] or remaining[1]: if not remaining[who] or (remaining[1 - who] and r(10000) < per_ten_thousand): who = 1 - who pattern.append(who) remaining[who] -= 1 return pattern print("switch probability runs wrong observed wrong ratio") for per_ten_thousand in (5000, 1000, 100, 10, 1): r = generator(SEED) wrong = sum(1 for _ in range(2000) if counter_run(sample_run(r, per_ten_thousand)) != 2) print(f" per 10000 {per_ten_thousand:6d} 2000 {wrong:6d} {wrong / 2000:21.4f}") ``` ``` switch probability runs wrong observed wrong ratio per 10000 5000 2000 1519 0.7595 per 10000 1000 2000 346 0.1730 per 10000 100 2000 40 0.0200 per 10000 10 2000 1 0.0005 per 10000 1 2000 0 0.0000 ``` The last row is the lesson's sentence: in two thousand of two thousand runs the counter comes out 2 — and the program is still wrong. The rows in between are just as instructive — at a probability of ten per ten thousand, only **1** wrong result is seen in two thousand runs. A test that happens to catch this single observation will, if run again, most likely come back clean, and the bug will be considered "fixed." The reachable interleaving set did not change across any of these five rows: **20 interleavings, 18 wrong**. What changed is only how often the sample visits that set. Increasing the run count is not a solution; seeing the error at its **expected value** at a probability of one per ten thousand requires hundreds of thousands of runs, and even that number produces no proof — only observation. #### Three Numbers | Metric | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | Execution order | single thread, **1** order | two threads, **20** interleavings | 19 extra orders | | Wrong result | **0** | **18** | 18 broken executions | | Wrong ratio | 0.0000 | 0.9000 | — | A fourth row shows what the quantum setting does: at quantum 3, reachable interleavings are **2**, wrong is **0**, ratio **0.0000**. This row enters the table not as a **fix** but as a measure of **visibility**. The error itself is still sitting in 18 interleavings; those interleavings cannot be reached with this setting. #### The Real Fix Is Exclusion, Not a Setting What eliminates a race condition cannot be how the scheduler happens to be set, because the scheduler is not under the program's control. What eliminates it is **mutual exclusion**: protecting the critical section so that it admits at most one thread at any given moment. The shared definition's `counter_run` routine carries this as an option: when `lock=True` is passed, the critical section is treated as indivisible, and the routine returns **2** regardless of the interleaving. All twenty of the twenty interleavings become correct. What is gained is not narrowing the reachable set but **making every interleaving in that set correct**. This has a cost, and that cost is the next lesson's measurement: once the critical section is serialized, threads wait for one another, waiting steps accumulate, and processor utilization drops. #### Summary - Incrementing a shared counter is three steps — read, increment, write; execution can be split between them, and when it is, one write overwrites the other. - Two threads' three-step sequences have **20** interleavings; **18** produce a wrong result, a wrong ratio of **0.9000**. - The scheduler's quantum narrows the reachable interleaving set: 20 interleavings are reachable at quantum 1, 6 at quantum 2, and 2 at quantum 3. - When the quantum is greater than or equal to the critical section, **none** of the reachable interleavings are wrong; the program has not changed, only the error has become unreachable. - A concurrency error cannot be tested by output; testing is done over the reachable interleaving set. #### Next Step This lesson set up the problem and named the fix: mutual exclusion. The next lesson builds that fix and **counts its cost**. Threads with a 10-step critical section and 10 steps of non-critical work will be run under a mutex; it will be shown that a single thread takes 20 time units, that a second thread raises this to 29, a fourth to 47, and an eighth to 83, and that the waiting steps rise from zero to 252. How a semaphore brings that number down, and what it relaxes in doing so, sits in the same table. ### Locks, Mutexes, and Semaphores Source: https://academia.sh/en/courses/operating-system-concepts/locks-and-mutual-exclusion How mutual exclusion secures the critical section, the cost of contention in time and waiting steps, and what a semaphore gains and what it relaxes. The previous lesson set up the race condition and named the fix: mutual exclusion. Naming it is free; implementing it is not. This lesson first shows that exclusion genuinely works, then counts **how much it costs**. The axis of measurement should be stated up front. A lock does not speed a program up; it removes no work and shortens no step. The only thing it does is make some threads **wait**. Its cost is therefore measured in a single unit: **waiting steps**. #### What a Lock Guarantees A **lock** is an object that carries the right to enter a critical section. A lock that can be granted to only one thread at a time is called a **mutex**; its name comes directly from the guarantee it provides. The shared definition's `counter_run` routine carries this guarantee as an option: when `lock=True` is passed, the critical section is treated as indivisible. The measurement below sweeps the previous lesson's 20 interleavings twice. ```python def counter_run(pattern: list[int], lock: bool = False) -> int: """lock=True treats the critical section as indivisible.""" if lock: return 2 counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def interleavings(a: int, b: int) -> list[list[int]]: if a == 0: return [[1] * b] if b == 0: return [[0] * a] return ([[0] + s for s in interleavings(a - 1, b)] + [[1] + s for s in interleavings(a, b - 1)]) everything = interleavings(3, 3) for lock in (False, True): results = [counter_run(d, lock) for d in everything] wrong = sum(1 for s in results if s != 2) print(f"lock {str(lock):5s} | interleavings {len(everything):2d} | distinct results {sorted(set(results))}" f" | wrong {wrong:2d} | wrong ratio {wrong / len(everything):.4f}") ``` ``` lock False | interleavings 20 | distinct results [1, 2] | wrong 18 | wrong ratio 0.9000 lock True | interleavings 20 | distinct results [2] | wrong 0 | wrong ratio 0.0000 ``` The difference is **different in kind** from what the quantum setting did in the previous lesson. The quantum narrowed the reachable interleaving set from 20 to 2; the lock does not narrow the set — it **makes all twenty of the twenty interleavings in the set correct**. The distinct result set goes from `[1, 2]` to `[2]`. Correctness no longer depends on the scheduler's setting. #### Measuring Contention The gain has been counted; now the cost. The shared definition's `locked_run` routine runs threads that each carry a critical section and a piece of non-critical work, and returns three numbers: time, waiting steps, and processor utilization. **CC7.** Acquiring and releasing a lock are treated as free; only waiting steps are measured. **CC8.** Each thread carries **10 steps** of critical section and **10 steps** of non-critical work. **CC9.** Non-critical work is fully parallel; the number of cores is not a limiting factor here. **CC10.** A waiting thread does not hold a core; waiting steps are counted but not counted as busy. **CC11.** The lock's queue is fair; no thread is locked out indefinitely. An increase in the number of threads entering the same critical section is called **contention**. The sweep raises contention from 1 to 16. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: """Each thread does a `critical`-length critical section and `non_critical` steps of non-critical work. permits=1 is a mutex, permits>1 is a semaphore.""" remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: # non-critical work is parallel k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} print("mutex (permits 1), critical 10 , non-critical 10") print(" threads time waiting utilization waiting/(n*(n-1))") for n in (1, 2, 3, 4, 6, 8, 12, 16): k = locked_run(n, 10, 10, 1) ratio = "-" if n == 1 else f"{k['waiting'] / (n * (n - 1)):.1f}" print(f" {n:7d} {k['time']:4d} {k['waiting']:7d} {k['utilization']:11.4f} {ratio:>17s}") ``` ``` mutex (permits 1), critical 10 , non-critical 10 threads time waiting utilization waiting/(n*(n-1)) 1 20 0 1.0000 - 2 29 9 0.6897 4.5 3 38 27 0.5263 4.5 4 47 54 0.4255 4.5 6 65 135 0.3077 4.5 8 83 252 0.2410 4.5 12 119 594 0.1681 4.5 16 155 1080 0.1290 4.5 ``` A single thread finishes its work in **20 time units**, with **0** waiting steps and utilization **1.0000**. Adding a second thread brings the time to **29**. With a fourth, **47**; with an eighth, **83**; with a sixteenth, **155**. This is the plainest form of the course's second claim: **a second thread slows the work down.** Two threads carry 40 steps of work in total and finish the single thread's 20 steps in 29 time units; because the critical sections are serialized, there is no speedup at all, only a 9-time-unit delay. #### Time Is Linear, Waiting Is Quadratic The two columns do not grow at the same rate, and the difference is measurable. The time column is linear: each thread adds **9 time units**. Because the critical sections are serialized, the total time approaches the sum of the serialized critical sections. The waiting column is quadratic. The last column shows this directly: the ratio of waiting steps to $n(n-1)$ is constant at **4.5** across every row. That is, waiting steps grow approximately as $4.5 \cdot n^2$. Doubling the thread count does not double the time, but it **roughly quadruples** the waiting: **252** at 8 threads, **1080** at 16 — the ratio is `1080/252 = 4.29`, not exactly four, and it approaches four as $n$ grows. The consequence is read in the utilization column: it drops from **1.0000** to **0.1290**. The sixteenfold power of sixteen threads cannot actually be used, because of the critical section. The design rule that follows rests on this number: **the way to lower contention is not a faster lock but a shorter critical section.** This claim cannot be left uncosted; it has to be counted. #### Measuring the Effect of Shortening the Critical Section The next sweep fixes the thread count at **8** and varies the critical section's share of the total work. **CC12.** Total work per thread is fixed at **20 steps**; what varies is only how many of those 20 steps fall in the critical section. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} TOTAL = 20 print("8 threads , 20 total steps per thread , mutex") print(" critical non-critical critical share time waiting utilization") for critical in (1, 2, 5, 10, 15, 20): k = locked_run(8, critical, TOTAL - critical, 1) print(f" {critical:8d} {TOTAL - critical:12d} {critical / TOTAL:14.2f}" f" {k['time']:4d} {k['waiting']:7d} {k['utilization']:11.4f}") ``` ``` 8 threads , 20 total steps per thread , mutex critical non-critical critical share time waiting utilization 1 19 0.05 20 0 1.0000 2 18 0.10 27 28 0.7407 5 15 0.25 48 112 0.4167 10 10 0.50 83 252 0.2410 15 5 0.75 118 392 0.1695 20 0 1.00 153 532 0.1307 ``` The work done is the same in every row: eight threads, 20 steps each. The only thing that changes is how many of those steps must be serialized. At a critical share of 0.50, the time is **83**; dropping the share to 0.25 gives **48**. Halving the critical section nearly halves the time. At a share of 0.05, the time becomes **20** — the same as a single thread. Eight threads can use their eightfold power only once the critical section shrinks to a single step. The reverse direction is just as clear. Raising the share from 0.50 to 0.75 takes the time from 83 to **118**, and to 1.00 takes it to **153**. Waiting steps rise from 252 to **532**. In work that is entirely critical section, concurrency gains nothing at all; it only produces waiting. The table's first row is also what later lessons rest on: work whose critical section is a **single step** produces no contention. When hardware executes such a step indivisibly, it is called an **atomic operation**, and its cost in this table is **zero**. #### The Semaphore A **semaphore** is a tool that can admit more than one thread into a critical section at the same time. The number it carries is the number of **permits** that can be granted. **CC13.** The permit count is fixed and does not change during a run. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: """Each thread does a `critical`-length critical section and `non_critical` steps of non-critical work. permits=1 is a mutex, permits>1 is a semaphore.""" remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} print("semaphore: varying the permit count") print(" threads permits time waiting utilization") for n in (2, 4, 8, 16): for permits in (1, 2, 4): k = locked_run(n, 10, 10, permits) print(f" {n:7d} {permits:7d} {k['time']:4d} {k['waiting']:7d} {k['utilization']:11.4f}") ``` ``` semaphore: varying the permit count threads permits time waiting utilization 2 1 29 9 0.6897 2 2 20 0 1.0000 2 4 20 0 1.0000 4 1 47 54 0.4255 4 2 29 18 0.6897 4 4 20 0 1.0000 8 1 83 252 0.2410 8 2 47 108 0.4255 8 4 29 36 0.6897 16 1 155 1080 0.1290 16 2 83 504 0.2410 16 4 47 216 0.4255 ``` A semaphore with two permits brings two threads' time down from **29 to 20** and waiting from **9 to 0**. There is a regular pattern across the whole table: **the permit count divides contention.** Eight threads with two permits finish at **47**, the same as four threads with one permit. Sixteen threads with four permits also finish at **47**. Waiting steps do not divide the same way. Four threads with one permit produce **54** waiting steps, while eight threads with two permits produce **108**, and sixteen threads with four permits produce **216**. The time is equal, but the waiting is four times as much: **reaching the same time with more threads does not come for free.** #### A Semaphore Does Not Provide Mutual Exclusion The gain in the table invites an easy but wrong conclusion: raising the permit count both protects us and speeds us up. This is wrong. A semaphore with two permits, by definition, **admits two threads into the critical section at the same time.** The previous lesson's counter is not protected under this condition: with two threads inside, the read-increment-write triplets interleave again, and **18 of the 20 interleavings** again produce a wrong result. This is a return to this lesson's first measurement's `lock=False` row. So the two tools do different jobs. **A mutex is a correctness tool**; it protects the critical section. **A semaphore is a resource tool**; it limits how many threads can use a resource pool at the same time. If a pool has four connections, a semaphore with four permits is correct; a semaphore with two permits in front of a shared counter is **a bug**. The shared definition's fourth reading sums this up in one sentence: a semaphore with two permits brings 29 down to 20, but this is **relaxing mutual exclusion**, and it is not free. #### How Waiting Is Done In this measurement, a waiting thread does not hold a core (CC10). There is a second form of waiting: **busy waiting** — continuously polling whether the lock has become free. The shared definition's third reading makes remeasuring this option unnecessary: the polling model makes processor utilization **1.0000** and **does not change the time at all**. Applied to the table above, sixteen threads' utilization would read 1.0000 instead of 0.1290, and the time would still be **155**. Here, utilization is a proxy metric, and it misleads. #### Three Numbers | Metric | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | Time | single thread, **20** | eight threads, mutex, **83** | 63 time units | | Waiting steps | **0** | **252** | 252 steps | | Processor utilization | **1.0000** | **0.2410** | 0.7590 drop | | Wrong interleavings | 18 (unprotected) | **0** | correctness gained | The last row says why the first three rows are paid. If the cost looks high, so is what it buys: without protection, eight threads would finish in 20 time units, and there would be no guarantee at all that the result was correct. #### Summary - A mutex does not narrow the reachable interleaving set; it makes every interleaving in the set correct — the distinct result set goes from `[1, 2]` to `[2]`. - As contention grows, time grows linearly: each thread adds 9 time units; going from 1 to 16 threads, time rises from 20 to 155. - Waiting steps grow quadratically; the ratio to $n(n-1)$ is 4.5 across every row. Doubling the thread count roughly quadruples the waiting. - A semaphore divides contention by the permit count and lowers time, but it relaxes mutual exclusion; it is not a correctness tool in front of a shared counter. - The way to lower contention is not a faster lock but a shorter critical section: at eight threads, dropping the critical share from 0.50 to 0.25 lowers time from 83 to 48, and to 0.05 lowers it to 20. #### Next Step This lesson measured the cost of a single lock. Real programs do not use a single lock: every shared structure gets its own lock, and a thread can request two at once. The next lesson takes up two new failure modes that arise from this — **deadlock**, where a group of threads waits on each other forever, and **starvation**, where a thread's turn never comes. The waiting relationship will be turned into a graph, the Data Structures course's cycle detection will be called directly, and it will be shown, by scanning 648 cases, that lock ordering structurally eliminates deadlock. ### Deadlock and Starvation Source: https://academia.sh/en/courses/operating-system-concepts/deadlock-and-starvation Deadlock's four conditions, detecting it through cycle detection on the wait-for graph, lock ordering's structural prevention, and its cost in waiting steps. The previous lesson measured the cost of a single lock and collected the result on a single axis: waiting steps. On that axis, a bad number means a slow program. This lesson brings out a second kind of failure that produces **no** number on that axis at all: a deadlocked thread does not slow down, it **stops**. Two locks are enough. If one thread holds the first lock and requests the second, while another thread holds the second and requests the first, neither ever advances again. This lesson **counts** when this situation arises, builds the structural form of prevention, and measures what prevention costs. #### Four Conditions **Deadlock** does not happen at random. It arises when four conditions hold **at the same time**, and breaking any one of them makes it impossible. **Mutual exclusion.** The resource cannot be shared; only one thread can hold it at a time. Removing this condition would also remove the previous lesson's correctness guarantee. **Hold and wait.** A thread requests a new resource without releasing the one it already holds. **No preemption.** A lock cannot be forcibly taken back; only the holder can release it. **Circular wait.** The waiting relationship forms a ring. **CC14.** The wait-for graph's nodes are threads, and its edges are the relation "waiting for a held lock." **CC15.** A lock is held by only one thread at a time; if the requested lock is free, there is no edge. **CC16.** Every thread holds one lock and requests another; releasing a lock cannot be forced, and recovery after detection is not modeled. The first three conditions hold in most programs by design. The one remaining target is **circular wait**, and in the language of graphs that is exactly a **cycle**. #### Cycle Detection Is Not a New Routine The depth-first search lesson in the Data Structures course built cycle detection on a directed graph, and the same distinction applies here unchanged: "visited" must not be confused with "still open." The shared definition's `has_cycle` routine carries this with three colors — 0 never seen, 1 still open, 2 branch finished. The routine is **not rebuilt**; it is called directly. The measurement below first tests five wait-for graphs, then scans a state space. ```python from itertools import permutations, product def has_cycle(waiting: dict[str, list[str]]) -> bool: """Cycle test on a directed graph. color 1 = still open, color 2 = branch done.""" color = {d: 0 for d in waiting} def visit(d): color[d] = 1 for h in waiting.get(d, []): if color.get(h, 0) == 1: return True if color.get(h, 0) == 0 and visit(h): return True color[d] = 2 return False return any(color[d] == 0 and visit(d) for d in list(waiting)) for name, graph in (("nobody waiting", {"T1": [], "T2": []}), ("chain T1 -> T2", {"T1": ["T2"], "T2": []}), ("two branches, shared target", {"T1": ["T3"], "T2": ["T3"], "T3": []}), ("ring T1 -> T2 -> T1", {"T1": ["T2"], "T2": ["T1"]}), ("ring T1 -> T2 -> T3", {"T1": ["T2"], "T2": ["T3"], "T3": ["T1"]})): print(f" {name:28s} deadlock {has_cycle(graph)}") def scan(lock_count: int, thread_count: int, ordered: bool) -> tuple[int, int]: """Each thread holds one lock and requests another. All states.""" locks = list(range(1, lock_count + 1)) states = deadlocked = 0 for held in permutations(locks, thread_count): for requested in product(locks, repeat=thread_count): if any(t == i for t, i in zip(held, requested)): continue # does not request the lock it already holds if ordered and any(i < t for t, i in zip(held, requested)): continue # ordered acquisition: only a higher number is requested owner = {k: f"T{j+1}" for j, k in enumerate(held)} graph = {f"T{j+1}": [] for j in range(thread_count)} for j, i in enumerate(requested): if i in owner: # if the requested lock is free, there is no edge graph[f"T{j+1}"].append(owner[i]) states += 1 if has_cycle(graph): deadlocked += 1 return states, deadlocked print() print("4 locks , each thread holds one lock and requests another") print(" threads acquisition states deadlocked deadlock ratio") for n in (2, 3, 4): for ordered in (False, True): d, k = scan(4, n, ordered) label = "ordered" if ordered else "free " ratio = f"{k / d:.4f}" if d else "no states" print(f" {n:7d} {label} {d:8d} {k:10d} {ratio:>16s}") ``` ``` nobody waiting deadlock False chain T1 -> T2 deadlock False two branches, shared target deadlock False ring T1 -> T2 -> T1 deadlock True ring T1 -> T2 -> T3 deadlock True 4 locks , each thread holds one lock and requests another threads acquisition states deadlocked deadlock ratio 2 free 108 12 0.1111 2 ordered 22 0 0.0000 3 free 648 264 0.4074 3 ordered 36 0 0.0000 4 free 1944 1944 1.0000 4 ordered 0 0 no states ``` The third row is the heart of the measurement: with four locks and three threads, **648** distinct waiting states can be built, and **264** of them are deadlocked. The ratio is **0.4074**. The second branch matters: at two threads the ratio is **0.1111**, at three it is **0.4074**, at four it is **1.0000**. As threads are added, deadlock **stops being the exception and becomes the rule**. The 1.0000 in the row where four threads hold four locks is not a coincidence. When every thread holds one lock and requests another, the "whose lock am I waiting for" relation builds a graph with exactly one outgoing edge per node; a finite graph of this kind, with no node lacking an outgoing edge, **always** contains a ring. #### Detection and Prevention Are Not the Same Thing The scan above is a **detection** routine: given a state, it says whether it is deadlocked. Using this in a running system requires three things: **continuously keeping the wait-for graph up to date**, **scanning the graph at regular intervals**, and **rolling back a thread** when a cycle is found. The cost of the scan was measured in the Data Structures course and is $O(V + E)$; it is not repeated here. The third step is the most expensive. Rolling back means forcibly stripping a held lock and canceling the work that thread has done — that is, **breaking the no-preemption condition** — and the canceled work has to be redone. This lesson does not model that recovery (CC16). Prevention, on the other hand, **measures nothing and scans nothing** during the run. It pays its cost at design time: locks are given an order, and that order is followed everywhere. #### Lock Ordering In the table, every `ordered` row has **0** deadlocked states. This is not an improvement; it is a **structural impossibility**, and its justification fits in one sentence. **CC17.** Locks are placed in a fixed total order; every thread requests locks **only in increasing number order**. Suppose a ring exists. Then every thread in the ring is waiting for a lock numbered **higher** than the one it holds. Walking around the ring, the numbers keep increasing; but the ring returns to where it started, and a number cannot be greater than itself. Contradiction. So no ring exists. The table shows this in two separate ways. At three threads, the state space drops from **648** to **36**, and **none** of the remaining 36 states are deadlocked. At four threads, under lock ordering, **no states remain at all** — that state cannot even be constructed. The drop from 648 to 36 here also says where prevention's cost lies: **most of the eliminated states were not deadlocked.** Lock ordering forbids not only rings but also many harmless forms of waiting. #### The Cost of Prevention The forbidden harmless states are paid for somewhere. A thread that needs a second lock must, to follow the order, **acquire the first lock early** and **hold onto it**; two separate critical sections collapse into a single one. **CC18.** Under free acquisition, two resources have two separate locks, and two threads can be in a critical section at the same time; this gives the same numbers as a semaphore with two permits. Under ordered acquisition, the two locks are held nested, so there is a single critical section. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} print("two locks , critical section 10 steps total , non-critical 10 steps") print(" threads acquisition permits time waiting utilization") for n in (2, 4, 8): for label, permits in (("free ", 2), ("ordered", 1)): k = locked_run(n, 10, 10, permits) print(f" {n:7d} {label} {permits:4d} {k['time']:4d} {k['waiting']:7d}" f" {k['utilization']:8.4f}") print() for n in (2, 4, 8): s = locked_run(n, 10, 10, 1)["time"] - locked_run(n, 10, 10, 2)["time"] b = locked_run(n, 10, 10, 1)["waiting"] - locked_run(n, 10, 10, 2)["waiting"] print(f" {n} threads -> cost of ordered acquisition: time +{s} , waiting +{b}") ``` ``` two locks , critical section 10 steps total , non-critical 10 steps threads acquisition permits time waiting utilization 2 free 2 20 0 1.0000 2 ordered 1 29 9 0.6897 4 free 2 29 18 0.6897 4 ordered 1 47 54 0.4255 8 free 2 47 108 0.4255 8 ordered 1 83 252 0.2410 2 threads -> cost of ordered acquisition: time +9 , waiting +9 4 threads -> cost of ordered acquisition: time +18 , waiting +36 8 threads -> cost of ordered acquisition: time +36 , waiting +144 ``` At four threads, lock ordering raises time from **29 to 47** and waiting steps from **18 to 54**. At eight threads, the gap widens further: time from **47 to 83**, waiting from **108 to 252**. The cost grows with the thread count — **+9, +18, +36**. These numbers make the trade explicit. Lock ordering brings the deadlock probability down from 0.4074 to **0.0000**; in return, **144 extra waiting steps** are paid at eight threads. Zero deadlock is bought at the price of a performance loss, and this trade cannot be defended without being counted. #### Starvation Deadlock is threads stopping **together**. **Starvation**, by contrast, is a single thread's turn never coming while the system keeps running. Unlike deadlock, there is no cycle in the wait-for graph; the lock keeps being granted, just always to the same threads. **CC19.** Threads request the critical section **continuously**; as soon as they finish their non-critical work, they queue again. **CC20.** When the lock frees up, one of the waiters is chosen; the selection rule takes either the lowest-numbered waiter or the longest-waiting one. ```python def continuous_run(thread_count: int, critical: int, non_critical: int, duration: int, fair: bool) -> dict: """Threads that continuously request the critical section. The lock goes to the longest waiter if fair, otherwise to the lowest-numbered waiter.""" remaining = [0] * thread_count # steps left in the critical section outside = [0] * thread_count # steps left in non-critical work request = [0] * thread_count # how long it has been waiting turns = [0] * thread_count # how many times it entered the critical section inside = None for t in range(duration): for j in range(thread_count): if outside[j]: outside[j] -= 1 elif inside != j: request[j] += 1 if inside is None: waiting = [j for j in range(thread_count) if not outside[j]] if waiting: chosen = max(waiting, key=lambda j: request[j]) if fair else min(waiting) inside, remaining[chosen], request[chosen] = chosen, critical, 0 turns[chosen] += 1 if inside is not None: remaining[inside] -= 1 if not remaining[inside]: outside[inside] = non_critical inside = None return {"turns": turns, "starved": request} # starved: steps waited since the last request print("4 threads , critical 10 , non-critical 10") print(" duration selection rule turn distribution total turns steps starved") for duration in (400, 4000): for fair in (False, True): s = continuous_run(4, 10, 10, duration, fair) label = "fair " if fair else "lowest " print(f" {duration:4d} {label} {str(s['turns']):20s} {sum(s['turns']):10d}" f" {s['starved']}") ``` ``` 4 threads , critical 10 , non-critical 10 duration selection rule turn distribution total turns steps starved 400 lowest [20, 20, 0, 0] 40 [0, 0, 400, 400] 400 fair [10, 10, 10, 10] 40 [20, 10, 0, 0] 4000 lowest [200, 200, 0, 0] 400 [0, 0, 4000, 4000] 4000 fair [100, 100, 100, 100] 400 [20, 10, 0, 0] ``` In four hundred time units, the critical section sees **40** total entries — **under both selection rules**. Throughput is the same. The distribution is not: the rule that picks the lowest-numbered waiter distributes entries as `[20, 20, 0, 0]`. The third and fourth threads **never enter** and sit starved for **400 steps**. When the duration is multiplied by ten, the result does not change: `[200, 200, 0, 0]`. Steps starved rise from 400 to **4000**. This is a failure distinct from deadlock, and it **does not pass with time**; it has no bound and grows with duration. The fair selection rule distributes the same 40 entries as `[10, 10, 10, 10]`. Total throughput does not change, so **fairness comes free here**. The reason it comes free is that the critical section is already serialized; the cost was already paid in the previous lesson. The real warning in this measurement is that a throughput metric **cannot see** starvation. The total turn count is 40 under both rules; the only thing that reveals the failure is the **distribution**. #### Three Numbers | Metric | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | Deadlocked states | single lock, **0** | four locks, three threads, **264/648** | ratio 0.4074 | | After lock ordering | — | **0/36** | time +18, waiting +36 | | Starvation | single thread, **0** | four threads, unfair selection | 2 threads, **4000** steps starved | The table's second row carries the course's rule: eliminating deadlock is not a gain, it is a **trade**. At four threads, the 0.4074 deadlock ratio is zeroed out, and in return every thread waits longer. #### Summary - Deadlock arises when four conditions hold at once; in practice the only breakable condition is circular wait, which is a cycle in the wait-for graph. - Cycle detection is not a new routine; the three-color test built in the Data Structures course's depth-first search lesson is called unchanged. - With four locks and three threads, **264** of 648 waiting states are deadlocked (0.4074); as the thread count grows, the ratio rises from 0.1111 to 1.0000. - Lock ordering makes a ring structurally impossible — the state space drops from 648 to 36 and deadlocked states become **0**; the cost at eight threads is 144 extra waiting steps. - In starvation there is no cycle and throughput does not drop: in 400 time units, a total of 40 entries is the same under both selection rules; the failure shows up only in the distribution. #### Next Step Everything measured so far happened on a single core; the threads never actually advanced at the same time. The next lesson lifts that restriction. Adding a core brings the time down from 197 to 180, but a fourth core plateaus at 179, and idle core steps rise from 108 to 1355. The same lesson will also show what became of the first lesson's quantum protection: under real parallelism, the reachable interleavings climb back to 20, and 18 of them are wrong. ### Concurrency on Multiple Cores Source: https://academia.sh/en/courses/operating-system-concepts/concurrency-on-multiple-cores Where real parallelism's contribution to time runs out, the cost paid in idle core steps, and how memory visibility removes the quantum's protection. Every measurement so far was taken on a single core. Threads advanced in turn; the phrase "at the same time" was always an approximation, an appearance created by the scheduler's fast switching. This lesson lifts that restriction and asks two questions together. The first is a performance question: how much does adding cores speed the work up, and where does it stop? The second is a correctness question, and it matters more: what happens to the **quantum's protection** from the first lesson under multiple cores? Both questions are answered numerically on the same shared definition. This course models **a single machine**; there is no network cost, and none enters any measurement. #### Adding Cores **Parallelism** is two pieces of work genuinely executing at the same time. It is distinct from concurrency: concurrency is work being able to **interleave**, parallelism is work being able to **advance simultaneously**. **CC21.** Each core executes at most one step per time unit; cores are identical. **CC22.** A waiting step does not hold a core; a waiting process occupies no core at all. **CC23.** A process runs on exactly one core at a time; splitting within a process is not modeled. ```python SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_DURATION = 30 # how many time units one wait step takes CONTEXT_COST = 2 # cost of one context switch (time units) VIRTUAL_PAGE = 16 def generator(seed): """Deterministic pseudo-random generator. The same seed gives the same sequence.""" d = seed def next_val(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_val def workload(seed=SEED): 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"S{i+1}", "steps": steps, "priority": 1 + r(3), "arrival": i * 4}) return jobs INFINITY = 10**9 def schedule(jobs, policy="fcfs", quantum=4, cores=1, context_cost=CONTEXT_COST): """Every core executes at most one step per time unit.""" state = [{"name": i["name"], "steps": list(i["steps"]), "pos": 0, "arrival": i["arrival"], "ready_at": i["arrival"], "used": 0, "finish": None, "priority": i["priority"]} for i in jobs] share_limit = INFINITY if policy == "fcfs" else quantum cores_list = [{"process": None, "previous": None, "share": 0, "stall": 0} for _ in range(cores)] t, context_switches, idle_steps = 0, 0, 0 def not_done(d): return d["pos"] < len(d["steps"]) 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_list: # release d = c["process"] if d is not None and (not not_done(d) or d["ready_at"] > t or c["share"] >= share_limit): c["process"] = None for c in cores_list: # assign if c["stall"] or c["process"] is not None: continue held = [x["process"] for x in cores_list if x["process"] is not None] ready = [d for d in state if not_done(d) and d["ready_at"] <= t and d not in held] if not ready: continue if policy == "priority": chosen = min(ready, key=lambda d: (-d["priority"], d["ready_at"], d["name"])) elif policy == "fair": chosen = min(ready, key=lambda d: (d["used"], d["ready_at"], d["name"])) else: chosen = min(ready, key=lambda d: (d["ready_at"], d["name"])) if c["previous"] is not None and c["previous"] is not chosen: context_switches += 1 c["stall"] = context_cost c["process"] = chosen c["previous"] = chosen c["share"] = 0 for c in cores_list: # execute if c["stall"]: c["stall"] -= 1 continue d = c["process"] if d is None: idle_steps += 1 continue kind, value = d["steps"][d["pos"]] if kind == "WAIT": d["pos"] += 1 d["ready_at"] = t + value c["process"] = None idle_steps += 1 if not not_done(d): d["finish"] = t + value else: d["pos"] += 1 d["used"] += 1 d["ready_at"] = t + 1 c["share"] += 1 if not not_done(d): d["finish"] = t + 1 c["process"] = None t += 1 for d, i in zip(state, jobs): wait_total = sum(v for kind, v in i["steps"] if kind == "WAIT") d["waiting"] = d["finish"] - d["arrival"] - d["used"] - wait_total return {"time": t, "context_switches": context_switches, "idle_core_steps": idle_steps, "total_work": sum(d["used"] for d in state), "avg_turnaround": round(sum(d["finish"] - d["arrival"] for d in state) / len(state), 2), "avg_waiting": round(sum(d["waiting"] for d in state) / len(state), 2), "finish": {d["name"]: d["finish"] for d in state}} JOBS = workload() print("cores time context idle core steps total work avg.turnaround") for c in (1, 2, 3, 4, 6, 8): m = schedule(JOBS, "round_robin", cores=c) print(f" {c:5d} {m['time']:4d} {m['context_switches']:5d} {m['idle_core_steps']:17d}" f" {m['total_work']:9d} {m['avg_turnaround']:14.2f}") print() print("each process's own chain (earliest finish with no sharing at all):") for i in JOBS: h = sum(1 for kind, _ in i["steps"] if kind == "COMPUTE") b = STEP_COUNT - h print(f" {i['name']} arrival {i['arrival']:2d} compute {h} wait {b}" f" -> earliest finish {i['arrival'] + h + WAIT_DURATION * b}") print(" reachable lower bound:", max(i["arrival"] + sum(1 for t, _ in i["steps"] if t == "COMPUTE") + WAIT_DURATION * sum(1 for t, _ in i["steps"] if t == "WAIT") for i in JOBS)) ``` ``` cores time context idle core steps total work avg.turnaround 1 197 25 108 39 153.80 2 180 21 279 39 142.40 3 179 19 460 39 141.40 4 179 19 639 39 141.40 6 179 19 997 39 141.40 8 179 19 1355 39 141.40 each process's own chain (earliest finish with no sharing at all): S1 arrival 0 compute 9 wait 3 -> earliest finish 99 S2 arrival 4 compute 9 wait 3 -> earliest finish 103 S3 arrival 8 compute 7 wait 5 -> earliest finish 165 S4 arrival 12 compute 7 wait 5 -> earliest finish 169 S5 arrival 16 compute 7 wait 5 -> earliest finish 173 reachable lower bound: 173 ``` A second core brings the time down from **197 to 180**: 17 time units, well above the measurement band. A third core gives **179**. So does a fourth. So do the sixth and eighth. After two cores, there is no gain at all. The **1-time-unit difference** between 180 and 179 already falls below the measurement band and **counts as unmeasured**; a meaningful difference is at least as large as the context cost, that is, 2 time units. #### The Cost Sits in Idle Core Steps The gain stopped; the spending did not. Idle core steps rise from **108** to **279**, then to **639**, reaching **1355** at eight cores. Total work is **39** in every row — the work actually done never changes. Placing three numbers side by side gives this lesson's main table: | Metric | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | Time | single core, **197** | four cores, **179** | 18 time units gained | | Idle core steps | **108** | **639** | 531 extra idle steps | | Total work | **39** | **39** | unchanged | The fourth core, compared with the third, gains nothing at **179** but spends **179 extra idle core steps**. Going all the way to the eighth core, the time gained for 1355 idle steps is **0**. The course's second claim is paid here too: **abstraction sometimes makes things worse** — here it does not worsen the time, but it measurably spends the resource. Two more columns should be read. Context switches drop from **25** to **21**, then to **19**: as cores are added, the scheduler needs less to swap processes for one another. Average turnaround also falls from **153.80** to **141.40**; while the overall time stalls at 179, individual processes' finish times keep improving. Time alone is not enough to decide on a core count. A caveat belongs here too. "Two cores are enough" is the result **for this workload**, not a general rule. This workload is I/O-heavy; for a compute-heavy workload, the curve flattens somewhere else. A ranking measured on a single workload **counts as unmeasured**, and this course writes it that way. #### Why It Stalls at 179 The second part of the output gives the reason. Every process has its own chain of steps, and that chain cannot be split: once a wait step ends, the next compute step follows — never the other way around. S5 arrives at time unit 16 and carries 7 compute steps and 5 wait steps. The waits take $5 \times 30 = 150$ time units, and during that stretch **no core is of any use**. Its earliest possible finish is $16 + 7 + 150 = 173$. **173 is a lower bound that cannot be beaten even with infinite cores.** The measured 179 is 6 time units above this bound. The gap comes from context switching and the order of arrivals. The rule that follows rests on this number: **if the work is bound by I/O, adding cores does not change it.** This workload has 39 compute steps against 21 wait steps; the waits take 630 time units, the compute only 39. The thing to be sped up was never the compute in the first place. #### Memory Visibility Now the correctness question. The first lesson showed that when the scheduler's quantum is larger than the critical section, the reachable interleavings drop to **2** and none of them are wrong. What did that protection rest on? On a single thing: **two threads being unable to advance at the same time.** **CC24.** With two cores, two threads land on separate cores; since no scheduler switch is needed between them, the quantum does not constrain the order of their memory accesses. ```python def counter_run(pattern: list[int], lock: bool = False) -> int: if lock: return 2 counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def interleavings(a: int, b: int) -> list[list[int]]: if a == 0: return [[1] * b] if b == 0: return [[0] * a] return ([[0] + s for s in interleavings(a - 1, b)] + [[1] + s for s in interleavings(a, b - 1)]) def quantum_interleavings(steps: int, quantum: int) -> list[list[int]]: result = [] def walk(remaining_a, remaining_b, current, sequence): if not remaining_a and not remaining_b: result.append(list(sequence)) return for candidate in (0, 1): remaining = remaining_a if candidate == 0 else remaining_b if not remaining: continue n = min(quantum, remaining) sequence.extend([candidate] * n) walk(remaining_a - n if candidate == 0 else remaining_a, remaining_b - n if candidate == 1 else remaining_b, candidate, sequence) del sequence[len(sequence) - n:] walk(steps, steps, None, []) distinct = [] for d in result: if d not in distinct: distinct.append(d) return distinct print("cores quantum lock reachable wrong wrong ratio") for cores, quantum, lock in ((1, 1, False), (1, 3, False), (2, 3, False), (4, 3, False), (2, 3, True)): # with two cores, two threads land on separate cores: the quantum constraint disappears reachable = interleavings(3, 3) if cores > 1 else quantum_interleavings(3, quantum) wrong = sum(1 for d in reachable if counter_run(d, lock) != 2) print(f" {cores:5d} {quantum:7d} {str(lock):5s} {len(reachable):9d} {wrong:5d}" f" {wrong / len(reachable):11.4f}") ``` ``` cores quantum lock reachable wrong wrong ratio 1 1 False 20 18 0.9000 1 3 False 2 0 0.0000 2 3 False 20 18 0.9000 4 3 False 20 18 0.9000 2 3 True 20 0 0.0000 ``` The second row is the first lesson's result: single core, quantum 3, **2** reachable interleavings, **0** wrong. The third row is taken with the same quantum, only with one more core: reachable interleavings **20**, wrong **18**, ratio **0.9000**. The quantum is still 3. The program is still the same. The only thing that changed is the core count — and the first lesson's "invisible" error **has come back with a hardware change**. The first lesson's sentence was exactly about this: the error had never disappeared. This is the plainest form of the **memory visibility** problem. When a value one core writes becomes visible to another core is not under the program's control. The last row shows the one solution: once the critical section is made indivisible, all twenty of the twenty interleavings produce the correct result. The practical consequence of this completes the first lesson's sampling measurement. There, it was shown that run count produces no proof; here, it is seen that **the run environment** produces no proof either. A program that comes back clean thousands of times on a single-core environment can break the moment the core count grows — because what changes is not the program itself but **the reachable interleaving set**. A concurrency guarantee must be independent of the number of cores it runs on; if it depends on that, it is not a guarantee. #### Cache Coherence and Atomic Operations While cores share memory, each has its own cache. Invalidating a line one core writes in the others, and transferring it when needed, is handled by the **cache coherence** mechanism. This mechanism is not free: writing frequently to a shared variable produces continuous transfer between cores. **CC25.** This definition does **not model** cache coherence or memory bus contention; the cost in that direction is therefore **not measured** in this course and counts as unmeasured. The 639 idle core steps above do **not include** the coherence cost. The single-step solution to the visibility problem is the **atomic operation**: hardware executing the read-increment-write triplet as a single indivisible step. Once the critical section shrinks to one step, contention disappears too; the previous lesson's sweep measured this — at eight threads, with a 10-step critical section the time was **83** and utilization **0.2410**, while with the critical section down to a single step, the time became **20** and utilization **1.0000**. The atomic operation's limit sits right there too: it applies only to **a single location**. If two fields must be kept consistent together, the critical section becomes multiple steps again, and the lock's cost comes back. #### Summary - A second core brings the time from 197 to 180; a third gives 179, and beyond that nothing is gained — the 1-time-unit difference between 180 and 179 falls below the measurement band. - Idle core steps rise from 108 to 639, reaching 1355 at eight cores, while total work stays fixed at 39; the resource spent buys nothing. - The lower bound is 173 and comes from the wait chains; when work is bound by I/O, adding cores does not change it. - Under real parallelism, the quantum's protection disappears: the reachable interleavings that were 2 on a single core at quantum 3 climb to 20 on two cores, and 18 of them are wrong. - Cache coherence's cost is not modeled in this definition and counts as unmeasured; an atomic operation shrinks the critical section to a single step, but it applies only to a single location. #### Next Step For three lessons, a single concurrency model was used: threads accessing shared memory, protected by locks. That model's cost is now counted — contention, deadlock risk, the visibility problem. The next lesson shows that shared memory is not mandatory and compares three models **on the same workload**: threads, the event loop, and message passing. The measurement is repeated on two separate workloads, because a ranking measured on a single workload counts as unmeasured. ### Concurrency Models Source: https://academia.sh/en/courses/operating-system-concepts/concurrency-models Comparing the thread, event loop, and message passing models on the same workload in terms of time, idle core steps, and correctness guarantee. For four lessons, a single concurrency model was used: threads accessing shared memory, protected by locks. That model's cost is now counted — contention producing 252 waiting steps at eight threads, a 0.4074 deadlock ratio with four locks and three threads, 18 wrong interleavings at two cores. All of these costs have **one common source**: shared mutable state. Remove it, and they all disappear together. This lesson adds two models that either remove shared state or structurally serialize access to it, and counts all three **on the same workload**. #### Three Models **The thread model.** Shared address space, preemptive scheduling, lock-protected critical sections. This is the model measured up to this point. **The event loop model.** A single thread, non-preemptive execution, **run-to-completion**. Waiting does not block work; when one task finishes, the next is taken. This model was built and measured in detail in the **Asynchronous JavaScript and the Runtime** course; the event loop's queue rule, the microtask distinction, and the consequences of blocking work are **not repeated here**. This lesson takes it only as **one of three models**. **The message passing model.** Isolated state, no sharing, communication only through copied messages. Because state is not shared, no lock is needed either. The three models are three settings of the same scheduler, and this is what makes the comparison meaningful. **CC26.** The thread model: preemptive, quantum 4, single core, context cost 2. **CC27.** The event loop model: non-preemptive, single core, context cost **0** — a switch is not an address-space change but a move to the next task in the queue. **CC28.** The message passing model: isolated state, four cores, context cost 2. **CC29.** The cost of copying a message is **not modeled** in this definition and counts as unmeasured. **CC30.** All three models run **the same job list**; the workload is identical. ```python SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_DURATION = 30 # how many time units one wait step takes CONTEXT_COST = 2 # cost of one context switch (time units) VIRTUAL_PAGE = 16 def generator(seed): """Deterministic pseudo-random generator. The same seed gives the same sequence.""" d = seed def next_val(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_val def workload(seed=SEED): 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"S{i+1}", "steps": steps, "priority": 1 + r(3), "arrival": i * 4}) return jobs INFINITY = 10**9 def schedule(jobs, policy="fcfs", quantum=4, cores=1, context_cost=CONTEXT_COST): """Every core executes at most one step per time unit.""" state = [{"name": i["name"], "steps": list(i["steps"]), "pos": 0, "arrival": i["arrival"], "ready_at": i["arrival"], "used": 0, "finish": None, "priority": i["priority"]} for i in jobs] share_limit = INFINITY if policy == "fcfs" else quantum cores_list = [{"process": None, "previous": None, "share": 0, "stall": 0} for _ in range(cores)] t, context_switches, idle_steps = 0, 0, 0 def not_done(d): return d["pos"] < len(d["steps"]) 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_list: # release d = c["process"] if d is not None and (not not_done(d) or d["ready_at"] > t or c["share"] >= share_limit): c["process"] = None for c in cores_list: # assign if c["stall"] or c["process"] is not None: continue held = [x["process"] for x in cores_list if x["process"] is not None] ready = [d for d in state if not_done(d) and d["ready_at"] <= t and d not in held] if not ready: continue if policy == "priority": chosen = min(ready, key=lambda d: (-d["priority"], d["ready_at"], d["name"])) elif policy == "fair": chosen = min(ready, key=lambda d: (d["used"], d["ready_at"], d["name"])) else: chosen = min(ready, key=lambda d: (d["ready_at"], d["name"])) if c["previous"] is not None and c["previous"] is not chosen: context_switches += 1 c["stall"] = context_cost c["process"] = chosen c["previous"] = chosen c["share"] = 0 for c in cores_list: # execute if c["stall"]: c["stall"] -= 1 continue d = c["process"] if d is None: idle_steps += 1 continue kind, value = d["steps"][d["pos"]] if kind == "WAIT": d["pos"] += 1 d["ready_at"] = t + value c["process"] = None idle_steps += 1 if not not_done(d): d["finish"] = t + value else: d["pos"] += 1 d["used"] += 1 d["ready_at"] = t + 1 c["share"] += 1 if not not_done(d): d["finish"] = t + 1 c["process"] = None t += 1 for d, i in zip(state, jobs): wait_total = sum(v for kind, v in i["steps"] if kind == "WAIT") d["waiting"] = d["finish"] - d["arrival"] - d["used"] - wait_total return {"time": t, "context_switches": context_switches, "idle_core_steps": idle_steps, "total_work": sum(d["used"] for d in state), "avg_turnaround": round(sum(d["finish"] - d["arrival"] for d in state) / len(state), 2), "avg_waiting": round(sum(d["waiting"] for d in state) / len(state), 2), "finish": {d["name"]: d["finish"] for d in state}} MODELS = (("thread", dict(policy="round_robin", quantum=4, cores=1, context_cost=2)), ("event loop", dict(policy="fcfs", cores=1, context_cost=0)), ("message passing", dict(policy="round_robin", quantum=4, cores=4, context_cost=2))) for k, seed in enumerate((20260218, 20260219)): if k: print() JOBS = workload(seed) compute = sum(1 for i in JOBS for t, _ in i["steps"] if t == "COMPUTE") print(f"workload {seed}: {compute} compute steps , " f"{PROCESS_COUNT * STEP_COUNT - compute} wait steps") print(" model time context idle core avg.turnaround avg.waiting") for name, settings in MODELS: s = schedule(JOBS, **settings) print(f" {name:16s} {s['time']:4d} {s['context_switches']:6d} {s['idle_core_steps']:9d}" f" {s['avg_turnaround']:14.2f} {s['avg_waiting']:11.2f}") ``` ``` workload 20260218: 39 compute steps , 21 wait steps model time context idle core avg.turnaround avg.waiting thread 197 25 108 153.80 20.00 event loop 178 22 139 137.20 3.40 message passing 179 19 639 141.40 7.60 workload 20260219: 46 compute steps , 14 wait steps model time context idle core avg.turnaround avg.waiting thread 202 22 112 122.20 29.00 event loop 177 14 131 98.00 4.80 message passing 175 12 630 98.00 4.80 ``` #### What the Table Shows The clearest result is that **the thread model gives the worst time on both workloads**: **197** on the first, **202** on the second. This is the face of the shared definition's first reading that falls to this lesson — preemptive time-slicing makes fairness cost time, and the cost holds on both workload compositions. The difference between the event loop and message passing, however, **cannot be measured**. On the first workload, 178 against 179, that is **1 time unit**; on the second, 177 against 175, that is **2 time units**. On this workload, the measurement band's lower bound is the size of the context cost, that is, 2 time units. The first difference is **below** the band and cannot be interpreted; the second sits exactly **at** the boundary and is not enough on its own to establish a ranking. The difference between these two models sits not in the time column but in the **idle core steps** column. On the first workload, the event loop spends **139** idle core steps, message passing **639**. To get the same time, message passing uses **four cores**; the event loop, **one**. Time is equal, but the resource is four and a half times as much. A ranking claim cannot be established, but a **cost comparison can be**: on this workload, message passing's four cores produce no gain in time. #### What the Workload's Composition Changes The two workloads carry the same five processes in different compositions: the first has **39 compute, 21 wait**; the second has **46 compute, 14 wait**. The second is more compute-heavy. As the compute share grows, message passing improves relatively: on the first workload it trails the event loop by 1 time unit, on the second it moves 2 time units ahead. The direction is the expected one — adding cores parallelizes compute, not waiting. But the **magnitude sits at the boundary of the measurement band**, and in this course such a difference is not converted into a claim of superiority. The context-switch column speaks more clearly. On the second workload, the thread model produces **22** context switches, the event loop **14**, message passing **12**. The cost of preemption shows up directly here. Average turnaround diverges too: on the second workload, the thread model gives **122.20**, the other two **98.00**. While the difference in overall time cannot be measured, individual jobs' finish times diverge measurably — **which metric is asked determines which model wins.** #### The Correctness Axis Time is not the only axis. The three models give **three separate guarantees** in answer to the same shared-counter question. ```python def counter_run(pattern: list[int]) -> int: counter, local = 0, {0: None, 1: None} stage = {0: 0, 1: 0} for who in pattern: s = stage[who] if s == 0: local[who] = counter elif s == 1: local[who] = local[who] + 1 else: counter = local[who] stage[who] = s + 1 return counter def interleavings(a: int, b: int) -> list[list[int]]: if a == 0: return [[1] * b] if b == 0: return [[0] * a] return ([[0] + s for s in interleavings(a - 1, b)] + [[1] + s for s in interleavings(a, b - 1)]) def quantum_interleavings(steps: int, quantum: int) -> list[list[int]]: result = [] def walk(remaining_a, remaining_b, current, sequence): if not remaining_a and not remaining_b: result.append(list(sequence)) return for candidate in (0, 1): remaining = remaining_a if candidate == 0 else remaining_b if not remaining: continue n = min(quantum, remaining) sequence.extend([candidate] * n) walk(remaining_a - n if candidate == 0 else remaining_a, remaining_b - n if candidate == 1 else remaining_b, candidate, sequence) del sequence[len(sequence) - n:] walk(steps, steps, None, []) distinct = [] for d in result: if d not in distinct: distinct.append(d) return distinct print("model shared state critical section splits reachable wrong") for name, shared, splits in (("thread", "yes", True), ("event loop", "yes", False), ("message passing", "no", None)): if shared == "no": # a single owner changes the counter, no interleaving occurs print(f" {name:16s} {shared:12s} {'-':>24s} {'-':>9s} {'-':>5s}") continue reachable = interleavings(3, 3) if splits else quantum_interleavings(3, 3) wrong = sum(1 for d in reachable if counter_run(d) != 2) print(f" {name:16s} {shared:12s} {str(splits):>24s} {len(reachable):9d} {wrong:5d}") ``` ``` model shared state critical section splits reachable wrong thread yes True 20 18 event loop yes False 2 0 message passing no - - - ``` In the thread model, the critical section can be split; if unprotected, **18 of the 20 interleavings** produce a wrong result. If protected, correctness follows, and its cost was already counted in the previous lessons: at four threads, time rises from 29 to 47 and waiting from 18 to 54. In the event loop model, the critical section **cannot be split**: the run-to-completion rule structurally forbids another task from running in the middle of one. Reachable interleavings are **2**, wrong is **0**, and this is **different in kind** from the quantum setting in the first lesson — there, the protection was a setting; here, it is the model's definition. In exchange, the same rule brings a limit: a long compute step holds up the entire queue, and the model cannot go beyond a single core. In the message passing model, the question **cannot be asked**: a single owner changes the counter, and the other side sends a message. Because there is no shared mutable state, there is no critical section, no lock, and no memory visibility problem. Deadlock does not disappear outright, though; it changes shape. If queue capacity is bounded, or if each side waits on the other's message, a **communication deadlock** can arise; the job list in this definition contains no such wait. Its cost sits somewhere unmeasured — **copying** state on every message (CC29). #### The Models Do Not Exclude One Another That the three models are three settings of the same scheduler is not just a measurement convenience; it is a structural observation. The settings are independent of one another and can be mixed. The most visible example of this is in the table. The event loop setting is single-core; the message passing setting is four-core and isolates state. Combining the two means running **one event loop per core** and sending only messages between them. This combination is not a new model; it is choosing two settings at once. In the same way, the thread model can be combined with isolation: shared state is left only where it genuinely needs to be shared, and the rest is kept private to each thread. As the critical section shortens, contention drops, and this drop was already measured in the second lesson — at eight threads, as the critical share fell from 0.50 to 0.05, time dropped from 83 to 20. The rule that follows is this: **a model is not a flag, it is a set of settings.** The question to ask is not "which model" but "which state will be shared, will there be preemption, how many cores will be used." Each of these has had its cost counted separately in this topic. #### What Choosing a Model Actually Chooses | Model | Time (39/21) | Time (46/14) | Idle core | Correctness guarantee | |---|---|---|---|---| | Thread | 197 | 202 | 108 / 112 | none, built with a lock | | Event loop | 178 | 177 | 139 / 131 | run-to-completion | | Message passing | 179 | 175 | 639 / 630 | no sharing | The one general conclusion that can be drawn from the table is that **the thread model gives the worst time on both workloads**. The difference between the other two models sits within or at the boundary of the measurement band on both workloads; in this course, such a difference **counts as unmeasured**. The choice, then, is not made on time. What is chosen is **which cost will be paid**: contention and deadlock risk in the thread model, the single-core limit in the event loop, copying and four and a half times the idle core steps in message passing. #### Summary - When the three models are measured on the same workload, the thread model gives the worst time on both workloads: 197 and 202. - The time difference between the event loop and message passing is 1 and 2 time units; it sits below or at the boundary of the measurement band and is not enough to establish a ranking. - The difference shows up in idle core steps: for the same time, the event loop spends 139 idle core steps, message passing 639. - The correctness guarantees differ in kind: the thread model has none and it is built with a lock; the event loop's comes from run-to-completion; in message passing the question cannot even be asked, since there is no sharing. - Which metric is asked changes the winner: on the second workload, while the time difference cannot be measured, average turnaround diverges at 122.20 against 98.00. #### Next Step This topic counted concurrency's cost on three axes: waiting steps, deadlock ratio, and the reachable interleaving set. All of them shared one assumption: that memory is unlimited and access is free — a compute step always took one time unit. The next topic removes that assumption. Memory is finite, the address space is larger than the physical one, and an access may have to wait for a page coming from disk. The first lesson will take the 39-access sequence this workload produces, sweep three page-replacement procedures across 15 distinct virtual pages, and show that a smarter procedure does not always pay off. ## Memory and Storage Virtual memory and page replacement, heap allocation and fragmentation, garbage collection pauses, file system abstraction, and input/output models. ### Virtual Memory Source: https://academia.sh/en/courses/operating-system-concepts/virtual-memory The three costs of paged memory: address translation, page faults, and the choice of page replacement policy — measured by sweeping the physical page count over a 39-access sequence. The concurrency topic measured three models on the same workload, and all three silently assumed one thing: every address a process touches is already sitting in memory. Hardware gives no such guarantee. A process's address space can exceed the machine's physical memory, and when five processes run at once, their combined footprint almost always does. This lesson builds the abstraction that closes that gap and counts its cost. The Memory Layout lesson in How Computers Work already defined the address space, the stack, and the heap; that definition is not repeated here. The one addition is this: when the address space does not sit directly on real memory, every access passes through a translation, every translation that comes up empty produces a **page fault**, and page faults can be counted. #### Virtual Pages and Physical Pages **Virtual memory** is the abstraction that separates the address space a process sees from the machine's physical memory. The separation is built on fixed-size units: the address space is divided into equal-size **virtual pages**, physical memory into equal-size **physical pages**, and a **page table** tracks which virtual page sits in which physical page. This arrangement is called **paging**. The baseline without the abstraction states itself in one sentence: if there are as many physical pages as virtual pages, the mapping is one-to-one, the table is never searched, and after the first load no access ever goes to disk. In the common definition's workload the address space is 16 virtual pages, and the access sequence produced by five processes touches 15 of them. The baseline is fetching those 15 pages once. - **BD1** — The machine is the common definition's model: a 16-virtual-page address space, a five-process workload, and seed 20260218. No real operating system is invoked. - **BD2** — The access sequence is produced from the processes' compute steps in time order; wait steps never touch memory. - **BD3** — Fetching a page from disk is one wait step, that is, **30 time units**. A compute step is one time unit. - **BD4** — Page table lookup is free in the model; the only thing measured is faults. On a real machine, table lookup would also carry a cost, and this lesson does not count it. ```python """M01/K05 common definition (excerpt): workload and virtual page access sequence.""" SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_TIME = 30 VIRTUAL_PAGES = 16 def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def workload(seed=SEED): r = generator(seed) jobs = [] for i in range(PROCESS_COUNT): steps = [] for _ in range(STEP_COUNT): if r(10) < 3: steps.append(("WAIT", WAIT_TIME)) else: base = (i * 3) % VIRTUAL_PAGES steps.append(("COMPUTE", (base + r(4)) % VIRTUAL_PAGES)) jobs.append({"name": f"P{i+1}", "step": steps, "priority": 1 + r(3), "arrival": i * 4}) return jobs def access_sequence(jobs): events = [] for j in jobs: t = j["arrival"] for kind, value in j["step"]: if kind == "COMPUTE": events.append((t, value)) t += 1 else: t += value events.sort(key=lambda e: e[0]) return [s for _, s in events] SEQUENCE = access_sequence(workload()) print("accesses:", len(SEQUENCE), "| distinct virtual pages:", len(set(SEQUENCE))) print("sequence:", SEQUENCE) for window in (4, 8, 16): widths = [len(set(SEQUENCE[i:i + window])) for i in range(len(SEQUENCE) - window + 1)] print(f"window {window:2d} working set average {sum(widths)/len(widths):5.2f} " f"widest {max(widths):2d}") ``` ``` accesses: 39 | distinct virtual pages: 15 sequence: [6, 9, 11, 9, 11, 9, 12, 1, 3, 1, 6, 9, 7, 9, 0, 2, 0, 5, 2, 3, 0, 5, 2, 3, 5, 3, 8, 9, 6, 4, 13, 12, 15, 13, 8, 12, 14, 12, 7] window 4 working set average 3.47 widest 4 window 8 working set average 5.75 widest 8 window 16 working set average 9.25 widest 11 ``` The last three lines give the **working set**: the number of distinct pages touched inside a window. In a four-access window the average is 3.47 distinct pages, meaning nearly every one of the four accesses lands on a different page. The locality defined in the Processor Cache lesson produces a direct number here, and this workload's locality is weak: in the widest eight-access window, all eight accesses touch eight distinct pages — no repetition at all. Weak locality determines from the outset how sensitive the fault count will be to the number of physical pages. #### Address Translation A virtual address splits into two parts: which virtual page it falls in, and which byte inside that page it is. The second part is called the **page offset**. If the page size is 256 bytes, translation is two divisions — the page number is the address divided by 256, the offset is the remainder. The physical address is the physical page number the page table returns, combined with the same offset. - **BD5** — Page size is 256 bytes, physical page count is 4. The first ten steps of the access sequence are used; each step's page offset is fabricated, the page number comes from the common definition. - **BD6** — When no free physical page remains, the first-in-first-out rule applies. ```python """Address translation: virtual address -> virtual page + offset -> physical address.""" PAGE_SIZE = 256 PHYSICAL = 4 FIRST = [6, 9, 11, 9, 11, 9, 12, 1, 3, 1] # first ten steps of the access sequence table, order = {}, [] # virtual page -> physical page print("virtual addr virtual page offset status physical physical addr") for k, virtual in enumerate(FIRST): addr = virtual * PAGE_SIZE + (k * 23) % PAGE_SIZE page, offset = divmod(addr, PAGE_SIZE) if page in table: status = "resident" else: status = "page fault" if len(order) == PHYSICAL: table.pop(order.pop(0)) free = min(set(range(PHYSICAL)) - set(table.values())) table[page] = free order.append(page) print(f"{addr:11d} {page:11d} {offset:5d} {status:12s} {table[page]:8d}" f" {table[page] * PAGE_SIZE + offset:14d}") print("page table:", dict(sorted(table.items()))) ``` ``` virtual addr virtual page offset status physical physical addr 1536 6 0 page fault 0 0 2327 9 23 page fault 1 279 2862 11 46 page fault 2 558 2373 9 69 resident 1 325 2908 11 92 resident 2 604 2419 9 115 resident 1 371 3210 12 138 page fault 3 906 417 1 161 page fault 0 161 952 3 184 page fault 1 440 463 1 207 resident 0 207 page table: {1: 0, 3: 1, 11: 2, 12: 3} ``` Ten accesses, six faults. Two points are worth watching. First, the offset never changes across translation: address 2327 had offset 23, its physical counterpart is 279, and 279 divided by 256 also leaves a remainder of 23. When the page size is chosen as a power of two, this division collapses to a bit split and no division is ever performed. Second, on the eighth line virtual page 6 is evicted and virtual page 1 lands in that same physical page; the process's view of the address did not change, what changed was the physical location under it. That is what the abstraction provides, and the fault on that line is what it costs. #### The Page Table's Own Cost If the page table holds a mapping, that mapping has to sit somewhere, and that somewhere is memory. The model's table has 16 entries because the address space is 16 virtual pages. The entry count is the address space divided by the page size, and when both are chosen as powers of two this too collapses to a subtraction. - **BD7** — A table entry is assumed to hold 8 bytes; the entry carries the physical page number, the validity bit, and the access flags. ```python """The page table's own cost: entry count grows with the address space.""" ENTRY_BYTES = 8 # bytes held per table entry print("address bits page size entry count single-level table (bytes)") for addr_bits, page_bits in ((12, 8), (22, 12), (32, 12), (48, 12)): entries = 2 ** (addr_bits - page_bits) print(f"{addr_bits:12d} {2 ** page_bits:9d} {entries:11d} {entries * ENTRY_BYTES:26d}") ``` ``` address bits page size entry count single-level table (bytes) 12 256 16 128 22 4096 1024 8192 32 4096 1048576 8388608 48 4096 68719476736 549755813888 ``` The first row is this lesson's model: a 12-bit address space, a 256-byte page, 16 entries, a 128-byte table. The fourth row shows how the abstraction behaves at scale — with a 48-bit address space, a single-level table demands a place larger than the memory it represents, and one is needed per process. The applied fix is to split the table into levels: the top-level table only points to used ranges, and no sub-table is ever allocated for an unused range. This costs multiple table reads per translation — the abstraction makes you pay in steps once again. #### Three Policies, One Sequence When a physical page fills up, a **page replacement** policy decides which page to evict. Three policies are measured: **first in first out**, **least recently used**, and **optimal replacement** — the last one evicts the page whose next use is furthest away, that is, it knows the future. ```python """Three page replacement policies on the same access sequence. Sequence is the output of block 01.""" SEQUENCE = [6, 9, 11, 9, 11, 9, 12, 1, 3, 1, 6, 9, 7, 9, 0, 2, 0, 5, 2, 3, 0, 5, 2, 3, 5, 3, 8, 9, 6, 4, 13, 12, 15, 13, 8, 12, 14, 12, 7] FETCH = 30 # a page fault is one wait step def page_fault(sequence, physical, policy="fifo"): """policy: fifo | lru | optimal (looks ahead at the future)""" resident, order, faults = [], [], 0 for k, s in enumerate(sequence): if s in resident: if policy == "lru": order.remove(s) order.append(s) continue faults += 1 if len(resident) < physical: resident.append(s) order.append(s) continue if policy in ("fifo", "lru"): evicted = order.pop(0) else: distance = {} for y in resident: distance[y] = sequence.index(y, k + 1) if y in sequence[k + 1:] else 10**9 evicted = max(resident, key=lambda y: distance[y]) order.remove(evicted) resident.remove(evicted) resident.append(s) order.append(s) return faults compulsory = len(set(SEQUENCE)) print("accesses", len(SEQUENCE), "| compulsory faults:", compulsory, "| baseline duration:", len(SEQUENCE) + compulsory * FETCH) print("physical fifo lru optimal fifo extra fifo duration") for f in (2, 3, 4, 5, 6, 8, 15): a = page_fault(SEQUENCE, f, "fifo") b = page_fault(SEQUENCE, f, "lru") c = page_fault(SEQUENCE, f, "optimal") print(f" {f:6d} {a:4d} {b:3d} {c:7d} {a - compulsory:11d}" f" {len(SEQUENCE) + a * FETCH:13d}") ``` ``` accesses 39 | compulsory faults: 15 | baseline duration: 489 physical fifo lru optimal fifo extra fifo duration 2 30 31 27 15 939 3 28 28 23 13 879 4 23 23 19 8 729 5 23 22 18 8 729 6 20 20 17 5 639 8 19 17 15 4 609 15 15 15 15 0 489 ``` Three numbers sit side by side. **Baseline:** 15 physical pages, 15 compulsory faults, 489 time units. **Setup:** 2 physical pages, first in first out, 30 faults. **Cost:** 15 extra faults and 939 − 489 = 450 time units. On this workload, the virtual memory abstraction shrinks memory by a factor of seven and a half in exchange for stretching runtime to 1.92 times its baseline. The table lays bare where the cost comes from. Thirty of the 39 accesses end in a fault, so roughly three quarters of accesses hit disk and the machine spends more time fetching pages than computing. This condition is called **thrashing**: once the physical page count drops below the working set, every new access evicts a page that will be requested again shortly after. The working-set measurement already predicted this — at an average of 3.47 distinct pages per four-access window, running with two physical pages means refetching half the window on every turn. #### A Smarter Policy Does Not Always Pay Off Least recently used uses more information than first in first out: it tracks when each page was last touched. Even so, at two physical pages it produces **31** faults against first in first out's **30**. The policy that uses more information produces one more fault at this point. How this difference is read matters. The common definition's resolution rule is this: at 39 accesses, a one-fault difference is a ratio of 0.0256 and **counts as unmeasured**; a meaningful difference is at least three faults. So the sentence "least recently used is worse" cannot be written either. Reading the table by this criterion makes the result even clearer: the gap between the two policies never reaches three in any row — the largest is 19 against 17 at eight physical pages, a gap of two. **This workload has not measured an advantage for least recently used.** An implementation that chooses it pays the cost of keeping a timestamp per page for nothing. The same criterion applies to adding physical pages. Going from 3 to 4 drops first in first out from 28 to 23: five faults, meaningful. Going from 4 to 5 leaves it at 23: zero. One more physical page buys nothing here. Going from 5 to 6 wins back three faults. The return on adding a resource does not decline smoothly, it steps, and where the step falls depends on the workload's access pattern. #### Why the Optimal Baseline Is Unreachable The third column sits below the other two on every row: 27 at 2 pages, 15 at 8 pages. At eight physical pages, 15 faults equals the compulsory fault count — meaning the optimal policy never refetches a single page at eight pages. This column is not a policy, it is a **lower bound**. Choosing which page to evict requires reading the rest of the access sequence — the addresses a not-yet-run program will produce. A scheduler does not know at translation time which process it will interrupt and when, which data a user will request, or which way a branch will go. The lower bound's role is not to be implemented but to measure: at eight physical pages, first in first out's 19 faults are four faults away from the bound's 15, and that gap is the entire remaining room for improvement. #### Summary - Virtual memory separates the address space a process sees from physical memory through fixed-size pages; every access splits into a virtual page number and a page offset and gets translated. - The common definition's 39-access sequence touches 15 distinct virtual pages; the baseline is 15 compulsory faults and 489 time units, the two-physical-page setup is 30 faults and 939 time units, the cost is 450 time units. - Thrashing starts once the physical page count drops below the working set: 30 of 39 accesses hit disk and the machine fetches pages more than it computes. - The gap between least recently used and first in first out never reaches three faults at any physical page count; on this workload, no measured advantage exists between the two. - The return on adding physical pages steps: going from 3 to 4 wins five faults, going from 4 to 5 wins nothing. #### Next Step This lesson distributed memory in fixed-size pages and assumed every request fits one page. That is not true of a process's heap: requests come in different sizes, arrive out of order, and are released out of order. The next lesson models heap management on the same machine and compares two allocation policies on the same event sequence — one rejects a request while the other places all of them, but leaves behind an unusable remainder. ### Memory Allocation Source: https://academia.sh/en/courses/operating-system-concepts/memory-allocation Placing variable-size requests on the heap: the difference between first-fit and best-fit placement on the same event sequence, the moment external fragmentation rejects a request, and the unusable remainder left behind. In the virtual memory lesson every request was the same size: one page. Fixed size removes the placement problem — if a free physical page exists, every virtual page fits there, and which free page gets chosen does not change the outcome. A process's heap is not like that. Requests come in different sizes, arrive out of order, are released out of order, and which free block they land in determines whether later requests fit at all. The Memory Layout lesson in How Computers Work already defined the heap, the allocator, and fragmentation; this lesson does not repeat those definitions. What it adds is measurement: two placement policies run on the same event sequence, and the difference between them is counted in placed requests, bytes left free, and unusable remainder. #### Baseline, Setup, and What Gets Measured The baseline without an allocator is not an allocator at all: the heap holds a single boundary variable, every request pushes the boundary forward by its own size, and there is no such operation as releasing. This arrangement's management cost is one addition; in exchange, freed memory is never reclaimed. The setup adds releasing and reuse. The heap splits into blocks, each block either belongs to a name or is free, a released block returns to free, and adjacent free blocks are merged. What gets measured is this: how many requests does keeping this ledger save, and what does it leave behind. - **BD8** — The heap is 1024 bytes and starts as a single block. The allocator gives exactly the number of bytes requested; there is no alignment or header overhead, so internal fragmentation is zero in this lesson. - **BD9** — The event sequence comes from the common definition: six allocations, two releases, two more allocations. Total requested is 1254 bytes, that is, more than the heap; without releasing, not all of it fits. - **BD10** — Two placement policies are measured. **First fit** picks the first sufficient block in the list; **best fit** picks the smallest of the sufficient blocks. - **BD11** — At release, only **adjacent** free blocks merge; two free blocks apart from each other stay separate. No moving or compaction is performed. ```python """M01/K05 common definition (excerpt): allocator, external fragmentation and the end-to-end baseline.""" HEAP = 1024 EVENTS = [("A", "a", 200), ("A", "b", 150), ("A", "c", 200), ("A", "d", 100), ("A", "e", 200), ("A", "f", 174), ("R", "b"), ("R", "d"), # two free blocks of 150 and 100 bytes ("A", "g", 90), ("A", "h", 140)] def allocate(events, size=HEAP, policy="first_fit"): """events: ("A", name, size) allocate , ("R", name) release.""" block = [{"name": None, "start": 0, "size": size}] # name None means free placed = rejected = 0 for event in events: if event[0] == "A": _, name, want = event candidates = [b for b in block if b["name"] is None and b["size"] >= want] if not candidates: rejected += 1 continue chosen = candidates[0] if policy == "first_fit" else min(candidates, key=lambda b: b["size"]) k = block.index(chosen) left = chosen["size"] - want block[k] = {"name": name, "start": chosen["start"], "size": want} if left: block.insert(k + 1, {"name": None, "start": chosen["start"] + want, "size": left}) placed += 1 else: for b in block: if b["name"] == event[1]: b["name"] = None k = 0 # adjacent free blocks merge while k < len(block) - 1: if block[k]["name"] is None and block[k + 1]["name"] is None: block[k]["size"] += block[k + 1]["size"] block.pop(k + 1) else: k += 1 free = [b["size"] for b in block if b["name"] is None] return {"placed": placed, "rejected": rejected, "free": sum(free), "largest_free": max(free) if free else 0, "block": len(free), "layout": [(b["name"] or "-", b["start"], b["size"]) for b in block]} def end_to_end(events, size=HEAP): """Baseline without allocator: no releasing , only a forward-moving boundary.""" boundary, placed, rejected = 0, 0, 0 for event in events: if event[0] == "A": if boundary + event[2] <= size: boundary, placed = boundary + event[2], placed + 1 else: rejected += 1 return placed, rejected def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def long_sequence(seed, count=200): """Long event sequence: each step is either an allocation or a random release.""" r = generator(seed) events, live, counter = [], [], 0 for _ in range(count): if live and r(10) < 5: events.append(("R", live.pop(r(len(live))))) else: name = f"n{counter}" counter += 1 events.append(("A", name, 16 + r(8) * 16)) live.append(name) return events print("heap", HEAP, "bytes | requests", sum(1 for o in EVENTS if o[0] == "A"), "| total requested", sum(o[2] for o in EVENTS if o[0] == "A")) print("baseline (end-to-end , no releasing): placed %d rejected %d" % end_to_end(EVENTS)) print("policy placed rejected free largest free blocks") for y in ("first_fit", "best_fit"): a = allocate(EVENTS, HEAP, y) print(f" {y:12s} {a['placed']:5d} {a['rejected']:10d} {a['free']:5d}" f" {a['largest_free']:14d} {a['block']:6d}") print(" ", " ".join(f"{name}@{start}+{size}" for name, start, size in a["layout"])) print() print("long sequence (200 events) requests first fit best fit") for seed in (20260218, 20260219): U = long_sequence(seed) requests = sum(1 for o in U if o[0] == "A") i = allocate(U, HEAP, "first_fit") e = allocate(U, HEAP, "best_fit") print(f" seed {seed} {requests:4d} {i['placed']:9d} {e['placed']:9d}") ``` ``` heap 1024 bytes | requests 8 | total requested 1254 baseline (end-to-end , no releasing): placed 6 rejected 2 policy placed rejected free largest free blocks first_fit 7 1 160 100 2 a@0+200 g@200+90 -@290+60 c@350+200 -@550+100 e@650+200 f@850+174 best_fit 8 0 20 10 2 a@0+200 h@200+140 -@340+10 c@350+200 g@550+90 -@640+10 e@650+200 f@850+174 long sequence (200 events) requests first fit best fit seed 20260218 119 96 98 seed 20260219 114 100 99 ``` Three numbers sit side by side. **Baseline:** end-to-end allocation, 6 placed, 2 rejected, and a single boundary variable. **Setup:** an allocator holding a block list, best fit places 8. **Cost:** a block list scanned on every request, a heap split into eight blocks, and two remaining gaps. What releasing buys is plain: the baseline hands out its 1024 bytes once and is done, the allocator reuses the released 250 bytes and satisfies two more requests. But it does not get the full gain — the first-fit policy places only seven of the eight requests. #### External Fragmentation Is a Cause of Rejection When `b` and `d` are released, two free blocks of 150 and 100 bytes appear in the heap. Since neither is adjacent to the other, merging never triggers; 250 bytes are free in total, but no single block holds more than 150. This is called **external fragmentation**: the total of free memory is sufficient, a single block is not. The result shows up in the last two requests. First fit places the 90-byte `g` request in the first sufficient block in the list — the 150-byte one — and leaves 60 bytes behind. The following 140-byte `h` request then finds 60- and 100-byte blocks left: 160 total, which is enough, but neither alone is. ```python """External fragmentation: free total is enough , a single block is not. Layouts are the output of block 01.""" LAYOUT = { "first_fit": [("a", 200), ("g", 90), ("-", 60), ("c", 200), ("-", 100), ("e", 200), ("f", 174)], "best_fit": [("a", 200), ("h", 140), ("-", 10), ("c", 200), ("g", 90), ("-", 10), ("e", 200), ("f", 174)], } for name, layout in LAYOUT.items(): gaps = sorted((b for n, b in layout if n == "-"), reverse=True) free, largest = sum(gaps), gaps[0] print(f"{name:12s} free {free:4d} largest {largest:4d} blocks {len(gaps)}" f" external fragmentation ratio {1 - largest / free:.4f}") for want in (10, 60, 90, 140): print(f" {want:4d}-byte request: free sufficient {free >= want}" f" , single block sufficient {largest >= want}") ``` ``` first_fit free 160 largest 100 blocks 2 external fragmentation ratio 0.3750 10-byte request: free sufficient True , single block sufficient True 60-byte request: free sufficient True , single block sufficient True 90-byte request: free sufficient True , single block sufficient True 140-byte request: free sufficient True , single block sufficient False best_fit free 20 largest 10 blocks 2 external fragmentation ratio 0.5000 10-byte request: free sufficient True , single block sufficient True 60-byte request: free sufficient False , single block sufficient False 90-byte request: free sufficient False , single block sufficient False 140-byte request: free sufficient False , single block sufficient False ``` First fit's rejection is not a memory shortage; a 140-byte request is turned away while 160 bytes stand free. The external fragmentation ratio — the share of free memory outside the largest block — is 0.3750 here. Best fit places both of the same requests. It puts the 90-byte `g` request into the 100-byte gap, leaving 10 bytes, and the 140-byte `h` request into the 150-byte gap, again leaving 10 bytes. All eight requests are placed, none rejected. But the two remaining gaps are 10 bytes each, and the external fragmentation ratio has climbed to 0.5000: 20 bytes appear free, yet not even an 11-byte request can be satisfied. **Unusable memory is a different line item from unused memory**, and a metric that looks only at the total of free bytes does not show it. #### Best Fit Does Not Always Pay Off The gap between seven placed requests and eight invites reading best fit as a general rule. The last block of output tests that: the same allocator, on two separate 200-event sequences. In the first workload, first fit places 96 of 119 allocation requests, best fit places 98. Best fit is two requests ahead. In the second workload, first fit places 100 of 114, best fit places 99; this time first fit is one request ahead. **The ranking flips with the workload.** The differences themselves are small too: two and one request, roughly a two-percent swing on about a hundred requests. Taken together these two observations give a single conclusion: **no advantage between the two policies has been established in this measurement.** What has been established is that on the eight-event sequence, best fit places one more request and leaves behind a more unusable remainder in exchange. Which policy wins depends on the workload's size distribution and release pattern; a ranking measured on a single sequence counts as unmeasured. There is also a cost this model does **not** count. This implementation scans the entire block list on every request, so the two policies come out with equal search cost. A real first-fit implementation can stop as soon as it finds the first sufficient block; best fit cannot, because it can only know whether a smaller sufficient block exists once it has finished the list. This difference was not measured in this lesson, and because it was not measured, it is not written down as grounds for an advantage. #### Why Compaction Is Not Free External fragmentation has an exact fix: slide the resident blocks toward the start of the heap and collect all the gaps into one. This is called **compaction**, and it rescues the request first fit rejected. - **BD12** — Compaction is performed only as a measurement; moving a block counts as copying that block's bytes to its new location. ```python """The cost of compaction: how many bytes moving to collect gaps into one block costs.""" LAYOUT = [("a", 0, 200), ("g", 200, 90), ("-", 290, 60), ("c", 350, 200), ("-", 550, 100), ("e", 650, 200), ("f", 850, 174)] # first-fit result boundary, moved, moved_block = 0, 0, 0 for name, start, size in LAYOUT: if name == "-": continue if start != boundary: moved += size moved_block += 1 boundary += size print("resident bytes:", boundary, "| gap collapsed into one:", 1024 - boundary) print("blocks moved:", moved_block, "| bytes moved:", moved) print("does the 140-byte request fit after compaction:", 1024 - boundary >= 140) ``` ``` resident bytes: 864 | gap collapsed into one: 160 blocks moved: 3 | bytes moved: 574 does the 140-byte request fit after compaction: True ``` The rejected request is rescued, but the cost is copying 574 bytes — two thirds of the 864 bytes resident in the heap. This is a task on a scale incomparable to allocation itself, and it is paid for a single request. The second and heavier cost is not the copying. Every block that moves changes address, so every reference pointing to that block must change too. In a layout where addresses are held directly as numbers, there is no way to know which number is a pointer and which is data, so compaction cannot be applied. In layouts where it can be, a block is reached not directly but through an indirection table; then moving reduces to changing one row in the table, but from that point on **every access** pays one extra table read. The step the abstraction charges does not disappear, it only changes location. #### Internal Fragmentation Does Not Enter Here The allocator hands out exactly the number of bytes requested: request 90, get 90 bytes allocated. So internal fragmentation is zero in this lesson, and the table has no such column. It exists in every layout that works with fixed-size units — in the virtual memory lesson, a page not filled to its last byte is internal fragmentation, and in the file system, a block half left empty is too. The two fragmentations are each other's counterpart: fixed size removes external fragmentation and puts internal fragmentation in its place; variable size removes internal fragmentation and puts external fragmentation in its place. The fourth lesson will measure the other end of this trade-off in bytes. #### Summary - The end-to-end baseline places 6 of 8 requests and never uses releasing; the allocator holding a block list reuses the released 250 bytes and satisfies one or two more requests. - First fit places 7 requests and rejects one: a 140-byte request is turned away while 160 bytes stand free, because the largest single block is 100 bytes. That is external fragmentation. - Best fit places all 8 requests but leaves behind two 10-byte gaps; the external fragmentation ratio climbs from 0.3750 to 0.5000 and the remaining 20 bytes are unusable. - The ranking flips across two separate 200-event sequences: best fit is two requests ahead in the first workload, first fit is one request ahead in the second. No advantage between the two policies has been measured. - In this model both policies scan the entire block list; the search-cost difference was not measured and is not used as grounds. #### Next Step In this lesson the program itself performed the releasing: `b` and `d` were released, their space reclaimed. A program that forgets to release leaks memory; one that releases too early uses a freed address. The next lesson models the arrangement that hands this decision from the program to the runtime: a collector working by a reachability criterion decides which of 40 objects stay alive, and the cost of that is a pause. The question to measure is whether the length of the pause is proportional to the garbage collected, or to the objects that survive. ### Garbage Collection Source: https://academia.sh/en/courses/operating-system-concepts/garbage-collection Handing the release decision to the runtime, and its cost: reachability sweeps a 40-object graph, the pause is proportional to the surviving objects, and the pause shrinks as more garbage is collected. In the previous lesson the program itself made the release decision: `b` and `d` were released and their space reclaimed. That decision has two ways of going wrong. A block that is never released stays unusable until the program ends. An address used after release reads or writes memory that has since been handed to another request. Neither shows up in the source text; both surface only at runtime. This lesson models the arrangement that takes the decision away from the program and hands it to the runtime. The handoff requires a criterion — not which object is still needed, but which one is **reachable**. Mark and sweep itself, along with the reachability criterion, was already established earlier in this catalog, in the Garbage Collection lesson of the Memory and Performance topic in the Asynchronous JavaScript and the Runtime course, and is not repeated here. What this lesson adds is measurement alone: how many steps does the handoff cost, and what does that step count depend on. #### Baseline, Setup, and the Name of the Cost The baseline without an abstraction is manual release. There is no collector, no scan, no pause; a block's lifetime is written into the program text. Its cost is paid not at runtime but in correctness. The setup is a **tracing garbage collector**. Starting from the root set, references are followed, every object reached is marked; unmarked objects have their space reclaimed. The name of the cost is **pause**, and in this lesson a pause is not a duration but a step count: how many objects were scanned. - **BD13** — The object graph is the common definition's model: 40 objects, seed 20260218, root set the first three objects. Links come from the generator and are the same on every run. - **BD14** — Scanning one object is one step; an object's size and the number of links it carries do not change the step count. - **BD15** — Collection runs in one pass with the program fully stopped. There is no incremental or concurrent collection in this model. - **BD16** — Sweeping walks the entire object list once to reclaim unmarked objects' space; this too is one step per object. ```python """M01/K05 common definition (excerpt): object graph , reachability and mark-and-sweep.""" SEED = 20260218 def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def object_graph(seed=SEED, n=40, roots=3): r = generator(seed) links = {i: [] for i in range(n)} for i in range(n): for _ in range(r(3)): h = r(n) if h != i and h not in links[i]: links[i].append(h) return links, list(range(roots)) def mark_and_sweep(links, roots): seen, stack, scan = set(), list(roots), 0 while stack: d = stack.pop() if d in seen: continue seen.add(d) scan += 1 for h in links[d]: stack.append(h) return {"reachable": len(seen), "collected": len(links) - len(seen), "scan": scan} G, K = object_graph() print("objects:", len(G), "| links:", sum(len(v) for v in G.values()), "| roots:", len(K)) print("baseline measurement:", mark_and_sweep(G, K)) print() print("roots reachable collected marking sweeping total work per collected") for roots in (1, 2, 3, 4, 6, 8, 12): g, k = object_graph(roots=roots) r = mark_and_sweep(g, k) total = r["scan"] + len(g) print(f"{roots:5d} {r['reachable']:9d} {r['collected']:9d} {r['scan']:7d}" f" {len(g):8d} {total:10d} {total / r['collected']:13.2f}") ``` ``` objects: 40 | links: 44 | roots: 3 baseline measurement: {'reachable': 17, 'collected': 23, 'scan': 17} roots reachable collected marking sweeping total work per collected 1 3 37 3 40 43 1.16 2 7 33 7 40 47 1.42 3 17 23 17 40 57 2.48 4 19 21 19 40 59 2.81 6 21 19 21 40 61 3.21 8 23 17 23 40 63 3.71 12 25 15 25 40 65 4.33 ``` Three numbers sit side by side. **Baseline:** manual release, 0 scan steps, 0 pause. **Setup:** a tracing collector with three roots, **17 of 40 objects reachable**, 23 collected. **Cost:** a **17-step pause** followed by a 40-step sweep pass, 57 steps total. Notice that reachability is a traversal: starting from the root set, following links, walking without revisiting what it has already seen. The graph traversal from the Data Structures course is not redefined here, it is invoked directly; the only novelty is that the visit count is counted as a cost. What the root set is also reads from the arrangement this course built. In the address space from the Memory Layout lesson, the places the collector counts as "starting points" are settled: the local variables sitting on each thread's own stack, the global variables in the initialized and uninitialized data segments, and the references currently held in registers. These three are not a list the process's own code hands over by name; they are read from the address space's structure. In the model, this same set is the `roots` parameter, and its size is directly a cost item — the traversal deepens as the root count grows. Nothing outside the roots is ever a starting point; so a cluster of objects that reference each other but are cut off from the roots gets collected regardless of how many links it carries. #### What the Pause Is Proportional To Reading the table's first two columns together produces an unexpected pattern. At a root count of 1, 37 objects are collected and the pause is 3 steps. At a root count of 12, only 15 objects are collected and the pause is 25 steps. **As the garbage collected shrinks, the pause grows.** This inverse relation is not a coincidence, it follows from the method's own definition: marking visits only reachable objects. A dead object is never visited — it was already unreachable. The construction below isolates the same relation independently of the common definition's graph: the surviving object count is held fixed while the dead object count is multiplied by thirty. ```python """What the pause is proportional to: surviving objects fixed , garbage variable.""" def mark_and_sweep(links, roots): seen, stack, scan = set(), list(roots), 0 while stack: d = stack.pop() if d in seen: continue seen.add(d) scan += 1 for h in links[d]: stack.append(h) return {"reachable": len(seen), "collected": len(links) - len(seen), "scan": scan} def construct(alive, dead): """Survivors are reached by a chain from the root , dead objects are linked among themselves.""" links = {i: [] for i in range(alive + dead)} for i in range(alive - 1): links[i].append(i + 1) for j in range(alive, alive + dead): links[j].append(alive + (j - alive + 1) % dead) return links, [0] print("alive dead total marking sweeping collected") for alive, dead in ((8, 32), (8, 152), (8, 992), (32, 8), (200, 8)): g, k = construct(alive, dead) r = mark_and_sweep(g, k) print(f" {alive:5d} {dead:4d} {len(g):5d} {r['scan']:7d}" f" {len(g):8d} {r['collected']:9d}") ``` ``` alive dead total marking sweeping collected 8 32 40 8 40 32 8 152 160 8 160 152 8 992 1000 8 1000 992 32 8 40 32 40 8 200 8 208 200 208 8 ``` In the first three rows, the surviving count is fixed at 8 and the dead count climbs from 32 to 992; the marking step **stays at 8**. In the last two rows, the dead count is fixed at 8 and the surviving count climbs from 32 to 200; the marking step climbs **from 32 to 200**. That is the lesson's sentence: **the length of the pause is proportional not to the garbage collected, but to the objects that survive.** The practical consequence is direct. A program that produces many short-lived objects does not cost the collector much; those objects are never visited at all. What is expensive is a large, long-lived object structure — it gets rescanned from end to end on every collection and is never collected. #### Sweeping's Share If marking is proportional to survivors, sweeping is proportional to the total: reclaiming unmarked objects' space requires walking the entire list once. In the table, the sweeping column is 40 in every row, because the object count never changes. Total work is the sum of the two, and the last column reduces it to a per-collected-object figure. At a root count of 1, 1.16 steps are spent per collected object; at a root count of 12, 4.33 steps. The gap is 3.7-fold, and all of it comes from the rise in the surviving object count. The collector's efficiency depends on how much garbage sits in the heap — the more garbage, the cheaper the collection. Sweeping's share in this model is also worth noting: in the three-root run, 40 of the total work is sweeping, 17 is marking. So the larger part of the pause comes not from scanning but from walking the list. A collector that copies objects next to the survivors while reclaiming space removes this pass entirely, paying only the 17 steps; in exchange it must move every surviving object and update every reference that points to it. This trade-off is the same one as compaction in the previous lesson. Sweeping also has an end that stays out of view. The bytes of the 23 reclaimed objects go back to the heap, that is, they are handed over to the previous lesson's allocator; from there the rules of external fragmentation take over. The collector decides which object dies; the order of death decides where and at what size the next gap opens. So garbage collection does not replace an allocator, it is built on one, and it inherits the remainder problem measured in the previous lesson. This is also why a copying collector is willing to pay for moving: by laying the objects it moves end to end, it reduces allocation back down to sliding a single boundary. #### Splitting the Pause A pause that takes 17 steps in one piece can be shrunk by splitting marking into chunks and giving the program turns in between. It is not free: because the program runs between two chunks, the object graph can change, so the changed region has to be rescanned. - **BD17** — After every interruption, 2 objects need rescanning. This number is the model's parameter; in a real implementation it would depend on how many references the program changes during the interruption. ```python """Incremental collection: the cost of splitting the pause. Survivors 17 , total 40.""" ALIVE = 17 # reachable object count measured by block 01 TOTAL = 40 RESCAN = 2 # objects needing rescan after each interruption print("chunks pause count longest pause marking work total work") for chunks in (17, 8, 4, 2, 1): count = -(-ALIVE // chunks) marking = ALIVE + (count - 1) * RESCAN print(f"{chunks:6d} {count:12d} {min(chunks, ALIVE):13d}" f" {marking:13d} {marking + TOTAL:11d}") ``` ``` chunks pause count longest pause marking work total work 17 1 17 17 57 8 3 8 21 61 4 5 4 25 65 2 9 2 33 73 1 17 1 49 89 ``` The longest pause drops from 17 steps to 1, total work climbs from 57 steps to **89**. What is gained is not total cost but the distribution of cost: instead of stopping for 17 steps at once, the program stops 17 times for one step each, advancing in between. A metric that looks at response time calls this an improvement; a metric that looks at total work calls it a 1.56 times worsening. **Both are correct, and which one matters depends on the metric** — this is where the course's second claim gets paid in this lesson. #### How Often to Collect When the collector runs is also a decision, and it pits two costs against each other. Collecting early keeps the heap small but runs the collector often; collecting late runs the collector rarely but raises the heap's peak. - **BD18** — The program produces 200 objects, and each object becomes unreachable 30 steps after it is produced. Lifetime is fixed; a real program would have a distribution. ```python """Collection frequency: the trade-off between memory peak and collector work.""" OBJECTS = 200 # how many objects are produced LIFETIME = 30 # steps after which an object becomes unreachable print("every N allocations collections marking work sweeping work peak resident") for n in (10, 25, 50, 100, 200): resident, peak, collections, marking, sweeping = [], 0, 0, 0, 0 for t in range(OBJECTS): resident.append(t) peak = max(peak, len(resident)) if (t + 1) % n == 0: alive = [i for i in resident if t < i + LIFETIME] collections += 1 marking += len(alive) sweeping += len(resident) resident = alive print(f"{n:20d} {collections:11d} {marking:13d} {sweeping:14d} {peak:13d}") ``` ``` every N allocations collections marking work sweeping work peak resident 10 20 570 740 40 25 8 235 405 55 50 4 120 290 80 100 2 60 230 130 200 1 30 200 200 ``` A setup that collects every ten allocations keeps the heap at 40 objects at most and costs the collector 1310 steps. A setup that collects only at the end pays 230 steps but the heap grows to 200 objects. A five-times-lower memory peak is bought in exchange for 5.7 times more collector work. Every point between these two extremes is a valid choice, and what decides the choice is whether memory or the processor is scarce on the machine. #### What Is Reachable Is Not Collected The criterion is not "is it needed" but "can it be reached," and this distinction names the problem the collector does not solve. When the root count climbs from 3 to 12, the collected object count drops from 23 to 15; nothing changed in the graph, only the region reachable from the roots grew. In a program, this corresponds to holding an object that is no longer used in a list or a map: the object is unnecessary, it is reachable, and it is not collected. That is why garbage collection does not eliminate memory leaks, it changes the leak's **form**. Under manual release, a leak is a forgotten release call; under tracing collection, a leak is a reference that is never cut from the roots. In both cases the leak is a program defect, and its diagnosis is sought in the program. #### Summary - The tracing collector reaches 17 of 40 objects from three roots and collects 23; the pause is 17 scan steps, sweeping is 40 steps, total work is 57 steps. - With the surviving object count fixed, raising the dead object count from 32 to 992 leaves the marking step at 8; with the dead count fixed, raising the surviving count from 32 to 200 raises the step from 32 to 200. - The pause is proportional to surviving objects, not to garbage collected; the cost per collected object climbs from 1.16 to 4.33 steps while the only thing that changes is the surviving object count. - The sweep pass is proportional to the total object count and is the larger share of total work in this model; a copying collector removes this pass, paying for moving and reference updates in exchange. - Splitting marking into chunks drops the longest pause from 17 steps to 1 but raises total work from 57 to 89 steps; raising collection frequency drops the memory peak from 200 to 40 objects while raising collector work from 230 steps to 1310. - The criterion is reachability, not necessity; an unneeded object that has not been cut off from a root is never collected, which is why a collector does not remove leaks. #### Next Step These three lessons measured three separate questions about memory, and in all three the data vanished once the run ended. Most of the data a process produces, though, has to outlive the run, and that requires a second abstraction — one where bytes are named, placed in directories, and split into fixed-size blocks. The next lesson models the file system: the 4741 bytes of six files are placed into 512-byte blocks, the bytes going to waste are counted, and sweeping the block size measures the trade-off between internal fragmentation and the block list the inode has to carry. ### File System Abstraction Source: https://academia.sh/en/courses/operating-system-concepts/file-system-abstraction Turning bytes into names, names into blocks: fitting the 4741 bytes of six files into 512-byte blocks produces 1403 bytes of internal fragmentation, a cost that drops as the block shrinks while indirect blocks and read steps grow. The previous three lessons measured memory, and in all three, data vanished once the run ended. When a virtual page was evicted its content could be fetched back, but when the process terminated the address space disappeared entirely. Most of the data produced, though, has to outlive the run, and that requires a second abstraction: an arrangement where bytes are named, names are placed in a hierarchy, and content is split into fixed-size blocks. This lesson models that arrangement and counts two of its costs. Commands for creating files, granting permissions, and navigating directories have already been used throughout this catalog; no command is taught here. What is measured is the mechanism — how many steps it takes to turn a byte into a block, a name into a number. #### Three Separate Objects The abstraction separates three objects from one another, and the separation itself is a design decision. A **file** is a sequential byte sequence and has no name on its own. An **inode** carries everything about a file except its name: its size, permissions, timestamps, and the block list that says which blocks hold its content. A **directory** is itself a file; its content is a table mapping names to inode numbers. The name living in the directory rather than the file produces two consequences. The same inode can be pointed to by more than one directory entry, meaning a file can have more than one name. And deleting a name is not the same as deleting the file — the file disappears only once the last entry pointing to it is also gone. - **BD19** — Six files come from the common definition: 120, 700, 1500, 40, 2048, and 333 bytes, totaling **4741 bytes**. The default block size is 512 bytes. - **BD20** — An inode carries **8 direct block pointers**. A file needing more blocks keeps their numbers in an **indirect block**; a block pointer is 4 bytes, so an indirect block carries `block / 4` pointers. - **BD21** — The indirect block is single-level. None of the files in this model exceed a single level's capacity. - **BD22** — One read step per block; looking up a pointer in the indirect block adds one more read. The disk's own latency is not counted in this lesson. ```python """M01/K05 common definition (excerpt): inode , block and internal fragmentation.""" BLOCK = 512 FILE = [120, 700, 1500, 40, 2048, 333] DIRECT = 8 # direct block pointers an inode carries POINTER = 4 # bytes per block pointer def inode(sizes, block=BLOCK): used = sum(-(-b // block) for b in sizes) return {"files": len(sizes), "bytes": sum(sizes), "blocks": used, "internal_fragmentation": used * block - sum(sizes)} def indirect(sizes, block): """Extra indirect blocks and read steps needed for blocks that exceed the direct pointers.""" extra, reads = 0, 0 for b in sizes: data = -(-b // block) reads += data if data > DIRECT: extra += -(-(data - DIRECT) // (block // POINTER)) reads += data - DIRECT # each indirect pointer is one more read return extra, reads print("common definition:", inode(FILE)) print() print("block data blocks indirect total blocks disk bytes int. frag. read steps") for block in (64, 128, 256, 512, 1024, 4096): d = inode(FILE, block) extra, reads = indirect(FILE, block) total = d["blocks"] + extra print(f"{block:4d} {d['blocks']:11d} {extra:8d} {total:12d} {total * block:10d}" f" {d['internal_fragmentation']:11d} {reads:10d}") ``` ``` common definition: {'files': 6, 'bytes': 4741, 'blocks': 12, 'internal_fragmentation': 1403} block data blocks indirect total blocks disk bytes int. frag. read steps 64 76 4 80 5120 123 119 128 39 2 41 5248 251 51 256 21 0 21 5376 635 21 512 12 0 12 6144 1403 12 1024 8 0 8 8192 3451 8 4096 6 0 6 24576 19835 6 ``` Three numbers sit side by side. **Baseline:** the content of six files is 4741 bytes, and laid out contiguously it would hold 4741 bytes on disk; the inode would carry a single start address and a length. **Setup:** 512-byte blocks, **12 blocks**, 6144 bytes on disk. **Cost:** **1403 bytes of internal fragmentation** — 22.8 percent of what is written to disk carries no data at all — and 12 block pointers in the inode instead of a single pair. Why contiguous placement was abandoned can be read from the previous lesson. A file growing requires the bytes behind it to be free, and when they are not, the whole file must be moved. A block list removes that requirement: a new block gets appended to the list wherever it lands on disk. So internal fragmentation is the price paid to escape external fragmentation. #### What Happens as the Block Shrinks The table sweeps the block size, and two columns move in opposite directions. Internal fragmentation shrinks with the block: 19,835 bytes at a 4096-byte block, 1403 at 512, only **123 bytes** at 64. The reason is direct — every file's last block wastes half a block on average, and for six files that is roughly three times the block size. As the block shrinks, so does the wasted share. Read steps move the other way: 6 reads at a 4096-byte block, 12 at 512, **119 reads** at 64. Reading the same 4741 bytes takes twenty times as many requests. Indirect blocks add to this: at 128 bytes and below, some files no longer fit within eight direct pointers, and part of the block list moves into a separate block. Looking up every pointer in that block is one extra read, which is why the read column jumps to 51 for 39 data blocks. Total disk bytes do not move in a straight line either. At a 64-byte block, including indirect blocks, it is 5120 bytes; at 512, 6144 bytes; at 4096, 24,576 bytes. The smallest block uses space most efficiently and makes reads most expensive. **Block size is a budget decision, not a correctness decision**, and the budget's two line items move in opposite directions. #### Turning a Name into a Number The name a program uses is a path; the name the file system uses is an inode number. The translation between the two is one directory read per path component. - **BD23** — Six files are spread across three directories; the names stand in for measurement and log data, and their sizes match the list above. - **BD24** — Reading one directory is one step; how many entries the directory carries does not change the step count. ```python """Directory resolution: how many reads a name translates to.""" TREE = { # directory -> name: (kind , inode number) "/": {"measurement": ("D", 1), "log": ("D", 2)}, "/measurement": {"raw.data": ("F", 10), "summary.data": ("F", 11), "old": ("D", 3)}, "/measurement/old": {"history.data": ("F", 12)}, "/log": {"day.record": ("F", 13), "week.record": ("F", 14), "month.record": ("F", 15)}, } PATH = ["/measurement/raw.data", "/measurement/summary.data", "/measurement/old/history.data", "/log/day.record", "/log/week.record", "/log/month.record"] def resolve(path): """Returns: inode number , read steps. Every path component reads one directory , the end reads one inode.""" current, steps, no = "/", 0, None for part in path.strip("/").split("/"): steps += 1 # directory carrying the component is read kind, no = TREE[current][part] if kind == "D": current = ("" if current == "/" else current) + "/" + part return no, steps + 1 # inode read at the end total = 0 for y in PATH: no, steps = resolve(y) total += steps print(f"{y:32s} inode {no:3d} resolution steps {steps}") print("total resolution steps for six files:", total) print() ACCESS = 20 y = "/measurement/old/history.data" _, steps = resolve(y) print(f"{y} , {ACCESS} accesses") print(" re-resolving on every access:", ACCESS * steps, "steps") print(" resolve once , then use a descriptor:", steps + ACCESS, "steps") ``` ``` /measurement/raw.data inode 10 resolution steps 3 /measurement/summary.data inode 11 resolution steps 3 /measurement/old/history.data inode 12 resolution steps 4 /log/day.record inode 13 resolution steps 3 /log/week.record inode 14 resolution steps 3 /log/month.record inode 15 resolution steps 3 total resolution steps for six files: 19 /measurement/old/history.data , 20 accesses re-resolving on every access: 80 steps resolve once , then use a descriptor: 24 steps ``` Resolution steps grow linearly with path depth: a two-component path takes 3 steps, a three-component path takes 4. All six files together cost 19 steps, and none of that reads data — all of it is name lookup. The last two lines show what a **file descriptor** buys. Twenty accesses to the same file, each resolving the path from scratch, cost 80 steps; resolving the path once and then using the resulting descriptor costs 24. A descriptor is a shortcut that caches the result of resolution and makes its cost payable once. It has a cost too: a descriptor holds an inode, not a name, so if the file is renamed or its name is deleted in between, it keeps reading the same content anyway. #### One Update, Three Writes Appending a block to a file is not a single write. The data block itself is written, that block is marked occupied in the block bitmap, and the inode's size and block list are updated. Which state remains on disk if the machine halts between these three writes is the file system's most expensive question. - **BD25** — One update carries three writes, and a crash can land between any two of them. Since write order depends on the implementation, all six orderings are counted. - **BD26** — The invariant is this: if an inode points to a block, that block must be marked occupied in the bitmap and its data written. A block that appears occupied in the bitmap but that no inode points to is an **orphaned block** — not inconsistent, but unrecoverable space. ```python """Crash consistency: journal-less and journaled layouts , every crash point.""" from itertools import permutations WRITE = ("data", "bitmap", "inode") # data block , block bitmap , inode def check(on_disk): """Invariant: if the inode points to the block , the bitmap must be occupied and data written.""" consistent = ("inode" not in on_disk) or {"bitmap", "data"} <= on_disk orphaned = "bitmap" in on_disk and "inode" not in on_disk return consistent, orphaned states = inconsistent = orphaned_count = 0 for order in permutations(WRITE): for k in range(len(WRITE) + 1): c, orphan = check(set(order[:k])) states += 1 inconsistent += not c orphaned_count += orphan print("journal-less: writes", len(WRITE), "| order x crash point", states, "| inconsistent", inconsistent, "| orphaned blocks", orphaned_count) # Journaled layout: first to the journal , then a commit record , last in place. STEP = [("to journal", a) for a in WRITE] + [("commit", None)] \ + [("in place", a) for a in WRITE] states = inconsistent = 0 for k in range(len(STEP) + 1): committed = ("commit", None) in STEP[:k] # recovery: if no commit , the journal is discarded (old state) , if committed , it is replayed on_disk = set(WRITE) if committed else set() c, _ = check(on_disk) states += 1 inconsistent += not c print("journaled: writes", len(STEP), "| crash points", states, "| inconsistent", inconsistent, "| write multiplier", round(len(STEP) / len(WRITE), 2)) ``` ``` journal-less: writes 3 | order x crash point 24 | inconsistent 6 | orphaned blocks 4 journaled: writes 7 | crash points 8 | inconsistent 0 | write multiplier 2.33 ``` Six orderings times four crash points give 24 possible end states. **6 of these are inconsistent**: the inode points to a block, but that block either appears free in the bitmap or has nothing written into it. In four of them there is an orphaned block — space is allocated, nothing points to it, and it cannot be reclaimed either. Only in 14 states is the disk sound. A **journaling file system** drops this number to zero. The three writes go first to a separate journal area, then a single commit record is written, and only after that are the data applied in place. Recovery follows one rule: if there is no commit record, the journal is discarded and the disk stays in its old state; if there is one, the writes in the journal are replayed and the disk moves to its new state. All eight crash points fall into one of these two consistent states. The cost is right there in the table: 7 writes instead of 3, that is, **2.33 times**. Every byte goes to disk twice. Part of this is recoverable — a setup that journals only structures like the inode and the bitmap while writing data blocks directly lowers the multiplier, in exchange for bringing back the possibility of data loss. This trade-off between the disk staying sound and the amount written cannot be removed; only where it is placed can be chosen. It is also worth noting what the journal does not remove. The journal keeps the on-disk structures consistent with one another at the moment of a crash; it does not prevent data being written from getting lost. An update that crashes before its commit record looks, after recovery, as if it never happened, and that is the correct outcome by definition. The gap between a program saying "I wrote it" and the data actually being on disk is a related but separate matter that falls outside this lesson's model: a write request can be accepted while the byte is not yet on disk. #### Summary - A file is a sequential byte sequence, an inode carries everything about it besides its name along with the block list, and a directory is a table mapping a name to an inode number; a name is a property of the directory, not the file. - The 4741 bytes of six files fit into 12 blocks of 512 bytes and take up 6144 bytes on disk; 1403 bytes, that is, 22.8 percent of what is written, is internal fragmentation. - Sweeping the block size moves two costs in opposite directions: at a 64-byte block, internal fragmentation drops to 123 bytes but read steps climb to 119; at a 4096-byte block, reads drop to 6 but internal fragmentation climbs to 19,835 bytes. - An inode carries eight direct pointers; as the block shrinks, some files exceed that limit and the block list moves into an indirect block, adding one more read per access. - Translating a path name into an inode number is one directory read per path component; 20 accesses to the same file cost 80 steps if resolved every time, 24 steps if resolved once and then used through a descriptor. - A single block append carries three writes; of the 24 states produced by six orderings and four crash points, 6 are inconsistent and 4 leave an orphaned block. A journaled layout drops this to zero, in exchange for raising the write count from 3 to 7, that is, 2.33 times. #### Next Step This lesson assumed reading a block is one step and never asked how long that step takes. Yet a disk request takes thirty times as long as one of the processor's compute steps, and during that time the processor either waits, asks, or does other work. The course's last lesson counts all three options on the same workload and ends on a surprising result: the model that keeps the processor one hundred percent busy does not finish its work any sooner at all. ### Input/Output Models Source: https://academia.sh/en/courses/operating-system-concepts/input-output-models Blocking, non-blocking, and asynchronous input/output measured on the same workload: the polling model drives processor utilization to 1.0000 and never changes the duration, the asynchronous model drops duration from 248 to 38. The previous lesson counted reading a block as one step and never asked how long that step takes. In the common definition, one input/output operation takes **30 time units**; one compute step is one time unit. That factor of thirty is the single number that decides where a process's time goes. This lesson counts three decisions about what the processor does while facing that factor of thirty, on the same workload: wait, ask, or do other work. The result is the course's most contrarian measurement — one of the three models keeps the processor completely full and does not finish its work even one time unit sooner. #### Three Models In a **blocking** call, the process issues the request and leaves the ready queue until it completes; the processor can be handed to another process during this time, but the requesting process does nothing at all. In a **polling** setup, the process is not blocked, it keeps asking whether the operation is complete; this is **busy waiting** and it holds the processor. In an **asynchronous** setup, the process issues the request, returns immediately, does other work, and completion arrives through a notification. The hardware counterpart of the notification is an interrupt; the interrupt itself was defined in the Interrupts lesson of the How Computers Work course and is used here only as a completion notification. - **BD27** — An input/output operation's latency is 30 time units, the processor work per request is 1 time unit. Eight requests are measured. - **BD28** — In the asynchronous model, eight requests can be in flight at once and their latencies fully overlap; the disk serves all eight in parallel. - **BD29** — Processor utilization is the ratio of steps the processor spends busy to total duration. Busy waiting counts as busy — the processor really is executing an instruction. - **BD30** — This lesson is a single machine. There is no network cost, remote call, or data transfer cost of any kind. ```python """M01/K05 common definition (excerpt): input/output models.""" WAIT_TIME = 30 # latency of one input/output operation , time units def io_model(requests, policy="blocking", latency=WAIT_TIME, per_request=1): """requests: how many input/output operations. Returns: duration , busy steps , utilization.""" if policy == "blocking": duration = requests * (latency + per_request) busy = requests * per_request elif policy == "polling": duration = requests * (latency + per_request) busy = duration # busy waiting: processor is always full else: duration = latency + requests * per_request busy = requests * per_request return {"duration": duration, "busy": busy, "utilization": round(busy / duration, 4)} print("eight requests , the common definition's measurement") for y in ("blocking", "polling", "asynchronous"): print(f" {y:12s}", io_model(8, y)) print() print("requests blocking polling asynchronous") print(" duration util. duration util. duration util.") for requests in (1, 2, 4, 8, 16, 32): e = io_model(requests, "blocking") y = io_model(requests, "polling") a = io_model(requests, "asynchronous") print(f"{requests:5d} {e['duration']:6d} {e['utilization']:8.4f} {y['duration']:6d}" f" {y['utilization']:8.4f} {a['duration']:6d} {a['utilization']:8.4f}") ``` ``` eight requests , the common definition's measurement blocking {'duration': 248, 'busy': 8, 'utilization': 0.0323} polling {'duration': 248, 'busy': 248, 'utilization': 1.0} asynchronous {'duration': 38, 'busy': 8, 'utilization': 0.2105} requests blocking polling asynchronous duration util. duration util. duration util. 1 31 0.0323 31 1.0000 31 0.0323 2 62 0.0323 62 1.0000 32 0.0625 4 124 0.0323 124 1.0000 34 0.1176 8 248 0.0323 248 1.0000 38 0.2105 16 496 0.0323 496 1.0000 46 0.3478 32 992 0.0323 992 1.0000 62 0.5161 ``` Three numbers sit side by side. **Baseline:** blocking calls, eight requests, **248 time units**, processor utilization 0.0323. **Setup:** the asynchronous model, **38 time units**, utilization 0.2105. **Cost:** processing eight completion notifications and keeping a ledger of eight simultaneously in-flight requests — both get counted shortly. #### High Utilization Is Not a Success Metric The table's middle column is the course's most contrarian result. The polling model drives processor utilization to **1.0000**: the processor is never idle, a command executes on every time unit. The duration on the same row is **248** — identical to the blocking model. Keeping the processor completely full did not bring the work forward by even one time unit. The reason reads directly from the definition. In the polling model, the processor's commands ask "is it done yet"; they produce no work. Of the 248 busy steps, only 8 are real work, the remaining 240 are the waiting step spent in a different form. The blocking model leaves those same 240 steps idle; the polling model fills them and **speeds up nothing.** The rule that follows concerns metric choice. Processor utilization is a **proxy metric**: the question actually being asked is "when does the work finish," but because it is easy to measure, utilization stands in for that question instead. On this workload the proxy runs backward — the highest-utilization model does not give the best duration, and the model that does, the asynchronous one, has a utilization of only 0.2105. If a setup's utilization is high, nothing can be said without asking **what it is full of**. How the asynchronous model wins is in the same table. Its duration barely moves with request count: 31 at one request, 62 at thirty-two. The blocking model climbs from 31 to 992 while the asynchronous model does not even double, because the thirty-unit latency is paid once and every request overlaps inside it. The gain grows with request count: 6.5 times at eight, 16 times at thirty-two. #### Non-Blocking Calls and the Polling Interval The mechanism beneath the polling setup is a separate concept with a separate name. A **non-blocking** call does not put the process to sleep if the result is not ready; it returns immediately, saying "not ready yet." Polling is repeating that call inside a loop. The two are not the same thing: a non-blocking call is an interface property, polling is only one way of using it — and the most expensive one. In the measurement above, polling was done every time unit. The interval can be widened; the processor then asks less often, but notices completion later. - **BD31** — Polling happens at fixed intervals, and each question takes one time unit. Completion is noticed on the first question after the latency elapses. ```python """Non-blocking calls: which two costs the polling interval pits against each other.""" LATENCY = 30 REQUESTS = 8 print("interval polls noticed at extra delay total duration processor steps") for interval in (1, 2, 4, 7, 10, 30, 45): polls = -(-LATENCY // interval) # how many questions until completion is noticed noticed = polls * interval # moment of notice print(f"{interval:8d} {polls:5d} {noticed:10d} {noticed - LATENCY:11d}" f" {REQUESTS * (noticed + 1):14d} {REQUESTS * (polls + 1):15d}") ``` ``` interval polls noticed at extra delay total duration processor steps 1 30 30 0 248 248 2 15 30 0 248 128 4 8 32 2 264 72 7 5 35 5 288 48 10 3 30 0 248 32 30 1 30 0 248 16 45 1 45 15 368 16 ``` As the interval widens from 1 to 30, processor steps drop from **248 to 16** and duration stays at 248: on this workload, 240 of polling's steps were entirely wasted work. But the table does not run in a straight line. At intervals 4 and 7, the delay before completion is noticed stretches by 2 and 5 units, and duration climbs to 264 and 288; at interval 45, completion is noticed 15 units late and duration jumps to 368. Wherever the interval does not evenly divide the latency, a remainder is paid — the cost of not knowing exactly when the operation will finish. The gap between the two extremes is this: **a small interval costs the processor, a large one costs response time.** There is no single best point in between — the 30-unit interval minimizes both costs here only because the latency happens to be known to be exactly 30. If the latency varies, that knowledge is gone and the choice turns back into a guess. The asynchronous model, using a completion notification, removes this guess entirely — in exchange it needs a mechanism to process the notification. #### Two Limits of Asynchrony The measurement above counted two things as free: processing the completion notification, and requests being independent of one another. Neither is always true. - **BD32** — Processing one completion notification takes `notification` time units; this is the interrupt handler running and the request being struck off the ledger. The swept value ranges from 0 to 16. - **BD33** — In a dependent chain, every request uses the previous one's result; so latencies cannot overlap. ```python """Two limits of the asynchronous model: notification cost and dependency.""" LATENCY = 30 REQUESTS = 8 def asynchronous(requests, notification=0, dependent=False): """notification: time units to process each completion notification. dependent: if every request waits on the previous one's result , there is no overlap.""" per_request = 1 + notification duration = requests * (LATENCY + per_request) if dependent else LATENCY + requests * per_request busy = requests * per_request return {"duration": duration, "busy": busy, "utilization": round(busy / duration, 4)} print("independent requests , notification cost swept") print("notification duration busy util. gain over blocking") for b in (0, 1, 2, 4, 8, 16): a = asynchronous(REQUESTS, b) print(f"{b:12d} {a['duration']:8d} {a['busy']:4d} {a['utilization']:8.4f}" f" {REQUESTS * (LATENCY + 1) / a['duration']:19.2f}") print() print("dependent chain (each request waits on the previous)") for b in (0, 1): a = asynchronous(REQUESTS, b, dependent=True) print(f" notification {b}: duration {a['duration']} utilization {a['utilization']}") print(" blocking model's duration:", REQUESTS * (LATENCY + 1)) ``` ``` independent requests , notification cost swept notification duration busy util. gain over blocking 0 38 8 0.2105 6.53 1 46 16 0.3478 5.39 2 54 24 0.4444 4.59 4 70 40 0.5714 3.54 8 102 72 0.7059 2.43 16 166 136 0.8193 1.49 dependent chain (each request waits on the previous) notification 0: duration 248 utilization 0.0323 notification 1: duration 256 utilization 0.0625 blocking model's duration: 248 ``` The first limit is the notification's cost. When 16 time units of processing are added to each completion, duration climbs from 38 to **166** and the gain over the blocking model drops from 6.53 times to **1.49 times**. What stands out is that utilization climbs from **0.2105 to 0.8193** across the same sweep: the model slows down at every step while its metric keeps improving — the second proof that utilization is not a success metric. The second limit is dependency. If requests wait on one another's results, there is nothing left to overlap; the asynchronous model finishes in **248 time units**, exactly the same as the blocking model. Once notification processing is added, it climbs to **256**, and the asynchronous setup becomes **worse** than the blocking one. What asynchrony sells is not speed, it is **overlap**; with no work to overlap, all that remains is bookkeeping cost. #### Summary - On eight input/output requests, the blocking model finishes in 248 time units at 0.0323 utilization; the polling model finishes in the same 248 at 1.0000 utilization; the asynchronous model finishes in 38 at 0.2105 utilization. - Busy waiting fills the processor and speeds up nothing: of the 248 busy steps, only 8 produce work, 240 are the question "is it done yet." - Processor utilization is a proxy metric and runs backward on this workload; if a setup's utilization is high, no conclusion follows without asking what it is full of. - A non-blocking call is an interface property, polling is one way of using it; widening the polling interval from 1 to 30 drops processor steps from 248 to 16, but when the interval does not evenly divide the latency, duration stretches to 288 and 368. - The asynchronous model's gain comes from overlap and grows with request count: 6.5 times at eight requests, 16 times at thirty-two. - The gain erodes under two conditions: it drops to 1.49 times once 16 time units are paid per completion notification, and it vanishes when requests depend on one another, dropping below the blocking model once notification cost is added. #### Course Wrap-Up Fifteen lessons modeled a single machine and asked a single question: how many steps does an abstraction charge while it delivers convenience. On every lesson, three numbers stood side by side — the baseline without the abstraction, the setup with it, and the cost between them. The course's rule was this: **an abstraction whose cost goes uncounted counts as unmeasured.** | Lesson | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | The Process Concept | five processes run one after another: **669** time units | five processes sharing one core: **194** | **22 context switches = 44 time units**, above the real work (39); 111 idle-core steps | | Process Forking | no forking: **0** copied pages | four forks, eager copy: **64 virtual pages** | copy-on-write brings it down to **15 pages**, 49 of which were empty; the advantage disappears past a fault cost of **4** | | Threads | five separate processes: **194** time units, **15** extra virtual pages | five threads in one process: **186**, **4** stack pages | **73.33** percent memory gain, only **8** units in duration; the cost is **isolation disappearing entirely** | | Choosing Between Processes and Threads | a single address space: **0** copied pages, spread ratio **5.0** | five separate address spaces: **1** affected unit | **15** copied pages (64 with eager copy); partial isolation is not linear — 6 pages bring 5 down to 3, the last 5 pages buy only 1 | | Scheduling Algorithms | non-preemptive queue: **194** (189 on the second workload) | time-sliced scheduling: **197** (202 on the second workload) | **206** at slice 1, **36** context switches, wait **33.00**; no best policy in either workload | | Race Conditions | one execution order: **1** result | two threads, a splittable three-step operation: **20** interleavings | **18 wrong** (0.9000); at slice 3, of the **2** reachable interleavings **none** is wrong — the bug does not vanish, it becomes invisible | | Locks, Mutexes, and Semaphores | one thread: **20** time units, **0** wait steps | eight threads, a mutex: **83** | **252** wait steps, utilization from **1.0000 to 0.2410**; waiting is **4.5** times $n(n-1)$ | | Deadlock and Starvation | uncoordinated acquisition: **264** of 648 states locked (0.4074) | ordered acquisition: state space **36**, deadlocked **0** | **+144** wait steps at eight threads; throughput does not drop under starvation, the failure shows only in **distribution** | | Concurrency on Multiple Cores | one core: **197**, 108 idle-core steps | four cores: **179** (lower bound 173) | **639** idle-core steps, total work **fixed at 39**; slice protection disappears, reachable interleavings go from 2 to **20** | | Concurrency Models | thread model: **197** (202 on the second workload) | event loop **178**, message passing **179** | the 1-time-unit gap is **below the measurement band**; the difference shows in idle-core steps: **139 versus 639** | | Virtual Memory | 15 physical pages, 15 compulsory faults, 489 time units | 2 physical pages, paging, first in first out | 15 extra page faults, 450 time units | | Memory Allocation | end-to-end allocation, 6 requests placed | block-list allocator, best fit, 8 requests placed | two 10-byte remainders, external fragmentation ratio 0.5000 | | Garbage Collection | manual release, 0 scan steps | tracing collector, 17 of 40 objects reachable | 17-step pause, 40-step sweep, 57 steps total | | File System Abstraction | contiguous placement, 4741 bytes | 12 blocks of 512 bytes, 6144 bytes on disk | 1403 bytes internal fragmentation, 12 block pointers | | Input/Output Models | blocking call, 248 time units | asynchronous model, 38 time units | 8 completion notifications and a ledger of 8 in-flight requests | The table's second reading is worth more than its first: **an abstraction sometimes makes things worse.** A smarter page replacement policy can produce more faults, best fit can leave behind a more unusable remainder, splitting a pause can grow total work, a journaled layout writes every byte twice, busy waiting fills the processor and speeds up nothing. None of these results were hidden, because someone who cannot tell when an abstraction worsens things also cannot tell when to choose it. The third and most expensive result came from the concurrency topic: **correct output does not mean a correct program.** The same bug is entirely invisible once the scheduler's slice happens to be large enough. The bug does not disappear, it only becomes invisible — and the only thing that reveals an invisible bug is modeling the mechanism and counting every state. Everything measured across the course was measured on **a single machine**. Network cost, remote call latency, and inter-machine data transfer appear in none of these measurements; these numbers lose validity once carried into a distributed setup. The next course, **Modeling and Representation**, takes the model itself as its subject. Here a model was executable text and its output a number; there, a model will be a diagram and its output a question answered. The shared discipline does not change: a diagram earns its keep only when it is clear which question it answers, just as an abstraction counts as measured only once its cost is counted. Showing a system through class, component, sequence, and state diagrams does, in another representation, what this course did with numbers — and there too the criterion for avoiding needless representation is the same question: what does this measure.