《操作系统导论》第 29 章：基于锁的并发数据结构 - 深度知识架构

1. 核心矛盾 (The Crucial Problem)

对于特定的数据结构，如何通过精妙的加锁方式，在保证数据结构功能绝对正确（线程安全）的前提下，实现极高的并发访问性能（扩展性）？

2. 核心概念 (Core Concepts)

• 并发数据结构 (Concurrent Data Structure)：
  • 定义：在传统数据结构（如链表、散列表）基础上加入并发控制原语（如锁），使其能够被多个线程同时访问而不发生竞态条件的代码结构。
  • 角色：多线程环境下的“安全数据容器”，是构建复杂并发软件的基础模块。
• 懒惰计数器 (Sloppy Counter / Approximate Counter)：
  • 定义：一种高扩展性的并发计数器机制。它为每个中央处理器 (Central Processing Unit, CPU) 维护一个局部计数器和一个局部锁，同时维护一个全局计数器和一个全局锁。
  • 角色：性能与精确度的“调和者”。它通过推迟全局更新，完美解决了单锁计数器在多核环境下的性能瓶颈。
• 过手锁 (Hand-over-hand Locking) / 锁耦合 (Lock Coupling)：
  • 定义：一种针对链表的极细粒度加锁技术。为链表中的每个节点配置一把锁，线程在遍历时，先获取下一个节点的锁，再释放当前节点的锁。
  • 角色：试图提高链表并发度的“激进尝试”，但在实际工程中往往因为开销巨大而适得其反。
• 大内核锁 (Big Kernel Lock, BKL)：
  • 定义：早期 Linux 操作系统中用于保护整个内核数据结构的单一全局锁。
  • 角色：说明“先简单后复杂”优化演进的反面教材。它在多 CPU 普及后成为性能瓶颈，推动了内核向细粒度锁的重构。

3. 逻辑演进 (Logical Evolution)

为了让不同的数据结构在并发下既安全又快速，计算机科学家针对每种结构进行了如下推演：

• 演进 1：并发计数器 (Concurrent Counters)
  • 最初方案：给整个计数器加一把单把大锁。
  • 遇到问题：当多个线程频繁更新计数器时，锁竞争极其激烈，扩展性极差，导致多核 CPU 性能甚至不如单核。
  • 成熟方案：引入懒惰计数器。每个 CPU 独立累加自己的局部计数器（只竞争自己的局部锁，冲突极小）。只有当局部计数器达到某个阈值 $S$ 时，才去获取全局锁，将局部值累加到全局计数器中，并将局部值清零。这完美实现了多核下的线性扩展。
• 演进 2：并发链表 (Concurrent Linked Lists)
  • 最初方案：在操作（如插入/查找）开始时获取一把大锁，结束时释放。
  • 遇到问题：如果内部发生异常（如 malloc 失败导致提前返回），极容易忘记释放锁而导致死锁。
  • 演进与修补：收缩临界区，仅在实际操作共享指针的那几行代码前后加锁，并优化代码以单一路径返回，降低控制流引发的错误概率。
  • 追求更高并发：引入过手锁 (Hand-over-hand locking)，将锁粒度细化到每个节点。
  • 遭遇新问题：频繁获取和释放锁的时间开销过于庞大，导致其实际运行速度通常比单把大锁还要慢。
• 演进 3：并发队列 (Concurrent Queues)
  • 最初方案：使用一把大锁保护整个队列。
  • 遇到问题：入队（操作队尾）和出队（操作队首）操作相互阻塞，并发度低。
  • 成熟方案：Michael 和 Scott 提出的并发队列。使用两把锁（一把 headLock，一把 tailLock），并引入一个虚拟节点 (Dummy Node) 来分离头尾操作。这使得入队和出队可以完全并行执行。
• 演进 4：并发散列表 (Concurrent Hash Tables)
  • 最初方案：整个散列表共用一把大锁。
  • 遇到问题：散列表本就是为了极速查找而生，单锁抹杀了其并发潜力。
  • 成熟方案：不为整个散列表加锁，而是为每个散列桶（Hash Bucket，通常对应一个链表）配备一把独立的锁。由于散列函数会将操作均匀分布到不同桶中，锁竞争被极大稀释，这种设计扩展性极好，性能优异。

4. 机制与策略 (Mechanisms vs. Policies)

• 机制 (Mechanisms - 底层实现)：
  • 底层的互斥机制完全依赖上一章打造的锁原语（如 pthread_mutex_lock / unlock）。它们提供了保障原子性的硬性手段。
• 策略 (Policies - 上层决策)：
  • 在懒惰计数器中，局部计数的阈值 $S$ 的选择是一个纯粹的策略决策。它决定了系统偏向哪一端：如果 $S$ 很小，全局计数器非常精确，但性能趋近于单把大锁；如果 $S$ 很大，性能扩展极佳，但全局计数器会有严重的滞后误差。

5. 设计折衷 (Design Trade-offs)

• 牺牲“全局数据的实时精确度”，换取“极致的并发扩展性能”：这是懒惰计数器（Sloppy Counter）的经典折衷。系统不再强求随时都能读取到最精确的计数值，而是允许一定的滞后和误差，从而彻底消除了核心间对全局变量的锁争用。
• “并发度收益”与“锁操作开销”的折衷：过手锁（Hand-over-hand locking）试图通过降低锁的粒度来换取更多的线程同时工作。但它牺牲了单次操作的性能（因为要执行成百上千次 lock 和 unlock 操作）。在工程实践中，这种微观管理的固定开销往往大于它带来的并发收益。

6. 关键洞察 (Key Insights)

• 避免不成熟的优化 (Knuth 定律)：“不成熟的优化是所有坏事的根源。”在实现并发数据结构时，最聪明的工程做法是：先加上一把简单粗暴的大锁。如果你发现这把大锁没有成为性能瓶颈，就到此为止；只有当你通过测试确认它严重拖慢了系统时，再去改进它。
• 更多并发不一定更快：增加锁的细粒度和复杂性（例如为每个节点加锁）听起来很酷，但其实会带来极高的底层操作开销。有时候简单的自旋锁或单锁反而最有效。你无法在性能上作弊：结果要么更快，要么不快。必须通过实测来验证复杂的并发方案是否值得。
• 当心锁与异常控制流的碰撞：当函数在开始时获取锁，而在中间因为各种错误分支（如内存不足）提前 return 时，极易产生“忘解死锁”的惨剧。优秀的并发代码应该尽量收缩临界区范围，或者精心组织代码，使其拥有清晰的、统一的退出路径。

导师的下一步建议： 在本章中，我们终于用锁为常见的数据结构穿上了“并发防弹衣”。但你可能注意到了，我们在操作队列时有一个隐藏的问题尚未解决：如果一个线程想出队，但此时队列是空的，它该怎么办？ 它总不能一直死循环（自旋）占用着 CPU 来检查队列什么时候有数据吧？

为了解决这种”一个线程需要等待另一个线程完成某事”的协同问题，我们需要学习并发的第二大神器——条件变量 (Condition Variables)。

MOC · 下一章：Ch30 条件变量