MESI - MOESI coherence protocols: Exercises — Hardware deep dive

Throughout, the actors are cores C0, C1, C2, …, each with a private cache, all watching a shared bus (see Snooping vs Directory-based protocols). The bus messages are:

The five state letters (four in MESI, five in MOESI): Modified (only copy, dirty), Exclusive (only copy, clean), Shared (clean, others may hold it), Invalid (no valid data), and Owned (dirty and possibly shared — MOESI only).

Level 1 — Recognition

Exercise 1.1

For each situation, name the single MESI state that matches: (a) The line matches memory and no other cache holds it. (b) The line differs from memory and this is the only copy. (c) The line is read-only and may sit in several caches. (d) The line holds no valid data.

Recall Solution

(a) E — Exclusive: only copy + clean. (b) M — Modified: only copy + dirty. (c) S — Shared: clean + possibly-shared. (d) I — Invalid.

The trick: two yes/no questions decide everything — Am I the only copy? and Am I dirty? The table:

	Only copy	Others may hold
Clean	E	S
Dirty	M	(needs MOESI's O)

Exercise 1.2

In MOESI, which single state means dirty and may be shared with other caches?

Recall Solution

O — Owned. It fills the empty "dirty + shared" cell that MESI cannot express. The owner keeps the dirty data, forwards it to readers cache-to-cache, and writes back to memory only when finally evicted. See MOESI in AMD.

Level 2 — Application

Exercise 2.1

Line starts in E in C0. C0 issues a store (write). What message goes on the bus, and what is the new state?

Recall Solution

No message (zero bus traffic). New state M. C0 is the sole holder of a clean line, so no other cache needs invalidating — SWMR is already satisfied. The silent E→M upgrade is exactly the payoff of having an E state at all.

Exercise 2.2

Line is in S in C0. C0 issues a store. What message, and what new state?

Recall Solution

Message BusRdX (Read-for-Ownership). New state M. Because S means others may hold clean copies, C0 must invalidate them (they all go → I) before it becomes the single writer. Then S→M.

Exercise 2.3

Line is in M in C0 (MESI). C0 snoops a BusRd from C1. What must C0 do, and where do C0 and C1 end up?

Recall Solution

C0 must write the dirty data back to memory, supply the value, and transition M→S. C1 ends in S. Why write back? A BusRd means C1 will hold a copy too, so C0 can no longer be the exclusive owner — but memory is stale, so the fresh value must be pushed down before two clean sharers exist.

Exercise 2.4

Same as 2.3 but in MOESI. What changes?

Recall Solution

C0 transitions M→O (not M→S), forwards the data directly to C1 (cache-to-cache), and does not write memory. C1 ends in S. C0 remains the owner and the only cache responsible for the eventual write-back. This is the whole point of O: skip the memory round-trip.

Level 3 — Analysis

Exercise 3.1 (MESI full trace)

Address X, initial value in memory = 5. All caches start I. Trace the states after each step:

C0 reads X
C1 reads X
C2 reads X
C1 writes X = 9
C0 reads X

Report (C0, C1, C2) after every step and count the BusRdX messages issued.

Recall Solution

Step	Action	Bus msg	C0	C1	C2
1	C0 read	BusRd	E	I	I
2	C1 read	BusRd	S	S	I
3	C2 read	BusRd	S	S	S
4	C1 write	BusRdX	I	M	I
5	C0 read	BusRd	S	S	I

Step 1: no other holder → C0 lands in E.
Step 2: another copy appears → both go S (C0 does E→S).
Step 3: three clean sharers, all S.
Step 4: C1 stores from S → BusRdX, invalidating C0 and C2, then S→M.
Step 5: C0 read-miss → BusRd; C1 (in M) must write back and go M→S; C0 lands in S.

BusRdX count = 1 (only step 4).

Exercise 3.2 (MOESI same trace)

Repeat Exercise 3.1 in MOESI. What are the states after step 5, and how many memory writes occur across the whole trace? Compare to MESI.

Recall Solution

Steps 1–4 identical (C1 = M, C0 = C2 = I). Step 5: C0 read-miss → BusRd. C1 is in M → goes M→O, forwards the value 9 to C0, no memory write. C0 lands in S. Final: C0 = S, C1 = O, C2 = I.

Memory writes in MOESI = 0 (data lives dirty in C1's O state until eviction). Memory writes in MESI = 1 (step 5's M→S write-back). MOESI saved one memory round-trip by forwarding cache-to-cache. See Write-back vs Write-through caches for why avoiding memory writes is the whole game.

Level 4 — Synthesis

Exercise 4.1

Two threads increment counters that happen to sit in the same cache line (see False Sharing). C0 writes counter A, C1 writes counter B, alternating 4 times each (C0, C1, C0, C1, …), starting from all-I. Using MESI, how many BusRdX messages fire in total across these 8 writes? Assume the line starts uncached.

Recall Solution

Even though A and B are different variables, they live in one line, so writes ping-pong ownership.

Write 1 (C0): line is I → BusRdX (fetch + own) → C0 = M. (1)
Write 2 (C1): C0 is M → C1 issues BusRdX, C0 writes back + →I, C1 = M. (2)
Write 3 (C0): BusRdX → C1 writes back + →I, C0 = M. (3)
… the pattern repeats: every one of the 8 writes issues a BusRdX.

Total BusRdX = 8.

This is false sharing: no logical data is shared, yet the line bounces on every write. The fix is to pad A and B onto separate cache lines so each stays privately in M/E.

Exercise 4.2

Take Exercise 4.1's 8-write ping-pong. In MESI each ownership transfer forces a memory write-back (the losing M cache must flush). In MOESI, dirty data forwards cache-to-cache. Yet here the requester writes (BusRdX), not reads (BusRd). Does MOESI's O state help this false-sharing pattern? Explain.

Recall Solution

No — O does not help here. The O state only benefits BusRd (read) requests, where the owner can forward dirty data and stay owner. But this pattern is all BusRdX (writes), and a BusRdX invalidates the previous owner outright — there is no "shared dirty" outcome to preserve. Each write still transfers exclusive ownership.

MOESI can still forward the dirty bytes cache-to-cache instead of via memory, saving latency, but the number of ownership transfers is unchanged and the line still ping-pongs 8 times. The real cure is structural (padding), not protocol choice.

Level 5 — Mastery

Exercise 5.1 (state counting)

MESI needs enough bits per line to encode its states; MOESI adds one more state. Compute the minimum bits per cache line for (a) MESI and (b) MOESI, and explain the jump.

Recall Solution

A state field needs $⌈ lo g_{2} N ⌉$ bits for $N$ states. (a) MESI: $N = 4 \Rightarrow ⌈ lo g_{2} 4 ⌉ = 2$ bits. (b) MOESI: $N = 5 \Rightarrow ⌈ lo g_{2} 5 ⌉ = 3$ bits. Going from 4 to 5 states crosses a power-of-two boundary ( $2^{2} = 4 < 5 \leq 8 = 2^{3}$ ), so one extra bit is forced even though only one state was added. With 3 bits you could encode up to 8 states (room for MESIF-style extras too).

Exercise 5.2 (amortised cost argument)

A shared, mostly-read counter is read $R$ times and written $W$ times by a set of cores, always in MOESI. Suppose each read from a remote owner costs $c$ (cache-to-cache) and each memory write-back (only on eviction) costs $m$ , with $m > c$ . If the owning line is evicted exactly once at the very end, write the total data-movement cost as a function of $R$ , and compare to a hypothetical write-through scheme where every one of the $W$ writes costs $m$ to memory.

Recall Solution

MOESI: the owner forwards to each of the $R$ readers cache-to-cache ( $R \cdot c$ ) and performs one write-back on the final eviction ( $m$ ). Writes among the cores update the owner's dirty copy locally (no memory cost while owned). Total: $Cost_{MOESI} = R c + m .$ Write-through: every write reaches memory: $Cost_{WT} = W m (+ R c for the reads) .$ Since $m > c$ and typically $W ≫ 1$ , MOESI's single deferred write-back dominates the savings: it replaces $W$ memory writes with 1. The forwarding term $R c$ is common to both, so the net MOESI advantage is $Δ = W m - m = (W - 1) m .$ This is precisely why write-back + ownership beats write-through under write-heavy sharing — see Write-back vs Write-through caches.

Exercise 5.3 (design synthesis)

You are told a workload has (i) many uncontended per-core locks and (ii) some hot read-shared dirty data forwarded between cores. Which two state letters carry the most value for this workload, and why? Which real vendor lineage matches best?

Recall Solution

E carries the lock case: an uncontended lock is read (→ E) then written (E→M silently, zero bus traffic). Without E, every lock acquisition would broadcast.
O carries the hot-dirty-shared case: the owner forwards dirty data cache-to-cache on each BusRd, avoiding memory writes. Both matter, so a MOESI design fits best — matching AMD's lineage. (Intel's MESIF instead adds Forward to pick a single responder among clean sharers — a different optimisation aimed at reducing redundant clean-copy responses rather than dirty forwarding.)

Wrap-up recall

Recall One-line answers (cover them!)

Bits per line: MESI vs MOESI? ::: 2 vs 3.
Which state gives free (silent) writes? ::: E, via E→M.
Which message invalidates others? ::: BusRdX.
Does MOESI fix false sharing? ::: No — it is a data-layout problem.
On BusRd in MOESI, an M line becomes __ and forwards data. ::: O (Owned).
Memory writes in Ex 3.1 (MESI) vs Ex 3.2 (MOESI)? ::: 1 vs 0.