我想用“放松”的原子.部分地是为了那一点额外的oomph,并且部分地真正了解他们.
我一直在这方面做了很多工作,而我在这个代码中通过了我所有的测试.这不是“证明”,所以我想知道有没有什么我失踪,或任何其他方法我可以测试这个?
这是我的前提:
> Node必须正确地按下并弹出,并且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_; };
与其他人相比,这个问题有什么不同?轻松的原子他们对这个问题有很大的影响.
所以你怎么看?有什么我错过的吗?
解决方法
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,则当堆栈实际上不为空时,您可能无法弹出.
如果两个线程同时尝试从堆栈中弹出最后一个节点,则pop也可以具有未定义的行为.它们都为_head.next()看到相同的值,一个线程成功完成pop.另一个线程进入while循环 – 由于观察到的节点指针不是nullptr – 但是compareAndSwap循环很快将其更新为nullptr,因为堆栈现在为空.在循环的下一个迭代中,该nullptr被去除以获取其_next指针,并且引起了很多的欢呼.
流行音乐也显然遭受了ABA的痛苦.两个线程可以看到堆叠顶部的同一个节点.说一个线程到达评估_next指针然后阻止的点.另一个线程成功地弹出节点,推送5个新节点,然后在另一个线程唤醒之前再次推送该原始节点.该另一个线程的compareAndSwap将成功 – 堆栈顶端节点是相同的 – 但将旧的_next值存储在_head而不是新的.另一个线程推送的五个节点都被泄露.对于memory_order_seq_cst也是如此.