Accession Number : ADA309143
Title : Correction of a Memory Management Method for Lock-Free Data Structures.
Descriptive Note : Technical rept.,
Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE
Personal Author(s) : Michael, Maged M. ; Scott, Michael L.
PDF Url : ADA309143
Report Date : DEC 1995
Pagination or Media Count : 10
Abstract : Memory reuse in link-based lock-free data structures requires special care. Many lock-free algorithms require deleted nodes not to be reused until no active pointers point to them. Also, most lock-free algorithms use the compare.and. swap atomic primitive, which can suffer from the ABA problem' (l) associated with memory reuse. Valois (3) proposed a memory management method for link-based data structures that addresses these problems. The method associates a reference count with each node of reusable memory. A node is reused only when no processes or data structures point to it, The method solves the ABA problem for acyclic link-based data structures, and allows lock-free algorithms more flexibility as nodes are not required to be freed immediately after a delete operation (e.g. dequeue, pop, delete min, etc.). However, there are race conditions that may corrupt data structure that use this method. In this report we correct these race conditions and present a corrected version of Valois's method.
Descriptors : *ALGORITHMS, *DATA MANAGEMENT, *DATA LINKS, *REUSABLE EQUIPMENT, *CORRECTIONS, DATA BASES, COUNTING METHODS, NODES, MEMORY DEVICES.
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE