DS4Fun

Cache Replacement LRU Algorithm - (Least Recently Used) Least Recently Used algorithm, the name itself represents its behavior. When we use this algorithm with the cache replacement policy, it will always remove the least used page from the cache and make space for the currently used page. Based on the above statement, we have to think about the implementation of the same. We need a data structure where we have to add all the recently used data from the tail and remove it from the head. For Example:- We can store a maximum of 3 pages in our cache. Suppose, we have the request of pages as given below. 3 , 2 , 1 , 0 , 2 , 3 , 7 , 4 , 7 Cache Frame 2 1 0 2 3 7 4 7 1 2 2 1 0 2 3 7 4 0 3 3 3 2 1 0 2 3 3 Page Status Cache Miss Cache Miss Cache Miss Cache Miss Cache Hit Cache Miss Cache Miss Cache Miss Cache Hit We will follow the steps to push the missing pages into the cache for the performance. If the page is found then remove it and again push it on the top. If the size o...

Cache Replacement FIFO Algorithm - (First In First Out) Before, we understood how the cache replacement algorithm works using FIFO. We will just look for a while to understand the FIFO with the layman term. Suppose a company running a seminar and max capacity of the seminar hall is 100 employees. They have decided whoever comes first they will get the entry and once's seminar hall is full then wouldn't allow anyone. There is no priority to anyone or any designation. So, we will implement a cache replacement algorithm using the Queue abstract data type. We can implement a queue using ArrayList or LinkedList. Let's do the code and understand the implementation of the algorithm. Implement Cache Replacement FIFO policy using ArrayList import java.util.Arrays; import java.util.List; import java.util.Optional; /** * @author Chandra Shekhar Paatni on 26/04/20 */ public class CacheReplacementFIFO< T > { T [] cacheReplacementFIFOS ; int index = - 1 ; pu...

A cache is secure storage, where we store frequently used data/pages in a system. It gives us valuable advantages with respect to performance. Whenever we look at something in a system, it stores a duplicate copy of data into the cache and next time onward it will serve from the cache only until data is modified. It improves our performance in terms of recently used data from the cache instead of the main memory. There are two main terminologies used:- Cache hit :- If data found in a cache. Cache miss :- If data is not found in a cache. Cache has some limitations with respect to size. Whenever it is full, the respective algorithm will discard the item to make space for new data. Cache Replacement algorithms/policies are optimizing instructions to make a cache work with low latency and high throughput . We will discuss some of the cache replacement algorithms on the coming blog with their implementation.