Fortgeschrittene Speicherverwaltung

Lernziele und Kompetenzen

• Sie lernen die weiterführenden Konzepte der Speicherverwaltung in modernen Betriebssystemen kennen,

• verstehen wie Speichermanagement mittels einer Free List realisiert werden kann,

• verstehen die Grundlagen des Pagings

Grundlegende Überlegung

Wie gehen wir mit großen Adressräumen um?

• Zwischen Heap und Stack liegt ggf. viel (ungenützter) Speicher

• Mit 32-Bit lassen sich 4 GB große Adressräume ansprechen

Exkurs

• Unter 32-Bit Windows waren die obersten 2 GB physikalischem Speicher für Windows Reserviert: max. 2 GB virtueller Adressraum

• Unter 32-Bit Linux 1 GB physikalischem Speicher für Betriebssystem: max. 3 GB virtueller Adressraum

Lösung: Segmentierung

• Ein Base- und Bounds-Paar pro logisches Speichersegment des Adressraums

• Was ist eine Speichersegment?

• Zusammenhängender Speicherbereich

• In unserem Fall drei Segmente

  • Programm-Code

  • Heap

  • Stack

Hardware-Unterstützung

• Folglich: Es müssen drei Base- und Bounds-Paare in der MMU unterstützt werden

• Frage: Woher weiß die CPU welches Segment gemeint ist?

• Lösung: Teile der virtuellen Speicheradresse werden für das Segment genutzt

Base- und Bounds Beispiel

Segment	Base	Größe
Code	32K	2K
Heap	34K	3K
Segment	28K	2K

Segmentation Fault

Speicherzugriff auf illegale Adresse in segmentiertem (aber auch bei nicht-segmentiertem Speicher)

Wie kann dass passieren?

• Typisch für C-Programmer.

• Aufgrund von Pointer-Arithmetik ist es rechte einfach versehentlich eine Adresse zu »berechnen«, die außerhalb des gültigen Segments liegt

Adressierung von Code-Segmenten

Beispiel:

• 00 - Code Segment

• 01 - Heap Segment

• 10 - Stack Segment

Berechnung:

• Offset + Base-Register: physikalische Speicheradresse

• Zum Prüfen der Obergrenze, wir die Größe hinzuaddiert

• Was ist mit dem Stack?

  • Hardware-Support durch zusätzliches Bit

• Aus Effizienzgründen: Speicherbereiche können geteilt werden

  • Hardware-Support durch zusätzliches Protection-Bit

  • Segment kann somit in mehreren virtuellen Adressräumen genutzt werden

Segment	Base	Gräße (max. 4K)	Wächst pos.	Schutz
Code	32K	2K	1	Read-Execute
Heap	34K	3K	1	Read-Write
Stack	28K	2K	0	Read-Write

Segmentierung und das Betriebssystem

• Bei Context Switch müssen Segment-Register ebenfalls gesichert/geladen werden

• Was passiert wenn das Speichersegment nicht genügt?

  • malloc-Aufruf liefert Pointer auf Speicherbereich im Heap, Heap ist jedoch zu klein

  • sbrk-SysCall wird ausgeführt, um Heap zu vergrößern

  • Betriebssystem vergrößert das Segment und aktualisiert die entsprechenden Register

  • Hinweis: Vergrößerung kann vom Betriebssystem zurückgewiesen werden (Programm hat bereits genügend Speicher oder es gibt keinen physikalischen Speicher mehr)

Fragmentierung

Speicherfragmentierung (engl. external fragmentation)

• Ursprüngliche Annahme: Alle virtuellen Adressräume sind gleich groß, das ist leider in der Realität nicht so

• Für Segmente müssen passende Speicherbereiche gesucht werden

• Physikalischer Speicher besteht somit schnell aus einer Vielzahl an belegten Speicherabschnitten und Löchern

• Speicher muss vom Betriebssystem komprimiert werden

Exkurs: MS-DOS und EMM386.SYS

• Unter MS-DOS gab es Anfangs ein 640KB Limit

• Um den Speicher optimal auszunutzen musste der Speicher händisch optimiert werden, z.B.

  • durch Nutzung zusätzlicher Tools zur Speicherverwaltung

  • händisches Anordnen der zu ladenden Treiber, um Lücken im

  • Speicher möglichst zu vermeiden (minimieren)

Hausaufgabe:

• Lesen Sie The 640K memory limit of MS-DOS

config.sys

SWITCHES=/f#
DOS=NoAuto,DOS=high,umb
BUFFERSHIGH=40
FILESHIGH=20
FCBSHIGH=1
LASTDRIVEHIGH=m
DEVICE=c:\drivers\qhmboot.sys
DEVICE=c:\drivers\umbpci.sys /i=e000-efff
DEVICEHIGH=c:\drivers\qhimem.sys /n48
DEVICE=c:\windows\himem.sys
DEVICEHIGH=c:\windows\emm386.exe ram auto
DEVICEHIGH=c:\windows\ifshlp.sys
DEVICEHIGH=c:\drivers\usbaspi.sys /v
DEVICEHIGH=c:\drivers\di1000dd.sys
INSTALL=c:\drivers\ctmouse.exe
DEVICEHIGH=c:\drivers\qcdrom.sys /D:mycdrom
INSTALL=c:\drivers\shcdx33a.com /D:mydrom

Paging

• Bisher gelernt: Segmentierung führt früher oder später dazu, dass der Speicher fragmentiert…

• Glücklicherweise nutzen Betriebssysteme noch einen zweiten Mechanismus der Speicherverwaltung: Paging

• Dabei wird der Speicher in fixe Einheiten aufgeteilt

  • Jede solche fixe Einheit heißt Page (dt. Speicherseite)

  • Der physikalische Speicher ist demnach eine Aneinanderreihung von gleichgroßen Slots

  • Jeder solcher Slot heißt Page Frame (dt. Seitenrahmen)

  • Jeder Frame kann eine Page enthalten

Paging Beispiele

Hier ein einfaches Beispiel:

• 64-Byte virtueller Adressraum

• 4 Pages a 16-Byte Pages

• Betriebssystem muss »nur« vier freie Page Frames finden

• Dafür gibt es eine Free List mit freien Page Frames

• Datenstruktur mit den Einträgen wo eine Page im physikalischen Speicher liegt, heißt Page Table (dt. Seitentabelle)

• Es gibt eine Page Table pro Prozess

Zuordnung von Frames

Paging und Address Translation

• Unser Beispiel zuvor hatte ein 64-Byte Adressraum

• Nun versuchen wir Daten aus einer virtuellen Adresse <virtual address> in das Register eax zu laden

• Hierfür benötigen wir zwei Komponenten

  • Virtual Page Number (VPN)

  • Offset (innerhalb der Page)

In Assembler:

movl <virtual address>, %eax

• Wir haben 16-Byte Seiten in einem 64-Byte Adressraum

• Es müssen 4 Seiten adressiert werden können

• Daher die 2-Bit Virtual Page Number (VPN)

• Die restlichen Bits können zur Adressierung innerhalb der Seite verwendet werden (= Offset)

• Beispiel:

  • Zugriff auf virtuelle Adresse 21

  • 21 im Dezimalsystem in ist 010101 Binär, ist 15 im Hexadezimalsystem

  • Somit Zugriff auf Byte5 in Page 1

In Asssembler:

movl 15h, %eax

• Die physikalische Adresse1 von Page 1 ist 7 (= 111)

• Physical Frame Number (PFN) oder auch Physical Page Number (PPN)

Wo liegen Page Tables?

• Page Tables können sehr groß werden

  • Pro Eintrag 20-Bit VPN + 12-Bit Offset für 4KB Pages

  • 20-Bit VPN bedeuten 220 Adressberechnungen pro Prozess (ca. 1 Million)

  • 100 Prozesse in einem 32-Bit System bedeuten ca. 400 MB nur für die Page Tables

  • In 64-Bit Systemen nochmals einiges mehr

• Daher keine extra Hardware (Speicher) in der MMU

• Anstelle dessen werden Sie im Hauptspeicher vorgehalten

  • Konkret im virtuellen Speicher des Betriebssystems vorgehalten

Beispiel: x86 Page-Table-Eintrag

• Present Bit (P): Liegt die Page im Hauptspeicher oder auf Disk (Swapping kommt später)

• Read/Write Bit (R/W): Darf in die Page geschrieben werden

• User/Supervisor Bit (U/S): Kann ein User-Mode Prozess auf die Page zugreifen

• PWT, PCD, PAT u. G: Beschreiben Hardware-Caching

• Accessed Bit (A): Wird für einen sog. “Least recently used page”-Algorithmus genutzt

• Dirty Bit (D): Wurde der Speicherinhalt verändert

• PFN: Page Frame Number