Comment Re:Drawback (Score 0) 316
One easy way to implement exact LRU in software.... (doubly) linked list.
Each item points to its node in the linked list. On each access to an item move its node to the head of the list. When you need to evict, kick out the tail element. Alot of software cache simulators use this for exact LRU
This way you can maintain LRU by only changing a few pointers in a nice generic manner.
Also, since this would be fully associative with ALOT of associativity, the things that get evicted are the files that you nearly NEVER use.
Each item points to its node in the linked list. On each access to an item move its node to the head of the list. When you need to evict, kick out the tail element. Alot of software cache simulators use this for exact LRU
This way you can maintain LRU by only changing a few pointers in a nice generic manner.
Also, since this would be fully associative with ALOT of associativity, the things that get evicted are the files that you nearly NEVER use.
