Generational Reference Counting: A Reduced-Communication Distributed Storage Reclamation Scheme

Research output: Contribution to journalArticlepeer-review

Abstract

This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. Although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive. The communication overhead for generational reference counting is one message for each copy of an interprocessor reference 1989. Unlike conventional reference counting, when a reference to an object is copied no message is sent to the processor on which the object lies. A message is sent only when a reference is discarded. Unfortunately, generational reference counting shares conventional reference counting's inability to reclaim cyclical structures. In this paper, we present the generational reference counting algorithm, prove it correct, and discuss some refinements that make it more efficient. We also compare it with weighted reference counting, another distributed reference counting scheme described in the literature.

Original languageEnglish (US)
Pages (from-to)313-321
Number of pages9
JournalACM SIGPLAN Notices
Volume24
Issue number7
DOIs
StatePublished - Jun 21 1989

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Generational Reference Counting: A Reduced-Communication Distributed Storage Reclamation Scheme'. Together they form a unique fingerprint.

Cite this