快速时代回收:一种针对无锁编程的快速垃圾回收算法

Fast Epoch: a Fast Memory Reclamation Algorithm for Lock-free Programming

在多核、众核时代,并行编程模型如软件事务内存、无锁编程等成为研究热点.无锁编程技术使得多个线程无需加锁即可并发访问同一个数据结构成为可能,该技术已被证明能够有效地提升程序的性能.实现无锁算法的一个关键的技术是垃圾回收.时代回收算法是一种高效、易用的垃圾回收算法,但其回收速度受制于最慢的线程,在极端情况下该算法完全停滞,难以在实际情况下使用.本文针对时代回收算法的不足,在其基础上提出了快速时代回收算法,新算法的回收速度与最快线程保持一致,在测试中回收成功率为100%,实验证明快速时代回收算法一种适用于无锁编程的快速实用的垃圾回收算法.

In multi-core and many-core age, parallel programming model, such as software transactional memory and lock-free pro- gramming becomes a research hotspot. Lock-free programming technology allows multiple threads in a process access a data structure concurrently without locking. Lock-free programming have been proven to effectively improve the performance of concurrent pro- grams. One of its key technology is memory reclamation. Epoch-based algorithm is an efficient, easy to use memory reclamation al- gorithm, but it is restricted by the speed of the slowest thread. In extreme circumstances the algorithm is completely stall, which make it impractical in real situation. In this paper, fast epoch algorithm is proposed, which is based on epoch-based algorithm and its reclamation speed is the same the fast thread. In the test, fast epoch algorithm has 100% reclamation success rate, and experiments shows that fast epoch algorithm is an fast and practical memory reclamation algorithm for lock-free programming.