Title: IN0009_GBS / GBS: Kapitel 3: Parallele Systeme und Synchronisation
On every note of this deck, unless a note says otherwise:
Title: IN0009_GBS::GBS: Kapitel 3: Parallele Systeme und Synchronisation
Logo: tum_logo.png

Front: Welche Interaktionen zwischen Prozessen sind möglich?
Back: - Kausale Beziehungen
- Kommunikation: Austausch von Nachrichten (Auch Rechensystem unabhängig)
- Koordinierung
- Konkurrenz: Prozesse konkurrieren um gemeinsame Ressourcen

Front: Warum kann die Parallelität von Aktivitäten zu nicht-deterministischem Verhalten von Prozessen führen?
Back: - Scheduler bestimmt über den Ablauf eines Prozesses (Meistens viele Faktoren z.B. Interrupts).
- Multi-Core/CPU Systeme mit echter Parallelität

Front: Wie können parallele Aktivitäten auf der Modell-Ebene beschrieben werden?
Back: - Aktionsstrukturen: Fokus auf Aktionen und deren Abhängigkeiten
- Petri-Netze: Fokus auf Zuständen und Zustandsübergängen

Front: Wie können parallele Aktivitäten auf der Programmiersprachen-Ebene beschrieben werden?
Back: - POSIX Threads (pthread_create, etc.)
- Prozesshierachien (fork, join)
- Kommunikationskonzepte (send, recv)
- Synchronisationskonzepte (lock, unlock)

Front: Wie können parallele Aktivitäten auf der Betriebssystem-Ebene beschrieben werden?
Back: - Prozesse (Programme in Ausführung)
- Threads (Leichtgewichtige Prozesse)
- Kommunikation
  - Shared Memory
  - Dateien
  - Nachrichten
- Synchronisation
  - Locks
  - Interrupts

Front: Mit welchen zwei Sichten kann das Verhalten von Aktivitäten beschrieben werden?
Back: - Aktionen: Modellierenden Einheiten (z.B. C-Anweisungen, Maschinenbefehl)
- Ereignisse Modellierten Einheiten, die Veränderungen bewirken

Front: Was sind die fünf primären Eigenschaften paralleler Systeme
Back: - Determiniertheit
- Störungsfreiheit
  - Ausführungsreihenfolge die Aktionen und Ergebnisse nicht beeinflusst
- Wechselseitiger Ausschluss (engl. mutual exclusion)
  - Max. ein Prozess greift gleichzeitig auf eine gemeinsame Ressource zu
- Verklemmungsfreiheit (engl. Deadlock)
  - Zyklische Wartesituation zwischen mehreren Prozessen
- Kein Verhungern (engl. Starvation)
  - Keine Prozesse die nie ausgeführt werden

Front: Was ist eine Race Condition?
Back: - Mindestens zwei Prozesse greifen lesend oder schreibend auf gemeinsame Ressourcen zu
- Das Ergebnis hängt von der Reihenfolge der Prozess-Ausführung ab

Front: Wie können Race Conditions verhindert werden?
Back: Wechselseitiger Ausschluss (engl. mutual exclusion) von konkurrierenden Aktionen.

Front: Was ist ein kritischer Abschnitt?
Back: In Kritischen Abschnitten greifen Prozesse auf gemeinsame Ressourcen zu.

Front: Was sind die vier Phasen des kritischen Abschnitts
Back: 1. Ausführung der unkritischen Abschnitte
2. Betreten eines kritischen Abschnitts
3. Ausführung der Aktionen des kritischen Abschnitts
4. Verlassen des kritischen Abschnitts

Front: Was ist das Leser-Schreiber-Problem?
Back: - Mehrere Leser sind gleichzeitig zugelassen
- Mehrere Schreiber dürfen nicht gleichzeitig aktiv sein
- Leser und Schreiber dürfen auch nicht gleichzeitig aktiv sein

Front: Was sind die vier Anforderungen an die Realisierung des wechselseitigen Ausschlusses?
Back: 1. Abschnitte sind wechselseitig ausgeschlossen
2. Nicht von einer Reihenfolge abhängig sein
3. Keine Annahmen über die Ausführungszeit eines Prozesses
4. Kein Prozess darf einen anderen Prozess unendlich lange daran hindern, seinen kritischen Abschnitt auszuführen

Front: Wie kann der wechselseitige Ausschluss auf der Hardwareebene implementiert werden?
Back: - Interrupts sperren (disabling), Unterbrechungssperre
- Atomare Maschinenbefehle u.a. TSL, cmpxchg

Front: Nenne zwei einfache Betriebsystemdienste die als Locking Mechanismen dienen.`
Back: - Dienste mit aktiven Warten: z.B. Spin-Lock
- Dienste mit passiven Warten: sleep, wakeup

Front: Warum kann man ein Mutex auch als eine binäre Semaphore bezeichnen?
Back: Eine binäre Semaphore hat nur zwei Zustände: 0 und 1. Ein Mutex ist ähnlich, da er ebenfalls nur zwei Zustände hat: gesperrt (locked) und entsperrt (unlocked).

Front: Was ist das Konzept von Eigentum bei einem Mutex?
Back: Konzept von "Eigentum": Nur der Thread, der den Mutex gesperrt hat, darf ihn auch wieder entsperren.

Front: Was passiert mit einem aktiven Prozess, wenn ein Interrupt signalisiert wird?
Back: Bei Signalisierung eines Interrupts wird der aktive Prozess unterbrochen und in den Zustand rechenwillig/wartend überführt, wobei er die CPU freigibt. Die Unterbrechung wird dann durch einen Handler (oder Interrupt Service Routine ISR) behandelt.

Front: Warum ist eine Unterbrechungssperre nur bei Ein-Prozessorsystemen zur Realisierung kritischer Abschnitte geeignet?
Back: In Multi-Prozessor Systemen verhindert die Unterbrechungssperre auf einem CPU nicht, dass andere Prozessoren auf die geteilte Ressource zuzugreifen.

Front: Warum müssen Kritische Abschnitte, die durch Unterbrechungssperren geschützt sind, kurz sein?
Back: Lange kritische Abschnitte mit deaktivierten Interrupts verhindern das Behandlen von anderen wichtigen Unterbrechnungen. Die Folge sind Verzögerungen, oder das Verpassen von Events/Benachrichtigungen.

Front: Warum sollte das Konzept einer Unterbrechnungssperre höchstens im Betriebssystem-Kern verwendet werden?
Back: - Grundbaustein für wichtige Dienste im Betriebsystem. Falsche Anwendung kann zur Instabilität, oder zum Absturz führen.
- Einschränkung der Privilegien auf Nutzerebene

Front: Wofür kann der "Compare and Exchange" Befehl verwendet werden?
Back: Atomarer Austausch von zwei Werten.
Beispiel Spin-Lock:
enter_crit_region:
  mov rax, $0 ; Expected val
  mov rbx, $42 ; New value
  cmpxchg [lock], rbx
  jne enter_crit_region ; Busy-Waiting
  ret
leave_crit_region:
  mov [lock], $0 ; Reset lock to 0
ret

Front: Wann sind Spin-Locks (aktives Warten) von Vorteil?
Back: - (Sehr) kurze Wartezeiten (gerade bei Multi-Core/CPU Systemen)
- Weniger Overhead (kein Kontextswitch) kann bei schnellen Wechseln (bzw. sehr kurzen kritischen Abschnitten) effizienter sein

Front: Kann aktives Warten zum Problem werden?
Back: Bei längeren kritischen Abschnitten, oder Wartezeiten.

Front: Erkläre die Semantik der P-Operation bei Semaphoren und wie sie funktioniert.
Back: Die P-Operation (down) dekrementiert die Kontrollvariable s. Falls s < 0 wird, muss der Prozess warten. Bei passivem Warten wird der Prozess in den Zustand wartend überführt und in einer Wait-Queue verwaltet.

Front: Was wird durch die V-Operation bei Semaphoren erreicht und wie interagiert sie mit der Wait-Queue?
Back: Die V-Operation (up) inkrementiert die Kontrollvariable s. Bei passivem Warten wird, falls die Wait-Queue nicht leer ist, ein Prozess aus der Queue in den Zustand rechenbereit überführt.

Front: Beschreibe, wie Semaphoren zur Realisierung kritischer Abschnitte genutzt werden.
Back: Semaphoren werden verwendet, indem ein Semaphor-Objekt definiert und seine Kontrollvariable initialisiert wird. Kritische Abschnitte werden dann mit P- und V-Operationsaufrufen geklammert, um wechselseitigen Ausschluss zu gewährleisten.

Front: Wie wird das Erzeuger-Verbraucher-Problem unter Verwendung von Semaphoren korrekt gelöst?
Back: Zur Lösung werden zwei zusätzliche Semaphore verwendet: "voll", initialisiert mit 0, zählt die Elemente im Puffer, und "leer", initialisiert mit der Anzahl der Pufferplätze, zählt die freien Pufferplätze. Der Producer und Consumer nutzen diese Semaphore, um den Zugriff auf den Puffer zu synchronisieren.
Warum reicht bei dem Erzeuger-Verbraucher-Problem nicht ein einziges Semaphor?

Front: Was ist das Monitor-Konzept?
Back: - Ziel: Abstrahieren von Semaphoren und Integrierung in Datenstrukturen
- Vermeiden von Problemen, wie
  - vertauschen der Operationen P und V
  - vergessen der zu einer P- zugehörigen V-Operation
- Beispiel: Methoden Produce und Consume auf gekapselten Puffer

Front: Warum sind Mutexe != binäre Semaphore?
Back: - Mutexe haben einen Owner, Semaphore haben keine Owner.
- Mutexe sind Locks: Sie realisieren mutual exclusion und können vor Races schützen.
- Semaphore dienen zum Synchronisieren von Aktionen: z.B. im Producer-Consumer Problem modellieren sie die Anzahl der vollen bzw. leeren Plätze im Puffer.

Front: Was ist das "Speisende Philosophen" Problem?

Front: Was sind die Takeaways vom "Speisenden Philosophen" Problem?
Back: - Kritische Abschnitte so kurz wie möglich halten, da unser Programm sonst zu einem sequentiellen Ablauf degeneriert.
- Es kann immer nur ein Philosoph gleichzeitig essen.
- Ressourcen erst belegen, wenn alle verfügbar sind.

Front: Nenne die vier Bedingung für Deadlocks.
Back: 1. Exklusiv nutzbare Ressource (Mutual Exclusion)
2. Belegen und Anfordern (Hold-and-wait)
3. Nicht Entziehbar (no-preemption)
4. Zyklische Wartebedingung (Circular wait): zyklische Kette von min. zwei Prozessen, die jeweils auf eine Ressource warten, die vom nächsten Prozess in der Kette belegt ist.
Es müssen alle vier Bedingungen erfüllt sein, damit ein Deadlock auftreten kann.

Front: Wie können Deadlocks modelliert werden?
Back: Die vier Deadlock Bedingungen können durch einen gerichteten Graphen, den Belegungsanforderungsgraphen, modelliert werden.
- Knoten: Prozesse (Kreise) und Ressourcen (Quadrate)
- Kanten
  - Prozess A belegt Ressource R: gerichtete Kante von R zu A
  - Prozess A fordert Ressource R an: gerichtete Kante von A zu R

Front: Nenne die vier Strategien zum Umgang mit Deadlocks.
Back: 1. Ignorieren: Vogel-Strauß Methode, wird in BS häufig gemacht z.B. Verwaltung der Prozesstabelle im Linux Kernel.
2. Deadlock-Detection (Erkennung): Das BS erkennt und beseitigt Deadlocks, falls sie auftreten sollten
3. Deadlock-Prevention (Verhinderung): BS setzt eine der Deadlock-Bedingungen außer Kraft
4. Deadlock-Avoidance (Vermeidung): BS führt keine Ressourcenzuteilung durch, die potentiell in einem Deadlock enden könnte

Front: Wann kann das Ignorieren eines Deadlocks sinnvoll sein?
Back: Wenn Prozesse neugestartet werden können, oder die Kosten für die Erkennung zu hoch sind.

Front: Was sind mögliche Probleme bei der Deadlock Erkennung?
Back: Komplexität, höhere CPU Nutzung und Execution delay.

Front: Was ist ein Problem bei der Vermeidung von Deadlocks?
Back: - Geringerer Durchsatz
- Komplexität
- Schlechte Skalierbarkeit

Front: Vorteil und Nachteil des Bankiers-Algorithmus zur Vermeidung von Deadlocks.
Back: - Vorteil: Kein Ressourcen Entzug
- Nachteil: Zukünftiger Bedarf muss bekannt sein

Front: Vorteil und Nachteil zur Verhinderung von Deadlocks mittels fester Reihenfolge bei Zuteilung.
Back: - Vorteil: Keine Laufzeitprüfungen
- Nachteil: Statisch, inflexibel

Front: Vorteil und Nachteil bei Erkennung von Deadlocks mittels periodischen Aufrufen:
Back: - Vorteil: Interaktive Reaktion
- Nachteil: Verlust durch Abbruch