Algoritm de cache
Un algoritm de memorie cache este un algoritm utilizat pentru a gestiona o memorie cache sau un grup de date. Atunci când memoria cache este plină, acesta decide ce element trebuie șters din memoria cache. Cuvântul "hit rate" descrie cât de des poate fi servită o cerere din memoria cache. Termenul latență descrie cât timp poate fi obținut un element din memoria cache. Aloritmurile de memorie cache reprezintă un compromis între rata de acces și latență.
- Cel mai eficient algoritm de stocare în memoria cache ar fi acela de a elimina întotdeauna informațiile care nu vor fi necesare pentru o perioadă cât mai lungă de timp în viitor. Acest rezultat optim este denumit algoritmul optim al lui Belady sau algoritmul clarvăzător. Deoarece, în general, este imposibil să se prevadă cât de mult timp în viitor vor fi necesare informațiile, acest lucru nu este, în general, implementabil în practică. Minimul practic poate fi calculat numai după experimentare și se poate compara eficacitatea algoritmului de cache ales efectiv cu minimul optim.
- Least Recently Used (LRU): șterge mai întâi elementele utilizate cel mai recent. Acest algoritm necesită urmărirea a ceea ce a fost folosit și când. Acest lucru este costisitor dacă se dorește ca algoritmul să se asigure că elimină întotdeauna elementul cel mai recent utilizat. Implementările generale ale acestei tehnici necesită păstrarea unor "biți de vârstă" pentru liniile cache și urmărirea liniei cache "cel mai recent utilizate" pe baza acestor biți de vârstă. Într-o astfel de implementare, de fiecare dată când o linie de memorie cache este utilizată, vârsta tuturor celorlalte linii de memorie cache se modifică. LRU este, de fapt, o familie de algoritmi de memorare în memoria cache cu membri care includ: 2Q de Theodore Johnson și Dennis Shasha și LRU/K de Pat O'Neil, Betty O'Neil și Gerhard Weikum.
- Cel mai recent utilizat (MRU): Acest algoritm șterge mai întâi elementele utilizate cel mai recent. Acest mecanism de memorare este utilizat în mod obișnuit pentru memoria cache a bazelor de date.
- Pseudo-LRU (PLRU): Există anumite cazuri în care LRU este foarte dificil de implementat. În astfel de cazuri, poate fi suficient să se știe că, în majoritatea cazurilor, unul dintre elementele cel mai recent utilizate este șters. Algoritmul PLRU poate fi utilizat în acest caz, deoarece are nevoie de un singur bit pentru fiecare element din memoria cache pentru a funcționa.
- 2 way set associative: pentru memoria cache de mare viteză a procesorului, unde chiar și PLRU este prea lent. Adresa unui element nou este utilizată pentru a calcula una dintre cele două locații posibile în memoria cache unde poate fi plasat. LRU dintre cele două este eliminat. Acest lucru necesită un bit pentru fiecare pereche de linii de memorie cache, pentru a indica care dintre cele două a fost cel mai recent utilizat.
- Memoria cache cu mapare directă: pentru memoria cache de cea mai mare viteză a procesorului, în cazul în care chiar și memoria cache asociativă cu set de 2 căi este prea lentă. Adresa noului element este utilizată pentru a calcula singura locație din memoria cache în care acesta poate fi plasat. Ceea ce a fost acolo înainte este eliminat.
- Cel mai rar utilizat (LFU): LFU calculează cât de des este necesar un articol. Cele care sunt folosite cel mai rar sunt aruncate primele.
- Adaptive Replacement Cache (ARC): echilibrează în mod constant între LRU și LFU, pentru a îmbunătăți rezultatul combinat.
- Algoritm de memorare în memoria cache MQ (Multi Queueue): (de Y. Zhou, J.F. Philbin și Kai Li).
Alte lucruri de luat în considerare:
- Obiecte cu costuri diferite: păstrați obiectele care sunt scumpe de obținut, de exemplu cele care necesită mult timp pentru a fi obținute.
- Elemente care ocupă mai multă memorie cache: Dacă elementele au dimensiuni diferite, este posibil ca memoria cache să vrea să renunțe la un element mare pentru a stoca mai multe elemente mai mici.
- Articole care expiră în timp: Unele cache-uri păstrează informații care expiră (de exemplu, un cache de știri, un cache DNS sau un cache de browser web). Este posibil ca computerul să renunțe la elemente deoarece acestea au expirat. În funcție de dimensiunea memoriei cache, este posibil să nu fie necesar un alt algoritm de memorare pentru a elimina elementele.
Există, de asemenea, diverși algoritmi pentru menținerea coerenței cache-ului. Acest lucru se aplică numai în situațiile în care se utilizează mai multe memorii cache independente pentru aceleași date (de exemplu, mai multe servere de baze de date care actualizează un singur fișier de date partajat).
Ce locații de memorie pot fi stocate în memoria cache prin ce locații de memorie cache
Întrebări și răspunsuri
Î: Ce este un algoritm de cache?
R: Un algoritm de cache este un algoritm utilizat pentru a gestiona un cache sau un grup de date. Acesta decide ce element trebuie să fie șters din memoria cache atunci când aceasta este plină.
Î: Ce este rata de succes?
R: Rata de succes descrie cât de des poate fi servită o cerere din memoria cache.
Î: Ce descrie latența?
R: Latența descrie cât timp poate fi obținut un element din memoria cache.
Î: Ce este algoritmul optim al lui Belady?
R: Algoritmul optim al lui Belady, cunoscut și sub numele de algoritmul clarvăzător, este un algoritm eficient de memorare în cache care elimină întotdeauna informațiile care nu vor fi necesare pentru o perioadă cât mai lungă de timp în viitor. Acest rezultat nu poate fi, în general, implementat în practică, deoarece necesită prezicerea a ceea ce va fi necesar într-un viitor îndepărtat.
Î: Cum funcționează LRU (Least Recently Used)?
R: LRU șterge mai întâi elementele utilizate cel mai recent și necesită urmărirea a ceea ce a fost utilizat și când a fost utilizat, utilizând "biți de vârstă" pentru fiecare linie de memorie cache și urmărind care a fost utilizată cel mai recent pe baza acestor biți de vârstă. De fiecare dată când o linie de memorie cache este utilizată, vârstele tuturor celorlalte linii de memorie cache sunt modificate în mod corespunzător.
Î: Cum funcționează MRU (Most Recently Used)?
R: MRU șterge mai întâi elementele utilizate cel mai recent, iar acest mecanism de memorare în cache este utilizat în mod obișnuit pentru memoria cache a bazelor de date.
Î: Ce alți algoritmi există pentru a menține coerența cache-ului?
R: Există diverși algoritmi pentru a menține coerența cache-ului atunci când se utilizează mai multe cache-uri independente pentru date partajate, cum ar fi mai multe servere de baze de date care actualizează un singur fișier de date partajat.
