MESI Protocol & Cache Coherence

By the end of this lesson, you will be able to...

• Trace a cache line through Exclusive, Shared, Modified, and Invalid states.

• Explain why a writer must obtain ownership before changing a shared line.

• Distinguish cache coherence, false sharing, and memory-ordering questions.

Idea in one sentence: MESI keeps private cache copies coherent by making write ownership exclusive and invalidating copies that would otherwise become stale.

Core Insight

Two threads run on different cores. Both read a shared counter with value 4. Each core now has a nearby cached copy.

Core A changes the counter to 5. Core B reads again.

The naive cache model says that B should simply use its fast local copy. That copy still contains 4.

Private caches create a correctness problem as soon as shared data can change. The machine needs a rule that answers:

Who has a valid copy?
Who may write?
What must happen to the other copies before a write?
Where can a later reader obtain the current line?

MESI is one family of answers. It tracks state at cache-line granularity and allows only one owner to modify a line at a time.

The Four States Are Permissions

MESI names four stable states. Real processors add transient states and protocol variants; this lesson uses the stable states as a teaching model.

Modified (M)

This cache holds the only valid copy known to the coherence protocol, and its data differs from the copy in lower memory. The cache owns the line and may write it locally.

Exclusive (E)

This cache holds the only valid copy, and the data still matches lower memory. Because no other cache shares it, a local write can usually move E -> M without first invalidating peers.

Shared (S)

Multiple caches may hold valid clean copies. A core may read locally, but it cannot modify the line until it obtains write ownership and invalidates other sharers.

Invalid (I)

The local bits cannot be used as a valid copy of the line. A read or write needs a coherence transaction to obtain the line and appropriate permission.

These states are easier to remember as permissions:

A Line Moves from Private to Shared

Start with cache line L, which contains counter x = 4. Neither core has it cached.

Core A: I
Core B: I

Step 1: A reads

A misses and requests the line. In this simplified trace, no other cache holds it, so A receives a clean exclusive copy.

A: E(x=4)
B: I

Step 2: B reads

B requests the same line. The coherence system discovers A's copy. Both cores may now hold clean shared copies.

A: S(x=4)
B: S(x=4)

Nothing has been copied incorrectly. Shared read-only access is exactly what caches are good at.

Step 3: A writes

A cannot change its S copy while B's copy remains valid. It requests ownership. B receives an invalidation and moves to I. A moves to M and writes 5.

A: M(x=5)
B: I

Step 4: B reads again

B's local line is invalid, so it must request the current data. Depending on the implementation, the modified owner or another level in the hierarchy supplies it. A common simplified outcome is that both end with shared clean views of 5 after the required protocol work.

A: S(x=5)
B: S(x=5)

The important result is not the exact bus message name. It is the permission change:

input: A and B share one clean line
  -> A requests the right to write
  -> B's copy becomes invalid
  -> A modifies the only writable copy
  -> B later obtains the current line before reading it

Without the invalidation step, B could keep treating 4 as valid after A writes 5.

Check: Why can A change E -> M more cheaply than S -> M?

Think first, then reveal.

Answer: E already says no other cache has a valid copy, so A does not need to invalidate sharers. In S, peers may hold the line, so A must obtain exclusive ownership first.

Ownership Movement Is the Performance Cost

Coherence preserves a usable shared-memory abstraction, but write ownership is not free.

If A and B alternately update the same line, the line repeatedly changes owner:

A owns and writes
  -> B requests ownership; A loses it
  -> B writes
  -> A requests ownership; B loses it
  -> repeat

Each handoff can require coherence messages and waiting. Adding cores does not help when all useful work depends on one write-heavy line. The extra cores become extra contenders.

This explains several familiar symptoms:

• a shared counter scales worse than per-thread counters;
• a contended lock becomes hotter as threads increase;
• a shared queue's head or tail metadata limits throughput;
• read-mostly data behaves well until frequent writes begin.

The source-level operation may be one integer increment. The hardware work includes obtaining permission for the entire cache line.

Compare a Read Trace with a Write Trace

The difference between sharing and contention becomes clearer if the address never changes.

First, let sixteen cores repeatedly read one immutable configuration flag. After their initial misses, the line may remain S in many private caches:

core A reads -> local Shared hit
core B reads -> local Shared hit
core C reads -> local Shared hit

The line is widely shared, but no core asks the others to surrender it. More readers can still encounter limits elsewhere, such as bandwidth or instruction overhead, but the stable shared line is not bouncing between write owners.

Now let the same cores increment a shared progress counter. An atomic operation protects the value from lost updates, yet every successful update still needs exclusive write permission:

A obtains ownership -> increments
B obtains ownership -> increments
C obtains ownership -> increments

The word atomic describes the operation's correctness contract. It does not mean “physically local” or “free from coordination.” The cache line serializes the writers because only one may hold the writable version at a time.

This distinction helps when reading profiles. A hot atomic instruction can be both necessary and correctly implemented while still being the scalability limit. The question is not “is the atomic broken?” It is “does every request need to participate in this single ownership sequence?”

Possible design changes alter that sequence:

• per-thread counters turn frequent global writes into local writes and a later merge;
• batching requests ownership once for several logical updates;
• approximate counters exchange exact immediacy for lower coordination;
• partitioned queues give different workers different hot metadata lines.

Each option changes semantics. A sharded counter may lag; batching may lose the newest partial batch during a crash; partitioning may require rebalancing. Removing coherence traffic is not a free optimization—it moves coordination somewhere else.

False Sharing: Different Variables, Same Line

Cache coherence tracks lines, not programming-language fields.

Consider a simplified structure:

struct Counters {
    long requests_a;
    long requests_b;
};

Thread A updates requests_a. Thread B updates requests_b. The fields are logically independent. If they occupy the same cache line, each write still requests ownership of that line.

Thread A writes field A -> line moves to A
Thread B writes field B -> same line moves to B
Thread A writes field A -> same line moves back to A

This is false sharing. The sharing is false at the variable level but real at the cache-line level.

Possible mitigations include:

• separate frequently written per-thread data;
• pad or align hot fields when evidence supports it;
• shard counters and combine them less often;
• reduce write frequency with batching.

Padding everything is not a universal fix. It increases memory footprint and can hurt locality. First prove that independently written data shares a hot line.

Check: Two read-only fields share a cache line across many cores. Is that automatically false sharing?

Think first, then reveal.

Answer: No. False sharing is harmful when independent writes cause ownership and invalidation traffic. Shared reads can coexist in S without the same ping-pong behavior.

Coherence Is Not the Whole Memory Model

Coherence answers a narrow question about one memory location: how do cached copies participate in a single order of writes to that location?

Memory consistency asks a broader question: in what orders may operations to different locations become visible?

Suppose A writes data = 42 and then writes ready = true. B reads ready and then reads data. Coherence manages the lines containing ready and data, but MESI alone does not specify every ordering the program may observe across those two locations. The language and processor memory models, together with synchronization operations, define the required ordering.

This boundary matters because “the caches are coherent” is not a substitute for atomics, locks, or other synchronization. Coherence makes those mechanisms implementable; it does not infer the program's intended happens-before relationship.

There is a useful two-question test:

1. Same location: after writes to one line, can a reader keep treating an invalid old copy as current? That is a coherence question.
2. Different locations: if a reader observes ready = true, must it also observe the earlier write to data? That is an ordering and synchronization question.

Answering the first does not settle the second. Source-language atomics and locks connect the program's required ordering to the processor mechanisms.

Signals and Boundaries

Suspect coherence pressure when performance worsens with more writing cores even though the amount of useful work stays similar.

Useful evidence includes:

• contention or lock profiles;
• cache-to-cache transfer or coherence-related hardware counters when available;
• throughput as thread count changes;
• a comparison between shared and sharded state;
• data-layout experiments that isolate a suspected false-sharing line.

MESI is not the only coherence protocol, and stable-state diagrams omit many implementation details. Use this model to explain ownership and invalidation. Use architecture-specific documentation and measurement for exact events and costs.

The practical trade-off is how much immediacy and centralized precision the workload actually needs. Less frequent aggregation can reduce ownership movement, but readers then observe an older or approximate total. State that semantic change before comparing performance.

A useful experiment changes one suspected ownership pattern while preserving the work. Run the same request mix with one shared counter and with per-worker counters combined once per second. Sweep the number of writing threads. If the shared version flattens while the sharded version keeps scaling, and the result survives repeated runs, the evidence supports a hot-line hypothesis. If both flatten at the same point, investigate another shared resource before changing layouts.

Practice: Explain the Hot Line

A request counter is protected by one atomic increment. With one thread, the service handles 100 units of work in an illustrative benchmark. With sixteen writing threads, useful throughput grows only slightly while time in the increment rises sharply.

Explain one likely mechanism and propose one experiment.

Model answer: The atomic counter requires write ownership of one cache line. More writers make that line move among cores, so coherence and serialization limit scaling. Compare the shared counter with per-thread or sharded counters combined periodically. Measure total throughput and counter-update cost; if sharding helps, the ownership hotspot was material.

Resources

• [BOOK] A Primer on Memory Consistency and Cache Coherence — Focus: Separate stable MESI intuition from memory-consistency and transient-state details.
• [DOC] Linux Kernel: False Sharing — Focus: Connect cache-line ownership to practical data-layout diagnosis.
• [DOC] Intel 64 and IA-32 Architectures Optimization Reference Manual — Focus: Use architecture-specific guidance for sharing, alignment, and measurement.

Key Takeaways

• MESI states describe whether a cache-line copy is valid, shared, or exclusively writable.
• A writer must invalidate sharers before modifying a shared line.
• Write-heavy ownership movement, not shared reading alone, creates coherence pressure.
• False sharing happens because hardware coordinates cache lines rather than source-level fields.
• Coherence for one location does not replace synchronization across locations.