项目9天带你走进无锁化编程
Source
Edit
History

内存屏障和 ABA 问题

内存屏障和 ABA 问题

一、内存屏障

内存屏障也被称为内存栅栏，都是一个意思。内存屏障是全局操作，在之前内存顺序的松散模型中，编译器或者硬件通常可以自由的进行重新排序。屏障限制了这一自由。

从 C++11 开始，提供了下面两个机制：

  • std::atomic_thread_fence：在线程间进行数据访问的同步
  • std::atomic_signal_fence：线程和信号处理器间的同步

本节我们只关注 std::atomic_thread_fence 。演示一段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::atomic<bool> x, y;
std::atomic<int> z;
void write_x_then_y() {
    x.store(true, std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_release); // 释放屏障
    y.store(true, std::memory_order_relaxed);
}
void read_y_then_x() {
    while (!y.load(std::memory_order_relaxed));
    std::atomic_thread_fence(std::memory_order_acquire); // 获取屏障
    if (x.load(std::memory_order_relaxed)) ++z;
}
int main() {
    x = false;
    y = false;
    z = 0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load() != 0);
}

如上代码。释放屏障和获取屏障同步，y 的 store 一定会在 y 的 load 之前。也就意味着对 x 的 store 发生在 x 的 load 之前，所以读取的值一定是 true。因此 assert 一定不会触发。

屏障的总体思路：如果获取操作看到了释放屏障后发生的存储的结果，该屏障与获取操作同步；如果在获取屏障之前发生的载入看到释放操作的结果，该释放操作与获取屏障同步。

mutex 与内存屏障

其实锁 mutex 也用到了内存屏障，拿到 mutex 锁的线程才能进入到临界区。

而 mutex 除了保证互斥之外，其他 mutex 的加锁和解锁之间也起到了“内存屏障”的功能。因为临界区的代码是不会被优化到临界区外的，这个是一定保证的。但是有一点，不保证临界区外的内容被优化到临界区中。

二、ABA 问题

参考维基百科的定义，问题可以描述为：

  1. 线程 T1 从共享内存中读取值 A
  2. 线程 T1 被抢占，线程 T2 执行
  3. 线程 T2 将共享内存中值 A 修改为值 B，然后又修改为值 A
  4. 线程 T1 执行，看到值 A 没有发生变化，则继续执行

咋一看，没什么问题，但是如果这个值是指针呢？指针的值没有改变，但是指针所指向的内容有可能发生改变。而操作系统中内存复用（MRU算法）是常见的行为，很容易出现新分配的对象与删除的对象处于同一位置。而这个问题在无锁的编程中需要关注。

从网上找到的一个例子：

有一个人类(男)拿着一个装满钱的手提箱在飞机场，此时过来了一个火辣性感的美女，然后她很暖昧地挑逗着这个人类，并趁这个人类不注意的时候，用一个一模一样的手提箱和这个人类装满钱的箱子调了个包，然后就离开了，这个人类看到自己的手提箱还在，于是就提着手提箱去赶飞机去了。

如何解决 ABA 问题

参考维基百科，有三种解决方法

  1. 标记状态：一种常见的解决方法是在所要同步的结构上添加额外的“标签”位。例如，在指针上使用比较和交换的算法可能会使用地址的低位来指示指针已成功修改的次数。因此，即使地址相同，下一次比较和交换也会失败，因为标签位不匹配。这有时被称为ABAʹ，因为第二个A与第一个略有不同。

  2. 中间节点：一个可行但昂贵的方法是使用不是数据元素的中间节点，从而在插入和删除元素时确保不变量，

  3. 延迟回收：推迟回收已删除的数据元素，实现较为复杂

三、简单总结

本小节的主要分享了内存屏障、ABA 问题。内存屏障主要作用于编译器，阻止编译器在具体位置生成乱序的代码。而 ABA 问题在我们进行无锁编程中是比较重要的，尤其是对于 CAS 操作，比如：CAS 判断的是指针的地址，如果这个地址被重用了呢？那问题就大了。

这些概念是为了我们后面更加深入的学习和实现无锁化编程