Maurice Herlihy
Victor Luchangco
Abstract
Conventional dynamic memory management methods interact poorly with lock-free synchronization. In this article, we introduce novel techniques that allow lock-free data structures to allocate and free memory dynamically using any thread-safe memory management library. Our mechanisms are lock-free in the sense that they do not allow a thread to be prevented from allocating or freeing memory by the failure or delay of other threads. We demonstrate the utility of these techniques by showing how to modify the lock-free FIFO queue implementation of Michael and Scott to free unneeded memory. We give experimental results that show that the overhead introduced by such modifications is moderate, and is negligible under low contention.
- Agesen, O., Detlefs, D., Flood, C., Garthwaite, A., Martin, P., Moir, M., Shavit, N., and Steele, G. 2002. DCAS-based concurrent deques. Theory of Computing Systems 35, 349--386. (A preliminary version appeared in the Proceedings of the 12th ACM Symposium on Parallel Algorithms and Architectures, 2000.) Google Scholar
- Anderson, J. and Moir, M. 1997. Using local-spin k-exclusion algorithms to improve wait-free object implementations. Distrib. Comput. 11, 1--20. (A preliminary version appeared in Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, 1994, pp. 141--150.) Google Scholar
- Anderson, J. and Moir, M. 1999. Universal constructions for large objects. IEEE Trans. Paral. Distrib. Syst. 10, 12, 1317--1332. (A preliminary version appeared in the Proceedings of the 9th Annual International Workshop on Distributed Algorithms, 1995.) Google Scholar
- Bacon, D. F., Attanasio, C. R., Lee, H. B., Rajan, V. T., and Smith, S. 2001. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation. ACM, New York, 92--103. Google Scholar
- Detlefs, D., Flood, C., Garthwaite, A., Martin, P., Shavit, N., and Steele, G. 2000. Even better DCAS-based concurrent deques. In Proceedings of the 14th International Conference on Distributed Computing. 59--73. Google Scholar
- Detlefs, D., Martin, P., Moir, M., and Steele, G. 2001. Lock-free reference counting. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing. ACM, New York, 190--199. Google Scholar
- Dice, D. and Garthwaite, A. 2002. Mostly lock-free malloc. In Proceedings of the ACM SIGPLAN International Symposium on Memory Management. ACM, New York. Google Scholar
- Doherty, S., Groves, L., Luchangco, V., and Moir, M. 2004a. Formal verification of a practical lock-free queue algorithm. In Proceedings of the 24th Annual International Conference on Formal Techniques for Networked and Distributed Systems (FORTE). Lecture Notes in Computer Science, Vol. 3235, Springer Verlag, New York, 97--114.Google Scholar
- Doherty, S., Herlihy, M., Luchangco, V., and Moir, M. 2004b. Bringing practical lock-free synchronization to 64-bit applications. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing. ACM, New York, 31--39. Google Scholar
- Greenwald, M. 1999. Non-blocking synchronization and system design. Ph.D. dissertation, Stanford University Tech. Rep. STAN-CS-TR-99-1624, Palo Alto, Calif. Google Scholar
- Harris, T. 2001. A pragmatic implementation of non-blocking linked lists. In Proceedings of the 15th International Symposium on Distributed Computing. Google Scholar
- Herlihy, M. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. and Systems 13, 1, 124--149. Google Scholar
- Herlihy, M., Luchangco, V., Martin, P., and Moir, M. 2002. Brief announcement: Dynamic-sized lock-free data structures. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC 2002). ACM, New York, 131. Google Scholar
- Herlihy, M., Luchangco, V., and Moir, M. 2003. Space- and time-adaptive nonblocking algorithms. In Proceedings of Computing: The Australasian Theory Symposium (CATS).Google Scholar
- Lamport, L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28, 9 (Sept.), 241--248.Google Scholar
- Lea, D. 2003. Concurrency jsr-166 interest site. http://gee.cs.oswego.edu/dl/concurrency-interest/.Google Scholar
- Lynch, N. and Tuttle, M. 1989. An introduction to input/output automata. Tech. Rep. CWI-Quarterly, 2(3), Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands.Google Scholar
- Martinez, J. F. and Torrellas, J. 2002. Speculative synchronization: Applying thread-level speculation to explicitly parallel applications. In Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems. Google Scholar
- Michael, M. 2002a. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In Proceedings of the 21st Annual ACM Symposium on the Principles of Distributed Computing. ACM, New York, 21--30. Google Scholar
- Michael, M. M. 2002b. High performance dynamic lock-free hash tables and list-based sets. In Proceeding of the 14th Annual Symposium on Parallel Algorithms and Architectures. ACM, New York, 73--82. Google Scholar
- Michael, M. 2004. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE Trans. Parall. Distrib. Syst. 15, 6 (June), 491--504. Google Scholar
- Michael, M. and Scott, M. 1996. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the 15th Annual ACM Symposium on the Principles of Distributed Computing. ACM, New York, 267--276. Google Scholar
- Michael, M. and Scott, M. 1998. Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. J. Paral. Distrib. Comput. 51, 1, 1--26. Google Scholar
- Moir, M. 1997. Practical implementations of non-blocking synchronization primitives. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing. ACM, New York, 219--228. Google Scholar
- Oplinger, J., and Lam, M. S. 2002. Enhancing software reliability with speculative threads. In Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems. Google Scholar
- Printezis, T. and Detlefs, D. 2000. A generational mostly-concurrent garbage collector. In Proceedings of the 2nd International Symposium on Memory Management. ACM, New York, 143--154. Google Scholar
- Rajwar, R. and Goodman, J. R. 2002. Transactional lock-free execution of lock-based programs. In Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems. Google Scholar
- Treiber, R. 1986. Systems programming: Coping with parallelism. Tech. Rep. RJ5118, IBM Almaden Research Center.Google Scholar
- Valois, J. 1995. Lock-free linked lists using compare-and-swap. In Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing. ACM, New York, 214--222. (See http://www.cs.sunysb.edu/~valois for errata.) Google Scholar
- Weaver, D., and Germond, T. 1994. The SPARC Architecture Manual Version 9. Prentice-Hall, Englewood Cliffs, N.J. Google Scholar
Index Terms
- Nonblocking memory management support for dynamic-sized data structures
Recommendations
DCAS is not a silver bullet for nonblocking algorithm design
SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architecturesDespite years of research, the design of efficient nonblocking algorithms remains difficult. A key reason is that current shared-memory multiprocessor architectures support only single-location synchronisation primitives such as compare-and-swap (CAS) ...
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 ...
Nonblocking k-compare-single-swap
SPAA '03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architecturesThe current literature o .ers two extremes of nonblocking software synchronization support for concurrent data structure design:intricate designs of specific structures based on single-location operations such as compare-and-swap (CAS), and general-...
Reviews
Sergei Gorlatch
An in-depth discussion of a new mechanism for lock-free data structures that allow memory to be freed dynamically is presented in this paper. Lock-free algorithms do not rely on locking for thread safety, but instead use certain atomic operations (usually provided in hardware), such as compare-and-swap. While lock-free algorithms avoid many problems caused by locking, a common problem is that data structures cannot easily be shrunk because they can be used by other threads concurrently. The paper proposes a simple mechanism and application programming interface (API) to overcome this problem: prior to using a data item, threads post a guard on the item and release this guard only when they do not use the reference anymore. Before a data item can be released, a special "liberate" method is called to check that the item is not guarded by any other thread. The paper applies the presented mechanisms to two examples: a simple stack implementation, which serves as an initial illustrating example, and the lock-free first in first out (FIFO) queue algorithm of Michael and Scott. The paper provides an implementation for the proposed scheme, and presents a correctness proof for the implementation. The authors also present experimental results, documenting that the cost incurred by the presented mechanisms is negligible under low contention, and modest for high contention. In addition to the FIFO case study, a general methodology (single-word lock-free reference counting) is also presented. The paper provides a great deal of insight into the problems (and solutions) of lock-free data structures, and also provides many pointers to related work. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments