PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Verteilte und Parallele Programmierung

Mit Virtuellen Maschinen

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Synchronisation und Prozesskommunikation

Wie können parallele und nebenläufige Prozesse synchronisiert werden?

Wie wird Datenkonsistenz in parallelen Programmen gewährleistet?

Synchronisationsobjekte: Mutex, Semaphore, Event, Barrier, Timer, Channel, Monitor

Gruppenkommunikation

2 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Prozesskommunikation

  • Start und Terminierung von Prozessen kann durch die Prozesse selbst, den Prozesskonstruktoren oder explizit durch Synchronisationsobjekte erfolgen

  • Aber auch zwischen Start und Terminierung eines Prozesses ist es häufig erforderlich den inneren Prozessfluss von einer Gruppe von Prozessen zu synchronisieren, d.h. an bestimmten Punkten (Milestones) den Kontrollfluss abgleichen.

3 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Synchronisationsklassen

  1. Bei geteilten Resourcen und konkurrierenden Zugriff

    • Gegenseitiger Ausshluß und Schutz von kritischen Programmbereichen (Lock)
  2. Kooperation

    • Verteilung und Zusammenführung von Prozessen und Daten
  3. Koordination

    • Reihenfolge, Abläufe, Aufgabenverteilung
4 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Invarianten

Synchronisationsobjekte müssen bestimmte Bedingungen erfüllen, damit Konsistenz, Sicherheit und Lebendigkeit in parellelen Prozessystemen jederzeit gewährleistet sind!

  • Eine Invariante ist häufig eine Boolescher oder relationer Ausdruck der sowohl Parameter des Objekts als auch die Prozessinteraktion berücksichtigt
5 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Lock und atomare Operationen

Mutualer Ausschluss mit Lock Objekt

  • Ein LOCK Objekt ist ein geteiltes Objekt dass sich in zwei verschiedenen Zuständen σ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
6 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Lock und atomare Operationen

  • Ein LOCK Objekt stellt Prozessen zwei Operationen zur Verfügung:
Operation acquire (lock)
Ein Prozess kann eine Ressource anfordern. Ist der Lock im Zustand σLock=FREE, wird dem anfordernden Prozess die Ressource gewährt (Zustandsübergang σLock: FREELOCKED), andernfalls wird er blockiert bis die Ressource (vom Eigentümer) freigegeben wird.
7 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

Lock und atomare Operationen

Operation release (unlock)
Ein Prozess gibt eine zuvor mit acquire beanspruchte Ressource wieder frei (Zustandsübergang σLock: LOCKEDFREE).

Ein Prozess muss die Operationen acquire und release immer paarweise verwenden!

Zustandsübergangsdiagramm des Lock Objekts

8 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

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.

9 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

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 Lock Objekts

Atomare Ressourcen: Register

  • Ein Schreib-Lese Register ist die einfachste Form einer geteilten Ressource und wird für die Implementierung eine Lock Objektes benötigt.
    • Aber: Operationen auf dieses Register müssen atomar und konfliktfrei sein, d.h., sequenzialisierbar sein!
10 / 59

PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation

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!

Atomares Register

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.
11 / 59