US 8,019,785 B2 · Space-and time-adaptive nonblocking algorithms

Abstract

We explore techniques for designing nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption both adapt to various measures, rather than being based on predefined worst-case scenarios, and that cannot be prevented from future memory reclamation by process failures. These techniques can be implemented using widely available hardware synchronization primitives. We present our techniques in the context of solutions to the well-known Collect problem. We also explain how our techniques can be exploited to achieve other results with similar properties; these include long-lived renaming and dynamic memory management for nonblocking data structures.

Claims12

Dependent claims

A non-transitory, computer readable storage medium, storing program code executable on one or more processors to instantiate a dynamically sizable data structure;

wherein accesses to the shared data structure are lock-free;
wherein instantiation of the shared data structure does not require a known bound on the number of processes that will ever access the shared data structure;
wherein the amount of storage consumed by the shared data structure is adaptive independent of any historical maximum value associated with the shared data structure;
and
wherein failure of a thread that accesses the shared data structure does not prevent all future reclamation of the storage consumed by the shared data structure by a non-failed thread;
wherein the adaptivity of the amount of storage consumed by the shared data structure is achieved through explicit reclamation and without resorting to garbage collection.

3 more elements

Dependencies are inferred from the claim text.

Space-and time-adaptive nonblocking algorithms

Life of this patent

Space-and time-adaptive nonblocking algorithms

Life of this patent

Abstract

Claims12