c++ - test_and_set 线程的这种用法安全吗？

Question

一直在思考如何实现无锁单向链表。老实说，我没有看到很多防弹方法。即使是使用 CAS 的更强大的方法最终也会有一定程度的 ABA problem .

所以我开始思考。部分无锁系统难道不会比总是使用锁更好吗？一些操作可以是原子的和无锁的吗？如果我能做到这一点，它应该仍然是线程安全的。

那么，进入正题。我在想一个简单的单向链表。 2 主要操作。 push 和 pop。 push 总是在前面插入。像这样:

void push(int n) {
    T *p = new T;
    p->n = n;
    p->next = root;
    root = p;
}

pop 总是取第一个元素。像这样:

T *pop() {
    T *p = root;
    root = root->next;
    return p;
}

显然，推送非常重要，因此可能不会采用简单的无锁方法。但流行看起来可能是可行的。使用 gcc-intrinsics 我想到了这个:

T *pop() {
    return __sync_lock_test_and_set(&root, root->next);
}

功能等同？是的。无锁？是的。线程安全？ 我不知道。我的直觉 react 是否定的，原因如下。

我担心 test_and_set 的参数之一必须取消引用内存。如果 root 在 root->next 和对 __sync_lock_test_and_set 的调用之间发生变化怎么办。

我想这段代码等同于:

T *pop() {
    T *temp = root->next;
    // are we broken if a push/pop happens here?
    return __sync_lock_test_and_set(&root, temp);
}

所以，正如我所说，我认为这段代码不正确。但是谁能肯定地说我得出的结论是正确的(我不愿意取消一些效果很好的东西)。如果它真的像我怀疑的那样坏了。有什么简单的解决办法吗？

Answer 1

你是对的。在 C++ 中，函数的参数按任何顺序求值，但您的编译器肯定无法知道 root->next 是序列中的原子操作。

考虑调用 pop() 的两个线程:一个线程计算 root->next，然后另一个计算 root->next，并且两者都调用 test_and_set()。现在您只弹出了一个节点。