原子操作 CAS 与锁实现

原子操作 CAS 与锁实现文章目录原子操作 CAS 与锁实现1. CPU 缓存架构与缓存一致性1.1 为什么需要 CPU 缓存1.2 写回策略与缓存不一致问题1.3 缓存一致性协议MESI 与总线嗅探2. 原子操作不可分割的执行单元2.1 什么是原子操作2.2 为什么需要原子操作2.3 硬件如何支持原子操作3. Compare-And-SwapCAS原理与应用3.1 CAS 定义3.2 C 中的 CAS 接口3.3 CAS 的 ABA 问题及解决4. 内存序从指令重排到可见性4.1 为什么会有内存序问题4.2 内存序解决什么问题4.3 C 内存模型与六种内存序5. 锁的实现从自旋锁到互斥锁5.1 自旋锁Spinlock5.2 互斥锁Mutex5.3 锁的代价与无锁编程5.4 自旋锁和互斤锁的区别6. 案例手撕线程安全的 shared_ptr关键点解析7. 总结在多线程编程中数据竞争和同步问题是开发者必须面对的挑战。为了解决这些问题我们需要深入理解硬件层面的缓存架构、原子操作、内存序以及锁的实现原理。本文将从底层硬件开始逐步剖析原子操作 CASCompare-And-Swap的工作机制并通过实现一个线程安全的shared_ptr来展示原子操作的实际应用。1. CPU 缓存架构与缓存一致性1.1 为什么需要 CPU 缓存CPU 的运算速度远快于内存的访问速度内存访问延迟通常是几十纳秒而 CPU 周期仅零点几纳秒。为了弥合这一差距现代 CPU 引入了多级缓存L1/L2/L3。CPU 优先从缓存中读取数据只有当缓存缺失时才访问内存从而大幅提升性能。1.2 写回策略与缓存不一致问题当 CPU 修改缓存中的数据时并不会立即写回内存而是采用写回Write-back策略仅当缓存行被替换或显式刷新时才写回内存。这种策略提高了性能但也带来了缓存不一致问题——多个 CPU 核心各自持有同一内存地址的副本一个核心的修改可能对其他核心不可见。1.3 缓存一致性协议MESI 与总线嗅探为了解决缓存不一致硬件实现了缓存一致性协议最常见的是MESI 协议。每个缓存行被标记为四种状态之一Modified数据已被修改与内存不一致且仅存在于当前缓存中。Exclusive数据与内存一致且仅存在于当前缓存中。Shared数据与内存一致且可能存在于多个缓存中。Invalid数据无效不可使用。总线嗅探机制Bus Snooping是 MESI 的核心每个核心监听总线上的事务当检测到其他核心读取或写入某个缓存行时根据当前状态进行响应。例如当核心 A 修改了一个处于 Shared 状态的缓存行它会通过总线发出“读并独占”的信号其他核心的对应缓存行被标记为 Invalid从而保证数据一致性。这种机制实现了事务串行化并通过状态机降低了总线带宽的压力。2. 原子操作不可分割的执行单元2.1 什么是原子操作原子操作Atomic Operation是指一个或多个指令的执行过程不可中断要么全部完成要么全部不执行且中间状态对其他线程不可见。常见的原子操作包括读-改-写RMW操作例如、CAS等。2.2 为什么需要原子操作在多线程环境中多个线程同时访问同一变量可能导致数据竞争Data Race。例如两个线程同时对count执行count在汇编层面可能对应多条指令读取、加1、写回线程切换可能破坏操作的完整性导致最终结果错误。原子操作保证了这些指令作为一个整体执行避免了数据竞争。2.3 硬件如何支持原子操作CPU 提供了特定的指令来实现原子性例如 x86 的LOCK前缀可以锁定总线或缓存行确保多处理器环境中指令的原子执行。现代 CPU 还支持如cmpxchgCompare-And-Swap等原子指令。3. Compare-And-SwapCAS原理与应用3.1 CAS 定义CASCompare-And-Swap是一种经典的原子操作它接受三个参数内存地址p、期望值expected、新值desired。操作逻辑如下if(*pexpected){*pdesired;returntrue;}else{returnfalse;}整个过程是原子的不可被其他线程打断。3.2 C 中的 CAS 接口C11 的atomic库提供了compare_exchange_weak和compare_exchange_strong方法std::atomicintvalue(0);intexpected0;intdesired1;boolsuccessvalue.compare_exchange_strong(expected,desired);compare_exchange_strong保证在*p expected时成功更新否则返回false并将expected更新为当前值。compare_exchange_weak可能因虚假失败而返回false某些平台上性能更好通常用于循环中。3.3 CAS 的 ABA 问题及解决ABA 问题是指线程 1 读取变量值为 A随后线程 2 将 A 改为 B 又改回 A此时线程 1 执行 CAS 发现值仍为 A误认为变量未被修改从而导致逻辑错误。常见解决方案使用带版本的原子指针例如std::atomicstd::shared_ptrT或为数据附加一个标记tag每次修改递增标记通过双字 CAS 同时比较值和标记。避免复用地址在无锁数据结构中谨慎设计。4. 内存序从指令重排到可见性4.1 为什么会有内存序问题为了提高性能编译器和 CPU 可能对指令进行重排Reordering只要不改变单线程的语义。但在多线程环境中重排可能导致其他线程看到“奇怪”的执行顺序破坏同步逻辑。此外由于缓存的存在一个线程的修改何时对其他线程可见也是不确定的。4.2 内存序解决什么问题内存序约束了编译器和 CPU 的重排行为并规定了多线程间的可见性。它主要解决两个问题顺序性保证某些操作在另一个操作之前发生happens-before 关系。可见性保证一个线程对共享变量的修改能被其他线程及时看到。4.3 C 内存模型与六种内存序C11 定义了六种内存序std::memory_order从松到严memory_order_relaxed只保证原子性无顺序和可见性保证。用于计数器等不依赖同步的场景。memory_order_consume已弃用不建议使用针对数据依赖的优化。memory_order_acquire用于读操作保证之后的所有读写操作不会被重排到 acquire 之前且能看到之前 release 操作写入的数据。memory_order_release用于写操作保证之前的所有读写操作不会被重排到 release 之后且对 acquire 操作可见。memory_order_acq_rel同时具有 acquire 和 release 语义用于读-改-写操作。memory_order_seq_cst最强约束全局顺序一致所有线程看到相同的操作顺序但性能开销最大。典型的使用模式是Release-Acquire 屏障一个线程用 release 写入另一个线程用 acquire 读取从而建立 happens-before 关系保证数据同步。5. 锁的实现从自旋锁到互斥锁5.1 自旋锁Spinlock自旋锁是最简单的锁它通过忙等待循环检查实现。使用 CAS 可以轻松实现classSpinlock{std::atomicboolflag{false};public:voidlock(){while(flag.exchange(true,std::memory_order_acquire)){// 自旋等待}}voidunlock(){flag.store(false,std::memory_order_release);}};这里使用exchange原子地设置flag并返回旧值若旧值为true表示锁已被占用循环继续。解锁时用store释放锁配合 acquire/release 语义确保同步。5.2 互斥锁Mutex操作系统提供的互斥锁如std::mutex通常比自旋锁更复杂当锁被占用时线程会被挂起阻塞避免浪费 CPU。其底层实现依赖于系统调用如 Linux 的futex和原子操作。一个简化的futex互斥锁可描述为使用原子变量state表示锁状态0 未锁1 加锁2 有等待者。lock()尝试用 CAS 将 0 改为 1若成功则获得锁否则原子地增加等待者计数并调用futex_wait阻塞。unlock()将状态改回 0若有等待者则调用futex_wake唤醒。虽然实现细节复杂但其核心仍然是基于原子操作和 CAS。5.3 锁的代价与无锁编程锁会导致线程阻塞、上下文切换还可能引发死锁、优先级反转等问题。因此在高性能场景下人们倾向于使用无锁数据结构Lock-Free它们直接利用原子操作如 CAS来避免锁。但无锁编程难度更高需要仔细处理 ABA 问题和内存序。5.4 自旋锁和互斤锁的区别1.等待策略自旋锁用户态忙等待互斥锁内核态休眠2.上下文切换自选锁无上下文切换互斥锁有3.场景自旋锁适用于持锁时间短互斥锁适用于持锁时间长6. 案例手撕线程安全的shared_ptrstd::shared_ptr的核心是引用计数它必须保证多线程环境下计数的增减是安全的。通常引用计数用std::atomicsize_t实现并且需要注意内存序的选择。下面我们手写一个简化的Shared_ptr并分析其中原子操作的使用。#pragmaonce#includeatomictemplatetypenameTclassShared_ptr{public:Shared_ptr():ptr_(nullptr),ref_count_(nullptr){}explicitShared_ptr(T*ptr):ptr_(ptr),ref_count_(ptr?newstd::atomicsize_t(1):nullptr){}// 拷贝构造增加引用计数Shared_ptr(constShared_ptrTother):ptr_(other.ptr_),ref_count_(other.ref_count_){if(ref_count_){// 使用 relaxed 即可因为不需要同步其他内存ref_count_-fetch_add(1,std::memory_order_relaxed);}}// 拷贝赋值Shared_ptrToperator(constShared_ptrTother){if(this!other){release();// 释放旧资源ptr_other.ptr_;ref_count_other.ref_count_;if(ref_count_){ref_count_-fetch_add(1,std::memory_order_relaxed);}}return*this;}// 移动构造直接转移所有权Shared_ptr(Shared_ptrTother)noexcept:ptr_(other.ptr_),ref_count_(other.ref_count_){other.ptr_nullptr;other.ref_count_nullptr;}// 移动赋值Shared_ptrToperator(Shared_ptrTother)noexcept{if(this!other){release();ptr_other.ptr_;ref_count_other.ref_count_;other.ptr_nullptr;other.ref_count_nullptr;}return*this;}~Shared_ptr(){release();}Toperator*()const{return*ptr_;}T*operator-()const{returnptr_;}T*get()const{returnptr_;}size_tuse_count()const{returnref_count_?ref_count_-load(std::memory_order_acquire):0;}voidreset(T*ptrnullptr){if(ptr!ptr_){release();ptr_ptr;ref_count_ptr?newstd::atomicsize_t(1):nullptr;}}private:voidrelease(){if(ref_count_){// 减 1并检查是否变为 0if(ref_count_-fetch_sub(1,std::memory_order_acq_rel)1){deleteptr_;deleteref_count_;}}}T*ptr_;std::atomicsize_t*ref_count_;// 指向堆上的原子计数器};关键点解析拷贝构造函数使用memory_order_relaxed增加计数。因为只需要保证计数本身原子递增不涉及其他内存的同步。即使线程 A 在递增后立即释放原指针由于ref_count_是指向共享内存的指针其他线程看到的是同一计数器所以relaxed足够安全。release()函数使用fetch_sub(1, memory_order_acq_rel)。为什么需要acq_rel获取acquire语义保证在fetch_sub之前的所有操作如对ptr_的访问不会被重排到fetch_sub之后确保递减时对象仍然有效。释放release语义保证递减操作本身对其他线程可见并且如果当前线程是最后一个返回 1它将负责删除资源。acq_rel确保了在这之前对ptr_的读写对其他线程如果有是可见的同时后续删除操作不会被提前。如果使用relaxed可能出现一个线程刚刚把计数减到 0但另一个线程还没来得及看到新值就同时尝试减少导致重复释放。所以必须用更强的内存序保证正确性。use_count()使用memory_order_acquire因为读取计数需要看到其他线程对计数的修改即前面 release 写的结果。acquire确保读取到的是最新值。为什么析构函数不需要显式内存序因为release()内部已经处理了内存序。7. 总结原子操作和内存序是多线程编程的基石本文从 CPU 缓存架构出发解释了缓存一致性问题如何催生原子操作然后深入 CAS 的原理和 ABA 问题的解决接着讨论了内存序的必要性和 C 中的内存序选项最后通过自旋锁和shared_ptr的实现展示了原子操作的实际应用。https://github.com/0voice