Browse Prior Art Database

Combination Replacement Algorithms

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

Publishing Venue

IBM

Related People

Chia, DK: AUTHOR [+2]

Abstract

This configuration replaces data on a combination of both the least used and first in, first out replacement algorithms.

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

Page 1 of 2

Combination Replacement Algorithms

This configuration replaces data on a combination of both the least used and first in, first out replacement algorithms.

Data in the memory 10 is divided into segments 12, each of which is split into a number of pages 14. Selection of a segment 12 for replacement is done on the basis of the least recently used (LRU) algorithm by shift registers 16, while within the segment 12 the page 14 selected for replacement is determined by registers 18 on a first in, first out (FIFO) basis.

Updating of the LRU shift register 16 is done whenever a request for data is received by the memory, while the FIFO counters 18 are updated by shifting the binary "1" stored therein one position to the right whenever replacement occurs within the segment they service. Since the FIFO algorithm is used to select pages for replacement, the possibility of an active page being replaced still exists. However, the probability of this occurring is reduced by the use of the LRU replacement selection of the segments. Alternatively, selection of the segment 12 for replacement can be done on the basis of the FIFO replacement algorithm by shift register 16, while within the segment 12 the page 14 selected for replacement is determined on a LRU basis by registers 18.

1

Page 2 of 2

2

[This page contains 3 pictures or other non-text objects]