Title: IN0009_GBS / GBS: Kapitel 6: Speicherverwaltung
On every note of this deck, unless a note says otherwise:
Title: IN0009_GBS::GBS: Kapitel 6: Speicherverwaltung
Logo: tum_logo.png

Front: Welche Probleme entstehen, wenn alle Programme vollen Zugriff auf den kompleten physischen Hauptspeicher haben?
Back: - Programme können das im Hauptspeicher befindliche Betriebsystem und andere Programme ändern
- Programme können sich gegenseitig stören
- Jedes Programm belegt potentiell den gesamten Hauptspeicher

Front: Wie kann vom physischen Speicher abstrahiert werden, um Störungen zwischen mehreren Programmen zu vermeiden?
Back: - Einführung einer Speicherabstraktion in Form von Adressräumen
- (Abstrakte) Menge von Speicherzellen, die ein Prozess adressieren kann. z.B. 4GByte
- Jeder Prozess erhält seinen eigenen, isolierten Adressraum

Front: Direkte Adressierung
Back: Jede logische (virtuelle) Adresse entspricht ihrer physischen Adresse

Front: Wie können mehrere Programme bei direkter Adressierung gleichzeitig laufen?
Back: Option 1: Extensives Swapping
- Immer nur das ausführende Programm im Speicher
- Beim Wechsel wird der Speicherinhalt gewechselt (swapping)
Option 2: Relokation
- Programme weren an unterschiedliche Stellen im Speicher geladen
- Beim Laden müssen dann die Adressen in den Programmen umgeschrieben warden, damit sie zur Stelle im Speicher passen

Front: Können sich Programme bei direkter Adressierung und Relokation stören?
Back: Ja. Programme können auf den gesamten Speicher zugreifen.

Front: Beschreibe die Basis-Adressierung
Back: - Das BS legt für jeden logischen Adressraum eines Prozesses eine Basisadresse b_x fest
- Bei Prozess-Start wird die Basisadresse bx in das Basisregister der CPU geladen

Front: Wie funktioniert die Adressberechnung bei der Basis-Adressierung
Back: - physische Adresse = logische Adresse + Basisadresse
- Berechnung erfolgt durch die CPU, bevor eine Adresse auf den Speicherbus gelegt wird

Front: Vorteile und Nachteile der Basis-Adressierung
Back: Vorteile
- Das BS kann Programme im Hauptspeicher verschieben (relocation)
- Das BS kann mehrere Prozesse zu einem Zeitpunkt in den Hauptspeicher laden
Nachteile
- Aufwendige Additionsoperation

Front: Ja oder Nein? Jedes Programm belegt bei direkter Adressierung potentiell den gesamten Hauptspeicher des Rechners.
Back: Ja

Front: Ja oder Nein? Prozesse benötigen bei direkter Adressierung Kenntnis über Struktur des Hauptspeichers.
Back: Ja

Front: Ja oder Nein? Programme können bei direkter Adressierung das ebenfalls im Hauptspeicher befindliche Betriebssystem korrumpieren.
Back: Ja

Front: Ja oder Nein? Bei der Basisadressierung belegt jedes Programm potentiell den gesamten Hauptspeicher des Rechners.
Back: Nein

Front: Ja oder Nein? Bei der Basisadressierung benötigen Prozesse Kenntnis über Struktur des Hauptspeichers.
Back: Nein

Front: Ja oder Nein? Bei der Basisadressierung können Programme das ebenfalls im Hauptspeicher befindliche Betriebsystem korrumpieren
Back: Nein

Front: Beschreibe die Segmentadressierung
Back: - Unterteilung des Adressraums in logische Segmente, unterschiedlicher Länge
- Beispiel: Stack-, Daten-, Code-Segment
- Mögliche Zugriffsberechtigungen
- Adressierung pro Segment erforderlich

Front: Wie funktioniert die Segmentadressierung beim Intel x86 Prozessor
Back: - Verwaltung einer Tabelle: Global Descriptor Table (GDT)
- Eintrag in der Tabelle enthält für jedes Segment:
  - Basisadresse und Länge des Segments
  - Flags (Zugriffsbeschränkungen, etc.)
- Segmentregister: Index in die Global Descriptor Table

Front: Welche Datenstrukturen bieten sich zur Freispeicherverwaltung an?
Back: 1. Bitmap
2. Verkettete Liste von Frei-Speicherbereichen

Front: Beschreibe die Bitmap Datenstruktur zur Freispeicherverwaltung
Back: - Aufteilung des Speichers in Blöcke gleicher Größe
- Bitmap zur Indexierung des Speichers
- Pro Block 1 Bit zur Repräsentation in der Map (1 belegt, 0 frei)

Front: Nenne Vor- und Nachteile von einer Bitmap zur Freispeicherverwaltung
Back: Vorteile
- Einfacher und schneller Zugriff
Nachteile
- Bei Anfrage auf k freie Blöcke: Lineare Suche
- Bei zu kleinen Blöcken wird eine große Bitmap zur Verwaltung benötigt
- Bei zu großen Blöcken ist der Verschnitt ggf. hoch.

Front: Wie kann eine Freispeicherverwaltung mittels einer verketteten Liste erfolgen?
Back: Aufbau
- BS verwaltet Liste mit Bereichen bestehend aus zusammenhängenden Hauptspeicherblöcken
- Bereiche sind einem Prozess zugeordnet, oder frei

Front: Welche Informationen enthält typischerweise ein Listeneintrag bei einer Freispeicherverwaltung?
Back: - Anfangsadresse des Bereichs
- Die Länge des Bereichs (in Blöcken)
- Einen Zeiger auf den nächsten Eintrag (oder NULL Terminator)

Front: Was sind Vor- und Nachteile bei der Freispeicherverwaltung mittels einer verketteten Liste?
Back: Vorteile
- Flexible Speicheraufteilung
Nachteile
- Lineare Suche
- Keine feste Verwaltungsstruktur (dynamischer Größenänderung)

Front: Was sind Optimierungsmöglichkeiten bei der Freispeicherverwaltung mittels einer verketteten Liste?
Back: - Getrennte listen für belegten und freien Speicher
- Sortierung nach Speichergröße
- Verwaltung in (balancierter) Baumstruktur

Front: Was ist ein Vorteil bei der Sortierung der Freibereichsliste?
Back: Es können leicher freie Speicherbereiche zusammengeführt werden.

Front: Welche Belegungsstrategien gibt es bei der Freispeicherverwaltung?
Back: - First-Fit
- Next-Fit
- Best-Fit
- Worst-Fit

Front: Was ist die Strategie des First-Fit in der Speicherzuweisung und was ist ihr Hauptvorteil?
Back: First-Fit durchsucht die Liste der Freibereiche vom Anfang und belegt den ersten ausreichend großen Freibereich. Hauptvorteil ist die Einfachheit und schnelle Auffindung eines passenden Freibereichs.

Front: Erkläre den Unterschied zwischen First-Fit und Next-Fit in der Speicherzuweisung
Back: Next-Fit ist eine Variante von First-Fit, beginnt aber die Suche im Speicher beim zuletzt belegten Bereich, nicht am Anfang der Liste.

Front: Was bedeutet Best-Fit in der Speicherzuweisung und was könnte ein Nachteil dieser Strategie sein?
Back: Best-Fit durchsucht die Liste der Freibereiche vollständig und wählt den Bereich mit dem geringsten Verschnitt.
Nachteil
Erhöhter Suchaufwand.

Front: Wahr oder Falsch: Worst-Fit belegt in der Speicherzuweisung immer den kleinsten verfügbaren Freibereich
Back: Falsch. Worst-Fit belegt den Freibereich mit dem größten Verschnitt.

Front: Was könnte ein Problem bei der Anwendung der First-Fit Strategie sein?
Back: Ein mögliches Problem bei First-Fit könnte die zunehmende Fragmentierung des Speichers sein, da immer der erste passende Freibereich genutzt wird.

Front: Was ist die interne Fragmentierung?
Back: Beim blockweisen Allokieren von Speicher wird meist mehr Speicher vergeben als benötigt. Die interne Fragmentierung beschreibt diesen Verschnitt.

Front: Was ist die externe Fragmentierung?
Back: Anders als bei der internen Fragmentierung, bezeichnet die externe Fragmentierung die "Löcher" im Hauptspeicher, die bei der Vergabe und Freigabe von Speicherblöcken unterschiedlicher Größe entstehen können.

Front: Was ist das Ziel des Buddy-Algorithmus und wie wird der Speicher verwaltet?
Back: - Kompromiss zwischen der Verwaltung von Speicherblöcken fester und dynamischer Größe ab.
- Speicher wird in Blöcken der Größe 2^k verwaltet

Front: Beschreibe den Prozess der Speicherbelegung und -freigabe im Buddy-Algorithmus.
Back: Bei der Belegung wird der Speicher in gleich große Bereiche aufgeteilt, bis der kleinste passende Block gefunden ist. Bei der Freigabe werden freie Buddies verschmolzen, um größere Blöcke zu bilden. Dies wird rekursiv fortgesetzt, bis keine Buddies mehr verschmolzen werden können.

Front: Welche Vorteile bietet der Buddy-Algorithmus und wo wird eine Variante davon verwendet?
Back: - einfach zu implementieren
- effizientes Suchen nach freien Speicherbereichen-maximalen Verschnitt von einem halben Block
Eine Variante des Buddy-Algorithmus wird in der Speicherverwaltung von Linux verwendet.

Front: Was ist das Problem mit dem virtuellen Prozess-Adressraum eines Prozesses und wie begegnet das Betriebssystem diesem Problem?
Back: Der virtuelle Prozess-Adressraum kann größer sein als der physische Hauptspeicher. Das Betriebssystem löst dieses Problem durch automatisierte virtuelle Speicherverwaltung, häufig durch das Konzept des Paging.

Front: Was ist Paging in der Speicherverwaltung und wie funktioniert es?
Back: Virtuelle Adressräume werden in Seiten (Pages) und der Hauptspeicher werden in physische Kacheln (Frames) aufgeteilt. Seiten und Kacheln haben in der Regel die gleiche Größe (oder die Seitengröße ist ein Vielfaches der Kachelgröße).

Front: Was sind typische Seiten-/Kachelgrößen auf x86?
Back: 4KB / 2 MB / 1 GB

Front: Was ist die Rolle der Memory Management Unit (MMU) im Kontext des Paging?
Back: Die MMU bildet Seiten-Adressen auf physische Adressen in einer Kachel ab.

Front: Warum ist eine manuelle Aufteilung des virtuellen Adressraums durch den Programmierer problematisch?
Back: Eine manuelle Aufteilung des virtuellen Adressraums durch den Programmierer ist aufwendig und fehleranfällig, da sie manuelles Ein- und Auslagern von Adressbereichen in den Hauptspeicher erfordert.

Front: Was macht eine Page Table?
Back: - Verwaltung der Zuordnung von Seiten zu Kacheln
- BS verwaltet eine Page Table pro Prozess

Front: Was passiert bei einem Prozesswechsel mit dem Seitentabellenregister?
Back: Bei einem Prozesswechsel wird die Anfangsadresse der neuen Prozess-Page-Table in das Seitentabellenregister der CPU geladen

Front: Wann und wie entsteht ein Seitenfehler (page fault)
Back: - Bei Zugriff auf eine virtuelle Adresse einer Seite, die in keiner Kachel eingelagert ist.
- Die Hardware löst einen Interrupt, einen page fault, aus

Front: Wie kann ein Seitenfehler (page fault) behoben werden?
Back: Das Betriebsystem lagert die erforderliche Seite ein

Front: Was versteht man unter der Seiteneinlagerung?
Back: Wenn fast alle Kacheln belegt sind, müssen Seiten ersetzt werden. Die Seiteneinlagerung ist somit die Auslagerung von Seiten auf die Festplatte.

Front: Was ist Seitenflattern (Thrashing)
Back: Zeit für das Laden und Auslagern von Seiten (Page Swapping) im virtuellen Speicher nimmt den größten Teil der Prozessorzeit in Anspruch.

Front: Was ist der Unterschied zwischen Paging vs. Swapping?
Back: Paging
- Seitenweise Auslagern
- Feinere Granularität
Swapping
- Gesamter Speicher des Prozesses wird ausgelagert

Front: Was ist der Ablauf der Memory Address Translation in einer MMU?
Back: 1. Prozessor sendet eine virtuelle Adresse an die MMU
2. Anfrage mit Page Table Entry Address (PTEA) zum Cache/Speicher
3. MMU bekommt Page Table Entry (PTE) aus Cache/Speicher
4. MMU sendet die physische Adresse an Cache/Speicher
5. Cache/Speicher sendet die Daten zum Prozessor

Front: Was ist das Hauptproblem bei der Adressabbildung?
Back: Der hohe Zeitaufwand

Front: Was ist der Translation Lookaside Buffer (TLB)?
Back: - Cache für die Abbildung von Seiten auf Kacheln
- Klein: wenige Einträge, typisch: 256
- Oft mehrstufig
Mögliche Spalten
Valid, Virtual Page No., Modified, Protection, Page Frame

Front: Wie ist eine virtuelle Adresse v aufgebaut?
Back: [$]v = (s, w)[/$]
Die höherwertigen Bits werden als Seitennummer s und die niedrigwertigen Bits als Offset w interpretiert.
Die Seitennummer definiert den Index in die Seiten-Tabelle des BS mit dem Eintrag für die Seite
Der Offset definiert den Offset in einer Seite bzw. Kachel und muss bei gleicher Seiten-/Kachelgröße nicht verändert werden.
Schema
[$$][ \overbrace{\texttt{Seitennummer s}}^{\text{higher order bits}} \quad \underbrace{\texttt{Offset w}}_{\text{lower order bits}} ][/$$]

Front: Wie ist eine Page Table strukturiert?
Back: Ein Eintrag enthält die Seitennummer und die korrespondierende Framenummer

Front: Was sind die fünf vorgestellten Informationen (Bits) bei einen Page Table Eintrag?
Back: - P (present): Physische Adresse ist vorhanden und valide
- U/S (user/supervisor)
- R (referenced): Wurde auf die Seite zugegriffen?
- M (modify): Wurde auf der Inhalt der Seite modifiziert?
- XD (execute-disable): Darf der Inhalt der Seite auch ausgeführt werden?

Front: Wann sind mehrstufige Seitentabellen vom Vorteil?
- Große virtuelle Adressräume -> Seitentabelle ist ebenfalls sehr groß
- Die Speicherung der Tabelle belegt viel Hauptspeicher
Folge?
Nur ein Teil der Page Table muss zur Prozessausführung im Hauptspeicher eingelagert sein

Front: Wie werden mehrstufige Seitentabellen umgesetzt?
Back: Höhererwertige Bits (Seitennummer) werden aufgeteilt, um weitere hierarchisch angeordnete Tabellen zu indexen.
[$$][\text{Virtual Address} = \left( \overbrace{\text{PDN}}^{\text{Page Directory Number}}, \overbrace{\text{PTN}}^{\text{Page Table Number}}, \overbrace{\text{Offset}}^{\text{Offset within Page}} \right) ][/$$]

Front: Beschreibe den Ablauf der Seitenfehlerbehandlung (durch BS)
Back: 1. HW löst Interrupt aus
2. Ausführung des Page-Fault-Handlers
3. BS behandelt Seitenfehler a) Seite ist ausgelagert: einlagern b) Seite ist nicht ausgelagert: Löse Speicherschutz-Fehler aus
4. Aktualisieren des Page-Table-Eintrags (Setzen von P, Löschen von R und M Bits)
5. Wiederherstellen des Programmzustands, reaktivieren der Interrupts
6. Interrupt-Kontext verlassen

Front: Welche drei strategischen Aufgaben gibt es beim Paging?
Back: - Wann? On-Demand, und/oder Prefetching
- Wohin? Platzierungsstrategie
- Welche Seite wird u.u. ausgelagert?

Front: Nenne die 6 vorgestellten Seitenersetzungstrategien.
Back: - FIFO
- Second-Chance
- Clock
- Least Recently Used (LRU), Aging
- Working Set
- Working Set with Clock

Front: Was beschreibt die FIFO-Strategie (First-in-First-Out)?
Back: - Verwalten einer Liste aller im Speicher geladenen Seiten, sortiert nach Ankunftszeit
- Die am längsten im Speicher befindliche Seite (an der Spitze der Liste) wird für das Page-out ausgewählt.

Front: Was ist ein großes Problem bei der FIFO Seitenersetzungsstrategie?
Back: Möglicherweise häufig genutzte Seiten können ersetzt werden, was zu einer Erhöhung der Seitenfehler führen kann (bekannt als Béládys Anomalie).

Front: Wie modifiziert der Second-Chance-Algorithmus die FIFO-Strategie im Seitenersatz?
Back: Seiten, die ihr R-Bit gesetzt haben, erhalten eine zweite Chance. Diese Seiten werden ans Ende der Liste verschoben und ihre Ankunftszeit wird aktualisiert.
Sind alle R-Bits gesetzt, fällt der Algorithmus auf FIFO zurück.

Front: Was ist die Motivation für den Second-Chance-Algorithmus im Seitenersatz?
Back: Der Ansatz zielt darauf ab, unnötige Seitenersetzungen zu reduzieren, kann aber zu häufigen Verschiebungen in der Liste führen.

Front: Was ist der Clock-Algorithmus im Seitenersatz und wie funktioniert er?
Back: - Anordnung von Seiten in einer kreisförmigen Liste an (ähnlich einer Uhr)
- Verwendet einen Zeiger, um die älteste Seite zu identifizieren
Ablauf bei Seitenfehler
1. Ist das R-Bit der angezeigten Seite nicht gesetzt -> Ersetzung. Zeiger rückt vor.
2. Ist das R-Bit gesetzt, rückt der Zeiger ohne Ersatz vor und das R-Bit wird gelöscht. (Loop bis Seite mit R=0 gefunden wurde)
Das M-Bit entscheidet, ob der Seiteninhalt vorher zurück auf den Speicher geschrieben oder die Seite einfach verworfen wird.

Front: Was beschreibt die LRU (Least Recently Used) Seitenersetzungsstrategie?
Back: - Nutzt die Lokalitätseigenschaft von Programmen aus und ersetzt bei einem Seitenfehler diejenige Seite, die am längsten nicht verwendet wurde
- Gute Approximation des optimalen Seitenersetzungsalgorithmus

Front: Was ist das Hauptproblem bei der Implementierung der LRU Seitenersetzungsstrategie?
Back: Eine exakte Implementierung erfordert spezielle Hardware oder komplizierte Software-Lösungen wie NFU oder Aging.

Front: Wie funktioniert das NFU und Aging Verfahren in der Seitenverwaltung?
Back: - Für jede Seite wird ein Software-Counter geführt, der bei jedem Timer-Interrupt erhöht wird, wenn das R-Bit gesetzt ist
- Die Seite mit dem niedrigsten Zählerstand wird ausgelagert
Erfassung der Alterung von Zugriffen
Aging verbessert NFU, indem der Zähler auch das Alter der Zugriffe berücksichtigt, wodurch Seiten, die frisch oder lange nicht referenziert wurden, unterschieden werden können.

Front: Wie kann bei dem Aging Verfahren (Seitenverwaltung) die Alterung von Zugriffen erfasst werden?
Back: Es wird ein Zeit-Intervall t festgelegt in dem Zugriffe erfasst werden (z.B. 20 ms)
Ablauf nach Timer-Interrupt
1. Neuberechnung des Zählerstands
2. Shift des Zählers um eine Stelle nach Rechts
3. Addition des R-Wertes zum am weitesten links stehenden bit des Zählers

Front: Was ist das Working-Set eines Prozesses (Seitenverwaltung)?
Back: Die Menge der Seiten die ein Prozess aktuell benötigt.

Front: Was ist das Working-Set-Modell in der Seitenverwaltung?
Back: - Prozesse arbeiten eine zeitlang mit dem gleichen Working-Set
- Optimalfall: Das Working-Set ist (zu einem großen Teil) im Hauptspeicher eingelagert
- Idee: Ersetzungs-Strategie auf der Basis des Working-Set Modells

Front: Wie funktioniert das Working-Set-Model in der Seitenverwaltung?
Back: Festlegung eines Zeit-Intervalls I. Timer-Interrupt nach Ablauf von I (Clock-Tick)
Ablauf bei Timer-Interrupt
1. Neuberechnung des Working-Sets
2. Löschen aller R-Bits aller Seiten. Typischerweise ist [$]i \lt \tau[/$] (Tau ist ein Interval in der Rechenzeit (nicht Echtzeit))

Front: Wie funktioniert die Seitenfehlerbehandlung bei dem Working-Set Verfahren?
Back: BS inspiziert R-Bits aller Seiten. Sei [$]Z[/$] der (monoton steigender) Zähler und [$]Z_p[/$] der Zähler für die Seite [$]p[/$].
1. R = 1 Seite gehört zum Working-Set und wird nicht entfernt (Aktualisiere Zähler)
2. R = 0
- [$]Z - Z_p \gt \tau[/$]: p wird ersetzt (nicht Teil des WS)
- [$]Z - Z_p \le \tau[/$]: Wurde nicht verwendet, abr Teil des WS
1. Wenn keine Seite gefunden wurde, ersetze die älteste Seite

Front: Was ist die WSClock Seitenersetzungstrategie?
Back: Kombiniert Clock und Working-Set Strategie.

Front: Was versteht man unter "higher half kernel"?
Back: - Der obere Teil des viruellen Addressraums gehört dem kernel
- Kein Kontextwechsel für jeden Syscall und Interrupt nötig