Atomic Weapons 笔记

源于 Herb Sutter 的 “C++ and Beyond 2012: atomic Weapons” 对的一些笔记，以及对 atomic 的理解

关于顺序一致性

顺序一致性 Sequential consistency (SC)

the result of any execution is the same as if the reads and writes occurred in some order, and the operations of each individual processor appear in this sequence in the order specified by its program (Leslie Lamport, 1979)
倘若读写顺序按照一定的顺序进行执行，那么执行的结果将会是一致的，并且出现在每个处理器的指令顺序完全由它的程序所指定

你一定会觉得自己所编写的程序 CPU 一定会按照所编写的顺序进行执行，然而实际上受到编译器，处理器以及 Cache 等影响（优化），实际的顺序并不完全按照我们所编写的进行执行。倘若我们的程序完全按照 SC 的方式进行执行，那它不一定是高效的，因此我们需要各种优化

无数据竞争的顺序一致性 SC for data-race-free (SC-DRF)

倘若这个程序不存在数据竞争，那么编译器和处理器等就可以对它进行各种优化，但不会破坏结果的正确性。因此人们提出了 SC-DRF 模型，只要编写者正确处理程序中的数据竞争那么就可以进行各种优化，充分利用硬件性能提高执行效率。（Java 和 C++ 均采用此模型）

Acquire 和 Release 操作的解释

Acquire 和 Release 操作其实可以理解为临界区的开始与结束：

• Acquire：表明这块代码需要开始区别于其他代码进行独立运行（进入临界区）
• Release：表明这块代码已经运行结束（离开临界区）

Why？

为什么会有这个概念呢？
其实它们相当于比 SC 更宽松的一种内存序，为什么说更宽松呢？
首先 编译器和处理器对于临界区的代码会遵循如下原则：

1. 不会将临界区的代码移出来进行重排

   mutex.lock();
   x = 12;
   mutex.unlock();

     不会优化成❌  

   x = 12;          // 出现竞争
   mutex.lock();
   mutex.unlock();

     &  

   mutex.lock();
   mutex.unlock();
   x = 12;          // 出现竞争

2. 可能会将临界区外的代码移入到临界区内，但不会穿越临界区进行重排

   x = 12;
   mutex.lock();
   :::
   mutex.unlock();
   y = 13;

     可能会优化成✔  

   mutex.lock();
   x = 12;
   :::
   y = 13;
   mutex.unlock();

     但绝不会❌  

   y = 13;
   mutex.lock();
   :::
   mutex.unlock();
   x = 12;

而 Acquire 和 Release 承担了怎样的角色呢？

• Acquire 之前的代码可以移入到临界区开始之后
• Release 之后的代码可以移入到临界区结束之前
  所以 Acquire 和 Release 两个操作可以理解成单向内存屏障（acquire barrier，release barrier ），而 SC 则是一个双向内存屏障（Full Fence），因此它们就相当于比 SC 更宽松的一种屏障来约束指令重排，关系如下：

如何控制指令重排？

1. 使用互斥量（推荐）
2. 使用原子操作（推荐，但需要正确编写）
3. 使用内存屏障（不推荐）

为什么不推荐使用内存屏障？

缺点：

1. 不具有通用性：不同的处理器具有不同的特性
2. 编写繁琐：在所有需要保持顺序的情况下每个地方都不能省略
3. 容易出错：很难解释，而且 Lock-Free 避免使用
4. 性能问题：调用很沉重，是个很悲观的调用
   使用内存屏障的同时有可能使得原本可以进行的优化无法进行，导致运行效率下降，所以代码中应尽量避免使用

数据竞争

Herb Sutter 提到了两种数据竞争的情况

1. 可能将临近的数据视为一个 object 进行处理

如果存在有两个数据长度较短而且毗邻的情况下，编译器和处理器有可能将这两个作为一个 object 来进行处理。比如，拥有两个全局变量 char c 和 char d，同时有两个线程进行修改：

// THREAD 1
:::
lock_guard lock(cMutex);
c = 1;
:::

  〰  

// THREAD 2
:::
lock_guard lock(dMutex);
d = 1;
:::

那么会有竞争吗？
答案是可能会存在，因为可能会出现这样的优化：

char tmp[4];              // 32-bit scratchpad
memcpy(&tmp[0], &c, 4);   // read 32 bits starting at c
tmp[1] = 1;               // set only the bits of d
memcpy(&c, &tmp[0], 4);   // write 32 bits back

THREAD 2 在修改 d 的时候隐形的修改了 c 的值
那么使用结构体的方式也会可能出现吗？ 比如 struct { char c; char d; }，答案其实也是可能会优化成上述的情况
但如果是使用位域 struct { int c:9; int d:7; } ，那么必然出现竞争的情况

2. 寄存器写回数据时导致的数据竞争

为了进行高效的循环，编译器可能会将某些变量读到寄存器中，进行快速的处理，然后将寄存器中的数据写回内存中。那么这样就导致了一个问题，写回内存中时就有可能出现数据竞争的情况，所以需要增加适当的互斥以及条件判断来确保不会发生这个问题

不同的平台上的处理

针对于不同的平台都符合一个标准：我们可以容忍 store 的耗时，但是 load 的操作必须要快速才行
列举了很对不同平台的编译后的指令，不多说，主要记录下 ArmV7 和 ArmV8 的指令：

	Load	Load(SC Atomic)	Store	Store(SC Atomic)
ARM V7	ldr	ldr; dmb	str	dmb; str; dmb
ARM V8	ldr	ldra	str	strl

不难看出，ArmV7 的原子性的 Load 操作会有调用内存屏障来保证顺序性这样就违背了上述标准，这也是为什么 C/C++ 中存在 宽松内存序(relaxed) 这一枚举。ArmV8 可以看出解决了这一问题，这也说明了两者在架构上实现的不同

Memory Order

C 中提供了常用的内存序，如下：

enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,    // since C11
    memory_order_release,    // since C11
    memory_order_acq_rel,
    memory_order_seq_cst
};

枚举值的解释

• memory_order_relaxed
  只保证指令的原子性，可通过编译器和 CPU 进行指令重排，并且不保证可见性的同步，但对于其他线程来说观察到的修改顺序是一致的
• memory_order_release
  属于 Release 操作，不做过多叙述。保证可见性的同步
• memory_order_consume，memory_order_acquire
  均属于 Acquire 操作，虽然两者均为单向的内存屏障，但还是有细微差别：
  即使用了 memory_order_consume 获取后的变量并对其进行相关的操作均不能越过它提前，但是与其无关的操作可以越过；而 memory_order_acquire 单向性更强，所有之后的操作均不能越过

  但某些编译器并未支持 memory_order_consume 而是多将其转换为 memory_order_acquire 使用

• memory_order_acq_rel
  集合了 Acquire-Release 操作，一般用于 RMW （Read-Modify-Write）可以将这几步操作整体视为一个原子操作，保证可见性的同步
• memory_order_seq_cst
  强内存序，C/C++ 中调用原子操作时一般默认的内存序，前后的代码均不能越过它进行重排，保证可见性的同步

对于 Happens-before （先行发生），Synchronizes-with （同步） 与可见性的解释

Happens-before 在单线程来说是比较容易理解的，无非是 A 指令在 B 指令前执行，但置于多线程中就不一样了，指令重排和乱序执行导致了不具有 Happens-before 这样的逻辑存在，因此原子操作就起到了作用
多线程中的 Happens-before 应该按照 Release-Acquire 作为组合的方式来看待:

// THREAD 1
:::
// A
atomic_var.store(1, memory_order_release);
:::

  〰  

// THREAD 2
:::
// B
while (!atomic_var.load(memory_order_acquire)) {}
:::

Release 操作保证发生在 Acquire 操作之前，（ A Happens-before B），当 Release 操作完毕时，Acquire 操作会立即在内存中可见对应的数据进行执行，这样就形成了线程间的同步（A Synchronizes-with B）
为什么会有可见性这一说法？
由于各种架构的都具有不同的内存模型（比如 Intel 的 TSO 内存模型）， 这就使得数据会优先存放进 Cache 中，因此在线程1更新的数据并不会及时的同步到内存中，这就导致了线程2从内存中取得对应的数据不会是最新的数据，这就出现了缓存不一致的情况

使用场景

事件计数器

众所周知，使用非原子操作在多个线程中进行计数累加则会导致最终的计数出现问题，因此使用原子操作是最好的选择：

// global
atomic_int count = 0;

// Threads 1..N
while(...) {
  :::
  ++count;
  :::
}

main() {
  launch_workers();
  :::
  join_workers();
  cout << count << endl;
}

但使用默认情况下的内存顺序是 memory_order_seq_cst ，这样会影响到许多优化操作。所以应该如何选择？由于这个 count 既不受到其他线程中操作的先后顺序（Happens-before，Synchronizes-with ）影响，每个线程不需要关注其数据变化，只需要保证数据修改顺序的一致性，那么就可以保证数据的正确性，所以可以选择使用 memory_order_relaxed ：

// global
atomic_int count = 0;

// Threads 1..N
while(...) {
  :::
  count.fetch_add(1, memory_order_relaxed);
  :::
}

main() {
  launch_workers();
  :::
  join_workers();
  cout << count.load(memory_order_relaxed) << endl;
}

标志位

使用标志位来作为线程循环是否继续是很常用的方法，这某些场景中可以避免锁的调用：

// global
atomic_bool stop = false;
atomic_bool dirty = false;

// Threads 1..N
while(!stop) {
  :::
  if (...) {
    dirty = true;
  }
  :::
}

main() {
  launch_workers();
  stop = true;
  join_workers();
  if (dirty) {
    :::
  }
}

由于 stop 用于控制循环是否继续，所以stop = true 的操作必须满足：

1. 发生在 launch_workers() 之后
2. 发生在 join_workers() 之前（ Happens-before ）
3. 每个线程需要能够看到 stop 的变化（ Synchronizes-with ）

因此该操作只能选择使用 memory_order_seq_cst 来保证前后的指令不会跨越它进行优化的同时保证变化能够及时的让每个线程可以看到，而循环中对 stop 的读取使用 memory_order_relaxed 即可
dirty 这块均可以使用 memory_order_relaxed

最开始我看 Herb Sutter 在视频里对 dirty 使用的是 Release-Acquire 但后面参考发布的 PPT 发现，两者均用的是 Relaxed，他对此的解释如下：
dirty can be relaxed, relying on “join”‘s ordering (doesn’t itself publish data).
其实也就是说明线程的生命周期结束时，间接的保证了数据同步

// global
atomic_bool stop = false;
atomic_bool dirty = false;

// Threads 1..N
while(!stop.load(memory_order_relaxed)) {
  :::
  if (...) {
    dirty.store(true, memory_order_relaxed);
  }
  :::
}

main() {
  launch_workers();
  stop = true;      // 默认为 memory_order_seq_cst
  join_workers();
  if (dirty.load(memory_order_relaxed)) {
    :::
  }
}

引用计数

Herb Sutter 这里引用的是 C++ 智能指针的源码：

// Threads 1: Increment.
// (inside, say, smart_ptr copy ctor)
:::
control_block_ptr = other->control_block_ptr;
++control_block_ptr->refs;
:::

// Thread 2: Decrement.
// (inside, say, smart_ptr dtor)
:::
if(--control_block_ptr->refs == 0)
{
  delete control_block_ptr;
:::

对于内存序的使用是这样的：

// Threads 1: Increment.
// (inside, say, smart_ptr copy ctor)
:::
control_block_ptr = other->control_block_ptr;
control_block_ptr->refs.fetch_add(1,memory_order_relaxed);
:::

// Thread 2: Decrement.
// (inside, say, smart_ptr dtor)
:::
if(control_block_ptr->refs.fetch_sub(1,memory_order_acq_rel) == 0)
{
  delete control_block_ptr;
:::

对于引用递增，只需要考虑修改的原子性和顺序的一致性即可，所以可以使用 memory_order_relaxed
对于引用递减，需要考虑在多线程中进行释放时能够立即看到引用计数的变化，这样保证不会进行重复释放导致出错，同时需要保证多个步骤（ RMW ）具有原子性并且也防止前后的代码越过它进行执行，所以选用 memory_order_acq_rel 。为什么不选用 memory_order_release ？不仅因为 fetch_sub 由多个步骤构成，单使用 _release 无法保证多步骤的原子性，而且 _release 控制的屏障方向也不一样

更安全的单例模式

Herb Sutter 在视频上也提到了单例的懒汉模式多线程下的安全性，主要是指针形式的：

A* A::_inst = nullptr;

A* A::GetInstance() {
  if (_inst == nullptr) {
    _inst = new A();
  }
  return _inst;
}

这种其实在多线程的情况下并不安全，当然可以考虑增加一个静态 Mutex 但对于调用者来说不仅需要依次等待前者的解锁并且过于沉重，那么原子操作就起到了它的作用。这里不过多的说明如何操作，最简单的解决方案是改成：

A A::GetInstance() {
  static A inst;
  return &A;
}

这样不仅保证了多线程中的安全性，同时也避免了出现调用者拿到指针进行释放的操作

volatile

总而言之，该关键字用于阻止编译器对变量的读取进行优化，比如在循环中，可能某些变量会先放到寄存器中，便于进行快速的操作，但这样就导致了如果内存中这个变量已经被修改但在这个循环中并没有观察到这个变量的话，那么就可能导致某些错误
那它可以用于多线程吗？
不行，volatile 可用于实时观察内存中变量的变化，但它并不具有原子性，也就意味者它并不能保证修改顺序的一致性

Ref

1. 现代C++的内存模型
2. 内存模型与c++中的memory order - woder - 博客园
3. C++ and Beyond 2012: Herb Sutter - atomic Weapons 2 of 1
4. C++ and Beyond 2012: Herb Sutter - atomic Weapons 2 of 2