论文标题
同时进行的参考计数和资源管理在无等待的恒定时间中
Concurrent Reference Counting and Resource Management in Wait-free Constant Time
论文作者
论文摘要
实施并发程序时的一个常见问题是有效地保护进程阅读之间的不安全种族，然后使用资源（例如，内存块，文件描述符或网络连接）以及其他同时覆盖并破坏相同资源的过程。这种读取式种族可以通过锁或无锁的解决方案（例如危险点或阅读拷贝）（RCU）保护。 在本文中，我们描述了一种保护阅读毁灭性种族的方法，其预期恒定时间开销，$ O（p^2）$ space和$ o（p^2）$延迟破坏，只有单个单词原子记忆操作（读取，写入和CAS）。它基于一个带有四个原语的接口，一个以保护访问权限的获取释放对，以及一对退休对，以延迟破坏性直至安全。我们将其称为“收购休息接口”。使用收购退休界面，我们为三种常见用例开发了简单的实现：（1）记忆填充堆栈和队列的应用，（2）参考计数对象，以及（3）对象通过拥有移动，副本和破坏的所有权来管理。前两个结果显着改善了先前的结果，第三个应用程序是原始的。重要的是，所有操作都期望持续的时间开销。
A common problem when implementing concurrent programs is efficiently protecting against unsafe races between processes reading and then using a resource (e.g., memory blocks, file descriptors, or network connections) and other processes that are concurrently overwriting and then destructing the same resource. Such read-destruct races can be protected with locks, or with lock-free solutions such as hazard-pointers or read-copy-update (RCU). In this paper we describe a method for protecting read-destruct races with expected constant time overhead, $O(P^2)$ space and $O(P^2)$ delayed destructs, and with just single word atomic memory operations (reads, writes, and CAS). It is based on an interface with four primitives, an acquire-release pair to protect accesses, and a retire-eject pair to delay the destruct until it is safe. We refer to this as the acquire-retire interface. Using the acquire-retire interface, we develop simple implementations for three common use cases: (1) memory reclamation with applications to stacks and queues, (2) reference counted objects, and (3) objects manage by ownership with moves, copies, and destructs. The first two results significantly improve on previous results, and the third application is original. Importantly, all operations have expected constant time overhead.
