Cache

Cache [1] [2] [3] [4] eller cache [5] [6] [7] ( eng.  cache , fra fransk  cacher  - "skjul"; udtales [ kæʃ ] - "cache") - mellembuffer med hurtig adgang til den, indeholdende information, der med størst sandsynlighed kan rekvireres. Adgang til data i cachen er hurtigere end at hente de originale data fra langsommere hukommelse eller en fjernkilde, men dens volumen er betydeligt begrænset sammenlignet med kildedatalageret.

Historie

Ordet "cache" blev første gang brugt i en computersammenhæng i 1967 , mens man forberedte en artikel til offentliggørelse i IBM Systems Journal . Artiklen omhandlede hukommelsesforbedringer i IBM System/360 model 85 under udvikling . Journalredaktør Lyle Johnson bad om et mere beskrivende udtryk end "high-speed buffer", men på grund af mangel på ideer foreslog han selv ordet "cache". Artiklen blev offentliggjort i begyndelsen af ​​1968, forfatterne blev præmieret af IBM , deres arbejde blev formidlet og efterfølgende forbedret, og ordet "cache" blev hurtigt et almindeligt begreb i computerlitteratur [8] .

Fungerer

En cache er en hukommelse med en hurtigere adgangshastighed, designet til at fremskynde adgangen til data, der er indeholdt permanent i hukommelsen med en lavere adgangshastighed (i det følgende benævnt "hovedhukommelse"). Caching bruges af CPU'en , harddiske , browsere , webservere , DNS- og WINS - tjenester .

Cachen består af et sæt poster. Hver post er forbundet med et dataelement eller en blok af data (et lille stykke data), som er en kopi af dataelementet i hovedhukommelsen. Hver post har en identifikator , ofte kaldet en tag , der definerer overensstemmelsen mellem dataelementer i cachen og deres modstykker i hovedhukommelsen.

Når en cache-klient (CPU, webbrowser, operativsystem) tilgår data, undersøges cachen først. Hvis der findes en post i cachen med et id, der matcher id'et for det anmodede element, så bruges emnerne i cachen. Sådan en begivenhed kaldes et cache-hit . Hvis en post, der indeholder det anmodede dataelement, ikke findes i cachen, så læses den fra hovedhukommelsen ind i cachen og bliver tilgængelig for efterfølgende adgange. Sådan en sag kaldescache miss . Procentdelen af ​​cachehits, når et resultat er fundet, kaldes hitraten eller cachehitforholdet .

For eksempel tjekker en webbrowser sin lokale cache på disken for en lokal kopi af en webside, der matcher den anmodede URL. I dette eksempel er URL'en identifikatoren, og indholdet af websiden er dataelementerne.

Hvis cachen er begrænset i størrelse, kan det ved en glip blive besluttet at kassere noget indtastning for at frigøre plads. Forskellige eviction - algoritmer bruges til at vælge, hvilken post der skal kasseres .

Når dataelementer i cachen ændres, opdateres de i hovedhukommelsen. Tidsforsinkelsen mellem ændringen af ​​data i cachen og opdateringen af ​​hovedhukommelsen styres af den såkaldte skrivepolitik .

I en skrive - kun cache forårsager hver ændring en synkron opdatering af dataene i hovedhukommelsen.

I en tilbageskrivnings - cache (eller tilbageskrivning ) sker der en opdatering, når et dataelement bliver smidt ud, periodisk eller efter anmodning fra klienten. For at holde styr på ændrede dataelementer gemmer cacheposter et modifikationsflag ( modificeret eller "beskidt" ). En cache-miss med en tilbageskrivning kan kræve to adgange til hovedhukommelsen: den første til at skrive de erstattede data fra cachen, den anden til at læse det nødvendige dataelement.

I tilfælde af at dataene i hovedhukommelsen kan ændres uafhængigt af cachen, kan cacheindgangen blive forældet . Protokoller til kommunikation mellem caches, der opretholder datakonsistens, kaldes cache-kohærensprotokoller .

Hardwareimplementering

CPU cache

På grund af stigningen i frekvensen , hvormed processorer arbejder , og stigningen i ydeevnen af ​​RAM-undersystemet ( RAM), er dataoverførselsgrænsefladen blevet flaskehalsen i computersystemet.

Cachehukommelse kan give betydelige ydeevnefordele, når RAM-clockhastigheden er væsentligt lavere end processorens clockhastighed. En række processormodeller har deres egen cache for at minimere adgangstiden til random access memory (RAM), som er langsommere end registre (disse registre og I/O-buffere kan betragtes som cache-niveau nul). Klokkehastigheden for cachehukommelsen er normalt ikke meget mindre end CPU-frekvensen.

Processorer, der understøtter virtuel adressering , inkluderer ofte en lille, hurtig adresseoversættelsesbuffer (TLB). Dens hastighed er vigtig, fordi den bliver pollet ved hver hukommelsesadgang.

Problemet med synkronisering mellem forskellige caches (både én og flere processorer) løses ved cache-kohærens .

Der er tre muligheder for at udveksle information mellem caches på forskellige niveauer, eller, som man siger, cache-arkitekturer: inklusive, eksklusiv og ikke-eksklusiv.

Eksklusiv cachehukommelse antager det unikke ved information, der er placeret på forskellige niveauer af cachen (foretrukket af AMD ).

I ikke-eksklusive caches kan opføre sig som de vil.

Processor cache niveauer

CPU-cachen er opdelt i flere niveauer. Det maksimale antal caches er fire. I en universel processor kan antallet af niveauer i øjeblikket være op til tre. Niveau N+1 caches er generelt større og langsommere i adgang og dataoverførsel end niveau N caches.

  • Den hurtigste er første niveau cache - L1 cache (niveau 1 cache). Faktisk er det en integreret del af processoren, da den er placeret på den samme chip og er en del af funktionsblokkene. I moderne processorer er L1 normalt opdelt i to caches - instruktions (instruktions) cachen og data cachen ( Harvard architecture ). De fleste processorer uden L1 kan ikke fungere. L1 fungerer ved processorens frekvens, og i det generelle tilfælde kan den tilgås hver clock-cyklus . Det er ofte muligt at udføre flere læse-/skrivehandlinger på samme tid.
  • Den næsthurtigste er L2-cachen, der ligesom L1 normalt er placeret på samme chip som processoren. Tidlige processorer implementerede L2 som et separat hukommelseschipsæt på bundkortet. Volumen af ​​L2 er fra 128 KB til 1-12 MB. I moderne multi-core processorer er det andet niveaus cache, placeret på samme chip, en separat hukommelse - med en samlet cachestørrelse på n MB har hver kerne n / c MB, hvor c er antallet af processorkerner.
  • Cachen på tredje niveau er den mindst hurtige, men den kan være meget stor - mere end 24 MB. L3 er langsommere end tidligere caches, men stadig betydeligt hurtigere end RAM. I multiprocessorsystemer er det almindeligt brugt og er designet til at synkronisere data fra forskellige L2.
  • Der er et fjerde niveau af cache, hvis brug kun er berettiget til multiprocessor højtydende servere og mainframes . Normalt implementeres det af en separat chip.
Cache Associativitet

En af de grundlæggende egenskaber ved cachehukommelse - niveauet af associativitet - afspejler dens logiske segmentering, som er forårsaget af det faktum, at sekventiel opregning af alle cache-linjer på jagt efter de nødvendige data ville kræve snesevis af cyklusser og ville ophæve al gevinsten fra ved hjælp af den indbyggede hukommelse i CPU'en. Derfor er RAM-celler fastkablet til cache-linjer (hver linje kan indeholde data fra et fast sæt adresser), hvilket reducerer søgetiden markant.

Med den samme cachestørrelse vil et skema med en større associativitet være det mindst hurtige, men det mest effektive (efter en fire-tråds implementering vokser stigningen i "specifik effektivitet" pr. tråd kun lidt).

Ekstern lagercache

Mange perifere lagerenheder bruger en intern cache til at fremskynde tingene, især harddiske bruger 1MB til 256MB cache ( NCQ / TCQ- modeller bruger det til lagring og forespørgselsbehandling), CD/DVD/BD-diske cacher også læseoplysninger for at fremskynde hentning.

Operativsystemet bruger også en del af RAM'en som cache til diskoperationer (f.eks. til eksterne enheder, der ikke har deres egen cache, inklusive harddiske, flashhukommelse og disketter). Ofte er al gratis (ikke allokeret til processer) RAM tilvejebragt til caching af harddiske.

Brugen af ​​cachelagring af eksterne drev skyldes følgende faktorer:

  1. hastigheden af ​​processoradgang til RAM er hundredvis eller flere gange større end til hukommelsen på eksterne drev;
  2. ydeevnen af ​​disklagerenheder (harde, floppy, optiske diske) er maksimal ved læsning og skrivning af flere på hinanden følgende blokke og falder betydeligt med enkelte anmodninger til forskellige steder på disken, hvilket skyldes inertien af ​​hovedets mekaniske drev.
  3. ekstremt ujævn frekvens for adgang til forskellige hukommelsesblokke af eksterne drev:
    1. brugen af ​​en del af blokkene af flere processer på samme tid, til læsning og skrivning (f.eks. i databaser)
    2. meget hyppig læsning af en del af blokkene (indeksfiler, mapper i filsystemet)
    3. meget hyppig skrivning af en del af blokkene (logfiler, journaler, databasefiler; filsystemmetadata).

Når den er læst, giver cachen dig mulighed for at læse blokken én gang, derefter gemme en kopi af blokken i RAM for alle processer og returnere indholdet af blokken "øjeblikkeligt" (sammenlignet med en diskanmodning). Der er en "pre-request"-teknik - i baggrunden læser operativsystemet også de næste par blokke (efter den påkrævede) ind i cachen.

Når du skriver, giver cachen dig mulighed for at gruppere korte poster i større, der behandles mere effektivt af drev, eller for at undgå at skrive mellemliggende ændringer. I dette tilfælde er alle mellemtilstande af blokken synlige for processer fra RAM.

Ekstern lagercache forbedrer systemets ydeevne betydeligt ved at optimere I/O-brug. Fordelen ved teknologien er den gennemsigtige (usynlige for programmer) automatiske optimering af brugen af ​​diskhukommelse, mens logikken i applikationer, der arbejder med filer, forbliver uændret.

Ulempen ved skrive-caching er mængden af ​​tid mellem en skriveanmodning fra et program og den faktiske skrivning af en blok til disk, samt genbestilling af skrivninger, hvilket kan føre til tab af information eller strukturinkonsekvens under et strømsvigt eller et system hænge. Dette problem afbødes af tvungen periodisk synkronisering (skrivning af ændrede cachelinjer) og filsystemjournalføring.

Softwareimplementering

Caching skrivepolitik

Ved læsning af data giver cachehukommelsen en klar ydelsesforstærkning. Når du skriver data, kan gevinster kun opnås på bekostning af reduceret pålidelighed. Derfor kan forskellige applikationer vælge forskellige cache-skrivepolitikker.

Der er to hovedcache-skrivepolitikker - gennemskrivning og tilbageskrivning:

  1. Write-through - skrivningen foretages direkte til hovedhukommelsen (og duplikeres i cachen), det vil sige, at skrivningen ikke cachelagres.
  2. Doven skrivning - data skrives til cachen. Skrivning til hovedhukommelsen udføres senere (når forudgående eller efter at tiden er gået), idet flere skriveoperationer grupperes til naboceller i én operation. Genskrivningsteknologien gør dataene i hovedhukommelsen irrelevante i nogen tid, disse irrelevanser er ikke mærkbare for selve CPU'en, men før man får adgang til hukommelsen på en anden førende systembus ( DMA controller, PCI bus-master bus enhed ), skal cachen skrives til hukommelsen med magt. Når du bruger tilbageskrivning på et multiprocessorsystem, skal cachen for de forskellige CPU'er være konsistente (eller processorerne skal dele den samme cache).
Genskrivnings-cache-algoritme

Til at begynde med placeres alle bufferoverskrifter på den frie liste over buffere. Hvis en proces har til hensigt at læse eller ændre en blok, udfører den følgende algoritme:

  1. forsøger at finde overskriften på bufferen med det givne tal i hash-tabellen ;
  2. hvis den modtagne buffer er optaget, venter på at den bliver frigivet;
  3. hvis bufferen ikke findes i hash-tabellen, tager den den første buffer fra halen af ​​den frie liste;
  4. hvis listen over ledige buffere er tom, udføres eviction-algoritmen (se nedenfor);
  5. hvis den modtagne buffer er markeret som "beskidt", udfører en asynkron skrivning af bufferindholdet til ekstern hukommelse.
  6. fjerner bufferen fra hash-tabellen, hvis den var placeret i den;
  7. placerer bufferen i hash-tabellen med et nyt tal.

Processen læser data ind i den modtagne buffer og frigør dem. I tilfælde af modifikation markerer processen bufferen som "snavset", før den frigøres. Når den er frigivet, placeres bufferen i spidsen af ​​den frie liste over buffere.

På denne måde:

  1. hvis en proces læser en blok ind i bufferen, så er det højst sandsynligt, at en anden proces, når denne blok læser, vil finde bufferen i RAM;
  2. skrivning af data til ekstern hukommelse udføres kun, når der ikke er nok "rene" buffere, eller efter anmodning.

Forskydningsalgoritme

Hvis listen over ledige buffere er tom, udføres bufferflush-algoritmen. Udsættelsesalgoritmen påvirker cachens ydeevne betydeligt. Der er følgende algoritmer:

  1. Implementeret med en timer :
    1. LRU ( English  Least Recently Used ) - den buffer, der ikke har været brugt i længst tid, udskiftes;
    2. MRU ( English  Most Recently Used ) - den sidst brugte buffer udskiftes;
  2. Implementeret med en tæller :
    1. LFU ( eng.  Least Frequently Used ) - den buffer, der bruges mindst ofte, udskiftes;
    2. ARC ( engelsk  Adaptive Replacement Cache ) er en ekstruderingsalgoritme, der kombinerer LRU og LFU , patenteret af IBM .

Brugen af ​​en eller anden algoritme afhænger af datacachestrategien. LRU er mest effektiv, hvis dataene er garanteret genbrugt hurtigst muligt. MRU er mest effektiv, hvis dataene garanteres ikke at blive genbrugt snarest. Hvis applikationen eksplicit specificerer en cachestrategi for et datasæt, vil cachen fungere mest effektivt.

Operativsystem caching

RAM-cachen består af følgende elementer:

  1. et sæt RAM-sider opdelt i buffere, der er lige lange med datablokken i den tilsvarende eksterne hukommelsesenhed;
  2. et sæt bufferoverskrifter, der beskriver tilstanden af ​​den tilsvarende buffer;
  3. hash-tabel, der indeholder det matchende bloknummer til overskriften;
  4. lister over gratis buffere.

Websidecache

I processen med at overføre information over et netværk, kan webside-caching bruges - processen med at gemme ofte efterspurgte dokumenter på (mellemliggende) proxyservere eller brugerens maskine for at forhindre deres konstante download fra kildeserveren og reducere trafikken . Dermed rykker informationen tættere på brugeren. Caching styres af HTTP -headere.

Alternativt kan websidecaching udføres ved hjælp af et bestemt websteds CMS for at reducere serverbelastningen under høj trafik. Caching kan foretages både i hukommelsen og i filcachen [9] . Ulempen ved caching er, at ændringer foretaget i én browser muligvis ikke umiddelbart afspejles i en anden browser, der henter data fra cachen.

Caching af arbejdsresultater

Mange programmer skriver et sted mellem- eller hjælperesultater af arbejdet, for ikke at beregne dem, hver gang de er nødvendige. Dette fremskynder arbejdet, men kræver yderligere hukommelse (RAM eller disk). Et eksempel på sådan caching er databaseindeksering .

Se også

Noter

  1. ↑ Kontanter // Stor staveordbog for det russiske sprog / red. S. G. Barkhudarova , I. F. Protchenko og L. I. Skvortsova . - 3. udg. - M . : ONIKS Mir og Uddannelse, 2007. - S. 399. - ISBN 978-5-488-00924-0 . - ISBN 978-5-94666-375-5 .
  2. ↑ Stor forklarende ordbog over det russiske sprog / forfatter, komp. og Ch. udg. S. A. Kuznetsov. Institut for Sprogforskning RAS, 2000
  3. ↑ Zakharenko E. N., Komarova L. N., Nechaeva I. V. En ny ordbog over fremmede ord. M.: 2003
  4. ↑ Explanatory Dictionary of Computer Science. Microsoft Press, russisk udgave, 1995
  5. ↑ Russisk staveordbog: omkring 180.000 ord [Elektronisk version] / O. E. Ivanova , V. V. Lopatin (ansvarlig red.), I. V. Nechaeva , L. K. Cheltsova . — 2. udg., rettet. og yderligere — M .: Det russiske Videnskabsakademi . Institut for det russiske sprog opkaldt efter V. V. Vinogradov , 2004. - 960 s. — ISBN 5-88744-052-X .
  6. ↑ Pershikov V.I., Savinkov V.M. Explanatory Dictionary of Informatics / Reviewers: Cand. Fysisk.-Matematik. Sci. A. S. Markov og Dr. Phys.-Math. Videnskaber I. V. Pottosin. - M. : Finans og statistik, 1991. - 543 s. — 50.000 eksemplarer.  - ISBN 5-279-00367-0 .
  7. ↑ Borkovsky A. B. Engelsk-russisk ordbog for programmering og informatik (med fortolkninger). - M . : Russisk sprog, 1990. - 335 s. - 50.050 (yderligere) eksemplarer.  — ISBN 5-200-01169-3 .
  8. ↑ G.C. Stierhoff, A.G. Davis. A History of the IBM Systems Journal // IEEE Annals of the History of Computing. - januar 1998. - V. 20 , nr. 1 . - S. 29-35 . - doi : 10.1109/85.646206 .
  9. ↑ Distribueret OS . Hentet 29. november 2009. Arkiveret fra originalen 10. september 2010.

Litteratur

  • Bach M.J. UNIX-operativsystemarkitektur