§10.1–10.2Multiprocessor Architecture … Synchronization

The last stop in CPU virtualization: what changes when there’s more than one CPU? Plenty — and (per the book’s aside on advanced chapters) this material lands best after the concurrency piece, though it belongs here logically. The multicore multicore Multiple CPU cores on one chip — the reason multiprocessors went mainstream when single CPUs hit the power wall. defined in ch. 10 — open in glossary era made the question unavoidable: architects couldn’t push single-CPU speed further without absurd power draw, so chips sprouted cores instead. One caveat up front: a typical single-threaded C program gets no faster on more CPUs — you must rewrite it to run in parallel (threads, Part II’s subject).

10.1 Background: Multiprocessor Architecture

The fundamental difference between one CPU and many is what happens to hardware caches. A single-CPU system (Figure 10.1) keeps copies of popular data in small, fast caches, making the big slow memory appear fast — the first load of a value takes maybe 100 ns from memory; a repeat hit in cache takes a few:

Caches work because programs exhibit locality, in two flavors:

Now the tricky part (Figure 10.2): multiple CPUs, private caches, one shared memory. Step through what goes wrong:

That failure is the problem of cache coherence cache coherence The problem of keeping per-CPU caches consistent with the shared-memory illusion (stale-D vs updated-D′); solved in hardware. defined in ch. 10 — open in glossary — a research field of its own. The basic solution lives in hardware: monitor memory accesses and preserve the illusion of a single shared memory. On a bus-based system, the classic technique is bus snooping bus snooping Each cache watches the shared bus and invalidates/updates its copy when it sees a write to data it holds. defined in ch. 10 — open in glossary : every cache watches the bus; when a CPU sees an update to data it holds, it either invalidates its copy or updates it in place. Write-back caches complicate the details — but the scheme’s spirit survives all the way to modern protocols.

10.2 Don’t Forget Synchronization

If hardware keeps caches coherent, can programs just access shared data freely? Alas, no — coherence makes reads see writes, but it does nothing to make multi-step updates safe. Concurrent access to shared structures still needs mutual exclusion (locks). Witness this innocent list deletion:

typedef struct __Node_t {
    int              value;
    struct __Node_t *next;
} Node_t;

int List_Pop() {
    Node_t *tmp = head;         // remember old head ...
    int value   = head->value;  // ... and its value
    head        = head->next;   // advance head to next pointer
    free(tmp);                  // free old head
    return value;               // return value at head
}

Figure 10.3: Simple List Delete Code

Two threads on two CPUs enter List_Pop() together. Both execute line 7 and capture the same head in their private tmp (it’s on each thread’s stack). Now both try to remove the same element: a double free of the head node, and possibly the same value returned twice — the same species of disaster as chapter 2’s broken counter, at data-structure scale. The fix: a mutex — lock(&m) at entry, unlock(&m) at exit — makes the routine correct. The cost: as CPU counts grow, synchronized structures get slow, a tension Part II confronts head-on.

Coherence handled by hardware, correctness handled by locks — one issue remains before we can build the scheduler itself: performance depends on where a process runs. That’s cache affinity, next.