Upload
ghada
View
64
Download
0
Embed Size (px)
DESCRIPTION
Linda und JavaSpaces. Linda. Motivation / Einführung Parallele Kommunikationsstrukturen Beschränkungen Probleme. Linda. Motivation / Einführung Parallele Kommunikationsmuster Beschränkungen Probleme. Message Passing. Prozess. Prozess. send. send. send. rcv. rcv. Prozess. rcv. - PowerPoint PPT Presentation
Citation preview
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