What we will look at now is one of the simpler coherence protocols called MSI.
In MSI, a block can be in one of three states in a cache.
I stands for the invalid state.
A block is in an invalid state either when it is present in the cache, but
its valid bit will not be set, or when it's simply not present in the cache.
So a block that is not present in the cache is treated like it is present, but
in an invalid state.
S stands for the shared state.
A block that is in the shared state in a cache
can be read without any further ado.
But if we write it, we have to do something.
A local read to a block that is in the shared state
keeps the block in the shared state and doesn't do anything else.
And finally, m stands for the modified state.
In this state we can read the block
just like the shared state without sending anything out.
And we can also write to this block by the local core
without sending anything out.
Now, because this is an invalidation-based protocol,
what happens is in the modified state, we are sure that
there are no other cached copies, which is why we are allowed to locally write.
We don't have to tell anybody that we are writing because we know there
is nobody.
So this is sort of equivalent to having valid equals 1, and
dirty equals 1 in a normal cache.
We just call this state modified because it's easier to understand what's going
on this way, than if we have to look at individual bits.
And we will see that with more complicated coherence protocols,
we will add maybe a state or two, but
we will need to add several bits in order to track what's going on.
So now, in the invalid state, we have what's equivalent to valid bit being 0.
Pretty much, we behave like we don't have the block.
Either because we really don't have it, or because we have it but
we are not supposed to read it or write it.
So, when we have a write and
the block is in the invalid state, we move the block to the modified state.
So when we have a local write, meaning the local processor wants to write and
the block is in the invalid state, we move the block to the modified state.
But we cannot just do that.
To do that, we have to put the write request on the bus.
So pretty much this is a write miss,
we have to tell others that it's a write miss.
We get the data and now we can put it in the modified state.
Why? Well,
because our write request on the bus pretty much made sure
that nobody else has a copy any more because
the right request that we made invalidated everybody else.
If we have a block in the modified state and we observe on the bus that another
cache is placing a write on the bus, then we will go to the invalid state.
So we do this when we snoop the write on the bus.
And we cannot just do this and be done.
When we snoop a write on the bus,
because we are in the modified state where we have the dirty copy.
Meaning really the only fresh copy of the data in the system is in our cache.
It's not even in memory because it's dirty here.
We have to write the block back, as we're transitioning to invalid.
And we have to delay the data that would be sent to the write request
until we are done with the write back.
This can be done in two ways.
One is to actually cancel that request, write back, move to invalid and
then that request gets repeated and now gets the data from memory.
Another one is, when we see a write on the bus,
if it's requesting data, then what we do is we suppress the memory response and
feed the data to the processor.
The simpler way of doing things is just to delay that request, write back, and
then let it proceed.
But either way, we have to make sure that before we move from modified to
invalid, we write back the data to memory.
And also make sure that the write request, if it is a write miss and
needs the data, gets our new data not the data from memory.
Now, if we snoop a read on the bus and
we are in the modified state, then we move to the shared state.
So we have snooped a read on the bus,
we will now not be the only one who has a copy of the data.
That means we will not be able to write without telling others.
So we will move to the shared state.
Just like here, we have to also make sure that the block is written back.
The shared state is equivalent to having V=1, and D=0.
So we will not be doing a write back from a shared state,
because it only allows reads anyway.
So as we are moving from the dirty to a clean state,
modified to shared, we are going to write back the data.
The reading processor wants a copy of this block.
Again, we have to either delay that request, do our write back,
change to the shared state, and then let that processor proceed with a read.
Or we have to suppress the memory response that would happen
as a result of this read and
provide our data instead as we are transitioning to a shared state.
If the processor reads a block, and the block is in the invalid state,
then the block will be moved to a shared state.
So in response to a local read, we put a read request on the bus.
And then we get the data, and then we are in the shared state for the data.
Note that the data might come from memory, or
it may come from another cache because it had data in the modified state, and
we need it to get that data.
But as far as this local cache is concerned,
it puts a read request on the bus, it gets the data, and
then it puts that block in the shared state in the local cache.
Then we can do many reads without telling anybody.
If we have a block in the shared state, and we observe
a snooped write on the bus, then we move the block to the invalid state.
We don't have to do anything,
because the block is clean as far as we are concerned.
We don't have to write it back.
We simply have to do the equivalent of resetting the valid bit and
move to the invalid state.
So there is nothing really that we have to do except change the state so
that next time we try to read it we can no longer read it here,
we have to put the read request on the bus again.
If we snoop a read on the bus in the shared state,
we don't need to do anything.
Why? Well because our shared state is okay
with there being other sharers that are only going to read the data.
And finally, all the local reads are okay in the shared state.
If we have a local write, that is not allowed in the shared state.
So a local write that finds the block in the shared state will make us move
the block to a modified state, but we cannot do that silently.
We cannot just move the block and
write to it, what we have to do is put an invalidation on the bus.
Know that things are slightly different when we move from invalid state on
the local right to modify and
when we moved from shared state to a modified state on a local write.
Here we put a write request that asks for a block so that we can write it.
Here we already have the block.
This is the most up to date copy, because if there was another write after
that, we would not have it in the shared state.
So now we want to write to it.
We already have the data,
we just have to put an invalidation request on the bus.
So this invalidation request does not actually request the data.
It just puts a request on the bus for
everybody to invalidate their copies, but it's not asking for the data.
So pretty much, as soon as we put this request on the bus,
we can write because by putting an invalidation on the bus,
we have made sure that now everybody is invalidated.
At which point, we are in the modified state.
Now of course, in the invalid state, whatever we snooped for
this block on the bus doesn't matter.
We're going to stay in the invalid state.
Also in the shared state, it doesn't matter whether we snoop somebody's
request to write, or an invalidation that they put on the bus.
We still move to the invalid state without doing much.
And finally note that if we are in a modified state,
we will observe a write if somebody wants to write, and not an invalidation.
Because if we are in the modified state that means that
everybody else is in the invalid state for this block.
So if they want to write, they'll have to put a write request on the bus.
They cannot be in the shared state and put just an invalidation on it.