OS_05

• Partitioning (Speicheraufteilung auf Prozesse)

• Relocation (flexible Positionierung von Code und Daten im Speicher), Virtual-Memory Management

• Protection (Speicherschutz)

• Sharing (gemeinsamer Zugriff auf Speicher)

• Performance (effektive log./phys. Organisation)

• Fixed partitioning

• Dynamic partitioning

• Buddy System

Unterteilung des Hauptspeichers in nicht überlappende Teile:

• Prozesse, die kleiner gleich einer Partition sind, können geladen werden (gleiche bzw. ungleiche Partitionsgrößen)

• Auslagern eines Prozesses durch das BS, wenn alle Partitionen belegt sind

• Programme, die größer als Partitionen sind => Programmierung von Overlays

Partitionen variabler Länge und Anzahl:

• Zwischen Partitionen entstehen Löcher

• Placement Strategies beim Einfügen

Verschieben der Partitionen, um statt Löchern größeren zusammenhän- genden freien Speicherbereich zu erhalten

• Best fit

• First fit

• Next fit

Interne Fragmentierung:

Verschwendung von Speicherplatz innerhalb einer Partition;

Daten und Programm füllen Partition nicht aus (z.B. bei fixer Partitionierung)

Externe Fragmentierung:

Zerstückelung des Speicherbereichs außerhalb der Partitionen (z.B. bei dynamischer Partitionierung)

Versuch, die Nachteile der vorher angeführten Strategien zu verringern:

=> Zerlegung des Speichers in “Buddies” der Größe 2k, mit MinVal <= k <= MaxVal

Der von Prozessen belegte Speicherbereich ist nicht statisch fixiert (Aufruf bei unterschiedlicher Speicherbelegung, Swapping, Compaction)

=> Referenzen auf physischen Speicher müssen veränderbar sein

=> Unterscheidung zwischen logischer Adresse und physischer (absoluter) Adresse

• Physische (absolute) Adresse

• Logische Adresse

• Relative Adresse

Position relativ zu einem bekannten Punkt im Programm (= logische Adr.)

• Übersetzter Code enthält logische, meist relative Adressen => zur Laufzeit: Adressübersetzung auf absolute Adressen

Referenz einer Position im Speicher, unabhängig von Organisation des Speichers

absolute Position im Hauptspeicher

1. Adressübersetzung durch Hardware

2. Physische Startadresse des laufenden Prozesses im Base Register

3. Endadresse des physischen Speichers des Prozesses im Bound Register

4. Zugriff auf relative Adresse: Inhalt des Basisregisters wird zu relativer Adresse addiert

5. Speicherschutz(Protection): Überprüfung,ob die Adresse im gültigen Bereich (= innerhalb der Bound) liegt

Unterteilung von Programmen in Blöcke unterschiedlicher Länge (=Segmente)

Enthalten: Code und/oder Daten

Eigenschaften:

• Beim Laden des Prozesses werden seine Segmente “beliebig” im Speicher platziert

• keine interne, aber externe Fragmentierung

• sichtbar für den Programmierer

• Segmenttabelle pro Prozess, für jedes Segment existiert ein Eintrag: (Start, Länge)

Unterteilung des Hauptspeichers in (kleine) Seitenrahmen (Frames) gleicher Größe

Prozesse werden in Seiten (Pages) der selben Größe unterteilt:

• Seiten werden in Seitenrahmen geladen

  => Frames eines Prozesses nicht unbedingt dicht

• Page Table pro Prozess: enthält für jede Page die aktuelle Frame-Nummer

• Free Frame List verweist auf freie Frames im Speicher

Dynamische Adressübersetzung:

=> Aufspaltung von Prozessen in Seiten (oder Segmente), die nicht hintereinander im Speicher abgelegt werden müssen

• Logische Adressen referenzieren Virtual Memory

• Seitentabelle (Segmenttabelle) und Memory-Management HW unterstützen die Übersetzung von virtuellen Adressen in absolute Adressen

• Teile eines Prozesses, die sich im Hauptspeicher befinden: Resident Set

Es ist eine Ausnahmebehandlung, wenn eine Adresse im VM referenziert wird, die sich nicht im Hauptspeicher befindet

=> entsprechender Speicherbereich wird von Sekundärspeicher geladen (Demand Paging)

Durch häufige Page Faults verbringt der Prozessor sehr viel Zeit mit dem Laden vom Sekundärspeicher

=> drastischer Einbruch der Effektivität

(z.B., Resident Set eines Prozesses zu klein)

• Present Bit – Seite im Hauptspeicher?

• Frame Number bzw. wo Seite zu finden ist

• Modified Bit – Seite seit Laden verändert?

• Control Bits: r/w-Bits, Locking, Kernel vs. User Page

Eine IPT für das gesamte System:

Ein IPT-Eintrag pro Frame

• Bei Zugriff auf Speicher: assoziative Suche in IPT bzw. Hashing um Suche in IPT zu beschleunigen

• Page Fault, wenn gesuchter Eintrag nicht in IPT

Translation Lookaside Buffer (TLB) = Cache für Einträge der Seitentabelle

• Einträge enthalten Nummern (Page, Frame) der “zuletzt” verwendeten Seiten

• 16-512 Einträge

• Assoziativer Zugriff beim Suchen

• Löschen des TLB bei jedem Context Switch

Wozu?

Page Table im Hauptspeicher => pro Zugriff auf das VM sind (mindestens) zwei Zugriffe auf den physischen Speicher notwendig

Sie bestimmt, wann eine Seite geladen wird

Demand Paging:

• lädt eine Seite, wenn eine Adresse der Seite referenziert wird

• viele Page Faults beim Start eines Prozesses

Prepaging:

• lädt mehr Seiten als angefragt im Voraus

• durch Lokalitätsprinzip motiviert (Prog., Disk) – Laden nicht benötigter Seiten ...

Sie bestimmt, welche Seite beim Laden einer neuen Seite im Hauptspeicher ersetzt wird

lokal:

Austausch innerhalb der Seiten des Prozesses

global:

Austauschstrategie wird auf alle Seiten des Hauptspeichers angewandt

OPT: optimale Strategie

• minimale Anzahl von Page Faults

• ersetzt die Seite, deren nächste Referenz am weitesten in der Zukunft liegt

• keine reale Strategie

• wird zur Bewertung anderer Strategien herangezogen

LRU (least recently used):

• ersetzt die Seite, die am längsten nicht benützt worden ist

• aufgrund des Lokalitätsprinzips ist zu erwarten, dass die Seite auch in naher Zukunft nicht referenziert werden wird

• Anzahl der Page Faults kaum höher als bei OPT

• Implementierung aufwändig

FIFO (first in - first out):

• bei vollem Seitenkontingent wird die älteste Seite ersetzt

• einfache Implementierung: Pointer, der zyklisch über die Seitenrahmen fortgeschaltet wird

Nachteil: eine Seite, die gerade oft verwendet wird, kann die älteste sein; sie wird ausgelagert

Ringpuffer mit Frames, die für Austausch in Frage kommen + Positionszeiger:

• Use Bit pro Frame, wird auf 1 gesetzt, wenn Seite geladen oder referenziert wird

• bei Page Fault:

  1. Suche erste Seite ab Zeigerposition mit Use Bit = 0

  2. Setze dabei Use Bits mit Wert 1 auf 0

• nach Page Fault: Zeiger wird auf den folgenden Frame im Ringpuffer gesetzt

Allokation einer variablen Anzahl von Frames pro Prozess basierend auf Lokalitätsannahme

Working Set eines Prozesses wächst beim Start schnell an und:

• stabilisiert sich während der weiteren Prozessausführung (Lokalitätsprinzip),

• wächst, wenn sich die Abarbeitung in einen anderen Adressbereich verschiebt, ...

• Beobachtung des Working Set der Prozesse

• Periodisches Löschen der Seiten, die sich nicht im Working Set befinden

• Wenn Resident Set = teilmenge vom Working Set:

  1. allokiere fehlende Frames

  2. sind nicht genügend Frames verfügbar, suspendiere den Prozess und probiere Allokation später nochmals

• Mitloggen der Seitenreferenzen

• Ordnen der Seitenreferenzen

• optimales D ist zur Laufzeit unbekannt und variiert

Gängige Praxis: Beobachtung der Anzahl der Page Faults pro Zeitintervall und Prozess statt Working Set