代码之家 › 专栏 › 技术社区 › Evan Teran

这个test\u和\u set的用法是线程安全的吗?

lock-free gcc c c++

Evan Teran · 技术社区 · 16 年前

CAS 最终有了某种程度的 ABA problem .

所以,我来回答这个问题。我在想一个简单的单链表。2主要业务。 push 和 pop . 推 总是在前面插入。像这样:

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

流行音乐总是第一个元素。像这样:

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

显然,push是非常重要的,一个简单的无锁方法可能不会发生。但流行音乐看起来可能可行。使用gcc内部函数,我想到了:

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

功能等效?是的。无锁?是的。线程安全? 我不知道 . 我的直觉反应是否定的,这就是原因。

我担心的是 test_and_set 必须取消对内存的引用。如果根在 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);
}

所以,就像我说的,我认为此代码不正确。但有谁能肯定地说,我得出了正确的结论(我不想写下一些工作得很好的东西)。如果它真的像我怀疑的那样坏了。有什么简单的解决办法吗?

3 回复 | 直到 16 年前

rlbond 16 年前

你说得对。在C++中,函数的参数以任意顺序进行计算,但肯定地,编译器无法知道 root->next 是你序列中的一个原子操作。

考虑两个线程调用 pop() 根->下一个 ,然后另一个 根->下一个 ,两个都打电话 test_and_set() . 现在只弹出了一个节点。

thechao 16 年前

两件事:(1)测试;集合只有一致数2;对于这样一个弱同步原语,只使用读/写内存屏障而不产生专门指令的开销就足够了(2) ABA问题是一个真正的问题,解决方案少得可怜;然而,对于CAS(32位系统上的cmpxchg8b和64位系统上的cmpxchg16b,用于x86/-64),寄存器的上部有足够的空间来存储如此大的时间戳,以至于ABA在实践中从未出现过(即使是在相当人为的设置中,也需要一个线程暂停几天或几周,然后在正确的时间点唤醒)正确的时刻)。

不过,我认为您正在尝试实现一个无锁队列(而不是列表)。队列比列表更容易实现。Edya Lazan Mozes和Nir Shavit的论文《无锁FIFO队列的一种乐观方法》和Maged M。迈克尔和迈克尔L。Scott对于无锁队列的实现既有丰富的信息,又易于实现。

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

nategoose 16 年前

在两个版本的 pop :

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

和

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

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

root 在测试\u和\u集发生之前到达下一个。它本质上变成了一个test\u and\u then\u test\u and\u set操作,其中and\u表示需要多个步骤。

pop的第一个版本必须是:

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

我敢肯定你会看到这一点,在混合中加入了更多的步骤。