基于无锁数据结构的FIFO队列算法

俊昌, ,

(1.南京邮电大学 计算机学院,南京 210023; 2.江苏省大数据安全与智能处理重点实验室,南京 210023)

0 概述

近年来,随着多核处理器的广泛应用,高速应用程序的并行化飞速发展[1-4]。其中一种可行的并行化方法为流水线并行化,即多核处理器中的一个处理器核心完成较大任务中的第一阶段子任务,然后将该任务传递给另一个核心,该核心负责完成下一阶段的子任务处理。

由于现代商用多核处理器中普遍缺乏硬件支持的核间通信机制[5],因此当前研究大多采用基于软件实现的无锁队列[1-2,6-7]作为流水线的核间通信机制。然而,现有无锁队列算法在设计时均假设数据的到达速率处于稳定状态,如果输入数据到达速率波动较大,队列将频繁地趋于空或趋于满,从而导致无锁队列性能急剧下降。因此,在真实应用场景中,采用流水线并行技术的软件性能往往急剧下降。

针对数据到达速率不稳定的实际应用场景,本文提出一种新的无锁队列TinyQueue。当数据到达速率较低时,自适应地减小队列大小,以减少内存占用;而当数据到达速率较高时,则自适应地增加队列大小,以避免数据丢失。

1 相关工作

无锁队列被广泛地应用于多线程程序中,并且也有大量关于并发无锁队列的研究[8-11],其中大部分研究都集中在多生产者多消费者队列。然而,由于需要避免ABA问题,因此这些无锁队列性能都不甚理想。

作为一种特殊情况,单生产者单消费者队列是实现高速核间通信很好的解决方案[1-2,6-7,12],因为它从根本上避免了ABA问题。……