缓存一致性与写入同一元素

Question

以下结果是在 Intel (haswell) x86_64 上生成的。假设我们有一个整数数组 int32_t A[32]={0}，请考虑以下函数，其中 func(&A[i]) 从两个不同的线程调用。

void func(int32_t *elem) {
  for (int i = 0; i < 10000; i++) 
    *elem=*elem+1;
}

假设Thread1调用func(&A[0])，考虑以下三种在Thread2上调用func的场景：

Thread2调用 func(&A[16]):不会有 A[0] 和 A[16] 存在于不同的缓存行中，最终结果是正确 A[0]=10000, A[16]=10000
Thread2调用 func(&A[1]): 有由于错误共享和 A[0]、A[1] 驻留在同一个上，性能受到影响缓存行。但是最终结果是正确的 A[0]=10000,A[1]=10000
Thread2 调用 func(&A[0])：我们会得到错误的结果，因为竞争条件，即 A[0]<20000

问题：因为在场景 2 和 3 中两个线程中寻址的缓存行是相同的，所以为什么像 MESI 这样的缓存一致性协议不保护结果场景 3，而它确保场景 2 的结果是正确的。

谢谢

Answer 1

缓存一致性协议不保护场景 3，因为 *elem=*elem+1 不是原子的（至少在 C/C++ 中它不是原子的）。

来自 Wikipedia article 缓存一致性保证：

Reads/Writes to a single memory location must be seen by all processors in the same order.

但这是关于个人操作的。 *elem=*elem+1 包含两个操作：读取，然后写入。

考虑 2 个线程在不同的 CPU 上执行 *elem=*elem+1，并且 elem1 的初始值为 0。因为每个 CPU 都在执行 2 个操作，Read+Write，所以可能排序如下。让我们用真实世界的序列号标记每个输入输出操作，因此前者严格出现在后者之前：

CPU1                   CPU2  
---------------------------------------------
1) Read elem1 (0)
   Calculate 0+1                
                       2) Read elem1 (0)
                          Calculate 0+1
3) Write to elem1 0+1 
                       4) Write to elem1 0+1

每个缓存看到Reads/Writes顺序与1-2-3-4（Read-Read-Write-Write）相同的顺序，符合缓存一致性，但仍然存在竞争条件结果仍然是错误的（最后是 elem1==1）。

如果用MESI protocol写下每一步，也说明两个缓存看到Reads/Writes的顺序是一样的1-2-3-4，但是结果还是错误的：

缓存一致性与写入同一元素

Cache Coherency vs writing to same element

multithreading

caching

memory

concurrency

race-condition