Cache Coherence Protocols: MSI, MESI, MOESI

When each core has its own cache, the same memory location can exist in several places at once, and a write by one core must not leave the others with a stale copy. Cache coherence is the hardware's way of making all those copies behave like a single memory. Every core gets a correct view, without software having to do anything. This article explains the problem, the rule hardware must follow, and how the MSI, MESI and MOESI protocols work, with step-by-step examples, and what all this costs.

12 min read | Intermediate

What You'll Learn

• Explain the coherence problem and what coherence guarantees
• Describe the MSI states and transitions
• Trace a sequence of reads and writes on two cores
• Explain what MESI and MOESI add and why

The Problem

Take two cores with write-back caches and a variable x, holding 0 in memory:

core 0 reads x            core 0's cache: x = 0
core 1 reads x            core 1's cache: x = 0
core 0 writes x = 5       core 0's cache: x = 5    memory still 0
core 1 reads x            core 1's cache hit: x = 0   WRONG

Core 1 reads a stale value from its own cache. Nothing is wrong with either cache as such, but the system as a whole has broken the idea that memory has one value. Single-core caches never had this problem. It comes from having several copies that can change.

What Coherence Means

A coherent system guarantees two things for each memory location:

• Single writer, multiple readers: at any moment, a location may be written by one core, or read by many, but not both.
• Latest value: a read returns the value of the most recent write to that location.

Together, these mean that all cores agree on the order of writes to any one location. Coherence says nothing about the order of writes to different locations. That is the memory consistency model, covered in Memory Consistency, Atomics and Fences.

Hardware keeps this property one cache line at a time, and it uses a coherence protocol: a set of states for each line, and the rules for moving between them. The caches work together through a shared interconnect, and Snooping vs Directory Coherence explains how they find each other. Most protocols are write-invalidate: before a core writes, it makes sure that all other copies are removed.

The MSI Protocol

The simplest useful protocol gives each line in each cache one of three states:

• Modified (M): this cache holds the only valid copy, and it has been changed. Memory is out of date. This core may read and write freely.
• Shared (S): this cache holds a clean copy. Others may hold it too. This core may read, but not write.
• Invalid (I): this cache has no usable copy.

The picture shows the main transitions for one line in one cache. A local read of an invalid line fetches a copy and enters S. A local write needs exclusive ownership, so the cache sends an invalidate request, and all other copies go to I. It then enters M. If another core then wants to read the line, the core in M must supply the data, and drop to S.

Here is the earlier sequence under MSI:

The last line is the key step. Core 1 misses, because its copy was invalidated, and it gets the new value from core 0. This kind of miss, caused only by another core's write, is the coherence miss mentioned in Miss Types and Average Memory Access Time.

MESI: The Exclusive State

MSI has an annoying inefficiency. A program reads a private variable, and then writes it. The read puts it in S, and the write must then send an invalidate on the interconnect, though no one else has a copy. In single-threaded code this happens all the time, and every such message is wasted.

MESI adds a fourth state:

• Exclusive (E): this cache holds the only copy, and it is clean, equal to memory.

When a read finds that no one else has the line, the line enters E rather than S. A later write moves it from E to M silently, with no message at all, because the cache already knows it has the only copy. If another core reads it first, it drops to S. MESI, in some form, is the base of most protocols used today. The name is sometimes given as the Illinois protocol, after the university where it was first described.

MOESI: The Owned State

MESI has a remaining cost: when a core in M must share a line, the data is also written back to memory. If the line is shared around a lot, that is much unneeded memory traffic. MOESI adds:

• Owned (O): this cache has a modified copy, and other caches may hold shared copies. Memory is out of date, and this cache is responsible for supplying the data, and for writing it back in the end.

A line in M that receives a read request can move to O, and the reader gets S. No memory write takes place. Several sharers can go on reading a value newer than memory, with the owner serving requests. Some processor families use it, while others use a variation called MESIF, in which a Forward state marks one clean sharer as the one that answers. In each case, the point is to reduce slow memory traffic by making caches answer each other.

Write-Invalidate or Write-Update?

An alternative is write-update: instead of invalidating other copies, send them the new value. If they will read it soon, this avoids misses. But most writes are followed by more writes from the same core, so sending every one uses far more interconnect bandwidth than one invalidate. Nearly all designs use invalidation.

What Happens Under the Hood

The table above treated each step as instant, but a real transaction takes several messages and many cycles, and things can happen in between. Two cores may try to write the same line at the same moment. So an interconnect must put requests in a single order per line, and each cache has transient states, such as "waiting for data, want M". A real protocol has many of these in addition to its four or five named states. They are the reason protocols are so hard to verify, and they are often formally checked, because the bugs can be very rare and timing-dependent. Engineers use model checkers, which explore every possible order of messages in a small system.

Coherence must also work with evictions. A line in M that is evicted has to be written back to memory, and a modern protocol must handle a request for a line that is on its way out.

Coherence Beyond the Data Caches

Instruction caches are usually left out of the protocol, or handled more simply, because code rarely changes. This saves work, but a program that writes new code, such as a just-in-time compiler, must run fence.i on RISC-V before it runs that code, so that the instruction cache sees it. Devices are the other case. An engine that reads memory by DMA might find a stale value if the newest data is in a core's cache. A coherent interconnect lets the device's access snoop the caches, so that it sees the same values as the cores. Without that, the driver has to clean and invalidate the caches by hand. TLBs are not kept coherent by this hardware either, which is why TLBs and Page Table Walks needs shootdowns.

An Example: A Spin Lock

A lock shows the protocol under stress. Suppose four cores wait for a lock by repeatedly doing an atomic swap on one word. Each swap is a write, so each needs the line in M. The line moves from core to core all the time, even though the lock is held and nobody can get it. The interconnect fills up with useless traffic, and the core that holds the lock is slowed down too.

A small change in software fixes this. A test-and-test-and-set lock spins on an ordinary load, which keeps a Shared copy in each cache and makes no traffic. Only when the value changes, because the holder wrote it and invalidated those copies, does a waiting core try the atomic swap. The lock now uses the protocol in a way that suits it.

The Cost of Coherence

Coherence is automatic, but it is not free. Each cache needs extra state, and some logic to handle incoming requests. Traffic grows with the number of cores. Misses that go to another core's cache cost tens to a hundred or more cycles. When programs share a line heavily, performance can suffer badly. A spin lock, in which several cores repeatedly write to one word, is a classic example: the line bounces around, and all the cores slow down. Multicore Processors and Shared Memory describes the related trap of false sharing. Coherence makes sharing correct, but not cheap, and well-written software shares as little as it can.

Common Mistakes