Was ist der Seitenersetzungsalgorithmus?

Wenn während des Adresszuordnungsprozesses festgestellt wird, dass sich die Seite, auf die zugegriffen werden soll, nicht im Speicher befindet, kommt es zu einer Seitenfehlerunterbrechung. Wenn ein Seitenfehler auftritt und keine freie Seite im Speicher des Betriebssystems vorhanden ist, muss das Betriebssystem eine Seite im Speicher auswählen und aus dem Speicher verschieben, um Platz für die zu übertragende Seite zu schaffen. Die Regeln zur Auswahl der zu entfernenden Seiten werden Seitenersetzungsalgorithmen genannt.

Gemeinsame Ersetzungsalgorithmen

Optimaler Ersetzungsalgorithmus (OPT)

Das ist Ein idealer Seitenersetzungsalgorithmus, der jedoch in der Praxis nicht umsetzbar ist. Die Grundidee dieses Algorithmus ist: Wenn ein Seitenfehler auftritt, befinden sich einige Seiten im Speicher, auf eine davon wird bald zugegriffen (einschließlich der Seite der nächsten Anweisung), während auf andere Seiten möglicherweise erst nach 10 oder 10 Jahren zugegriffen wird 100 Oder es wird nach 1000 Anweisungen aufgerufen. Auf jeder Seite kann [1] die Anzahl der auszuführenden Anweisungen angegeben werden, bevor die Seite zum ersten Mal aufgerufen wird. Der optimale Seitenersetzungsalgorithmus besagt einfach, dass die Seite mit dem größten Markup ersetzt werden sollte. Das einzige Problem dieses Algorithmus besteht darin, dass er nicht implementiert werden kann. Wenn ein Seitenfehler auftritt, kann das Betriebssystem nicht wissen, wann das nächste Mal auf die einzelnen Seiten zugegriffen wird. Obwohl dieser Algorithmus nicht implementiert werden kann, kann der optimale Seitenersetzungsalgorithmus verwendet werden, um die Leistung erreichbarer Algorithmen zu messen und zu vergleichen.

First-In-First-Out-Ersetzungsalgorithmus (FIFO)

Der einfachste Seitenersetzungsalgorithmus ist die First-In-First-Out-Methode (FIFO). Der Kern dieses Algorithmus besteht darin, immer die Seite auszuwählen, die am längsten (d. h. die älteste) im Hauptspeicher verblieben ist, um sie zu ersetzen, d. h. die Seite, die zuerst in den Speicher gelangt und ihn zuerst verlässt. Der Grund dafür ist, dass die älteste in den Speicher übertragene Seite mit größerer Wahrscheinlichkeit nicht mehr verwendet wird als die Seite, die gerade in den Speicher übertragen wurde. Erstellen Sie eine FIFO-Warteschlange, um alle Seiten im Speicher zu speichern. Ersetzte Seiten werden immer an die Spitze der Warteschlange gestellt. Wenn eine Seite in den Speicher gestellt wird, wird sie am Ende der Warteschlange eingefügt.

Dieser Algorithmus ist nur ideal, wenn in linearer Reihenfolge auf den Adressraum [1] zugegriffen wird, andernfalls ist er nicht effizient. Denn die Seiten, auf die häufig zugegriffen wird, bleiben in der Regel am längsten im Hauptspeicher und müssen deshalb ersetzt werden, weil sie „alt“ sind.

Ein weiterer Nachteil von FIFO besteht darin, dass es ein abnormales Phänomen aufweist, das heißt, wenn der Speicherblock erhöht wird, steigt die Seitenfehler-Interruptrate. Natürlich ist die Seitenrichtung, die diese Anomalie verursacht, tatsächlich selten.

Least-Recent-Used-Algorithmus (LRU)

Der Hauptunterschied zwischen dem FIFO-Algorithmus und dem OPT-Algorithmus besteht darin, dass der FIFO-Algorithmus die Zeitspanne nach dem Aufruf der Seite verwendet der Speicher als Ersatz Grundlage des OPT-Algorithmus ist der Zeitpunkt, zu dem die Seite in Zukunft verwendet wird. Wird die jüngste Vergangenheit als Annäherung an die nahe Zukunft herangezogen, können Seiten ersetzt werden, die in der Vergangenheit über einen längsten Zeitraum nicht genutzt wurden. Der Kern besteht darin, dass, wenn eine Seite ersetzt werden muss, die Seite ausgewählt wird, die in der vorherigen Zeitspanne am längsten nicht verwendet wurde, um sie zu ersetzen. Dieser Algorithmus wird als der am wenigsten kürzlich verwendete Algorithmus (Least Recent Used, LRU) bezeichnet.

Der LRU-Algorithmus bezieht sich auf den Zeitpunkt, zu dem jede Seite das letzte Mal verwendet wurde. Wenn eine Seite ersetzt werden muss, wählt der LRU-Algorithmus die Seite aus, die in der vergangenen Zeitspanne am wenigsten genutzt wurde.

Der LRU-Algorithmus ist ein häufig verwendeter Seitenersetzungsalgorithmus und gilt als recht gut, es gibt jedoch ein Problem bei der Implementierung.

Der LRU-Algorithmus erfordert die Unterstützung tatsächlicher Hardware.

Das Problem besteht darin, die Reihenfolge der zuletzt verwendeten Zeit zu ermitteln. Dafür gibt es zwei Möglichkeiten:

1.

Der einfachste Fall besteht darin, jeden Seitentabelleneintrag einem Nutzungszeitfeld zuzuordnen und der CPU eine logische Uhr oder einen logischen Zähler hinzuzufügen. Dieser Takt wird bei jedem Speicherzugriff um 1 erhöht. Bei jedem Zugriff auf eine Seite wird der Inhalt des Uhrenregisters in das Nutzungszeitfeld des entsprechenden Seitentabelleneintrags kopiert. Auf diese Weise können wir immer die „Zeit“ des letzten Besuchs jeder Seite im Auge behalten. Wählen Sie beim Ersetzen von Seiten die Seite mit dem kleinsten Zeitwert aus. Dabei muss nicht nur die Seitentabelle nachgeschlagen werden, sondern auch die Zeit in der Seitentabelle beibehalten werden, wenn sich die Seitentabelle ändert (aufgrund der CPU-Planung), und auch das Problem des Überlaufs der Taktwerte muss berücksichtigt werden .

2. Stapel.

Verwenden Sie einen Stapel, um Seitenzahlen beizubehalten. Bei jedem Zugriff auf eine Seite wird diese aus dem Stapel genommen und oben auf dem Stapel abgelegt. Auf diese Weise wird die am häufigsten verwendete Seite immer oben im Stapel und die am wenigsten verwendete Seite unten im Stapel platziert. Da ein Gegenstand aus der Mitte des Stapels entfernt werden muss, wird eine Zwei-Wege-Kette mit Kopf- und Schwanzzeigern verwendet, um ihn zu verbinden. Im schlimmsten Fall erfordert das Entfernen einer Seite und das Platzieren oben auf dem Stapel das Ändern von 6 Zeigern. Für jede Änderung entsteht ein Overhead, aber die Seite, die ersetzt werden muss, kann direkt ohne Suche abgerufen werden, da der Endzeiger auf das untere Ende des Stapels zeigt, wo sich die zu ersetzende Seite befindet.

Da die Implementierung des LRU-Algorithmus ein hohes Maß an Hardwareunterstützung erfordert, erfordert sie auch einen gewissen Software-Overhead. Was also tatsächlich implementiert wird, ist ein einfacher und effektiver LRU-Approximationsalgorithmus.

Ein LRU-Approximationsalgorithmus ist der Not-Recent-Used-Algorithmus (NUR).

Es fügt jedem Eintrag in der Speicherblocktabelle ein Referenzbit hinzu und das Betriebssystem setzt sie regelmäßig auf 0. Dieses Bit wird von der Hardware gesetzt, wenn auf eine Seite zugegriffen wird. Im Laufe der Zeit können diese Bits untersucht werden, um festzustellen, welche Seiten verwendet wurden und welche Seiten nicht verwendet wurden, seit sie das letzte Mal auf 0 gesetzt wurden. Die Seite, deren Bit 0 ist, kann entfernt werden, da in der letzten Zeit nicht auf sie zugegriffen wurde.

4) Taktersetzungsalgorithmus (ungefähre Implementierung des LRU-Algorithmus)

5) Least Used (LFU)-Ersetzungsalgorithmus

Wenn der am wenigsten verwendete Ersetzungsalgorithmus verwendet wird, sollte dies der Fall sein Jede Seite im Speicher ist mit einem Schieberegister ausgestattet, um aufzuzeichnen, wie oft auf die Seite zugegriffen wird. Der Ersetzungsalgorithmus wählt die im vorherigen Zeitraum am wenigsten genutzte Seite als Räumungsseite aus.

Aufgrund der hohen Zugriffsgeschwindigkeit des Speichers, beispielsweise 100 ns, kann auf eine Seite innerhalb von 1 ms tausende Male ununterbrochen zugegriffen werden. Daher ist es normalerweise nicht möglich, die Anzahl direkt mit einem Zähler aufzuzeichnen Mal wird auf eine Seite zugegriffen, stattdessen wird eine Schieberegistermethode verwendet. Bei jedem Zugriff auf eine Seite wird das höchste Bit des Schieberegisters auf 1 gesetzt und dann zu einem bestimmten Zeitpunkt (z. B. 100 ns) nach rechts verschoben. Auf diese Weise wird die Seite, die in der letzten Zeit am wenigsten genutzt wurde, die Seite mit dem kleinsten ΣRi sein.

Das Seitenzugriffsdiagramm des LFU-Ersetzungsalgorithmus ist genau das gleiche wie das Zugriffsdiagramm des LRU-Ersetzungsalgorithmus, mit anderen Worten, ein solcher Hardwaresatz kann sowohl den LRU-Algorithmus als auch den LFU-Algorithmus implementieren. Es sollte darauf hingewiesen werden, dass der LFU-Algorithmus die Seitennutzung nicht wirklich widerspiegelt, da in jedem Zeitintervall nur ein Bit des Registers zur Aufzeichnung der Seitennutzung verwendet wird. Daher entspricht ein einmaliger Zugriff einem 10.000-maligen Zugriff.

6) Working-Set-Algorithmus

7) Working-Set-Clock-Algorithmus

8) Aging-Algorithmus (ein effizienter Algorithmus, der LRU sehr ähnlich ist)

9) NRU-Algorithmus (in letzter Zeit nicht verwendet)

10) Algorithmus der zweiten Chance

Die Grundidee des Algorithmus der zweiten Chance ist dieselbe wie bei FIFO, wurde jedoch verbessert, um häufig verwendete Seiten zu vermeiden Ersetzen Sie es. Wenn eine Ersatzseite ausgewählt wird, werden deren Zugriffsbits überprüft. Wenn es 0 ist, wird die Seite eliminiert; wenn das Zugriffsbit 1 ist, erhält es eine zweite Chance und die nächste FIFO-Seite wird ausgewählt. Wenn eine Seite eine zweite Chance erhält, wird ihr Zugriffsbit auf 0 gelöscht und ihre Ankunftszeit auf die aktuelle Zeit gesetzt. Wurde die Seite in diesem Zeitraum besucht, wird Position 1 besucht. Seiten, denen auf diese Weise eine zweite Chance gegeben wurde, werden erst entfernt, wenn alle anderen Seiten entfernt wurden (oder ebenfalls eine zweite Chance erhalten haben). Wenn eine Seite häufig verwendet wird, bleibt ihr Zugriffsbit daher immer 1 und wird niemals gelöscht.

Der Algorithmus der zweiten Chance kann als kreisförmige Warteschlange betrachtet werden. Verwenden Sie einen Zeiger, um anzugeben, welche Seite als nächstes entfernt werden soll. Wenn ein Speicherblock benötigt wird, bewegt sich der Zeiger weiter, bis er eine Seite findet, deren Zugriffsbit 0 ist. Wenn der Zeiger vorrückt, wird das Zugriffsbit auf 0 gelöscht. Im schlimmsten Fall sind alle Zugriffsbits 1 und der Zeiger durchläuft eine Woche lang die gesamte Warteschlange, wodurch jede Seite eine zweite Chance erhält. Zu diesem Zeitpunkt degeneriert es zum FIFO-Algorithmus.

Das obige ist der detaillierte Inhalt vonWas ist der Seitenersetzungsalgorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!