Semaphore

Zur Lösung dieses Problems hat E. W. Dijkstra 1965 vorgeschlagen sogenannte Semaphore einzuführen. Semaphore sind Integer-Variablen auf denen zwei Operationen up und down definiert sind. up und down sind Verallgemeinerungen von sleep und wakeup. Wird down auf eine Variable mit größer als 0 angewandt, so wird der Wert um 1 erniedrigt. Wird down auf 0 angewandt so legt sich der Prozess schlafen. Die Operation up angewandt auf einen Semaphor der den Wert 0 enthält, weckt einen (zufällig ausgewählten) Prozess auf, der sich bezüglich des Semaphors schlafen gelegt hat, und weckt ihn auf. Der Wert bleibt 0. Ist kein Prozess bezüglich des Semaphors blockiert, wird der Semaphor um 1 erhöht.

Sowohl die up- als auch die down-Operation sind atomare Operationen. Das heißt es ist nicht möglich die Ausführung von up oder down zu unterbrechen. Dies ist entscheidend, um das aufgezeigte Problem zu lösen.

Betrachten wir nun die Lösung des Erzeuger-Verbraucher-Problems mit Hilfe von Semaphoren (Abbildung

**Figure:** Lösung des Erzeuger-Verbraucher-Problems mit Semaphoren
$\begin{figure}\begin{center} \begin{program} typedef int semaphore; \par semap... ...item(); /* verarbeite Eintrag */ \} \} \end{program} \end{center}\end{figure}$

In der Lösung des Erzeuger-Verbraucher-Problems werden drei Semaphore eingesetzt. Der Semaphor empty zählt die leeren Puffereinträge und legt den Erzeuger schlafen, falls der Puffer voll ist. Der Semaphor full zählt die Puffereinträge und legt den Verbraucher schlafen, falls der Puffer leer ist. Der Semaphor mutex stellt sicher, dass sich immer nur ein Prozess in seinem kritischen Bereich befindet. Dieser Semaphor nimmt nur die Werte 0 und 1 an. Man nennt ihn deshalb auch binären Semaphor.

Das Konzept der Semaphoren direkt beispielsweise in der Sprache C zu programmieren bringt einige Probleme bei der Fehlersuche mit sich.

Betrachten wir zum Beispiel den Fehler, dass ein Programmierer versehentlich up und down verwechselt:

$\begin{program} up(mutex) \ldots critical_section() \ldots down(mutex) \end{program}$

Durch diesen Fehler ist es möglich, dass sich verschiedene Prozesse gemeinsamen in ihren kritischen Bereichen befinden. Der Fehler führt möglicherweise selten zu falschen Ergebnissen, weil er sich nur dann auswirkt, wenn sich tatsächlich verschiedene Prozesse gleichzeitig in ihren kritischen Bereichen befinden. Außerdem ist der Fehler nur sehr schwer reproduzierbar.

Ein weiterer möglicher Programmierfehler wäre, dass man ausversehen zweimal die down Operationen verwendet:

$\begin{program} down(mutex) \ldots critical_section() \ldots down(mutex) \end{program}$

Das Programm würde in diesem Fall immer mit einem Deadlock enden, denn der Prozess wird immer nachdem er den kritischen Bereich verlassen schlafengelegt.

Um das Auftreten von Fehlern dieser Art zu minimieren, gibt es eine ganze Reihe von Konstrukten in höheren Programmiersprachen, die es ermöglichen, Lösungen auf einer höheren Ebene anzugeben. Wir werden hier das Konzept der Kritischen Regionen und der Monitore vorstellen.