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.

Autor: Philip K.

Created: 10:14:43

Validate