These questions separate per-location coherence from cross-location ordering. Every answer starts by naming the model (SC, TSO, Armv8-A or RVWMO), the initial values and the instructions, because the same observed outcome is legal under one model and a bug under another. Then connect the ordering rule to the protocol event that enforces it: a store draining into an M line, an Inv-Ack collected at H, an Inv hitting the load queue.
Field | Answer |
|---|---|
Interviewer is testing | Per-location coherence versus cross-location consistency. |
Weak answer | No: if the caches are coherent, everyone sees the same memory. |
Strong answer (a 4) | Assumption: X and Y in separate lines, X = Y = 0, plain aligned loads and stores, the SB test: C0 W(X)=1 then r1=R(Y); C1 W(Y)=1 then r2=R(X). Mechanism: coherence gives each location one modification order. SC requires one total order of all four operations preserving program order; r1=0, r2=0 needs both loads from-read ordered before the other core's store, which with the two program-order edges forms a cycle, so SC forbids it. Under TSO each store waits in a FIFO store buffer while the later load reads the other address, so 0,0 is allowed, and each location still has a coherent history. Trade-off: store buffers hide store latency at the cost of store-to-load order. Evidence: draw the program-order and from-read cycle. |
Follow-ups | Would proving SWMR for X and Y forbid 0,0? (No.) Is the TSO 0,0 a stale-cache bug? (No: name the violated rule first.) |
Common trap | Inferring cache states from a litmus outcome, or calling a legal older observation a coherence failure. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Three distinct store events and same-address forwarding. |
Weak answer | Stores can be reordered with loads. |
Strong answer (a 4) | Assumption: abstract FIFO-buffer TSO, ordinary aligned memory. Mechanism: a store appends to its core's FIFO buffer; a separate drain makes it globally visible; a load forwards from the newest own buffered store to the same address, otherwise reads the visible value. So a load of another address may be performed before an older store is visible (SB 0,0 allowed), but a load of X after W(X)=1 must return 1, and MP's r1=1, r2=0 stays forbidden because stores drain in FIFO order and loads stay ordered. Trade-off: hides store-miss latency, loses store-to-load order across addresses. Evidence: distinguish issue, forwarding to the same core and global visibility; one 'completed' label cannot describe all three. |
Follow-ups | Can a TSO load ignore its own pending store to X? (No.) Does FIFO store-buffer order mean the interconnect is FIFO? (No: it can be built with completion dependencies over an unordered fabric.) |
Common trap | Treating store-buffer FIFO order as a property of the network. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Exact outcome tables per named model, and what MP needs on each side. |
Weak answer | Weak CPUs can reorder anything, so everything is allowed. |
Strong answer (a 4) | Assumption: X = Y = 0, separate lines, plain loads and stores, no fences or dependencies. Mechanism: SB r1=r2=0: forbidden under SC, allowed under TSO, Armv8-A and RVWMO. MP r1=1, r2=0: forbidden under SC and TSO, allowed under Armv8-A and RVWMO, because the writer's stores and the reader's loads to different addresses may both be reordered. MP needs ordering on both sides. Armv8-A: DMB ISH or STLR on the writer, DMB ISH, LDAR or an address dependency on the reader. RVWMO: FENCE w,w or an amoswap with .rl on the writer, FENCE r,r, an LR or AMO with .aq, or an address dependency on the reader. Trade-off: weaker models allow more reordering in hardware and push ordering into the program. Evidence: enumerate small tests exactly; use the published model and a litmus tool for real instructions, recording the model version. |
Follow-ups | Does FENCE w,w on the writer alone forbid MP's (1,0) under RVWMO? (No.) Why does MP not separate SC from TSO while SB does? (FIFO drains plus ordered loads.) |
Common trap | Presenting a non-atomic C or C++ data race as a hardware litmus test. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | IRIW, the Arm and RISC-V facts and the link to ack collection. |
Weak answer | All cores see stores in the same order. |
Strong answer (a 4) | Assumption: four agents for IRIW (C0 to C3), X = Y = 0. Mechanism: a store seen by one other core is seen by all others; the issuing core may see its own store early through store-buffer forwarding. Armv8-A is other-multi-copy-atomic (since the 2017 revision of the Arm Architecture Reference Manual, DDI 0487) and RVWMO is multi-copy atomic in the same sense. The course's invalidation protocol gives it directly: H collects every Inv-Ack before granting M, so once any core can read the new value from the M copy, no other cache can still return the old one. Trade-off: an update protocol that pushes values to sharers one at a time, or a store buffer shared between hardware threads of one core, can break it. Evidence: IRIW, C2 reading X=1, Y=0 while C3 reads Y=1, X=0, is forbidden under SC and TSO, and on Armv8-A and RVWMO once both readers' loads are ordered; it is allowed there with plain unordered loads. |
Follow-ups | Why does granting M before the last ack break it? (A sharer can still return the old value after another core read the new one.) Which test is pure coherence on every model? (CoRR.) |
Common trap | Claiming Armv8-A is non-multi-copy-atomic, or treating IRIW with plain loads on Arm as a bug. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Separation of ordering from cache maintenance. |
Weak answer | Yes, a fence writes everything back so other cores see it. |
Strong answer (a 4) | Assumption: SB with a fence F between each store and load, TSO, MSI. Mechanism: no. F stalls C0's later load of Y until its buffered W(X)=1 has drained, and draining needs the line in M: GetM, H reads memory, Data(M), then the buffered store is written into the line. After the fence C0 is M / 1, H records exclusive(C0) and memory is still 0; any later reader is forwarded to C0. That forbids SB's 0,0 again. Trade-off: a fence costs the store's coherence latency on the critical path; a clean or invalidate is a separate operation with a named target. Evidence: on RVWMO, FENCE rw,rw is the full fence, SB needs only FENCE w,r, and MP needs FENCE w,w on the writer and FENCE r,r on the reader. |
Follow-ups | How can another core get 1 while memory holds 0? (H forwards to C0.) Does a forced writeback prove ordering? (No.) |
Common trap | Using fence, flush and drain as synonyms. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The reads-from condition and the one-way rules. |
Weak answer | Release flushes my writes, acquire refreshes my cache. |
Strong answer (a 4) | Assumption: C0 writes payload X=1 then release W(Y)=1; C1 does acquire R(Y) into r1 then R(X) into r2; X = Y = 0, no other writes. Mechanism: operations before a release are ordered before operations after an acquire that reads from that release. r1=1, r2=0 is forbidden; r1=0 establishes no edge, so r2=1 is not promised. Each annotation is one-way: an acquire stops later accesses moving before it, a release waits until every earlier access is performed (in protocol terms, every earlier store holds its line in M and has been written into it), but accesses may move into the protected region. Trade-off: one-way ordering is cheaper than full fences. RCsc forms (Arm LDAR and STLR, RISC-V .aq and .rl) are also ordered with each other; RCpc (Arm LDAPR) may be performed before an earlier release to a different address. Evidence: name which release the acquire read, not just the flag value. Under TSO every load already acts as an acquire and every store as a release. |
Follow-ups | Why are equal flag bits not enough? (Another writer of 1 or an initial 1 breaks the argument.) Does release/acquire excuse a lost dirty payload? (No.) |
Common trap | 'An acquire makes all memory current.' |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The lock window and what happens to a forward that arrives inside it. |
Weak answer | The core gets M and does the load and store. |
Strong answer (a 4) | Assumption: MSI, C0 M / 1, H exclusive(C0), memory = 0, C1's GetM serialized after C0's. Mechanism: C0 performs the read half (1) and locks the line; a Fwd-GetM that arrives is deferred until the write half stores 2 and unlocks; C0 then answers with Data(2) and C1's fetch-add returns 2 and writes 3. The lock is bounded to one RMW with no other request or miss inside it, so it cannot deadlock or livelock; an Inv that arrives while locked is held the same way. Trade-off: far atomics send the operation to H or the last-level cache instead, with no line moving between caches. Evidence: answering the forward mid-RMW sends Data(1); C1 makes 2 and C0's write half later stores 2 again: two increments from 1 end at 2, a lost update with every message and state coherent. |
Follow-ups | Is final X=1 after two split load-plus-store increments incoherent? (No: coherent, just not atomic.) Does M permission give acquire/release ordering? (No: separate contract.) |
Common trap | Inferring cross-location ordering from exclusive permission for X. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | The RISC-V contract stated correctly and the reservation's link to coherence events. |
Weak answer | SC succeeds if the value has not changed since LR. |
Strong answer (a 4) | Assumption: RISC-V LR/SC (Zalrsc part of the A extension), MSI, C0 holds S / 0 after LR with a line-granularity reservation. Mechanism: an Inv or Fwd-GetM for the line, C0's own eviction of it, or any SC by C0 clears the reservation; a new LR replaces it. If C1 writes X, H's Inv clears C0's reservation and C0's SC fails locally: no write, no GetM, rd nonzero (0 means success), even if X went from 0 to 5 and back to 0 (ABA). A successful SC still needs M. Trade-off: for a constrained loop (at most 16 instructions, base I only between LR and SC, no loads, stores, backward jumps, FENCE or SYSTEM, a region with the eventuality property), the execution environment guarantees only that eventually this hart or another hart executes a successful SC to the reservation set, or another hart or device writes to it, or this hart exits the loop or traps. That is system-wide progress, not freedom from starvation for each hart: if other harts keep writing the reservation set, no hart is guaranteed to leave its loop. A common design guideline holds the line for a bounded window after LR to stop two harts livelocking. Evidence: a directed test: C1 writes X with the same value and C0's SC must fail; a store by C1 to another word may also fail it, which the specification allows. |
Follow-ups | What does a Fwd-GetS do to the reservation? (Implementation-defined, commonly kept.) Compare with an AMO at the cache. (One instruction, no retry loop, completes once M is granted.) |
Common trap | Assuming any retry loop eventually succeeds for every hart. |
Taught in |
Field | Answer |
|---|---|
Interviewer is testing | Performed versus committed, load-queue snooping and the Inv-Ack rule. |
Weak answer | It replays loads that turn out wrong. |
Strong answer (a 4) | Assumption: MP with C1 writing X then Y and C0 reading Y then X; C0 holds X in S / 0; TSO. Mechanism: C0's younger R X performs early with 0 while the older R Y misses. Every incoming Inv or Fwd-GetM, and C0's own eviction of a line, is compared with the line address of every performed, uncommitted load; on a match with an older load still unperformed, the core squashes and re-executes from that load. C1's GetM must invalidate C0 before C1 writes X, so the Inv is C0's only warning. C0 sends the Inv-Ack at once and never waits for the replay, or C1's store to Y, C0's R Y and the ack would form a deadlock. Trade-off: the check is conservative and line-granular, so it gives false replays. The scheme goes back to Gharachorloo, Gupta and Hennessy (ICPP 1991); value-based re-execution at commit (Cain and Lipasti, ISCA 2004) avoids the snoop but adds a second cache access. Evidence: without the eviction check, MP commits (1,0) with no Inv ever sent. |
Follow-ups | Does an Inv change a committed register? (No.) Do Armv8-A and RVWMO need the check? (Yes, for same-address read pairs (CoRR) and wherever a dependency, acquire or fence orders loads.) |
Common trap | Holding the Inv-Ack until the replayed load completes. |
Taught in | Speculative Loads and Invalidations and Load Replay on Snoop |
Field | Answer |
|---|---|
Interviewer is testing | Classifying an observation against a named model before choosing a fix. |
Weak answer | Yes, the payload is stale: there is a coherence bug. |
Strong answer (a 4) | Assumption: record the model, instructions, initial values and whether each value was performed or committed. Mechanism: under Armv8-A or RVWMO with plain accesses it is allowed. Under SC or TSO, or with ordering on both sides, a committed (1,0) is forbidden: check the load-queue match (including own evictions and the compare mask), the store-buffer drain order (for example coalescing), and the order of the writer's GetM grants for X and Y. A tentative 0 that was squashed is not a violation. Trade-off: a fence can fix a missing ordering edge, never a lost value: an H buffer that overwrites a newer X is a data-value failure on one location. Evidence: an evidence packet with which write the flag load read, the payload result at commit, any Inv, Fwd-GetM or eviction of X before commit, and whether a replay was marked. |
Follow-ups | What does CoRR going backwards indicate? (A same-address read-read ordering bug, forbidden on every model.) What if a squash freed the MSHR? (Orphan Data, then a hang.) |
Common trap | Weakening the expected outcome until the regression passes. |
Taught in |
A bug: with fences SB's 0,0 is forbidden under TSO, because each load waits until its own store is globally visible, so whichever load runs second reads 1. Look at the fence implementation: whether it waits for the buffered store to be written into an M line (GetM granted after every Inv-Ack) or returns early, for example because some line's tag reads M while the store is still buffered ahead of the cache.