Referat zum Seminar:

Thema:

Datum:



Inhaltsverzeichnis:


  1. Einleitung

  2. Erklärung des Linda-Modells
    1. Tupel-Raum
    2. Primitiven
    3. Tupel-Typen
    4. Matching

  3. Linda Implementierungen

  4. Erweiterungen des Modells bei objekt-orientierten Sprachen
    1. Objekt-Orientierung bei Tupeln und Tupel-Räumen
    2. Kommunikation
      1. Orthogonalität von Sender und Empfänger
      2. Kommunikatiionsprimitiven
    3. mehrere Tupel-Räume
    4. Beispiel: Das Philosophen Problem
    5. Tupel-Raum Manager
    6. Matching-Erweiterungen
    7. Vererbung und Wiederverwendung

  5. Schlußbemerkung

  6. Literaturverzeichnis


1. Einleitung

Zuerst soll allgemein das Linda-Modell vorgestellt und dessen Bestandteile erklärt werden.
Danach folgt ein Überblick über die verschiedenen Linda Implementierungen, Erweiterungen des Modells und eine Betrachtung des Modells unter dem objekt-orientierten Gesichtspunkt.

Bei parallel ablaufenden Programmen löst man ein Problem im allgemeinen durch Zerlegen des Problems in kleine Teile, welche dann auf die vorhanden Ressourcen verteilt werden und jeweils für sich gelöst bzw. berechnet werden. Am Schluß werden die einzelnen Teile bzw. die Teillösungen wieder zusammengefügt und somit eine Gesamtlösung des Problems erstellt.
Um aber dieses Aufteilen und Zusammenfügen auf der programmiersprachlichen Ebene koordinieren zu können, benötigt man entsprechende Konstrukte bzw. Primitiven. Das heißt als Programmierer muß man in der Lage sein können, mehrere Threads zu erzeugen, sowie diese auch zu koordinieren.
An diesem Punkt kommt das Linda-Modell ins Spiel.

2. Erklärung des Linda-Modells

Vorgestellt wurde das Modell vor einigen Jahren von David Gelernter.
Linda ist ein Modell bzw. ein Paradigma zur parallelen Programmierung, welches eine Semantik zur Koordination und Kommunikation zwischen mehreren Prozessen anbietet. Dabei wird nicht betrachtet, wie einzelne Teile eines Problems berechnet werden, sondern man betrachtet nur die Erzeugung von Prozessen und deren Koordination.
Ein paralleles Programm läßt sich immer in zwei Teile aufteilen. Einerseits die Berechnung und andererseits deren Kommunikation. Die Koordinationsprimitiven werden, wie schon gesagt, durch das Linda-Modell beschrieben. Die Berechnung hingegen wird durch die Gast-Sprache, in welche das Modell eingebettet wird, ermöglicht.
Insbesondere ist Linda also kein Werkzeug, sondern wie schon gesagt ein Modell und kann somit in vielen verschiedenen Formen implementiert bzw. realisiert werden.

2.1 Tupel-Raum

Linda besteht aus wenigen einfachen Operationen, welche den Tupel-Raum charakterisieren.
Alle Prozesse können über den Tupel-Raum auf die gleichen Daten oder Nachrichten zugreifen. Der Tupel Raum stellt somit den gemeinsamen Speicher dar.
Realisiert wird der Tupel-Raum im allgemeinen mittels Shared Memory bzw. Distributed Shared Memory Konzepten oder aber auch durch Message Passing. Beim Message Passing werden Datenobjekte zwischen den einzelnen Prozessen hin- und hergeschickt, während beim Shared Memory Konzept die Prozesse direkt auf die gleichen Datenobjekte zugreifen.

2.2 Primitiven

Linda bzw. Implementierungen von Linda umfassen mindestens die vier grundlegenden Operationen out , in , read und eval .

Diese vier genannten Operationen sind in jeder Linda-Implementierung zu finden. Zusätzlich finden sich in den meisten Implementierungen noch die Operationen inp und readp , welche die Prädikatversionen von in bzw. read darstellen.

Obwohl die Prädikatversionen vom ursprünglichen Linda-Modell propagiert werden, findet man diese Operationen nicht in allen Implementierungen von Linda.
Es gibt auch Ansätze inp und readp , durch eine einzige neue Operationen zu ersetzen. Ein Beispiel hierfür ist die die collect -Primitive (siehe "Global Synchronisation in Linda "). Collect setzt die Verwendung von mehreren Tupel-Räumen voraus (siehe Kapitel 4.1), wo- bei jeweils alle Tupel, welche zum gegebenen Template passen, in einen Ziel-Tupel-Raum verschoben werden. Die Anzahl der verschobenen Tupel wird dabei zurückgegeben.

2.3 Tupel-Typen

Tupel sind im allgemeinen von passiver Natur, z.B. wenn ein Tupel mit out(t) in den Tupel-Raum eingefügt wird, handelt es sich um ein passives Datum. Bei der eval Operation wird das Tupel jedoch erst passiv, wenn nach dem Einfügen in den Tupel-Raum alle Elemente ausgewertet worden sind. Erst dann kann es von einem anderen Prozeß angesprochen bzw. angefordert werden. Solange noch die Auswertungsprozesse ausgeführt werden, handelt es sich um ein aktives Tupel. Gerade hier liegt die Besonderheit von eval , da diese Funktion somit zum Erzeugen von Threads bzw. Prozessen dient.
Ein Konstrukt um beispielsweise n Arbeiter-Prozesse zu erzeugen, würde in C/C++ Linda folgendermaßen aussehen:
   for (i = 0; i < n; ++i)
      eval("Arbeiter", i, work());
Hierbei würden also implizit n neue Prozesse erzeugt und abgearbeitet.

2.4 Matching

Wie schon angesprochen, können mit den Operationen in bzw. read bestimmte Tupel angefordert werden.
Ein Tupel aus dem Tupel Raum wird als passend zu einem Template, also der Tupel-Beschreibung einer in bzw. read Operation, angesehen, wenn bestimmte Bedingungen bezüglich der Elemente des Templates bzw. Tupels erfüllt sind.
Hierbei werden zwei Arten von Feldern unterschieden. Dies sind einerseits actual Felder und andererseits formal Felder. Felder mit expliziten Werten sind actual . Formal Felder hingegen sind eine Art Wildcard für alle Werte des entsprechendes Typs.
Eine dieser Bedingungen ist nun die gleiche Feldanzahl von Template und Tupel. Weiterhin müssen die Felder jeweils den gleiche Typ haben, wobei allerdings nicht beide Felder formal sein dürfen. Sind beide Felder actual müssen natürlich auch die jeweiligen Werte identisch sein.
Bei objekt-orientierter Betrachtung ergeben sich noch zusätzliche Matching-Regeln, siehe hierzu Kapitel 4.6.

3. Linda Implementierungen

Das Linda-Modell bzw. die Operationen lassen sich in nahezu jede Programmiersprache einbetten. Beispiele hierfür sind C bzw. C++, Eiffel, Smalltalk, Lisp, Simula, Prolog, Fortran, Pascal, Modula-2 oder sogar Postscript.
Bei einigen Sprachen sind Modifikationen am Compiler bzw. Runtime-System notwendig um eine Linda-Variante der Sprache zu erstellen. Je nach Sprache kann dies jedoch auch durch hinzufügen einer neuen Bibliothek erreicht werden. Bei Eiffel-Linda beispielsweise, wurde nur eine neue Klasse mit den genannten Operationen erstellt, welche benutzt werden kann um in Eiffel-Linda parallel ablaufende Programme schreiben zu können.
Mit dem Linda-Modell erweitert man ein Sprache zwar zu einer neuen parallelen Variante dieser Sprache, allerdings bietet Linda keine Möglichkeit zur Kontrolle der Auslastung der Ressourcen des Systems. D.h. es ist nicht möglich, explizit Ressourcen für bestimmte Programmteile bzw. Prozesse zu definieren. Allerdings ist dies ist sowieso ein allgemeines Problem bei paralleler Programmierung bzw. parallelen Abläufen.
Bezüglich der verwendeten Hardware läßt sich Linda natürlich an viele verschiedene Systeme anpassen, seien es nun Transputer, Mehrprozessorrechner (Hypercubes) oder vernetzte Workstations.

4. Erweiterungen des Modells bei objekt-orientierten Sprachen

In den einzelnen Implementierungen findet man allerdings nicht unbedingt immer nur das grundlegende Linda-Modell, sondern Varianten des Modells. Modifikationen oder Erweiterungen werden vorgenommen, um Ineffizienzen oder Probleme des ursprünglichen Modells zu beheben bzw. zu verringern. Betrachtete Aspekte sind hier vorwiegend Modifikationen von Linda-Primitiven, wie z.B. die schon erwähnte collect -Primitive, die Möglichkeit mit mehreren Tupel-Räumen zu arbeiten, Tupel-Raum-Manager, neue Kommunikationsprimitiven, Verbesserung von objekt-orientierten Linda-Varianten.
Die Verwendung des ursprünglichen Linda-Modells, insbesondere bezüglich der Tupel-Raum-Kommunikation, weist Unzulänglichkeiten auf, wenn es in eine objekt-orientierte Sprache eingebettet wird. Möglichkeiten diese Unzulänglichkeiten zu lösen, werden von Matsuoka und Kawai in ihrer Veröffentlichung "Using Tuple Space Communication in Distributed Object-Oriented Languages " vorgestellt, welche im Folgenden (Kapitel 4.1-4.4) genauer betrachtet werden sollen.

4.1 Objekt-Orientierung von Tupeln und Tupel-Räumen

Bei der Tupel-Raum-Kommunikation kommunizieren die Objekte mittels Tupeln, also liegt es nahe auch die Tupel als Objekte zu betrachten. Die Funktionalität der Tupel kann somit in gleicher Weise wie bei anderen Objekten im System definiert werden. Hieraus ergeben sich einige Vorteile; zum einen kann ein Objekt dann Nachrichten entgegennehmen, auch wenn es zu dem Zeitpunkt des Nachrichtenempfangs noch nicht die Fähigkeit hat, diese zu verstehen. Hieraus resultiert eine Zeit-Unabhängigkeit bei der Nachrichtenverarbeitung, d.h. ein Objekt kann Nachrichten entgegennehmen und erst später, wenn es in der Lage ist diese zu verstehen, weiterverarbeiten. Die dynamische Veränderung der Handlungsweise eines Objekt ist hierbei von Bedeutung.
Weiterhin ist eine transparente Übertragung von Nachrichten möglich. Ein Objekt kann also Nachrichten weiterleiten, ohne volles Wissen über den Inhalt bzw. die Bestandteile der Nachricht haben zu müssen (transparent delegation ).
Durch die Betrachtung von Tupel-Räumen als Objekte ergibt sich weiter die Möglichkeit, diese dann als Elemente eines Tupels zu benutzen (-> Tupel-Räume als first-class Objekte). Garbage Collection von Tupeln und Tupel-Räumen ist auch möglich. Hierdurch kann dann ein Tupel bzw. Tupel-Raum welcher schon einmal bei einer bestimmten Kommunikation benutzt wurde bei einer anderen Kommunikaiton wieder benutzt werden.

4.2 Kommunikation

4.2.1 Orthogonalität von Sender und Empfänger

Im Originalmodell erzeugt ein Sender beispielsweise ein Tupel durch Angabe der Tupel-Spezifikationen in einer out -Operation, ein Empfänger hingegen gibt ein Template mit den gesuchten Tupeln bzw. deren Spezifikationen in einer in - oder read -Operation an. Hierbei ist eine Orthogonalität zwischen Sender und Empfänger nicht mehr gegeben, da der Sender das Tupel nur implizit erzeugt. Ein Sender kann das Tupel an andere weiterleiten, welche die Spezifikationen des Tupels nicht kennen müssen um es weiterzuverarbeiten. Auf der Empfängerseite hingegen müßten die Spezifikationen allen Empfänger bekannt sein, was nicht vernünftig realisierbar ist.
Um diese Unzulänglichkeit des ursprünglichen Modells zu beheben, wird das Modell in der Weise modifiziert, daß sowohl Sender als auch Empfänger Tupel in den Tuple-Raum einfügen, wobei zwischen Sender-Tupeln und Empfänger-Tupeln unterschieden wird.
Matching geschied duch gegenseitige Überprüfung der Tupel auf Gleichheit. Ein passendes Tupel wird dann an den Empfänger zurückgegeben und kann somit unter den Empfängern verteilt werden.

4.2.2 Kommunikationsprimitiven

Bei der Benutzung von Tupel-Raum Mangern (siehe Kapitel 4.7), werden die Vorteile der Othogonalität deutlich.
Bei Verwendung des Originalmodells könnten Arbeiter nur mit dem Manager kommunizieren, also nur indirekt mit dem Auftraggeber. Hierdurch ergibt sich somit eine hierarchische Struktur, welche allerdings je nach Anwendungsfall restriktiv ist und somit nicht unbedingt die effizienteste Möglichkeit darstellt.
Aber eben diese Art der Kommunikation ergibt sich, wenn man das Linda-Modell ganz naiv in eine objektorientierte Sprache einbettet, da hier oft die Methode des Message Passing zur Kommunikation benutzt wird. Beim Message Passing kann man normalweise eine Nachricht nur an ein explizites Ziel schicken (1 zu 1 Kardinalität), eine Art Broadcasting ist also nicht direkt möglich. Der Manager muß also jeden Arbeiter einzeln ansprechen, dies setzt natürlich auch voraus, daß er auch alle Arbeiter kennt. Es muß dann also auch sichergestellt werden, daß ein neuer Arbeiter bzw. der Ausfall eines Arbeiters dem Tupel-Raum-Manager bekannt gemacht wird.
Beim alten Modell ist man nicht flexibel genug um auf natürliche Weise komplexe Interaktionen zwischen Objekten ausdrücken zu können.
Bessere Kommunikationsprimitiven sind also nötig. Eine effektivere Form der Kommunikation ist die direkte Kommunikation, welche die beschriebene Orthogonalität zwischen Sender und Empfänger voraussetzt. Der Manager teilt im voraus den Arbeitern eine Teilspezifikation der Tupel mit, welche er in der Kommunikation mit dem Auftrageber benutzen will. Hierdurch werden die Arbeiter in die Lage versetzt, Nachrichten welche an den Manager gehen, aber für den Arbeiter gedacht sind zu erkennen und diese somit direkt zu erhalten und verarbeiten zu können ohne dabei aber komplettes Wissen über die Tupel zu haben, welche in der Kommunikation zwischen Auftraggeber und Manager benutzt werden.

4.3 mehrere Tupel-Räume

Die Motivation für die Verwendung von mehreren Tupel-Räumen liegt darin, daß bei nur einem Tupel-Raum dieser sozusagen zum Flaschenhals des Systems wird, wenn sehr viele Tupel durch ihn geschleust werden müssen. Durch Verwendung von mehreren Tupel-Räumen wird somit die Performance des Systems gesteigert.
Insbesondere können dann Tupel-Räume dynamisch erzeugt werden, wenn sie benötigt werden.
Weiterhin hat man bei mehreren Tupel-Räumen mehr Spielraum bezüglich der Namensgebung von Elementen der Tupel. Wenn man beispielsweise zwei Gruppen von Objekten hat, welche nicht miteinander kommunizieren, müßte man bei nur einem Tupel-Raum trotzdem bestimmte Konventionen bezüglich der Namensgebung einhalten, was aber eigentlich nicht nötig bzw. sinnvoll ist.
Weiter bieten mehrere Tupel-Räume eine größere Sicherheit gegen Objekte, welche Tupel mit Falschinformationen einfügen könnten oder auch wichtige Tupel aus dem Tupel-Raum herausnehmen könnten. Bei mehreren Räumen erhöht sich die Sicherheit dadurch, daß ein bestimmter Tupel-Raum nur der Gruppe von kommunizierenden Objekten bekannt ist, nicht aber anderen Objekten welche nicht an dieser Kommunikation teilnehmen.

4.4 Beispiel: Das Philosophen Problem

Um die Effektivität der objekt-orientierten Tupel-Raum-Kommunikation deutlich zu machen soll das Philosophen Problem (nach E. Dijkstra) betrachtet werden.
Philosophen werden als aktive Objekte modelliert die entweder denken oder essen. Sie sind Instanzen der Klasse Philosopher . Demgegenüber sind Gabeln statische Entitäten und Instanzen der Klasse Fork , welche sich die Philosophen aneignen können. Es existieren n Instanzen von Philosopher und Fork . Die Philosophen müssen die Gabeln selber zwischen sich aufteilen, wobei die Philosophen nicht direkt miteinander kommunizieren. Allerdings wird die Verfügbarbeit an alle Philosophen verbreitet.
Die Gabeln sind Elemente eines Tupels. Das i -te Element eines Tupels ist eine Instanz von Fork falls sie erhältlich ist, ansonsten nil. Der i -te Philosoph benutzt die i -te und (i +1 mod n )-te Gabel zum essen. Die Philosophen kommunizieren über den Tupel-Raum aTS .
Zu Beginn des Programms wird ein einzelnes Tupel, dessen Elemente Instanzen von Fork sind, in den Tupel-Raum aTS eingefügt. Jeder aktive Philosoph führt dann das folgende Programm (Smalltalk-Version) aus:

     action       (for the ith philosopher)
       | tuple leftFork rightFork |
       [
         ...
         "dine"
         ...
         tuple <- (a tuple whose ith and (i+1)th elements are
                   Formal ofClass: Fork and the rest are Formal any).
         aTS get: tuple.
         leftFork <- tuple at: i.
         rightFork <- tuple at: i+1 \\ n.
         tuple at: i put: nil; at: i+1 \\ n put: nil.
         aTS put: tuple.
         ...
         "dine with leftFork and rightFork"
         ...
         tuple <- (a tuple whose ith and (i+1)th elements are nil
                   and the rest are Formal any).
         aTS get: tuple.
         tuple at: i put: leftFork; at: i+1 // n put: rightFork.
         aTS put: tuple.
       ] loop
(get entspricht hierbei der normalen in -Operation und put entspricht out , siehe "Using Tuple Space Communication in Distributed Object-Oriented Languages ")

In der ersten Hälfte der Schleife enthält das empfangene Tupel die von den Philosophen angeforderten Gabeln. Nach herausnehmen der Gabeln (und ersetzen durch nil ) wird es wieder in den Tupel-Raum aTS eingefügt. Nach dem Essen mit den Gabeln wird das Tupel wider empfangen und die Gabeln werden wieder zurückgelegt, damit sie ein anderer Philosoph benutzen kann. Die Atomariät der Tupel-Raum Kommunikation garantiert das beide Gabeln gleichzeitig erhalten werden, somit ist ein Deadlock nicht möglich.
Das Beispiel macht deutlich wie einfach und vorallem wie natürlich das Philosophen Problem gelöst werden kann.

4.5 Tupel-Raum Manager

Insbesondere bei Verwendung von mehreren Tupel-Räumen findet man auch sogenannte Tupel-Raum Manager, welche die Kommunikation zwischen den Prozessen koordinieren.
Ein Auftraggeber übergibt ein zu lösendes Problem an einen Tupel-Raum Manager, welcher eine Menge von Arbeitern zur Verfügung hat und das Problem unter den Arbeitern aufteilt. Wenn alle Teile berechnet wurden, wird die Lösung an den Auftraggeber übermittelt (siehe Kapitel 4.2.2).
Weitere Aufgaben eines Tupel-Raum-Managers sind Matching, Gargabe Collection sowie Handhabung von weitergehenden Zugriffen auf den Tupel-Raum bzw. auf die Tupel.
Je nach Implementierung wird nicht nur ein Manager sondern mehrere Manager eingesetzt.

4.6 Matching bei Objekt-Orientierung

Bei Objekt-Orientierung, also der Betrachtung von Tupeln, Templates und Tupel-Räumen als Objekte, ergeben sich zwangsläufig Erweiterungen bezüglich Matching.
Ein Tupel bzw. Objekt kann dann als passend zu einem Template angesehen werden, wenn einerseits die schon genannten Bedingungen zutreffen, aber weiterhin kann dann auch ein Objekt als passend zu einem Template angesehen werden, wenn das Objekt mehr Datenelemente beinhaltet als das Template. Bedingung ist dann, daß die Klasse des Objektes von der Klasse des Templates abgeleitet sein muß und natürlich die jeweiligen Elemente vom Typ her zueinanderpassen.
Je nach Linda-Implementierung besteht auch die Möglichkeit, verschiedene (selbstdefinierte) Matching-Algorithmen zu wählen. Insbesondere bei selbstdefinierten Matching-Algorithmen, welche je nach Applikation eingesetzt werden können, ist es auch möglich innerhalb von einer Operation auf mehr als nur ein Objekt zugreifen zu können (siehe "The Object Space Approach ", A. Polze).
Allerdings ist Matching immer eine schwierige Angelegenheit, beispielsweise wenn mit komplexen Objekten, wie z.B. linked lists, gearbeitet wird, wenn ein Feld eines Objektes das Objekt selber referenziert oder wenn zwei Felder das gleiche Objekt referenzieren. Und ganz allgemeinen sind natürlich auch Zeiger problematisch. Bei einigen Linda-Varianten werden dem Programmierer deshalb Restriktionen bezüglich der Verwendung solcher Objekte auferlegt. In C++ Linda sind z.B. Zeiger verboten und nur in Spezialfällen erlaubt.
Aber nicht nur die aufgezeigten Beispiele sind schwierig zu handhaben, Matching stellt grundsätzlich ein zentrales Problem bei Linda-Implementierungen dar, da effizientes Matching bei komplexen Objekten schwieriger zu realisieren ist.

4.7 Vererbung und Wiederverwendung

Durch die Betrachtung von Tupeln und Tupel-Räumen als Objekte werden natürlich die aus der Objekt-Orientierung bekannten Aspekte der Vererbung und Wiederverwendung ermöglicht. Beispielsweise lassen sich dann neue Tupel-Räume von existierenden ableiten, womit sich Tupel-Räume mit spezieller Funktionalität erzeugen lassen.

5. Schlußbemerkung

Durch Einbettung von Linda bzw. der dargestellten Linda-Primitiven in eine Programmiersprache erhält man eine neue, parallele Variante dieser Sprache. Die Einbettung wird im Allgemeinen durch Verwendung einer objekt-orientierten Sprache wie z.B. C++ oder Eiffel erleichtert, da die Klassifikation von Tupeln bzw. Templates weniger aufwendig ist.
In objekt-orientierten Sprachen werden bzw. sollten Tupel, Tupel-Räume wie auch Templates als First-Class Objekte behandelt werden. Hierdurch lassen sich dann Tupel oder Templates wie jedes andere Objekt in der Sprache handhaben. Die aus der Objekt-Orientierung bekannten Aspekte wie Vererbung, Datenkapselung und Wiederverwendung werden somit ermöglicht.
Allerdings hat die Verwendung einer objekt-orientierten Sprache nicht nur Vorteile. Die Art der verwendeten Kommunikationsprimitiven hat großen Einfluß auf die Performance und Funktionaliät der Linda-Implementation. Wie schon gezeigt, findet man in manchen objekt-orientierten Sprachen Message Passing Verfahren, welche allerdings in einigen Situationen, wie z.B. bei einem gemeinsamen Zugriff auf den Objektzustand, restriktiv sind. Doch auch solche Restriktionen können vermindert bzw. aufgelöst werden, wie dies in einigen Linda-Varianten gezeigt wird.
Doch das Linda-Modell und dessen verschiedene Implementierungen bieten immer noch Raum für Erweiterungen und Verbesserungen, welches nicht zuletzt durch die Forschungen auf diesem Gebiet unterstrichen wird.

6. Literaturverzeichnis



[an error occurred while processing this directive]