无锁队列并非真的无锁

近几年经常被提起的无锁队列，似乎被视为解决高并发的万能良药。无锁队列是一种通过CPU提供的原子操作指令 CAS 和 FAA，以及循环重试，来实现的乐观并发控制算法。虽然无锁队列算法并未显式调用锁，但事实上，在多核环境下，所谓的无锁队列算法本质上就是实现了锁的功能。

首先，原子指令本身就是一种带锁的操作，只是锁的颗粒度较小而已。单核 CPU 系统的情况比较简单，因为单条指令操作总是原子的；而 SMP 的情况就比较复杂了，需要使用缓存一致性（Cache Coherence）的机制来确保操作的原子地执行。

从上图可以得知，每个 CPU 核心都有对应的本地缓存。由于系统存在多套缓存，必然导致数据一致性问题。CPU 通过缓存一致性协议（Cache Coherency Protocols）来解决这个问题。虽然不同协议的实现方式不同，但是为了保证 CPU 数据写入的事务串形化，都会隐含实现锁的功能。

其次，由于无锁队列是一种乐观并发控制的实现，所以必须处理 CAS 失败的情况。为了尽可能地保证写入成功，需要不断重试 CAS 操作，直到写入成功为止。这种类似于自旋锁的机制会导致一定的 CPU 开销。随着并发数的上升，CAS 操作失败的几率会上升，最终导致耗尽 CPU 资源。某些优化算法就是在重试循环中加入 Sleep 指令来降低 CPU 开销。

此外，在设计无锁队列的数据结构时，还需要避免伪共享（False Sharing）现象。即在频繁写入的数据附近加入填充数据，以避免 CPU Cache 失效而带来的性能损失。