PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Mit Virtuellen Maschinen
PD Stefan Bosse
Universität Bremen - FB Mathematik und Informatik
PD Stefan Bosse - VPP - Modul H: 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
PD Stefan Bosse - VPP - Modul H: Synchronisation und 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.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Bei geteilten Resourcen und konkurrierenden Zugriff
Kooperation
Koordination
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Synchronisationsobjekte müssen bestimmte Bedingungen erfüllen, damit Konsistenz, Sicherheit und Lebendigkeit in parellelen Prozessystemen jederzeit gewährleistet sind!
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Ein Prozess muss die Operationen acquire und release immer paarweise verwenden!
Zustandsübergangsdiagramm des Lock Objekts
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
OBJECT L: LOCKVAR VPAR 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.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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
Ein atomares geteiltes Register erfüllt dabei folgende Eigenschaften:
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Der Zeitpunkt der Ausführung der Operation liegt garantiert innerhalb des Intervalls:
Für zwei verschiedene Operationen op1 und op2 gilt:
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Das bedeutet: ein atomares Register verhält sich so als ob die Ausführung aller Operationen sequenziell ausgeführt worden wäre.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Beispiel von konkurrierenden und zeitlich überlappenden Schreib/Lese Zugriffen auf ein atomares Register
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Eine Mutex ist das einfachste aber wichtigste Synchronisationsobjekt für parallele Systeme. Es dient der Datenkonsistenz durch Schutz von krtischen nicht atomaren Ausführungsbereichen.
Das Objekt bietet mindest zwei Operationen:
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
local mu = Mutex()Par({ function () .. mu:lock() .. mu:unlock() .. end, function () .. mu:lock() .. mu:unlock() .. end, function () .. mu:lock() .. mu:unlock() .. end, ... }, { mu = mu})
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
local mu = Mutex()local x = Register:new('float');Par({ function () mu:lock(); x:write(x:read() + 1); mu:unlock() end, function () mu:lock(); x:write(x:read() - 1); mu:unlock() end,}, { mu = mu, x = x}) print(x:read())
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Zu jedem Zeitpunkt t darf maximal ein Prozess den Lock besitzen. Weitere Anfragen des Locks müssen garantiert abgewiesen werden. Nur ein Prozess darf maximal den Wettbewerb gewinnen.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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 s0 initialisiert.
Es gibt zwei wesentliche Operationen {S.down, S.up}
um den konkurrierenden und synchronisierenden Zugriff auf eine Semaphore zu ermöglichen.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
S.counter=s0+∑(S.up)−∑(S.down)
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Eine Semaphore mit s0=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).
local sem = @Semaphore(init)Par({ function () P:down() .. C:up()end, function () P:down() .. C:up()end, function () loop(2) P:up() .. loop(2) C:down() end},{ P = Semaphore(0), C =Semaphore(0) })
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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).
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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 OPERATIONEND OBJECT
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Synchronisation von Produzenten und Konsumenten von Daten mittels zweier Semaphoren
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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() DONEEND
Dinining Philosophers Template
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
sema[left]:down();if sema[right]:level() == 1 then sema[right]:down()else sema[left]:up(); sleep(random time) end
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Es gibt zwei Operationen:
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
local ev = Event()Par({ function () ev:await() .. end, function () ev:await() .. end, function () ev:wakeup() .. end},{ ev:ev })
Wenn das Signal vor dem Erwarten ausgelöst wird ist das Signal verloren und wartende Prozesse werden nicht frei gegeben!
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
local ba = Barrier(groupsize)Par({ function () ba:await() .. end, function () ba:await() .. end, function () ba:await() .. end},{ ba:Barrier(3) })
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
local t = Timer(interval, once, fiber?)Par({ function () loop t:await() .. end function () loop t:await() .. end function () t:start() .. end},{t:Timer(1000,false)}}
Lua CSP Timer
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Ein Kanal ist ein synchronisierter Pufferspeicher mit First-In First-Out Reihenfolge und wird in Produzenten-Konsumenten Systemen eingesetzt.
Operationen und Verhalten
Ist die Puffergröße Null, dann Rendezvous Handshake!
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
local ch = Channel(size,fiber?)Par({ function () local v = ch:read() .. end, function () ch:write(ε) .. end},{ch=ch})
Lua CSP Channels
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Die Arbeit mit Channels kann bedeuten dass ein Prozess aus mehreren Channels gleichzeitig Daten lesen muss, aber aufrgund des synchronen Verhaltens nicht alle Channel einer Gruppe Ch={chi} abfragen kann.
Ein Lösung bietet der Alt(ernative) Prozesskonstruktur der es ermöglich auf das Eintreten mehrerer Ereignisse (hier die Verfügbarkeit von Daten in Channels) zu warten und eines auszuwählen.
Der Alt Prozess garantiert Mutual Exclusion Verhalten, d.h.:
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
ch1 = Channel()ch2 = Channel() ... local x Alt({ function () x=ch1:read(); <optional handler code> end, function () x=ch2:read(); <optional handler code> end, .. }) <process x>
Lua CSP Auswahlprozesskonstruktor. Es wird immer nur einer der Alt Prozesse aktiviert wenn die blockierende Anweisung (read) bereit wird
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Objektmonitor mit automatischen Schutz (Datenkonsistenz des Objekts)
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Bedingungsvariablen C sind Objekte die interne Synchronisation ermöglichen sollen.
Bedingungsvariablen können nur innerhalb des Monitors durch folgende Operationen verwendet werden:
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Bewahrung des mutualen Ausschlusses in Fall ii.) erforderlich:
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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
Semaphore mit Bedingungsvariablen
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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(𝔼)
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Ein signalisierter (blockierter) Prozess der auf eine Bedingung C wartet wird sofort aktiviert (d. h. die Bedingung ist erfüllt).
Verschiedene Prozessmengen bei Monitoren
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
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.
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
local S = class()function S:init (i) self.counter=i; self.L=Mutex()endfunction S:up () self.counter=self.counter+1endfunction S:down () self.counter=self.counter+1endfunction S:__index (index) local value = rawget( self, index ) if value == nil then return function (...) rawget( self, 'L' ):lock(); -- LOCK rawget(getmetatable(self), index)(...) -- CALL PROT rawget( self, 'L' ):unlock() -- UNLOCK end else return value endend
Beispiel für einen einfachen und naiven geschützten Monitor in Lua. Wo könnte es Probleme geben?
PD Stefan Bosse - VPP - Modul H: Synchronisation und Prozesskommunikation
Es gibt verschiedene Synchronisations- und Kommunikationsobjekete für Prozesssysteme (parallel wie sequenziel) ⇒ Interprozesskommunikation
Häufige Objekte: Mutex, Semaphore, Event, Barriere, Timer, Channel, Monitor
Diese Objekte müssen Invarianten erfüllen die zu keinem Zeitpunkt verletzt werden dürfen (d.h. ungültig werden)