Verstehen Sie das Prinzip des Seitenersetzungsalgorithmus anhand von Codebeispielen

Algorithmus zum Ersetzen von Seiten: Das Wesentliche besteht darin, den begrenzten Speicher in die Lage zu versetzen, drahtlose Prozesse zu erfüllen.

Erklären Sie zunächst den Prozess der Behandlung von Seitenfehlern:

Die Paging-Hardware bemerkt, dass das Ungültigkeitsbit gesetzt ist, wenn die Adresse durch die Seitentabellen übersetzt wird, und blockiert so das Betriebssystem. Dieser Fehler wird dadurch verursacht, dass das Betriebssystem die erforderliche Seite nicht in den Speicher laden kann.

Umgang mit Seitenfehlern:

1. Überprüfen Sie die interne Tabelle dieses Prozesses, um festzustellen, ob es sich bei der Referenz um einen gültigen Speicherzugriff handelt (es kann davon ausgegangen werden, dass dieser Speicher vom aktuellen Prozess verwendet werden kann). Wenn es ungültig ist, beenden Sie den Prozess direkt. Wenn es gültig ist, die Seite jedoch nicht in den Speicher geladen wurde, laden Sie die Seite in den Speicher.

2. Suchen Sie dann in der Liste der Leerlaufframes nach einem Leerlaufframe.

3. Planen Sie die Festplatte so ein, dass sie den vom Prozess benötigten Speicher in den Seitenrahmen liest.

4. Nachdem der Lesevorgang von der Festplatte abgeschlossen ist, ändern Sie die Seitentabelle so, dass der freie Rahmen der Seitenzahl entspricht. Und ändern Sie das Gültig-Ungültig-Bit der Seitentabelle in Gültig.

Beachten Sie einige Flags in der Seitentabelle:

Änderungsbit: Wenn das effektive Bit 1 ist, bedeutet dies, dass es geändert wurde. Daher muss der Speicher beim Ersetzen der Seite auf die Festplatte geschrieben werden. Wenn es 0 ist, bedeutet dies, dass es nicht geändert wurde. Daher wird der Seitenersetzungsalgorithmus verwendet, um es direkt freizugeben.

Schutzbit: Kann als schreibgeschützt markiert werden.

Gültig-Ungültig-Bit: i: Gibt an, dass die logische Seitennummer nicht dem physischen Seitenrahmen entspricht. V gibt an, dass ein entsprechender physischer Seitenrahmen vorhanden ist.

Algorithmus zum Ersetzen von Seiten:

FIFO: Algorithmus

Das Betriebssystem ersetzt immer die Seite, die am längsten im Speicher verblieben ist. Ein Zeiger kann verwendet werden, um auf diese Stelle zu zeigen (der Mehraufwand ist sehr gering und kann mithilfe einer Warteschlange implementiert werden. Immer wenn ein Seitenfehler auftritt, wird die letzte Seite entfernt und eine neue Seite am Anfang der Warteschlange hinzugefügt. Wenn kein Seitenfehler auftritt, muss die Warteschlange nicht bedient werden).

LRU-Algorithmus: Das Betriebssystem ersetzt immer die Seite im Speicher, die am längsten nicht verwendet wurde: Wir können eine verknüpfte Liste verwenden, um diesen Algorithmus zu implementieren. Der Tabellenkopf gibt die zuletzt verwendete Seite an, und das Tabellenende gibt die Seite an, die am längsten nicht verwendet wurde. Unabhängig davon, ob ein Seitenfehler auftritt, muss die verknüpfte Liste jedes Mal durch Hinzufügen, Löschen, Ändern und Überprüfen überprüft werden, um sicherzustellen, dass jede verknüpfte Liste das ist, was wir benötigen (der Aufwand ist zu hoch).

Ungefährer LRU-Algorithmus: Wir fügen der Seitentabelle eine Referenzbituhr hinzu. Wenn die Uhr 1 ist, kann sie nicht herausgezogen werden. Wenn die Uhr 0 ist, bedeutet dies, dass sie entfernt werden kann.

Prozedur t: {
  Zeiger p: zeigt auf die aktuelle Seite p = 0; // zeigt auf die Anfangsposition boolean: Flag-Bit-Uhr
  Die zirkuläre verknüpfte Liste aller im Prozess enthaltenen Seiten: linklist //Wenn der Prozess ausgeführt wird, ist die verknüpfte Liste vorhanden. Wenn der Prozess endet, verschwindet die verknüpfte Liste, während (Prozess ausgeführt wird) {
    
    wenn(p.clock == 1){
      p.Uhr = 0;
      p++; // Zeiger zeigt auf das nächste }
    wenn(p.clock == 0){
      Löschen Sie die Seite, auf die p zeigt, und fügen Sie bei p eine neue Seite hinzu.
      p.Uhr = 1;
      p++;
    }
  }
}

Ungefährer erweiterter LRU-Algorithmus: Kombinieren Sie das Änderungsbit und das Referenzbit als Ersetzungsbedingung: Wenn (Änderungsbit, Referenzbit) = (0, 0) ist, bedeutet dies, dass es ersetzt werden kann

Prozedur t: {
  Zeiger p: zeigt auf die aktuelle Seite p = 0; // zeigt auf die Anfangsposition boolean: Flag-Bit-Uhr
  Boolesch: Bit m ändern
  Die zirkuläre verknüpfte Liste aller im Prozess enthaltenen Seiten: linklist //Wenn der Prozess ausgeführt wird, ist die verknüpfte Liste vorhanden. Wenn der Prozess endet, verschwindet die verknüpfte Liste, während (Prozess ausgeführt wird) {
    
  
    wenn(p.(Uhr,m) == (0,0)){
      
      Löschen Sie die Seite, auf die p zeigt, und fügen Sie bei p eine neue Seite hinzu.
      p.(Uhr,m) = (1,0);
      p++;
    }
    wenn(p.(Uhr,m) == (0,1)){
      
      
      p.(Uhr,m) = (0,0);
      p++;
    }
    wenn(p.(Uhr,m) == (1,0)){
      
      
      p.(Uhr,m) = (0,0);
      p++;
    }
    wenn(p.(Uhr,m) == (1,1)){
      
      p.(Uhr,m) = (0,1);
      p++;
    }
    if (Seite ändern) {
      p.(Uhr,m) = (1,1);
      p++
    }
    if (Seite lesen) {
      p.(Uhr,m) = (1,0);
      p++;
    }
  }
}

Seitenpufferalgorithmus: Das Betriebssystem reserviert einen Pool freier Frames.

Wenn ein Seitenfehler auftritt, liest die erforderliche Seite den freien Frame und legt den ersetzten Opfer-Frame in den Pufferpool. Während der Paging-Leerlaufzeit wird der Inhalt des Opfer-Frames im Pufferpool auf die Festplatte geschrieben (wenn das Änderungsbit in der Seitentabelle 1 ist) (wodurch der Prozess des direkten Festplattenzugriffs während des Paging des Betriebssystems reduziert und die Paging-Effizienz verbessert wird).

Die zweite Methode besteht darin, den Inhalt des Opferrahmens auf die Festplatte zu schreiben, den Inhalt des Rahmens jedoch nicht freizugeben, da der Prozess möglicherweise die vorherige Seite aufruft, sodass der Rahmen im Pufferpool direkt in den Speicher geschrieben wird, wodurch (der Vorgang des Lesens von Daten von der Festplatte) reduziert wird.

Bei den oben genannten Algorithmen handelt es sich um lokale Seitenersetzungsvorgänge, bei denen es sich um Seitenersetzungsvorgänge handelt, die innerhalb eines einzelnen Prozesses ausgeführt werden. Während des Betriebs des Betriebssystems können jedoch verschiedene Prozesse parallel ausgeführt werden, sodass die Seitenersetzung nicht auf einen einzelnen Prozess beschränkt ist.

Als nächstes lernen wir den globalen Ersetzungsalgorithmus: Wir geben einen Arbeitssatz und einen Residentsatz an. Der Arbeitssatz gibt die Δ-Seiten an, auf die das aktuelle Programm zugreifen muss, und der Residentsatz gibt die Seiten an, die das Betriebssystem verwendet.

Arbeitssatz: WS(Δ, t) = {} Der Arbeitssatz wird ständig verschoben, und das Betriebssystem ersetzt Seiten, die nicht im Arbeitssatz enthalten sind.

Algorithmus zum dynamischen Ersetzen von Seiten im Arbeitssatz: Wie in der folgenden Abbildung dargestellt, legen wir einen Schwellenwert für die Fenstergröße = 2 fest. Wir verwenden die Differenz zwischen zwei Seitenfehlerunterbrechungen (die angibt, wie oft es zwischen den beiden Unterbrechungen keine Unterbrechungen gab), um sie mit dem Schwellenwert zu vergleichen. Wenn sie größer als der Schwellenwert ist, werden die Seiten des aktuellen Arbeitssatzes nicht mehr ausgelagert und die Größe des Arbeitssatzes wird zurückgesetzt. Wenn sie kleiner als der Schwellenwert ist, werden die fehlenden Seiten in den Arbeitssatz ausgelagert und die Größe des Arbeitssatzes wird zurückgesetzt.

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, er wird für jedermanns Studium hilfreich sein. Ich hoffe auch, dass jeder 123WORDPRESS.COM unterstützen wird.