Cache (tijdelijk geheugen)

Hoe caches werken

Een cache is een blok geheugen voor het opslaan van gegevens die waarschijnlijk opnieuw worden gebruikt. De CPU en de harde schijf gebruiken vaak een cache, net als webbrowsers en webservers.

Een cache bestaat uit veel inzendingen, een zogenaamde pool. Elke entry bevat een referentiepunt (een beetje data) dat een kopie is van een referentiepunt op een andere plaats. Caches gebruiken meestal een zogenaamde backing store. Backing stores zijn traag of duur in vergelijking met de cache. Een schijfcache gebruikt bijvoorbeeld een harde schijf als backing store. Elke entry heeft ook een beetje informatie bijgevoegd, een zogenaamde tag. Deze tag wordt gebruikt om de locatie te vinden waar de originele gegevens zijn opgeslagen.

Caches voor het lezen

Een client (een CPU, webbrowser, besturingssysteem) wil toegang tot een beetje data, het gelooft in de backing store, het controleert eerst of de datum kan worden gevonden in de cache. Als de gegevens in de cache kunnen worden gevonden, kan de client deze gebruiken en hoeft hij niet het hoofdgeheugen te gebruiken. Dit staat bekend als een cachehit. Dus, bijvoorbeeld, een webbrowser programma kan zijn lokale cache op schijf controleren om te zien of het een lokale kopie heeft van de inhoud van een webpagina op een bepaalde URL. In dit voorbeeld is de URL de tag en de inhoud van de webpagina de datum.

De andere situatie die zich kan voordoen is dat het referentiepunt met de tag niet in de cache te vinden is. Dit staat bekend als cache miss. Het referentiepunt moet worden opgehaald bij de backing store. Meestal wordt het in de cache gekopieerd, zodat het de volgende keer niet meer uit de backing store gehaald hoeft te worden.

De cache heeft slechts een beperkte omvang. Om ruimte te maken voor de eerder niet in de cache opgenomen vermelding, kan het nodig zijn een andere vermelding uit de cache te verwijderen. Er worden speciale regels gebruikt om de vermelding te vinden die het best kan worden verwijderd. Deze regels worden meestal Heuristiek genoemd. Heuristieken die gebruikt worden om de entry te vinden worden vervangend beleid genoemd. Een zeer eenvoudige regel die gebruikt wordt heet Minst recentelijk gebruikt (of LRU). Het neemt gewoon de entry die het langst geleden is gebruikt. Andere heuristieken worden vermeld bij het cache-algoritme...

Caches voor het schrijven

Caches kunnen ook worden gebruikt voor het schrijven van gegevens; het voordeel hiervan is dat de klant de werking ervan kan voortzetten zodra de entry naar de cache is geschreven; hij hoeft niet te wachten tot de entry naar de backing store is geschreven.

De vermelding moet echter wel op een bepaald moment naar de backing store worden geschreven. Het tijdstip waarop dit gebeurt, wordt bepaald door het schrijfbeleid.

In een doorschrijfcache wordt elke vermelding onmiddellijk naar de backing store geschreven en in de cache opgeslagen.

De andere optie is om alleen naar de cache te schrijven, en later naar de backing store te schrijven. Dit staat bekend als write-back (of write-behind) cache. De cache markeert de vermeldingen die nog niet naar de backing store zijn geschreven; het merkteken dat wordt gebruikt wordt vaak aangeduid als "dirty flag". Voordat de items uit de cache worden verwijderd, worden ze naar de backing store geschreven. Dit staat bekend als lazy write. Een misser in een write-back cache (waarbij een blok moet worden vervangen door een ander) zal vaak twee geheugentoegangen nodig hebben: een om de benodigde datum te krijgen, en een andere om vervangende data uit de cache naar de store te schrijven.

Het cachingbeleid kan ook zeggen dat een bepaalde datum in de cache moet worden geplaatst. De klant kan veel wijzigingen hebben aangebracht in de datum in de cache. Nadat dit is gedaan, kan hij de cache expliciet vertellen dat de datum moet worden teruggeschreven.

No-write toewijzing is een cachebeleid waarbij alleen lezen wordt gecached. Dit vermijdt de noodzaak om terug te schrijven of door te schrijven in de cache. Schrijven gebeurt de hele tijd in de backing store.

De klant is niet de applicatie die de gegevens in de backing store wijzigt. Als de gegevens in de backing store zijn gewijzigd, zal de kopie in de cache verouderd of muf zijn. Als de cliënt de gegevens in de cache bijwerkt, worden kopieën van die gegevens in andere caches muf. Er zijn speciale communicatieprotocollen die cachemanagers in staat stellen met elkaar te praten om de gegevens betekenisvol te houden. Deze staan bekend als coherency protocollen.

Diagram van een CPU-geheugencache

Selecteren van de te vervangen vermelding

Een cache is klein en zal meestal vol zijn, of bijna vol. Dus als er een nieuwe waarde wordt toegevoegd, moet er een oude worden verwijderd. Er zijn verschillende manieren waarop deze selectie kan worden gedaan:

• First in First out: Vervang gewoon de vermelding die het langst geleden aan de cache werd toegevoegd...
• Minst recentelijk gebruikt: Dit idee is vergelijkbaar met de FIFO hierboven, maar wanneer een item wordt gebruikt, wordt de tijdstempel/leeftijd bijgewerkt.
• Minstens zo vaak gebruikt: Ook hier geldt dat, net als bij de FIFO-zaak, in plaats van een tijdstempel een teller moet worden gebruikt, die elke keer dat een item wordt gebruikt, wordt verhoogd.
• Kies een willekeurig item

Geschiedenis

Het woord cache werd voor het eerst gebruikt in de informatica in 1967, toen een wetenschappelijk artikel werd voorbereid om te worden gepubliceerd in IBM Systems Journal. Het artikel ging over een nieuwe verbetering van het geheugen in Model 85. Model 85 was een computer van de IBM System/360 productlijn. De redacteur van het Journal wilde een beter woord voor hogesnelheidsbuffer, gebruikt in het artikel. Hij kreeg geen input, en stelde een cache voor, van de Franse cacher, wat betekent "te verbergen". Het artikel werd gepubliceerd in het begin van 1968, en de auteurs werden vereerd door IBM. Hun werk werd breed toegejuicht en verbeterd. Cache werd al snel standaardgebruik in de computerliteratuur.

Waar caches worden gebruikt

CPU-caches

Kleine geheugens op of dicht bij de CPU-chip kunnen sneller worden gemaakt dan het veel grotere hoofdgeheugen. De meeste CPU's hebben sinds de jaren '80 één of meer caches gebruikt. Moderne algemene CPU's in pc's kunnen wel een half dozijn bevatten. Elke cache kan gespecialiseerd zijn in een ander deel van de taak om programma's uit te voeren.

Schijfcaches

CPU-caches worden over het algemeen volledig door hardware beheerd, andere caches worden door een ander soort software beheerd. Het besturingssysteem beheert meestal een pagina-cache in het hoofdgeheugen. Gebruikers buiten de computerwetenschap noemen deze cache meestal virtueel geheugen. Het wordt beheerd door de kernel van het besturingssysteem.

Moderne harde schijven hebben schijfbuffers. Deze worden soms "disk cache" genoemd, maar dit is verkeerd. De belangrijkste functie van deze buffers is het bestellen van schijfschrijven, en het beheren van reads. Herhaalde cache hits zijn zeldzaam, omdat de buffer erg klein is in vergelijking met de grootte van de harde schijf.

Lokale harde schijven zijn snel in vergelijking met andere opslagapparaten, zoals externe servers, lokale tapedrives of optische jukeboxen. Het gebruik van lokale harde schijven als cache is het belangrijkste concept van hiërarchisch opslagbeheer.

Webcaches

Webbrowsers en webproxyservers gebruiken caches om eerdere reacties van webservers, zoals webpagina's, op te slaan. Webcaches verminderen de hoeveelheid informatie die over het netwerk moet worden verzonden. Informatie die eerder in de cache is opgeslagen, kan vaak opnieuw worden gebruikt. Dit vermindert de bandbreedte en de verwerkingsvereisten van de webserver en draagt bij aan een betere respons voor de gebruikers van het web.

Moderne webbrowsers maken gebruik van een ingebouwde web cache, maar sommige internet service providers of organisaties maken ook gebruik van een caching proxy server. Dit is een web cache die gedeeld wordt tussen alle gebruikers van dat netwerk.

Zoekmachines maken ook vaak webpagina's die ze hebben geïndexeerd beschikbaar vanuit hun cache. Google stelt bijvoorbeeld een "Cached" link ter beschikking naast elk zoekresultaat. Dit is handig wanneer webpagina's tijdelijk ontoegankelijk zijn vanaf een webserver.

Caching met onbetrouwbare netwerken

Doorschrijven is gebruikelijk in onbetrouwbare netwerken (zoals een Ethernet LAN). Het protocol dat wordt gebruikt om ervoor te zorgen dat de gegevens in de schrijf-cache zinvol zijn wanneer er meerdere schrijf-caches worden gebruikt, is in zo'n geval zeer complex.

Bijvoorbeeld, webpagina caches en client-side netwerkbestandssysteem caches (zoals die in NFS of SMB) zijn meestal read-only of write-through om het netwerkprotocol eenvoudig en betrouwbaar te houden.

Het verschil tussen buffer en cache

Buffer en cache sluiten elkaar niet uit, ze worden ook vaak samen gebruikt. De reden waarom ze worden gebruikt is echter anders. Een buffer is een locatie in het geheugen die traditioneel wordt gebruikt omdat CPU-instructies niet direct gegevens kunnen aanspreken die zijn opgeslagen in randapparatuur. Het computergeheugen wordt gebruikt als tussenopslag.

Bovendien kan een dergelijke buffer haalbaar zijn wanneer een groot blok gegevens wordt samengesteld of gedemonteerd (zoals vereist door een opslagapparaat), of wanneer de gegevens in een andere volgorde worden geleverd dan die waarin ze worden geproduceerd. Ook wordt een hele buffer van gegevens meestal sequentieel overgedragen (bijvoorbeeld naar de harde schijf), dus het bufferen zelf verhoogt soms de overdrachtprestaties. Deze voordelen zijn zelfs aanwezig als de gebufferde gegevens één keer naar de buffer worden geschreven en één keer uit de buffer worden gelezen.

Een cache verhoogt ook de overdrachtsprestaties. Een deel van de verhoging komt ook voort uit de mogelijkheid dat meerdere kleine transfers worden gecombineerd tot één groot blok. Maar de belangrijkste prestatiewinst komt omdat de kans groot is dat dezelfde datum meerdere keren uit de cache wordt gelezen, of dat de geschreven gegevens snel worden gelezen. Het enige doel van Caches is om de toegang tot de onderliggende tragere opslag te verminderen. Cache is meestal ook een abstractielaag die ontworpen is om onzichtbaar te zijn vanuit het perspectief van naburige lagen. Op die manier is het mogelijk dat de applicaties of clients zich niet bewust zijn van het feit dat er een cache is.