b algoritmul de înlocuire a Cache-ului
cel mai eficient algoritm de cache ar fi să aruncați întotdeauna informațiile care nu vor fi necesare pentru cea mai lungă perioadă de timp în viitor. Acest rezultat optim este denumit algoritmul optim al B-Ului/Politica de înlocuire pur și simplu optimă sau algoritmul Clarvăzător. Deoarece este, în general, imposibil să se prevadă cât de departe vor fi necesare informații în viitor, acest lucru nu este în general implementabil în practică. Minimul practic poate fi calculat numai după experimentare și se poate compara eficacitatea algoritmului cache ales efectiv.
în momentul în care apare o eroare de pagină, un anumit set de pagini este în memorie. În exemplu, secvența de ‘5’, ‘0’, ‘1’ este accesat de Cadrul 1, cadrul 2, cadrul 3 respectiv. Apoi, când ‘2’ este accesat, înlocuiește valoarea ‘5’, care este în cadrul 1, deoarece prezice că valoarea ‘ 5 ‘ nu va fi accesată în viitorul apropiat. Deoarece un sistem de operare cu scop general din viața reală nu poate prezice de fapt când va fi accesat ‘5’, algoritmul B Xqql Xqqy nu poate fi implementat pe un astfel de sistem.
First in first out (FIFO)Edit
folosind acest algoritm cache-ul se comportă în același mod ca o coadă FIFO. Cache-ul evacuează blocurile în ordinea în care au fost adăugate, fără a ține cont de cât de des sau de câte ori au fost accesate înainte.
Last in first out (LIFO) sau First in last out (FILO)Edit
folosind acest algoritm, cache-ul se comportă în același mod ca o stivă și exact invers ca o coadă FIFO. Cache-ul evacuează blocul adăugat cel mai recent, fără a ține cont de cât de des sau de câte ori a fost accesat înainte.
cel mai recent utilizat (LRU)editare
aruncă mai întâi elementele cel mai recent utilizate. Acest algoritm necesită urmărirea a ceea ce a fost folosit atunci când, ceea ce este scump dacă cineva dorește să se asigure că algoritmul aruncă întotdeauna elementul cel mai puțin utilizat recent. Implementările generale ale acestei tehnici necesită păstrarea ” biților de vârstă „pentru liniile cache și urmărirea liniei cache” cel mai puțin utilizate recent ” pe baza biților de vârstă. Într-o astfel de implementare, de fiecare dată când se utilizează o linie cache, vârsta tuturor celorlalte linii cache se schimbă. LRU este de fapt o familie de algoritmi de cache cu membri, inclusiv 2Q de Theodore Johnson și Dennis Shasha, și LRU/K de Pat O ‘Neil, Betty O’ Neil și Gerhard Weikum.
secvența de acces pentru exemplul de mai jos este A B C D E D F.
în exemplul de mai sus, odată ce un B C D este instalat în blocurile cu numere de secvență (Increment 1 pentru fiecare Acces nou) și când E este accesat, este un dor și trebuie să fie instalat într-unul din blocuri. Conform algoritmului LRU, deoarece A are cel mai mic rang(A(0)), E va înlocui A.
În al doilea ultim pas D este accesat și, prin urmare, numărul secvenței este actualizat.
LRU, ca multe alte Politici de înlocuire, poate fi caracterizat folosind un câmp de tranziție de stare într-un spațiu vectorial, care decide că starea cache dinamică se schimbă similar cu modul în care un câmp electromagnetic determină mișcarea unei particule încărcate plasate în el.
Time aware least recently used (TLRU)Edit
Time aware Least Recently Used (TLRU) este o variantă a LRU concepută pentru situația în care conținutul stocat în cache are o durată de viață validă. Algoritmul este potrivit în aplicațiile cache de rețea, cum ar fi rețelele centrate pe informații (ICN), rețelele de livrare a conținutului (CDN) și rețelele distribuite în general. TLRU introduce un nou termen: TTU (timpul de Utilizare). TTU este o marcă de timp a unui conținut/pagină care stipulează timpul de utilizare a conținutului în funcție de localitatea conținutului și de anunțul editorului de conținut. Datorită acestei ștampile de timp bazate pe localitate, TTU oferă mai mult control administratorului local pentru a reglementa stocarea în rețea.În algoritmul TLRU, când ajunge o bucată de conținut, un nod cache calculează valoarea TTU locală pe baza valorii TTU atribuită de editorul de conținut. Valoarea TTU locală este calculată utilizând o funcție definită local. Odată ce valoarea TTU locală este calculată înlocuirea conținutului se efectuează pe un subset al conținutului total stocat în nodul cache. TLRU asigură că conținutul de viață mai puțin popular și mic ar trebui înlocuit cu conținutul primit.
cel mai recent utilizat (MRU)Edit
aruncă înapoi în mare, spre deosebire de LRU, cele mai recent utilizate elemente în primul rând. În concluziile prezentate la cea de-a 11-a Conferință VLDB, Chou și DeWitt au menționat că „atunci când un fișier este scanat în mod repetat într-un model de referință, MRU este cel mai bun algoritm de înlocuire.”Ulterior, alți cercetători prezenți la cea de-a 22-a Conferință VLDB au remarcat că pentru modelele de acces aleatoriu și scanările repetate pe seturi de date mari (uneori cunoscute sub numele de modele de acces ciclic) algoritmii cache MRU au mai multe accesări decât LRU datorită tendinței lor de a păstra date mai vechi. Algoritmii MRU sunt cei mai folositori în situațiile în care cu cât un articol este mai vechi, cu atât este mai probabil să fie accesat.
secvența de acces pentru exemplul de mai jos este A B C D E C D B.
aici, A B C D sunt plasate în cache, deoarece există încă spațiu disponibil. La al 5-lea acces E, vedem că blocul care deținea D este acum înlocuit cu E, deoarece acest bloc a fost folosit cel mai recent. Un alt acces la C și la următorul acces la D, C este înlocuit așa cum a fost blocul accesat chiar înainte de D și așa mai departe.
Pseudo-LRU (PLRU)Edit
pentru cache-urile CPU cu asociativitate mare (în general>4 moduri), costul de implementare al LRU devine prohibitiv. În multe cache-uri CPU, este suficientă o schemă care aproape întotdeauna aruncă unul dintre elementele cel mai puțin utilizate recent, așa că mulți designeri CPU aleg un algoritm PLRU care are nevoie doar de un bit pe element cache pentru a funcționa.PLRU are de obicei un raport de ratare ușor mai rău, are o latență puțin mai bună, folosește o putere puțin mai mică decât LRU și cheltuieli generale mai mici în comparație cu LRU.
următorul exemplu arată cum funcționează biții ca un arbore binar de indicatori de 1 biți care indică subarborele mai puțin utilizat. În urma lanțului pointer la nodul de frunze identifică candidatul de înlocuire. La un acces, toți indicii din lanț de la nodul frunzei căii accesate la nodul rădăcină sunt setați să indice subarborele care nu conține calea accesată.
secvența de acces este A B C D E.
principiul de aici este simplu de înțeles dacă ne uităm doar la indicatoarele săgeată. Când există un acces la o valoare, spuneți ‘A’ și nu o putem găsi în memoria cache, atunci o încărcăm din memorie și o așezăm în blocul în care săgețile indică în prezent, mergând de sus în jos. După ce am plasat acel bloc, întoarcem aceleași săgeți, astfel încât acestea să îndrepte direcția opusă. În exemplul de mai sus vedem cum a fost plasat ‘A’, urmat de ‘B’, ‘C și ‘D’. Apoi, pe măsură ce cache-ul a devenit plin ‘E’ a înlocuit ‘A’ pentru că acolo erau îndreptate săgețile în acel moment, iar săgețile care duceau la ‘A’ au fost rotite pentru a indica în direcția opusă. Săgețile apoi a condus la ‘B’, care va fi blocul înlocuit pe următoarea dor cache.
Random replacement (RR)Edit
selectează aleatoriu un element candidat și îl aruncă pentru a face spațiu atunci când este necesar. Acest algoritm nu necesită păstrarea informațiilor despre istoricul accesului. Pentru simplitatea sa, a fost utilizat în procesoarele ARM. Admite o simulare stocastică eficientă.
secvența de acces pentru exemplul de mai jos este A B C D E B D F
segmentat LRU (SLRU)editare
memoria cache SLRU este împărțită în două segmente, un segment de probă și un segment protejat. Liniile din fiecare segment sunt ordonate de la cel mai mult la cel mai puțin accesat recent. Datele din ratări sunt adăugate în memoria cache la capătul cel mai recent accesat al segmentului de probă. Accesările sunt eliminate de oriunde se află în prezent și adăugate la capătul cel mai recent accesat al segmentului protejat. Liniile din segmentul protejat au fost astfel accesate de cel puțin două ori. Segmentul protejat este finit, astfel încât migrarea unei linii de la segmentul de probă la segmentul protejat poate forța migrarea liniei LRU din segmentul protejat la capătul cel mai recent utilizat (MRU) al segmentului de probă, oferind acestei linii o altă șansă de a fi accesată înainte de a fi înlocuită. Limita de dimensiune a segmentului protejat este un parametru SLRU care variază în funcție de modelele de încărcare I/O. Ori de câte ori datele trebuie aruncate din cache, liniile sunt obținute de la capătul LRU al segmentului de probă.
cel mai puțin frecvent utilizat (LFU)Edit
contează cât de des este necesar un element. Cele care sunt folosite cel mai des sunt aruncate mai întâi. Acest lucru funcționează foarte similar cu LRU, cu excepția faptului că, în loc să stocăm valoarea cât de recent a fost accesat un bloc, stocăm valoarea de câte ori a fost accesat. Deci, desigur, în timp ce rulează o secvență de acces, vom înlocui un bloc care a fost folosit de mai puține ori din cache-ul nostru. De exemplu, dacă A a fost folosit (accesat) de 5 ori și B a fost folosit de 3 ori și altele C și D au fost folosite de 10 ori fiecare, vom înlocui B.
cel mai puțin frecvent utilizat recent (LFRU)Edit
cel mai puțin frecvent utilizat recent (Lfru) schema de înlocuire cache combină beneficiile schemelor LFU și LRU. LFRU este potrivit pentru aplicațiile cache ‘în rețea’, cum ar fi rețelele centrate pe informații (ICN), rețelele de livrare a conținutului (CDN) și rețelele distribuite în general. În lfru, memoria cache este împărțită în două partiții numite partiții privilegiate și neprivilegiate. Partiția privilegiată poate fi definită ca o partiție protejată. Dacă conținutul este foarte popular, acesta este împins în partiția privilegiată. Înlocuirea partiției privilegiate se face după cum urmează: lfru evacuează conținutul din partiția neprivilegiată, împinge conținutul din partiția privilegiată în partiția neprivilegiată și, în final, introduce conținut nou în partiția privilegiată. În procedura de mai sus, LRU este utilizat pentru partiția privilegiată și o schemă LFU aproximată (ALFU) este utilizată pentru partiția neprivilegiată, de unde și abrevierea lfru.
ideea de bază este de a filtra conținutul popular local cu schema ALFU și de a împinge conținutul popular într-una din partițiile privilegiate.
LFU cu îmbătrânire dinamică (lfuda)Edit
o variantă numită LFU cu îmbătrânire dinamică (Lfuda) care folosește îmbătrânirea dinamică pentru a găzdui schimbări în setul de obiecte populare. Se adaugă un factor de vârstă cache la numărul de referință atunci când un obiect nou este adăugat la cache sau atunci când un obiect existent este re-referire. Lfuda incrementează cache vârstele atunci când evacuarea blocuri setându-l la valoarea cheie a obiectului evacuat. Astfel, vârsta cache-ului este întotdeauna mai mică sau egală cu valoarea minimă a cheii din cache. Să presupunem că atunci când un obiect a fost accesat frecvent în trecut și acum devine nepopular, acesta va rămâne în cache mult timp, împiedicând astfel obiectele nou sau mai puțin populare să îl înlocuiască. Deci, această îmbătrânire dinamică este introdusă pentru a reduce numărul de astfel de obiecte, făcându-le astfel eligibile pentru înlocuire. Avantajul LFUDA este că reduce poluarea cache cauzată de LFU atunci când dimensiunile cache sunt foarte mici. Când dimensiunile Cache-ului sunt mari, puține decizii de înlocuire sunt suficiente și poluarea cache nu va fi o problemă.
low inter-reference recency set (LIRS)Edit
LIRS este un algoritm de înlocuire pagină cu o performanță îmbunătățită față de LRU și multe alte algoritmi de înlocuire mai noi. Acest lucru se realizează prin utilizarea distanței de reutilizare ca metrică pentru clasarea dinamică a paginilor accesate pentru a lua o decizie de înlocuire. LIRS abordează în mod eficient limitele LRU utilizând recency pentru a evalua Inter-Reference Recency (IRR) pentru luarea unei decizii de înlocuire.
în figura de mai sus, „x” reprezintă faptul că un bloc este accesat la momentul t. Să presupunem că dacă blocul A1 este accesat la momentul 1, atunci Recency va deveni 0, deoarece acesta este primul bloc accesat și IRR va fi 1, deoarece prezice că A1 va fi accesat din nou în timpul 3. În timpul 2 de la accesarea A4, recența va deveni 0 pentru A4 și 1 pentru A1, deoarece A4 este obiectul cel mai recent accesat, iar IRR va deveni 4 și va continua. La ora 10, algoritmul LIRS va avea două seturi LIR set = {a1, A2} și hir set = {A3, A4, A5}. Acum, la ora 10, dacă există acces la A4, apare dor. Algoritmul LIRS va evacua acum A5 în loc de A2 din cauza celei mai mari recente.
CLOCK-ProEdit
algoritmul LRU nu poate fi implementat direct în calea critică a sistemelor informatice, cum ar fi sistemele de operare, datorită Regiei sale ridicate. O aproximare a LRU, numit ceas este frecvent utilizat pentru punerea în aplicare. În mod similar, CLOCK-Pro este o aproximare a LIRS pentru o implementare cu costuri reduse în sisteme. CLOCK-Pro este în cadrul ceasului de bază, dar are trei merite distincte majore. În primul rând, CLOCK-Pro are trei „mâini de ceas”, spre deosebire de o structură simplă de ceas în care se folosește o singură „mână”. Cu cele trei mâini, CLOCK-Pro este capabil să măsoare distanța de reutilizare a acceselor de date într-un mod aproximativ. În al doilea rând, toate meritele LIRS sunt păstrate, cum ar fi evacuarea rapidă a elementelor de acces unic și/sau a datelor de localitate scăzute. În al treilea rând, complexitatea CLOCK-Pro este aceeași cu cea a CLOCK, astfel este ușor de implementat la un cost redus. Implementarea înlocuirii cache-ului tampon în versiunea curentă a Linux este o combinație de LRU și CLOCK-Pro.
cache de înlocuire adaptivă (ARC)editare
echilibrează constant între LRU și LFU, pentru a îmbunătăți rezultatul combinat. ARC îmbunătățește SLRU utilizând informații despre elementele cache evacuate recent pentru a ajusta dinamic dimensiunea segmentului protejat și segmentul de probă pentru a utiliza cât mai bine spațiul cache disponibil. Algoritmul de înlocuire adaptiv este explicat cu exemplul.
AdaptiveClimb (AC)Edit
folosește lovitura / ratarea recentă pentru a regla saltul unde în urcare orice lovitură comută poziția cu un slot în partea de sus, iar în LRU hit comută poziția loviturii în partea de sus. Astfel, beneficiind de optimitatea urcării atunci când programul se află într-un domeniu fix și de adaptarea rapidă la un nou domeniu, așa cum face LRU. De asemenea, acceptă partajarea cache-ului între nuclee, eliberând extras atunci când referințele sunt la partea de sus a cache-ului.
ceas cu înlocuire adaptivă (mașină)editare
combină avantajele Cache de înlocuire adaptivă (ARC) și ceas. Masina are performanțe comparabile cu ARC, și substanțial surclasează atât LRU și ceas. La fel ca ARC, mașina se auto-reglează și nu necesită parametri magici specificați de utilizator. Acesta utilizează 4 liste legate de două ori: Două ceasuri T1 și T2 și două liste simple LRU B1 și B2. T1 magazine ceas pagini bazate pe” recent „sau” utilitate pe termen scurt „întrucât T2 magazine pagini cu” frecvență „sau”utilitate pe termen lung”. T1 și T2 conțin acele pagini care se află în memoria cache, în timp ce B1 și B2 conțin pagini care au fost evacuate recent din T1 și respectiv T2. Algoritmul încearcă să mențină dimensiunea acestor liste B1 T2 și B2 T1. Paginile noi sunt inserate în T1 sau T2. Dacă există o lovitură în dimensiunea B1 a T1 este crescută și, în mod similar, dacă există o lovitură în dimensiunea B2 A T1 este scăzută. Regula de adaptare utilizată are același principiu ca și cea din ARC, investește mai mult în liste care vor da mai multe accesări atunci când i se adaugă mai multe pagini.
multi queue (mq)Edit
algoritmul multi queue sau mq a fost dezvoltat pentru a îmbunătăți performanța cache-ului tampon de nivelul doi, de exemplu, pentru un cache tampon de server. Este introdus într-o lucrare de Zhou, Philbin și Li. memoria cache MQ conține un număr m de cozi LRU: Q0, Q1,…, Qm-1. Aici, valoarea lui m reprezintă o ierarhie bazată pe durata de viață a tuturor blocurilor din acea coadă. De exemplu, dacă j > i, blocurile din Qj vor avea o durată de viață mai lungă decât cele din Qi. În plus față de acestea există un alt tampon istoric Qout, o coadă care menține o listă a tuturor identificatorilor de blocuri împreună cu frecvențele lor de acces. Când Qout este plin cel mai vechi identificator este evacuat. Blocurile rămân în cozile LRU pentru o anumită durată de viață, care este definită dinamic de algoritmul MQ ca fiind distanța temporală maximă dintre două accesări la același fișier sau numărul de blocuri cache, oricare dintre acestea este mai mare. Dacă un bloc nu a fost menționat în timpul vieții sale, acesta este retrogradat de la Qi la Qi−1 sau evacuat din cache dacă este în Q0. Fiecare coadă are, de asemenea, un număr maxim de acces; dacă un bloc din coada Qi este accesat de mai mult de 2i ori, acest bloc este promovat la Qi+1 până când este accesat de mai mult de 2i+1 ori sau durata sa de viață expiră. Într-o anumită coadă, blocurile sunt clasate în funcție de recența accesului, conform LRU.
putem vedea din Fig. cum sunt plasate cozile m LRU în memoria cache. Vezi și din Fig. modul în care qout stochează identificatorii blocului și frecvențele lor de acces corespunzătoare. a a fost plasat în Q0, deoarece a fost accesat o singură dată recent și putem verifica în Qout cum b și c au fost plasate în Q1 și respectiv Q2, deoarece frecvențele lor de acces sunt 2 și 4. Coada în care este plasat un bloc depinde de frecvența de acces(f) ca log2(f). Când cache-ul este plin, primul bloc care va fi evacuat va fi capul lui Q0 în acest caz a. Dacă a este accesat încă o dată, se va muta la Q1 sub b.
Pannier: algoritm de cache bazat pe Containere pentru obiecte compusedit
Pannier este un mecanism de cache flash bazat pe containere care identifică containerele divergente (eterogene) în care blocurile deținute în acesta au modele de acces foarte variate. Pannier folosește o structură de coadă de supraviețuire bazată pe priorități pentru a clasifica containerele în funcție de timpul lor de supraviețuire, care este proporțional cu datele live din container. Pannier este construit pe baza LRU segmentat (s2lru), care separă datele calde și reci. Pannier folosește, de asemenea, un controler de feedback în mai mulți pași pentru a accelera scrierea blițului pentru a asigura durata de viață a blițului.