Browse Prior Art Database

Simplified LRU Buffer Select Subroutine

IP.com Disclosure Number: IPCOM000041486D
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 2 page(s) / 47K

Publishing Venue

IBM

Related People

Lindley, JV: AUTHOR

Abstract

An algorithm for selecting a LRU (Least Recently Used) buffer is described. This procedure is required in a system having a plurality of buffers, all of which are being used when a buffer is requested for a new task. One criteria for selecting which buffer is to be assigned to the requester is the least recently used buffer. This scheme requires only three bits (flags), no matter how many buffers are in the system. LRU selection algorithms usually require complicated bookkeeping steps that keep track of the number of times each buffer has been accessed and its length of time in use. In addition to being time consuming, the prior systems also require several bits per buffer, the number increasing with an increase in the number of buffers used in the system.

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

Page 1 of 2

Simplified LRU Buffer Select Subroutine

An algorithm for selecting a LRU (Least Recently Used) buffer is described. This procedure is required in a system having a plurality of buffers, all of which are being used when a buffer is requested for a new task. One criteria for selecting which buffer is to be assigned to the requester is the least recently used buffer. This scheme requires only three bits (flags), no matter how many buffers are in the system. LRU selection algorithms usually require complicated bookkeeping steps that keep track of the number of times each buffer has been accessed and its length of time in use. In addition to being time consuming, the prior systems also require several bits per buffer, the number increasing with an increase in the number of buffers used in the system. The algorithm to be described uses only three bits per buffer and requires a minimum amount of code and time to execute. Written as a subroutine to be entered when a new buffer is requested, the program operates as shown in the flowchart of the figure. It is assumed that the main program has previously initialized the buffer pointer, i. The value of i is incremented to point to a buffer in the list of buffers. The value of i is incremented modulo-m, where m is the maximum number of buffers in the list. That is, the pointer wraps around from the last value to its first value. Each buffer in the list has three flags assigned to it. A reference flag associated with the i-th...