Name
Title | ||
|---|---|---|
Brief announcement: resettable objects and efficient memory reclamation for concurrent algorithms |
Abstract | ||
|---|---|---|
We present a new technique for reclaiming memory in concurrent shared memory algorithms with n asynchronous processes. Our methodology can be applied in the same settings as hazard pointers [10], but provides better worst-case guarantees: For the same tasks for which hazard pointers have expected constant amortized complexity, our technique guarantees constant time in the worst-case. We use our technique to implement efficient randomized long-lived test-and-set (TAS) objects from registers, based on known constructions of randomized one-time TAS objects [2, 9]. One of our constructions uses O(n) space (which is optimal), and the reset() and Test&Set() operations have expected step complexity O(log log n) against the oblivious adversary. We also present a general method of augmenting shared objects with a reset() operation which can be used to reset the object into its initial state at any time. In many cases the transformation is optimal with respect to the time complexity of the resulting object. E.g., an object implemented from m registers can be augmented with a reset() operation which has O(1) time complexity and without affecting the asymptotic time complexity of other operations; the resulting object uses O(n2 ⋅ m) unbounded registers. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2484239.2484286 | PODC |
Keywords | Field | DocType |
efficient memory reclamation,step complexity o,hazard pointer,resettable object,brief announcement,constant time,concurrent shared memory algorithm,asymptotic time complexity,constant amortized complexity,resulting object,concurrent algorithm,time complexity,new technique,randomized one-time tas object,shared memory,test and set,memory management | Asynchronous communication,Shared memory,Computer science,Amortized analysis,Parallel computing,Algorithm,Hazard pointer,Memory management,Test-and-set,Memory map,Distributed shared memory,Distributed computing | Conference |
Citations | PageRank | References |
4 | 0.48 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zahra Aghazadeh | 1 | 16 | 2.39 |
| Wojciech Golab | 2 | 210 | 17.22 |
| Philipp Woelfel | 3 | 432 | 38.40 |