Safe memory reclamation for dynamic lock-free objects using atomic reads and writes

ABSTRACT

A major obstacle to the wide use of lock-free data structures, despite their many performance and reliability advantages, is the absence of a practical lock-free method for reclaiming the memory of dynamic nodes removed from dynamic lock-free objects for arbitrary reuse.The only prior lock-free memory reclamation method depends on the DCAS atomic primitive, which is not supported on any current processor architecture. Other memory management methods are blocking, require special operating system support, or do not allow arbitrary memory reuse.This paper presents the first lock-free memory management method for dynamic lock-free objects that allows arbitrary memory reuse, and does not require special operating system or hardware support. It guarantees an upper bound on the number of removed nodes not yet freed at any time, regardless of thread failures and delays. Furthermore, it is wait-free, it is only logarithmically contention-sensitive, and it uses only atomic reads and writes for its operations. In addition, it can be used to prevent the ABA problem for pointers to dynamic nodes in most algorithms, without requiring extra space per pointer or per node.

REFERENCES

• 1: Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Guy L. Steele, Jr., DCAS-based concurrent deques, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.137-146, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341817]
• 2: James H. Anderson , Mark Moir, Universal Constructions for Large Objects, IEEE Transactions on Parallel and Distributed Systems, v.10 n.12, p.1317-1332, December 1999 [doi>10.1109/71.819952]
• 3: Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165265]
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: David Detlefs , Christine H. Flood , Alex Garthwaite , Paul Martin , Nir Shavit , Guy L. Steele, Jr., Even Better DCAS-Based Concurrent Deques, Proceedings of the 14th International Conference on Distributed Computing, p.59-73, October 04-06, 2000
• 6: David L. Detlefs , Paul A. Martin , Mark Moir , Guy L. Steele, Jr., Lock-free reference counting, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.190-199, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384016]
• 7: Michael Barry Greenwald , David R. Cheriton, Nonblocking synchronization and system design, 1999
• 8: Timothy L. Harris, A Pragmatic Implementation of Non-blocking Linked-Lists, Proceedings of the 15th International Conference on Distributed Computing, p.300-314, October 03-05, 2001
• 9: 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]
• 10: Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
• 11: Maurice P. Herlihy , J. E. B. Moss, Lock-free garbage collection for multiprocessors, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.229-236, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113400]
• 12: IBM System/370 Extended Architecture, Principles of Operation. IBM Publication No. SA22-7085, 1983.
• 13: Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
• 14: Paul E. McKenney and John D. Slingwine. Read-Copy Update: Using Execution History to Solve Concurrency Problems. In Proceedings of the 11th International Conference on Parallel and Distributed Computing Systems, October 1998.
• 15: Maged M. Michael. Dynamic Lock-Free Deque Algorithm Using Single-Address Double-Word CAS. Research Report RC 22401, IBM T. J. Watson Research Center, April 2002.
• 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 , 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]
• 18: Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259442]
• 19: Mark Moir, Laziness pays!: using lazy synchronization mechanisms to improve non-blocking constructions, Distributed Computing, v.14 n.4, p.193-204, December 2001 [doi>10.1007/s004460100063]
• 20: S. Prakash , Yann Hang Lee , T. Johnson, A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap, IEEE Transactions on Computers, v.43 n.5, p.548-559, May 1994 [doi>10.1109/12.280802]
• 21: Nir Shavit and Dan Touitou. Software Transactional Memory. Distributed Computing 10(2): 99-116, 1997.
• 22: R. Kent Treiber. Systems Programing: Coping with Parallelism. Research Report RJ 5118, IBM Almaden Research Center, April 1986.
• 23: John Turek , Dennis Shasha , Sundeep Prakash, Locking without blocking: making lock based concurrent data structure algorithms nonblocking, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.212-222, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137873]
• 24: John D. Valois. Implementing Lock-Free Queues. In Proceedings of the 7th International Conference on Parallel and Distributed Computing Systems, pages 64-69, October 1994.
• 25: John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224988]