Cachingalgoritmer ( preemption algorithms , preemption policys och "replacement algorithms/policys") - inom datavetenskap är detta instruktionsoptimering : ett speciellt datorprogram eller hårdvarustödd struktur som kan hantera cachen för information som lagras i en dator. När cachen är full måste algoritmen välja exakt vad som ska tas bort från den för att kunna skriva (till cachen) ny, mer uppdaterad information. Hårdvaruimplementeringen av dessa algoritmer involverar användningen av en timer , räknare eller en kombination av båda.
"Träffhastigheten" i cachen syftar på hur ofta data du letar efter finns i cachen. Effektivare vräkningspolicyer håller reda på åtkomst till den mest använda informationen för att förbättra träfffrekvensen (för samma cachestorlek).
Cache "latency" hänvisar till hur snabbt cachen kan returnera den begärda datan direkt efter begäran (i händelse av att en "träff" inträffar). Snabbare vräkningsstrategier håller vanligtvis reda på den minst använda informationen – eller, i fallet med en direktmappad cache, bristen på information – för att minska den tid det tar att uppdatera informationen.
Varje förskjutningsstrategi är en kompromiss mellan träffhastighet och latens.
Den mest effektiva vräkningsregeln är att kassera information från cachen som inte kommer att behövas längst i framtiden. Denna optimala cachningsalgoritm har kallats Beladi- algoritmen eller framsynsalgoritmen . Eftersom det i det allmänna fallet är omöjligt att förutsäga när exakt denna information kommer att behövas nästa gång, är i praktiken (igen, i det allmänna fallet) en sådan implementering omöjlig. Det praktiska minimumet kan endast beräknas empiriskt, varefter effektiviteten hos den aktuella cachningsalgoritmen kan jämföras med den.
Minst nyligen använd (LRU): Först och främst är den längsta oanvända förskjuten. Denna algoritm kräver att man håller reda på vad som användes och när, vilket kan vara ganska dyrt, speciellt om du behöver göra ytterligare verifiering för att vara säker. Den allmänna implementeringen av denna metod kräver att man håller en "åldersbit" för cache-rader, och genom att göra det håller man reda på de minst använda raderna (det vill säga genom att jämföra sådana bitar). I en sådan implementering ändras "åldern" för alla andra rader varje gång en cache-rad nås. LRU är faktiskt en familj av cachningsalgoritmer som inkluderar 2Q av Theodore Johnson och Dennis Schasha, och LRU/K av Pat O'Neill, Betty O'Neill och Gerhard Weikum.
Most Recently Used (MRU): Till skillnad från LRU, vräkas det senast använda föremålet först. Enligt källan [1] , "När en fil periodiskt skannas på ett round robin-sätt är MRU den bästa vräkningsalgoritmen." I [2] betonar författarna också att för slumpmässiga åtkomstscheman och cyklisk skanning av stora datamängder (ibland kallade round robin-scheman) har MRU-cachingalgoritmer fler träffar jämfört med LRU på grund av deras tendens att bevara gamla data. MRU-algoritmer är mest användbara i fall där ju äldre element, desto fler åtkomster till det sker.
Pseudo-LRU (PLRU): För cacher med stor associativitet (vanligtvis fler än 4 kanaler) blir de nödvändiga resurserna för att implementera LRU för stora. Om policyn är tillräcklig för att nästan alltid förkasta den minst använda posten, kan PLRU-algoritmen användas i detta fall, vilket kräver endast en bit per cache-post.
Segmenterad LRU (eller SLRU): "SLRU-cachen är uppdelad i två segment: ett testsegment och ett skyddat segment. Raderna i varje segment är ordnade från mest använda till minst använda. Data om missar läggs till i cachen och i området för de senast använda elementen i testsegmentet. Data om träffar tas bort var den än befinner sig och läggs till området för ofta använda delar av det skyddade segmentet. Skyddade segmentrader nås alltså minst två gånger. Det skyddade segmentet är begränsat. En sådan linjeöverföring från försökssegmentet till det skyddade segmentet kan orsaka att den senast använda (LRU) raden i det skyddade segmentet överförs till MRU-området i försökssegmentet, vilket ger den linjen en andra chans att användas innan den används vräkts. Den skyddade segmentstorleken är en SLRU-parameter som varierar beroende på I/O-schemat. Närhelst data behöver kastas bort från cachen, begärs rader från LRU-änden av sondsegmentet. [3] »
2-vägs associativitet gäller för höghastighetsprocessorcacher , där även PLRU är för långsam . Adressen till det nya elementet används för att beräkna en av två möjliga platser i cachen (i det område som tilldelats för detta). Enligt LRU-algoritmen är två element förskjutna. Det kräver en bit för ett par cache-rader för att ange vilka som senast användes.
Direct Mapped Cache : För höghastighetsprocessorcacher där prestanda för associativ 2-vägs cache saknas. Adressen till det nya elementet används för att beräkna platsen i cachen (i det område som tilldelats för detta). Allt som var tidigare byts ut.
Minst ofta använda (LFU): LFU räknar hur ofta ett element används. De element som nås minst ofta föregrips först.
Adaptive Replacement Cache (ARC): [4] balanserar hela tiden mellan LRU och LFU, vilket förbättrar slutresultatet.
Multi Queue (MQ) cachingalgoritm : [5] (utvecklad av Y. Zhu, J.F. Philbin och Kai Li).
Följande punkter beaktas:
Det finns också olika algoritmer för att säkerställa cache-koherens . Detta gäller endast i de fall där flera oberoende cachar används för att lagra samma information (till exempel flera databasservrar uppdaterar en gemensam datafil).