6.1 并发设计的意义

设计并发数据结构是为了让多线程并发访问，并且线程可对数据结构做相同或不同的操作。多线程环境下，无数据丢失和损毁，所有的数据需要维持原样，且无条件竞争的数据结构，称之为“线程安全”的数据结构。通常情况下，多个线程对数据结构进行并发操作是安全的，但不同操作需要单线程独立访问数据结构。当线程执行不同的操作时，对同一数据结构的并发操作是安全的，而多线程执行同样的操作时，可能会出现问题。

实际的设计意义并不止上面提到的那样，而是要为线程提供并发访问数据结构的机会。本质上，在互斥量的保护下同一时间内只有一个线程可以获取锁。互斥量为了保护数据，会显式阻止线程对数据结构的并发访问。

串行化(serialzation)则是线程轮流访问数据，对数据进行串行访问。因此，需要对数据结构仔细斟酌，确保能进行真正的并发。虽然，有些数据结构比其他结构的并发访问范围更大，但思路都是一样的：减少保护区域，减少序列化操作，提升并发访问的能力。

进行数据结构的设计之前，快速浏览一下并发设计的指导指南。

6.1.1 并发数据结构设计的指南

设计并发数据结构时，需要考量两方面：一是确保访问安全，二是真正并发访问。第3章已经对如何保证数据结构是线程安全的做过简单的描述：

• 确保无线程能够看到“不变量”变化时的状态。

• 小心会引起条件竞争的接口，提供完整操作的函数，而非操作步骤。

• 注意数据结构的行为是否会产生异常，从而确保“不变量”的状态。

• 将死锁的概率降到最低。限制锁的范围，避免嵌套锁的存在。

还需要考虑数据结构对于使用者有什么限制，当线程通过特殊的函数对数据结构进行访问时，其他的线程还有哪些函数能安全调用？

这是一个很重要的问题，普通的构造函数和析构函数需要独立访问数据结构，所以用户使用时，就不能在构造函数完成前或析构函数完成后对数据结构进行访问。当数据结构支持赋值操作swap()或拷贝构造时，作为数据结构的设计者，即使线程操纵数据结构中有大量的函数，也需要保证这些操作在并发下是安全的(或确保这些操作能够独立访问)，以保证并发访问时不会出错。

第二个方面是确保真正的并发访问，这里没有更多的指导意见。不过，作为一个数据结构的设计者，需要考虑以下问题：

• 操作在锁的范围中进行，是否允许在锁外执行？

• 数据结构中不同的互斥量能否保护不同的区域？

• 所有操作都需要同级互斥量的保护吗？

• 能否对数据结构进行简单的修改，增加并发访问的概率？

这些问题都源于一个指导思想：如何让序列化访问最小化，让真实并发最大化？允许线程并发读取的数据结构并不少见，但修改必须是单线程的，这种结构类似于std::shared_mutex。同样，这种数据结构也很常见——支持多线程的不同操作时，也能串行执行相同的操作。

最简单的线程安全结构通常会对数据使用互斥量或锁。虽然，这么做还有问题，不过这样做相对简单，并且能保证只有一个线程在同一时间对数据结构进行独立访问。为了更轻松的设计线程安全的数据结构，接下来了解一下基于锁的数据结构。