Abstract
We have demonstrated a practical design for memory management in a concurrent system running on stack hardware. Under our modification of Brooks' forwarding pointers, the only runtime costs, owing to storage reclamation, incurred by user processes are an extra level of indirection when accessing object contents and the need to scavenge when updating mutable objects. Therefore, we believe that our system can successfully off-load much of the cost of memory management to, otherwise unused, dead-time.
Beyond Pegasus, this work has application to any system based on lightweight processes and heap allocation. We believe the ease with which the memory management system was implemented is a testimony to the soundness of Pegasus as a foundation for building programming environments.
Consultant.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barth, J. “Shifting Garbage Collection Overhead to Compile Time,” Communications of the ACM, V. 20, Nr. 7, July 1977, pp. 513–518.
Baker, H.G. “List Processing in Real Time on a Serial Computer,” Communications of the ACM, V. 21, Nr. 4, April 1978, pp. 280–294.
Ben-Ari, M. “Algorithms for On-the-fly Garbage Collection,” ACM TOPLAS, V. 6, Nr. 3, July, 1984, pp. 333–344.
Ballard, S., Shirron, S. “The Design and Implementation of VAX/Smalltalk-80,” in Smalltalk-80: Bits of History, Words of Advice, G. Krasner, ed., Addison-Wesley, Reading, Mass., 1983, pp. 127–150.
Brooks, R.A. “Trading Data Space for Reduced Time and Code Space in Real Time Garbage Collection on Stock Hardware,” Conference Record of the 1984 ACM Symposium on LISP and Functional Programming, Aug. 6–8, 1984, pp. 256–262.
Cohen, J. “Garbage Collection of Linked Data Structures,” Computing Surveys, V. 13, Nr. 3, September 1981, pp. 340–367.
Clark, Douglas W., and Green, C. Cordell. “An Empirical Study of List Structure in Lisp,” Communications of the ACM, V. 20, Nr. 2, pp. 78–87.
Dawson, J.L. “Improved Effectiveness From a Real Time Lisp Garbage Collector,” Conference Record of the 1982 ACM Symposium on Lisp and Functional Programming, August 15–18, 1982, pp. 159–167.
Deutsch, L.P., Bobrow, D. “An Efficient, Incremental, Automatic Garbage Collector,” Communications of the ACM, V. 19, Nr. 9, September 1976, pp. 522–526.
Dijkstra, E.W., Lamport, L., et al. “On-the-Fly Garbage Collection: An Exercise in Cooperation,” Communications of the ACM, V. 21, Nr. 11, November 1978, pp. 966–975.
Fenichel, R., Yochelson, J. “A LISP Garbage Collector for Virtual Memory Computer Systems,” Communications of the ACM, V. 12, Nr. 11, November 1969, pp. 611–612.
Gabriel, R.P. Performance and Evaluation of Lisp Systems, The MIT Press, Cambridge, Mass., 1985.
Goldberg, A. Smalltalk-80: The Language and Its Implementation, Addison-Wesley, Reading, Mass., 1983.
Jones, N.D., Muchnik, S.S. “Flow Analysis and Optimization of LISP-like Structures,” in Program Flow Analysis: Theory and Applications, S.S. Muchnik and N.D. Jones, eds., Prentice-Hall, Englewood Cliffs, N.J., pp. 102–131.
Lieberman, H., Hewitt, C. “A Real-time Garbage Collector Based on the Lifetime of Objects,” Communications of the ACM, V. 26, Nr. 6, June 1983, pp. 419–429.
Milner, R. “The Standard ML Core Language,” Polymorphism, V. 2, Nr. 2, October 1985.
MacQueen, D. “Modules for Standard ML,” Polymorphism, V. 2, Nr. 2, October 1985.
Moon, D.A. “Garbage Collection in a Large Lisp System,” Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, August 6–8, 1984, pp. 235–246.
Motorola Inc. MC68020 32-bit Microprocessor User's Manual, 2nd Ed., Prentice-Hall, Englewood Cliffs, N.J., 1985.
Rovner, P. “On Adding Garbage Collection and Runtime Types to a Strongly-Typed, Statically-Checked, Concurrent Language,” Xerox PARC Report CSL-84-7, July 1985.
Reppy, J.H., Gansner, E.R. “Pegasus: A Foundation for Programming Environments,” AT&T Bell Laboratories Technical Memorandum, December 1986. An earlier version of this appeared in the Proceedings of the Second ACM SIGSOFT/SIGPLAN Symposium on Practical Software Development Environments, December 9–11, 1986, pp. 218–227.
Steele, G.L. Jr., “Data Representations in PDP-10 MacLISP,” Proceedings of the 1977 MACSYMA Users' Conference, NASA, Washington, D.C., July 1977, pp. 203–214.
Stoyan, H. “Early LISP History (1956–1959),” Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, August 6–8, 1984, pp. 229–310.
Ungar, D. “Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm,” Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, April 23–25, 1984, pp. 157–167.
Vo, K.P. AT&T Bell Laboratoires, Murray Hill, N.J. Unix memory allocator, personal communication.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
North, S.C., Reppy, J.H. (1987). Concurrent garbage collection on stock hardware. In: Kahn, G. (eds) Functional Programming Languages and Computer Architecture. FPCA 1987. Lecture Notes in Computer Science, vol 274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18317-5_8
Download citation
DOI: https://doi.org/10.1007/3-540-18317-5_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18317-4
Online ISBN: 978-3-540-47879-9
eBook Packages: Springer Book Archive