亲宝软件园·资讯

展开

C++11无锁队列 C++11怎样实现无锁队列

fzzjoy 人气:0
想了解C++11怎样实现无锁队列的相关内容吗,fzzjoy在本文为您仔细讲解C++11无锁队列的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++11无锁队列,下面大家一起来学习吧。

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

atomic

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

memory_order枚举值

在这里插入图片描述

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原子操作

示例代码如下:

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;
}

ABA问题

所谓ABA(见维基百科的ABA词条),问题基本是这个样子:

虽然P1以为变量值没有改变,继续执行了,但是这个会引发一些潜在的问题。ABA问题最容易发生在lock free 的算法中的,CAS首当其冲,因为CAS判断的是指针的地址。如果这个地址被重用了呢,问题就很大了。(地址被重用是很经常发生的,一个内存分配后释放了,再分配,很有可能还是原来的地址)

eg:
好比你拿着一个装满钱的手提箱在飞机场,此时过来了一个火辣性感的美女,然后她很暖昧地挑逗着你,并趁你不注意的时候,把用一个一模一样的手提箱和你那装满钱的箱子调了个包,然后就离开了,你看到你的手提箱还在那,于是就提着手提箱去赶飞机去了。

这就是ABA的问题。

Fetch-And-Add (FAA)

一般用来对变量做+1的原子操作

Test-And-Set (TAS)

写值到某个内存位置并传回其旧值

参考文章

C++11:原子交换函数compare_exchange_weak和compare_exchange_strong

加载全部内容

相关教程
猜你喜欢
用户评论