33
bs-5 1 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher (memory) Sekundärspeicher/Hintergrundspeicher (backing store) Tertiärspeicher/Archivspeicher Adressraum (address space)

Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

Embed Size (px)

Citation preview

Page 1: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 1

5 Speicherverwaltung

Pufferspeicher (cache)

Primärspeicher/Arbeitsspeicherrealer Speicher (memory)

Sekundärspeicher/Hintergrundspeicher(backing store)

Tertiärspeicher/Archivspeicher

Adressraum (address space)

Page 2: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 2

5.1 Elementare Adressraumverwaltung

Zur Erinnerung – Arbeitsspeicher und Prozessor:

Speicheradresse, reale Adresse (memory/physical address)

identifiziert Arbeitsspeicherzelle (location)

Programmadresse, virtuelle Adresse (program/virtual address)

= vom Prozessor formulierbare Adresse

Adressraum des Prozessors (processor address space)

= alle Programmadressen

Page 3: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 3

5.1.1 Adressumsetzung

Prozessor4711

ist Aufgabe der Hardware:

Adressumsetzer (memory management unit, MMU)

bildet Programmadressen auf Speicheradressen ab:

MMU ArbeitsspeicherSpeicherzugriff

2503476

Page 4: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 4

MMU für zusammenhängende Speicherbereiche:

Basisregister (base register), enthält Basisadresse,

Längenregister (length register), enthält Länge.

Page 5: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 5

MMU für zusammenhängende Speicherbereiche:

Basisregister (base register), enthält Basisadresse,

Längenregister (length register), enthält Länge.

Adressumsetzung für eine Programmadresse address:

if address < length

then location = base + address

else address fault trap

base location (Speicheradressen)

Arbeits-speicher

0 address (Programmadressen)

length

Page 6: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 6

Basisadresse und Länge

werden üblicherweise in größeren Einheiten gemessen

(z.B. units, blocks, ...)

Vereinfachende Voraussetzung:

Block im Speicher entspricht

Sektor/Block im Hintergrundspeicher (Platte)

Page 7: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 7

„Adressraum“ wird auch in anderer Bedeutung gebraucht:

aktueller Adressraum des Prozessors= alle aktuell erlaubten Programmadressen,

z.B. bei obiger MMU alle address < length

Adressraum eines Prozesses= gemäß einem Prozessattribut length alle address < length

oder auch= Inhalt (Code + Daten) eines Prozesses

oder auch= Code+Daten-Paket, das einmal Inhalt eines Prozesses werden kann

Page 8: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 8

Prozessormodus (processor mode) (Bits im PSW)

– z.B. user/system oder user/supervisor/kernel oder ... –

bestimmt

Zulässigkeit privilegierter Befehle,

evtl. Unterbrechungsunterdrückung,

aktuellen Adressraum des Prozessors, z.B.

im Benutzermodus: Adressumsetzung wie oben,im Systemmodus: Adressumsetzung abgeschaltet (!)

oderAdressumsetzung mit anderem

Registersatz

Page 9: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 9

Adressraumwechsel

bei Wechsel des Prozessormodus im PSW, d.h.

bei Unterbrechung

bei IRET/RTI

Merke: Eine Unterbrechung führt i.d.R. zu einem

neuen Adressraum – das muss aber nicht

notwendig so sein (BS bestimmt neues PSW!).

Beachte: Der neue Adressraum kann sich mit dem

alten überlappen oder kann von diesem

völlig disjunkt sein.

Page 10: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 10

5.1.2 Adressraumumschaltung

Betriebssystem profitiert von der Adressumsetzung:

Verschieblichkeit (relocatability) von Prozessen:Programm kann an beliebige Stelle des Speichers

geladen werden, ohne dass dabei Adressen im Programm (z.B Sprungadressen) entsprechend angepasst werden müssten; Prozesse können ohne Modifikation verschoben werden.

Speicherschutz (memory protection): Prozess kann weder absichtlich noch unabsichtlich auf andere als die ihm zugeordneten Speicherzellen zugreifen.

Page 11: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 11

Inhalt der MMU-Register ist Teil des Prozessorstatus

und damit auch Teil des Prozessstatus !

Betriebssystem ist zuständig für geeignetes

Laden der MMU-Register bei Aktivierung eines Prozesses

(vgl. 3.2 und 3.5.2 2)

mit privilegiertem Befehl oder über spezielle Adressen.

! Unterscheide also zwischen

Adressraumumschaltung als Teil der Prozessumschaltung,

tatsächlichem Adressraumwechsel (Unterbrechung, RTI).

Page 12: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 12

5.1.3 Adressraumänderung

Prozessattribute base/length : Initialisierung ? Änderung ?

! Muss notwendig von der Speicherverwaltung ausgehen,

die über die Speicherbelegung Buch führt ( 5.2)

2 Varianten:

Speicherverwaltung greift direkt auf Prozessdeskriptor zu– falls im gleichen Adressraum wie Prozessverwaltung –

Speicherverwaltung benutzt entsprechende Operationder Prozessverwaltung

Page 13: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 13

Prozessattribute base/length werden gesetzt beim

Initialisieren eines Prozesses (fork) – length kopieren vom Erzeuger,base gemäß Speicherbelegung

Laden eines Programms (exec) – length gemäß Angabe in Datei, base gemäß Speicherbelegung

Verschieben des Prozesses –base gemäß Speicherbelegung

Verändern der Adressraumgröße (brk u.ä.) – length ändern, eventuell auch base , falls Verschieben erforderlich

Page 14: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 14

5.2 Elementare Arbeitsspeicherverwaltung

für zusammenhängende Speicherbereiche, ohne Umlagerungen:

Aufruf impliziert

fork Belegung (allocation, Zuweisung) für neuen Prozess[Alloziierung – falsche Übersetzung]

exec Vergrößern/Verkleinern des Prozessbereichs

brk Vergrößern/Verkleinern des Prozessbereichs

exit Freigabe (deallocation) des Prozessbereichs

Page 15: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 15

Typische Schnittstelle der Buchführung über Speicherbelegung:

interface Allocation {

int allocate(int length); // belegt Bereich der Größe length // und liefert dessen Adresse, // sofern verfügbar, sonst 0

void deallocate(int base, int length); // gibt Bereich der Größe length frei, // der bei base beginnt }

Page 16: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 16

Typische Implementierungen wie für die Halde (ALP 3!):

Repräsentation: Bitlisteverkettete Liste

Belegungsstrategien: first-fit, ...

Problem: Speicherverschnitt, extern/intern (fragmentation)

Externer Verschnitt kann im Prinzip durch

Kompaktifizierung (compaction)

beseitigt werden (wenig üblich).

Page 17: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 17

Verschiebung einzelner Prozesse ist aber unvermeidlich,

wenn Vergrößern unterstützt werden soll,

wenn dadurch für neuen Prozess Platz geschaffen

werden kann, der sonst nicht vorhanden ist

Dank der MMU ist Verschiebung einfach realisierbar !

(Übung: implementiere Kompaktifizierung !)

Page 18: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 18

5.3 Prozessumlagerung(process) swapping

= Umlagerung des Adressraums eines Prozesses

zwischen Arbeitsspeicher und Hintergrundspeicher,

falls Arbeitsspeicher zu klein für alle Prozesse

(aber groß genug für jeden einzelnen Prozess!)

Arbeits-speicher

Auslagerungsbereich(swap area)

auslagern (swap out)

einlagern (swap in)

(so im Ur-Unix; bei alten IBM-Systemen: „roll-in/roll-out“)

Page 19: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 19

Prozessor aktiv

Arbeitsspeicher

blockiert bereit

3. Ressource schlafend wartend

Zustände eines Prozesses (vgl. 1.1.2),

bezogen auf den Besitz der Betriebsmittel

1.Prozessor,2.Arbeitsspeicher,3.3. Ressource:

Page 20: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 20

Entwurf der Speicherverwaltung (vgl. 4.2 ):

Aufrufe/Aufträge, z.B. durch fork, brk, ...

OperationenUmlagerer(swapper)

Verwaltungsdaten

hochpriorisierter, speicherresidenter Systemprozess,regelmäßig aktiv nach Ablauf eines

Zeitquantums

(quantum timeSlice)

Page 21: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 21

5.3.1 Verwaltungsdaten

Speicherverwaltung führt Buch über

• Arbeitsspeicherbelegung (wie in 5.2) Allocation memory

• Belegung des Auslagerungsbereichs Allocation swaparea

• eingelagerte Prozesse SwapoutList present

• ausgelagerte Prozesse SwapinList absent

Page 22: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 22

Auch bei der Umlagerung ist wichtig die

Trennung von Mechanismen und Strategien:

Auslagerungstrategie

wird bestimmt durch die Implementierung von

present.remove()

Einlagerungstrategie

wird bestimmt durch die Implementierung von

absent.remove()

Page 23: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 23

5.3.2 Umlagerungsmechanismen

Achtung: nicht alle Prozesse müssen auslagerbar sein;

z.B. können dringliche Systemprozesse

grundsätzlich speicherresident sein.

Jedem auslagerbaren Prozess ist eine physikalischzusammenhängende Folge von Blöcken/Sektoren im Auslagerungsbereich zugeordnet. Die Nummer desersten Blocks heißt Auslagerungsadresse. Die Basis-adresse base eines ausgelagerten Prozesses ist 0 .

Page 24: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 24

Voraussetzungen:

Für den Zugriff auf den Auslagerungsbereich gibt es

einen Plattentreiber mit Schnittstelle (statt IO(4.2))

interface Driver {void input (int base, int length, int addr);void output(int base, int length, int addr);}

Eine Klasse Timer erlaubt die Erzeugung von virtuellen

Zeitgeber-Objekten:

class Timer {...public wait(int time);}

Page 25: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 25

Die Klasse Process verfügt über Operationen

start/stop : stop versetzt einen Prozess in einen

Zustand, in dem er bei der Auswahl aus der Bereitliste

ignoriert wird; start erlöst ihn aus diesem Zustand.

Der Umlagerungsprozess befindet sich im gleichen

Adressraum wie der Kern.

Ein/Ausgabe der Prozesse wird über Pufferbereiche

des E/A-Systems abgewickelt, nie direkt zwischen Gerät

und Prozess-Adressraum.

Page 26: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 26

class SwappableProcess extends Process {static final Driver disk = ...;

final int backupBase; // Auslagerungsadresse

final int backupLength;// Anzahl der Blöcke

final int swapTime; // letzte Umlagerung

public void swapout() { disk.output(backupBase,

backupLength, status.base);}// (3.1)

public void swapin() { disk.input (backupBase,

backupLength, status.base);}

}

Page 27: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 27

public SwappableProcess(SwappableProcess p){ super(); if(p != null){ status = p.status;

backupLength = p.backupLength; }}

(Konstruktor erlaubt „Klonen“ zum Zwecke von fork)

Page 28: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 28

process Swapper {

static final Timer timer = new Timer();

static final int freeMemory = ...;static final Allocation memory

= new Allocation(freeMemory);

static final int freeDisk = ...;static final Allocation swaparea

= new Allocation(freeDisk);

static final SwapoutList present = new SwapoutList();

static final SwapinList absent = new SwapinList(memory);

Page 29: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 29

static{while(true) { // swapper permanent loop

timer.wait(quantum);

Process victim = present.remove(); if(victim == null) continue; swapout(victim); // siehe unten

do {Process lucky = absent.remove(); if(lucky == null) break;

swapin(lucky); // siehe unten

while(true);}

Page 30: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 30

private void swapout(Process victim){ victim.stop(); victim.swapout(); // swapper blocks! memory.deallocate(victim.base,victim.length); absent.add(victim);}

private void swapin(Process lucky){ present.add(lucky); lucky.base = memory.allocate(lucky.length); lucky.swapin(); // swapper blocks! lucky.start();}

Page 31: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

31

public int fork(){//from first-level trap handler SwappableProcess parent

= (SwappableProcess)Process.current(); SwappableProcess child

= new SwappableProcess(parent); // has new pid, is ready but stopped

child.backupBase = swaparea.allocate(current.backupLength);

if(child.backupBase == 0) return –11; //EAGAIN // swap area overflow, child becomes garbage

child.status.EAX = 0; // child gets result 0 child.swapout(); absent.add(child); return child.pid; // parent gets result pid} // via trap handler} // end of Swapper

Page 32: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 32

5.3.3 Umlagerungsstrategien

verbergen sich in der Implementierung von

SwapoutList present (eingelagerte Prozesse)

SwapinList absent (ausgelagerte Prozesse)

Ziel Effizienz/Ressourcennutzung:möglichst viele bereite Prozesse im Arbeitsspeicher !kleine bereite Prozesse bevorzugen, hochpriorisierte Prozesse möglichst nicht auslagern

Nicht vergessen Fairness:bereite Prozesse rotierend umlagern

Page 33: Bs-51 5 Speicherverwaltung Pufferspeicher (cache) Primärspeicher/Arbeitsspeicher realer Speicher(memory) Sekundärspeicher/Hintergrundspeicher (backing

bs-5 - letzte Folie 33

Zusätzliches Problem:

ein langzeitig blockierender Prozess

– z.B. beim Warten auf Eingabe von der Tastatur –

sollte auch vor Ablauf seines Quantums ausgelagert werden,

wenn es ausgelagerte, bereite Prozesse gibt.

ein kurzzeitig blockierender Prozess aber

– z.B. beim Warten auf Leeren eines Ausgabepuffers –

sollte nicht unbedingt ausgelagert werden,

Zwei Arten von Blockaden unterscheiden, Mechanismen entsprechend erweitern

und mit der Strategie ausnutzen !