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

本章主要内容

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

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

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

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