Editing Cache replacement policies (section)

==== {{anchor|LRU Approximations}}LRU approximations ====
LRU may be expensive in caches with higher [[Associative property|associativity]]. Practical hardware usually employs an approximation to achieve similar performance at a lower hardware cost.

===== Pseudo-LRU (PLRU) =====
{{Further|Pseudo-LRU}}
For [[CPU caches]] with large [[CPU cache#Associativity|associativity]] (generally > four ways), the implementation cost of LRU becomes prohibitive. In many CPU caches, an algorithm that almost always discards one of the least recently used items is sufficient; many CPU designers choose a PLRU algorithm, which only needs one bit per cache item to work. PLRU typically has a slightly-worse miss ratio, slightly-better [[CAS latency|latency]], uses slightly less power than LRU, and has a lower [[Overhead (computing)|overhead]] than LRU.

Bits work as a binary tree of one-bit pointers which point to a less-recently-used sub-tree. Following the pointer chain to the leaf node identifies the replacement candidate. With an access, all pointers in the chain from the accessed way's leaf node to the root node are set to point to a sub-tree which does not contain the accessed path. The access sequence in the example is A B C D E:

[[File:Plruexample.png|center|alt=Graphic example of pseudo-LRU]]

When there is access to a value (such as A) and it is not in the cache, it is loaded from memory and placed in the block where the arrows are pointing in the example. After that block is placed, the arrows are flipped to point the opposite way. A, B, C and D are placed; E replaces A as the cache fills because that was where the arrows were pointing, and the arrows which led to A flip to point in the opposite direction (to B, the block which will be replaced on the next cache miss).

===== {{anchor|CLOCK-Pro}}Clock-Pro =====
The LRU algorithm cannot be implemented in the critical path of computer systems, such as [[operating system]]s, due to its high overhead; [[Page replacement algorithm#Clock|Clock]], an approximation of LRU, is commonly used instead. Clock-Pro is an approximation of [[LIRS caching algorithm|LIRS]] for low-cost implementation in systems.<ref>{{cite journal |last1=Jiang |first1=Song |last2=Chen |first2=Feng |last3=Zhang |first3=Xiaodong |date=2005 |title=CLOCK-Pro: An Effective Improvement of the CLOCK Replacement |url=http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-05-3.pdf |journal=Proceedings of the Annual Conference on USENIX Annual Technical Conference |publisher=USENIX Association |pages=323–336}}</ref> Clock-Pro has the basic Clock framework, with three advantages. It has three "clock hands" (unlike Clock's single "hand"), and can approximately measure the reuse distance of data accesses. Like LIRS, it can quickly evict one-time-access or low-[[Locality of reference|locality]] data items. Clock-Pro is as complex as Clock, and is easy to implement at low cost. The buffer-cache replacement implementation in the 2017 version of [[Linux]] combines LRU and Clock-Pro.<ref>{{cite web |date=2017-12-30 |title=Linux Memory Management: Page Replacement Design. |url=https://linux-mm.org/PageReplacementDesign |access-date=2020-06-30}}</ref><ref>{{cite web |date=2005-08-16 |title=A CLOCK-Pro page replacement implementation |url=https://lwn.net/Articles/147879/ |access-date=2020-06-30 |publisher=[[LWN.net]]}}</ref>