Browse Prior Art Database

One Pass Page Replacement Algorithm

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

Publishing Venue

IBM

Related People

Disbrow, JR: AUTHOR [+2]

Abstract

The following is a one pass replacement algorithm which can be used in a machine design including virtual paging, which causes a page trap or interrupt whenever a program attempts to access a byte which is not resident. The hardware can determine residency by scanning a page table. The page table is a description of virtual pages which currently occupy memory. Each entry in this table is two bytes long. A first byte is the virtual page address while the second byte is the status byte. The paging algorithm described uses bits in this status byte to determine which page to replace. In general, N different weighted factors are considered in one pass in deciding which page should be pushed or overridden.

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

Page 1 of 2

One Pass Page Replacement Algorithm

The following is a one pass replacement algorithm which can be used in a machine design including virtual paging, which causes a page trap or interrupt whenever a program attempts to access a byte which is not resident. The hardware can determine residency by scanning a page table. The page table is a description of virtual pages which currently occupy memory. Each entry in this table is two bytes long. A first byte is the virtual page address while the second byte is the status byte. The paging algorithm described uses bits in this status byte to determine which page to replace. In general, N different weighted factors are considered in one pass in deciding which page should be pushed or overridden.

Six factors have been identified as having value in page selection, as seen below in decreasing order of importance:. L H C R W S L= Lock - this bit is set by the hardware when a Perform Input/Output instruction is given which references the page. If this bit is on, the page must not be pushed since the I/O is either writing to it or reading from it. This bit could also be set by software under some circumstances. H= Hold- this is the software lock bit and is set when it is desired to leave a page in core which would be pushed or overlaid only if there were no lower-priority page available. To prevent indiscriminate setting of this bit by other system programs, an operating system is provided which evaluates each situation and sets it if, according to some criteria, enough other pages are available. Storage protection will ordinarily prevent this as well as all other status bytes from being set by the problem program. C= Current - i.e., the current page - this is set by the page routine to indicate the page from which the page trap was generated. It is likely (certain in case of operand page trap) that the page which generated the trap will be referred to again soon. If a program inadvertently has a loop...