原子比较交换 VS 互斥锁

Question

用这种方式替换互斥锁有什么意义？

void stack_push(stack* s, node* n)
{
    node* head;
    do
    {
        head = s->head;
        n->next = head;
    }
    while ( ! atomic_compare_exchange(s->head, head, n));
} 

不理解使用原子交换替换互斥锁的好处在哪里？

- Galimov Albert

---

重点是当前的代码没有锁。 - Kerrek SB

@Mehrdad：那又怎样？至少有一个线程肯定会跳出循环。 - Kerrek SB

与操作系统运行互斥量所需的工作相比，CAS延迟很长但微不足道。我们正在谈论一个非常非常慢的单个指令，与大量代码和函数调用以及切换到内核的上下文相比。 - user82238

你很可能确实需要：atomic_compare_exchange(&s->head, &head, n)。 - Michael Burr

刚读完Anthony Williams的《C++并发编程实战》。互斥锁通常由原子布尔标志实现，但使用其他原子类型可以做更多的事情并避免锁定。在高竞争情况下，互斥锁可能会变得非常缓慢。 - Walter

Answer 1

有许多优点：

1. 速度更快（在Windows上，大约是10倍或100倍 - 在Linux上不太明显，只有10%的提升）
2. 它可以更好地扩展（虽然仍然不够 - 只能到大约100个逻辑核心）
3. 它更酷，你看起来更聪明、更有能力
4. 在不需要等待或休眠的情况下，此代码可用于禁止等待或休眠的地方，例如中断处理程序、Windows（DISPATCH_LEVEL）和Linux内核的某些部分等

- user82238

---

顺便问一下，为什么在Linux上速度较慢？ - user541686

它并不是。不同之处在于互斥锁的速度快慢。在Windows上，互斥锁非常慢。在Linux上，它们非常快（我认为它们必须是用户模式而不是内核模式）。因此，在Windows上，无锁方法要快得多。在Linux上，它只快了一点。 - user82238

@mehrdad: 我相信Linux的互斥锁是建立在futex之上的，futex是一个在进程间共享的原子整数，以及内核中的等待队列。实现时，只有在发生冲突时才需要进入内核。详细信息请参考：http://en.wikipedia.org/wiki/Futex - Dave S

@Mehrdad：我建议测试两种实现。我想知道“Windows互斥锁很慢”的概念是基于早期实现还是可能曾经是真的，但现在不再是真的。 - Dave S

你忘记了负面点：互斥锁编写起来要简单得多，并且更容易正确实现。无锁编程是一个雷区，非常容易出错（特别是如果你想通过不使用顺序一致的内存顺序来真正挤取最佳性能）。多线程编程中最令人烦恼的是：你不能通过运行简单的测试来验证代码，因为多线程代码是不确定的（即使串行代码也是如此，但它更接近确定性）。 - Walter

Answer 2

相比于互斥锁，通常更快。尽管如此，你不能只是简单地用CAS替换所有互斥锁。单个CAS仅会在多个线程之间安全地交换一个引用到另一个引用。

如果你有一个复合函数，在其中一个写操作依赖于另一个读操作时（例如），你需要使用互斥锁来确保原子性。

- John Vint

---

你不能使用带有 memory_order_acq_rel 的 CAS 来模拟锁并获得正确的内存顺序吗？ - atlex2