LRU Cache Implemetation

 How to implement LRU caching scheme? What data structures should be used? 

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

Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size). The most recently used pages will be near front end and least recently pages will be near the rear end.

A Hash with page number as key and address of the corresponding queue node as value.

When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue. 

If the required page is not in memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of the queue, and add the new node to the front of the queue.

Example – Consider the following reference string : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5




/* We can use Java inbuilt Deque as a double ended queue to store the cache keys, with
the descending time of reference from front to back and a set container to check presence
of a key. But remove a key from the Deque using remove(), it takes O(N) time. This can be
optimized by storing a reference (iterator) to each key in a hash map. */

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Iterator;

public class LRUCache {

// store keys of cache
private Deque<Integer> doublyQueue;

// store references of key in cache
private HashSet<Integer> hashSet;

// maximum capacity of cache
private final int CACHE_SIZE;

LRUCache(int capacity) {
doublyQueue = new LinkedList<>();
hashSet = new HashSet<>();
CACHE_SIZE = capacity;
}

/* Refer the page within the LRU cache */
public void refer(int page) {
if (!hashSet.contains(page)) {
if (doublyQueue.size() == CACHE_SIZE) {
int last = doublyQueue.removeLast();
hashSet.remove(last);
}
}
else {/* The found page may not be always the last element, even if it's an
intermediate element that needs to be removed and added to the start
of the Queue */
doublyQueue.remove(page);
}
doublyQueue.push(page);
hashSet.add(page);
}

// display contents of cache
public void display() {
Iterator<Integer> itr = doublyQueue.iterator();
while (itr.hasNext()) {
System.out.print(itr.next() + " ");
}
}

public static void main(String[] args) {
LRUCache cache = new LRUCache(4);
cache.refer(1);
cache.refer(2);
cache.refer(3);
cache.refer(1);
cache.refer(4);
cache.refer(5);
cache.refer(2);
cache.refer(2);
cache.refer(1);
cache.display();
}
}

Output - 1, 2,5, 4














Comments

Post a Comment

Popular posts from this blog

Java 8 : Find the number starts with 1 from a list of integers

  List<Integer> list = List. of ( 12 , 32 , 14 , 15 , 56 ); //Result->12,14,15 List<String> listString = list.stream().map(String::valueOf).collect(Collectors.toList()); List<String> result1 = listString.stream().filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result1-->" +result1); List<String> result2 = list.stream().map(x->x+ "" ).filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result2-->" +result2);
Read more

Junit Mockito and Power Mockito

Mock vs Spy Both can be used to mock methods or fields. The difference is that  in mock, you are creating a complete mock or fake object while in spy, there is the real object and you just spying or stubbing specific methods of it . Mock vs InjectMock @Mock  creates a mock.  @InjectMocks  creates an instance of the class and injects the mocks that are created with the  @Mock  (or  @Spy ) annotations into this instance. Unit Testing Void Methods with Mockito and JUnit How to Test Void Methods  As we already know that our aim is to test void methods in a class. But it is also really important to understand why we test void methods.  Whenever we write unit test cases for any method, we expect a return value from the method. Generally, we use assert for checking if the method returns the value that we expect it to return, but in the case of void methods, they do not return any value. So how do we check if our method is functioning properly? Let’s...
Read more

Important Linux Commands

  ls -lrt → command lists the contents of the directory with all the details, in reverse order of their modification time (older files will be displayed first) ls -lrth → This will list the contents of the current directory showing more information and sorting them so the most recently modified file will be displayed last. The h flag makes the file sizes more human friendly! chmod 755 <name> → chmod 755 sets the 755 permission for a file. 755 means full permissions for the owner and read and execute permission for others. ln -s 14.9.0-SNAPSHOT current → Create a current tag and mapped to current version. To link files in the same directory Update Any File → sed -i 's/10.46.87.148/10.46.87.115/g' journal.sch textToFind → 10.46.87.148 replaceText → 10.46.87.115 FileName → journal.sch . SED is a text stream editor used on Unix systems to edit files quickly and efficiently Untar a tar file → tar -xvzf filename.tar Rmove a folder → rm -r folderName netstat -anpe | grep ...
Read more