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