એલઆરયુ કેશ અમલીકરણ  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance કેપિટલ વન સિસ્કો સિટાડેલ સુસંગતતા ક્રુઝ Autoટોમેશન ડ્રૉપબૉક્સ ઇબે એક્સપેડિયા ફેસબુક ગોલ્ડમૅન સૅશ Google માઈક્રોસોફ્ટ ન્યુટનિક્સ ઓરેકલ પેપાલ Pinterest Salesforce Snapchat ટેસ્લા Twilio ઉબેર વીએમવેર વોલમાર્ટ લેબ્સ શુભેચ્છા ઝિલો
ડિઝાઇન ઓપેરેટીંગ સીસ્ટમ

ઓછામાં ઓછું તાજેતરમાં વપરાયેલ (LRU) કેશ એક પ્રકારની પદ્ધતિ છે જેનો ઉપયોગ ડેટાને જાળવવા માટે કરવામાં આવે છે જેથી ડેટાનો ઉપયોગ કરવા માટે જરૂરી સમય ઓછામાં ઓછો શક્ય હોય. જ્યારે કેશ ભરાય ત્યારે એલઆરયુ અલ્ગોરિધમનો ઉપયોગ થાય છે. અમે સિસ્ટમની કacheશ મેમરીમાંથી તાજેતરમાં ઉપયોગમાં લેવાયેલા ડેટાને દૂર કરીએ છીએ. આ ખૂબ જ રોમાંચક સમસ્યા છે જેમાં કેશ મેમરીનું કદ અને પૃષ્ઠો કે જેનો આપણે ઉલ્લેખ કરવો જરૂરી છે. અમે ડેટા એમાં ઉમેરીએ છીએ યાદી જેમ કે જો ડેટા પહેલેથી હાજર છે તો તેની સ્થિતિ બદલો અને તે તત્વને સૂચિની સામે મુકો. બાકી સૂચિની સામે ડેટા ઉમેરો.

એલઆરયુ કેશ માટે સમજૂતી  

ચાલો નીચેનાં ઉદાહરણ દ્વારા એલઆરયુ કેશ અમલીકરણ માટે ઝડપી સમજ જોઈએ- કેશ મેમરીમાં આપણે સંદર્ભ લેવાની જરૂર છે તે પૃષ્ઠોની સંખ્યા 3, 5, 6, 1, 3, 7, 1 છે.

એલઆરયુ કેશ અમલીકરણપિન

 

એલઆરયુ કેશ અમલીકરણપિન

એલઆરયુ કેશ અમલીકરણપિન

એલઆરયુ કેશ અમલીકરણપિન

એલઆરયુ કેશ અમલીકરણપિન

પિન

પિન

પિન

નૉૅધ: અહીં પૃષ્ઠ સંદર્ભ દરમ્યાન આપણને 5-પૃષ્ઠ ખામી અને 2-પૃષ્ઠ ફટકો પડ્યો.

એલઆરયુ કેશ અમલીકરણ માટે અમલીકરણ  

/*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

સમય જટિલતા  

ઓ (એસ * એન) જ્યાં એસ એ કેશનું કદ છે અને N એ પૃષ્ઠોની સંખ્યા છે જેને આપણે સંદર્ભિત કરવા માગીએ છીએ. દરેક પૃષ્ઠ માટે, અમે તપાસ કરીએ છીએ કે તે હાજર છે કે નહીં. જો પૃષ્ઠ હિટ થાય છે, તો તે સમય જટિલતા O (S) છે તે દૂર કરવા કાર્યનો ઉપયોગ કરો. જો કોઈ પૃષ્ઠ દોષ થાય છે, તો પ_પફ્રન્ટ ઓ (1) માં પ્રથમ તત્વને દૂર કરશે. O (1) માં સૂચિના અંતે પૃષ્ઠ દાખલ કરવા માટે.

આ પણ જુઓ
સ્ટ્રિંગ પાળીને લેટકોડ કરો

સંદર્ભ