Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way
Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way
复制标题
为无锁数据结构回收内存：必须有更好的方法
DOI：
10.1145/2767386.2767436
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Trevor Brown
中科院分区：
文献类型：
--
作者：
Trevor Brown
对于顺序或基于锁定的数据结构的内存填海通常很容易。但是，无锁数据结构的记忆填充是一个重大挑战。诸如垃圾收集之类的自动技术效率低下或使用锁，非自动技术要么具有高开销，要么不适用于许多合理简单的数据结构。例如，当危险指针（最常见的非自动技术之一）应用于许多自然无锁的数据结构时，可能会出现微妙的问题。迄今为止最有效的非自动化技术是基于时期的开垦（EBR），它允许无界的对象的数量在没有界限的情况下增长，因为一个缓慢或崩溃的过程可以防止所有其他过程回收记忆。我们开发了EBR的更有效，分布式的变体，可以解决此问题。它基于信号，该信号由许多操作系统（例如Linux和Unix）提供。我们的新方案在无锁的数据结构上进行O（1）每个高级操作的摊销步骤，并且每次从数据结构中删除对象时，在最坏情况下，O（1）步骤。在任何时候，o（mn2）对象正在等待释放，其中$ n $是流程的数量，而m对于大多数数据结构而言是一个小常数。实验表明，我们的方案的开销非常低：在许多线程计数，操作混合和争论水平上，平衡的二进制搜索树平均为10％，最糟糕的是28％。我们的计划还表现出色的危险指针的实施平均为75％。通常，内存填海代码将紧密编织成无锁的数据结构代码。为了改善模块化并促进不同记忆填海方案的比较，我们还引入了高度灵活的抽象。它允许程序员通过更改单个代码线来轻松互换方案，以便与几乎没有开销的开垦，对象合并，分配和交易。
Memory reclamation for sequential or lock-based data structures is typically easy. However, memory reclamation for lock-free data structures is a significant challenge. Automatic techniques such as garbage collection are inefficient or use locks, and non-automatic techniques either have high overhead, or do not work for many reasonably simple data structures. For example, subtle problems can arise when hazard pointers, one of the most common non-automatic techniques, are applied to many natural lock-free data structures. Epoch based reclamation (EBR), which is by far the most efficient non-automatic technique, allows the number of unreclaimed objects to grow without bound, because one slow or crashed process can prevent all other processes from reclaiming memory. We develop a more efficient, distributed variant of EBR that solves this problem. It is based on signaling, which is provided by many operating systems, such as Linux and UNIX. Our new scheme takes O(1) amortized steps per high-level operation on the lock-free data structure and O(1) steps in the worst case each time an object is removed from the data structure. At any point, O(mn2) objects are waiting to be freed, where $n$ is the number of processes and m is a small constant for most data structures. Experiments show that our scheme has very low overhead: on average 10%, and at worst 28%, for a balanced binary search tree over many thread counts, operation mixes and contention levels. Our scheme also outperforms a highly efficient implementation of hazard pointers by an average of 75%. Typically, memory reclamation code is tightly woven into lock-free data structure code. To improve modularity and facilitate the comparison of different memory reclamation schemes, we also introduce a highly flexible abstraction. It allows a programmer to easily interchange schemes for reclamation, object pooling, allocation and deallocation with virtually no overhead, by changing a single line of code.