A core reads a line nobody else has, then writes it. With the simplest protocol, that costs two bus transactions: one to read the line, and one to announce the write so other copies can be invalidated, even though there are no other copies. Almost every private variable in every program follows this read-then-write pattern. One extra state removes the second transaction.
What states does a cache line need, and what does each extra state save?
The minimum is three states: Modified (this cache has the only copy and it is dirty), Shared (a clean copy, others may exist) and Invalid. That is MSI, and it is correct. But a cache holding a line in S cannot know whether it is the only holder, so every first write must ask the bus, even for private data. And a Modified line read by another cache must be written back to memory before it becomes Shared, even if it is about to be written again.
State | Meaning | May read | May write | Dirty |
|---|---|---|---|---|
M Modified | Only copy; memory is stale | Yes | Yes, silently | Yes |
O Owned (MOESI) | Dirty, but others may hold Shared copies; this cache supplies data and writes back later | Yes | No (must invalidate others first) | Yes |
E Exclusive (MESI) | Only copy; clean | Yes | Yes, silently (becomes M) | No |
S Shared | Clean copy; others may exist | Yes | No (must invalidate others first) | No |
I Invalid | No copy | No | No | — |
The model runs MSI, MESI and MOESI over four caches on a snooping bus, with three workloads of 100 lines, counting bus transactions and memory accesses (reads plus writebacks). In this model, memory supplies clean data; only an M or O cache supplies data itself.
"""MSI, MESI and MOESI on a snooping bus: bus transactions and memory traffic.
Four caches share a bus and a memory. Each cache line is in one state per cache.
Bus requests: BusRd (read miss), BusRdX (write miss), BusUpgr (write to a shared copy).
Data comes from a cache holding the line Modified or Owned, otherwise from memory.
MSI: a read miss always installs Shared; writing it later needs a BusUpgr.
MESI: a read miss with no other copy installs Exclusive; writing E is silent (E -> M).
MOESI: as MESI, but a Modified line that is read by another cache becomes Owned and
supplies the data without writing memory; in MSI and MESI it writes memory back
and becomes Shared.
Three workloads, 100 lines each:
private: each core reads then writes its own lines
producer-consumer: core 0 writes a line, cores 1-3 read it, repeated 100 times on one line
read-shared: every core reads every line
Counts: bus transactions, and memory accesses (reads from memory plus writebacks).
"""
CORES, LINES = 4, 100
def run(protocol, ops):
st = {} # (core, line) -> 'M', 'O', 'E', 'S' (absent = I)
bus = mem = 0
def holders(line, exclude):
return [c for c in range(CORES) if c != exclude and (c, line) in st]
def supply(line, exclude):
nonlocal mem
if not any(st.get((c, line)) in ("M", "O") for c in holders(line, exclude)):
mem += 1 # no dirty owner: memory supplies the data
for core, op, line in ops:
s = st.get((core, line))
if op == "R":
if s:
continue # hit
bus += 1 # BusRd
others = holders(line, core)
supply(line, core)
for c in others:
if st[(c, line)] == "M":
if protocol == "MOESI":
st[(c, line)] = "O"
else:
st[(c, line)] = "S"; mem += 1 # write back on downgrade
elif st[(c, line)] == "E":
st[(c, line)] = "S"
st[(core, line)] = "S" if (others or protocol == "MSI") else "E"
else:
if s in ("M",):
continue
if s == "E":
st[(core, line)] = "M"; continue # silent upgrade
bus += 1 # BusUpgr (from S/O) or BusRdX (from I)
if s is None:
supply(line, core)
for c in holders(line, core):
del st[(c, line)] # invalidate every other copy
st[(core, line)] = "M"
return bus, mem
workloads = {
"private": [op for c in range(CORES) for l in range(LINES) for op in ((c, "R", c * LINES + l), (c, "W", c * LINES + l))],
"producer-consumer": [op for _ in range(LINES) for op in [(0, "W", 0)] + [(c, "R", 0) for c in range(1, CORES)]],
"read-shared": [(c, "R", l) for l in range(LINES) for c in range(CORES)],
}
res = {}
print(f"{'workload':18s} {'protocol':8s} {'bus':>5s} {'memory':>7s}")
for w, ops in workloads.items():
for p in ("MSI", "MESI", "MOESI"):
res[(w, p)] = run(p, ops)
print(f"{w:18s} {p:8s} {res[(w, p)][0]:5d} {res[(w, p)][1]:7d}")
assert res[("private", "MESI")][0] * 2 == res[("private", "MSI")][0]
assert res[("producer-consumer", "MOESI")][1] < res[("producer-consumer", "MESI")][1]
assert res[("read-shared", "MSI")] == res[("read-shared", "MESI")] == res[("read-shared", "MOESI")]
print("PASS: E halves bus traffic for private data; O removes the writebacks of shared dirty data; read-only sharing gains nothing from either")It prints:
workload protocol bus memory
private MSI 800 400
private MESI 400 400
private MOESI 400 400
producer-consumer MSI 400 301
producer-consumer MESI 400 301
producer-consumer MOESI 400 1
read-shared MSI 400 400
read-shared MESI 400 400
read-shared MOESI 400 400
PASS: E halves bus traffic for private data; O removes the writebacks of shared dirty data; read-only sharing gains nothing from eitherPrivate data: MESI halves the bus traffic (800 to 400). Each line is read into E and written silently; MSI needs a second, useless transaction per line.
Producer-consumer on one line: MSI and MESI write the line back to memory every time a consumer first reads it, then serve the other consumers from memory: 301 memory accesses. MOESI keeps it Owned in the producer's cache and supplies it from there: one memory access in total.
Read-only sharing: nothing to gain; all three are identical.
Protocol | States |
|---|---|
MESI | Widely used in processors; the common textbook protocol |
MOESI | Adds Owned for dirty sharing (used by AMD) (fact T23) |
MESIF | Adds Forward: one designated clean sharer answers requests, so many sharers do not all reply (Intel, introduced with QuickPath) (fact T23) |
AMBA CHI | Its own state names (Unique Dirty, Shared Clean and others) with the same ideas (fact A23) |
A protocol implementation (illustrative) let a cache in E respond to another core's read by moving to S without telling the requester that another copy existed. The requester also installed E, and both believed they could write silently. Two cores wrote the line without either invalidating the other, a direct SWMR violation. The fix: a read that finds any other copy must install S, never E, which the requester learns from a "shared" response.
It moves to S, and the requester installs S too, since there are now two copies.
When a consumer reads the producer's M line, the producer moves to O and supplies the data, keeping responsibility for the dirty line instead of writing it to memory.
MSI is the minimum: Modified, Shared, Invalid.
E (only copy, clean) makes private data's first write silent; O (dirty but shared) avoids writebacks when sharing dirty data.
Each state is knowledge that must always be true; every transition that could break it must be covered.