C++ 原子操作与无锁编程

C++ 原子操作与无锁编程

一 原子操作？

     原子(atomic)本意是 不能被进一步分割的最小粒子 ,而原子操作(atomic operation)意为”不可被中断

的一个或一系列操作”

并发系统要保证数据的有序性，需要对数据进行有序访问，保持数据的有序访问有两种方式：锁

和原子操作。锁相对于原子操作更容易理解，不容易错误，缺点是锁会造成线程切换，耗时会比较

多，在一些极端场景，如高频交易，线程切换所产生的耗时是不能忍受的.所以，在高频交易场景都会

优先考虑原子操作。

二 如何做到原子操作

(1) 使用总线锁保证原子性

如果多个处理器同时对共享变量进行读写操作,那么共享变量就会被多个处理器同时进行操作,这样读写操作就不是原子的,操作完之后共享变量的值会和期望的不一致.

所谓总线锁就是使用处理器提供的一个LOCK#信号,当一个处理器在总线上输出次信号时,其他处理器的请求将被阻塞住,那么该处理器可以独占共享内存.

(2) 使用缓存锁保证原子性

通过缓存锁定保证原子性。在同一时刻我们只需保证对某个内存地址的操作是原子性即可，但总线锁定把CPU和内存之间通信锁住了，这使得锁定期间，其他处理器不能操作其他内存地址的数据，所以总线锁定的开销比较大。

所谓“缓存锁定”就是如果缓存在处理器缓存行中内存区域在LOCK操作期间被锁定，当它执行锁操作回写内存时，处理器不在总线上声言LOCK＃信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时会起缓存行无效。

三 缓存一致性

 

 

一个变量（一个内存位置）其实可以被多个Cache所共享。那么，当我们需要修改这个变量的时候，Cache要如何保持一致呢？

理想情况下，原子地修改多个Cache，但多个CPU之间往往通过总线进行通信，不可能同时修改多个；所以其实要制造一种假象，看起来是原子地修改多个Cache，也就是让Cache看起来是强一致的

四 volatile

volatile在C/C++中的作用：

(1) 告诉编译器不要将定义的变量优化掉；

(2) 告诉编译器总是从缓存取被修饰的变量的值，而不是寄存器取值。

说明：

1. 与平台无关的多线程程序，volatile几乎无用（Java和C#中的volatile除外）；

1. volatile不保证原子性（一般需使用CPU提供的LOCK指令）；

1. volatile不保证执行顺序；

1. volatile不提供内存屏障（Memory Barrier）和内存栅栏（Memory Fence）；

1. 多核环境中内存的可见性和CPU执行顺序不能通过volatile来保障，而是依赖于CPU内存屏障

五 锁

   互斥锁

1. 在访问共享资源后临界区域前，对互斥锁进行加锁；

2. 在访问完成后释放互斥锁导上的锁。在访问完成后释放互斥锁导上的锁；

3. 对互斥锁进行加锁后，任何其他试图再次对互斥锁加锁的线程将会被阻塞，直到锁被释放。对互斥锁进行加锁后，任何其他试图再次对互斥锁加锁的线程将会被阻塞，直到锁被释放。

C 语言：

 

C++11：

C++11中新增了，它是C++标准程序库中的一个头文件，定义了C++11标准中的一些互斥访问的类与方法等。其中std::mutex就是lock、unlock。std::lock_guard与std::mutex配合使用，把锁放到lock_guard中时，mutex自动上锁，lock_guard析构时，同时把mutex解锁。mutex又称互斥量。

 C++11标准库定义了4个互斥类：

 (1)、std::mutex：该类表示普通的互斥锁, 不能递归使用。

 (2)、std::timed_mutex：该类表示定时互斥锁，不能递归使用。std::time_mutex比std::mutex多了两个成员函数：

 A、try_lock_for()：函数参数表示一个时间范围，在这一段时间范围之内线程如果没有获得锁则保持阻塞；如果在此期间其他线程释放了锁，则该线程可获得该互斥锁；如果超时(指定时间范围内没有获得锁)，则函数调用返回false。

 B、try_lock_until()：函数参数表示一个时刻，在这一时刻之前线程如果没有获得锁则保持阻塞；如果在此时刻前其他线程释放了锁，则该线程可获得该互斥锁；如果超过指定时刻没有获得锁，则函数调用返回false。

 (3)、std::recursive_mutex：该类表示递归互斥锁。递归互斥锁可以被同一个线程多次加锁，以获得对互斥锁对象的多层所有权。例如，同一个线程多个函数访问临界区时都可以各自加锁，执行后各自解锁。std::recursive_mutex释放互斥量时需要调用与该锁层次深度相同次数的unlock()，即lock()次数和unlock()次数相同。可见，线程申请递归互斥锁时，如果该递归互斥锁已经被当前调用线程锁住，则不会产生死锁。此外，std::recursive_mutex的功能与 std::mutex大致相同。

 (4)、std::recursive_timed_mutex：带定时的递归互斥锁。

读写锁

 读写锁与互斥量类似，不过读写锁允许更改的并行性，也叫共享互斥锁。互斥量要么是锁住状态，要么就是不加锁状态，而且一次只有一个线程可以对其加锁。读写锁可以有3种状态：读模式下加锁状态、写模式加锁状态、不加锁状态。

 一次只有一个线程可以占有写模式的读写锁，但是多个线程可以同时占有读模式的读写锁（允许多个线程读但只允许一个线程写）。

【读写锁的特点】：

如果有其它线程读数据，则允许其它线程执行读操作，但不允许写操作；

如果有其它线程写数据，则其它线程都不允许读、写操作。

【读写锁的规则】：

如果某线程申请了读锁，其它线程可以再申请读锁，但不能申请写锁；

如果某线程申请了写锁，其它线程不能申请读锁，也不能申请写锁。

读写锁适合于对数据结构的读次数比写次数多得多的情况。

 

自旋锁

 自旋锁与互斥量功能一样，唯一一点不同的就是互斥量阻塞后休眠让出cpu，而自旋锁阻塞后不会让出cpu，会一直忙等待，直到得到锁。

 自旋锁在用户态使用的比较少，在内核使用的比较多！自旋锁的使用场景：锁的持有时间比较短，或者说小于2次上下文切换的时间。

 自旋锁在用户态的函数接口和互斥量一样，把pthread_mutex_xxx()中mutex换成spin，如：pthread_spin_init()。

信号量

 信号量广泛用于进程或线程间的同步和互斥，信号量本质上是一个非负的整数计数器，它被用来控制对公共资源的访问。

 编程时可根据操作信号量值的结果判断是否对公共资源具有访问的权限，当信号量值大于 0 时，则可以访问，否则将阻塞。PV 原语是对信号量的操作，一次 P 操作使信号量减１，一次 V 操作使信号量加１。

六 Cpu 乱序执行

 

单例模式：

方式一：

方案二：

七 C++11 原子操作

定义

C++11:std::atomic - cppreference.com

 

 

load

 

memory_order 乱序执行&指令重排

compare_exchange_strong & compare_exchange_weak

compare_exchange_weak和compare_exchange_strong则是著名的CAS（compare and set）。参数会要求在这里传入期待的数值和新的数值。它们对比变量的值和期待的值是否一致，如果是，则替换为用户指定的一个新的数值。如果不是，则将变量的值和期待的值交换。

compare_exchange_strong：atomic库中的一个函数，入参是3个，expect，desire，memoryorder，意思是如果当前的变

量this的值==expect值，则将this值改为desire，并返回true，否则，返回false，不进行修改，即进行一个读的操作。通常用于例如线程B等待线程A执行完毕，或者执行到某个步骤。此时线程B可以进行while等待，线程A在执行到对应步骤，将对应的原子变量置为expect值即可。类似于“接力运动”。这里由于会进行读写操作，所以，memory order一般是acq rel，而A线程由于要保证都执行完毕，执行顺序没有关系，所以一般是Release的memory order。

bool compare_exchange_weak( T& expected, T desired,

               std::memory_order order =

                 std::memory_order_seq_cst ) volatile noexcept;

bool compare_exchange_strong( T& expected, T desired,

                std::memory_order order =

                  std::memory_order_seq_cst ) noexcept;

八 无锁编程---实现一个栈