What is LRU caching?

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.

Importance

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.

Implementation

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.

Working

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 $-1$.

As the get(A1) function is executed, the following change takes place:

The get(F1) function returns $-1$. This is because we are trying to access the page that is not present in the hashmap, which also means that it is not present in the memory.

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:

Algorithm

1. Search hash map using page number to get the corresponding node address.
2. A page number is in the cache. If it appears in the hash table, it is referred to as a "cache hit." In this case, a get() function is used, which does the following:

• It finds the relevant linked list node by using the hash table.
• It pushes the corresponding node to the head of DDL.

3. If the page number has not existed in the hash table, it is known as a cache miss. In this case, a put() function is utilized, which does the following:

• If the cache is full, it gets the least recent page number that the cache utilized and removes it from the linked list and the hash map to make room for the new element.
• For the new element, it makes a new linked list node. It then adds it to the linked list's beginning and stores it in the hash table.

Runtime and space complexity

The time for get() is$O(1)$in the average-case scenario and$O(n)$in the worst-case scenario.

The time for put() is$O(1)$.

The space required is$O(n)$.

Advantages

• LRU caching is fast and efficient for data retrieval, updating, and removal in constant time.
• Its performance improves as the cache size increases.

Disadvantages

• LRU caching is expensive in terms of space complexity.
• We need a larger cache if we want good efficiency.

Click here to read more about the code implementation of LRU cache?