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.
