Cache

Cache [1] [2] [3] [4] sau cache [5] [6] [7] ( eng.  cache , din franceză  cacher  - „ascunde”; pronunțat [ kæʃ ] - „cache”) - buffer intermediar cu acces rapid la acesta, conținând informații care pot fi solicitate cu cea mai mare probabilitate. Accesarea datelor din cache este mai rapidă decât preluarea datelor originale dintr-o memorie mai lentă sau dintr-o sursă la distanță, dar volumul acestora este semnificativ limitat în comparație cu depozitul de date sursă.

Istorie

Cuvântul „cache” a fost folosit pentru prima dată într-un context informatic în 1967 , în timp ce pregătea un articol pentru publicare în IBM Systems Journal . Articolul s-a ocupat de îmbunătățirile de memorie ale modelului IBM System/360 85 în curs de dezvoltare . Editorul jurnalului Lyle Johnson a cerut un termen mai descriptiv decât „buffer de mare viteză”, dar din lipsă de idei, el însuși a sugerat cuvântul „cache”. Articolul a fost publicat la începutul anului 1968, autorii au fost premiați de IBM , munca lor a fost diseminată și ulterior îmbunătățită, iar cuvântul „cache” a devenit curând un termen comun în literatura informatică [8] .

Funcționare

Un cache este o memorie cu o viteză de acces mai mare, concepută pentru a accelera accesul la datele conținute permanent în memorie cu o viteză de acces mai mică (denumită în continuare „memorie principală”). Memorarea în cache este utilizată de CPU , hard disk-uri , browsere , servere web , servicii DNS și WINS .

Cache-ul constă dintr-un set de intrări. Fiecare intrare este asociată cu un element de date sau cu un bloc de date (o bucată mică de date), care este o copie a elementului de date din memoria principală. Fiecare intrare are un identificator , numit adesea etichetă , care definește corespondența dintre elementele de date din cache și omologii lor din memoria principală.

Când un client de cache (CPU, browser web, sistem de operare) accesează date, memoria cache este examinată mai întâi. Dacă se găsește o intrare în cache cu un ID care se potrivește cu ID-ul articolului solicitat, atunci elementele din cache sunt utilizate. Un astfel de eveniment se numește cache hit . Dacă o intrare care conține elementul de date solicitat nu este găsită în cache, atunci este citită din memoria principală în cache și devine disponibilă pentru accesările ulterioare. Un astfel de caz se numeștecache miss . Procentul de accesări în cache atunci când este găsit un rezultat se numește rata de accesare sau rata de accesare în cache .

De exemplu, un browser web verifică memoria cache locală de pe disc pentru o copie locală a unei pagini web care se potrivește cu adresa URL solicitată. În acest exemplu, adresa URL este identificatorul, iar conținutul paginii web este elementele de date.

Dacă memoria cache este limitată în dimensiune, atunci în caz de ratare se poate decide să renunți la o intrare pentru a elibera spațiu. Sunt utilizați diferiți algoritmi de evacuare pentru a selecta înregistrarea de eliminat .

Când elementele de date din cache sunt modificate, acestea sunt actualizate în memoria principală. Întârzierea dintre modificarea datelor din cache și actualizarea memoriei principale este controlată de așa-numita politică de scriere .

Într-o memorie cache numai pentru scriere , fiecare modificare determină o actualizare sincronă a datelor din memoria principală.

Într-o memorie cache write- back (sau write- back), o actualizare are loc atunci când un element de date este evacuat, periodic, sau la cererea clientului. Pentru a ține evidența elementelor de date modificate, intrările în cache stochează un indicator de modificare ( modificat sau „murdar” ). O pierdere a memoriei cache cu o rescriere poate necesita două accesări la memoria principală: prima pentru a scrie datele înlocuite din cache, a doua pentru a citi elementul de date necesar.

În cazul în care datele din memoria principală pot fi modificate independent de memoria cache, atunci intrarea în cache poate deveni învechită . Protocoalele de comunicare între cache care mențin consistența datelor sunt numite protocoale de coerență a memoriei cache .

Implementarea hardware

memoria cache a procesorului

Datorită creșterii frecvenței la care funcționează procesoarele și creșterii performanței subsistemului RAM ( RAM), interfața de transfer de date a devenit blocajul sistemului de calcul.

Memoria cache poate oferi beneficii semnificative de performanță atunci când viteza de ceas a memoriei RAM este semnificativ mai mică decât cea a procesorului. Un număr de modele de procesoare au propriul cache pentru a minimiza timpul de acces la memoria cu acces aleatoriu (RAM), care este mai lent decât registrele (acești registre și buffer-uri I/O pot fi considerate cache de nivel zero). Viteza de ceas pentru memoria cache nu este de obicei cu mult mai mică decât frecvența procesorului.

Procesoarele care acceptă adresarea virtuală includ adesea un buffer mic și rapid de traducere a adresei (TLB). Viteza sa este importantă deoarece este interogat la fiecare acces la memorie.

Problema sincronizării între diferitele cache (atât unul cât și mai multe procesoare) este rezolvată prin coerența cache .

Există trei opțiuni pentru schimbul de informații între cache-uri de diferite niveluri sau, după cum se spune, arhitecturi cache: inclusive, exclusive și neexclusive.

Memoria cache exclusivă presupune unicitatea informațiilor situate în diferite niveluri ale memoriei cache (preferată de AMD ).

În cache-urile neexclusive se pot comporta după bunul plac.

Nivelurile cache al procesorului

Cache-ul CPU este împărțit în mai multe niveluri. Numărul maxim de cache este de patru. Într-un procesor universal , numărul de niveluri poate fi în prezent de până la trei. Cache-urile de nivel N+1 sunt în general mai mari și mai lente în ceea ce privește accesul și transferul de date decât cache-urile de nivel N.

  • Cel mai rapid este cache de prim nivel - cache L1 (cache de nivel 1). De fapt, este o parte integrantă a procesorului, deoarece este situat pe același cip și face parte din blocurile funcționale. În procesoarele moderne, L1 este de obicei împărțit în două cache - cache-ul de instrucțiuni (instrucțiuni) și cache-ul de date ( arhitectura Harvard ). Majoritatea procesoarelor fără L1 nu pot funcționa. L1 funcționează la frecvența procesorului și, în cazul general, poate fi accesat în fiecare ciclu de ceas . Este adesea posibil să se efectueze mai multe operații de citire/scriere în același timp.
  • Al doilea cel mai rapid este cache-ul L2, care, la fel ca L1, se află de obicei pe același cip cu procesorul. Procesoarele timpurii au implementat L2 ca un chipset de memorie separat pe placa de bază. Volumul L2 este de la 128 KB la 1-12 MB. În procesoarele moderne cu mai multe nuclee, memoria cache de nivel al doilea, situată pe același cip, este o memorie separată - cu o dimensiune totală a memoriei cache de n MB, fiecare nucleu are n / c MB, unde c este numărul de nuclee de procesor.
  • Cel de-al treilea nivel cache este cel mai puțin rapid, dar poate fi foarte mare - mai mult de 24 MB. L3 este mai lent decât cache-urile anterioare, dar totuși semnificativ mai rapid decât RAM. În sistemele cu multiprocesor, este de uz comun și este conceput pentru a sincroniza datele diferitelor L2.
  • Există un al patrulea nivel de cache, a cărui utilizare este justificată numai pentru serverele multiprocesoare de înaltă performanță și mainframe . De obicei, este implementat de un cip separat.
Asociativitatea cache

Una dintre caracteristicile fundamentale ale memoriei cache - nivelul de asociativitate - reflectă segmentarea sa logică, care este cauzată de faptul că enumerarea secvențială a tuturor liniilor cache în căutarea datelor necesare ar necesita zeci de cicluri și ar anula tot câștigul din folosind memoria integrată în procesor. Prin urmare, celulele RAM sunt conectate la liniile cache (fiecare linie poate conține date de la un set fix de adrese), ceea ce reduce semnificativ timpul de căutare.

Cu aceeași dimensiune cache, o schemă cu o asociativitate mai mare va fi cea mai puțin rapidă, dar cea mai eficientă (după o implementare cu patru fire, creșterea „eficienței specifice” pe fir crește puțin).

Memorarea în cache de stocare externă

Multe periferice de stocare folosesc un cache intern pentru a accelera lucrurile, în special, hard disk-urile folosesc cache de la 1 MB până la 256 MB ( modelele NCQ / TCQ îl folosesc pentru stocare și procesarea interogărilor), discurile CD/DVD/BD memorează și informațiile de citire în cache pentru a accelera regăsire.

Sistemul de operare utilizează, de asemenea, o parte din memoria RAM ca cache pentru operațiunile de pe disc (de exemplu, pentru dispozitivele externe care nu au propriul cache, inclusiv hard disk-uri, memorie flash și dischete). Adesea, toată memoria RAM gratuită (nealocată proceselor) este furnizată pentru stocarea în cache a hard disk-urilor.

Utilizarea stocării în cache a unităților externe se datorează următorilor factori:

  1. viteza de acces a procesorului la RAM este de sute sau mai multe ori mai mare decât la memoria unităților externe;
  2. performanța dispozitivelor de stocare pe disc (hard, dischetă, discuri optice) este maximă la citirea-scrierea mai multor blocuri consecutive și scade semnificativ cu solicitări unice în diferite locuri de pe disc, ceea ce se datorează inerției unității mecanice a capului.
  3. frecvență extrem de neuniformă de accesare a diferitelor blocuri de memorie ale unităților externe:
    1. utilizarea unei părți din blocuri de către mai multe procese în același timp, pentru citire și scriere (de exemplu, în baze de date)
    2. citirea foarte frecventă a unei părți a blocurilor (fișiere index, directoare în sistemul de fișiere)
    3. scrierea foarte frecventă a unei părți a blocurilor (fișiere jurnal, jurnale, fișiere baze de date; metadate ale sistemului de fișiere).

Când este citit, memoria cache vă permite să citiți blocul o dată, apoi să stocați o copie a blocului în RAM pentru toate procesele și să returnați conținutul blocului „instantaneu” (comparativ cu o solicitare de disc). Există o tehnică de „pre-cerere” - în fundal, sistemul de operare citește și următoarele câteva blocuri (după cel necesar) în cache.

Când scrieți, memoria cache vă permite să grupați înregistrările scurte în altele mai mari care sunt procesate mai eficient de unități sau să evitați scrierea modificărilor intermediare. În acest caz, toate stările intermediare ale blocului sunt vizibile pentru procesele din RAM.

Memorarea în cache a stocării externe îmbunătățește considerabil performanța sistemului prin optimizarea utilizării I/O. Avantajul tehnologiei este optimizarea automată transparentă (invizibilă pentru programe) a utilizării memoriei pe disc, în timp ce logica aplicațiilor care lucrează cu fișiere rămâne neschimbată.

Dezavantajul memorării în cache de scriere este intervalul de timp dintre o solicitare de scriere de la un program și scrierea efectivă a unui bloc pe disc, precum și reordonarea scrierilor, care poate duce la pierderea de informații sau la inconsecvențe de structură în timpul unei căderi de curent sau a unui sistem. atârna. Această problemă este atenuată de sincronizarea periodică forțată (scrierea liniilor de cache modificate) și jurnalizarea sistemului de fișiere.

Implementarea software

Politica de scriere în cache

La citirea datelor, memoria cache oferă un câștig clar de performanță. La scrierea datelor, câștigurile pot fi obținute doar cu prețul unei fiabilități reduse. Prin urmare, diferite aplicații pot alege politici diferite de scriere în cache.

Există două politici principale de scriere în cache - write-through și write-back:

  1. Write-through - scrierea se face direct în memoria principală (și duplicat în cache), adică scrierea nu este stocată în cache.
  2. Scriere leneșă - datele sunt scrise în cache. Scrierea în memoria principală se efectuează mai târziu (când este preempțiată sau după ce a trecut timpul), grupând mai multe operații de scriere la celulele învecinate într-o singură operație. Tehnologia writeback face ca datele din memoria principală să fie irelevante de ceva timp, aceste irelevante nu sunt vizibile pentru CPU în sine, dar înainte de a accesa memoria unei alte magistrale de sistem lider ( controler DMA , dispozitiv PCI bus-master bus ), memoria cache trebuie să fie scris în memorie cu forța. Când utilizați writeback pe un sistem multiprocesor, cache-urile diferitelor procesoare trebuie să fie consecvente (sau procesoarele trebuie să partajeze aceeași memorie cache).
Algoritmul de rescriere cache

Inițial, toate anteturile bufferelor sunt plasate pe lista liberă de buffere. Dacă un proces intenționează să citească sau să modifice un bloc, atunci execută următorul algoritm:

  1. încearcă să găsească antetul buffer-ului cu numărul dat în tabelul hash ;
  2. dacă tamponul primit este ocupat, așteaptă să fie eliberat;
  3. dacă bufferul nu este găsit în tabelul hash, acesta ia primul buffer din coada listei libere;
  4. dacă lista de buffere libere este goală, atunci algoritmul de evacuare este executat (vezi mai jos);
  5. dacă tamponul primit este marcat ca „murdar”, efectuează o scriere asincronă a conținutului bufferului în memoria externă.
  6. elimină tamponul din tabelul hash, dacă a fost plasat în el;
  7. plasează tamponul în tabelul hash cu un număr nou.

Procesul citește datele în memoria tampon primită și le eliberează. În cazul modificării, procesul marchează tamponul ca „murdar” înainte de a-l elibera. Când este eliberat, tamponul este plasat în fruntea listei libere de buffere.

În acest fel:

  1. dacă un proces citește un bloc în buffer, atunci este foarte probabil ca un alt proces, când citește acest bloc, va găsi tamponul în RAM;
  2. scrierea datelor în memoria externă se realizează numai atunci când nu există suficiente buffer-uri „curate”, sau la cerere.

Algoritm de deplasare

Dacă lista de buffer-uri libere este goală, atunci algoritmul de spălare a tamponului este executat. Algoritmul de evacuare afectează semnificativ performanța memoriei cache. Există următorii algoritmi:

  1. Implementat cu un cronometru :
    1. LRU ( English  Least Recently Used ) - tamponul care nu a fost folosit pentru cel mai mult timp este înlocuit;
    2. MRU ( English  Most Recently Used ) - ultimul buffer folosit este înlocuit;
  2. Implementat cu un contor :
    1. LFU ( eng.  Least Frequently Used ) - tamponul care este utilizat cel mai puțin des este înlocuit;
    2. ARC ( în engleză  Adaptive Replacement Cache ) este un algoritm de extrudare care combină LRU și LFU , patentat de IBM .

Utilizarea unui algoritm sau altuia depinde de strategia de stocare în cache a datelor. LRU este cel mai eficient dacă se garantează că datele vor fi reutilizate cât mai curând posibil. MRU este cel mai eficient dacă se garantează că datele nu vor fi reutilizate în curând. Dacă aplicația specifică în mod explicit o strategie de stocare în cache pentru un anumit set de date, atunci memoria cache va funcționa cel mai eficient.

Memorarea în cache a sistemului de operare

Memoria cache RAM constă din următoarele elemente:

  1. un set de pagini RAM împărțite în buffer-uri egale ca lungime cu blocul de date al dispozitivului de memorie extern corespunzător;
  2. un set de anteturi de buffer care descriu starea tamponului corespunzător;
  3. tabel hash care conține numărul de bloc care se potrivește cu antetul;
  4. liste de buffere gratuite.

Memorarea în cache a paginii web

În procesul de transfer de informații într-o rețea, se poate folosi caching-ul paginilor web - procesul de stocare a documentelor solicitate frecvent pe serverele proxy (intermediare) sau pe mașina utilizatorului, pentru a preveni descărcarea constantă a acestora de pe serverul sursă și pentru a reduce traficul . Astfel, informația se apropie de utilizator. Memorarea în cache este controlată de antetele HTTP .

Alternativ, memorarea în cache a paginilor web se poate face folosind CMS -ul unui anumit site pentru a reduce încărcarea serverului în timpul traficului ridicat. Memorarea în cache se poate face atât în ​​memorie, cât și în cache-ul fișierelor [9] . Dezavantajul stocării în cache este că modificările efectuate într-un browser nu pot fi reflectate imediat în alt browser care preia date din cache.

Memorarea în cache a rezultatelor muncii

Multe programe scriu undeva rezultate intermediare sau auxiliare ale lucrării, pentru a nu le calcula de fiecare dată când sunt necesare. Acest lucru accelerează munca, dar necesită memorie suplimentară (RAM sau disc). Un exemplu de astfel de stocare în cache este indexarea bazei de date .

Vezi și

Note

  1. ↑ Cash // Dicționarul ortografic mare al limbii ruse / ed. S. G. Barkhudarova , I. F. Protchenko și L. I. Skvortsova . - Ed. a 3-a. - M . : ONIKS Mir și Educația, 2007. - S. 399. - ISBN 978-5-488-00924-0 . - ISBN 978-5-94666-375-5 .
  2. ↑ Marele dicționar explicativ al limbii ruse / Autor, comp. și Ch. ed. S. A. Kuznetsov. Institutul de Cercetări Lingvistice RAS, 2000
  3. ↑ Zakharenko E. N., Komarova L. N., Nechaeva I. V. Un nou dicționar de cuvinte străine. M.: 2003
  4. ↑ Dicţionar explicativ de informatică. Microsoft Press, ediția rusă, 1995
  5. ↑ Dicționar ortografic rus: aproximativ 180.000 de cuvinte [Versiunea electronică] / O. E. Ivanova , V. V. Lopatin (red. responsabilă), I. V. Nechaeva , L. K. Cheltsova . — Ed. a II-a, corectată. si suplimentare — M .: Academia Rusă de Științe . Institutul Limbii Ruse numit după V. V. Vinogradov , 2004. - 960 p. — ISBN 5-88744-052-X .
  6. ↑ Pershikov V.I., Savinkov V.M. Dicţionar explicativ de informatică / Recenzători: Cand. Fiz.-Matematică. Sci. A. S. Markov și Dr. Phys.-Math. Științe I. V. Pottosin. - M. : Finanţe şi statistică, 1991. - 543 p. — 50.000 de exemplare.  - ISBN 5-279-00367-0 .
  7. ↑ Borkovsky A. B. Dicționar englez-rus de programare și informatică (cu interpretări). - M . : Limba rusă, 1990. - 335 p. - 50.050 de exemplare (suplimentare).  — ISBN 5-200-01169-3 .
  8. ↑ G.C. Stierhoff, A.G. Davis. O istorie a jurnalului IBM Systems // IEEE Analele istoriei calculului. - ianuarie 1998. - V. 20 , nr 1 . - S. 29-35 . - doi : 10.1109/85.646206 .
  9. ↑ Sistem de operare distribuit . Consultat la 29 noiembrie 2009. Arhivat din original la 10 septembrie 2010.

Literatură

  • Bach M.J. Arhitectura sistemului de operare UNIX