一种采用消隐技术的锁无关栈算法

Lock-free Stack Algorithm Using Elimination Technology

随着对实时系统的实时性和系统服务要求的不断提高,基于多核/多处理器硬件平台的实时系统成为发展趋势.相应的高性能实时操作系统需具有更高的硬实时性和可靠性,并避免优先级逆转、死锁.相比阻塞同步,非阻塞同步在提高实时系统性能、确定性和容错性等方面具有优势,有利于实现上述要求.设计锁无关数据结构是实现非阻塞同步的方法之一.文章介绍了锁无关算法的基本结构,提出一种采用消隐技术的锁无关栈算法及证明锁无关算法正确性的理论方法,并证明了该锁无关栈算法的正确性.实验结果表明,该算法提高了访问共享数据的执行速度,并避免了死锁、优先级逆转、低容错性等缺点.

With the increasing requirements for real-time and system services of real-time system, the real-time system based on mul- ticore/multiprocessor hardware platform becomes a development trend. Corresponding high-performance real-time operating system needs to have higher hard real-time and reliability, and avoids priority inversion, deadlock. Compared to blocking synchronization, non-blocking synchronization has the advantage in improving real-time system performance, certainty and fault tolerance, is conducive to achieving the above requirements. To design lock-free data structure is one of the methods of achieving non-blocking synchroniza- tion. This paper introduces the basic structure of lock-free algorithm, presents a lock-free stack algorithm using elimination technology and a theoretical method to prove the correctness of lock-free algorithm, and proves the correctness of the lock-free stack algorithm. Experimental results show that the algorithm improves the execution speed for accessing shared data, and avoids deadlocks, priority inversion and low fault tolerance.