Henry G. Baker
Abstract
A simple real-time garbage collection algorithm is presented which does not copy, thereby avoiding some of the problems caused by the asynchronous motion of objects. This in-place "treadmill" garbage collection scheme has approximately the same complexity as other non-moving garbage collectors, thus making it usable in a high-level language implementation where some pointers cannot be traced. The treadmill is currently being used in a Lisp system built in Ada.
- Andre, David L. Paging in Lisp Programs. M.S. Thesis, U. of Maryland, 1986.Google Scholar
- Appel, Andrew W., Ellis, John R., and Li, Kai. "Real-time concurrent garbage collection on stock multiprocessors". Proc. ACM PLDI, June 1988, 11-20. Google ScholarDigital Library
- Baker, Brenda, et al. "Algorithms for Resolving Conflicts in Dynamic Storage Allocation". J. ACM 32, 2 (April 1985), 327-343. Google ScholarDigital Library
- Baker, Henry. "List processing in real time on a serial computer". CACM 21, 4 (April 1978), 280-294. Google ScholarDigital Library
- Baker, Henry. "Garbage Collection in Ada". Ada-9X Revision Request#643, Ada Joint Program Office, Oct., 1989.Google Scholar
- Baker Henry. "Unify and Conquer (Garbage, Updating, Aliasing ..) in Functional Languages". Proc. 1990 ACM Conf. on Lisp and Functional Programming, Nice, France, June, 1990, 218-226. Google ScholarDigital Library
- Baker, Henry. "Structured Programming with Limited Private Types in Ada: Nesting is for the Soaring Eagles". ACM Ada Letters XI, 5 (July/Aug. 1991), 79-90. Google ScholarDigital Library
- Baker Henry. "CONS Should not CONS its Arguments, or, A Lazy Alloc is a Smart Alloc". Submitted to Comm. of the ACM, 1991.Google Scholar
- Baker, Henry. "Equal Rights for Functional Objects, or, The More Things Change, The More They Are the Same". Submitted to ACM TOPLAS, 1991.Google Scholar
- Beaudoing, B., and Queinnec, C. "Mark-DURING-Sweep: A Real-Time Garbage Collector". Submitted to PARLE '91.Google Scholar
- Boehm, Hans-J., and Demers, Alan. "Garbage Collection in an Uncooperative Environment". Soft. Pract. & Exper. 18, 9 (Sept. 1988), 807-820. Google ScholarDigital Library
- Brent, R. P. "Efficient Implementation of the First-Fit Strategy for Dynamic Storage Allocation". ACM TOPLAS 11, 3 (July 1989), 388-403. Google ScholarDigital Library
- Chase, David. Garbage Collection and Other Optimizations. Ph.D. Thesis, Rice Univ., Aug. 1987. Google ScholarDigital Library
- Chase, David. "Safety considerations for storage allocation optimizations". Proc. ACM PLDI, June 1988. Google ScholarDigital Library
- Hederman, Lucy. Compile Time Garbage Collection. MS Thesis, Rice U. Comp. Sci. Dept., Sept. 1988.Google Scholar
- Hickey, T., and Cohen, J. "Performance Analysis of On-the-Fly Garbage Collection". CACM 27, 11 (Nov. 1984), 1143-1154. Google ScholarDigital Library
- Knuth, Donald E. The Art of Computer Programming Vol. I: Fundamental Algorithms, 2nd Ed. Addison-Wesley, Reading, MA, 1973, 634 p. Google ScholarDigital Library
- Kung, H.T., and Song, S.W. "A Parallel Garbage Collection Algorithm and its Correctness Proof". Tech. Report, Computer Science Dept., Carnegie-Mellon Univ., May 1977, 20 p.Google Scholar
- Lieberman, H., and Hewitt, C. "A Real-Time Garbage Collector Based on the Lifetimes of Objects". CACM 26, 6 (June 1983), 419-429. Google ScholarDigital Library
- Moon, David. "Garbage collection in a large Lisp system". Proc. ACM Symp. on Lisp and Funct. Prog., 1984, 235-246. Google ScholarDigital Library
- Moss, J.E.B. "Managing Stack Frames in Smalltalk". Sigplan '87 Symp. on Interpreters and Interpretive Techniques, in Sigplan Not. 22, 7 (July 1987), 229-240. Google ScholarDigital Library
- Nilsen, K. "Garbage Collection of Strings and Linked Data Structures in Real Time". SW Prac. & Exper. 18, 7 (July 1988), 613-640. Google ScholarDigital Library
- Queinnec, Christian, et al. "Mark DURING Sweep, rather than Mark THEN Sweep". Proc. PARLE'89. Google ScholarDigital Library
- Robson, J.M. "Bounds for Some Functions Concerning Dynamic Storage Allocation". JACM 21, 3 (July 1974), 491-499. Google ScholarDigital Library
- Robson, J.M. "Storage Allocation is NP-Hard". Info. Proc. Let. 11, 3 (1980), 119-125.Google ScholarCross Ref
- White, Jon L. "Three Issues in Object-Oriented Garbage Collection". Proc. ECOOP/OOPSLA'90 Workshop on Garbage Collection, 1990.Google Scholar
- Wilson, Paul R. "Some Issues and Strategies in Heap Management and Memory Hierarchies". ACM Sigplan Not. 26, 3 (March 1991), 45-52. Google ScholarDigital Library
- Yuasa, T. "Real-Time Garbage Collection on General-Purpose Machines". J. Sys. Soft. 11 (1990), 181-198. Google ScholarDigital Library
- Zorn, Ben. Comparative performance evaluation of garbage collection algorithms. Ph.D. Thesis, UC Berkeley EECS Dept., 1989. Google ScholarDigital Library
Index Terms
- The treadmill: real-time garbage collection without motion sickness
Recommendations
Mark-copy: fast copying GC with less space overhead
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applicationsCopying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard ...
Mark-copy: fast copying GC with less space overhead
Special Issue: Proceedings of the OOPSLA '03 conferenceCopying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationAn on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Comments