Waitfree distributed memory management by Create, and Read Until Deletion (CRUD)
Wim H. Hesselink, Jan Friso Groote · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1998
The acronym CRUD represents an interface specification and an algorithm for the management of memory shared by concurrent processes. The memory cells form a directed acyclic graph. This graph is only modified by adding a new node with a list of reachable children, and by removing unreachable nodes. If memory is not full, the algorithm ensures waitfree redistribution of free nodes. It uses atomic counters for reference counting and consensus variables to ensure exclusive access. Performance is enhanced by using nondeterminacy guided by insecure knowledge. Experiments indicate that the algorithm is very suitable for multiprocessing. 1991 Mathematics Subject Classification: 68Q20, 68Q22 1991 Computing Reviews Classification System: D.m, D.2.4, E.1 Keywords and Phrases: Distributed Garbage Collection, Reference Counting, Shared Memory, Waitfree, Consensus, Terms 1 INTRODUCTION 2 1 Introduction The setting of this note is a system of concurrent sequential processes that operate on a c...