4

我一直在思考如何实现一个无锁单链表。老实说，我没有看到很多防弹的方法来做到这一点。即使是使用的更强大的方法最终也存在CAS一定程度的ABA 问题。

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

所以，直奔问题。我正在考虑一个简单的单链表。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;
}

显然，push 并不简单，简单的无锁方法可能不会发生。但流行看起来可能是可行的。使用 gcc-intrinsics 我想到了这个：

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

功能等同？对。无锁？对。线程安全？我不知道。我的直觉反应是否定的，这就是为什么。

我担心其中一个参数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);
}

所以，就像我说的，我认为这段代码是不正确的。但是任何人都可以肯定地说我得出了正确的结论（我不想注销一些效果很好的东西）。如果它真的像我怀疑的那样坏了。有没有简单的解决方案？

4

3 回答 3

2

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

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

于 2010-05-24T21:11:55.693 回答
1

两件事：（1）test&set的共识数只有2；对于这样一个弱同步原语，只使用读/写内存屏障就足够了，而不会产生专门指令的开销；(2) ABA 问题是一个真正的问题，几乎没有解决方案；但是，对于 CAS（32 位系统上的 cmpxchg8b 和 x86/-64 的 64 位系统上的 cmpxchg16b），寄存器的上部有足够的空间来存储如此大的时间戳，以至于 ABA 在实践中从未出现（即使在相当人为的设置中，它也需要一个线程停止数天或数周，然后在正确的时刻唤醒）。

不过，我认为您正在尝试实现无锁队列（而不是列表）。队列比列表更容易实现。Edya Lazan-Mozes 和 Nir ​​Shavit 的论文“无锁 FIFO 队列的乐观方法”和 Maged M. Michael 和 Michael L. Scott 的“Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”都是用于实现无锁队列的信息非常丰富且易于实现。

但是，如果您坚持使用无锁链表，请考虑 Michail Fomitchev 和 Eric Ruppert 在“无锁链表和跳过列表”中的实现。您还可以查看 Damian Dechev 的无锁动态数组（Wikipedia 上有一个链接）。

于 2010-05-24T23:41:24.587 回答
0

在两个版本中pop：

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

和

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

您已经有一个错误，即在从假定的根节点读取之前，您没有验证您的列表/堆栈是否为空。

这加剧了您提到的root在 test_and_set 甚至发生之前必须取消引用才能到达 next 的问题。它本质上变成了一个 test_and_then_test_and_set 操作，其中 and_then 表示需要不止一个步骤。

您的第一个 pop 版本需要是：

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

我相信你会看到这会带来更多的步骤。

于 2010-05-24T21:12:36.880 回答