A practical parallel garbage collection algorithm and its implementation

ABSTRACT

One of the major problems of list processing programs is that of garbage collection. This paper presents a new practical parallel garbage collection algorithm and its improvements, and proposes a special processor for parallel garbage collection. For the parallel garbage collection system, an urgent requirement is to reduce the the garbage collector cycle time that is defined as the total execution time for the marking and reclaiming phase. The effect of improvements discussed here reduces the garbage collector cycle time to one half of that for the original algorithm. The performance of the processor tailored for parallel garbage collection is six times faster than that of an ordinary processor, while it requires a little bit larger amount of hardware than a typical channel controller. This processor satisfies the effectiveness condition for parallelism, even if the list process node consumption rate is high, e.g. when a compiled program is executed.

REFERENCES

• 1: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 2: Philip L. Wadler, Analysis of an algorithm for real time garbage collection, Communications of the ACM, v.19 n.9, p.491-500, Sept. 1976 [doi>10.1145/360336.360338]
• 3: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , Carel S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Language Hierarchies and Interfaces, International Summer School, p.43-56, July 23-August 02, 1975
• 4: David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
• 5: Kung, H. T. and Song, S. W.: An efficient Parallel Garbage Collection System and Its Correctness Proof, Proc. of the 18th Annual Symposium on Foundation of Computer Science, 1977.
• 6: Usuki, T. et. al.: LISP Machine Implementation on Multi-Microprocessor System, Paper of the Technical Group on Computer, IECE, Japan, EC78-33, 1978, in Japanese.
• 7: Hibino, Y.: A Parallel Garbage Collection Algorithm and its Application to LISP, Paper of the Technical Group on Computer, IECE, Japan, EC78-32, 1978, in Japanese.
• 8: Chin-Liang Chang , Richard C. Lee , Richard Char-Tung Lee, Symbolic Logic and Mechanical Theorem Proving, Academic Press, Inc., Orlando, FL, 1997
• 9: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 10: Hibino, Y.: A Parallel Garbage Collection Algorithm and its Application to LISP, Trans. IECE, Japan, E63, No.1, 1980

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Algorithms, Management