Browse Prior Art Database

Alteration of a Partial LRU Algorithm to Temporarily Prevent Specific Slot Selections

IP.com Disclosure Number: IPCOM000102131D
Original Publication Date: 1990-Oct-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Reeve, SM: AUTHOR

Abstract

The idea of this disclosure is to alter an existing least-recently-used (LRU) algorithm to prevent a desired cache location from being selected for replacement.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 60% of the total text.

Alteration of a Partial LRU Algorithm to Temporarily Prevent Specific Slot Selections

       The idea of this disclosure is to alter an existing
least-recently-used (LRU) algorithm to prevent a desired cache
location from being selected for replacement.

      In a memory management system, the LRU algorithm is used to
keep the most recently used lines of data in the cache.  Since the
cache holds only part of the main memory, data must be swapped in and
out of the cache.  The LRU selected line will be swapped out and
replaced by a new line.  The information about the LRU algorithm is
saved within LRU bits that give the previous state of the algorithm.
To minimize the number of bits needed to record the information for
the algorithm, a partial LRU is used.

      Situations may occur where it is desirable to force the
algorithm to select a particular slot or not allow a slot to be
chosen for replacement.  The method described involves a slot being
"held."  A held slot is a slot that should not be chosen to be
replaced by the LRU algorithm.  Each of the slots may be held
independently of other slots.  The held slot conditions may change
each time the LRU algorithm is accessed.

      The method used to alter the LRU involves temporarily updating
the LRU bits so that all the held slots look like they were recently
accessed, which would then cause the LRU algorithm to not pick those
slots for replacement.  Thus, an LRU update for each held slot is
perfo...