Real-time replication garbage collection

ABSTRACT

We have implemented the first copying garbage collector that permits continuous unimpeded mutator access to the original objects during copying. The garbage collector incrementally replicates all accessible objects and uses a mutation log to bring the replicas up-to-date with changes made by the mutator. An experimental implementation demonstrates that the costs of using our algorithm are small and that bounded pause times of 50 milliseconds can be readily achieved.

REFERENCES

• 1: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 2: 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]
• 3: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.157-164, June 24-28, 1991, Toronto, Ontario, Canada
• 4: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 5: Stuart K. Card , Allen Newell , Thomas P. Moran, The Psychology of Human-Computer Interaction, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1983
• 6: Eric Cooper , Scott Nettles , Indira Subramanian, Improving the performance of SML garbage collection using application-specific virtual memory management, Proceedings of the 1992 ACM conference on LISP and functional programming, p.43-52, June 22-24, 1992, San Francisco, California, United States
• 7: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 8: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 9: John R. Ellis, Kai Li, and Andrew W. Appel. Real-time Concurrent Garbage Collection on Stock Multiprocessors. Technical Report DEC-SRC-TR-25, DEC Systems Research Center, February 1988.
• 10: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.92-109, October 18-22, 1992, Vancouver, British Columbia, Canada
• 11: Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.73-82, May 19-22, 1993, San Diego, California, United States
• 12: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 13: S. Nettles , J. O''Toole , D. Gifford, Concurrent Garbage Collection of Persistent Heaps, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 14: Scott Nettles , James O'Toole , David Pierce, Replication-Based Incremental Copying Collection, Proceedings of the International Workshop on Memory Management, p.357-364, September 17-19, 1992
• 15: K. Nilsen, Garbage collection of strings and linked data structures in real time, Software—Practice & Experience, v.18 n.7, p.613-640, July 1988 [doi>10.1002/spe.4380180704]
• 16: S. C. North , J. H. Reppy, Concurrent garbage collection on stock hardware, Proc. of a conference on Functional programming languages and computer architecture, p.113-133, October 1987, Portland, Oregon, United States
• 17: James W. O'Toole. Garbage Collecting an Object Cache. Technical Report MIT/LCS/TM-485, Massachusetts Institute of Technology, April 1993. To appear.
• 18: James O''Toole , Scott Nettles, Concurrent Replication Garbage Collection: An Implementation Report, Carnegie Mellon University, Pittsburgh, PA, 1993
• 19: James W. O'Toole and Scott M. Nettles. Real-Time Replication GC: An Implementation Report. Technical Report MIT- LCS-TR-568 and CMU-CS-93-136, Massachusetts Institute of Technology and Carnegie Mellon University, 1993.
• 20: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Algorithms, Experimentation

Keywords:
concurrent collection, copying garbage collection, incremental collection, real-time garbage collection, replication