Browse Prior Art Database

Page Replacement Method and Mechanism Disclosure Number: IPCOM000049774D
Original Publication Date: 1982-Jul-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 9 page(s) / 72K

Publishing Venue


Related People

Weinberger, A: AUTHOR


This scheme saves a large amount of software processing in paging in and out of main storage.

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 18% of the total text.

Page 1 of 9

Page Replacement Method and Mechanism

This scheme saves a large amount of software processing in paging in and out of main storage.

Fig. 1 is a block diagram of the replacement algorithm consisting of the following major elements: 1 (CHRONOLOGY) TABLE - It uniquely identifies one of the 4 categories to which each main store page can

belong. (For conciseness,it will be referred

to simply as the TABLE.) The TABLE can be

implemented with 8 256x9 array chips for 8K pages, the

maximum number assumed. It can be adjusted from

1K through 8K pages in 1K increments. 2 (LRU) STACK - It contains up to 28 page addresses identifying identifying the pages that have been selected as

candidates for replacement. It can be implemented with

a single 32x18 array chip. (It will be referred to

simply as the STACK). The remaining 4 locations are

reserved for temporary storage during algorithm processing. 3 Miscellaneous registers and logic. The imputs comprise. 1 DATA IN - a 13-bit bus carrying a 13-bit page address or data for loading various registers, 2 CONTROL IN - a 4-bit encoded control specifying the type of function to be performed by the replacement algorithm

hardware. 3 TIME INCREMENT - a 1-bit signal indicating the elapse of a unit of time the machine has been in operation

(arbitrarily assumed to represent approximately

1 millisecond), and 4 INITIALIZE - a signal which resets various registers and control flip flops during IPL (initial program


The outputs comprise: 1 DATA OUT - a 13-bit bus carrying the 13-bit page address of a selected replacement page or other data, and 2 CONTROL OUT - a 2-bit encoded control interpreting the DATA OUT.

Fig. 2 is a more detailed diagram showing specific registers associated with the various hardware functions.


A recentness-of-use record, i.e., a chronology, is kept in the TABLE for each of the 8K (2/13/) pages in a maximum size main store. Each time a page is referenced in main store, the page address will also select an entry in the TABLE and modify the TABLE accordingly.

An entry in the TABLE consists of a 2-bit code identifying 4 categories: (see original)


Page 2 of 9

LRU (Least Recently Used) - code 00

NLRU (Next Least Recently Used) - code 01

MRU (Most Recently Used) - code 10

NONE (None of the above) - code 11

The last category is assigned to pages that are not to be replaced, e.g., system programs permanently resident in specific main store pages.

With 2 bits per page, the TABLE for 2/13/ pages can be stored in 8 256x9 array chips and addressed as shown in Fig. 3. Each 4 entries, comprising 8 bits, share a common parity bit. With fewer pages in main store, the TABLE is correspondingly reduced.

During IPL, the TABLE is loaded with the proper code for each page address, most with 00 (LRU) but some with 11 (NONE, i.e., not to be replaced code).

During normal operation, every reference to a page in main store will bring in the page address on DATA IN and held in the DATA IN REGI...