LRU önbelleğin tətbiqi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Capital One Cisco Citadel Birlik Kruiz avtomatlaşdırılması Dropbox eBay Expedia Facebook Goldman Sachs google microsoft Nutanix Kahin PayPal Pinterest Salesforce Snapchat Tesla Twilio Über VMware Walmart Laboratoriyaları Arzu Zillow
Layihə Əməliyyat SistemləriBaxılıb 104

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Ən az istifadə olunan (LRU) önbellek məlumatların istifadəsi üçün tələb olunan vaxtın minimum olması üçün məlumatları qorumaq üçün istifadə olunan bir metod növüdür. Önbellek dolduğunda istifadə olunan LRU alqoritmi. Sistemin önbellek yaddaşından ən az istifadə olunan məlumatları silirik. Bu, Cache yaddaşının ölçüsü və müraciət etməyimiz lazım olan səhifələrin verildiyi qədər həyəcan verici bir problemdir. Biz məlumatları a siyahı belə ki, məlumatlar artıq mövcuddursa, mövqeyini dəyişdirin və həmin elementi siyahının önünə qoyun. Başqa məlumatlar siyahının önünə əlavə edin.

LRU Keşi üçün İzahat

Aşağıdakı nümunəyə baxaraq LRU Cache Uygulaması üçün sürətli bir anlayışı görək - Önbellek yaddaşında müraciət etməli olduğumuz səhifə sayı 3, 5, 6, 1, 3, 7, 1-dir.

LRU önbelleğin tətbiqiPin

 

LRU önbelleğin tətbiqiPin

LRU önbelleğin tətbiqiPin

LRU önbelleğin tətbiqiPin

LRU önbelleğin tətbiqiPin

Pin

Pin

Pin

Qeyd: Burada 5 səhifəlik nöqsan və səhifəyə müraciət zamanı 2 səhifəlik zərbə var.

LRU önbelleğinin tətbiqi üçün tətbiqetmə

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

Zamanın mürəkkəbliyi

O (S * N) burada S önbellek ölçüsü, N isə müraciət etmək istədiyimiz səhifə sayıdır. Hər səhifə üçün mövcud olub olmadığını yoxlayırıq. Səhifənin vurulması baş verərsə, zamanın mürəkkəbliyi O (S) olan qaldırılma funksiyasından istifadə edin. Bir səhifə xətası baş verərsə, pop_front O (1) içindəki ilk elementi siləcəkdir. Səhifəni siyahının sonunda O (1) daxil edin.

References

Crack Sistemi Dizayn Müsahibələri
Translate »