Kapitel 9: Hauptspeicherverwaltung

Kapitel 9: Hauptspeicherverwaltung

• Ein Laptop mit 32 GB RAM hat 16.000-mal so viel Hauptspeicher wie ein IBM-Großrechner von 1965.
• Anwendungsprogramme wachsen schneller als die Speicherkapazität.
• "Parkinsons Gesetz" besagt, dass sich Arbeit ausdehnt, um die verfügbare Zeit auszufüllen; Programme dehnen sich aus, um den verfügbaren Speicher voll auszunutzen.
• Die Speicherverwaltung ist ein Teil des Betriebssystems.
• Zu den Aufgaben der Speicherverwaltung gehören die Verfolgung der Speichernutzung, die Zuteilung und Freigabe zugeteilten Speichers für Prozesse sowie die Verwaltung des Auslagerns von Hauptspeicher auf die Festplatte und zurück.
• Das Verständnis der Speicherverwaltung ist für die Programmierung wichtig, obwohl einfache Methoden in PCs seltener, aber in Smartphones häufiger verwendet werden.
• Ein idealer Speicher wäre groß, schnell und günstig, aber in der Realität werden Kompromisse durch eine Speicherhierarchie eingegangen.

9.1 Speicherhierarchie

• Das Speichersystem eines Rechners ist hierarchisch aufgebaut und ähnelt einer Pyramide.
• Schnellerer Speicher ist teurer und kleiner, während langsamerer Speicher billiger und größer ist.
• In der Speicherhierarchie befinden sich Register, Cache, Hauptspeicher, Festplatte und Archiv (CD-ROM, Band).
• Beim Zugriff auf ein Datenelement "wandert" eine Kopie entlang der Speicherhierarchie nach oben.
• Nach der Modifikation eines Datenelements werden Änderungen schrittweise nach unten propagiert.

Ziel und Mechanismen der Speicherhierarchie

• Das Ziel ist, dass die gerade benötigten Daten und Programme möglichst weit oben in der Speicherhierarchie (schneller Zugriff) verfügbar sind.
• Die Kapazitäten werden nach oben hin sehr knapp.
• Das Wissen um den nächsten Datenzugriff basiert auf spekulativer Prognose des Programmverhaltens.
• Programmierer, Übersetzer, Betriebssystem und Hardware verwalten den Datentransport zwischen den Schichten.
• Daten werden in Bytes, Speicherworten, Cachezeilen, Blöcken und Dateien transportiert.
• Der Zugriff auf eine Schicht kann durch Caching beschleunigt oder die Kapazität durch Virtualisierung erweitert werden.

Lokalität in der Speicherhierarchie

• Die Speicherhierarchie beruht auf dem Lokalitätsprinzip, wobei Programme in einem kleinen Zeitraum nur auf einen kleinen Teil ihres Adressraums zugreifen.
• Räumliche Lokalität bedeutet, dass ein Zugriff auf eine Adresse die Wahrscheinlichkeit erhöht, dass auf nahegelegene Adressen zugegriffen wird.
• Zeitliche Lokalität bedeutet, dass ein Zugriff auf eine Adresse die Wahrscheinlichkeit erhöht, dass kurz darauf wieder auf dieselbe Adresse zugegriffen wird.
• Programme mit oft und randomisiert zugegriffen Daten sind schwer effizient zu handhaben.
• Die meisten Programme zeigen lokales Verhalten, was bedeutet, dass sie zeitlich und/oder räumlich lokal sind.
• Anweisungsfolgen werden sequentiell abgearbeitet, was räumliche Lokalität erzeugt.
• Programme verbringen die meiste Zeit in Schleifen, was zeitliche Lokalität erzeugt.
• Viele Programmteile werden nur in Ausnahmefällen ausgeführt.
• Ein Prozess verbringt statistisch 90 % seiner Zeit in 10 % seines Adressraums.
• Datenbankserver bedienen viele Anwendungen, nutzen aber meist nur ein Datenbank und dort nur wenige Tabellen.

Caching vs. Virtualisierung

• Die Speicherhirarchie wird genutzt aber nicht immer sind alle Schichten sichtbar, einige sind transparent.
• Dem Programmierer wird vermittelt, dass es nur eine Schicht gibt, auf die sich die Zugriffe beziehen.
• Beim Caching greift der Benutzer auf Schicht k zu, aber tatsächlich auf Schicht k-1.
• Bei der Virtualisierung liegen die adressierten Daten tatsächlich auf Schicht k+1, obwohl der Benutzer Schicht k sieht.
• Caching beschleunigt Datenzugriffe, während Virtualisierung die Kapazität vergrößert.

Zuständigkeit während der Ausführung

• Während der Laufzeit eines Programms wird der Datentransport zwischen Hauptspeicher, Caches, Registern und Prozessor direkt von der Hardware (CPU, Cache-Controller) erledigt.
• Zugriffe auf die Platte und der Datentransport zwischen Hauptspeicher und Platte sind Aufgabe des Betriebssystems.
• Das Aus- und Einlagern von Dateien vom Archivspeicher kann entweder explizit vom Benutzer oder automatisch vom Betriebssystem erfolgen.

9.2 Flüchtiger / Permanenter Speicher

• Obere (schnelle) Speicherschichten sind meist flüchtig und verlieren ihren Inhalt bei Stromausfall.
• Obere Schichten werden für temporäre Objekte (Programmvariablen) und untere Schichten für permanente Objekte (Dateien) verwendet.

Caching vs. Virtualisierung bezüglich der Flüchtigkeit

• Caching und Virtualisierung verwischen die traditionelle Verwendung von Hauptspeicher (nur Programmadressraum) und Plattenspeicher (nur Dateien).
• Virtualisierung lagert temporäre Daten auf nichtflüchtigen Speicher aus.
• Beim Caching sind permanente Daten möglicherweise nur im flüchtigen Speicher vorhanden, bis Änderungen in den nichtflüchtigen Speicher geschrieben werden.

9.3 Adressräume

• Ein Adressraum (AR) ist eine zusammenhängende Menge von Speicheradressen.
• Der physische Adressraum wird durch die Breite des Adressbusses definiert und gibt die Menge der Adressen an, die der Prozessor ansprechen kann.
• Der logische Adressraum ist die Menge der Adressen, mit denen ein Programm arbeiten kann.
• Alle Prozesse teilen sich den physischen Adressraum. Mehrere Threads können sich einen logischen Adressraum teilen.
• Einige Teile des Adressraums können undefiniert sein.
• Ein Pentium-Prozessor mit 32-Bit-Adressen hat einen physischen AR von 4 GB (2^32 Byte).
• Wenn nur 512 MB (2^29 Byte) physischer Speicher vorhanden sind, sind Adressen über 2^29 undefiniert.

Layout eines logischen Adressraums

• Der logische Adressraum besteht aus Programmtext (Maschinencode), statischen Daten (Programmkonstanten), Heap (dynamische Daten außerhalb von Funktionen) und Stack (dynamische lokale Daten von Funktionen).
• Mehrere Threads in einem logischen Adressraum teilen sich Programm und Daten, aber ihre Stacks sind getrennt.

Adressumsetzung: Logisch - Physisch

• Die Umsetzung zwischen logischen und physischen Adressräumen kann unterschiedlich realisiert werden.

9.4 Direkte Adressierung des Hauptspeichers

• In einem ausführbaren Programm werden direkt physische Adressen verwendet (Programmadresse = physische Speicheradresse).
• Logische Adressräume sind Teilbereiche des physischen Adressraums.
• Der Übersetzer legt zur Übersetzungszeit die Adressbindung fest, wodurch die Lage des Programms im Hauptspeicher vorgegeben ist.

Direkte Adressierung: Diskussion

• Bei Mehrprogrammbetrieb kann die Adressbindung zur Übersetzungszeit zu Konflikten führen.
• Programme können nur konfliktfrei in den Speicher geladen werden, wenn ihre Adressräume disjunkt sind.

Alternative: Relative Adressierung

• Die relative Adressierung ist flexibler, da die Adresse erst beim Zugriff gebildet wird (Adressbindung zur Laufzeit).
• Das Programm enthält nach dem Laden nur relative Adressen (logischer Adressraum beginnt bei 0).
• Der Prozessor enthält ein Basisadressregister, das auf die Anfangsadresse gesetzt wird und zu jeder relativen Programmadresse addiert wird, um die Speicheradresse zu bilden.
• Die logischen Adressräume werden auf zusammenhängende, disjunkte Teile des physischen Adressraums abgebildet.
• Dynamisches Umspeichern oder Einlagern an einer anderen Adresse ist möglich, indem die Basisadresse geändert wird.

9.5 Speicherschutz – Problematik

• Programmierfehler können zu Zugriffen auf Adressen außerhalb des logischen Adressraums oder auf geschützte Speicherbereiche führen.
• Lesezugriffe könnten sensible Daten anderer Prozesse offenlegen.
• Schreibzugriffe können zum Beeinträchtigen/Beschädigen anderer Programme/Betriebssystemteile führen.

Speicherschutz durch Speichertrennregister

• Im Einbenutzerbetrieb genügt es, das Betriebssystem gegen Zugriffe der Anwendungsprogramme zu schützen.
• Ein Register legt die kleinste oder größte zulässige Adresse eines Anwendungsprogramms fest.
• Die Einhaltung wird von der Hardware gewährleistet.

Speichergrenzregister (relative Adressierung)

• Im Mehrprogrammbetrieb mit relativer Adressierung belegt ein Programm einen zusammenhängenden Speicherbereich, dessen Anfang und Ende überprüft werden müssen.
• Statt eines Speichertrennregisters sind zwei Register erforderlich: das Basisregister (Anfang) und das Grenzregister (Ende) des Programmadressraumes.

Funktionsweise des Grenzregisters

• Zur relativen Programmadresse wird der Inhalt des Basisregisters addiert.
• Kleinere Adressen als die Basisadresse sind nicht möglich.
• Die Obergrenze wird mit Hilfe des Grenzregisters geprüft.
• Bei Überschreitung löst der Prozessor eine Unterbrechung (segmentation fault, address violation) aus.

9.6 Verschnitt (fragmentation)

• Verschnitt sind unbenutzte, aber nicht belegbare Teile des Speichers.

Zwei Arten: Externer und Interner Verschnitt

• Externer Verschnitt tritt auf, wenn der Speicherplatz für einen neuen Prozess insgesamt ausreicht, aber kein hinreichend großes, zusammenhängendes Stück gefunden wird.
• Interner Verschnitt tritt auf, da Speicher meist in Vielfachen von Elementargrößen vergeben wird und Anforderungen auf das nächste Vielfache gerundet werden, ist, jedoch nicht benutzt wird.

Verschnitt (Fragmentation)

• Verschnitt kann auf allen Speichermedien vorkommen und ist unerwünscht.
• Verschnitt kann durch Defragmentierung reduziert werden.
• Es ist besser, Verschnitt durch geeignete Speicherverwaltung von vornherein klein zu halten.

9.7 Streuende Adressierung

• Im Gegensatz zur zusammenhängenden Adressierung wird bei der streuenden Adressierung der logische Adressraum in kleinere Stücke zerlegt, die unabhängig voneinander im Speicher abgelegt werden.
• Paging(gleichlange Stücke) und Segmentierung(variabel) sind Arten der Adressierung.
• Die Adressumsetzung erfolgt dynamisch durch die Memory Management Unit (MMU) des Prozessors.

Methode 1: Stückelung in gleichlange Teile (Paging)

• Die Teile des Adressraums im Prozess (Seiten) und die korrespondierenden Einheiten des Speichers (Seitenrahmen oder Kacheln) sind gleich groß.

Methode 2: Stückelung in variabel lange Teile (Segmentierung)

• Segmente haben variable Größen und sind meist größer als Seiten und angepasst an die Speicheranforderungen konkreter Prozesse.

Stückelung in gleichlange Teile (Paging) in Bezug zum Verschnitt

• Es entsteht kein externer Verschnitt, sondern nur interner Verschnitt, da die Seitengröße immer ein Vielfaches der Kachelgröße beträgt.

Seitentabelle: Arbeitsweise

• Da es beim Paging viele Basisadressen gibt, wird eine Seitentabelle im Hauptspeicher abgelegt.
• Der Prozessor enthält nur die Basisadresse der Seitentabelle.
• Die Programmadresse besteht aus der Seitennummer und einem Offset innerhalb der Seite.
• Die physische Adresse wird durch Konkatenation der Kacheladresse und des Offsets gebildet.

Optimierung der Seitengröße

• Kleine Seiten führen zu geringerem internen Verschnitt, aber langen Seitentabellen.
• Große Seiten führen zu hohem internen Verschnitt, aber kurzen Seitentabellen.
• Die optimale Seitengröße minimiert den Speicherverlust durch Verschnitt und die Seitentabelle.
• Die empirisch optimale Seitengröße (Sopt) beträgt √2p, wobei p die Größe des logischen Adressraums ist. Der resultierende Speicherverlust beträgt Vopt = √2/p.

Beispiel der Anwendung der Optimierung

• Wählt man jeweils die optimale Seitengröße, so nimmt der relative Speicherverlust mit zunehmender Größe des Programmadressraums ab.

Segmentierung: Stückelung in variabel lange Teile in Bezug zum Verschnitt

• Segmente haben variable Größen und sind angepasst and die Speicheranforderungen konkreter Prozesse
• kein interner Verschnitt
• dafür externer Verschnitt

Segmentierung: Arbeitsweise

• Segmente werden wie Seiten in einer Segmenttabelle verwaltet.
• Bei Aktivierung eines Prozesses wird die Segmenttabelle geladen, die die Speicherverwaltung nutzt.
• Da Segmente bei unterschiedlichen Adressen beginnen kann die Segmenttabelle volle Adressen aufnehmen
• Die Relativadresse innerhalb des Segments wird zur Segmentbasisadresse addiert.

Beschleunigung der Adressumsetzung

• Segment- und Seitentabellen passen nicht in Prozessorregister und müssen deshalb im Hauptspeicher untergebracht werden..
• Für jeden Zugriff (Befehl oder Daten) ist damit mindestens ein zusätzlicher Hauptspeicherzugriff erforderlich.
• Die Lösung dafür sind sind aktuell benötigte (Teile der) Segment-/Seitentabellen, unter Ausnutzung der Lokalität, im einem schnellen Registersatz gespeichert.
• TLB = Translation Lookaside Buffer ist eine Art Cache für Seiten-/Segmenttabellen
• Ein TLB ist ein Assoziativspeicher, der simultan in den Zeilen der Tabelle nach den zu findenden Daten durchsucht(teuer).
• Der TLB wird wird entweder in der Hardware oder Software implementiert.

9.8 Virtualisierung des Speichers

• Batch-Systeme bearbeiten Aufträge, die in festen Partitionen des Speichers platziert und von Anfang bis Ende bearbeitet werden.
• Timesharing Systeme und PCs mit GUI haben nicht genug Speicher für aktive Prozesse. Die Daten "wandern" zwischen Arbeitsspeicher und Festplatte.
• Swapping ist ein Prozess bei dem die Daten nur wenn sie im Hauptspeicher sind ausgeführt werden; Prozesse werden wiederholt vollständig ein- und ausgelagert.
• Virtueller Speicher führt Prozesse aus, auch wenn sich nur Teile des Kontexts im Hauptspeicher liegen.
• BS hält die zurzeit benötigten Teile von Programmen und Daten im Hauptspeicher, den Rest auf der Festplatte und ist eine gute Art der Speicherverwaltung.
• Für die Virtualisierung von Speicher wird Paging und Segmentierung genutzt und es werden Ersetzungsstrategien angewendet.

Virtueller Speicher: Aspekte der Implementierung

• Das Zerlegen der Adressräume und das Ein- und Auslagern kann (mit HW-Unterstützung) automatisiert werden.
• Die benötigten Teile werden erst auf Anforderung eingelagert (demand paging).
• Diese Vorgänge sind transparent, so der Eindruck der Benutzer über unbegrenzten Speicher.
• Der Speicher ist jedoch nur virtuell vorhanden.
• Für den effizienten Betrieb sind streuende Adressierung(Seitentabellen), Auto Seitenerkennung im Hauptspeicher, Zugriff auf nichtvorhandene Seite löst Unterbrechung aus und Einlagerung der Seite im Rahmen der Unterbrechungsbehandlung nötig.

Typische Datenstrukturen für virtuellen Speicher

• Seitentabelle (page table) dient der Adresstransformation und hält Nutzungs/Präsenzinformationen und die Adresse der Kachel(Speicherbereich). Seiten können sehr groß werden, daher kann der Speicher sehr groß werden.
• Kacheltabelle (page frame table, inverted page table) dient der Speicherverwaltung. Ist eine Alternative zu Seitentabellen. Nachteil: bei jedem Speicherzugriff muss die Gesamttabelle nach dem Eintrag durchsucht werden. Vorteil: Viel weniger Platz als bei Seitentabellen.
• Die Lösung für Seitentabellen ist die Nutzung des TLB, da die Suche nur durchgeführ wird wenn die Seite nicht im TLB liegt.
• Als Ersatzspeicher (swap area) auf der Festplatte für ausgelagerte Seiten.

Seitentabelle für virtuellen Speicher und drei Bits

• Zusätzlich zur physischen Adresse enthält der Eintrag für jede Seite in der Seitentabelle folgende Informationen (drei Bits):
• ob die Seite im Hauptspeicher vorhanden ist: Präsenzbit (presence bit, valid bit)
• ob auf die Seite kürzlich zugegriffen wurde: Referenzbit (reference bit)
• ob die Seite verändert wurde (Schreibzugriff): Modifikationsbit (dirty bit)

Aufgaben bei Seitenfehlern

• Ein Seitenfehler ist, wenn eine Seite nicht im Systemspeicher ist. Es wird überprüft ob eine Seite zum auslagern gewählt werden muss und der Kachelinhalt wird verändert. Es ist notwenidige das eine Neue Seite von Ersatzspeicher eingelagert werden kann und das Umschreiben der Einträge wird schwierig und ist ein Strategieproblem.

Pufferung

• Viele Seitenfehler (d.h. die benötigte Seite ist nicht im Hauptspeicher)können stoßweise auftreten, deshalb muss ein Vorrat an freien Kacheln bereitgestellten.
• In BS wird dazu ein eigener Thread, der im Hintergrund läuft zum Kachelleeren ausgeführt. Sinkt der Vorrat an Kacheln unter einen wert, durchsucht der Threads Seiten die ausgelagert werden können. Durch den Speicher steht bei Seitenhelern ausreichend Speicher zur Verfügung.
• Unterschiedliche Seitenersetzungsstrategien (d.h. Auswahl der Seite zum Auslagern) hilft und sind wir im nächsten Abschnitt erklärt.

Segmentierung und Paging heute

• Segmentierung ist nicht mehr besonders populär. Hier sind Daten, Stack und Programmcode unterschiedlich angeordnet. Durch Geeignete Größen der Seiten kann man Verschnitte klein hallten werden
• Segmentierung ist für Programmierer erkennbar.
• Segmentierung Paging kann zusammen eingesetzt werden, hier wird der logische Speicher wird in Segmenten mit verschiedenen Grössen aufgeteilt. Jeder Abschnitt hat dann seine eigene Seitentabelle. . Vorteile: effiziente Speichernutzung und Nachteile: größere Komplexität
• Moderne Systeme nutzen Paging, nur in Echtzeit-BS wird noch Segmentierung verwendet.