Swap Space Management während des reinen Demand Paging

12

Das Folgende ist ein Zweifel, auf den ich bei einer OS-Hausaufgabe gestoßen bin - es scheint jedoch eher konzeptbasiert als eine einfache Codierungsfrage zu sein, daher denke ich, dass das Hausaufgaben-Tag dafür nicht geeignet ist.

In einem reinen Bedarfs-Paging-Schema für mehrere Prozesse, die gleichzeitig ausgeführt werden, bei einer festgelegten Menge an RAM und Swap-Speicher, was passiert in den folgenden 2 Fällen für den Swap-Speicher, wenn

  1. Bei einem Prozess tritt ein Seitenfehler auf, und im RAM sind keine freien Frames verfügbar. Daher muss eine der Seiten aus dem Prozessblock der Kernel-Frames zum Austauschen ausgeschrieben werden (der Einfachheit halber erwäge ich die Kopie nicht -on-write case). Explizit, wo im Swap-Bereich würde dieser Frame geschrieben und welche Datenstrukturen müssen dafür aktualisiert werden?

  2. Wenn ein Prozess eine bestimmte Seite einblättern muss, wo sieht er im Swap-Speicher aus und wie würde er wissen, ob diese bestimmte Seite überhaupt in Swap vorhanden ist?

Wie Sie sich gut vorstellen können, habe ich Schwierigkeiten zu verstehen, wie der Swap-Bereich während des reinen Bedarfsverwaltungsschemas verwaltet werden kann und welche Datenstrukturen wesentlich wären. Es wäre großartig, wenn Sie in Ihrer Antwort auf Links verweisen könnten (ich habe in "Betriebssystemkonzepte - 8. Ausgabe von Silberschatz, ich konnte keine explizite Antwort auf meine Frage finden) gesucht.

TCSGrad
quelle
3
Eine schöne Hardcore-CS-Frage!
Dave Clarke

Antworten:

8

Um diese Frage zu beantworten, werde ich einige Voraussetzungen für ein Verständnis besuchen. Pure Demand Paging kann ohne Hardware-Unterstützung nicht durchgeführt werden. Alle modernen Computerarchitekturen unterstützen Paging, viele haben jedoch unterschiedliche Implementierungsdetails.

x86-Prozessoren verwenden eine sogenannte Seitentabelle, um virtuelle Adressräume und Seitenzuordnungen sowie Informationen zu Zugriffsberechtigungen und, was noch relevanter ist, ob diese Seite überhaupt im physischen Speicher vorhanden ist oder nicht, zu verfolgen . Verstöße lösen Seitenfehler aus, die vom Betriebssystem abgefangen werden.

Weitere Informationen hierzu finden Sie in diesem Artikel .

Um die Frage des Seitentauschs zu beantworten, müssen wir zunächst die Frage beantworten, wie das Betriebssystem verfolgt, welche Seiten von welchem ​​Prozess verwendet werden und wie sie zugewiesen werden. Es gibt viele verschiedene Datenstrukturen, die für solche verwendet werden können. Ein Flat-Bit-Array, das angibt, ob ein Frame zugewiesen ist oder nicht, ist eine Möglichkeit. Verknüpfte Listen oder Stapel sind andere. Bei reinem Bedarfs-Paging werden zugewiesene Seiten bei der Zuweisung nicht als vorhanden markiert. Dies hat zur Folge, dass kein physischer RAM für einen Prozess reserviert wird, bis er tatsächlich darauf schreibt. Sobald dies der Fall ist, gibt die Hardware einen Fehler aus, den das Betriebssystem abfängt, und das Betriebssystem verwendet einen Auslagerungsalgorithmus, wenn keine physischen Seiten verfügbar sind, die der bereits zugewiesenen virtuellen Seite zugewiesen werden können.

Weitere Informationen zur Zuweisung von Seitenrahmen finden Sie hier . Dort sehen Sie einen allgemeinen Überblick über einige geeignete Datenstrukturen.

Sobald ein geeigneter Algorithmus für die Seitenzuweisung implementiert ist, muss ein anderer für die Zuweisung von Speicherplatz zum Austauschen ausgewählt werden. Windows hat beispielsweise in der Vergangenheit eine flache Datei im Dateisystem zum Austauschen von Seiten verwendet. Ich würde mir vorstellen, dass für jeden Knoten in der Datenstruktur, der die zugewiesenen Seiten verfolgt, ein zugeordneter Zeiger auf einen Versatz in der Datei vorhanden ist, der die Position der Seite auf der Festplatte angibt. Unix-ähnliche Betriebssysteme haben traditionell separate Partitionen für den Seitentausch verwendet, was wohl schneller ist, da es keine Dateisystemschicht gibt.

Es ist auch möglich, die Datenstrukturen des Swap-Algorithmus von denen des Zuordnungsalgorithmus zu trennen, die beiden sind jedoch miteinander verbunden, so dass dies wahrscheinlich nicht oft durchgeführt wird.

Ich hoffe, das beantwortet Ihre Frage trotz der relativen Kürze, mit der ich sie behandelt habe. Ich fand heraus, dass der beste Weg, um mehr über Betriebssysteme zu erfahren, darin besteht, in die manchmal unangenehmen architektonischen Details einzutauchen, die auf Websites wie wiki.osdev.org und www.osdever.net zu finden sind, die sich speziell mit der Erstellung von Hobby-Betriebssystemen befassen und hervorragende Tutorials bereitstellen auf solche Details.

Dougvj
quelle
Ja, jetzt verstehe ich, wie die Details von Datenstrukturen usw. zwischen Betriebssystemen stark variieren können - +1 für die Links zu osdev.org!
TCSGrad