3.2.2 Semaphoren

Next: 3.2.2.1 Semaphorenkonzept Up: 3.2 Synchronisation paralleler Prozesse Previous: 3.2.1 Einige Begriffe

3.2.2 Semaphoren

Ein generelles Problem beim Zugriff auf gemeinsame Ressourcen ist die Deadlock-Freiheit.

Deadlock :
Verklemmung, mehrere Prozesse warten auf je ein Ereignis welches aber nur durch einen der wartenden Prozesse ausgelöst werden kann.

Bsp.: Dinner for five [Dijkstras oder Hoare, 1971]

**Abbildung 3.5:** Dinner for five
$\begin{figure} \unitlength0.03\textwidth \begin{center} \begin{picture} (10,1... ...1}} % \put(1.36,7.65){\line(4,-3){1.1}} \end{picture}\end{center} \end{figure}$

''Das Leben der Philosophen besteht aus den sich abwechselnden Tätigkeiten Denken und Essen. Jeder Philosoph hat seinen Platz am Tisch.
Ihr einziges Problem - abgesehen von denen philosophischer Natur - besteht darin, daß die aufgetragene Mahlzeit eine sehr schwierige Art von Spaghetti ist, zu deren Verzehr man 2 Gabeln benötigt. Neben jedem Teller liegen 2 Gabeln, so daß grundsätzlich keine Schwierigkeiten auftauchen sollten. Es hat jedoch zur Folge, daß 2 Nachbarn nicht zur selben Zeit essen können'' [Rec94]

Die 5 Gabeln stehen hier stellvertretend für knappe Resourcen in einem großen System.

Lösungsvariante (Handlungsanweisung) 1:

1.: Wenn Du hungrig bist, setzte Dich an an Deinen Platz.
2.: Warte bis links eine Gabel frei ist und ergreife sie.
3.: Warte bis rechts eine Gabel frei ist und ergreife sie.
4.: Gib nach dem Essen beide Gabeln frei !

$\Longrightarrow$ Deadlock :
Alle Philosophen verhungern mit einer Gabel in ihrer linken Hand.

Lösungsvariante 2:

1.: Wenn Du hungrig bist, setzte Dich an an Deinen Platz.
2.: Warte bis links und rechts die Gabeln frei sind und ergreife sie.
3.: Esse Deine Spaghetti.
4.: Gib nach dem Essen beide Gabeln frei !

$\Longrightarrow$ ''Deadlock für alle'' ist ausgeschlossen, aber dem Einzelnen kann der Hungertod drohen (z.B. für Philosoph Nr.1, wenn sich Nr.0 und Nr.2 leicht überlappend beim Essen abwechseln).

Dijkstras Vorschlag : Einführung von Semaphoren (Semaphore ist ein Signal bei der holländischen Eisenbahn).

Semaphor :
Signal welches von einzelnen Prozessen betätigt wird und nicht von einer Zentralinstanz (Abb. 3.6).

Der Prozeß [Zug] wartet, wenn das Signal auf '' WAIT'' [Rot] steht. Ansonsten ist der Zugriff [Einfahrt] auf den kritischen Bereich [Fahrtstrecke] frei und der Prozeß [Zug] stellt das Signal auf '' WAIT'' [Rot] für alle anderen Prozesse [Züge].

**Abbildung 3.6:** Freigabe einer Semaphore
$\begin{figure} \unitlength0.03\textwidth \begin{picture} (30,8.5)(0,-1) \put(0... ...(30,3){\vector(1,0){3}} \put(30,2){\vector(3,-2){3}} \end{picture}\end{figure}$

Shared Memory $\longrightarrow$ Semaphorenkonzept
Distributed Memory $\longrightarrow$ Message-Passing Modell $\longrightarrow$ Kommunikation

Next: 3.2.2.1 Semaphorenkonzept Up: 3.2 Synchronisation paralleler Prozesse Previous: 3.2.1 Einige Begriffe

Gundolf Haase
1998-12-22