Paging on an object-oriented personal computer

ABSTRACT

A high-performance personal computing environment must avoid perceptible pauses resulting from many page faults within a short period of time. Our performance goals for a paged virtual memory system for the Smalltalk-80TM@@@@; programming environment are both to decrease the average page fault rate and to minimize the pauses caused by clusters of page faults. We have applied program restructuring techniques to the Smalltalk-80 object memory in order to improve the locality of reference. The analysis in this paper considers the clustering of page faults over time and distinguishes between steady-state behavior and phase transitions. We compare the effectiveness of different restructuring strategies in reducing the amount of main memory needed to obtain desired levels of performance.

REFERENCES

• 1: Özalp Babaoglu , William Joy, Converting a swap-based system to do paging in an architecture lacking page-referenced bits, Proceedings of the eighth ACM symposium on Operating systems principles, p.78-86, December 14-16, 1981, Pacific Grove, California, United States
• 2: Scott B. Baden, High Performance Storage Reclamation in an Object-Based Memory System, University of California at Berkeley, Berkeley, CA, 1982
• 3: Ballard, S. and S. Shirron. "The Design and Implementation of VAX/Smalltalk-80," in Krasner, G., ed. Smalltalk 80: Bits of History, Words of Advice. Reading, MA: Addison-Wesley, 1983.
• 4: Ricki Blau, Paging on an Object-oriented Personal Computer for Smalltalk, University of California at Berkeley, Berkeley, CA, 1983
• 5: Chu, W. W. and H. Opderbeck, "Program Behavior and the Page-Fault-Frequency Replacement Algorithm," Computer, 9, 11 (Nov. 1976), 29-38.
• 6: Peter J. Denning , Kevin C. Kahn, A study of program locality and lifetime functions, Proceedings of the fifth ACM symposium on Operating systems principles, p.207-216, November 19-21, 1975, Austin, Texas, United States
• 7: Deutsch, L. P. Lecture at Univ. of California, Berkeley (Feb. 1982).
• 8: Deutsch, L.P. Private communication, 1982.
• 9: Domenico Ferrari, Improving locality by critical working sets, Communications of the ACM, v.17 n.11, p.614-620, Nov. 1974 [doi>10.1145/361179.361195]
• 10: Ferrari, D. "The Improvement of Program Behavior," Computer, 9, 11 (Nov. 1976), 39-47.
• 11: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 12: Gould, L. and W. Finzer. "Programming by Rehearsal," unpublished manuscript, Palo Alto, CA: Xerox PARC, Software Concepts Group, Dec. 1982.
• 13: Robert B. Hagmann , Robert S. Fabry, Program page reference patterns, Proceedings of the 1982 ACM SIGMETRICS conference on Measurement and modeling of computer systems, August 30-September 01, 1982, Seattle, Washington
• 14: Hatfield, D. J. and J. Gerald. "Program Restructuring for Virtual Memory," IBMSystems J. 10, 3 (1971), 168-192.
• 15: Kaehler, T. and G. Krasner. "LOOM-Large Object-Oriented Memory for Smalltalk-80 Systems," in Smalltalk 80: Bits of History, Words of Advice. Reading, MA: Addison-Wesley, 1983.
• 16: A. Wayne Madison , Alan P. Batson, Characteristics of program localities, Communications of the ACM, v.19 n.5, p.285-294, May 1976 [doi>10.1145/360051.360227]
• 17: McCall, K. "The Benchmarks," in Smalltalk 80: Bits of History, Words of Advice. Reading, MA: Addison-Wesley, 1983.
• 18: Patterson, D. A. and C. H. Séquin. "A VLSI RISC," Computer, 15, 9 (Sep. 1982), 8-21.
• 19: A. Snyder, A MACHINE ARCHITECTURE TO SUPPORT AN OBJECT-ORIENTED LANGUAGE, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 20: Stamos, J. W. A Large Object-Oriented Virtual Memory: Grouping Strategies, Measurements, and Performance. Palo Alto, CA: Xerox PARC, Software Concepts Group, May, 1982. SCG-82-2.
• 21: Ungar, D. M. and D. A. Patterson. "Berkeley Smalltalk: Who Knows Where the Time Goes?" in Smalltalk 80: Bits of History, Words of Advice. Reading, MA: Addison-Wesley, 1983.
• 22: Ungar, D. M. A High-Performance Smalltalk Computer. Ph.D. dissertation, University of California, Berkeley, in progress.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

General Terms:
Management, Performance