Warum ist LRU besser als FIFO?
https://stackoverflow.com/questions/2058403
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Warum ist Zuletzt benutzt Besser als FIFO in Bezug auf Seitendateien?
Lösung
Wenn Sie es im Sinne von Speicherseiten auf die Festplatte meinen. Wenn Ihr Prozess häufig auf eine Seite zugreift, möchten Sie wirklich nicht, dass sie auf die Festplatte aufgetragen wird, auch wenn es das allererste war, auf das Sie zugegriffen haben. Wenn Sie jedoch mehrere Tage lang nicht mehr auf eine Speicherseite zugegriffen haben, ist es unwahrscheinlich, dass Sie dies in naher Zukunft tun werden.
Wenn Sie das nicht meinen, bearbeiten Sie bitte Ihre Frage, um weitere Details zu erhalten.
Andere Tipps
Es gibt keinen einzelnen Cache -Algorithmus, der immer gut abschneidet, da dies ein perfektes Wissen über die Zukunft erfordert. (Und wenn Sie wissen, wo Sie das bekommen können ...) Die Dominanz von LRU im VM -Cache -Design ist das Ergebnis einer langen Geschichte des Verhaltens des Systems. Angesichts der tatsächlichen Arbeitsbelastung funktioniert LRU ziemlich gut ein sehr großer Teil der Zeit. Es ist jedoch nicht sehr schwierig, eine Referenzzeichenfolge zu konstruieren, für die FIFO über eine überlegene Leistung über LRU verfügen würde.
Betrachten Sie einen linearen Sweep durch einen großen Adressraum, der viel größer ist als der verfügbare, vorliegbare reale Speicher. LRU basiert auf der Annahme, dass "das, was Sie in letzter Zeit berührt haben, wahrscheinlich wieder berühren wird", aber der lineare Sweep gegen diese Annahme verstößt vollständig. Aus diesem Grund ermöglichen es bei einigen Betriebssystemen Programmen, den Kernel über ihr Referenzverhalten zu beraten - ein Beispiel ist die Müllsammlung "Mark und Sweep", die von klassischen Lisp -Dolmetschern angepasst ist. (Und ein wichtiger Treiber für die Arbeit an moderneren GCs wie "Generation".)
Ein weiteres Beispiel ist die Symboltabelle in einem bestimmten antiken Makroprozessor (Stufe2). Der binäre Baum wird von der Wurzel für jedes Symbol gesucht, und die Saitenbewertung wird auf einem Stapel durchgeführt. Es stellte sich heraus, dass Reduzierung Die verfügbaren Seitenrahmen, indem Sie die Wurzelseite des Symbolbaums und die untere Seite des Stapels "verdrahten". Der Cache war winzig und erbrachte heftig und drückte immer die beiden am häufigsten verwiesenen Seiten heraus, da der Cache kleiner als der Abstand zwischen den Referenzen zu diesen Seiten war. Also a klein Der Cache funktionierte besser, aber nur, weil diese zwei Seitenrahmen aus dem Cache mit Bedacht verwendet wurden.
Das Netz von all dem ist, dass LRU die Standardantwort ist, da es normalerweise ziemlich gut für echte Workloads bei Systemen ist, die nicht schrecklich überlastet sind (VM oft als realer Speicher), und dies wird durch jahrelange sorgfältige Messungen unterstützt. Sie können jedoch sicherlich Fälle finden, in denen alternatives Verhalten überlegen ist. Deshalb Messung Reale Systeme sind wichtig.
Behandle den RAM als Cache. Um ein effektiver Cache zu sein, muss die Elemente am wahrscheinlichsten im Speicher angefordert werden.
LRU hält die Dinge, die zuletzt im Gedächtnis verwendet wurden. FIFO hält die Dinge, die zuletzt hinzugefügt wurden. LRU ist im Allgemeinen effizienter, weil es im Allgemeinen Speicherelemente gibt, die einmal hinzugefügt und nie wieder verwendet werden, und es werden regelmäßig Elemente hinzugefügt und verwendet. LRU hält die häufig verwendeten Elemente viel häufiger im Speicher.
Abhängig von Zugangsmustern kann FIFO manchmal LRU besiegen. Ein Adaptiver Ersatzcache ist Hybrid, der seine Strategie anhand der tatsächlichen Nutzungsmuster anpasst.
Entsprechend zeitliche Referenzlokalität, Speicher, auf das in letzter Zeit zugegriffen wurde, ist eher wieder zugegriffen.
