Browse Prior Art Database

mLRU Page Replacement Algorithm in Terms of the Reference Matrix

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

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 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 is removed from the main memory.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 66% of the total text.

Page 1 of 2

mLRU Page Replacement Algorithm in Terms of the Reference Matrix

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 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 is removed from the main memory.

Here it is assumed that whenever a page fault occurs, m pages, whe 1 < or = m < or = n, are brought from the auxiliary memory and they are placed in the main memory. Where one of the 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 least recently used pages (some pages may be unused pages) from the main memory, so that those m pages from the auxiliary memory can be placed in the main memory. This is called the "mLRU page replacement policy". Description of mLRU Algorithm

Let A be an n by n matrix where each entry a(ij) can assume either 0 or 1. In the matrix A, which is called the reference matrix, the i-th row and the i-th column correspond to the i-th page in the main memory.

Let Z be an n-dimensional vector, which is called the page-availabe vector, where each entry z(i) can be either 0 or 1. The i-th element z(i)...