Browse Prior Art Database

Page-Replacement Algorithm

IP.com Disclosure Number: IPCOM000039353D
Original Publication Date: 1987-May-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

King, RP: AUTHOR

Abstract

The algorithm described in this article is a modification of the standard clock algorithm found in the Multics system. It is a page replacement algorithm that adapts to the sequential versus localized nature of page references and achieves a greater memory hit ratio than other algorithms. It provides for the management of memory, and decides which data are to be retained for later use, and which are to be discarded to make room for other data. This algorithm is applicable to the management of a processor's main memory, and also to the management of secondary levels of a storage hierarchy (for instance a cache for a set of disk files). The criteria for judging such algorithms are: 1. The proportion of data requests which can be satisfied directly from storage (the hit ratio), and 2.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 2

Page-Replacement Algorithm

The algorithm described in this article is a modification of the standard clock algorithm found in the Multics system. It is a page replacement algorithm that adapts to the sequential versus localized nature of page references and achieves a greater memory hit ratio than other algorithms. It provides for the management of memory, and decides which data are to be retained for later use, and which are to be discarded to make room for other data. This algorithm is applicable to the management of a processor's main memory, and also to the management of secondary levels of a storage hierarchy (for instance a cache for a set of disk files). The criteria for judging such algorithms are: 1. The proportion of data requests which can be satisfied directly from storage (the hit

ratio), and 2. The processor time necessary to perform the algorithm.

The algorithm surpasses both the standard clock

algorithm and the least- recently-used (LRU) algorithm

on both of these scores. Storage is taken to be organized as a set of page

frames, in which are stored copies of pages of program

instructions and data for which requests are received

to read from or write into such pages. These requests

are fulfilled either by locating the page within

storage or by requesting the page from some other

medium, in which case the page is also copied into

storage in case it is required in the near future. Each page frame has associated with it a reference bit. There is also a pointer kept to the frame which

was last allocated. When a request for a page can be

fulfilled from a copy already in storage, the reference

bit for that page frame is turned on. When a page

frame is to be allocated for storage of a new page: 1.

The reference bit of the last frame allocated is turned

off. 2. The last-frame pointer is advanced to point to the next

frame in storage. 3. If the reference bit of the frame pointed to now is

off, then that frame is allocated. 4. Otherwise, the reference bit for that frame is turned off, and the allocation procedure continues at the

second step. 5. The desired data is copied into the allocated frame. The tur...