A Mixed-Strategy Page Replacement Algorithm for a Multiprogramming, Virtual Memory Computer

Get BibTex-formatted data

Author

Eugene Howard Spafford

Entry type

mastersthesis

Abstract

Most modern computers depend on some form of virtual memory, using either a paged, segmented, or hybrid (paged-segmenteed) memory organization and management scheme. One aspect of most of these schemes that has a dramatic effect on system performance is the algoirthm used in demand paging to select pages for removal. Many near-optimal replacement schemes have been found, but their complexity and various practical considerations tend to limit the effectiveness of the algorithms implemented in real systems. This thesis examines some strategies for page replacement and their rationales. A mathematical argument is given to modify the current version of "The Principle of Optimality" governing page replacement and implementations derived from that principle. A scheduling consideration is developed as an extension to the concept of demand paging. The extensions discussed have been incorporated into working systems. These implementations are discussed, and results from various forms of load testing are examined and interpreted. Conclusions are made as to the applicability of this type of algoirthm to other systems, and as to extensions that might yet be made.

Key alpha

Spafford

Note

August 1981

School

Georgia Institute of Technology

Publication Date

1900-01-01

1. Introduction 2. The Page Replacement Problem 3. An Implementation 4. Experimental Results 5. Further Research 6. Conclusions

Language

English

Location

A hard-copy of this is in REC 216

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Mastersthesis{ Spafford,
	title = "A Mixed-Strategy Page Replacement Algorithm for a Multiprogramming, Virtual Memory Computer",
	author = "Eugene Howard Spafford",
	note = "August 1981",
	school = "Georgia Institute of Technology",
	abstract = "Most modern computers depend on some form of virtual memory, using either a paged, segmented, or hybrid (paged-segmenteed) memory organization and management scheme.  One aspect of most of these schemes that has a dramatic effect on system performance is the algoirthm used in demand paging to select pages for removal.  Many near-optimal replacement schemes have been found, but their complexity and various practical considerations tend to limit the effectiveness of the algorithms implemented in real systems.
This thesis examines some strategies for page replacement and their rationales.  A mathematical argument is given to modify the current version of "The Principle of Optimality" governing page replacement and implementations derived from that principle.  A scheduling consideration is developed as an extension to the concept of demand paging.
The extensions discussed have been incorporated into working systems.  These implementations are discussed, and results from various forms of load testing are examined and interpreted.  Conclusions are made as to the applicability of this type of algoirthm to other systems, and as to extensions that might yet be made.",
	contents = "1. Introduction
2. The Page Replacement Problem
3. An Implementation
4. Experimental Results
5. Further Research
6. Conclusions",
	language = "English",
}