Correction of a Memory Management Method for Lock-Free Data Structures
Correction of a Memory Management Method for Lock-Free Data Structures
复制标题
DOI：
--
复制
发表时间：
1995-12
期刊：
影响因子：
--
通讯作者：
Maged M. Michael;M. Scott
中科院分区：
文献类型：
--
作者：
Maged M. Michael;M. Scott
基于链路的无锁数据结构中的内存重用需要特别注意。许多无锁算法要求删除的节点在没有活动指针指向它们之前不能被重用。此外，大多数无锁算法使用compare＿and＿swap原子原语，这可能会受到与内存重用相关的‘’ ABA问题‘’‘’的影响。Valois \cite{Valois-thesis-1995}为基于链接的数据结构提出了一种内存管理方法来解决这些问题。该方法将引用计数与可重用内存的每个节点关联起来。只有当没有进程或数据结构指向节点时，节点才会被重用。该方法解决了基于非循环链接的数据结构的ABA问题，并且允许无锁算法更灵活，因为节点不需要在删除操作（例如dequeue， pop， delete min等）后立即被释放。但是，存在可能破坏使用此方法的数据结构的竞争条件。在本报告中，我们修正了这些竞态条件，并提出了瓦卢瓦方法的修正版本。
Memory reuse in link-based lock-free data structures requires special care. Many lock-free algorithms require deleted nodes not to be reused until no active pointers point to them. Also, most lock-free algorithms use the compare_and_swap atomic primitive, which can suffer from the ``ABA problem'''' associated with memory reuse. Valois ~\cite{Valois-thesis-1995} proposed a memory management method for link-based data structures that addresses these problems. The method associates a reference count with each node of reusable memory. A node is reused only when no processes or data structures point to it. The method solves the ABA problem for acyclic link-based data structures, and allows lock-free algorithms more flexibility as nodes are not required to be freed immediately after a delete operation (e.g.\ dequeue, pop, delete min, etc.). However, there are race conditions that may corrupt data structure that use this method. In this report we correct these race conditions and present a corrected version of Valois''s method.