我想在没有摇滚队列的情况下写这个博客之前让以下几点出名。 第一，本文侧重于如何实现锁定安全，而不详细介绍底层的CAS机制。 其理由是第二个。 不知道看博客的你是否在搜索框中输入过关键字“无密钥队列”。 点击后你会惊讶地发现每本书都是那么相似。 你不明白写博客的a是抄b，b是抄c只是为了欺骗访问者吗？
这是酷壳zjdys老师原创的博客，老师的博客深刻说明了自由摇滚队列的原理。 只是，缺少最后一个代码的实现。 既然有hcdls级别的说明，我们就完成那个部分没有安装的部分。
尚不了解锁定救援基础CAS机制的学生可以看到jjdqz和程序员疏忽草莓这两篇文章：什么是锁定救援的实现和CAS机制
锁定救援的基本原理其实CAS机制并不容易理解。 你只需要理解CAS机制中的三个关键词。 分别为原始值、期望值、更新值(名词)。 这三个值加起来用一句话总结，如果原来的值和期待值相同，就把原来的值修正为更新值
从图中可以看出，CAS机制并不容易理解。 现在，让我们来看看拯救摇滚的思想吧。
无锁定队列的具体实现在此，必须使用在C 11中引入的atomic类。 这个类意味着原子的操作，函数接口很容易使用。 首先，看一下拯救锁定的实现思想，然后结合代码进行理解，会更容易理解
无锁定队列的基本结构
操作每个指针时必须是原子。 也就是说，指针的方向是变化还是不变化，不会产生第三个结果。 每个队列都需要一个伪节点，以便更好地确定队列是否为空。
# includeatomicusingnamespacestd； templateclasstclasslockfreequeue { struct node { t _ value； atomicNode* _next； 节点(const TV ) :_value(v ) v )，_ next (nullptr ) }； 公共： lockfreequeue (({ _ head=_ tail=new node ) t ) )； (} ~LockFreeQueue () ) { Node* cur=_head； wile(cur ) { Node* next=cur-_next； 删除Cur； cur=next； } } private :自动节点* _ head； 自动节点* _ tail； (； 未锁定队列如何进入队列？
下面介绍两种类型的自动函数操作
//当前atomic对象指向的值tload (memory _ ordersync=memory _ order _ seq _ CST ) const volatile noexcept； //如果内存中的值和参数相同，则替换为参数2，trueboolcompare _ exchange _ weak (texpected，T val，memory _ ordersync=memory 现在，让我们看看在未锁定队列中插入代码块。
voidenqueue(consttx ) node*newnode=newnode ) x； //要插入的新值Node* oldtail=nullptr； //旧尾节点Node* nullnode=nullptr； //空节点do{oldtail=_tail.load (； 在load中检索当前_tail节点的值} //如果当前tail节点的下一个节点为空，即等于参数1，则参数2 while (old tail-_ next.com pare _ exchange _ change ) //因为当前真正的尾节点是newnode，所以将_tail节点设置为newnode _ tail.com pare _ exchange _ weak (old tail，new node )； }其中，请理解while条件下的CAS语句用于插入此新节点，而最后一个语句用于修改控制整个队列的_tail指针，使其指向新的末尾
未锁定队列如何退出队列？
离开队伍比插入容易。 别说得那么没用，直接看看队伍是怎么实现的吧。
T DeQueue () {Node* oldhead=_head.load )； //取出当前头节点，即虚拟节点T ret； do{Node* next=oldhead-_next； //检索头部节点的下一个节点。 该节点包含我们想要的值if(next==nullptr ) {return T )； }else{ret=next-_value； //取值}//将
头节点(哑节点)修改为下一个节点while(_head.compare_exchange_weak(oldhead,oldhead->_next) != true);delete oldhead;return ret;}判断队列是否为空和其他问题
判断是否为空，直接判断头部和尾部是否指向同一个节点
bool Empty(){return _head.load() == _tail.load();}因为我们的无锁队列是不能够被拷贝的，所以我们使用delete关键字直接将拷贝构造函数删除掉
LockFreeQueue(const LockFreeQueue<T>&) = delete;到这里，我们的无锁队列就实现完成了，之所以这么简单，还是因为C++库为我们提供了atomic这个类。无锁队列这里重在理解他的如何使用CAS的思想去更新节点的。
无锁队列全部源码和测试经过笔者多次测试，发现无锁队列总体来说还是不错的，比加锁的队列能快一倍左右(第一行为无锁队列)，这是插入10w数据的一次的结果，基本在这两个数字中波动。但是无锁队列对于线程数量的选择很关键。随着线程数增大，最后会比加锁队列更差，原因不难理解，CAS机制本身还是太消耗CPU资源了。
#pragma once#include<atomic>#include<iostream>#include<queue>#include<thread>#include<mutex>#include<condition_variable>using namespace std;template<class T>class LockFreeQueue{struct Node{T _value;std::atomic<Node*> _next;Node(const T& x): _value(x), _next(nullptr){}};public:LockFreeQueue(){_head = _tail = new Node(T());}LockFreeQueue(const LockFreeQueue<T>&) = delete;~LockFreeQueue(){Node* cur = _head;while (cur){Node* next = cur->_next;delete cur;cur = next;}}void Enqueue(const T& x){Node* newnode = new Node(x);Node* oldtail = nullptr;Node* nullnode = nullptr;do{oldtail = _tail.load();} while (oldtail->_next.compare_exchange_weak(nullnode, newnode) != true);_tail.compare_exchange_weak(oldtail, newnode);}T Dequeue(){Node* oldhead = _head.load();T headvalue;do{Node* next = oldhead->_next;if (next == nullptr){return T();}else{headvalue = next->_value;}} while (_head.compare_exchange_weak(oldhead, oldhead->_next) != true);delete oldhead;return headvalue;}bool Empty(){return _head.load() == _tail.load();}private:std::atomic<Node*> _head;std::atomic<Node*> _tail;};mutex mutx;int main(){LockFreeQueue<int> lq;queue<int> nq;atomic<size_t> n = 100000;//测试无锁队列{size_t costtime = 0;vector<thread> threads;for (size_t i = 0; i < 3; ++i){threads.push_back(thread([&](){size_t begin = 0, end = 0;begin = clock();for (size_t j = 0; j < n; ++j){lq.Enqueue(j);}end = clock();costtime += (end - begin);}));}for (auto& e : threads){e.join();}cout << costtime << endl;}//测试有锁队列{size_t costtime = 0;vector<thread> threads;for (size_t i = 0; i < 3; ++i){threads.push_back(thread([&](){size_t begin = 0, end = 0;begin = clock();for (size_t j = 0; j < n; ++j){mutx.lock();nq.push(j);mutx.unlock();}end = clock();costtime += (end - begin);}));}for (auto& e : threads){e.join();}cout << costtime << endl;}return 0;}