Concurrency and time

Lesson 11 gave us mutable data — set_head, mutable queues and tables, the agenda-driven circuit simulator — and one quiet warning: the rear-pointer trick worked only because exactly one process touched the queue at a time. This lesson removes that assumption. The moment two processes share a mutable cell and their steps can interleave, the order in which their operations land becomes a correctness problem. We trace the canonical bank-account race step by step, watch a deposit silently vanish, and then state precisely what "correct concurrent behavior" even means and how serializers buy it back. The deep finding: mutable state forced a notion of time back in Lesson 09, and concurrency is what drags that hidden time into the open where it can hurt you.

1 · Why concurrency is forced on us

So far our processes ran one step after another: a single evaluator, one expression at a time. Real systems break that single thread for two unavoidable reasons. Reflecting reality: the world is parallel — many bank customers, many sensors, many requests arrive at once, and a faithful model must let independent objects act independently. Performance: a CPU with eight cores, or a program waiting on the network, wastes time if it insists on one-at-a-time execution. So we let multiple processes run concurrently — their steps overlapping or arbitrarily interleaved in time.

For purely functional code (Lessons 01–08) this costs nothing: with no mutable state, no process can observe another's intermediate steps, so any interleaving gives the same answer. The trouble begins exactly where Lesson 09 began — with assignment. Once two processes share a mutable cell, one can read it in the middle of another's update, and now when each step happens changes the result.

2 · The canonical race — a lost update

Take the account object from Lesson 09, stripped to its mutating core. The balance is a shared mutable cell; withdraw reads it, computes, and writes it back.

function make_account(balance) {                 // balance is the SHARED mutable cell
  function withdraw(amount) {
    const current = balance;                     // STEP read
    const next = current - amount;               // STEP compute
    balance = next;                              // STEP write
    return balance;
  }
  return withdraw;
}
const acc = make_account(100);
// Two processes share `acc` and run "concurrently":
//   Process A: acc(10)
//   Process B: acc(20)

The bug is that withdraw is not atomic: it is three separate steps (read, compute, write), and the scheduler may run a step of B between A's read and A's write. Each process holds its own private current/next, but they both target the one shared balance. If A reads 100, then B reads 100 before A has written, both compute from the same stale value and the second write clobbers the first.

The defect is structural, not a typo. There are six ways to interleave A's three steps with B's three (preserving each process's internal order); several of them — any in which one process reads before the other writes — produce 80 or 90 instead of 70. The answer depends on scheduler timing the program never controls, so the same code gives different results on different runs. That non-reproducibility is what makes these bugs notorious.

3 · What does "correct" even mean here?

You might hope concurrency would just "give the right answer," but with truly independent processes there is often no single right answer — if A and B both deposit, the order genuinely does not matter, yet for read-modify-write it does. SICP's criterion is sharper and is the one to memorize:

This is exactly why the 80 is a bug and a reordering of two deposits is not: 70 is achievable by both serial orders, so any execution yielding 70 is correct; 80 is achievable by neither, so it is wrong. The criterion deliberately permits nondeterminism (you do not get to demand a particular order) while forbidding the impossible interleaved states. It is weaker than "deterministic" and that weakness is the point — demanding a single fixed order would throw away the parallelism we paid for.

4 · Serializers and mutual exclusion

To guarantee "equivalent to some serial order," we make the dangerous region — the whole read-compute-write of withdraw — run as one indivisible unit. A region that must not interleave with itself is a critical section; the rule that at most one process is inside it at a time is mutual exclusion. SICP packages this as a serializer: an object that wraps procedures so that no two serialized procedures from the same serializer ever overlap.

// A serializer hands back wrapped procedures that cannot run concurrently
// with each other. (mutex acquire/release are the atomic primitive; a real
// one is built from a hardware test-and-set, not from ordinary assignment.)
function make_serializer() {
  const mutex = make_mutex();
  return function serialized(fn) {
    return function (...args) {
      mutex.acquire();              // wait until no one else holds it
      try { return fn(...args); }   // critical section: runs alone
      finally { mutex.release(); }  // always hand it back
    };
  };
}

function make_account(balance) {
  const protect = make_serializer();
  const withdraw = protect(function (amount) {   // whole body is one critical section
    balance = balance - amount;
    return balance;
  });
  const deposit = protect(function (amount) {     // SAME serializer ⇒ excludes withdraw too
    balance = balance + amount;
    return balance;
  });
  return { withdraw, deposit };
}

Now re-run the race: A acquires the mutex at t1; when B tries to acquire it, B blocks until A releases. B's read cannot slip in before A's write, so the read-modify-write is atomic and the only possible outcomes are the two serial ones (both 70). Two notes that matter: (a) withdraw and deposit must share the same serializer instance, or a deposit could still interleave a withdrawal on the same balance; (b) the mutex itself can't be built from ordinary assignment — "test the lock, then set it" is itself a race — so it rests on an atomic hardware primitive (test-and-set / compare-and-swap). Serialization is how we re-impose order; the cost is that processes now wait.

5 · Deadlock — the cure has its own disease

Mutual exclusion fixes lost updates but introduces a new failure: processes can wait forever. Consider an exchange that moves the difference between two accounts and must lock both to stay atomic.

Process P:  exchange(a1, a2)        Process Q:  exchange(a2, a1)
  acquire a1   ✔  (P holds a1)        acquire a2   ✔  (Q holds a2)
  acquire a2   …blocks (Q has it)     acquire a1   …blocks (P has it)
                ▲                                    ▲
                └──────── each waits for a lock the other holds ───────┘
                          neither can proceed or release  →  DEADLOCK

The standard cure is a global ordering on the resources: give every account a unique id and require that any process acquire locks in increasing id order. Then exchange always locks the lower-numbered account first, no matter which way it was called:

function exchange(x, y) {                  // x, y have stable ids x.id, y.id
  const [first, second] = x.id < y.id ? [x, y] : [y, x];
  first.lock.acquire();                    // ALWAYS lower id first
  second.lock.acquire();
  try { /* atomic transfer between x and y */ }
  finally { second.lock.release(); first.lock.release(); }
}

Why this works: a deadlock cycle needs P waiting on Q while Q waits on P. But if everyone acquires in increasing id order, a process holding lock i only ever waits for some lock j > i. You cannot form a cycle out of strictly increasing steps — the "waits-for" graph has no loop — so deadlock becomes impossible. Ordering acquisitions does not make processes faster; it makes the cycle that deadlock requires structurally unbuildable.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

We have a cure, but look at its shape: serializers, mutexes, deadlock-avoidance orderings — an entire apparatus whose only job is to re-impose the serial order that assignment threw away. The root disease is the pair we named in §1: mutable shared state plus interleaving in time. Lesson 11's mutation introduced the shared state; concurrency exposed the time. What if we attacked the disease instead of medicating the symptom? Lesson 13 — streams and delayed evaluation — does exactly that. By modeling a changing quantity not as one cell rewritten over time but as an immutable sequence of its successive values, it decouples the order in which we compute from the order in which events occur. A balance becomes a stream of balances; there is no cell to race on, no critical section to guard, because nothing is ever mutated. Streams cure concurrency by removing the assignment that made time matter in the first place.

Interview prompts

• What two ingredients does every concurrency bug require, and how does each remedy attack one of them? (§1 — shared mutable state + interleaving; immutability/streams remove the first, serialization forbids the second, private copies remove sharing.)
• Walk through the lost-update race on a single balance step by step. (§2 — withdraw is read-compute-write, not atomic; if B reads the balance before A's write, B computes from a stale value and its write clobbers A's, so one withdrawal vanishes; final 80 instead of 70.)
• What is the correctness criterion for concurrent execution? Why not just "deterministic"? (§3 — result must equal that of some serial order; demanding one fixed order would forbid the reorderings that are genuinely harmless and discard the parallelism, so the criterion permits nondeterminism but bans impossible interleaved states.)
• What is a serializer / critical section / mutual exclusion, and why can't a mutex be built from plain assignment? (§4 — a serializer wraps procedures so same-serializer ones never overlap; the critical section runs under mutual exclusion; "test then set" is itself a race, so the mutex needs an atomic test-and-set/CAS primitive.)
• Construct a two-lock deadlock and give the standard fix. (§5 — P locks a1 wants a2 while Q locks a2 wants a1, each holds what the other needs; fix by acquiring locks in a global id order so the waits-for graph cannot contain a cycle.)
• Why is purely functional code immune to these races? (§1 — no mutable shared state means no process can observe another's intermediate step, so every interleaving yields the same result.)
• Why is "it always worked in testing" not evidence a concurrent program is correct? (§common mistakes — races are timing-dependent and may surface once in millions of runs; correctness requires reasoning over all legal interleavings, not the observed ones.)