改进型锁无关双端队列的设计与实现

Design and Realization of the Improved Lock-free Double-Ended Queue

高性能实时系统对系统性能、确定性和容错性有着更高的要求。非阻塞同步在任务同步方面满足要求,实现方法之一就是设计锁无关数据结构。介绍了设计锁无关数据结构算法的关键技术,通过对已有算法不足的分析提出了一种改进型的锁无关双端队列算法,介绍了对该算法的实验分析和实际应用。实验结果表明,该算法提高了访问双端队列的执行速度,并避免了多任务间同步引发的死锁、优先级逆转、低容错性等缺点。

High-performance real-time system has higher requirement for system performance, certainty and fault tolerance. Non-blgcking synchronization meets the requirement in task synchronization, one of the methods of achieving non-blocking synchronization is to design lock-free data structure. This paper introduces the key technology for designing lock-free data structure algorithm, presents an improved lock-free double-ended queue algorithm by the analysis of the existing algorithm shortage, and introduces the experimental analysis and practical application of the algorithm. Experimental results show that the algorithm improves the execution speed for accessing double-ended queue, and avoids deadlocks, priority inversion and low fault tolerance caused by multitask synchronization.