Semaphore (Semaphor)

Erfunden von Edsger W. Dijkstra (Niederländer, daher heißen die Operationen oft P und V).

• P (Proberen / Wait): Versuche reinzufahren (Zähler - 1). Wenn 0, warte.
• V (Verhogen / Signal): Fahre raus (Zähler + 1). Wecke einen Wartenden.

Nutzung: Rate Limiting ("Maximal 10 API-Requests pro Sekunde").

1. Binary Semaphore vs. Mutex

Eine binäre Semaphore (0 oder 1) verhält sich fast wie ein Mutex. Unterschied:

• Mutex: Hat einen "Besitzer". Nur der Thread, der zugeschlossen hat, darf aufschließen.
• Semaphore: Hat keinen Besitzer. Thread A kann rein ("wait"), Thread B kann die Schranke öffnen ("signal"). Das erlaubt komplexere Signalisierungen zwischen Threads.

2. Dining Philosophers Solution

Man kann Semaphoren nutzen, um Deadlocks zu lösen (z. B. "Erlaube nur 4 Philosophen am Tisch mit 5 Gabeln").

1. Dijkstra’s P & V: Die mathematische Basis

Edsger W. Dijkstra führte 1965 die Operationen P (proberen - prüfen) und V (verhogen - erhöhen) ein. In modernem C# oder Java heißen sie meist Wait() und Release(). Mathematisch gesehen ist eine Semaphore ein Integer $S \geq 0$.

• P(S): Falls $S > 0$, dekrementiere $S$ und fahre fort. Falls $S = 0$, blockiere den Thread, bis $S > 0$ wird.
• V(S): Inkrementiere $S$. Falls Threads auf $S$ warten, wecke einen davon auf. Der entscheidende Punkt: Diese Operationen müssen atomar sein. Das OS garantiert über Hardware-Instruktionen (wie Compare-and-Swap), dass niemals zwei Threads gleichzeitig den Zähler von 1 auf 0 setzen und beide glauben, sie hätten den Parkplatz gewonnen.

2. Priority Inversion: Das Mars-Pathfinder-Problem

Ein berüchtigter Bug, der 1997 den Mars-Rover fast lahmgelegt hätte. Ein hoch-priorisierter Thread (A) wartet auf eine Semaphore, die ein niedrig-priorisierter Thread (C) hält. Ein mittel-priorisierter Thread (B) läuft derweil munter weiter, weil er keine Semaphore braucht. Das Problem: B klaut C die CPU-Zeit. C kann die Semaphore nicht freigeben. A (der wichtigste Thread) verhungert, während B arbeitet. Die Lösung ist Priority Inheritance: Das Betriebssystem erkennt diese Abhängigkeit und hebt die Priorität von C temporär auf das Niveau von A an, damit C seine Arbeit beenden kann und die Semaphore für den Boss (A) freigibt.

3. Spincount & Kernel-Transitions

Das Rufen einer Semaphore (wait()) ist teuer, weil es meist eine Context-Switch in den Kernel-Mode erfordert. Die CPU muss Register sichern, den Scheduler fragen und den Thread schlafen legen. In High-Performance Systemen nutzt man oft "Hybrid Semaphores" mit einem Spincount: Bevor der Thread wirklich schlafen geht (Kernel-Call), dreht er ein paar Hundert Runden in einer hohlen while-Schleife (Spinning) und prüft, ob der Zähler frei wird. Oft wird die Ressource in Nanosekunden frei – das Spinning ist dann massiv schneller als das schlafengehen und wieder aufwachen.