Übungen Betriebssysteme (BS)

U4 – Speicherverwaltung

Alwin Berger

TU Dortmund - AG Systemsoftware

🚀 by Decker

Agenda

Arbeitsspeicherverwaltung
- Paging und Segmentierung
Ersetzungsalgorithmen
- LFU-Algorithmus
- LRU-Algorithmus
Dynamische Speicherverwaltung in C mit malloc und free
Platzierungsstrategie Next Fit

Arbeitsspeicher

Arbeitsspeicher

Speicherlandkarten

Die Menge aller Adressen der Speicherzellen (die einem Prozess zur Verfügung stehen) wird als Adressraum des Prozesses bezeichnet
Die skizzenhafte Darstellung eines Adressraumes als Speicherlandkarte (engl. memory map)

Monolithisch / Defragmentiert: Zusammenhängend

Fragmentiert: Nicht zusammenhängend

Virtuelle Adressen (Motivation)

Virtuelle Adressen (Motivation)

Virtuelle Adressen (Motivation)

Paging (Motivation)

Paging

Paging

Speicherverwaltungseinheit (MMU)

Speicherarchitektur ohne MMU

Speicherarchitektur mit MMU

Holen der Kachelnummer (Falls vorhanden)

Sonderfall: Kachelnummer nicht vorhanden

Zusammensetzen der physikalischen Adresse

Segmentierung

Segmentierung

Segmentierung

Holen der Segmentnummer (Falls vorhanden)

Zusammensetzen der physikalischen Adresse

Präsenzaufgabe: Segmentierung

Präsenzaufgabe: Segmentierung

Präsenzaufgabe: Segmentierung

Präsenzaufgabe: Segmentierung mit Paging

Ersetzungsalgorithmen (Motivation)

Ersetzungsalgorithmen (Motivation)

Präsenzaufgabe: LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

LFU-Algorithmus

Präsenzaufgabe: LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

LRU-Algorithmus

Dynamische Speicherverwaltung

Dynamische Speicherverwaltung in C

Standardbibliotheksfunktion zur Allokation von Speicher:

void* malloc(size_t size)

Reserviert zur Laufzeit Speicher auf dem Heap
Das Argument size legt die Größe des zu reservierenden Bereichs in Bytes fest
Rückgabewerte:
- ≠ NULL, wenn Allokation erfolgreich -> Rückgabewert ist Adresse
- = NULL, wenn ein Fehler aufgetreten ist

Speicherplatz freigeben

Gegenstück zu malloc:

void* free(void *ptr)

Gibt Speicher an Adresse ptr wieder frei
Speicher darf nur einmal freigegeben werden

Array im Heap

int* first_n_squares(unsigned n) {
	int* array;
	array = malloc(n * sizeof(*array)); // ❶ malloc
	if (array == NULL) { // ❷ Fehlerbehandlung
		perror("malloc");
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < n; ++i) {
		array[i] = i * i;
	}
	return array;
}

int main(void) {
	int* ptr;
	ptr = first_n_squares(200);
	printf("10*10 = %d\n", ptr[10]) ;
	free(ptr); // ❸ free
	return 0;
}

Casting von Zeigern

Zeiger lassen sich beliebig in andere Zeigertypen umwandeln.
- Ihr müsst sicherstellen, dass am Zielort genug Speicher reserviert ist.
Beispiel: Wie schreibt man den Int-Wert 0x12345678 in einen Bereich der Größe 42?

char *x = malloc(42);

Der Zeiger x wird gecastet:
- x ist ein Zeiger auf ein char
- ( int* )(x) castet x zu einen Zeiger auf ein int
- Wie gewohnt dereferenzieren:
```
*((int*)(x)) = 0x12345678;
```

Zeiger als einfache Zahl nutzen

Zeigervariablen lassen sich durch Typumwandlung als Zahl Zweck-entfremden oder umgekehrt
- Problem: sizeof(void*) ist plattformabhängig (32b vs. 64b CPUs)
- Umwandlungen zwischen verschieden großen Werten können zu Fehlern führen.
intptr_t(3) und uintptr_t haben immer die richtige Größe.

void* thread_function(void* arg) {
	intptr_t number = (intptr_t)arg; // 9223372036854775807
	int wrong = (int)arg; // -1
	// ...
}
int main() {
	pthread_t thread_id;
	pthread_create(&thread_id, NULL, thread_function, (void*)INTPTR_MAX);
	pthread_join(thread_id, NULL);
	return 0;
}

Speicherplatzierungsstrategien

Platzierung und Fragmentierung finden sich auf verschiedenen Ebenen wieder
- Betriebssystem, Heap in Prozess, Dateien auf Festplatten und mehr
Fokus der heutigen Übung: dynamische Allokation auf dem Heap
- Besprechung “Next Fit” und “Best Fit”

Speicherplatzierungsstrategie ‘Next Fit’

Sucht nächste passende Lücke im Speicher
Merkt sich Position der letzten Allokation, setzt Suche bei nächster Anfrage dort fort
Schnelle Platzierungsstrategie die sich besonders für sehr kleine Blöcke gut eignet

Allokation

Metadaten pro Block (Chunk)
- Status des Blocks: frei oder belegt
- Länge des Blocks; falls 0, ist der Status irrelevant
Anfänglich können Daten hintereinander in den Speicher gelegt werden

Ausgangszustand

Allokation eines Blockes A der Länge 14

Allokation eines Blockes B der Länge 4

Allokation eines Blockes C der Länge 8

Allokation eines Blockes D der Länge 4

Reallokation

Blöcke können realloziert werden, indem der Status entsprechend angepasst wird
Vergrößern ist nur möglich, wenn hinter dem Block eine entsprechend große Lücke frei ist