Scalable lock-free dynamic memory allocation

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.

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 2: Emery David Berger , Kathryn S. Mckinley, Memory management for high-performance applications, 2002
• 3: Emery D. Berger , Kathryn S. McKinley , Robert D. Blumofe , Paul R. Wilson, Hoard: a scalable memory allocator for multithreaded applications, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.117-128, November 2000, Cambridge, Massachusetts, United States
• 4: 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.
• 5: Dave Dice , Alex Garthwaite, Mostly lock-free malloc, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 6: Wolfram Gloger. Dynamic Memory Allocator Implementations in Linux System Libraries http://www.dent.med.uni-muenchen.de/~wmglo/.
• 7: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 8: IBM. IBM System/370 Extended Architecture, Principles of Operation 1983. Publication No. SA22-7085.
• 9: IEEE. IEEE Std 1003.1, 2003 Edition 2003.
• 10: Arun K. Iyengar, Dynamic storage allocation on a multiprocessor, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 11: 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.
• 12: Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
• 13: Per-Åke Larson , Murali Krishnan, Memory allocation for long-running server applications, Proceedings of the 1st international symposium on Memory management, p.176-185, October 17-19, 1998, Vancouver, British Columbia, Canada
• 14: Doug Lea. A Memory Allocator http://gee.cs.oswego.edu/dl/html/malloc.html
• 15: 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.
• 16: Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564881]
• 17: Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571829]
• 18: Maged M. Michael. ABA prevention using single-word instructions. Technical Report RC 23089, IBM T. J. Watson Research Center, January 2004.
• 19: Maged M. Michael, Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.491-504, June 2004 [doi>10.1109/TPDS.2004.8]
• 20: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 21: Ori Shalev , Nir Shavit, Split-ordered lists: lock-free extensible hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.102-111, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872049]
• 22: J. Torrellas , H. S. Lam , J. L. Hennessy, False Sharing and Spatial Locality in Multiprocessor Caches, IEEE Transactions on Computers, v.43 n.6, p.651-663, June 1994 [doi>10.1109/12.286299]
• 23: Paul R. Wilson , Mark S. Johnstone , Michael Neely , David Boles, Dynamic Storage Allocation: A Survey and Critical Review, Proceedings of the International Workshop on Memory Management, p.1-116, September 27-29, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization; Concurrency; Deadlocks; Threads

General Terms:
Algorithms, Performance, Reliability

Keywords:
async-signal-safe, availability, lock-free, malloc