并发数据结构-1.1.2 阻塞技术

原文链接，译文链接，译者：周可人，校对：梁海舰

1.1.2 阻塞技术

在很多数据结构中，内存竞争所带来的不良现象和前文所说的顺序瓶颈带来的影响都可以通过使用细粒度锁机制来减小。在细粒度锁机制中，我们用多个粒度较小的锁来保护数据结构中的不同部分。这样做的目的是允许并发操作在它们不访问数据结构的相同部分时并行执行。这种方法也可以用于避免独立内存位置访问的额外竞争。在一些数据结构中，这种现象经常发生；举个例子，在哈希表中，对那些被哈希到不同哈希桶中的值的操作自然访问的是数据结构中的一部分。

对其他的数据结构，如基于锁的共享计数器，怎样减少竞争和降低顺序瓶颈并没有那么清晰，因为抽象地来说，所有的操作都对数据结构的同一部分做修改。一种处理竞争的方法是将所有操作分散在不同时间，从而使每一个操作在不同的时段访问计数器。一种广泛使用的处理技术被称为回退。然而，即使减少了竞争，我们的基于锁的计数器仍然缺少并行性，并且不可扩展。幸运的是，更加细致的技术可以提升可扩展性。

一种技术，被称为“合并树”，可以用来实现一个可扩展的计数器。这种技术使用了一个二叉树，每个叶子表示一个线程。树的根节点存储实际的计数器值，树的其他内部节点用来协调对根节点的访问。其中的核心思想是线程从树的叶子节点向上爬，尝试去和其他并发操作“合并”。每一次两个线程的操作在一个内部节点合并，其中一个线程（失败者），简单地在当前节点等待，直到一个返回值传递给它。另外一个线程（胜利者），朝着根节点向上，携带所有在该节点子树中合并的操作之和；一个到达根节点的胜利者线程将它的和增加到计数器中，因此所有合并的操作增长被加到计数器中。之后这个胜利者在树中下降，分发一个返回值给每一个之前合并的，处在等待状态的失败者线程。这些返回值被分发下来，这样的效果就好像所有增长操作都在根计数器被修改的时刻一个接着一个的执行。

在合并树中，失败者在等待胜利者时所使用的技术对性能而言是重要的。一个失败者采用重复地读取一个树节点的一个内存地址的方式操作等待，这被称为自旋。在缓存一致性多核处理器中，一个重要的推论是这个位置会位于运行失败者操作的处理器的本地缓存，直到胜利者操作报告结果。这意味着等待的失败者并没有产生任何不必要的，并且可能降低胜利者性能的内存流量。这种等待被称为本地自旋，且已经被证实对提升可扩展性来说至关重要。

在所谓的非一致性内存访问(NUMA)架构中，处理器访问他们的共享存储中本地存储部分要比访问其他处理器的部分要快的多。在这样的架构中，数据布局——合并树中节点在内存中的分布方式——对性能有着显著的影响。将树的叶子节点存放在处理相应线程的处理器附近可以提升性能。（我们假设线程是和处理器静态绑定的）

数据布局的问题也对缓存一致性多核处理器上并发数据结构的设计有影响。回顾合并树的一个作用是减少独立内存位置的竞争，从而提升性能。然而，因为缓存一致性多核处理器用缓存行大小的块管理内存，如果两个线程访问不同内存区域，落在了相同的缓存行中，会和他们访问同一块内存地址一样受到性能影响。这种现象被称为伪共享，这是一个常见的，令人困惑的性能问题。

在减少独立内存位置的竞争，用本地自旋减少内存流量，允许操作并行执行之后，用合并树实现的，随着并发线程的数量扩展的计数器，比单锁版本的计数器要好的多。如果所有线程被用于不断合并，那么一个P宽度的树允许P个线程在O(logP)个（合并树中的）上升和下降的操作之后，返回P个值，提供了O(P/logP)的加速比。

尽管使用合并树的方式有很多优点，但是它也有一些不足之处。合并树需要限定P个线程访问计数器，并且需要O(P)的空间。虽然它在高负载下能提供更高的吞吐量，即在树被大量线程访问时，但它在低负载访问时的最好性能是差的：它必须遍历树中的O(logP)个节点，然而一个基于单锁的fetch-and-inc操作在常数时间内可以完成。此外，如果一个线程因为它在一个胜利者线程离开树向上后马上到达导致合并失败，那么它必须等待，直到胜利者返回才能继续向上。如果上升的胜利者，失败者，以及之后的上升线程之间的协调处理错误，那么可能会导致死锁：线程可能以循环的方式互相阻塞，没有一个可以继续执行。避免死锁显著地增加了设计正确，并且高效的阻塞并发数据结构的复杂性。

总的来说，如果在使用足够的阻塞来达到正确，和尽量降低阻塞来允许并发操作并行执行之间达到平衡，阻塞数据结构可以提供强大的，高效的实现。