Čo je vyrovnávacia pamäť LRU?

Algoritmy na nahradenie vyrovnávacej pamäte sú efektívne navrhnuté tak, aby nahradili vyrovnávaciu pamäť, keď je miesto plné. The Najmenej nedávno použité (LRU) je jedným z týchto algoritmov. Ako už názov napovedá, keď je vyrovnávacia pamäť plná, LRU vyberie údaje, ktoré boli naposledy použité, a odstráni ich, aby sa vytvoril priestor pre nové údaje. Priorita údajov vo vyrovnávacej pamäti sa mení podľa potreby týchto údajov, t. j. ak sa niektoré údaje načítajú alebo aktualizujú nedávno, priorita týchto údajov by sa zmenila a priradila by sa najvyššej priorite a priorita údajov sa zníži, ak zostáva nevyužité operácie po operáciách.

Obsah

• Čo je vyrovnávacia pamäť LRU?
• Operácie na vyrovnávacej pamäti LRU:
• Fungovanie vyrovnávacej pamäte LRU:
• Spôsoby implementácie vyrovnávacej pamäte LRU:
• Implementácia vyrovnávacej pamäte LRU pomocou frontu a hashovania:
• Implementácia vyrovnávacej pamäte LRU pomocou dvojitého prepojeného zoznamu a hašovania:
• Implementácia vyrovnávacej pamäte LRU pomocou Deque & Hashmap:
• Implementácia vyrovnávacej pamäte LRU pomocou Stack & Hashmap:
• Cache LRU pomocou implementácie Counter:
• Implementácia vyrovnávacej pamäte LRU pomocou Lazy Updates:
• Analýza zložitosti vyrovnávacej pamäte LRU:
• Výhody vyrovnávacej pamäte LRU:
• Nevýhody vyrovnávacej pamäte LRU:
• Aplikácia vyrovnávacej pamäte LRU v reálnom svete:

LRU Algoritmus je štandardný problém a môže mať odchýlky podľa potreby, napríklad v operačných systémoch LRU hrá kľúčovú úlohu, pretože sa dá použiť ako algoritmus na nahradenie stránky, aby sa minimalizovali chyby stránky.

Operácie na vyrovnávacej pamäti LRU:

• LRUCache (kapacita c): Inicializujte vyrovnávaciu pamäť LRU s kapacitou kladnej veľkosti c.
• dostať (kľúč) : Vráti hodnotu kľúča ' k' ak je prítomný vo vyrovnávacej pamäti, inak vráti -1. Aktualizuje tiež prioritu údajov vo vyrovnávacej pamäti LRU.
• vložiť (kľúč, hodnota): Aktualizujte hodnotu kľúča, ak tento kľúč existuje. V opačnom prípade pridajte pár kľúč – hodnota do vyrovnávacej pamäte. Ak počet kľúčov prekročil kapacitu vyrovnávacej pamäte LRU, zrušte kľúč, ktorý ste použili naposledy.

Fungovanie vyrovnávacej pamäte LRU:

Predpokladajme, že máme vyrovnávaciu pamäť LRU s kapacitou 3 a chceli by sme vykonať nasledujúce operácie:

1. Vložte (kľúč=1, hodnota=A) do vyrovnávacej pamäte
2. Vložte (kľúč=2, hodnota=B) do vyrovnávacej pamäte
3. Vložte (kľúč=3, hodnota=C) do vyrovnávacej pamäte
4. Získajte (kľúč=2) z vyrovnávacej pamäte
5. Získajte (kľúč=4) z vyrovnávacej pamäte
6. Vložte (kľúč=4, hodnota=D) do vyrovnávacej pamäte
7. Vložte (kľúč=3, hodnota=E) do vyrovnávacej pamäte
8. Získajte (kľúč=4) z vyrovnávacej pamäte
9. Vložte (kľúč=1, hodnota=A) do vyrovnávacej pamäte

Vyššie uvedené operácie sa vykonávajú jedna po druhej, ako je znázornené na obrázku nižšie:

Podrobné vysvetlenie každej operácie:

1. Vložte (kľúč 1, hodnota A) : Keďže vyrovnávacia pamäť LRU má prázdnu kapacitu = 3, nie je potrebná žiadna výmena a na začiatok umiestnime {1 : A}, t. j. {1 : A} má najvyššiu prioritu.
2. Vložte (kľúč 2, hodnota B) : Keďže vyrovnávacia pamäť LRU má prázdnu kapacitu=2, opäť nie je potrebná žiadna výmena, ale teraz má {2 : B} najvyššiu prioritu a prioritu zníženia {1 : A}.
3. Vložte (kľúč 3, hodnota C) : Vo vyrovnávacej pamäti je stále 1 voľné miesto, preto vložte {3 : C} bez náhrady, všimnite si, že teraz je vyrovnávacia pamäť plná a aktuálne poradie priorít od najvyššej po najnižšiu je {3:C}, {2:B }, {1:A}.
4. Získať (kľúč 2) : Teraz vráťte hodnotu kľúča=2 počas tejto operácie, aj keď sa používa kľúč=2, nové poradie priority je teraz {2:B}, {3:C}, {1:A}
5. Získajte (kľúč 4): Všimnite si, že kľúč 4 nie je prítomný vo vyrovnávacej pamäti, pre túto operáciu vrátime „-1“.
6. Vložte (kľúč 4, hodnota D) : Všimnite si, že vyrovnávacia pamäť je PLNÁ, teraz pomocou algoritmu LRU zistite, ktorý kľúč bol použitý naposledy. Keďže {1:A} malo najmenšiu prioritu, odstráňte {1:A} z našej vyrovnávacej pamäte a vložte {4:D} do vyrovnávacej pamäte. Všimnite si, že nové poradie priority je {4:D}, {2:B}, {3:C}
7. Vložte (kľúč 3, hodnota E) : Keďže kľúč=3 bol už prítomný vo vyrovnávacej pamäti s hodnotou=C, táto operácia nebude mať za následok odstránenie žiadneho kľúča, ale aktualizuje hodnotu kľúča=3 na „ AND' . Teraz sa nové poradie priority zmení na {3:E}, {4:D}, {2:B}
8. Získať (kľúč 4) : Vráti hodnotu kľúča=4. Teraz sa nová priorita stane {4:D}, {3:E}, {2:B}
9. Vložte (kľúč 1, hodnota A) : Keďže naša vyrovnávacia pamäť je PLNÁ, použite náš algoritmus LRU na určenie, ktorý kľúč bol naposledy použitý, a keďže {2:B} mal najmenšiu prioritu, odstráňte {2:B} z našej vyrovnávacej pamäte a vložte {1:A} do cache. Teraz je nové poradie priority {1:A}, {4:D}, {3:E}

Spôsoby implementácie vyrovnávacej pamäte LRU:

LRU cache môže byť implementovaná rôznymi spôsobmi a každý programátor si môže zvoliť iný prístup. Nižšie sú však bežne používané prístupy:

1. LRU pomocou fronty a hashovania
2. pomocou LRU Dvojito prepojený zoznam + hašovanie
3. LRU pomocou Deque
4. LRU pomocou zásobníka
5. pomocou LRU Implementácia pultu
6. LRU pomocou Lazy Updates

Implementácia vyrovnávacej pamäte LRU pomocou frontu a hashovania:

Na implementáciu vyrovnávacej pamäte LRU používame dve dátové štruktúry.

preity zinta

1. Fronta sa implementuje pomocou dvojito prepojeného zoznamu. Maximálna veľkosť frontu sa bude rovnať celkovému počtu dostupných snímok (veľkosť vyrovnávacej pamäte). Naposledy použité strany budú blízko prednej strany a najmenej naposledy použité strany budú blízko zadnej strany.
2. A Hash s číslom stránky ako kľúčom a adresou zodpovedajúceho uzla frontu ako hodnotou.

Keď sa na stránku odkazuje, požadovaná stránka môže byť v pamäti. Ak je v pamäti, musíme odpojiť uzol zoznamu a priviesť ho do popredia frontu.
Ak požadovaná stránka nie je v pamäti, prenesieme ju do pamäte. Jednoducho povedané, pridáme nový uzol na začiatok frontu a aktualizujeme zodpovedajúcu adresu uzla v hash. Ak je front plný, t. j. všetky rámce sú plné, odstránime uzol zo zadnej časti frontu a nový uzol pridáme do prednej časti frontu.

Ilustrácia:

Pozrime sa na operácie, Odkazy kľúč X s vo vyrovnávacej pamäti LRU: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Poznámka: Na začiatku nie je v pamäti žiadna stránka.

Nižšie uvedené obrázky ukazujú krok za krokom vykonávanie vyššie uvedených operácií na vyrovnávacej pamäti LRU.

Algoritmus:

• Vytvorte triedu LRUCache s deklarovaním zoznamu typu int, neusporiadanej mapy typu a premenná na uloženie maximálnej veľkosti vyrovnávacej pamäte
• V referenčnej funkcii LRUCache
  • Ak sa táto hodnota nenachádza vo fronte, posuňte túto hodnotu pred front a odstráňte poslednú hodnotu, ak je front plný
  • Ak je hodnota už prítomná, odstráňte ju z frontu a zatlačte ju do prednej časti frontu
• V zobrazení funkcie tlače, LRUCache pomocou fronty začínajúce spredu

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++

>

>

C

>

>

char to int java

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

Implementácia vyrovnávacej pamäte LRU pomocou dvojitého prepojeného zoznamu a hašovania :

Myšlienka je veľmi základná, t.j. vkladať prvky do hlavy.

• ak sa prvok v zozname nenachádza, pridajte ho na začiatok zoznamu
• ak je prvok prítomný v zozname, presuňte prvok na začiatok a posuňte zostávajúci prvok zoznamu

Všimnite si, že priorita uzla bude závisieť od vzdialenosti tohto uzla od hlavy, čím je uzol najbližšie k hlave, tým vyššiu prioritu má. Takže keď je veľkosť vyrovnávacej pamäte plná a potrebujeme odstrániť nejaký prvok, odstránime prvok susediaci s koncom dvojito prepojeného zoznamu.

Implementácia vyrovnávacej pamäte LRU pomocou Deque & Hashmap:

Štruktúra údajov Deque umožňuje vkladanie a vymazávanie spredu aj z konca, táto vlastnosť umožňuje implementáciu LRU, pretože predný prvok môže predstavovať prvok s vysokou prioritou, zatiaľ čo koncový prvok môže byť prvkom s nízkou prioritou, t. j. Najmenej naposledy použitý.

pracuje:

1. Získajte operáciu : Skontroluje, či kľúč existuje v hašovacej mape vyrovnávacej pamäte, a postupujte podľa nasledujúcich prípadov na deque:
   • Ak sa nájde kľúč:
     • Položka sa považuje za nedávno použitú, preto sa presunie na prednú stranu deque.
     • Hodnota spojená s kľúčom sa vráti ako výsledokget>prevádzka.
   • Ak sa kľúč nenájde:
     • návrat -1 na označenie, že takýto kľúč neexistuje.
2. Vložte operáciu: Najprv skontrolujte, či kľúč už existuje v hašovacej mape vyrovnávacej pamäte a postupujte podľa nižšie uvedených prípadov na deque
   • Ak kľúč existuje:
     • Hodnota spojená s kľúčom sa aktualizuje.
     • Položka sa presunie na prednú časť deque, pretože je teraz naposledy použitá.
   • Ak kľúč neexistuje:
     • Ak je vyrovnávacia pamäť plná, znamená to, že je potrebné vložiť novú položku a najmenej nedávno použitú položku je potrebné odstrániť. To sa robí odstránením položky z konca deque a zodpovedajúcej položky z hash mapy.
     • Nový pár kľúč-hodnota sa potom vloží do hašovacej mapy aj na prednú stranu deque, aby znamenal, že ide o naposledy použitú položku

Implementácia vyrovnávacej pamäte LRU pomocou Stack & Hashmap:

Implementácia vyrovnávacej pamäte LRU (Najmenej nedávno použitá) pomocou štruktúry údajov zásobníka a hašovania môže byť trochu zložitejšia, pretože jednoduchý zásobník neposkytuje efektívny prístup k najmenej nedávno použitej položke. Môžete však kombinovať zásobník s hash mapou, aby ste to dosiahli efektívne. Tu je prístup na vysokej úrovni na jeho implementáciu:

1. Použite hashovú mapu : Hašovacia mapa bude uchovávať páry kľúč – hodnota vyrovnávacej pamäte. Kľúče sa namapujú na zodpovedajúce uzly v zásobníku.
2. Použite zásobník : Zásobník zachová poradie kľúčov na základe ich použitia. Najmenej použitá položka bude v spodnej časti zásobníka a naposledy použitá položka bude v hornej časti

Tento prístup nie je taký efektívny, a preto sa často nepoužíva.

Cache LRU pomocou implementácie Counter:

Každý blok vo vyrovnávacej pamäti bude mať svoj vlastný počítadlo LRU, do ktorého patrí hodnota počítadla {0 až n-1} , tu ' n ‘ predstavuje veľkosť vyrovnávacej pamäte. Blok, ktorý sa zmení pri výmene bloku, sa stane blokom MRU a v dôsledku toho sa jeho hodnota počítadla zmení na n – 1. Hodnoty počítadla väčšie ako hodnota počítadla prístupového bloku sa znížia o jednu. Zvyšné bloky sú nezmenené.

Implementácia vyrovnávacej pamäte LRU pomocou Lazy Updates:

Implementácia vyrovnávacej pamäte LRU (Najmenej nedávno použitá) pomocou lenivých aktualizácií je bežnou technikou na zlepšenie efektívnosti operácií vyrovnávacej pamäte. Lenivé aktualizácie zahŕňajú sledovanie poradia prístupu k položkám bez okamžitej aktualizácie celej štruktúry údajov. Keď dôjde k vynechaniu vyrovnávacej pamäte, môžete sa na základe určitých kritérií rozhodnúť, či vykonáte úplnú aktualizáciu alebo nie.

Analýza zložitosti vyrovnávacej pamäte LRU:

• Časová zložitosť:
  • Operácia Put(): O(1) t.j. čas potrebný na vloženie alebo aktualizáciu nového páru kľúč – hodnota je konštantný
  • Operácia Get(): O(1) t.j. čas potrebný na získanie hodnoty kľúča je konštantný
• Pomocný priestor: O(N), kde N je kapacita vyrovnávacej pamäte.

Výhody vyrovnávacej pamäte LRU:

• Rýchly prístup : Prístup k údajom z vyrovnávacej pamäte LRU trvá O(1).
• Rýchla aktualizácia : Aktualizácia páru kľúč – hodnota vo vyrovnávacej pamäti LRU trvá O(1).
• Rýchle odstránenie údajov, ktoré boli naposledy použité : Trvá O(1) odstrániť to, čo nebolo nedávno použité.
• Žiadne mlátenie: LRU je v porovnaní s FIFO menej náchylný na mlátenie, pretože zohľadňuje históriu používania stránok. Dokáže zistiť, ktoré stránky sa často používajú, a uprednostniť ich pri prideľovaní pamäte, čím sa zníži počet chýb stránok a diskových I/O operácií.

Nevýhody vyrovnávacej pamäte LRU:

• Vyžaduje veľkú veľkosť vyrovnávacej pamäte na zvýšenie efektívnosti.
• Vyžaduje si to implementáciu dodatočnej dátovej štruktúry.
• Hardvérová pomoc je vysoká.
• V LRU je detekcia chýb v porovnaní s inými algoritmami obtiažna.
• Má obmedzenú prijateľnosť.

Aplikácia vyrovnávacej pamäte LRU v reálnom svete:

• V databázových systémoch pre rýchle výsledky dotazov.
• V operačných systémoch na minimalizáciu chýb stránok.
• Textové editory a IDE na ukladanie často používaných súborov alebo útržkov kódu
• Sieťové smerovače a prepínače využívajú LRU na zvýšenie efektívnosti počítačovej siete
• V optimalizácii kompilátora
• Nástroje na predpovedanie textu a automatické dopĺňanie