Verteilte und Parallele Programmierung

PD Stefan Bosse

Universität Bremen, FB Mathematik & Informatik

SS 2020
Version 2020-05-19

sbosse@uni-bremen.de

Das Prozessmodell

Fluss und Pfad

Ein Datenfluss (Graph aus Operationen oder Variablen) beschreibt den Verlauf und die Verarbeitung von Daten durch Operationen → Verhaltensbeschreibung
Ein Datenpfad beschreibt die Verbindung von Komponenten zur Implementierung des Datenflusses → Strukturbeschreibung
Der Kontrollfluss beschreibt die zustandsbasierte Steuerung einer Berechnung
- Bedingte (↔ Datenfluss) Verzweigungen im Kontrollfluss
- Schleifen im Kontrollfluss
Der Kontrollpfad implementiert den Kontrollfluss → Zustandsautomat

Daten- und Kontrollpfade

Jeder generische Mikroprozessor und i.A. jedes anwendungsspezifische Digitallogiksystem läßt sich in die zwei funktionale Bereiche aufteilen:

Datenfluss → Datenpfade
Kontrollfluss → Kontrollpfad → Zustandsautomat

Datenpfad

Führt Berechnungen durch
Kann rein funktional (speicherlos, kombinatorisch) oder speicherbasiert mir Register-Transfer Architektur sein

Kontrollpfad

Der Kontrollpfad ist immer zustandsbasiert (Speicher) und bestimmt die Reihenfolge von Operationen und Berechnungen

Daten- und Kontrollpfade

Parallelisierung

Der Programmfluss kann in Daten- und Kontrollfluss zerlegt werden, die jeweils im Daten- und Kontrollpfad eines Datenverarbeitungssystems verarbeitet werden.

Kontrollpfad: Parallelität auf Prozessebene (Multithreading) mit Interprozesskommunikation → Mittlere bis geringe Beschleunigung, mittlerer Overhead
Datenpfad: Parallelität auf Dateninstruktionsebene ohne explizite Kommunikation → Hohe Beschleunigung, geringer Overhead

Daten- und Kontrollpfade

Zustandsautomat

Der Zustandsautomat ist für die sequenzielle Ablaufsteuerung zuständig:
1. Der Zustandsautomat steuert den Datenfluss im Datenpfad;
2. Er ist für die Ein- und Ausgabesteuerung zuständig,
3. Implementierung von Handshake-Protokollen für den Datenaustausch mit anderen Systemblöcken (auch IPC), und
4. Er behandelt Ausnahmesignale und Fehler.

Daten- und Kontrollpfade

Programm

Ein (prozedurales/imperatives) Programm besteht aus mindestens einem Daten- und Kontrollpfad (oder Fluss)
Ein Programm ist aus einer Vielzahl von Komponenten zusammengesetzt → Komposition
Komposition von Datenfluss und Datenpfad:
- Funktionale Komposition
- Parallele Komposition
Komposition von Daten- und Kontrollfluss/pfad:
- Sequenzielle Komposition
- Parallele Komposition

Daten- und Kontrollpfade

Basisblöcke und Parallelisierung

Datenflussgraph (DFG)

Der DFG beschreibt Datenabängigkeiten zwischen einzelnen Berechnungen
Ein DFG besteht i.A. aus einer Menge von einzelnen DFGs
Unabhängige DFGs bzw. Teilgraphen können parallel berechnet werden

Daten- und Kontrollpfade

Kontrollflussgraphen (KFG)

Der KFG bildet verschieden Ablaufpfade (Sequenzen) in einem Programm ab
Der KFG besteht aus Basisblöcken mit DFG
Ein Basisblock beinhaltet nur Berechnungen ohne Verzweigungen und Schleifen
- Ein Basisblock ist eine Einheit für die Datenpfadparallelisierung
Verzweigungen im Kontrollfluss können konditional sein und von Variablen abhängen

Daten- und Kontrollpfade

Daten- und Kontrollpfade

Definition 1. (Kontrollflussgraph)
Ein Kontrollflussgraph ist ein gerichteter Graph G_CFG(BB,E_control) der aus einer Knotenmenge BB von Basisblöcken bestehten aus reinen Berechnungsanweisungen (Datenpfad) und einer Menge von Kanten E besteht, die den Kontrollfluss zwsichen den Basisblöcken beschreiben.

Daten- und Kontrollpfade

Die Kombination aus KFg und DFG zu sog. hierarchischen Taskgraphen (HTG) führt zu einer Komposition eines Programms aus einzelnen Tasks H
Die Abhängigkeiten und der Fluss der Tasks wird im folgendne Prozessmodell wieder auftauchen
Abhängigkeiten im HTG können Synchronisation erfordern!
Mit Tasks können auch komplexeren Kontrollstrukturen wie Schleifen, Bedingte Verzweigung und Mehrfachauswahl gekapselt werden!
Hierarchie: HTG Blöcke (Knoten des HTG) können aus weiteren Tasks und HTG Knoten bestehen!

Daten- und Kontrollpfade

Funktionale Komposition

Eine Berechnung setzt sich aus der verschachtelten und verketteten Applikation von Funktionen zusammen, die jeweils aus elementaren Ausdrücken E={ε₁,ε₂,..} bestehen → Funktionale Komposition F(X)=f₁(f₂(f₃..(X)))

Jede Funktion f_i beschreibt einen Teil der Berechnung.
Ausdrücke bestehen aus:

Konstante und variable Werte 1,2.0,'c',"hello",x,y,z
Einfache arithmetische Ausdrücke ε=x+y
Zusammengesetzte Ausdrücke (arithmetische Komposition) ε=(x+1)*(y-1)*z

Relationale Ausdrücke x < 0
Boolesche Ausdrücke a and b or c
Bedingte Ausdrücke liefern Werte if x < 0 then x+1 else x-1
Funktionsapplikation f(x,y,z)

Funktionale Komposition

Entspricht dem mathematischen Modell was auf Funktionen und Ausdrücken gründet mit den Methoden
- Definition f(x) = λ.x → ε(x)
- Applikation f(ε), bei mehreren Funktionsargumenten f(ε₁,ε₂,..)
- Komposition f ∘ g ∘ h ∘ .. = f(g(h(..(x)))
- Rekursion f(x) = λ.x → ε(f,x)
- und Substitution a=ε
Zeitliches Modell: unbestimmt (t ↦ 0), Auswertereihenfolge nicht festgelegt

figfunblockex

Sequenzielle Komposition

Eine imperative Berechnung setzt sich aus einer Sequenz I=(i₁ , i₂ , ..) von elementaren Anweisungen A={a₁,a₂,..} zusammen →
Sequenzielle Komposition i₁ ; i₂ ; …

Die Anweisungen werden sequentiell in exakt der angegebenen Reihenfolge ausgeführt
Die Menge der Anweisungen A lässt sich in folgende Klassen unterteilen:

Arithmetische, relationale, und boolesche Ausdrücke (in Verbindung mit 2./3.) x+1, a*(b-c)*3, x<(a+b), ...
Datenanweisungen: Wertzuweisungen an Variablen x := a+b
Kontrollanweisungen wie bedingte Verzweigungen und Sprünge (Schleifen)

if a < b then x := 0
label: x:=x+1; if x < 100 then loop label

Sequenzielle Komposition

Man fasst die Sequenz I als ein imperatives Programm X == Ausführungsvorschrift zusammen.
Die Ausführung des Programms (statisch) bezeichnet man als Prozess (dynamisch)
Ein Prozess befindet sich aktuell immer in einem Zustand σ einer endlichen Menge von Zuständen Σ={σ₁ , σ₂ , ..}.
Der gesamte Zustandsraum Σ des Prozesses setzt sich aus dem
- Kontrollzustand s ∈ S={s₁, s₂, ..}, und dem
- Datenzustand mit der Menge aller Speicherzustände (Daten) d ∈ D={d₁, d₂, ..} zusammen.
Der Fortschritt eines sequenziellen Programms bedeutet ein Änderung des Kontroll- und Datenzustandes → Zustandsübergänge
Die Zustandsübergänge können durch ein Zustandsübergangsdiagramm dargestellt werden.

Zustände und Zustandsdiagramm

Jede Anweisung i_n wird durch wenigstens einen Kontrollzustand s_m ∈ S repräsentiert: i_n ∈ I ∈ A ⇒ s_m ∈ S

Beispiel Berechnung GGT

A={assign^:=,loop^WHILE,branch^IF}
 
S={s1,s2,s3,s4,s5,s6}
 
x^i1→s1 := 32;
y^i2→s2 := 16;
WHILEi^i3→s3 x <> y DO
  IF^i4→s4 x < y THEN 
    x^i5→s5 := x - y; 
  ELSE 
    y^i6→s6 := y - x;

Kontrollzustandsdiagramm

figfsmex1

Sequenzieller Prozess

Ausführungszustände

Ein Prozess P besitzt einen “makroskopischen” Ausführungszustand ps. Die Basismenge der Ausführungszustände PS ist (“Milestones”):
- Start/Bereit aber noch nicht rechnend (START)
- Rechnend (RUN)
- Terminiert und nicht mehr rechnend (END)
Dazu kann es eine erweiterte Menge PS*an Ausführungszuständen geben:
- Auf ein Ereignis wartend (AWAIT)
- Blockiert (BLOCKED)
- Rechenbereit aber nicht rechnend (nach Ereignis) (READY)

\begin{gathered} PS = \{\mathtt{START,RUN,END}\} \hfill \\ PS^{*} = \{ \mathtt{AWAIT,BLOCKED,READY}\} \hfill \\ ps(P) \in PS \cup PS^{*} \hfill \\ \end{gathered}

Sequenzieller Prozess

Prozessblockierung

Das Konzept der Prozessblockierung ist elementar für kommunizierende Prozesse
Kommunikation: Lesen und Schreiben von Daten, Ein- und Ausgabe, Netzwerknachrichten, usw.
Befindet sich ein Prozess im Ausführungszustand BLOCKED wartet dieser auf ein Ereignis:
- Daten sind verfügbar
- Zeitüberschreitung
- Geteilte Ressource ist frei
- Synchronisation mit anderen Prozessen
Bei einem blockierten Prozess schreitet der Kontrollfluss nicht weiter voran (keine Terminierung der aktuellen Operation)
Die Ausführung einer Operation (Instruktion) kann verzögert werden bis das zu erwartende Ereignis eintritt

Sequenzieller Prozess

Ein Prozess kann mittels der Operation suspend und resume blockiert oder wieder lauffähig gemacht werden
In einem Kontrollflussdiagramm würde es einen Kantenübergang auf den blockierten Zustand geben

Prozesszustandsübergangsdiagramm

figprocstate [bitsofcomputer.blogspot.com]

Sequenzieller Prozess

Instruktionen sind Prozesse

Jede Instruktion i kann als ein elementarer Prozess P aufgefasst werden.
Zu jeder Instruktion gehört eine Aktion
Terminierung eines Prozesses entspricht ausgeführter Instruktion.
Ein folgender Prozess wird erst dann aktiviert (gestartet) wenn der vorherige terminiert ist → Synchronisation.

figseqpro

Sequenzieller Prozess

Zeitliches Modell

Ein Prozess führt die Anweisungen der Reihe nach aus. Das symbolische Semikolon teilt den Anweisungen eigene Ausführungsschritte (Zeitpunkte t_i) zu.

\begin{gathered} {i_1}:{t_1} \mapsto {i_2}:{t_2} \mapsto {i_3}:{t_3} \mapsto .. \mapsto {i_n}:{t_n}{\text{ mit}} \hfill \\ {t_1} < {t_2} < {t_3} < .. < {t_n} \hfill \\ T = \sum\limits_i {{t_i-t_{i-1}}} \hfill \\ \end{gathered}

Die gesamte Ausführungszeit T(p) eines sequenziellen Prozesses p ist die Summe der Ausführungszeiten der Elementarprozesse

Sequenzieller Prozess

Prozesskonstruktor

\begin{gathered} P = ({P_1}{\text{ ; }}{P_2}{\text{ ; }}..{\text{ ; }}{P_n}){\text{ }} \Leftrightarrow \hfill \\ {\mathtt{SEQ}} \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_1} \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_2} \hfill \\ {\mathtt{\quad}}.. \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_n} \hfill \\ \end{gathered}

Sequenzielle Prozesse können geschachtelt werden (hierarchische Komposition).
- Jede Schachtelung von sequenziellen Prozessen kann ohne Verletzung des Ablaufmodells durch einen einzelnen sequenzielle Prozess ersetzt werden (sofern Reihenfolge beachtet wird):

P = (P_1(P_2(..(P_n)))) = ({P_1}{\text{ ; }}{P_2}{\text{ ; }}..{\text{ ; }}{P_n})

Sequenzieller Prozess

Parallele Komposition

Ausgangspunkt: Ausführungsmodell eines sequenziellen Prozesses P

Ein sequenzieller Prozess Ps besteht aus einer Sequenz von Anweisungen I=(i₁ ; i₂ ;..) (Berechnungen), die schrittweise und nacheinander ausgeführt werden: Ps=P(i₁ ; i₂ ; .. ; i_n) ⇒ p₁ ↦ p₂ ↦ .. ↦ p_n

Ein Prozess P kann sich in verschiedenen Ausführungszuständen ps ∈ RS ⊂ PS ∪ PS* befinden:

RS={START, RUN, BLOCKED(i),END}
ps(P) ∈ RS

Prozessblockierung

Dabei kann ein Prozess in einer Instruktion i blockieren, d.h. die folgende Instruktion i+1 wird noch nicht ausgeführt und der Prozess verbleibt aktionslos in der aktuellen Instruktion

Parallele Komposition

Prozesse als steuerbare Objekte

Ein Prozess P kann mittels Operationen gestartet und gestoppt werden:

Definition 2.

op start(P):   ps(P)=START|END ↦ ps(P)=RUN
op stop(P):    ps(P)=RUN|BLOCKED|START ↦ ps(P)=END
op suspend(P): ps(P)=RUN ↦ ps(P)=BLOCKED
op resume(P):  ps(P)=BLOCKED ↦ ps(P)=RUN

Parallele Prozesse

Ein Datenverarbeitungssystem als paralleler Prozess kann aus einer Vielzahl nebenläufig ausgeführter Prozesse P={P₁, P₂, P₃,…} bestehen

Parallele Komposition P=P₁ ∥ P₂ ∥ P₃ ∥ ..

Paralleler Prozess

Prozesskonstruktor

\begin{gathered} P = ({P_1}\parallel {P_2}\parallel ..\parallel {P_n}){\quad} \Leftrightarrow \hfill \\ {\mathtt{PAR}} \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_1} \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_2} \hfill \\ {\mathtt{\quad}}.. \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_n} \hfill \\ \end{gathered}

Ausführungsreihenfolge

Achtung! Wenn keine Kommunikation (Synchronisation) zwischen den Prozessen stattfindet ist die Ausführung und das Endergebnis (der Berechnung) gleich der sequenziellen Ausführung der Prozesse:

$\begin{gathered} {P_1}\parallel {P_2}\parallel ..\parallel {P_n} \Rightarrow {P_1};{P_2};..;{P_n} \hfill \\ {P_1}\parallel {P_2} \Rightarrow {P_1};{P_2} \Rightarrow {P_2};{P_1}! \hfill \\ \end{gathered}$

Paralleler Prozess

Prozesserzeugung und Synchronisation

Ein neuer paralleler Prozess kann durch den entsprechenden Prozesskonstruktor erzeugt werden
Geschieht dies innerhalb eines Prozesses P_i so wird dessen Prozessausführung blockiert bis alle Teilprozesses des parallelen Prozessen terminiert sind!

Forking

Ein neuer Prozess P_j kann mittels Forking erzeugt werden (Aufspaltung des Kontrollflusses, so auch von einem anderen Prozess P_i) ohne dass ein ausführender Prozess auf die Terminierung des Parallelprozesses warten muss:

\begin{gathered} {P_1};{\fork}{P_2};{P_3} = {P_1};{P_3}\parallel {P_2} \hfill \\ {\fork}{P_1};{\fork}{P_2};{P_3} = {P_1}\parallel {P_2}\parallel {P_3} \hfill \\ \end{gathered}

Paralleler Prozess

Prozesskonstruktor

\begin{gathered} P = {P_1};{\fork}{P_2} {\quad} \Leftrightarrow \hfill \\ {\mathtt{FORK}} \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_1} \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_2} \hfill \\ {\mathtt{\quad}}.. \hfill \\ {\mathtt{\quad}}{{\mathtt{i}}_n} \hfill \\ \end{gathered}

Paralleler Prozess

Zeitliches Modell

\begin{gathered} P = {P_1}\parallel {P_2}\parallel ..\parallel {P_n} \hfill \\ {P_1} = ({i_{1,1}}:{t_{1,1}};{i_{1,2}},:{t_{1,2}};..) \cdots {P_n} = ({i_{n,1}}:{t_{n,1}};{i_{n,2}}:{t_{n,1}};..),{\text{ mit}} \hfill \\ {t_{i,1}} < {t_{i,2}} < .. < {t_{i,m}}{\text{ f\"u r jeden Prozess mit }}m{\text{ Instr}}{\text{. und }} \hfill \\ t(P) = [{t_1},{t_2}] = [{t_{1,1}},{t_{1,q}}] \cup [{t_{2,1}},{t_{2,r}}] \cup .. \cup [{t_{n,1}},{t_{n,s}}] \hfill \\ {t_1} = \min \{ {t_{1,1}},{t_{2,1}},..,{t_{n,1}}\} \hfill \\ {t_2} = \max \{ {t_{1,q}},{t_{2,r}},..,{t_{n,s}}\} \hfill \\ T=t_2-t_1 \hfill \\ \end{gathered}

Prozessfluss

Prozessflussdiagramme

Der Prozessfluss in einem parallelen System kann durch Übergangs- und Terminierungsdiagramme dargestellt werden. (wie bereits im seq. Fall gezeigt wurde).
Eingehende Kanten (Pfeile) des Graphen beschreiben den Start eines Prozesses, ausgehende Kanten die Terminierung.

Prozessfluss

Beispiel

Seq({
  function (id) print('P1: I am '+id) end,
  function (id) print('P2: I am '+id) end, 
})
Par({
  function (id) print('P3: I am '+id) end,
  function (id) print('P4: I am '+id) end, 
})
print('after')

Metaprozesse

Die Menge aller Prozesse {P₁, P₂,..} eines Systems bilden ein Meta-Prozess P. Dieser terminiert wenn alle enthaltenen (Sub-) Prozesse terminiert sind.

Kommunizierende Sequenzielle Prozesse

Definition 3.
Prozesskommunikation bedeutet Synchronisation zwischen Prozessen

Prozess Synchronisation tritt auf, wenn der Berechnungsfortschritt eines oder mehrerer Prozesse von dem Verhalten der anderen Prozesse abhängt.

Zwei Arten der Prozessinteraktion benötigen Synchronisation:
- Wettbewerb und Konfliktlösung, z.B. um geteilte Ressourcen → Konkurrenz
- Kooperation → Parallelität

Kommunizierende Sequenzielle Prozesse

Parallele Datenverarbeitung bedeutet:
- Distribution: Partitionierung und Verteilung von Eingabedaten auf verschiedene Prozesse, die jeweils ein Teilergebnis berechenen → Kooperation
- Zusammenführung: Zusammenführen von Teilergebnissen → Kooperation

Kommunizierende Sequenzielle Prozesse

Paralleler Datenzugriff

Daten werden gespeichert und befinden sich in Speicherelementen: einzelne Register oder adressierbare RAM Speicher.
Mehrere Prozesse müssen je nach Datenabhängigkeit parallel auf geteilte Ressource Speicher zugreifen, um
- Eingabedaten zu lesen und
- Zwischenergebnisse auszutauschen und
- Ausgabedaten schreiben zu können.

⇔ Wettbewerb

Nebenläufiger Zugriff auf geteilte Ressourcen ist ein Konflikt der aufgelöst werden muss → Mutual Exclusion Problem

Geteilte Ressourcen und Kommunikation

Queue

Ressourcen-Konflikt und Synchronisation kann mit Daten-Queues/Channels aufgelöst werden.
Eine Queue hat im wesentlichen zwei Operationen die synchronisierten Zugriff ermöglicht (FIFO Speicher):

Definition 4.

OP WRITE(Q,x): Q[y,z,...],x → Q[x,y,z,...]
OP READ(Q):    Q[x,y,z] → Q[x,y],z

Geteilte Ressourcen und Kommunikation

Eine Queue hat einen Prozess P_W der Daten in die Queue schreiben kann und einen Prozess P_R der Daten aus der Queue lesen kann.

Synchronisation

Queue Q=[]      ⇔ state=EMPTY: Lesender Prozess wird blockiert bis Q ≠ []
Queue Q=[x,y,z] ⇔ state=FULL:  Schreibender Prozess wird blockiert bis state(Q) ≠ FULL

Geteilte Ressourcen und Kommunikation

Channel

Ähnlich wie eine Queue mit Einschränkungen:
- Puffergröße: 0 (!!) → Kein Wettbewerb! / 1
- Nur zwei Prozesse zugelassen: Ein Leser und ein Schreiber
- Rendezvous Synchronisation: Schreibender Prozess wird blockiert bis lesender Prozess read Operation ausführt

Beispiel

Par({
  function () 
    local x=ch:read();
    log('hello '+x);
  end,
  function () 
    ch:write('world');
  end
},{
  ch=Channel(1)
})

Geteilte Ressourcen und Kommunikation

Prozessmehrfachauswahl

Ein Prozess kann in seinem Kontrollfluss nur eine blockierende Anweisung gleichzeitig aufrufen, d.h. in unserem Prozessmodell nur einen folgenden elementaren Prozess aktivieren.
Häufig ist es aber notwendig dass der Prozessfluss in mehrere Elementarprozesse mit einer blockierenden Operation aufspaltet (z.B. Lesen eines Channels) von dem dann nur ein Prozess zur Ausführung kommt (der erste der bereit wurde) → Konditionaler Fork
Der aufgespaltete konditonale Prozessfluss wird dann wieder zusammengeführt (join) → Klassische IO Selektion

Auswahlprozesskonstruktor:

\begin{gathered} P = ({p_{1,cond}} \to {p_{1,do}}|{p_{2,cond}} \to {p_{2,do}}|..) \hfill \\ \mathtt{ALT} \hfill \\ \mathtt{\quad {i_{1,cond}}?{i_{1,do}}} \hfill \\ \mathtt{\quad {i_{1,cond}}?{i_{1,do}}} \hfill \\ \mathtt{\quad ..} \hfill \\ \end{gathered}

Prozessmehrfachauswahl

Beispiel ALT

Par({
  function () 
    local x;
    Alt({
      {function () x=ch1:read() end,  Konditonaler Prozess 1 
       function () print('Got channel 1') end},  Ereignis Prozess 1
      {function () x=ch2:read() end,  Konditonaler Prozess 2
       function () print('Got channel 2') end },  Ereignis Prozess 2
      {function () x=ch3:read() end,  Konditonaler Prozess 3
       function () print('Got channel 3') end },  Ereignis Prozess 3
    ]);
    log('Got data '+x);
  },
  function () 
    ch1:write('world');
  end
],{
  ch1=Channel(),
  ch2=Channel(),
  ch3=Channel()
})

Prozessmehrfachauswahl

CSP Modell und Prozessalgebra

Prozessalgebra nach dem “Communicating Sequential Processes” (CSP) Modell von Hoare:
Beschreibung des Verhaltens von Prozessen als Reaktion auf Ereignisse → Synchronisierter Prozessfluss
Kommunikation sind Ereignisse
Algebraisch wird die Entwicklung von Prozessen durch Ereignisse x,y, .. beschrieben

Definition 5.
Ereignis : $x$

Prozess : $P$

Ein Prozess der nach einem Ereignis $x$ sich wie Prozess $P$ verhält: $x \rightarrow P$

Folge von Ereignissen: $x \rightarrow (y \rightarrow P)$

Parallele Ausführung: $P \parallel Q$

Alphabet eines Prozesses: $\alpha P={x_1,y_2,..}$

CSP Modell und Prozessalgebra

Ein Alphabet eines Prozesses beschreibt die möglichen Ereignisse die als Vorbedingung eines Prozesses auftreten können: $\alpha P={x_1,y_2,..}$
Rekursive Definition von Prozessen: $\mu X : A \bullet F(X)$
Mit $A$ : Alphabet des Prozesses (Ereignismenge)

Beispiel

Ein Taktprozess:

\begin{gathered} A = \alpha CLOCK = \{ tick\} \hfill \\ CLOCK = \mu X:\{ tick\} \bullet (tick \to X) \hfill \\ \end{gathered}

Ein Snackautomat:

\begin{gathered} A = \alpha SNACK = \{ coin,choco\} \hfill \\ SNACK = \mu X:\{ coin,choco\} \bullet (coin \to (choc \to X)) \hfill \\ \end{gathered}

CSP Modell und Prozessalgebra

Deterministische oder nichtdeterministische Auswahl von Ereignissen und Prozessentwicklungen sind typisch für parallele Systeme!

Definition 6.
Auswahl: $(x \rightarrow P | y \rightarrow Q)$

→ D.h. entweder tritt Ereignis $x$ ein und der Auswahlprozess verhält sich wie $P$ , oder es tritt das Ereignis $y$ ein und der Prozess verhält sich wie $Q$ .

Es gilt: $\alpha(x \rightarrow P | y \rightarrow Q) = \alpha P = \alpha Q$

→ D.h. die Ereignismenge ist immer ${x,y}$ .

CSP Modell und Prozessalgebra

Beispiel Snackautomat mit Choco und Kaffee

VMCT = \mu X \bullet coin \to (choc \to X|coffee \to X)

Beispiel Alt Prozessauswahlkonstruktor

\begin{gathered} ALT = \mu X:\{ i{n_1}.x,i{n_2}.x, \cdots , ou{t_1}.x,ou{t_2}.x, \cdots \} \bullet ( \hfill \\ i{n_1}.x \to ({P_1} \to (ou{t_1}.x \to X))| \hfill \\ i{n_2}.x \to ({P_2} \to (ou{t_2}.x \to X))| \cdots ) \hfill \\ \end{gathered}

CSP Modell und Prozessalgebra

Spur

Eine Spur (Trace) des Verhaltens eines Prozesses beschreibt die zeitliche Abfolge von Ereignissen in die ein Prozess verwickelt war.
Spruen werden von Beobachtern aufgenommen (Monitor).

Definition 7.
Spur: $< x, y, .. >$

Leere Spur: $<>$

Spurbindung: $<a,b> \hat{} <c,d>$ → $<a,b,c,d>$

Beispiele

\begin{gathered} < coin, choc, coin, choc, coin, coin, coffee > \hfill \\ < tick, tick, tick> \hfill \\ \end{gathered}

CSP Modell und Prozessalgebra

Spurenmenge

Es gibt eine Vielzahl von möglichen Spuren in einem Einzel- und Multiprozesssystem!
Jede Spur kann zudem in Teilspuren zerlegt werden beginned mit der leeren Spur.
Spurenmenge ⇔ Zustandsraumdiagramm!

Beispiele

\begin{gathered} traces(STOP) = \{ < > \} \hfill \\ traces(coin \to STOP) = \{ < > , < coin > \} \hfill \\ traces(\mu X \bullet tick \to X) = \{ < > , < tick > , < tick,tick > ,..\} = \{ tick\} * \hfill \\ traces(\mu X \bullet coin \to choc \to X) = \{ < > , < coin > , < coin,choc > ,..\} \hfill \\ = \{ s|\exists n \bullet s \leqslant < coin,choc{ > ^n}\} \hfill \\ \end{gathered}

CSP Modell und Prozessalgebra

Kommunikation

Definition 8.
$\alpha c(P)=\{v|c.v \in \alpha P \}$ : Menge aller Nachrichten eines Prozeses P

$(c!v \rightarrow P)=(c.v \rightarrow P)$ : Ausgabe eines Wertes über den Kanal c (Schreiben)

$(c?x \rightarrow P)$ : Eingabe eines Wertes über einen Kanal c (Lesen)