Browse Prior Art Database

Least Recently Used Replacement Control

IP.com Disclosure Number: IPCOM000078674D
Original Publication Date: 1973-Feb-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 50K

Publishing Venue

IBM

Related People

Tsui, F: AUTHOR

Abstract

After initialization: H G F E D C B A Counter content shifted in. After initial loading of page A: A H G F E D C B Replacement of 1 page (see bottom line below). After initial loading of all pages: H G F E D C B A Random interim status: C A F D H B G E Use page F: F D H B G E C A X shifts until match found. After use of page F: F C A D H B C E (N-X) shortened ring shifts. After replacement of 1 page: E F C A D H B C 1 shift.

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

Page 1 of 3

Least Recently Used Replacement Control

After initialization: H G F E D C B A Counter content

shifted in. After initial loading of page A: A H G F E D C B Replacement of 1 page (see bottom line below). After initial loading of all pages: H G F E D C B A Random interim status: C A F D H B G E Use page F: F D H B G E C A X shifts until match found. After use of page F: F C A D H B C E (N-X) shortened ring shifts. After replacement of 1 page: E F C A D H B C 1 shift.

For the control of page replacement in memories (main stores or high-speed cache buffers), the "least recently used" (LRU) algorithm is usually preferred to the "first in first out" (FIFO) algorithm, because the former gives better performance.

For the control of N pages, R ring-shift registers (R being an integer (> or =) log(2)N) each consisting of N elements, an R-stage counter (capable of counting from 0 to N-1), and a "Match" latch (ML) are provided. The figure shows a schematic diagram of the arrangement for N=8, R=3.

The contents of the shift registers are sensed at their right ends. Each shift register is provided with a switchable bypass route at the input to the second leftmost element, allowing a shortened ring-shift register to be built consisting of (N-I) elements excluding he leftmost element.

The operation of the arrangement is briefly as follows:
1) At the initialization, the R shift registers are shifted

right N times with the counter content (a binary number

with R bits) being injected into their left ends. The

shift registers contain thereupon, in their N columns,

the binary numbers 0 to N-1, representing the encoded

addresses of N pages.
2) At the beginning of each updating due to the usage of a

page, the counter and the ML are set to 0.
3) Each time when page i (i = intege...