Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation

• US 20040107227A1
• Filed: 12/03/2002
• Published: 06/03/2004
• Est. Priority Date: 12/03/2002
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Michael, Maged M.
• Application Number:
  US10/308,449
• Publication Number:
  US 20040107227A1
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for safe memory reclamation for dynamic lock-free data structures employs a plurality of shared pointers, called hazard pointers, that are associated with each participating thread. Hazard pointers either have null values or point to nodes that may potentially be accessed by a thread without further verification of the validity of the local references used in their access. Each hazard pointer can be written only by its associated thread, but can be read by all threads. The method requires target lock-free algorithms to guarantee that no thread can access a dynamic node at a time when it is possibly unsafe (i.e., removed from the data structure), unless one or more of its associated hazard pointers has been pointing to the node continuously, from a time when it was not removed.

Claims

1. A computer-implemented method for managing a shared, lock-free dynamic data structure in a multithreaded operating environment, comprising the steps of:

setting a hazard pointer to an address of a portion of a data structure to be removed;

removing the portion of the data structure; and

ensuring that memory associated with the removed portion of the data structure is freed only when the hazard pointer no longer points to the removed portion of the data structure.

2. The computer-implemented method of claim 1, wherein each thread sharing the dynamic data structure has at least one hazard pointer.

3. The computer-implemented method of claim 1, wherein a thread setting the hazard pointer is different from a thread freeing the portion of the data structure.

4. The computer-implemented method of claim 3, wherein the thread setting the hazard pointer ensures that it accesses a portion of the data structure to be removed, only if the hazard pointer continuously points to the portion of the data structure to be removed from a time when it was not removed.

5. The computer-implemented method of claim 1, wherein the data structure is a linked-list data structure.

6. The computer-implemented method of claim 1, wherein the portion of the data structure is a node.

7. The computer-implemented method of claim 6, wherein the linked-list data structure implements one of a stack, a queue, a heap, and a hash table.

8. The computer-implemented method of claim 1, further including the step of scanning the removed portions of the data structure to determine ones of the removed portions that can be safely freed.

9. The computer-implemented method of claim 8, wherein the removed portions of the data structure are scanned only when the number of removed portions exceeds a predetermined value.

10. The computer-implemented method of claim 8, wherein the removed portions of the data structure are scanned only when the number of removed portions equals or exceeds a value proportionate to the number of threads.

11. The computer-implemented method of claim 8, wherein the scanning step includes:

creating a sorted list of hazard pointers; and

searching the sorted list of hazard pointers to determine matches between any of the hazard pointers and the removed portions.

12. The computer-implemented method of claim 11, wherein the searching step is performed using a binary search.

13. The computer-implemented method of claim 12, wherein the created sorted list of hazard pointers includes only non-null hazard pointers.

14. The computer-implemented method of claim 1, wherein hazard pointers associated with threads not using the data structure are set to null.

15. The computer-implemented method of claim 1, wherein only single-word read and write operations are used for memory access.

16. The computer-implemented method of claim 1, wherein only single-word operations are used for memory access.

17. The computer-implemented method of claim 1, wherein operations on the data structure are guaranteed to proceed concurrently without any one of the operations preventing other operations from completing indefinitely.

18. The computer-implemented method of claim 1, wherein freed portions of the data structure are freed for arbitrary reuse.

19. A program storage device readable by a machine, tangibly embodying a program of instructions executable on the machine to perform method steps for managing a shared dynamic data structure in a multithreaded operating environment, the method steps comprising:

setting a hazard pointer to an address of a portion of a data structure to be removed;

removing the portion of the data structure; and

ensuring that memory associated with the removed portion of the data structure is freed only when the hazard pointer no longer points to the removed portion of the data structure.