Remote reference counting: Distributed garbage collection with low communication and computation overhead

Automatic storage management is important in distributed programming enviro nments 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 o perations. We present a novel, efficient distributed garbage collection (GC ) algorithm called Remote Reference Counting (RRC). This algorithm has smal l network traffic and computation overheads, essentially eliminating all co mmunication 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 o peration. Messages for different objects can be combined and piggybacked on non-CC messages, trading promptness of garbage reclamation for additional communication efficiency. The low cost of local garbage identification is p rovided by a reference counting strategy which is independent of the heap s ize. RRC works correctly for asynchronous environments where messages may e xperience arbitrary delays on the way to their destinations. In addition, w hen applied in granularity of pages, the communication and memory overhead is not inflated when the average allocation size is small, and the memory r eorganization required due to the CC operations is simplified. RRC was impl emented as a WIN32 library on Windows-NT on top of a distributed shared mem ory system called MILLIPAGE. We confirm RRC efficiency by providing perform ance results measured on a set of widely accepted benchmarks. (C) 2000 Acad emic Press.