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