一、C无锁(lockfree)数据结构与有锁数据结构相比

在现代多核 CPU 中，提升性能的重点的不在于有锁还是无锁，而是尽可能减少核间通讯。

要减少核间通讯，就要减少写竞争，要减少写竞争，最直接的途径就是细化锁粒度，这不是一件容易的事，无锁数据结构也不是一件容易的事，好的无锁数据结构实现一般会同时细化锁粒度。比如并发队列需要几个锁？再细分一下 spsc, spmc, mpsc, mpmc，又各自需要哪些锁？

实际上，很多所谓的 LockFree 数据结构的实现，只是使用 user spin lock + yield 代替 mutex，这种锁实际上不 scale，并且不 fair，要极力避免干这种事。

LockFree 实际上仍然有锁，只是把它移到了用户代码，理想条件下，竞争应该非常罕见，锁的作用就是在这种非常罕见的情况下，保证并发程序正确地按照预期顺序执行。如果竞争率很高，那不管是有锁还是无锁，性能损失都是非常大的。

例如在 RocksDB 中，并发写 MemTable 时就使用了非常激进的 spin，导致并发写较高时大量 CPU 都浪费在 spin 上了，ToplingDB 反其道而行，把这一块改成了发生竞争时优先 wait(使用 futex)，把 cpu 让出来，起到很好的效果，避免了 CPU 的浪费。

延伸阅读：

二、无锁数据结构的好处

主要原因： 将并发最大化。

使用基于锁的容器， 会让线程阻塞或等待； 互斥锁削弱了结构的并发性。 在无锁数据结构中， 某些线程可以逐步执行。 在无等待数据结构中， 无论其他线程当时在做什么， 每一个线程都可以转发进度。

健壮性：

如果线程在持有锁的同时死亡，那么该数据结构将永远被破坏。但是，如果线程在对无锁数据结构的操作中途中途死亡，则除了该线程的数据外，什么都不会丢失。其他线程可以正常进行。

死锁活锁问题：

死锁问题不会困扰无锁数据结构; 无等待的代码不会被活锁所困扰,因其操作执行步骤是有上限的。

上一篇

树堆（Treap）和红黑树（RB-Tree）各有哪些优劣?

下一篇

数据结构线性链表插入中的ElemType e与删除中的ElemType&e有什么区别吗?