Verteilte und Parallele Programmierung

Synchronisation und Kommunikation

Nebenläufigkeit, Wettbewerb, und Synchronisation

• Konkurrierender Zugriff auf geteilte Ressourcen wie z. B. Speicher oder Kommunikationskanäle müssen synchronisiert werden, z. B. mit mutualen Ausschluss (Mutex) und zeitlicher Sequenzialisierung → Schutz kritischer Ausführungsbereiche

Nebenläufigkeit, Wettbewerb, und Synchronisation

• Zeitliche ereignisbasierte Synchronisation z.B. mit Semaphoren oder einfacher mit Events werden in Produzenten-Konsumenten Anwendungen benötigt, z.B.
  • Bei der Partitionierung und Verteilung von Eingabedaten auf mehrere Prozesse (Produzenten);
  • Der Annahme und Verarbeitung durch die einzelnen Prozesse (Konsumenten); sowie
  • Bei der Einsammlung von Ergebnis-/Ausgabedaten.

• Synchronisation ist Kommunikation und dient der Bewahrung von Invarianten der Datenverarbeitung (Datenkonsistenz)!

• Synchronisationsobjekte sind ebenfalls geteilte Ressourcen!!!!!

Der Mutuale Ausschluss: Ein Problem und seine Definition

Eigenschaften von Parallelen Systemen

Ein solches Wettbewerbsproblem ist gekennzeichnet durch die Eigenschaften Sicherheit und Lebendigkeit.

Sicherheit bedeutet: Bedingung Anzahl der Prozesse im kritischen Bereich K muss |{ p | I(p) ∈ K}| ≤ 1 immer erfüllt sein.

Eigenschaften von Parallelen Systemen

Eigenschaft (Liveness) Lebendigkeit → Starvation Freiheit

• Starvation Freiheit bedeutet dass ein Prozess p_i der die Ressource/den kritischen Bereich anfragt maximal eine endliche Anzahl von Zeiteinheiten / Wettbewerben n ≠ ∞ durch jeden anderen Prozess umgangen werden kann (Bypass, haben den Wettbewerb gewonnen).

Eigenschaft Deadlock Freiheit

• Wenn bis zu einem beliebigen Zeitpunkt t eine Reihe von Prozessen versucht haben den kritischen Bereich zu erlangen, ihn aber nicht erhalten haben, zu wird es in der Zukunft eine Zeit t' > t geben, wo sie erfolgreich sind (d.h. die Anfrage-Operation terminiert).

• D.h. eine Anfrage der Ressource terminiert mit einem gewonnen Wettbewerb garantiert irgendwann.

  • Starvation Freiheit impliziert Deadlock Freiheit!
  • Worst case eines Deadlocks: alle Prozesse verlieren den Wettbewerb, keiner kann die Ressource mehr nutzen/zugeteilt bekommen!

Eigenschaften von Parallelen Systemen

Eigenschaft Begrenztes (Bounded) Bypass Kriterium

• Es gibt eine Funktion f(N) für N Prozesse die die maximale Anzahl von verlorenen Wettbewerben (bei Konkurrenz) angibt.

Service gegen Klienten Sichtweise

Der Service ist die Ressource, der kritische Bereich. Der Klient ist der Prozess, der die Ressource anfragt.

• Aus Sicht des Service (Ressource) ist die Deadlock Freiheit wichtigstes Kriterium. Der konkurrierende Wettbewerb führt immer dazu, dass irgendein Prozess die Ressource nutzen kann → die Ressource gewinnt immer.

• Aus Sicht des Klienten (Prozesses) ist die Starvation Freiheit wichtigstes Kriterium. Wenn immer ein Prozess die Ressource anfragt, wird er sie (eventuell) zugeteilt bekommen → der Prozess gewinnt immer.

Eigenschaften von Parallelen Systemen

• Es gibt daher eine Hierarchie der Lebendigkeitseigenschaften (entsprechend ihrer Stärke):

1. Bounded Bypass f(N)=X ⇒

2. Starvation Freiheit ≡ Endlicher Bypass f(N) ≠ ∞ ⇒

3. Deadlock Freiheit

Deadlock

• Tritt häufig ein wenn zwei (oder mehrere) Prozesse gegenseitig eine Ressource (Lock) beanspruchen die aber jeweils vom anderen bereits belegt ist.
  • Prozesse, die bereits Sperren halten, fordern neue Sperren an.
  • Die Anforderungen für neue Sperren werden gleichzeitig gestellt.
  • Zwei oder mehr Prozesse bilden eine kreisförmige Kette, in der jeder Prozesse auf eine Sperre wartet, die vom nächsten Prozess in der Kette gehalten wird → Dining Philosopher Problem.

Eigenschaften von Parallelen Systemen

Lock und atomare Operationen

Mutualer Ausschluss mit LOCK Objekt

• Ein LOCK Objekt ist ein geteiltes Objekt dass sich in zwei verschiedenen Zuständen S_LOCK={FREE,LOCKED} befinden kann und eine Ressource schützt:

  State FREE

  Die Ressource ist nicht in Verwendung

  State LOCKED

  Die Ressource wird bereits von einem Prozess verwendet, andere Prozesse müssen warten

• Ein LOCK Objekt stellt Prozessen zwei Operationen zur Verfügung:

Operation ACQUIRE / LOCK

Ein Prozess kann eine Ressource anfordern. Ist der LOCK im Zustand S_LOCK=FREE, wird dem anfordernden Prozess die Ressource gewährt (Zustandsübergang S_LOCK: FREE ⇒ LOCKED), andernfalls wird er blockiert bis die Ressource (vom Eigentümer) freigegeben wird.

Lock und atomare Operationen

Operation RELEASE / UNLOCK

Ein Prozess gibt eine zuvor mit ACQUIRE beanspruchte Ressource wieder frei (Zustandsübergang S_LOCK: LOCKED ⇒ FREE).

Ein Prozess muss die Operation ACQUIRE und RELEASE immer paarweise verwenden!

Lock und atomare Operationen

• Beispiel der Nutzung eines LOCK Objekts für den Schutz von kritischen Bereichen beim Zugriff auf geteilte Ressourcen

OBJECT L: LOCK
VAR V
PAR
  PROCESS P1 IS                         PROCESS P2 IS
  WHILE (True)                          WHILE (True)
    non-critical section                  non-critical section
    L.ACQUIRE()                           L.ACQUIRE()
     critical section(V)                   critical section(V)
    L.RELEASE()                           L.RELEASE()
    non-critical section                  non-critical section
  DONE                                  DONE

• Das LOCK Objekt löst das mutuale Ausschlussproblem (mutual exclusion), und wird daher auch als Mutex bezeichnet.

• Mehr als zwei Prozesse können mit einem LOCK synchronisiert werden.

Lock und atomare Operationen

Synchronisation durch Blockierung

• Ereignisbasierte Synchronisation blockiert die Ausführung von Prozessen bis das Ereignis auf das gewartet wurde eingetreten ist.
  • Hier die Freigabe eines belegten LOCKs

Atomare Ressourcen: Register

• Ein Lese/Schreib Register ist die einfachste Form einer geteilten Ressource und wird für die Implementierung eine LOCK Objektes benötigt.

Lock und atomare Operationen

Besipielssituation

VAR GLOBAL SHARED: R          (VAR LOCAL NOTSHARED: x)
P1: VAR x     P2: VAR x       P3: VAR x
|x := ε(R)|   |R := ε(x)|     |R := ε(x)|

Eigenschaften eines atomaren Registers

Ein atomares geteiltes Register erfüllt dabei folgende Eigenschaften:

• Zugriffe (op=READ/WRITE) erscheinen als wären sie zu einem einzigen Zeitpunkt τ(op) ausgeführt worden.

• Der Zeitpunkt der Ausführung der Operation liegt garantiert innerhalb des Intervalls:
  τ(op_S) ≤ τ(op) ≤ τ(op_E), mit

  • S: Start und E: Ende der Operation (gemeint ist: Aktivierung durch Prozess)

• Für zwei verschiedene Operationen op₁ und op₂ gilt:
  τ(op₁) ≠ τ(op₂)

Lock und atomare Operationen

• Jede Lese-Operation gibt den Wert zurück der von der am nächsten (in der Vergangenheit) liegenden Schreibe-Operation resultiert.

Das bedeutet: ein atomares Register verhält sich so als ob die Ausführung aller Operationen sequenziell ausgeführt worden wäre.

Komposition mit atomaren Objekten

• Atomarität erlaubt die einfache Komposition von geteilten (atomaren) Objekten zu neuen geteilten und atomaren Objekten ohne zusätzlichen (Synchronisations-) Aufwand.

• D.h. wenn eine Menge von für sich atomaren Registern {R₁,R₂,..} mit den Operationen {R₁.READ,R₁.WRITE}, {R₂.READ,R₃.WRITE}, .. zu einem neuen Objekt (R₁,R₂,…) zusammengefasst (komponiert) werden, so ist dieses ebenfalls atomar.

Lock und atomare Operationen

Mutex

• Eine Mutex garantiert mittels eines LOCK Objekts den mutualen Ausschluss durch Erfüllung einer Invariante, d.h. einer logischen Bedingung die niemals verletzt werden darf.

• Angenommen eine Menge von Prozessen {P₁,P₂,..} wollen durch Mutualen Ausschluss sicher stellen dass immer nur ein Prozess sich im kritischen Bereich CS befindet (p_i=True). Dann gilt für die Invariante der Mutex:

• Das Prädikat Mutex muss eine globale Invariante sein, die mit atomaren Registern implementiert werden kann.

• Die Blockierung eines oder mehrere Prozesse beruht prinzipiell auf einer atomaren Schleife die auf das Eintreten einer booleschen Bedingung wartet, z.B. in der Form
  |await (cond) then (action)|

  • Die Anweisung blockiert den Prozess solange cond nicht wahr ist und dann unmittelbar (atomar) die Anweisung action ausführt (Datenzuweisung) → Test-and-set

Mutex

Protokolle

• Es muss in jedem Prozess der einen kritischen Bereich ausführen muss ein Eingangs- und Ausgangsprotokoll eingehalten werden damit der mutuale Ausschluss garantiert werden kann.
• Für die Implementierung dieses Protokolls soll gelten:

1. Mutualer Ausschluss und Einhaltung der LOCK Invariante (logische Bedingung): Höchstens ein Prozess zur Zeit führt seinen kritischen Abschnitt aus.
2. Keine Deadlocks und Livelocks: Wenn zwei oder mehr Prozesse versuchen, ihre kritischen Abschnitte zu betreten, wird mindestens einer erfolgreich sein.
3. Niedrige Latenz (niedrige Verzögerung): Wenn ein Prozess versucht, in seinen kritischen Abschnitt einzutreten, und die anderen Prozesse ihre nicht kritischen Abschnitte ausführen oder beendet haben, wird der erste Prozess nicht daran gehindert, in seinen kritischen Abschnitt einzutreten.
4. Garantierter Eintritt: Ein Prozess, der versucht, in seinen kritischen Abschnitt einzutreten, wird schließlich erfolgreich sein.

Mutex

Kritisches Abschnittsproblem: Grobe Lösung A.

bool in1 = false, in2 = false; 
## MUTEX: not(inl and in2) -- global invariant
process CSl { 
  while (true) {
    |await (!in2) then in1 = true|; /* entry */ 
    critical section 
    |in1 = false|;
    noncritical section
    /* exit */ 
  } 
}
process CS2 { 
  while (true) {
    |await (!in1) then in2 = true|; /* entry */ 
    critical section 
    |in2 = false|; 
    noncritical section
    /* exit */ 
  } 
}

Mutex

• Die Lösung A. garantiert den mutualen Ausschluss aber nicht die Lebendigkeit einzelner Prozesse.
  • Es können Wettlaufbedingungen eintreten (race conditions), wo immer nur einer oder einige wenige Prozesse den Wettbewerb gewinnen

• Ein fairer Scheduler ist erforderlich um Wettlaufbedingungen zu vermeiden!

Mutex

Kritisches Abschnittsproblem: Grobe Lösung B. mit Spin Locks

• Benötigt nur noch eine Variable → geringere Latenz!

bool lock = false; 
process CS1 { 
  while (true) {
    |await (!lock) then lock = true|;  /* entry */ 
    critical section 
    lock = false; 
    noncritical section;
    /* exit */ 
  } 
}
process CS2 { 
  while (true) {
    |await (!lock) then lock = true|; /* entry */ 
    critical section 
    lock = false; 
    noncritical section
    /* exit */ 
  } 
}

Mutex

• Da es nur zwei Zustände der Mutex gibt reicht eine Variable für die die Invariante gilt:

• Weiterer Vorteil der Spin-Lock Lösung: Sie kann für beliebige N>2 Prozesssysteme angewendet werden.

Test-and-set Operation

• Die atomare await-then Anweisung ist prinzipiell eine atomare Test-and-set (TS) Operation, wie sie von vielen Mikroprozessoren als eigenständiger Maschinenbefehl zur Verfügung gestellt wird.

bool TS (bool lock) {
  |bool initial = lock; 
   lock = true; 
   return initial| 
}

Mutex

• Die bedingten atomaren Aktionen werdend ann durch Schleifen ersetzt, die erst dann enden, wenn die Sperre falsch ist, und TS gibt daher false zurück.

• Da alle Prozesse dieselben Protokolle ausführen, funktioniert die gezeigte Lösung für eine beliebige Anzahl von Prozessen.

• Wenn eine Sperrvariable als ein Spin Lock verwendet wird, heisst das, dass die Prozesse während des Wartens auf das Löschen der Sperre eine Schleife durchlaufen (rotieren).

• Gegenseitiger Ausschluss ist sichergestellt:

  • Wenn zwei oder mehr Prozesse versuchen, in ihren kritischen Abschnitt einzutreten, wird nur einer erfolgreich sein, der erste zu sein, der den Wert von lock von falsch auf wahr ändert
  • Daher beendet nur einer sein Eintrittsprotokoll.

Mutex

• Die vorherigen Algorithmen können dann für N Prozesse mit einer TS Operation und einer bedingten Schleife implementiert werden, in der Art:

bool lock = false; 
process CS[i = 1 to n] {
  while (true) {
    while (TS(lock)) skip; 
    critical section 
    lock = false; 
    noncritical section
  } 
}

• Es wird keine atomare Schleife mehr benötigt!

• Aber auch hier ist der Eintritt (Lebendigkeit einzelner Prozesse) nicht garantiert. Warum?

• Weiterhin zeigt obiger Algorithmus bei Multiprozessorsystemen eine schlechte Performanz → Speicherzugriffe.

Mutex

Test-Test-and-Set Lösung

• Besser eine geschachtelte und verkettete Kombination aus Test und Test-and-Set:

boo1 lock = false;
process CS[i = 1 to n] { 
  while (true) {
    while (lock) skip; 
    while (TS(lock)) { while (lock) skip};
    critical section 
    lock = false; 
    noncritical section
  } 
}

• Diese Variante verbesserte den Speicherzugriff über die Cacheebene (probalistisch!)

Mutex

Faire Lösung mit dem Tie-Breaker Algorithmus

• Faires Scheduling durch “Fahrstuhlalgorithmus” und Iteration über mehrere (n-1) Ebenen [4]:

  int in[l:n] = ([n] 0), last[1:n] = ([n] 0); 
  process CS[i = 1 to n] {
  while (true) { 
    for [j = 1 to n] { /* entry protocol */
      /* remember process i is in stage j and is last */
      last[j] = i; in[i] = j; 
      for [k = 1 to n with i != k] {
        /* wait if process k is in higher numbered stage and 
           process i was the last to enter stage j */ 
        while (in[k] >= in[i] and last[j] == i) skip;
      } 
    }
    critical section 
    in[i] = 0;
    noncritical section
   }
  } 

Mutex

Peterson-Algorithmus für das LOCK Objekt und zwei Prozessen

• Algorithmus für die Operationen {ACQUIRE,RELEASE} des LOCK Objekts, der mutualen Ausschluss garantiert und Wettbewerb um eine geschützte Ressource ermöglicht.

• Der Peterson Algorithmus besteht aus zwei Komponenten, die unterschiedliche Eigenschaften des LOCK erfüllen.

• Erfüllung des mutualen Ausschlusses

OPERATION ACQUIREA(i) IS           OPERATION RELEASEA(i) IS 
  AFTER_YOU := i                     RETURN
  WAIT UNTIL AFTER_YOU /= i         END OPERATION
  RETURN
END OPERATION

Mutex

• Dieser Teil garantiert den mutualen Ausschluss und löst das Wettbewerbsproblem, d. h. maximal ein Prozess x von zwei Prozessen erlangt die Ressource und die Operation ACQUIRE(x) terminiert, der Operation ACQUIRE(y) des anderen Prozesses y terminiert nicht.

• Nachteil: Rendezvous ist erforderlich. Beide Prozesse müssen die Ressource anfordern, d.h. ein einzelner Prozess verliert seinen eigenen Wettbewerb immer.

• Erfüllung des Lebendigkeitskriteriums

OPERATION ACQUIREB(i) IS           OPERATION RELEASEB(i) IS
  FLAG[i] := UP                      FLAG[i] := DOWN
  WAIT UNTIL FLAG[j] = DOWN        END OPERATION
  RETURN
END OPERATION

• Dieser Teil löst das Problem, wenn nur ein Prozess zu gleichen Zeit an der Ressource interessiert ist, und die ACQUIRE(i) Operation terminieren kann.

Mutex

• Nachteil: Deadlock wenn beide Prozesse gleichzeitig ACQUIRE Operation durchführen. (beide setzen gleichzeitig ihr FLAG auf UP).

• Zusammenführung beider Teilalgorithmen 1. und 2. führt zum Peterson Algorithmus für die Implementierung der Operationen eines LOCK Objekts (Zwei Prozesse i und j).

OBJECT LOCK IS
REG FLAG[2],AFTER_YOU
OPERATION ACQUIRE(i) IS           OPERATION RELEASE(i) IS
  FLAG[i] := UP                     FLAG[i] := DOWN
  AFTER_YOU := i                    RETURN
  WAIT UNTIL FLAG[j] = DOWN OR    END OPERATION
       AFTER_YOU != i
  RETURN
END OPERATION

Mutex

• FLAG zeigt das Interesse an einer Ressource an mit Wertemenge {DOWN, UP}.

• AFTER_YOU besitzt die Wertemenge {1,2} und bezeichnet die Prozessnummer.

• FLAG und AFTER_YOU sind atomare Register (Single Write Multiple Read Verhalten).

• Dieser Algorithmus erfüllt

  • Mutuale Exklusion (max. ein Prozess erhält die Ressource)
  • Bounded Bypass (ein Prozess gewinnt den Wettbewerb) mit f(n)=1

Mutex

Mutual Exklusion Eigenschaft (I)

• Der erste Prozess (i) führt FLAG[i] := UP und AFTER_YOU := *i aus
• Der erste Prozess (i) terminiert durch FLAG[j]=DOWN
• Der zweite Prozess (j) führt FLAG[j] := UP und AFTER_YOU := j aus
• Der zweite Prozess (j) wartet

Mutex

Mutual Exklusion Eigenschaft (II)

• Der erste Prozess (i) führt FLAG[i] := UP und AFTER_YOU := i aus
• Der zweite Prozess (j) führt FLAG[j] := UP und AFTER_YOU := j aus
• Der erste Prozess (i) terminiert durch AFTER_YOU = j
• Der zweite Prozess (j) wartet

Mutex

Bounded Bypass

• Ein Prozess (j) besitzt die Ressource (FLAG[j] := UP)
• Der andere Prozess (i) führt FLAG[i] := UP und AFTER_YOU := i aus
• Eine zeit lang liest Prozess (i) FLAG[j] nicht.
• Während dessen gibt Prozess (j) die Ressource frei und führt FLAG[j] := DOWN aus.
• Danach beantragt Prozess (j) die Ressource erneut, und führt FLAG[j] := UP und AFTER_YOU := j aus.
• Der Prozess (i) liest AFTER_YOU=j und terminiert, Prozess (j) liest FLAG[i] = UP und wartet, d.h. f(n)=1 !

Mutex

Peterson Algorithmus für N Prozesse

OBJECT LOCK IS
REG FLAG_LEVEL[N],AFTER_YOU[N]
OPERATION ACQUIRE(i) IS           OPERATION RELEASE(i) IS
  FOR l = 1 TO (N-1) DO
    FLAG_LEVEL[i] := l              FLAG_LEVEL[i] := 0
    AFTER_YOU[l] := i               RETURN
    WAIT (∀ k != i: 
       FLAG_LEVEL[k] < l) OR    
       AFTER_YOU[l] != i
  RETURN
END OPERATION                     END OPERATION

• Der N=2 Peterson Algorithmus erfüllt Deadlock Freiheit und starken Bounded Bypass!
• Aber der N>2 Algorithmus erfüllt nur Deadlock Freiheit und schwachen Finite Bypass!

Mutex

Tournament tree

• Ein einfaches Prinzip, um die Anzahl der Shared Memory-Zugriffe zu reduzieren, ist die Verwendung eines Turnierbaumes. Ein solcher Baum ist ein vollständiger Binärbaum.

Semaphore

Eigenschaften

• Ein Semaphore Objekt S ist ein LOCK basiertes Synchronisationsobjekt und ein geteilter Zähler mit Warteschlange S.counter, das folgende Eigenschaften erfüllt:

  • Die Bedingung S.counter ≥ 0 ist immer erfüllt.

  • Der Semaphorenzähler wird mit einem nicht-negativen Wert s₀ initialisiert.

  • Es gibt zwei wesentliche Operationen {S.DOWN, S.UP} um den konkurrierenden und synchronisierenden Zugriff auf eine Semaphore zu ermöglichen.

  • Wenn #(S.DOWN) und #(S.UP) die Anzahl der Operationsaufrufe ist, die terminiert sind, so gilt die Invariante:

Semaphore

Operationale Semantik

Operation WAIT/DOWN

S.DOWN erniedrigt den Zähler S.counter atomar um den Wert 1 sofern S.counter > 0.

Wenn S.counter=1 und mehrere Prozesse versuchen gleichzeitig die DOWN Operation anzuwenden, so wird einer den Wettbewerb gewinnen (Mutualer Ausschluss = LOCK). Wenn S.counter = 0 dann werden Prozesse blockiert und in einer Warteschlange S.Q eingereiht.

Operation SIGNAL/UP

S.UP erhöht den Zähler S.counter atomar um den Wert 1. Diese Operation kann immer ausgeführt werden, und blockiert nicht die Ausführung des aufrufenden Prozesses.

Wenn S.counter = 0 ist und es blockierte Prozesse gibt, wird einer aus S.Q ausgewählt und freigegeben (d. h. der Zähler ändert sich effektiv nicht).

Semaphore

Eine Semaphore mit s₀=1 ist eine binäre Semaphore vergleichbar mit einer Mutex! Eine Semaphore ist stark wenn die blockierten (wartenden) Prozesse in der Reihenfolge wieder freigegeben werden in der sie blockiert wurden (First In First Out / FIFO Ordnung).

Algorithmus

OBJECT SEMAPHORE(init) IS
  VAR counter:INT
  OBJECT Q:QUEUE, L:LOCK
  OPERATION down(i) IS
    L.lock()
    IF counter = 0 THEN
      Q := Q + {i}
      |L.unlock(),BLOCK(i)|
    ELSE
      counter := counter - 1
      L.unlock()
    END IF
    RETURN 
  END OPERATION

OPERATION up(i) IS 
  L.lock()
  IF counter = 0 THEN
    IF Q = {} THEN
      counter := counter + 1
    ELSE 
      j := Head(Q), Q := Tail(Q)
      UNBLOCK(j) 
    END IF
  ELSE counter := counter + 1
  END IF
  L.unlock()
  RETURN 
END OPERATION

Semaphore

Implementierung mit Channels

• Verwendung von voll synchronisierten Channels (Rendezvous):
  • Vom Teilnehmer- zum Semaphoreprozess ein Request Channel ch^r
  • Vom Semaphore- zum Teilnehmerprozess ein Ack. Channel ch^g
  • Semaphoreprozess benutzt Alt Operator für alle Request Channels

Semaphore - Produzenten-Konsumenten Systeme

• Semaphoren können eingesetzt werden um konkurrierende Produzenten-Konsumenten Probleme zu lösen. Beispiel ist ein Pufferspeicher mit First-In First-Out Reihenfolge, der eine endliche Anzahl von Speicherzellen eines geschützten Speichers Buf[0..k-1] mit k=size besitzt, und die beiden Zustände S={FREE, FULL} annehmen kann.
  • Schutz des Speichers bedeutet: gleichzeitiger Zugriff zweier Prozesse auf gleiche Speicherzelle Buf[x] muss verhindert werden.
  • Schutz durch zwei Semaphoren FREE(k) und BUSY(0).

Implementierung eines Pufferspeichers mit Semaphoren

OBJECT BUFFER (size) IS
  VAR BUF: datatype[size], in,out: INT
  OBJECT FREE: SEMA(size),
         BUSY:SEMA(0)
  OPEARTION produce(v) IS
    FREE.down()
    BUF[in].write(v) 
    in := (in+1) mod size
    BUSY.up()
  END OPERATION

  OPERATION consume IS
    BUSY.down()
    r := BUF[out].read()
    out := (out+1) mod size
    FREE.up()
    RETURN r
  END OPERATION
END OBJECT

Semaphore - Produzenten-Konsumenten Systeme

Semaphore - Dining Philosophers

• Das Problem der fünf dinierenden Philosophen ist ein Beispiel für Deadlocks in verteilten und parallelen (asynchronen) Systemen mit dem Communicating Sequential Processes Modell!

Semaphore - Dining Philosophers

Algorithmus

OBJECT ARRAY Forks [N]: SEMA(1)
PROCESS ARRAY Philosopher [N]
  FOR try = 1 TO 10 DO
    THINKING ...
    Forks[#id].down()
    Forks[#id+1 % N].down()
    EATING ...
    Forks[#id+1 % N].up()
    Forks[#id].up()
  DONE
END 

Semaphore - Dining Philosophers

• Klassisches Problems das zu Deadlocks führt!

Deadlockefreie Lösungen

1. Einführung einer zentralen Instanz die die Gabeln mittels Prioritäswarteschlangen verwaltet
   • Prozess fragt mit einer Nachricht zwei Gabeln an (Input Channel)
   • Verwalter prüft Verfügbarkeit und gewährt die Gabeln durch eine Antwortnachricht (Output Channel)
   • Ein Prozess gibt Gabeln mit einer Nachricht wieder zurück

2. Abfrage des Semaphorenwertes beider Gabeln bevor die Ressource angefragt wird ggf. über eine globale Mutex geschützt:

sema[left]:down();
if sema[right]:level() == 1 then sema[right]:down()
else sema[left]:up(); sleep(random time) end

3. Münzwurf und Reihenfolge des Zugriffs: Eine Zufallszahl zwischen 0..1 entscheidet ob zuerst die linke und dann rechte Gabel beansprucht wird oder umgekehrt.

Monitor

• Mutex und Semaphore sind low-level Synchronisationsobjekte

• Monitore erlauben die Definition von konkurrierenden Objekten auf der Abstraktionsebene der imperativen Programmiersprachen → high-level.

• Ein Monitor ist eine Generalisierung eines Objekts, welches Daten und Operationen kapselt. Zugriff auf die interne Repräsentation erfolgt durch die Operationen mutual exklusiv.

Monitor

Konzepte

Mutualer Ausschluss

Der Monitor stellt sicher dass immer nur ein Prozess eine Operation des Objektes ausführen kann à geschützter kritischer Ausführungsbereich = mutualer Ausschluss.

Ein Prozess muss das Schloss des Monitors öffnen. Nachdem der Prozess den Monitor “betritt” (nutzt), schließt das Schloss automatisch wieder. Wenn der Prozess den Monitor verlässt wird das Schloss wieder automatisch geöffnet.

Events: Bedingungsvariablen mit Queues

• Bedingungsvariablen C sind Objekte die interne Synchronisation ermöglichen sollen.

• Bedingungsvariablen können nur innerhalb des Monitors durch folgende Operationen verwendet werden:

Monitor

Operation C.wait(cond)

Diese Operation blockiert = stoppt den aufrufenden Prozess p und reiht ihn in die Warteschlange C.Q ← C.Q + {p} ein. Für den Prozess der nicht mehr aktiv ist, kann der Mutex LOCK aufgehoben werden.

• Die Wait Operation stellte eine boolesche Bedingung cond dar auf deren Erfüllung gewartet wird.

Operation C.signal()

Ein Prozess p ruft diese Operation auf und erfüllt damit die Bedingung cond.

• Wenn C.Q = ∅ ist dann hat die Operationen keinen Effekt
• Wenn C.Q = {q,…} dann wird ein Prozess q aus Q ausgewählt und aktiviert, so dass C.Q ← C.Q \ {q}

Bewahrung des mutualen Ausschlusses in Fall ii.) erforderlich:

• Der aktivierte Prozess q fährt innerhalb des Monitors fort (bekommt den Eintritt wieder) und führt die Anweisungen nach C.wait() aus.

Monitor

• Der aktivierende Prozess p wird blockiert, hat aber höchste Priorität den Monitor danach wieder zu erlangen um die Anweisungen nach C.signal() auszuführen.

Operation C.empty()

Liefert das Ergebnis für die Bedingung C.Q = ∅

• Algorithmik der Bedingungsvariablen (vereinfacht)

  OBJECT CONDITION 
  (M:MONITOR) IS
  OBJECT q: QUEUE               OPERATION signal IS
     p: PROCESS               IF q != {} THEN
  OPERATION wait IS                 p := Head(q), q := Tail(q)
    p := MYSELF()                   UNBLOCK(p)
    q := q + {p}                  END IF    
    |BLOCK(p) & M.l.unlock()|   END OPERATION      
  END OPERATION                   

Monitor

• Implementierung einer Semaphore mit Bedingungsvariablen (vereinfacht)

  MONITOR SEM IS
  VAR s:INT
  OBJECT c: CONDITION
  OPERATION down IS         OPERATION up IS
    IF s=0 THEN c.wait()      s := s + 1
      s := s - 1              c.signal();
    RETURN                    RETURN
  END OPERATION             END OPERATION

• Um den mutualen Ausschluss zu garantieren muss Vorrang der Prozessausführung und Aktionen mit Bedingungsvariablen definiert werden.
  • Wartende bereite Prozesse (Menge 𝕎) deren Bedingung cond erfüllt ist.
  • Signalisierende Prozesse (Menge 𝕊)
  • Prozesse die noch keinen Eintritt in den Monitor erhalten haben (blockiert, Menge 𝔼)
  • Prioritäten: Prio(𝕎) > Prio(𝕊) > Prio(𝔼)

Monitor

Ein signalisierter (blockierter) Prozess der auf eine Bedingung C wartet wird sofort aktiviert (d. h. die Bedingung ist erfüllt).

Monitor

• Würde nach Aktivierung des wartenden Prozesses (cond=TRUE) auch der signalisierende Prozess im Monitor aktiv sein könnte er die Bedingung, die der Bedingungsvariablen zu Grunde liegt, wieder ungültig (cond=FALSE) machen und müsste ebenfalls wieder blockiert werden.

• Es gilt daher für den Monitor die Erfüllung eines Prädikats P (boolesche Bedingung), das die Datenkonsistenz des Objektes sicher stellen muss.

Varianten

signal-and-wait

Der signalisierende Prozess wartet nach der Signalisierung und der mutuale Ausschluss ist sichergestellt und die Wahrung P=TRUE. Der wartende Prozess führt aus:

IF ¬P THEN C.wait() END IF

signal-and-continue (re-check)

Der signalisierende Prozess läuft weiter! Das könnte zur Verletzung des Prädikats P führen, daher muss der signalisierte Prozess nochmals die Gültigkeit P=TRUE prüfen so dass für ihn auszuführen ist:

WHILE ¬P DO C.wait () END WHILE

Event

• Mit signal-and-continue Monitoren und Bedingungsvariablen lassen sich einfache temporale ereignisbasierte Synchronisationsobjekte implementieren.

• Mehrere Prozess p₁,p₂,…,p_N-1 können auf ein Event warten (OP E.await). Eine geordnete Warteschlange ist nicht erforderlich.

• Dieses Event wird durch einen weiteren Prozess p_N ausgelöst (OP E.wakeup), so dass alle blockierten inklusive des signalisierenden Prozesse in der Ausführung fortfahren (auch zeitgleich).

Operationen

OPERATION await

Ein Prozess p wird blockiert bis das Ereignis (event) eintritt

OPERATION wakeup

Die Operation aktiviert alle auf das Ereignis wartenden Prozesse {p_i}.

Event

• Algorithmik des Event Objekts

  MONITOR EVENT IS
  OBJECT c: CONDITION
  OPERATION await IS    OPERATION wakeup
    c.wait()              c.signal();
    RETURN                RETURN
  END OPERATION         END OPERATION

Beispiel in Lua

local ev  = Event();
local mem = Buffer(16000);
 
ProcessArray(function () {
  local sum=0;
  waitForData:await();
  for i=1,data.size do sum = sum + data:read(i) end
  print(sum);
},N,{waitForData = ev, data=mem, N=N})
for  i=1,mem.size do mem.write(m.random(1,256),i) end
ev:wakeup();

Barriere

• Eine Barriere ist ein Rendezvous Objekt, oder auch ein selbst-auslösendes Event. Es gibt eine (vorher) bekannte Gruppe aus N Prozessen {p₁,p₂,…,p_N}
• Jeder beliebige Prozess i=1..N-1 nimmt an der Barriere durch die B.await Operation teil und wird blockiert.
• Der letzte (beliebige) Prozess p_N ruft ebenfalls die Barriere mit der B.await Operation auf, wird jedoch nicht blockiert und aktiviert dabei die wartenden Prozesse.
• Alle Prozesse haben damit einen gemeinsamen Kontrollpunkt passiert.

Operationen

OPERATION await

Der aufrufende Prozess p wird blockiert wenn #blocked(B) < N, ansonsten fährt er in der Ausführung weiter und aktiviert alle blockierten Prozesse.

OPERATION init(N:numebr)

Setzt die Größe der Barrierengruppe (Anzahl der Prozesse N)

Barriere

• Algorithmik der Barriere mit Monitor

  MONITOR BARRIER (N) IS
  VAR counter: {0,1,..,N} := 0
  OBJECT q: condition
  OPERATION await IS
    counter := counter + 1
    IF counter < N THEN q.await()
    ELSE counter := 0 
    q.signal() END IF
    RETURN
  END OPERATION

Timer

• Timer sind temporal selbstsynchronisierende Events.
• Anstelle eines Auslöseprozesses führt der Timer nach Ablauf eines Zeitintervalls die wakeup Operation aus.

Operationen

OPERATION await

Der aufrufende Prozess p wird blockiert bis der Timer ein wakeup ausführt.

OPERATION init(timeout:number,once:boolean)

Setzt das Timerintervall und ein Flag ob der Timer einmalig oder periodisch arbeitet

OPERATION start

Startet den Timer

Channel

• Anders als bei den vorherigen Synchronisationsobjekten dienen Kanäle und Warteschlangen der synchronisierten Nachrichtenübertragung zwischen Prozessen: Daten + Synchronisation

• Kanäle werden auch häufig in der verteilten Programmierung eingesetzt.

• Kanäle sind daher Semaphoren (Produzenten-Konsumenten System!) mit Daten

• Ein Kanal kann multidimensional sein (tupelbasiert)

Operationen

OPERATION read(x₁,x₂,..) / receive(x₁,x₂,..)

Lesen eines Datenwertes oder Datensatzes und Übertragung der gelesenen Werte an die Variablenargumente (call-by-reference). Bedingung: Wenn der Kanal leer ist wird der lesende Prozess solange blockiert und in eine Prozesswarteschlange eingereiht bis ein schreibender Prozess teilnimmt.

Channel

OPERATION write(ε₁,ε₂,..) / send(ε₁,ε₂,..)

Schreiben eines Datenwertes oder Datensatzes. Bedingung: Wenn der Kanal voll ist wird der schreibende Prozess solange blockiert und in eine Prozesswarteschlange eingereiht bis ein lesender Prozess teilnimmt.

OPERATION empty

Testet den Kanal ob er leer ist (keine Daten enthält)