Bélády’s algorithmEdit
Der effizienteste Caching-Algorithmus wäre, immer die Informationen zu verwerfen, die für die längste Zeit in der Zukunft nicht benötigt werden. Dieses optimale Ergebnis wird als Béládys optimaler Algorithmus / einfach optimale Ersatzpolitik oder hellseherischer Algorithmus bezeichnet. Da in der Regel nicht vorhergesagt werden kann, wie weit in der Zukunft Informationen benötigt werden, ist dies in der Praxis in der Regel nicht umsetzbar. Das praktische Minimum kann erst nach Experimenten berechnet werden, und man kann die Wirksamkeit des tatsächlich gewählten Cache-Algorithmus vergleichen.
In dem Moment, in dem ein Seitenfehler auftritt, befinden sich einige Seiten im Speicher. Im Beispiel wird die Sequenz von ‚5‘, ‚0‘, ‚1‘ auf Frame 1, Frame 2, Frame 3 zugegriffen wird. Wenn dann auf ‚2‘ zugegriffen wird, wird der Wert ‚5‘ ersetzt, der sich in Frame 1 befindet, da vorhergesagt wird, dass in naher Zukunft nicht auf den Wert ‚5‘ zugegriffen wird. Da ein echtes Allzweck-Betriebssystem nicht vorhersagen kann, wann auf ‚5‘ zugegriffen wird, kann der Algorithmus von Bélády auf einem solchen System nicht implementiert werden.
First in first out (FIFO)Bearbeiten
Mit diesem Algorithmus verhält sich der Cache wie eine FIFO-Warteschlange. Der Cache räumt die Blöcke in der Reihenfolge, in der sie hinzugefügt wurden, ohne Rücksicht darauf, wie oft oder wie oft zuvor auf sie zugegriffen wurde.
Last in first out (LIFO) oder First in last out (FILO)Bearbeiten
Mit diesem Algorithmus verhält sich der Cache genauso wie ein Stapel und genau umgekehrt wie eine FIFO-Warteschlange. Der Cache räumt den zuletzt hinzugefügten Block zuerst, ohne Rücksicht darauf, wie oft oder wie oft zuvor darauf zugegriffen wurde.
Least recently used (LRU)Edit
Verwirft zuerst die zuletzt verwendeten Elemente. Dieser Algorithmus erfordert den Überblick darüber, was wann verwendet wurde, was teuer ist, wenn man sicherstellen möchte, dass der Algorithmus immer das zuletzt verwendete Element verwirft. Allgemeine Implementierungen dieser Technik erfordern das Beibehalten von „Altersbits“ für Cache-Zeilen und das Verfolgen der „Zuletzt verwendeten“ Cache-Zeile basierend auf Altersbits. Bei einer solchen Implementierung ändert sich jedes Mal, wenn eine Cache-Zeile verwendet wird, das Alter aller anderen Cache-Zeilen. LRU ist eigentlich eine Familie von Caching-Algorithmen mit Mitgliedern wie 2Q von Theodore Johnson und Dennis Shasha und LRU / K von Pat O’Neil, Betty O’Neil und Gerhard Weikum.
Die Zugriffssequenz für das folgende Beispiel ist A B C D E D F.
Im obigen Beispiel, sobald ABC in den Blöcken mit Sequenznummern installiert wird (Inkrement 1 für jeden neuen Zugriff) und wenn auf E zugegriffen wird, ist es ein Fehler und muss in einem der Blöcke installiert werden. Gemäß dem LRU-Algorithmus ersetzt E, da A den niedrigsten Rang (A(0)) hat, A.
Im vorletzten Schritt wird auf D zugegriffen und daher die Sequenznummer aktualisiert.
LRU kann, wie viele andere Ersatzpolitiken, durch ein Zustandsübergangsfeld in einem Vektorraum charakterisiert werden, das die dynamischen Cache-Zustandsänderungen bestimmt, ähnlich wie ein elektromagnetisches Feld die Bewegung eines darin platzierten geladenen Teilchens bestimmt.
Time aware Least recently used (TLRU)Bearbeiten
Die Time aware Least Recently Used (TLRU) ist eine Variante von LRU, die für die Situation entwickelt wurde, in der der gespeicherte Inhalt im Cache eine gültige Lebensdauer hat. Der Algorithmus eignet sich für Netzwerk-Cache-Anwendungen wie informationszentrierte Netzwerke (ICN), Content Delivery Networks (CDNs) und verteilte Netzwerke im Allgemeinen. TLRU führt einen neuen Begriff ein: TTU (Time to Use). TTU ist ein Zeitstempel eines Inhalts / einer Seite, der die Usability-Zeit für den Inhalt basierend auf dem Ort des Inhalts und der Ankündigung des Inhaltsherausgebers festlegt. Aufgrund dieses lokalitätsbasierten Zeitstempels bietet TTU dem lokalen Administrator mehr Kontrolle über die Regulierung des Netzwerkspeichers.Im TLRU-Algorithmus berechnet ein Cache-Knoten beim Eintreffen eines Inhalts den lokalen TTU-Wert basierend auf dem vom Inhaltsverlag zugewiesenen TTU-Wert. Der lokale TTU-Wert wird mithilfe einer lokal definierten Funktion berechnet. Sobald der lokale TTU-Wert berechnet wurde, wird der Inhalt für eine Teilmenge des im Cache-Knoten gespeicherten Gesamtinhalts ersetzt. Die TLRU stellt sicher, dass weniger beliebte und kleine Lebensinhalte durch die eingehenden Inhalte ersetzt werden.
Zuletzt verwendet (MRU)Bearbeiten
Verwirft im Gegensatz zu LRU die zuletzt verwendeten Elemente zuerst. In den auf der 11. VLDB-Konferenz vorgestellten Ergebnissen stellten Chou und DeWitt fest, dass „MRU der beste Ersatzalgorithmus ist, wenn eine Datei wiederholt in einem Referenzmuster gescannt wird.“ Anschließend stellten andere Forscher, die auf der 22. VLDB-Konferenz vorstellten, fest, dass MRU-Cache-Algorithmen für zufällige Zugriffsmuster und wiederholte Scans über große Datensätze (manchmal auch als zyklische Zugriffsmuster bezeichnet) aufgrund ihrer Tendenz, ältere Daten beizubehalten, mehr Treffer aufweisen als LRU. MRU-Algorithmen sind am nützlichsten in Situationen, in denen der Zugriff auf ein Element umso wahrscheinlicher ist, je älter es ist.
Die Zugriffssequenz für das folgende Beispiel ist A B C D E C D B.
Hier werden A B C D in den Cache gelegt, da noch Speicherplatz verfügbar ist. Beim 5. Zugriff E sehen wir, dass der Block, der D enthielt, jetzt durch E ersetzt wird, da dieser Block zuletzt verwendet wurde. Ein weiterer Zugriff auf C und beim nächsten Zugriff auf D wird C ersetzt, wie es der Block war, auf den kurz vor D zugegriffen wurde und so weiter.
Pseudo-LRU (PLRU)Bearbeiten
Für CPU-Caches mit großer Assoziativität (im Allgemeinen >4-Wege) werden die Implementierungskosten von LRU unerschwinglich. In vielen CPU-Caches ist ein Schema, das fast immer eines der zuletzt verwendeten Elemente verwirft, ausreichend, so dass viele CPU-Designer einen PLRU-Algorithmus wählen, der nur ein Bit pro Cache-Element benötigt, um zu funktionieren.PLRU hat typischerweise ein etwas schlechteres Miss-Verhältnis, eine etwas bessere Latenz, verbraucht etwas weniger Strom als LRU und geringere Gemeinkosten im Vergleich zu LRU.
Das folgende Beispiel zeigt, wie Bits als Binärbaum von 1-Bit-Zeigern funktionieren, die auf den weniger kürzlich verwendeten Teilbaum verweisen. Im Anschluss an die Zeigerkette zum Blattknoten wird der Ersatzkandidat identifiziert. Bei einem Zugriff werden alle Zeiger in der Kette vom Blattknoten des Zugriffswegs zum Stammknoten so festgelegt, dass sie auf einen Teilbaum zeigen, der den Zugriffsweg nicht enthält.
Die Zugriffssequenz ist A B C D E.
Das Prinzip hier ist einfach zu verstehen, wenn wir nur die Pfeilzeiger betrachten. Wenn es einen Zugriff auf einen Wert gibt, sagen wir ‚A‘, und wir ihn nicht im Cache finden können, laden wir ihn aus dem Speicher und platzieren ihn an dem Block, auf den die Pfeile gerade zeigen, von oben nach unten. Nachdem wir diesen Block platziert haben, drehen wir dieselben Pfeile um, sodass sie in die entgegengesetzte Richtung zeigen. Im obigen Beispiel sehen wir, wie ‚A‘ platziert wurde, gefolgt von ‚B‘, ‚C und ‚D‘. Dann, als der Cache voll wurde, ersetzte ‚E‘ ‚A‘, weil dort die Pfeile zu dieser Zeit zeigten, und die Pfeile, die zu ‚A‘ führten, wurden umgedreht, um in die entgegengesetzte Richtung zu zeigen. Die Pfeile führten dann zu ‚B‘, was der Block sein wird, der beim nächsten Cache-Miss ersetzt wird.
Random replacement (RR)Edit
Wählt zufällig ein Kandidatenelement aus und verwirft es, um bei Bedarf Platz zu schaffen. Dieser Algorithmus erfordert keine Speicherung von Informationen über den Zugriffsverlauf. Aufgrund seiner Einfachheit wurde es in ARM-Prozessoren verwendet. Es ermöglicht eine effiziente stochastische Simulation.
Die Zugriffssequenz für das folgende Beispiel ist A B C D E B D F
Segmentierte LRU (SLRU)Bearbeiten
Der SLRU-Cache ist in zwei Segmente unterteilt, ein Probesegment und ein geschütztes Segment. Die Zeilen in jedem Segment werden von den meisten bis zu den am wenigsten kürzlich aufgerufenen Zeilen geordnet. Daten aus Fehlern werden dem Cache am Ende des Probesegments hinzugefügt, auf das zuletzt zugegriffen wurde. Treffer werden von überall dort entfernt, wo sie sich gerade befinden, und dem zuletzt aufgerufenen Ende des geschützten Segments hinzugefügt. Leitungen im geschützten Segment sind somit mindestens zweimal zugegriffen worden. Das geschützte Segment ist endlich, daher kann die Migration einer Leitung vom Probesegment zum geschützten Segment die Migration der LRU-Leitung im geschützten Segment zum zuletzt verwendeten (MRU) Ende des Probesegments erzwingen, sodass auf diese Leitung erneut zugegriffen werden kann, bevor sie ersetzt wird. Die Größenbeschränkung für das geschützte Segment ist ein SLRU-Parameter, der je nach E/A-Workload-Mustern variiert. Immer wenn Daten aus dem Cache verworfen werden müssen, werden Zeilen vom LRU-Ende des Probesegments abgerufen.
Least-frequently used (LFU)Edit
Zählt, wie oft ein Element benötigt wird. Diejenigen, die am wenigsten verwendet werden, werden zuerst verworfen. Dies funktioniert sehr ähnlich wie LRU, außer dass wir nicht den Wert speichern, wie kürzlich auf einen Block zugegriffen wurde, sondern den Wert, wie oft darauf zugegriffen wurde. Während wir also eine Zugriffssequenz ausführen, ersetzen wir natürlich einen Block, der am seltensten aus unserem Cache verwendet wurde. Wenn z. B. A 5 Mal verwendet wurde (zugegriffen) und B 3 Mal verwendet wurde und andere C und D jeweils 10 Mal verwendet wurden, ersetzen wir B.
Least frequent recently used (LFRU)Edit
Das Least Frequent Recently Used (LFRU) Cache Replacement Scheme kombiniert die Vorteile von LFU- und LRU-Schemata. LFRU eignet sich für Cache-Anwendungen im Netzwerk wie informationszentrierte Netzwerke (ICN), Content Delivery Networks (CDNs) und verteilte Netzwerke im Allgemeinen. In LFRU ist der Cache in zwei Partitionen unterteilt, die als privilegierte und unprivilegierte Partitionen bezeichnet werden. Die privilegierte Partition kann als geschützte Partition definiert werden. Wenn Inhalte sehr beliebt sind, werden sie in die privilegierte Partition verschoben. Das Ersetzen der privilegierten Partition erfolgt wie folgt: LFRU entfernt Inhalte aus der unprivilegierten Partition, schiebt Inhalte von der privilegierten Partition auf die unprivilegierte Partition und fügt schließlich neuen Inhalt in die privilegierte Partition ein. In der obigen Prozedur wird die LRU für die privilegierte Partition und ein angenähertes LFU-Schema (ALFU) für die unprivilegierte Partition verwendet, daher die Abkürzung LFRU.
Die Grundidee besteht darin, die lokal beliebten Inhalte mit dem ALFU-Schema herauszufiltern und die beliebten Inhalte auf eine der privilegierten Partitionen zu verschieben.
LFU mit dynamischer Alterung (LFUDA)Bearbeiten
Eine Variante namens LFU mit dynamischer Alterung (LFUDA), die dynamische Alterung verwendet, um Verschiebungen in der Menge populärer Objekte zu berücksichtigen. Es fügt dem Referenzzähler einen Cache-Altersfaktor hinzu, wenn ein neues Objekt zum Cache hinzugefügt wird oder wenn ein vorhandenes Objekt erneut referenziert wird. LFUDA erhöht das Cache-Alter beim Entfernen von Blöcken, indem es auf den Schlüsselwert des entfernten Objekts gesetzt wird. Daher ist das Cache-Alter immer kleiner oder gleich dem minimalen Schlüsselwert im Cache. Angenommen, wenn in der Vergangenheit häufig auf ein Objekt zugegriffen wurde und es jetzt unbeliebt wird, bleibt es lange Zeit im Cache, wodurch verhindert wird, dass die neu oder weniger beliebten Objekte es ersetzen. Daher wird diese dynamische Alterung eingeführt, um die Anzahl solcher Objekte zu verringern, wodurch sie für den Austausch in Frage kommen. Der Vorteil von LFUDA besteht darin, dass die durch LFU verursachte Cache-Verschmutzung reduziert wird, wenn die Cache-Größen sehr klein sind. Wenn Cache-Größen groß sind, sind nur wenige Ersatzentscheidungen ausreichend und Cache-Verschmutzung wird kein Problem sein.
Low inter-reference Recency set (LIRS)Edit
LIRS ist ein Seitenersatzalgorithmus mit einer verbesserten Leistung gegenüber LRU und vielen anderen neueren Ersetzungsalgorithmen. Dies wird erreicht, indem die Wiederverwendungsentfernung als Metrik für das dynamische Ranking aufgerufener Seiten verwendet wird, um eine Ersatzentscheidung zu treffen. LIRS adressieren effektiv die Grenzen der LRU, indem sie die Aktualität verwenden, um die Interreferenz-Aktualität (IRR) für eine Ersatzentscheidung zu bewerten.
In der obigen Abbildung stellt „x“ dar, dass zum Zeitpunkt t auf einen Block zugegriffen wird. Angenommen, wenn zum Zeitpunkt 1 auf Block A1 zugegriffen wird, wird Recency zu 0, da dies der erste Block ist, auf den zugegriffen wird, und IRR zu 1, da vorhergesagt wird, dass zum Zeitpunkt 3 erneut auf A1 zugegriffen wird. In der Zeit 2 seit dem Zugriff auf A4 wird die Aktualität für A4 zu 0 und für A1 zu 1, da A4 das zuletzt aufgerufene Objekt ist und IRR zu 4 wird und es weitergeht. Zum Zeitpunkt 10 hat der LIRS-Algorithmus zwei Sätze LIR set = {A1, A2} und HIR set = {A3, A4, A5}. Jetzt zum Zeitpunkt 10, wenn es Zugang zu A4 gibt, tritt Miss auf. Der LIRS-Algorithmus wird nun A5 anstelle von A2 aufgrund seiner größten Aktualität entfernen.
CLOCK-ProEdit
Der LRU-Algorithmus kann aufgrund seines hohen Overheads nicht direkt im kritischen Pfad von Computersystemen wie Betriebssystemen implementiert werden. Eine Approximation von LRU, CLOCK genannt, wird üblicherweise für die Implementierung verwendet. In ähnlicher Weise ist CLOCK-Pro eine Annäherung an LIRS für eine kostengünstige Implementierung in Systemen. CLOCK-Pro ist unter dem grundlegenden CLOCK-Framework, hat aber drei große Vorzüge. Erstens hat CLOCK-Pro drei „Uhrzeiger“ im Gegensatz zu einer einfachen Struktur der Uhr, wo nur ein „Hand“ verwendet wird. Mit den drei Zeigern ist CLOCK-Pro in der Lage, die ungefähre Entfernung von Datenzugriffen ungefähr zu messen. Zweitens bleiben alle Vorteile von LIRS erhalten, wie z. B. das schnelle Entfernen einmaliger Zugriffsdaten und / oder Datenelemente mit geringer Lokalität. Drittens ist die Komplexität der CLOCK-Pro ist die gleiche wie die der Uhr, so ist es einfach, zu geringen Kosten zu implementieren. Die Implementierung zum Ersetzen des Puffercaches in der aktuellen Linux-Version ist eine Kombination aus LRU und CLOCK-Pro.
Adaptive Replacement Cache (ARC)Bearbeiten
gleicht ständig zwischen LRU und LFU aus, um das kombinierte Ergebnis zu verbessern. ARC verbessert die SLRU, indem Informationen zu kürzlich geräumten Cache-Elementen verwendet werden, um die Größe des geschützten Segments und des Probesegments dynamisch anzupassen und den verfügbaren Cache-Speicherplatz optimal zu nutzen. Der adaptive Ersetzungsalgorithmus wird anhand des Beispiels erläutert.
AdaptiveClimb (AC)Edit
Verwendet recent hit/miss, um den Sprung anzupassen, wobei in climb jeder Treffer die Position um einen Slot nach oben und in LRU hit die Position des Treffers nach oben wechselt. Somit profitieren Sie von der Optimalität des Aufstiegs, wenn sich das Programm in einem festen Bereich befindet, und der schnellen Anpassung an einen neuen Bereich, wie dies bei LRU der Fall ist. Unterstützen Sie auch die Cache-Freigabe zwischen Kernen, indem Sie Extras freigeben, wenn sich die Referenzen im oberen Teil des Caches befinden.
Clock with adaptive replacement (CAR)Bearbeiten
Kombiniert die Vorteile von Adaptive Replacement Cache (ARC) und CLOCK. CAR hat eine mit ARC vergleichbare Leistung und übertrifft sowohl LRU als auch CLOCK erheblich. Wie ARC, AUTO ist selbst-tuning und erfordert keine benutzer-angegeben magie parameter. Es verwendet 4 doppelt verknüpfte Listen: zwei Uhren T1 und T2 und zwei einfache LRU-Listen B1 und B2. T1 clock speichert Seiten basierend auf „recency“ oder „short term utility“, während T2 Seiten mit „frequency“ oder „long term utility“ speichert. T1 und T2 enthalten die Seiten, die sich im Cache befinden, während B1 und B2 Seiten enthalten, die kürzlich aus T1 bzw. T2 entfernt wurden. Der Algorithmus versucht, die Größe dieser Listen B1≈T2 und B2≈T1 beizubehalten. Neue Seiten werden in T1 oder T2 eingefügt. Wenn es einen Treffer in B1 gibt, wird die Größe von T1 erhöht und in ähnlicher Weise, wenn es einen Treffer in B2 gibt, wird die Größe von T1 verringert. Investieren Sie mehr in Listen, die mehr Treffer liefern, wenn mehr Seiten hinzugefügt werden.
Multi queue (MQ)Edit
Der Multi queue algorithm oder MQ wurde entwickelt, um die Leistung des Second Level Buffer Cache für z.B. einen Server Buffer Cache zu verbessern. Der MQ-Cache enthält eine m Anzahl von LRU-Warteschlangen: Q0, Q1, …, Qm-1. Hier stellt der Wert von m eine Hierarchie dar, die auf der Lebensdauer aller Blöcke in dieser bestimmten Warteschlange basiert. Wenn beispielsweise j>i , haben Blöcke in Qj eine längere Lebensdauer als Blöcke in Qi. Zusätzlich zu diesen gibt es einen weiteren Verlaufspuffer Qout, eine Warteschlange, die eine Liste aller Blockkennungen zusammen mit ihren Zugriffshäufigkeiten verwaltet. Wenn Qout voll ist, wird der älteste Bezeichner entfernt. Blöcke bleiben für eine bestimmte Lebensdauer in den LRU-Warteschlangen, die dynamisch vom MQ-Algorithmus als maximale zeitliche Entfernung zwischen zwei Zugriffen auf dieselbe Datei oder als Anzahl der Cache-Blöcke definiert wird, je nachdem, welcher Wert größer ist. Wenn ein Block innerhalb seiner Lebensdauer nicht referenziert wurde, wird er von Qi auf Qi−1 herabgestuft oder aus dem Cache entfernt, wenn er sich in Q0 befindet. Jede Warteschlange hat auch eine maximale Zugriffszahl; Wenn auf einen Block in der Warteschlange Qi mehr als 2i Mal zugegriffen wird, wird dieser Block auf Qi + 1 hochgestuft, bis mehr als 2i + 1 Mal darauf zugegriffen wird oder seine Lebensdauer abläuft. Innerhalb einer bestimmten Warteschlange werden Blöcke gemäß LRU nach der Aktualität des Zugriffs geordnet.
Wir können aus Abb. wie die m LRU-Warteschlangen im Cache platziert werden. Siehe auch Fig. wie der Qout die Blockkennungen und ihre entsprechenden Zugriffsfrequenzen speichert. a wurde in Q0 platziert, da erst kürzlich darauf zugegriffen wurde, und wir können in Qout überprüfen, wie b und c in Q1 bzw. Q2 platziert wurden, da ihre Zugriffsfrequenzen 2 und 4 sind. Die Warteschlange, in der ein Block platziert wird, ist abhängig von der Zugriffsfrequenz (f) als log2 (f). Wenn der Cache voll ist, ist der erste Block, der geräumt wird, der Kopf von Q0 in diesem Fall a. Wenn noch einmal auf a zugegriffen wird, wird er zu Q1 unter b verschoben.
Pannier: Containerbasierter Caching-Algorithmus für zusammengesetzte Objektebearbeiten
Pannier ist ein containerbasierter Flash-Caching-Mechanismus, der divergierende (heterogene) Container identifiziert, in denen darin enthaltene Blöcke stark unterschiedliche Zugriffsmuster aufweisen. Pannier verwendet eine prioritätswarteschlangenbasierte Überlebenswarteschlangenstruktur, um die Container basierend auf ihrer Überlebenszeit zu ordnen, die proportional zu den Live-Daten im Container ist. Pannier basiert auf segmentierter LRU (S2LRU), die heiße und kalte Daten trennt. Pannier verwendet auch eine multi-schritt feedback controller zu gas flash schreibt zu gewährleisten flash lebensdauer.