关于原子变量的一些事情

为什么需要原子变量

考虑下面的代码

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
using namespace std;

int global ; 
const static int LoopCount = 20000000; 
int worker(int)
{
  for ( int i = 0; i < LoopCount ; i++)
  {
     global++;
  }
}

int main(int argc, char**argv)
{
  vector<thread*> vec(2);
  for (auto& th : vec)
  {
     th = new thread(worker, 0);
  }
  for (auto& th : vec)
  {
     th->join(); 
  }

  cout << global << endl;
  return 0;
}

我们可以保证打印的global一定是2*20000000吗？答案是否定的。那为什么呢？

在多核心的CPU架构中， 每个核心都有自己独立的寄存器，缓存。 如果两个线程又被分配到了不同的核心，虽然不同的线程访问的global是唯一的, 对应于内存的某个地址。但cpu使用的寄存器和缓存确实相互独立的。 两个线程并发从内存读到的都是100，在完成自增操作后，本地的缓存都被更新为101，并没有按预想的被更新到102。

如何避免多线程的竞争

传统的方法是向使用互斥锁加volatile。互斥锁保证每次只有一个线程进行修改，volatile保证变量每次都从内存进行读取。但由于每次加锁操作，都涉及到操作系统申请资源，所以这个操作相对比较耗时。

所以随着硬件的发展，cpu开始提供了缓存一致性保证。缓存一致性的目的是为了保证A线程修改了某变量后，在B线程可以感知到该修改。

缓存一致性

关于缓存一致性这里有篇文章讲的很详细。 https://albk.tech/%E8%81%8A%E8%81%8A%E7%BC%93%E5%AD%98%E4%B8%80%E8%87%B4%E6%80%A7%E5%8D%8F%E8%AE%AE.html

简单的讲，就是CPU在指令层实现了MESI缓存交互协议，虽然有多个缓存, 但当某个线程要修改某数据时，保证该线程独享该数据。并且其他进程再次读取该缓存时，可以感知到该次修改。 这里要强调的是，缓存一致性协议针对的是缓存行。 缓存行大小，可以通过如下指令查看。

more /sys/devices/system/cpu/cpu1/cache/index0/coherency_line_size 
64

也就是说，通过缓存一致性实现的原子变量的大小不能超过这个大小。

在编码的层次，c++提供了atomic模板类封装了指令层的原子语义。 我们只要将int global ; 提更换为 std::atomic global； 就可以保证上面代码的正确性。这里需要注意的是, 引入了原子变量后, 又使用临时变量辅助计算, 会导致出现最开始提到的问题。

自旋锁

利用原子变量，我们可以实现一种自旋锁。

伪代码如下：

std::atomic<int> lock;
std::atomic<int> some_value;

主线程初始化：
lock=0;
some_value=0;

A线程：
    some_value=....;
    lock=1;

B线程：
    while (0 == lock) {}  // 自旋等待
    read some_value;

自旋锁的引入，需要我们对cpu的另一个特性有所了解，那就是：

乱序执行及内存屏障

关于乱序执行, 可以参考下面的文章, 讲的比较详细. https://blog.csdn.net/dd864140130/article/details/56494925

简单的讲, 就是说cpu为了提高执行效率, 在保证结果正确性的情况下, 并不会保证指令执行顺序和代码逻辑顺序完全一致.

对于上面的自旋锁的例子, some_val和lock的设置, 由于两个变量相互独立, 对于单线程, 谁先执行并不会影响最终的正确性. 所以在指令层面, lock反倒可能优先被设置.

为了解决这个问题, cpu在指令层面, 提供了mfence指令(内存屏障), 根据相应的屏障类型, 来保证在某个数据被修改前, 其之前的代码逻辑已经生效.

inline constexpr memory_order memory_order_relaxed = memory_order::relaxed; 
inline constexpr memory_order memory_order_consume = memory_order::consume;
inline constexpr memory_order memory_order_acquire = memory_order::acquire;
inline constexpr memory_order memory_order_release = memory_order::release;
inline constexpr memory_order memory_order_acq_rel = memory_order::acq_rel;
inline constexpr memory_order memory_order_seq_cst = memory_order::seq_cst;

在标准库层面, 可以认为提供了如上6种屏障类型. 对于原子变量的相关操作, 默认值为memory_order_seq_cst.

多写一读无锁队列

原子变量的另一个用途是实现多写一读的无锁队列.

基本原理是:

1. 多个writer先抢占队列尾(tail为原子变量), 申请空间. 然后对这块独占的空间进行写操作, 写完成后, 在这块独占空间的某个字段种设置完成标志.
2. reader则负责从队列读数据, 在读完成后, 之前writer写的空间清空, 并修改队头.

由于多个write同时抢队尾有可能失败, 程序会设置了一个最大重试次数, 超过该重试次数则会丢弃写请求.

1. 相同竞争数的情况, 请求数越多, 冲突率越高
2. 相同请求数,竞争数的增加, 冲突率越高
3. 保证正确率的情况下, 随着竞争数的增加, 每s请求数, 先下降再升高.
4. 相同竞争数, 相同sleep模型下, 冲突率和正确率有正比关系 不同竞争数, 不同sleep模型下, 尚未找到必然规律

总结

本文对原子变量, 缓存一致性,内存屏障等问题做了一个简单介绍. 并对实现的多写一读的无锁队列的性能做了一个评估. 希望对此感兴趣的同学有所帮助.