cachingcpu-architecturecpu-cachemesi

MSI: When shared and invalid states can occur at the same time

So, as the title says, is it possible that Processor 0 has line A with a Shared (S) state, and Processor 1 has line B with an Invalid (I) state?

Imagine the following situation:

If P2 makes a read request for Line A, what is P1 final state? Shared or keeps Invalid?

Solution

  • TL;DR

    P1's line A will still be in Invalid state. An Invalid state cannot be changed by other processors' actions.
    Both P0 and P2 will have line A in Shared state.

    On the Wikipedia's page for the MSI protocol there's the state machine description of the algorithm.
    Along with the English description, there are two pictures.

    Given a set of processors and their relative cache lines, a processor can either be "active" by making one action among "load/read" and "store/write", or can be "passive" by snooping an event on the bus.

    The input to the MSI (and similar) protocol is either an action or a bus event. For simplicity Wikipedia split the state machine in two: one when the input is an action and one when the input is a bus event. This way you can use one picture to calculate the new states for the lines of the active processor (which is exactly one) and the other picture for the states of the lines of the passive processors.

    Let's say processor X is the active one, thus making a load or a store.

    The first picture describes how the cache lines state changes for processor X (the active processor):

    enter image description here

    Each label has the form x/y where x is the input action (either PrRd for a load/read or PrWr for a store/write) and y is the bus event that is emitted ("-" means no event is emitted on the bus).

    The second picture is used similarly but for the passive processors (any processor but processor X):

    enter image description here

    Each label here is again a x/y pair but x is a bus event and y is a bus action.

    The bus events are:

    Of course, a Flush is the act of writing a line to memory. Wikipedia considers it a bus transaction (I consider it a bus action since it's not used as an input).

    We are now ready to answer your question.

    P2 is the active processor and needs to read line A, so it performs a PrRd. The first picture tells us that its line A will end up in S state and that a BusRd is issued on the bus (note that this is a mental model, real hardware won't probably send a special transaction, rather it will detect the read itself).

    P2: LineA -> Shared

    Both P0 and P1 are passive processors and both see the BusRd.
    P0 has the line in state Modified, the second picture tells us that it will flush the line (making the last value available to P2) and set line A to state Shared.
    P1 has the line in state Invalid, from the second picture we see that there is no way to escape an Invalid state for a passive processor. Specifically, the BusRd input will set the state of line A to Invalid again (it is actually ignored).

    So after the read from P2 we have:

    P0: LineA -> Shared
P1: LineA -> Invalid
P2: LineA -> Shared