Questions: Cache Coherence Protocols and Memory Consistency

Question 1

Under the MESI protocol, Processor A writes a new value to a cache line currently in the Shared state (held by both A and B). What state does Processor B's copy transition to?

• A. Shared — B's copy is automatically updated to the new value via broadcast
• B. Invalid — B's copy is marked unusable; B must fetch the updated value from A or memory on next access
• C. Modified — B holds the updated copy since A's write propagated to it
• D. Exclusive — B becomes the sole holder once A finishes writing

Answer: (B)

MESI uses an invalidation protocol, not an update protocol. When A writes to a Shared line, it sends an *invalidation* message to all other caches holding that line — not the new value. B's copy transitions to Invalid. On B's next read, it must fetch the current value (which A holds in Modified state). The tempting wrong answer is A: a write-update protocol would broadcast the new value, but MESI invalidates instead, deferring the transfer until B actually needs the data.

Question 2

Two threads each modify a different variable, X and Y, that happen to be allocated on the same 64-byte cache line. On a multi-core machine, this causes severe performance degradation. What is this phenomenon called, and why does it occur?

• A. True sharing — X and Y are logically dependent, causing serialized access
• B. False sharing — the coherence protocol treats the entire cache line as the unit of coherence, so writes to either variable invalidate the other processor's copy of the whole line
• C. Cache thrashing — the cache is too small to hold both variables simultaneously
• D. Directory overflow — the directory-based protocol cannot track two variables in the same entry

Answer: (B)

False sharing is the key pathology that demonstrates why coherence operates on cache lines (typically 64 bytes), not individual variables. Even though X and Y are logically independent and never accessed together, the protocol sees one cache line. Every time thread 1 writes X, it invalidates thread 2's cache line (which also contains Y), and vice versa. The result is constant cache misses despite no logical data sharing. The fix is to pad the data structures so X and Y reside on different cache lines.

Question 3

Cache coherence and memory consistency are the same concept: both describe what value a processor reads from a shared memory location.

• T. True
• F. False

Answer: False

These are distinct but complementary concepts. Cache *coherence* is a hardware-level guarantee about a *single memory location*: eventually, all processors agree on its current value (stale copies are invalidated). Memory *consistency* is a higher-level contract about *multiple memory locations*: it specifies what orderings of reads and writes across *different* locations are visible to programs. For example, sequential consistency says each processor sees all writes in a globally consistent order; relaxed models allow reordering for performance. Coherence is the mechanism; consistency is the programmer-facing specification.

Question 4

In a directory-based coherence protocol, a processor that wants to write to a cache line must receive explicit permission from the directory, which then invalidates all other cached copies before granting the write.

• T. True
• F. False

Answer: True

This is exactly how directory-based protocols work. Unlike snooping protocols (where every cache watches a shared bus), the directory maintains a table of which caches hold each line. When a processor requests write permission, the directory sends targeted invalidation messages to all sharers listed for that line, waits for acknowledgments, then grants exclusive write access. This avoids the broadcast overhead of snooping and scales to larger systems, but adds latency for the directory lookup and invalidation round-trip.

Question 5

What is the difference between cache coherence and a memory consistency model, and why does a system need both?

Model answer: Cache coherence ensures that all processors eventually agree on the value of a *single* memory location — stale copies are invalidated so no processor reads outdated data. A memory consistency model specifies the ordering guarantees for reads and writes across *multiple* locations as seen by concurrent threads (e.g., whether a write to X is visible before a subsequent write to Y). You need both: coherence prevents reading stale data for any one variable, while the consistency model tells programmers what ordering assumptions they can safely rely on when reasoning about concurrent programs. Without coherence, programs see phantom old values; without a consistency model, programs have no contract for when writes become visible.

The key insight is the different scopes: coherence is about agreement on one location over time; consistency is about ordering across multiple locations simultaneously. Many bugs in concurrent programs stem from confusing these two levels or assuming stronger guarantees (like sequential consistency) when the hardware provides a weaker model (like x86's TSO).