第7章 无锁并发数据结构设计

本章主要内容

• 设计无锁并发数据结构
  
• 无锁结构中内存管理技术
  
• 对无锁数据结构设计的简单指导
  

上一章了解了在设计并发数据结构时会遇到的问题，根据指导意见确定设计的安全性。对一些通用数据结构进行检查，并了解使用互斥锁对共享数据进行保护的例子。第一组例子就是使用单个互斥量来保护整个数据结构，但之后的例子使用多个锁来保护数据结构不同的部分，并且允许对数据结构进行更高级别的并发访问。

互斥量是一个强大的工具，可以保证在多线程情况下安全的访问数据结构，且不会有条件竞争或破坏不变量的情况存在。使用互斥量的代码，其原因很简单：就是让互斥量来保护数据。不过，这并不会如所想的那样；可以回看一下第3章，回顾一下死锁形成的原因，再回顾一下基于锁的队列和查询表的例子，看一下细粒度锁是如何影响并发的。如果能写出一个无锁安全的并发数据结构，那就能避免这些问题。

本章中还会使用原子操作(第5章介绍)的“内存序”特性，并使用这个特性来构建无锁数据结构。设计这样的数据结构时，因为这样的数据机构不是那么容易正确实现的，所以要格外小心，并且让其失败的条件很难复现。我们将从无锁数据结构的定义开始；而后，将通过几个例子来了解使用无锁数据结构的意义，最后给出通用的指导意见。