Cache

Cache [1] [2] [3] [4] eller cache [5] [6] [7] ( eng.  cache , från franska  cacher  - "gömma"; uttalas [ kæʃ ] - "cache") - mellanbuffert med snabb tillgång till den, innehållande information som med största sannolikhet kan begäras. Att komma åt data i cachen är snabbare än att hämta originaldata från ett långsammare minne eller en fjärrkälla, men dess volym är avsevärt begränsad jämfört med källdatalagret.

Historik

Ordet "cache" användes först i datorsammanhang 1967 när man förberedde en artikel för publicering i IBM Systems Journal . Artikeln behandlade minnesförbättringar i IBM System/360 modell 85 under utveckling . Tidskriftsredaktören Lyle Johnson bad om en mer beskrivande term än "höghastighetsbuffert", men på grund av brist på idéer föreslog han själv ordet "cache". Artikeln publicerades i början av 1968, författarna belönades av IBM , deras arbete spreds och förbättrades därefter, och ordet "cache" blev snart en vanlig term i datorlitteratur [8] .

Fungerar

En cache är ett minne med en snabbare åtkomsthastighet, utformat för att påskynda åtkomst till data som finns permanent i minnet med en lägre åtkomsthastighet (nedan kallat "huvudminne"). Cachning används av CPU , hårddiskar , webbläsare , webbservrar , DNS- och WINS - tjänster .

Cachen består av en uppsättning poster. Varje post är associerad med ett dataelement eller datablock (en liten bit data), som är en kopia av dataelementet i huvudminnet. Varje post har en identifierare , ofta kallad en tagg , som definierar överensstämmelsen mellan dataobjekt i cachen och deras motsvarigheter i huvudminnet.

När en cacheklient (CPU, webbläsare, operativsystem) kommer åt data, undersöks cachen först. Om en post hittas i cachen med ett ID som matchar det begärda objektets ID, används objekten i cachen. En sådan händelse kallas en cacheträff . Om en post som innehåller det begärda dataelementet inte hittas i cachen, läses den från huvudminnet in i cachen och blir tillgänglig för efterföljande åtkomster. Ett sådant fall kallascache miss . Procentandelen cacheträffar när ett resultat hittas kallas träfffrekvensen eller cacheträffförhållandet .

Till exempel kontrollerar en webbläsare sin lokala cache på disken efter en lokal kopia av en webbsida som matchar den begärda URL:en. I det här exemplet är URL:en identifieraren och innehållet på webbsidan är dataelementen.

Om cachen är begränsad i storlek kan det vid missar beslutas att kassera en del post för att frigöra utrymme. Olika eviction- algoritmer används för att välja vilken post som ska kasseras .

När dataobjekt i cachen ändras uppdateras de i huvudminnet. Tidsfördröjningen mellan ändringen av data i cachen och uppdateringen av huvudminnet styrs av den så kallade skrivpolicyn .

I en endast skrivcache orsakar varje ändring en synkron uppdatering av data i huvudminnet.

I en återskrivningscache (eller återskrivningscache ) sker en uppdatering när ett dataelement vräks, med jämna mellanrum eller på begäran av klienten. För att hålla reda på modifierade dataobjekt lagrar cacheposter en modifieringsflagga ( modifierad eller "smutsig" ). En cachemiss med en återskrivning kan kräva två åtkomster till huvudminnet: den första för att skriva ersatt data från cachen, den andra för att läsa det nödvändiga dataelementet.

I händelse av att data i huvudminnet kan modifieras oberoende av cachen, kan cache-posten bli inaktuell . Protokoll för kommunikation mellan cachar som upprätthåller datakonsistens kallas cachekoherensprotokoll .

Hårdvaruimplementering

CPU-cache

På grund av ökningen av frekvensen vid vilken processorer arbetar , och ökningen av prestanda för RAM-undersystemet ( RAM), har dataöverföringsgränssnittet blivit flaskhalsen i datorsystemet.

Cacheminne kan ge betydande prestandafördelar när RAM-klockhastigheten är betydligt lägre än processorns klockhastighet. Ett antal processormodeller har sin egen cache för att minimera åtkomsttiden till RAM-minnet (Random Access Memory), vilket är långsammare än register (dessa register och I/O-buffertar kan betraktas som cachenivå noll). Klockhastigheten för cacheminnet är vanligtvis inte mycket mindre än CPU-frekvensen.

Processorer som stöder virtuell adressering inkluderar ofta en liten, snabb adressöversättningsbuffert (TLB). Dess hastighet är viktig eftersom den pollas vid varje minnesåtkomst.

Problemet med synkronisering mellan olika cacher (både en och flera processorer) löses genom cachekoherens .

Det finns tre alternativ för att utbyta information mellan cacher på olika nivåer, eller, som man säger, cachearkitekturer: inkluderande, exklusivt och icke-exklusivt.

Exklusivt cacheminne förutsätter unikheten hos information som finns på olika nivåer av cacheminnet (föredraget av AMD ).

I icke-exklusiva cacher kan bete sig som de vill.

Processorns cachenivåer

CPU-cachen är uppdelad i flera nivåer. Det maximala antalet cacher är fyra. I en universell processor kan antalet nivåer för närvarande vara upp till tre. Nivå N+1-cacher är i allmänhet större och långsammare i åtkomst och dataöverföring än nivå N-cacher.

  • Den snabbaste är den första nivåns cache - L1 cache (nivå 1 cache). Faktum är att det är en integrerad del av processorn, eftersom den är placerad på samma chip och är en del av funktionsblocken. I moderna processorer är L1 vanligtvis uppdelad i två cacher - instruktions (instruktions) cache och datacache ( Harvard architecture ). De flesta processorer utan L1 kan inte fungera. L1 arbetar med processorns frekvens, och i det allmänna fallet kan den nås varje klockcykel . Det är ofta möjligt att utföra flera läs-/skrivoperationer samtidigt.
  • Näst snabbast är L2-cachen, som liksom L1 vanligtvis sitter på samma chip som processorn. Tidiga processorer implementerade L2 som en separat minneskretsuppsättning på moderkortet. Volymen på L2 är från 128 KB till 1-12 MB. I moderna flerkärniga processorer är den andra nivåns cache, som ligger på samma chip, ett separat minne - med en total cachestorlek på n MB har varje kärna n / c MB, där c är antalet processorkärnor.
  • Den tredje nivåns cache är minst snabb, men den kan vara väldigt stor - mer än 24 MB. L3 är långsammare än tidigare cachar, men ändå betydligt snabbare än RAM. I multiprocessorsystem är den i vanlig användning och är utformad för att synkronisera data från olika L2.
  • Det finns en fjärde nivå av cache, vars användning är motiverad endast för multiprocessor högpresterande servrar och stordatorer . Vanligtvis implementeras det av ett separat chip.
Cacheassociativitet

En av de grundläggande egenskaperna hos cacheminnet - nivån av associativitet - återspeglar dess logiska segmentering, som orsakas av det faktum att sekventiell uppräkning av alla cache-rader på jakt efter nödvändig data skulle kräva tiotals cykler och skulle förneka all vinst från använder minnet inbyggt i processorn. Därför är RAM-celler hårdkopplade till cache-linjer (varje rad kan innehålla data från en fast uppsättning adresser), vilket avsevärt minskar söktiden.

Med samma cachestorlek kommer ett schema med större associativitet att vara det minst snabba, men det mest effektiva (efter en fyratrådsimplementering växer ökningen i "specifik effektivitet" per tråd lite).

Extern lagringscache

Många kringutrustning för lagring använder en intern cache för att snabba upp saker och ting, i synnerhet hårddiskar använder 1MB till 256MB cache ( NCQ / TCQ- modeller använder det för lagring och frågebehandling), CD/DVD/BD-diskar cachelagrar också information för att snabba upp hämtning.

Operativsystemet använder också en del av RAM-minnet som cache för diskoperationer (till exempel för externa enheter som inte har sin egen cache, inklusive hårddiskar, flashminne och disketter). Ofta tillhandahålls allt gratis (ej allokerat till processer) RAM-minne för cachelagring av hårddiskar.

Användningen av cachelagring av externa enheter beror på följande faktorer:

  1. hastigheten för processoråtkomst till RAM är hundratals eller fler gånger högre än till minnet på externa enheter;
  2. prestandan för disklagringsenheter (hårda, disketter, optiska diskar) är maximal vid läsning och skrivning av flera på varandra följande block och minskar avsevärt med enstaka förfrågningar till olika platser på disken, vilket beror på trögheten hos huvudets mekaniska enhet.
  3. extremt ojämn frekvens för åtkomst till olika minnesblock för externa enheter:
    1. användningen av en del av blocken av flera processer samtidigt, för att läsa och skriva (till exempel i databaser)
    2. mycket frekvent läsning av delar av blocken (indexfiler, kataloger i filsystemet)
    3. mycket frekvent skrivning av delar av blocken (loggfiler, journaler, databasfiler; filsystemmetadata).

När det är läst låter cachen dig läsa blocket en gång, sedan lagra en kopia av blocket i RAM för alla processer och returnera innehållet i blocket "omedelbart" (jämfört med en diskbegäran). Det finns en "pre-request"-teknik - i bakgrunden läser operativsystemet även in de närmaste blocken (efter det nödvändiga) i cachen.

När du skriver låter cachen dig gruppera korta poster till större som bearbetas mer effektivt av enheter, eller för att undvika att skriva mellanliggande ändringar. I detta fall är alla mellanliggande tillstånd i blocket synliga för processer från RAM.

Extern lagringscache förbättrar systemets prestanda avsevärt genom att optimera I/O-användningen. Fördelen med tekniken är den transparenta (osynliga för program) automatiska optimeringen av användningen av diskminne, medan logiken för applikationer som arbetar med filer förblir oförändrad.

Nackdelen med skrivcachelagring är hur lång tid det tar mellan en skrivbegäran från ett program och den faktiska skrivningen av ett block till disk, samt omordning av skrivningar, vilket kan leda till förlust av information eller strukturinkonsekvenser under ett strömavbrott eller system hänga. Detta problem mildras av påtvingad periodisk synkronisering (skriva ändrade cache-rader) och filsystemsjournalföring.

Programvaruimplementering

Cachning av skrivpolicy

Vid läsning av data ger cacheminnet en tydlig prestandavinst. Vid skrivning av data kan vinster endast erhållas till bekostnad av minskad tillförlitlighet. Därför kan olika applikationer välja olika cache-skrivpolicyer.

Det finns två huvudsakliga cache-skrivpolicyer - genomskrivning och återskrivning:

  1. Genomskrivning - skrivningen görs direkt till huvudminnet (och dupliceras i cachen), det vill säga skrivningen cachelagras inte.
  2. Lat skrivning - data skrivs till cachen. Skrivning till huvudminnet utförs senare (när det föreskrivs eller efter att tiden har förflutit), och flera skrivoperationer grupperas till angränsande celler i en operation. Återskrivningstekniken gör data i huvudminnet irrelevant under en tid, dessa irrelevanser är inte märkbara för själva processorn, men innan man kommer åt minnet på en annan ledande systembuss ( DMA -kontroller, PCI -bus-masterbussenhet ), måste cachen skrivas till minnet med våld. När du använder återskrivning på ett multiprocessorsystem måste cacharna för de olika CPU:erna vara konsekventa (eller så måste processorerna dela samma cache).
Återskrivningscachealgoritm

Inledningsvis placeras alla bufferthuvuden på den fria listan över buffertar. Om en process avser att läsa eller modifiera ett block, kör den följande algoritm:

  1. försöker hitta rubriken för bufferten med det givna numret i hashtabellen ;
  2. om den mottagna bufferten är upptagen, väntar på att den ska frigöras;
  3. om bufferten inte hittas i hashtabellen, tar den den första bufferten från den fria listans svans;
  4. om listan med lediga buffertar är tom, exekveras eviction-algoritmen (se nedan);
  5. om den mottagna bufferten är markerad som "smutsig", utför en asynkron skrivning av buffertens innehåll till externt minne.
  6. tar bort bufferten från hashtabellen, om den placerades i den;
  7. placerar bufferten i hashtabellen med ett nytt nummer.

Processen läser in data i den mottagna bufferten och frigör den. Vid modifiering markerar processen bufferten som "smutsig" innan den frigörs. När den är fri placeras bufferten i spetsen för den fria listan över buffertar.

På det här sättet:

  1. om en process läser in ett block i bufferten, är det högst troligt att en annan process, vid läsning av detta block, kommer att hitta bufferten i RAM;
  2. skrivning av data till externt minne utförs endast när det inte finns tillräckligt med "rena" buffertar, eller på begäran.

Förskjutningsalgoritm

Om listan över lediga buffertar är tom, exekveras buffertspolningsalgoritmen. Vräkningsalgoritmen påverkar cacheprestandan avsevärt. Det finns följande algoritmer:

  1. Implementerad med en timer :
    1. LRU ( English  Least Recently Used ) - bufferten som inte har använts under längst tid byts ut;
    2. MRU ( English  Most Recently Used ) - den senast använda bufferten ersätts;
  2. Implementerad med en räknare :
    1. LFU ( eng.  Least Frequently Used ) - bufferten som används minst ofta byts ut;
    2. ARC ( engelsk  Adaptive Replacement Cache ) är en extruderingsalgoritm som kombinerar LRU och LFU , patenterad av IBM .

Användningen av en eller annan algoritm beror på datacachestrategin. LRU är mest effektiv om uppgifterna garanteras återanvändas så snart som möjligt. MRU är mest effektivt om uppgifterna garanterat inte kommer att återanvändas inom kort. Om applikationen uttryckligen anger en cachningsstrategi för någon uppsättning data, kommer cachen att fungera mest effektivt.

Cachning av operativsystem

RAM-cachen består av följande element:

  1. en uppsättning RAM-sidor uppdelade i buffertar lika långa som datablocket för motsvarande externa minnesanordning;
  2. en uppsättning bufferthuvuden som beskriver tillståndet för den motsvarande bufferten;
  3. hashtabell som innehåller det matchande blocknumret till rubriken;
  4. listor över fria buffertar.

Cachning av webbsidor

I processen att överföra information över ett nätverk kan webbsides cachning användas - processen att lagra ofta begärda dokument på (mellanliggande) proxyservrar eller användarens maskin, för att förhindra att de ständigt laddas ner från källservern och minska trafiken . Därmed flyttas informationen närmare användaren. Caching styrs av HTTP - rubriker.

Alternativt kan webbsidans cachelagring göras med hjälp av CMS för en viss webbplats för att minska serverbelastningen under hög trafik. Cachning kan göras både i minnet och i filcachen [9] . Nackdelen med cachelagring är att ändringar som görs i en webbläsare kanske inte omedelbart återspeglas i en annan webbläsare som hämtar data från cachen.

Cachning av arbetsresultat

Många program skriver någonstans mellan- eller hjälpresultat av arbetet, för att inte beräkna dem varje gång de behövs. Detta påskyndar arbetet, men kräver ytterligare minne (RAM eller disk). Ett exempel på sådan cachning är databasindexering .

Se även

Anteckningar

  1. ↑ Kontanter // Stor stavningsordbok för det ryska språket / ed. S. G. Barkhudarova , I. F. Protchenko och L. I. Skvortsova . - 3:e uppl. - M . : ONIKS Mir och utbildning, 2007. - S. 399. - ISBN 978-5-488-00924-0 . - ISBN 978-5-94666-375-5 .
  2. ↑ Stor förklarande ordbok för det ryska språket / Författare, komp. och Ch. ed. S. A. Kuznetsov. Institutet för språkforskning RAS, 2000
  3. ↑ Zakharenko E. N., Komarova L. N., Nechaeva I. V. En ny ordbok över främmande ord. M.: 2003
  4. ↑ Förklarande ordbok för datavetenskap. Microsoft Press, Russian Edition, 1995
  5. ↑ Rysk stavningsordbok: cirka 180 000 ord [Elektronisk version] / O. E. Ivanova , V. V. Lopatin (ansvarig utg.), I. V. Nechaeva , L. K. Cheltsova . — 2:a uppl., rättad. och ytterligare — M .: Ryska vetenskapsakademin . Institutet för det ryska språket uppkallat efter V. V. Vinogradov , 2004. - 960 s. — ISBN 5-88744-052-X .
  6. ↑ Pershikov V.I., Savinkov V.M. Explanatory Dictionary of Informatics / Granskare: Cand. Phys.-Matte. Sci. A. S. Markov och Dr. Phys.-Math. Vetenskaper I. V. Pottosin. - M. : Finans och statistik, 1991. - 543 sid. — 50 000 exemplar.  - ISBN 5-279-00367-0 .
  7. ↑ Borkovsky A. B. Engelsk-Rysk ordbok för programmering och informatik (med tolkningar). - M . : Ryska språket, 1990. - 335 s. - 50 050 (ytterligare) exemplar.  — 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. - Januari 1998. - V. 20 , nr 1 . - S. 29-35 . - doi : 10.1109/85.646206 .
  9. ↑ Distribuerat OS . Hämtad 29 november 2009. Arkiverad från originalet 10 september 2010.

Litteratur

  • Bach M.J. UNIX Operativsystemsarkitektur