Local Cache miss using MESI Coherence Protocol

Question

My notes on MESI state that there are a few courses of action when we experience a local cache miss on read, depending on the global state of the data (whether other copies already exist, and the state they exist in)
I'm having some trouble understanding how we know the state of the data when we miss on a read.
As far as I'm aware, MESI data is attached to each cache line, so if we have do not have a copy of the required data (we missed on the read) then how do we know the relevant MESI data, so we can make the decision on how to react to the miss? (whether we should read from memory, check for shared/modified copies etc)

Answer 1

In cache coherence protocols there needs to be a single location where the global state can be figured out. There are two ways to implement this location. The first is to use a directory. The second way is to broadcast all information on a shared bus.

If you are using a directory, then the cache that misses sends a message to the directory node that "knows" the global state for that cache line. The directory records the list of caches that have a copy of the cache line and what the state is at each of those caches. (This is easier than it sounds at first, the line is either invalid everywhere, modified in exactly one cache, exclusive in exactly one cache, or shared in more than one cache.)

In a directory-based coherence protocol, when a cache misses it sends a message to the directory for that line. If the directory sees that the line is invalid everywhere it forwards the request to the main memory, which responds to the cache, and the directory updates its state so that it knows the cache has an exclusive copy.

If the directory sees that the line is modified or exclusive in another cache, it forwards the request to that cache, changes the global state to shared, and (in most versions of the algorithm) saves the identifiers of the two caches that are now sharing the line.

If the directory sees that the line is in state shared, it forwards the request to one of the other caches sharing the line, and adds the requester to the list of sharers.

Directory based cache coherence is elegant, and scalable, but requires more than the necessary number of message hops for small systems, so for small systems a hack is used to replace the directory. Instead of a directory, all requests from caches or responses to requests (from other caches or from memory) are placed on a shared bus. Every message is broadcast to all the other nodes on the bus. So in the case of a read miss: the cache that missed broadcasts a request for the data in state "shared". All the other caches and the main memory are listening to the bus (this is called snooping). If one of the other caches has the line in state modified or exclusive, it changes its state to shared and sends the data back on the bus to the requester. If several of the other caches have the line in state shared then they will all try to send the data back on the bus to the requester (and the bus arbiter will ignore all but one of the replies). Finally if none of the other caches have a copy of the line then the main memory will respond with the data. The cache that made the request sees that the responder was main memory rather than another cache, so puts the newly received line in state exclusive.