并发与异步编程（五） -- 无锁编程梳理

• 1. 背景
• 2. 锁竞争的代价
  • 2.1. 多线程加锁访问（实验）
  • 2.2. 原子变量无锁访问（实验）
  • 2.3. 对比分析
• 3. 一些优化思路
  • 3.1. 降低缓存缺失率
  • 3.2. 减少上下文切换
  • 3.3. 实践tips
• 4. 无锁编程技术
  • 4.1. 概念说明
    • 4.1.1. 澄清：RCU、CAS、RMW
    • 4.1.2. ABA问题
  • 4.2. 指令重排
  • 4.3. C++中的atomic
    • 4.3.1. 内存序（memory order）
    • 4.3.2. CAS成员函数
  • 4.4. 无锁队列实现参考
• 5. 小结
• 6. 参考

本篇梳理学习无锁编程。

1. 背景

并发编程中离不开资源同步，其中往往伴随着mutex、semaphore、condition_variable等机制，在实际使用中如果不是对实时性要求极高的场景，合理控制锁粒度和持锁时长基本都能满足业务要求了。

无锁编程是多线程编程的一种有效技术，但不应轻易使用。 在使用它之前，必须了解复杂性，并且应仔细衡量，以确保它确实能给你带来预期的收益。 在许多情况下，应该使用更简单、更快的解决方案，例如更少地共享数据。

正确安全地使用无锁编程需要对硬件和编译器有深入的了解。

执行无锁编程时，必须处理两个难题：非原子操作和重新排序。
可了解：无锁编程注意事项

使用锁来进行并发同步时，性能受锁竞争和上下文切换的开销影响。其中还涉及局部性原理对应的缓存问题，一并进行分析。

若想要更进一步减少锁竞争带来的损耗，可以尝试无锁（lock-free）相关技术和相关结构，本篇开始梳理学习无锁编程相关的技术点。

说明：本博客作为个人学习实践笔记，可供参考但非系统教程，可能存在错误或遗漏，欢迎指正。若需系统学习，建议参考原链接。

2. 锁竞争的代价

先看看锁竞争的代价，用个demo来实际对比一下。

2.1. 多线程加锁访问（实验）

编译：g++ mutex_cost.cpp -o mutex_cost -pthread

其中 std::chrono::high_resolution_clock 表示最小滴答周期（tick period）的实现，一般会是std::chrono::system_clock或者std::chrono::steady_clock的别名，也支持第三方实现，具体以不同的编译平台为准。具体见：cppreference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// mutex_cost.cpp
#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
#include <vector>

std::mutex mtx;
int shared_variable = 0;

void worker(int iterations) {
    for (int i = 0; i < iterations; ++i) {
        std::lock_guard<std::mutex> lock(mtx);
        // 模拟一些工作
        ++shared_variable;
    }
}

int main() {
    const int num_threads = 4;
    const int iterations = 1000000;

    std::vector<std::thread> threads;
    auto start_time = std::chrono::high_resolution_clock::now();

    // 创建并启动线程
    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back(worker, iterations);
    }

    // 等待所有线程完成
    for (auto& t : threads) {
        t.join();
    }

    auto end_time = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count();

    std::cout << "Total time: " << duration << " ms" << std::endl;
    std::cout << "Final shared variable value: " << shared_variable << std::endl;

    return 0;
}    

perf list看下跟缓存相关的几个event，并把之前 CPU及内存调度（一） – 进程、线程、系统调用、协程上下文切换 中谈到的TLB缓存命中率、上下文切换一并统计对比。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# perf stat -e cache-references,cache-misses,cpu-clock,cycles,instructions,context-switches,L1-dcache-loads,L1-dcache-load-misses,L1-icache-loads,L1-icache-load-misses,dTLB-loads,dTLB-load-misses,iTLB-loads,iTLB-load-misses
[CentOS-root@xdlinux ➜ mutex_cost git:(main) ✗ ]$ perf stat -e cache-references,cache-misses,cpu-clock,cycles,instructions,context-switches,L1-dcache-loads,L1-dcache-load-misses,L1-icache-loads,L1-icache-load-misses,dTLB-loads,dTLB-load-misses,iTLB-loads,iTLB-load-misses ./mutex_cost
Total time: 150 ms
Final shared variable value: 4000000

 Performance counter stats for './mutex_cost':

        # 运行期间对 CPU 缓存的总访问次数
        34,939,239      cache-references          #   73.922 M/sec                    (40.55%)
        # 访问 CPU 缓存时发生缺失的次数
         8,606,333      cache-misses              #   24.632 % of all cache refs      (41.60%)
        # 在 CPU 上实际运行所花费的时钟时间
            472.65 msec cpu-clock                 #    3.112 CPUs utilized          
        #  CPU 所经历的时钟周期数
     1,862,093,362      cycles                    #    3.940 GHz                      (43.42%)
        # 程序执行的指令总数
     1,816,283,768      instructions              #    0.98  insn per cycle           (42.92%)
        # 上下文切换次数
            46,308      context-switches          #    0.098 M/sec                  
       751,711,274      L1-dcache-loads           # 1590.424 M/sec                    (43.25%)
        # L1 数据缓存加载时发生缺失的次数
        12,983,482      L1-dcache-load-misses     #    1.73% of all L1-dcache accesses  (43.18%)
       105,670,987      L1-icache-loads           #  223.572 M/sec                    (42.96%)
        # L1 指令缓存加载时发生缺失的次数
           537,149      L1-icache-load-misses     #    0.51% of all L1-icache accesses  (40.99%)
            12,958      dTLB-loads                #    0.027 M/sec                    (40.48%)
        # 数据TLB 加载时发生缺失的次数
             1,099      dTLB-load-misses          #    8.48% of all dTLB cache accesses  (40.11%)
               892      iTLB-loads                #    0.002 M/sec                    (40.76%)
        # 指令TLB 加载时发生缺失的次数
         2,421,208      iTLB-load-misses          # 271435.87% of all iTLB cache accesses  (39.78%)

       0.151890572 seconds time elapsed

       0.150408000 seconds user
       0.296823000 seconds sys

说明：

• 其中cache-references表示总的CPU缓存访问次数，cache-misses表示缓存缺失次数（即缓存没命中），后面是占比。
• 测试5次，平均耗时150ms，cache-misses变化不大，基本都在24%；context-switches上下文切换46,308左右（0.097 M/sec）。

2.2. 原子变量无锁访问（实验）

使用atomic替换mutex加锁。

编译：g++ atomic_cost.cpp -o atomic_cost -pthread

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// atomic_cost.cpp
#include <iostream>
#include <thread>
#include <atomic>
#include <chrono>
#include <vector>

std::atomic<int> shared_variable(0);

void worker(int iterations) {
    for (int i = 0; i < iterations; ++i) {
        // 原子自增操作
        ++shared_variable;
    }
}

int main() {
    const int num_threads = 4;
    const int iterations = 1000000;

    std::vector<std::thread> threads;
    auto start_time = std::chrono::high_resolution_clock::now();

    // 创建并启动线程
    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back(worker, iterations);
    }

    // 等待所有线程完成
    for (auto& t : threads) {
        t.join();
    }

    auto end_time = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count();

    std::cout << "Total time: " << duration << " ms" << std::endl;
    std::cout << "Final shared variable value: " << shared_variable.load() << std::endl;

    return 0;
}    

perf采集结果说明：

• 测试5次，平均耗时42ms左右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
[CentOS-root@xdlinux ➜ mutex_cost git:(main) ✗ ]$ perf stat -e cache-references,cache-misses,cpu-clock,cycles,instructions,context-switches,L1-dcache-loads,L1-dcache-load-misses,L1-icache-loads,L1-icache-load-misses,dTLB-loads,dTLB-load-misses,iTLB-loads,iTLB-load-misses ./atomic_cost
Total time: 42 ms
Final shared variable value: 4000000

 Performance counter stats for './atomic_cost':

         2,626,586      cache-references          #   16.746 M/sec                    (35.33%)
         2,455,763      cache-misses              #   93.496 % of all cache refs      (36.92%)
            156.85 msec cpu-clock                 #    3.591 CPUs utilized          
       714,531,996      cycles                    #    4.555 GHz                      (39.46%)
        73,826,720      instructions              #    0.10  insn per cycle           (42.01%)
                 3      context-switches          #    0.019 K/sec                  
        28,718,275      L1-dcache-loads           #  183.091 M/sec                    (44.56%)
         2,321,953      L1-dcache-load-misses     #    8.09% of all L1-dcache accesses  (46.87%)
           333,198      L1-icache-loads           #    2.124 M/sec                    (47.76%)
             3,581      L1-icache-load-misses     #    1.07% of all L1-icache accesses  (46.49%)
               786      dTLB-loads                #    0.005 M/sec                    (43.97%)
               533      dTLB-load-misses          #   67.81% of all dTLB cache accesses  (41.43%)
                 0      iTLB-loads                #    0.000 K/sec                    (38.86%)
               272      iTLB-load-misses          #    0.00% of all iTLB cache accesses  (36.35%)

       0.043679512 seconds time elapsed

       0.155564000 seconds user
       0.000997000 seconds sys

2.3. 对比分析

上述结果不大直观，放到一起进行对比说明。

分析说明：

• 总时间：150ms vs 42ms
  • mutex：涉及上下文切换和锁竞争的开销，所以更慢。
  • atomic：利用CPU提供的原子操作指令，避免了锁的开销，所以更快。
• 缓存引用次数和速率：mutex 的缓存引用次数和速率都远高于 atomic
  • mutex：涉及多个线程的同步和上下文切换，导致更多的指令和数据访问，从而增加了对 CPU 缓存的引用。
  • atomic：操作相对简单，对缓存的访问较少。
• 缓存缺失率：使用atomic时极高，缺失率达93%
  • mutex：虽然会增加缓存引用，但由于线程在获取锁时可能会被阻塞，此时CPU可以执行其他任务，缓存中的数据有更多机会被复用，从而降低了缓存缺失率。
    • 缓存虽然被复用访问了，但是要注意伪共享问题（false sharing），一般设计cache line对齐
  • atomic：操作通常是比较轻量级，但由于多个线程可能同时对原子变量进行操作，会频繁地更新缓存中的数据，导致缓存行的频繁失效和重新加载，从而使缓存缺失率大幅上升。
• CPU时钟时间和CPU利用率：atomic的CPU时钟时间更短，但CPU利用率更高
  • mutex：线程等待锁时会处于阻塞状态，不占用CPU时间，因此CPU时钟时间较长，但CPU利用率相对较低。
  • atomic：操作是无锁的，线程可以持续执行，不会因为等待锁而阻塞，所以CPU时钟时间更短，但由于多个线程同时竞争原子变量，会使CPU利用率更高。
• 指令总数（instructions）和每周期指令数（insn per cycle）：mutex的指令总数更多，但每周期指令数更高
  • mutex：操作涉及锁的获取和释放，需要执行更多的指令来实现线程同步。但由于线程在等待锁时会让出 CPU，CPU 有更多机会进行指令调度，所以每周期指令数较高。
  • atomic：操作相对简单，指令总数较少。但由于多个线程同时竞争原子变量，会导致 CPU 频繁地进行指令流水线的刷新和重新调度，从而降低了每周期指令数。
• 上下文切换次数：mutex 的上下文切换次数远高于 atomic
  • mutex：当一个线程尝试获取被其他线程持有的锁时，会被阻塞，此时操作系统会进行上下文切换，将 CPU 资源分配给其他线程。在多个线程竞争锁的情况下，会频繁发生上下文切换，增加了系统开销。
  • atomic：操作是无锁的，线程不需要等待锁，因此不会因为锁竞争而导致上下文切换，只有在操作系统进行其他调度时才会发生少量的上下文切换。
• L1 缓存和 TLB 相关指标
  • 总体来说，mutex的 L1缓存 和 TLB相关指标 相对较好，而atomic的 dTLB缺失率 和 L1数据缓存缺失率 较高。
  • 原因：
    • mutex：线程在等待锁时会让出 CPU，缓存中的数据有更多机会被复用，减少了 L1 缓存和 TLB 的缺失率。
    • atomic：多个线程同时对原子变量进行操作，会频繁地更新缓存中的数据，导致 L1 缓存和 TLB 的频繁失效和重新加载，从而增加了缺失率。

3. 一些优化思路

上面实验对比中，有两个优化点此处进行说明：降低缓存缺失率 和 减少上下文切换。

3.1. 降低缓存缺失率

缓存缺失率高的影响：

• 数据访问延迟增加：缓存缺失发生时CPU要从主存获取数据，这比缓存慢得多。L1缓存访问速度一般几个时钟周期，主存则几十上百时钟周期
• 指令执行效率降低：现代处理器通常采用流水线技术来提高指令执行效率，缓存缺失会导致流水线停顿，因为处理器需要等待数据从主内存中加载到缓存后才能继续执行相关指令
• 系统吞吐量下降：高缓存缺失率会使 CPU 花费更多时间等待数据，而不是执行有用的指令，这会导致系统的吞吐量下降

优化思路：

• 优化数据访问模式：
  • 空间局部性优化，尽量按数据在内存中的存储顺序进行访问；
  • 时间局部性，频繁使用的数据，放在靠近循环顶部的位置，以减少缓存缺失。
• 合理设计缓存策略：
  • 选择合适的缓存替换算法，如LRU，能够较好地适应大多数程序的访问模式，提高缓存利用率；
  • 调整缓存容量和分区，可根据访问频率和重要性分区
• 优化程序代码
  • 减少不必要的内存分配和释放，频繁的内存分配和释放会导致内存碎片，影响缓存的使用效率。可使用内存池、对象池

3.2. 减少上下文切换

上下文切换的影响：

• 额外的开销：需要保存当前进程或线程的上下文信息（如寄存器值、程序计数器等），并加载新进程或线程的上下文信息。需要一系列的指令，会消耗CPU和内存产生额外开销
  • 相关开销，在CPU及内存调度（一） – 进程、线程、系统调用、协程上下文切换中也有了解
• 缓存失效与重建：不同的进程或线程可能使用不同的内存空间，切换到新进程和线程时，原来缓存中的数据可能不再有效，需要重新加载数据到缓存中
  • 如上所述，缓存缺失会导致数据访问延迟增加和指令执行效率下降
• 影响程序的局部性
  • 程序的局部性原理指出，程序在执行过程中通常会频繁访问相邻的内存地址和最近使用过的数据
  • 上下文切换会打破这种局部性，新的进程或线程可能具有不同的访问模式，导致缓存无法有效利用，降低了缓存的命中率，进而影响程序性能

优化思路：

• 优化线程数量
  • 分析任务特性：对任务进行分析，确定其是CPU密集型还是I/O密集型。CPU 密集型任务通常需要较少的线程，因为过多的线程会导致频繁的上下文切换，而 I/O 密集型任务则可以通过增加线程数来提高资源利用率。
    • 通常建议CPU密集型任务的线程数与CPU核心数相匹配，或者稍微多一些以应对可能的任务等待情况；对于IO密集型，执行IO操作时线程一般处于等待状态，可以切换到其他线程执行任务
  • 使用线程池：线程池可以限制线程的创建数量，并对线程进行复用。通过合理设置线程池的大小，能够避免线程的频繁创建和销毁，从而减少上下文切换。
• 优化锁的使用
  • 减小锁的粒度：将大的锁分解为多个小的锁，使得每个锁保护的资源范围更小。这样可以降低多个线程同时竞争锁的概率，减少因获取锁而导致的上下文切换。
    • 例如，在一个包含多个元素的集合中，如果对整个集合加锁，那么每次只有一个线程能够访问集合中的元素。可以将集合分解为多个子集合，每个子集合使用一个独立的锁，这样不同的线程可以同时访问不同的子集合，提高并发度。
  • 避免不必要的锁：有些操作可能在单线程环境下执行，或者在特定的条件下不需要进行同步，此时应该去除不必要的锁，以减少上下文切换
• 采用无锁数据结构
  • 无锁数据结构通过使用原子操作和一些特殊的算法来实现数据的并发访问，避免了传统锁机制带来的上下文切换开销。
    • 无锁栈（Lock-Free Stack），基于原子操作（如 CAS，Compare-And-Swap）实现，其入栈和出栈操作都使用CAS来保证操作的原子性
      • 使用场景：比如在多线程环境下，用于任务调度或内存管理中的临时数据存储。多个线程可以同时向栈中压入任务，或者从栈中弹出任务进行处理
      • std::atomic的compare_exchange_weak，可见：cppreference
    • 无锁队列（Lock-Free Queue），通常使用两个原子指针（头指针和尾指针）以及 CAS 操作来实现。
      • 使用场景：比如在多线程生产者 - 消费者模型中广泛应用，生产者线程可以无锁地将任务放入队列，消费者线程可以无锁地从队列中取出任务进行处理
    • 无锁哈希表、无锁链表
• 优化系统调度
  • 设置线程优先级，根据任务的重要性和紧急程度，为线程设置不同的优先级。调度器会优先调度优先级高的线程，减少低优先级线程的上下文切换。
    • pthread_setschedparam可设置线程优先级，除非绝对必要，否则应避免修改线程的默认优先级
  • 使用亲缘性绑定，将线程绑定到特定的 CPU 核心上，使得线程在执行过程中尽量在同一个 CPU 核心上运行，减少因线程在不同 CPU 核心之间迁移而导致的上下文切换。
    • taskset 或 pthread_setaffinity_np
• 避免阻塞操作
  • 尽量避免在关键路径上执行阻塞操作，如 I/O 操作、等待锁等。可以采用异步编程模型或者使用非阻塞 I/O 来减少线程的阻塞，从而降低上下文切换的频率。
    • io_uring、epoll

3.3. 实践tips

记录一些实践建议。

1）比如 为什么你的高并发锁优化做不好？中：

基于分片锁减小锁的粒度时：将锁的粒度减小，分散到多个分片，并通过哈希映射将竞争分散到不同锁上。

• 分片锁需要去关注硬件方面的细节，建议N（分片数量）取CPU核心数的2到4倍，而且要通过alignas(64)来对齐缓存行，这样的话能够避免性能上的暗坑。
• 如：alignas(64) std::array<std::mutex, N> shards;（template <size_t N>;）

4. 无锁编程技术

上面对比锁和atomic时，已经涉及到无锁相关的使用了，但比较散不成体系，这里再梳理总结下。

4.1. 概念说明

无锁编程不只是说没有互斥锁的编程方式，这里的“锁”并不是简单地指互斥锁，而是代表使整个程序陷入锁住状态的可能性。

• Lock-Free（无锁）：在一个无锁的并发算法中，即使存在多个线程同时尝试对同一数据进行操作，也能保证至少有一个线程能够继续前进，而不会因为其他线程的操作被阻塞或等待。这意味着系统整体上总是能向前进展。
• Wait-Free（等待自由）：这是比无锁更强的一种性质，指的是每一个参与执行的线程都能够在有限步数内完成自己的任务，而不依赖于其他线程的行为。换句话说，没有任何线程会被无限期地延迟。

在无锁编程中实现无阻塞，有一系列的技术可以实现：原子操作（如上面提到的CAS）、内存屏障、避免ABA问题等。（主要参考自：无锁编程简介（翻译）——译自《An Introduction to Lock-Free Programming》）

• 原子操作：RMD（Read-Modify-Write）
  • RMW操作的应用：
    • 例如lightweight mutex（轻量级互斥锁）， recursive mutex（递归互斥锁）和lightweight logging system（轻量级的日志系统），本篇参考文章中都贴了链接，可以进一步了解学习
  • RMW操作，包含C++11下的std::atomic::fetch_add（Win32、IOS暂不关注）。
    • 注意C++11中，原子操作标准并不保证这个操作在所有平台下都是无锁的，所以最好能够了解你使用的平台是否符合。
    • 可以通过调用std::atomic<T>::is_lock_free来确认
  • CAS（Compare-And-Swap）循环：可能讨论最多的RMW操作就是compare-and-swap（CAS）
    • 当进行CAS循环时，特殊需要注意的地方是操作必须防止出现ABA问题

关于内存模型、缓存一致性协议（MESI），可了解：无锁编程——从CPU缓存一致性讲到内存模型

4.1.1. 澄清：RCU、CAS、RMW

1、RCU（Read-Copy-Update，读 - 复制 - 更新）

• 原理：RCU 是一种针对多读少写场景设计的同步机制。它允许多个读操作并发执行，且不会被写操作阻塞；写操作则需要先复制一份数据副本，在副本上进行修改，修改完成后再更新到原数据结构中，同时等待所有正在进行的读操作完成，才会释放旧数据。
• 应用场景：常用于内核、数据库、文件系统等需要高效处理大量读操作的场景，例如 Linux 内核中的路由表管理、文件系统的 inode 管理等。

2、CAS（Compare-And-Swap，比较并交换）

• 原理：CAS 是一种原子操作，它会比较内存中的值与预期值，如果相等则将内存中的值更新为新值，整个过程是原子的，不会被其他线程中断。CAS 操作通常由硬件指令支持，例如 x86 架构中的CMPXCHG指令。
• 应用场景：常用于实现无锁数据结构，如无锁栈、无锁队列等，也可用于实现自旋锁、信号量等同步原语。

3、RMW（Read-Modify-Write，读 - 修改 - 写）

• 原理：RMW 是一类原子操作的统称，它包含了读取内存中的值、对该值进行修改、再将修改后的值写回内存这三个步骤，并且保证这三个步骤是原子的。
  • CAS 可以看作是 RMW 操作的一种特殊形式。
• 应用场景：在需要对共享数据进行原子更新的场景中使用，如计数器的原子递增、递减操作等。

相互关系：

• 实现依赖关系：
  • RCU 可能依赖 CAS 或 RMW：在 RCU 的实现中，写操作可能会使用 CAS 或其他 RMW 操作来更新指针或标记位。例如，在更新数据结构的指针时，为了确保操作的原子性，可能会使用 CAS 操作来将新的指针值更新到内存中。
  • CAS 是 RMW 的一种特殊形式：CAS 操作符合 RMW 的定义，它包含了读取内存值、比较值、更新值的过程，并且保证这三个步骤是原子的。因此，CAS 可以看作是 RMW 操作的一个特例。
• 使用场景互补
  • RCU 适用于多读少写场景
  • CAS 和 RMW 适用于对共享数据进行原子更新的场景。一些无锁数据结构的实现中，CAS 和 RMW 操作是核心的实现手段。
• 并发控制策略不同
  • RCU 提供了一种宽松的并发控制策略
  • CAS 和 RMW 提供了更严格的原子性保证
    • 通过硬件指令确保操作的原子性，保证在多线程环境下对共享数据的操作不会出现数据竞争。

4.1.2. ABA问题

当一个变量的值从 A 变为 B，再变回 A 时，系统可能会误认为该变量没有发生变化，但实际上它经历了中间状态 B 的改变。

示例：多线程环境中，2个线程同时操作一个原子变量

• 线程 1 读取原子变量的值为 A，然后暂停
• 线程 2 接着执行，将原子变量的值从 A 改为 B，再改为 A
• 线程 1 恢复执行，它检查原子变量的值，发现还是 A，就认为变量没有被修改过，但实际上变量已经经历了 ABA 的变化过程

可能造成的问题：

• 如果某个操作依赖于变量值未发生变化来保证数据的一致性，那么 ABA 问题可能会破坏这种一致性
  • 例如，在使用乐观锁进行数据库更新时，以为数据未变而进行更新，可能覆盖掉其他线程对数据的中间修改，导致数据丢失或错误
• 在一些资源分配和回收的场景中，ABA 问题可能导致资源被错误地重复使用
  • 比如内存释放又申请

解决方法：使用版本号机制、使用原子引用类

模拟ABA问题：std::atomic<int*>对指针进行原子操作

• 线程1 读取指针后暂停（sleep等待）；
• 线程2 将指针值从 &valueA 改为 &valueB 再改回 &valueA
• 线程1 恢复后，使用compare_exchange_strong比较并交换（CAS），即使值变回了 &valueA，操作也会成功，这就模拟了 ABA 问题。
  • compare_exchange_strong的说明，具体见下面的章节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 模拟ABA问题
void simulateABAProblem() {
    std::atomic<int*> atomicPtr(nullptr);
    int valueA = 10;
    int valueB = 20;

    atomicPtr.store(&valueA);

    // 线程1读取值
    std::thread thread1([&]() {
        int* expected = atomicPtr.load();
        // 模拟一些操作
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        if (atomicPtr.compare_exchange_strong(expected, &valueA)) {
            std::cout << "Thread 1: CAS succeeded, but there might be an ABA problem." << std::endl;
        }
    });

    // 线程2修改值
    std::thread thread2([&]() {
        int* expected = &valueA;
        // 改成&valueB
        if (atomicPtr.compare_exchange_strong(expected, &valueB)) {
            std::this_thread::sleep_for(std::chrono::milliseconds(50));
            expected = &valueB;
            // 改成&valueA
            atomicPtr.compare_exchange_strong(expected, &valueA);
        }
    });

    thread1.join();
    thread2.join();
}

4.2. 指令重排

在不改变程序语义的前提下，编译器和处理器会对指令进行重新排序，以更好地利用硬件资源，提高指令级并行度，从而提高程序的执行速度。例如，对于一些相互之间没有依赖关系的指令，它们的执行顺序可以被调整，以减少处理器的等待时间，充分发挥处理器的运算能力。

了解重排规则：

• 数据依赖性：如果两条指令之间存在数据依赖关系，即后一条指令依赖于前一条指令的结果，那么它们的执行顺序不能被重排。
  • 例如，int a = 5;、int b = a + 3;，这两条指令中，第二条指令依赖于第一条指令对a的赋值，所以它们的顺序不能改变。
• 控制依赖性：指令的执行顺序依赖于控制流，如if-else语句、循环语句等。
  • 在保证程序逻辑正确的前提下，编译器和处理器会尽量对控制流中的指令进行重排优化，但不会改变控制流的执行顺序。
• 内存访问顺序：在多线程环境下，内存访问顺序的重排可能会导致数据竞争和不一致性问题。

有两类重排类型：

• 1、编译器重排
  • 编译器在编译阶段，会对源代码进行分析和优化，根据指令之间的依赖关系和目标平台的特性，对指令进行重新排列。
  • 例如，对于一些可以提前计算的表达式，编译器可能会将其计算顺序调整到更早的位置，以减少后续指令的等待时间。
• 2、处理器重排
  • 处理器在执行指令时，也会根据自身的流水线结构和执行单元的空闲情况，对指令进行动态重排。

4.3. C++中的atomic

C++11 在头文件中引入了 atomic 模板，对原子对象进行了封装。可以应用到任何类型上去。

但不同类型效果有所不同：

• 对于整型量和指针等简单类型，通常结果是无锁的原子对象；
• 其他一些类型，编译器会自动为这些原子对象的操作加上锁
  • 编译器提供了一个原子对象的成员函数 is_lock_free，可以检查这个原子对象上的操作是否是无锁的，可见cppreference

原子操作有三类：

• 读：在读取的过程中，读取位置的内容不会发生任何变动
• 写：在写入的过程中，其他执行线程不会看到部分写入的结果
• 读‐修改‐写（RMW）：读取内存、修改数值、然后写回内存，整个操作的过程中间不会有其他写入操作插入，其他执行线程不会看到部分写入的结果。

4.3.1. 内存序（memory order）

atomic头文件中定义了6种内存序，对比前面指令重排的影响，就更有概念了：

• memory_order_relaxed：松散内存序，只用来保证对原子对象的操作是原子的
• memory_order_consume：目前不鼓励使用，其内部实现可能同 memory_order_acquire
• memory_order_acquire：获得操作，在读取某原子对象时，当前线程的任何后面的读写操作都不允许重排到这个操作的前面去，并且其他线程在对同一个原子对象释放之前的所有内存写入都在当前线程可见
• memory_order_release：释放操作，在写入某原子对象时，当前线程的任何前面的读写操作都不允许重排到这个操作的后面去，并且当前线程的所有内存写入都在对同一个原子对象进行获取的其他线程可见
• memory_order_acq_rel：获得释放操作，一个读‐修改‐写操作（RMW）同时具有获得语义和释放语义，即它前后的任何读写操作都不允许重排，并且其他线程在对同一个原子对象释放之前的所有内存写入都在当前线程可见，当前线程的所有内存写入都在对同一个原子对象进行获取的其他线程可见
• memory_order_seq_cst：顺序一致性语义，对于读操作相当于获取，对于写操作相当于释放，对于读‐修改‐写操作相当于获得释放，是所有原子操作的默认内存序
  • 对访问顺序的约束力最强

从读写的角度划分：

这里也说下 volatile：

在某些编译器里，使用 volatile 关键字可以达到内存同步的效果。但我们必须记住，这不是 volatile 的设计意图，也不能通用地达到内存同步的效果。volatile 的语义只是防止编译器“优化”掉对内存的读写而已。它的合适用法，目前主要是用来读写映射到内存地址上的 I/O 操作。

由于 volatile 不能在多处理器的环境下确保多个线程能看到同样顺序的数据变化，在今天的通用应用程序中，不应该再看到 volatile 的出现。
参考：内存模型和atomic：理解并发的复杂性

4.3.2. CAS成员函数

上述原子变量的成员函数 compare_exchange_strong、compare_exchange_weak，实现了两个CAS（比较加交换）版本。

下面仅列举其中一个进行功能说明。具体定义，见：cppreference compare_exchange。atomic的其他成员函数，也可见cppreference。

1
2
bool compare_exchange_strong( T& expected, T desired, std::memory_order order = std::memory_order_seq_cst );
bool compare_exchange_weak( T& expected, T desired, std::memory_order order = std::memory_order_seq_cst );

1）共同逻辑：首先将原子变量的当前值与期望值（desired）进行比较

• 如果相等，则将原子变量的值更新为新值（desired）；
• 如果不相等，则将期望值（expected）更新为原子变量的当前值。（注意是修改expected的值，原子变量的值不变）

2）区别

• 伪失败情况
  • compare_exchange_weak 可能会出现 “伪失败” 的情况，即即使原子对象的值等于期望值，交换操作也可能失败。
    • 这通常是由于硬件层面的一些限制导致的，例如在某些架构上，CAS 操作可能会受到缓存一致性协议或其他硬件因素的影响。
    • 因此，compare_exchange_weak 通常需要在循环中使用，以确保操作最终能够成功。
  • compare_exchange_strong 保证不会出现 “伪失败” 的情况。只要比较失败，就意味着原子对象的值确实不等于期望值。
• 性能差异
  • compare_exchange_weak 在某些硬件平台上的性能可能会更好，因为伪失败的处理通常比真正的并发冲突处理要轻量级
  • compare_exchange_strong 虽然提供了更强的语义保证，但由于需要避免伪失败，可能会有一些额外的性能开销。

3）使用场景

• compare_exchange_weak：适用于高并发场景，且操作可以被重试的情况。
  • 例如，在实现无锁队列、无锁栈等无锁数据结构时，由于这些操作通常会在循环中进行，即使出现伪失败也可以通过重试来完成操作，因此可以使用 compare_exchange_weak 来提高性能。
• compare_exchange_strong：适用于对操作结果的准确性要求较高，不允许出现伪失败的场景。
  • 例如，在某些需要精确判断原子变量值是否发生变化的场景中，或者在不适合使用循环重试的情况

4.4. 无锁队列实现参考

前面谈到各种无锁结构（Lock-Free），比如无锁栈、无锁队列、无锁哈希表、无锁链表，这里了解下无锁队列实现。

下面是一个基本实现，实际中使用可能还要考虑ABA问题，节点结构中可定义一个递增标记或版本号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
template<typename T>
class LockFreeQueue {
private:
    struct Node {
        T data;
        std::atomic<Node*> next;
        Node(const T& value) : data(value), next(nullptr) {}
    };

    std::atomic<Node*> head;
    std::atomic<Node*> tail;

public:
    LockFreeQueue() {
        Node* dummy = new Node(T());
        head.store(dummy);
        tail.store(dummy);
    }

    ~LockFreeQueue() {
        while (head.load()) {
            Node* temp = head.load();
            head.store(temp->next.load());
            delete temp;
        }
    }

    void enqueue(const T& value) {
        Node* newNode = new Node(value);
        Node* oldTail = tail.load();
        while (!tail.compare_exchange_weak(oldTail, newNode)) {}
        oldTail->next.store(newNode);
    }

    bool dequeue(T& value) {
        Node* oldHead = head.load();
        Node* next = oldHead->next.load();
        if (next == nullptr) {
            return false;
        }
        while (!head.compare_exchange_weak(oldHead, next)) {
            next = oldHead->next.load();
            if (next == nullptr) {
                return false;
            }
        }
        value = next->data;
        delete oldHead;
        return true;
    }
};

5. 小结

梳理学习无锁编程技术，并实验对比锁的消耗情况，有更直观的体感。

6. 参考

• 为什么你的高并发锁优化做不好？
• C++性能榨汁机之无锁编程
• 无锁编程简介（翻译）——译自《An Introduction to Lock-Free Programming》
• 无锁编程——从CPU缓存一致性讲到内存模型
• Xbox 360 和 Microsof Windows 的无锁编程注意事项
• 内存模型和atomic：理解并发的复杂性
• coolshell – 无锁队列的实现
• LLM