Cache-algoritme

Een Cache-algoritme is een algoritme dat wordt gebruikt om een cache of een groep gegevens te beheren. Wanneer de cache vol is, beslist het welk item uit de cache moet worden verwijderd. Het woord hit rate beschrijft hoe vaak een verzoek uit de cache kan worden verwijderd. De term latency beschrijft hoe lang een cache-item kan worden verkregen. Cache alorithms zijn een afweging tussen hit rate en latency.

  • Het meest efficiënte caching-algoritme zou zijn om altijd de informatie weg te gooien die het langst niet nodig is in de toekomst. Dit optimale resultaat wordt het optimale algoritme van Belady of het helderziende algoritme genoemd. Aangezien het over het algemeen onmogelijk is om te voorspellen hoe ver in de toekomst informatie nodig zal zijn, is dit in de praktijk meestal niet uitvoerbaar. Het praktische minimum kan pas na het experiment worden berekend en men kan de effectiviteit van het daadwerkelijk gekozen cache-algoritme vergelijken met het optimale minimum.
  • Minst recentelijk gebruikt (LRU): verwijdert de minst recent gebruikte items eerst. Dit algoritme vereist het bijhouden van wat wanneer is gebruikt. Dit is duur als men er zeker van wil zijn dat het algoritme altijd het minst recent gebruikte item weggooit. Algemene implementaties van deze techniek vereisen het bijhouden van "age bits" voor cache-lijnen en het bijhouden van de "Least Recently Used" cache-lijn op basis van age-bits. Bij een dergelijke implementatie verandert de leeftijd van alle andere cache-lijnen telkens wanneer een cache-lijn wordt gebruikt. LRU is eigenlijk een familie van cache-algoritmes met onder andere leden: 2Q van Theodore Johnson en Dennis Shasha en LRU/K van Pat O'Neil, Betty O'Neil en Gerhard Weikum.
  • Meest recentelijk gebruikt (MRU): Dit algoritme verwijdert de meest recent gebruikte items als eerste. Dit caching mechanisme wordt vaak gebruikt voor databasegeheugencaches.
  • Pseudo-LRU (PLRU): Er zijn bepaalde gevallen waarin de hoofdspoorwegonderneming zeer moeilijk te implementeren is. In dergelijke gevallen kan het voldoende zijn om te weten dat in de meeste gevallen een van de minst recentelijk gebruikte items wordt verwijderd. Het OURU-algoritme kan daar gebruikt worden, omdat het slechts één bit per cache-item nodig heeft om te werken.
  • 2-weg set associatief: voor hogesnelheids CPU-caches waar zelfs PLRU te traag is. Het adres van een nieuw item wordt gebruikt om een van de twee mogelijke locaties in de cache te berekenen waar het mag komen. De LRU van de twee wordt weggegooid. Dit vereist een bit per paar cachinelijnen, om aan te geven welke van de twee het minst recentelijk is gebruikt.
  • Direct-mapped cache: voor de CPU-caches met de hoogste snelheid waar zelfs 2-wegs set associatieve caches te traag zijn. Het adres van het nieuwe item wordt gebruikt om de ene locatie in de cache te berekenen waar het mag komen. Wat er eerder was wordt weggegooid.
  • Minst frequent gebruikt (LFU): LFU telt hoe vaak een item nodig is. Degenen die het minst vaak worden gebruikt, worden het eerst weggegooid.
  • Adaptieve vervangingscache (ARC): een constante balans tussen LRU en LFU, om het gecombineerde resultaat te verbeteren.
  • Multi Queue (MQ) caching algoritme: (door Y. Zhou J.F. Philbin en Kai Li).

Andere dingen om te overwegen:

  • Items met verschillende kosten: bewaar items die duur zijn om te verkrijgen, bijvoorbeeld die die lang duren om te krijgen.
  • Items die meer cache innemen: Als de items verschillende maten hebben, kan het zijn dat de cache een groot item wil weggooien om meerdere kleinere items op te slaan.
  • Items die met de tijd verlopen: Sommige caches bewaren informatie die vervalt (bijvoorbeeld een nieuwscache, een DNS-cache of een webbrowser-cache). De computer kan items weggooien omdat ze verlopen zijn. Afhankelijk van de grootte van de cache kan het zijn dat er geen verder cache-algoritme nodig is om items weg te gooien.

Er bestaan ook verschillende algoritmen om de cache-coherency te behouden. Dit geldt alleen voor situaties waarin meerdere onafhankelijke caches worden gebruikt voor dezelfde gegevens (bijvoorbeeld meerdere databaseservers die het ene gedeelde gegevensbestand updaten).

Welke geheugenlocaties kunnen worden gecached door welke cache-locaties
Welke geheugenlocaties kunnen worden gecached door welke cache-locaties


AlegsaOnline.com - 2020 / 2021 - License CC3