Nachshon Cohen
Erez Petrank
ABSTRACT
Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are ``manual'' in the sense that the developer has to specify when nodes have retired and may be reclaimed. Retiring nodes adequately is non-trivial and often requires the modification of the original lock-free algorithm. In this paper we present an automatic lock-free reclamation scheme for lock-free data-structures in the spirit of a mark-sweep garbage collection. The proposed algorithm works with any normalized lock-free algorithm and with no need for the programmer to retire nodes or make changes to the algorithm. Evaluation of the proposed scheme on a linked-list and a hash table shows that it performs similarly to the best manual (lock-free) memory reclamation scheme.
- D. Alistarh, P. Eugster, M. Herlihy, A. Matveev, and N. Shavit. Stacktrack: An automated transactional approach to concurrent memory reclamation. In EuroSys. ACM, 2014. Google Scholar
Digital Library
- J. Auerbach, D. F. Bacon, P. Cheng, D. Grove, B. Biron, C. Gracie, B. McCloskey, A. Micic, and R. Sciampacone. Tax-and-spend: Democratic scheduling for real-time garbage collection. In EMSOFT, pages 245–254, 2008. Google ScholarDigital Library
- A. Braginsky, A. Kogan, and E. Petrank. Drop the anchor: lightweight memory management for non-blocking data structures. In SPAA, pages 33–42. ACM, 2013. Google ScholarDigital Library
- N. Cohen and E. Petrank. Efficient memory management for lock-free data structures with optimistic access. In SPAA. ACM, 2015. Google ScholarDigital Library
- D. L. Detlefs, P. A. Martin, M. Moir, and G. L. Steele Jr. Lockfree reference counting. DISC, pages 255–271, 2002. Google ScholarDigital Library
- T. L. Harris. A pragmatic implementation of non-blocking linked-lists. In DISC, pages 300–314. Springer, 2001. Google ScholarDigital Library
- T. E. Hart, P. E. McKenney, A. D. Brown, and J. Walpole. Performance of memory reclamation for lockless synchronization. JPDC, pages 1270–1285, 2007. Google ScholarDigital Library
- M. Herlihy. Wait-free synchronization. TOPLAS, 1991. Google ScholarDigital Library
- M. Herlihy and N. Shavit. The Art of Multiprocessor Programming, Revised Reprint. Elsevier, 2012. Google ScholarDigital Library
- M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking memory management support for dynamic-sized data structures. TOCS, 23(2):146–196, 2005. Google ScholarDigital Library
- M. P. Herlihy and J. E. B. Moss. Lock-free garbage collection for multiprocessors. TPDS, 1992. Google ScholarDigital Library
- R. L. Hudson and J. E. B. Moss. Sapphire: Copying GC without stopping the world. In Joint ACM-ISCOPE Conference on Java Grande, pages 48–57, 2001. Google ScholarDigital Library
- A. Kogan and E. Petrank. Wait-free queues with multiple enqueuers and dequeuers. In PPoPP, pages 223–234. ACM, 2011. Google ScholarDigital Library
- A. Kogan and E. Petrank. A methodology for creating fast wait-free data structures. In PPoPP, pages 141–150. ACM, 2012. Google ScholarDigital Library
- M. M. Michael. High performance dynamic lock-free hash tables and list-based sets. In SPAA, pages 73–82. ACM, 2002. Google ScholarDigital Library
- M. M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. TPDS, 15(6):491–504, 2004. Google ScholarDigital Library
- M. M. Michael and M. L. Scott. Correction of a memory management method for lock-free data structures. Technical report, DTIC Document, 1995. Google ScholarDigital Library
- S. Owens, S. Sarkar, and P. Sewell. A better x86 memory model: x86-tso. In Theorem Proving in Higher Order Logics, pages 391–407. Springer, 2009. Google ScholarDigital Library
- E. Petrank. Can parallel data structures rely on automatic memory managers? In MSPC, pages 1–1. ACM, 2012. Google ScholarDigital Library
- F. Pizlo, D. Frampton, E. Petrank, and B. Steensgard. Stopless: A real-time garbage collector for multiprocessors. In ISMM, pages 159–172, 2007. Google ScholarDigital Library
- F. Pizlo, E. Petrank, and B. Steensgaard. A study of concurrent real-time garbage collectors. In PLDI, pages 33–44, 2008. Google ScholarDigital Library
- F. Pizlo, L. Ziarek, P. Maj, A. L. Hosking, E. Blanton, and J. Vitek. Schism: Fragmentation-tolerant real-time garbage collection. In PLDI, pages 146–159, 2010. Google ScholarDigital Library
- H. Sundell. Wait-free reference counting and memory management. In IPDPS, pages 24b–24b. IEEE, 2005. Google ScholarDigital Library
- S. Timnat and E. Petrank. A practical wait-free simulation for lock-free data structures. In PPoPP, pages 357–368. ACM, 2014. Google ScholarDigital Library
- J. D. Valois. Lock-free linked lists using compare-and-swap. In PODC, pages 214–222. ACM, 1995. Google ScholarDigital Library
Index Terms
- Automatic memory reclamation for lock-free data structures
Recommendations
Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed ComputingMemory 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 ...
Automatic memory reclamation for lock-free data structures
OOPSLA '15Lock-free data-structures are widely employed in practice, yet designing lock-free memory reclamation for them is notoriously difficult. In particular, all known lock-free reclamation schemes are ``manual'' in the sense that the developer has to ...
Efficient Memory Management for Lock-Free Data Structures with Optimistic Access
SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and ArchitecturesLock-free data structures achieve high responsiveness, aid scalability, and avoid deadlocks and livelocks. But providing memory management support for such data structures without foiling their progress guarantees is difficult. Often, designers employ ...
Comments