本文及其后续文章将介绍一些不基于锁的线程安全的c++数据结构的实现，c++中无锁的数据结构主要基于原子操作和内存序实现。本文主要介绍c++中的原子操作和内存序。本文会使用到一些c++17或c++20的新特性。

参考书目：《c++并发编程实战》

完整代码在GitHub：Github

原子操作

  原子操作可以替代互斥量，来完成同步操作。C++17中，所有原子类型有一个static constexpr成员变量，如果相应硬件上的原子类型X是无锁类型，那么X::is_always_lock_free将返回true。只有 std::atomic_flag 类型不提供 is_lock_free() 。该类型是一个简单的布尔标志，并且在这种类型上的操作都是无锁的。当有一个简单无锁的布尔标志时，可以使用该类型实现一个简单的锁，并且可以实现其他基础原子类型。对 std::atomic_flag 明确初始化后，做查询和设置(使用test_and_set()成员函数)，或清除(使用clear()成员函数)都很容易：无赋值，无拷贝，没有测试和清除，没有任何多余操作。剩下的原子类型都可以通过特化 std::atomic<> 得到，并且拥有更多的功能，但不可能都是无锁的。

  std::atomic<> 类模板不仅仅是一套可特化的类型，作为原发模板也可以使用自定义类型创建对应的原子变量。因为是通用类模板，操作限制为 load()，store()(赋值和转换为用户类型) exchange()，compare_exchange_weak()和compare_exchange_strong()。每种函数类型的操作都有一个内存序参数，这个参数可以用来指定存储的顺序。

原子操作共分为三类：

1. Store操作，可选如下内存序： memory_order_relaxed, memory_order_release, memory_order_seq_cst。
2. Load操作，可选如下内存序： memory_order_relaxed, memory_order_consume, memory_order_acquire,memory_order_seq_cst。
3. Read-modify-write(读-改-写)操作，可选如下内存序： memory_order_relaxed, memory_order_consume,memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_seq_cst。

NOTE：原子操作是不能复制和拷贝的
原子类型的所有操作都是原子的，而赋值和拷贝调用了两个对象，这就就破坏了操作的原子性（拷贝构造和拷贝赋值都会将第一个对象的值进行读取，然后再写入另外一个。对于两个独立的对象，这里就有两个独立的操作了，合并这两个操作必定是不原子的。因此，操作就不被允许）。

使用原子操作实现自旋锁

我们使用atomic_flag（一定是无锁类型）实现自旋锁代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class spinlock_mutex {
    std::atomic_flag flag;

public:
    spinlock_mutex() : flag(ATOMIC_FLAG_INIT) {}

    void lock() {
        while (flag.test_and_set(std::memory_order_acquire));
    }

    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

需要用到两个内存序：

• memory_order_acquire：在调用test_and_set时，使用此内存序列意味着在此操作之前的所有读写操作都不能被重排到此操作之后。这确保了在当前线程中，所有在调用lock()之前的写入操作对其他线程都是可见的。这是为了确保当一个线程获取锁时，它可以看到其他线程在释放锁之前所做的所有更改。
• memory_order_release：在调用clear时，使用此内存序列意味着在此操作之后的所有读写操作都不能被重排到此操作之前。这确保了当前线程在释放锁时，所有对共享数据的修改都将在其他线程读取到锁之前完成，从而保持数据的一致性。

基本的原子操作

存储操作：store()，写入。
加载操作：load()，加载。
读改写操作：exchange()，允许使用新选的值替换已存储的值，并且会自动检索原始值。

1
2
3
4

std::atomic<bool> b;
bool x=b.load(std::memory_order_acquire);
b.store(true);
x=b.exchange(false, std::memory_order_acq_rel);

读改写操作：compare_exchange_weak()/compare_exchange_strong()，比较/交换，存储一个新值(或旧值)取决于当前值。“比较/交换”操作是原子类型编程的基石，它比较原子变量的当前值和期望值，当两值相等时，存储所提供值。当两值不等，期望值就会被更新为原子变量中的值。“比较/交换”函数值是一个bool变量，当返回true时执行存储操作，false则更新期望值。当存储完成(因为值相等)，则操作是成功的，否则即为失败。操作成功是返回true，失败时返回false。

compare_exchange_weak()：当原始值与预期值一致时，存储也可能会不成功。在这种情况中变量的值不会发生改变，并且compare_exchange_weak()的返回值是false。这最可能发生在缺少单条CAS操作(“比较-交换”指令)的机器上，当处理器不能保证这个操作能够原子的完成（可能因为线程的操作执行到必要操作的中间时被切换，并且另一个线程将会被操作系统调度（这里线程数多于处理器数量）），称为“伪失败”，因为造成这种情况的是时间，而不是变量值。
compare_exchange_strong()：，当实际值与 expected 不符，compare_exchange_strong()就能保证值返回false。这就能消除对循环的需要，就可以知道是否成功的改变了一个变量，或已让另一个线程完成。该函数保证在预期值与实际值相等时，操作总是成功。它会处理伪失败情况，因此在需要确保操作成功时应使用此函数。

思考：compare_exchange_weak() 通常比compare_exchange_strong()更高效，因为它可能会使用更少的CPU指令，尤其是在循环中多次调用时。因此，在需要频繁尝试的场景下，使用 compare_exchange_weak() 可以提高性能compare_exchange_strong()可能会引入额外的开销，以确保每次操作都能成功，因此在不需要强保证的场合下，使用它可能会导致性能下降。compare_exchange_weak()适合于需要在循环中多次尝试的情况，例如实现无锁数据结构时，通常会将其放在while循环中以处理伪失败。compare_exchange_strong()适合于单次尝试且需要确保成功的场合，例如在某些情况下不允许失败的关键操作。
因为compare_exchange_weak()可以伪失败，所以通常会配合一个循环使用：

1
2
3

bool expected=false;
extern atomic<bool> b; 
while(!b.compare_exchange_weak(expected, true) && !expected);

比较和交换的工作流程：
比较：将原子变量b的当前值与expected的值进行比较。
交换：如果二者相等，则将b的值设置为true并返回true。同时，expected会保持不变。如果不相等，则将b的当前值赋给 expected，并返回false。

代码中的循环在干什么？
这个操作被放在一个 while 循环中，目的是为了确保在成功将 b 的值设置为 true 之前不断尝试。由于使用的是 compare_exchange_weak，它可能会因为“伪失败”（spurious failure）而返回 false，即使当前值与 expected 相等。因此，循环会继续执行，直到成功更新 b。

  比较/交换操作的另一点需要注意的地方是：它拥有对两个内存序的参数进行操作的能力，这就允许内存序语义在成功和失败的情况下有所不同。可能成功时使用memory_order_acq_rel，而失败时使用memory_order_relaxed。失败的“compare/exchange”将不会进行存储，所以“compare/exchange”操作不能拥有meory_order_release或memory_order_acq_rel。如果没有指定失败语序，那就和成功的语序一样了，除了release部分的顺序：memory_order_release变成memory_order_relaxed，并且memoyr_order_acq_rel变成memory_order_acquire。

  原子的指针类型std::atomic<T*>（T可以使用内置类型或自定义类型）为指针运算提供新的操作。基本操作有fetch_add()和fetch_sub()(也可以使用内存序)，它们在存储地址上做原子加法和减法，为+=, -=, ++和–提供简易的封装。fetch_add()和fetch_sub()的返回值略有不同(所以x.ftech_add(3)让x指向第四个元素，并且函数返回指向第一个元素的地址)。这种操作也被称为“交换-相加”，并且这是一个原子的“读-改-写”操作，如同exchange()和compare_exchange_weak() / compare_exchange_strong()一样。正像其他操作那样，返回值是一个普通的 T* 值，而非是 std::atomic<T*> 对象的引用。所以调用代码可以基于之前的值进行操作：

1
2
3
4
5
6
7
8
9

class Foo{};
Foo some_array[5];
std::atomic<Foo*> p(some_array);
Foo* x=p.fetch_add(2); // p加2，并返回原始值
assert(x==some_array);
assert(p.load()==&some_array[2]);
x=(p-=1); // p减1，并返回原始值
assert(x==&some_array[1]);
assert(p.load()==&some_array[1]);

  std::atomic<int>和std::atomic<unsigned long long>也是有一套完整的操作可以供使用：fetch_add(), fetch_sub(), fetch_and(), fetch_or(), fetch_xor()，还有复合赋值方式(+=, -=, &=, |=和^=)，以及++和–(++x, x++, –x和x–)。

内存序

  在C++中，同发（concurrent）和先行（happens-before）是处理多线程编程时的重要概念，特别是在理解内存模型和同步机制时。

• 同发： 同发指的是两个或多个事件（如线程中的操作）在时间上可以重叠，但并不一定存在直接的因果关系。在同发的情况下，两个事件的执行顺序是不可预测的，它们可能同时进行，也可能交替进行。具体来说：如果两个事件A和B在不同线程中执行且没有直接的消息传递或依赖关系，那么它们被认为是同发的。这意味着A和B之间既没有A→B的关系，也没有B→A的关系。同发事件之间的结果可能会受到调度器的影响，因此它们的执行顺序可能会导致不同的程序行为。
• 先行：先行关系是一个更严格的概念，它定义了事件之间的可见性和顺序。具体来说，如果事件A先行于事件B（记作A→B），则意味着：事件A的效果在事件B之前可见。这通常用于确保多线程程序中的数据一致性。

  在C++中，内存序（memory order）是多线程编程中至关重要的概念。它定义了在并发环境中对共享数据的访问顺序和可见性。内存序共分为三类：顺序一致性（Sequential Consistency）、获取/释放序（Acquire/Release）和自由序（Relaxed Consistency）（后两者也被称为非顺序一致性）：

1. 顺序一致性（Sequential Consistency）—— memory_order_seq_cst：
   • 定义：这是最强的一种内存序，提供全局顺序一致性。
   • 作用：保证所有线程看到的操作顺序是一致的，形成一个全局线性顺序。
   • 使用场景：适合于需要严格同步和一致性的场合，如简单的共享变量读写，或者在不希望出现任何数据竞争时使用。
   • 适用性：由于其强制性，可能导致性能下降，因此应谨慎使用。

  程序的默认序命名为顺序一致性，因为程序中的行为从任意角度去看，序列都保持一定顺序。如果原子实例的所有操作都是序列一致的，那么多线程就会如单线程那样以某种特殊的排序执行。所以，操作都不能重排；如果代码在一个线程中，将一个操作放在另一个操作前面，那其他线程也需要了解这个顺序。

  从同步的角度看，是对同一变量的存储操作与载入操作的同步。这就提供了一种对两个(以上)线程操作的排序约束，但顺序一致的功能要比排序约束大的多，所以对于使用顺序一致的原子操作，都会存储值后再加载。不过，简单就要付出代价。多核机器会加强对性能的惩罚，因为整个序列中的操作都必须在多个处理器上保持一致，可能需要对处理器间的同步操作进行扩展(代价很昂贵！)。

  当踏出顺序一致的世界时，事情就开始复杂了。不同线程看到相同操作，不一定有着相同的顺序，还有对于不同线程的操作，都会一个接着另一个执行的想法就不可行了。不仅是考虑事情同时发生的问题，还有线程没办法保证一致性。为了写出(或仅是了解)一段使用非默认内存序列的代码，绝不仅是编译器重新排列指令的事情。即使线程运行相同的代码，都能拒绝遵循事件发生的顺序，因为操作在其他线程上没有明确的顺序限制，不同的CPU缓存和内部缓冲区，在同样的存储空间中可以存储不同的值。

2. 自由序（Relaxed Consistency）—— memory_order_relaxed：
   • 定义：最宽松的内存序，不提供任何同步或顺序保证。
   • 作用：允许最大程度的优化，仅保证原子性，不保证顺序或可见性。
   • 使用场景：适合于只需要原子性的简单计数器等操作，如 std::shared_ptr 的引用计数。
   • 适用性：当不需要考虑数据依赖关系时，可以提高性能。

  使用自由序时，原子类型上的操作以自由序执行。同一线程中对于同一变量的操作还是遵从先行关系，但不同线程不需要规定顺序。唯一的要求是在访问同一线程中的单个原子变量不能重排序，当给定线程看到原子变量的值时，随后线程的读操作就不会去检索较早的那个值。当使用memory_order_relaxed时，不需要任何额外的同步，对于每个变量的修改顺序只存在于线程间共享。

3. 获取/释放序（Acquire/Release）—— memory_order_acquire：
   • 定义：获取操作，确保在此加载之前的所有读写操作不会被重排。
   • 作用：使得所有在此操作之前的写入对其他线程可见。
   • 使用场景：常用于锁机制中，确保获取锁后能看到锁释放前的所有修改。
   • 适用性：适合需要确保数据可见性的场合。
4. 获取/释放序（Acquire/Release）—— memory_order_release：
   • 定义：释放操作，确保在此存储之后的所有读写操作不会被重排
   • 作用：使得当前线程中的所有写入在释放时对其他线程可见。
   • 使用场景：常用于锁机制中，在释放锁时确保之前的所有修改对其他线程可见。
   • 适用性：适合需要确保数据一致性的场合。
5. 获取/释放序（Acquire/Release）—— memory_order_acq_rel：
   • 定义：结合了获取和释放操作，既不允许重排获取之前的读写，也不允许重排释放之后的读写。
   • 作用：适用于读改写（RMW）操作，确保数据的一致性和可见性。
   • 使用场景：常用于复杂的同步场景，如实现自旋锁或其他复杂的数据结构。
   • 适用性：适合需要同时保证获取和释放语义的情况。

  获取/释放序是自由序(relaxed ordering)的加强版，虽然操作依旧没有统一顺序，但引入了同步。这种序列模型中，原子加载就是获取(acquire)操作(memory_order_acquire)，原子存储就是释放(memory_order_release)操作，原子读-改-写操作(例如fetch_add()或exchange())在这里，不是“获取”就是“释放”，或者两者兼有的操作(memory_order_acq_rel)，同步在线程释放和获取间是成对的(pairwise)，释放操作与获取操作同步就能读取已写入的值。

6. 获取/释放序（Acquire/Release）—— memory_order_consume：
   • 定义：确保依赖于加载值的后续操作不会被重排到加载之前。
   • 作用：处理数据依赖关系，确保读取的数据在使用前是有效的。
   • 使用场景：通常用于复杂的数据结构，但由于支持较差，在实际应用中不常用。
   • 适用性：适合于需要处理复杂依赖关系的数据结构，但由于实现复杂性和可移植性问题，实际应用较少。

  memory_order_consume是“获取-释放”模型的一部分，memory_order_consume很特别：完全依赖于数据，并且其展示了与线程间先行关系的不同之处。这个内存序非常特殊，即使在C++17中也不推荐使用，这里不过多介绍。

总结

  C++中的原子操作和内存序是实现无锁数据结构的基础。原子操作提供了不可分割的操作，确保在多线程环境中安全访问共享数据。内存序定义了对共享数据的访问顺序和可见性。理解这些概念对于编写高效、安全的并发程序至关重要，能够有效避免数据竞争和不一致性问题，这也是实现无锁的线程安全的数据结构的基础。