Article

Free access

A Modified Locality Matrix Model (MLMM) - dynamic clustering in a demand paging environment

Authors:

David M. BurrisAuthors Info & Claims

ACM '76: Proceedings of the 1976 annual conference

Pages 337 - 343

https://doi.org/10.1145/800191.805612

Published: 20 October 1976 Publication History

Abstract

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 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.

The Modified Locality Matrix Model is used to determine inherent program locality and 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]

A. V. Aho, P. J. Denning, and J. D. Ullman. Principles of optimal page replacement. J. ACM 18, 1, January, 1971, 80-93.

Digital Library

[2]

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

Digital Library

[3]

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

[4]

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

[5]

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

Digital Library

[6]

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

Digital Library

[7]

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

Digital Library

[8]

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

[9]

P. J. Denning. Virtual memory. Computing Surveys 2, 3, September, 1970, 153-187.

Digital Library

[10]

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

[11]

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

[12]

R. L. Hedges, and U. W. Pooch. A measure for program locality in demand paging. ACM '75 National Conference, Minneapolis, Minnesota, October, 1975.

Digital Library

[13]

U. W. Pooch. A dynamic clustering strategy in a demand paging environment. Proc. of the 4th Annual Symposium on Simulation of Computer Systems, Boulder, Colorado, August, 1976.

Digital Library

[14]

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

Digital Library

[15]

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

[16]

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

Cited By

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

Index Terms

A Modified Locality Matrix Model (MLMM) - dynamic clustering in a demand paging environment
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        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 dynamic clustering strategy in a demand paging environment

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 ...
General C-Means Clustering Model

Partitional clustering is an important part of cluster analysis. Based on various theories, numerous clustering algorithms have been developed, and new clustering algorithms continue to appear in the literature. It is known that Occam's razor plays a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM '76: Proceedings of the 1976 annual conference

October 1976

576 pages

ISBN:9781450374897

DOI:10.1145/800191

Copyright © 1976 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 October 1976

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
289
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)18

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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

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 Table of Contents