Chapter 2’s invariants were all safety safety The 'nothing bad ever happens' half of correctness — coherence's SWMR and data-value invariants. Trivially satisfiable by doing nothing; must be paired with liveness. defined in Chapter 9 — open in glossary : nothing bad ever happens. Facetiously, safety is easy — an unplugged computer never does anything incorrect. The other half of correctness is liveness liveness The 'something good eventually happens' half of correctness: freedom from deadlock, livelock, and starvation. defined in Chapter 9 — open in glossary : something good eventually happens, which means preventing three distinct failures.
9.3.1 Deadlock
Deadlock deadlock Two or more actors each waiting for another to act — a cycle of resource dependences; nobody progresses. In coherence: protocol deadlocks (waiting for a message never sent), cache resource deadlocks (e.g., all TBEs held by own requests), and protocol-dependent network deadlocks (broken by the three virtual-network invariants). defined in Chapter 9 — open in glossary : actors waiting on each other in a cycle, forever. The canonical shape:
Coherence implementations can deadlock three ways:
Protocol deadlock
A controller waits for a message that will never be sent — a design bug. Example: skip the Put-Ack wait after a PutS and go straight to I; if the directory’s Inv crosses that PutS in flight, the requesting core waits for an Inv-Ack that C0 (already in I) will never send. Usually an untested race.
Cache resource deadlock
Allocation before action: if the shared TBEs transaction buffer entry (tbe) A cache controller's shared buffer entry allocated per in-flight transaction (own or serviced). If all TBEs fill with a core's own requests on every core, nobody can service anyone else: a cache resource deadlock. defined in Chapter 9 — open in glossary serve both a core’s own requests and other cores’ requests, a core that fills them with its own can’t service anyone. All cores in that state ⇒ system deadlock.
Network deadlock (protocol-dependent)
Message classes blocking each other in shared FIFOs — prevented structurally by the three invariants below. (Buggy-routing deadlocks are the protocol-independent kind — virtual channels virtual channels Extra per-switch FIFO queues used at the NETWORK level to break routing deadlocks (e.g., dimension-ordered torus rules) — orthogonal to virtual networks, which separate coherence message classes; each virtual network may contain several virtual channels. defined in Chapter 9 — open in glossary ’ territory.)
The three no-deadlock invariants
For the directory chain request → forwarded request → response:
- One network per message class — physical or virtual; a message of one class must never sit stuck behind another class in a FIFO.
- Respect the dependence order — if class A can cause class B, a controller may not stall B’s processing while waiting for an A. (No stalling a forwarded request to wait for a request; no stalling a response to wait for a forwarded request.)
- The last class always sinks — a response must be removable from its queue unconditionally, blocked by nothing.
Requests may stall waiting on the other classes — harmlessly, because the number of forwards and responses is bounded by outstanding transactions. Cycles are what these rules make impossible.
9.3.2 Livelock
Livelock livelock Actors keep acting and changing state but never progress — a special case of starvation. Classic coherence causes: NACK-retry storms, and the window of vulnerability (IS^D_I invalidation loops on contended blocks). defined in Chapter 9 — open in glossary : everyone keeps acting, nobody progresses — starvation’s total form. NACK-retry storms are the classic cause (this primer’s protocols have no NACKs), so the star exhibit is the window of vulnerability window of vulnerability Without Atomic Requests, the gap between issuing a request and its serialization, during which another core's request may be ordered first and change the block's state. defined in Chapter 7 — open in glossary . Table 9.1’s trace, in a snooping protocol:
| Cycle | Event (all for block B) | C1’s state for B |
|---|---|---|
| 0 | Initial state | I |
| 1 | Load request; issue GetS to bus | ISAD |
| 2 | Observe Own-GetS on bus | ISD |
| 3 | Observe Other-GetM on bus | ISDI |
| 4 | Receive data for Own-GetS | I |
| 5 | Re-issue GetS to bus | ISAD |
| 6 | Observe Own-GetS on bus | ISD |
| 7 | Observe Other-GetM on bus | ISDI |
| 8 | Receive data for Own-GetS | I |
| 9 | Etc. — the load never completes | … |
Table 9.1 (recreated): the window-of-vulnerability loop. Perversely, it bites hardest on contended blocks — where every core loops at once: system livelock.
The fix is almost free: perform at least one load when the data arrives — logically the load occurs when the GetS was ordered, so coherence is safe. But consistency is not automatically safe. Step through why:
Non-stalling §8.7.2 protocol; directory actions elided.
1 / 8The program (Table 9.2)
A = B = 0. C0: Store A=1, then Store B=1. C1: Prefetch A for read, then Load r1=B, then Load r2=A. Under SC and TSO, r1=1 ∧ r2=0 is the one illegal outcome — if C1 sees the second store (B=1), it must see the first (A=1).
The Peekaboo peekaboo problem A consistency hazard of the window-of-vulnerability fix: a PREFETCHED block invalidated before its data arrives, then demand-referenced — performing the access on data arrival effectively orders it at invalidation time, reordering it against program-order-earlier accesses and violating SC/TSO. Fix: perform the access iff it was the oldest load/store in program order when the request was issued. defined in Chapter 9 — open in glossary rule
Perform the window-of-vulnerability access iff it was the oldest unperformed load/store in program order when its coherence request was issued. Intuition: no problem can arise if a core issues coherence requests one at a time, in demand-miss order. The same discipline covers stores caught in IMDS / IMDSI / IMDI — a GetM issuer must perform at least one store when data arrives and forward the newly written data to the cores that requested the block in between. The rule comes from Manerkar et al.’s CCICheck, a tool for formally verifying the coherence–consistency interface — §11.3 shows the machinery behind it.
9.3.3 Starvation
Starvation starvation Some cores never progress while others do. Root causes: unfair arbitration (fixed-priority buses) — fixed by fair arbitration — and misused NACKs whose retries are never guaranteed to succeed. defined in Chapter 9 — open in glossary : some cores progress, others never do. Two root causes:
- Unfair arbitration. A fixed-priority bus (C2 yields to C1, C3 to both, …) can lock a low-priority core out indefinitely. Known problem, known cure: fair arbitration fair arbitration An arbitration policy guaranteeing every requestor eventually wins — the standard cure for fixed-priority starvation on shared resources like snooping buses. defined in Chapter 9 — open in glossary .
- Misused NACKs nack Negative acknowledgment forcing a requestor to re-issue its request; risks livelock (section 9.3.2), so this book's protocols avoid it (the SGI Origin's Upgrade race uses one). defined in Chapter 8 — open in glossary . NACK-and-retry looks like a seductively simple answer to in-progress-transaction races (the SGI Origin uses one for its Upgrade race) — but guaranteeing a NACKed request eventually succeeds, under arbitrary contention, is genuinely hard. One of the primer’s authors confesses to having designed a NACK protocol that starved.
Check yourself
1.Why does the book call safety alone 'facetiously easy'?
2.Name the three flavors of deadlock in coherence implementations.
3.What three invariants eliminate protocol-dependent network deadlock (for request → forwarded request → response)?
4.Virtual networks vs. virtual channels — what's the difference?
5.In the window-of-vulnerability livelock (Table 9.1), C1 loops IS^AD → IS^D → IS^D_I → I forever. Why is the simple fix ('perform one load when data arrives') both correct for coherence AND dangerous for consistency?
6.What are the two root causes of starvation, and their remedies?