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

FIFO Queue Algorithm Based on Lock-free Data Structure

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