PD Stefan Bosse - VPP - 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

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: 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.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Synchronisationsklassen

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

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Synchronisationsklassen

Synchronisationsklassen

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Invarianten

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

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

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

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

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: FREE ⇒ LOCKED), andernfalls wird er blockiert bis die Ressource (vom Eigentümer) freigegeben wird.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

Lock und atomare Operationen

Operation release (unlock)

Ein Prozess gibt eine zuvor mit acquire beanspruchte Ressource wieder frei (Zustandsübergang σ_Lock: LOCKED ⇒ FREE).

Zustandsübergangsdiagramm des Lock Objekts

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

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.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

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!

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

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.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

• 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₂)

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

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.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen

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.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Lock und atomare Operationen { - }

Lock und atomare Operationen { - }

Beispiel von konkurrierenden und zeitlich überlappenden Schreib/Lese Zugriffen auf ein atomares Register

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Mutex: Der Mutuale Ausschluß

Mutex: Der Mutuale Ausschluß

Protokolle

• Es muss in jedem Prozess der einen kritischen Bereich ausführen muss ein Eingangs- und Ausgangsprotokoll eingehalten werden damit der mutuale Ausschluss garantiert werden kann.
• Für die Implementierung dieses Protokolls soll gelten:

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Mutex Objekt

Mutex Objekt

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:

lock (acquire)

Ein Prozess versucht den Mutex Lock zu erlangen. Wenn dieser Prozess der einzige Bewerber ist bekommt er den Lock und kann in der Ausführung fortfahren. Ist der Lock bereits an einen anderen Prozess vergeben, wir der Aufrufer blockiert (Warten).

unlock (release)

Ein Prozess gibt den Lock zurück. Wenn es wartende Prozesse gibt wird maximal einer ausgewählt und erhält den Lock.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Mutex Objekt

Mutex Objekt

Lua CSP

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 - Synchronisation und Prozesskommunikation :: Mutex Objekt

Beispiele für den Einsatz einer Mutex

• Nicht atomare Operationen auf geteilte Dateneregister

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())

• Nicht atomare Operationen auf geteilte Datenestrukturen, z.B. Listen oder Graphen

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Mutex Objekt

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Mutex

Mutex

Invariante

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.

• Man unterscheidet schwache und starke Mutex Objekte:
  • Bei starken Mutex Objekten darf nur der Prozess den Lock freigeben der ihn agefordert hat und besitzt. Ein Versuch eines Nichteigentümers führt zu einem Programmfehler (Versagen)
  • Bei schwachen Mutex Objekten darf jeder Prozess den Lock freigeben (und auch wenn dieser garnicht vergeben ist)

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore

Semaphore

Eigenschaften

• 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 s₀ 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 - Synchronisation und Prozesskommunikation :: Semaphore

Semaphore

• Wenn #(S.DOWN) und #(S.UP) die Anzahl der Operationsaufrufe ist, die terminiert sind, so gilt die Invariante:

$$S.counter = s_0 + \sum(S.up) - \sum(S.down)$$

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore

Semaphore

Operationale Semantik

Operation down (wait)

S.down erniedrigt den Zähler S.counter atomar um den Wert 1 sofern S.counter > 0.
Wenn S.counter=1 und mehrere Prozesse versuchen gleichzeitig die down Operation anzuwenden, so wird einer den Wettbewerb gewinnen (Mutualer Ausschluss = Lock). Wenn S.counter = 0 dann werden Prozesse blockiert und in einer Warteschlange S.Q eingereiht.

Operation up (signal)

S.up erhöht den Zähler S.counter atomar um den Wert 1. Diese Operation kann immer ausgeführt werden, und blockiert nicht die Ausführung des aufrufenden Prozesses.
Wenn S.counter = 0 ist und es blockierte Prozesse gibt, wird einer aus S.Q ausgewählt und freigegeben (d. h. der Zähler ändert sich effektiv nicht).

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore

Semaphore

Eine Semaphore mit s₀=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 - Synchronisation und Prozesskommunikation :: Semaphore

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore

Algorithmus

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 - Synchronisation und Prozesskommunikation :: Semaphore

Semaphore

Implementierung mit Channels

• Verwendung von voll synchronisierten Channels (Rendezvous):
  • Vom Teilnehmer- zum Semaphoreprozess ein Request Channel ch^r
  • Vom Semaphore- zum Teilnehmerprozess ein Ack. Channel ch^g
  • Semaphoreprozess benutzt Alt Operator für alle Request Channels

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore - Produzenten-Konsumenten Systeme

Semaphore - Produzenten-Konsumenten Systeme

• Semaphoren können eingesetzt werden um konkurrierende Produzenten-Konsumenten Probleme zu lösen. Beispiel ist ein Pufferspeicher mit First-In First-Out Reihenfolge, der eine endliche Anzahl von Speicherzellen eines geschützten Speichers Buf[0..k-1] mit k=size besitzt, und die beiden Zustände S={FREE, FULL} annehmen kann.

• 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 - Synchronisation und Prozesskommunikation :: Semaphore - Produzenten-Konsumenten Systeme

Implementierung eines Pufferspeichers mit Semaphoren

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 OPERATION
END OBJECT

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore - Produzenten-Konsumenten Systeme

Semaphore - Produzenten-Konsumenten Systeme

Synchronisation von Produzenten und Konsumenten von Daten mittels zweier Semaphoren

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore - Dining Philosophers

Semaphore - Dining Philosophers

• Das Problem der fünf dinierenden Philosophen ist ein Beispiel für Deadlocks in verteilten und parallelen (asynchronen) Systemen mit dem Communicating Sequential Processes Modell!

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore - Dining Philosophers

Semaphore - Dining Philosophers

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()
  DONE
END

Dinining Philosophers Template

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore - Dining Philosophers

Semaphore - Dining Philosophers

• Klassisches Problems das zu Deadlocks führt!

Deadlockefreie Lösungen

1. Einführung einer zentralen Instanz die die Gabeln mittels Prioritäswarteschlangen verwaltet
   • Prozess fragt mit einer Nachricht zwei Gabeln an (Input Channel)
   • Verwalter prüft Verfügbarkeit und gewährt die Gabeln durch eine Antwortnachricht (Output Channel)
   • Ein Prozess gibt Gabeln mit einer Nachricht wieder zurück

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Semaphore - Dining Philosophers

Semaphore - Dining Philosophers

2. Abfrage des Semaphorenwertes beider Gabeln bevor die Ressource angefragt wird ggf. über eine globale Mutex geschützt:

sema[left]:down();
if sema[right]:level() == 1 then sema[right]:down()
else sema[left]:up(); sleep(random time) end

3. Münzwurf und Reihenfolge des Zugriffs: Eine Zufallszahl zwischen 0..1 entscheidet ob zuerst die linke und dann rechte Gabel beansprucht wird oder umgekehrt.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Ergeinisobjekt (Event)

Ergeinisobjekt (Event)

• Ein Event ist ein Signalobjekt. Ein oder mehrere Prozesse können auf das Eventsignal warten. Ein weiterer Prozess signalisiert schließlich das Event

Es gibt zwei Operationen:

Opeartion await

Ein Prozess wartet auf das Eintreten des Ereignisses (das Signal). Der Prozess blockiert bis das Signal eintrifft und wird in eine Warteschlange Q eingereiht.

Operation wakup

Ein Prozess signalisiert das Ereignis. Alle in die Warteschlange befindlichen Prozesse werden aktiviert.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Ergeinisobjekt (Event)

Lua CSP

local ev = Event()
Par({
  function () ev:await() .. end,
  function () ev:await() .. end,
  function () ev:wakeup() .. end
},{ ev:ev })

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Barriere

Barriere

• Um das Problem des Wettrennens bei Events zu vermeiden ist es besser eine Barriere für eine Prozessgruppe bekannter Größe zu verwenden.
• Da Barriere ist selbstauslösend, d.h. der letzte Prozess löst das Signal aus.

local ba = Barrier(groupsize)
Par({
  function () ba:await() .. end,
  function () ba:await() .. end,
  function () ba:await() .. end
},{ ba:Barrier(3) })

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Barriere

Barriere

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Timer

Timer

• Ein Timer ist ein automatisch synchronisierendes Event

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 - Synchronisation und Prozesskommunikation :: Channel

Channel

• Ein Kanal ist ein synchronisierter Pufferspeicher mit First-In First-Out Reihenfolge und wird in Produzenten-Konsumenten Systemen eingesetzt.

• Operationen und Verhalten

Operation read

Ein Datenelement wird aus dem Puffer gelesen. Wenn der Puffer leer ist wird der Prozess in eine Wartschlange eingereiht: Q=Q ∩ {P}

Operation write

Ein Datenelement wird in den Puffer geschrieben. Wenn die Warteschlange Q ≠∅, dann wird ein Prozess entfernt und die ausstehende read Operation ausgeführt.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Channel

Channel

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 - Synchronisation und Prozesskommunikation :: Channel

Channel

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Der Alt Prozesskonstruktor

Der Alt Prozesskonstruktor

• 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={ch_i} abfragen kann.

• Ein Lösung bietet der Alt(ernative) Prozesskonstruktur der es ermöglich auf das Eintreten mehrerer Ereignsse (hier die Verfügbarkeit von Daten in Channels) zu warten und eines auszuwählen.

• Der Alt Prozess garantiert Mutual Exclusion Verhalten, d.h.:

  • Treten mehrere Ereignisse gleichzeitig ein, wird genau eines (wie auch immer) ausgewählt und ein Verarbeitungsprozess gestartet
  • Nur maximal eine Operation (also channel:read) wird aus Ch={ch_i} ausgeführt, auch wenn die anderen bereist eingetretende Ereignisse (Daten) haben (Mikro Event loop!!)

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Alt Prozesskonstruktor

Alt Prozesskonstruktor

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 - Synchronisation und Prozesskommunikation :: Monitor

Monitor

• 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.

  • Aber immer mit dem Ziel die Datenkonsistenz möglichst frein granular zu gewährleisten.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Monitor

Monitor

Objektmonitor mit automatischen Schutz (Datenkonsistenz des Objekts)

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Monitor

Monitor

Konzepte

Mutualer Ausschluss

Der Monitor stellt sicher dass immer nur ein Prozess eine Operation des Objektes ausführen kann ⇒ geschützter kritischer Ausführungsbereich = mutualer Ausschluss.

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 - Synchronisation und Prozesskommunikation :: Monitor

Monitor

Events: Bedingungsvariablen mit Queues

• 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 - Synchronisation und Prozesskommunikation :: Monitor

Monitor

Operation C.wait(cond)

Diese Operation blockiert = stoppt den aufrufenden Prozess p und reiht ihn in die Warteschlange C.Q ← C.Q + {p} ein. Für den Prozess der nicht mehr aktiv ist, kann der Mutex LOCK aufgehoben werden.

• Die Wait Operation stellte eine boolesche Bedingung cond dar auf deren Erfüllung gewartet wird.

Operation C.signal()

Ein Prozess p ruft diese Operation auf und erfüllt damit die Bedingung cond.

• Wenn C.Q = ∅ ist dann hat die Operationen keinen Effekt
• Wenn C.Q = {q,...} dann wird ein Prozess q aus Q ausgewählt und aktiviert, so dass C.Q ← C.Q \ {q}

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Monitor

Monitor

Bewahrung des mutualen Ausschlusses in Fall ii.) erforderlich:

• Der aktivierte Prozess q fährt innerhalb des Monitors fort (bekommt den Eintritt wieder) und führt die Anweisungen nach C.wait() aus.

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Monitor

Monitor

• Der aktivierende Prozess p wird blockiert, hat aber höchste Priorität den Monitor danach wieder zu erlangen um die Anweisungen nach C.signal() auszuführen.

Operation C.empty()

Liefert das Ergebnis für die Bedingung C.Q = ∅

• Algorithmik der Bedingungsvariablen (vereinfacht)

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 - Synchronisation und Prozesskommunikation :: Monitor

Monitor

• Implementierung einer Semaphore mit Bedingungsvariablen (vereinfacht)

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 - Synchronisation und Prozesskommunikation :: Monitor

Monitor

• 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 - Synchronisation und Prozesskommunikation :: Monitor

Monitor

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 - Synchronisation und Prozesskommunikation :: Monitor

Monitor

• 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 - Synchronisation und Prozesskommunikation :: Monitor

Varianten

signal-and-wait

Der signalisierende Prozess wartet nach der Signalisierung und der mutuale Ausschluss ist sichergestellt und die Wahrung P=TRUE. Der wartende Prozess führt aus: IF ¬P THEN C.wait() END IF

signal-and-continue (re-check)

Der signalisierende Prozess läuft weiter! Das könnte zur Verletzung des Prädikats P führen, daher muss der signalisierte Prozess nochmals die Gültigkeit P=TRUE prüfen so dass für ihn auszuführen ist: WHILE ¬P DO C.wait() END WHILE

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Objektmonitore in Lua

Objektmonitore in Lua

local S = class()
function S:init (i)
  self.counter=i;  self.L=Mutex()
end
function S:up ()
  self.counter=self.counter+1
end
function S:down ()
  self.counter=self.counter+1
end
function 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 end
end

Beispiel für einen einfachen und naiven geschützten Monitor in Lua. Wo könnte es Probleme geben?

PD Stefan Bosse - VPP - Synchronisation und Prozesskommunikation :: Zusammenfassung

Zusammenfassung

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)