并发数据结构-1.1 并发的数据结构的设计

原文链接，译文链接，译者：董明鑫，校对：周可人

随着多个处理器共享同一内存的机器在商业上的广泛使用，并发编程的艺术也产生了巨大的变化。当前的趋势向着低功耗芯片级多线程（CMT）发展，所以这样的机器一定会更加广泛的被使用。

共享内存多处理器是指并发的执行多个线程的系统，这些线程在共享的内存中通过数据结构通讯和同步。这些数据结构的效率对于性能是很关键的，而目前熟练掌握为多处理器机器设计高效数据结构这一技术的人并不多。对大多数人来说，设计并发的数据结构比设计单线程的难多了，因为并发执行的线程可能会多种方式地交错运行他们的指令，每一种方式会带来不同的，甚至不符合预期的输出。这就要求设计者改变他们对运算的认识，理解新的设计方法，采用新的编程工具集。此外，设计可扩展的并发数据结构，使得当机器执行越来越多的并发线程时依旧表现良好也是新的挑战。本文主要介绍设计并发数据结构的相关挑战，和一些重要的数据结构相关内容的总结。我们的总结绝不是全面的；相反，我们特意选取了一些能说明设计的关键问题的流行的数据结构，希望我们提供了足够的背景和知识，让有兴趣的读者接触那些我们没有提到的内容。

1.1 并发的数据结构的设计

共享内存多处理器的一些特性使得并发数据结构的设计和校验比相对应的单线程结构难度显著增加。

acquire(Lock);

oldval = X;                                                                                      oldval = X;

X = oldval + 1;                                                                                X = oldval + 1;

return oldval;                                                                                 release(Lock);

return oldval;

图1.1：顺序的和基于锁机制的fetch-and-inc操作代码片段

难点的根源在于并发：因为线程是在不同的处理器上并发的执行，而且受操作系统的调度决策、缺页、中断等等影响，我们必须按照全部异步的想法来思考，以保证不同的线程能够随意交错的运行。这显著提升了正确设计并发数据结构的复杂度。

为多处理器系统设计并发的数据结构在性能和可扩展性上也有大量的挑战。在现代的机器上，处理器和内存的布局、数据在内存中的布局、多处理器体系结构中各个元素间的通信负载全都对性能有影响。此外，正确性和性能两者联系非常的紧密：算法的改进在提高性能的同时经常使其更加难以设计和检验正确的数据结构实现。

下面的例子阐述了影响数据结构设计的各个多处理器特征。假设我们想要实现一个共享的计数器数据结构，用于支持fetch-and-inc操作，即计数器加一然后返回增加前的值。一个普通的顺序fetch-and-inc实现的代码就如图1.1中左边部分所展示的那样。

如果我们允许多个线程并发地调用fetch-and-inc操作，上述实现运行起来并不正确。来看看原因，注意大多数编译器会把这份源代码转换成机器指令：把 X 的值装进一个寄存器，然后把寄存器中的值加一，然后再把这个寄存器的值存回 X 。假如计数器初始化为 0 ，两个不同的处理器并发的执行两个fetch-and-inc操作。然后就有可能两个操作都从 X 中读出 0 ，然后都把 1 存回 X 并且返回 0 。这显然是不正确的：两个操作中有一个应该返回 1 。

如上所述，两个fetch-and-inc操作不正确的交错结果导致了不正确的行为。一个自然并且普通的方法来阻止这样的交错就是用互斥锁（也被叫做 mutex 或者 lock）。锁是一个在任意时间点，都是不被（其他线程）获取，只被一个线程所获取的构造。如果一个线程 t1 希望获取已经被另一个线程 t2 所获取到的锁，那么 t1 必须等到 t2 释放这个锁。

如图 1.1 右半部分所示，我们能通过锁机制得到一个正确的顺序实现。我们通过阻止所有的交错来预防坏的交错。这样很容易得到一个正确的共享计数器，然而这种简单是有代价的：锁机制引发了许多关于性能和软件工程上的问题。