Synchronisation

Question 1

Vorteile von kooperierenden Prozesse und Threads

Answer 1

• Verteilen von Arbeitspaketen auf mehrere Prozesse
• Teilen von Zwischenergebnissen in einem Shared Memory Segment
• Schreiben der Ergebnisse in eine gemeinsame Datei

Ergebnisse können von der Reihenfolge der Abarbeitung abhängen.
Ohne Synchronisation können geteilte Ressourcen inkonsistent werden.

Question 2

Race Conditions

Answer 2

Eine Race Condition tritt auf, wenn zwei Prozesse versuchen, auf dieselben Daten im
Speicher (kritischer Bereich) zuzugreifen bzw. diese zu ändern.
Ein einfaches Beispiel sind zwei Prozesse, die dieselbe Zählervariable inkrementieren.
Um dies zu verhindern werden Semaphore verwendet.

Question 3

Critical Section

Answer 3

Abschnitt eines Programms, in dem auf eine geteilte Ressource zugegriffen wird.

Wenn so eine Ressource keinen gleichzeitigen Zugriff erlaubt,
muss die CS geschützt werden und darf nur von einem
Prozess oder Thread gleichzeitig ausgeführt werden.

⇒ Wir benötigen einen Mutual Exclusion Mechanismus

Question 4

Mutual Exclusion

Answer 4

• Software Algorithmen (mit atomaren Speicherzugriffen)

Ein Mutex (Mutual Exclusion) ein Semaphore mit 2 Zuständen (0=Unlock und 1=Lock).

Wenn ein Prozess prüft, ob er auf eine kritische Region zugreifen kann, prüft er den Mutex.
Wenn der Mutex 0 ist, setzt er den Mutex atomar auf 1 (er “erwirbt die Sperre”) und kein anderer Prozess kann die kritische Region betreten. Nachdem der Prozess mit der kritischen Region fertig ist, setzt er den Mutex wieder auf 0.

Question 5

Mutex Lock

Answer 5

Objekt, das zwei Zustände annehmen kann: locked und unlocked. Um zwischen diesen Zuständen zu wechseln, gibt es zwei Operationen: lock und unlock.

Wird ein Mutex gelockt, kann kein anderer Prozess oder Thread den Mutex locken, bis er wieder entsperrt wurde. Versucht ein Prozess oder Thread einen gelockten Mutex zu locken, wird er blockiert, bis der Mutex wieder entsperrt wurde.

Question 6

Condition Variables

Answer 6

ermöglichen es Threads, bestimmte Ereignisse zu notifizieren und auf diese zu warten. Hierfür bieten sie zwei Operationen an:

• wait() wartet auf eine Notifizierung. Der Thread wird blockiert, bis ein anderer Thread die Condition Variable notifiziert.
• signal() notifiziert einen wartenden Thread. Falls es keinen wartenden Thread gibt, wird die Notifizierung verworfen.

Condition Variables werden in Kombination mit Mutex Locks verwendet, um Race Conditions zu vermeiden.

Question 7

Semaphoren

Answer 7

Objekt, das einen ganzzahligen Wert enthält, der mit bestimmten Operationen atomar verändert werden kann:

• Initialisierung auf einen nicht-negativen Wert
• Atomares Dekrementieren mit der Operation wait(). Falls
  der Wert 0 ist, wird der Prozess oder Thread blockiert.
• Atomares Inkrementieren mit der Operation signal(). Falls es blockierte Prozesse oder Threads gibt, wird einer davon fortgesetzt.

Question 8

Arten von Semaphoren

Answer 8

Binäre Semaphoren: können nur die Werte 0 und 1 annehmen und können an Stelle von Mutex Locks verwendet werden.

Zählsemaphoren können beliebige Werte annehmen und
werden oft verwendet, um eine Anzahl von geteilten Ressourcen zu verwalten.

Question 9

Das Producer-Consumer Problem

Answer 9

Es gibt zwei Arten von Threads:

• Producer erzeugen Daten und
• Consumer verarbeiten diese Daten.

Der Austausch der Daten erfolgt über einen geteilten,
größenbeschränkten Puffer.

Question 10

Welche Anforderungen muss eine korrekte Lösung des Producer-Consumer Problems erfüllen?

Answer 10

1. Producer und Consumer dürfen nicht gleichzeitig auf den Puffer zugreifen.
2. Der Puffer hat eine maximale Größe.
3. Wenn der Puffer voll ist, muss der Producer warten.
4. Wenn der Puffer leer ist, muss der Consumer warten.

Question 11

Deadlock

Answer 11

Ein Deadlock ist eine Situation, in der zwei oder mehr Prozesse (oder Threads) nicht weiterarbeiten können, weil sie jeweils auf einen der anderen Prozesse warten.

Question 12

Wann tritt ein Deadlock auf?

Answer 12

1. Mutual Exclusion: Nur ein Prozess kann eine Ressource gleichzeitig nutzen. Kein Prozess kann auf eine Ressource zugreifen, die von einem anderen Prozess genutzt wird.
2. Hold and Wait: Prozesse halten ihre zugewiesenen Ressourcen während sie auf die Zuweisung anderer Ressourcen warten.
3. No Preemption: Ressourcen können den Prozessen nicht gewaltsam entzogen werden.
4. Circular Wait: Es existiert eine geschlossene Kette von Prozessen, die jeweils auf die Freigabe einer Ressource warten, die vom nächsten Prozess in der Kette gehalten wird.

Question 13

Resource Allocation Graph

Answer 13

Ein Resource Allocation Graph (RAG) ist ein gerichteter Graph, der die Zuweisung von Ressourcen an Prozesse darstellt

Question 14

Wie geht man gegen Deadlocks vor?

Answer 14

• Deadlocks verhindern, indem man eine der vier Bedingungen aushebelt.
• Deadlocks vermeiden, indem bei jeder Ressourcenallokation das System auf einen sicheren Zustand überprüft wird (z.B. Bankieralgorithmus).
• Deadlocks beseitigen, indem man sie zuerst erkennt und einen oder mehrere beteiligte Prozesse terminiert.

Question 15

Erkläre die Begriffe Livelock und Starvation

Answer 15

Livelock
Wenn mehrere Prozesse versuchen, einen Deadlock zu verhindern, kann es vorkommen, dass sie dadurch dennoch gegenseitig blockiert werden.

Starvation
Wenn mehrere Prozesse auf eine Ressource warten, kann es vorkommen, dass ein Prozess durch unfaire Scheduling Entscheidungen wiederholt übergangen wird.