In operating systems, Least Recently Used caching is a cache eviction policy. It removes the most recently accessed page frames from the cache and makes space for newly inserted pages when the cache has reached its limit to get fewer cache misses and page faults.
Cache is used to store temporary data that is repeatedly accessed. However, the cache memory size is limited, which means that it has to eliminate unnecessary data and add new data. LRU enters the picture at this point.
For the implementation of the LRU cache, we need two data structures. These are as follows:
A doubly linked list (DLL) is implemented using a queue based on the FIFO approach. The pages accessed most recently will be toward the front, while those accessed least recently will be toward the end of the linked list. The primary reason to use DDL is to maintain the eviction order in constant time.
A hash map contains key and value pairs. The key holds the page number, while the value holds the address of a particular DDL node.
Let's suppose we have an empty doubly-linked list of size 4. The following operations will be performed on these two data structures:
put(A1,5)
put(C1,3)
put(B1,1)
put(G1,11)
get(A1)
get(F1)
put(Y1,7)
At first, when we look up the hashmap, it's empty, which means the cache is also unoccupied. We use the put()
function to cache the data into the DDL.
The DDL after the first entry will look as follows:
The same process will be followed for the three successive operations. The least recent accessed element will shift towards the tail end of the linked list, and the most recently accessed element will be moved to the beginning of the linked list.
The output will look as follows:
When the get()
function is first called, it checks if the corresponding page number is present in the hashmap. If it is, it will retrieve the element and push it towards the head of the linked list. If not, it will return
As the get(A1)
function is executed, the following change takes place:
The get(F1)
function returns
Now the cache has reached its limit and we must evict the element present at the tail end from the linked list to make space for the newly accessed element. To perform put(Y1,7)
, (C1,3)
must be removed from the linked list because it is the least recently used element.
The updated cache will be as follows:
get()
function is used, which does the following: put()
function is utilized, which does the following:The time for get()
is
The time for put()
is
The space required is
Click here to read more about the code implementation of LRU cache?
Free Resources