--- title: 'Concurrency Models' source: 'https://academia.sh/en/courses/operating-system-concepts/concurrency-models' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:17+00:00' license: 'CC BY-SA 4.0' --- # 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, no deadlock, no memory visibility problem. 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.