Concurrency on Multiple Cores

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.

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.

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.