Kaj je predpomnilnik LRU?

Algoritmi za zamenjavo predpomnilnika so učinkovito zasnovani za zamenjavo predpomnilnika, ko je prostor poln. The Najmanj nedavno uporabljeno (LRU) je eden od teh algoritmov. Kot že ime pove, ko je predpomnilnik poln, LRU izbere podatke, ki so bili nazadnje uporabljeni, in jih odstrani, da naredi prostor za nove podatke. Prednost podatkov v predpomnilniku se spreminja glede na potrebo po teh podatkih, tj. če so nekateri podatki pridobljeni ali posodobljeni pred kratkim, se prioriteta teh podatkov spremeni in dodeli najvišji prioriteti, prednost podatkov pa se zmanjša, če ostane neuporabljenih operacij po operacijah.

Kazalo

• Kaj je predpomnilnik LRU?
• Operacije v predpomnilniku LRU:
• Delovanje predpomnilnika LRU:
• Načini implementacije predpomnilnika LRU:
• Implementacija predpomnilnika LRU z uporabo čakalne vrste in zgoščevanja:
• Izvedba predpomnilnika LRU z uporabo dvojno povezanega seznama in zgoščevanja:
• Izvedba predpomnilnika LRU z uporabo Deque & Hashmap:
• Implementacija predpomnilnika LRU z uporabo Stack & Hashmap:
• Predpomnilnik LRU z implementacijo števca:
• Izvedba predpomnilnika LRU z uporabo lenih posodobitev:
• Analiza kompleksnosti predpomnilnika LRU:
• Prednosti predpomnilnika LRU:
• Slabosti predpomnilnika LRU:
• Realna uporaba predpomnilnika LRU:

LRU algoritem je standardni problem in ima lahko različice glede na potrebe, na primer v operacijskih sistemih LRU igra ključno vlogo, saj se lahko uporablja kot algoritem za zamenjavo strani, da se zmanjša število napak na strani.

Operacije v predpomnilniku LRU:

• LRUCache (kapaciteta c): Inicializirajte predpomnilnik LRU s pozitivno velikostjo c.
• dobiti (ključ) : vrne vrednost ključa ' k’ če je prisoten v predpomnilniku, sicer vrne -1. Posodobi tudi prioriteto podatkov v predpomnilniku LRU.
• postavi (ključ, vrednost): Posodobite vrednost ključa, če ta ključ obstaja. V nasprotnem primeru dodajte par ključ-vrednost v predpomnilnik. Če je število ključev preseglo zmogljivost predpomnilnika LRU, zavrzite najmanj nazadnje uporabljen ključ.

Delovanje predpomnilnika LRU:

Recimo, da imamo predpomnilnik LRU s kapaciteto 3 in bi radi izvedli naslednje operacije:

1. Vstavite (ključ=1, vrednost=A) v predpomnilnik
2. Vstavite (ključ=2, vrednost=B) v predpomnilnik
3. Vstavite (ključ=3, vrednost=C) v predpomnilnik
4. Pridobite (ključ=2) iz predpomnilnika
5. Pridobite (ključ=4) iz predpomnilnika
6. Vstavite (ključ=4, vrednost=D) v predpomnilnik
7. Vstavite (ključ=3, vrednost=E) v predpomnilnik
8. Pridobite (ključ=4) iz predpomnilnika
9. Vstavite (ključ=1, vrednost=A) v predpomnilnik

Zgornje operacije se izvajajo ena za drugo, kot je prikazano na spodnji sliki:

Podrobna razlaga vsake operacije:

1. Put (ključ 1, vrednost A) : Ker ima predpomnilnik LRU prazen kapacitet=3, ni potrebe po kakršni koli zamenjavi in ​​{1 : A} smo postavili na vrh, tj. {1 : A} ima najvišjo prednost.
2. Put (ključ 2, vrednost B) : Ker ima predpomnilnik LRU prazen kapacitet=2, spet ni potrebe po kakršni koli zamenjavi, toda zdaj ima {2 : B} najvišjo prednost in prednost {1 : A} se zmanjša.
3. Put (ključ 3, vrednost C) : Še vedno je 1 prazen prostor v predpomnilniku, zato postavite {3 : C} brez kakršne koli zamenjave, opazite, da je predpomnilnik poln in trenutni vrstni red od najvišje do najnižje je {3:C}, {2:B }, {1:A}.
4. Pridobi (ključ 2) : Zdaj vrnite vrednost ključa=2 med to operacijo, tudi ker je uporabljen ključ=2, je zdaj novi prednostni vrstni red {2:B}, {3:C}, {1:A}
5. Pridobite (ključ 4): Upoštevajte, da ključa 4 ni v predpomnilniku, za to operacijo vrnemo '-1'.
6. Put (ključ 4, vrednost D) : Opazujte, da je predpomnilnik POLN, zdaj uporabite algoritem LRU, da ugotovite, kateri ključ je bil nazadnje uporabljen. Ker je imel {1:A} najmanjšo prednost, odstranimo {1:A} iz našega predpomnilnika in postavimo {4:D} v predpomnilnik. Upoštevajte, da je novi prednostni vrstni red {4:D}, {2:B}, {3:C}
7. Put (ključ 3, vrednost E) : Ker je bil ključ=3 že prisoten v predpomnilniku z vrednostjo=C, ta operacija ne bo povzročila odstranitve nobenega ključa, temveč bo posodobila vrednost ključa=3 na ' IN' . Zdaj bo novi prednostni vrstni red postal {3:E}, {4:D}, {2:B}
8. Pridobi (ključ 4) : vrne vrednost ključa=4. Zdaj bo nova prioriteta postala {4:D}, {3:E}, {2:B}
9. Put (ključ 1, vrednost A) : Ker je naš predpomnilnik POLN, uporabite naš algoritem LRU, da ugotovite, kateri ključ je bil nazadnje uporabljen, in ker je imel {2:B} najmanjšo prednost, odstranite {2:B} iz našega predpomnilnika in postavite {1:A} v predpomnilnik. Zdaj je nov prednostni vrstni red {1:A}, {4:D}, {3:E}

Načini implementacije predpomnilnika LRU:

Predpomnilnik LRU je mogoče implementirati na različne načine in vsak programer lahko izbere drugačen pristop. Vendar pa so spodaj navedeni pogosto uporabljeni pristopi:

1. LRU z uporabo čakalne vrste in zgoščevanja
2. uporaba LRU Dvojno povezan seznam + zgoščevanje
3. LRU z uporabo Deque
4. LRU z uporabo sklada
5. uporaba LRU Protiizvedba
6. LRU z uporabo lenih posodobitev

Implementacija predpomnilnika LRU z uporabo čakalne vrste in zgoščevanja:

Za implementacijo predpomnilnika LRU uporabljamo dve podatkovni strukturi.

1. Čakalna vrsta se izvaja z uporabo dvojno povezanega seznama. Največja velikost čakalne vrste bo enaka skupnemu številu razpoložljivih okvirjev (velikost predpomnilnika). Nazadnje uporabljene strani bodo blizu sprednjega dela, najmanj nazadnje uporabljene strani pa blizu zadnjega dela.
2. Hash s številko strani kot ključem in naslovom ustreznega vozlišča čakalne vrste kot vrednostjo.

Ko se stran sklicuje, je zahtevana stran morda v pomnilniku. Če je v pomnilniku, moramo odklopiti vozlišče seznama in ga postaviti na čelo čakalne vrste.
Če zahtevane strani ni v pomnilniku, jo shranimo v pomnilnik. Preprosto povedano, dodamo novo vozlišče na začetek čakalne vrste in posodobimo ustrezen naslov vozlišča v zgoščeni vrednosti. Če je čakalna vrsta polna, torej so vsi okvirji polni, odstranimo vozlišče z zadnjega dela čakalne vrste in dodamo novo vozlišče na čelo čakalne vrste.

Ilustracija:

Razmislimo o operacijah, Nanaša se ključ x z v predpomnilniku LRU: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Opomba: Sprva v pomnilniku ni nobene strani.

Spodnje slike prikazujejo postopno izvajanje zgornjih operacij v predpomnilniku LRU.

Algoritem:

• Ustvarite razred LRUCache z deklaracijo seznama tipa int, neurejenega zemljevida tipa in spremenljivko za shranjevanje največje velikosti predpomnilnika
• V referenčni funkciji LRUCache
  • Če te vrednosti ni v čakalni vrsti, potisnite to vrednost pred čakalno vrsto in odstranite zadnjo vrednost, če je čakalna vrsta polna
  • Če je vrednost že prisotna, jo odstranite iz čakalne vrste in potisnite na začetek čakalne vrste
• V funkciji prikaza natisne LRUCache s čakalno vrsto, ki se začne od spredaj

Spodaj je izvedba zgornjega pristopa:

C++

plsql

>

>

C

globalna var. v js

>

>

Java

seznam programov python

>

>

Python3

>

>

C#

>

>

Javascript

polja v Javi

>

>

Izvedba predpomnilnika LRU z uporabo dvojno povezanega seznama in zgoščevanja :

Ideja je zelo osnovna, tj. nadaljujte z vstavljanjem elementov na glavo.

• če elementa ni na seznamu, ga dodajte na glavo seznama
• če je element prisoten na seznamu, ga premaknite v glavo in premaknite preostali element seznama

Upoštevajte, da bo prioriteta vozlišča odvisna od oddaljenosti tega vozlišča od glave, najbližje kot je vozlišče glavi, višjo prednost ima. Torej, ko je velikost predpomnilnika polna in moramo odstraniti kakšen element, odstranimo element, ki meji na rep dvojno povezanega seznama.

Implementacija predpomnilnika LRU z uporabo Deque & Hashmap:

Struktura podatkov Deque omogoča vstavljanje in brisanje s sprednje in končne strani, ta lastnost omogoča možno implementacijo LRU, saj lahko sprednji element predstavlja element z visoko prioriteto, medtem ko je končni element lahko element z nizko prioriteto, tj. Najmanj nedavno uporabljen.

Delo:

1. Pridobite operacijo : preveri, ali ključ obstaja v razpršenem zemljevidu predpomnilnika in sledi spodnjim primerom na deque:
   • Če je ključ najden:
     • Predmet velja za nedavno uporabljenega, zato je premaknjen na sprednji del deque.
     • Vrednost, povezana s ključem, je vrnjena kot rezultatget>delovanje.
   • Če ključa ni mogoče najti:
     • vrni -1, da nakaže, da tak ključ ni prisoten.
2. Postavite operacijo: Najprej preverite, ali ključ že obstaja v razpršenem zemljevidu predpomnilnika in sledite spodnjim primerom na deque
   • Če ključ obstaja:
     • Vrednost, povezana s ključem, je posodobljena.
     • Predmet je premaknjen na sprednji del deque, saj je zdaj nazadnje uporabljen.
   • Če ključ ne obstaja:
     • Če je predpomnilnik poln, to pomeni, da je treba vstaviti nov element, najmanj uporabljen element pa je treba odstraniti. To storite tako, da odstranite element s konca deque in ustrezen vnos iz razpršitvenega zemljevida.
     • Nov par ključ-vrednost se nato vstavi tako v zgoščeni zemljevid kot v sprednji del deque, da označi, da je to nazadnje uporabljen element.

Implementacija predpomnilnika LRU z uporabo Stack & Hashmap:

Implementacija predpomnilnika LRU (najmanj nedavno uporabljenega) z uporabo podatkovne strukture sklada in zgoščevanja je lahko nekoliko težavna, ker preprost sklad ne zagotavlja učinkovitega dostopa do elementa, ki je bil najmanj uporabljen. Vendar pa lahko združite sklad z zgoščenim zemljevidom, da to učinkovito dosežete. Tukaj je pristop na visoki ravni za njegovo izvajanje:

1. Uporabite Hash Map : Zgoščena karta bo shranila pare ključ-vrednost predpomnilnika. Ključi bodo preslikani v ustrezna vozlišča v skladu.
2. Uporabite Stack : Sklad bo ohranil vrstni red ključev glede na njihovo uporabo. Najmanj nedavno uporabljen element bo na dnu sklada, nazadnje uporabljen element pa na vrhu

Ta metoda ni tako učinkovita in se zato ne uporablja pogosto.

Predpomnilnik LRU z implementacijo števca:

Vsak blok v predpomnilniku bo imel svoj števec LRU, kamor spada vrednost števca od 0 do n-1} , tukaj ' n ' predstavlja velikost predpomnilnika. Blok, ki je spremenjen med zamenjavo bloka, postane blok MRU in posledično se njegova vrednost števca spremeni na n – 1. Vrednosti števca, večje od vrednosti števca dostopanega bloka, se zmanjšajo za eno. Preostali bloki so nespremenjeni.

Izvedba predpomnilnika LRU z uporabo lenih posodobitev:

Implementacija predpomnilnika LRU (najmanj nedavno uporabljenega) z uporabo lenih posodobitev je običajna tehnika za izboljšanje učinkovitosti delovanja predpomnilnika. Lene posodobitve vključujejo sledenje vrstnemu redu, v katerem se dostopa do elementov, ne da bi takoj posodobili celotno strukturo podatkov. Ko pride do napake v predpomnilniku, se lahko na podlagi nekaterih meril odločite, ali boste izvedli popolno posodobitev ali ne.

Analiza kompleksnosti predpomnilnika LRU:

• Časovna zapletenost:
  • Operacija Put(): O(1), tj. čas, potreben za vstavljanje ali posodobitev novega para ključ-vrednost, je konstanten
  • Operacija Get(): O(1), tj. čas, potreben za pridobitev vrednosti ključa, je konstanten
• Pomožni prostor: O(N), kjer je N zmogljivost predpomnilnika.

Prednosti predpomnilnika LRU:

• Hiter dostop : Dostop do podatkov iz predpomnilnika LRU traja O(1) časa.
• Hitra posodobitev : Posodabljanje para ključ-vrednost v predpomnilniku LRU traja O(1) časa.
• Hitro odstranjevanje najmanj uporabljenih podatkov : Potrebno je O(1) izbrisati tisto, kar ni bilo nedavno uporabljeno.
• Brez tresenja: LRU je manj dovzeten za udarce v primerjavi s FIFO, ker upošteva zgodovino uporabe strani. Zazna lahko, katere strani se pogosto uporabljajo, in jim dodeli prednost za dodelitev pomnilnika, s čimer zmanjša število napak strani in V/I operacij diska.

Slabosti predpomnilnika LRU:

• Za povečanje učinkovitosti potrebuje veliko velikost predpomnilnika.
• Za implementacijo je potrebna dodatna podatkovna struktura.
• Strojna pomoč je visoka.
• V LRU je odkrivanje napak težko v primerjavi z drugimi algoritmi.
• Ima omejeno sprejemljivost.

Realna uporaba predpomnilnika LRU:

• V Database Systems za hitre rezultate poizvedb.
• V operacijskih sistemih za zmanjšanje napak strani.
• Urejevalniki besedil in IDE za shranjevanje pogosto uporabljenih datotek ali izrezkov kode
• Omrežni usmerjevalniki in stikala uporabljajo LRU za povečanje učinkovitosti računalniškega omrežja
• V optimizacijah prevajalnika
• Orodja za predvidevanje besedila in samodokončanje