LRU Cache Implementation

Least Recently Used (LRU) Cache is a type of method which is used to maintain the data such that the time required to use the data is the minimum possible. LRU algorithm used when the cache is full. We remove the least recently used data from the cache memory of the system. This is so exciting problem in which the size of the Cache memory and the pages that we need to refer are given. We add the data in a list such that if the data is present already then change its position and put that element to the front of the list. Else add the data in front of the list.

Explanation For LRU Cache

Let’s see a quick understanding for LRU Cache Implementation by see the below example-  Number of pages which we need to refer in the cache memory are 3, 5, 6, 1, 3, 7,  1.

Note: Here we got 5-page fault and 2-page hit during page refer.

Implementation For LRU Cache Implementation

/*C++ Implementation of LRU Cache*/ 
#include<bits/stdc++.h> 
using namespace std;
void LRU_Cache(int pages[],int cache_size,int total_page)
{
    int page_hit=0,page_fault=0;
    list<int> cache;
    for(int i=0;i<total_page;i++)
    {
        list<int>::iterator itr; 
        itr=find(cache.begin(),cache.end(),pages[i]);
        /*page is not present in cache memory*/
        if(itr==cache.end())
        {
            page_fault++;
            int rand_size=cache.size();
            /*if cache is full*/
            if(rand_size==cache_size)
            {
                /*remove the least recently used page from cache*/
                int pop_element=cache.front();
                cache.pop_front();
                /*push page at the end of cache*/
                cache.push_back(pages[i]);
            }
            else//cache is not full;
            {
               cache.push_back(pages[i]);   
            }
        }
        else//page is present in cache;
        {
            page_hit++;
            /*remove the page from previous location*/
            cache.remove(pages[i]);
            /*make the page to most recently used by inserting it at end of list*/
            cache .push_back(pages[i]);
        }
    }
    /*print the page hit and page fault*/
    cout<<"Page Hit: "<<page_hit<<" "<<"Page Fault: "<<page_fault<<endl;
    cout<<"Cache containg pages: ";
    for(auto itr:cache)
    {
        cout<<itr<<" ";
    }
    cout<<endl;
}
int main() 
{ 
    int cache_size,total_page;
    /*take input the size of cache and total pages count*/
    cin>>cache_size>>total_page;
    int pages[total_page];
    /*input the pages which we want to refer*/
    for(int i=0;i<total_page;i++)
    {
        cin>>pages[i];
    }
    /*call LRU_Cache*/
    LRU_Cache(pages,cache_size,total_page);
    return 0; 
}

4 7
3 5 6 1 3 7 1

Page Hit: 2 Page Fault: 5
Cache containg pages: 6 3 7 1

Time Complexity

O(S*N) where S is the size of cache and N is the number of pages that we want to refer to. For every page, we check whether it is present or not. If page hit occur then use remove function which time complexity is O(S). If a page fault occurs then pop_front will remove the first element in O(1). For insert the page at the end of the list in O(1).

References