|This article does not cite any sources. (April 2017) (Learn how and when to remove this template message)|
Pseudo-LRU or PLRU is a family of cache algorithms which improve on the performance of the Least Recently Used (LRU) algorithm by replacing values using approximate measures of age rather than maintaining the exact age of every value in the cache.
PLRU usually refers to two cache replacement algorithms: tree-PLRU and bit-PLRU.
Tree-PLRU is an efficient algorithm to select an item that most likely has not been accessed very recently, given a set of items and a sequence of access events to the items.
The algorithm works as follows: consider a binary search tree for the items in question. Each node of the tree has a one-bit flag denoting "go left to find a pseudo-LRU element" or "go right to find a pseudo-LRU element". To find a pseudo-LRU element, traverse the tree according to the values of the flags. To update the tree with an access to an item N, traverse the tree to find N and, during the traversal, set the node flags to denote the direction that is opposite to the direction taken.
Bit-PLRU stores one status bit for each cache line. We call these bits MRU-bits. Every access to a line sets its MRU-bit to 1, indicating that the line was recently used. Whenever the last remaining 0 bit of a set's status bits is set to 1, all other bits are reset to 0. At cache misses, the line with lowest index whose MRU-bit is 0 is replaced.
|This computer science article is a stub. You can help Wikipedia by expanding it.|