无锁堆栈 – 这是正确使用c 11轻松原子吗？可以证明吗

概述我写了一个容器,用于需要在线程之间同步的一个非常简单的数据.我想要最好的表现.我不想使用锁. 我想用“放松”的原子.部分地是为了那一点额外的oomph,并且部分地真正了解他们. 我一直在这方面做了很多工作,而我在这个代码中通过了我所有的测试.这不是“证明”,所以我想知道有没有什么我失踪,或任何其他方法我可以测试这个？ 这是我的前提： > Node必须正确地按下并d出,并且Stack永远不会被无效. 我写了一个容器,用于需要在线程之间同步的一个非常简单的数据.我想要最好的表现.我不想使用锁.

我想用“放松”的原子.部分地是为了那一点额外的oomph,并且部分地真正了解他们.

我一直在这方面做了很多工作,而我在这个代码中通过了我所有的测试.这不是“证明”,所以我想知道有没有什么我失踪,或任何其他方法我可以测试这个？

这是我的前提：

> Node必须正确地按下并d出,并且Stack永远不会被无效.
>我认为记忆中的 *** 作顺序在一个重要的地方是重要的：

>在compare_exchange *** 作本身之间.这是保证,即使轻松的原子.

>通过向指针添加标识号可以解决“ABA”问题.在32位系统上,这需要一个双字compare_exchange,在64位系统上,指针的未使用的16位用ID号填充.
>因此：堆栈将始终处于有效状态. (对？)

这是我在想什么“通常”,我们对我们正在阅读的代码的理解方式是查看其编写顺序.内存可以读取或写入“无序”,但不能使程序的正确性无效.

在多线程环境中发生变化.这就是记忆围栏 – 所以我们仍然可以看看代码,并且能够说明它的工作原理.

所以如果一切都可以在这里全部乱序,我在做什么放松原子？是不是有点太远了？

我不这么认为,这就是为什么我在这里要求帮助.

compare_exchange *** 作本身保证了彼此的顺序恒定.

读取或写入原子的唯一其他时间是在compare_exchange之前获取头的初始值.它被设置为变量初始化的一部分.据我所知,无论这项行动是否带来“适当”的价值,这是无关紧要的.

当前代码：

struct node{    node *n_;#if PROCESSOR_BITS == 64    inline constexpr node() : n_{ nullptr }                 { }    inline constexpr node(node* n) : n_{ n }                { }    inline voID tag(const stack_tag_t t)                    { reinterpret_cast<stack_tag_t*>(this)[3] = t; }    inline stack_tag_t read_tag()                           { return reinterpret_cast<stack_tag_t*>(this)[3]; }    inline voID clear_pointer()                             { tag(0); }#elif PROCESSOR_BITS == 32    stack_tag_t t_;    inline constexpr node() : n_{ nullptr },t_{ 0 }        { }    inline constexpr node(node* n) : n_{ n },t_{ 0 }       { }    inline voID tag(const stack_tag_t t)                    { t_ = t; }    inline stack_tag_t read_tag()                           { return t_; }    inline voID clear_pointer()                             { }#endif    inline voID set(node* n,const stack_tag_t t)           { n_ = n; tag(t); }};using std::memory_order_relaxed;class stack{public:    constexpr stack() : head_{}{}    voID push(node* n)    {        node next{n},head{head_.load(memory_order_relaxed)};        do        {            n->n_ = head.n_;            next.tag(head.read_tag() + 1);        } while (!head_.compare_exchange_weak(head,next,memory_order_relaxed,memory_order_relaxed));    }    bool pop(node*& n)    {        node clean,head{head_.load(memory_order_relaxed)};        do        {            clean.set(head.n_,0);            if (!clean.n_)                return false;            next.set(clean.n_->n_,head.read_tag() + 1);        } while (!head_.compare_exchange_weak(head,memory_order_relaxed));        n = clean.n_;        return true;    }protected:    std::atomic<node> head_;};

与其他人相比,这个问题有什么不同？轻松的原子他们对这个问题有很大的影响.

所以你怎么看？有什么我错过的吗？

解决方法 push已损坏,因为在compareAndSwap失败后您不更新node-> _next.当下一个compareAndSwap尝试成功时,您可能使用node-> setNext原来存储的节点从堆栈顶部被另一个线程d出.因此,一些线程认为它已经从堆栈d出了一个节点,但是这个线程已经将它放回到堆栈中.它应该是：

voID push(Node* node) noexcept{    Node* n = _head.next();    do {        node->setNext(n);    } while (!_head.compareAndSwap(n,node));}

此外,由于next和setNext使用memory_order_relaxed,所以不能保证_head_.next()在这里返回最近推送的节点.可能从堆栈顶部泄漏节点. pop中也明显存在同样的问题：_head.next()可能会返回一个以前但不再位于堆栈顶部的节点.如果返回的值为nullptr,则当堆栈实际上不为空时,您可能无法d出.

如果两个线程同时尝试从堆栈中d出最后一个节点,则pop也可以具有未定义的行为.它们都为_head.next()看到相同的值,一个线程成功完成pop.另一个线程进入while循环 – 由于观察到的节点指针不是nullptr – 但是compareAndSwap循环很快将其更新为nullptr,因为堆栈现在为空.在循环的下一个迭代中,该nullptr被去除以获取其_next指针,并且引起了很多的欢呼.

流行音乐也显然遭受了ABA的痛苦.两个线程可以看到堆叠顶部的同一个节点.说一个线程到达评估_next指针然后阻止的点.另一个线程成功地d出节点,推送5个新节点,然后在另一个线程唤醒之前再次推送该原始节点.该另一个线程的compareAndSwap将成功 – 堆栈顶端节点是相同的 – 但将旧的_next值存储在_head而不是新的.另一个线程推送的五个节点都被泄露.对于memory_order_seq_cst也是如此.

总结

以上是内存溢出为你收集整理的无锁堆栈 – 这是正确使用c 11轻松原子吗？可以证明吗全部内容，希望文章能够帮你解决无锁堆栈 – 这是正确使用c 11轻松原子吗？可以证明吗所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。