详细介绍：【多线程】无锁数据结构（Lock-Free Data Structures）是什么？

【多线程】无锁数据结构（Lock-Free Data Structures）是什么？

本文来自于我关于多线程系列文章。欢迎阅读、点评与交流
1.什么？就是【多线程】互斥锁（Mutex）
2.【多线程】临界区（Critical Section）是什么？
3.【多线程】计算机领域中的各种锁
4.什么？就是【多线程】信号量（Semaphore）
5.【多线程】信号量（Semaphore）常见的应用场景
6.什么？就是【多线程】条件变量（Condition Variable）
7.什么？就是【多线程】监视器（Monitor）
8.【多线程】什么是原子操控(Atomic Operation)?
9.【多线程】竞态条件（race condition）是什么？
10.【多线程】无锁数据结构（Lock-Free Data Structures）是什么？

一、核心概念：一句话概括

无锁数据结构是一个并发编程中的高级概念，它被设计为在多线程并发访问时，不必须使用互斥锁来保护其内部数据的特殊数据结构。

它的目标是通过原子操作（如CAS, Compare-And-Swap）和精心设计的逻辑，允许多个线程能够安全、高效地同时读写该结构。

---

二、为什么需要无锁数据结构？—— 锁的弊端

要理解“无锁”为什么好，第一要明白传统“有锁”（如互斥锁Mutex、自旋锁Spinlock）的缺点：

1. 阻塞与死锁：

   • 阻塞：如果一个线程持有锁，其他所有试图获取该锁的线程都会被挂起（阻塞），直到锁被释放。这会导致线程切换的开销，并使得其他核心“空转”。
   • 死锁：不正确的锁管理容易导致死锁（两个或以上线程互相等待对方持有的锁）。

2. 优先级反转：

   • 低优先级的线程持有一把锁，高优先级的线程试图获取它时，只能等待，导致高优先级线程被低优先级线程阻塞，违背了优先级设计的初衷。

3. 性能瓶颈：

   • 锁本质上将并发处理串行化了。即使在多核CPU上，对同一个锁的竞争也会使得多个核心无法真正并行工作，从而限制了可扩展性。锁竞争激烈时，性能会不升反降。

无锁编程的哲学：与其让线程“排队”等待一个令牌（锁），不如设计一套巧妙的规则，让所有线程都能“同时前进”，即使某个线程中途慢下来或挂掉，也不会阻碍整个队伍。

---

三、无锁如何实现？—— 核心武器：CAS

无锁数据结构的构建极度依赖于原子操作，其中最重要的是CAS。

CAS操作 包含三个参数：CAS(内存地址， 期望值， 新值)
：就是它的工作流程

1. 检查内存地址中的当前值是否等于期望值。
2. 如果相等，则自动将内存地址的值更新为新值，并返回成功。
3. 如果不相等，说明有其他线程修改了该数据，则不做任何操作，并返回失败。

这是一个在硬件层面实现的原子“读-修改-写”操作，其硬件底层达成通常由缓存锁来保证其原子性，而不是粗粒度的总线锁。

一个生动的例子：无锁栈的入栈管理

假设我们有一个简单的栈，栈顶指针是 top。

1. 线程A想入栈一个新节点 X。

2. 线程A读取当前栈顶指针 old_top = top。

3. 线程A将节点 X 的 next 指针指向 old_top。

4. 线程A执行 CAS操作：CAS(&top, old_top, X)。

   • 意思是：“我认为现在的栈顶还是 old_top，如果是，就把栈顶换成 X。”

5. 关键情况：

   • 如果CAS成功：说明在步骤2到步骤4之间，没有其他线程修改栈顶。入栈操作成功完成。
   • 如果CAS失败：说明在步骤2到步骤4之间，有其他线程（比如线程B）已经修改了栈顶（例如，也插入了一个节点）。那么线程A的 old_top 已经过时了。此时，线程A不会阻塞，它只是简便地重试整个流程：重新读取最新的 top，重新设置 X.next，然后再次执行CAS。

这个过程就像是在说：“我试着去更新，如果发现世界已经变了，那我就根据新的世界再试一次。”

---

四、无锁数据结构的优缺点

优点：

1. 免于死锁：由于根本不用锁，自然也就不会发生死锁。
2. 高并发性与可扩展性：线程不会因为等待同一个锁而被挂起，它们可以持续重试。在多核系统上，随着核心数增加，性能可以更好地线性增长。
3. 对线程终止的免疫力：如果一个线程在执行中途崩溃，它不会持有任何锁，因此不会导致其他线程被永久阻塞。
4. 更低的延迟：对于高并发场景，无锁操作的平均延迟通常比有锁操作更低，因为线程不会被强制挂起和调度。

缺点：

1. 设计极其麻烦：完成一个正确的无锁数据结构相当困难，需要考虑各种微妙的并发冲突，比如ABA问题。
   • ABA问题：线程A读取 top 看到值是 A。然后线程B介入，弹出 A，然后压入 B，又压入一个新的 A（地址可能相同，但已是不同的节点）。线程A再执行CAS时，发现 top 还是 A，于是成功，但这实际上是不正确的，因为中间状态已经变了。解决ABA问题通常需要引入“标签”或版本号。
2. 对CPU不友好（忙等待）：在竞争激烈时，线程可能会不停地重试CAS操作，导致CPU空转，消耗大量资源。这被称为“乐观锁” 的代价。
3. 适用范围有限：并非所有的数据结构都容易实现无锁版本。队列、栈、链表相对容易，而像平衡二叉树这样的复杂结构则非常困难。
4. 测试和调试地狱：并发bug本身就难以复现和调试，无锁数据结构的bug更是如此。

---

五、关键概念辨析

• 无等待一个比“无锁”更强的条件。在无锁中，至少有一个线程能保证前进。而在就是：这无等待中，要求每一个线程都能在有限步内完成操作，绝对不会发生饥饿。达成无等待更加困难。

总结

方面	无锁数据结构
核心思想	用 CAS）就是原子管理（主要 和 非阻塞算法 替代互斥锁。
实现关键	CAS操作 和 重试循环。
优点	高并发、可扩展、免死锁、抗线程崩溃。
缺点	建立复杂、可能导致CPU忙等待、有ABA等困难、调试困难。
适用场景	多核环境下，对性能、延迟和可扩展性要求极高的核心组件，如操作系统内核、高性能数据库、低延迟交易系统、并发容器库（如Java的ConcurrentLinkedQueue）等。

简单来说，无锁数据结构是用算法的复杂性去换取极致的性能。它是一把锋利的双刃剑，只有在确实需要并且有足够能力驾驭时，才应该使用。对于绝大多数应用场景，经过优化的有锁数据结构（如细粒度锁）已经足够好了。