Bélády ‘ s algoritmedit
het meest efficiënte caching-algoritme zou zijn om altijd de informatie weg te gooien die in de toekomst niet langer nodig zal zijn. Dit optimale resultaat wordt aangeduid als bélády ‘ s optimal algorithm / simply optimal replacement policy of het helderziende algoritme. Aangezien het over het algemeen onmogelijk is te voorspellen in hoeverre in de toekomst informatie nodig zal zijn, is dit in de praktijk over het algemeen niet uitvoerbaar. Het praktische minimum kan alleen worden berekend na experimenten, en men kan de effectiviteit van de daadwerkelijk gekozen cache algoritme vergelijken.
op het moment dat een paginafout optreedt, is een aantal pagina ‘ s in het geheugen. In het voorbeeld, de volgorde van ‘5’, ‘0’, ‘1’ is toegankelijk door Frame 1, Frame 2, Frame 3 respectievelijk. Wanneer’ 2 ‘dan wordt benaderd, vervangt het waarde’ 5′, die in frame 1 is omdat het voorspelt dat waarde’ 5 ‘ niet zal worden benaderd in de nabije toekomst. Omdat een real-life algemeen besturingssysteem niet kan voorspellen wanneer ‘5’ zal worden benaderd, kan Bélády ‘ s algoritme niet worden geïmplementeerd op een dergelijk systeem.
First in first out (FIFO)Bewerk
met dit algoritme gedraagt de cache zich op dezelfde manier als een FIFO-wachtrij. De cache zet de blokken uit in de volgorde waarin ze zijn toegevoegd, zonder rekening te houden met hoe vaak of hoe vaak ze eerder zijn benaderd.
Last in first out (LIFO) of First in last out (FILO)Bewerk
met behulp van dit algoritme gedraagt de cache zich op dezelfde manier als een stack en precies andersom als een FIFO-wachtrij. De cache zet het blok toegevoegd meest recent eerst zonder enige aandacht voor hoe vaak of hoe vaak het eerder werd geopend.
minst recent gebruikte (LRU)bewerken
verwijdert eerst de minst recent gebruikte items. Dit algoritme vereist het bijhouden van wat werd gebruikt wanneer, dat is duur als men wil ervoor zorgen dat het algoritme altijd teruggooit het minst recent gebruikte item. Algemene implementaties van deze techniek vereisen het bewaren van “age bits” voor cache-lijnen en het bijhouden van de “minst recent gebruikte” cache-lijn gebaseerd op age-bits. In een dergelijke implementatie verandert telkens wanneer een cache-lijn wordt gebruikt, de leeftijd van alle andere cache-lijnen. LRU is eigenlijk een familie van caching algoritmes met leden waaronder 2Q van Theodore Johnson en Dennis Shasha, en LRU / K van Pat O ‘Neil, Betty O’ Neil en Gerhard Weikum.
De toegangsvolgorde voor het onderstaande voorbeeld is een B C D E D F.
in het bovenstaande voorbeeld wanneer een B C D wordt geïnstalleerd in de blokken met volgnummers (verhoging 1 voor elke nieuwe toegang) en wanneer E wordt geopend, is het een misser en moet het worden geïnstalleerd in een van de blokken. Volgens het LRU-algoritme, aangezien A De laagste rang heeft(A(0)), vervangt E A.
in de voorlaatste stap D wordt benaderd en daarom wordt het volgnummer bijgewerkt.
LRU kan, net als veel andere vervangingsbeleid, worden gekarakteriseerd met behulp van een toestandstransitieveld in een vectorruimte, dat de dynamische toestandsveranderingen bepaalt die vergelijkbaar zijn met hoe een elektromagnetisch veld de beweging bepaalt van een geladen deeltje dat erin wordt geplaatst.
Time aware least recently used (TLRU)bewerken
De Time aware Least Recently Used (TLRU) is een variant van LRU die is ontworpen voor de situatie waarin de opgeslagen inhoud in de cache een geldige levensduur heeft. Het algoritme is geschikt voor Netwerk cache-toepassingen, zoals informatie-centric networking( LIW), Content Delivery Networks (CDN ‘ s) en gedistribueerde netwerken in het algemeen. TLRU introduceert een nieuwe term: TTU (tijd om te gebruiken). TTU is een tijdstempel van een inhoud/pagina die de bruikbaarheidstijd voor de inhoud bepaalt op basis van de plaats van de inhoud en de aankondiging van de uitgever van de inhoud. Door deze local based time stamp biedt TTU meer controle aan de lokale beheerder om de netwerkopslag te reguleren.In het TLRU-algoritme berekent een cacheknooppunt de lokale TTU-waarde op basis van de TTU-waarde die door de inhouduitgever is toegewezen. De lokale TTU-waarde wordt berekend met behulp van een lokaal gedefinieerde functie. Zodra de lokale TTU-waarde is berekend, wordt de vervanging van inhoud uitgevoerd op een subset van de totale inhoud die is opgeslagen in het cacheknooppunt. De TLRU zorgt ervoor dat minder populaire en kleine leven inhoud moet worden vervangen door de inkomende inhoud.
meest recent gebruikte (MRU)Bewerk
teruggooi, in tegenstelling tot HOOFDSPOORWEGONDERNEMING, de meest recent gebruikte items eerst. In bevindingen gepresenteerd op de 11e VLDB conferentie, Chou en DeWitt opgemerkt dat “wanneer een bestand herhaaldelijk wordt gescand in een referentiepatroon, MRU is de beste vervanging algoritme.”Vervolgens, andere onderzoekers presenteren op de 22e VLDB conferentie opgemerkt dat Voor willekeurige toegang patronen en herhaalde scans over grote datasets (soms bekend als cyclische toegangspatronen) MRU cache algoritmen hebben meer hits dan LRU als gevolg van hun neiging om oudere gegevens te behouden. MRU-algoritmen zijn het nuttigst in situaties waar hoe ouder een item is, hoe waarschijnlijker het is om te worden benaderd.
De toegangsvolgorde voor het onderstaande voorbeeld is een B C D E C D B.
Hier wordt een B C D in de cache geplaatst omdat er nog ruimte beschikbaar is. Bij de 5e toegang E, zien we dat het blok dat hield D is nu vervangen door E zoals dit blok werd gebruikt meest recent. Een andere toegang tot C en bij de volgende toegang tot D, C wordt vervangen omdat het het blok was dat net voor D werd geopend enzovoort.
Pseudo-LRU (PLRU)bewerken
voor CPU-caches met grote associativiteit (over het algemeen >4 manieren) worden de implementatiekosten van LRU prohibitief. In veel CPU-caches is een schema dat bijna altijd een van de minst recent gebruikte items weggooit voldoende, dus veel CPU-ontwerpers kiezen voor een PLRU-algoritme dat slechts één bit per cache-item nodig heeft om te werken.PLRU heeft doorgaans een iets slechtere miss-ratio, een iets betere latentie, gebruikt iets minder vermogen dan HOOFDSPOORWEGONDERNEMING en lagere overheadkosten in vergelijking met HOOFDSPOORWEGONDERNEMING.
het volgende voorbeeld laat zien hoe Bits werken als een binaire boom van 1-bit pointers die verwijzen naar de minder recent gebruikte subboom. Het volgen van de wijzerketen naar de bladknoop identificeert de vervangende kandidaat. Bij een toegang worden alle aanwijzers in de keten van het bladknooppunt van de toegangsweg naar het wortelknooppunt ingesteld om te wijzen naar een subtree die de toegangsweg niet bevat.
De toegangsvolgorde is een B C D E.
het principe is hier eenvoudig te begrijpen als we alleen naar de pijlwijzers kijken. Als er een toegang is tot een waarde, zeg dan ‘A’, en we kunnen het niet vinden in de cache, dan laden we het uit het geheugen en plaatsen het op het blok waar de pijlen op dit moment wijzen, gaande van boven naar beneden. Nadat we dat blok hebben geplaatst draaien we dezelfde pijlen zodat ze de tegenovergestelde kant op wijzen. In het bovenstaande voorbeeld zien we hoe ‘A’ werd geplaatst, gevolgd door ‘B’, ‘C en ‘D’. Toen de cache vol werd verving ‘E’ ‘A’ omdat daar de pijlen op dat moment naar Wijzen, en de pijlen die naar ‘ A ‘ leidden werden omgedraaid om in de tegenovergestelde richting te wijzen. De pijlen leidden vervolgens naar ‘B’, wat het blok zal worden vervangen op de volgende cache miss.
willekeurige vervanging (RR)bewerken
selecteert willekeurig een kandidaat-item en gooit het weg om ruimte te maken indien nodig. Dit algoritme vereist geen informatie over de toegangsgeschiedenis. Voor zijn eenvoud, het is gebruikt in ARM processors. Het geeft efficiënte stochastische simulatie toe.
De toegangsvolgorde voor het onderstaande voorbeeld is een B C D E B D F
gesegmenteerde LRU (SLRU)bewerken
SLRU cache is verdeeld in twee segmenten, een proefsegment en een beschermd segment. Lijnen in elk segment worden geordend van het meest naar het minst recent toegankelijk. Gegevens van missers worden toegevoegd aan de cache aan het meest recent geopende einde van het proefsegment. Hits worden verwijderd van waar ze zich momenteel bevinden en toegevoegd aan het meest recent geopende einde van het beveiligde segment. Lijnen in het beschermde segment zijn dus ten minste tweemaal benaderd. Het beschermde segment is eindig, zodat de migratie van een lijn van het proefsegment naar het beschermde segment de migratie van de HOOFDSPOORWEGONDERNEMING in het beschermde segment naar het meest recent gebruikte (MRU) einde van het proefsegment kan dwingen, waardoor deze lijn nog een kans krijgt om te worden benaderd alvorens te worden vervangen. De maximale grootte van het beschermde segment is een SLRU parameter die varieert afhankelijk van de I/O werkbelasting patronen. Wanneer gegevens uit de cache moeten worden verwijderd, worden lijnen verkregen aan het einde van de HOOFDSPOORWEGONDERNEMING van het proefsegment.
Least-frequently used (LFU)Bewerk
telt hoe vaak een item nodig is. Degenen die het minst vaak worden gebruikt, worden eerst weggegooid. Dit werkt zeer vergelijkbaar met de HOOFDSPOORWEGONDERNEMING, behalve dat in plaats van het opslaan van de waarde van hoe recent een blok werd geopend, slaan we de waarde van hoe vaak het werd geopend. Dus natuurlijk tijdens het uitvoeren van een toegangsvolgorde zullen we een blok vervangen dat het minste aantal keren uit onze cache is gebruikt. Bijvoorbeeld, als A 5 keer werd gebruikt (geraadpleegd) en B 3 keer werd gebruikt en anderen C en D werden 10 keer gebruikt elk, zullen we vervangen B.
minst frequent recent gebruikt (LFRU)bewerken
het minst Frequent recent gebruikt (LFRU) cachevervangingsschema combineert de voordelen van lfu-en LRU-schema ‘ s. LFRU is geschikt voor’ in network ‘cache toepassingen, zoals informatie-centric networking (LIW), Content Delivery Networks (CDN’ s) en gedistribueerde netwerken in het algemeen. In LFRU is de cache verdeeld in twee partities genaamd geprivilegieerde en niet-geprivilegieerde partities. De geprivilegieerde partitie kan worden gedefinieerd als een beschermde partitie. Als inhoud zeer populair is, wordt deze in de geprivilegieerde partitie geduwd. Vervanging van de geprivilegieerde partitie gebeurt als volgt: lfru verwijdert inhoud uit de geprivilegieerde partitie, pusht inhoud van geprivilegieerde partitie naar geprivilegieerde partitie, en voegt uiteindelijk nieuwe inhoud in de geprivilegieerde partitie. In de bovenstaande procedure wordt de LRU gebruikt voor de geprivilegieerde partitie en wordt een benaderde LFU (ALFU) schema gebruikt voor de niet-geprivilegieerde partitie, vandaar de afkorting LFRU.
het basisidee is om de lokaal populaire inhoud uit te filteren met ALFU schema en de populaire inhoud naar een van de bevoorrechte partitie te pushen.
LFU met dynamische veroudering (LFUDA)Edit
een variant genaamd LFU met dynamische veroudering (LFUDA) die gebruik maakt van dynamische veroudering om verschuivingen in de reeks van populaire objecten tegemoet te komen. Het voegt een cache leeftijd factor aan de referentie telling wanneer een nieuw object wordt toegevoegd aan de cache of wanneer een bestaand object opnieuw wordt verwezen. LFUDA verhoogt de cache veroudert bij het uitzetten van blokken door deze in te stellen op de sleutelwaarde van het uitgezette object. De cache leeftijd is dus altijd kleiner dan of gelijk aan de minimale sleutelwaarde in de cache. Stel dat wanneer een object vaak werd benaderd in het verleden en nu wordt het impopulair, het zal blijven in de cache voor een lange tijd waardoor de nieuwe of minder populaire objecten te vervangen. Dus deze dynamische veroudering wordt geïntroduceerd om het aantal van dergelijke objecten te verlagen waardoor ze in aanmerking komen voor vervanging. Het voordeel van LFUDA is het vermindert de cache vervuiling veroorzaakt door LFU wanneer cache maten zijn zeer klein. Wanneer cachegroottes groot zijn, zijn weinig vervangingsbeslissingen voldoende en zal cachevervuiling geen probleem zijn.
Low inter-reference recentency set (LIRS)Edit
LIRS is een paginavervangingsalgoritme met verbeterde prestaties ten opzichte van LRU en vele andere nieuwere vervangingsalgoritmen. Dit wordt bereikt door hergebruikafstand te gebruiken als maatstaf voor dynamisch rangschikken van toegangspagina ‘ s om een vervangende beslissing te nemen. De LR ‘ s bieden een doeltreffende oplossing voor de grenswaarden van de HOOFDSPOORWEGONDERNEMING door de recentheid te gebruiken om de Interreferentie-recentheid (IRR) te evalueren voor het nemen van een vervangingsbesluit.
in de bovenstaande figuur geeft ” x ” aan dat een blok wordt benaderd op tijd t. Stel dat als blok A1 wordt benaderd op tijd 1 dan zal recentheid 0 worden omdat dit het eerste blok is en IRR zal 1 zijn omdat het voorspelt dat A1 opnieuw zal worden benaderd in tijd 3. In de tijd 2 sinds A4 wordt benaderd, zal de recentheid 0 worden voor A4 en 1 voor A1 omdat A4 het meest recent gebruikte Object is en IRR 4 wordt en het zal doorgaan. Op tijd 10 heeft het LIRS algoritme twee sets LIR set = {A1, A2} en HIR set = {A3, A4, A5}. Nu op tijd 10 als er toegang tot A4, miss optreedt. LIRS algoritme zal nu verwijderen A5 in plaats van A2 vanwege de grootste recente.
CLOCK-ProEdit
LRU-algoritme kan niet direct worden geïmplementeerd in het kritieke pad van computersystemen, zoals besturingssystemen, vanwege de hoge overhead. Een benadering van de HOOFDSPOORWEGONDERNEMING, genaamd klok, wordt vaak gebruikt voor de implementatie. Ook CLOCK-Pro is een benadering van LIRS voor een lage kosten implementatie in systemen. CLOCK-Pro is onder de basis klok kader, maar heeft drie belangrijke verschillende verdiensten. Ten eerste heeft CLOCK-Pro drie “wijzers” in tegenstelling tot een eenvoudige structuur van de klok waar slechts één “wijzer” wordt gebruikt. Met de drie wijzers is CLOCK-Pro in staat om de hergebruikafstand van data-toegangen bij benadering te meten. In de tweede plaats blijven alle voordelen van RGB ‘ s behouden, zoals het snel verwijderen van eenmalige toegang en/of low locality-gegevensposten. Ten derde is de complexiteit van de CLOCK-Pro hetzelfde als die van de klok, dus het is gemakkelijk te implementeren tegen lage kosten. De buffer cache vervanging implementatie in de huidige versie van Linux is een combinatie van LRU en CLOCK-Pro.
adaptive replacement cache (ARC)bewerken
balanceert constant tussen LRU en LFU, om het gecombineerde resultaat te verbeteren. ARC verbetert SLRU door informatie te gebruiken over recent verwijderde cache-items om dynamisch de grootte van het beschermde segment en het proefsegment aan te passen om zo optimaal mogelijk gebruik te maken van de beschikbare cacheruimte. Adaptief vervangingsalgoritme wordt uitgelegd met het voorbeeld.
AdaptiveClimb (AC)Edit
gebruikt recente hit/miss om de sprong aan te passen waar in climb een hit de positie één sleuf naar boven schakelt, en in LRU hit de positie van de hit naar boven schakelt. Zo profiteren zij van de optimaliteit van de klim wanneer het programma zich in een vaste scope bevindt, en van de snelle aanpassing aan een nieuwe scope, zoals de HOOFDSPOORWEGONDERNEMING dat doet. Ook ondersteuning cache delen tussen kernen door het vrijgeven van extra ‘ s wanneer de referenties zijn naar het bovenste deel van de cache.
Klok Met adaptieve vervanging (CAR)bewerken
combineert de voordelen van adaptieve Vervangende Cache (ARC) en klok. Auto heeft prestaties vergelijkbaar met ARC, en aanzienlijk overtreft zowel LRU en klok. Net als ARC, auto is self-tuning en vereist geen door de gebruiker opgegeven magische parameters. Het maakt gebruik van 4 dubbel gelinkte lijsten: twee klokken T1 en T2 en twee eenvoudige LRU lijsten B1 en B2. T1 klok slaat pagina ‘ s op op basis van “recent” of “short term utility” terwijl T2 pagina ‘ s opslaat met “frequency” of “long term utility”. T1 en T2 bevatten de pagina ’s die zich in de cache bevinden, terwijl B1 en B2 pagina’ s bevatten die onlangs uit respectievelijk T1 en T2 zijn verwijderd. Het algoritme probeert de grootte van deze lijsten B1≈T2 en B2≈T1 te behouden. Nieuwe pagina ‘ s worden ingevoegd in T1 of T2. Als er een hit in B1 grootte van T1 wordt verhoogd en op dezelfde manier als er een hit in B2 grootte van T1 wordt verlaagd. De gebruikte aanpassingsregel heeft hetzelfde principe als dat in ARC, meer investeren in lijsten die meer hits zal geven wanneer meer pagina ‘ s worden toegevoegd.
Multi queue (mq)Edit
het multi queue algoritme of MQ werd ontwikkeld om de prestaties van tweede niveau buffer cache voor bijvoorbeeld een server buffer cache te verbeteren. Het is geïntroduceerd in een paper door Zhou, Philbin, en Li. de mq cache bevat een M aantal LRU wachtrijen: Q0, Q1,…, Qm-1. Hier vertegenwoordigt de waarde van m een hiërarchie gebaseerd op de levensduur van alle blokken in die specifieke wachtrij. Bijvoorbeeld, als j>i, zullen blokken in Qj een langere levensduur hebben dan die in Qi. Naast deze is er nog een geschiedenis buffer Qout, een wachtrij die een lijst van alle blok-ID ‘ s bijhoudt samen met hun toegangsfrequenties. Wanneer Qout vol is, wordt de oudste identifier uitgezet. Blokken blijven gedurende een bepaalde levensduur in de LRU-wachtrij, die dynamisch wordt gedefinieerd door het mq-algoritme als de maximale tijdsafstand tussen twee toegangen tot hetzelfde bestand of het aantal cacheblokken, afhankelijk van wat groter is. Als er niet naar een blok is verwezen tijdens zijn levensduur, wordt het gedegradeerd van Qi naar Qi−1 of verwijderd uit de cache als het in Q0 staat. Elke wachtrij heeft ook een maximum aantal Toegang; als een blok in wachtrij Qi meer dan 2i keer wordt geopend, wordt dit blok gepromoveerd naar Qi+1 totdat het meer dan 2i+1 keer wordt geopend of de levensduur ervan verloopt. Binnen een bepaalde wachtrij worden de blokken volgens de HOOFDSPOORWEGONDERNEMING gerangschikt op basis van de recentheid van de toegang.
We kunnen zien uit Fig. hoe de M LRU wachtrijen in de cache worden geplaatst. Zie ook uit Fig. hoe de Qout De block identifiers en hun bijbehorende toegangsfrequenties opslaat. a werd geplaatst in Q0 omdat het slechts een keer onlangs werd benaderd en we kunnen in Qout controleren hoe b en c werden geplaatst in Q1 en Q2 respectievelijk als hun toegang frequenties zijn 2 en 4. De wachtrij waarin een blok wordt geplaatst is afhankelijk van de toegangsfrequentie(f) als log2 (f). Als de cache vol is, zal het eerste blok dat wordt uitgezet het hoofd van Q0 zijn in dit geval a. als a nog een keer wordt benaderd, zal het naar Q1 onder b gaan.
Pannier: Container-based caching algorithm for compound objectsEdit
Pannier is een container-based flash caching mechanisme dat divergente (heterogene) containers identificeert waar blokken die daarin worden gehouden sterk variërende toegangspatronen hebben. Pannier gebruikt een priority-queue gebaseerde survival queue structuur om de containers te rangschikken op basis van hun overlevingstijd, die evenredig is met de live data in de container. Pannier is gebouwd op basis van gesegmenteerde LRU (S2LRU), die warme en koude gegevens scheidt. Pannier maakt ook gebruik van een multi-step feedback controller om flits schrijven te throttlen om de levensduur van de flits te garanderen.