Cost-effective object space management for hardware-assisted real-time garbage collection

ABSTRACT

Modern object-oriented languages and programming paradigms require finer-grain division of memory than is provided by traditional paging and segmentation systems. This paper describes the design of an OSM (Object Space Manager) that allows partitioning of real memory on object, rather than page, boundaries. The time required by the OSM to create an object, or to find the beginning of an object given a pointer to any location within it, is approximately one memory cycle. Object sizes are limited only by the availability of address bits. In typical configurations of object-oriented memory modules, one OSM chip is required for every 16 RAM chips. The OSM serves a central role in the implementation of a hardware-assisted garbage collection system in which the worst-case stop-and-wait garbage collection delay ranges between 10 and 500 &mgr;sec, depending on the system configuration.

REFERENCES

• 1: 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]
• 2: BARTLETT, J.F. 1988. Compacting garbage collection with ambiguous roots. WRL Res. Rep. 88/2. Digital Equipment Corporation Western Research Laboratory.
• 3: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 4: 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
• 5: Craig David Chambers, The design and implementation of the self compiler, an optimizing compiler for object-oriented programming languages, Stanford University, Stanford, CA, 1992
• 6: CHAMBERS, C. 1991. Cost of garbage collection in the SELF system. In the 1991 Workshop on Garbage Collectmn tn Object-Oriented Systems of OOPSLA. ACM, New York.
• 7: CHRISTOPHER, T.W. 1984. Reference count garbage collection. Softw. Prac. Exp. 14, 503-507.
• 8: DETLEFS, D.L. 1990. Concurrent garbage collection for C+ +. CMU-CS-90-119, Carnegie-Mellon Univ., Pittsburgh, Penn.
• 9: Amer Diwan , Eliot Moss , Richard Hudson, Compiler support for garbage collection in a statically typed language, ACM SIGPLAN Notices, v.27 n.7, p.273-282, July 1992
• 10: 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
• 11: ENGELSTAD, S. L., AND VANDENDORPE, J.E. 1991. Automatic storage management for systems with real-time constraints. In Oral Presentation at 1991 Workshop on Garbage CoUectzon in Object-Oriented Systems of OOPSLA. ACM, New York.
• 12: Ralph E Griswold , Madge T Griswold, The implementation of the Icon programming language, Princeton University Press, Princeton, NJ, 1986
• 13: HANSON, D.R. 1977. Storage management for an implementation of SNOBOLA. Softw. Pract. Exp. 7, 179-192.
• 14: Ralph E. Johnson, Reducing the latency of a real-time garbage collector, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.46-58, March 1992 [doi>10.1145/130616.130621]
• 15: Moss, J. E. B. 1991. The UMass language independent garbage collector toolkit. In 1991 Workshop on Garbage Collection in Object-Oriented Systems of OOPSLA. ACM, New York.
• 16: NILSEN, K. 1991. Memory cycle accountings for hardware-assisted real-time garbage collection. Tech. Rep 91-21, Iowa State Univ.
• 17: 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]
• 18: NILSEN, K. AND SCHMIDT, W.J. 1992a. Hardware-assisted general-purpose garbage collection for hard real-time systems, Tech. Rep. 92-15, Iowa State Univ.
• 19: NILSEN, K. D., AND SCHMIDT, W. J. 1992b. Preferred embodiment of a hardware-assisted garbage~collection system. Tech. Rep. 92-17~ Iowa State Univ.
• 20: William Jon Schmidt, Issues in the design and implementation of a real-time garbage collection architecture, Iowa State University, Ames, IA, 1992
• 21: SCHMIDT, W. J., AND NILSEN, K.D. 1992. Experimental measurements of a real-time garbage collection architecture. Tech. Rep. 92-26, Iowa State Univ.
• 22: SCHMIT, W. J., AND NILSEN, K. 1991. Architectural support for garbage-collected memory in hard real-time systems. Tech. Rep. 91-23, Iowa State Univ.
• 23: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 24: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Management, Performance

Keywords:
automatic garbage collection, dynamic storage management, high-level language architectures, memory technologies, real-time and embedded systems, run-time environments