Caching- algoritmer ( preemption algorithms , preemption policys , og "replacement algorithms / policies") - i datalogi er dette instruktionsoptimering : et specielt computerprogram eller hardware-understøttet struktur , der kan styre cachen af information, der er gemt på en computer. Når cachen er fuld, skal algoritmen vælge, hvad der præcist skal fjernes fra den, for at kunne skrive (til cachen) ny, mere opdateret information. Hardwareimplementeringen af disse algoritmer involverer brugen af en timer , tæller eller en kombination af begge.
"Hitraten" i cachen refererer til, hvor ofte de data, du leder efter, findes i cachen. Mere effektive fraflytningspolitikker holder styr på adgangen til de mest brugte oplysninger for at forbedre hitraterne (for samme cachestørrelse).
Cache "latency" henviser til, hvor hurtigt cachen kan returnere de anmodede data umiddelbart efter anmodningen (i tilfælde af, at et "hit" opstår). Hurtigere udsættelsesstrategier holder typisk styr på den mindst brugte information - eller, i tilfælde af en direkte kortlagt cache, manglen på information - for at reducere den tid, det tager at opdatere informationen.
Hver forskydningsstrategi er et kompromis mellem hitrate og latens.
Den mest effektive udsættelsesregel er at kassere oplysninger fra cachen, som ikke vil være nødvendige længst i fremtiden. Denne optimale caching-algoritme er blevet kaldt Beladi- algoritmen eller fremsynsalgoritmen . Da det i det generelle tilfælde er umuligt at forudsige, hvornår nøjagtigt disse oplysninger vil være nødvendige næste gang, er en sådan implementering i praksis (igen i det generelle tilfælde) umulig. Det praktiske minimum kan kun beregnes empirisk, hvorefter effektiviteten af den aktuelle cachingalgoritme kan sammenlignes med den.
Mindst nyligt brugt (LRU): Først og fremmest er den længste ubrugte forskudt. Denne algoritme kræver at holde styr på, hvad der blev brugt og hvornår, hvilket kan være ret dyrt, især hvis du skal foretage yderligere verifikation for at være sikker. Den generelle implementering af denne metode kræver, at man holder en "aldersbit" for cache-linjer, og ved at gøre det holder man styr på de mindst brugte linjer (det vil sige ved at sammenligne sådanne bits). I en sådan implementering ændres "alderen" på alle andre linjer, hver gang der tilgås en cache-linje. LRU er faktisk en familie af caching-algoritmer , der inkluderer 2Q af Theodore Johnson og Dennis Schasha, og LRU/K af Pat O'Neill, Betty O'Neill og Gerhard Weikum.
Most Recently Used (MRU): I modsætning til LRU bliver den senest brugte genstand smidt ud først. Ifølge kilden [1] , "Når en fil periodisk scannes på en round robin-måde, er MRU den bedste eviction-algoritme." I [2] understreger forfatterne også, at for random access -skemaer og cyklisk scanning af store datasæt (nogle gange kaldet round robin-skemaer) har MRU-caching-algoritmer flere hits sammenlignet med LRU på grund af deres tendens til at bevare gamle data. MRU-algoritmer er mest nyttige i tilfælde, hvor jo ældre elementet er, jo flere adgange til det.
Pseudo-LRU (PLRU): For caches med stor associativitet (typisk mere end 4 kanaler), bliver de nødvendige ressourcer til at implementere LRU for store. Hvis politikken er tilstrækkelig til næsten altid at kassere den mindst brugte post, så kan PLRU-algoritmen bruges i dette tilfælde, hvilket kun kræver én bit pr. cache-indgang.
Segmenteret LRU (eller SLRU): “SLRU-cachen er opdelt i to segmenter: et prøvesegment og et beskyttet segment. Linjerne i hvert segment er ordnet fra mest brugt til mindst brugt. Data om fejl føjes til cachen og i området for de sidst brugte elementer i prøvesegmentet. Data om hits fjernes, uanset hvor de er placeret, og føjes til området med ofte brugte elementer i det beskyttede segment. Der er således adgang til beskyttede segmentrækker mindst to gange. Det beskyttede segment er begrænset. En sådan linjeoverførsel fra forsøgssegmentet til det beskyttede segment kan forårsage, at den sidst brugte (LRU) række i det beskyttede segment overføres til MRU-området i forsøgssegmentet, hvilket giver den linje en ny chance for at blive brugt, før den bliver brugt smidt ud. Den beskyttede segmentstørrelse er en SLRU-parameter, der varierer afhængigt af I/O-skemaet. Når data skal fjernes fra cachen, anmodes der om rækker fra LRU-enden af sondesegmentet. [3] »
2-vejs associativitet gælder for højhastighedsprocessorcacher , hvor selv PLRU'en er for langsom. Adressen på det nye element bruges til at beregne en af to mulige placeringer i cachen (i det område, der er tildelt til dette). Ifølge LRU-algoritmen er to elementer forskudt. Det kræver en bit til et par cache-linjer for at angive, hvilke der sidst blev brugt.
Direct Mapped Cache : Til højhastighedsprocessorcaches, hvor ydeevnen af 2-vejs associativ cache mangler. Adressen på det nye element bruges til at beregne placeringen i cachen (i det område, der er tildelt hertil). Alt, hvad der var før, bliver udskiftet.
Mindst hyppigt brugt (LFU): LFU tæller, hvor ofte et element bruges. De elementer, der er tilgået mindst ofte, foregribes først.
Adaptive Replacement Cache (ARC): [4] balancerer konstant mellem LRU og LFU, hvilket forbedrer det endelige resultat.
Multi Queue (MQ) caching-algoritme : [5] (udviklet af Y. Zhu, J. F. Philbin og Kai Li).
Følgende punkter tages i betragtning:
Der er også forskellige algoritmer til at sikre cache-kohærens . Dette gælder kun i tilfælde, hvor flere uafhængige caches bruges til at gemme den samme information (f.eks. opdaterer flere databaseservere en fælles datafil).