Table of Contents
boost无锁队列
要求里面存放的元素具有trivial destructor，因为里面的元素有可能被删除两次。trivial destructor的解释：https://en.cppreference.com/w/cpp/language/destructor#:~:text=A%20trivial%20destructor%20is%20a,POD%20types)%20are%20trivially%20destructible.
也就是说元素的析构函数是nop(注意nop和默认析构函数的差别，nop是说什么都不做)。
concurrentqueue
https://github.com/cameron314/concurrentqueue
基于c++11的无锁队列，但是只保证来自于同一个producer的元素在pop时是保持原相对顺序的，不保证来自于不同producer的元素在pop时保持push的顺序(其实也基本合理)。支持bulk push和pop，在pop时如果需要阻塞式pop，那么就使用blockingconcurrentqueue版本。
单producer单consumer的无锁队列
https://www.drdobbs.com/parallel/lock-free-queues/208801974?pgno=1
一种无锁队列的设计，核心是只在produce函数里修改队列，consume函数里并没有真正的修改队列，只是读取元素。但是这个实现有一些限制：
- 只能单producer单consumer；
- iterator的操作需要保证原子性或者换成其他能保证原子性且作用和iterator相当的类型；
- 关键变量的修改可见性要自己保证，比如使用volatile之类的关键字；
folly中的实现
wikipedia的介绍
- non-blocking algorithm
一个非阻塞的算法需要满足：一个线程的失败或者挂起不会导致另一个线程的失败或者挂起(failure or suspension)； - wait free
一个wait free的算法需要满足：保证每个线程都能够取得进展(make progress)； - lock free
一个lock free的算法需要满足：保证整个系统能够取得进展； - obstruction free
可以看出这几重概念的”并行”程度：non-blocking < obstruction free < lock free < wait free；
为什么需要非阻塞的算法：
- 有时候我们就是不想挂起线程，比如对于执行实时任务的线程；
- 使用锁可能导致活锁，死锁，优先级反转(priority inversion)，锁的粒度划分等问题；
- 非阻塞算法可以在中断处理程序中使用；
- 非阻塞算法可以提高性能，增加程序并行执行的时间而不是花费时间去执行串行的操作；
这里的non-blocking居然最先是用来描述电信网络的(以前那种需要接线的电话网络)，保证用户每次打电话时，线路总是能够接通．
实现
几乎所有的非阻塞算法依赖于atomic read-modify-write原语，而原子RMW原语中最广为人知的是compare and swap(CAS)．关键区等机制总是基于这些原语RMW操作实现，而如果想实现non-blocking算法，则需要自己编程操作这些底层原语．
已经有很多论文研究了如何实现非阻塞的基础数据结构，这些数据结构可以允许线程之间以异步的方式交换数据：
- stack
- queue
- set
- hash table
疑问：list,tree这些呢？
另外也有一些非阻塞的数据结构足够简单以至于不需要使用特别的原子原语，包括如下：
- 单reader单writer的环形FIFO缓冲区；
- 单writer任意数量reader的RCU；
- 多writer任意数量reader的RCU；
wait-freedom
wait free其实就是每个操作都会有一个执行步数的上限，这个性质对于实时系统非常重要．1980年代人们证明了所有算法都可以实现为wait free，只是wait free的算法可能并不比得上现有的阻塞版本的算法．
- lock-free queue的论文
Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
https://lrita.github.io/2020/04/24/michael-lockfree-queue/ 别人的论文笔记 - wait-free queue的论文
Wait-free queues with multiple enqueuers and dequeuers，这是基于上面lock-free queue实现的wait-free，但是性能比上面的lock-free queue差； - wait-free queue的论文
A method for creating fast wait-free data structures，这改进了２中的wait-free queue，性能和1中的lock free一样好； - wait-free算法的论文
A Practical Wait-Free Simulation for Lock-Free Data Structures，提出了如何基于lock-free的算法生成wait-free的版本；
lock-freedom
obstruction-freedom
一个线程在无干扰(其他线程都挂起/没有竞争)的情况下总是能够在有限步内完成自己的操作．
论文笔记
Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
这篇文章提了两个算法，一个是无锁队列的实现，另外一个是用了两个锁的队列，这两个算法都优于只有一个锁的队列，无锁队列性能最好．在没有CAS支持时，我们可以使用这个有两个锁的队列．
- ABA问题
进行CAS操作，程序会先记录该地址保存的旧值，然后计算出一个新值，再调用CAS指令将该地址的内容和旧值进行比较，如果相同就将新值写到该地址．但实际情况是该地址的值可能被其他线程修改过多次，只是最终又改回了该地址的原值．很多算法不能区分出这种情况，因此就可能在算法逻辑上产生问题．因为CAS比较的对象长度有限，所以很多无锁队列算法没法比较对象，只能比较对象的指针，而由于内存管理机制很多对象分配的地址都会被重用，因此就导致了ABA问题．
参考论文：http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf
教程文章
https://www.infoq.com/news/2014/10/cpp-lock-free-programming/
近期评论