LRU CACHE ALGORITHM

Algorithm to find the least recently used item in the cache.

WHAT IS LRU CACHE ?

We are given total possible page numbers that can be referred. We are also given cache (or memory) size (Number of page frames that cache can hold at a time). The LRU(least recent;y used ) caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache.

We use two data structures to implement an LRU Cache Algorithm .

1. QUEUE AS DOUBLY LINKED LIST
2. HASH TO STORE THE ADDRESS O THE PAGE STORED IN A QUEUE

So now the questions is ??

Why DLL(Doubly Linked List) used not simply linked list?

In general, finding an item in a linked list is O(n) time, since we need to walk the whole list. But the whole point of a cache is to get quick lookups.

How could we speed that up?

We’ll add in a hash map that maps items to linked list nodes: That lets us find an element in our cache’s linked list in O(1) time, instead of O(n).

ALGORITHM

Accessing and Evicting Putting things together, here are the steps we’d run through each time an item was accessed:

1. Look up the item in our hash map. If the item is in the hash table, then it’s already in our cache — this is called a “cache hit” Use the hash table to quickly find the corresponding linked list node.
2. Move the item’s linked list node to the head of the linked list, since it’s now the most recently used (so it shouldn’t get evicted any time soon). If the item isn’t in the hash table, we have a cache miss. We need to load the item into the cache: Is our cache full?
3. If so, we need to evict something to make room: Grab the least-recently used cache item — it’ll be at the tail of the linked list.
4. Evict that item from the cache by removing it from the linked list and the hash map.
5. Create a new linked list node for the item. Insert it at the head of the linked list.
6. Add the item to our hash map, storing the newly-created linked list node as the value.