Self-Adjusting Page Replacement Algorithm
Original Publication Date: 1985-May-01
Included in the Prior Art Database: 2005-Feb-18
This article describes a not-recently-used (NRU) page replacement algorithm which uses a reference interval which is self-adjusting to real storage demand and to the locality of virtual storage references. The following rules are used: 1. A page is eligible to be stolen if it has not been referenced within the current or last reference interval. 2. The first reference interval ends when some arbitrary allocation point has been reached, such as the assignment of all real storage frames. 3. Each subsequent reference interval ends whenever a scan is made of two bits of reference data for all page frames in real storage, and no page is found to be eligible to be stolen by having both reference bits in zero state. One bit is the "last-interval reference bit", and the other bit is the "current reference bit". 4.