Simplified LRU Buffer Select Subroutine
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Feb-02
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.