一直在思考如何实现无锁单向链表。老实说,我没有看到很多防弹方法。即使是使用 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);
}
所以,正如我所说,我认为这段代码不正确。但是谁能肯定地说我得出的结论是正确的(我不愿意取消一些效果很好的东西)。如果它真的像我怀疑的那样坏了。有什么简单的解决办法吗?
最佳答案
你是对的。在 C++ 中,函数的参数按任何顺序求值,但您的编译器肯定无法知道 root->next
是序列中的原子操作。
考虑调用 pop()
的两个线程:一个线程计算 root->next
,然后另一个计算 root->next
,并且两者都调用 test_and_set()
。现在您只弹出了一个节点。
关于c++ - test_and_set 线程的这种用法安全吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2900244/