Kas ir LRU kešatmiņa?

Kešatmiņas aizstāšanas algoritmi ir efektīvi izstrādāti, lai aizstātu kešatmiņu, kad vieta ir pilna. The Vismazāk lietots (LRU) ir viens no šiem algoritmiem. Kā norāda nosaukums, kad kešatmiņa ir pilna, LRU atlasa datus, kas ir vismazāk izmantoti, un noņem tos, lai atbrīvotu vietu jaunajiem datiem. Kešatmiņā esošo datu prioritāte mainās atkarībā no šo datu nepieciešamības, t.i., ja daži dati tiek ielādēti vai atjaunināti nesen, tad šo datu prioritāte tiks mainīta un piešķirta augstākajai prioritātei, un datu prioritāte samazinās, ja tā paliek neizmantotas operācijas pēc operācijām.

Satura rādītājs

• Kas ir LRU kešatmiņa?
• Darbības LRU kešatmiņā:
• LRU kešatmiņas darbība:
• LRU kešatmiņas ieviešanas veidi:
• LRU kešatmiņas ieviešana, izmantojot rindu un jaukšanu:
• LRU kešatmiņas ieviešana, izmantojot divkārši saistīto sarakstu un jaukšanu:
• LRU kešatmiņas ieviešana, izmantojot Deque & Hashmap:
• LRU kešatmiņas ieviešana, izmantojot Stack & Hashmap:
• LRU kešatmiņa, izmantojot Counter Implementation:
• LRU kešatmiņas ieviešana, izmantojot Lazy Updates:
• LRU kešatmiņas sarežģītības analīze:
• LRU kešatmiņas priekšrocības:
• LRU kešatmiņas trūkumi:
• LRU kešatmiņas reālā lietojumprogramma:

LRU algoritms ir standarta problēma, un tas var mainīties atkarībā no vajadzības, piemēram, operētājsistēmās LRU Tam ir izšķiroša nozīme, jo to var izmantot kā lapas aizstāšanas algoritmu, lai samazinātu lappušu kļūdas.

Darbības LRU kešatmiņā:

• LRUCache (ietilpība c): Inicializējiet LRU kešatmiņu ar pozitīva izmēra ietilpību c.
• saņemt (atslēgu) : atgriež atslēgas vērtību k' ja tas atrodas kešatmiņā, pretējā gadījumā tas atgriež -1. Atjaunina arī datu prioritāti LRU kešatmiņā.
• likt (atslēga, vērtība): Atjauniniet atslēgas vērtību, ja šī atslēga pastāv, pretējā gadījumā pievienojiet atslēgas vērtību pāri kešatmiņai. Ja atslēgu skaits pārsniedz LRU kešatmiņas ietilpību, noraidiet vismazāk izmantoto atslēgu.

LRU kešatmiņas darbība:

Pieņemsim, ka mums ir LRU kešatmiņa ar ietilpību 3, un mēs vēlētos veikt šādas darbības:

1. Ievietojiet (key=1, value=A) kešatmiņā
2. Ievietojiet (atslēga = 2, vērtība = B) kešatmiņā
3. Ievietojiet (key=3, value=C) kešatmiņā
4. Iegūstiet (atslēga=2) no kešatmiņas
5. Iegūstiet (atslēga=4) no kešatmiņas
6. Ievietojiet (key=4, value=D) kešatmiņā
7. Ievietojiet (key=3, value=E) kešatmiņā
8. Iegūstiet (atslēga=4) no kešatmiņas
9. Ievietojiet (key=1, value=A) kešatmiņā

Iepriekš minētās darbības tiek veiktas viena pēc otras, kā parādīts zemāk esošajā attēlā:

Detalizēts katras darbības skaidrojums:

1. Put (1. atslēga, A vērtība) : Tā kā LRU kešatmiņā ir tukša ietilpība = 3, nav nepieciešama nomaiņa, un mēs ievietojam {1 : A} augšpusē, t.i., {1 : A} ir augstākā prioritāte.
2. Put (2. atslēga, B vērtība) : Tā kā LRU kešatmiņā ir tukša ietilpība = 2, atkal nav nepieciešama nomaiņa, bet tagad {2 : B} ir augstākā prioritāte un prioritāte ir {1 : A} samazinājums.
3. Put (3. atslēga, vērtība C) : Kešatmiņā joprojām ir 1 brīva vieta, tāpēc ievietojiet {3 : C} bez aizstāšanas, ievērojiet, ka tagad kešatmiņa ir pilna un pašreizējā prioritātes secība no augstākās līdz zemākajai ir {3:C}, {2:B }, {1:A}.
4. Iegūt (2. atslēga) : Tagad šīs darbības laikā atgriežat atslēgas vērtību 2, arī tāpēc, ka tiek izmantota atslēga 2, tagad jaunā prioritātes secība ir {2:B}, {3:C}, {1:A}
5. Iegūt (4. atslēga): Ievērojiet, ka atslēgas 4 nav kešatmiņā, mēs atgriežam “-1” šai darbībai.
6. Put (4. atslēga, D vērtība) : ievērojiet, vai kešatmiņa ir PILNA, tagad izmantojiet LRU algoritmu, lai noteiktu, kura atslēga ir izmantota vismazāk. Tā kā {1:A} bija vismazākā prioritāte, noņemiet {1:A} no mūsu kešatmiņas un ievietojiet {4:D} kešatmiņā. Ņemiet vērā, ka jaunā prioritātes secība ir {4:D}, {2:B}, {3:C}
7. Put (3. atslēga, vērtība E) : Tā kā atslēga = 3 jau bija kešatmiņā ar vērtību = C, šī darbība neizraisīs nevienas atslēgas noņemšanu, bet gan atjauninās atslēgas = 3 vērtību uz ' UN' . Tagad jaunā prioritātes secība kļūs par {3:E}, {4:D}, {2:B}
8. Iegūt (4. atslēga) : atgriež atslēgas vērtību =4. Tagad jaunā prioritāte būs {4:D}, {3:E}, {2:B}
9. Put (1. atslēga, A vērtība) : Tā kā mūsu kešatmiņa ir PILNA, izmantojiet mūsu LRU algoritmu, lai noteiktu, kura atslēga tika izmantota vismazāk, un, tā kā atslēgai {2:B} bija vismazākā prioritāte, noņemiet {2:B} no mūsu kešatmiņas un ievietojiet {1:A} kešatmiņa. Tagad jaunā prioritātes secība ir {1:A}, {4:D}, {3:E}

LRU kešatmiņas ieviešanas veidi:

LRU kešatmiņu var ieviest dažādos veidos, un katrs programmētājs var izvēlēties citu pieeju. Tomēr tālāk ir norādītas visbiežāk izmantotās metodes:

1. LRU, izmantojot rindu un jaukšanu
2. LRU izmantojot Divkārši saistīts saraksts + jaukšana
3. LRU, izmantojot Deque
4. LRU, izmantojot Stack
5. LRU izmantojot Counter ieviešana
6. LRU, izmantojot Lazy Updates

LRU kešatmiņas ieviešana, izmantojot rindu un jaukšanu:

Mēs izmantojam divas datu struktūras, lai ieviestu LRU kešatmiņu.

1. Rinda tiek ieviests, izmantojot divkārši saistītu sarakstu. Maksimālais rindas lielums būs vienāds ar kopējo pieejamo kadru skaitu (kešatmiņas lielums). Pēdējās izmantotās lapas atradīsies tuvu priekšpusei un vismazāk izmantotās lapas būs tuvu aizmugurei.
2. Hašs ar lapas numuru kā atslēgu un atbilstošā rindas mezgla adresi kā vērtību.

Atsaucoties uz lapu, vajadzīgā lapa var būt atmiņā. Ja tas ir atmiņā, mums ir jāatvieno saraksta mezgls un jānogādā tas rindas priekšgalā.
Ja vajadzīgā lapa nav atmiņā, mēs to ievietojam atmiņā. Vienkāršiem vārdiem sakot, mēs pievienojam jaunu mezglu rindas priekšpusē un atjauninām atbilstošo mezgla adresi jaucējkodā. Ja rinda ir pilna, t.i., visi kadri ir pilni, mēs noņemam mezglu no rindas aizmugures un pievienojam jauno mezglu rindas priekšpusē.

Ilustrācija:

Apskatīsim operācijas, Atsaucas taustiņu x ar LRU kešatmiņā: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Piezīme: Sākotnēji atmiņā nav nevienas lapas.

Zemāk redzamajos attēlos soli pa solim parādīta iepriekš minēto darbību izpilde LRU kešatmiņā.

rudyard kipling ja paskaidrojums

Algoritms:

• Izveidojiet klasi LRUCache, deklarējot int tipa sarakstu, nesakārtotu tipa karti , un mainīgais, lai saglabātu maksimālo kešatmiņas lielumu
• LRUcache atsauces funkcijā
  • Ja šīs vērtības rindā nav, nospiediet šo vērtību rindas priekšā un noņemiet pēdējo vērtību, ja rinda ir pilna
  • Ja vērtība jau ir, noņemiet to no rindas un ievietojiet to rindas priekšpusē
• Displeja funkcijā drukājiet LRUCache, izmantojot rindu, sākot no priekšpuses

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

C++

>

pyspark

>

C

>

>

Java

>

>

Python3

>

>

iemet java izņēmumu apstrādi

C#

>

>

kas ir hashset java

Javascript

>

>

LRU kešatmiņas ieviešana, izmantojot divkārši saistīto sarakstu un jaukšanu :

Ideja ir ļoti vienkārša, t.i., turpiniet ievietot elementus galvā.

• ja elements nav iekļauts sarakstā, pievienojiet to saraksta sākumā
• ja elements ir sarakstā, pārvietojiet elementu uz galveni un pārvietojiet pārējo saraksta elementu

Ņemiet vērā, ka mezgla prioritāte būs atkarīga no šī mezgla attāluma no galvas, jo vistuvāk mezgls atrodas galvai, jo augstāka ir tā prioritāte. Tātad, kad kešatmiņas lielums ir pilns un mums ir jānoņem kāds elements, mēs noņemam elementu, kas atrodas blakus divkārši saistītā saraksta astei.

objekts Java

LRU kešatmiņas ieviešana, izmantojot Deque & Hashmap:

Deque datu struktūra ļauj ievietot un dzēst gan no priekšpuses, gan no gala, šis rekvizīts ļauj ieviest LRU, jo priekšējais elements var būt augstas prioritātes elements, savukārt beigu elements var būt zemas prioritātes elements, t.i., vismazāk izmantotais.

Darbojas:

1. Saņemt operāciju : pārbauda, ​​vai atslēga pastāv kešatmiņas jaucējkartē, un izpildiet tālāk norādītos gadījumus dekvē:
   • Ja atslēga ir atrasta:
     • Prece tiek uzskatīta par nesen lietotu, tāpēc tā tiek pārvietota uz dekas priekšpusi.
     • Ar atslēgu saistītā vērtība tiek atgriezta kā rezultātsget>darbība.
   • Ja atslēga netiek atrasta:
     • atgriezt -1, lai norādītu, ka šādas atslēgas nav.
2. Ievietošanas darbība: Vispirms pārbaudiet, vai atslēga jau pastāv kešatmiņas jaucējkartē, un izpildiet tālāk norādītos gadījumus deque
   • Ja atslēga pastāv:
     • Ar atslēgu saistītā vērtība tiek atjaunināta.
     • Vienums tiek pārvietots uz dekas priekšpusi, jo tagad tas ir nesen izmantots.
   • Ja atslēga neeksistē:
     • Ja kešatmiņa ir pilna, tas nozīmē, ka ir jāievieto jauns vienums un jāizņem vismazāk izmantotā prece. Tas tiek darīts, noņemot vienumu no deque beigām un atbilstošo ierakstu no hash kartes.
     • Pēc tam jaunais atslēgas-vērtības pāris tiek ievietots gan jaucējkartē, gan deque priekšpusē, lai norādītu, ka tas ir pēdējais izmantotais vienums.

LRU kešatmiņas ieviešana, izmantojot Stack & Hashmap:

LRU (vismazāk izmantotās) kešatmiņas ieviešana, izmantojot steka datu struktūru un jaukšanu, var būt nedaudz sarežģīta, jo vienkārša steka nenodrošina efektīvu piekļuvi vismazāk izmantotajam vienumam. Tomēr, lai to panāktu efektīvi, varat apvienot kaudzi ar jaucējkarti. Šeit ir augsta līmeņa pieeja tās ieviešanai:

1. Izmantojiet jaucējkarti : jaucējkarte saglabās kešatmiņas atslēgu un vērtību pārus. Atslēgas tiks kartētas uz atbilstošajiem steka mezgliem.
2. Izmantojiet kaudzi : steka saglabās atslēgu secību, pamatojoties uz to lietojumu. Visretāk lietotā prece būs kaudzes apakšā, bet pēdējā lietotā prece būs augšpusē

Šī pieeja nav tik efektīva, un tāpēc to neizmanto bieži.

LRU kešatmiņa, izmantojot Counter Implementation:

Katram kešatmiņas blokam būs savs LRU skaitītājs, kuram pieder skaitītāja vērtība No 0 līdz n-1} , šeit ' n ' apzīmē kešatmiņas lielumu. Bloks, kas tiek mainīts bloka nomaiņas laikā, kļūst par MRU bloku, un rezultātā tā skaitītāja vērtība tiek mainīta uz n – 1. Skaitītāja vērtības, kas ir lielākas par pieejamā bloka skaitītāja vērtību, tiek samazinātas par vienu. Pārējie bloki ir nemainīgi.

LRU kešatmiņas ieviešana, izmantojot Lazy Updates:

LRU (vismazāk izmantotās) kešatmiņas ieviešana, izmantojot slinkus atjauninājumus, ir izplatīts paņēmiens, lai uzlabotu kešatmiņas darbību efektivitāti. Slinki atjauninājumi ietver secības izsekošanu, kādā vienumiem tiek piekļūts, nekavējoties neatjauninot visu datu struktūru. Ja notiek kešatmiņas izlaidums, varat izlemt, vai veikt pilnu atjaunināšanu, pamatojoties uz dažiem kritērijiem.

LRU kešatmiņas sarežģītības analīze:

• Laika sarežģītība:
  • Operācija Put(): O(1), t.i., laiks, kas nepieciešams, lai ievietotu vai atjauninātu jaunu atslēgas vērtību pāri, ir nemainīgs
  • Get() operācija: O(1), t.i., laiks, kas nepieciešams atslēgas vērtības iegūšanai, ir nemainīgs
• Palīgtelpa: O(N), kur N ir kešatmiņas ietilpība.

LRU kešatmiņas priekšrocības:

• Ātra piekļuve : Lai piekļūtu datiem no LRU kešatmiņas, nepieciešams O(1) laiks.
• Ātra atjaunināšana : Atslēgas vērtību pāra atjaunināšana LRU kešatmiņā aizņem O(1) laiku.
• Ātra vismazāk izmantoto datu noņemšana : Nepieciešams O(1) izdzēst to, kas nesen nav izmantots.
• Bez dauzīšanas: Salīdzinot ar FIFO, LRU ir mazāk uzņēmīga pret sagraušanu, jo tā ņem vērā lapu lietošanas vēsturi. Tas var noteikt, kuras lapas tiek bieži izmantotas, un noteikt tām atmiņas piešķiršanas prioritāti, samazinot lappušu kļūdu skaitu un diska I/O darbību.

LRU kešatmiņas trūkumi:

• Lai palielinātu efektivitāti, ir nepieciešams liels kešatmiņas lielums.
• Lai to ieviestu, ir jāievieš papildu datu struktūra.
• Aparatūras palīdzība ir augsta.
• LRU kļūdu noteikšana ir sarežģīta salīdzinājumā ar citiem algoritmiem.
• Tam ir ierobežota pieņemamība.

LRU kešatmiņas reālā lietojumprogramma:

• Datu bāzu sistēmās, lai ātri iegūtu vaicājumu rezultātus.
• Operētājsistēmās, lai samazinātu lapu kļūdas.
• Teksta redaktori un IDE, lai saglabātu bieži lietotus failus vai koda fragmentus
• Tīkla maršrutētāji un slēdži izmanto LRU, lai palielinātu datortīkla efektivitāti
• Kompilatoru optimizācijās
• Teksta prognozēšanas un automātiskās pabeigšanas rīki