Global Computing Seminar WS 2005/2006 Lehrstuhl für Informatik II Prof. Dr.-Ir. J.-P. Katoen Softwaremodellierung und Verifikation Ahornstr. 55 - 52074

Global ComputingSeminar WS 2005/2006

Lehrstuhl für Informatik IIProf. Dr.-Ir. J.-P. Katoen

Softwaremodellierung und Verifikation Ahornstr. 55 - 52074 Aachen

Klaim / X-Klaim

Lutz Franzkowiak219 447

Thomas Mock219 538

Betreut von Professor J.-P. Katoen

Klaim / X-Klaim

2/54

Lutz Franzkowiak / Thomas Mock

Motivation / Einleitung

LINDA

KLAIM (als Erweiterung von LINDA)

X-KLAIM (“KLAIM in Java”, Erweiterung von KLAIM)

Zusammenfassung

Gliederung des Vortrages

Klaim / X-Klaim

3/54


Technologischer Fortschritt in Bereichen Telekommunikation und Computertechnik immer stärkere und schnellere Vernetzung von Computersystemen

Vermehrte Verbreitung von global computers = Rechnernetzwerke, welche

Dynamisch rekonfigurierbar sind,

Aus vielen teilweise mobilen Komponenten bestehen, und

Auf Basis von unvollständigen Informationen arbeiten können

Beispiel : Internet (WWW)


Klaim / X-Klaim

4/54


Bedingungen bzw. Anforderungen für Anwendungen :

Skalierbarkeit:

große Anzahl von Benutzern und Netzwerkknoten

Heterogenität:

Verschiedene Betriebssysteme und Anwendungen müssen untereinander kommunizieren

Autonomie:

Unabhängige Verwaltung von Subnetzwerken

Adaptierbarkeit:

Auf unvorhersehbare Änderungen muss reagiert werden können

Mobilität:

Prozesse, Code und Daten müssen innerhalb des Netzwerkes verschiebbar sein


Klaim / X-Klaim

5/54


Entwicklung von Kalkülen und Kernel Sprachen

Hier:

KLAIM

X-KLAIM (als Erweiterung von KLAIM)

Entwicklung dieser Programmiersprachen wurde v.a. beeinflußt durch Prozess-Algebren Calculus) und das Koordinationsmodell LINDA


Klaim / X-Klaim

6/54


LINDA ist keine Programmiersprache

Koordinationsmodell, stellt Operationen zur Erzeugung (und Verwaltung) von Prozessen bereit

(asynchrone) Kommunikation unter Prozessen einer verteilten Anwendung

Diese lassen sich unter traditionellen Programmiersprachen (etwa C, C++) einbetten Entstehung von neuen parallelen Programmiersprachen wie C-LINDA

LINDA

Klaim / X-Klaim

7/54


Koordination mittels eines globalen Speicherbereiches: Tupel-Space

Interaktion von Prozessen durch Ablage (out-Operation), und Entnahme (in-Operation) von Daten

TUPEL - SPACE

Klaim / X-Klaim

8/54


Enthält eine beliebige, ungeordnete Anzahl von Tupeln (als atomare Einheiten des Speicherbereiches)

Tupel = geordnete Reihe bzw. Liste von typisierten Feldern (z.B. (“p”, 5, false) )

Zwei Arten von Feldern:

Actual fields (z.B. Konstanten, Prozesse oder Ausdrücke)

Formal fields (z.B. Variablen: !identifier)

Das erste Feld enthält üblicherweise einen logischen Bezeichner bzw. Namen zur Identifikation des Tupels

NICHT notwendigerweise eindeutig

TUPEL - SPACE

Klaim / X-Klaim

9/54


Tupel-Space besitzt Eigenschaften eines Assoziativspeichers

Zugriff auf die gespeicherten Daten über einen Werte- bzw. Strukturvergleich: pattern matching

Zwei Tupel bilden ein “matching”, wenn

Sie die gleiche Anzahl an Feldern besitzen, und

Die entsprechenden Feldern denselben Typ besitzen

Wenn “matching” – Vorgang erfolgreich, so wird eine (passende) Substitution für die formalen Parameterwerte gewonnen

PATTERN-MATCHING

Klaim / X-Klaim

10/54


In(s): wird benutzt, um eine Datentupel aus dem Speicher zu “konsumieren” Auswahl durch pattern-matching mit Template s

Read(s): entspricht der Operation In(s), aber: ausgelesenes Datentupel bleibt weiterhin im globalen Speicher

Out(t): Ablage von Datentupeln (Übergabe der Felder als Parameterwerte t)

Eval(t): ähnlich wie Out(t), aber: Tupel können neben Datenfeldern auch einen Prozess als Komponente enthalten (aktive Tupel)

Abspaltung von neuen Prozessen, welche nach Ausführung in Datentupel übergehen

OPERATIONEN

Klaim / X-Klaim

11/54


Kein direkter Datenaustausch zwischen Prozessen

Sondern: Interprozesskommunikation über gemeinsam genutzten globalen Speicherbereich (Tupel-Space)

Durch den sogenannten Sender wird eine “Nachricht” generiert, und in den Speicher geschrieben

Wird unabhängig vom erzeugenden Prozess im Speicher gehalten, bis ein Empfänger-Prozess die Nachricht ausliest

GENERATIVE KOMMUNIKATION

Klaim / X-Klaim

12/54


Zeitliche Entkopplung (time uncoupling):

Ablage von Datentupeln erfolgt asynchron, dh unabhängig von Empfangsbereitschaft anderer Prozesse

Zwei Prozesse müssen nicht zur gleichen Zeit aktiv sein

Räumliche Entkopplung (space uncoupling):

Zur Ablage von Daten werden keine Infos über Identität oder Allokation von Empfängerprozessen benötigt

Entkopplung des Ziels (destination uncoupling):

Kommunikation ist asynchron und anonym

Sender muss keine Kenntnis über Empfänger oder Gebrauch von Daten besitzen

GENERATIVE KOMMUNIKATION

Klaim / X-Klaim

13/54


Nachteile von LINDA:

unzureichende Skalierbarkeit und Modularität

Datentupel aus unterschiedlichen Kontexten können vermischt werden

Keine restriktiven Speicherbereiche, auf welche nur ausgewählte Untermengen von Prozessen zugreifen können

KLAIM als Erweiterung von LINDA, u.a. mehrere verteilte Tupel-Spaces

Vorgehen: Einführen von Prozesskalkülen steigender Komplexität, welche schrittweise um bestimmte Eigenschaften von KLAIM erweitert werden

Warum KLAIM ?

Klaim / X-Klaim

14/54


cKLAIM (coreKLAIM) als Varianate des -Calculus

Prozess-Mobilität

Asynchrone Kommunikation

Lokalitäten (anstelle von kanalbasierter Kommunikation)

cKLAIM

Klaim / X-Klaim

15/54


Netz = endliche Menge von Knoten (nodes)

Knoten = geordnetes Paar l::C l: enthält die Adresse l einer Lokalität

C: parallele Komponente an der Lokalität l : Prozesse oder Daten

Restriktion: durch die Notation (l)N wird der Gültigkeitsbereich der Lokalität l auf N eingeschränkt (analog zur Restriktion unter Calculus)

cKLAIM - Syntax

Klaim / X-Klaim

16/54


Ein Prozess P kann aus dem Nullprozess nil, und mittels vier Aktionen aufgebaut werden

Aktions-Praefixe

Parallele Komposition

Rekursion

cKLAIM - Syntax

Klaim / X-Klaim

17/54


Aktionen: weitgehend analog zu LINDA

out: Ablage von Daten

eval: Erzeugung von neuen Prozessen

in: Entnahme von Daten

newloc: Generierung von neuen Knoten

Übergabe einer Lokalität l als Parameter

cKLAIM - Syntax

Klaim / X-Klaim

18/54


Zwei Netze N1 und N2 sind struktuell kongruent, wenn diese intuitiv dasselbe Netz beschreiben – Notation: N1 N2

Regeln entsprechen weitgehend analogen Regeln aus der Beschreibung des -Calculus

cKLAIM – Struktuelle Kongruenz

Klaim / X-Klaim

19/54


Abgeschlossenheit bzgl. Kommutativität (COM) und Assoziativität (ASSOC) für Komposition von Netzen

Neutralität des Nullprozesses bzgl. paralleler Komposition (ABS)

Prozessvariablen können durch ihre entsprechende Definition ersetzt werden (PRINV)

Parallelität von Komponenten (Prozessen) lässt sich zu Parallelität bezüglich Knoten transformieren (CLONE)

cKLAIM – Struktuelle Kongruenz

Klaim / X-Klaim

20/54


Durch die Reduktions-Relation wird das Verhalten von Prozessen beschrieben

z.B. (NEW): durch die Anweisung new(l’) wird lediglich eine Restriktion bzgl. l’ dem Netz hinzugefügt

cKLAIM – Operationale Semantik

Klaim / X-Klaim

21/54


(PAR): eine Reduktionsschritt bezüglich eines Teilnetzes ist entsprechend auf das gesamte Netz zu übertragen

(STRUCT): auf zwei Netze, welche struktuell kongruent sind, lassen sich dieselben Reduktionsschritte anwenden

cKLAIM – Operationale Semantik

Klaim / X-Klaim

22/54


KLAIM (microKLAIM) als Erweiterung von cKLAIM, insbesondere um weitere Eigenschaften von LINDA :

Tupel-Räume

Pattern-matching

KLAIM

Klaim / X-Klaim

23/54


Aktive Elemente der Kommunikation (Argumente von out) werden als Tupel bezeichnet

Tupel = Folge von actual fields (Ausdrücke, Lokalitäten oder Lokalitäts-Variablen)

KLAIM - Syntax

Klaim / X-Klaim

24/54


Durch die Menge der gespeicherten Tupel wird der Tupel-Space eines Knoten bestimmt

Auswahl von Tupeln (analog zu LINDA) über patterns (bzw. Templates) – bestehen aus formal und actual fields

KLAIM - Syntax

Klaim / X-Klaim

25/54


Templates T müssen zunächst ausgewertet werden, bevor sie zur Auswahl von Tupeln eingesetzt werden können

Berechnung aller Werte von enthaltenen Ausdrücken

Templates, welche Variablen in actual fields enthalten, können NICHT ausgewertet werden

Notation: [T]

KLAIM - Syntax

Klaim / X-Klaim

26/54


Zusätzliche Aktion read(T)@l : Auslesen von Tupeln, ohne diese aus dem Tupel-Space zu entfernen (analog zu LINDA)

KLAIM - Syntax

Klaim / X-Klaim

27/54


Regeln für pattern-matching werden analog zu LINDA formuliert

Ein Tupel bildet ein “matching” zu einem Template, wenn

diese dieselbe Anzahl an Feldern enthalten,

und die entsprechenden Felder denselben Typ besitzen

Wenn der “matching”-Vorgang erfolgreich ist, so wird eine Substitution für die formalen Parameterwerte in T gewonnen

KLAIM - Semantik

Klaim / X-Klaim

28/54


Definition für struktuelle Kongruenz wird von cKlaim übernommen

Abweichungen für die Reduktions-Relation (vgl. oben):

(OUT): ein Tupel, welches sich aus der Auswertung von t ergibt, wird wird dem Tupel-Space an l’ hinzugefügt

(IN): zusätzliche Bedingung: Template T muss auswertbar sein

(READ): für neue Operation read – entspricht der Regel (IN), nur: ausgelesenes Tupel verbleibt im Tupel-Space des Zielknotens

KLAIM - Semantik

Klaim / X-Klaim

29/54


KLAIM als Erweiterung von LINDA:

Higher-order Kommunikation: Tupel können Prozesse als Komponenten enthalten

Allocation environments

Logische und physikalische Lokalitäten

KLAIM

Klaim / X-Klaim

30/54


Netz = parallele Komposition von Knoten (nodes)

Ein Knoten enthält einen Tupel-Raum, und eine endliche Menge von Prozessen

Zugriff auf Knoten über Lokalitäten:Physikalische Lokalitäten = Bezeichner, welche einen Knoten eindeutig identifizieren (z.B. Netzwerk-Adresse)

absolute Bedeutung

Logische Lokalitäten = symbolische (Alias)-Namen für Knoten (mit relativer Bedeutung bzgl. Knoten)

Reservierte Lokalität: self ermöglicht es Prozessen, auf den Knoten zuzugreifen, auf denen sie gerade ausgeführt werden

KLAIM - Syntax

Klaim / X-Klaim

31/54


Knoten werden dargestellt als Tripel der Form: s1::P

s1 = physikalische Lokalität

P = Menge der Prozesse

= allocation environment = partielle Abbildung aus der Menge der logischen Lokalitäten in die Menge der physikalischen Lokalitäten

Insbesondere gilt: (self) = s1 (entsprechend für JEDEN Knoten)

KLAIM - Knoten

Klaim / X-Klaim

32/54


KLAIM - Netz

Klaim / X-Klaim

33/54


Definition für struktuelle Kongruenz wird (mit leichten Anpassungen) übernommen

Reduktionsregeln: siehe Abbildung

KLAIM - Semantik

Klaim / X-Klaim

34/54


(NEW): wird durch neue Regel ersetzt

allocation environment für einen neuen Knoten ist vom erzeugenden Knoten abzuleiten

Ausnahme: Belegung für reservierte Variable self verweist auf den neu erzeugten Knoten

Mittels dieser Anweisung können “private Knoten” erzeugt werden:

Die physikalische Lokalität l eines neuen Knotens ist zunächst nur dem erzeugenden Knoten bekannt

Dh. ein Prozess von “ausserhalb” kann nur auf diesen Knoten zugreifen, wenn er die Lokalität des neuen Knotens vom Erzeuger “mitgeteilt” bekommt (z.B. durch Zugriff auf allocation environment)

KLAIM - Semantik

Klaim / X-Klaim

35/54


Bei der Auswertung von Tupeln werden Ausdrücke berechnet, und logische Lokalitäten werden auf physikalische Lokalitäten abgebildet

Auswertung von Prozessen = Substitution mit Abschluss

Abschluss = P{} (Prozess zusammen mit Allokation von Lokalitäten)

Hieraus ergibt sich ein Unterschied zwischen out und eval :

Durch die Anweisung out(P)@l wird insbesondere auch der Abschluss von P dem Tupel-Raum des Zielknoten l übergeben

Durch die Anweisung eval(P)@l wird ausschließlich der Prozess P (zur Ausführung) an der Lokalität l übergeben

KLAIM – Auswertung

Klaim / X-Klaim

36/54


KLAIM – Static Scoping Strategy

Klaim / X-Klaim

37/54


KLAIM – Dynamic Scoping Strategy

Klaim / X-Klaim

38/54


Einleitung

Grundlagen

Implementierung

Beispiel eines “Hello World”-Programms

X-Klaim : Gliederung

Klaim / X-Klaim

39/54


Was ist X-Klaim?

X-Klaim = eXtended-Klaim

Programmiersprache für verteilte Systeme

Erweiterung von Klaim

Klaim wird erweitert um:

High-Level Syntax für Prozesse

Variabeldeklarationen

erweiterte Operationen und Anweisungen (inp, readp)

objekt-orientierte Fähigkeiten

Funktionen zur sequentiellen und iterativen Programmierung

Klaim / X-Klaim

40/54


Syntax

Angelehnt an PASCAL

Codeblöcke werden von begin und end eingeschlossen

Semikolon ; als Befehlstrennungnicht als Befehlsabschluss

case-sensitive bei Schlüsselwörtern

nicht case-sensitive bei Namen von z.B. Prozessen oder Variabeln

Kommentarebeginnen mit #

enden immer am Zeilenende

begin instr1 ; instr2 end # syntaktisch korrekt

begin instr1 ; instr2 ; end # syntaktisch falsch

Klaim / X-Klaim

41/54


Ein einfacher Prozess

Beginnt mit den Schlüsselwort rec

der Name des Prozesses

die Parameterliste [ ]

der Codeblock

rec HelloProc[

param1 : paramtype, # call by value

param2 : ref paramtype # call by ref

]

begin

#...Befehle

end

Klaim / X-Klaim

42/54


lokale VariabelnSchlüsselwort: declare

Syntax: var name : type

const name

Standardtypen: int, str, bool

Der Typ einer Konstanten wird vom Compiler bestimmt.

rec HelloProc[ ]

declare

var serverName : str

begin

#...Befehle

end

Klaim / X-Klaim

43/54


Lokalitäten

logische Lokalitäten

Typ: logloc

besteht nur aus einem String

physikalische Lokalitäten

Typ: phyloc

String der Form: „IP:Port“

Obertyp: loc

var l : loc;var output : logloc;var server : phyloc;output := "screen";server := "192.168.100.200:9999";

Klaim / X-Klaim

44/54


Operationen

readp und inp

nicht blockierende Versionen

arbeiten wie read und in

liefern false zurück, wenn kein Tupel gefunden wurde

Timeout-Funktion within

if in(!x, !y)@l within 2000 then

# ... Ok

else

# ... Zeit abgelaufen

endif

Klaim / X-Klaim

45/54


Iterationen

unendliche Schleife kann entstehen

da immer das gleiche Tupel im Tupel-Space gefunden wird

inp ist keine Lösung, da

Zerstörungen des Tupel-Space nicht immer gewollt ist

und dann ein Wiedereinfügen nötig wäre

while readp(!i, !s)@self doout(i + 1, s)@l

enddo

Klaim / X-Klaim

46/54


Iterationen

forall liefert jedes Tupel nur genau einmal zurück

forall blockiert den Tupel-Space nicht

Änderungen am TS beeinflussen Ergebnis

Quelle:{(10, String1), (10, String1), (20, String2)}

Ziel : {(11, String1), (11, String1), (21, String2)}

forall readp(!i, !s)@self doout(i + 1, s)@l

enddo

Klaim / X-Klaim

47/54


Arten von Mobilität

weak mobility

Code, der sich an einer anderen Lokalität befindet, kann dynamisch gelinkt werden.

strong mobility

Ein Prozess kann seinen Code und seinen aktuellen Zustand zu einer anderen Lokalität verschieben und dort weiter ausführen lassen.

full mobility

Das gesamte Programm wird an eine andere Lokalität verschoben, inklusive aller Stacks, Namesräume und sämtlicher Ressourcen.

Klaim / X-Klaim

48/54


Mobilität von Prozessen

eval(P)@l startet Prozess P auf dem Knoten der Lokalität l

eval( P("string1", 10) )@loc

eval( in(!i)@self; out(i)@loc2 )@loc

Strong Mobility wird durch die Funktion go@l unterstützt

in(!i, !j)@self

go@loc

out(i, j)@self

Klaim / X-Klaim

49/54


Nodes

Knoten sind die Ausführungsbasis

Deklaration zwischen nodes und endnotes

Knoten werden definiert durch:

Name

Umgebung

lokale Prozesse

weitere Optionen wie z.B. den Port des Knoten

Klaim / X-Klaim

50/54


Hello World

„Hello World“- Programm auf einen Knoten

nodes

hello_world::{}

begin

print "Hallo Welt!"

end

endnodes

Klaim / X-Klaim

51/54


Hello World

„Hello World“- Programm auf einem Knoten mit Ausgabe durch einen weiteren Prozess

rec HelloProc[]

begin

print "Hallo Welt!"

end

nodes

hello_world2::{}

begin

eval(HelloProc())@self

end

endnodes

Klaim / X-Klaim

52/54


Hello World

„Hello World“- Programm mit einem Sender- und einem Empfänger- Knoten

rec HelloSenderProc[ dest : loc ]

begin

out("Hello World!")@dest

end

nodes

hello_sender::{receiver ~ localhost:11000}

port 10000

begin

eval(HelloSenderProc(receiver))@self

end

endnodes

Klaim / X-Klaim

53/54


Hello World

Der Empfänger-Knoten

nodes

hello_receiver::{}

port 11000

declare

var msg:str

begin

in(!msg)@self

print "received: " + msg

end

endnodes

Klaim / X-Klaim

54/54


Programmiersprache für verteilte Systeme

Syntax ähnlich der von PASCAL

Prozesse erstellen

Variabeln anlegen

Lokalitäten anlegen

Knoten erzeugen

Bewegen von Prozessen zwischen Knoten

Beispiel eine Programm auf einem und auf mehreren Knoten

Implementierung unter Java im Package KLava

Zusammenfassung

Documents

Global Computing Seminar WS 2005/2006 Lehrstuhl für Informatik II Prof. Dr.-Ir. J.-P. Katoen Softwaremodellierung und Verifikation Ahornstr. 55 - 52074