Wait-free reference counting and memory management
Wait-free reference counting and memory management
复制标题
无等待引用计数和内存管理
DOI：
10.1109/ipdps.2005.451
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
H. Sundell
中科院分区：
文献类型：
--
作者：
H. Sundell
我们提出了一个实际的无等待实现的垃圾收集计划的基础上引用计数，使用原子原始主义，这是在现代计算机系统。据我们所知，这是第一个无等待算法的引用计数方案，可以支持动态并发数据结构。由于无等待算法的所有操作都保证在有限的步骤内完成，而与其他操作的动作无关，因此新算法特别适合于执行时间保证非常重要的实时系统。我们还提出了一个自由列表的无等待算法，以支持并发分配和释放内存块。新的算法是线性化的，并兼容以前实现的非阻塞动态数据结构。
We present a practical wait-free implementation of a garbage collection scheme based on reference counting that uses atomic primitivism, which are available in modern computer systems. To the best of our knowledge, this is the first wait-free algorithm of a reference counting scheme that can support dynamic concurrent data structures. As all operations of wait-free algorithms are guaranteed to always finish in a finite number of their own steps independently of the other operations' actions, the new algorithm is especially suitable for real-time systems where execution time guarantees are of significant importance. We also present a wait-free algorithm of a free-list, for supporting concurrent allocation and freeing of memory blocks. The new algorithms are linearizable and are compatible to previous implementations of non-blocking dynamic data structures.