High-level dynamic memory management for object-oriented real-time systems

ABSTRACT

Dynamic memory management in real-time systems is difficult because most traditional allocation and deallocation algorithms are unpredictable in terms of their worst-case memory utilization and execution times. This paper describes recent work on a new memory management system designed specifically to support hard-real-time allocation, automatic garbage collection, and defragmentation of the free pool. The memory management system consists of special hardware circuits placed between the CPU's level-two caches and its memory subsystem. Benefits include worst-case allocation delays of two microseconds and typical memory utilizations that exceed binary-buddy allocators by over 30%. A commercial implementation of this technology is currently under development.

REFERENCES

• 1: K. D. Nilsen , Hong Gao, The real-time behavior of dynamic memory management in C++, Proceedings of the Real-Time Technology and Applications Symposium, p.142, May 15-17, 1995
• 2: Norman R. Nielsen, Dynamic memory allocation in computer simulation, Communications of the ACM, v.20 n.11, p.864-873, Nov. 1977 [doi>10.1145/359863.359890]
• 3: 3. Nilsen, K., Schmidt, W.: A High-Performance Hardware-Assisted Real-Time Garbage Collection System, Journal of Programming Languages, 2, 1. (Jan. 1994), 1-40.
• 4: William J. Schmidt , Kelvin D. Nilsen, Performance of a hardware-assisted real-time garbage collector, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.76-85, October 05-07, 1994, San Jose, California, United States
• 5: 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]
• 6: 6. Dylan Home Page, http:www.cambridge.apple.com
• 7: 7. ScriptX Technical Reference Series, http:// web.kaleida.com/reference/index.html
• 8: 8. Java Home Page, http:/java.sun.com
• 9: 9. Nilsen, K., Schmidt, W. J.: Hardware-Assisted General-Purpose Garbage Collection for Hard Real-Time Systems, Iowa State University Technical Report 92-15. (1992).
• 10: Ralph E. Griswold , Madge T. Griswold, ICON Programmng Language, Prentice Hall Professional Technical Reference, 1983
• 11: 11. Basumallick, S., Nilsen, K.: Cache Issues in Real-Time Systems, ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, Orlando, FL. (June 1994).
• 12: 12. Narasimhan, K., Nilsen, K.: Portable Execution Time Analysis for RISC Processors, ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, Orlando, FL. (June 1994).
• 13: Kelvin D. Nilsen , William J. Schmidt, Cost-effective object space management for hardware-assisted real-time garbage collection, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.338-354, Dec. 1992 [doi>10.1145/161494.161508]
• 14: 14. Toshiba TC59R0409 4-Megabit RDRAM, Rambus Inc., (1993).
• 15: 15. Chinta, R.: Hardware-Assisted Garbage Collection for the Icon Programming Language, Iowa State University Technical Report 92-39. (Dec. 1992).
• 16: 16. Power PC 601 RISC Microprocessor User's Manual , Motorola. (1993).
• 17: 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
• 18: Benjamin Zorn , Dirk Grunwald, Evaluating models of memory allocation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.1, p.107-131, Jan. 1994 [doi>10.1145/174619.174624]
• 19: Dirk Grunwald , Benjamin Zorn, CustoMalloc: efficient synthesized memory allocators, Software—Practice & Experience, v.23 n.8, p.851-869, Aug. 1993 [doi>10.1002/spe.4380230804]
• 20: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 21: 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]
• 22: Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
• 23: 23. Wilson, P. R., Johnstone, M. S.: Real-Time Non-Copying Garbage Collection, Preprints of Position Papers OOPSLA '93 Workshop on Memory Management and Garbage Collection, Washington, DC. (Sep. 1993).
• 24: 24. Hennessey, W.: Real-Time Garbage Collection in a Multimedia Programming Language, Preprints of Position Papers OOPSLA '93 Workshop on Memory Management and Garbage Collection, Washington, DC. (Sep. 1993).
• 25: Kelvin D. Nilsen , Bernt Rygg, Worst-case execution time analysis on modern processors, Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, p.20-30, November 1995, La Jolla, California, United States
• 26: 26. DM1M36SJ/DM1M32SJ 1Mbx36/1Mbx32 Enhanced DRAM SIMM, Ramtron International Corporation. (1994).
• 27: K. Nilsen, Real-time is no longer a small specialized niche, Proceedings of the Fifth Workshop on Hot Topics in Operating Systems (HotOS-V), p.2, May 04-05, 1995
• 28: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 29: Kelvin D. Nilsen, Progress in Hardware-Assisted Real-Time Garbage Collection, Proceedings of the International Workshop on Memory Management, p.355-379, September 27-29, 1995

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Worst-case analysis**

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.1 Control Design Styles
          Subjects: Hardwired control**

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Management, Theory