xerox CSL-91-7 Virtual Memory Replacement Using Historical Information on Virtual Objects free download

File name CSL-91-7_Virtual_Memory_Replacement_Using_Historical_Information_on_Virtual_Objects.pdf

Vi rtual Memory Replacement . Using Historical Information on Vi rtual Objects Virtual Memory Replacement Using Historical Information on Virtual Objects Robert B. Hagmann Xerox Palo Alto Research Center CSl- 91-7 September 1991 [P91 - 00094] (!) Copyright 1991 Xerox Corporation. All rights reserved. Abstract: Most current virtual memory systems retain very little information about page usage. Typically, only a single bit of history is used. The history is usually only kept on pages currently resident in physical memory. With larger main memories, changes in applications, and the increases in file system caching in memory, these design decisions should be reviewed. If mUltiple bits of history are kept on virtual objects, whether they are memory resident or not, then there is the potential to improve memory replacement performance. This paper describes a measurement technique that is used to monitor memory usage. It then proposes a new virtual memory replacement algorithm that is partially based on periodic, sequential, and transient behaviors. It also describes an approximation to LRU, called cluster LRU, that performs better on the programs measured than the usual clock algorithm. The performance of various algorithms is compared by trace driven simulation. Finally, this paper shows how a Translation Lookaside Buffer can be designed for a RISC machine to support both cluster lRU and detection of periodic, sequential, and transient behaviors. CR Categories and Subject Descriptors: 0.4.2 [Memory Structures]: Design Styles - Virtual memory; 0.4.2 [Operating Systems]: Storage Management - Virtual memory Additional Keywords and Phrases: Large Main Memories XEROX Xerox Corporation Pa 10 Alto Research Center 3333 Coyote Hill Road Palo Alto, California 94304 1. Introduction 1 1. Introduction Much has changed since most current virtual memory replacement algorithms were designed over a decade ago. The amount of memory and the usage of memory was different then. The characteristics of program behavior when using hundreds of pages is different from using tens of thousands of pages of memory. Many machines are now single user workstations rather than time - shared machines. On a single user machine, the time for page fault is now directly visible to the interactive user, particularly when pages are faulted over a network. In addition, some systems now do not make major distinctions between pages for file system buffers and pages for program execution (see [Nels88] for Sprite and [Gingell] for SunOS 4.0). Mapped files further confuse the distinction between file system buffers and pages for program execution. Ex