基于锁的并发数据结构

1. 核心问题：如何给数据结构加锁？

目标：通过锁机制使数据结构线程安全，确保多线程并发访问的正确性，同时尽量提升性能以支持高并发。
挑战：
正确性：锁必须保护共享资源的访问，避免数据竞争（data race）和不一致性。
性能：锁的粒度和使用方式直接影响并发性能，过多的锁或不当的锁机制可能导致性能瓶颈。
方法：
简单加锁：为整个数据结构加一把大锁，简单但扩展性差。
细粒度锁：为数据结构的子部分（如链表节点、散列桶）分配锁，提升并发性。
优化技术：如懒惰计数器、过手锁等，通过减少锁竞争或降低锁开销提升性能。
权衡：
简单方案（大锁）易实现，正确性高，但性能可能不佳。
复杂方案（多锁、细粒度锁）性能好，但实现难度高，容易出错。

2. 并发计数器

2.1 无锁计数器

实现：简单结构，仅包含一个整数值，提供初始化、增量、减量和获取操作（图29.1）。
问题：无同步机制，多线程访问会导致数据竞争，计数结果不正确。

2.2 简单加锁计数器

实现：在计数器结构中加入互斥锁（pthread_mutex_t），每个操作（增、减、获取）都通过锁保护（。
特点：
正确性：锁确保每次只有一个线程修改计数器值。
性能问题：所有线程竞争同一把锁，扩展性差。实验表明，线程数增加时性能急剧下降。
适用场景：低并发场景或性能要求不高的场景。

2.3 懒惰计数器（Sloppy Counter）

背景：研究表明，可扩展的计数器对多核系统性能至关重要。
实现：
结构：每个CPU核心维护一个局部计数器（local），全局有一个全局计数器（global），分别配有局部锁（llock）和全局锁（glock）。
更新流程：
1. 线程更新本地计数器，获取对应核心的局部锁。
2. 当本地计数器达到阈值（threshold，S）时，获取全局锁，将本地值累加到全局计数器并清零本地计数器。
获取值：直接读取全局计数器（可能不精确）。
特点：
高扩展性：局部计数器减少锁竞争，不同核心的线程可并行更新。
不精确性：全局计数器可能滞后，需通过阈值S平衡精确性和性能（图29.4）。
阈值S的影响：
- S小：频繁更新全局计数器，精确性高但性能差。
- S大：减少全局更新，性能好但全局值可能偏差大。
适用场景：高并发场景，如操作系统内核计数或性能监控。

3. 并发链表

3.1 简单加锁链表

实现：
链表结构包含节点（node_t）和链表头（list_t），配有一把全局锁。
插入和查找操作通过全局锁保护整个操作。
问题：
扩展性差：所有线程竞争同一把锁，无法并行操作。
异常处理复杂：如malloc失败，需在返回前释放锁，容易出错。
优化：
细化锁范围：仅在更新链表的关键部分（如插入节点到链表）加锁，非关键操作（如malloc）无需锁。
统一返回路径：查找操作通过单一返回路径释放锁，减少错误可能。
优点：降低锁开销，减少异常控制流中的错误风险。

3.2 过手锁（Hand-over-Hand Locking/Lock Coupling）

原理：
每个节点配一把锁，遍历时获取下一节点的锁后释放当前节点锁。
理论上允许多线程同时遍历不同部分，提升并发性。
问题：
高开销：频繁获取和释放锁的开销可能抵消并发带来的性能提升。
实际效果：除非链表非常大且线程数多，否则性能可能不如单锁方案。
改进思路：尝试混合方案，如每N个节点共享一把锁，平衡并发和开销。

4. 并发队列

4.1 Michael和Scott并发队列

实现：
结构：队列包含头尾指针（head、tail），分别配有头锁（headLock）和尾锁（tailLock）。
操作：
- 入队（Enqueue）：获取尾锁，更新尾指针。
- 出队（Dequeue）：获取头锁，更新头指针。
技巧：初始化时添加假节点，分离头尾操作，减少竞争。
特点：
高并发：入队和出队操作分别使用不同锁，可并行执行。
正确性：假节点确保头尾操作互不干扰。
局限：
仅支持基本入队和出队，缺乏有界队列功能（如满/空时等待）。
下一章将讨论条件变量，解决有界队列的等待问题。

5. 并发散列表

5.1 简单并发散列表

实现：
结构：散列表包含固定数量的桶（BUCKETS），每个桶是一个并发链表。
操作：插入和查找通过哈希函数定位桶，调用相应链表的操作。
特点：
高扩展性：每个桶有独立锁，支持多线程并行操作（图29.10）。
简单高效：基于并发链表实现，代码复用性高。
局限：
未考虑动态调整大小，需额外工作支持扩容/缩容。
桶数量（BUCKETS）需根据负载合理设置，避免冲突过多。

6. 通用建议与经验教训

避免不成熟的优化（Knuth定律）：
优先实现简单方案（如大锁），确保正确性。
仅在性能瓶颈明确时优化，避免复杂设计带来的维护成本。
例：Linux早期使用大内核锁（BKL），在多核普及后逐步替换为细粒度锁。
注意锁与控制流：
异常路径（如malloc失败）需确保锁正确释放。
统一返回路径减少错误风险。
更多并发不一定更快：
细粒度锁增加并发但引入开销，需通过实验验证实际性能。
简单方案在低并发场景下可能更优。
性能优化策略：
减少锁竞争：如懒惰计数器通过局部计数减少全局锁使用。
细化锁粒度：如散列表按桶加锁，队列分头尾锁。
权衡正确性与性能：如懒惰计数器通过阈值S调整精确性。

总结

基于锁的并发数据结构通过锁机制确保线程安全，但锁的设计直接影响正确性和性能。简单加锁方案（如计数器、链表的大锁）易实现但扩展性差；优化方案（如懒惰计数器、过手锁、头尾锁队列、桶锁散列表）通过细粒度锁或减少竞争提升并发性，但需权衡复杂性与开销。开发者应从简单方案入手，基于性能需求逐步优化，同时注意异常控制流和锁管理的正确性。Moir和Shavit的调查提供了深入研究的起点，结合实践和内核案例可进一步掌握并发设计的精髓。