论文标题
NBR:基于中和的开垦
NBR: Neutralization Based Reclamation
论文作者
论文摘要
安全的记忆开垦(SMR)算法在界限未宣称的记忆与开垦速度之间的权衡。危险指针(HP)算法始终绑定了未确定的内存,但往往比其他方法慢。基于时期的开垦(EBR)算法更快,但不绑定记忆回收。其他算法遵循混合方法,需要特殊的编译器或硬件支持,更改以记录布局和/或广泛的代码更改。并非所有SMR算法都可以用于回收所有数据结构的内存。 我们提出了一种新的基于中和的填隙(NBR)算法,该算法比最著名的EBR算法更快,并实现了有限的未确定记忆。当与非阻滞操作系统(OS)内核一起使用时,它是非障碍物的,并且仅需要原子读,写入和CAS。 NBR很容易与许多不同的数据结构一起使用,在大多数情况下,需要类似的推理和程序员努力与两步锁定。 NBR是使用OS信号和参与线程之间的轻巧的握手机制实施的,以确定何时可以安全收回记录。基于锁定的二进制搜索树和懒惰链接列表的实验表明,NBR的表现明显优于许多最先进的回收算法。在树中,NBR比下一个最佳算法要快,黛布拉高达38%,HP高达17%。并且,在列表中,NBR的速度分别比Debra和HP快15%和243%。
Safe memory reclamation (SMR) algorithms suffer from a trade-off between bounding unreclaimed memory and the speed of reclamation. Hazard pointer (HP) based algorithms bound unreclaimed memory at all times, but tend to be slower than other approaches. Epoch based reclamation (EBR) algorithms are faster, but do not bound memory reclamation. Other algorithms follow hybrid approaches, requiring special compiler or hardware support, changes to record layouts, and/or extensive code changes. Not all SMR algorithms can be used to reclaim memory for all data structures. We propose a new neutralization based reclamation (NBR) algorithm that is faster than the best known EBR algorithms and achieves bounded unreclaimed memory. It is non-blocking when used with a non-blocking operating system (OS) kernel, and only requires atomic read, write and CAS. NBR is straightforward to use with many different data structures, and in most cases, require similar reasoning and programmer effort to two-phased locking. NBR is implemented using OS signals and a lightweight handshaking mechanism between participating threads to determine when it is safe to reclaim a record. Experiments on a lock-based binary search tree and a lazy linked list show that NBR significantly outperforms many state of the art reclamation algorithms. In the tree NBR is faster than next best algorithm, DEBRA by upto 38% and HP by upto 17%. And, in the list NBR is 15% and 243% faster than DEBRA and HP, respectively.