最近尝试了一种新的无锁链表的实现方法，主要思想是：push操作使用原子操作将原来的tail指针保存在线程的局部变量中，然后再修改old tail的next指针；pop操作首先使用原子操作改变head指针指向下一个位置，保证其他线程无法获old head指针，然后再进行删除。原来的实现方法不会保证head指针指向对象的存在。这样，在push取出old tail并修改tail之后，修改old tail的next之前，pop弹出最后一个对象并删除以后就会导致old tail变成空悬指针，这时push修改old tail的next就会导致未定义行为。在pop弹出最后一个以后，虽然old head指向会被删除，但是这时tail是指向head->next的，即使同时其他线程调用pop，也不会在修改old tail时候崩溃；如果链表只有一个元素，但是同时想弹出两个，那么在弹出第2个不会执行，会失败，也不会导致程序崩溃。那么会不会存在pop函数在验证不为空之后又变成空的情况呢？在多个消费者的情况下会出现这个情况，另外多个消费者还会存在old head被删除后在调用compare_exchange时候求head->next而导致解空悬指针。那么多个生产者会不会出现问题呢？目前来看，首先原子更改了tail的指向，那么后面来的线程即使在push的中间状态tail没有被挂到链表末尾，也能正确的识别并写到当前tail的后面。因此理论上是可以接受多个生产者的。即当前实现为MPSC的。

（原理介绍图...后期插入）

具体实现如下：

#ifndef _LOCK_FREE_LIST_HPP_
#define _LOCK_FREE_LIST_HPP_
#include <atomic>template<typename val_t>
class lock_free_list
{
private:struct node{val_t v;node* next;node():v(), next(nullptr){}node(const val_t& v_):v(v_), next(nullptr){}}; std::atomic<node*> head, tail;
public:lock_free_list():head(new node), tail(head.load(std::memory_order_relaxed)){}lock_free_list<val_t>& push_back(const val_t& v){auto pnew = new node(v);node* poldtail = tail.load(std::memory_order_relaxed);while(!tail.compare_exchange_strong(poldtail, pnew, std::memory_order_relaxed, std::memory_order_relaxed));poldtail->next = pnew;return *this;}bool pop_front(val_t& v){if (head.load(std::memory_order_relaxed)->next == nullptr){return false;}node* poldhead = head.load(std::memory_order_relaxed);while(!head.compare_exchange_strong(poldhead, poldhead->next, std::memory_order_relaxed, std::memory_order_relaxed));v = head.load(std::memory_order_relaxed)->v;delete poldhead;return true;}
};#endif