一 CPP六种内存序¶
在C11的atomic库，定义了六种内存序： - memory_order_relaxed（松散顺序）
std::atomic<int> counter{0};
counter.fetch_add(1, std::memory_order_relaxed); // 原子递增，无顺序保证
std::atomic<bool> ready{false};
int data = 0; // 生产者
data = 42;
ready.store(true, std::memory_order_release); // 发布数据 // 消费者
while (!ready.load(std::memory_order_acquire)); // 等待同步
assert(data == 42); // 保证看到 data=42
| 作用 | 适用场景 | |
|---|---|---|
| memory_order_relaxed | 仅保证原子操作的原子性（无数据竞争），不提供任何同步或顺序约束。编译器和处理器可自由重排指令 | 无同步需求的独立操作，如计数器统计 |
| memory_order_consume | 仅保证依赖该原子变量的操作不被重排到其之前（依赖链同步）。例如，通过原子指针访问数据时，解引用操作有序 | 数据依赖较强的场景（如指针发布），但实际使用较少，且 C++26 起已被弃用（推荐用 acquire替代） |
| memory_order_acquire | 确保后续操作不会重排到该操作之前，且能看到其他线程的 release写入 |
读取共享数据前的同步。又称读屏障 |
| memory_order_release | 确保之前的操作不会重排到该操作之后，且修改结果对 acquire线程可见。 |
写入共享数据后的同步（如锁释放、发布数据） |
| memory_order_acq_rel | 同时具备 acquire和 release语义，适用于读-修改-写（RMW）操作 | 自旋锁、无锁数据结构（如队列、栈） |
| memory_order_seq_cst（顺序一致性） | 最强约束，所有线程看到的操作顺序一致（全局总顺序）。默认内存序，但性能开销最大 | 需要严格全局顺序的算法（如 Dekker 算法、跨线程标志检查） |
二 为什么不用多线程¶
多线程问题¶
传统的共享数据访问方式是采用同步原语(临界区、锁、条件变量等) 来达到共享数据的安全访问，同步恰恰和并行编程是对立的。 - 一方面，有些同步原语是操作系统的内核对象，调用该原语会带来昂贵的上下文切换(用户态切换到内核态)代价 - 同时，内核对象是一个比较有限的资源。 - 另一方面，同步杜绝了并行操作，一个线程在访问共享数据的时候，其他的多个线程必须在排队空闲等待。 - 同时，同步可扩展性很弱，随着并行线程的增加，很容易成为程序的一个瓶颈，
多线程编程惯例¶
- CPU开销大场景，能利用多核，就多核
- 多线程默认加锁。在加锁保证业务正常条件下，再考虑互斥锁带来的性能损耗。
- 互斥锁<读写锁<自旋锁<无锁（原子操作）
- 减少线程之间的相关性：
- 线程间共享变量<线程内变量<函数式编程（没有变量）
- 尽量减少锁的粒度：
- 减少加锁的代码段（减少加锁的时间）
- 分成多个锁，减少竞争
多线程编程痛点¶
- 条件竞争：忘记加锁
- 死锁：不正确的加锁顺序
- 异常：未被捕获的异常导致程序崩溃
- 错误地忽略通知：线程无法被唤醒
二 并发访问之初¶
人们开始研究对共享数据进行并发访问的数据结构和算法，延伸出以下方向。 1. Transactional memory --- 事务性内存 ：一个事务（transaction ） 执行并原子地提交所有结果到内存（如果事务成功），或中止并取消所有的结果（如果事务失败）。 1. 缺点：软件性能开销大 2. Fine-grained algorithms --- 细粒度(锁)算法： - 另类“同步”--比如“轻量级”原子性原语（自旋锁），而不动用系统提供的昂贵消耗同步原语。适用任何一个锁持有时间少于线程阻塞和唤醒所需要的时间和场合。 - 由于锁粒度极小，在此类原语之上构建的数据结构，可以并行读取，甚至并发写入。 - 缺点：在并发连接相对轻量的情况下，其性能和无锁性能相媲美 3. Lock-free data structures --- 无锁数据结构 - 为解决在高并发场景下，细粒度锁无法避免的性能瓶颈，将共享数据放入无锁的数据结构中，采用原子修改的方式来访问共享数据。
常用无锁结构：无锁队列lock free queue，无锁容器：b+tree，
三 无锁编程¶
针对无锁编程我们主要会涉及到如下几个方面： 1、原子性、原子性原语、原子操作 2、CAS解法与ABA问题 3、seqlock（顺序锁） 4、内存屏障（Memory Barriers）
3.1 原子性、原子性原语、原子操作¶
对共享资源的安全访问，在不使用锁、同步原语的情况下，只能依赖于硬件支持的原子性操作，离开原子操作的保证，无锁编程(lock-free programming)将变得不可能。
原子性操作¶
原子性操作可以简单划分为两部分：
1. 原子性读写(atomic read and write)：原子load(读)、原子store(写)。
2. 原子性交换(Atomic Read-Modify-Write -- RMW)。
什么是原子操作？保证指令以原子的方式执行——执行过程不被打断。
这是是多数无锁编程的基本前提。
原子操作--问题¶
-
昂贵：原子操作要保证要么全部发生，要么全部没发生，这样原子操作绝对不是一个廉价的消耗低的指令，相反，原子操作是一个较为昂贵的指令。
-
通常情况下，我们有一个对共享变量必须使用原子操作的规则： 任何时刻，只要存在两个或多个线程并发地对同一个共享变量进行操作，并且这些操作中的其中一个是执行了写操作，那么所有的线程都必须使用原子操作。
原子操作实现¶
早期：CPU芯片上有一条引线#HLOCK pin，如果汇编语言的程序中在一条指令前面加上前缀"LOCK"，经过汇编以后的机器代码就使CPU在执行这条指令的时候把#HLOCK pin的电位拉低，持续到这条指令结束时放开，从而把总线锁住，这样同一总线上别的CPU就暂时不能通过总线访问内存了，保证了这条指令在多处理器环境中的原子性。较low 现在：现在LOCK只会阻塞其他cpu核对相关内存的缓存块的访问 - 独占：LOCK是一个指令的描述符，表示后续的指令在执行的时候，在内存总线上加锁。总线锁会导致其他几个核在一定时钟周期内无法访问内存。 - 轻量：虽然总线锁会影响其他核的性能，但比起操作系统级别的锁，已经轻量太多了。
操作系统内核提供atomic_*系列原子操作¶
- 声明和定义
- 读写操作：read，add,sub
- 加一减一：atomic_inc,atomic_dec
- 执行操作并测试；
- 自增，自减sync版本built-in函数
原子性能测试¶
- Linux、20线程创建+运行自增200000次：互斥锁性能消耗是原子变量的五倍。 此结果还会随着随着冲突数量的增加，性能差距会进一步拉开
语言层面：¶
C++ atomic library、¶
值得注意的是：C++并没有规定原子操作，所有的内存操作都是非原子性的。 但是在任何X86、X64等现代处理器中，只要内存对齐，32位整型赋值操作被编译期和和处理器保证为原子操作，
但是，为了保证移植性，必须使用C++11的原子库。
volatile¶
- 在现代处理器中，对于一个对齐的整形类型(整形或指针)，其读写操作是原子的，
- 而对于现代编译器，用volatile修饰的基本类型正确对齐的保障，并且限制了编译器对其优化。 这样通过对int变量加上volatile修饰，我们就能对该变量进行原子性读写。
无保证：但是，其实vloatile既不能保证原子性，也不会有任何的Memery Barrier(内存栅栏)的保证。 volatile仅仅是保证int的地址对齐，具有以下特性： - 易变性：需要重新从内存读取 - 不可优化性： - 不要对我这个变量进行各种激进的优化，甚至将变量直接消除。 - 保证程序员写在代码中的指令，一定会被执行。 - 顺序性：能够保证Volatile变量间的顺序性，编译器不会进行乱序优化。
3.2 CAS¶
一般采用原子级的read-modify-write原语来实现Lock-Free算法，而 compare-and-swap (CAS）被认为是最基础的一种原子性RMW操作，其伪代码如下： - 用原子级的read-modify-write原语来实现Lock-Free算法，而 compare-and-swap (CAS）被认为是最基础的一种原子性RMW操作 返回成功：
bool CAS( int * pAddr, int nExpected, int nNew )
atomically {
if ( *pAddr == nExpected ) {
*pAddr = nNew ;
return true ;
}
else
return false ;
}
int FAA( int * pAddr, int nIncr )
{
int ncur = *pAddr;
do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr ) ;//compare_exchange失败会返回当前值于ncur
return ncur ;
}
CAS延伸¶
CAS作为最基础的RMW操作，其他所有RMW操作都可以通过CAS来实现，例如 fetch-and-add(FAA)，伪代码如下：
int FAA( int * pAddr, int nIncr )
{
int ncur = *pAddr;
do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr ) ;//compare_exchange失败会返回当前值于ncur
return ncur ;
}
C++11 的原子library¶
compare_exchange_weak()就是最基础的CAS
std::atomic<>::fetch_add() std::atomic<>::fetch_sub() std::atomic<>::fetch_and() std::atomic<>::fetch_or() std::atomic<>::fetch_xor() std::atomic<>::exchange() std::atomic<>::compare_exchange_strong() std::atomic<>::compare_exchange_weak()
C++11 atomic library中的原子RMW操作有点少，不能满足我们实际需求，我们可以自己动手实现自己需要的原子RMW操作。
Weak and Strong CAS¶
相信大家看到C++11的CAS操作有两个compare_exchange_weak和compare_exchange_strong，CAS怎么还有强弱之分呢？现代处理器架构对CAS的实现分成两大阵营： (1)实现了原子性CAS原语 -- X86、Intel Itanium、Sparc等处理器架构，最早实现于IBM System 370。 (2)实现LL/SC对(load-linked/store-conditional) -- PowerPC, MIPS, Alpha, ARM 等处理器架构，最早实现于DEC，通过LL/SC对可以实现原子性CAS，但在一些情况下它并不具有原子性。为什么会存在LL/SC对的使用，而不直接实现CAS原语呢？要说明LL/SC对存在的原因，不得不说一下无锁编程中的一个棘手问题：ABA问题。
3.3 无锁编程棘手问题：ABA 问题¶
一般的CAS在决定是否要修改某个变量时，会判断一下当前值跟旧值是否相等。 如果相等，则认为变量未被其他线程修改，可以改。 但是，“相等”并不真的意味着“未被修改”。
比如： - 另一个线程可能会把变量的值从A改成B，又从B改回成A。 这就是ABA问题。
有时不会影响业务问题可以忽略，有时不能忽略。 解决方法: 这时要解决这个问题，一般的做法是给变量关联一个只能递增、不能递减的版本号。 在compare时不但compare变量值，还要再compare一下版本号。
3.4 无所编程棘手问题：伪共享¶
3.4 顺序锁SeqLock¶
用于能够区分读与写的场合，并且是读操作很多、写操作很少，写操作的优先权大于读操作。
实现： - seqlock的实现思路是，用一个递增的整型数表示sequence。写操作进入临界区时，sequence++；退出临界区时，sequence再++。 - 写操作还需要获得一个锁（比如mutex），这个锁仅用于写写互斥，以保证同一时间最多只有一个正在进行的写操作。 - 当sequence为奇数时，表示有写操作正在进行，这时读操作要进入临界区需要等待，直到sequence变为偶数。 - 读操作进入临界区时，需要记录下当前sequence的值，等它退出临界区的时候用记录的sequence与当前sequence做比较，不相等则表示在读操作进入临界区期间发生了写操作，这时候读操作读到的东西是无效的，需要返回重试。 - 写写操作：seqlock写写是必须要互斥的。但是seqlock的应用场景本身就是读多写少的情况，写冲突的概率是很低的。所以这里的写写互斥基本上不会有什么性能损失。 - 读写操作：而读写操作是不需要互斥的。
seqlock的应用场景是写操作优先于读操作，对于写操作来说，几乎是没有阻塞的（除非发生写写冲突这一小概率事件），只需要做sequence++这一附加动作。而读操作也不需要阻塞，只是当发现读写冲突时需要retry。
典型应用--获取时钟：seqlock的一个典型应用是时钟的更新，系统中每1毫秒会有一个时钟中断，相应的中断处理程序会更新时钟（写操作）。 - 在这种情况下，使用seqlock可以避免过多的gettimeofday系统调用把中断处理程序给阻塞了（如果使用读写锁，而不用seqlock的话就会这样）。 - 中断处理程序总是优先的，而如果gettimeofday系统调用与之冲突了，那用户程序多等等也无妨。
具体实现¶
seqlock的实现非常简单： 写操作进入临界区时：
void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock); // 上写写互斥锁
++sl->sequence; // sequence++
}
void write_sequnlock(seqlock_t *sl)
{
sl->sequence++; // sequence再++
spin_unlock(&sl->lock); // 释放写写互斥锁
}
unsigned read_seqbegin(const seqlock_t *sl)
{
unsigned ret;
repeat:
ret = sl->sequence; // 读sequence值
if (unlikely(ret & 1)) { // 如果sequence为奇数自旋等待
goto repeat;
}
return ret;
}
读操作尝试退出临界区时
int read_seqretry(const seqlock_t *sl, unsigned start)
{
return (sl->sequence != start); //看看sequence与进入临界区时是否发生过改变
}
而读操作一般会这样进行：
do {
seq = read_seqbegin(&seq_lock);// 进入临界区
do_something();
} while (read_seqretry(&seq_lock, seq)); // 尝试退出临界区，存在冲突则重试
四 内存屏障¶
也称内存栅栏，内存栅障，屏障指令，是一类同步屏障指令。 是CPU或编译器在对内存随机访问的操作中的一个同步点，使得此点之前的所有读写操作都执行后才可以开始执行此点之后的操作。
为什么需要内存屏障¶
大多数现代计算机为了提高性能而采取乱序执行，这使得内存屏障成为必须。 通常情况下，我们希望我们所编写的程序代码能"所见即所得"，即程序逻辑满足程序的顺序性(满足program order)，然而，很遗憾，我们的程序逻辑("所见")和最后的执行结果("所得")隔着：
编译器、CPU取指执行
- CPU的核心思想就是取指执行，对于in-order的单核CPU，并且没有cache，汇编指令的取指和执行是严格按照顺序进行的。
- 然而，随着计算机系统越来越复杂（多核、cache、superscalar、out-of-order），使用汇编指令这样贴近处理器的语言也无法保证其被CPU执行的结果的一致性，
- 编译器了解底层CPU的思维模式，因此，它可以在将程序翻译成汇编的时候进行优化（例如内存访问指令的重新排序），让产出的汇编指令在CPU上运行的时候更快。
但编译器开发者和cpu厂商都遵守着内存乱序的基本原则，不能随便乱序，简单归纳如下：
不能改变单线程程序的执行行为 -- 但线程程序总是满足Program Order(所见即所得)
两种内存barrier¶
存在两种类型的Memory Barriers: 编译器的Memory Barrier、处理器的Memory Barrier。 对于编译器的Memory Barrier比较好理解，就是防止编译器为了优化而将代码执行调整乱序。而处理器的Memory Barrier是防止CPU怎样的乱序呢？CPU的内存乱序是怎么来的？
Cache架构¶
cache一致性协议MESI：前面讲了，跳过。
内存屏障规则¶
memory barrier的语义在不同CPU上是不同的，因此，想要实现一个可移植的memory barrier的代码需要对形形色色的CPU上的memory barrier进行总结。幸运的是，无论哪一种cpu都遵守下面的规则：
[1]、CPU内存序：从CPU自己的视角看，它自己的memory order是服从program order的 [2]、全局存储顺序：从包含所有cpu的sharebility domain的角度看，所有cpu对一个共享变量的访问应该服从若干个全局存储顺序 [3]、成对使用：memory barrier需要成对使用 [4]、互斥原语：memory barrier的操作是构建互斥锁原语的基石
大致实现¶
- 语义上，内存屏障之前的所有写操作都要写入内存；内存屏障之后的读操作都可以获得同步屏障之前的写操作的结果。 因此，对于敏感的程序块，写操作之后、读操作之前可以插入内存屏障。
memory barrier内存屏障类型¶
显示内存屏障：全屏障，全功能内存屏障(General memory barrier)，然而全功能的内存屏障对性能的杀伤较大 隐式内存屏障: 操作可以隐含memory barrier的功能，主要有两种类型的操作： - 写屏障：一是加锁操作，确保之前的写入操作在其写入操作之后完成，防止写入操作的重排序 - 释放锁的操作。
五 无锁队列¶
- 队列和栈容器的难点不同，push()和pop()访问不同部分
- 如果某线程在队列一端做出改动，另一线程访问队列另一端。代码就要保证前面的改动能正确的被后文所见。
对比普通的链表队列实现，无锁实现复杂了很多，多出了很多独有的特征操作：
1. C++11 标准的原子性操作： load、store、compare_exchange_weak、compare_exchange_strong
2. 一个无限循环： while ( true ) { ... }
3. 局部变量的安全性(guards)：t = guard.protect( m_pTail, node_to_value() );
4. 补偿策略(functor bkoff)：这不是必须的，但可以在连接很多的情况下缓解处理器的压力，尤其是多个线程逐个地调用队列时。
5. helping方法：本例中，dequeue中帮助enqueue将m_pTail设置正确。
// It is needed to help enqueue
m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release,
memory_model::memory_order_relaxed );
6. 标准原子操作中使用的内存模型(memory model)，也就是内存栅栏(屏障)：memory_order_release、memory_order_acquire等
单进单出队列（解决读写问题）¶
见LockFree.SinglePushPop - tail指针存储操作7和其载入操作1同步。 - 在运行push的线程上，原有的尾节点中的data指针先完成存储操作5，然后tail才作为指针存入新值7。 - 在运行pop()操作的线程上，tail先完成载入1，原data指针才执行加载操作2. - 因此，本质上7先行于2。即读前必定写入 但是，多线程并发调用push和pop就会出问题。
如果两线程同时调用push，就会分别构造一个新的空结点分配内存3,并同时从尾部指针读取相同的值4。针对同一个尾节点更新数据，却各自把data和next指针设置为不同的值5和6。此为数据竞争。
多线程Push问题¶
理想实现：5和6变为原子版。即CAS比较--交换操作。
- 如果shared_ptr是无锁实现，那就万事大吉。可惜多个线程使用同一个shared_ptr并非线程安全的，需要采用其他方法
- 可行的方法是令pop返回unique_ptr（可以支持读改写）指针，并在队列中存储指向数据的普通指针。
- 可以让代码得以按atomic