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

FIFO Queue Algorithm Based on Lock-free Data Structure

作　　者：王俊昌[1,2] 王振 付雄 WANG Junchang1,2 ,WANG Zhen1,2,FU Xiong1,2(1.School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;2.Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing 210023, Chin)

机构地区：[1]南京邮电大学计算机学院,南京210023 [2]江苏省大数据安全与智能处理重点实验室,南京210023

出　　处：《计算机工程》2018年第8期315-320,共6页Computer Engineering

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

摘　　要：现代商用多核处理器缺少硬件支持的处理核间通信机制,多个处理核间必须通过加锁保护的共享内存传递数据。为此,设计一种基于软件的无锁队列作为核间通信机制,通过无锁数据结构提高软件队列的性能。当数据到达速率较低时,队列自适应地减小队列长度,从而占用较小的内存空间,进而更好地利用处理器高速缓存;当数据到达速率较高时,队列自适应地增加队列长度,以避免数据丢失。实验结果表明,在数据到达速率变化较大的实际应用场景中,该队列较FastForward、MCRingBuffer和B-Queue队列具有更高的数据处理性能。Modern commercial multicore processors lack a hardware-supported mechanism for processing inter-core communication,and multiple processing cores must pass data through locked shared memory. Therefore,a software-based lock-free queue is designed as an inter-core communication mechanism,to improve the performance of the software queue through the data structure without lock. When the data arrival rate is lower,the queue adaptively reduces the queue length,thus taking up less memory space and making better use of processor cache;When the data arrival rate is higher,the queue adaptively increases the queue length to avoid data loss. Experimental results show that this queue has higher data processing performance than FastForward,MCRingBuffer and B-Queue queues in practical application scenarios w here the data arrival rate changes greatly.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]