Zusammenfassung Betriebssysteme

Aus VISki
Wechseln zu: Navigation, Suche

Ziel dieser Zusammenfassung: All denjenigen welche die Vorlesung besucht (oder Slides studiert) haben, helfen, sich an alle Details und Zusammenhänge zu erinnern

  • Die behandelten Konzepte kurz und präzise erläutern und übersichtlich darstellen
  • Die wichtigsten Eigenschaften von Konzepten auflisten
  • Die Begriffe (Buzz-Words) wichtiger Konzepte auflisten und kurz beschreiben, damit man sich an die Begriffe erinnern kann
  • Überblick vermitteln (Wo gehört was hin? Wie hängt was zusammen? Worin unterscheiden sich die Konzepte?)


Nicht Ziel dieser Zusammenfassung: Jemandem der keine Ahnung vom Stoff der Vorlesung hat diesen verständlich machen

  • Die Konzepte ins Detail erklären (Dies ist Aufgabe der Vorlesung/Slides)
  • Viele Beispiele auflisten
  • Prüfungsfragen als Beispiele (Besser das getestete Wissen in die Zusammenfassung integrieren)
  • Nicht vorlesungsbezogenes Wissen vermitteln (Dies ist eine Zusammenfassung der Vorlesung. Eine Auswahl von all dem was es zu wissen gibt. Wer mehr will darf jeder Zeit Wikipedia verlinken)
  • Wikipedia kopieren


Inhaltsverzeichnis

Bootvorgang

Bootstraping

(= booting up)

Ausgangslage:

  • Prozessor im Realmode

Bootvorgang

  1. BIOS (= Basic Input/Output System) laden
    • Löst Henne-Ei Problem (Zum Software laden wird Software benötigt)
    • Sucht gültigen MBR gemäss BIOS Boot Device Präferenzliste
  2. Ausführung wird an den IPL des MBR übergeben

Links

http://www.multibooters.co.uk/multiboot.html


Partitionierung

MBR (Master Boot Record)

Der MBR umfasst 512 Bytes (1 Block/log. Sektor) und ist ganz am Anfang einer Harddisk lokalisiert.

Der MBR setzt sich zusammen aus IPL (Initial Program Loader) und Partition Table (PT)

 -------------------------------------
|  IPL                    | Part Tab  |
 -------------------------------------
0                         446        512

PBR (Partition Boot Record)

(auch VBR = Volume Boot Record)

ToDo:
PBR beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Partitionstabellen

ToDo:
Aufbau der Partitionstabellen beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.


Beispiel

Block an Position
              ----------------------                     Typ   LBA Start         LBA End            Size
0            | MBR = IPL + PT       |       PT Eintrag 1: 76          63          19'151          19'089 (ca  9MB)  AOS Partition (nur Daten)
(+63)        |                      |       PT Eintrag 2:  5      19'152          99'791          80'640 (ca 40MB)  Extended Partition (inkl IPL + PT)
              ----------------------
             : leer                 :
              ----------------------
63           | Data PT Typ 76       |
(+19'089)    : ca 9MB               :
             :                      :                               rel Angaben zu 19'152 (BaAdr)
             |                      |                                 |             |
              ----------------------   \                              |             |
19'152 BaAdr | IPL? + PT            |   |   PT Eintrag 1: 76          63          27'215          27'153 (ca 13MB)  AOS Partition 1 (nur Daten)
(+63)        |                      |   |   PT Eintrag 2:  5      27'216          40'319          13'104 (ca  6MB)  Next Partition 2 (inkl IPL + PT)
              ----------------------    |                             |               |
             : leer                 :   |                           rel Angaben zu 19'152 (BaAdr)
              ----------------------    |
19'215       | Data PT 1            |   |
(+27'153)    : ca 13MB              :   |---- Extended Partition (80'640 Blocks)
             :                      :   |
             |                      |   |                           rel Angaben zu 46'368
              ----------------------    |                             |               |
46'368       | IPL? + PT            |   |   PT Eintrag 1: 76          63          13'103          13'041 (ca  6MB)  AOS Partition 2 (nur Daten)
(+63)        |                      |   |   PT Eintrag 2:  5      40'320          80'576          40'257 (ca 20MB)  Next Partition 3 (inkl IPL + PT)
              ----------------------    |                             |               |
             : leer                 :   |                           rel Angaben zu 19'152 (BaAdr)
              ----------------------    | 
46'431       | Data PT 2            |   | 
(+13'041)    : ca 6MB               :   |                                  
             :                      :   |
             |                      |   |                           rel Angaben zu 59'472
              ----------------------    |                             |               |
59'472       | IPL? + PT            |   |   PT Eintrag 1: 76         63           40'319          40'257 (ca 13MB)  AOS Partition 3 (nur Daten)
(+63)        |                      |   |   PT Eintrag 2:  0          0                0               0 
              ----------------------    |                  
             : leer                 :   |                        
              ----------------------    |
59'535       | Data PT 3            |   |
(+40'256)    : ca 20MB              :   |
             :                      :   |
99'791       |                      |   |
              ----------------------   /
99'792

Dateisysteme

Ausführliche Übersicht über existierende Dateisysteme

Aufgabe des Dateisystems

Operationen, die auf einem Dateisystem möglich sein müssen:

  • In möglichst konstanter Zeit: (?)
    • Datei anlegen
    • Datei löschen
    • Datei erweitern (verlängern)
    • Datei in ein anderes Verzeichnis verschieben
    • Datei (für Lesen ab Anfang) öffnen
    • Datei (für Lesen ab beliebiger Stelle) öffnen
    • ...

Verwaltung freien Speichers

Die freien Blöcke werden auch als Block-Poll bezeichnet

Bittabelle

Für jeden Block wird ein Bit benutzt zum Speichern ob der Block benutzt oder unbenutzt ist

Eigenschaften

  • Nicht adaptiv: Benötigter Speicherplatz zur Verwaltung der freien Blöcke ist unabhängig von der Datenmenge
  • 1 Bit / freier Block
  • Grösse der freien, zusammenhängende Bereiche nicht direkt erkennbar

Liste freier Blöcke

Die Blocknummern der freien Blöcke werden in eine (nicht zwingend sortierte) Liste gespeichert.

Eigenschaften

  • Adaptiv: Benötigter Speicherplatz zur Verwaltung der freien Blöcke wird mit zunehmender Belegung geringer
  • 4 Byte / Block (je nach Dateisystem)
  • Grösse der zusammenhängenden, freien Bereiche überhaupt nicht erkennbar

Free-List

Die freien Blöcke werden untereinander gelinkt. Die Zeiger auf den nächsten freien Block befinden sich dabei selbst im freien Speicher

 --------------------------------------------------------------
|xxxxx|p1, len   |xxxxx|xxxxx|p2, len   |xxxxx|xxxxx|p3, len   |
 --------------------------------------------------------------

Eigenschaf* Geringe externe Fragmentierung

  • Hohe interne Fragmentierung
  • Wahlfreier Zugriff nicht performantten
  • linearer Aufwand zum finden eines freien Blocks
  • Adaptiv: Die Liste des freien Speichers wird im freien Speicher selbst verwaltet
  • Fehleranfällig: Das verlieren eines Pointers unterbricht die ganze Kette (jedoch in der Regel reparierbar)


Verwaltung belegten Speichers

Zusammenhängende Allokation

Files werden an einem Stück in den Speicher geschrieben


Eigenschaften

  • Hohe interne Fragmentierung
  • Hohe externe Fragmentierung
  • Performantes Lesen


Blockweise Allokation mit verketteter Liste

Files wird in einzelne Blöcke unterteilt, welche über den Speicher verteilt gespeichert werden können. Jeder Block enthält Zeiger auf den nächsten Block.


Eigenschaften

  • Geringe externe Fragmentierung
  • Hohe interne Fragmentierung
  • Wahlfreier Zugriff nicht performant


Blockweise Allokation mit File Allocation Table

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Eigenschaften

  • Geringe externe Fragmentierung
  • Hohe interne Fragmentierung
  • Wahlfreier Zugriff nicht performant aber besser alsmit verketteter Liste (FAT kann im Hauptspeicher gehalten werden)
  • Speicherbedarf: FAT wächst linear mit der Anzahl Blöcke

Blockweise Allokation mit hierarchischer Struktur

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

-> inodes

Zugriffszeit Harddisk

Gesamte Zugriffszeit = T + 1/(2r) + b/(rN)

  • T: Mittlere Positionierungszeit [s]
  • r: Rotationsgeschwindigkeit [U/s]
  • b: # Bytes
  • N: # Bytes / Spur


Fehlertoleranz

Fehlerursachen:

  • Hardware
  • Software: Inkonsistenz der Diskdaten nach System Crash

Gegenmassnahmen:

  • Hardware Schutz: z.B Puffer auch bei Stromausfall fertig schreiben
  • Badsector Pseudofile: Ein File, welches die als defekt bekannten Sektoren belegt
  • Scavenging: Redundanz zur Rekunstruktion der Filesystemdatenstruktur
    • Replikation kritischer Blöcke (z.B FAT, Superblock)
    • Markiere File Headerblöcke mit Fingerabdruck
    • Trage Filenamen in File Headerblöcken ein
    • Verkette Datenblöcke sequenziell
  • Journaling: An sich keine Gegenmassnahme. Verbessert lediglich die Performance bei der Wiederherstellung.

Raid

  • Raid 0 (Striped Data): Daten werden auf mehrer Festplatten verteilt. +Performance, -Sicherheit
  • Raid 1 (Mirrored Data): Daten werden auf mehreren Festplatten gespiegelt. ?Performance, +Sicherheit
  • Raid 4 (Striped Data + Parity): Daten werden auf mehrer Festplatten verteilt. Eine weitere Festplatte speichert Parity Prüfsummen zu den Daten. Da bei allen Lese- und Schreiboperationen jeweils die Festplatte mit den Parity Summen benötigt wird, wird diese zum limitierenden Faktor (+)Performance, +Sicherheit
  • Raid 5 (Striped Data + Parity): Daten werden auf mehrer Festplatten verteilt. Jede Festplatte speichert dabei die Parity Prüfsummen über einen bestimmten Bereich der anderen Festplatten. +Performance, +Sicherheit

http://de.wikipedia.org/wiki/RAID


Links

Softlinks

Definition: Softlink

Ein Softlink ist eine Datei welche einen Verweis auf eine andere Datei in Form einer Pfad- und Dateiangabe enthält, wobei keine Garantie gegeben wird, dass diese Datei/Ordner wirklich existiert

Abhängigkeit zwischen Softlink und Datei / Ordner

  • Löschen des Softlinks löscht die Datei nie
  • Löschen der Datei führt dazu, dass der Softlink ins leere zeigt
  • Umbenennen der Datei führt dazu, dass der Softlink ins leere zeigt


Eigenschaften

  • Von der Implementation des Dateisystems unabhängig
  • Kann auf Files oder Ordner anderer Partitionen oder Festplatten verweisen
  • Der Softlink kann ins "leere" zeigen

Hardlinks

Definition: Hardlink

Ein Hardlink ist ein Eintrag in einem Ordner welcher einen Verweis auf eine Datei enthält, wobei der Verweis durch eine Nummer angegeben ist (z.B Inode-Nummer), welche die Datei eindeutig identifiziert. Es wird keine Pfadangabe benötigt

Abhängigkeit zwischen Hardlink und Datei

  • Löschen eines Hardlinks löscht die Datei nur, wenn es keine anderen Hardlinks auf die Datei mehr gibt
  • Löschen der Datei ist nur via Hardlink möglich


Eigenschaften

  • Von der Implementation des Dateisystems abhängig
  • Kann nur auf Files der gleichen Partition verweisen
  • Kann in der Regeln nicht auf Ordner verweisen, da dies rekursive Baum-Strukturen erlauben würde
  • Zeigt immer auf eine Datei (kann nie ins leere zeigen)

FATxx

(=File Allocation Table)

Der Name FAT stammt von der verwendeten Technik im Dateisystem, welche sich File Allocation Table (kurz FAT) nennt. Es handelt sich um eine Tabelle mit Blocknummern (FAT-Terminologie: Clusternummern). Deren Aufgabe ist es, Datenblöcke von Dateien in einer Richtung zu verklinken. D.h. gegeben die Blocknummer eines Blocks einer Datei, gibt die FAT Auskunft über den nächsten Block der Datei.

FAT - How It Seems To Work

Verzeichnis

Enthält einen Eintrag für jede Datei und jedes Unterverzeichnis in diesem Verzeichnis. Ein Eintrag umfasst:

  • Dateiname
  • Attribut (Definiert Typ des Eintrags: Verzeichnis, Archiv, Datenträgername, Versteckt, Nur Lesen, System...)
  • Zeit und Datum der Erzeugung
  • Datum letzter Zugriff
  • Clusternummer des ersten Blocks der Datei
  • Grösse der Datei in Bytes

Wichtig sind dabei folgende zwei Punkte:

  • Es wird nur der erste Block einer Datei angegeben (alle weiteren müssen aus der File Allocation Table ermittelt werden)

NTFS

Grundidee: Alles ist eine Datei

ToDo:
NTFS beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Unix ext2

inode

Root-Knoten einer Baumstruktur deren Blätter die zu einer Datei gehörenden Blöcke sind.

In einem Inode sind folgende Informationen gespeichert:

  • Inode Nummer (eindeutig pro Datei)
  • Besitzer der Datei
  • Bevorrechtigte Gruppe
  • Zugriffsrechte der Datei
  • Typ der Datei (einfache Datei, Verzeichnis, Link, etc)
  • Größe der Datei (in Bytes)
  • Referenzzähler (Anzahl der Hardlinks)
  • Datum der letzten Inode-Änderung (change time, ctime), des letzten Zugriffs auf die Datei (letzte Dateiöffnung/-ausführung, access time, atime) und der letzten modifikation der Datei (modification time, mtime)
  • Verweis/Verweise auf die eigentlichen Cluster der Datei

Bemerkung: Der Dateiname ist nicht im Inode gespeichert!


Verzeichnis

Bei UNIX Filesystemen sind auch Verzeichnise Dateien. Ein Verzeichnis setzt sich also zusammen aus

  • Inode
    • Enthält Eintrag welcher auf die Dnodes zeigt
  • Dnode
    • Enthält die effektiven Einträge des Verzeichnisses. Zu jedem Unterverzeichniss ist die Inode-Nummer des Verzeichnisses angegeben

Links

http://homepage.smc.edu/morgan_david/cs40/analyze-ext2.htm

Aos FS

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Vergleich Dateisysteme

ToDo:
Angaben überprüfen und vervollständigen.
Alle momentan zu editierenden Einträge werden hier gesammelt.
Dateisystem Struktur für Zuordnung
Dateiname Datei
Struktur für Zuordnung
Datei Blöcke
Layout (vereinfacht) Umgesetzte Konzepte Weiteres
FAT Verzeichnisdateien
(unsortierte Listen)
File Allocation Table Bootsektor : FAT : FAT (2) : (Wurzelvz.) : Daten/Vz.blöcke
NTFS Verzeichnisdateien Master File Table MFT, als Runs PBR : MFT : Systemdateien : Dateibereich Journaling, Kompression, Alternate Data Streams
ext2 Verzeichnisdateien inode/dnodes Boot Block : Super Block : inodes : dnodes
ext3 Verzeichnisdateien inode/dnodes Boot Block : Super Block : inodes : dnodes Journaling Ext3 := ext2 + Journaling
Aos FS B-Baum

Vergleich Dateizugriffsmuster

Es soll auf die Datei f in ./a/b zugegriffen werden und 1 KB an die Datei angehängt werden. Die Blockgrösse sei 1 KB.

ToDo:
Reihenfolge der Aktionen ist zu korrigieren/genauer anzugeben. Ich habe diese komplett vernachlässigt!!
Alle momentan zu editierenden Einträge werden hier gesammelt.
ToDo:
Stimmt das für NTFS so?
Alle momentan zu editierenden Einträge werden hier gesammelt.
FAT UNIX (ext2, ext3) NTFS

Ausgangslage

  • Der erste Block von "." sowie die FAT sei schon geladen


Zugriffsmuster

  • Erster Block von "." schon geladen
  • Lade Block von a
  • Lade Block von b
  • Lade ersten Block von f
  • Durchlaufe die FAT um das Ende von f zu finden (kostet nichts, weil im Hauptspeicher)
  • Allokation eines Blocks in der FAT (kostet nichts, weil im Hauptspeicher)
  • Neuen Block schreiben
  • FAT auf Harddisk updaten
  • Verzeichnis-Eintrag Block von b updaten (File-Grösse, Datum, Zeit)


Ausgangslage

  • Der I-Node des aktuellen Verzeichnisses "." sei schon geladen
  • Ein I-Node hat 12 direkte, je einen einfach, zweifach und dreifach indirekten Eintrag


Zugriffssmuster

  • Datenblock von "." laden. Darin Inode-Nummer a ermitteln
  • Inode von a laden
  • Ersten Datenblock von a laden. Darin Inode-Nummer von b ermitteln
  • Inode von b laden
  • Ersten Datenblock von b laden. Darin Inode-Nummer von f ermitteln
  • Inode von f laden
  • Indirekten Block laden (muss dieser geladen werden?? wir brauchen keine Information daraus. Und zum Schreiben müssen wir den Inhalt auch nicht kennen?)
  • Neuen Datenblock anlegen
  • Neuen Datenblock in indirektem Block eintragen
  • Inode von f updaten (File-Grösse, Zeit)

NTFS

Ausgangslage

  • MFT Eintrag von "." geladen
  • Verzeichnisse sind "klein"

Zugrifssmuster

  • Im MFT Eintrag von "." nach a suchen (MFT-Index ermitteln)
  • MFT-Eintrag von a laden
  • Im MFT Eintrag von a nach b suchen (MFT-Index ermitteln)
  • MFT-Eintrag von b laden
  • MFT-Eintrag von b nach f suchen (MFT-Index ermitteln)
  • MFT-Eintrag von f laden
  • Neuen Block schreiben
  • Neuen Block als Run im MFT-Eintrag von f eintragen
  • Filesize und Datum/Zeit updaten


Interrupts

ToDo:
Wo gehören Interrups hin in der Zusammenfassung?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Arten von Unterbrechungen

  • Synchronous
    • Exceptions
      • Fault:
      • Trap: A processor-generated exception, usually resulting in a switch into kernel mode
      • Abort:
    • System-Calls: Implementation may use traps or interrupts
  • Asynchronous


Bemerkung:

  • Die Begriffe scheinen schwammig zu sein. Für trap existieren mehrere Gebrauchsformen. So wie es aussieht wird trap auch äquivalent zu system-calls verwendet.

First-Level-Interrupt-Handler

  • Läuft im Kernel-Mode und wird direkt von der Maschine aufgerufen
  • Blockiert das ganze System bis er fertig ist (muss Zeitnah abgearbeitet werden)


Einsatz

  • Realtime
  • Traps (Statk muss erhalten bleiben)

Second-Level-Interrup-Handler

  • Läuft im Benutzermodus und wird vom FLI inkarniert als Prozess oder Thread
  • Abschottung des Systems
  • Benutzerprogramme bekommen die Möglichkeit zur Interrupt Verarbeitung und damit User-Library Funktionalität
  • Auszuführender Interrupt code ist potentiell unsicher


Einsatz

  • Abschottung der Fehler vom System
  • Verwendung von Benutzer-Code, bei dem Kontext-Switches enthalten sein können

I/O-Subsysteme

I/O-Subsysteme lassen sich in zwei Klassen aufteilen:

  • Blockorientiert
  • Zeichenorientiert


Unterkapitel sind

  • Heapverwaltung
  • Stackverwaltung
  • Paging

Definitionen

Definition: Interne Fragmentierung

Interne Fragmentierung liegt vor, wenn der Speicherplatz in Blöcken nicht vollständig durch Nutzdaten belegt werden kann

Auswirkung

  • Erhöter Speicherverbrauch


Definition: Externe Fragmentierung

Externe Fragmentierung liegt vor, wenn die Daten nicht in zusammenhängenden Blöcken alloziert werden können

Auswirkung

  • Zugriffseffizienz schlechter

Heapverwaltung

Allokation

Mit Free-List

Die (expliziten) Free-Listen verketten den freien Speicher. Wird Speicher frei, so wird dieser wieder in die Free-Liste eingetragen.

  • Coalescing: Wenn möglich werden benachbarte Speicherbereiche verschmolzen

Bemerkung

Aus der Vorlesung Systemnahe Programmierung und Rechnerarchitektur sind die Konzepte der expliziten und impliziten Free-Listen bereits bekannt


First-Fit

First-Fit nimmt den ersten verfügaren, ausreichend grossen Speicherblock

  • Eigenschaften
    • Tendenz, dass kleine Blöcke am Anfang und grössere am Ende des Heap frei sind
  • Allokation
    • Grosse Blöcke: langsam: Da erst alle kleinen Blöcke am Anfang durchgegangen werden müssen
    • Kleine Blöcke: schnell: Am Anfang vorhanden
  • Externe Fragmentierung:

Best-Fit

First-Fit nimmt den kleinsten verfügaren, ausreichend grossen Speicherblock

  • Allokation: Es muss fast immer die ganze Free-Liste durchsucht werden. Das fast stammt daher, dass ein genau passender Block gefunden werden kann
  • Externe Fragmentierung: Nur wenige kleine Blöcke (=geringe Externe Fragmentierung)

Next-Fit

First-Fit nimmt den nächsten verfügaren, ausreichend grossen Speicherblock

  • Allokation: Schnell, da der Anfang der Liste meist auf einen sehr lange nicht mehr benutzten Speicherbereich zeigt, wo in der Regel ein grosser freie Block ist
  • Externe Fragmentierung:

Worst-Fit

First-Fit nimmt den grössten verfügaren, ausreichend grossen Speicherblock

  • Allokation: Es muss immer die ganze Free-Liste durchsucht werden
  • Externe Fragmentierung:
  • Blockgrösse: Worst-Fit benutzt immer den grössten Block. Dadurch ist tendenziell die maximale Blockgrösse kleiner als bei anderen Verfahren

Buddy-System

Beim Buddy-Sytem wird eine Folge von Blockgrössen festgelegt, so dass zwei alignierte, aufeinanderfolgende Blöcke einer Grösse (Buddies genannt) zur nächstgrösseren Grösse verschmolzen werden können. Es eignen sich zu diesem Zweck vor allem Zweierpotenzen und Finbonacci Zahlen

Sind zu wenig kleine Blöcke vorhanden, wird ein nächst grösserer gemäss gemäss der definierten Folge von Blockgrössen unterteilt.

Die freien Blöcke werden in einer speziellen Baumstruktur verwaltet

  • Merging: Schnelle Verschmelzung benachbarter Blöcke
  • Externe Fragmentierung: gut ?weshalb?
  • Interne Fragmentierung: schlecht (50% < Nutzgrad <= 100%)


Vergleich Allokationsstrategien

Vergleich unter der Annahme, dass nur eine einzige Free-List verwendet wird

ToDo:
Bei Fragmentierung bin ich mir nicht 100% sicher. Die allokation sollte gemäss übungen stimmen? Was meint ihr?
Alle momentan zu editierenden Einträge werden hier gesammelt.
Verfahren Allokationsgeschwindigkeit Fragmentierung durchschnittliche Blockgrösse
First-Fit Schnell externe Fragmentierung: Gut (Tendenz kleine Blöcke am Anfang, grössere am Ende des Heap)
Next-Fit i.A schneller als First-Fit externe Fragmentierung: Schlechter als First-Fit
Best-Fit Langsam: Fast immer die ganze Liste durchsuchen externe Fragmentierung: Gut (Nur wenige sehr kleine Blöcke, dafür eher kleinere Blöcke als Worst-Fit)
Worst-Fit Langsam: Immer die ganze Liste durchsuchen externe Fragmentierung: ??? tendenziell keine sehr grossen freien Blöcke
Buddy-System externe Fragmentierung:
interne Fragmentierung: schlecht

Garbage Collection

Unerscheidung von Garbage-Collector-Algorithmen:

  • Stop-And-Go: Der Garbage-Collector hat so lange exklusiven Zugriff wie er benötigt um alles zu Bereinigen
  • Inkrementell: Der Garbage-Collecor hat nur für eine gewisse Zeit exklusiven Zugriff. D.h. er muss unterbrochen werden können und seine Arbeit zu einem späteren Zeitpunkt wieder fortsetzen können


Vorteile von Garbage-Collector gegenüber keine Garbage-Collector

  • Keine dangling-pointer
  • Keine memory-leaks

Root-Set Bestimmung

(=Ankermenge)

Es gibt mehrere Ansätze das Root-Set zu bestimmen:

  1. Basierend auf Codebereich und Heap
    • Compilererzeugte Metadaten
      • Zeiger Offsets in Modulen und Typen
    • Laufzeit Typdeskriptor
      • Verweise vom Objekt auf Typdeskriptor
  2. Basierend auf dem Stack und Registern
    • Compilererzeugte Metadaten
      • Zeiger Offsets in Prozeduren
    • Spekulative Methoden
      • Bei diesem Verfahren werden alle Werte die auf dem Stack liegen als Adressen interpretiert und geschaut, ob diese auf einen allozierten Block auf dem Heap zeigen
      • Entscheidet konservativ (Da möglicherweise Blöcke zum Root-Set genommen werden, welche eigentlich frei wären)


Reference-Counting

Jedes Objekt enthält einen Referenzzähler. Wird der Zähler eines Objektes A 0, so kann das Objekt A entfernet werden. Dies bedeutet auch, dass der Zähler aller Child-Objekte des Objektes A dekrementiert werden muss.

Beim Refernce-Counting-Verfahren entstehen Probleme mit zyklischen Datenstrukturen: Objekte zeigen gegenseitig aufeinander. Dadurch werden diese Objekte nie entfernt (da Counter immer grösser 0), sind unter Umständen jedoch gar nicht mehr erreichbar.


Eigenschaften

  • Produktive Prozess wird nicht unterbrochen: Memory Management Overhead verteilt sich auf die Ausführungszeit
  • Lokalität der Referenz zur Kollektionszeit
  • Sofortige Finalisierung möglich
  • Speicherplatz: In naiven Implementationen eine Pointer-Grösse pro Referenz

Mark & Sweep

Der Mark & Sweep Collector läuft in zwei Phasen:

  • Garbage Detection (Mark)
    1. Bestimmung des Root-Set: Dazu werden globalze Zeiger im Codebereich, lokale Zeiger auf dem STack und temporäre Zeiger in Registern verwendet
    2. Traversierung des Objektgraphen: Ausgehend vom Root-Set werden alle erreichbaren Objekte traversiert und markiert
  • Garbage Collection (Sweep)
    1. Traversierung des Heaps: Der Heap wird linear traversiert und nicht markiete Bereiche werden der Free-Liste hinzugefügt


Bemerkung: Die Sweep-Phase kann auch mit der Allokation von neuen Blöcken durchgeführt werden. Dieses Vorgehen wird als Lazy-Sweep bezeichnet


Eigenschaften

  • Wird nur bei Bedarf durchgeführt
  • Unterbricht den produktiven Prozess

Mark & Compact

Der Mark & Compact Collector arbeitet ähnlich wie der Mark & Sweep Collector. Zusätzlich wird der Heap kompaktifiziert (allozierte Blöcke werden neu angeordnet / defragmentiert)

Dies bringt das Problem mit sich, dass Zeiger durch das Verschieben von Blöcken ungültig werden. Mögliche Lösungsansätze sind:

  • Indirekte Zeiger: Anstatt direkt auf das Objekt zu zeigen, zeigt man auf stets auf einen Zeiger, welcher dann auf das Objekt zeigt. Dadurch muss nur an genau einem (bekannten) Ort die neue Position des Objektes geupdatet werden
  • Direkte Zeiger: In diesem Fall müssen existierenden Zeiger geupdatet werden


Der Mark & Compact Collector läuft in zwei Phasen:

  • Garbage Detection (Mark)
    1. Bestimmung des Root-Set: Dazu werden globalze Zeiger im Codebereich, lokale Zeiger auf dem STack und temporäre Zeiger in Registern verwendet
    2. Traversierung des Objektgraphen: Ausgehend vom Root-Set werden alle erreichbaren Objekte traversiert und markiert
  • Kompaktifizierung (Compact)
    1. Kompaktifizierung des Heaps: Die allozierten Blöcke auf dem Heap werden neu angeordnet


Eigenschaften

  • Keine Defragmentierung
  • Schnelle Allokation, da nach der Kompaktifizierung nur ein grosser freie Block vorliegt


Generational

Bei Generational-Collectors wird ausgenutzt, dass Objekte unterschiedliche Lebensdauern haben

  • Bei Objekte die lange gelebt haben, geht man deshalb davon aus, dass sie auch noch lange leben werden (Alte Generation)
  • Bei Objekte, welche erst kürzlich erzeugt wurden, geht man davon aus, dass sie nicht lange leben werden (Junge Generation)

Objekte alter Generation wedern deshalb selten überprüft, Objekte junger Generationen häufiger

Vergleich Garbage-Collector

Verfahren Eigenschaften Schwierigkeiten ?
Reference-Counting
Mark & Sweep
Mark & Compact
Generational

Inkrementelle Kollektion

  • Eignet sich am ehsten für Echtzeitanforderungen, da der produktive Prozess nur kurz unterbrochen wird


Dreifarben-Modell

(=Wellenfront Modell)

Beim Dreifarben-Modell werden alle Objekte in eine von dei Klassen (Farben) eingeteilt


  • schwarze Objekte: wurden bereits traversiert. Sind hinter der Wellenfront
  • graue Objekte: Werden traversiert. Sind auf der Wellenfront
  • weisse Objekte: Wurden noch nicht traversiert. Sind vor der Wellenfront


Invariante
Es existiert kein weisses Objekt, auf welches NUR ein schwarzes Objekt zeigt.

In anderen Worten, es darf kein schwarzes Objekt geben das auf ein weisses Objekt A zeigt, wenn nicht auch ein anderes weisses oder graues Objekt auf dieses weisse Objekt A zeigt.


Wird der GC unterbrochen und der produktive Prozess nimmt seine Arbeit wieder auf, so muss dieser dafür sorgen, dass die Invariante eingehalten wird. Dadurch ist sichergestellt, dass nur Objekte eingesammelt werden, welche auch wirklich Garbage sind.

ToDo:
Ab hier spekulativ!! Stimmt das?
Alle momentan zu editierenden Einträge werden hier gesammelt.
  • Der produktive Prozess legt neues Objekte A an
    • Auf A zeigt ein graues Objekt: OK, da das graue Objekt noch traversiert wird
    • Auf A zeigt ein weisses Objekt: OK, da das weisse Objekt noch traversiert wird
    • Auf A zeigt ein schwarzes Objekt B: Die Invariante muss eingehalten werden. Zwei Möglichkeiten:
        1. Das neue Objekt A wird grau markiert: Dadurch ist sichergestellt, dass A und seine Kinder markiert werden
        2. Das schwarze Objekt B welches auf A zeigt wird grau gefärbt und das neue Objekt A weiss: Dadurch wird B und seine Kinder ein weiteres mal traversiert. Also auch A markiert


Anwendungsmöglichkeit

  • Inkrementeller Mark & Sweep Kollektor

Kopierender Kollektor

ToDo:
kopierender Kollektor erklären
Alle momentan zu editierenden Einträge werden hier gesammelt.


Baker'sche Treadmill

Doppelt verkettete Liste Liste von Blöcken repräsentiert den Heap.

ToDo:
Bakersche Treadmill erklären. Kapier ich nicht...
Alle momentan zu editierenden Einträge werden hier gesammelt.

Paging

Anwendungen

  • Memory-Mapped-IO
  • Swapping
  • Prozess-Isolation
  • Dynamische Stack-Allokation
  • Copy-On-Write

Definitionen

Definition: Working-Set

Das working-set eines Prozesses ist die Menge von Pages, welche in einer gewissen Zeitspanne vom Prozess verwendet wurden

Trahsing

Definition: Trashing

TODO


Mögliche Ursachen

  • Das working-set aller aktiven Prozesse ist grösser als der verfügbare Hauptspeicher

Seitenersetzungsalgorithmen

Begriffe

Belady's anomaly

ToDo:
belady's anomaly beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Least Recently Created (LRC)

  • FIFO
  • Schlechte Behandlung permanent benutzter Seite
  • Verbesserung durch Second Chance

Least Recently Used (LRU)

  • Implementierung durch Aging

Aging

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Second Chance

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.


Vergleich Seitenersetzungsalgorithmen

Verfahren Eigenschaften Schwierigkeiten ?
Least Recently Created (LRC)
Least Recently Used (LRU)
Aging
Second Chance

Zuteilungsstrategien

Gleichmässige Verteilung

ToDo:
Strategien stichwortartig erleutern
Alle momentan zu editierenden Einträge werden hier gesammelt.

Bedarfsorientierte Verteilung

ToDo:
Strategien stichwortartig erleutern
Alle momentan zu editierenden Einträge werden hier gesammelt.

Seitenverwaltung

Einstufige Seitentabellen

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Mehrstufige Seitentabellen

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.


Inverse Seitentabellen (hashing)

Die inverse Seitentabelle ermöglicht das Mapping von existierender Seite (physikalischer Adresse) nach zugehöriger virtueller Adresse der Seite.

Eigschaften

  • Weniger Speicherplatz benötigt: Da nur existierende Seiten aufgelistet werden ist die Zahl der Einträge viel (!) kleiner, als wenn man alle möglichen virtuellen Adressen von Seiten auflistet und dazu die meistens nicht existente physikalische Adresse der Seite
  • Langsamere Adressübersetzung: Die Liste der virtuellen Adressen muss im worst-case komplett durchgelaufen werden, bis die dazugehörige physikalische Adresse gefunden wird
    • Verbesserung durch hashing

Prozessorenverwaltung

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.
ToDo:
Ist Multicore überbegriff für SMP und NUMA?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Symmetric Multiprocessing (SMP)

Aufbau

  • Jeder CPU hat eine eigene Cache
  • Die CPU's hängen alle am selben Bus
  • Die CPU's greifen alle über diesen Bus auf das selbe RAM zu


Weiteres

  • Cache-Kohärenz
    • Bus Snooping: Cache hört mit was über den Bus kommuniziert wird
    • MESI Protokoll: ?TODO?


Eigenschaften

  • Trahsing bei geringer Affinität der Prozesse


ToDo:
Eigenschaften ergänzen
Alle momentan zu editierenden Einträge werden hier gesammelt.

Non Uniform Memory Access (NUMA)

Aufbau

  • Jede CPU hat eigene Cache
  • x CPU's bilden zusammen eine Zelle
  • In einer Zelle sind alle CPU's über einen Bus verbunden
  • Jede Zelle hat eigenes RAM


Weiteres

  • Speicher-Konsistenz
    • Verschiedene Modelle in Hardware implementiert


Eigenschaften

  • Lokales RAM: schneller Zugriff
  • Entferntes RAM: langsamer Zugriff


Beispiele

  • Cell
  • NVIDIA GPU

Multicore

Aufbau

  • Mehrere Prozessorkerne auf einem DI
  • Seperater und gemeinsamen Cache


Beispiele

  • NUMA
    • z.B. AMD Opteron
  • SMP
    • Intel Xeon

Concurrency

Definitionen

Definition: Semaphore

Globale nicht negative Integer value die nur durch die Operationen P und V verändert werden kann (Erlaubt die Limitierung der Anzahl Prozesse in einem Abschnitt))

Implementation

  • mittels Spinlock
  • mittels Scheduler (block process)


Definition: Binary Semaphore

Semaphore welche nur die Werte 0 und 1 annehmen kann (Erlaubt den gegenseitigen Ausschluss von Prozessen in einem Abschnitt)


Definition: Mutex

Binary Semaphore die den gegenseitigen Auschluss von Prozessen erlaubt


Definition: Monitor

Ein Monitor ist eine Sammlung von Prozeduren, Variablen und Datenstrukturen, auf welche stets nur durch einen Prozess zugregriffen werden kann. (Implementation z.B. mit Semaphore und Scheduler)

Bedingungen für kritische Abschnitte

  1. Mutual exclusion (Wechselseitiger Ausschluss): Keine zwei Prozesse dürfen gleichzeitig in eine kritische Region eintreten
  2. Es darf keine Annahme über die Geschwindigkeit oder Anzahl der CPU's gemacht werden
  3. Kein grundloser Auschluss: Prozesse dürfen nur ausgeschlossen werden, wenn wirklich ein Prozess in der kritischen Region ist
  4. Kein Prozess darf ewig im kritischen Abschnitt verweilen
    • Keine "Starvation": Jeder Prozess muss einmal Zugang zur kritischen Region erhalten
    • Kein "Deadlock": Keine Verklemmung

Vermeidung von Deadlocks

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.


Implementation des gegenseitigen Ausschlusses

Ansätze sind:

  1. Sperren der Interrupts: Dadurch wird das Auswechseln von Prozessen und das Ausführen von Interrupt-Handlern verhindert
  2. Software-Ansatz: z.B Dekker Algorithmus, Peterson Algorithmus
  3. Hardwareunterstützt: Assembler-Befehle wie Test-And-Set (TAS), Compare-And-Swap (CAS), Exchange (XCHG)


Eigenschaften

1.

  • Funktioniert nur auf Einprozessor-Systemen
  • Betriebssystem verliert Kontrolle

2. - 3.

  • Aktives Warten
  • Starvation möglich (Aufgrund des zufälligen Scheduling)
  • Verklemmung möglich (Durch Prioritätsprobleme)

Concurrency & Prozessprioritäten

Die Verwendung von Locks auf Ressourcen in Verbindung mit Priority Based Preemptive Scheduler (PBPS) kann zu Priority Inversion führen


Gegenmassnahmen sind

  • Priority Inheritance: Sobald ein höher priorisierter Prozess eine Ressource von einem tiefer priorisierten Prozess anfordert, erhält der tiefer priorisierte Prozess die Priorität des höher-priorisierten, wartenden, Prozess
  • Priority Ceiling: Prozesse welche Ressourcen locken erhalten die Priorität "sehr hoch" solange sie das Lock besitzen


Priority Inversion

Hoch-Priorisierter Prozess wartet auf Ressource die von einem tief-priorisierten Prozess gelockt ist:

  • Hoch-Priorisierter Prozess kann nicht ausgeführt werden
  • Tief-Priorisierter Prozess hat keine Priorität und wird deshalb nicht ausgeführt
  • -> Mittel-Priorisierte Prozesse werden mehr ausgeführt als der Hoch-Priorisierte


Scheduling

ToDo:
Stimmt das? Was ist Unterschied zwischen Globalen dispatching und prioritätsbasiertem scheduling?
Alle momentan zu editierenden Einträge werden hier gesammelt.

Scheduling lässt sich in zwei Bereiche unterteilen

  • Globale Dispatching Strategien: ??? Beschreibung, allgemein ???
  • Prioritätsbasiertes Scheduling: ?? Beschreibung, allgemein ???

Definitionen

Definition: Verweilzeit

Die Verweilzeit ist die Zeit vom Eintreten eines Prozesses in die Warteschlange bis zum Beenden dieses Prozesses


Definition: Wartezeit

Die Wartezeit ist die Zeit welche eine Prozess auf Ausführung warten muss

Konzepte

Ready-Liste

Liste der Prozesse die bereit zur Ausführung sind

Prozesse werden in die Ready-Liste aufgenommen wenn

  • Neu erstellt wurden
  • Yield aufgerufen haben
  • Rückkehr aus waiting-condition (z.B durch signal)
  • Rückkehr aus waiting-ressource
  • Preempted werden


Prozesse werden aus der Ready-Liste entfernt wenn

  • Prozess beendet wird
  • Prozess vom scheduler dispatched wird

Symmetrie

ToDo:
Stimmt das?
Alle momentan zu editierenden Einträge werden hier gesammelt.
Assymetrisches Multi-Processing
Scheduling und I/O auf einem ausgewählten Prozessor, welcher für alle anderen mitplant
Symmetrisches Multi-Processing
Jeder Prozessor plant selbst, welcher Prozess er laufen lässt


Affinität

Soft Affinity
Thread wird möglichst auf einem Prozessor gehalten
Hard Affinity
Feste Zuordnung eines Threads zu einem Prozessor


Eigenschaften

  • Bessere Nutzung der Cache (L1, L2): Kein trashing
  • Wirkt load balancing entgegen

Load Balancing

Mit Load Balancing versucht man alle Prozessoren möglichst gleich auszulasten


Eigenschaften

  • Wirkt der Affinität entgegen: Was zu trashing führen kann

Globale Dispatching Strategien

First Come First Served (FIFO)

  • Die Prozesse welche zuerst in die Warteschlange eintreten, werden zuerst gescheduelt.

Eigenschaften

  • non-preemptive: Ein endlos laufender Prozess kann das ganze System lahm legen
  • Priorität: Prozesse die zuerst kommen

Highest Priority First (HPF)

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.


Shortest Job First (SJF)

Zu jedem Zeitpunkt wird derjenige Prozess ausgeführt, welcher die kürzeste Laufzeit hat. Dies bedeutet insbesondere, dass wenn während der Ausführung eines Prozesses A ein neuer Prozess B ankommt und die Laufzeit von B kürzer ist als die verbleibende Laufzeit von A, wird A preempted und B ausgeführt.


Eigenschaften

  • Preemptive
  • Prioriät: Prozess mit kürzester Laufzeit

Round Robin (Timesharing)

  • Basiert auf einer FIFO Warteschlange
  • Time slicing: Der auszuführende Prozess erhält ein fixes Zeitquantum (Time-Slice) zur Ausführung. Danach muss er sich wieder hinten in die Warteschlange einordnen


Eigenschaften

  • Preemptive: Endlos laufende Prozesse beeinträchtigen das System nicht
  • Zu kleine time-slices: Overhead durch Kontextwechsel dominant
  • Zu grosse time-slices: System träge


Shortest Remaining Time

Basiert auf SJF, unterbricht zusätzlich die Prozesse falls dies zu einem Vorteil führt


Eigenschaften

  • Preemptive

Longest (Highest) Response Ratio Next

ToDo:
Beschreiben
Alle momentan zu editierenden Einträge werden hier gesammelt.

Vergleich dispatching Strategien

Strategie Eigenschaften Schwierigkeiten ?
First Come First Served (FIFO)
  • Non-preemptive
Highest Priority First (HPF)
Shortest Job First (SJF)
  • Preemptive
Round Robin (Timesharing)
Shortest Remaining Time
(Verbesserter Round Robin)
  • Preemptive
Longest (Highest) Response Ratio Next

Prioritätsbasiertes Scheduling

Konzepte

Zyklenscheduling

(=Clock-Driven Scheduling)

ToDo:
Stimmt das? Genauer beschreiben!
Alle momentan zu editierenden Einträge werden hier gesammelt.

Die Zeitachse wird aufgeteilt in time-slices und gegliedert in Haupt und neben Zyklen

Rate Monotonic (RM), Highest Rate First, Statisch

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.


Latest Release Time (LRT)

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Least Slacktime (LST)

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.
Definition: Slacktime

Slacktime ist die verbleibende Zeit nach Ausführung des Prozesses bis zu seiner Deadline, wenn der Prozess als nächstes geschedult würde


Eigenschaften

  • Geeignet für aperiodische Tasks
  • Potenziell suboptimal bei kurzzeitiger 100% Auslastung
  • Suboptimal bei Verwendung mit ununterbrechbaren Threads
  • Anwendbar bis 100% Systemlast

Earliest Deadline First (EDF)

ToDo:
{{{1}}}
Alle momentan zu editierenden Einträge werden hier gesammelt.

Vergleich prioritätsbasierte Schedulingstrategien

Strategie Eigenschaften Schwierigkeiten ?
Rate Monotonic (RM)
Latest Release Time (LRT)
Least Slacktime (LST)
Earliest Deadline First (EDF)

Virtualisierung

Definition

Definition: Application Binary Interface (ABI)

Das ABI ist das Interface zum Betriebssystem auf welchem die Prozesse laufen


Virtual machines

Definition: System-Virtuelle Maschine

Virtuelle Maschine welche die ISA (Instruction Set Architecture) virtualisiert

Eigenschaften

  • Gesamte ISA muss virtualisiert werden
Definition: Prozess-Virtuelle Maschine

Virtuelle Maschine welche das ABI virtualisiert

Eigenschaften

  • User-ISA muss virtualisiert werden
  • ABI des Betriebssystems muss virtualisiert werden

Intressante links