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
Paul E. McKenney
2011-12-16