3.3.2.2.3 Seitenersetzungsverfahren

[gesichtete Version][gesichtete Version]
Keine Bearbeitungszusammenfassung
 
(58 dazwischenliegende Versionen von 5 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
<p>
<p>
Tritt bei der Adressumrechnung in der MMU ein Page fault auf, so muss das Betriebssystem dafür sorgen, dass die benötigte virtuelle Seite aus dem Hintergrundspeicher in einen freien Seitenrahmen des physikalischen Speichers eingelagert wird.
In der [[Was_bei_der_Seitenersetzung_passiert|vorangegangenen Auflistung]] findet sich u.a. der Punkt "''Die zu ersetzende Seite E wird bestimmt,...''", und es stellt sich die Frage:
</p>
</p>


<p>
<p>
Steht derzeit aber kein freier Seitenrahmen zur Verfügung, so ist es die Aufgabe des implementierten Seitenersetzungsverfahrens zu entscheiden, welche momentan eingelagerte virtuelle Seite in den Hintergrundspeicher verschoben wird. Dadurch wird dann (mindestens) ein freier Seitenrahmen geschaffen, die benötigte virtuelle Seite kann eingelagert werden, und die MMU kann die zuvor gescheiterte Adressumrechnung erneut durchführen.
<loop_area type="question">
</p>
 
<br />
==== Was bei der Seitenersetzung passiert ====
<p>
<p>
Eine einfache Beschreibung des Ablaufs einer Seitenersetzung ist wie folgt:
'''Wie''' wird die zu ersetzende Seite bestimmt?
</p>
</p>
<p>
</loop_area>
# Die MMU stellt fest, dass die benötigte virtuelle Seite B nicht in einem Seitenrahmen eingelagert ist und löst deshalb einen Page fault aus.
# Es wird festgestellt, dass kein freier Seitenrahmen mehr verfügbar ist, das Seitenersetzungsverfahren wird deshalb gestartet.
# Die zu ersetzende Seite E wird bestimmt, sie ist derzeit in Seitenrahmen X eingelagert.
# Die zu ersetzende Seite E wird in den Hintergrundspeicher geschrieben. Damit ist ihr Inhalt gesichert, sie kann später wieder eingelagert werden.
# Die benötigte Seite B wird eingelagert, d.h. ihr Inhalt wird in den Seitenrahmen X geschrieben. Das Ersetzungsverfahren ist damit abgeschlossen.
</p>
</p>


<br />
<br />
<p>
<p>
<loop_area type="important">
Diese Aufgabe wird von einem sogenannten Seitenersetzungsalgorithmus erledigt.
<p>
Das Schreiben der zu ersetzenden Seite E in den Hintergrundspeicher kostet viel Zeit! Das ist schlecht für die Performanz des Gesamtsystems.</p>
</loop_area>
</p>
</p>
 
<p>  
<br />
Im Laufe der Entwicklungsgeschichte von Betriebssystemen wurden eine ganze Reihe verschiedener Seitenersetzungsverfahren (oder Verdrängungsstrategien) vorgeschlagen bzw. implementiert, u.a.:
<p>
Es ist deshalb sinnvoll, eine zu ersetzende Seite nur dann in den Hintergrundspeicher zu kopieren, wenn dies auch tatsächlich notwendig ist.
</p>
</p>


<p>
<p>
Eine Seite kann beispielsweise den Programmtext oder die Daten eines Prozesses enthalten.
<loop_index id="5fa9787a94f4b">Optimaler Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac51ba">NRU, Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac51ca">Not Recently Used Algorithmus</loop_index><loop_index id="5fa9787ac51d6">FIFO, Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac51e3">First In First Out Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac51f0">Second Chance Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac51fb">Clock Page Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac5205">LRU, Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac520d">Least Recently Used Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac5216">NFU, Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac521f">Not Frequently Used Seitenersetzungsalgorithmus</loop_index><loop_index id="5fa9787ac5228">Working Set Seitenersetzungsalgorithmus</loop_index>
* Optimaler Algorithmus
* NRU - Not Recently Used Algorithmus
* FIFO - First In First Out Algorithmus
* Second Chance Algorithmus
* Clock Page Algorithmus
* LRU - Least Recently Used Algorithmus
* NFU - Not Frequently Used Algorithmus
* Working Set Algorithmus
</p>
</p>


<br />
<br />
==== Aufgabe 1 ====
<p>
<p>
<loop_area type="task">
<loop_area type="notice">'''Weiterführende Literatur'''
<loop_task title="Wenn eine Seite Programmtext enthält">
<p>
<p>
Eine zu ersetzende Seite enthält lediglich Programmtext (also den ausführbaren Maschinencode mit den Befehlen) eines Prozesses. Diese Inhalte dürfen während der Ausführung des zugehörigen Prozesses nicht verändert werden.
<cite id="5fa9787a94f54">Mandl+2013</cite> erläutert die genannten Algorithmen in den Kapiteln 7.2.3 und 7.2.4. Die Lektüre dieser Quelle sei ausdrücklich empfohlen.
</p>
</p>
<p>
<p>
Ist es erforderlich, diese Seite in den Hintergrundspeicher auszulagern, oder kann die dafür benötite Zeit eingespart werden? Erläutere deine Antwort!
<small>Studierende sind oftmals berechtigt, eine PDF-Version dieses Buches ohne entstehende Kosten [[Hinweise für Studierende#Downloadbare Bücher von Springerlink|über ihre Hochschulen von Springerlink zu beziehen.]]</small>
</p>
</p>
</loop_task>
</loop_area>
</loop_area>
</p>
</p>


<br />
<br />
==== Aufgabe 2 ====
<p>
<loop_area type="task">
<loop_task title="Wenn eine Seite Daten enthält">
<p>
<p>
Eine zu ersetzende Seite enthält Daten. Diese Inhalte können verändert worden sein, müssen aber es nicht.
Einige der genannten Algorithmen werden auf den folgenden Seiten behandelt. Die ausführlichere Besprechung aller Verfahren leistet jedoch nur die weiterführende Literatur.
</p>
</p>
<br />
<p>
<p>
Ist es erforderlich, diese Seite in den Hintergrundspeicher auszulagern, oder kann die dafür benötite Zeit eingespart werden? Erläutere deine Antwort!
<loop_area type="notice">
</p>
<p>
<p>
Betrachte folgende Situationen:
Beim Durcharbeiten der genannten Kapitel bei <cite id="5fa9787a94f5b">Mandl+2013</cite> kann man sehr schön die ''Evolution der Algorithmen'' verfolgen. D.h. ein späteres Verfahren beruht sehr oft auf einem vorangegangenen Verfahren, wobei jedoch ein vorheriger Nachteil verbessert wurde.<br />
* Die Inhalte der Seite wurden verändert, weil Werte in Speicherzellen dieser Seite geschrieben wurden.
Achte mal darauf!
* Die Inhalte der Seite wurden nicht verändert, zudem befindet sich eine Kopie der Seite bereits im Hintergrundspeicher, weil sie zu einem früheren Zeitpunkt bereits einmal ausgelagert war.
</p>
</p>
</loop_task>
</loop_area>
</loop_area>
</p>
</p>
Zeile 74: Zeile 60:
<br />
<br />


==== to do ====
== So geht es weiter:==
<p>
<p>
Im Laufe der Entwicklungsgeschichte von Betriebssystemen wurden eine ganze Reihe von Seitenersetzungsverfahren vorgeschlagen:
<loop_area type="arrangement"><loop_toc>  </loop_toc></loop_area>
</p>
</p>


<br />
== Aufgabe 1 ==
<p>
<loop_area type="task">
<loop_task title="Die MMU und Seitenersetzungsverfahren" id="5fa9787a94f62">
<p>
<p>
* Optimaler Algorithmus
In diesem Kapitel wird beschrieben, dass ein Seitenersetzungsverfahren zum Einsatz kommt, wenn bei der Umrechnung einer virtuellen Adresse in eine physikalische Adresse auf der MMU ein Seitenfehler (page fault) ausgelöst wird.</p>
* NRU
<p>
* FIFO
Was ist jedoch im anderen Fall:<br />
* Second Chance
Eine virtuelle Adresse kann von der MMU erfolgreich in eine physikalische Adresse umgerechnet werden, es tritt also '''kein''' Seitenfehler auf.</p>
* Clock Page
<p>
* LRU
Kommt dann auch ein Seitenersetzungsverfahren zum Einsatz?
* NFU
</p>
</p>
 
</loop_task>
<p>
</loop_area>
Siehe <cite>Mandl+2013</cite> Kap. 7.2.3, 7.2.4
</p>
</p>


Aktuelle Version vom 10. November 2020, 13:56 Uhr

In der vorangegangenen Auflistung findet sich u.a. der Punkt "Die zu ersetzende Seite E wird bestimmt,...", und es stellt sich die Frage:

Frage

Wie wird die zu ersetzende Seite bestimmt?


Diese Aufgabe wird von einem sogenannten Seitenersetzungsalgorithmus erledigt.

Im Laufe der Entwicklungsgeschichte von Betriebssystemen wurden eine ganze Reihe verschiedener Seitenersetzungsverfahren (oder Verdrängungsstrategien) vorgeschlagen bzw. implementiert, u.a.:

  • Optimaler Algorithmus
  • NRU - Not Recently Used Algorithmus
  • FIFO - First In First Out Algorithmus
  • Second Chance Algorithmus
  • Clock Page Algorithmus
  • LRU - Least Recently Used Algorithmus
  • NFU - Not Frequently Used Algorithmus
  • Working Set Algorithmus


Hinweis

Weiterführende Literatur

Mandl 2013 erläutert die genannten Algorithmen in den Kapiteln 7.2.3 und 7.2.4. Die Lektüre dieser Quelle sei ausdrücklich empfohlen.

Studierende sind oftmals berechtigt, eine PDF-Version dieses Buches ohne entstehende Kosten über ihre Hochschulen von Springerlink zu beziehen.


Einige der genannten Algorithmen werden auf den folgenden Seiten behandelt. Die ausführlichere Besprechung aller Verfahren leistet jedoch nur die weiterführende Literatur.


Hinweis

Beim Durcharbeiten der genannten Kapitel bei Mandl 2013 kann man sehr schön die Evolution der Algorithmen verfolgen. D.h. ein späteres Verfahren beruht sehr oft auf einem vorangegangenen Verfahren, wobei jedoch ein vorheriger Nachteil verbessert wurde.
Achte mal darauf!


So geht es weiter:

Gliederung
3.3.2.2.3 Seitenersetzungsverfahren
3.3.2.2.3.1 Optimaler Seitenersetzungsalgorithmus
3.3.2.2.3.2 NRU - Not Recently Used Algorithmus
3.3.2.2.3.3 FIFO - First In First Out Algorithmus
3.3.2.2.3.4 Second Chance Algorithmus
3.3.2.2.3.5 Working Set Algorithmus


Aufgabe 1

Aufgabe
 Aufg. 169: Die MMU und Seitenersetzungsverfahren

In diesem Kapitel wird beschrieben, dass ein Seitenersetzungsverfahren zum Einsatz kommt, wenn bei der Umrechnung einer virtuellen Adresse in eine physikalische Adresse auf der MMU ein Seitenfehler (page fault) ausgelöst wird.

Was ist jedoch im anderen Fall:
Eine virtuelle Adresse kann von der MMU erfolgreich in eine physikalische Adresse umgerechnet werden, es tritt also kein Seitenfehler auf.

Kommt dann auch ein Seitenersetzungsverfahren zum Einsatz?


Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png

Abgerufen von „https://vfhcab.eduloop.de/mediawiki/index.php?title=Seitenersetzungsverfahren&oldid=5150“