浅谈原子操作的实现原理

引言：编程中，经常遇到并发处理的时候，一般我们采用多线程，对于一些涉及多线程处理内存空间，一般我们会采用加锁，让每次只能有一个线程进行操作；当然还有采用原子操作的方式。主要目的就是保证我们多个线程对同一块内存的操作是串行的，不会因为并发操作把内存写的不符合预期。那么，这种原子操作具体是怎么实现的呢？

一段代码

• 先看一段代码

#include <iostream>
#include <pthread.h>
using namespace std;
#define NUM_THREADS 4
int global_num;
 
void* run(void* args)
{
    for(int i=0; i<100000000; i++){
        global_num++;
    }
    return 0;
}

int main()
{
    pthread_t tids[NUM_THREADS];
    for(int i = 0; i < NUM_THREADS; ++i)
    {
        pthread_create(&tids[i], NULL, run, NULL);
        pthread_join (tids[i], NULL);
    }
}

• 多线程下，global_num的值是无法预期的

如何保证原子性？

• 加锁
• 原子操作

加锁

• 上面的代码，我们采用加锁的方式的话，一般会这样操作。

  std::mutex g_mutex;
  void* run(void* args)
  {
      for(int i=0; i<100000000; i++){
          g_mutex.lock();
          global_num++;
          g_mutex.unlock();
      }
      return 0;
  }

• 这样便保证了每一个线程在操作变量的时候都是独占的，线程间不会相互影响。

原子操作

• 当然还有一种更高效的方式，是使用原子操作

  void* run(void* args)
  {
      for(int i=0; i<100000000; i++){
          __sync_fetch_and_add(&global_num,1);
      }
      return 0;
  }

性能有多少区别？

• 通过4个线程执行1亿次纯i++运算，通过时间来看性能差别

• 加锁

  400000000(运算结果)
  
  real    0m10.035s
  user    0m10.030s
  sys     0m0.004s

• 原子操作

  400000000
  
  real    0m2.427s
  user    0m2.420s
  sys     0m0.004s

• 我的机器是i5 4核，目前跑出来加锁耗时10s，原子操作耗时2s，相差在5倍左右

原子操作到底变成了什么？

• 通过g++ -S -o atomic.s thread_with_atomic.cpp -lpthread编译成汇编代码，得到了下面对run函数的实现

  _Z3runPv:
      pushq	%rbp
      movq	%rsp, %rbp
      movq	%rdi, -24(%rbp)
      movl	$0, -4(%rbp)
  .L3:
      cmpl	$99999999, -4(%rbp)
      jg	.L2
      lock addl	$1, global_num(%rip)
      addl	$1, -4(%rbp)
      jmp	.L3
  .L2:
      movl	$0, %eax
      popq	%rbp
      ret

• 核心的一句是lock addl $1, global_num(%rip)

lock发生了什么？

总线锁

早期的时候，当cpu执行lock指令的时候，会直接进行总线锁，就是把总线锁住，这样cpu和内存之间就不能进行通信，如果多核cpu，就出现了一核工作，多核围观的尴尬局面，此时就会出现严重的资源浪费问题，开销比较大。

缓存锁

后面有了缓存锁，缓存锁不再锁总线，而是在写回内存时，通过一致性机制来保证一个时刻只有一个核心能修改指定的内存区域。

何时使用

有些场景是不能使用的缓存锁的，只能进行总线锁

• 当操作的数据不能被缓存在处理器内部
• 跨多个缓存行操作
• 处理器不支持

缓存锁是什么原理？

总线锁很好理解，通过锁住cpu和内存通信，并阻塞cpu执行指令完成。但是缓存锁呢？这就需要了解一下缓存一致性了。

cpu和缓存的关系

graph TD
subgraph Cpu
    subgraph Cpu1
        cpu1(cpu1) --> cache1(L1)
        cache1 --> cache12(L2)
    end
        cache12 --> cacheShare(L3)
    subgraph Cpu2    
        cpu2(cpu2) --> cache2(L1)
        cache2 --> cache22(L2)    
    end
        cache22 --> cacheShare(L3)
    subgraph Cpu3
        cpu3(cpu3) --> cache3(L1)
        cache3 --> cache32(L2)
    end
        cache32 --> cacheShare(L3)
    subgraph Cpu4
        cpu4(cpu4) --> cache4(L1)
        cache4 --> cache42(L2)
    end
        cache42 --> cacheShare(L3)
end
    cacheShare(L3) --总线--> mem(内存)

首先了解下cpu，缓存，内存之间的关系，大致是这样的，1,2级缓存cpu独享，3级缓存共享，共享物理内存。
每个核心都有自己的cache，那么如何保证cpu之间的数据一致呢?

cache写

写通

• 每次cpu修改了cache中的内容，都会立即写入内存，高一致性，但是效率不高。

写回

• 每次cpu修改了cache中的内容，不会立即写入内存。

写失效（MESI）

• 当一个cpu已经修改了数据，如果其他cpu有数据，则通知其修改。

写更新

• 当一个cpu已经修改了数据，如果其他CPU有该数据，则通知其跟新数据。

MESI – 维基百科

• 已修改Modified (M)
  缓存行是脏的（dirty），与主存的值不同。如果别的CPU内核要读主存这块数据，该缓存行必须回写到主存，状态变为共享(S).
• 独占Exclusive (E)
  缓存行只在当前缓存中，但是干净的（clean）–缓存数据同于主存数据。当别的缓存读取它时，状态变为共享；当前写数据时，变为已修改状态。
• 共享Shared (S)
  缓存行也存在于其它缓存中且是干净的。缓存行可以在任意时刻抛弃。
• 无效Invalid (I)
  缓存行是无效的

• 任意一对缓存，对应缓存行的相容关系: – 维基百科

	已修改M	独占E	共享S	无效I
已修改M	x	x	x	o
独占E	x	x	x	o
共享S	x	x	o	o
无效I	o	o	o	o

当块标记为 M (已修改), 在其他缓存中的数据副本被标记为I(无效)

状态图

上面的表可以用状态图来表示，如下

• M:修改
• S:共享
• E:独享
• I:无效
• LR:Local Read 本地cache读取本地cache
• LW:Local Write 本地cache写入本地cache
• RR:Remote Read 其他cache读取本地cache
• RW:Remote Write 其他cache写入本地cache

graph LR

subgraph Modified
M((M,修改))
end
subgraph Shared
S((S,共享))
end
subgraph Exclusive
E((E,独享))
end
subgraph Invalid
I((I,无效))
end



M --LR本地读--> M
M --RR其他读--> M
M --RW其他写--> I
M --RR其他读--> S

I --LW本地写--> M
I --LR本地读--> E

E --RW其他写--> I
E --LR本地读--> E
E --RR其他读--> S
E --LW本地写--> M

S --LR本地读--> S
S --RR其他读--> S
S --LW本地写--> M
S --RW其他写--> I

例子

• 初始化

graph TD
subgraph Cpu
    subgraph Cpu1
       cacheLine(cacheLine)
    end
    subgraph Cpu2
       cacheLine1(cacheLine)
    end
    subgraph Cpu3
       cacheLine2(cacheLine)
    end
end
cacheLine --- bus(总线)
cacheLine1 --- bus(总线)
cacheLine2 --- bus(总线)
bus --- mem(内存
x=0)
style mem fill:red

• cpu1读取

graph TD
subgraph Cpu
    subgraph Cpu1
       cacheLine(cacheLine
x=0
E,独占)
       style cacheLine fill:red
    end
    subgraph Cpu2
       cacheLine1(cacheLine)
    end
    subgraph Cpu3
       cacheLine2(cacheLine)
    end
end
cacheLine --- bus(总线)
cacheLine1 --- bus(总线)
cacheLine2 --- bus(总线)
bus --- 内存(内存
x=0)

• cpu2读取

cpu2读取，此时cpu1处于监听中，当他发现cpu2要读的地址是自己的cacheline中的，所以cpu1做出响应，把数据给cpu2
cpu1在E收到RR，E–>S

graph TD
subgraph Cpu
    subgraph Cpu1
       cacheLine(cacheLine
x=0
S,共享)
       style cacheLine fill:red
    end
    subgraph Cpu2
       cacheLine1(cacheLine
x=0
S,共享)
       style cacheLine1 fill:red
    end
    subgraph Cpu3
       cacheLine2(cacheLine)
    end
end
cacheLine --- bus(总线)
cacheLine1 --- bus(总线)
cacheLine2 --- bus(总线)
bus --- 内存(内存
x=0)

• cpu1修改

cpu1在S收到LW，S–>M
cpu2在S收到RW，S–>I

graph TD
subgraph Cpu
    subgraph Cpu1
       cacheLine(cacheLine
x=1
M,修改)
       style cacheLine fill:red
    end
    subgraph Cpu2
       cacheLine1(cacheLine
x=0
I,无效)
       style cacheLine1 fill:red
    end
    subgraph Cpu3
       cacheLine2(cacheLine)
    end
end
cacheLine --- bus(总线)
cacheLine1 --- bus(总线)
cacheLine2 --- bus(总线)
bus --- 内存(内存
x=0)

• cpu2读取

cpu2读取的时候
cpu1在M收到远程读，此时会把cache的值写入内存，从M–>S
cpu2在I收到LR，从I–>S

graph TD
subgraph Cpu
    subgraph Cpu1
       cacheLine(cacheLine
x=1
S,共享)
       style cacheLine fill:red
    end
    subgraph Cpu2
       cacheLine1(cacheLine
x=1
S,共享)
       style cacheLine1 fill:red
    end
    subgraph Cpu3
       cacheLine2(cacheLine)
    end
end
cacheLine --- bus(总线)
cacheLine1 --- bus(总线)
cacheLine2 --- bus(总线)
bus --- mem(内存
x=1)
style mem fill:red

似乎完美了？

这样是不是就完美了？其实不是的，当cpu1切换状态的时候，此时，cpu1需要通知其他所有cpu，让其他cpu进行确认，并且在发出消息，接收所有cpu回应这一段时间，cpu1可能出现阻塞的情况，导致性能不佳，这样的情况又要怎么处理？

sequenceDiagram
participant cpu1
participant cpu2
participant cpu3
participant cpu4

cpu1->> + cpu2:invalidate
cpu1->>  cpu3:invalidate
cpu1->>  cpu4:invalidate

cpu2->>  cpu1:ack
cpu3->>  cpu1:ack
cpu4->> - cpu1:ack
Note over cpu1,cpu4 : 阻塞至其他cpu全部确认
cpu1->>cpu1:执行其他指令

Store Bufferes

为了避免上述的情况导致cpu1阻塞，cpu引入的Store Bufferes，原理就是当cpu要等待其他cpu的确认的时候，先把修改后的值写入Store Bufferes，等待其他所有cpu的响应，此时可以去处理其他事，当所有确认都收到，再把数据提交。

graph TD
subgraph Cpu
    cpu0
    buff(Store Bufferes)
    cache

    cpu0 --> buff
    buff --> cache
    cache --> cpu0
end

新的问题

a=1;
b=a+1；
assert(b == 2)

sequenceDiagram
participant cpu0
participant cpu0SB
Note over cpu0SB:  cpu0的Store Bufferes
participant cpu0CL
Note over cpu0CL: cpu0的cacheLine b=0
participant cpu1
Note over cpu1 : cpu1中cacheline a=0



Note over cpu0 : cpu0执行a=1

cpu0->>cpu1: cpu0 缓存没命中a,发送 read invalidate 到cpu1，读取a的值
cpu0->>cpu0SB: 写入a=1到Store Bufferes

cpu1->>cpu0CL: 发送a=0到cpu0
cpu0CL->>cpu0: cpu0从cacheLine读取a=0到寄存器
cpu0SB->>cpu0CL: 写入存在Store Bufferes的a=1
cpu0->>cpu0: 执行b=a+1

最后b=1不符合期望

store forwarding

为了解决上面的问题，硬件工程师修改了cpu的设计
当CPU执行load操作的时候，不但要看cache，还有看store buffer是否有内容，如果store buffer有该数据，那么就采用store buffer中的值。因此，即便是store操作还没有写入cacheline，store forwarding的效果看起来就好象cpu的store操作被向前传递了一样（后面的load的指令可以感知到这个store操作）

graph TD
subgraph Cpu
    cpu0
    buff(Store Bufferes)
    cache

    cpu0 --> buff
    buff --> cache
    cache --还要根据Store Bufferes是否有这个值进行返回--> cpu0
end

void foo(){
    a=1;
    b=1;
}
void bar(){
    while(b==0) continue;
    assert(a==1);
}

sequenceDiagram
participant cpu0
Note over cpu0: cpu0执行foo函数

participant cpu0SB
Note over cpu0SB:  cpu0的Store Bufferes
participant cpu0CL
Note over cpu0CL: cpu0的cacheLine b=0
participant cpu1
Note over cpu1 : cpu1中cacheline a=0
Note over cpu1 : cpu1执行bar函数

Note over cpu0 : cpu0执行a=1

cpu0->>cpu1: cpu0 缓存没命中a,发送 read invalidate 到cpu1，读取a的值
cpu0->>cpu0SB: 写入a=1到Store Bufferes

Note over cpu1 : cpu1执行while(b==0)
cpu1->>cpu0: cpu1 cache中没有b的值,发送 read invalidate 到cpu0，试图读取b的值

Note over cpu0 : cpu0继续执行b=1

cpu0->>cpu0CL: 由于cacheline中有b的值，处于E或者M状态，所以直接更新b=1到cacheline

Note over cpu0 : cpu0收到cpu1要读取b的值
cpu0CL->>cpu1: cpu0把最新的b=1给cpu1，同时修改自己的状态为S

Note over cpu1 : cpu1判断b为1，跳出循环
Note over cpu1 : cpu1执行assert(a==1),此时cpu1中a还等于0，失败

Note over cpu1 : cpu1收到cpu0的read invalidate
Note over cpu1 : 返回a的值，并且清空自己的cache，但是此时已经晚了


cpu0SB->>cpu0CL: cpu0收到ack，把a=1写入cache，但是此时cpu1已经assert fail了

void foo(void)
{
    a = 1;
    smp_mb();
    b = 1;
}

void bar(void)
{
    while (b == 0) continue;
    smp_mb();
    assert(a == 1);
 }

sequenceDiagram
participant cpu0
Note over cpu0: cpu0执行foo函数

participant cpu0SB
Note over cpu0SB:  cpu0的Store Bufferes
participant cpu0CL
Note over cpu0CL: cpu0的cacheLine b=0
participant cpu1
Note over cpu1 : cpu1中cacheline a=0
Note over cpu1 : cpu1执行bar函数

Note over cpu0 : cpu0执行a=1

cpu0->>cpu1: cpu0 缓存没命中a,发送 read invalidate 到cpu1，读取a的值
cpu0->>cpu0SB: 写入a=1到Store Bufferes

Note over cpu1 : cpu1执行while(b==0)
cpu1->>cpu0: cpu1 cache中没有b的值,发送 read invalidate 到cpu0，试图读取b的值

Note over cpu0 : cpu0遇到smp_mb(),标记Store Bufferes中的a=1


Note over cpu1 : cpu1收到cpu0的 
 invalidate 消息，放入Invalidate Queue，
并立刻回送Ack。
cpu1->>cpu0: cpu1返回Invalidate ack
cpu0SB->>cpu0CL: cpu0收到ack，把a=1写入cacheline
Note over cpu0 : cpu0越过内存屏障，继续执行b=1

cpu0->>cpu0CL: 由于cacheline中有b的值，处于E或者M状态，所以直接更新b=1到cacheline

Note over cpu0 : cpu0收到cpu1要读取b的值
cpu0CL->>cpu1: cpu0把最新的b=1给cpu1，同时修改自己的状态为S

Note over cpu1 : cpu1判断b为1，跳出循环

Note over cpu1 : cpu1遇到smp_mb，
现在不能执行， 
 只能等待，
直到Invalidate Queue中的message 
 被处理完成

Note over cpu1 : CPU 1处理队列中缓存的
Invalidate消息，
 将a对应的cacheline 
 设置为无效
Note over cpu1 : cpu1执行assert(a==1),由于现在a无效，所以cpu1去cpu0获取a的最新值

Note over cpu1 : cpu1再执行assert(a==1)就成功了

---

参考了很多文章，试着理解了下这个过程，若有不妥之处，请指正。

简单的一个语句，cpu都做了这么多事，真是伟大的东西。

参考文章

• 总线锁和缓存锁
• 细说Cache-L1/L2/L3/TLB
• CPU中的cache结构以及cache一致性
• 维基百科-MESI
• MESI协议－CPU缓存一致性协议
• 【并发编程】CPU cache结构和缓存一致性（MESI协议）
• CPU缓存一致性协议MESI 这篇文章很不错
• 内存屏障Memory Barrier: a Hardware View
• Why Memory Barriers？中文翻译（上）
• Cache一致性和内存模型