Efficient multi-word lock-free synchronization algorithm based on hardware CAS primitive

Lock-based synchronization may become a performance bottleneck which limits the concurrency in shared-memory machines. In order to solve this problem, a lock-free synchronization algorithm based on hardware CAS (Compare And Swap) primitive is proposed in this paper. In the proposed method, compare and swap instruction provided by underlying processor is used to implement non-blocking synchronization for shared variables in multi-core or multi-thread environment. Global mark value is introduced to avoid performance overhead caused by bits reservation of memory word in the traditional design, and guarantee the consistency. Theoretical analysis and experimental results show that the proposed method can efficiently support arbitary multi-word CAS synchronization, improve the concurrent access performance and provide good scalability.