C.2.3 MESI State Diagram
Keywords: perfbook_html

##
C.2.3 MESI State Diagram

A given cache line's state changes as protocol messages are sent and received, as shown in Figure .

Figure: MESI Cache-Coherency State Diagram

The transition arcs in this figure are as follows:

- Transition (a): A cache line is written back to memory, but the CPU retains it in its cache and further retains the right to modify it. This transition requires a ``writeback'' message.
- Transition (b): The CPU writes to the cache line that it already had exclusive access to. This transition does not require any messages to be sent or received.
- Transition (c): The CPU receives a ``read invalidate'' message for a cache line that it has modified. The CPU must invalidate its local copy, then respond with both a ``read response'' and an ``invalidate acknowledge'' message, both sending the data to the requesting CPU and indicating that it no longer has a local copy.
- Transition (d): The CPU does an atomic read-modify-write operation on a data item that was not present in its cache. It transmits a ``read invalidate'', receiving the data via a ``read response''. The CPU can complete the transition once it has also received a full set of ``invalidate acknowledge'' responses.
- Transition (e): The CPU does an atomic read-modify-write operation on a data item that was previously read-only in its cache. It must transmit ``invalidate'' messages, and must wait for a full set of ``invalidate acknowledge'' responses before completing the transition.
- Transition (f): Some other CPU reads the cache line, and it is supplied from this CPU's cache, which retains a read-only copy, possibly also writing it back to memory. This transition is initiated by the reception of a ``read'' message, and this CPU responds with a ``read response'' message containing the requested data.
- Transition (g): Some other CPU reads a data item in this cache line, and it is supplied either from this CPU's cache or from memory. In either case, this CPU retains a read-only copy. This transition is initiated by the reception of a ``read'' message, and this CPU responds with a ``read response'' message containing the requested data.
- Transition (h): This CPU realizes that it will soon need to write to some data item in this cache line, and thus transmits an ``invalidate'' message. The CPU cannot complete the transition until it receives a full set of ``invalidate acknowledge'' responses. Alternatively, all other CPUs eject this cache line from their caches via ``writeback'' messages (presumably to make room for other cache lines), so that this CPU is the last CPU caching it.
- Transition (i): Some other CPU does an atomic read-modify-write operation on a data item in a cache line held only in this CPU's cache, so this CPU invalidates it from its cache. This transition is initiated by the reception of a ``read invalidate'' message, and this CPU responds with both a ``read response'' and an ``invalidate acknowledge'' message.
- Transition (j): This CPU does a store to a data item in a cache line that was not in its cache, and thus transmits a ``read invalidate'' message. The CPU cannot complete the transition until it receives the ``read response'' and a full set of ``invalidate acknowledge'' messages. The cache line will presumably transition to ``modified'' state via transition (b) as soon as the actual store completes.
- Transition (k): This CPU loads a data item in a cache line that was not in its cache. The CPU transmits a ``read'' message, and completes the transition upon receiving the corresponding ``read response''.
- Transition (l): Some other CPU does a store to a data item in this cache line, but holds this cache line in read-only state due to its being held in other CPUs' caches (such as the current CPU's cache). This transition is initiated by the reception of an ``invalidate'' message, and this CPU responds with an ``invalidate acknowledge'' message.

Quick Quiz C.4: How does the hardware handle the delayed transitions described above? End Quick Quiz