Concurrency Models

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.

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.

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.