LOCK prefix vs MESI protocol?

10
votes

What is the purpose of the x86 LOCK prefix, if the MESI protocol prevents other cores from writing to "exclusive"-ly owned data anyway?

I am getting a little confused between what LOCK provides and what MESI provides?

I understand the MESI protocol is about ensuring the cores all see a consistent state of memory, but as I understand, it also prevents cores from writing to memory which another core is already writing to?

2
multithreadingx86lockingcpumesi
Consider the difference between a locked and an unlocked increment: if two cores simultaneously increment a value 0 in memory, they both decide to write 1 to the memory. Cache coherency doesn't prevent the loss of one of the updates. – Kerrek SB
@KerrekSB sorry, I didn't quite understand what you meant. Wouldn't cache coherency ensure only one of the cores owned the cacheline being written to? Therefore if the second core went to modify the cacheline whilst the first was incrementing, MESI would prevent the write until the first core had completed the increment? – user997112
Incrementing isn't an atomic operation. First both cores read the same value (0) off a clean cache line. Then they both decide compute the new value (1). Then they both write the value back. At that writing stage, cache coherency doesn't help because writing to memory is not immediately affected by coherency (only reading from dirtied pages is). – Kerrek SB

2 Answers

6
votes

The MESI protocol makes the memory caches effectively invisible. This means that multithreaded programs don't have to worry about a core reading stale data from them or two cores writing to different parts of a cache line and getting half of one write and half of the other sent to main memory.

However, this doesn't help with read-modify-write operations such as increment, compare and swap, and so on. The MESI protocol won't stop two cores from each reading the same chunk of memory, each adding one to it, and then each writing the same value back, turning two increments into one.

On modern CPUs, the LOCK prefix locks the cache line so that the read-modify-write operation is logically atomic. These are oversimplified, but hopefully they'll give you the idea.

Unlocked increment:

  1. Acquire cache line, shareable is fine. Read the value.
  2. Add one to the read value.
  3. Acquire cache line exclusive (if not already E or M) and lock it.
  4. Write the new value to the cache line.
  5. Change the cache line to modified and unlock it.

Locked increment:

  1. Acquire cache line exclusive (if not already E or M) and lock it.
  2. Read value.
  3. Add one to it.
  4. Write the new value to the cache line.
  5. Change the cache line to modified and unlock it.

Notice the difference? In the unlocked increment, the cache line is only locked during the write memory operation, just like all writes. In the locked increment, the cache line is held across the entire instruction, all the way from the read operation to the write operation and including during the increment itself.

Also, some CPUs have things other than memory caches that can affect memory visibility. For example, some CPUs have a read prefetcher or a posted write buffer that can result in memory operations executing out of order. Where needed, a LOCK prefix (or equivalent functionality on other CPUs) will also do whatever needs to be done to handle memory operation ordering issues.

0
votes

Yep, you're confusing two different things. The MESI protocol is a cache-coherence protocol that ensures each core/processor gets the most up-to-date data from other processors' cache (or mem) when requested. If a cacheline is in 'E' state, that tells the requesting processor that one (and only one) other processor has a copy of this line. That's all it does; the 'E' state does not in anyway prevent the requesting processor from accessing the data; it just states the fact that only one processor has a copy of the data (and that copy is also consistent with that is in memory). So, if a core request the data which is in 'E' state, the core will get a copy of it. The other copy which was in 'E' will be changed based on whether the core is requesting the copy for 'writing' or 'reading'. If it is being requested for writing, the old copy will be invalidated ('I' state) and if it's for reading the old copy will be put into the shared 'S' state.