Four nodes, one block: directory walkthroughs and the exam exercise

One block, one home, three shapes

Take the machine of the three papers and of the notes (Fig. 42, p. 468): four nodes N0 … N3, each with a processor P, a cache C, a main memory MM and a directory D, on one interconnection network. The physical address space is statically partitioned among the nodes, so every block has exactly one home. The notes follow one block, B0, whose home is N0: B0 lives in MM0, and its directory entry lives in D0.

The papers write the entry on one line, and so does this lesson: Directory N0 Block B0 | State: Shared | Sharer Bits: 1001. The state is Uncached, Shared or Modified. The four sharer bits are read left to right as N0 N1 N2 N3, so 1001 means that C0 and C3 hold copies. In Modified exactly one bit is set, and it names the owner.

The three roles come from the same lesson. The home holds the block in its memory and keeps its entry; the local node issues the request; a remote node is one whose cache holds a copy, Shared or Modified. One node can play two roles: in the June 2026 entry N0 is the home and, because C0 holds a copy, also a remote.

Lesson 37 pictured the home as a librarian with a lending card for every book. Asked for a book, the librarian has only three ways to answer, and every scenario of this lesson is one of them (Fig. 1). If the copy on the shelf is good — nobody has the book, or readers hold only photocopies — the librarian lends from the shelf. If readers hold photocopies and someone wants to edit, the readers are told to shred them, and they bring nothing back: a photocopy holds nothing the shelf lacks. If one reader holds the edited master, the shelf copy is out of date, and the master must come back first.

The home answers from its own memory whenever memory is up to date (Uncached, Shared); only in Modified must it first fetch the block from the owner. A clean copy is told to invalidate and sends nothing back.

Two things in the entry make this possible. The state tells the home whether its memory can be trusted: yes in Uncached and Shared, no in Modified. The sharer bits tell it whom to contact, so nothing is ever broadcast: only the nodes the bits name receive a message.

Uncached and Shared: the memory answers

Run the notes' walkthrough on B0 (pp. 469–471). Start from Directory N0 Block B0 | Uncached | 0000: no cache holds B0, and MM0 has the only copy. N1 reads B0 and misses. N1 sends a Read Miss to N0; N0 answers with a Data Value Reply read from MM0 and sets N1's bit: Shared | 0100. Two messages, and memory is still up to date, because N1 holds a clean photocopy.

From the same Uncached entry, a Write Miss from N2 costs two messages too. There is nobody to invalidate, so the home replies at once and records N2 as the owner: Modified | 0010. N2 writes into its copy, and from that moment MM0 is stale.

The Shared cases are the ones the papers ask. Take Shared | 0100, where only C1 holds B0, and the two requests of the notes. The table uses the columns of the June 2025 paper.

In the Read Miss from N2, N1 is a remote node — its cache holds a copy — yet it receives nothing. In Shared, memory is up to date, so the home replies from MM0 by itself; asking N1 would only add a message.

In the Write Miss from N2, N1 must lose its copy before N2 may write. The home sends N1 an Invalidate, then the Data Value Reply to N2. N1 invalidates and sends no data back: its copy was clean, identical to MM0, so there is nothing to save.

A write hit on a Shared block

The papers add a scenario the notes never walk: the local node already holds the block Shared and writes it. Take the second access of June 2025, Directory N1 Block B1 | Shared | 0110 and a Write Hit from N2. N2 already has the data, so it needs no block, only permission. It sends an Invalidate to the home N1, which invalidates every other sharer — here the copy in its own cache C1 — and makes N2 the owner: Modified | 0010. That is 1 + k messages for k other sharers, and no Data Value Reply. With k = 0 the request is still sent, because the home must learn that N2 now owns a dirty block.

Two quieter cases

When the local node is the home, only the route changes. In the first access of the July 2024 quiz (question 4), N1 reads B1 and N1 is B1's home: C1 asks D1, MM1 answers, and N1's bit is set. It is the same pair of messages, inside one node, and the entry goes from Shared | 1001 to Shared | 1101.

When a sharer evicts its clean copy, nothing is sent at all. The home is not told, so the bit stays at 1: a stale sharer bit. The next Invalidate to that node finds nothing to invalidate, useless but harmless. Only a Modified copy announces its eviction, with a Data Write-Back.

Modified: the home must ask the owner

Now Directory N0 Block B0 | Modified | 0100: N1 owns a dirty copy, and MM0 is stale. Give the block a value to see what moves: C1 holds x = 7, while MM0 still holds the old x = 3. N2 reads B0 (pp. 472–473).

The read miss needs four messages because the fresh value is in C1, not in MM0. The home sends a Fetch to the owner. N1 answers with a Data Write-Back and keeps a read-only copy, Modified → Shared. The home writes the block into MM0 and forwards it to N2 with a Data Value Reply. The state does not become Modified, because N2 only reads: Shared | 0110 (Fig. 2).

The write miss has the same four-message shape with one word changed: Fetch/Invalidate. N1 sends the block back and drops its copy, Modified → Invalid, and N2 becomes the new owner, Modified | 0010. For a moment MM0 is up to date again, refreshed by the Data Write-Back. But N2 asked for the block in order to write it, and once it writes, MM0 is stale once more.

In the last case the owner starts the conversation: N1 evicts B0 to make room for another block. A dirty copy cannot be dropped, so N1 sends a Data Write-Back; the home writes it into MM0 and clears the entry: Uncached | 0000, memory up to date, one message (p. 475). The notes call N1 "Remote, Owner" here, because a Data Write-Back always travels remote → home.

Every scenario of the protocol is now on the table. At the exam, read it by rows: find the state of the entry, then the request, and copy the shape with the actual node names.

The home's view: one state machine, six invariants

Follow only the entry through the walkthroughs. It goes Uncached → Shared when N1 reads, Shared → Shared when N2 reads too, Shared → Modified when N2 writes, Modified → Shared when another node reads, Modified → Modified when another node writes, Modified → Uncached when the owner evicts. Those six arcs, plus Uncached → Modified, are the whole directory state machine of p. 476 (the notes' Fig. 43): three states, three events — Read Miss, Write Miss and Data Write-Back — described "from the Home directory's perspective".

The table is the MSI protocol of lesson 35 seen from the home. With snooping, every cache watched the bus and took its own transition. Here the caches still have their Invalid, Shared and Modified states, but the decisions are taken in one place, and the bus events have become messages: a snooped read miss on a Modified block is now a Fetch, a snooped write miss is now an Invalidate or a Fetch/Invalidate, sent only to the nodes the bits name. One arc is missing on purpose: there is no Shared → Uncached, because a clean eviction is silent and the home never learns that the last sharer has left.

The notes' own summary of the arcs (p. 477) repeats the slip of p. 473 on the Modified → Shared arc:

The notes close the chapter with six invariants, conditions that must hold "regardless of the sequence of operations" (p. 478). Each is kept true by particular messages:

1. Single owner: at most one cache holds the block Modified. Kept by the Invalidates and the Fetch/Invalidate that go out before the home grants Modified.
2. Memory freshness: Shared or Uncached → memory up to date; Modified → memory stale. Kept by the Data Write-Back that every exit from Modified requires.
3. Sharer set: the sharer bits list every node that holds a copy. Kept by every miss, which sets the requester's bit. After silent evictions the list may name too many nodes, never too few.
4. Owner membership: in Modified the owner is the one bit set.
5. State-transition correctness: states change only through the defined messages. (The notes' list leaves out Write Miss; add it.)
6. Atomicity of updates: the directory processes one request at a time for a given block. With no bus to order the requests, this is how write serialization comes back: two Write Misses that arrive together are served one after the other.

The directory state machine is MSI seen from the home: Uncached means no copies, Shared means clean copies and fresh memory, Modified means one dirty owner and stale memory. Every message of the protocol is there to keep one of the six invariants true.

The exam exercise in seven moves

The three papers ask the same exercise in three forms. July 2024 asks for the definitions and the message lists (Question 1) and adds a three-access quiz (quiz question 4); June 2025 asks for three accesses with home, local, remotes, messages and the final entry (Question 1); June 2026 asks for one access in eleven boxes (Exercise 3). The moves below solve any of them. Here they solve the hook.

1. Home. The node named in the entry: Directory N0 Block B0, so the home is N0. It is fixed by the address and never changes during the exercise.

2. Read the bits. 1001 is N0 N1 N2 N3, so C0 and C3 hold clean copies; the state Shared says that MM0 is up to date.

3. Local. The node the request comes from: a Write Miss from N2, so the local node is N2. C2 holds no copy, so it really is a miss.

4. Remotes. Every other node whose bit is 1, or the owner if the state is Modified: N0 and N3. The home's own cache counts too (unless the home is the requester), so N0 is the home and a remote at once.

5. Shape. Shared and a Write Miss: the memory answers and the sharers are told to leave, 1 + 2 + 1 messages.

6. Messages, each with sender and receiver. N2 → N0 Write Miss (N2, B0); N0 → N3 Invalidate (B0) and N0 → C0, inside N0, Invalidate (B0); N0 → N2 Data Value Reply, with the block read from MM0. From the remotes to the home: nothing, because their copies were clean.

7. Final states. C0 Invalid, C3 Invalid, C2 Modified; Directory N0 Block B0 | Modified | 0010; final owner N2; MM0 stale as soon as N2 writes.

Back to the hook. The answer is no: N0 and N3 send nothing to the home. Their copies are Shared, which means clean, identical to MM0, so there is no newer value to save; they simply invalidate. Only an owner in Modified answers the home, with a Data Write-Back, because only an owner holds a value that memory lacks. If you answered yes, you mixed up the two kinds of remote: a sharer drops its copy, an owner returns it. A real machine would send an invalidation acknowledgement, but the course's seven messages have none.