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

来源：计算机工程杂志2018年第8期北京时间：

作者：王俊昌,王振,付雄

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

摘要：现代商用多核处理器缺少硬件支持的处理核间通信机制,多个处理核间必须通过加锁保护的共享内存传递数据。为此,设计一种基于软件的无锁队列作为核间通信机制,通过无锁数据结构提高软件队列的性能。当数据到达速率较低时,队列自适应地减小队列长度,从而占用较 小的内存空间,进而更好地利用处理器高速缓存;当数据到达速率较高时,队列自适应地增加队列长度,以避免数据丢失。实验结果表明,在数据到达速率变化较大的实际应用场景中,该队列较FastForward、MCRingBuffer和B-Queue队列具有更高的数据处理性能。

关键词：无锁数据结构,多核处理,流水线并行,自适应调整,CPU核间通信

基金资助：国家自然科学基金(61602264)。