Speicherverwaltung / Memory Management

Das OS wird zuerst in den Hauptspeicher eingefügt und stellt dann Prozessen Speicher zur verfügung.

Wir wollen Speicher effektiv aufteilen und verwalten:

Partitioning

Haupt-Speicher-Aufteilung auf Prozesse.

Prozesse beinhalten Programm und Daten, Kontext.

OS wird immer zuerst eingefügt.

Zu wenig Speicherplatz:

Swapping / Auslagern von Prozessen vorrübergehend auf Sekundärspeicher auslagern.

Overlays / Überladen von Programmen Programm Anteile im Primär- oder Sekundärspeicher.

Speicherplatz wird nicht effizient ausgenützt:

Fragmentierung Teile des Speichers bleiben ungenützt.

Interne Fragmentierung Ungenützter Speicherplatz innerhalb einer Partition.

Externe Fragmentierung Zerstückelung des Speicherbereichs außerhalb der Partitionen.

Löst sich mit compaction (Zusammenschieben, teure Operation).

1) Fixed Partitioning

Statisch Partitionen mit fix vordefinierten Größe.

Problem Speichernutzung ineffizient, interne Fragmentierung

Gleiche Partitions-Größen

Unterschiedliche Partitions-Größen

2) Dynamic Partitioning

Dynamisch Partitionen mit variabler Länge und Anzahl.

Problem Externe Fragmentierung

Weist jedem Prozess eine Partition zu die exakt so groß ist.

Placement Stategien beim Einfügen

Auswahl der Partition in die ein Prozess eingefügt werden soll:

3) Buddy System

Fixed und dynamic partitioning sind nicht mehr in Benutzung.

Versucht Schwächen von statischer und dynamischer Partitionierung auszugleichen:

Ablauf: Anforderung von Blockgröße$S$

1. Suche nach Block mit $U$ für die Schranken $2^{U-1} < S \leq 2^U$ .

   Sucht nach kleinstem bestehenden passenden Block.

   Am Anfang ist der gesamte Speicher ein großer Block.

2. Falls nicht gefunden, zerteile nächstgrößeren Block in $2$ kleinere (so lange bis gefunden).

   Zerkleinert größere Blöcke.

   zB angenommen wir finden$2^{U+2}$dann zerteilen wir den Block$2$mal herunter.

Nach dem Löschen: Vereine benachbarte Blöcke die nicht belegt wurden.

__________

Relocation - Logische Adressierung

Referenzen auf physikalischen Speicher müssen veränderbar sein.

Wir wollen Daten im Speicher verschieben können (= dynamisch positionieren) da wir andere absolute Adressen haben bei

Addressübersetzung

Physische (absolute) Adresse

Logische Adresse

Relative Adresse

Einfache Addressübersetzung

Erfolgt bei jedem Speicherzugriff durch Hardware.

Wir speichern 2 wichtige physische Addressen

Base Register Programm-Anfang: Zeigt auf Start-Adresse vom laufenden Prozesses

Bound Register Programm-Ende: damit wir nur auf gültige Addressbereiche zugreifen

Umsetzung:

__________

Relocation - Virtual memory management

Virtual Memory

Wir abstrahieren darüber welcher Anteil vom Prozess im Hauptspeicher ist.

Wir übernehmen nur notwendige Frames vom Prozess ins Hauptspeicher.

Logischer Addressraum kann viel größer sein als der physischer Addressraum.

Anteil von Prozess Frames / Segmente im Sekundärspeicher heißt virtual memory.

Resident Set

Page Fault (Exception Handling)

Thrashing

1) Segmentierung

Wir wollen nicht gesamtes Programm für Prozess in Hauptspeicher laden sondern Segmente davon definieren die dann in den Partitionen eingefügt werden.

Es kann zu Fragmentierung kommen.

Segment Programm-Block mit beliebiger Länge die zusammengehörenden Code und Daten enthält.

Segment-Tabelle Enthält Segmentlänge und Start (Base der physischen Adresse).

Adressübersetzung mit Segment-tabelle

Logische Addresse besteht aus Offset und Segmentnummer (= Index aus Segmenttabelle)

Logische Addresse: ( Segment-Index | Offset )
↓
Segment table: ( Length | Base )
↓
Physische Addresse: Base + Offset 

2) Paging

Effizienter als Segmentierung

Page Frame

Page

Page-table

Adressübersetzung

Compiler, Linker muss nichts über Unterteilung nichts wissen - passiert durch Paging-Hardware

Logischer Addressbereich         Physischer Addressbereich
( Page Number | Offset )          ( Frame Number | Offset )
|                              ↑
index  └──────────────────────────────┘ table entry
Page Table

Eintrag in page table wird gefunden indem mit dem pointer welche die page table base enthält addiert wird.

Multilevel Page Tables

Die page-table der Prozesse selbst muss im Arbeitsspeicher sein - Kann mit der Zeit sehr groß werden.

Page-table wird selbst in pages unterteilt, die in der root-page-table nachgeschlagen werden.

Ineffizient: 2 Speicherzugriffe vor jedem eigentlichen Speicherzugriff.

Inverted Page Table IPT

Platz sparen indem sich Prozesse eine große Tabelle teilen

Keine page-table pro Prozess sondern eine große page-table für alle Prozesse im Arbeitsspeicher.

Suche durch assoziativen Suchalgorithmus oder Hashing mit Hardware.

Translation Lookaside Buffer TLB

Um zu vermeiden dass 2 physikalische Speichezugriffe notwendig sind (page table, daten lesen).

Cache in der CPU für die Einträge der page-table auf die zuletzt zugegriffen wurde.

Assoziativer Zugriff beim Suchen (sofort zugreifbar).

TLB wird bei jedem context switch gelöscht.

Bei TLB-miss wird Cache erweitert.

Effizient wegen Lokalitätsprinzip.

Fetch policy

Wann kommen Seiten in den Hauptspeicher? Ähnlich wie: Pre-Cleaning vs. Demand Cleaning

Demand Paging laden bei Bedarf (viele Page faults am Anfang)

Prepaging lädt mehr im Voraus (Lokalitätsprinzip) - viele Seiten nicht benötigt

Replace policy

Welche pages werden ersetzt wenn eine neue ins Hauptspeicher geladen wird?

local replacement Austauschstrategie auf Seiten des gleichen Prozesses

global replacement Austauschstrategie auf alle Seiten des Hauptspeichers

Austausch-Strategien

• OPT Policy (optimal)

  Optimale Strategie nicht implementierbar sondern als Maßstab für andere Strategien.

  Wählt die Page die am spätesten referenziert wird.

  Minimale #page-faults

• LRU Policy (last recently used)

  Ersetzt die Seite die am längsten nicht benützt worden ist.

  Nutzt zeitliche Lokalität, sehr nahe zur optimaler strategie

  Viel overhead, viel zum Protokollieren, aufwendig zu Implementieren:

  Speichern der Zugriffszeiten + Suche

• FIFO Policy

  Ersetzt die älteste Seite (die zuerst geladen wurde).

  Einfach zu implementieren: Pointer welcher zyklisch die page-frames iteriert

  Keine Information über Frequenz der Verwendung der Seite

  Deutlich mehr #page-faults

• Clock Policy

  Ringpuffer aus Seiten die für Austausch in Frage kommen.

  Jede Seite hat ein used-bit (welche sagt ob neulich auf sie zugegriffen wurde oder nicht).

  Nicht viel mehr page-faults als LRU.

  Pointer wird am Anfang zufällig gesetzt.

  1. Es wird nach 0 gesucht und alle 1-Einträge dazwischen werden geflipped.

  2. Nachdem 0 gefunden wurde, wird die Seite ersetzt und der Bit auf 1 gesetzt

  3. Danach wird der pointer auf die nächste Position gestellt bis zur nächste Suche.

  

  In diesem Szenario, wird in der darauf erneut folgenden Replacement, gleich die page ersetzt auf die der pointer das letzte Mal gezeigt hat, weil dort eine 0 steht und das bit auf 1 geflipped.

Working Set Strategie

Zur Bestimmung der richtigen Größe des Resident-Sets

Working Set von einem Prozess

$W(D,t)$ = Set an pages, auf die $D$ virtuelle Zeiteinheiten vor Zeitpunkt $t$ zugegriffen wurde.

Virtuelle Zeiteinheiten: Nur Zeitfortschreitung im Prozess - zB preemptions nicht betrachtet.

Eigenschaften:

Anwendung

Wir checken periodisch das Working Set für alle Prozesse.

Resident Set $\supset$ Working Set

Resident Set $\sub$ Working Set

Eigenschaften

Overhead: Zusätzliches Logging und Ordnen von Seitenreferenzen

Optimales $D$ variiert und ist zur Laufzeit unbekannt

Best Practice

Protection

Speicherschutz: Prozesse sollen nur auf die eigenen Seiten zugreifen können.

Virtueller Addressraum als Schutz

Protection Keys