Browse Prior Art Database

mLRU Page Replacement Algorithm in Terms of the Reference Counters

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

Publishing Venue

IBM

Related People

Maruyama, K: AUTHOR

Abstract

When a page fault occurs in a computer with the virtual memory (or cache with an extended core memory), one page must be removed from the main memory of n pages to provide a free page, so that the demanded page can be brought from an auxiliary memory and be placed in the main memory. The replacement policy determines which page must be removed from the main memory. One well-known policy is called LRU; the Least Recently Used Page is removed from the main memory.

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

Page 1 of 2

mLRU Page Replacement Algorithm in Terms of the Reference Counters

When a page fault occurs in a computer with the virtual memory (or cache with an extended core memory), one page must be removed from the main memory of n pages to provide a free page, so that the demanded page can be brought from an auxiliary memory and be placed in the main memory. The replacement policy determines which page must be removed from the main memory. One well-known policy is called LRU; the Least Recently Used Page is removed from the main memory.

Here it is assumed that whenever a page fault occurs, m pages, where 1 < or = m < n, are brought from the auxiliary memory and they are placed in the main memory. Where one of m pages is the demanded page, m pages are stored physically contiguous in the auxiliary memory. To place m pages in the main memory, m pages must be removed from the main memory. The m stored physically contiguous in the auxiliary memory. To place m pages in the main memory, m pages must be removed from the main memory. The m least recently used pages (some pages may be unused pages) are removed from the main memory, so that m pages from the auxiliary memory can be placed in the main memory. This is called an "mLRU page replacement policy". Description of the mLRU Algorithm

Let C denote an n-dimensional vector, which is called the counter vector, such that the counter c(i) is assigned to the i-th page of the main memory. Each counter c(i) can assume any integer between 0 and n - 1.

Let Z be an n-dimensional vector, which is called the page-availability vector, such that z(i) is assigned to the i-th page of the main memory. Each page- availability bit z(i) can assume either 0 or 1. If the i-th page is available for processing then z(i) = 1, otherwise z(i) = 0. Algorithm A1 (when replaced)

When a new page from the auxiliary memory is placed in the i-th page frame of the main memory (simply, in the i-th page of the main memory), then set; zi <-- 1, c(i) <-- 0, and n(a) <-- n(a) - 1.

Setting z(i) <-- 1 means that the ith page is now available for processing, because of the completion of the page replacement. Since the i-th page of the Main memory is new and never referenced by CPU yet, the counter c(i) is reset to c(i) <-- 0. The parameter n(a) denotes the current number of pages in the main memory which are unavailable for processing. Since the i-th page becomes now available ,n (a)is set to n (a) <-- (a)- 1'. Algorithm A2 (when referenced)

When the i-th page in the main memory is referenced by CPU, the count...