Safe Memory Reclamation for Dynamic Lock-Free Objects

Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes

M a g e d M. Michael IBM Thomas J. Watson Research Center P.O. Box 218 Yorktown Heights NY 10598 USA magedm@us.ibm.com

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 lockfree 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 A B A problem for pointers to dynamic nodes in most algorithms, without requiring extra space per pointer or per node.

1.

INTRODUCTION

A shared object is lock-free (also called non-blocking) if it guarantees that in a system with multiple threads attempting to perform operations on the object, some thread will complete an operation successfully in a finite number of system steps even with the possibility of arbitrary thread delays, provided that not all threads are delayed indefinitely [10]. By definition, lock-free objects are immune to deadlock even with thread failures and provide robust performance even when faced with inopportune thread delays. Dynamic lock-free objects have the added advantage...