Semaphoren
Semaphoren
Eine Semaphore implementiert passives (blockierendes) Warten: ein atomarer Zähler + eine Warteschlange. wait() dekrementiert (blockiert ggf.), signal() inkrementiert (weckt ggf.). Wartende verbrauchen keine CPU-Zeit.
Idee
Bei längeren Wartesituationen ist passives Warten besser als das aktive Warten der Spinlocks: Wartende Prozesse liegen in einer Warteschlange und verbrauchen keine CPU-Zeit. Das setzt die Hilfe des Betriebssystems voraus.
Eine Semaphore besteht aus:
- einem atomaren Zähler mit Dekrement
wait()und Inkrementsignal(), - einer Warteschlange von Prozessen.
typedef struct { int counter; struct task_struct *waiter; } sema;
Semantik
counterwird auf einen Wert > 0 initialisiert und zählt Ressourcenanforderungen.- Dekrementiert ein Prozess den Zähler unter 0, wird er schlafen gelegt (in die Warteschlange).
- Wird der Zähler inkrementiert, wird ein wartender Prozess geweckt.
wait(sema *S){ S->counter--; if (S->counter < 0){ add to waiter; sleep(); } }
signal(sema *S){ S->counter++; if (S->counter <= 0){ remove one from waiter; wake it; } }
Beide Operationen müssen atomar sein (intern oft mit einem Spinlock geschützt).
Interaktiv: blockierendes Warten
Genau dieser Ablauf — wait() blockiert, signal() weckt — Schritt für Schritt:
Spezialfälle
- Binäre Semaphore / Mutex (
counter ∈ {0,1}) → reiner wechselseitiger Ausschluss. - Zählende Semaphore → erlaubt bis zu n gleichzeitige Zugriffe (z.B. Pufferplätze im Producer/Consumer).
Werden mehrere Semaphoren in unterschiedlicher Reihenfolge angefordert, drohen Deadlocks — siehe Philosophenproblem.
Verwandte Notes
Spinlocks · Kritischer Abschnitt & Mutual Exclusion · Deadlocks · Philosophenproblem · Race Conditions
