Garbage collection for functional languages in a distributed system
J. Dana Eckart · SMARTech Repository (Georgia Institute of Technology) · 1987
Garbage collection is a helpful facility which is provided by many applicative languages such as Prolog, SISAL, FP, and Lisp. While these, and other, languages provide easy recognition of actions which may be executed in parallel, the garbage collection algorithms which have been used for single machine environments become significantly more inefficient in multi-machine environments. Thus, in order to make effective use of these languages, more efficient algorithms for collecting inter-machine structures is needed. Reference marking is the algorithm which was developed to meet these needs. It takes advantage of the semantics of applicative languages allowing each parallel action to be responsible for collecting any discarded structures which it was responsible for creating. Simulation results comparing the performance of reference marking with other distributed garbage collection algorithms are given. A variety of problem types and sizes are examined to determine the effects of particular styles of computation on each of the garbage collection algorithms. The results gathered demonstrate the usefulness of the reference marking algorithm in both uni- and multi-machine systems.