Cache coherence problem: Question bank — Hardware deep dive

Before we start, one reminder of the vocabulary you must not blur:

Valid copy ::: a cached line whose stored value equals the true logical value; a read may safely return it.
Stale copy ::: a cached line that the core still trusts, but whose value no longer matches the latest write elsewhere.
Propagation / serialization ::: the two halves of coherence — does the write ever reach others, and do all cores agree on the order of writes to one address.

True or false — justify

Write-through caches make the cache coherence problem disappear.

False. Write-through keeps memory fresh, but it never touches other cores' cached copies, so a reader still returns its own stale line — the cache-vs-cache gap survives.

Coherence and consistency are two names for the same property.

False. Coherence governs a single address across caches; consistency governs the ordering of operations across different addresses. One can hold without the other.

If every core used only read-only data, you would still need a coherence protocol.

False. With no writes there are no stale copies — every valid copy stays equal forever, so the coherence invariant is never threatened.

A system with only one core and one cache can still suffer cache incoherence.

False. Incoherence needs two or more private copies of one address; a lone cache has nobody to disagree with (though it can still be stale versus memory — a different issue).

Write-invalidate and write-update produce identical bus traffic for the same program.

False. Repeated writes to one line cost one invalidate versus many update broadcasts; tight producer/consumer sharing reverses which is cheaper. Traffic depends on the access pattern.

"Write propagation" alone is enough to call a system coherent.

False. You also need write serialization — all cores must observe writes to that location in the same order, otherwise two cores can end up believing different final values.

A dirty write-back line means main memory is momentarily wrong.

True. Write-back holds the new value in the cache and defers the memory update, so memory lags until the flush — that is the memory-vs-cache gap, separate from cache-vs-cache.

Broadcasting the new value to all caches on every write (update protocol) guarantees coherence.

True, it does restore equal valid copies — but it is often wasteful, spraying the bus on writes nobody is currently reading.

Spot the error

"A writes X=10 with write-through, so B will now read 10."

The error: write-through updates memory, not B's cache. B's own copy is still 10-was-5 stale, so B reads 5 until it is invalidated or updated.

"Invalidate is always better than update, no exceptions."

The error: "always." In tight sharing (write once, read immediately, repeatedly), invalidate forces the reader into a miss each round; update avoids it. Pattern decides.

"With write-back and no protocol, only B's cache is stale; memory is fine."

The error: memory is also stale — write-back hasn't flushed A's dirty line, so both the cache-vs-cache and memory-vs-cache values still read 5.

"Coherence guarantees that if I write X then write Y, everyone sees X before Y."

The error: that is a cross-address ordering claim — a consistency question, not coherence. Coherence only orders writes to the same location.

"An update protocol sends one message per write, so for three writes to X it sends three; invalidate sends three too."

The error: after the first write invalidate grants exclusive ownership, so the next two writes are silent — one message, not three.

"Since B never wrote X, B's copy can't be the stale one."

The error: staleness is about being out of date, not about who wrote. B's untouched copy goes stale the instant A writes X. :::

"The invalidate turns B's read into a hit with the fresh value."

The error: invalidate turns it into a forced miss; the miss is what fetches the fresh value. The value is fresh because the hit was denied.

Why questions

Why does the problem require private caches, not just any caches?

Because incoherence is disagreement between separate copies. A single shared cache holds one copy per address, so there is nothing to fall out of sync.

Why is write-serialization needed on top of write-propagation?

Propagation only promises writes arrive; without a common order, two cores could apply writes W1,W2 in opposite orders and settle on different final values.

Why do real CPUs (MESI and friends) choose invalidate over update?

Real workloads write the same line repeatedly (loops, counters); invalidate charges once for a burst of writes, update pays per write — invalidate scales better on bus traffic.

Why can a read "miss" actually be the fix rather than a failure?

Because after an invalidate the stale copy is gone; the miss is the mechanism that forces the core back to the true value instead of trusting garbage.

Why does the coherence invariant only compare valid copies?

An invalidated line is marked "don't trust me," so it can hold any leftover bits without violating anything — the invariant only demands agreement among copies a read may return.

Why doesn't flushing dirty lines to memory by itself make the system coherent?

Flushing closes the memory-vs-cache gap, but other cores still read their own cached copies, not memory — the cache-vs-cache gap needs invalidate or update.

Edge cases

What happens if two cores write the same X at the "same" time?

The protocol must serialize them into one order (via the bus or directory); exactly one write wins the ownership race, and all cores observe that single agreed order.

What if a core writes a line no other cache holds?

No invalidate is even needed — there are no other valid copies, so the invariant already holds; the write is purely local (this is the payoff of an "Exclusive" state in MESI).

What if X and Y sit in the same cache line but cores touch different variables?

The protocol tracks whole lines, so a write to X invalidates the line holding Y too — the cores fight over a line they don't logically share. That is false sharing.

Is a read-only shared line ever invalidated?

Not until someone writes it. Many cores can hold the same clean copy simultaneously; the first write is what triggers invalidation of all the others.

Does coherence say when a write becomes visible, exactly?

No — only that it becomes visible eventually (propagation) and in a consistent order (serialization). Precise timing across addresses is the job of consistency models.

What if a core reads X, is invalidated, then reads again with no new write?

Its first copy was dropped, so the second read misses and re-fetches the same valid value — correct but slower; pure invalidation overhead, no incoherence.

Does snooping vs directory change whether coherence holds?

No — both enforce the same invariant; they differ in how the invalidate/update reaches other caches (broadcast vs targeted), affecting scalability, not correctness.