SP2 Vorlesungsnotizen

1 [2018-10-26 Fri] Scheduling

Scheduling ist die Einplanen und entscheiden wann Prozesse eingelstet werden sollten
- Unterscheidet sich von Dispatching welches dieses tatsächlich umsetzt
- In der Praxis ist Prozesswechsel nicht eindeutig. Es kann passieren das Logisch ein Prozess schon lauft, aber physikalisch noch nicht dazu gekommen ist
Wenn ein Prozess auf die Peripherie Wartet (Speicherstöße) kann es den Prozessor erlauben die CPU Last einem anderen zu übergeben
- Sobald der Erste Prozess bereit ist wird es auf die "Ready" liste gelegt
- Durch dieses "Überlappen" gelingt es dem System erfolgreicher die CPU besser aus-zulasten
Durchschnittliche Fadenverzögerung beträgt \(\frac{n-1}{2} \cdot t_\text{cpu}\) und ist meist vernachlässigbar wenn \(t_\text{cpu} << t_\text{mem}\)
- dh. in einem Speicherstoß können mehere viele CPU-Stöße gelegt werden
Arten von Scheduling

Langfristige Planung (m bis s)
Zur Lastkontrolle, nicht notwendig

Mittelfristige Planung (ms bis s)
Für Swapping, nicht umbedingt Notwendig

Kurzfristige Planung (μ s bis ms)
Einlastungsreihenfolge, obligatorisch

2 [2018-11-02 Fri] Weiteres zu Scheduling

Abhängig von Umständen sind verschiedene Faktoren bei der Planung zu bevorzugen
- Kooperative- (Prozess geben selbstständig die CPU ab, kann zu monopolisierung führen) vs. Preemptive Planung (CPU kann entzogen werden)
- Deterministische- (Es ist a priori bekannt was wann laufen soll) vs. Probabilistische Planung (Abschätzen zur Laufzeit)
- Vorlaufende- (Vor dem Start festgelegt was wann laufen soll, "off-line") vs. Mitlaufende Planung (Zur Laufzeit bestimmt, "on-line")
- Asymetrische- (Verschiedene Befehlssätze werden in betracht genommen) vs. Symmetrische Planung (Gleiche Befehlsätze, bspw bei Muliti-Porcessor)
Kontroll-Methoden

FCFS (First Come, First Serve)
Prozesse werden in einer Queue abgearbeitet

RR (Round Robin)
Mit "Zeitscheiben" (time slices) werden Prozess nach einer Maximalzeit verdrängt

VRR (Virtual RR)
RR mit einer Vorzugsliste von bereiten Prozessen, die auf bspw. IO stöße gewartet haben

SPN (Shortest Prozess Next)
Einplannung nach zu erwartender Laufzeit

HRRN (Highest Response Ratio Next)
SPN mit Berücksichtigung von Wartezeiten

SRTF (Shortest Ready Time First)
Einplannung nachdem welches prozess erwartet wird noch am kürzesten laufen zu müssen

MLQ (Multi-Level Queue)
Unterteilung von Prozessen nach Arten in verschiedene Queues welche lokal geplant werden, mit globaler Planung der einzelnen Queues

MLFQ (Multilevel Feedback Queue)
MLQ mit Versetzung von Prozessen auf höhere oder niedrigere Prioritäten.

3 [2018-11-09 Fri] Nebenläufigkeit

Nebenläufigkeit bezeichnet das verhalten von kausal nicht abhängigen Prozessen
- Wird von Daten- und Zeitabhängigkeit (für Echtzeitbetrieb relevant, wenn Prozesse zu bestimmten Zeiten ausgeführt werden müssen) eingeschränkt
Unter concurrent oder simultanious Processes versteht man Prozesse welche sich mehr als eine Aktionsfolge in Raum und Zeit überlappen
- Hierfür notwendig ist ein Betriebsysteme welches horizontal oder vertikales Multiplexing unterstützt, hinreichend ist das dieses vom Prozess ausgenutzt wird
- Nebenläufigkeit kann entweder "off-line"/statisch koordiniert werden, falls die Mittel dazu bereit stehen (analytischer Ansatz), oder wie meist "on-line"/dynamisch explizit synchronisiert wird (konstruktiver Ansatz)
Unter atomare Aktion bezeichnen Aktionen welche nach außen hin scheinbar gleichzeitig (ohne Unterbrechung, nicht unterteilbar) stattfinden
- Müssen je nach Abstraktionsebene nicht tatsächlich atomar sein, durch Kritischer Abschnitte erzwingbar
- Falls es zu einem Wettstreit um Ressourcen (CPU, Speicher, Signale, …) kommt muss dieses aufgelöst werden
- Freihabe/Vergabe muss hierfür korrekt koordiniert werden
- Mögliche Synchronisationmethoden
  
  Unterbrechend
  Verhindert neue Prozessauslösung, verdrängt jetzige Prozesse nicht
  
  Blokierend (Mutual Exlusion)
  Sperrt Betriebsmittel von neuen Prozessen, was zu Verzögerung führen kann (pessimistischer Ansatz)
  
  Nicht Blokierend
  Mögliches zurückrollen von Änderungen, falls Konflikte festgestellt werden (optimistischer Ansatz)

4 [2018-11-16 Fri] Monitore und Kritische Bereiche

Ein Monitor ist Erweiterung eines Kritischen Bereichs für höhere Sprachen.
- Conditions ermöglichen bedeingetes Zugreifen auf Ressourcen oder Variablen
- Diese "mehrseitige Synchronisation" steht im Kontrast zur "einseitigen Syncrhonisation" von wait und signal aufrufen
- Abhängig von Modell, können Bedinungsvariablen Blocken (Hansen oder Hoare) oder nicht (Mesa)

5 [2018-11-23 Fri] Binäre Semaphore

Binäre Semaphoren können benutzt werden, um allgemeine Semaphoren umzusetzen.
- Monitore eignen sich hierfür nicht, da diese meist auf Semaphoren basiert sind
- Unterschied zwischen Semaphor und Mutex
  - Semaphoren können von allen Prozessen freigegeben werden
  - Mutexe (Mutual Exclusive) können nur vom besitzendem Prozess freigegeben werden
- Mutexe erlauben also das kontrollierte Benutzen von Semaphoren
Die \(\mathcal{P}\) und \(\mathcal{V}\) Operationen müssen dabei atomar sein

6 [2018-11-30 Fri] Spinlocks, TAS und CAS

Ein Spinlock wartet aktiv auf Ressourcen, welche von anderen Prozessen beansprucht werden
- Die relevanten Operationen sind hierbei aquire (oder lock) und release (oder unlock).
Atomare Operationen
Test and Set (TAS)
Lese Datum aus dem Speicher, schreibe 1 und gebe alten Wert zurück

Compare and Swap (CAS)
\(CAS(var, cmp, new) = \begin{cases} \mathit{true},\; new \to var &\text{if}\;var = cmp\\\mathit{false}&\text{else}\end{cases}\)
- Im Gegensatz zu Sequenzieller Synchronisation, arbeitest CAS auf lokalen Kopien der Daten, und schreibt bedingt die Werte zurück (Transaktion).

7 [2018-12-07 Fri] Stillstand und Verklemmungen

Ein Betriebsystem muss Verklemmung und Verhungernung vermeiden, wozu Buchführung gemacht werden sollte.
- Virtualisierung von verschiedenen Ressourcen bietet Möglichkeit Ressourcen nicht "direkt" vergeben, sondern nur den Anschein zu geben.
- Möglichkeiten
  statisch
  vor Laufzeit oder zu bestimmen Zeitpunkten werden Ressourcen verschiedenen Prozessen zugeteilt (benötigt eine "brach-phase")
  - Kann zu "suboptimaler Auslastung" führen, deswegen in der Praxis weniger oft benutzt
  dynamisch
  Resourcen werden dann angeboten und zubereitet werden, sobald sie benötigt werden (eg. malloc)
  - Kann zur Verklemmung führen
"Tödliche Umarmung" bzw. Stillstand entsteht aus fehlerhaften Verwaltung von gemeinsamen Ressourcen.
- Entweder "Todsperre"/Verklemmung (deadlock, erkennbar, "inaktives warten") und "Lebendspere" (lifelock, nicht erkennbar, "aktives warten" dh. der Prozessor läuft weiter)
  Verklemmung
  Entsteht wenn verschiedene Prozess gegenseitig Blokiert sind, und vom Scheduler als solches bekannt sind (-> kann mittels Zyklenerkennung in Graphen erkannt werden)
  
  "Lebendsperre"
  Mit (bspw spin locks) versuchen wache (-> immer auf der Bereitliste) Prozesse auf Resourcen zuzugreifen, wo durch ungünstiges beanspruchen von Ressourcen zu keinem Ergebnisse kommen können. Kann deswegen nicht eindeutig erkannt werden
  - Konzeptionelles Beispeil: (Speisende Philosophen Problem
    
    Notwendige Bedingungen zur Verklemmung von gekoppelten Prozessen: mutual exclusion, hold and wait, no preemption. Wenn zirkular gewartet wird, kann es zu einem Deadlock kommen. Wird eines vermieden, können deadlocks
    
    Vermeidbar durch umstrukturierung des Algorithmusses, oder eine ausführlichere Analyse der Anforerungen was Vorabwissen benötigt

8 [2018-12-14 Fri] Speichervirtualisierung

Zum Virtualisieren des Speichers muss ein Ein-/Auslagerungsmechanismus vorhanden sein, um den Arbeitsspeicher auf Festplatten (u.ä.) zu kopieren und vice versa
- Beim Paging wird dieses mit "Page-Faults" koordiniert, wo ein "Present Bit" indiziert ob eine Seite sich im Arbeitsspeicher befindet oder nicht
- Falls das "Present Bit" nicht gesetzt ist, verweist die Adresse der Page-tabelle auf den Hauptspeicher
In nicht-Echtzeit Systemen ist nicht bekannt auf welche Adressen zugegriffen wird, müssen approximative, suboptimale Verfahren (im Gegensatz zu MIN) verwendet werden.
- Diese sind:
  FIFO
  First-In-First-Gut
  
  LFU
  Least-Frequently-Used
  
  MFU
  anti-LFU
  
  LRU
  Least-Recently-Used
  - Mit Variation Second Chance wird aus "Am Längsten", "Länger nicht benutzt", da eine Seite zweimal als Inaktiv bemerkt werden muss, bevor diese Ausgelagert wird
  - Mit Hardware-Timestamps oder Kondensatoren umsetzbar
- Diese sind Probabilistisch, da ungünstige Situationen leicht zu Provozieren sind
- Alternativ zum "On-Demand" Paging kann auch ein probablistischer Ansatz helfen, um Zugriffsfehlern vorzubeugen
Das "Seitenflattern" beschreibt den Umstand das zu viel Aufwand für das Ein-/Auslagern von Seiten aufgewandt wird
- Ein "Freiseitenpuffer" kann dafür sorgen dieses zu vermeiden, indem zu jeder Zeit eine gewisse Anzahl von logisch abwesenden, aber physikalisch vorhandenen Seiten nach FIFO verwaltet wird, und somit asynchron Bestimmbar ist, was "frei" ist

9 [2018-12-21 Fri] …

10 [2019-01-11 Fri] Dateisysteme

Festplatten bestehen aus meheren Zylindern, welche jeweils unterteilt sind in Sektoren und Zonen. In diesen sind wiederum (nummerierten) Blöcke enthalten
Da eine Datei oft mehr als ein Block, weswegen verschiedene Speichermethoden existeieren:
Kontinuierliche Speicherung
Daten werden in aufeinander folgende Blöcke gespeichert. Erhöht Fragmentierungsgefahr.

Verkettete Speicherung
Am Anfang von jedem Block wird ein Verweis auf den nächsten logischen Block gespeichert. Probleme sind hierbei die daraus entstehende Lesezeit und und Fehleranfälligkeit.
- Variation benutzt in FAT Sytemen, wo Verkettung extern in einer "File Allocation Table" gespeicher wird
Indiziertes Speichern
Index-Blöcke verweisen auf Blöcke von Daten, und auf indirekt indizierte Blöcke für größere Daten

11 [2019-01-18 Fri] Weiteres zu Dateisystemen

Für größere Dateisysteme wird Journaling verwendet
- Alle Operationen (löschen, verkürzen, erweitern, etc.) wird als Transaktion erfasst
- Transaktionen (mit redo und undo Anweisungen) werden in einem Log gespeichert, um Inkonsistenzen zu erkennen und reparieren
- Alternative Möglichkeit sind Log-Structured-FS, wo alle Änderungen auf Kopien getätigt werden, mit der Gefahr der höheren Fragmentation
Datensicherung ist notwendig wegen der Gefahr des Totalausfalls von Platten
- Einfachste Möglichkeit ist die Sicherung auf externes Speicher
  - Um effizienter (Zeit, Speicher) zu sein können nur Inkrementelle Backups benutzt werden, in denen die Änderungen im Zustand seit dem letztem Backup gespeichert werden
- Durch Einsatz von mehrerer Platten können RAID \(n\) (redundant array of independent disks) Strategien benutzt werden:
  
  RAID 0
  Daten werden über meheren Platten gespeichert
  
  Keine Datensicherung wird garantiert, da wenn eine Platte ausfällt, das gesamte System ausfällt
  
  RAID 1
  Alle Schreibzugriffe gehen auf beide Platten (kann durch Hardware Optimierungen beschleunigt werden)
  
  Benötigt mehr Speicher, ist aber schneller beim Lesen
  
  RAID 4
  Mehrere Platten + Paritäts Block (xor aller Platten)
  
  Besitzt die Gefahr der hohen Auslastung der Paritäts-Plate
  
  RAID 5
  Paritäts-Blöcke werden auf allen Systemen verteilt
  
  RAID 6 und höher unterstützen zunehmen den Ausfall mehrerer Platten gleichzeitig.