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 lockfree 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 scalable 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 storage 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. PhD thesis, 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-Åke 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.html.Google 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 lockfree 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 singleword 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 sharing and spatial 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 storage allocation: A survey and critical review. In Proceedings of the 1995 International Workshop on Memory Management, pages Google ScholarDigital Library
Index Terms
- PLDI 2004: Scalable Lock-Free Dynamic Memory Allocation
Recommendations
wfspan: Wait-free Dynamic Memory Management
Dynamic memory allocation plays a vital role in modern application programs. Modern lock-free memory allocators based on hardware atomic primitives usually provide good performance. However, threads may starve in these lock-free implementations, leading ...
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, ...
Scalable lock-free dynamic memory allocation
PLDI '04Dynamic 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, ...
Comments