Remote Reference Counting: Distributed Garbage Collection with Low Communication and Computation Overhead

✍ Scribed by Dmitry Kogan; Assaf Schuster

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 443 KB
• Volume: 60
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1653

✦ Synopsis

Automatic storage management is important in distributed programming environments because programmer controlled reclamation is highly prone to errors. The main disadvantage of existing memory reclamation schemes is their high communication cost, a cost that is proportional to the number of pointer operations. We present a novel, efficient distributed garbage collection (GC) algorithm called Remote Reference Counting (RRC). This algorithm has small network traffic and computation overheads, essentially eliminating all communication when there is no active collection. The efficiency is provided by locality of RRC computations. RRC sends an average of only two to three messages from every node in order to reach global consensus on reclamation of any object. Moreover, no GC messages are sent as a result of a pointer operation. Messages for different objects can be combined and piggybacked on non-GC messages, trading promptness of garbage reclamation for additional communication efficiency. The low cost of local garbage identification is provided by a reference counting strategy which is independent of the heap size. RRC works correctly for asynchronous environments where messages may experience arbitrary delays on the way to their destinations. In addition, when applied in granularity of pages, the communication and memory overhead is not inflated when the average allocation size is small, and the memory reorganization required due to the GC operations is simplified. RRC was implemented as a WIN32 library on Windows-NT on top of a distributed shared memory system called millipage. We confirm RRC efficiency by providing performance results measured on a set of widely accepted benchmarks.