Linda und JavaSpaces

Lindaund

JavaSpaces

Linda

Motivation / Einführung

Parallele Kommunikationsstrukturen

Beschränkungen Probleme

Linda

Motivation / Einführung

Parallele Kommunikationsmuster

Beschränkungen Probleme

Message Passing

Prozess

Prozess

Prozess

Prozess Prozess

send

send

send

rcv

rcv

rcv

send

send

sendrcv

rcvrcv

send

rcv

Message Passing

Prozess

Prozess

Prozess

Prozess Prozess

send

send

send

rcv

rcv

rcv

send

send

sendrcv

rcvrcv

send

?

Linda

wurde in den 80er Jahren von Prof. David Gelernter an der YaleUniversity entwickelt.

stellt ein alternatives Paradigma der parallelen Programmierung dar.

beruht auf dem Konzept des tuple-space …

tuple-space

zentraler Datenspeicher zur Kommunikation ähnlich schwarzem Brett Prozesse können Tupel erzeugen, Tupel

lesen und Tupel entfernen jeder Prozess hat vollen Zugriff auf den

tuple-space sämtliche Kommunikation läuft durch

erstellen und lesen der Tupel ab es gibt keine weiteren

Kommunikationsmechanismen wie z.B. Nachrichten

Linda

Satz sprachunabhängiger Kommunikationsoperationen zur Interaktion mit dem tuple-space.

4 Grundoperationen: in out rd eval

tuple-space - Operationen

out - Erzeugen eines Tupels

tuple-spaceProzess

out

tuple-space - Operationen

rd - Lesen eines Tupels

tuple-spaceProzess

rd

tuple-space - Operationen

in - konsumierendes Lesen eines Tupels

tuple-spaceProzess

in

Kommunikationsschema

tuple-space

Prozess

Prozess

Prozess

Prozess Prozess

in

out

rd

out

rd

Hello World

Prozess 1:out("Hello World!");

Prozess 2:in(? msg);printf("%s", msg);

Hello World

Prozess 1:out("Hello World!");

Prozess 2:in(? msg);printf("%s", msg);

tuple-space

Hello World

Prozess 1:out("Hello World!");

Prozess 2:in(? msg);printf("%s", msg);

tuple-space

in

Gesucht wird ein Tupel, dessen erste n Komponenten mit value1, …, valuen

übereinstimmen letzte n Komponenten mit den Typen von

var1, … varn übereinstimmen

Die Werte der letzten n Einträge werden in den Variablen var1, …, varn abgelegt.

Blockiert bis gesuchtes Tupel vorhanden

in(value1,…, valuen, ? var1, …, ? varn);

rdp, inp

Prädikatoperationen: rdp – inp:

versuchen spezifizierten Wert zu lesen, liefern 1 im Erfolgsfall, 0 sonst.

nicht blockierend

variierende Ausführungsgeschwindigkeiten der beteiligten Systeme Nichtdeterminismus

eval

eval – Erzeugung eines neuen Prozesses: verhält sich wie out, legt jedoch einen neuen

Prozess an um den Wert des einzufügenden Tupels zu berechnen.

out(x, f(x));

1. der Wert y von f(x) wird bestimmt

2. das Tupel (x, y) wird dem tuple-space hinzugefügt

3. die Anweisung kehrt zurück

eval(x, f(x));

1. es wird ein neuer Prozess p erzeugt

2. die Anweisung kehrt zurück3. p berechnet y und fügt das

Tupel (x, y) dem tuple-space hinzu

Linda

Motivation / Einführung

Parallele Kommunikationsmuster

Beschränkungen Probleme

Master-Worker Schema

Master:

for (int i = 2; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

TSMaster

Worker

Worker

Worker

Master-Worker Schema

TSMaster

Worker

Worker

Worker

Master:

for (int i = 2; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Master-Worker Schema

TSMaster

Worker

Worker

Worker

Master:

for (int i = 2; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Master-Worker Schema

TSMaster

Worker

Worker

Worker

Master:

for (int i = 2; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Master-Worker Schema

TSMaster

Worker

Worker

Worker

Master:

for (int i = 2; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Datenstrukturen

Pseudo-Datenstrukturen durch Nutzung von Bennenungsschemata:

out(1, firstelt)out(2, secondelt)

out(n, nthelt)

Vektor:

out(1, 1, elem11) … out(1, n, elem1n)out(2, 1, elem21) … out(2, n, elem2n)

out(n, 1, elemn1) … out(1, n, elemnn)

… …

Matrix:

…

Vektorberechnung

int lmain() {for (int i = 0; i < VEC_SIZE; i++) {

eval( i, combine(a[i], b[i]) );}

return 0;}

Prozess Datenelement

Datenelement = Tupel

1 eval-Anweisung pro Datenelement

1:1

Message Passing

Emulation von Kanälen im tuple-space: Queue-Struktur - FIFO Nummerierung der Nachrichten spezielle Tupel zur Verwaltung des aktuellen

Zählerstandes von Anfang und Ende der Queue

void send_msg(int msg) {int tail_index;in("my_channel", "tail", ? tail_index);out("my_channel", tail_index + 1, msg);out("my_channel", "tail", tail_index + 1);

}

Message Passing

void send_msg(int msg) {int tail_index;in("my_channel", "tail", ? tail_index);out("my_channel", tail_index + 1, msg);out("my_channel", "tail", tail_index + 1);

}

int rcv_msg() {int head_index;in("my_channel", "head", ? head_index);in("my_channel", head_index, ? msg);out("my_channel", "head", head_index + 1);

}

Entwurfstechnik

1. Erstelle paralleles Programm. Nutze Kommunikationstechnik (message passing, eval-Tupel, master-worker…), die sich intuitiv anbietet.

2. Transformiere Programm ggf. (Performance) hin zu effizienterem Muster.

Vorteil:Alle Programmtransformationen können innerhalb von Linda realisiert werden.

Linda

Motivation / Einführung

Parallele Kommunikationsmuster

Beschränkungen Probleme

Endloses Blockieren

rd, in blockieren u.U. endlos: es ist nicht möglich einen Timeout zu

spezifizieren testet man mittels der Prädikatoperationen

rdp und inp kommt es zum busy-waiting und man läuft Gefahr, das gewünschte Tupel zu verpassen

while ( !inp(t) ) {} while ( !inp(t) ) {sleep(some_time);

}

unnötig hohe Systembelastung erhöhte Gefahr des Verpassens

Black-Box Effekt

i.A. sehr schwierig Überblick über den Inhalt des tuple-space zu gewinnen

Wie können mehrere (alle) Tupel zu einer Suchanfrage gefunden werden?

TS

?

Black-Box Effekt

rd("search", ? value1);

rd("search", ? value2); ?TS

?

Black-Box Effekt

rd("search", ? value1);

rd("search", ? value2);

nicht korrekt!

aufgrund des Nichtdeterminismus kann zweimal das gleiche Tupel ausgewertet werden

TS

?

Black-Box Effekt

Lösung:1. alle relevanten Tupel konsumieren2. Tupel zurückschreiben

void read_all() {int counter = 0, value;int tuples[SIZE];

while ( inp("entry", ? value) ) {tuples[counter] = value;counter++;

}for (int i = 0; i < counter; i++) {

out("entry", tuples[i]);}

}

Black-Box Effekt

Lösung:1. alle relevanten Tupel konsumieren2. Tupel zurückschreiben

void read_all() {int counter = 0, value;int tuples[SIZE];

while ( inp("entry", ? value) ) {tuples[counter] = value;counter++;

}for (int i = 0; i < counter; i++) {

out("entry", tuples[i]);}

}

Black-Box Effekt

Lösung:1. alle relevanten Tupel konsumieren2. Tupel zurückschreiben

void read_all() {int counter = 0, value;int tuples[SIZE];

while ( inp("entry", ? value) ) {tuples[counter] = value;counter++;

}for (int i = 0; i < counter; i++) {

out("entry", tuples[i]);}

}

Black-Box Effekt

Problem:Was, wenn der tuple-space während des Auslesens modifiziert wird?

Black-Box Effekt

Lösung: wechselseitiger Ausschluss bei

Schreibzugriffen Nachbildung von Semaphorfunktionalität

in("write_mutex");…out("write_mutex");

P(write_mutex);…V(write_mutex);

Black-Box Effekt

Lösung: void read_all() {in("write_mutex");

int counter = 0, value;int tuples[SIZE];

while ( inp("entry", ? value) ) {tuples[counter] = value;counter++;

}

for (int i = 0; i < counter; i++) {out("entry", tuples[i]);

}

out("write_mutex");}

Aufstauung

nicht benötigte Tupel sammeln sich im TS an

Black-Box Effekt: schwer Übersicht zu behalten garbage collection mühsam

TS

Teilausfall

Verteilte Umgebung (LAN, Internet, etc.):

mit dem tuple-space verbundene Systeme können jederzeit ausfallen

aufgrund der Struktur des tuple-space Modells hat ein Prozess keine Kenntnis über andere aktive Prozesse

ein Ausfall wird nicht bemerkt

Teilausfall

TSMaster

Worker

Worker

Worker

Master:

for (int i = 0; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Teilausfall

TSMaster

Worker

Worker

Worker

Master:

for (int i = 0; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Teilausfall

TSMaster

Worker

Worker

Master:

for (int i = 0; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Master-Worker Schema

TSMaster

Worker

Worker

Master:

for (int i = 0; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number)) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Master-Worker Schema

TSMaster

Worker

Worker

Master:

for (int i = 0; i < MAX; i++) {out("task", i);

}

bool result;int number;for (int i = 0; i < MAX; i++) {

in("result", ? number,? result);

}

Worker:

int number;while (!done) {

in("task", ? number);if (is_prime(number) {

out("result", number,TRUE);

}else {

out("result", number,FALSE);

}

Zusammenfassung

Linda bietet ein klares Anweisungssystem zur Entwicklung paralleler Programme.

Eine Vielzahl an Kommunikationsmustern ist realisierbar.

Die Prozessgranularität ist kontrollierbar.

Prozesse sind schwach gekoppelt. Einsatz in verteilten Umgebungen Einige

Probleme im praktischen Einsatz.

JavaSpaces

Einführung

Adressierte Probleme

Weitere Möglichkeiten

JavaSpaces

Einführung

Adressierte Probleme

Weitere Möglichkeiten

JavaSpaces

von Sun Ende der 90er Jahre entwickelt.

keine Linda Implementierung im strengen Sinn

greift tuple-space Gedanken auf – transportiert diesen in die Welt der Objekte

Entwicklung im Rahmen von Jini

JavaSpaces

Transaktionen Leases (Lebenszeiten) mehrere spaces Objektorientierung – starke Typisierung

Erweiterung bzw. Modifikation der tuple-space Idee:

Entry

Einträge im tuple-space: TupelEinträge im (java)space: Objekte… die das Interface Entry implementieren.

import net.jini.core.entry.Entry;

public class Message implements Entry {

public String content;

public Message() {}

}

Grundoperationen

out - write in - take rd - read rdp - readIfExists inp - takeIfExists

Message msg = new Message();msg.content = "Hello World!";space.write(msg, null, Lease.FOREVER);

space

Prozess

Grundoperationen

out - write in - take rd - read rdp - readIfExists inp - takeIfExists

Message template = new Message();Message result;result = (Message)space.take(template, null, Long.MAX_VALUE);

space

Prozess

take und read

erhalten als Anfrage ein Objekt mit vorbelegten Feldern.

liefern einen Eintrag zurück, der vom Typ des übergebenen Objektes ist und dessen Felder die vorbelegten Werte aufweisen.

Classname template = new Classname();template.field = valuespace.take(template, null, Long.MAX_VALUE);

liefert einen Eintrag zurück, der vom Typ Classname ist und dessen Objektfeld field, den Wert value aufweist

JavaSpaces

Einführung

Adressierte Probleme

Weitere Möglichkeiten

spezifizierbare Wartezeiten

read und take können eine maximale Wartezeit übergeben bekommen

nach Ablauf dieser Wartezeit kehren sie erfolglos zurück

lösen Problem des "endlosen Blockierens"

space.read(template, null, 1000);

kehrt nach Ablauf von 1000 Millisekunden erfolglos zurück

Leases

ordnen einem Eintrag eine "Lebenszeit" zu, nach derer der betreffende Eintrag automatisch entfernt wird

werden beim Erstellen eines Eintrags angegeben

können u.U. erneuert werden

Leases

Es wird ein Lease von 1000 Millisekunden angefordert.

write liefert den tatsächlich erteilten Lease zurück.

der erteilte Lease kann durchaus kürzer als der angeforderte sein

Lease l = write(msg, null, 1000);

Transaktionen

fassen mehrere Aktionen zu einer atomaren Ausführungseinheit zusammen:entweder es werden alle zusammengefassten Aktionen ausgeführt – oder keine von ihnen

fällt ein teilnehmendes System während der Durchführung einer Transaktion aus, so wird der Effekt aller unter dieser Transaktion durchgeführten Änderungen rückgängig gemacht Lösung des Problems "Teilausfall"

Transaktionen

1. Arbeitsauftrag abholen

2. Ergebnis zurückschreiben

Master-Worker Schema mit Transaktionen:

1 Transaktion

Transaktionen

spaceMaster

Worker

Worker

Worker

Transaktions-manager

Transaktionen

spaceMaster

Worker

Worker

Worker

Transaktions-manager

Transaktionen

spaceMaster

Worker

Worker

Transaktions-manager

Transaktionen

spaceMaster

Worker

Worker

Transaktions-manager

Transaktionen

spaceMaster

Worker

Worker

Transaktions-manager

JavaSpaces

Einführung

Adressierte Probleme

Weitere Möglichkeiten

Mehrere spaces

Ein Prozess kann mit mehreren spaces verbunden sein.

Transaktionen können mehrere spaces umspannen.

bsplw. können Einträge so auf sichere Art und Weise zwischen zwei spaces verschoben werden.

space

Prozess

space

Verteilung ausführbarer Inhalte

take, read liefern bei einer Anfrage ein Objekt zurück, das vom Typ des übergebenen Anfrage-Objektes ist …

also insbesondere auch Objekte einer Unterklasse des Anfrage-Objektes

Was, wenn diese Unterklasse auf dem anfragenden System nicht vorhanden ist? sie wird mittels Java RMI auf das anfragende

System übertragen.

Verteilung ausführbarer Inhalte

space

Prozess

Prozess

SpecialMessage msg = new SpecialMessage();space.write(msg, null, Lease.FOREVER);

Message template = new Message();Message msg;msg = (Message)space.take(template, null,

timeout);

msg

… SpecialMessage extends Message …

Verteilung ausführbarer Inhalte

space

Prozess

Prozess

SpecialMessage msg = new SpecialMessage();space.write(msg, null, Lease.FOREVER);

Message template = new Message();Message msg;msg = (Message)space.take(template, null,

timeout);

msg

Verteilung ausführbarer Inhalte

space

Prozess

Prozess

SpecialMessage msg = new SpecialMessage();space.write(msg, null, Lease.FOREVER);

Message template = new Message();Message msg;msg = (Message)space.take(template, null,

timeout);

Class not known: SpecialMessage

Verteilung ausführbarer Inhalte

space

Prozess

Prozess

SpecialMessage msg = new SpecialMessage();space.write(msg, null, Lease.FOREVER);

Message template = new Message();Message msg;msg = (Message)space.take(template, null,

timeout);

SpecialMessage.class

Command Pattern

Master-Worker Pattern mit Verteilung ausführbarer Inhalte:

Art der durchgeführten Berechnung lässt sich nachträglich ändern.

Verteilung der Berechnungsroutinen via Java RMI.

Im Rahmen konventioneller Architektur: Änderung der Berechnung Änderung des Programmcodes aller Worker

Zusammenfassung

JavaSpaces führt die Ideen von Linda weiter.

Viele der innerhalb von Linda auftretenden Probleme werden gelöst Praxistauglichkeit des Systems in einer verteilten Umgebung

Bislang noch kein Durchbruch was die Akzeptanz im praktischen Einsatz anbelangt.

Literatur

[1] David Gelernter. Generative communication in Linda. ACM Trans. Program. Lang. Syst., 7(1):80–112, 1985. ISSN 0164-0925.

[2] Steven L. Halter. Javaspaces Example by Example. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2001. ISBN 0-1306-1916-7.[3] Sanjay Mahapatra. Introducing javaspaces. Java Developer’s Journal, 5(9),

2000. URL http://jdj.sys-con.com/read/36482.htm.[4] Sun Microsystems. Le - Jini distributed leasing specification, . URL http://java.sun.com/products/jini/2.0.2/doc/specs/html/lease- spec.html#1034275.[5] Sun Microsystems. Java RMI specification, . URL http://java.sun.com/j2se/1.4.2/docs/guide/rmi/spec/rmiTOC.html.[6] Sun Microsystems. Java object serialization specification, . URL http://java.sun.com/j2se/1.4.2/docs/guide/serialization/spec/serialTOC.html.

Literatur

[7] Dave Sag. Jini as an enterprise solution. URL http://www.onjava.com/pub/a/onjava/2001/01/04/Jini_enterprise.html.

[8] Daniel H. Steinberg. Jini: Out of the bottle and into the box. URL http://www.onjava.com/pub/a/onjava/2004/12/29/jini.html.[9] Antony I. T. Rowstron und Alan Wood. Solving the linda multiple rd problem. In COORDINATION ’96: Proceedings of the First International Conference on Coordination Languages and Models, pages 357–367, London,UK, 1996. Springer-Verlag. ISBN 3-540-61052-9.[10]Gian Pietro Picco und Amy L. Murphy und Gruia-Catalin Roman. LIME: Linda meets mobility. In International Conference on Software Engineering, pages 368–377, 1999.[11]Nicholas Carriero und David Gelernter. Linda in context. Commun. ACM, 32(4):444–458, 1989. ISSN 0001-0782.[12] Nicholas Carriero und David Gelernter. How to write parallel programs: a

guide to the perplexed. ACM Comput. Surv., 21(3):323–357, 1989. ISSN 0360-0300.

Literatur

[13]Eric Freeman und Ken Arnold und Susanne Hupfer. JavaSpaces Principles, Patterns, and Practice. Addison-Wesley Longman Ltd., Essex, UK, 1999.

ISBN 0-2013-0955-6.[14]M. Chen und Y. Choo und J. Li. Crystal: from functional description to efficient parallel code. In Proceedings of the third conference on Hypercube concurrent computers and applications, pages 417–433, New York, NY, USA, 1988. ACM Press. ISBN 0-89791-278-0.[15]R. Loogen und Y. Ortega-Mallén und R. Peña-Marí. Parallel Functional Programming in Eden. Journal of Functional Programming, 15(3):431–475, 2005.[16]Gang Chen und Zhonghua Yang und Hao He und Kiah Mok Goh. Coordinating multiagents using javaspaces. In ICPADS, pages 63–68, 2002.[17] Jim Waldo. The Jini architecture for network-centric computing. Commun.

ACM, 42 (7):76–82, 1999. ISSN 0001-0782.[18] Manel Guerrero Zapata. Javaspaces: A distributed computing model. Technical report, Mobile Networks - Nokia Research Center, Itämerenkatu 11-13 FIN-00180 Helsinki, FINLAND.

Vortrag / Seminararbeit online

Seminararbeit:

http://www.informatik.uni-marburg.de/~heidtm/files/seminararbeit.pdf

Vortrag:

http://www.informatik.uni-marburg.de/~heidtm/files/vortrag.ppt