论文标题
通用的无等待记忆填海
Universal Wait-Free Memory Reclamation
论文作者
论文摘要
在本文中，我们提出了一种通用的内存填海方案，即无需候补时代（WFE），以在无候补的并发数据结构中删除的内存块。 WFE的关键创新是完全没有等待。尽管某些先前的技术为某些数据结构提供了相似的保证，但它们缺乏对任意候补数据结构的支持。因此，开发人员通常被迫将其无锁定的危险指针或（可能阻止）基于时期的记忆填海结合。由于这两种方案都提供了较弱的进度保证，因此它们基本上没收了无需候补数据结构的强大进度保证。尽管制定原始的危险指针计划或基于时期的回收似乎完全不可行，但我们通过最新的（无锁）危害时代计划实现了这一目标，我们将其扩展为保证候补。由于这一扩展是不平凡的，我们讨论了与普遍的无候补记忆填海建造有关的所有挑战。 WFE可以在无处不在的X86_64和AARCH64（ARM）架构上实现。它的API主要与危险指针兼容，这可以轻松将现有数据结构转换为WFE。我们的实验评估表明，WFE的性能接近基于时期的回收，几乎与原始危害时代方案相匹配，同时提供了更强的无候补进度保证。
In this paper, we present a universal memory reclamation scheme, Wait-Free Eras (WFE), for deleted memory blocks in wait-free concurrent data structures. WFE's key innovation is that it is completely wait-free. Although some prior techniques provide similar guarantees for certain data structures, they lack support for arbitrary wait-free data structures. Consequently, developers are typically forced to marry their wait-free data structures with lock-free Hazard Pointers or (potentially blocking) epoch-based memory reclamation. Since both these schemes provide weaker progress guarantees, they essentially forfeit the strong progress guarantee of wait-free data structures. Though making the original Hazard Pointers scheme or epoch-based reclamation completely wait-free seems infeasible, we achieved this goal with a more recent, (lock-free) Hazard Eras scheme, which we extend to guarantee wait-freedom. As this extension is non-trivial, we discuss all challenges pertaining to the construction of universal wait-free memory reclamation. WFE is implementable on ubiquitous x86_64 and AArch64 (ARM) architectures. Its API is mostly compatible with Hazard Pointers, which allows easy transitioning of existing data structures into WFE. Our experimental evaluations show that WFE's performance is close to epoch-based reclamation and almost matches the original Hazard Eras scheme, while providing the stronger wait-free progress guarantee.
