并发数据结构-1.4 池
实现高效并发栈和队列的大部分挑战来自于一个被插入的元素可以被删除这一需求。并发池是一种支持插入和删除操作的数据结构,它允许删除操作移除任何一个已经被插入的,并且没有在随后被删除的元素。这样的弱需求提供了提高并发性能的机会。
一个高效的并发池可以使用任意静态一致的计数器来构建。在这样的并发池中,元素被置于数组当中,fetch-and-inc操作决定插入操作在哪个位置存储元素,同样的,fetch-and-inc操作决定删除操作在哪个位置获得元素。每一个数组元素都包含了一个表示满/空的比特位或者等效的机制,来表明在相应的位置,将要删除的元素已经存在。在这种策略下,使用combining tree,combining funnel,counting network,diffracting tree中的任何一个技术都可以并行化共享技术器,解决这一主要的瓶颈来创建出一个高吞吐量的共享并发池。此外,一个类似栈的池可以使用一个允许增加和减少操作的计数器来实现,然后利用以上技术中的一种来并行化.
阅读全文