B Uscl Uscardi ’ s algorithmEdit
den mest effektiva cachningsalgoritmen skulle vara att alltid kasta bort den information som inte kommer att behövas under den längsta tiden i framtiden. Detta optimala resultat benämns B. O. C. O. C. S. optimala algoritm / simply optimal replacement policy eller den klärvoajanta algoritmen. Eftersom det i allmänhet är omöjligt att förutsäga hur långt i framtiden information kommer att behövas, är detta i allmänhet inte genomförbart i praktiken. Det praktiska minimumet kan beräknas först efter experiment, och man kan jämföra effektiviteten hos den faktiskt valda cachealgoritmen.
i det ögonblick då ett sidfel inträffar finns en del sidor i minnet. I exemplet är sekvensen av ’5’, ’0’, ’1’ nås av RAM 1, ram 2, Ram 3 respektive. Sedan när ’2’ nås ersätter det värdet ’5’, vilket är i RAM 1 eftersom det förutspår att värdet ’ 5 ’ inte kommer att nås inom en snar framtid. Eftersom ett verkligt operativsystem för allmänna ändamål faktiskt inte kan förutsäga när ’5’ kommer att nås, kan b exceptional inte implementeras på ett sådant system.
först in först ut (FIFO)redigera
med denna algoritm cachen beter sig på samma sätt som en FIFO kö. Cachen avlägsnar blocken i den ordning de Lades till, utan hänsyn till hur ofta eller hur många gånger de öppnades tidigare.
Last in first out (LIFO) eller First in last out (FILO)redigera
med hjälp av denna algoritm cachen beter sig på samma sätt som en stack och exakt motsatt sätt som en FIFO kö. Cachen avlägsnar blocket som lagts till senast först utan hänsyn till hur ofta eller hur många gånger det öppnades tidigare.
minst nyligen använda (LRU)redigera
kasserar de minst nyligen använda objekten först. Denna algoritm kräver att hålla reda på vad som användes när, vilket är dyrt om man vill se till att algoritmen alltid kasserar det minst nyligen använda objektet. Allmänna implementeringar av denna teknik kräver att man behåller ” åldersbitar ”för cache-linjer och spårar den” minst nyligen använda ” cache-linjen baserat på åldersbitar. I en sådan implementering ändras åldern för alla andra cache-linjer varje gång en cache-linje används. LRU är faktiskt en familj av cachningsalgoritmer med medlemmar inklusive 2Q av Theodore Johnson och Dennis Shasha, och LRU/K av Pat O ’Neil, Betty O’ Neil och Gerhard Weikum.
åtkomstsekvensen för exemplet nedan är A B C D E D F.
i exemplet ovan när en B C D installeras i blocken med sekvensnummer (Steg 1 för varje ny åtkomst) och när E nås är det en miss och den måste installeras i ett av blocken. Enligt LRU-algoritmen, eftersom A har den lägsta rankningen(a(0)), kommer E att ersätta A.
i det näst sista steget nås D och därför uppdateras sekvensnumret.
LRU, som många andra ersättningspolicyer, kan karakteriseras med hjälp av ett tillståndsövergångsfält i ett vektorutrymme, vilket bestämmer de dynamiska cache-tillståndsförändringarna som liknar hur ett elektromagnetiskt fält bestämmer rörelsen för en laddad partikel placerad i den.
Time aware minst nyligen använda (TLRU)redigera
Time aware minst nyligen använda (TLRU) är en variant av LRU utformad för den situation där det lagrade innehållet i cachen har en giltig livstid. Algoritmen är lämplig i nätverkscache-applikationer, såsom INFORMATIONSCENTRERAT nätverk (ICN), innehållsleveransnätverk (CDN) och distribuerade nätverk i allmänhet. TLRU introducerar en ny term: TTU (tid att använda). TTU är en tidsstämpel för ett innehåll / sida som anger användbarhetstiden för innehållet baserat på innehållets ort och innehållsutgivarens meddelande. På grund av denna lokalitetsbaserade tidsstämpel ger TTU mer kontroll till den lokala administratören att reglera i nätverkslagring.I tlru-algoritmen, när en del av innehållet anländer, beräknar en cache-nod det lokala ttu-värdet baserat på ttu-värdet som tilldelats av innehållsutgivaren. Det lokala ttu-värdet beräknas med hjälp av en lokalt definierad funktion. När det lokala ttu-värdet har beräknats utförs utbyte av innehåll på en delmängd av det totala innehållet som lagras i cache-noden. TLRU säkerställer att mindre populärt och litet livsinnehåll ska ersättas med det inkommande innehållet.
senast använda (MRU)redigera
kasserar, i motsats till LRU, de senast använda objekten först. I fynd som presenterades vid den 11: e vldb-konferensen noterade Chou och DeWitt att ”när en fil skannas upprepade gånger i ett referensmönster är MRU den bästa ersättningsalgoritmen.”Därefter noterade andra forskare som presenterade vid den 22: e vldb-konferensen att för slumpmässiga åtkomstmönster och upprepade skanningar över stora dataset (ibland kända som cykliska åtkomstmönster) har MRU-cachealgoritmer fler träffar än LRU på grund av deras tendens att behålla äldre data. MRU algoritmer är mest användbara i situationer där äldre ett objekt är, desto mer sannolikt är det att nås.
åtkomstsekvensen för exemplet nedan är A B C D E C D B.
Här placeras A B C D i cachen eftersom det fortfarande finns utrymme tillgängligt. Vid 5: e åtkomst E ser vi att blocket som höll D nu ersätts med E eftersom detta block användes senast. En annan åtkomst till C och vid nästa åtkomst till D, C ersätts eftersom det var blocket som nås strax före D och så vidare.
Pseudo – LRU (PLRU)redigera
för CPU-cachar med stor associativitet (i allmänhet >4 sätt) blir implementeringskostnaden för LRU oöverkomlig. I många CPU-cachar är ett schema som nästan alltid kasserar en av de minst nyligen använda objekten tillräckligt, så många CPU-designers väljer en PLRU-algoritm som bara behöver en bit per cacheobjekt för att fungera.PLRU har vanligtvis ett något sämre missförhållande, har en något bättre latens, använder något mindre effekt än LRU och lägre omkostnader jämfört med LRU.
följande exempel visar hur bitar fungerar som ett binärt träd med 1-bitars pekare som pekar på det mindre nyligen använda underträdet. Efter pekarkedjan till bladnoden identifieras ersättningskandidaten. Vid en åtkomst ställs alla pekare i kedjan från det åtkomliga sättets bladnod till rotnoden in för att peka på underträd som inte innehåller det åtkomliga sättet.
åtkomstsekvensen är A B C D E.
principen här är enkel att förstå om vi bara tittar på pilpekarna. När det finns tillgång till ett värde, säg ’A’, och vi kan inte hitta det i cachen, laddar vi det från minnet och placerar det i blocket där pilarna för närvarande pekar, går från topp till botten. När vi har placerat det blocket vänder vi samma pilar så att de pekar motsatt sätt. I exemplet ovan ser vi hur’ A ’placerades, följt av’ B’, ’C och’D’. Sedan som cachen blev full ’ e ’ersatt’ A ’ eftersom det var där pilarna pekade på den tiden, och pilarna som ledde till ’A’ vändes för att peka i motsatt riktning. Pilarna ledde sedan till ’B’, som kommer att vara blocket ersättas på nästa cache miss.
Random replacement (rr)Edit
väljer slumpmässigt ett kandidatobjekt och kasserar det för att göra plats vid behov. Denna algoritm kräver inte att du behåller någon information om åtkomsthistoriken. För sin enkelhet har den använts i ARM-processorer. Det medger effektiv stokastisk simulering.
åtkomstsekvensen för exemplet nedan är en B C D E B D F
segmenterad LRU (SLRU)redigera
SLRU-cache är uppdelad i två segment, ett provsegment och ett skyddat segment. Linjer i varje segment beställs från de mest till de minst nyligen åtkomliga. Data från missar läggs till i cachen vid det senast åtkomliga slutet av provsegmentet. Träffar tas bort från var de för närvarande bor och läggs till i den senast åtkomna änden av det skyddade segmentet. Linjer i det skyddade segmentet har således nås minst två gånger. Det skyddade segmentet är ändligt, så migrering av en linje från provsegmentet till det skyddade segmentet kan tvinga migreringen av LRU-linjen i det skyddade segmentet till det senast använda (MRU) slutet av provsegmentet, vilket ger denna linje ytterligare en chans att nås innan den byts ut. Storleksgränsen för det skyddade segmentet är en SLRU-parameter som varierar beroende på I / O-arbetsbelastningsmönstren. När data måste kasseras från cachen erhålls linjer från LRU-änden av provsegmentet.
minst använda (LFU)redigera
räknar hur ofta ett objekt behövs. De som används minst ofta kasseras först. Detta fungerar mycket lik LRU förutom att istället för att lagra värdet på hur nyligen ett block öppnades, lagrar vi värdet på hur många gånger det öppnades. Så naturligtvis när du kör en åtkomstsekvens kommer vi att ersätta ett block som användes minst gånger från vår cache. T. ex., om A användes (nås) 5 gånger och B användes 3 gånger och andra C och D användes 10 gånger vardera, kommer vi att ersätta B.
minst frekventa nyligen använda (LFRU)redigera
den minst frekventa nyligen använda (LFRU) cache ersättningsschema kombinerar fördelarna med lfu och LRU-system. LFRU är lämplig för’ i nätverk ’ cache-applikationer, såsom INFORMATIONSCENTRERADE nätverk (ICN), Content Delivery Networks (CDN) och distribuerade nätverk i allmänhet. I LFRU är cachen uppdelad i två partitioner som kallas privilegierade och oprivilegierade partitioner. Den privilegierade partitionen kan definieras som en skyddad partition. Om innehållet är mycket populärt skjuts det in i den privilegierade partitionen. Byte av den privilegierade partitionen görs enligt följande: LFRU avlägsnar innehåll från den oprivilegierade partitionen, skjuter innehåll från privilegierad partition till oprivilegierad partition och lägger slutligen in nytt innehåll i den privilegierade partitionen. I ovanstående procedur används LRU för den privilegierade partitionen och ett approximerat lfu (ALFU) – schema används för den oprivilegierade partitionen, därav förkortningen LFRU.
Grundtanken är att filtrera bort det lokalt populära innehållet med ALFU-schema och driva det populära innehållet till en av de privilegierade partitionerna.
LFU med dynamisk åldrande (LFUDA)redigera
en variant som heter LFU med dynamisk åldrande (LFUDA) som använder dynamisk åldrande för att rymma skift i uppsättningen populära objekt. Det lägger till en cache – åldersfaktor i referensräkningen när ett nytt objekt läggs till i cachen eller när ett befintligt objekt refereras igen. LFUDA ökar cachen åldrar när vräka block genom att ställa in den till vräkta objektets nyckelvärde. Således är cacheåldern alltid mindre än eller lika med det minsta nyckelvärdet i cachen. Antag att när ett objekt ofta nås tidigare och nu blir det impopulärt, kommer det att förbli i cachen under lång tid och därigenom förhindra att de nyligen eller mindre populära objekten ersätter det. Så denna dynamiska åldrande introduceras för att få ner räkningen av sådana objekt vilket gör dem berättigade till ersättning. Fördelen med LFUDA är att det minskar cache föroreningar som orsakas av LFU när cache storlekar är mycket små. När Cache storlekar är stora några ersättningsbeslut är tillräckliga och cache föroreningar kommer inte att vara ett problem.
låg interreferens recency set (LIRS)redigera
LIRS är en sida ersättningsalgoritm med en förbättrad prestanda över LRU och många andra nyare ersättningsalgoritmer. Detta uppnås genom att använda återanvändningsavstånd som ett mått för att dynamiskt rangordna åtkomna sidor för att fatta ett ersättningsbeslut. LIRS adresserar effektivt gränserna för LRU genom att använda recency för att utvärdera Inter-Reference Recency (IRR) för att fatta ett ersättningsbeslut.
i ovanstående figur representerar ” x ” att ett block nås vid tiden t. Antag att om block A1 nås vid tiden 1 blir Recency 0 eftersom detta är det första åtkomstblocket och IRR blir 1 eftersom det förutspår att A1 kommer att nås igen i tid 3. I tiden 2 sedan A4 nås blir recency 0 för A4 och 1 för A1 eftersom A4 är det senast åtkomna objektet och IRR blir 4 och det kommer att fortsätta. Vid tiden 10 kommer lirs-algoritmen att ha två uppsättningar LIR set = {A1, A2} och HIR set = {A3, A4, A5}. Nu vid tiden 10 om det finns tillgång till A4, miss inträffar. LIRS-algoritmen kommer nu att vräka A5 istället för A2 på grund av sin största nyhet.
CLOCK-ProEdit
LRU-algoritmen kan inte implementeras direkt i den kritiska vägen för datorsystem, till exempel operativsystem, på grund av dess höga kostnader. En approximation av LRU, kallad klocka används ofta för genomförandet. På samma sätt är CLOCK-Pro en approximation av LIRS för en billig implementering i system. CLOCK-Pro är under den grundläggande KLOCKRAMEN, men har tre stora distinkta meriter. För det första har CLOCK-Pro tre ”klockhänder” i motsats till en enkel klockstruktur där endast en ”hand” används. Med de tre händerna kan CLOCK-Pro mäta återanvändningsavståndet för dataåtkomst på ett ungefärligt sätt. För det andra behålls alla fördelar med LIRS, till exempel att snabbt avlägsna engångsåtkomst och/eller dataobjekt med låg lokalitet. För det tredje är komplexiteten i CLOCK-Pro samma som klockan, så det är lätt att genomföra till en låg kostnad. Implementeringen av buffertcachebyte i den nuvarande versionen av Linux är en kombination av LRU och CLOCK-Pro.
adaptiv ersättningscache (ARC)redigera
balanserar ständigt mellan LRU och LFU, för att förbättra det kombinerade resultatet. ARC förbättras på SLRU genom att använda information om nyligen vräkta cacheobjekt för att dynamiskt justera storleken på det skyddade segmentet och provsegmentet för att utnyttja det tillgängliga cacheutrymmet på bästa sätt. Adaptiv ersättningsalgoritm förklaras med exemplet.
AdaptiveClimb (AC)Edit
använder senaste hit/miss för att justera hoppet där i klättra någon träff växlar positionen en slits till toppen, och i LRU hit växlar positionen för träffen till toppen. Således drar nytta av klättringens optimalitet när programmet är i ett fast omfång och den snabba anpassningen till ett nytt omfång, som LRU gör. Stöder också cachedelning mellan kärnor genom att släppa extra när referenserna är till den övre delen av cachen.
klocka med adaptiv ersättning (bil)redigera
kombinerar fördelarna med adaptiv ersättning Cache (ARC) och klocka. Bilen har prestanda jämförbar med ARC, och överträffar väsentligt både LRU och klocka. Liksom ARC är bilen självinställd och kräver inga användardefinierade magiska parametrar. Den använder 4 dubbelt länkade listor: Två klockor T1 och T2 och två enkla LRU listor B1 och B2. T1 clock lagrar sidor baserade på” recency ”eller” short term utility ”medan T2 lagrar sidor med” frequency ”eller”long term utility”. T1 och T2 innehåller de sidor som finns i cachen, medan B1 och B2 innehåller sidor som nyligen har kastats ut från T1 respektive T2. Algoritmen försöker att behålla storleken på dessa listor B1 msk T2 och B2 msk T1. Nya sidor infogas i T1 eller T2. Om det finns en träff i B1 storlek T1 ökas och på samma sätt om det finns en träff i B2 storlek T1 minskas. Anpassningsregeln som används har samma princip som i ARC, investera mer i listor som ger fler träffar när fler sidor läggs till.
Multi queue (mq)redigera
Multi queue-algoritmen eller MQ utvecklades för att förbättra prestandan för buffertcache på andra nivån för t.ex. en serverbuffertcache. Det introduceras i ett papper av Zhou, Philbin och Li. mq-cachen innehåller ett m-antal LRU-köer: Q0, Q1, …, Qm-1. Här representerar värdet på m en hierarki baserad på livslängden för alla block i den specifika kön. Till exempel, om j>i, kommer block i Qj att ha en längre livslängd än de i Qi. Utöver dessa finns det en annan historikbuffert Qout, en kö som upprätthåller en lista över alla Blockidentifierare tillsammans med deras åtkomstfrekvenser. När Qout är full vräks den äldsta identifieraren. Block stannar i LRU-köerna under en viss livstid, vilket definieras dynamiskt av MQ-algoritmen för att vara det maximala temporära avståndet mellan två åtkomst till samma fil eller antalet cache-block, beroende på vilket som är större. Om ett block inte har refererats inom sin livstid, degraderas det från Qi till Qi-1 eller kastas ut från cachen om det är i Q0. Varje kö har också ett maximalt antal åtkomst; om ett block i kö Qi nås mer än 2i gånger, främjas detta block till Qi+1 tills det nås mer än 2i+1 gånger eller dess livstid löper ut. Inom en given kö rangordnas block efter senaste åtkomst, enligt LRU.
Vi kan se från Fig. hur m LRU-köerna placeras i cachen. Se även från Fig. hur Qout lagrar blockidentifierarna och deras motsvarande åtkomstfrekvenser. a placerades i Q0 eftersom den endast öppnades en gång nyligen och vi kan checka in Qout hur b och c placerades i Q1 respektive Q2 eftersom deras åtkomstfrekvenser är 2 och 4. Kön där ett block placeras är beroende av åtkomstfrekvens (f) som log2(f). När cachen är full kommer det första blocket som ska kastas ut att vara chefen för Q0 i detta fall a. Om a nås en gång till kommer det att flytta till Q1 under b.
Pannier: Containerbaserad cachningsalgoritm för sammansatta objektredigera
Pannier är en containerbaserad flashcachningsmekanism som identifierar divergerande (heterogena) behållare där block som hålls däri har mycket varierande åtkomstmönster. Pannier använder en prioritetsköbaserad överlevnadskönstruktur för att rangordna behållarna baserat på deras överlevnadstid, vilket är proportionellt mot live-data i behållaren. Pannier är byggt baserat på segmenterad LRU (S2LRU), som segregerar heta och kalla data. Pannier använder också en flerstegs feedback controller för att strypa flash skriver att säkerställa flash livslängd.