article

Free access

A dynamic clustering strategy in a demand paging environment

Author:

Udo W. PoochAuthors Info & Claims

ACM SIGSIM Simulation Digest, Volume 7, Issue 4

Pages 11 - 22

https://doi.org/10.1145/1013610.807296

Published: 01 July 1976 Publication History

Abstract

An algorithm is presented which dynamically clusters pages of a problem program based on its past program behavior (i.e. reference string patterns) in a demand paged virtual memory environment. The objective of this algorithm is to minimize the number of page faults during execution, while at the same time use memory page frames efficiently. Dynamic clusters of time and reference related pages are built during a program's execution time.

Whenever a page fault for the i-th page occurs in this time evolving environment, the pages of the cluster associated with the i-th page is compared to the pages currently in real (physical) memory. Thus during this current page fault, the demanded page, and any associated clustered pages not currently in physical memory are placed into memory. Page frames holding pages not in the current cluster are returned to the memory management system. Thus the physical amount of memory allocated to a processing program is dependent upon the size of the associated cluster at that time.

Simulation results of program behavior operating under this dynamic clustering strategy indicates that significant improvements in page faults and in the space time product may be achieved. The algorithm requires fewer real page frames per executed instruction than most currently implemented algorithms that utilize a fixed number of page frames per problem programs (i.e. fixed allocated partition or region).

The algorithm, MLMM (Modified Locality Matrix Model), an extension of work by Hedges and Pooch [12] is used to determine inherent program locality to predict independent dynamic program behavior, separating instruction from data references. Furthermore, strength coefficients between weakly or loosely coupled clusters are used to refine the cluster population, identify cluster transitions, as well as indicate the behavior of the cluster formations.

References

[1]

Aho, A. V., P. J. Denning, and J. D. Ullman. Principles of Optimal Page Replacement. J. ACM 18, 1 (January 1971), 80-93.

Digital Library

[2]

Belady, L. A. A study of replacement algorithms for a virtual storage computer. IBM System J. 5, 2 (1966), 78-101

Digital Library

[3]

Belady, L. A. Use of the minimum page replacement algorithm to produce specified memory states. IBM Research Report, RC 3408, 1971.

[4]

Belady, L. A. and Tsao, R. F. Memory allocation and program behavior under multiprogramming. IBM Research Report, RC 3469, 1971.

[5]

Boyle, J. Program behavior and virtual memory management in time-shared computer systems. Dissertation, Texas A&M University, 1973.

Digital Library

[6]

Coffman, E. G., Jr., and P. J. Denning. Operating Systems Theory, Prentice-Hall, Inc. Englewood Cliffs, New Jersey (1973), 241-305.

Digital Library

[7]

Denning, P. J. The working set model for program behavior. Comm. ACM 11 (May 1968), 232-333.

Digital Library

[8]

Denning, P. J. Thrashing: its causes and prevention. Proc. AFIPS 1968 FJCC, 915-922.

[9]

Denning, P. J. Virtural memory. Computing Surveys 2, 3 (Sept. 1970), 153-187.

Digital Library

[10]

Denning, P. J., Savage, J. E. and Spirn, J. R. Models for locality in program behavior. Department of Electrical Engineering, TR-107, Princeton University, 1972.

[11]

Denning, P. J., Savage, J. E. and Spirn, J. R. Some thoughts about locality in program behavior. Proc. Brooklyn Polytechnic Institute Symposium, 1972.

[12]

Hedges, R. L., and U. W. Pooch, "A Measure for Program Locality in Demand Paging," ACM '75 National Conference, Minneapolis, Minnesota, October 1975.

Digital Library

[13]

Shedler G. S. and Tung, C. Locality in Page Reference strings. SIAM J. on Computing, 1, 3, September 1972, 218-241.

Digital Library

[14]

Spirn, J. R. and Denning, P. J. Experiments with program locality. Proc. AFIPS 1972 FJCC, 611-621.

[15]

Thorington, J. M. and Irwin, J. D. An adaptive replacement algorithm for paged-memory computer systems. Nat's Tech. Info. Service, AD 725989, 1971.

Cited By

Smith A(1978)Sequential Program Prefetching in Memory HierarchiesComputer10.1109/C-M.1978.21801611:12(7-21)Online publication date: 1-Dec-1978
https://dl.acm.org/doi/10.1109/C-M.1978.218016
Smith A(1978)Bibliography on paging and related topicsACM SIGOPS Operating Systems Review10.1145/775406.77540912:4(39-56)Online publication date: 1-Oct-1978
https://dl.acm.org/doi/10.1145/775406.775409
Burris DPooch UKetchel JKriloff HBurner HCrockett PHerriot RHouston GKitto C(1977)The dynamic matrix modelProceedings of the 1977 annual conference10.1145/800179.1124631(386-391)Online publication date: 1-Jan-1977
https://dl.acm.org/doi/10.1145/800179.1124631
Show More Cited By

Index Terms

A dynamic clustering strategy in a demand paging environment
1. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
      1. Clustering and classification
  2. Information systems applications
    1. Data mining
      1. Clustering
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Allocation / deallocation strategies
        Virtual memory

Recommendations

A dynamic clustering strategy in a demand paging environment
ANSS '76: Proceedings of the 4th symposium on Simulation of computer systems

An algorithm is presented which dynamically clusters pages of a problem program based on its past program behavior (i.e. reference string patterns) in a demand paged virtual memory environment. The objective of this algorithm is to minimize the number ...
A Modified Locality Matrix Model (MLMM) - dynamic clustering in a demand paging environment
ACM '76: Proceedings of the 1976 annual conference

An algorithm is presented which dynamically clusters pages of a problem program based on its post program behavior (i.e. reference string patterns) in a demand paged virtual memory environment. The objective of this algorithm is to minimize the number ...
Demand paging for OneNAND™ Flash eXecute-in-place
CODES+ISSS '06: Proceedings of the 4th international conference on Hardware/software codesign and system synthesis

NAND flash memory can provide cost-effective secondary storage in mobile embedded systems, but its lack of a random access capability means that code shadowing is generally required, taking up extra RAM space. Demand paging with NAND flash memory has ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGSIM Simulation Digest

ACM SIGSIM Simulation Digest Volume 7, Issue 4

July 1976

183 pages

ISSN:0163-6103

DOI:10.1145/1013610

Issue’s Table of Contents

ANSS '76: Proceedings of the 4th symposium on Simulation of computer systems
August 1976
221 pages
Chairmen:
Larry G. Hull,
Arthur Chantker,
Gary J. Nutt,
W. R. Franta,
Editor:
Harold Joseph Highland

Copyright © 1976 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in SIGSIM Volume 7, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
347
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)8

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Smith A(1978)Sequential Program Prefetching in Memory HierarchiesComputer10.1109/C-M.1978.21801611:12(7-21)Online publication date: 1-Dec-1978
https://dl.acm.org/doi/10.1109/C-M.1978.218016
Smith A(1978)Bibliography on paging and related topicsACM SIGOPS Operating Systems Review10.1145/775406.77540912:4(39-56)Online publication date: 1-Oct-1978
https://dl.acm.org/doi/10.1145/775406.775409
Burris DPooch UKetchel JKriloff HBurner HCrockett PHerriot RHouston GKitto C(1977)The dynamic matrix modelProceedings of the 1977 annual conference10.1145/800179.1124631(386-391)Online publication date: 1-Jan-1977
https://dl.acm.org/doi/10.1145/800179.1124631
Pooch UBurris DGosden JJohnson O(1976)A Modified Locality Matrix Model (MLMM) - dynamic clustering in a demand paging environmentProceedings of the 1976 annual conference10.1145/800191.805612(337-343)Online publication date: 20-Oct-1976
https://dl.acm.org/doi/10.1145/800191.805612

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents