Speicherverwaltung Flashcards
Was passiert bei der statischen Relokation?
Objektdaten werden vom Binder verschoben, da alle Codestücke sich einen linearen Speicherbereich teilen
Swapping
Was beinhaltet Swapping?
- Auslagern ganzer Prozesse
- Speicher freigeben
- Ein anderes Programm in den freigewordenen Speicher einlagern
Fragmentierung (Verschnitt)
Wie entsteht interner Verschnitt?
- Der Speicher wird in Vielfachen von festen Blockgrößen vergeben
- Anforderungen werden auf das nächste Vielfache gerundet
- Dadurch ensteht Speicherplatz, der als belegt gekennzeichnet ist, aber nicht benutzt wird
Fragmentierung (Verschnitt)
Wie entsteht der externe Verschnitt?
- Durch die Dynamik des Belegens und Freigebens kann es vorkommen, dass eine Anforderung zwar von der Gesamtmenge des freien Speichers her erfüllbar wäre, durch die Zerstückelung jedoch kein hinreichend großes Stück gefunden werden kann.
- Dadurch entsteht Speicherplatz, der frei, aber (momentan) nicht belegbar ist
Freispeicherverwaltung: Reihenfolge
Welche Verfahren gibt es?
- In gleicher Reihenfolge: FIFO = First in First Out
- In umgekehrter Reihenfolge: LIFO = Last in First Out
Freispeicherverwaltung; Granularität
Nenne Punkte zur Granularität
- Konstante Einheiten: NUM = 1
- Vielfache gleicher Grundeinheiten: NUM = k
- Bestimmte Portionsgrößen: NUM = k1, k2, k3
- Beliebige Größen: NUM = x
Freispeicherverwaltung mit Bitmaps
Wie wird der Speicher unterteilt?
- Der Speicher wird in Blöcke gleicher Größe eingeteilt.
- Jeder Block hat ein Bit in der Bitmap, 1 = belegt, 0 = frei
- Je größer der Block, desto kleiner die Bitmap und desto größer der interne Verschnitt
- Es hat eine Laufzeit von O(n)
Freispeicherverwaltung mit Listen
Wie werden belegte und freie Speicherbereiche verkettet?
Belegte und freie Speicherbereiche werden mit einer linearen Liste verkettet
Freispeicherverwaltung mit Listen
Was ist der Nachteil der Listen?
Die Suche nach freiem Speicherplatz dauert lange und die Laufzeit bleibt theoretisch bei O(n)
Objekt-Orientierte Programme
Warum stellen OO-Programme besondere Herausforderungen an die Speicherverwaltung des Laufzeitsystems?
- Sehr viele Speicheranforderungen
- Meistens kleine Speicherbereiche
- Massenweise Freigabe durch den Garbage Collector
Objektorientierte Programme
Welche Optimierungen gibt es?
- Es macht Sinn “Konfektionsware” vorrätig zu haben
- Verspätetes Zusammenführen kann hilfreich sein
Buddy System alias “Halbierungsverfahren”
Aus wie viel Bytes besteht der Speicher?
Der Speicher besteht aus 2^kmax Bytes und wird in den Größen 2^min, 2^min+1… vergeben
Buddy System alias “Halbierungsverfahren”
Was wird bei einer Anforderung ausgewählt?
Bei einer Anforderung wird das kleinste passende Stück ausgewählt
Freispeicherverwaltung - First Fit
Erkläre “First Fit”
- Nimm den ersten freien Block, der groß genug ist
- Die Adresse wird von vorne durchlaufen
- Der durchschnittliche Suchaufwand ist gering - Im schlimmsten Fall immer noch O(n)
Freispeicherverwaltung - Next Fit
Erkläre “Next Fit”
- Nimm von der aktuellen Position in der Freispeicherliste aus den nächsten, der groß genug ist
- Dadurch, dass die Belegungen am Anfang vermieden werden gibt es bessere Suchzeiten als bei First-Fit
Freispeicherverwaltung - Best Fit
Erkläre “Best Fit”
- Nimm den Block mit dem geringsten externen Verschnitt
- Bessere Speichernutzung, da große Stücke nicht beachtet werden
- Neigt dazu, sehr kleine freie Stücke zu erzeugen, mit denen man gar nichts mehr anfangen kann
Freispeicherverwaltung - Worst Fit
Erkläre “Worst Fit”
Nimm den Block, der den größten externen Verschnitt hat
Freispeicherverwaltung - Nearest Fit
Erkläre “Nearest Fit”
- Wir geben eine Zieladresse vor und hätten den Speicherbereich gerne in der Nähe
- Man führt eine First-Fit-Suche durch
Spezialisierte Verfahren: Ringpuffer
Wie funktioniert das Verfahren mit Ringpuffer?
- Belegen und Freigeben in gleicher Reihenfolge (FIFO)
- Gleich lange Stücke
- Kein Suchen
- Kein externer Verschnitt
Spezialisierte Verfahren: Stack, Kellerspeicher
Wie funktioniert das Verfahren mit Stack und Kellerspeicher?
- Belegen und Freigeben in umgekehrter Reihenfolge (LIFO)
- Beliebig lange Stücke
- Kein Suchen
- Wenig externer Verschnitt
Overlays
Wie kann man das Problem, dass ein kompletter Prozess nicht in den Speicher passt lösen?
Indem man Teile des Programms mit einem anderen überschreibt (dem Overlay)
Virtueller Speicher
Wie lautet das dritte Problem das durch den virtuellen Speicher gelöst werden kann?
Externe Fragmentierung verschwendet Speicher und Memory Compaction ist teuer
Seitentabelle
Was enthält jede Zeile einer Seitentabelle?
- Die Nummer des physikalischen Speicherblocks
- Bit, das anzeigt, ob der Speicherblock ausgelagert ist
Seitentabelle
Welche Probleme kann es geben?
- Die Seitentabelle kann sehr groß werden
- Die Umrechnung von virtueller Adresse in physikalische Adresse muss sehr schnell gehen
Zeile einer Seitentabelle
Welche Bits gehören zur Zeile einer Seitentabelle?
- Caching Bit
- Modified Bit
- Referenced Bit
- Protection Bit
Zeile einer Seitentabelle - Modified Bit
Was passiert beim Auslagern einer Seite?
Die Seite muss beim Auslagern wieder auf die Festplatte geschrieben werden ansonsten kann die alte Kopie auf der Festplatte benutzt werden.
Zeile einer Seitentabelle - Referenced Bit
Nenne Punkte zum Referenced Bit
- Wird nach jeder Art von Zugriff gesetzt
- Benötigt für Seitenersetzungsalgorithmen
Hierarchische Seitentabelle
Wieso werden hierarchische Seitentabellen benötigt?
Sie verbrauchen keinen Speicher um riesige Löcher zu verwalten
Optimale Seitenersetzung
Beschreibe den Algorithmus der genutzt wird
Lagere die Seite aus, die gemäß Z am längsten nicht mehr gebraucht wird
Not Recently Used Algorithmus (NRU)
Was gilt für den NRU Algorithmus?
Entferne eine Seite, die in letzter Zeit nicht mehr benutzt wurde
Not Recently Used Algorithmus (NRU)
Welche Seite muss beim NRU-Algorithmus ersetzt werden?
- Klassifiziere die Seite
- Entferne eine Seite aus der niedrigsten (aus der 1.) Klasse
First In First Out (FIFO) Algorithmus
Was gilt für den FIFO Algorithmus?
- Ersetze die Seite, die am längsten im Speicher ist
- Das bedeutet, dass die erste Seite die reinkommt auch die erste Seite ist die wieder raus muss
Clock Algorithmus
Wie funktioniert der Clock Algorithmus?
Verhält sich genau wie Second Chance Algorithmus und hat eine bessere Datenstruktur.
Not Frequently Used (NFU)
Was ist der NFU Algorithmus?
- Es ist ein Versuch der LRU-Approximation
- Jede Seite hat ein Zähler der zu Anfang auf 0 steht
- Das R Bit wird periodisch auf den Zähler addiert
Notfrequently Used (NFU)
Welches Problem hat NFU?
Das Problem bei dem Algorithmus ist, wenn eine Seite mal sehr gefragt war und dann lange nicht, bleibt der Zähler dennoch hoch
Aging
Was ist der Aging Algorithmus?
- Es ist eine weitere LRU Approximation
- Der Zähler wird periodisch nach rechts geschrieben
- Das R Bit wird in das höchste Bit des Zählers geschrieben
Aging
Vorteile beim Aging Algorithmus
- Der Zähler hat ein kürzeres Gedächtnis als bei NFU
- Das R Bit bestimmt das höchste Bit des Zählers und nicht das niedrigste wie bei NFU
Working Set
Was ist ein Working Set?
Ein Working Set ist ein Speicherzugriff der öfter benutzt wird.
Working Set
Definition des Working Set
- Für Zeitpunkt t und Integer k ist w(k,t) die Menge der Seiten, die in den letzten k Speicherzugriffen vor dem Zeitpunkt t benutzt wurden
- Der Grenzwert für große k ist endlich, weil jeder Prozess nur endlich viele Seiten hat
Working Set und Swapping
Was ist das optimalste beim Working-Set und Swapping?
Nur die Seiten des Working-Set laden, da das Swapping dann schneller ist und nur wenige Seitenfehler auftauchen
Working-Set und Paging
Was bewirkt der Seitenersetzungs-Algorithmus?
- Entferne eine Seite, die nicht im Working-Set ist
- Wenn alle im Working-Set sind, dann entferne eine auf die schon lange nicht mehr zugegriffen wurde
Nachteile beim Working-Set und Paging
- Die Implementierung ist langsam
- Für eine weniger langsame Implementierung, wählen wir eine virtuelle Zeitspanne 𝜏
- Seiten, die länger als 𝜏 nicht mehr benutzt wurden, gehören nicht zum Working-Set
WS-Clock Algorithmus
Wie funktioniert der M-Bit beim WS-Clock Algorithmus?
- M-Bit bestimmt, ob eine Seite “sauber” ist
- M=0 -> Seite leer oder unverändert auf der Festplatte
- M=1 -> Seite muss erst ausgelagert werden
WS-Clock Algorithmus
Wie funktioniert der R-Bit beim WS-Clock Algorithmus?
- Wenn R = 1, dann setze den Zeitstempel und lösche das R-Bit
- Wenn R = 0 und Zeitstempel älter als 𝜏: Wenn Seite sauber ist, dann überschreiben. Ansonsten Seite für auslagern vormerken und weitersuchen
Design-Kriterien
Welche Lösung stellt die Page Fault Frequency dar?
Wenn ein Prozess sehr viele Seitenfehler hat und einer wenige, dann muss man umverteilen
Welche Lösung stellt Swapping dar?
Wenn alle Prozesse sehr viele Seitenfehler produzieren werden sie durch Swapping komplett ausgelagert
Design Kriterien
Welche gängigen Größen gibt es?
Es gibt gängige Größen zwischen 512 Byte und 16 KB
Segmentierung
Wofür steht GDT?
Global Descriptor Table
Segmentierung
Wofür steht LDT?
Local Descriptor Table
