CS计算机代考程序代写 compiler ER assembler Betriebssysteme

Betriebssysteme
Besprechung: 4. Speicherverwaltung
https://ess.cs.tu-dortmund.de/DE/Teaching/SS2020/BS/
Horst Schirmeier
horst.schirmeier@tu-dortmund.de
https://ess.cs.tu-dortmund.de/~hsc
AG Eingebettete Systemsoftware mit Material von Olaf Spinczyk, Informatik 12, TU Dortmund Universität Osnabrück

1. Speicherverwaltung bei Mehrprogrammbetrieb
Nennt die verschiedenen Arten der Adressbindung und erklärt in eigenen Worten deren Vor-/Nachteile.
2

1. Speicherverwaltung bei Mehrprogrammbetrieb
Nennt die verschiedenen Arten der Adressbindung und erklärt in eigenen Worten deren Vor-/Nachteile.
● AbsolutesBinden(Compile/LinkTime)
– Das Programm nur an einer bestimmter Speicherstelle korrekt ablaufen
3

1. Speicherverwaltung bei Mehrprogrammbetrieb
Nennt die verschiedenen Arten der Adressbindung und erklärt in eigenen Worten deren Vor-/Nachteile.
● AbsolutesBinden(Compile/LinkTime)
– Das Programm nur an einer bestimmter Speicherstelle
korrekt ablaufen
● StatischesBinden(LoadTime)
– Compiler/Assembler muss Relokationsinformation liefern
4

1. Speicherverwaltung bei Mehrprogrammbetrieb
Nennt die verschiedenen Arten der Adressbindung und erklärt in eigenen Worten deren Vor-/Nachteile.
● AbsolutesBinden(Compile/LinkTime)
– Das Programm nur an einer bestimmter Speicherstelle
korrekt ablaufen
● Statisches Binden (Load Time)
– Compiler/Assembler muss Relokationsinformation liefern
● Dynamisches Binden (Execution Time)
+ Das Programm kann jederzeit im Speicher verschoben
werden
– Programme werden etwas größer und langsamer
5

2. Seitenadressierung
logischer Adressraum
physikalischer Adressraum
ROM
RAM
Seiten
(pages)
Kacheln
(frames)
6

2. Seitenadressierung
a) Bei der Seiteneinlagerung kann sich der zugeordnete physikalische Adressbereich ändern. Muss das Betriebssystem diesen Fall gesondert behandeln?
logischer Adressraum
physikalischer Adressraum
ROM
RAM
Seiten
(pages)
Kacheln
(frames)
7

2. Seitenadressierung
a) Bei der Seiteneinlagerung kann sich der zugeordnete physikalische Adressbereich ändern. Muss das Betriebssystem diesen Fall gesondert behandeln?
● EsmussinjedemFalldieSeitentabelle(Präsenzbit,ggf. phys. Adresse) aktualisieren. Aus Sicht des Programms ändert sich nichts, da es logische Adressen nutzt.
logischer Adressraum
physikalischer Adressraum
ROM
RAM
Seiten
(pages)
Kacheln
(frames)
8

2. Seitenadressierung
9

2. Seitenadressierung
b) Warum muss bei einem Kontextwechsel der TLB geleert werden?
10

2. Seitenadressierung
b) Warum muss bei einem Kontextwechsel der TLB geleert werden?
● VerschiedeneProzessehabenverschiedene Speicherbereiche
→ Abbildung auf physikalische Adressen ist unterschiedlich, alte Informationen sind falsch
11

3. Platzierungstrategien
Best Fit
●
12

3. Platzierungstrategien
Best Fit
– Overhead durch aufwändige Verwaltung der Löcherlisten
●
13

3. Platzierungstrategien
Best Fit
– Overhead durch aufwändige Verwaltung der Löcherlisten
– Hohe Chance sehr kleine, nicht mehr nutzbare Speicherbereiche zu hinterlassen
●
14

3. Platzierungstrategien
Best Fit
– Overhead durch aufwändige Verwaltung der Löcherlisten
– Hohe Chance sehr kleine, nicht mehr nutzbare Speicherbereiche zu hinterlassen
+ Reduziert den externen Verschnitt
●
●
First Fit
15

3. Platzierungstrategien
Best Fit
– Overhead durch aufwändige Verwaltung der Löcherlisten
– Hohe Chance sehr kleine, nicht mehr nutzbare Speicherbereiche zu hinterlassen
+ Reduziert den externen Verschnitt
●
●
First Fit
– Nicht-optimale Belegung des Speichers => externer Verschnitt
16

3. Platzierungstrategien
Best Fit
– Overhead durch aufwändige Verwaltung der Löcherlisten
– Hohe Chance sehr kleine, nicht mehr nutzbare Speicherbereiche zu hinterlassen
+ Reduziert den externen Verschnitt
●
●
First Fit
– Nicht-optimale Belegung des Speichers => externer Verschnitt
– Kleine Lückenbildung am Anfang des Speichers
17

3. Platzierungstrategien
Best Fit
– Overhead durch aufwändige Verwaltung der Löcherlisten
– Hohe Chance sehr kleine, nicht mehr nutzbare Speicherbereiche zu hinterlassen
+ Reduziert den externen Verschnitt
●
●
First Fit
– Nicht-optimale Belegung des Speichers => externer Verschnitt
– Kleine Lückenbildung am Anfang des Speichers
+ Einfache Implementierung, da erste ausreichende Lücke verwendet wird
18

Programmierung: Next Fit
a) Speicherallokation
● nf_alloc(size_t size) soll size Bytes großen
Speicherbereich nach Next-Fit-Verfahren belegen
● StartadressedesbelegtenSpeicherbereichszurückgeben
● Fehlerfälle:
– 0 Bytes angefragt → NULL zurückgeben – nicht genug freier Speicher → NULL zurückgeben
19

a) Speicherallokation
size_t last_alloc = 0;
size_t last_alloc = 0;
void *nf_alloc(size_t size) {
void *nf_alloc(size_t size) {
/* Fall size == 0 abfangen */
/* Fall size == 0 abfangen */
/* size_to_chunks wandelt Anzahl an Bytes in Anzahl benötigter Chunks um */
/* size_to_chunks wandelt Anzahl an Bytes in Anzahl benötigter Chunks um */
size = size_to_chunks(size);
size = size_to_chunks(size);
/* find_gap gibt Startindex einer passenden Lücke zurück */
/* find_gap gibt Startindex einer passenden Lücke zurück */
size_t chunk_index = find_gap(size);
size_t chunk_index = find_gap(size);
/* Fall chunk_index nicht mehr innerhalb von heap → Fehlerbehandlung */ /* Fall chunk_index nicht mehr innerhalb von heap → Fehlerbehandlung */
if (allocation_list[chunk_index].length > size) { if (allocation_list[chunk_index].length > size) {
}
/* Hinter unserem Speicher entsteht neuer freier Speicherbereich
/* Hinter unserem Speicher entsteht neuer freier Speicherbereich
-> Dementsprechend markieren */
-> Dementsprechend markieren */
allocation_list[chunk_index + size].status = CHUNK_FREE; allocation_list[chunk_index + size].status = CHUNK_FREE;
allocation_list[chunk_index + size].length = allocation_list[chunk_index + size].length =
allocation_list[chunk_index].length – size; allocation_list[chunk_index].length – size;
allocation_list[chunk_index].status = CHUNK_ALLOCATED; allocation_list[chunk_index].status = CHUNK_ALLOCATED;
allocation_list[chunk_index].length = size; allocation_list[chunk_index].length = size;
}
/* Speicherbereich belegen */
/* Speicherbereich belegen */
last_alloc = chunk_index;
20
}
return heap + chunk_index * CHUNK_SIZE;
return heap + chunk_index * CHUNK_SIZE;
}
last_alloc = chunk_index;

a) Speicherallokation
static size_t find_gap(size_t req_size) {
static size_t find_gap(size_t req_size) {
size_t i = 0;
size_t i = 0;
for (i = last_alloc; i < NUM_CHUNKS; ) { for (i = last_alloc; i < NUM_CHUNKS; ) { } return NUM_CHUNKS; return NUM_CHUNKS; } } } } } /* gleich wie oben */ } if (allocation_list[i].status == CHUNK_ALLOCATED) { if (allocation_list[i].status == CHUNK_ALLOCATED) { i += allocation_list[i].length; } else { i += allocation_list[i].length; } else if (allocation_list[i].length < req_size) { } else if (allocation_list[i].length < req_size) { i += allocation_list[i].length; i += allocation_list[i].length; } else { } return i; return i; for (i = 0; i < last_alloc; ) { for (i = 0; i < last_alloc; ) { /* gleich wie oben */ /* Kein genügend großer Speicherbereich gefunden */ /* Kein genügend großer Speicherbereich gefunden */ 21 Programmierung: Next Fit b) Speicherfreigabe ● nf_free(void *addr) soll belegten Speicherbereich freigeben ● erhältStartadresseeinesSpeicherbereichsalsArgument ● allocation_list und last_alloc entsprechend aktualisieren ● Speicherbereichedavorund/oderdanachggf.mitaktuellem vereinigen ● Fehlerfälle: ● - NULL übergeben ● - Adresse ungültig* → nichts soll passieren → Fehlermeldung und Programm mit Fehlercode 255 beenden *Adresse nicht Startadresse eines belegten Speicherbereichs oder liegt nicht im Arbeitsspeicher 22 b) Speicherfreigabe (1) extern size_t last_alloc; extern size_t last_alloc; void nf_free(void *addr) { void nf_free(void *addr) { } } /* Fall addr == NULL abfangen */ /* Fall addr == NULL abfangen */ /* Fall addr außerhalb von unserem Speicher */ /* Fall addr außerhalb von unserem Speicher */ if ((char*)addr < heap || (char*)addr >= heap + sizeof(heap)) { if ((char*)addr < heap || (char*)addr >= heap + sizeof(heap)) {
printf(“free(%p): Illegal address\n”, addr); printf(“free(%p): Illegal address\n”, addr);
exit(255);
exit(255);
}
}
/* Index des Startblocks des freizugebenen Bereichs */
/* Index des Startblocks des freizugebenen Bereichs */
size_t chunk_index = ((char*)addr – heap) / CHUNK_SIZE; size_t chunk_index = ((char*)addr – heap) / CHUNK_SIZE;
size_t prev_index = 0;
size_t prev_index = 0;
/* Block bereits freigegeben oder nicht Start eines Speicherbereichs */
/* Block bereits freigegeben oder nicht Start eines Speicherbereichs */
if (allocation_list[chunk_index].status == CHUNK_FREE if (allocation_list[chunk_index].status == CHUNK_FREE
|| allocation_list[chunk_index].length == 0) { || allocation_list[chunk_index].length == 0) {
printf(“free(%p): Illegal address\n”, addr); printf(“free(%p): Illegal address\n”, addr);
exit(255);
exit(255);
}
}
…
…
23

b) Speicherfreigabe (2)
void nf_free(void *addr) {
void nf_free(void *addr) {
{
if ((chunk_index + old_size < NUM_CHUNKS) if ((chunk_index + old_size < NUM_CHUNKS) && (allocation_list[chunk_index + old_size].status == CHUNK_FREE)) && (allocation_list[chunk_index + old_size].status == CHUNK_FREE)) allocation_list[chunk_index].length += allocation_list[chunk_index].length += allocation_list[chunk_index + old_size].length; allocation_list[chunk_index + old_size].length; allocation_list[chunk_index + old_size].length = 0; allocation_list[chunk_index + old_size].length = 0; { } } ... ... /* Länge des freizugebenen Speicherbereichs */ /* Länge des freizugebenen Speicherbereichs */ size_t old_size = allocation_list[chunk_index].length; size_t old_size = allocation_list[chunk_index].length; /* An dieser Stelle beginnt jetzt ein freier Speicherbereich */ /* An dieser Stelle beginnt jetzt ein freier Speicherbereich */ allocation_list[chunk_index].status = CHUNK_FREE; allocation_list[chunk_index].status = CHUNK_FREE; /* Falls der nächste Speicherbereich auch frei war, gehört er nun zu uns /* Falls der nächste Speicherbereich auch frei war, gehört er nun zu uns } } ... ... (Freie Speicherbereiche vereinigen) */ (Freie Speicherbereiche vereinigen) */ 24 b) Speicherfreigabe (3) void nf_free(void *addr) { void nf_free(void *addr) { addieren -> Länge des freigegebenen Bereichs zu Länge des voherigen Bereich
…
…
/* Analog: Voherigen Speicherbereich mit unserem vereinigen */
/* Analog: Voherigen Speicherbereich mit unserem vereinigen */
/* Finden des Index des Bereichs vor uns */
/* Finden des Index des Bereichs vor uns */
size_t prev_index = 0;
size_t prev_index = 0;
if (chunk_index > 0) {
if (chunk_index > 0) {
addieren
}
}
}
}
}
while (prev_index + allocation_list[prev_index].length < chunk_index) { while (prev_index + allocation_list[prev_index].length < chunk_index) { prev_index += allocation_list[prev_index].length; prev_index += allocation_list[prev_index].length; /* Falls Speicherbereich vor uns frei, } /* Array durchlaufen, bis Index vor freigegebenem Bereich erreicht */ /* Array durchlaufen, bis Index vor freigegebenem Bereich erreicht */ /* Falls Speicherbereich vor uns frei, -> Länge des freigegebenen Bereichs zu Länge des voherigen Bereich
-> Länge des freigegebenen Bereichs auf 0 setzen
-> Länge des freigegebenen Bereichs auf 0 setzen
-> wenn last_alloc == chunk_index dann last_alloc anpassen*/
-> wenn last_alloc == chunk_index dann last_alloc anpassen*/
25

Zusatzaufgabe: Best Fit
● bf_alloc(size_t size) soll size Bytes großen
Speicherbereich nach Best-Fit-Verfahren belegen
● StartadressedesbelegtenSpeicherbereichszurückgeben
● Fehlerfälle:
– 0 Bytes angefragt → NULL zurückgeben – nicht genug freier Speicher → NULL zurückgeben
26

Zusatzaufgabe: Best Fit
/* Keine globale Variable notwendig */
/* Keine globale Variable notwendig */
static size_t find_gap(size_t req_size) {
static size_t find_gap(size_t req_size) {
for (size_t i = 0; i < NUM_CHUNKS; ) { for (size_t i = 0; i < NUM_CHUNKS; ) { } } } } ... ... /* nur else-Fall muss verändert werden */ } /* nur else-Fall muss verändert werden */ } else { } else { } return bestfit; return bestfit; /* Bereich bei Index i ist frei und genuegend Platz ist vorhanden */ /* Bereich bei Index i ist frei und genuegend Platz ist vorhanden */ if(bestfit == NUM_CHUNKS if(bestfit == NUM_CHUNKS || allocation_list[i].length < allocation_list[bestfit].length) { || allocation_list[i].length < allocation_list[bestfit].length) { /* bestfit speichert entweder noch NUM_CHUNKS oder i ist besser geeignet */ bestfit = i; bestfit = i; } } /* bestfit speichert entweder noch NUM_CHUNKS oder i ist besser geeignet */ i += allocation_list[i].length; i += allocation_list[i].length; void *bf_alloc(size_t size) { void *bf_alloc(size_t size) { } } /* wie a) ohne Verwendung von last_alloc */ /* wie a) ohne Verwendung von last_alloc */ void *bf_free(void *addr) { void *bf_free(void *addr) { /* wie b) ohne Verwendung von last_alloc */ /* wie b) ohne Verwendung von last_alloc */ 27 } }