For higher performance in a multiprocessor system, each processor will usually have its own cache. Cache coherence refers to the problem of keeping the data in these caches consistent. The main problem is dealing with writes by a processor.

There are two general strategies for dealing with writes to a cache:

• Write-through - all data written to the cache is also written to memory at the same time.
• Write-back - when data is written to a cache, a dirty bit is set for the affected block. The modified block is written to memory only when the block is replaced.

Write-through caches are simpler, and they automatically deal with the cache coherence problem, but they increase bus traffic significantly. Write-back caches are more common where higher performance is desired. The MSI cache coherence protocol is one of the simpler write-back protocols.

A write-back cache can be described by the diagram to the right, which shows the states and transitions for a block in the cache. The transition labels have the form "event/action". The event can be viewed as the trigger for the transition. The only actions mention here are bus actions. Transitions from a state to itself with no bus actions are omitted.

The following abbreviations are used for events:

• RH - read hit
• WH - write hit
• RM - read miss
• WM - write miss
• Repl - replacement

The following abbreviations are used for bus actions:

• RF - read fetch
• WF - write fetch
• WB - write back

Development of a new idea is easier if you can make an incremental change from a well-established idea. This involves adapting the older idea to new requirements. The development is easier if you have heuristic principles that keep you away from excessive complexity. For developing a multiprocessor write-back cache here are two useful principles:

• Each cache only keeps track of the blocks that it holds; all other blocks are in the invalid state.
• Maintain an invariant: if a cache holds a block in the modified state then all other caches must have that block in the invalid state.

In order to maintain the invariant, each cache must snoop on the bus - it must listen to bus transactions that are performed by other caches.

We arrive at the MSI cache coherence protocol from the simple write-back cache by making the following changes, shown in red in the diagrams below:

• The "unmodified" state is renamed to "shared" to reflect its role in the invariant.
• Transitions from the "modified" state to the "invalid" state and the shared state are added in response to a read fetch or a write fetch, respectively, from another cache. Any transition out of the "modified" state must be accompanied by a write back.
• An invalidate bus action is added, enabling caches to announce transitions from the "shared" state to the "modified" state. In response, other caches that are in the "shared" state must transition to the "invalid" state.