作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2018, Vol. 44 ›› Issue (8): 315-320. doi: 10.19678/j.issn.1000-3428.0050269

• 开发研究与工程应用 • 上一篇    

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

王俊昌 1,2,王振 1,2,付雄 1,2   

  1. 1.南京邮电大学 计算机学院,南京 210023; 2.江苏省大数据安全与智能处理重点实验室,南京 210023
  • 收稿日期:2018-01-24 出版日期:2018-08-15 发布日期:2018-08-15
  • 作者简介:王俊昌(1982—),男,讲师、博士,主研方向为高性能并行程序设计;王振,本科生;付雄,教授、博士。
  • 基金资助:

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

FIFO Queue Algorithm Based on Lock-free Data Structure

WANG Junchang 1,2,WANG Zhen 1,2,FU Xiong 1,2   

  1. 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,China
  • Received:2018-01-24 Online:2018-08-15 Published:2018-08-15

摘要:

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

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

Abstract:

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 where the data arrival rate changes greatly.

Key words: lock-free data structure, multi-core processing, pipeline parallelism, self-adjustment, CPU core-to-core communication

中图分类号: