B Larrl Larddys algoritmedit
den mest effektive cachealgoritme ville være at altid kassere de oplysninger, der ikke er nødvendige i længst tid i fremtiden. Dette optimale resultat omtales som B. R. L. R. S optimale algoritme / simpelthen optimal erstatningspolitik eller den clairvoyante algoritme. Da det generelt er umuligt at forudsige, hvor langt i fremtiden information vil være nødvendig, kan dette generelt ikke implementeres i praksis. Det praktiske minimum kan kun beregnes efter eksperimentering, og man kan sammenligne effektiviteten af den faktisk valgte cache-algoritme.
i det øjeblik, hvor der opstår en sidefejl, er et sæt sider i hukommelsen. I eksemplet er sekvensen af ‘5’, ‘0’, ‘1’ er adgang til Ramme 1, Ramme 2, Ramme 3 henholdsvis. Så når’ 2 ‘er adgang, erstatter den værdi’ 5′, som er i ramme 1, da den forudsiger, at værdien’ 5 ‘ ikke vil blive adgang til i den nærmeste fremtid. Fordi en real-life generelle formål operativsystem faktisk ikke kan forudsige, hvornår ‘ 5 ‘ vil blive adgang til, kan b Rolistl Rolidys algoritme ikke implementeres på et sådant system.
First in first out (FIFO)Rediger
ved hjælp af denne algoritme opfører cachen sig på samme måde som en FIFO-kø. Cachen udsætter blokkene i den rækkefølge, de blev tilføjet, uden hensyntagen til hvor ofte eller hvor mange gange de blev åbnet før.
Last in first out (LIFO) eller First in last out (FILO)Rediger
ved hjælp af denne algoritme opfører cachen sig på samme måde som en stak og nøjagtig modsat måde som en FIFO-kø. Cachen udsætter den blok, der blev tilføjet Senest først, uden hensyntagen til hvor ofte eller hvor mange gange den blev åbnet før.
senest anvendte (LRU)Rediger
kasserer de senest anvendte emner først. Denne algoritme kræver at holde styr på, hvad der blev brugt hvornår, hvilket er dyrt, hvis man vil sikre sig, at algoritmen altid kasserer den mindst anvendte vare. Generelle implementeringer af denne teknik kræver at holde “aldersbit” for cache-linjer og spore den “mindst anvendte” cache-linje baseret på aldersbit. I en sådan implementering ændres alderen på alle andre cache-linjer hver gang en cache-linje bruges. LRU er faktisk en familie af caching algoritmer med medlemmer, herunder 2k af Theodore Johnson og Dennis Shasha, og LRU/K af Pat O ‘Neil, Betty O’ Neil og Gerhard.
adgangssekvensen for nedenstående eksempel er en B C D E D F.
i ovenstående eksempel, når en B C D bliver installeret i blokkene med sekvensnumre (stigning 1 for hver ny adgang), og når E er adgang, er det en miss, og den skal installeres i en af blokkene. I henhold til LRU-algoritmen, da A har den laveste rang(A(0)), erstatter E A.
i det andet sidste trin åbnes D, og derfor opdateres sekvensnummeret.
LRU kan ligesom mange andre erstatningspolitikker karakteriseres ved hjælp af et tilstandsovergangsfelt i et vektorrum, der bestemmer de dynamiske cache-tilstandsændringer svarende til, hvordan et elektromagnetisk felt bestemmer bevægelsen af en ladet partikel placeret i den.
Tidsbevidst senest brugt (TLRU)Rediger
den Tidsbevidste mindst nyligt anvendte (TLRU) er en variant af LRU designet til den situation, hvor det lagrede indhold i cachen har en gyldig levetid. Algoritmen er velegnet i netværkscache-applikationer, såsom Informationscentrisk netværk (ICN), indholdsleveringsnetværk (CDN ‘ er) og distribuerede netværk generelt. TLRU introducerer et nyt udtryk: TTU (tid til brug). TTU er et tidsstempel for et indhold / en side, der angiver brugbarhedstiden for indholdet baseret på indholdets lokalitet og indholdsudgiverens meddelelse. På grund af dette lokalitetsbaserede tidsstempel giver TTU mere kontrol til den lokale administrator for at regulere i netværkslagring.I tlru-algoritmen, når et stykke indhold ankommer, beregner en cache-node den lokale TTU-værdi baseret på den TTU-værdi, der er tildelt af indholdsudgiveren. Den lokale TTU-værdi beregnes ved hjælp af en lokalt defineret funktion. Når den lokale TTU-værdi er beregnet, udføres udskiftningen af indhold på en delmængde af det samlede indhold, der er gemt i cache-node. TLRU sikrer, at mindre populært og lille livsindhold skal erstattes med det indgående indhold.
senest anvendte (MRU)Rediger
kasserer, i modsætning til LRU, de senest anvendte varer først. I resultater præsenteret på den 11.vldb-konference bemærkede Chou og Duvitt, at “når en fil gentagne gange scannes i et referencemønster, er MRU den bedste erstatningsalgoritme.”Efterfølgende bemærkede andre forskere, der præsenterede på den 22.vldb-konference, at for tilfældige adgangsmønstre og gentagne scanninger over store datasæt (undertiden kendt som cykliske adgangsmønstre) har MRU-cachealgoritmer flere hits end LRU på grund af deres tendens til at bevare ældre data. MRU-algoritmer er mest nyttige i situationer, hvor jo ældre et element er, jo mere sandsynligt er det at få adgang til det.
adgangssekvensen for nedenstående eksempel er en B C D E C D B.
her placeres en B C D i cachen, da der stadig er plads til rådighed. Ved 5. adgang E ser vi, at blokken, der holdt D, nu erstattes med E, da denne blok blev brugt Senest. En anden adgang til C og ved den næste adgang til D, C erstattes, da det var blokken, der blev åbnet lige før D og så videre.
Pseudo-LRU (PLRU)Rediger
for CPU-cacher med stor associativitet (generelt > 4 måder) bliver implementeringsomkostningerne for LRU uoverkommelige. I mange CPU-cacher er en ordning, der næsten altid kasserer en af de mindst anvendte genstande, tilstrækkelig, så mange CPU-designere vælger en PLRU-algoritme, som kun har brug for en bit pr.PLRU har typisk et lidt dårligere miss-forhold, har en lidt bedre latenstid, bruger lidt mindre strøm end LRU og lavere omkostninger sammenlignet med LRU.
følgende eksempel viser, hvordan Bits fungerer som et binært træ med 1-bit pointers, der peger på det mindre nyligt anvendte undertræ. Efter pegerkæden til bladknuden identificerer udskiftningskandidaten. Ved en adgang er alle peger i kæden fra den tilgængelige vejs bladknude til rodnoden indstillet til at pege på undertræ, der ikke indeholder den tilgængelige måde.
adgangssekvensen er en B C D E.
princippet her er let at forstå, hvis vi kun ser på pilpegerne. Når der er adgang til en værdi, skal du sige ‘A’, og vi ikke kan finde den i cachen, så indlæser vi den fra hukommelsen og placerer den ved den blok, hvor pilene i øjeblikket peger, og går fra top til bund. Når vi har placeret den blok, vender vi de samme pile, så de peger den modsatte vej. I ovenstående eksempel ser vi, hvordan ‘A’ blev placeret, efterfulgt af ‘B’, ‘C og ‘D’. Derefter blev cachen fuld ‘e’ erstattet ‘a’, fordi det var her pilene pegede på det tidspunkt, og pilene, der førte til’ A’, blev vendt for at pege i den modsatte retning. Pilene førte derefter til’ B’, som vil være blokken erstattet på den næste cache miss.
tilfældig udskiftning (RR)Rediger
vælger tilfældigt et kandidatelement og kasserer det for at skabe plads, når det er nødvendigt. Denne algoritme kræver ikke, at der opbevares oplysninger om adgangshistorikken. For sin enkelhed er den blevet brugt i ARM-processorer. Det indrømmer effektiv stokastisk simulering.
adgangssekvensen for nedenstående eksempel er en B C D E B D F
segmenteret LRU (SLRU)Rediger
SLRU cache er opdelt i to segmenter, et prøvesegment og et beskyttet segment. Linjer i hvert segment bestilles fra de mest til de mindst nyligt tilgængelige. Data fra misser føjes til cachen i den senest tilgængelige ende af prøvesegmentet. Hits fjernes, uanset hvor de i øjeblikket bor, og føjes til den senest tilgængelige ende af det beskyttede segment. Linjer i det beskyttede segment er således blevet adgang til mindst to gange. Det beskyttede segment er endeligt, så migration af en linje fra prøvesegmentet til det beskyttede segment kan tvinge migrationen af LRU-linjen i det beskyttede segment til den senest anvendte (MRU) ende af prøvesegmentet, hvilket giver denne linje endnu en chance for at få adgang til, før den udskiftes. Størrelsesgrænsen for det beskyttede segment er en SLRU-parameter, der varierer afhængigt af I/O-arbejdsbyrden. Når data skal kasseres fra cachen, opnås linjer fra LRU-enden af prøvesegmentet.
mindst hyppigt anvendte (LFU)Rediger
tæller, hvor ofte en vare er nødvendig. De, der bruges mindst ofte, kasseres først. Dette fungerer meget lig LRU bortset fra at i stedet for at gemme værdien af, hvor for nylig en blok blev åbnet, gemmer vi værdien af, hvor mange gange den blev åbnet. Så selvfølgelig, mens du kører en adgangssekvens, erstatter vi en blok, der blev brugt færrest gange fra vores cache. F. eks. Hvis A blev brugt (adgang til) 5 gange og B blev brugt 3 gange og andre C og D blev brugt 10 gange hver, erstatter vi B.
mindst hyppige nyligt anvendte (LFRU)Rediger
den mindst hyppige nyligt anvendte (LFRU) cache-udskiftningsordning kombinerer fordelene ved LFU-og LRU-ordninger. LFRU er velegnet til’ i netværk ‘cache-applikationer, såsom Informationscentrisk netværk (ICN), indholdsleveringsnetværk (CDN’ er) og distribuerede netværk generelt. I lfru er cachen opdelt i to partitioner kaldet privilegerede og uprivilegerede partitioner. Den privilegerede partition kan defineres som en beskyttet partition. Hvis indhold er meget populært, skubbes det ind i den privilegerede partition. Udskiftning af den privilegerede partition sker som følger: LFRU udsætter indhold fra den uprivilegerede partition, skubber indhold fra privilegeret partition til uprivilegeret partition og indsætter til sidst nyt indhold i den privilegerede partition. I ovenstående procedure bruges LRU til den privilegerede partition, og en tilnærmet LFU (ALFU) – ordning bruges til den uprivilegerede partition, deraf forkortelsen LFRU.
grundideen er at filtrere det lokalt populære indhold ud med ALFU-ordningen og skubbe det populære indhold til en af de privilegerede partitioner.
LFU med dynamisk aldring (LFUDA)Rediger
en variant kaldet LFU med dynamisk aldring (LFUDA), der bruger dynamisk aldring til at rumme skift i sættet med populære objekter. Det tilføjer en cache-aldersfaktor til referencetællingen, når et nyt objekt føjes til cachen, eller når et eksisterende objekt refereres igen. LFUDA øger cachen aldre, når evicting blokke ved at indstille den til den udsatte objektets nøgleværdi. Således er cache-alderen altid mindre end eller lig med den mindste nøgleværdi i cachen. Antag, at når et objekt ofte blev åbnet i fortiden, og nu bliver det upopulært, vil det forblive i cachen i lang tid og derved forhindre de nyligt eller mindre populære objekter i at erstatte det. Så denne dynamiske aldring introduceres for at nedbringe antallet af sådanne genstande og derved gøre dem berettigede til udskiftning. Fordelen ved LFUDA er det reducerer cache forurening forårsaget af LFU når cache størrelser er meget små. Når Cache størrelser er store få udskiftning beslutninger er tilstrækkelige og cache forurening vil ikke være et problem.
lav inter-reference recency set (LIRS)Rediger
LIRS er en side udskiftning algoritme med en forbedret ydeevne over LRU og mange andre nyere udskiftning algoritmer. Dette opnås ved at bruge genbrugsafstand som en metrisk til dynamisk placering af tilgængelige sider for at træffe en erstatningsbeslutning. LIRS adresserer effektivt grænserne for LRU ved at bruge recency til at evaluere Inter-Reference Recency (IRR) til at træffe en erstatningsbeslutning.
i ovenstående figur repræsenterer “h”, at der er adgang til en blok på tidspunktet t. Antag, at hvis blok A1 er tilgængelig på tidspunktet 1, bliver Recency 0, da dette er den første adgang til blok, og IRR vil være 1, da det forudsiger, at A1 vil blive åbnet igen i tide 3. I tiden 2 siden A4 er adgang, bliver nyheden 0 for A4 og 1 for A1, fordi A4 er det senest tilgængelige objekt, og IRR bliver 4, og det fortsætter. På tid 10 vil lirs-algoritmen have to sæt LIR set = {A1, A2} og HIR set = {A3, A4, A5}. Nu på tid 10 hvis der er adgang til A4, forekommer miss. LIRS algoritme vil nu smide A5 i stedet for A2 på grund af sin største recency.
CLOCK-ProEdit
LRU-algoritme kan ikke implementeres direkte i den kritiske vej til computersystemer, såsom operativsystemer, på grund af dens høje overhead. En tilnærmelse af LRU, kaldet ur, bruges ofte til implementeringen. Tilsvarende er CLOCK-Pro en tilnærmelse af LIRS til en billig implementering i systemer. CLOCK-Pro er under den grundlæggende URRAMME, men har tre store forskellige fordele. For det første har CLOCK-Pro tre “urhænder” i modsætning til en simpel URSTRUKTUR, hvor kun en “hånd” bruges. Med de tre hænder er CLOCK-Pro i stand til at måle genbrugsafstanden for dataadgang på en omtrentlig måde. For det andet bevares alle fordelene ved LIRS, såsom hurtigt at udskyde engangsadgang og/eller dataelementer med lav lokalitet. For det tredje er kompleksiteten af CLOCK-Pro den samme som CLOCK, og det er derfor let at implementere til en lav pris. Implementeringen af buffercacheudskiftningen i den aktuelle version er en kombination af LRU og CLOCK-Pro.
adaptiv udskiftningscache (ARC)Rediger
balancerer konstant mellem LRU og LFU for at forbedre det kombinerede resultat. ARC forbedrer SLRU ved at bruge oplysninger om nyligt udsatte cache-elementer til dynamisk at justere størrelsen på det beskyttede segment og prøvesegmentet for at udnytte den tilgængelige cache-plads bedst muligt. Adaptiv udskiftningsalgoritme forklares med eksemplet.
AdaptiveClimb (AC)Edit
bruger seneste hit / miss til at justere springet, hvor I klatre et hit skifter positionen en slot til toppen, og i LRU hit skifter hitets position til toppen. Således drager fordel af optimaliteten af klatring, når programmet er i et fast omfang, og den hurtige tilpasning til et nyt omfang, som LRU gør. Understøtter også cache-deling mellem kerner ved at frigive ekstramateriale, når referencerne er til den øverste del af cachen.
ur med adaptiv udskiftning (bil)Rediger
kombinerer fordelene ved adaptiv Udskiftningscache (ARC) og ur. Bilen har ydeevne, der kan sammenlignes med ARC, og overgår væsentligt både LRU og ur. Ligesom ARC er bilen selvindstillet og kræver ingen brugerdefinerede magiske parametre. Det bruger 4 dobbelt forbundet lister: to ure T1 og T2 og to enkle LRU lister B1 og B2. T1 clock gemmer sider baseret på “recency” eller “short term utility”, mens T2 gemmer sider med “frekvens” eller “long term utility”. T1 og T2 indeholder de sider, der er i cachen, mens B1 og B2 indeholder sider, der for nylig er blevet udsat for henholdsvis T1 og T2. Algoritmen forsøger at opretholde størrelsen på disse lister B1-kur T2 og B2-kur T1. Nye sider indsættes i T1 eller T2. Hvis der er et hit i B1 størrelse på T1 øges, og tilsvarende hvis der er et hit i B2 størrelse på T1 er faldet. Den anvendte tilpasningsregel har det samme princip som i ARC, invester mere i lister, der giver flere hits, når flere sider føjes til den.
Multi kø Rediger
multi kø algoritme eller MK blev udviklet til at forbedre ydeevnen af andet niveau buffer cache for f.eks. en server buffer cache. Cachen indeholder et m-antal LRU-køer: 0. kvartal, 1. kvartal,…, KM1. Her repræsenterer værdien af m et hierarki baseret på levetiden for alle blokke i den pågældende kø. For eksempel, hvis j >i, vil blokke i kj have en længere levetid end dem i Ki. Ud over disse er der en anden historikbuffer, en kø, der opretholder en liste over alle Blokidentifikatorer sammen med deres adgangsfrekvenser. Når den er fuld, bliver den ældste identifikator smidt ud. Blokke forbliver i LRU-køerne i en given levetid, som defineres dynamisk af MK-algoritmen til at være den maksimale tidsmæssige afstand mellem to adgange til den samme fil eller antallet af cache-blokke, alt efter hvad der er større. Hvis der ikke er henvist til en blok inden for dens levetid, degraderes den fra Chi til Chi−1 eller udvises fra cachen, hvis den er i 0.kvartal. Hvis der er adgang til en blok i kø Chi mere end 2i gange, forfremmes denne blok til Chi+1, indtil den er adgang til mere end 2i+1 gange, eller dens levetid udløber. Inden for en given kø rangeres blokke efter nylig adgang, ifølge LRU.
Vi kan se fra Fig. hvordan m LRU køer er placeret i cachen. Se også Fig. Sådan gemmes blokidentifikatorerne og deres tilsvarende adgangsfrekvenser. a blev placeret i 0. kvartal, da det kun blev åbnet en gang for nylig, og vi kan kontrollere, hvordan b og c blev placeret i henholdsvis 1.kvartal og 2. kvartal, da deres adgangsfrekvenser er 2 og 4. Køen, hvor en blok er placeret, afhænger af adgangsfrekvensen (f) som log2(f). Når cachen er fuld, vil den første blok, der skal udvises, være lederen af 0. kvartal i dette tilfælde a. hvis der åbnes en gang til, flyttes den til 1.kvartal under b.
Pannier: containerbaseret cachelagringsalgoritme til sammensatte objekterredit
Pannier er en containerbaseret flash-cachemekanisme, der identificerer divergerende (heterogene) containere, hvor blokke deri har meget forskellige adgangsmønstre. Pannier bruger en prioritetskøbaseret overlevelseskøstruktur til at rangordne containerne baseret på deres overlevelsestid, hvilket er proportionalt med live-dataene i containeren. Pannier er bygget baseret på segmenteret LRU (S2LRU), som adskiller varme og kolde data. Pannier bruger også en multi-trins feedback controller til at gasspjæld flash skriver for at sikre flash levetid.