Maged M. Michael
Abstract
Dynamic memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, and programming flexibility. A lock-free memory allocator guarantees progress regardless of whether some threads are delayed or even killed and regardless of scheduling policies. This paper presents a completely lock-free memory allocator. It uses only widely-available operating system support and hardware atomic instructions. It offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to deadlock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. Also, by leveraging some high-level structures from Hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing. In addition, our allocator allows finer concurrency and much lower latency than Hoard. We use PowerPC shared memory multiprocessor systems to compare the performance of our allocator with the default AIX 5.1 libc malloc, and two widely-used multithread allocators, Hoard and Ptmalloc. Our allocator outperforms the other allocators in virtually all cases and often by substantial margins, under various levels of parallelism and allocation patterns. Furthermore, our allocator also offers the lowest contention-free latency among the allocators by significant margins.
- Sarita V. Adve and Kourosh Gharachorloo. Shared memory consistency models: A tutorial. IEEE Computer 29(12):66--76, 1996. Google Scholar
Digital Library
- Emery D. Berger. Memory Management for High-Performance Applications PhD thesis, University of Texas at Austin, August 2002. Google ScholarDigital Library
- Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson. Hoard: A calable memory allocator for multithreaded applications. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems pages 117--128, November 2000. Google ScholarDigital Library
- Bruce M. Bigler, Stephen J. Allan, and Rodney R. Oldehoeft. Parallel dynamic torage allocation. In Proceedings of the 1985 International Conference on Parallel Processing pages 272--275, August 1985.Google Scholar
- Dave Dice and Alex Garthwaite. Mostly lock-free malloc. In Proceedings of the 2002 International Symposium on Memory Management pages 269--280, June 2002. Google ScholarDigital Library
- Wolfram Gloger. Dynamic Memory Allocator Implementations in Linux System Libraries http://www.dent.med.uni-muenchen.de/~wmglo/.Google Scholar
- Maurice P. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems 13(1):124--149, January 1991. Google ScholarDigital Library
- IBM. IBM System/370 Extended Architecture, Principles of Operation 1983. Publication No. SA22-7085.Google Scholar
- IEEE. IEEE Std 1003.1, 2003 Edition 2003.Google Scholar
- Arun K. Iyengar. Dynamic Storage Allocation on a Multiprocessor PhDthei, MIT, 1992. Google ScholarDigital Library
- Arun K. Iyengar. Parallel dynamic storage allocation algorithms. In Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing pages 82--91, December 1993.Google ScholarDigital Library
- Leslie Lamport. Concurrent reading and writing. Communications of the ACM 20(11):806--811, November 1977. Google ScholarDigital Library
- Per-.Ake Larson and Murali Krishnan. Memory allocation for long-running server applications. In Proceedings of the 1998 International Symposium on Memory Management pages 176--185, October 1998. Google ScholarDigital Library
- Doug Lea. A Memory Allocator http://gee.cs.oswego.edu/dl/html/malloc.htmlGoogle Scholar
- Chuck Lever and David Boreham. Malloc() performance in a multithreaded Linux environment. In Proceedings of the FREENIX Track of the 2000 USENIX Annual Technical Conference June 2000. Google ScholarDigital Library
- Maged M. Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures pages 73--82, August 2002. Google ScholarDigital Library
- Maged M. Michael. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing pages 21--30, July 2002. Google ScholarDigital Library
- Maged M. Michael. ABA prevention using single-word instructions. Technical Report RC 23089, IBM T. J. Watson Research Center, January 2004.Google Scholar
- Maged M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Transactions on Parallel and Distributed Systems 2004. To appear. See www.research.ibm.com/people/m/michael/pubs.htm Google ScholarDigital Library
- Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing pages 267--275, May 1996. Google ScholarDigital Library
- Ori Shalev and Nir Shavit. Split-ordered lists: Lock-free extensible hash tables. In Proceedings of the Twenty-Second Annual ACM Symposium on Principles of Distributed Computing pages 102--111, July 2003. Google ScholarDigital Library
- Josep Torrellas, Monica S. Lam, and John L. Hennessy. False haring and patial locality in multiprocessor caches. IEEE Transactions on Computers 43(6):651--663, June 1994. Google ScholarDigital Library
- Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles. Dynamic torage allocation: A survey and critical review. In Proceedings of the 1995 International Workshop on Memory Management page 1--116, September 1995. Google ScholarDigital Library
Index Terms
- Scalable lock-free dynamic memory allocation
Recommendations
PLDI 2004: Scalable Lock-Free Dynamic Memory Allocation
Supplemental issueDynamic memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, ...
Scalable lock-free dynamic memory allocation
PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementationDynamic memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, ...
Mostly lock-free malloc
MSP 2002 and ISMM 2002Modern multithreaded applications, such as application servers and database engines, can severely stress the performance of user-level memory allocators like the ubiquitous malloc subsystem. Such allocators can prove to be a major scalability impediment ...
Comments