并发编程网 - ifeve.com

原文链接，译文链接，译者：huavben，校对：周可人

实现高效并发栈和队列的大部分挑战来自于一个被插入的元素可以被删除这一需求。并发池是一种支持插入和删除操作的数据结构，它允许删除操作移除任何一个已经被插入的，并且没有在随后被删除的元素。这样的弱需求提供了提高并发性能的机会。

一个高效的并发池可以使用任意静态一致的计数器来构建。在这样的并发池中，元素被置于数组当中，fetch-and-inc操作决定插入操作在哪个位置存储元素，同样的，fetch-and-inc操作决定删除操作在哪个位置获得元素。每一个数组元素都包含了一个表示满/空的比特位或者等效的机制，来表明在相应的位置，将要删除的元素已经存在。在这种策略下，使用combining tree，combining funnel，counting network，diffracting tree中的任何一个技术都可以并行化共享技术器，解决这一主要的瓶颈来创建出一个高吞吐量的共享并发池。此外，一个类似栈的池可以使用一个允许增加和减少操作的计数器来实现，然后利用以上技术中的一种来并行化.

最后，在前文中说讨论的消除技术（elimination technique）可以使用在利用combining tree，combining funnel，counting network，diffracting tree等技术实现的并发池中：假如在树中插入和删除操作相遇，那么删除操作可以获取插入操作插入的值，之后两个操作就不用继续遍历这个结构树。这项技术在高负载下能表现出良好的高性能.

上述的这些实现的缺点是，它们在低复杂的情况下性能糟糕。而且，在做负载分布工作的时候，这些实现并不允许我们如同那些专门为负载分布设计的池一样，得到具体的位置信息。

负载均衡算法涉及到一个任务池集合，每个任务池中有一些工作单元，其中每一个任务池都被本地化到一个处理器上。当线程创建了工作项之后就把它们置于本地化的任务池中，依靠负载均衡算法确保任务池中的工作数量都是均衡的。这样就避免了其他处理器仍然忙碌于自己工作的时候，有些处理器却处于空闲状态。大体上有两种解决这类问题的算法：工作共享（work sharing ）和工作窃取（work stealing ）。在工作共享方案中，每一个处理器尝试不断地将自身任务池中的工作卸下，放到其他任务池中。在工作窃取模式下，一个线程已经完成了自己的工作后就会去窃取其他任务池中的工作去执行。两种方案通过随机选择任务池来平衡工作或窃取工作。

传统工作窃取技术是Arara等人提出的，它基于一个无锁结构的双向队列。该双向队列只允许一个线程（该任务池的本地线程）在队列的一端进行操作，在另一端只允许弹出操作，并且允许在这一端的并发弹出操作在线程相互干扰的情况下中止。在这样的约束下，双向队列适合于任务窃取，并且这种约束允许一种简单的实现方式，即本地线程用低开销的load and store操作来进行插入和删除，只有当它和其他非本地删除线程竞争队列里的最后一个任务的时候，才会依赖昂贵的CAS操作。

在一些案例中已经清晰表明一次窃取多个任务的效果是令人满意的。一个非阻塞的多任务窃取算法由Hendler与Shavit在PODC(2002)上提出。在一些案例中同样表明通过使用 同类工作项信息来决定窃取那些工作是可取的。另外在SPAA(2000)上，Acar等人提出了一种位置引导（locality-guided）的窃取算法.