Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Synchronisation: Semaphore, Mutex und Deadlock
Zwei Threads erhöhen denselben Zähler gleichzeitig, am Ende fehlt eine Erhöhung. Wie kann das sein? Weil nebenläufige Prozesse, die auf gemeinsame Daten zugreifen, koordiniert werden müssen. Ohne Synchronisation entstehen Race Conditions. Die klassischen Werkzeuge dagegen sind Mutex und Semaphor.
Was du in der Klausur können musst:
- Race Condition und kritischer Abschnitt (mutual exclusion)
- Mutex vs. Semaphor (P/V-Operationen, Zählsemaphor)
- das Producer-Consumer-Muster mit Semaphoren
- Deadlock und die vier Coffman-Bedingungen
Die Idee in einem Satz
Synchronisation koordiniert nebenläufige Prozesse beim Zugriff auf gemeinsame Ressourcen. Im kritischen Abschnitt darf immer nur einer sein (gegenseitiger Ausschluss), durchgesetzt mit Mutex oder Semaphor.
Race Condition
Eine Race Condition liegt vor, wenn das Ergebnis von der zeitlichen Reihenfolge der Zugriffe abhängt. Klassiker: zwei Threads führen jeweils ein nicht-atomares "lies, erhöhe, schreibe zurück" auf demselben Zähler aus. Lesen beide den alten Wert, geht eine Erhöhung verloren (Lost Update).
Der Codebereich, der gemeinsame Daten verändert, heißt kritischer Abschnitt. Die Lösung ist gegenseitiger Ausschluss (mutual exclusion): in diesem Abschnitt darf immer nur ein Thread gleichzeitig sein.
Mutex und Semaphor
| Mutex | Semaphor | |
|---|---|---|
| Wert | binär (gesperrt / frei) | Zähler ≥ 0 |
| Besitzer | ja (nur der Sperrende entsperrt) | nein |
| Operationen | lock / unlock | P (down/wait) und V (up/signal) |
| Zweck | gegenseitiger Ausschluss | Ressourcen zählen, Reihenfolge |
Ein Semaphor (Dijkstra) ist ein Zähler mit zwei atomaren Operationen:
- P (down, wait): zählt herunter; ist der Wert 0, blockiert der Prozess, bis ein V kommt.
- V (up, signal): zählt hoch und weckt einen wartenden Prozess.
Ein Zählsemaphor verwaltet mehrere gleichartige Ressourcen; ein binärer Semaphor (0/1) wirkt wie ein einfaches Lock.
Producer-Consumer mit Semaphoren
Das Standardmuster: ein Producer legt Elemente in einen beschränkten Puffer, ein Consumer entnimmt sie. Zwei Zählsemaphore koordinieren das:
- leer (frei): zählt freie Plätze, startet bei der Puffergröße. Der Producer macht P(leer) vor dem Ablegen.
- voll: zählt belegte Plätze, startet bei 0. Der Consumer macht P(voll) vor dem Entnehmen.
- ein Mutex schützt zusätzlich den Pufferzugriff selbst.
Ist der Puffer voll (leer = 0), blockiert der Producer; ist er leer (voll = 0), blockiert der Consumer. Probier es aus:
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Deadlock
Ein Deadlock (Verklemmung) entsteht, wenn Prozesse zyklisch aufeinander warten und keiner mehr weiterkommt. Nach Coffman müssen dafür alle vier Bedingungen gleichzeitig gelten:
- Gegenseitiger Ausschluss (Mutual Exclusion): Ressourcen sind exklusiv belegt.
- Hold and Wait: ein Prozess hält eine Ressource und wartet auf eine weitere.
- No Preemption: Ressourcen werden nicht zwangsweise entzogen.
- Circular Wait: es gibt eine zyklische Wartekette.
Fehlt eine der vier Bedingungen, kann kein Deadlock auftreten. Darauf zielen Vermeidungsstrategien (z.B. immer alle Locks in derselben Reihenfolge anfordern, das bricht den Circular Wait).
Verwandt, aber anders: Starvation (Verhungern), wenn ein Prozess zwar nicht blockiert ist, aber durch unfaire Vergabe nie an die Reihe kommt.
Klausur-Faustregeln
1. Race Condition: das Ergebnis hängt von der Ausführungsreihenfolge ab, bei ungeschütztem Zugriff auf gemeinsame Daten.
2. Kritischer Abschnitt: nur ein Thread gleichzeitig (gegenseitiger Ausschluss).
3. Mutex = binäres Lock mit Besitzer; Semaphor = Zähler mit P (down) und V (up).
4. Zählsemaphor zählt verfügbare Ressourcen; bei 0 blockiert P, bis ein V kommt.
5. Producer-Consumer: Semaphore leer (freie Plätze) + voll (belegte) + Mutex für den Puffer.
6. Deadlock braucht alle vier Coffman-Bedingungen. Fehlt eine, kein Deadlock.
Häufige Stolpersteine
1. Mutex und Semaphor gleichsetzen. Ein Mutex ist binär und hat einen Besitzer (nur wer sperrt, entsperrt). Ein Semaphor ist ein Zähler ohne Besitzer, jeder kann V aufrufen.
2. Race Conditions für reproduzierbar halten. Sie sind nichtdeterministisch und treten nur manchmal auf, was die Fehlersuche so schwer macht.
3. P und V vertauschen oder vergessen. P (down) vor dem kritischen Abschnitt, V (up) danach. Fehlt das V, bleibt die Ressource für immer blockiert.
4. Beim Producer-Consumer die Reihenfolge verdrehen. Erst P(leer) bzw. P(voll), dann P(mutex). Sperrt man zuerst den Mutex und blockiert dann am Zählsemaphor, droht ein Deadlock.
5. Busy-Waiting (Spinlock) als Standard nehmen. Aktives Warten verschwendet CPU. Semaphore lassen den Prozess stattdessen blockieren und schlafen.
6. Deadlock und Starvation verwechseln. Deadlock: mehrere warten zyklisch, niemand kommt weiter. Starvation: einer wird durch unfaire Vergabe dauerhaft übergangen, das System läuft aber weiter.
Interaktiv verstehen
Semaphore in Aktion
Klicke Produce und Consume und beobachte die beiden Semaphore. Fülle den Puffer ganz, der Producer blockiert (leer = 0). Leere ihn ganz, der Consumer blockiert (voll = 0). Genau dieses Blockieren verhindert Zugriffe auf einen vollen bzw. leeren Puffer.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Merke dir die Startwerte: leer = Puffergröße, voll = 0, mutex = 1. Und die Reihenfolge: erst den Zählsemaphor (leer bzw. voll), dann den Mutex, sonst riskierst du einen Deadlock.
Praxis-Übung
Klausurfragen mit Lösungen (6)
- F1.Was ist eine Race Condition?
Antwort: ein Fehler, bei dem das Ergebnis von der zeitlichen Reihenfolge der Zugriffe auf gemeinsame Daten abhängt
Erklärung: Eine Race Condition liegt vor, wenn das Ergebnis davon abhängt, in welcher Reihenfolge nebenläufige Threads auf gemeinsame Daten zugreifen. Typisch ist der Lost Update bei nicht-atomarem Lesen-Ändern-Schreiben.
- F2.Was darf im kritischen Abschnitt gelten?
Antwort: nur ein Thread gleichzeitig (gegenseitiger Ausschluss)
Erklärung: Im kritischen Abschnitt (Zugriff auf gemeinsame Daten) muss gegenseitiger Ausschluss (mutual exclusion) gelten: höchstens ein Thread darf gleichzeitig drin sein. Das verhindert Race Conditions.
- F3.Was tut die P-Operation (down/wait) eines Semaphors?
Antwort: sie verringert den Zähler; ist er 0, blockiert der Prozess, bis ein V kommt
Erklärung: P (down/wait) verringert den Semaphor-Zähler. Ist der Zähler bereits 0, blockiert der aufrufende Prozess, bis ein anderer mit V (up/signal) wieder hochzählt.
- F4.Ordne die Begriffe zu.
Zuordnungen:
- Mutex → binäres Lock mit Besitzer
- Semaphor → Zähler mit P und V
- Race Condition → Ergebnis hängt von der Reihenfolge ab
- Deadlock → zyklisches Warten, keiner kommt weiter
Erklärung: Mutex = binäres Lock mit Besitzer, Semaphor = Zähler (P/V), Race Condition = reihenfolgeabhängiges Ergebnis, Deadlock = zyklische Verklemmung.
Typ: Zuordnung
- F5.Beim Producer-Consumer startet der Semaphor leer mit dem Wert der Puffergröße und voll mit 0.
Antwort: Wahr
Erklärung: Richtig. leer zählt die freien Plätze (anfangs alle, also Puffergröße), voll die belegten (anfangs 0). Der Producer macht P(leer) und V(voll), der Consumer P(voll) und V(leer).
Typ: Wahr/Falsch
- F6.Wie viele der vier Coffman-Bedingungen müssen für einen Deadlock gleichzeitig erfüllt sein?
Antwort: alle vier (Mutual Exclusion, Hold-and-Wait, No Preemption, Circular Wait)
Erklärung: Ein Deadlock erfordert alle vier Coffman-Bedingungen gleichzeitig. Bricht man eine (z.B. Circular Wait durch feste Lock-Reihenfolge), ist ein Deadlock unmöglich. Das ist die Grundlage der Deadlock-Vermeidung.
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Worin unterscheidet sich ein Mutex von einem Semaphor?
Antwort: ein Mutex ist binär und hat einen Besitzer (nur der Sperrende entsperrt); ein Semaphor ist ein Zähler ohne Besitzer
Erklärung: Der Mutex ist binär (gesperrt/frei) und besitzgebunden: nur der Thread, der gesperrt hat, darf entsperren. Ein Semaphor ist ein Zähler mit P/V, den jeder Thread hochzählen darf, geeignet zum Zählen von Ressourcen.
- F2.Was bewirkt die V-Operation (up/signal) eines Semaphors?
Antwort: sie erhöht den Zähler und weckt einen wartenden Prozess
Erklärung: V (up/signal) erhöht den Semaphor-Zähler um eins und weckt, falls vorhanden, einen an P blockierten Prozess. P und V sind die beiden atomaren Semaphor-Operationen.
- F3.Warum ist Busy-Waiting (Spinlock) oft ungünstig?
Antwort: es verschwendet CPU-Zeit durch aktives Warten, statt den Prozess schlafen zu legen
Erklärung: Beim Busy-Waiting prüft der Thread in einer Schleife ständig die Bedingung und verbraucht dabei CPU, ohne Fortschritt. Semaphore lassen den Thread stattdessen blockieren (schlafen), was die CPU freigibt.
- F4.Ein {{1}} ist ein binäres Lock mit Besitzer. Ein Semaphor ist ein Zähler mit den Operationen {{2}} (herunter) und {{3}} (herauf).
Lösungen pro Lücke:
- {{1}}: Mutex
- {{2}}: P / P (down) / down / wait
- {{3}}: V / V (up) / up / signal
Erklärung: Mutex = binäres Lock mit Besitzer. Semaphor-Operationen: P (down/wait) verringert und blockiert ggf., V (up/signal) erhöht und weckt.
Typ: Lückentext
- F5.In welcher Reihenfolge sollte der Producer die Semaphore anfordern, um Deadlocks zu vermeiden?
Antwort: erst P(leer), dann P(mutex)
Erklärung: Erst den Zählsemaphor P(leer), dann P(mutex). Würde der Producer zuerst den Mutex sperren und dann an P(leer) blockieren, könnte der Consumer den Mutex nie bekommen, ein Deadlock.
- F6.Wie verhindert man Deadlocks durch Brechen des Circular Wait?
Antwort: indem man alle Locks immer in derselben global festgelegten Reihenfolge anfordert
Erklärung: Fordern alle Threads ihre Locks in derselben festen Reihenfolge an, kann keine zyklische Wartekette entstehen (Circular Wait gebrochen). Damit fehlt eine der vier Coffman-Bedingungen und ein Deadlock ist ausgeschlossen.
