Can one cache write while another keeps a read-only copy? For the invalidation protocols in this course, no: writable permission excludes every other cache's usable copy of that line. A writer is allowed to read its own copy. When nobody has writable permission, any number of caches, including zero, may have read-only permission. A writable holder need not be executing a store right now.

Prerequisite: read the course model. SWMR is a rule about permitted accesses at a logical instant, not a count of requests or occupied data arrays. It divides the life of a line into a write epoch (an interval in which exactly one cache may read and write) and a read epoch (an interval in which any number of caches, including none, may only read). A pending GetM is not permission to write. This permission-based definition follows the Primer, second edition, Chapter 2.

Classify permissions before values

These are independent classifications, not a transaction history. I has no usable value: '-' does not mean zero. M and E (MESI, MOESI) are writable; S and O are read-only. O names dirty responsibility, never write permission. H's directory entry exclusive(C0) records exclusive permission without necessarily distinguishing E from M after a silent local store. It is neither the location X nor a cache state. The MESI permissions agree with gem5's stable-state definitions.

A cold write acquires permission first

Use MSI for this trace. Reset is C0 = I, C1 = I, H = U, memory = 0. H serializes requests for X: it handles them one at a time in a single order. Because no cache holds X, memory is authoritative (it holds the value the next reader must get), so H reads it inside the home node; that read is a note, not a cache request.

IM^D is the transient state 'was I, wants M, waiting for Data'; C0 may neither load nor store in it. At step 2 the M grant assigns writable permission and dirty responsibility even though the bits still equal memory. H keeps its pending entry in that row; the next row, labelled (assumed), is the course model's assumption that H learns the grant has been delivered and records exclusive(C0). At L a write-back cache changes its local value without updating memory. The newest-data column also names Data in flight, so no value disappears between rows.

Check permissions without comparing values

This small program classifies stable permission vectors only. A state outside the chosen protocol, such as O in MESI, fails the membership assertion: the program refuses to mix protocol variants rather than returning a verdict. Beyond SWMR it enforces one protocol rule, at most one dirty-responsible holder (M or O). It checks neither transaction completion nor data preservation; the next lesson adds the value obligation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

states_by_protocol = {
    "MSI": {"I", "S", "M"},
    "MESI": {"I", "S", "E", "M"},
    "MOESI": {"I", "S", "E", "M", "O"},
}
def legal(protocol, states):
    assert all(s in states_by_protocol[protocol] for s in states)
    writers = [i for i, s in enumerate(states) if s in {"M", "E"}]
    swmr = len(writers) <= 1 and (
        not writers or all(i == writers[0] or s == "I"
                           for i, s in enumerate(states)))
    # Two O holders are read-only, so SWMR alone would pass them, but each
    # would believe it alone must write the dirty line back: H records one
    # dirty-responsible holder, so the protocol allows at most one M or O.
    one_responsible = sum(s in {"M", "O"} for s in states) <= 1
    return swmr and one_responsible
assert legal("MSI", ["I", "I"])
assert legal("MSI", ["S", "S"])
assert legal("MSI", ["M", "I"])
assert legal("MESI", ["E", "I"])
assert legal("MOESI", ["O", "S"])
assert not legal("MSI", ["M", "S"])
assert not legal("MESI", ["M", "M"])
assert not legal("MOESI", ["E", "S"])
assert not legal("MOESI", ["O", "O"])
try:
    legal("MESI", ["O", "S"])
    raise SystemExit("O must be rejected in MESI")
except AssertionError:
    pass
print("PASS: stable permission vectors classified, O rejected in MESI")

Related topics

• Course Model

• Next: The Data-Value Invariant