3.2.2.1 Semaphorenkonzept

Next: 3.2.2.2 Message Passing Up: 3.2.2 Semaphoren Previous: 3.2.2 Semaphoren

3.2.2.1 Semaphorenkonzept

Die Semaphore kann als strukturierter Datentyp aufgefaßt werden mit den

Elementen:
$\ensuremath{\bullet}$ $\ensuremath{\mathbb{S} }$ -Wert (Integer)
$\ensuremath{\bullet}$ Warteschlange (queue)

und Operationen ( $\bullet$ init):
$\ensuremath{\bullet}$ $\ensuremath{\mathbb{P} }$ roberen $\equiv$ WAIT
$\ensuremath{\bullet}$ $\ensuremath{\mathbb{V} }$ erhogen $\equiv$ SIGNAL

Die Operationen $\ensuremath{\mathbb{P} }$ und $\ensuremath{\mathbb{V} }$ sind atomar.

Die Operationen sind mit den Elementen wie folgt verknüpft :

$\ensuremath{\mathbb{P} }$ (s):	$\ensuremath{\mathbb{S} }$ -Wert 0	$\longrightarrow$	Prozeß in Queue [Zug auf Strecke]
	$\ensuremath{\mathbb{S} }$ -Wert 0	$\longrightarrow$	( $\ensuremath{\mathbb{S} }$ -Wert) $\,:=\,0$ und Resourcen ist verfügbar
			[Strecke ist frei, Einfahren und Signal auf ''Rot'' setzen]
$\ensuremath{\mathbb{V} }$ (s)	queue ist leer	$\longrightarrow$	( $\ensuremath{\mathbb{S} }$ -Wert) $\,:=\,1$ [Signal auf ''Grün'' setzen]
	queue nichtleer	$\longrightarrow$	Aktiviere einen (wartenden) Prozeß
			[Wartenden Zug einfahren lassen, Signal bleibt ''Rot'']

Die Abfrage $\ensuremath{\mathbb{P} }$ (s) geschieht nur einmal pro Prozeß, daher ist die queue notwendig.

Beispiele für Semaphoren-Anwendungen

exklusiver Zugriff (z.B. , )

$\ensuremath{\mathbb{S} }$ Semaphore $\longleftarrow$ INIT( $\ensuremath{\mathbb{S} }$ ) ist notwendig, sonst Deadlock
$\ensuremath{\mathbb{R} }$ Resourcen

Abbildung 3.7: Exklusiver Zugriff mittels Semaphoren
$\begin{figure} \unitlength0.05\textwidth \begin{picture} (18,5) \put(0,0){\li... ...put(5,1){\vector(4,3){3.2}} \thinlines % \end{picture}\\ [0.5ex] \end{figure}$

Ergebnis ist eindeutig ( $N\,:=\, (N+1) - 1$ ) !!
Eigenschaftssynchronisation (z.B. Produzent-Konsument)

2 Semaphoren
A $\longrightarrow$ signalisiert vollen Puffer; INIT(A) mit 0
B $\longrightarrow$ signalisiert leeren Puffer; INIT(A) mit 1

Abbildung 3.8: Eigenschaftssynchronisation mittels Semaphoren
$\begin{figure} \unitlength0.05\textwidth {\large \begin{center} \begin{pictur... ...} \put(7.2,2){\vector(1,0){1.3}} \end{picture} \\ \end{center}} \end{figure}$

Tritt auf bei der $\omega$ -Gauß-Seidel-Iteration (vorwärts) für das Laplace-Problem, mit dem 5-Punkte-Differenzenstern diskretisiert. $\begin{displaymath} \widehat{c} \makebox[0pt]{}_{i,j} \;:=\; c_{i,j} + \left(... ...-1} + 4 c_{i,j} - c_{i+1,j} - c_{i,j+1} \right] }\right) / 4 \end{displaymath}$
Hier tritt $\widehat{c} \makebox[0pt]{}_{i,j}$ als Konsument auf und alle anderen Größen sind Produzenten (auch $\widehat{c} \makebox[0pt]{}_{i-1,j}$ und $\widehat{c} \makebox[0pt]{}_{i,j-1}$ !!). Siehe auch Abschnitt 3.1 .

**Abbildung 3.7:** Exklusiver Zugriff mittels Semaphoren
$\begin{figure} \unitlength0.05\textwidth \begin{picture} (18,5) \put(0,0){\li... ...put(5,1){\vector(4,3){3.2}} \thinlines % \end{picture}\\ [0.5ex] \end{figure}$

**Abbildung 3.8:** Eigenschaftssynchronisation mittels Semaphoren
$\begin{figure} \unitlength0.05\textwidth {\large \begin{center} \begin{pictur... ...} \put(7.2,2){\vector(1,0){1.3}} \end{picture} \\ \end{center}} \end{figure}$

Dijkstras Lösung des ''Dinner for Five''

In the universe we assume declared

1.

the semaphore mutex initially

2.

the INTEGER ARRAY C[0:4] initially all elements

3.

the semaphore INTEGER ARRAY prisem[0:4] initially all elements

4.

there exists a procedure

 procedure test (integer value k);
   if C[(k-1) mod 5] <> 2   and   C[k] == 1   
                            and   C[(k+1) mod 5] <> 2
      begin  C[k] := 2,  V(prisem[k])  end
 end

Bemerkung :
$C[k] \;=\; \begin{cases}0 & \hspace{2em}\text{Platz ist frei} \\ 1 & \hspace{... ...} \\ 2 & \hspace{2em}\text{Platz besetzt, 2 Gabeln in Hand} \\ \end{cases}$

$prisem[k]\,==\, 1 \;\;\;$ Philosoph darf mit dem Essen anfangen.

Obige Procedure besteht für den Philosophen in den Abfragen

Hat der linke Nachbar keine 2 Gabeln, d.h. hat er keine Gabel in der Hand ? ( Er ißt nicht !)
Sitze ich am Tisch und habe ich Hunger ?
Hat der rechte Nachbar keine 2 Gabeln ?
Falls die Abfragen alle mit ja beantwortet werden können, nimmt Philosoph die 2 Gabeln neben sich und fängt an zu Essen.

5.

In this the live of philosophes can be coded (philosoph

 1:     cycle begin  think
 2:                  P(mutex)
 3:                    C[w] := 1;  test(w)
 4:                  V(mutex)
 5:                  P(prisem[w]);  eat
 6:                  P(mutex)
 7:                    C[w] := 0;  test[(w+1) mod 5];  
                                   test[(w-1) mod 5]
 8:                  V(mutex)
 9:           end

Erläuterung:

3:: Setzen und falls möglich 2 Gabeln nehmen.
5:: Habe ich die Erlaubnis zum Essen ? Wenn ja dann esse - ansonsten warte, bis die Erlaubnis erteilt wird (d.h. Semaphore prisem[w] gelöscht ist.)
7:: Nach dem Essen den Platz freigeben und den Nachbarn mitteilen, daß die beiden Gabeln wieder frei sind.

Nähere Erläuterungen sind in der Zeitschrift c't 12/90 auf Seite 246 zu finden bzw. im Internet.

Next: 3.2.2.2 Message Passing Up: 3.2.2 Semaphoren Previous: 3.2.2 Semaphoren

Gundolf Haase
1998-12-22