Verteilte und Parallele Programmierung

PD Stefan Bosse
Universität Bremen, FB Mathematik & Informatik
SS 2020
Version 2020-07-01

Synchronisation und Kommunikation


Nebenläufigkeit, Wettbewerb, und Synchronisation

Definition 1.
Nebenläufigkeit mit Konkurrenz. Operationen in verschiedenen Prozessen eines Programms konkurrieren z. B. um gemeinsame Ressourcen Wettbewerb. Konkurrenz bedeutet optionale Parallelität und kann auch sequenziell ausgeführt werden!

Definition 2.
Parallelität. Parallele Ausführung auf Verarbeitungs- und Systemebene mit zeitlicher Überschneidung von Ereignissen und Operationen ohne zwangsläufig mit Wettbewerb.

  • 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

Definition 3.
Kritischer Bereich. Sequenzielle Ausführung einer Anweisungssequenz K={I1,I2,..} in einem parallelen Programm darf nur von einem einzigen Prozess zur gleichen Zeit ausgeführt werden. Ein kritischer Bereich K ist daher eine geschützte Ressource.

Definition 4.
Mutualer Ausschluss. Es muss einen Algorithmus geben der sicher stellt dass immer und maximal nur ein Prozess pi aus einer Menge von Prozessen P={p1,p2,..} den kritischen Bereich K ausführen darf (die Ressource zugeteilt bekommt).

Eigenschaften von Parallelen Systemen

Definition 5.
Wettbewerb. Konkurrieren mehrere Prozesse um die Ressource K, so gewinnt maximal einer, die anderen verlieren den Wettbewerb.

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 pi 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

figdeadlock


Abb. 1. Deadlocksituation zweier Prozesse die wechselseitig gesperrte Ressourcen anfordern

Lock und atomare Operationen

Mutualer Ausschluss mit LOCK Objekt

  • Ein LOCK Objekt ist ein geteiltes Objekt dass sich in zwei verschiedenen Zuständen SLOCK={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 SLOCK=FREE, wird dem anfordernden Prozess die Ressource gewährt (Zustandsübergang SLOCK: 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 SLOCK: LOCKED FREE).

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

figlockstatedia


Abb. 2. Zustandsdiagramm des LOCK Objekts

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.

Definition 6.
Atomares Register. Der Zugriff auf ein atomares Register R erfolgt mittels zweier Operationen OP={READ,WRITE}: R.READ(), welches den aktuellen Wert von R zurück liefert, und R.WRITE(v), welche einen neuen Wert in das Register schreibt. Dabei ist ein Konflikt durch konkurrierende Schreib- und Lesezugriffe von einer Menge von Prozessen durch mutualen Ausschluss aufgelöst!

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:
    τ(opS) τ(op) τ(opE), mit

    • S: Start und E: Ende der Operation (gemeint ist: Aktivierung durch Prozess)
  • Für zwei verschiedene Operationen op1 und op2 gilt:
    τ(op1) τ(op2)

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 {R1,R2,..} mit den Operationen {R1.READ,R1.WRITE}, {R2.READ,R3.WRITE}, .. zu einem neuen Objekt (R1,R2,) zusammengefasst (komponiert) werden, so ist dieses ebenfalls atomar.

Lock und atomare Operationen