Was verwendet Linux, um virtuellen Speicher zu implementieren?

Die Implementierung des virtuellen Speichers muss auf der diskreten Speicherverwaltungsmethode basieren. Es gibt drei Implementierungsmethoden: 1. Anforderungs-Paging-Speicherverwaltungsmethode; 3. Segmentierte Speicherverwaltungsmethode. Unabhängig davon, welche Methode verwendet wird, ist eine bestimmte Hardwareunterstützung erforderlich: 1. Eine bestimmte Speicherkapazität und ein externer Speicher. 2. Ein Seitentabellenmechanismus (oder Segmenttabellenmechanismus) als Hauptdatenstruktur Bedarf Wenn der Zugriffsteil noch nicht in den Speicher übertragen wurde, kommt es zu einem Interrupt. 4. Adresskonvertierungsmechanismus, Konvertierung von logischer Adresse in physikalische Adresse.

Die Betriebsumgebung dieses Tutorials: Linux7.3-System, Dell G3-Computer.

1. Übersicht über den virtuellen Speicher

Traditionelle Speicherverwaltung speichert mehrere Prozesse gleichzeitig im Speicher, um eine Mehrfachprogrammierung zu ermöglichen. Sie alle haben folgende zwei Eigenschaften gemeinsam:

• Einmalig: Der Job muss sofort in den Speicher geladen werden , bevor er ausgeführt werden kann. Dies führt zu zwei Situationen: 1) Wenn der Job groß ist und nicht in den Speicher geladen werden kann, kann der Job nicht ausgeführt werden.
  2) Wenn eine große Anzahl von Jobs ausgeführt werden muss, weil der Speicher nicht verfügbar ist Es reicht aus, nur alle Jobs aufzunehmen. Dies kann dazu führen, dass einige Jobs zuerst ausgeführt werden, was zu einer Verringerung der Mehrfachprogrammierung führt.
  
• Residency: Nachdem der Job in den Speicher geladen wurde, bleibt er immer im Speicher verbleiben und kein Teil davon wird ausgelagert, bis der Job abgeschlossen ist. Ein laufender Prozess wird beim Warten auf E/A blockiert und befindet sich möglicherweise über einen längeren Zeitraum in einem Wartezustand.

Daher belegen viele Programme (Daten), die während des Programmbetriebs nicht oder vorübergehend nicht verwendet werden, viel Speicherplatz, und einige auszuführende Jobs können nicht geladen und ausgeführt werden, was offensichtlich wertvolle Speicherressourcen verschwendet . 1.1 Definition und Eigenschaften des virtuellen Speichers . Programmausführung starten. Wenn sich während der Ausführung des Programms die abgerufenen Informationen nicht im Speicher befinden, überträgt das Betriebssystem

den erforderlichen Teil in den Speicher

und führt dann das Programm weiter aus. Andererseits lagert das Betriebssystem den vorübergehend ungenutzten Inhalt im Speicher auf einen externen Speicher aus und schafft so Platz für die Speicherung der Informationen, die in den Speicher übertragen werden.

Da das System auf diese Weise Teillade-, Ladeanforderungs- und Ersetzungsfunktionen bereitstellt (völlig transparent für den Benutzer), hat der Benutzer das Gefühl, dass es einen Speicher gibt, der viel größer ist als der tatsächliche physische Speicher, der aufgerufen wird Virtueller Speicher.

Die Größe des virtuellen Speichers wird durch die Adressstruktur des Computers bestimmt und ist keine einfache Summe aus Arbeitsspeicher und externem Speicher. Der virtuelle Speicher weist die folgenden drei Hauptmerkmale auf:

Mehrmals: Es ist nicht erforderlich, den Speicher während der Ausführung des Jobs auf einmal zu laden, es ist jedoch zulässig, ihn in mehrere Male aufzuteilen und zu laden in den Speicher zum Ausführen. Austauschbarkeit: Es ist nicht erforderlich, den Speicher während der Ausführung des Jobs resident zu halten, sondern ermöglicht das Ein- und Auslagern während der Ausführung des Jobs.

Virtualität: Erweitern Sie die Speicherkapazität logisch, sodass die vom Benutzer gesehene Speicherkapazität viel größer ist als die tatsächliche Speicherkapazität.

1.2 Implementierung der virtuellen Speichertechnologie

• Der virtuelle Speicher ermöglicht die mehrfache Übertragung eines Jobs in den Speicher
.
• Bei Verwendung der kontinuierlichen Zuweisungsmethode befindet sich ein erheblicher Teil des Speicherplatzes in einem vorübergehenden oder „permanenten“ Ruhezustand, was zu einer erheblichen Verschwendung von Speicherressourcen führt und es nicht möglich ist, die Speicherkapazität logisch zu erweitern.
Daher muss die Implementierung des virtuellen Speichers auf der
• diskreten ZuordnungSpeicherverwaltungsmethode
basieren. Es gibt drei Möglichkeiten, virtuellen Speicher zu implementieren:

Paging anfordern Speicherverwaltung

Segmentierung anfordern Speicherverwaltung

Segment-Paging

Speicherverwaltung

Egal welche Methode, es sind bestimmte Anforderungen erforderlich Unterstützung . Der im Allgemeinen erforderliche Support umfasst folgende Aspekte:

Eine bestimmte Menge an Arbeitsspeicher und externem Speicher.
• Seitentabellenmechanismus (oder Segmenttabellenmechanismus) als Hauptdatenstruktur.
Interrupt-Mechanismus: Wenn der Teil, auf den das Benutzerprogramm zugreifen soll, nicht in den Speicher übertragen wurde, wird ein Interrupt generiert.
• Adresskonvertierungsmechanismus, Konvertierung einer logischen Adresse in eine physische Adresse.
Kontinuierliche Zuweisungsmethode

:

bezieht sich auf die Zuweisung eines kontinuierlichen Speicherplatzes für ein Benutzerprogramm.

• Feste Partitionszuordnung: Teilen Sie den Speicherplatz in mehrere Bereiche fester Größe auf. In jede Partition wird nur ein Job geladen, und mehrere Jobs können gleichzeitig ausgeführt werden. Mangelnde Flexibilität führt zu vielen internen Fragmenten und die Speicherauslastung ist sehr gering.
• Dynamische Partitionszuweisung: Weisen Sie dem Prozess dynamisch Speicherplatz entsprechend seinem tatsächlichen Bedarf zu. Wenn ein Job in den Speicher geladen wird, wird der verfügbare Speicher in einen zusammenhängenden Bereich für den Job aufgeteilt und die Größe der Partition ist genau auf die Größe des Jobs abgestimmt. Es wird eine Menge äußerer Schmutz geben.

Diskrete Zuordnungsmethode: Laden Sie einen Prozess verteilt in viele nicht benachbarte Partitionen, sodass der Speicher vollständig genutzt werden kann.

Das Konzept der Seitenspeicherung:

• Seiten, Seitenrahmen und Blöcke. Der Block im Prozess heißt Seite oder Seite (Seite), mit Seitennummer; der Block im Speicher heißt Seitenrahmen (Seitenrahmen, Seitenrahmen = Speicherblock = physischer Block = physisch). Seite ), mit Seitenrahmennummer. Externer Speicher ist ebenfalls in derselben Einheit unterteilt, die direkt Block genannt wird. Wenn ein Prozess ausgeführt wird, muss er Hauptspeicherplatz beantragen, was bedeutet, dass jeder Seite ein verfügbarer Seitenrahmen im Hauptspeicher zugewiesen werden muss, wodurch eine Eins-zu-Eins-Entsprechung zwischen Seiten und Seitenrahmen entsteht. Jede Seite muss nicht nacheinander gespeichert werden und kann in nicht benachbarten Seitenrahmen platziert werden.
• Adressstruktur: Der erste Teil ist Seitennummer P und der zweite Teil ist In-Page-Offset W. Die Adresslänge beträgt 32 Bit, wobei die Bits 0 bis 11 die Intra-Page-Adresse sind, d Seiten.
• Seitentabelle. Um das Auffinden des physischen Blocks zu erleichtern, der jeder Seite des Prozesses im Speicher entspricht, erstellt das System eine Seitentabelle für jeden Prozess, um die der Seite im Speicher entsprechende physische Blocknummer aufzuzeichnen Erinnerung. . Nachdem die Seitentabelle konfiguriert wurde und der Prozess ausgeführt wird, kann die physische Blocknummer jeder Seite im Speicher durch Nachschlagen in der Tabelle ermittelt werden. Es ist ersichtlich, dass die Rolle der Seitentabelle darin besteht, die Adresszuordnung von Seitennummern zu physischen Blocknummern zu implementieren.

2. Anforderungs-Paging-Verwaltung zur Implementierung des virtuellen Speichers

Anforderungs-Paging

ist derzeit die am häufigsten verwendete Methode zur Implementierung des virtuellen Speichers. Das Anforderungs-Paging-System basiert auf dem

Basis-Paging-System

. Um die Funktion des virtuellen Speichers zu unterstützen, wurden die Funktionen Paging anfordern und

Seitenersetzung

hinzugefügt. Im Request-Paging-System muss nur ein Teil der aktuell benötigten Seiten in den Speicher geladen werden, bevor der Job gestartet werden kann. Wenn sich die Seite, auf die zugegriffen werden soll, während der Ausführung des Auftrags nicht im Speicher befindet, kann sie über die Paging-Funktion eingeholt werden. Gleichzeitig können die vorübergehend nicht verwendeten Seiten über die Ersetzungsfunktion auf einen externen Speicher ausgelagert werden um Speicherplatz freizugeben. Um Request Paging zu implementieren, muss das System bestimmte Hardwareunterstützung bereitstellen. Zusätzlich zu einem Computersystem, das

eine bestimmte Menge an Arbeitsspeicher und externem Speicher

benötigt, benötigt es auch einen

Seitentabellenmechanismus, einen Seitenfehler-Unterbrechungsmechanismus und einen Adresskonvertierungsmechanismus. 2.1 Seitentabellenmechanismus

Der Seitentabellenmechanismus des Anforderungs-Paging-Systems unterscheidet sich vom Basis-Paging-System. Beim Anforderungs-Paging-System müssen nicht alle Daten auf einmal in den Speicher geladen werden, bevor ein Auftrag ausgeführt wird wird ausgeführt. Daher kommt es während des laufenden Auftragsvorgangs zwangsläufig zu einer Situation, in der sich die Seite, auf die zugegriffen werden soll, nicht im Speicher befindet. Das Erkennen und Behandeln dieser Situation ist zwei grundlegende Probleme, die das Anforderungs-Paging-System lösen muss. Zu diesem Zweck werden vier Felder zum Eintrag in der Anforderungsseitentabelle hinzugefügt:

Seitentabelleneintrag im Anforderungs-Paging-System

SeitennummerPhysische BlocknummerStatusbit P Zugriff auf Feld ABit M ändernExterne Speicheradresse

• Statusbit P: Wird verwendet, um anzuzeigen, ob die Seite zum Referenzieren in den Speicher übertragen wurde, wenn das Programm darauf zugreift.
• Zugriffsfeld A: Wird verwendet, um aufzuzeichnen, wie oft innerhalb eines bestimmten Zeitraums auf diese Seite zugegriffen wurde, oder wie lange auf diese Seite in letzter Zeit nicht zugegriffen wurde, als Referenz, wenn der Ersetzungsalgorithmus die Seite austauscht.
• Änderungsbit M: Zeigt an, ob die Seite nach dem Laden in den Speicher geändert wurde.
• Adresse des externen Speichers: Wird verwendet, um die Adresse der Seite im externen Speicher anzugeben, normalerweise die physische Blocknummer, als Referenz beim Laden der Seite. 2.2 Interrupt-Mechanismus für fehlende Seiten fehlende Seite in den Speicher.

Zu diesem Zeitpunkt sollte der Seitenfehlerprozess blockiert werden (nach Abschluss des Pagings aufwachen, einen Block zuweisen, die zu ladende Seite in den Block laden und ändern). entsprechender Seitentabelleneintrag in der Seitentabelle; Wenn zu diesem Zeitpunkt kein freier Block im Speicher vorhanden ist, muss eine bestimmte Seite gelöscht werden (wenn die gelöschte Seite während des Speicherzeitraums geändert wurde, muss sie in den externen Speicher zurückgeschrieben werden). .

Als Interrupt müssen seitenfehlende Interrupts auch mehrere Schritte durchlaufen, z. B. den Schutz der CPU-Umgebung, die Analyse der Ursache des Interrupts, die Übertragung an den Interrupt-Handler für fehlende Seiten und die Wiederherstellung der CPU-Umgebung. Im Vergleich zu allgemeinen Interrupts gibt es jedoch die folgenden zwei offensichtlichen Unterschiede: Interruptsignale werden während der Ausführung von Anweisungen generiert und verarbeitet und nicht erst nach der Ausführung einer Anweisung, bei der es sich um einen internen Interrupt handelt.

Während der Ausführung einer Anweisung können mehrere Seitenfehler-Interrupts auftreten.

2.3 Adresstransformationsmechanismus

Der Adresstransformationsmechanismus im Anforderungs-Paging-System basiert auf dem Adresstransformationsmechanismus des Paging-Systems und fügt bestimmte Funktionen hinzu, um den virtuellen Speicher zu realisieren.

• Adresstransformationsprozess im Anforderungs-Paging

Durchsuchen Sie bei der Adresskonvertierung zuerst die Schnelltabelle:

• Wenn die Seite gefunden wird, auf die zugegriffen werden soll, wird das Zugriffsbit im Seitentabelleneintrag geändert (das Änderungsbit muss beim Schreiben von Anweisungen zurückgesetzt werden) und dann Der Seitentabelleneintrag wird verwendet. Die physische Blocknummer und die Seitenadresse werden in Form der physischen Adresse angegeben.
• Wenn der Seitentabelleneintrag der Seite nicht gefunden wird, sollten Sie die Seitentabelle im Speicher durchsuchen und dann das Statusbit P im Seitentabelleneintrag vergleichen, um festzustellen, ob die Seite in den Speicher übertragen wurde , wird eine Seitenfehlerunterbrechung auftreten. Fordern Sie an, dass die Seite vom externen Speicher in den Speicher übertragen wird.

Seitentabelle weist auf die Entsprechung zwischen der Seitennummer in der logischen Adresse und der physischen Blocknummer des belegten Hauptspeichers hin. Die Seitenspeicherverwaltung verwendet Seitentabellen, um die Adressübersetzung durchzuführen, wenn Vorgänge mithilfe der dynamischen Verschiebung geladen werden.

Fast Table (TLB, Translation Lookaside Buffer) ist eine Teilseitentabelle, die im Cache-Speicher gespeichert ist. Als Cache der aktuellen Prozessseitentabelle ähnelt seine Funktion der Seitentabelle, beschleunigt jedoch die Adresszuordnung und verbessert die Zugriffsrate. Aufgrund der Verwendung von Seitentabellen zur Adressübersetzung muss die CPU beim Lesen und Schreiben von Speicherdaten zweimal auf den Hauptspeicher zugreifen (Abfrage der Seitentabelle und Zugriff auf die Zieladresse).

Mit der schnellen Tabelle muss manchmal nur einmal auf den Cache-Speicher und den Hauptspeicher zugegriffen werden, was die Suche beschleunigen und die Befehlsausführungsgeschwindigkeit erhöhen kann.

3. Seitenersetzungsalgorithmus

Wenn ein Prozess ausgeführt wird und die Seite, auf die er zugreift, nicht im Speicher ist und importiert werden muss, aber

kein freier Speicherplatz im Speicher vorhanden ist

, wird eine Seite von Das Programm muss aus dem Speicher aufgerufen werden Oder Daten werden an den Auslagerungsbereich der Festplatte gesendet.
Der Algorithmus zur Auswahl der aufzurufenden Seite wird als Seitenersetzungsalgorithmus bezeichnet
. Ein guter Seitenersetzungsalgorithmus sollte eine „niedrige Seitenersetzungshäufigkeit“ haben, das heißt, Seiten, auf die in Zukunft nicht mehr oder für längere Zeit nicht zugegriffen wird, sollten zuerst aufgerufen werden. 3.1 Optimaler Ersetzungsalgorithmus (OPT)

Bester (Optimaler, OPT) Ersetzungsalgorithmus Die ausgewählte entfernte Seite wird in Zukunft nie mehr verwendet oder wird in der längsten besuchten Zeit nicht mehr verwendet Seiten, um die niedrigste Seitenfehlerrate zu gewährleisten.

Aber weil die Menschen derzeit nicht vorhersagen können, auf welche der Tausenden von Seiten im Speicher des Prozesses in der Zukunft am längsten nicht mehr zugegriffen werden wird, kann

dieser Algorithmus nicht implementiert werden

, der beste Ersatzalgorithmus jedoch schon zur Bewertung anderer Algorithmen verwendet werden. Angenommen, das System weist einem Prozess drei physische Blöcke zu und berücksichtigt die folgende Seitenzahl-Referenzzeichenfolge: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Wenn der Prozess läuft, werden zunächst die drei Seiten 7, 0 und 1 nacheinander in den Speicher geladen. Wenn der Prozess auf Seite 2 zugreifen möchte, kommt es zu einem Seitenfehler-Interrupt. Gemäß dem optimalen Ersetzungsalgorithmus wird Seite 7 ausgewählt und entfernt, die erst nach dem 18. Zugriff übertragen werden muss. Wenn dann auf Seite 0 zugegriffen wird, muss kein Seitenfehler-Interrupt generiert werden, da diese bereits im Speicher vorhanden ist. Wenn auf Seite 3 zugegriffen wird, wird Seite 1 basierend auf dem optimalen Ersetzungsalgorithmus entfernt ... und so weiter. Aus der Abbildung können wir die Situation bei Verwendung des optimalen Ersetzungsalgorithmus ersehen.

Verschiebungskarte bei Verwendung des optimalen Verschiebungsalgorithmus

7Physischer Block 17 222270040 001. 33311√√√√√√√

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

7

7

2

.

Physikblock 2

0

0

Physikblock 3

1

Fehlende Seite Nr.

√

Es ist ersichtlich, dass die Anzahl der Seitenfehlerunterbrechungen 9 und die Anzahl der Seitenersetzungen 6 beträgt.

3.2 Der FIFO-Seitenersetzungsalgorithmus (First-In-First-Out)

gibt der Eliminierung der Seite Priorität, die am frühesten in den Speicher gelangt, d. h. der Seite, die sich am längsten im Speicher befindet.

Dieser Algorithmus ist einfach zu implementieren. Sie müssen lediglich die in den Speicher übertragenen Seiten entsprechend der Reihenfolge in eine Warteschlange verknüpfen und einen Zeiger festlegen, der immer auf die früheste Seite zeigt. Dieser Algorithmus eignet sich jedoch nicht für die tatsächlichen Ablaufregeln des Prozesses, da während des Prozesses häufig auf einige Seiten zugegriffen wird.

224400... 0 7. Physischer Block 2 22211100Physischer Block 30√√√

Seite besuchen

7

0

1

2

0

3

0

4

2

3.

0

7

7

7

2

4

77

1

1

1

0

0

3

3

3

2

2

2

1

Fehlende SeiteNein

√

√

√

√

√

√√

√

√

√

√

√

Bei Verwendung des FIFO-Algorithmus werden 12 Seitenersetzungen durchgeführt, was genau doppelt so viele ist wie beim optimalen Ersetzungsalgorithmus.

Der FIFO-Algorithmus erzeugt auch ein abnormales Phänomen, bei dem die Anzahl der Seitenfehler zunimmt, anstatt zu sinken. Dies wird 1969 von Belady entdeckt und wird daher als „Belady-Anomalie“ bezeichnet in der Tabelle unten dargestellt.

2 21132... √√ √ Vergleich nach Erhöhung der Anzahl der physikalischen Blöcke5421333 22Physische Blöcke 4*√

Seite besuchen

1

2

3

4

1

2

5

1

2

3

4

5

Physische Blöcke 1.

1.

1

Physikblock 2

2

1

3

3

Physischer Block 3.

3

3

2

2

√

√

√

√

Physischer Block 1*

1

1

1

1

5

5

5

4

Physikalische Blockade 2

2

2

1

1

1

5

Physikblock 3*

3

2

2

4

4

4...

√

√

√

√

√

Nur beim FIFO-Algorithmus können Belady-Anomalien auftreten, während bei den LRU- und OPT-Algorithmen niemals Belady-Anomalien auftreten.

3.3 LRU-Ersetzungsalgorithmus (Least Recent Used) Es wird davon ausgegangen, dass Seiten, die in der vergangenen Zeit nicht besucht wurden, in naher Zukunft möglicherweise nicht mehr besucht werden. Dieser Algorithmus legt für jede Seite ein

Besuchsfeld

fest, um die Zeit aufzuzeichnen, die seit dem letzten Zugriff auf die Seite vergangen ist. Wählen Sie beim Entfernen von Seiten diejenige mit dem größten Wert unter den vorhandenen Seiten aus, die entfernt werden sollen.

224011Physische Blockade 2000Physischer Block 3. 122√√√√√√√√

Seite besuchen

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0... Blöcke 1

7

7

7

4

4

1

0

0

0

0

0

3

3

3

1

3

3

2

2

2

7

Fehlende Seite Nr.

√

√

√

√

LRU bietet eine bessere Leistung, erfordert jedoch Hardwareunterstützung für Register und Stapel und ist teurer.

LRU ist ein Algorithmus der Stack-Klasse. Theoretisch kann bewiesen werden, dass in Stapelalgorithmen keine Belady-Ausnahme auftreten kann. Der FIFO-Algorithmus basiert auf einer Warteschlange und nicht auf einem Stapelalgorithmus.

3.4 Clock (CLOCK)-Ersetzungsalgorithmus

Die Leistung des LRU-Algorithmus ähnelt der von OPT, ist jedoch schwierig zu implementieren und teuer. Der FIFO-Algorithmus ist einfach zu implementieren, weist jedoch eine schlechte Leistung auf. Daher haben Betriebssystementwickler viele Algorithmen ausprobiert und versucht, die Leistung von LRU mit relativ geringem Overhead zu erreichen. Bei diesen Algorithmen handelt es sich allesamt um Varianten des CLOCK-Algorithmus.

Der einfache CLOCK-Algorithmus ordnet jedem Frame ein zusätzliches Bit zu, das als Nutzungsbit bezeichnet wird. Wenn eine Seite zum ersten Mal in den Hauptspeicher geladen und anschließend darauf zugegriffen wird, wird das Nutzungsbit auf 1 gesetzt.

Für den Seitenersetzungsalgorithmus wird der Satz von Kandidatenrahmen für die Ersetzung als Kreispuffer betrachtet und mit einem Zeiger verknüpft. Wenn eine Seite ersetzt wird, wird der Zeiger so eingestellt, dass er auf den nächsten Frame im Puffer zeigt.

Wenn es Zeit ist, eine Seite zu ersetzen, durchsucht das Betriebssystem den Puffer, um den ersten Frame mit einem Nutzungsbit von 0 zu finden. Immer wenn ein Frame mit einem Nutzungsbit von 1 auftritt, setzt das Betriebssystem das Bit auf 0 zurück. Wenn alle Frames ein Nutzungsbit von 1 haben, schließt der Zeiger einen Zyklus im Puffer ab, wodurch alle Nutzungsbits auf 0 gesetzt werden an der ursprünglichen Position und ersetzt die Seite im Rahmen. Da dieser Algorithmus den Status jeder Seite zyklisch überprüft, wird er CLOCK-Algorithmus genannt, auch bekannt als „Not Latest Used (NRU)“-Algorithmus. Die Leistung des CLOCK-Algorithmus kommt der von LRU relativ nahe, und durch Erhöhen der Anzahl der verwendeten Bits kann der CLOCK-Algorithmus effizienter gemacht werden. Durch Hinzufügen eines

modifizierten Bits modifiziert

zum verwendeten Bit erhalten wir einen verbesserten CLOCK-Ersetzungsalgorithmus. Jeder Frame befindet sich in einer der folgenden vier Situationen:

wurde in letzter Zeit nicht aufgerufen und wurde nicht geändert (u=0, m=0).

• wurde kürzlich aufgerufen, aber nicht geändert (u=1, m=0).

• wurde in letzter Zeit nicht besucht, wurde aber geändert (u=0, m=1).

• wurde kürzlich aufgerufen und geändert (u=1, m=1).

• Der Algorithmus führt die folgenden Schritte aus:

Scannen Sie ausgehend von der aktuellen Position des Zeigers den Bildpuffer. Während dieses Scans werden keine Änderungen an den Nutzungsbits vorgenommen. Der erste gefundene Frame (u=0, m=0) wird zum Ersetzen ausgewählt.

• Wenn Schritt 1 fehlschlägt, scannen Sie erneut und suchen Sie den Rahmen von (u=0, m=1). Der erste gefundene Frame wird zum Ersetzen ausgewählt. Während dieses Scans wird für jedes übersprungene Frame das Nutzungsbit auf 0 gesetzt.

• Wenn Schritt 2 fehlschlägt, kehrt der Zeiger zu seiner ursprünglichen Position zurück und die verwendeten Bits aller Frames im Satz sind 0. Wiederholen Sie Schritt 1 und ggf. Schritt 2. Dadurch werden Rahmen zum Austausch gefunden.

• Der verbesserte CLOCK-Algorithmus ist besser als der einfache CLOCK-Algorithmus, da
Seiten, die sich nicht geändert haben, beim Ersetzen bevorzugt werden

. Das spart Zeit, da

geänderte Seiten vor dem Ersetzen zurückgeschrieben werden müssen. 4. Seitenzuordnungsstrategie Daher muss das Betriebssystem entscheiden, wie viele Seiten gelesen werden sollen. Das heißt, wie viel Hauptspeicherplatz einem bestimmten Prozess zugewiesen werden soll, dabei müssen die folgenden Punkte berücksichtigt werden:

Je kleiner die einem Prozess zugewiesene Speichermenge ist, desto kleiner ist die Anzahl der Prozesse, die sich im Hauptspeicher befinden zu jeder Zeit Je mehr, desto effizienter kann die Zeitausnutzung des Prozessors sein.

Wenn ein Prozess zu wenige Seiten im Hauptspeicher hat, ist die Seitenfehlerrate

trotz des Lokalitätsprinzips immer noch relativ hoch.

Wenn

die Anzahl der Seiten zu groß ist
• , hat die Zuweisung von mehr Hauptspeicherplatz für einen bestimmten Prozess aufgrund des Lokalitätsprinzips keinen offensichtlichen Einfluss auf die Fehlerrate des Prozesses.

• Basierend auf diesen Faktoren verfolgen moderne Betriebssysteme normalerweise drei Strategien:

  Lokaler Ersatz mit fester Zuweisung

  : Es weist jedem Prozess eine bestimmte Anzahl physischer Blöcke zu,
ändert sich während des gesamten Laufs nicht
• . Wenn während der Ausführung des Prozesses ein Seitenfehler auftritt, können Sie nur eine Seite aus den Seiten im Speicher des Prozesses auswählen und auslagern und dann die erforderliche Seite laden. Es ist schwierig, die Anzahl der physischen Blöcke zu bestimmen, die jedem Prozess bei der Implementierung dieser Strategie zugewiesen werden sollten: Zu wenige führen zu häufigen Seitenfehlern und zu viele verringern die CPU- und andere Ressourcenauslastung.

Globale Ersetzung der Variablenzuweisung

: Dies ist die am einfachsten zu implementierende Strategie zur Zuweisung und Ersetzung physischer Blöcke. Jedem Prozess im System wird eine bestimmte Anzahl physischer Blöcke zugewiesen, und das Betriebssystem selbst unterhält auch eine Warteschlange mit freien physischen Blöcken Blöcke. Wenn in einem Prozess ein Seitenfehler auftritt, entnimmt das System einen physischen Block aus der Warteschlange für freie physische Blöcke, weist ihn dem Prozess zu und lädt die zu ladende Seite in ihn.

Variable Zuweisung lokaler Ersatz: Es wird jedem Prozess eine bestimmte Anzahl physischer Blöcke zugewiesen. Wenn in einem Prozess ein Seitenfehler auftritt, darf nur eine Seite aus den Speicherseiten des Prozesses ausgelagert werden Der Betrieb anderer Prozesse wird dadurch nicht beeinträchtigt. Wenn der Prozess häufig Seiten verpasst , während der Prozess ausgeführt wird, weist das System dem Prozess eine Reihe physischer Blöcke zu, bis die Seitenfehlschlagsrate des Prozesses auf ein angemessenes Niveau tendiert, umgekehrt, wenn der Prozess eine hat Besonders niedrige Page-Miss-Rate während der Ausführung. Dann können Sie die Anzahl der dem Prozess zugewiesenen physischen Blöcke entsprechend reduzieren.

4.2 Zeitpunkt des Ladens von Seiten

Um den Zeitpunkt des Systemladens von Seiten zu bestimmen, die bei laufendem Prozess fehlen, können die folgenden zwei Paging-Strategien angewendet werden:

• Pre-Paging-Strategie

  : Nach dem Lokalitätsprinzip kann das gleichzeitige Laden mehrerer benachbarter Seiten effizienter sein als das Laden einer Seite nach dem anderen. Wenn jedoch auf die meisten geladenen Seiten nicht zugegriffen wurde, ist dies ineffizient. Daher ist es notwendig, eine vorhersagebasierte Pre-Paging-Strategie zu verwenden, um Seiten, auf die voraussichtlich in naher Zukunft zugegriffen wird, vorab in den Speicher zu laden. Allerdings liegt die aktuelle Erfolgsquote vorab angepasster Seiten nur bei etwa 50 %. Daher wird diese Strategie hauptsächlich verwendet, wenn der Prozess zum ersten Mal geladen wird und der Programmierer angibt, welche Seiten zuerst geladen werden sollen. Paging anfordern

  Strategie
: Die
• Seite, auf die der Prozess während des Betriebs zugreifen muss, befindet sich nicht im Speicher und es wird eine Anfrage

  gestellt und das System überträgt die erforderliche Seite in den Speicher. Auf die mit dieser Strategie übertragenen Seiten wird definitiv zugegriffen, und diese Strategie ist relativ einfach zu implementieren, sodass diese Strategie hauptsächlich in aktuellen virtuellen Speichern verwendet wird. Der Nachteil besteht darin, dass jeweils nur eine Seite geladen wird. Wenn viele Seiten geladen und geladen werden, wird zu viel E/A-Overhead verbraucht. 4.3 Von wo soll die Seite geladen werden? Swap-Bereich. Der Swap-Bereich verwendet normalerweise die kontinuierliche Zuordnungsmethode, während der Dateibereich die diskrete Zuordnungsmethode verwendet, sodass die Festplatten-E/A-Geschwindigkeit des Swap-Bereichs schneller ist als die des Dateibereichs. Es gibt drei Situationen, in denen Seiten übertragen werden können:

Das System verfügt über genügend Swap-Bereichsplatz: Sie können alle erforderlichen Seiten aus dem Swap-Bereich übertragen, um die Seitenübertragungsgeschwindigkeit zu erhöhen. Aus diesem Grund müssen vor der Ausführung des Prozesses die mit dem Prozess verbundenen Dateien aus dem Dateibereich

in den Swap-Bereich kopiert werden.

Dem System fehlt genügend Platz im Auslagerungsbereich: Alle Dateien, die nicht geändert werden, werden direkt aus dem Dateibereich übertragen (kein Zurückschreiben beim Auslagern erforderlich). Teile, die geändert werden können, müssen jedoch beim Austausch in den Austauschbereich übertragen und bei späterem Bedarf wieder aus dem Austauschbereich zurückübertragen werden. UNIX-Methode: Mit dem Prozess verbundene Dateien werden im Dateibereich abgelegt, daher sollten Seiten, die nicht ausgeführt wurden, aus dem Dateibereich geladen werden

. Seiten, die zuvor ausgeführt, aber ausgelagert wurden, werden im Auslagerungsbereich abgelegt, sodass sie beim nächsten Mal aus dem Auslagerungsbereich geladen werden sollten. Wenn die vom Prozess angeforderte gemeinsam genutzte Seite von anderen Prozessen in den Speicher übertragen wird, besteht keine Notwendigkeit, sie aus dem Auslagerungsbereich zu übertragen. 5. Seiten-Jitter (Bump) und Arbeitssatz (Resident Set) Die ausgelagerte Seite wird sofort in den Hauptspeicher ausgelagert und die Seite, die gerade ausgelagert wurde, wird sofort aus dem Hauptspeicher ausgelagert. Dieses

häufige Seitenplanungsverhalten wird als Jitter oder Turbulenz bezeichnet. Wenn ein Prozess mehr Zeit mit dem Paging verbringt, als er zur Ausführung benötigt, liegt ein Thrashing-Prozess vor.

• Seitenfehlerunterbrechungen (Jitter) treten häufig auf, weil die Anzahl der Seiten, auf die ein Prozess häufig zugreift, höher ist als die Anzahl der verfügbaren physischen Seitenrahmen. Durch die virtuelle Speichertechnologie können mehr Prozesse im Speicher gehalten werden, um die Systemeffizienz zu verbessern. Im eingeschwungenen Zustand ist fast der gesamte Hauptspeicher durch Prozessblöcke belegt und Prozessor und Betriebssystem haben direkten Zugriff auf möglichst viele Prozesse. Bei unsachgemäßer Verwaltung verbringt der Prozessor jedoch die meiste Zeit damit, Blöcke auszutauschen, also den Vorgang zum Laden von Seiten anzufordern, anstatt die Anweisungen des Prozesses auszuführen, was die Systemeffizienz erheblich verringert. 5.2 Arbeitsset (Resident-Set)

• Der Arbeitssatz (oder residente Satz) bezieht sich auf den Satz von Seiten , auf die ein Prozess innerhalb eines bestimmten Intervalls zugreifen muss. Seiten, die häufig verwendet werden, müssen im Arbeitssatz enthalten sein, während Seiten, die längere Zeit nicht verwendet wurden, aus dem Arbeitssatz verworfen werden. Um eine Überlastung des Systems zu verhindern, müssen Sie eine geeignete Arbeitssatzgröße auswählen.
  
  Das Prinzip des Arbeitssatzmodells besteht darin, das Betriebssystem den Arbeitssatz jedes Prozesses verfolgen zu lassen und dem Prozess physische Blöcke zuzuweisen, die größer als sein Arbeitssatz sind. Wenn freie physische Blöcke vorhanden sind, können Sie einen anderen Prozess in den Speicher verlagern, um die Anzahl der Multiprogramme zu erhöhen. Wenn die Summe aller Arbeitssätze die Gesamtzahl der verfügbaren physischen Blöcke übersteigt, pausiert das Betriebssystem einen Prozess, lagert ihn aus und weist seine physischen Blöcke anderen Prozessen zu, um Thrashing zu verhindern.
  
  Die richtige Wahl der Größe des Arbeitssatzes hat einen wichtigen Einfluss auf die Speicherauslastung und die Verbesserung des Systemdurchsatzes.

  6. Zusammenfassung Die Verwaltungsmethode

  Paging und die Verwaltungsmethode Segmentierung sind an vielen Stellen ähnlich, z. B. ist der Speicher diskontinuierlich und es gibt Adressübersetzungsmechanismen für die Adresszuordnung usw. Es gibt jedoch viele Unterschiede zwischen den beiden. Tabelle 3-20 listet den Vergleich zwischen der Paging-Management-Methode und der Segmentierungs-Management-Methode in verschiedenen Aspekten auf.

  besser zu erfüllen. Die Größe der Seite wird vom System festgelegt und bestimmt. Das System unterteilt die logische Adresse in zwei Teile: Seitennummer und Intra -Seitenadresse. Sie wird von der Maschinenhardware implementiert, daher kann es nur eine Seitengröße im System geben. Die Länge des Segments ist nicht festgelegt und hängt vom vom Benutzer geschriebenen Programm ab Basierend auf den Informationen. So teilen Sie den Der Jobadressraum ist eindimensional, dh ein einzelner linearer Adressraum. Der Programmierer muss nur ein Speichersymbol verwenden, um eine Adresse darzustellen

  	Paging	Segmentierung
  Zweck	Seite ist die physische Informationseinheit, Paging ist eine Möglichkeit, diskrete Zuordnung zu reduzieren den externen Anteil des Speichers und bereitstellen hohe Speicherauslastung. Mit anderen Worten, Paging ist nur auf die Bedürfnisse der Systemverwaltung und nicht auf die Bedürfnisse der Benutzer zurückzuführen. Es handelt sich um eine logische Informationseinheit, die eine Reihe von Informationen enthält, deren Bedeutung relativ vollständig ist. Der Zweck der Segmentierung besteht darin, die Bedürfnisse der Benutzer	Länge
  	Adressraum	Der Job Der Adressraum ist zweidimensional. Beim Identifizieren einer Adresse muss der Programmierer sowohl den Segmentnamen als auch die Adresse innerhalb des Segments angeben Fragmente, keine internen Fragmente

Das obige ist der detaillierte Inhalt vonWas verwendet Linux, um virtuellen Speicher zu implementieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!