C++11如何实现无锁队列

无锁操作的本质依赖的原子操作，C++11提供了atomic的原子操作支持

atomic

compare_exchange_weak / compare_exchange_strong
当前值与期望值相等时，修改当前值为设定值，返回true
当前值与期望值不等时，将期望值修改为当前值，返回false

memory_order枚举值

C++11如何实现无锁队列

				?

									template<typename T>

									class lock_free_stack

									{

									private:

									    struct node

									    {

									        T data;

									        node* next;

									        node(T const& data_):

									        data(data_)

									        {

									        }

									    };

									    std::atomic<node*> head;

									public:

									    void push(T const& data)

									    {

									        node* const new_node=new node(data);

									        new_node->next=head.load();  

									        /*

									        ** 当前值.compare_exchange_weak(期望值, 设置值)

									        ** 单线程的情况：

									        ** 第一次执行while循环：

									        ** 此时当前值与期望值相等，修改当前值为设定值 head = new_node，返回true

									        ** 多线程的情况：

									        ** 第一次执行循环体的时候：

									        ** compare_exchange_weak如果失败, 返回false, 证明有其他线程更新了栈顶head，

									        ** 当前值与期望值不等时，将期望值修改为当前值, 即new_node->next等于新的栈顶head,

									        ** 被其他线程更新的新栈顶值会被更新到new_node->next中，

									        ** 因此循环可以直接再次尝试压栈而无需由程序员更新new_node->next。

									        ** 然后第二次执行循环体：

									        ** 此时 head == new_node->next, 所以 head = new_node.

									        ** 如果这是仍有其他线程干扰，则仍为循环更新new_node->next

									        */

									        while(!head.compare_exchange_weak(new_node->next,new_node));

									    }

									};

CAS原子操作

CAS即Compare and Swap，是所有CPU指令都支持CAS的原子操作（X86中CMPXCHG汇编指令），用于实现实现各种无锁（lock free）数据结构。
CAS用于检查一个内存位置是否包含预期值，如果包含，则把新值复赋值到内存位置。成功返回true，失败返回false。

示例代码如下：

				?

									bool compare_and_swap ( int *memory_location, int expected_value, int new_value)

									{

									    if (*memory_location == expected_value)

									    {

									        *memory_location = new_value;

									        return true;

									    }

									    return false;

									}