Definition
Modified Shared Invalid Protocol
The Modified-Shared-Invalid (MSI) protocol is a cache coherence protocol for write-back caches. It tracks each cache block with one of three states:
- Modified (M) — this cache has the only valid copy. The block is dirty, so it may differ from main memory. Reads and writes are allowed.
- Shared (S) — this cache has a clean copy. Other caches may have the same block. Reads are allowed, but writes need an upgrade.
- Invalid (I) — this cache has no usable copy. Reads and writes miss.
Requests
MSI distinguishes local processor requests from snooped bus requests.
| Request | Source | Meaning |
|---|---|---|
| PrRd | Local processor | The processor reads the block. |
| PrWr | Local processor | The processor writes the block. |
| BusRd | Bus | Another cache needs a readable copy. |
| BusRdX | Bus | Another cache needs exclusive write permission. |
| Flush | Bus or memory action | A dirty block is supplied or written back. |
Snoopy Bus
The bus is snooped: every cache observes bus transactions made by other caches and updates its own state for the same block.
The usual flow is that a local cache converts a processor request into a bus transaction. Other caches snoop that transaction and either keep, downgrade, or invalidate their copy.
Permissions
| State | Valid | Dirty | Permission |
|---|---|---|---|
| M | Yes | Yes | Read and write. |
| S | Yes | No | Read only. |
| I | No | No | No access. |
The central rule is that only one cache may write a block at a time. A write therefore requires M state. If the block is in S or I, the cache must issue BusRdX before writing.
Transitions
The local row shows what happens when this processor accesses the block. The snooped row shows what happens when another cache accesses the same block.
Self-transitions
Some requests do not change the state. For example, PrRd in M remains M, and BusRd in S remains S. The diagram shows these as small loops.
| Current | Request | Action | New State |
|---|---|---|---|
| M | PrRd | Read hit | M |
| M | PrWr | Write hit | M |
| M | BusRd | Supply dirty data, downgrade | S |
| M | BusRdX | Supply dirty data, invalidate | I |
| S | PrRd | Read hit | S |
| S | PrWr | BusRdX on bus, upgrade | M |
| S | BusRdX | Invalidate block | I |
| S | BusRd | No state change | S |
| I | PrRd | BusRd on bus, fetch block | S |
| I | PrWr | BusRdX on bus, fetch block | M |
Cases
Read miss
If this cache is in I and the processor reads, it issues BusRd. The block is fetched in clean form, so the new state is S.
Write miss
If this cache is in I and the processor writes, it issues BusRdX. Other copies are invalidated, so the new state is M.
Upgrade
If this cache is in S and the processor writes, it issues BusRdX. The cache already has the data, but it needs exclusive permission before the write. The new state is M.
Intervention
If this cache is in M and another cache issues BusRd, this cache supplies the dirty data and downgrades to S. The other cache receives a clean shared copy.
Invalidation
If another cache issues BusRdX, this cache loses permission to use its copy. S becomes I. M also becomes I, after supplying or writing back the dirty data.