Semaphore und Monitore

• Wurden 1965 von Dijkstra eingeführt.
• Gibt es in mehreren Varianten, hier eine:

Ein Sempaphor S ist eine Variable mit Natural-Werten und zwei Operationen

Wait(S)

if S > 0 then

S := S-1;

else

setze ausführenden Prozeß wartend;

end if;

  

Signal(S)

if es gibt auf S wartende Prozesse then

lasse ersten (FIFO) dieser Prozesse weitermachen;

else

S := S+1;

end if;

  

• Wait und signal werden atomar (= unteilbar) ausgeführt, d.h. keine andere Aktion zwischen Test und zugehöriger Handlung;
• wait und signal sind neben einer Initialisierung vor Prozeßstart die einzigen Operationen auf dem Semaphor.

Für Sempaphor S gilt folgende Invariante

Beispiel: Wechselseitiger Ausschluß

S: Semaphore := 1;

process 1

loop

   ...

Wait(S);

Critical_Section;

Signal(S);

   ...

end loop;

process 2 Genau wie bei process 1.

Lösung erweiterbar auf n 2 Prozesse.

1. Safety

   #CS 1 wegen (*) unmöglich.

2. Deadlockfrei

   Beide Prozesse warten

   

   S = 0 and #CS = 0

   

   1 = 0 (aus (*))

3. No starvation

   Process 1 wartet

   

   S = 0

   

   #CS = 1 (wegen (*))

   

   Process 2 in critical_section

   

   Process 2 macht als nächstes signal

   

   Process 1 wird aufgeweckt!

Varianten

Boolesche Semaphore

Einschränkung des Wertebereichs auf 0..1.

Schwächere Fairneßforderung

Z.B. Auswahl des wartenden Prozesses unbestimmt (nicht FIFO-Garantie); oder signalisierender Prozeß kann sofort wieder wait ausführen.

Implementierung

Durch Betriebssystemdienst oder (problematisch) busy waiting.

Korrektheit der Anwendung hängt ab von solchen Eigenschaften! Z.B. schwächere Fairneß kann bei obiger Lösung des mutual-exclusion Problems zu starvation führen!

Producer-Prozeß

erzeugt Daten.

Consumer-Prozeß

verarbeitet Daten.

Puffer

Datenstruktur für Zwischenspeicherung, gleicht vorübergehende(!) Unterschiede in Geschwindigkeit aus.

Dabei Synchronisation nötig.

• Consumer kann Datenelement erst lesen, wenn producer es geschrieben hat.
• Producer kann Datenelement erst schreiben, wenn Puffer freien Platz enthält.
• Ferner: Je nach Implementierung des Puffers sind Zugriffe unter wechselseitigen Ausschluß zu stellen!

Beispiel

• Puffer

  Vektor mit n 0 Plätzen und zyklischer (circular buffer) Verwendung (i := (i+1) mod n);

• Private Zeiger (Indizes) für producer und consumer, Lesezeiger folgt Schreibzeiger, beide zeigen jeweils auf nächste Position

Also

N: constant Positive := ...;

type Data is ...;

Buffer: array(0..N-1) of Data;

In_Ptr, Out_Ptr: Natural := 0;

Elements: Semaphore := 0; - Daten da?

Spaces: Semaphore := N; - noch Platz?

producer

D: Data;

begin

loop

Produce(D);

Wait(Spaces);

Buffer(In_Ptr) := D;

In_Ptr := (In_Ptr+1) mod N;

Signal(Elements);

end loop;

end Producer;

consumer

D: Data;

begin

loop

Wait(Elements);

D := Buffer(Out_Ptr);

Out_Ptr := (Out_Ptr+1) mod N;

Signal(Spaces);

Consume(D);

end loop;

end Consumer;

beachte Reihenfolge

• Erst Element schreiben, dann Signal(Element)
• Erst Element lesen, dann Signal(Spaces)

Schleifeninvariante

• Elements = #(noch nicht gelesene Elemente)
• Spaces = N - #(noch nicht gelesene Elemente)

Daraus folgt die Korrektheit

• Puffer kann nicht gelesen (geschrieben) werden, wenn er leer (voll) ist

• No deadlock

  Spaces = Elements = 0 N = 0 (aus Invariante).

• No starvation

  Klar: Einer verhungert der andere auch deadlock.

Hausaufgabe

producer

loop

Produce(D);

while((In_Ptr+1) mod N = Out_Ptr) loop

null;

end loop;

Buffer(In_Ptr) := D;

In_Ptr := (In_Ptr+1) mod N;

end loop;

consumer

loop

while(Out_Ptr = In_Ptr) loop

null;

end loop;

D := Buffer(Out_Ptr);

Out_Ptr := (Out_Ptr+1) mod N;

Consume(D);

end loop;

• Operationsaufruf auslassen.
• Operation (wait/signal) verwechselt.
• Operand (S) verwechselt.

Stattdessen: Zuständigkeit für Schutz- und Synchronisationsmaßnahmen wird dem Objekt übertragen, das von mehreren Prozessen benutzt wird, ohne Kopplung.

Schnittstelle

Zugriffsoperationen, kein Protokoll auf Prozeßseite

intern

Implementierung durch Operationen inklusive Synchronisation.

Eine solche Datenstruktur/Objekt heißt Monitor.

Monitore sind passiv, d.h. werden bei Aufruf ihrer Operationen tätig, sind nicht selbst Prozesse.

Beispiel: Producer-Consumer

Monitor Buffer is

procedure Insert(D: Data);

procedure Take(D: out Data);

end Buffer;






Monitor body Buffer is

N: Positive := ...;

B: array(0..N-1) of Data;

In_Ptr, Out_Ptr: natural := 0;

Count: Natural := 0; - Anzahl Elemente

Not_Full, Not_Empty: Condition; - Bedingungsvariablen






procedure Insert(D: Data) is

begin

if Count = N then

Wait(Not_Full);

end if;

B(In_Ptr) := D;

In_Ptr := (In_Ptr+1) mod N;

Count := Count+1;

Signal(Not_Empty);

end Insert;






procedure Take(D: out Data) is

begin

if Count = 0 then

Wait(Not_Empty);

end if;

D := B(Out_Ptr);

Out_Ptr := (Out_Ptr+1) mod N;

Count := Count-1;

Signal(Not_Full);

end Take;

end Buffer;

Gebrauch unit:

producer

D: Data;






begin

loop

Produce(D);

Insert(D);

end loop;

end;

consumer

D: Data;






begin

loop

Take(D);

Consume(D);

end loop;

end;

Semantik der Monitor-Konstruktion

• Jeweils nur 1 Monitor Operation in Ausführung, d.h. mutual exclusion.
• Operationen auf condition variables (C)

  Wait(C)

  Ausführender Prozeß wird suspendiert und in eine mit C assozierte FIFO-queue eingereiht; andere Prozesse jetzt zugelassen zur Operationsausführung.

  Signal(C)

  Falls die mit C assozierte FIFO-queue nicht leer ist, wird der erste der wartenden Prozesse aufgeweckt.

  Is_Empty(C)

  True gdw. Queue für C nicht leer (reine Abfrage!)

Interpretation von Signal

Sinnvolle Konvention: Signal letztes statement einer Prozedur und intern blockierte Prozesse haben Priorität über extern aufrufende!

Mehrere Festlegungen und Konventionen im Gebrauch! Wir verfolgen die Sache hier nicht weiter, sondern studieren (später) die Ada-Lösung!

Kritik an Monitoren