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.
- 1.Babaoglu, O. and W. N. Joy. "Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Referenced Bits," Proc. Eighth Symp. on Operating Systems Principles, in Operating Systems Review, 15, 5 (Dec. 1981), 78-86. Google ScholarDigital Library
- 2.Baden, S. "High Performance Storage Reclamation in an Object-Based Memory System," M.S. report, University of California, Berkeley, 1982. Google ScholarDigital Library
- 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.Google Scholar
- 4.Blau R. "Paging on an Object-Oriented Personal Computer for Smalltalk," Progres Report 83.2, Computer Science Division, University of California, Berkeley, June 1983. Google ScholarDigital Library
- 5.Chu, W. W. and H. Opderbeck, "Program Behavior and the Page-Fault-Frequency Replacement Algorithm," Computer, 9, 11 (Nov. 1976), 29-38.Google ScholarDigital Library
- 6.Denning, P. J. and K. C. Kahn, "A Study of Program Locality and Lifetime Functions," Proc. Fifth Symp. on Operating Systems Principles, in Operating Systems Review, 9, 5 (Nov. 1975), 207-216. Google ScholarDigital Library
- 7.Deutsch, L. P. Lecture at Univ. of California, Berkeley (Feb. 1982).Google Scholar
- 8.Deutsch, L.P. Private communication, 1982.Google Scholar
- 9.Ferrari, D. "Improving Locality by Critical Working Sets," CACM, 17, 11 (November, 1974, 614-620. Google ScholarDigital Library
- 10.Ferrari, D. "The Improvement of Program Behavior," Computer, 9, 11 (Nov. 1976), 39-47.Google Scholar
- 11.Goldberg, A. and D. Robson. Smalltalk-80: The Language and its Implementation. Reading, MA: Addison-Wesley, 1983. Google ScholarDigital Library
- 12.Gould, L. and W. Finzer. "Programming by Rehearsal," unpublished manuscript, Palo Alto, CA: Xerox PARC, Software Concepts Group, Dec. 1982.Google Scholar
- 13.Hagmann, R. B. and R. S. Fabry. "Program Page Reference Patterns," ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 1982, 20-29. Google ScholarDigital Library
- 14.Hatfield, D. J. and J. Gerald. "Program Restructuring for Virtual Memory," IBMSystems J. 10, 3 (1971), 168-192.Google Scholar
- 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.Google Scholar
- 16.Madison, A. W. and A. P. Batson. "Characteristics of Program Localities," Comm. ACM, 19, 5 (May 1976), 285-294. Google ScholarDigital Library
- 17.McCall, K. "The Benchmarks," in Smalltalk 80: Bits of History, Words of Advice. Reading, MA: Addison-Wesley, 1983.Google Scholar
- 18.Patterson, D. A. and C. H. Séquin. "A VLSI RISC," Computer, 15, 9 (Sep. 1982), 8-21.Google ScholarDigital Library
- 19.Snyder, A. A Machine Architecture to Support an Object-Oriented Language. Cambridge, MA:M.I.T. Laboratory for Computer Science, March, 1979. MIT/LCS/TR-209 Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 22.Ungar, D. M. A High-Performance Smalltalk Computer. Ph.D. dissertation, University of California, Berkeley, in progress.Google Scholar
Index Terms
- Paging on an object-oriented personal computer
Recommendations
Garbage collection without paging
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationGarbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are ...
Garbage collection without paging
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationGarbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are ...
Comments