An Algorithm for Garbage Collection in Multicomputer Systems

Abstract

There is widespread interest in multicomputer parallelism. Functional languages with their inherent parallelism can form a basis for programming these machines. These languages dynamically allocate memory, objects are created when required and eventually objects may lose links with active objects and become unreachable garbage. The process of recovering these inactive objects is called garbage collection. Garbage collection in a multicomputer system has to manage objects in physically separated memories. This introduces consistency and synchronization problems with the shared data. The development of an algorithm for garbage collection in a multicomputer system is reported. A description of the algorithm is presented. The design of the simulator and the simulation experiments are presented. The application of Petri nets to the modelling of this algorithm is discussed. Verification of some properties of this algorithm using the invariants of the Petri net model are presented.