MESI States and the Single-Writer Invariant · arch

Computer Architecture · All levels

On this page

Four states, two permissions

Each line in each private cache sits in one of four states. The state crosses dirty/clean with exclusive/shared.

State	Dirty or clean	Exclusive or shared	Memory copy	Store behavior
M (Modified)	Dirty	Exclusive	Stale; must write back	Silent hit, already owner
E (Exclusive)	Clean	Exclusive	Clean	Silent upgrade to M, no bus action
S (Shared)	Clean	Shared	Clean	Needs upgrade with invalidations
I (Invalid)	No data	No access	Clean	Needs ownership miss

Memory is stale exactly when some cache holds the line in M. In every other combination the memory copy is clean.

Only M holds write permission. E holds a promise of exclusivity that makes the next store silent.

Legal edges and forbidden edges

Twelve stable-state edges cover every hit, miss, upgrade, and eviction. Four edges are forbidden, and monitors check for them.

From	Event	To	Bus action
I	Read miss, no other sharer	E	BusRd, data from memory
I	Read miss, sharer present	S	BusRd, data from memory or sharer
I	Write miss	M	BusRdX, invalidate all copies
S	Read hit	S	None
E	Read hit	E	None
M	Read hit	M	None
M	Write hit	M	None
E	Write hit	M	None; silent upgrade
S	Write hit	M	BusUpgr plus one ack per sharer
M	Eviction	I	Writeback to memory
E	Eviction	I	None; line already clean
S	Eviction or remote invalidation	I	None

Forbidden edge	Why it is illegal
Two caches in M on one line	Two writers exist at once
M beside S on one line	A reader observes a dirty owner as clean
E beside S, or two in E	Exclusivity is broken
M entered while a sharer stays valid	The upgrade skipped invalidation

Races need transient states such as IS, IM, and SM between request and acknowledgement. Their full treatment lives in the cache-coherency course; here the stable edges plus the forbidden list are the contract.

Why the Exclusive state matters

A clean read miss with no other sharer grants E instead of S. The later store then upgrades silently to M with no bus traffic.

Without E, every write to clean private data would pay an invalidate round. E removes that cost for single-threaded phases.

Common mistakes

Check yourself A line is in E and the core stores to it. What bus action follows, and what state results?

None follows. The line moves silently to M, and the memory copy becomes stale at that moment.

Check yourself Two caches hold S and both store at once. What must the protocol enforce?

Exactly one winner. One upgrade collects every acknowledgement and reaches M while the loser is invalidated; monitors must never see M beside S or two M copies.

Related topics

Up nextMisses, Upgrades, and Evictions

Practice this lesson Report an error

Four states, two permissions

Each line in each private cache sits in one of four states. The state crosses dirty/clean with exclusive/shared.

State	Dirty or clean	Exclusive or shared	Memory copy	Store behavior
M (Modified)	Dirty	Exclusive	Stale; must write back	Silent hit, already owner
E (Exclusive)	Clean	Exclusive	Clean	Silent upgrade to M, no bus action
S (Shared)	Clean	Shared	Clean	Needs upgrade with invalidations
I (Invalid)	No data	No access	Clean	Needs ownership miss

Memory is stale exactly when some cache holds the line in M. In every other combination the memory copy is clean.

Only M holds write permission. E holds a promise of exclusivity that makes the next store silent.

Legal edges and forbidden edges

Twelve stable-state edges cover every hit, miss, upgrade, and eviction. Four edges are forbidden, and monitors check for them.

From	Event	To	Bus action
I	Read miss, no other sharer	E	BusRd, data from memory
I	Read miss, sharer present	S	BusRd, data from memory or sharer
I	Write miss	M	BusRdX, invalidate all copies
S	Read hit	S	None
E	Read hit	E	None
M	Read hit	M	None
M	Write hit	M	None
E	Write hit	M	None; silent upgrade
S	Write hit	M	BusUpgr plus one ack per sharer
M	Eviction	I	Writeback to memory
E	Eviction	I	None; line already clean
S	Eviction or remote invalidation	I	None

Forbidden edge	Why it is illegal
Two caches in M on one line	Two writers exist at once
M beside S on one line	A reader observes a dirty owner as clean
E beside S, or two in E	Exclusivity is broken
M entered while a sharer stays valid	The upgrade skipped invalidation

Common mistakes

Check yourself A line is in E and the core stores to it. What bus action follows, and what state results?

None follows. The line moves silently to M, and the memory copy becomes stale at that moment.

Check yourself Two caches hold S and both store at once. What must the protocol enforce?

Exactly one winner. One upgrade collects every acknowledgement and reaches M while the loser is invalidated; monitors must never see M beside S or two M copies.