{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:43:53Z","timestamp":1782971033577,"version":"3.54.5"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2005,5]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1062247.1062249","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"146-196","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":91,"title":["Nonblocking memory management support for dynamic-sized data structures"],"prefix":"10.1145","volume":"23","author":[{"given":"Maurice","family":"Herlihy","sequence":"first","affiliation":[{"name":"Brown University, Providence, RI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor","family":"Luchangco","sequence":"additional","affiliation":[{"name":"Sun Microsystems Laboratories, Burlington, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Martin","sequence":"additional","affiliation":[{"name":"Sun Microsystems Laboratories, Burlington, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Moir","sequence":"additional","affiliation":[{"name":"Sun Microsystems Laboratories, Burlington, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/341800.341817"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198073"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.819952"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation. ACM","author":"Bacon D. F.","unstructured":"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. 10.1145\/378795.378819 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. 10.1145\/378795.378819"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 14th International Conference on Distributed Computing. 59--73","author":"Detlefs D.","unstructured":"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 . 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."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing. ACM","author":"Detlefs D.","unstructured":"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. 10.1145\/383962.384016 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. 10.1145\/383962.384016"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the ACM SIGPLAN International Symposium on Memory Management. ACM","author":"Dice D.","unstructured":"Dice , D. and Garthwaite , A . 2002. Mostly lock-free malloc . In Proceedings of the ACM SIGPLAN International Symposium on Memory Management. ACM , New York. 10.1145\/512429.512451 Dice, D. and Garthwaite, A. 2002. Mostly lock-free malloc. In Proceedings of the ACM SIGPLAN International Symposium on Memory Management. ACM, New York. 10.1145\/512429.512451"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 24th Annual International Conference on Formal Techniques for Networked and Distributed Systems (FORTE). Lecture Notes in Computer Science","volume":"3235","author":"Doherty S.","unstructured":"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. 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."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing. ACM","author":"Doherty S.","unstructured":"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. 10.1145\/1011767.1011773 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. 10.1145\/1011767.1011773"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 15th International Symposium on Distributed Computing.","author":"Harris T.","year":"2001","unstructured":"Harris , T. 2001 . A pragmatic implementation of non-blocking linked lists . In Proceedings of the 15th International Symposium on Distributed Computing. Harris, T. 2001. A pragmatic implementation of non-blocking linked lists. In Proceedings of the 15th International Symposium on Distributed Computing."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/114005.102808"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC 2002","author":"Herlihy M.","year":"1825","unstructured":"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. 10.1145\/57 1825 .571847 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. 10.1145\/571825.571847"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of Computing: The Australasian Theory Symposium (CATS).","author":"Herlihy M.","unstructured":"Herlihy , M. , Luchangco , V. , and Moir , M . 2003. Space- and time-adaptive nonblocking algorithms . In Proceedings of Computing: The Australasian Theory Symposium (CATS). Herlihy, M., Luchangco, V., and Moir, M. 2003. Space- and time-adaptive nonblocking algorithms. In Proceedings of Computing: The Australasian Theory Symposium (CATS)."},{"key":"e_1_2_1_15_1","first-page":"241","article-title":"How to make a multiprocessor computer that correctly executes multiprocess programs","volume":"9","author":"Lamport L.","year":"1979","unstructured":"Lamport , L. 1979 . How to make a multiprocessor computer that correctly executes multiprocess programs . IEEE Trans. Comput. C-28 , 9 ( Sept. ), 241 -- 248 . Lamport, L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28, 9 (Sept.), 241--248.","journal-title":"IEEE Trans. Comput. C-28"},{"key":"e_1_2_1_16_1","unstructured":"Lea D. 2003. Concurrency jsr-166 interest site. http:\/\/gee.cs.oswego.edu\/dl\/concurrency-interest\/.  Lea D. 2003. Concurrency jsr-166 interest site. http:\/\/gee.cs.oswego.edu\/dl\/concurrency-interest\/."},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. CWI-Quarterly, 2(3), Centrum voor Wiskunde en Informatica","author":"Lynch N.","year":"1989","unstructured":"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 . 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."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems. 10","author":"Martinez J. F.","unstructured":"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. 10 .1145\/605397.605400 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. 10.1145\/605397.605400"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 21st Annual ACM Symposium on the Principles of Distributed Computing. ACM","author":"Michael M.","year":"2002","unstructured":"Michael , M. 2002 a. 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. 10.1145\/57 1825.571829 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. 10.1145\/571825.571829"},{"key":"e_1_2_1_20_1","volume-title":"Proceeding of the 14th Annual Symposium on Parallel Algorithms and Architectures. ACM","author":"Michael M. M.","year":"2002","unstructured":"Michael , M. M. 2002 b. 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. 10.1145\/564870.564881 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. 10.1145\/564870.564881"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.8"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 15th Annual ACM Symposium on the Principles of Distributed Computing. ACM","author":"Michael M.","unstructured":"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. 10.1145\/248052.248106 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. 10.1145\/248052.248106"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1446"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing. ACM","author":"Moir M.","year":"1997","unstructured":"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. 10.1145\/259380.259442 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. 10.1145\/259380.259442"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems. 10","author":"Oplinger J.","unstructured":"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. 10 .1145\/605397.605417 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. 10.1145\/605397.605417"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2nd International Symposium on Memory Management. ACM","author":"Printezis T.","unstructured":"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. 10.1145\/362422.362480 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. 10.1145\/362422.362480"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems. 10","author":"Rajwar R.","unstructured":"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. 10 .1145\/605397.605399 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. 10.1145\/605397.605399"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing. ACM","author":"Valois J.","year":"1995","unstructured":"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.) 10.1145\/224964.224988 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.) 10.1145\/224964.224988"},{"key":"e_1_2_1_30_1","unstructured":"Weaver D. and Germond T. 1994. The SPARC Architecture Manual Version 9. Prentice-Hall Englewood Cliffs N.J.   Weaver D. and Germond T. 1994. The SPARC Architecture Manual Version 9. Prentice-Hall Englewood Cliffs N.J."}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1062247.1062249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:00:20Z","timestamp":1672243220000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1062247.1062249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["10.1145\/1062247.1062249"],"URL":"https:\/\/doi.org\/10.1145\/1062247.1062249","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]},"assertion":[{"value":"2005-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}