PD Stefan Bosse
Universität Bremen, FB Mathematik & Informatik
SS 2020
Version 2020-07-01 sbosse@uni-bremen.de |
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.
Synchronisation ist Kommunikation und dient der Bewahrung von Invarianten der Datenverarbeitung (Datenkonsistenz)!
Synchronisationsobjekte sind ebenfalls geteilte Ressourcen!!!!!
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).
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.
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.
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.
1. Bounded Bypass f(N)=X ⇒
2. Starvation Freiheit ≡ Endlicher Bypass f(N) ≠ ∞ ⇒
3. Deadlock Freiheit
Ein LOCK Objekt ist ein geteiltes Objekt dass sich in zwei verschiedenen Zuständen SLOCK={FREE,LOCKED} befinden kann und eine Ressource schützt:
Ein LOCK Objekt stellt Prozessen zwei Operationen zur Verfügung:
Ein Prozess muss die Operation ACQUIRE und RELEASE immer paarweise verwenden!
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.
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!
VAR GLOBAL SHARED: R (VAR LOCAL NOTSHARED: x)
P1: VAR x P2: VAR x P3: VAR x
|x := ε(R)| |R := ε(x)| |R := ε(x)|
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
Für zwei verschiedene Operationen op1 und op2 gilt:
τ(op1) ≠ τ(op2)
Das bedeutet: ein atomares Register verhält sich so als ob die Ausführung aller Operationen sequenziell ausgeführt worden wäre.
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.