Swapping und Paging
Swapping und Paging
Swapping und Paging
Kartei Details
| Karten | 33 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 25.06.2016 / 31.03.2017 |
| Weblink |
https://card2brain.ch/box/swapping_und_paging
|
| Einbinden |
<iframe src="https://card2brain.ch/box/swapping_und_paging/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Nenne die Speicherhierarchie und die ungefähren Zugriffszeiten und Größenordnung
CPU-Register < 1ns, 1 - 2kB
Cache L1: 1 - 2ns 64 - 512 kB
Cache L1: ~5ns 512 kB
Hauptspeicher ~10ns >100MN
Plattenspeiche: ~ 10 ms >100GB
Wer koordiniert die verschiedenen Speicherypen?
Das Betriebssystem bzw ein Teil der CPU (Memory Management Unit)
Was ist Paging
Einzelne Speicherseiten von Prozessen werden auf Festplatte ausgelagert
Was is Swapping
Ganze Prozesse werden zeitweilig auf Festplatte ausgelagert
Was ist das standart Swap-Device bei Linux, was bei MS Windows?
Linux: Partition
Windows: Datei
Was ist ein Swap-Devices und wie ist es aufgebaut?
Auf einem Swap-Devices werden die ausgelagerten Seiten gespeichert. Es sind Blockorientierte Geräte mit fortlaufenden Blöcken
Was wird in der Swapmap aufgezeichnet?
Die FREIEN Blöcke eines Swap-Gerätes in form einer Liste von Blockadressen und den ab dort verfügbaren freien Blöcken
Welche 2 Arten von Page Faults gibt es und was sind die zugehörigen handler
Gültigkeitsfehler (die gewünschte Seite ist gerade nicht im Speicher)
- Plattenblock-Deskriptor: gültige Seite erzeugen
- Falls nötig, eine Seite aus dem Speicher auslagern
- Die benötigte Seite laden
Speicherschutzfehler (Verletzung des SchreibkopieBits)
- Kopie der Seite bauen
Wlecke 2 Arten von Paging gibt es wenn ein Prozess anläuft und noch keine Seiten geladen sind?
Prepaging: Das System führt Buch, welche Seiten der Prozess vermutlich braucht und lädt sie vor Beginn der Ausführung
Demand Paging: Die Seiten werden erst dann geladen, wenn der erste Zugriff erfolgt
Welche 2 Möglichkeiten gibt es freie Speicherseiten zu Finden
Bitmap: 1 Bit pro Seite (1: belegt, 0: frei)
Verkettete Liste: Verw auf voriges Element | Prozes/Loch Bit s
Nenne 3 Algorythmen zur Ermittlung eines passenden Speicherlochs
+ Vor und Nachteile
First Fit Algorithmus: Nimm das erste Loch, das groß genug ist
+einfach, +schnell, -ineffiziente Speichernutzung
Best-Fit Algorithmus: Nimm das Loch, das am besten passt
+effiziente Speichernutzung, -langsam, -komplizierter
Quick-Fit Algorithmus: Führe Listen über freie Löcher verschiedener Größe
Kompromiss bezüglich Geschwindigkeit und Speichereffizienz
Was sagt das Diry bit aus? Wo steht es?
Das Dirty bit sagt aus ob eine Seite geändert wurde seit sie in den Hauptspeicher geladen wurde. Ist dies nicht der Fall muss sie nicht wieder auf die Festplatte geschrieben werden, da dort ja schon eine exakte Kopie liegt.
Das Dirty bit steht im Seitentabellen - Eintrag
Wie funktioniert der "optimale" Algorithmus zur Bestimmung welche Seite ausgelagert werden muss? Was ist der Nachteil?
Der Optimaler Algorithmus lagert die Seite aus, die am längsten unbenutzt bleiben wird
- Nicht vorhersehbar welche Seite das sein wird
Nicht praktikabel, aber als Messlatte für die Effizienz realer Algorithmen beliebt
Wie funktioniert der Not Recently Used (NRU) Algorithmus?
Was sind Vor(2) und Nachteile(1)
- Regelmäßige Untersuchung der "Referenced" (benutzt) und "Modified" (verändert) Flags der Seiten im Speicher nach Clock Interrupt
- Bei Zugriff werden die entsprechenden Flags gesetzt
- Bei jedem Clock Interrupt wird das "Referenced"-Flag gelöscht
- Vier Klassen von Speicherseiten. Es werden immer Speicherseiten aus der niedrigsten nichtleeren Klasse ausgelagert
+einfach +Gut zu implementieren -Moderate Performance
Nenne die 4 Klassen von Speicherseiten beim Not Recently Used (NRU) Algorithmus
- 0: R=0 M=0 (nicht benutzt, "sauber")
- 1: R=0 M=1 (nicht benutzt, verändert)
- 2: R=1 M=0 (benutzt, "sauber")
- 3: R=1 M=1 (benutzt, verändert)
R= Referenced M = Modified
Wie finktioniert der First-In First-Out (FIFO) Algorithmus
1 Nachteil
- Verkettete Liste der Speicherseiten in der Reihenfolge, in der sie geladen wurden
- Die Seite, die am längsten im Speicher war, wird ausgelagert
-Nicht sehr zuverlässig: Unter Umständen wird die "älteste" Seite sehr häufig benutzt. Daher selten!
Wie funktioniert der Second Chance Algorithmus?
1 Vor- 1 Nachteil
- Kombination von NRU- und FIFO Algorithmus
- Die älteste Seite wird untersucht
- R-Flag = 0: nicht benutzt – auslagern
- R-Flag = 1: kürzlich benutzt – noch nicht auslagern
- R-Flag löschen
- ans Ende der Liste (als "jüngste" Seite) setzen
- Suche fortsetzen
+Besser als FIFO
-das ständige umsetzen von Listenelementen macht den Algorithmus kompliziert
Wie funktioniert der Clock Page Algorithmus
1 Vorteil
- Das Element, auf das der Zeiger weist, wird untersucht
- R = 0 (unbenutzt) – auslagern/ersetzen
- R = 1 (benutzt)
- R-Flag löschen
- Zeiger weiterdrehen
- Weitersuchen
+ Gleicher Effekt wie Second Chance, aber ohne Umsortieren der Liste
Was ist der Arbeitssatz (Working Set)
- Zugriffe auf benachbarte Seiten sind weit häufiger als solche auf "entfernte”: Lokalität ("locality of reference")
- Die letzten k Seiten, auf die zugegriffen wurde bilden den Arbeitssatz ("working set") des Prozesses (k: "Fenstergröße")
- Bei Seitenfehler wird eine Seite ausgelagert, die nicht zum Arbeitssatz gehört
Wie wird der Arbeitssatz (Working Set) realisiert
- Der Arbeitssatz besteht aus den Seiten, auf die in den letzten z.B. 100 ms zugegriffen wurde
- Dazu muss die Zeit des letzten Zugriffs (im Verhältnis zur insgesamt vom Prozess genutzten CPU-Zeit) gespeichert werden ("current virtual time")
- In regelmäßigen Abständen (Periodendauer T) werden alle R-Flags gelöscht
- Bei Seitenfehler:
- R = 1 (benutzt): Schreibe aktuelle Prozesszeit in den Seitenlisten-Eintrag
- R = 0 (unbenutzt): wie groß ist die Differenz Δt von aktueller und eingetragener Prozesszeit?
- Δt < T: Seite bleibt im Arbeitssatz
- Δt > T: Seite gehört nicht mehr zum Arbeitssatz und kann entfernt werden
Was passiert bei WSClock Page Algorithmus wenn Δt > T: (Seite kann entfernt werden )
- Seite "sauber": einfach überschreiben
- Seite verändert: Zum Schreiben auf Platte einplanen
- Zeiger weiterdrehen
- Zeiger einmal rundrum:
- Entweder: >= 1 Seite zum Schreiben eingeplant – weitersuchen
- Oder: keine Seite zum Schreiben eingeplant – irgendeine "saubere" Seite auslagern
Wie funktioniert der Pagedeamon unter UNIX/Linux
- Der Page Daemon verwendet eine Spielart des WSClock-Algorithmus
- Anstelle einer Zeitmarke wird jeder Seite ein Alter (Anzahl der Überprüfungen) zugeordnet
- Beim Systemstart wird der Page Daemon gestartet
- Prüft regelmäßig, ob genügend Speicher frei ist
- Wenn der freie Speicher knapp wird, beginnt der Page Daemon damit, Seiten zu markieren, die ausgelagert werden können
Was macht der Flush Deamon
Der Flush Daemon schreibt auslagerungsfähige Seiten, die verändert wurden, auf Platte
Was passiert wenn das Paging zu häufig wird
Wenn das Paging zu häufig wird ("thrashing"), werden Prozesse aus dem Speicher entfernt (Swapping)
Was Prüft der Swapper regelmäßig
(2)
- Ein lauffähiger Prozess in den Speicher geladen werden soll
- Die Frequenz der Seitenfehler so groß ist, dass ein Prozess ausgelagert werden sollte und lagert bei Bedarf Prozesse aus
Welche Prozesse werden grundsätzlich nicht ausgelagert
(3)
- Der Kernel
- Zombies (brauchen kaum Speicher)
- Prozesse, die nicht mindestens 2 Sekunden im Speicher waren
Was ist demand paging
Von ausgelagerten Prozessen werden nur die Seiten wieder geladen, die wirklich benötigt werden (demand paging)
was ist trashing
Der Swapper lagert bei Bedarf ganze Prozesse auf Platte aus, wenn die Rate der Seitenfehler zu groß wird
Das einfache Prozesszustandsmodell unter UNIX
Das komplizierte Prozesszustandsmodell unter UNIX
