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