Verteilte und Parallele Programmierung

PD Stefan Bosse
Universität Bremen, FB Mathematik & Informatik
SS 2020
Version 2020-06-02

Zustands-Raum Diagramme

Für die Visualisierung und Analyse von nebenläufigen Prozessen und Aktionen

Nebenläufige Programmierung: Zustands-Raum Diagramme

Zustands-Raum Diagramme beschreiben die möglichen Zustands-Entwicklungen - das Verhalten - von parallelen Programmen.

  • Computer sind endliche Zustandsautomaten. Der Zustandsübergang wird durch die Programminstruktionen hervorgerufen.

  • Der Zustand S eines parallelen Programms welches aus N Prozessen Pi besteht setzt sich zusammen aus folgenden Tupeln:

    • Globale Variablen des Programms:
    • Lokale Variablen und Instruktionszeiger von Prozess 1:
    • Lokale Variablen und Instruktionszeiger von Prozess 2: usw.

  • Die Berechnung ändert globale und lokale Variablen (Datenfluss) sowie Instruktionszeiger (Kontrollfluss) und führt zu einer Zustandsänderung comp: si → sj.

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Wesentliche Zustandsänderung ist die Änderung von lokalen und globalen Speicher.

  • Variablen sind Bestandteil von Ausdrücken und erlauben zwei Operationen: {read,write} 

1: var x: read(x) ⇔ RHS value(x) → ε (value(x))
2:        write(x,v) ⇔ LHS reference(x) → x := v

Beschreibung eines parallelen Programms auf Programmierebene

  • Der Zugriff auf globale und somit geteilte Variablen muss atomar sein, d.h. immer nur ein Prozess kann den Wert einer Variable lesen oder einen neuen Wert schreiben.

  • Der parallele Zugriff auf eine geteilte Ressource muss aufgelöst werden (Konflikt): i.A. mutualer Ausschluss durch Sequenzialisierung der parallelen Zugriffe!

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Beispiel 
1:   write(X,v1) || write(X,v2) || x3:=read(X) → 
2:   write(X,v1); read(X,x3); write(X,v2) |
3:   x3=read(X);  write(X,v2); write(X,v2) | ..
  • Algebraisch ausgedrückt ergibt sich die Transformation:
\[\frac{\begin{gathered} (WRITE(x,{v_1}) \to {p_1})\parallel \hfill \\ (WRITE(x,{v_2}) \to {p_2}) \hfill \\ \end{gathered} }{\begin{gathered} (WRITE(x,{v_1}) \to (WRITE(x,{v_2}) \to ({p_1}\parallel {p_2})))| \hfill \\ (WRITE(x,{v_2}) \to (WRITE(x,{v_1}) \to ({p_1}\parallel {p_2})))| \hfill \\ .. \hfill \\ \end{gathered} } \]
  • Es gibt eine Menge von möglichen Entwicklungen des parallelen Systems!

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Instruktionen von Prozessen werden sequenziell ausgeführt. Instruktionen können auf Prozess-lokale und Programm-globale Variablen zugreifen.
  • Definition eines parallelen Programms: globale Variablen (V) und Prozesse mit lokalen Variablen (v) 


1: var V1,V2,...
2: process p1(a1,a2,...)   process p2(a1,a2,...)
3:   var v1,v2,....          var v1,v2,....
4:   <Instruktion1 i1>       <Instruktion1 i1>
5:   <Instruktion2 i2>       <Instruktion1 i2>
6:   Vi := ε(ai,vi,Vi)        Vi := ε(ai,vi,Vi)
7:   vi := ε(ai,vi,Vi)        vi := ε(ai,vi,Vi)
8: end                     end

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Bei einem sequenziellen Programm ist das Ergebnis einer Berechnung (d.h. die Werte aller Variablen) deterministisch allein durch die Anweisungssequenz und die Eingabedaten gegeben, und kann beliebig oft wiederholt werden - immer mit dem gleichen Ergebnis → Reihenfolge aller Anweisungen der Berechnung vorgegeben und fest

  • Bei einem parallelen Programm können mehrere Anweisungen verschiedener Prozesse gleichzeitig ausgeführt werden bzw. konkurrieren.

  • Die Reihenfolge parallel ausgeführter Anweisungen von einzelnen Prozessen kann hingegen undeterministisch = zufällig sein!!

  • Jeder der Prozesse kann als nächster den Zustand des Programms ändern.

  • Ein Zustands-Raum Diagramm beschreibt die Änderung des Programmzustandes als sequenzielle Auswertung aller möglichen Prozessaktivitäten.

Nebenläufige Programmierung: Zustands-Raum Diagramme

  • Das Diagramm ist ein gerichteter Graph, dessen Knoten den aktuellen Programmzustand s ∈ S beschreiben, und dessen Kanten die möglichen Zustandsübergänge beschreiben.

  • Es gibt einen ausgewiesen Startzustand (Initialisierung) und einen oder mehrere Endzustände.

  • Gibt es mehrere Endzustände liegt wohl möglich ein Entwurfsfehler vor, da das Programm unterschiedliche Endergebnisse liefern kann.

Algorithmus: Entwicklung des Zustands-Raum Diagramms

  • Parallelen Programms welches aus N Prozessen P={p1,p2,..,pN} besteht.
  1. Initialisiere den Startzustand sx=s0 und erzeuge Wurzel-Knoten s0 im Diagramm.
  2. Aktueller Zustand: sx. Setze P*:=P mit P={p1,p2,..,pN} als Prozessliste und S*={}

Nebenläufige Programmierung: Zustands-Raum Diagramme

  1. Wähle (entferne) einen beliebigen Prozess px aus der Prozessliste P* und setze P*:= {pn| pn ∈ P* ∧ pn ∉ px}

  2. Evaluiere die nächste Instruktion ix,n von px und berechne die Wirkung auf lokale und globale Variablen sowie den Instruktionszeiger Ix,n.

  3. Erzeuge einen neuen Zustandsknoten sj/=x , füge ihn zur Liste S*:=S* ∪ {sj} hinzu und verbinde ihn mittels einer Kante tx→j mit dem aktuellen Ausgangszustand sx

  4. Wiederhole Schritt 3 bis 5 für alle anderen verbleibenden Prozesse p ∈ P bis P*={}

  5. Setze S**:=S*. Für jeden Knoten sx ∈ S** wiederhole die Schritte 2 bis 6. Iteriere Schritt 7 bis alle Prozesse terminiert sind oder keine Zustandsänderung mehr auftritt.

Nebenläufige Programmierung: Zustands-Raum Diagramme

Beispiel

1: Sequenzielles Programm      Paralleles Programm
2: for i := 1 to 3 do i1        process p1
3:                                for i := 1 to 3 do i1
4:                              end
5:                              process p2
6:                                for j := 1 to 3 do i2
7:                              end

figcpv

Abb. 1. Beispiel und mögliche Entwicklung des Programmzustands (lokale Var. i,j)

Globale Ressourcen und Synchronisation

Globale Ressourcen

  • In dem bisherigen Programmiermmodell gibt es nur globale Variablen als globale geteilte Ressourcen, die konkurrierend von Prozessen gelesen und beschrieben werden können.

  • Die globalen Variablen dienen dem Datenaustausch = Kommunikation zwischen den Prozessen (Shared Memory Model!).

Atomare Aktionen

  • Atomare Operationen, Schreibweise |A| werden in einem Schritt ausgeführt und können nicht durch andere Prozesse unterbrochen werden (keine Interferenz).

  • Einzelne Lese- und Schreibe-Operationen mit globalen Variablen sind atomar. Nebenläufigkeit wird durch Sequenzialisierung aufgelöst. 
t1: |X := v|

Globale Ressourcen und Synchronisation

Nicht atomare Aktionen und Synchronisation

Zusammengesetzte Ausdrücke können aus mehreren Berechnungsschritten bestehen, so ist z. B. X := X + 1 als Ganzes nicht mehr atomar! 

1: t1: |temp=X| 
2: t2: |X:=temp+1|

Beispiel einer unzureichend geschützten nicht atomaren Aktion

1: var X := 1     
2: INCR(X)     DECR(X)
3: process p1     process p2
4:   var t:=0       var t:=0
5:   t := X         t := X
6:   X := t + 1     X := t - 1
7: end            end

Globale Ressourcen und Synchronisation

figcpvex1

Abb. 2. Zustands-Raum Diagramm mit unterschiedlichen Endergebnissen (X=0,-1,1)

Globale Ressourcen und Synchronisation

Nicht atomare Aktionen (Sequenz von Aktionen) mit globalen Ressourcen müssen durch Mutuale Ausschlusssynchronisation geschützt werden → Schutz von kritischen Codebereichen ⇒ Datenkonsistenz!

Semaphore

  • Eine Semaphore S ist ein Zähler s>0 der niemals negative Werte annehmen kann.

  • Es gibt zwei atomare Operationen die von einer Menge von Prozessen P={p1,p2,…} auf einer Semaphore S angewendet werden können:

Globale Ressourcen und Synchronisation

Definition 1. (Operationen der Semaphore)
 

1: operation down(S) ∈ p: 
2:   |if s > 0 
3:    then s := s - 1 
4:    else WAITERS+(S,p),block(p)|
5: operation up(S) ∈ p: 
6:   |if s = 0 and WAITERS(S) ≠ [] 
7:    then pi=WAITERS-(S),unblock(pi) 
8:    else s := s + 1|

Globale Ressourcen und Synchronisation

  • Eine Semaphore mit einem Startwert s=1 entspricht einer Mutex (binäre Semaphore). Ein DOWN(S) leitet einen kritischen Bereich in einer Sequenz i1,i2,i3, … ein, und ein UP(S) gibt ihn wieder frei: 
1: semaphore S(1)
2: ... down(S) |i1,i2,i3,..,in)| up(S) ...

Beispiel einer mit einer Semaphore geschützten nicht atomaren Aktion

 1: var X := 1
 2: semaphore S := 1
 3: INCR(X)        DECR(X)
 4: process p1     process p2
 5:   var t:=0       var t:=0
 6:   down(S)        down(S)
 7:   t := X         t := X
 8:   X := t + 1     X := t - 1
 9:   up(S)          up(S)
10: end            end

Globale Ressourcen und Synchronisation

figcpvex2

Abb. 3. Zustands-Raum Diagramm mit einem Endergebnis (X=1)

Petri Netze

Petri-Netze für die Modellierung, Analyse, und Implementierung von Parallelen Systemen und Digitallogik

Petri-Netze: Einführung und Grundlagen

Petri-Netze eignen sich für die Darstellung paralleler Prozesse und deren Analyse des dynamischen Verhaltens

Petri-Netz (State-Transition)

  • Ein Petri-Netz ist ein Quadrupel PN = <S,T,E,A> mit

    • S: Menge von Stellen (oder auch Plätzen sowie Zuständen/States)
    • T: Menge von Übergängen (oder auch Transitions)
    • E: Menge der Eingabekanten, gegeben durch die Relation E ⊆ S × T
    • A: Menge der Ausgabekanten, gegeben durch die Relation A ⊆ T × S

Markierungen M

  • Das dynamische Verhalten der Petri-Netze wird mittels von Markierungen beschrieben (Tokens).

  • Es gibt eine Markierungsfunktion M: S → N mit N={0,1,2..}, die die Anzahl der Markierungen M(s), s ∈ S einer Stelle s angibt.

Petri-Netze: Einführung und Grundlagen

  • Eine Stelle kann keine, eine, oder mehrere Markierungen besitzen (aufnehmen). Es kann eine maximale Kapazität k einer Stelle geben, die Übergänge beeinflusst (k-begrenzte Stellen, im Gegensatz zu unbegrenzten mit k → ∞).

  • Eine Markierung kann durch Übergänge t ∈ T von eine Stelle s1 ∈ S zu einer anderen s2 ∈ S übertragen werden.

Interpretation

  • Petri-Netze können auch verschiedene Weise interpretiert werden, d.h. die Abbildung von Systemen auf PN durch Assoziation von Stellen und Übergängen!

figpn

Petri-Netze: Einführung und Grundlagen

Regeln für den Übergang

  • Jedem Übergang t ∈ T ist eine Menge von Eingangsstellen SE ∈ S zugeordnet (mindestens eine Stelle).

  • Jedem Übergang ist eine Menge von Ausgangsstellen SA ∈ S zugeordnet (mindestens eine Stelle).

  • Ein Übergang kann schalten, d.h. Markierungen von den Eingangs- zu den Ausgangsstellen übertragen, wenn alle Eingangsstellen wenigstens eine Markierung besitzen.

  • Eine Kante kann eine Gewichtung g besitzen, die die Anzahl der gleichzeitig zu übertragenden Markierungen angibt.

figpn2

Petri-Netze: Einführung und Grundlagen

Dynamik: Kausalität

Verschiedene Grundsituationen und Vorbedingungen (Guards/Aktivierung) für Übergänge

figpntrans
  1. Der Übergang t1 muss vor dem Übergang t2 geschaltet haben → Kausalität, Ereignisreihenfolge
  2. Hier muss t1 zweimal geschaltet haben, um die Kante zu t2 mit dem Gewicht g=2 zu aktivieren. Zusätzlich müssen zwei weitere Stellen Markierungen besitzen, um den Übergang t2 mit insgesamt vier Markierungen aktivieren zu können.
  3. Konflikt: Entweder Übergang t1 oder t2 wird aktiviert (nicht deterministisch!)

Petri-Netze: Einführung und Grundlagen

Dynamik: Parallelität und Synchronisation

Verschiedene Grundsituationen für die Synchronisation bei paralleler Aktivierung von Teilnetzen

figpnsync
  1. Fork Situation: Ein Übergang t produziert bei seiner Aktivierung mehrere Markierungen (entsprechend seiner Ausgangskanten).
  2. Join Situation: Mehrere Markierungen entsprechend der Eingangskanten werden konsumiert und aktivieren den Übergang t.
    1. Kontakt: nur bei Stellen mit endlicher Kapazität k möglich. Ähnlich dem Konflikt, wo ein ein Übergang (Kante x) einen anderen deaktiviert (Kante y). Jedoch auch D: Nebenläufigkeit der Übergänge t1, t2, und t3.

Petri-Netze: Einführung und Grundlagen

Beispiel: Dining Philosophers

figpndining

Abb. 4. Dinierende Philosophen (Ausschnitt für einen Philosophen) mit einer möglichen Situation (linke und rechte Gabel Stellen sind Ressourcen, und die beiden anderen Stellen bilden den Zustand des Philosophens ab). Es gilt k=1!

Petri-Netze: Einführung und Grundlagen

Petri-Netze mit Ressourcen und Prozessen

  • Stellen S können Lager/Kontainer für Daten/Ressourcen (Markierungen/Tokens) repräsentieren, meistens mit einer Kapazität k > 1!

  • FIFO-Queues wären Implementierungen solcher Kontainer!

  • Übergänge T können mit Prozessen oder Operationen verknüpft sein, die Daten/Ressourcen verarbeiten.

  • Datenflussgraphen können in solche ST Netze abgebildet werden.

Petri-Netze und Digitallogik

  • ST Petri-Netze können ebenfalls zur Darstellung kombinatorischer und sequenzieller Digitallogiksysteme verwendet werden.

  • Dabei werden Stellen Signalwerten, und Übergängen Signaländerungen zugeordnet.

Petri-Netze: Einführung und Grundlagen

  • Ein Signal (hier x und y) wird mit zwei Stellen verknüpft (zweiwertige Logik).
  • Die Übergänge werden mit einer Änderung des gegebenen Signals verknüpft (Aktivierungsbedingung): A= {a+,a-,a~}, wobei a+ den Übergang 0→1, a-:1→0, und a~ entweder 0→1 oder 1→0 des Signals a bedeutet.
  • Der bidirektionale Pfeil (Schleife) bedeutet hier einen “nur-lese” Transfer der Stellen der Eingangssignale!

figpninv

Abb. 5. Beispiel: (Circuit) PN für die Beschreibung des Verhaltens eines Inverters aus der Digitallogik (kombinatorische Logik) mit erweiterten Regelsatz für Übergänge

Petri-Netze: Einführung und Grundlagen

  • Die Plätze der Eingangssignale werden explizit mit Markierungen versehen.

  • Anmerkung: Das PN bildet einen Zustandsübergangsgraphen (STG) ab!

figpnor

Abb. 6. Weiteres Beispiel: (Circuit) PN für die Beschreibung des Verhaltens eines Oder-Gatters

Kommunizierende Seq. Prozesse und Petri-Netze

  • Petri-Netze können zur Beschreibung von Multi-Prozess (MP) Systemen verwendet werden.
  • Petri-Netze können aus Signalflussdiagrammen oder Datenflussgraphen abgeleitet werden.
  • Sie können dann zur Synthese von MP Systemen verwendet werden.

Kontroll-Prozess-Modell

Prozesse P

Prozesse p∈P führen (sequenziell) Anweisungen durch.

Dabei werden Prozesse auf Übergänge t∈T abgebildet, die mit der sequenziellen Ausführung von Anweisungen bei deren Aktivierung verknüpft sind.

Prozesssteuerung

Markierungen aktivieren Prozesse und dienen der Synchronisation.

Parallelisierung durch spezielle Fork-Übergänge und Synchronisation durch spezielle Join-Übergänge.

Kommunizierende Seq. Prozesse und Petri-Netze

Kommunikation
Interprozess-Kommunikation (synchronisierter Datenaustausch) findet durch Kontainer (Queues) statt, die durch spezielle Übergänge t∈T repräsentiert und abgebildet werden.

figpncsp

Abb. 7. Abbildungen von Anweisungen und Prozesskonstruktoren (z. B. :=, Seq, while, Par, ?!) auf Kontroll-Prozess-Petri-Netze

Kommunizierende Seq. Prozesse und Petri-Netze

Daten-Prozess-Modell

Prozesse P
Prozesse p∈P (bzw. funktionale Blöcke f∈F deren Berechnung durch Prozesse gekapselt werden können) führen Berechnungen durch.
  • Dabei werden Prozesse auf Übergänge t∈T abgebildet, die mit der Berechnung als Aktion verknüpft sind.
  • Direkte Abbildung aus Signalflussdiagrammen möglich!
  • Pipeline-Architektur
Daten
Daten werden durch Markierungen repräsentiert.
  • Sie dienen der Aktivierung von Prozessen = Übergängen, die die Daten verarbeiten sollen.

Kommunizierende Seq. Prozesse und Petri-Netze

Kommunikation
Interprozess-Kommunikation (synchronisierter Datenaustausch) findet durch Kontainer (Queues) statt, die durch Stellen s ∈ S repräsentiert und abgebildet werden.
  • Die Daten (Markierungen) werden durch die Stellen zwischen Übergangen übertragen.

Kommunizierende Seq. Prozesse und Petri-Netze

Beispiel aus der Digitalen Signalverarbeitung

figsigflowcon

Abb. 8. Beispiel eines Signalflussdiagramms für einen PID-Regler Algorithmus mit Grundelementen Addierer , Multiplizierer , und Verzögerungs-/Speicherelement Z-1

Kommunizierende Seq. Prozesse und Petri-Netze

figpncon

Abb. 9. Abbildung auf Petri-Netz (Funktionsblöcke/Operationen auf Übergänge, Daten auf Stellen) und hier umgekehrt schließlich auf CSP (process) mit Kommunikationskanälen (channel) und ConPro Programmiersprache.

Deadlocks in Petri-Netzen

  • Deadlocks in Petri-Netzen entstehen durch Konflikte oder Mehfachauswahl bei Übergängen (Nicht-Determinismus), wo die Reihenfolge der Aktivierungen maßgeblich ist.
  1. PN mit genau einer Kante zu und von jeder Stelle sind deadlock/konfliktfrei!
  2. PN wo alle Übergänge höchstens einen Eingangs- und Ausgangsplatz besitzen sind deadlock/konfliktfrei!

figpndead

Abb. 10. Beispiel einer Deadlock Situation die in einem Petri-Netz auftreten kann, in Abhängigkeit von der Reihenfolge der Aktivierungen der Übergänge

Verhaltensmodelle

Zustandsbasiert (Verhalten)

Reaktive Systeme:

  • Finite State Machines
  • Petri-Netze
  • Hierarchische nebenläufige FSMs

Aktionsbasiert (Verhalten)

Transformatorische Systeme:

  • Datenflussgraph
  • Kontrollflussgraph

Heterogene Modelle

  • Programmflussgraph: Kontrollflussgraph + Datenflussgraph
  • Programmiersprachliche Paradigmen

Verhaltensmodelle

Daten-, Kontroll-, und Programmfluss

  • Ein Programm wird durch einen Programmfluss beschrieben
  • Der Programmfluss lässt sich in reine Daten- und Kontrollanweisungen zerlegen → Daten- und Kontrollfluss
  • Der Datenfluss wird durch den Datenpfad implementiert (Verhaltensbeschreibung des Datenpfades, mit Datenabhängigkeitsgraphen) → Register, Funktionale Operatoren, Datenpfadselektoren (Multiplexer)
  • Der Kontrollfluss wird durch den Kontrollpfad implementiert (Verhaltensbeschreibung des Kontrollpfades mit Zustandsübergangsgraphen) → Zustandsautomat
  • Datenanweisungen verwenden arithmetische, relationale, und Boolesche Ausdrücke

Datenabhängigkeitsgraphen

  • Eine Datenabhängigkeit in der Informatik ist eine Situation, in der sich eine Programmanweisung (Anweisung) auf die Daten einer vorhergehenden Anweisung bezieht.

  • Ein Datenabhängigkeitsgraph G = (I, E) besteht aus einer Menge von Instruktionen I und einer Menge transitiver Relationen R = I x I, mit (a, b) in R falls die Instruktion a vor b bewertet werden muss.

  • Mit anderen Worten, es gibt eine Kante von a nach b:

figdadep

wenn a vor b ausgewertet werden muss.

Scheduling

  • Jeder Knoten (Anweisung) auf derselben Ebene ist unabhängig von der anderen → Parallelisierung
  • Um die Anweisungen in Level i auszuführen, müssen die Anweisungen in Level i-1 beendet sein

Datenabhängigkeitsgraphen

figddg[Ortiz­-Ubarri, José]

Abb. 11. Beispiel eines DAG für eine Instruktionssequenz (nur Datenanweisungen)