Betriebssysteme (Betriebssystemtheorie) - Kapitel 7 - Speicherverwaltung

Inhalte von Dr. E. Nadobnyh

7.1 Einführung

Aufgaben der Speicherverwaltung

1) Zuteilung (Allokation) und Freigabe von Speicherbereichen für mehrere Adressräume.

2) Die Abbildung der logischen Adressen auf die physische Adresse.

3) Führung einer Übersicht über freie und belegte Teile des Arbeitsspeichers.

4) Speicherbereinigung und Speicherverdichtung.

5) Auslagerung von Speicherbereichen auf einen Sekundärspeicher.

6) Speicherschutz der Adressräume von unbefugten Speicherzugriffen anderer Prozesse.

Grundbegriffe

1) Eine logische Adresse (Programmadresse) wird von einem Prozess generiert und von der CPU verwendet. Sie ist z.B. der Inhalt des Zeigers.

2) Eine physische Adresse (Speicheradresse) wird beim Speicherzugriff verwendet.
3) Eine Adresstransformation ist eine Abbildung von logischen Adressen auf die physischen. Sie findet bei jedem Speicherzugriff statt.
4) Ein Adressraum (logischer Adressraum) ist eine Menge von logischen Adressen, die ein Prozess zur Adressierung des seinen Speichers generieren kann. Er wird meist vom Compiler in 4 Bereiche aufgeteilt: Stack, Code, Data und Heap.
5) Eine Speicherabbildung ist eine Abbildung des Adressraums auf den Speicher (Arbeitsspeicher, Hauptspeicher, RAM, physikalischer Adressraum).

Varianten der Speicherabbildung

1) Mit der vollständigen oder unvollständigen Belegung.
Eine vollständige (komplette) Belegung findet statt, wenn das gesamte Programm in den Speicher geladen wird.

2) Mit der kontinuierlichen oder diskontinuierlichen Belegung.
Eine kontinuierliche Belegung findet statt, wenn verschiedene Teile des Programms zusammenhängend im Speicher platziert werden.

3) Mit oder ohne Auslagerung.
Eine Auslagerung ist eine regelmäßige Speicherung des Programms vom Hauptspeicher in Sekundärspeicher, z.B. auf die Festplatte und zurück.

⇒ Demo 1

Überblick

1) Realer Speicher: Ein Prozess kann nur dann laufen, wenn sich sein Adressraum vollständig im Speicher befindet.

2) Virtueller Speicher: Ein Prozess kann auch dann laufen, wenn sich nur ein Teil seines Adressraums im Speicher befindet.

7.2. Realer Speicher

Systeme ohne Speicherabstraktion

Im Hauptspeicher steht das Betriebssystem und ein einziges Anwenderprogramm.

Besonderheiten:

1) Logische und physische Adressen sind gleich.

2) Physische Adressen können zur Übersetzungszeit schon bekannt sein.

3) Es gibt keinen Speicherschutz. Ein Fehler im Anwendungsprogramm kann das Betriebssystem aushebeln, wenn es sich nicht im ROM befindet.

4) Diese Technik ist für Monoprogrammierung (Singletasking, Einprogrammbetrieb) geeignet und wird heute höchstens in einfachen eingebetteten Systemen verwendet. Frühes Beispiel: MS-DOS.

Variable Partitionierung

Definition:

Variable Partitionierung (Partitionierung variabler Größe) ist eine dynamische Aufteilung des Speichers in eine variable Anzahl von Bereichen variabler Größe.

Sachverhalt:

1) Speichersystem bedient die beliebige Reihenfolge von Reservierungen und Freigaben.

2) Reservierungen fordern Bereiche mit verschiedenen Größen.
3) Im Laufe der Zeit wird der Speicher in verschiedene belegte und freie Bereiche (Lücke) geteilt.
4) Wenn eine gefundene Lücke größer als benötigt ist, wird der Rest als neue Lücke markiert.
5) Wenn die passende Lücke nicht gefunden wird, wird die Reservierung abgelehnt.
6) Wenn zwei benachbarte Lücken frei sind, werden diese zu einer Lücke verschmolzen. Eine Verschmelzung wird als Rekombination bezeichnet.



Legende: P1, P2, P3, P4 – Prozesse.

Zeitpunkte:

1. Drei Prozesse am Laufen.

1. Prozess P1 endet. Freigabe. Lücke entsteht.

1. Prozess P4 kommt. Reservierung. Neue Lücke entsteht.

1. Prozess P2 endet. Rekombination von zwei Lücken

Dynamische Relokation

Bei der Partitionierung wird die Anfangsadresse eines Programms erst zur Ladezeit bekannt. Damit wird auch die Adresstransformation erst zur Ladezeit möglich.

Dynamische Relokation ist eine Technik für die Speicherabbildung zur Laufzeit:

1) Der Adressraum jedes Prozesses wird komplett in den Speicher geladen.

2) Die Adresstransformation findet bei jedem Speicherzugriff statt. Zu der logischen Adresse wird der Inhalt eines Basisregisters (oder Relokationsregisters) addiert. Das Basisregister enthält die physikalische Partitionsstartadresse.
Das Programm kann auch zur Laufzeit mit logischenAdressen arbeiten.

3) Für die korrekte Speicherabbildung ist der Zugriffsschutz notwendig. Bei jedem Speicherzugriff wird überprüft, ob die Adresse
innerhalb des Adressraums liegt. Dazu dient ein Grenzregister (Schutz-Register, Limitregister), das die Größe des Adressraums enthält.

4) Beim Prozesswechsel werden beide Register umgesetzt.

Bemerkungen:

1) Dynamische Relokation bietet eine Abstraktion vom physischen Speicher. Die Speicherverwaltung ist für den Programmierer transparent.
2) Der Grad der Multiprogrammierung wird von der Speichergröße abhängig.

3) Eine frühere Lösung war die statische Relokation. Dabei werden alle Adressen im Programm reloziert, wenn das Programm in den Speicher geladen wird.

Swapping

Grungidee: Wenn ein Prozess im Moment keine Rechenzeit benötigt, dann wird sein Adressraum komplett in Sekundärspeicher ausgelagert.

Verwendung:

1) Diese Technik wurde in Systemen ohne Speicherabstraktion verwendet, um mehrere Programme gleichzeitig auszuführen.

2) Swapping lässt sich mit variabler Partitionierung kombinieren:

1. Bei Speichermangel werden Prozesse ausgelagert.

1. Die freigewordenen Speicherbereiche werden für neue oder für ausgelagerte Prozesse genutzt.

1. Die Gesamtzahl der gestarteten Prozesse entspricht nämlich der Summe der ausgelagerten und nicht ausgelagerten Prozesse.

1. Swapping wurde bei älteren Unix-Systemen eingesetzt.

7.3.Freispeicherverwaltung

Grundidee

Das Ziel der Verwaltung des freien Speichers (dynamische Speicherbereitstellung) ist die effiziente Nutzung des realen Speichers. Dabei sollen die Zeit der Speicherzuteilung und die Fragmentierung minimiert werden.

Eine externe Fragmentierung (Zerstückelung, Verschnitt, Zersplitterung) ist ein Speicherzustand mit den schlecht nutzbaren Lücken. Im Laufe der Zeit entstehen überall im Speicher freie Bereiche, die teilweise zu klein sind, um Adressräume hineinladen zu können. Dabei kann eine neue Reservierung nicht erfüllt werden, obwohl insgesamt genügend Speicher frei ist.

Eine interne Fragmentierung ist der ungenutzte Teil des zugeteilten Speicherbereiches.

Einige Techniken

1) Speicherverdichtung (Kompaktierung, Verschiebung) ist eine Technik, bei der alle belegten Bereiche umkopiert werden, so dass nur eine große Lücke vorhanden ist.
Nachteil: Diese Technik ist zeitfressend und wird normalerweise nicht eingesetzt.

2) Abrundung: Wenn der Rest der Lücke zu klein ist, dann wird ganze Lücke reserviert.
Vorteil: Im Speicher entstehen keine kleine Lücken
Nachteil: Interne Fragmentierung.

3) Speicherbereinigung (Garbage Collection): Freigabe und aufwendige Rekombinationen werden automatisch zu einem späteren Zeitpunkt durchgeführt.
Vorteil: Optimalerweise findet eine Speicherbereinigung immer in Leerlaufphasen statt.

Belegungsstrategien

Belegungsstrategien (Allokations-Algorithmen) sind Algorithmen, die nach einer passenden Lücke im fragmentierten Speicher suchen.

1) Sequentielle Belegungsstrategien, welche eine einzige Liste oder andere Datenstruktur für alle Lücken führen.

2) Strategien mit festen Größenklassen (separierten Freilisten), welche mehrere Listen für verschiedene Lückengrößen führen.

Sequentielle Belegungsstrategien

Name	Die Suche beginnt	Gesuchte Lücke	Erzeugte Lücken
First Fit/ Last Fit	am Speicheranfang	erste/ letzte	Kleine Lücken entsteh- en am Anfang/am Ende des Speichers
Next Fit	am letzten allokierten Bereich.	erste	Kleine Lücken sind gleichmäßig überall.
Best Fit/ Worst Fit	am Speicheranfang	kleinste/ größte	Tendiert zum Erzeugen kleiner/großer Lücken

Vorteile: Es gibt keine innere Fragmentierung.
Nachteile:

1. Wesentliche externe Fragmentierung.

1. Sequentielle Algorithmen sind langsam, besonders Best Fit und Worst Fit.

Sequentielle Belegungsstrategien. Beispiel

1) Ausgangssituation(in MB):

Strategien mit separierten Freilisten

1) Quick Fit führt mehrere getrennte Listen für verschiedene Lückengrößen. Diese Strategie ist sinnvoll, wenn alle Anforderungen von gleichen oder bestimmten häufig benötigten Größen sind.

Vorteile:

1. Diese Strategie ist extrem schnell bei der Reservierung.

1. Keine Fragmentierung.

Nachteil:


2) Buddy–Algorithmus verteilt den Speicher in Größen von Zweierpotenzen. Alle Anforderungen müssen also auf die nächste Zweierpotenz aufgerundet werden.

Vorteil:

Nachteil:

Buddy-Algorithmus

Verwaltungsdaten:

1) Der Speicher wird in Größen von Zweierpotenzen verteilt. Jede Anforderung muss auf die nächste Zweierpotenz 2^k aufgerundet werden.

Eine Anforderung in 280 Bytes wird z.B. auf 2⁹ = 512 Bytes aufgerundet.

2) Für jede Speichergröße wird eine eigene Liste verwendet.Es gibt Listen für die folgende Blockgrößen:
2⁰ , 2¹ , 2² … 2^S Byte, wo 2^S - Speichergröße ist.

Anfangs sind alle Listen leer, nur in der 2^S -Liste ist ein einziger Block (der gesamte Speicher).

3) Jeder Block wird markiert: reserviert oder frei.


Speicheranforderung:

1) Ein Block 2^k wird aus der entsprechenden Liste zugeteilt.

2) Ist kein Block der gewünschten Größe frei, werden schrittweise die höheren Blockgrößen geprüft, bis ein freier Block gefunden wird.

3) Wird kein Block gefunden, wird die Speicheranforderung abgelehnt.

4) Der gefundene Block wird durch iterierte Halbierung soweit zerlegt, bis ein Block der benötigten Größe 2^k entsteht.

Bei jeder Halbierung entstehen zwei doppelt kleinere Blöcke der gleichen Größe (Buddies, Kumpel).


Freigabe:

1) Bei jeder Freigabe muss die Rekombination mit den benachbarten Blöcken derselben Größe geprüft werden.
Zwei benachbarte Blöcke der Große 2^k mit Adressen x und y sind Buddies, wenn die folgende Bedingung zutrifft:

y == x XOR 2^k

Bei der Rekombination entsteht ein Block der doppelten Größe 2^k+1.
2) Im Erfolgsfall muss auch die Rekombination der Blöcke mit höherer Größe iteriert geprüft werden.


Beispiel:

(1) Anfänglich besteht der Speicher aus einem kontinuierlichen Block 64 K.

(2) Zwei Anforderungen 8 K fallen an. Der Block 64 K wird dreimal halbiert. Beide Anforderungen werden erfüllt.

(3) Vier Anforderungen 4 K fallen an. Der Block 16 K wird zweimal halbiert und alle Anforderungen werden erfüllt.

(4) Zweite und dritte Blöcke 4 K werden freigegeben. Bei der Rekombinations-Prüfung wird kein Buddy gefunden.

(5) Der erste Block 4 K wird freigegeben. Bei der Prüfung werden zwei Buddies gefunden und rekombiniert.

Belegungsstrategien. Fazit

Keine der Strategien ist ideal, da praktische Situationen sehr unterschiedlich sind.

Zum Beispiel, es sei gegeben:

1. zwei Lücken 1300 und 1200 Bytes,

1. drei Aufträge 1000, 1100 und 250 Bytes.

Belegung und neu markierte Lücken:

Strategie	1.Auftrag	2.Auftrag	1.Auftrag
First Fit	1300-1000= 300	1200-1100= 100	300-250= 50
Best Fit	1200-1000= 200	1300-1100= 200	Reservierung abgelehnt

Verwendung der Freispeicherverwaltung

1) für Multitasking in einfachen Systemen, z.B.:

• Belegung mit variablen Partitionen

• Swapping;

2) im Betriebssystem selbst, z.B.:

• für innere Speicherverwaltung

• Speicherzuordnung für Treiber;

3) in Anwendungsprogrammen, z.B.:

• Heap Management.

⇒ Demo 2

---

CategoryBSys