1539 lines
87 KiB
Plaintext
1539 lines
87 KiB
Plaintext
Spezifikation einer Sprache zur Erstellung paralleler Applikationen auf
|
||
verteilten Systemen
|
||
----------------------------------------------------------------------------
|
||
|
||
Abriss
|
||
1. Einfuehrung
|
||
2. TQ
|
||
2.1 Verteilter geteilter Speicher
|
||
2.2 Prozesse
|
||
2.3 Geteilte Datenobjekte und abstrakte Datentypen
|
||
2.4 Synchronisation
|
||
2.5 Hierarchische Objekte
|
||
2.6 Datenstrukturen
|
||
3. Ein Beispiel fuer ein Objekttyp und dessen Anwendung
|
||
3.1 Ein Objekttyp
|
||
3.2 Eine parallele Applikation in TQ
|
||
4. Eine verteilte Implementierung von TQ
|
||
4.1 Oberste Schicht: TQ Applikationsprogramme
|
||
4.2 Mittlere Schicht: RTS
|
||
4.3 Unterste Schicht: Sichere Uebertragung
|
||
4.4 Ein Vergleich mit einem auf RPC-basierenden Protokoll.
|
||
5. Leistung einer Applikation
|
||
5.1 Das "parallele Problem" des Verkaeufers.
|
||
5.2 Paralleles "All-pairs-shortest-Path" Problem
|
||
5.3 Successive Overrelaxtion
|
||
6. Andere Arbeiten
|
||
Zusammenfassung
|
||
|
||
Abriss :
|
||
|
||
Hier wird eine Sprache vorgestellt, die dazu dient, parallele Applikationen
|
||
fuer lose aneinander gekoppelte Systeme zu implementieren. Wie die meisten
|
||
Sprachen fuer verteilte Systeme hat man die Moeglichkeit, verschiedene
|
||
Prozesse zu erstellen und Gebrauch von der Existenz sog. geteilten Daten zu
|
||
machen. Solche Daten sind in Datenobjekte eingekapselt. Dies sind
|
||
Einrichtungen, die von Benutzern vollzogen wurden. Es handelt sich hierbei
|
||
um abstrakte Datentypen. Die Implementierung einer solchen Sprache bedarf
|
||
der Vorsicht, soweit es die physikalische Verteilung von Objekten zwischen
|
||
dem lokalen Speicher und dem Prozessor betrifft. Tatsaechlich ist es so, dass
|
||
eine Implementierung entweder reproduzierend arbeitet oder die
|
||
Zugriffszeiten auf die einzelnen Objekte werden herabgesetzt, damit die
|
||
Parallelitaet mehr gefoerdert wird.
|
||
|
||
Diese Abhandlung soll einen detaillierten Einblick in eine solche
|
||
Programmiersprache geben. Er soll zeigen, wie eine solche Sprache designed
|
||
wird und unter welchen Gesichtspunkten sie zu implementieren ist. Die hier
|
||
beschriebene Sprache ist mehr fuer den Anwendungsprogrammierer gedacht;
|
||
weniger fuer den Systemprogrammierer. Dies wird durch das entsprechende
|
||
Design und die Zielabsichten dokumentiert. Die Sprache ist typensicher und
|
||
hat eine reine Semantik. Es werden drei Beispiele fuer parallele
|
||
Applikationen auf verteilten Systemen vorgestellt. Eines wird detailliert
|
||
dargestellt, waehrend die beiden anderen mehr oberflaechlich abgehandelt
|
||
werden. Weiterhin wird beschrieben, wie Implementierungen aussehen koennen,
|
||
die auf einer "stabilen Uebertragung" aufbauen.
|
||
|
||
Die Leistungsmasseinheit dieses Systems wird durch drei parallele
|
||
Applikationen dargestellt. Die Masseinheit zeigt, dass entscheidende
|
||
Geschwindigkeitserhoehungen fuer alle drei Applikationen erzeugt werden
|
||
koennen. Abschliessend werden noch andere Sprachen vorgestellt, die auf
|
||
verteilten Systemen eingesetzt werden.
|
||
|
||
|
||
|
||
Die Kommunikation in lose verbundenen verteilten Computersystemen kann
|
||
dadurch beschleunigt werden, dass man parallele Applikationen einsetzt. Ein
|
||
weiterer Grund solche Applikationen zu entwerfen ist der, dass die
|
||
Attraktivitaet erhoeht wird, z.B. durch Verkuerzen der Antwortzeiten. Nimmt man
|
||
beispielsweise Amoeba so ist es moeglich, kurze Messages zwischen
|
||
SUN-Workstations ueber ein Ethernet-Protokoll innerhalb von 1.1 Millisekunden
|
||
zu uebertragen. Obwohl dies immer noch langsamer ist als die Kommunikation
|
||
auf Multicomputern (z.B. Hypercubes oder Transputeranlagen), ist es fuer eine
|
||
parallele Applikation noch schnell genug.
|
||
|
||
Kommen wir nun aber zu den verteilten Systemen zurueck. Solche Systeme sind
|
||
recht einfach zusammenzubauen. Sie bestehen aus Komponenten der alltaeglichen
|
||
Computerhardware. Diese befinden sich in einem Zusammenschluss, der aus
|
||
mehreren Workstations oder Mikroprozessoren besteht. Die einzelnen
|
||
Komponenten sind durch ein LAN miteinander verbunden. Hinzu kommt, dass
|
||
solche Systeme sehr einfach ausgebaut werden koennen. Es muessen hierfuer
|
||
lediglich neue Workstations oder Prozessoren in das Netz gehaengt werden. Der
|
||
Standort dieser ist unwichtig.
|
||
|
||
Wir wollen uns jetzt mit der Implementierung von parallelen Applikationen
|
||
auf verteilten Systemen beschaeftigen. Wir werden damit beginnen, einige
|
||
parallele Applikationen auf einem System zu implementieren, wobei wir eine
|
||
sogenannte sequentielle Sprache verwenden, welche durch das sog. "Message
|
||
Passing" fuer die Interprozesskommunikation erweitert wurde.
|
||
|
||
Wie wir herausfinden werden, haben solche Sprachen sehr viele Nachteile und
|
||
sind fuer Applikationsprogrammierer zu kompliziert.
|
||
|
||
Daher wurde eine neue Sprache fuer verteilte Systeme entwickelt. Das Ziel
|
||
dieser Programmiersprache ist es, verteilte Applikationen zu schreiben. Sie
|
||
ist nicht so sehr fuer die Systemprogrammmierung gedacht. Aus diesem Grund
|
||
ist sie einfach designed, ausdrucksstark und effizient mit einer klaren
|
||
Semantik. Zu einem spaeteren Zeitpunkt werden wir die Einzelheiten dieser
|
||
Sprache genauer vorstellen.
|
||
|
||
Prozesse koennen innerhalb dieser Sprache ueber verteilte Daten miteinander
|
||
kommunizieren, auch dann, wenn der Prozessor auf dem sie laufen sollen,
|
||
keinen physikalisch teilbaren Speicher hat. Die wichtigste Neuerung der
|
||
Sprache ist, dass sie die Moeglichkeit hat, auf verteilte Daten zuzugreifen.
|
||
Nicht wie im Falle des geteilten physikalischen Speichers (oder auch
|
||
verteilter geteilter Speicher), koennen auf verteilte Daten die
|
||
Zugriffsmoeglichkeiten koordiniert werden, indem man sie ueber 'high-level'
|
||
Funktionen einer bestimmten Benutzergruppe zuordnet. Wie wir sehen werden,
|
||
ist ein solches Handling sehr kompliziert und hat entscheidende
|
||
Auswirkungen.
|
||
|
||
Moechte man verteilte Daten auf einem verteilten System unterstuetzen, so hat
|
||
man Schwierigkeiten, dies mit dem eigentlichen verteilten Betriebssystem und
|
||
der dazu gehoerigen Sprache zu vereinbaren. Zu diesem Problem wurden schon
|
||
sehr verschiedene Ansaetze gemacht.
|
||
|
||
Das hier entwickelte System benutzt ein "zuverlaessiges
|
||
Uebertragungsprotokoll". Beide Einheiten, sowohl das Protokoll wie auch die
|
||
Integrierung mit dem eigentlichen verteilten Betriebssystem sind neue
|
||
Erkenntnisse, die auf dem Gebiet der Compilerforschung erzielt worden sind.
|
||
|
||
Die meisten der bereits existierenden Sprachen fuer verteilte Sprachen sind
|
||
Erweiterungen von bereits bestehenden Sprachen. Die hier vorgestellte
|
||
Sprache schliesst sich diesem Prinzip nicht an, weil es sich nicht um eine
|
||
sequentielle Sprache handelt, sondern um eine parallel arbeitende. Vielmehr
|
||
wurde versucht, sequentielle und verteilte Konstrukte (besonders im Bereich
|
||
der Datenstrukturen) miteinander zu verknuepfen. Hierbei galt es, den
|
||
maximalen Nutzen aus den beiden urspruenglichen Funktionalitaeten der
|
||
entwickelten Konzepte zu verwirklichen. Im allgemeinen sind die verteilten
|
||
Sprachen so konstruiert, dass einfache Zusaetze bereits bestehenden Sprachen
|
||
hinzuaddiert wurden, wobei die Neuerungen auf dem Gebiet der Parallelitaet
|
||
und Kommunikation stattfinden. Der hierbei auftretende Nachteil ist, dass nur
|
||
eine mangelhafte Integration der Zusaetze zu der Basissprache gefunden wurde.
|
||
Beispiel hierfuer ist das Verarbeiten eines Pointers innerhalb einer Message.
|
||
In den allermeisten Faellen wird diese vernachlaessigt. Die hier vorgestellte
|
||
Sprache loest dieses Problem dadurch, dass die Semantik klar definiert ist.
|
||
Ein weiterer Punkt ist, dass die Typenbindung aehnlich der von bereits
|
||
bekannten Sprachen ist. Daher ist es moeglich, dass z.B. C-Programmierer diese
|
||
Sprache genauso schnell lernen koennen wie Cobol-Programierer.
|
||
|
||
Ein wichtiges Ziel der Sprache war es, dass sie einfach zu benutzen ist. Die
|
||
meisten parallelen Applikationen werden ausserhalb der Computerwissenschaften
|
||
erstellt. Daher muss es moeglich sein, dass auch Leute mit der Sprache umgehen
|
||
koennen, die nicht aus dem Informatikfach kommen.
|
||
|
||
Die Sprache unterstuetzt keine 'low-level' Features, die nur fuer die
|
||
Systemprogrammierung von Bedeutung waeren. Hienzu kommt, dass das
|
||
Abstraktionsniveau sehr niedrig gehalten wurde. Die Effizienz der Sprache
|
||
wird hierdurch nicht beeinflusst. Evtl. entstehende Nachteile koennen durch
|
||
ein Optimierungsverfahren am Ende der Codegeneration wieder beseitigt
|
||
werden. Wie eine solche Optimierung aussieht, soll zu einem spaeteren
|
||
Zeitpunkt dargestellt werden.
|
||
|
||
Ein anderer Gesichtspunkt, der zu beruecksichtigen war, ist der des Debuggen.
|
||
Wie allgemein bekannt, ist das Debuggen auf verteilten Systemen sehr
|
||
schwierig. Bei der Realisierung eines Debugsystems reicht das Wissen einer
|
||
einzelnen Person in dem meisten Faellen nicht aus. Daher wurde fuer das
|
||
Debuggen ein betraechtlicher Zeitaufwand betrieben. Der wichtigste Punkt in
|
||
dieser Sprache ist die Typensicherheit. Die Sprachentwicklung erlaubt die
|
||
Implementierung, Fehler waehrend der Compilierungszeit zu erkennen. Dies
|
||
bezieht sich auch auf Laufzeitfehler, die in herkoemmlichen Sprachen eben
|
||
erst zur Laufzeit erkannt werden. Hinzu kommt noch das Feature, dass das
|
||
Laufzeitsystem der Sprache ein erweitertes Fehlererkennungssystem
|
||
beinhaltet.
|
||
|
||
Diese Abhandlung soll nun einen Ueberblick ueber eine Spezifikation einer
|
||
solchen Sprache geben, ueber die Implementierung der Sprache und ueber ihre
|
||
Leistungsfaehigkeit. Diese Abschnitte werden in einer geeigneten Struktur
|
||
hier aufgezeigt.
|
||
|
||
In Kapitel 2 werden wir die Sprache an sich beschreiben und erklaeren was uns
|
||
dazu bewogen hat, bestimmte Verfahren zu realisieren.
|
||
|
||
In Kapitel 3 werden wir ein Beispiel zeigen, an dem man sieht, wie eine
|
||
Applikation aussieht, die in dieser Sprache programmiert wurde.
|
||
|
||
In Kapitel 4 wird eine Implementierung der Sprache gezeigt. Diese
|
||
Implementierung legt eine "zuverlaessige Uebertragung" zu Grunde. Wir moechten
|
||
weiterhin beschreiben, wie eine Implementierung bei einer einfachen
|
||
Uebertragung aussieht. Wir moechten die Sprache kurz mit anderen
|
||
Implementierungen vergleichen, die RPC verwenden.
|
||
|
||
In Kapitel 5 werden wir Leistungsmessungen fuer verschiedene Applikationen
|
||
aufzeigen.
|
||
|
||
In Kapitel 6 vergleichen wir unsere Abhandlung mit verwandten Sprachen und
|
||
Systemen.
|
||
|
||
Schliesslich werden wir eine kurze Zusammenfassung geben.
|
||
|
||
2. TQ
|
||
|
||
TQ ist eine prozedurale, streng typgebundene Sprache. Sie enthaelt
|
||
sequentielle Anweisungen und die Ausdruecke sind traditionell gehalten und
|
||
sehr gut vergleichbar mit denen in Modula-2, obwohl sie nicht zu denen von
|
||
Modula-2 identisch sind. Die datenstrukturierten Merkmale von TQ jedoch sind
|
||
grundsaetzlich von denen in Modula-2 verschieden. TQ unterstuetzt RECORDS,
|
||
UNIONS, DYNAMISCHE FELDER, SETS, BAGS und GRAPHEN. Pointer wurden bewusst
|
||
weggelassen um die Sicherheit der Sprache nicht nur zu sichern, sondern im
|
||
Vergleich zu anderen Sprachen auch zu erhoehen. Weiterhin ist zu bemerken,
|
||
dass es keine globalen Variablen gibt. Jedoch koennen solche Variablen
|
||
simuliert werden. Dies geschieht dadurch, dass sie als Referenzeparameter
|
||
eingesetzt werden.
|
||
|
||
Dieses Kapitel ist nun wie folgt aufgebaut:
|
||
|
||
Es wird aufgezeigt, wie wir das Message Passing ueber verteilte Daten
|
||
realisiert haben. Als naechstes werden wir einen Blick ueber die Prozesse
|
||
innerhalb der Sprache geben. Diese Prozesse werden benutzt, um den
|
||
Parallelanteil der Sprache zu realisieren. Dann kommen wir zu dem
|
||
Kommunikationsmodell, welches auf geteilte Datenobjekten aufbaut. Die
|
||
Synchronisierung von Operationen auf geteilten Objekten folgt dann im
|
||
naechsten Abschnitt. Anschliessend wird eine Diskussion ueber die hierarchische
|
||
Verwendung von Objekten stattfinden. Abschliessend werden dann noch die
|
||
Datenstrukturen in TQ aufgezeigt.
|
||
|
||
2.1 Verteilter geteilter Speicher
|
||
|
||
Die meisten Programmiersprachen fuer verteilte Programmierung basieren auf
|
||
dem Message Passing Prinzip. Dies scheint auch logisch zu sein, weil die
|
||
Hardware, auf der die Betriebssysteme laufen, das Message Passing
|
||
unterstuetzt. Jedoch gibt es eine Reihe von Gruenden in denen das Message
|
||
Passing nicht unbedingt das optimale Programmiermodell darstellt. Message
|
||
Passing ist eine Art von Kommunikation, die zwischen zwei "Parteien"
|
||
stattfindet, die miteinander explizit durch das Versenden und Empfangen von
|
||
Nachrichten kommunizieren. Message Passing ist jedoch nicht angebracht, wenn
|
||
einige Prozesse indirekt miteinander kommunizieren muessen. Diese Prozesse
|
||
muessen dann die Informationen teilen.
|
||
|
||
Es gibt viele Beispiele solcher Applikationen. Zum Beispiel in sog.
|
||
"branch-and-bound" Algorithmen wird die aktuell beste Loesung (bound) in
|
||
einer globalen Variablen gespeichert. Auf diese Variable kann von allen
|
||
Prozessen aus zugegriffen werden. Dies bedeutet nicht, dass der Algorithmus
|
||
physikalisch geteilte Speicher benoetigt. Vielmehr benoetigt er logisch
|
||
geteilte Daten. Solche Algorithmen sind weitaus schwieriger zu
|
||
implementieren, damit sie das Message Passing sinnvoll nutzen koennen. Daher
|
||
wird das Message Passing durch geteilte Daten ersetzt.
|
||
|
||
In der Literatur finden sich viele andere Beispiele ueber Applikationen und
|
||
Algorithmen auf verteilten Systemen die geteilte Daten unterstuetzen. Es gibt
|
||
sehr stabile Verfahren, die es sogar mueglich machen, solche Algorithmen
|
||
arbeiten zu lassen, wenn kein physikalisch teilbarer Speicher vorhanden ist.
|
||
Es existieren mehrere Applikationen, die dies beweisen. Darunter faellt ein
|
||
verteiltes Spracherkennungssystem, ein Programm, das lineare Gleichungen
|
||
ebenso loest wie partielle Differentialgleichungen dritten Grades. Ebenfalls
|
||
existieren Sortieralgorithmen, Computerschachprogramme, verteile
|
||
Systemdienste wie Nameserver oder Zeitgeber, globales Scheduling und sich
|
||
replizierende Dateien.
|
||
|
||
Die Schwierigkeit logisch geteilte Daten mit Hilfe des Message Passing zur
|
||
Verfuegung zu stellen, machen das System fuer die meisten Applikationen nicht
|
||
rentabel. Viele Wissenschaftler haben auf dem Gebiet der
|
||
Kommunikationsmodelle, die auf logisch geteilten Daten basieren und weniger
|
||
auf dem Message Passing geforscht. Mit diesen Modellen kann der Anwender
|
||
geteilte Daten benutzen, obwohl die darunterliegende Hardware den
|
||
physikalischen Speicher nicht unterstuetzt. Ein Speichermodell sieht so aus,
|
||
dass der Anwender den geteilten Speicher benutzen kann, indem er einfach den
|
||
Verbund zweier Maschinen nimmt. Beide Speicher dieser Maschinen zusammen
|
||
stellen dann den verteilten Speicher als eine Einheit dar.
|
||
|
||
Viele verschiedene Arten von verteiltem geteilten Speicher sind heute
|
||
existent. Li's geteilter virtueller Speicher ist wohl das beruehmteste
|
||
Beispiel. Das Modell simuliert einen physikalisch geteilten Speicher auf
|
||
einem verteilten System. Der geteilte virtuelle Speicher verteilt die Seiten
|
||
des Speicherplatzes ueber den lokalen Speicher. Die Read-Only Seiten koennen
|
||
dann auch reproduziert werden. Geteilter virtueller Speicher beschreibt ein
|
||
klares einfaches Modell, jedoch entstehen bei der Implementierung sehr viele
|
||
Probleme, die eine Realisierung in den meisten Faellen zu aufwendig machen.
|
||
|
||
Einige wenige Programmiersprachen verfolgen dieses Verfahrens. Linda
|
||
unterstuetzt einen global geteilten 'Tupel Space', in welchem die Prozesse
|
||
hineingreifen koennen um eine Art assoziative Adressierung vornehmen zu
|
||
koennen. 'Tupel Space' kann wiederherstellend oder partitionierend realisiert
|
||
werden, aehnlich wie der geteilte virtuelle Speicher. Die Operationen die im
|
||
'Tupel Space' erlaubt sind, sind eingebaute low-level Operationen, welche
|
||
wir uns spaeter naeher ansehen werden. Der Programmieraufwand mit solchen
|
||
Operationen ist zuerst aufwendig, der Vorteil ist jedoch, dass erstellte
|
||
Applikationen sehr effizient arbeiten koennen.
|
||
|
||
Die Emerald Sprache arbeitet relational zu dem verteilten geteilten
|
||
Speicher. Dies aeusserst sich so, dass ein geteilter benannter Speicher fuer
|
||
Objekte zusammen mit einem lokal transparenten Mechanismus zusammenarbeitet.
|
||
Emerald benutzt keine der wiederherstellenden Technik, wie sie typisch fuer
|
||
verteilte geteilte Speichersysteme ist.
|
||
|
||
Der wichtigste Punkt, den es in TQ zu realisieren gilt ist der, wie es
|
||
moeglich ist, dass Daten zwischen verteilten Prozessen auf eine effiziente
|
||
Weise geteilt werden k<>nnen. In Sprachen, die fuer Multiprozessoren
|
||
geschrieben sind, werden geteilte Datenstrukturen in geteiltem Speicher
|
||
gehalten und auf die gleiche Weise wie auf Variablen kann auf diese
|
||
Datenstrukturen zugegriffen werden. Ein solcher Vorgang kann durch einfache
|
||
Lade- und Speicherinstruktionen vollzogen werden. Wenn ein Prozess Teil
|
||
einer geteilten Datenstruktur wird, er sich aber nicht mit anderen Prozessen
|
||
den Platz teilen moechte, lehnt er den Platz in der Datenstruktur ab und
|
||
versucht es zu einem spaeteren Zeitpunkt wieder. All diese Operationen wie
|
||
Laden, Speichern, Freigeben, die auf geteilte Datenstrukturen einwirken,
|
||
also an ihnen beteiligt sind, sind hoeher gestellt als andere Operationen.
|
||
Die Begruendung liegt darin, dass es sehr schwierig ist, einen geteilten
|
||
Speicher zu handhaben - schwieriger als auf einen lokalen Speicher
|
||
zuzugreifen.
|
||
|
||
Auf einem verteilten System ist der Zugriff auf Daten sehr stark von der
|
||
Lokalitaet der Daten abhaengig, also dem Platz, an dem sich die Daten
|
||
befinden. Datenzugriff auf einen entfernten Prozessor ist des Ausmasses wegen
|
||
viel teurer als der Zugriff auf lokale Daten. Es ist daher unmoeglich das
|
||
Modell des Multiprozessors auf das des verteilten Systems zu uebertragen.
|
||
Die Operationen, die in diesem Modell benutzt werden, sind fast nur
|
||
low-level Operationen und wuerden auf einem verteilten System mit anderen
|
||
Operationen nicht zum Zuge kommen, weil die Wahrscheinlichkeit zu gering
|
||
ist.
|
||
|
||
Daher wurde fuer TQ ein neues Konzept entwickelt, das die Vorteile der beiden
|
||
Systeme vereint und die Nachteile ausschliesst. Mithin wurde der Versuch
|
||
unternommen, den Zugriff auf geteilte Datenstrukturen ausschliesslich durch
|
||
"High-Level" Operationen durchzufuehren. Anstatt, dass die 'Low-Level'
|
||
Operationen, wie z.B. das Schreiben und Lesen, auf die geteilten Daten
|
||
zugreifen, ueberlassen wir es dem Anwender, zusammengesetzte Operationen zu
|
||
definieren um geteilte Datenstrukturen zu manipulieren. Geteilte
|
||
Datenstrukturen sind in dem hier vorgestellten Modell in Kapseln gehalten.
|
||
Man nennt solche Erscheinungen auch Daten-Objekte. Diese Datenobjekte koennen
|
||
nun durch eine Reihe von benutzerdefinierten Operationen manipuliert werden.
|
||
Datenobjekte lassen sich am besten dadurch darstellen, dass Sie ein
|
||
Zusammenschluss von Variablen sind. Diese Variablen sind dann nichts anderes
|
||
als abstrakte Datentypen. Der Programmierer spezifiziert einen abstrakten
|
||
Datentyp dadurch, dass er Operationen definiert die zu Daten-Objekten
|
||
(Instanzen) zusammengefasst werden, die von dem Typ der Datenstruktur sind.
|
||
Die aktuellen Daten, die in dem Objekt enthalten sind, und der ausfuehrbare
|
||
Code fuer die Operationen sind in der Implementierung des abstrakten
|
||
Datentyps versteckt.
|
||
|
||
2.2 Prozesse
|
||
|
||
Der Parallelismus in TQ findet explizit statt. Dies hat den Grund, dass
|
||
Compiler im Bereich der Codegenerierung nicht effektiv genug sind um den
|
||
Parallelismus umzusetzen. Impliziter Parallelismus ist vielleicht fuer
|
||
Vektorrechner geeignet. Jedoch zum jetzigen Wissensstandard der
|
||
Computertechnologie ist es nicht besonders effektiv den Parallelismus
|
||
implizit auf verteilten Systemen zu benutzen.
|
||
|
||
Der Parallelismus in TQ wird durch die explizite Erscheinung sequentieller
|
||
Prozesse realisiert. Prozesse sind konzeptionell gesehen aehnlich wie
|
||
Prozeduren, jedoch mit der Ausnahme, dass Prozeduren sequentiell, Prozesse
|
||
indes parallel abgearbeitet werden.
|
||
|
||
Tatsaechlich besteht ein TQ Programm aus einem einzelnen Prozess, jedoch ist
|
||
es moeglich, neue Prozesse explizit mit dem fork Befehl zu generieren.
|
||
|
||
Diese Anweisung kreiert einen neuen anonymen Kindprozess. Optional kann der
|
||
neue Prozess einem bestimmten Prozessor zugeordnet werden. Prozessoren koennen
|
||
sequentiell durchnumeriert werden. Der Fork-Befehl kann einen ON-Teil mit
|
||
einem dazugehoerigen Ausdruck besitzen, welcher den Prozessor spezifiziert
|
||
auf dem der Kindprozess laufen soll. Wenn der ON-Teil fehlt, wird der
|
||
Kindprozess auf dem gleichen Prozessor gestartet wie sein Vaterprozess. Das
|
||
System verschiebt von sich aus keine Prozesse auf einen anderen Prozessor.
|
||
Dies ist fuer parallele Aplikationen im allgemeinen unerwuenscht.
|
||
|
||
Ein Prozess kann mehrere Parameter enthalten. Diese werden in der jeweiligen
|
||
Prozessdefinition spezifiziert. Zwei verschiedene Vorgehensweisen sind
|
||
hierbei moeglich. Eingabe und Ausgabe. Ein Prozess kann als Werteparameter
|
||
(Eingabe) irgendeine Datenstruktur erhalten. In diesem Fall erhaelt der
|
||
Prozess eine Kopie des aktuellen Parameters. Der Vaterprozess kann jedes
|
||
seiner Datenobjekte als einen geteilten Parameter seinem Kind uebergeben. In
|
||
diesem Fall ist das Datenobjekt zwischen dem Vater und dem Kind geteilt. Der
|
||
Vater und das Kind koennen ueber dieses geteilte Objekt miteinander
|
||
kommunizieren. Diese Kommunikation findet dadurch statt, dass die
|
||
Operationen, die durch den Objekttyp definiert sind, ausgefuehrt werden. Wie
|
||
dies genau funktioniert wird an einer anderen Stelle gezeigt.
|
||
|
||
Die Kinder koennen geteilte Objekte wiederum ihren Kindern geben und so
|
||
weiter. Auf diese Art und Weise koennen die Objekte zwischen den Kindern
|
||
eines kreierten Prozesses verteilt werden. Wenn irgendein Prozess eine
|
||
Operation auf das Objekt ausfuehrt, so hat dies den gleichen Effekt, als
|
||
wuerde das Objekt sich in geteiltem Speicher befinden. Das Objekt ist durch
|
||
eine gesperrte Variable geschuetzt.
|
||
|
||
2.3 Geteilte Datenobjekte und abstrakte Datentypen
|
||
|
||
Ein geteiltes Datenobjekt ist eine Variable, die von einem abstrakten
|
||
Datentyp (Objekttyp) stammt. Ein abstrakter Datentyp besteht in TQ aus zwei
|
||
Teilen:
|
||
|
||
einem Spezifikationsteil und einem Implementierungsteil.
|
||
|
||
Der Spezifikationsteil definiert die anwendbaren Operationen, die fuer die
|
||
Objekte eines betsimmten Typs vorgesehen sind.
|
||
|
||
Der Implementierungsteil stellt die Daten zur Verfuegung, die benoetigt
|
||
werden, um Objekte des entsprechenden Typs darzustellen, den Code der fuer
|
||
die Initialisierung der Daten fuer neue Instanzen des Types benoetigt wird und
|
||
die Codeimplementierung der Operationen.
|
||
|
||
Eine Implementation von "Operation" ist aehnlich der einer Prozedur. Eine
|
||
Operation kann nur auf ihre eigene lokalen Variablen zugreifen. Ebenso auf
|
||
ihre lokalen Parameter und die internen aber auch lokalen Daten des Objektes
|
||
innerhalb des sie sich befindet.
|
||
|
||
Ist ein Objekttyp erst einmal definiert, koennen Instanzen (Objekte) des
|
||
gleichen Typs dadurch erzeugt werden, indem Variablen dieses Typs deklariert
|
||
werden. Ist ein Objekt erzeugt, wird der benoetigte Speicherplatz fuer die
|
||
lokalen Variablen des Objektes allokiert (adressiert) und der
|
||
Initialisierungscode wird ausgefuehrt. Von da an koennen Operationen einem
|
||
Objekt zugeordnet werden bzw. Operationen koennen ein Objekt veraendern, also
|
||
mit ihm arbeiten.
|
||
|
||
TQ unterstuetzt einen einfachen abstrakten Datentypmechanismus. Diese
|
||
Mechanismen koennen dazu benutzt werden, geteilte oder nicht geteilte Daten
|
||
zusammenzufassen. Mit anderen Worten, der Mechanismus kann ebenso auf
|
||
regulaere (sequentielle) abstrakte Datentypen angewandt werden. Um nun aber
|
||
den Kreis zu schliessen:
|
||
|
||
Der gleiche abstrakte Datentyp kann herangezogen werden um sowohl geteilte
|
||
als auch lokale Objekte zu creieren. Weder Objektdeklarationen noch
|
||
Objekttypdeklarationen spezifizieren, ob Objekte geteilt sind oder nicht.
|
||
Diese Information wird vom Gebrauch der Objekte abgeleitet: Nur Objekte die
|
||
als geteilter Parameter in einer fork-Anweisung existieren, koennen als
|
||
geteilte Objekte dargestellt werden. Alle anderen Objekte sind lokal und
|
||
werden wie normale Variablen behandelt, die einen abstrakten Datentyp haben
|
||
koennen.
|
||
|
||
Die meisten existierenden Sprachen verwenden zur Realisierung dieser beiden
|
||
Tatsachen zwei verschiedene Mechanismen. Argus zum Beispiel benutzt Cluster
|
||
um lokale Daten zu handeln und Guardians (Waechter) fuer die geteilten Daten.
|
||
Die Cluster und die Guardians beinhalten voellig verschiedene Mechanismen. SR
|
||
benutzt einen einzelnen Mechanismus (Resources), aber der Overhead ueber den
|
||
Operationen dieser Resourcen ist so hochkaraetig abstrahiert, dass er fuer
|
||
sequentiell abstrakte Datentypen nicht angewendet werden kann. Die Tatsache,
|
||
dass auf geteilte Daten Operationen zugreifen koennen, die vom Benutzer
|
||
definiert werden, ist ein wichtiger Unterschied zwischen dem hier
|
||
vorgestellten Modell und anderen. Geteilter virtueller Speicher zum Beispiel
|
||
simuliert physikalisch geteilten Speicher, somit kann auf geteilte Daten mit
|
||
Hilfe von low-level Funktionen wie read und write zugegriffen werden.
|
||
Linda's 'Tupel Space' Modelle benutzen eine fest vorgegebene Anzahl von
|
||
eingebauten Operationen um geteilte Tupel zu handeln. Diese sind add, read
|
||
und delete. Hat man jedoch die Moeglichkeit benutzerdefinierte Operationen zu
|
||
benutzen, so hat dies gravierende Vorteile. Dies soll sowohl fuer das
|
||
Programmdesign als auch fuer die Programmentwicklung hier kurz gezeigt
|
||
werden.
|
||
|
||
Obwohl Datenobjekte logisch zwischen Prozessen geteilt sind, muss man bei
|
||
ihrer Implementierung nicht voraussetzen, dass physikalisch geteilter
|
||
Speicher vorhanden ist. Im schlimmsten Fall kann man eine Operation fuer ein
|
||
entferntes Objekt mit dem oben bereits erwaehnten Message Passing ausstatten.
|
||
Die grundlegende Idee jedoch ist, bei der Implementierung in Bezug auf die
|
||
physikalische Verteilung von Objekten zwischen Prozessen Vorsicht walten zu
|
||
lassen. Wie wir in Kapitel 4 sehen existieren geteilte Datenobjekte.
|
||
|
||
Dadurch, dass die Objekte kopiert werden, wird die Zugriffskontrolle fuer
|
||
geteilte Objekte dezentralisiert. Hierdurch werden die Zugriffskosten
|
||
verringert und die Geschwindigkeit zu Gunsten der Parallelitaet erhoeht. Dies
|
||
ist der Hauptunterschied, im Vergleich zu den Monitoren, die eine
|
||
zentralisierte Kontrolle auf die geteilten Daten haben.
|
||
|
||
2.4 Synchronisation
|
||
|
||
Ein abstrakter Datentyp in TQ ist in zweierlei Hinsicht nuetzlich. Man kann
|
||
ihn sowohl fuer die Erzeugung von geteilten Objekten als auch fuer die
|
||
Erzeugung von lokalen Objekten benutzen. Fuer Objekte, welche zwischen
|
||
multiplen Prozessen geteilt werden, nimmt die Bedeutung der Synchronisation
|
||
ueberproportional zu. Grundsaetzlich gibt es zwei verschiedene Typen von
|
||
Synchronisationsverfahren. Zum einen die sich gegenseitig ausschliessende
|
||
Synchronisation und zum anderen die bedingte Synchronisation. Wir werden
|
||
beide hier besprechen.
|
||
|
||
Gegenseitig ausschliessende Synchronisation:
|
||
Die sich gegenseitig ausschliessende Synchronisation ist in dem hier
|
||
vorgestellten Modell implizit implementiert. Dies geschieht durch das
|
||
Ausfuehren von Operationen auf Objekte. Die Objekte sind in diesem Fall
|
||
unteilbar. Konzeptionell gesehen sperrt jede Operation das komplette Objekt,
|
||
auf welches sie angewandt wird, fuehrt die aufgetragene Arbeit aus und hebt
|
||
die Sperre erst dann wieder auf, wenn die Arbeit abgeschlossen ist. Um
|
||
genauer zu sein, das Modell garantiert die sogenannte Serialisation. Dies
|
||
bedeutet, dass eine Operation das entsprechende Objekt nicht vereinnahmt.
|
||
Wenn also zwei Operationen gleichzeitig auf das gleiche Datenobjekt
|
||
zugreifen moechten, sieht das Ergebnis eben so aus, dass erst die eine und
|
||
danach die andere ausgefuehrt wird. Die Reihenfolge der Abarbeitung der
|
||
Operationen ist jedoch nichtdeterministisch.
|
||
|
||
Bei der Implementierung eines solchen Modells ist es nicht notwendeig, alle
|
||
Operationen nacheinander auszufuehren. Um den Grad des Parallelismus zu
|
||
erhoehen ist es moeglich, multiple Operationen auf das gleiche Objekt simultan
|
||
loszulassen. Dies geschieht dann ebenso wie bei der seriellen Ausfuehrung.
|
||
Zum Beispiel koennen Operationen, die die Daten in einem Objekt nur lesen
|
||
aber keine Veraenderungen vornehmen, parallel ausgefuehrt werden.
|
||
|
||
Seit jedoch die Benutzer ihre eigenen Operationen auf Objekte definieren
|
||
koennen ist es das Problem der Benutzer zu entscheiden, welche Teile des
|
||
Codes unteilbar ausgefuehrt werden sollen. Zum Beispiel kann ein abstrakter
|
||
Datentyp, der eine Integervariable beinhaltet eine Operation erhalten, der
|
||
den Integerwert erhoeht. Diese Operation wird unteilbar durchgefuehrt. Wenn
|
||
andererseits der Integerwert durch separierte Operationen wie read oder
|
||
write durchgefuehrt wird (erst wird der Wert gelesen und dann inkrementiert
|
||
zurueckgeschrieben), so ist es absolut notwendig diese beiden Operationen als
|
||
getrennte Aktionen zu behandeln. Diese Operationen sind dann nicht teilbar.
|
||
Die allgemeine Regel zu definieren, welche Aktionen teilbar sind und welche
|
||
nicht, ist einfach zu erklaeren. Einzelne Operationen sind unteilbar;
|
||
Sequenzen von Operationen sind nicht unteilbar. Das Modell stellt
|
||
gegenseitige Auschluesse nicht so sehr auf unterster Ebene zur Verfuegung,
|
||
mehr jedoch auf dem Level der Objekte. Andere Programmiersprachen wie Sloop
|
||
geben dem Entwickler mehr akurate Kontrolle ueber die sich gegenseitige
|
||
Ausschliessung der Synchronisation.
|
||
|
||
Das hier vorgestellte Modell unterstuetzt keine unteilbaren Operationen fuer
|
||
eine bestimmte Auswahl von Objekten. Operationen auf multiple Objekte
|
||
verlangen ein verteiltes blockierendes Protokoll. Dieses Protokoll ist nur
|
||
mit viel Aufwand effizient zu implementieren. Darueberhinaus wird das
|
||
Protokoll selten von parallelen Applikationen benutzt. Es wurde darauf
|
||
geachtet, dass das Basismodell in TQ recht einfach gehandhabt wurde und
|
||
Aktionen, die eine hoehere Komplexitaet haben, wurden daruebergestellt.
|
||
Operationen in diesem Modell greifen grundsaetzlich nur auf einfache
|
||
(einzelne) Objekte zu und werden immer als unteilbar ausgefuehrt. Jedoch wird
|
||
das Modell nur geringfuegig effektiver, wenn man dem Benutzer erlauben wuerde,
|
||
Sperren fuer multiple Operationsfolgen auf unterschiedliche Objekte zu
|
||
konstruieren; solche willkuerliche Aktionen koennen unteilbar ausgefuehrt
|
||
werden.
|
||
|
||
Bedingte Synchronisation:
|
||
Die zweite Form der Synchronisation ist die bedingte Synchronisation. Sie
|
||
bietet die Moeglichkeit solange zu warten bis eine Bedingung wahr wird. In
|
||
dem hier vorgestellten Modell ist die bedingte Synchronisation mit den
|
||
Operationen integeriert, die die Moeglichkeit haben auf andere Operationen zu
|
||
warten. Die implizite Prozesssynchronisation findet ueber Operationen auf
|
||
geteilte Objekte statt. Eine wartende Operation besteht aus einem oder
|
||
mehreren ueberwachenden Kommandos.
|
||
|
||
Diese Bedingungen sind Booleanausdruecke. Sie werden Guards (Waechter)
|
||
genannt. Um die Darstellung zu vereinfachen, werden wir einfach annehmen,
|
||
dass die Waechter keinerlei Seiteneffekte haben. Das Problem der Seiteneffekte
|
||
werden wir uns spaeter ansehen.
|
||
|
||
Die Operation wartet initiell solange bis der letzte der Waechter wahr wird.
|
||
Dann wird einer der wahren Waechter ausgewaehlt. Diese Auswahl erfolgt
|
||
nichtdeterministisch. Die Sequenz, die der W<>chter enthaelt, wird danach
|
||
ausgefuehrt.
|
||
|
||
Die Booleanausdruecke sind abhaengig von ihren Parameter, den lokalen Daten
|
||
der Operation und von den Daten des Objektes. Wenn ein Waechter fehlschlaegt,
|
||
also unwahr wird, kann er zu einem spaeteren Zeitpunkt wieder wahr werden.
|
||
Dies setzt voraus, dass der Status des Objektes sich veraendert. Auf diese Art
|
||
ist es maeglich die Waechter zu steuern.
|
||
|
||
Wir haben uns fuer diese Art der Synchronisation entschlossen, weil es um ein
|
||
vielfaches einfacher ist und es sich in das Modell besser einfuegen lassen
|
||
kann. Eine alternative Abhandlung die wir in Betracht gezogen haben, ist
|
||
eine separierte Synchronisation. Einfach und unabhaengig vom dem Mechanismus
|
||
fuer geteilte Objekte.
|
||
|
||
Ein Prozess der versucht ein Element aus einer leeren Schlange
|
||
herauszunehmen, muss so korrigiert werden, dass es ihm unmoeglich ist
|
||
weiterzuarbeiten. Mit anderen Worten, die Anzahl der Get-Operationen ist
|
||
abhaengig von der Anzahl der Elemente innerhalb der Schlange und somit auch
|
||
von der Anzahl der Add-Operationen. Die Zahl der Get-Operationen darf die
|
||
Zahl der Add-Operationen nicht uebersteigen. Dies hier ist nun ein Beispiel
|
||
einer zwingenden Synchronisation, die in der Reihenfolge ablaeuft in der die
|
||
Operationen ausgefuehrt werden. Zur Realisierung gibt es zwei vorstellbare
|
||
Wege:
|
||
|
||
1. Prozesse die versuchen ein Get auszufuehren sollten zuerst den Status der
|
||
Schlange ermitteln und solange warten, bis die Schlange leer ist. Erfolgt
|
||
ein Get auf eine leere Schlange, so handelt es sich hierbei um einen Fehler.
|
||
|
||
2. Die Get-Operation selbst wartet solange bis die Schlange leer ist.
|
||
Prozesse die auf eine leere Schlange ein Get versuchen werden automatisch in
|
||
den Wartezustand versetzt.
|
||
|
||
In beiden Faellen ist es ein Einfaches, die Prozesse in den Wartezustand zu
|
||
schicken. Im ersten Fall besteht die Einfachheit darin, direkt auf die
|
||
Benutzerprozesse zuzugreifen; im zweiten Fall muss nur auf die Operation
|
||
zugegriffen werden. Im ersten Fall wird eine besondere Operation
|
||
durchgefuehrt, die fuer die Schlange bestimmt ist und prueft, ob diese leer ist
|
||
oder nicht. Fuer beide Faelle soll das Aufwecken eines Prozesses und das
|
||
Wegnehmen von Elementen vom Kopf der Schlange von einer unteilbaren Aktion
|
||
durchgefuehrt werden. Dies ist erforderlich, um keine "Revance"-Situation
|
||
zwischen den beiden Prozessen hervorzurufen.
|
||
|
||
Der erste Weg hat den Nachteil, dass Benutzer eines Objekts dafuer
|
||
verantwortlich sind, dass eine strenge Synchronisation stattfindet. Dies
|
||
steht im Gegensatz zu der eigentlichen Idee von abstrakten Datentypen,
|
||
Einzelheiten von Objekten gegenueber dem Benutzer geheimzuhalten. Der zweite
|
||
Weg ist dagegen viel cleaner, weil der Implementierer von einem Objekt
|
||
Vorsicht bei der Synchronisation walten laesst und die Information vor dem
|
||
Benutzer geheimhaelt. Daher verwenden wir in TQ den zweiten Weg und
|
||
verwirklichen die bedingte Synchronisation, die innerhalb der Operationen
|
||
stattfindet. Dieses Modell erlaubt, dass Operationen warten koennen; Prozesse
|
||
koennen nur dann warten, wenn Operationen ausgefuehrt werden sollen, welche
|
||
zum Warten aufgefordert wurden.
|
||
|
||
Ein wichtiger Gesichtspunkt ist das Design des Synchronisationsmechanismus,
|
||
welcher die wartenden Operationen veranlasst zu warten, solange die
|
||
Unteilbarkeit von Operationen garantiert werden kann. Wenn eine Operation zu
|
||
irgend einem Zeitpunkt waehrend ihrer Ausfaehrung wartet, koennen die
|
||
Operationen nicht laenger seriell ablaufen.
|
||
|
||
Die Loesung die TQ anbietet ist die, dass Operationen nur dann fuer das Warten
|
||
initialisiert werden, wenn sie noch kein Objekt modifiziert haben. Eine
|
||
Operation kann solange warten bis eine bestimmte Bedingung erfuellt (wahr)
|
||
ist. Aber wenn die Operation dann auf das Objekt losgelassen wurde, also zur
|
||
Ausfuehrung gebracht wird, kann sie nicht noch einmal in den Wartezustand
|
||
versetzt werden.
|
||
|
||
2.5 Hierarchische Objekte
|
||
|
||
Abstrakte Datentypen sind nuetzlich um eine Sprache mit neuen Typen zu
|
||
erweitern. Diese Typenbauweise findet hierarchisch statt:
|
||
|
||
Bereits existierende abstrakte Datentypen koennen dazu benutzt werden, neue
|
||
zu bauen. Die internen Daten eines Objekts koennen daher wieder Objekte sein.
|
||
Man muss darauf achten, dass hierarchische Objekte keine abgeleiteten Objekte
|
||
von den bereits existierenden sind. In Objekt-orientierten Sprachen ist dies
|
||
moeglich. Die alten und neuen Objekte haben eine eigene Relation und nicht
|
||
etwa eine vererbte Relation.
|
||
|
||
Die Verschachtelung von Objekten wirft ein schweres Problem auf, wie wir
|
||
hier sehen werden.
|
||
|
||
Wir koennen nun diesen Objekttyp in der Implementierung fuer einen anderen Typ
|
||
benutzen, wir unterlassen aber die Spezifikation dieses Typs.
|
||
|
||
Objekte, die den neuen Typ beinhalten, beinhalten ein Objekt NestedObjekt
|
||
vom Typ OldType. Das letzte Objekt wird verschachteltes Objekt genannt, weil
|
||
es Teil eines anderen Objektes ist. Man bemerke, dass die Bestandteile von
|
||
NewType alles einzelne Objekte sind, dessen Operationen unteilbar sind. Das
|
||
verschachtelte Objekt, das ein Objekt einschliesst, ist nach aussen hin
|
||
unsichtbar, genauso wie alle anderen Daten.
|
||
|
||
Der Implementierer von NewType kann als Benutzer von OldType angesehen
|
||
werden. So weiss der Implementierer von NewType nicht, wie OldType
|
||
implementiert ist. Dieses Loch an Information ueber die Implementierung der
|
||
Operationen auf OldType bringt zwei Probleme mit sich.
|
||
|
||
Das erste Problem wird durch das Benutzen von OldOperation_1 in dem Waechter
|
||
von NewOperation dargestellt. Wir muessen wissen, ob die Waechterausdruecke
|
||
Seiteneffekte haben, wie es in einigen Faellen durchaus vorkommen kann.
|
||
Ungluecklicherweise wissen wir nicht, ob der Aufruf von OldOperation_1
|
||
irgendwelche Seiteneffekte hat. Wenn die Operation NestedObjekt modifiziert,
|
||
entstehen keine Seiteneffekte. Wir koennen dies aber nur dann sagen, wenn wir
|
||
uns die Implementierung dieser Operation ansehen, welche gegen die Idee von
|
||
abstrakten Datentypen wirkt.
|
||
|
||
Das zweite Problem ist mehr oder weniger unscheinbar. Angenommen ein Prozess
|
||
deklariert ein Objekt NewObjekt vom Typ NewTyp und teilt es mit einigen
|
||
seiner Kinderprozesse. Wenn einer der Prozesse NewOperation auf NewObjekt
|
||
aufruft, wird die Implementierung von diesem Objekt OldOperation_2 auf das
|
||
verschachtelte Objekt aufrufen. Das Problem ist dann, dass die letzte
|
||
Operationen nur initiativ warten duerfen. In dieser Situation gibt es zwei
|
||
gleichmaessig unattraktive Optionen:
|
||
|
||
1. Man muss verhindern, dass auf der einen Seite der Prozess auf NewOperation
|
||
zugreift, jedoch anderen Prozessen erlaubt ist, auf das Objekt zuzugreifen.
|
||
Dies bedeutet jedoch, dass die Operation nicht laenger unteilbar bleiben kann.
|
||
|
||
2. Man wartet auf den gerufenen Prozess, erlaubt den anderen Prozessen aber
|
||
nicht, auf das Objekt zuzgreifen. Dies setzt voraus, dass der Prozess fuer
|
||
immer unterstuetzt wird, weil kein anderer Prozess da ist um NestedObjektzu
|
||
modifizieren.
|
||
|
||
Man koennte dieses Problem loesen, indem man wartende Operationen auf
|
||
verschachtelte Objekte nicht zulaesst. Dies aber wiederum zieht dann nach
|
||
sich, dass man sich die Implementierung einer Operation betrachten muss, um zu
|
||
sehen, wie man sie benutzen kann.
|
||
|
||
Cooper und Hamilton haben <20>hnliche Konflikte zwischen der parallelen
|
||
Programmierung und der Datenabstraktion im Zusammenhang mit Monitoren
|
||
beobachtet. Sie schlagen erweiterte Operationsspezifikationen mit
|
||
Informationen ueber ihre Implementierung vor, egal ob die Operation
|
||
Seiteneffekte hat oder nicht. Wir denken jedoch, dass dies nicht gerade eine
|
||
elegante Weise ist das Problem zu loesen. Die Spezifikation eines abstrakten
|
||
Datentyps sollte keine Informationen ueber die Implementierung enthalten.
|
||
|
||
Wir loesen diese beiden Probleme, indem wir die Ausfuehrung der
|
||
Modelloperationen verfeinern. Konzeptionell wird eine Operation wie folgt
|
||
ausgefuehrt:
|
||
|
||
Die Operation wiederholt die Versuche seine Waechter auszuwerten und versucht
|
||
dann die Anweisungen mit einem wahren Waechter auszufuehren. Bevor der Waechter
|
||
ausgewertet wird, muss die Operation (konzeptionell) eine Kopie ihres Objekts
|
||
anfertigen, wobei die verschachtelten Objekte mitenthalten sein muessen.
|
||
Diese Kopie wird waehrend der Auswertung des Waechters und der Ausfuehrung der
|
||
Anweisungen benutzt. Die Operation stellt eine gleiche Alternative wie diese
|
||
dar:
|
||
|
||
1. Der W<>chter wird wahr (evaluates to true)
|
||
2. Die korrespondierenden Anweisungen koennen ausgefuehrt werden, ohne dass
|
||
irgendeine wartende Operation oder verschachtelte Objekte aufgerufen werden.
|
||
|
||
Sowie ein Waechter als unwahr deklariert wird oder die Anweisungen eine
|
||
wartende Operation aufruft, wird die Kopie des Objektes weggelegt und eine
|
||
andere Alternative wird versucht. Auf diese Weise bleibt eine Operation
|
||
nicht stehen bis ihr Waechter sie komplett ausgefuehrt hat. Dies gilt auch fuer
|
||
ihre korrespondierenden Anweisungen. Dies alles geschieht, ohne dass auf
|
||
wartende Operationen oder verschachtelte Objekte zugegriffen wird. Wenn alle
|
||
Alternativen einer Operation versagen, wird sie (und der Prozess, der sie
|
||
aktiviert hat) zum Warten animiert bis das Objekt von einem anderen Prozess
|
||
modifiziert wurde. Wenn eine Operation eine andere Alternative zur Verfuegung
|
||
stellt, wird dem Objekt der aktuelle Wert der Kopie zugeordnet.
|
||
|
||
Beispiel: Der Wert, der nach dem Auswerten des W<>chters und der Anweisungen
|
||
ausgewaehlt wurde.
|
||
|
||
Dieses Schema loest beide oben beschriebenen Probleme. Eine Operation die auf
|
||
ein verschachteltes Objekt angesetzt wird und einen impliziten Waechter
|
||
(Beispiel: OldOperation_1 im oben gezeigten Code) hat, kann Seiteneffekte
|
||
haben. Diese Seiteneffekte sind jedoch solange nicht permanent vorhanden,
|
||
solange der W<>chter aktiviert ist. Eine Operation auf ein verschachteltes
|
||
Objekt kann also auch in den Wartezustand geschickt werden. Wie auch in
|
||
anderen Faellen kann der Waechter seinen Wert aendern. Sind bis dahin jedoch
|
||
alle Alternativen ausgenutzt, beginnt der Kreislauf wieder von vorne. Die
|
||
Operation hat solange keinen Effekt bis irgendeine Alternative vollstaendig
|
||
abgearbeitet ist. Alle Alternativen werden bei einer Operation ausgetestet
|
||
und es wird versucht, die Seiteneffekte weitgehend auszuschliessen. Wenn eine
|
||
Alternative funktioniert, werden sowohl der Waechter als auch die Anweisungen
|
||
ohne Warten ausgefuehrt. Daher ist es notwendig, dass solche Operationen
|
||
unteilbar sind.
|
||
|
||
Der Schluessel zum Erfolg ist die Implementierung der effektiven Ausfuehrung
|
||
innerhalb des Models. Es ist sehr teuer Objekte fuer und vor jeder
|
||
Alternative zu kopieren. In nahezu allen Faellen jedoch wird der Compiler
|
||
versuchen, den Kopiervorgang der zu kopierenden Objekte zu optimieren. Viele
|
||
Objekttypen haben keine verschachtelten Objekte. Daher werden sie von dem
|
||
oben beschriebenen Problem nicht beruehrt. Weiterhin kann ein Compiler
|
||
ueberpruefen, ob eine Operation innerhalb eines Waechters oder eines "Koerpers"
|
||
frei von Seiteneffekten ist oder nicht. Auch kann er feststellen, in welchem
|
||
Zustand sich eine Opertion befindet. Um dies durchfuehren zu koennen, muss er
|
||
Zugriff auf den Implementierungscode der verschachtelten Objekte haben.
|
||
Dieser Vorgang unterscheidet sich kaum von dem der sonstigen globalen
|
||
Optimierungsvorgaengen. Optimierungsvorgaenge koennen nur im Ganzen vorgenommen
|
||
werden, was bedeutet, dass dem Optimierer das komplette Quellcodeprogramm zur
|
||
Verfuegung stehen muss. Dieser Mechanismus zeichnet sich weiterhin dadurch
|
||
aus, dass er sich zum Testen von Zirkularitaeten in verschachtelten
|
||
Objektdefinitionen einsetzen laesst. Die hier angebotene Loesung bewahrt die
|
||
Abstraktion aus der Sicht des Programmierers. Die globale Optimierung ist in
|
||
den meisten Faellen sehr effizient. Der hier vorgestellte Compiler
|
||
unterstuetzt diese Optimierungen. Diese Abhandlung soll die eigentliche
|
||
Sprache so einfach wie moeglich halten und die Optimierung so effizient wie
|
||
moeglich machen. Diese beiden Punkte zu verbinden ist eine nicht triviale
|
||
Aufgabe.
|
||
|
||
2.6 Datenstrukturen
|
||
|
||
In den meisten prozeduralen Sprachen werden Datenstrukturen wie Graphen oder
|
||
Baeume behandelt. Listen werden grundsaetzlich durch dynamische Speicherbloecke
|
||
allokiert und wieder deallokiert. Mehrere Listen werden durch Pointer
|
||
miteinander verknuepft. Fuer die verteilte Programmierung haben diese
|
||
Moeglichkeiten viele Nachteile. Die Hauptschwierigkeit besteht darin, wie wir
|
||
komplexe Datenstrukturen, die Pointer enthalten, zu einer entfernten
|
||
Maschine transportieren. Pointer sind, wenn sie als Adresse implementiert
|
||
sind, nur dann sinvoll, wenn sie auf einer einzigen Maschine laufen koennen.
|
||
Dies ist nur deshalb moeglich, weil sie eine besondere Behandlung benoetigen,
|
||
bevor sie uebermittelt werden. Ein viel wichtigerer Punkt ist der, dass die
|
||
meisten Sprachen solche Graphen im Sinne von "erste-Klasse-Objekte" erst gar
|
||
nicht in Betracht ziehen. Um so schwieriger ist es herauszufinden, was aus
|
||
den "Objekten" ueberhaupt uebertragen werden soll und was nicht.
|
||
|
||
Hinzu kommt das Problem, dass, wenn man dem Programmierer die explizite
|
||
Kontrolle ueber das Allokieren und das Deallokieren von Speicher gibt, im
|
||
allgemeinen die Typensicherheit verloren geht. Wenn ein Programierer
|
||
Speicher deallokieren und ihn wieder benutzen kann, fuehrt dies zu etlichen
|
||
Fehlern.
|
||
|
||
In TQ sind diese Probleme dadurch geloest, dass der Datentyp GRAPH eingefuehrt
|
||
wird. Ein Graph in TQ besteht mindestens aus 0 oder mehreren NODES. Jede
|
||
Node hat eine Anzahl von Felder. Diese Felder koennen verglichen werden mit
|
||
denen eines RECORDS. Weiterhin kann der Graph selbst globale Felder
|
||
enthalten. Diese koennen dazu benutzt werden, Informationen ueber den Graphen
|
||
zu enthalten. (Die root eines Baumes oder der Kopf oder Fuss einer Liste)
|
||
Individuelle Nodes, die sich innerhalb eines Graphen befinden, werden ueber
|
||
Werte eines Nodenames identifiziert. Eine Variable oder ein Feld eines
|
||
Nodenamenstyps wird grundsaetzlich mit NIL initialisiert. Dies geschieht,
|
||
damit der Name keiner weiteren Node gegeben werden kann.
|
||
|
||
Jede Node eines solchen Graphen enthaelt ein Datenfeld und die Felder
|
||
identifizieren sich durch die rechten und linken Soehne des Nodes.
|
||
Weiterhin hat der Graph ein globales Feld, das dazu dient, die Rootnode
|
||
eines Baums zu identifizieren.
|
||
|
||
Eine Baumdatenstruktur wird erstellt durch eine Variable seines Typs.
|
||
Initialisiert wird zuerst der leere Baum, aber Nodes koennen dynamisch
|
||
hinzugefuegt werden und dynamisch geloescht werden.
|
||
|
||
Der Konstrukt addnode addiert eine neue Node zu dem Graphen hinzu und
|
||
vergibt einen einmaligen Namen. Diese Namensauswahl wird durch das RTS
|
||
getroffen. Das RTS allokiert also automatisch Speicher fue den neuen Node.
|
||
In diesem Fall ist addnode aehnlich zu der Standardprozedur NEW in Pascal.
|
||
Als wichtiger Unterschied zwischen den beiden ist jedoch hervorzuheben, dass
|
||
der addnode Konstrukt eine Datenstruktur spezifiziert, fuer die der neue
|
||
Speicherblock gedacht ist. Nicht wie in Pascal, nimmt das RTS von TQ die
|
||
Ueberwachung der Knoten zu jedem einzelnen Graph. Diese Information wird
|
||
immer dann benutzt, wenn eine Kopie von dem Graphen erzeugt wurde. Zum
|
||
Beispiel, wenn er einen Werteparameter erh<72>lt und einer Prozedur eines
|
||
entfernten Prozesses weitergeben muss. Weiterhin wird die Information
|
||
dahingehend benutzt, um den Graphen zu loeschen, wenn das Ende der Prozedur
|
||
erreicht ist, fuer die er erzeugt wurde.
|
||
|
||
Die globalen Felder eines Graphen und die Felder seiner Nodes werden ueber
|
||
Designatoren erreichbar. Diese sind <20>hnlich wie die eines RECORDS oder
|
||
FELDES.
|
||
|
||
Zu bemerken ist, dass der Designator fuer das entsprechende Feld einen
|
||
Nodename spezifiziert. Dies geschieht auch fuer den eigentlichen Node wie
|
||
auch fuer den Graphen selbst. Diese Notation unterscheidet sich der von
|
||
Pascal, wo Nodes durch Pointer identifiziert werden. Die Notation in TQ ist
|
||
daher etwas mehr hinderlich, da sie komplexer ist. Jedoch hat sie den
|
||
Vorteil, dass sie dem Programmablauf immer saubere Datenstrukturen zur
|
||
Verfuegung stellt. Weiterhin existiert die Moeglichkeit, dass ein Nodename als
|
||
Index innerhalb eines Graphen dienen kann. aehnlich wie die Adresse der
|
||
Maschine. Neodenamen koennen daher zwischen fernen Maschinen uebertragen
|
||
werden, ohne dass sie ihre Bedeutung oder ihren Inhalt verlieren.
|
||
|
||
Die Graphen in TQ sind typensicher. Wenn irgendein Node aus dem Graphen
|
||
geloescht wird und auf eines seiner Felder wird trotzdem zugegriffen, kommt
|
||
es zu einem Laufzeitfehler. Hier nun ein Beispiel dafuer:
|
||
|
||
Das RTS ueberprueft, ob der Graph t eine Node mit dem entsprechenden Namen
|
||
enthaelt oder nicht. Weiterhin liefert jeder Aufruf von addnode(t) einen
|
||
anderen Namen zurueck. Auf diese Weise ist es nicht moeglich, dass der gleiche
|
||
Name fuer verschiedene Nodes benutzt werden kann. Wenn auch immer ein Node
|
||
aus einem Graphen geloescht wurde, wird ein zukuenftiger Zugriff auf diesen
|
||
Node zu einem Laufzeitfehler fuehren.
|
||
|
||
Der Mechanismus der Datenstrukturen von TQ hat einige Vorteile bei Feldern
|
||
und bei Pointer unterstuetzten Datenstrukturen. Der Mechanismus unterstuetzt
|
||
die dynamische Allokierung von Speicher. Dies erfolgt durch die
|
||
addnode-Operation. Graphen, wie auch Felder sind in TQ ganz oben
|
||
angesiedelt. Dieses Design hat einige Vorteile:
|
||
|
||
Es ist einfach, sie entfernten Prozessen zuzuordnen; weiterhin ist jede
|
||
Zuweisung durch Graphvariablen gekennzeichnet; Graphen allokieren automatsch
|
||
den benoetigten Speicher und deallokieren diesen dann wieder, wenn die
|
||
entsprechende Prozedur abgeschlossen ist. Das letztere Feature reduziert die
|
||
automatische "garbage collection" von Nodes. Nodenamen in TQ haben sicher
|
||
Vorteile, sowohl durch die Pointer als auch durch die Feldindizees. Die
|
||
Pointer koennen nicht durch arithmetische Operationen manipuliert werden;
|
||
eine nicht korrekte Benutzung der Feldindizees fuehrt bei der Laufzeit zu
|
||
einem Fehler.
|
||
|
||
Der Graphtyp in TQ hat aber auch Nachteile, wenn man sie mit den Pointern
|
||
vergleicht. Mit Pointern kann man zwei beliebige Datenstrukturen aufeinander
|
||
setzen und sie als eine Einheit innerhalb einer Zuweisung verwenden. Mit
|
||
Graphen ist dies wesentlich schwieriger. Wenn der Programmierer diese
|
||
Verknuepfung vollziehen moechte, koennen die Datenstrukturen durch den Einsatz
|
||
eines einfachen Graphen realisiert werden. Wenn getrennte Graphen benoetigt
|
||
werden, kann der eine in den anderen kopiert werden.
|
||
|
||
Ein anderer Nachteil ist die Laufzeit bei den Graphen. Ein Graph
|
||
representiert eine Liste mit Pointern zu den derzeit aktuellen Nodes. Somit
|
||
wird auf diese Nodes indirekt ueber eben diese Liste zugegriffen. Dies geht
|
||
auch auf das Konto der Graphen, die dadurch typensicher werden, da jeder
|
||
Nodenzugriff ueberprueft wird. Es ist beabsichtigt diese Kosten mit Hilfe der
|
||
globalen Optimierung besser in den Griff zu bekommen.
|
||
|
||
3. Ein Beispiel fuer einen Objekttyp und dessen Anwendung
|
||
|
||
In diesem Kapitel zeigen wir ein Beispiel einer Objekttypdefinition in TQ
|
||
und dessen Anwendung. Das Objekt definiert einen generierenden Job Queue Typ
|
||
mit den Operationen Jobs hinzuzufuegen und zu loeschen. Er wird benutzt in
|
||
parallelen Programmen, die auf replizierenden Arbeiten beruhen. Innerhalb
|
||
dieses Paradigmas ein Hauptprozess produziert wiederholt Jobs die von
|
||
Verbrauchern abgearbeitet werden. Die Kommunikation zwischen dem Hauptprozess
|
||
und dem Verbraucher benoetigt Platz innerhalb der Queue. Eine solche
|
||
Anwendung, "paralleles branch-and-bound" wird hier diskutiert.
|
||
|
||
3.1 Ein Objekttyp
|
||
|
||
Drei verschiedene Operationen werden fuer die Job Queue benoetigt. AddJob fuegt
|
||
einen neuen Job an das Ende der Schlange. Die Operation NoMoreJobs wird dann
|
||
aufgerufen, wenn keine weiteren Jobs in die Schlange eingefuegt werden
|
||
sollen. Dies ist dann der Fall, wenn der Master alle Jobs erzeugt hat.
|
||
Letztlich ist da noch die Operation GetJob, die versucht, einen Job vom Kopf
|
||
der Schlange wegzunehmen. Wenn die Schlange nicht leer ist, nimmt GetJob den
|
||
ersten Job vom Kopf der Schlange weg, und ordnet ihm dem OUT-Parameter job
|
||
zu; die Operation selbst gibt in diesem Fall ein TRUE zurueck. Ist die
|
||
Schlange leer und die Operation NoMoreJobs hat auf die Schlange zugegriffen,
|
||
versagt die erste Operation und gibt ein FALSE zurueck. Wenn keine der beiden
|
||
Bedingungen erfuellt ist, wartet die Operation solange bis eine von ihnen
|
||
wieder wahr wird.
|
||
|
||
Objekte diesen Typs enthalten zwei Variablen: eine Boolean Variable DONE und
|
||
eine Variable 0 vom Typ Queue. Der letztere Typ ist als Graph definiert. Er
|
||
hat zwei globale Felder. Diese dienen dazu, das jeweils erste und letzte
|
||
Element der Schlange zu identifizieren. Jedes Element kennt den Nodenamen
|
||
des naechsten Elementes in der Schlange und die Daten die den formalen Typ T
|
||
besitzen.
|
||
|
||
Die Implementierung von AddJob bedient sich der strengen
|
||
Vorwaertsmanipulation der Liste. Die GetJobOperation ist da wesentlich
|
||
interessanter. Sie beinhaltet zwei Waechter, die die beiden oben
|
||
beschriebenen Bedingungen reflektiert.
|
||
|
||
3.2 Eine parallele Applikation in TQ
|
||
|
||
Wir moechten nun einen genaueren Blick auf eine Applikation in TQ werfen. Es
|
||
handelt sich hierbei um das Problem des "fahrenden Verkauufers". Ein
|
||
Verkaeufer beginnt seine Route in einer bestimmten Stadt. Er hat eine Liste
|
||
von Staedten, die er besuchen muss. Jede dieser Staedte darf er aber nur einmal
|
||
besuchen. Das Objekt hat nun die Aufgabe den kuerzesten Weg zu allen Staedten
|
||
zu finden. Das Problem wird durch den parallelen "branch-and-bound"
|
||
Algorithmus geloest.
|
||
|
||
Der Algorithmus, den wir hier in TQ verwendet haben, nutzt einen
|
||
"Managerprozess" um die Pfade fuer den Verkaeufer zu initialisieren. Hierbei
|
||
beginnt er mit der Heimatstadt und besucht dann alle anderen Staedte, jede
|
||
aber nur einmal. Eine Anzahl von arbeitenden Prozessen fuehrt diese Expansion
|
||
der Pfade aus. Hierbei wird das Verfahren
|
||
"es-wird-die-Stadt-besucht-die-am-naehesten-liegt" benutzt. Die Suche findet
|
||
also nach einem heuristischen Schema statt. Ein Erzeuger generiert
|
||
systematisch alle Pfade, beginnend mit dem Startpunkt und ueberprueft, welcher
|
||
der moeglichen Pfade der kuerzeste ist. Die Laenge des aktuellen besten Pfades
|
||
wird in einem Datenobjekt gespeichert, das den TypIntObjekt hat.
|
||
|
||
Dieses Objekt wird zwischen allen arbeitenden Prozessen aufgeteilt. Der
|
||
Manager und die arbeitenden Prozesse kommunizieren ueber eine geteilte
|
||
Job-Queue, wie man in Bild5 sehen kann.
|
||
|
||
Der Masterprozess kreiert und initialisiert das geteilte Objekt 'Minimum' und
|
||
erzeugt einen arbeitenden Prozess fuer jeden Prozessor mit Ausnahme des
|
||
eigenen. Folglich werden die Jobs von der Funktion GenerateJobs erzeugt.
|
||
Diese Funktion wird hier nicht naeher dargestellt; sie erzeugt dann einen
|
||
Prozess fuer seinen eigenen Prozessor. Auf diese Weise wird eine parallele
|
||
Abarbeitung der Jobgeneration fuer die meisten arbeitenden Prozesse erreicht.
|
||
Der letzte arbeitende Prozess wird erst dann erzeugt, wenn alle anderen Jobs
|
||
erzeugt wurden, da auf diese Art die Geschwindigkeit der Job Generation
|
||
nicht verlangsamt wird, weil fuer den gleichen Prozessor immer nur ein Prozess
|
||
erzeugt wird.
|
||
|
||
Jeder arbeitende Prozess wiederholt den Vorgang einen Job von der Queue zu
|
||
holen und fuehrt ihn durch den Aufruf der Funktion TSP aus. TSP generiert
|
||
alle Routen, von dem Punkt aus, den man ihr als Parameter uebergibt. Wenn die
|
||
erste Route, die als Parameter uebergeben wird, laenger ist als die aktuelle
|
||
meldet TSP dies unmittelbar zurueck, weil dann eine andere Route gefunden
|
||
werden muss, da es sich bei der jetzigen Loesung nicht um die optimalste
|
||
handelt. Wenn dies nicht der Fall ist, ist die Route, die TSP als Parameter
|
||
uebergeben wurde die beste Route, die gefunden werden konnte. Jetzt kann der
|
||
Wert von Minimum upgedated werden. Es ist jedoch moeglich, dass mehrere
|
||
Prozesse eine Route entdecken, die besser ist als die derzeit aktuelle. In
|
||
diesem Fall wird der Wert von Minimum durch die unteilbare Operation Min
|
||
upgedated, welche ueberprueft, ob der neue Wert wirklich kleiner ist als der
|
||
Wert des derzeitigen Objektes.
|
||
|
||
Wenn die Job Queue leer ist und keine weiteren Jobs mehr generiert werden,
|
||
wird die Operation GetJob den Wert FALSE zurueckliefern und alle arbeitenden
|
||
Jobs werden terminiert.
|
||
|
||
4. Eine verteilte Implementierung von TQ
|
||
|
||
Obwohl TQ eine Sprache fuer die Programmierung auf verteilten Systeme ist,
|
||
ist das verwendete Kommunikationsmodell auf geteilten Daten aufgebaut. Die
|
||
Implementierung der Sprache hierfuer sollte die physikalische Verteilung von
|
||
der Hardware verstecken und die geteilten Daten auf eine effiziente Weise
|
||
simulieren. Die Implementierung, die hier beschrieben wird, basiert auf
|
||
Replikationen und sicherer Datenuebertragung. Wir werden kurz eine zweite
|
||
Implementierung in Kapitel 4.4 diskutieren.
|
||
|
||
Das Kopieren von Daten wird in vielen verschiedenen toleranten Systemen
|
||
benutzt, um die Verfuegbarkeit von Daten auf dem jeweiligen Prozessor zu
|
||
erhoehen. In der Implementierung wird das Kopieren dazu benutzt, die Kosten
|
||
der Zugriffe auf verteilte Daten zu senken.
|
||
|
||
Kurz und buendig, jeder Prozessor erhaelt eine lokale Kopie von jedem
|
||
geteilten Datenobjekt. Auf diese Kopie kann von allen Prozessen, die auf
|
||
diesem Prozessor laufen, zugegriffen werden. Operationen, die ein Objekt
|
||
nicht veraendern (Leseoperationen), koennen diese Kopie direkt verwenden.
|
||
Operationen, die ein Objekt veraendern (Schreiboperationen), uebertragen die
|
||
neuen Werte (oder die Operationen) zu all den anderen Prozessoren. Auf diese
|
||
Weise koennen diese simultan upgedated werden.
|
||
|
||
Die Implementierung kann am besten ueber ein 3 Schichtensystem vollzogen
|
||
werden.
|
||
|
||
1. Compilierte Applikationsprogramme
|
||
2. Laufzeitsystem
|
||
3. zuverlaessige Uebertragung
|
||
|
||
Die oberste Schicht ist mit Applikationen gefuellt, die in TQ geschrieben
|
||
sind und auf einer Maschine mit einem TQ Compiler compiliert worden sind.
|
||
Der ausfuehrbare Code enthaelt Aufrufe, die im Laufzeitsystem enthalten sind.
|
||
|
||
Beispiel: Erzeugung und Manipulierung von Prozessen und Objekten.
|
||
|
||
Die mittlere Schicht stellt das RTS dar. Es implementiert die Teile, die von
|
||
der darueberliegenden Schicht benoetigt werden. Wenn eine Applikation eine
|
||
Operation anfordert, die auf geteilte Daten zugreift, liegt es am RTS
|
||
sicherzustellen, dass das System das entsprechende Objekt im geteilten
|
||
Speicher am richtigen Platz zur Verfuegung stellt. Um dies zu erreichen
|
||
fertigt das RTS von jedem Datenobjekt auf dem jeweiligen Prozessor eine
|
||
Kopie an. Diese Kopien werden dann mit Hilfe der 'sicheren Uebertragung'
|
||
upgedated.
|
||
|
||
Die unterste Schicht ist mit der Implementierung der sicheren Uebertragung
|
||
vertraut, so dass das RTS sich nicht darum kuemmern muss, was passiert, wenn
|
||
eine Uebertragungsnachricht verloren geht. Soweit alles funktioniert, muss die
|
||
Uebertragung fehlerfrei sein. Es ist die Aufgabe der untersten Schicht, dies
|
||
zu verwirklichen.
|
||
|
||
Wir werden nun die Protokolle und Algorithmen in jeder Schicht beschreiben.
|
||
Dies geschieht auf folgende Weise: Zuerst beschreiben wir die oberste
|
||
Schicht, dann die mittlere und zuletzt die unterste.
|
||
|
||
4.1 Oberste Schicht: TQ Applikationsprogramme
|
||
|
||
Applikationsprogramme sind Programme, die von einem TQ Compiler in
|
||
ausfuehrbaren Code uebersetzt wurden. Der erzeugte Code enthaelt alle
|
||
benoetigten Laufzeitroutinen , die die Prozesse und die geteilten
|
||
Datenobjekte sowie die komplexen Datenstrukturen (dynamische Felder, Sets
|
||
und Graphen) benoetigen. Wir werden nun beschreiben, wie sich die
|
||
compilierten Operationen verhalten.
|
||
|
||
Wie bereits erwaehnt, ist es sehr wichtig, zwischen Lese- und
|
||
Schreiboperationen auf Objekte zu unterscheiden. Der Compiler analysiert
|
||
deshalb den Implementierungscode fuer jede Operation und testet in wie fern
|
||
diese Operationen ein Objekt modifizieren oder auch nicht. In den meisten
|
||
Sprachen ist eine solche Implementierung aeusserst schwer zu implementieren.
|
||
Betrachten wir nur einmal eine Pascalanweisung, welche eine indirekte
|
||
Zuweisung durch einen Pointer erhaelt.
|
||
|
||
Es ist schwer festzustellen, welche Datenstruktur von dieser Anweisung
|
||
beeinflusst wird. TQ hat dieses Problem nicht, weil der Name der
|
||
Datenstruktur durch den Programmierer angegeben wird.
|
||
|
||
In TQ wird explizit der Name der Datenstruktur mit angegeben, welche zu
|
||
modifizieren ist. Somit kann der Compiler unterscheiden, welche Operationen
|
||
die Datenstruktur eines Objektes modifizieren und welche nicht.
|
||
|
||
Der Compiler speichert die Informationen in einem Operationsbeschreiber.
|
||
Dieser Beschreiber spezifiziert ebenso die Groessen und Modis (Input/Output)
|
||
vom Parameter einer Operation. Wenn ein TQ Programm auf eine Operation fuer
|
||
ein Objekt zugreift, generiert der Compiler alle Aufrufe zu dem RTS mit einem
|
||
Befehl.
|
||
|
||
Das erste Argument identifiziert das Objekt auf welches die Operation
|
||
losgelassen werden soll. Es ist der Netzwerkname des Objektes. Das zweite
|
||
Argument ist der Operationsbeschreiber. Die Art und Weise wie der Befehl
|
||
arbeitet wird durch die Parameter beschrieben.
|
||
|
||
4.2 Mittlere Schicht: RTS
|
||
|
||
Die mittlere Schicht implementiert das RTS. Wie bereits erwaehnt, besteht die
|
||
Hauptaufgabe darin, geteilte Datenobjekte zu handeln. Im allgemeinen ist
|
||
auch der Befehl implementiert, welcher wie oben beschrieben arbeitet.
|
||
Um effizient arbeiten zu koennen, erzeugt das RTS Kopien von den Objekten und
|
||
kann somit Operationen auf die lokalen Kopien zulassen, wann immer es
|
||
notwendig ist.
|
||
|
||
Es gibt viele Gesichtspunkte um "Beziehungen" zu "Kopien" zu machen. So wie
|
||
bei den kopierten Objekten, wo es notwendig ist, Schreiboperationen zu
|
||
synchronisieren, wenn sie auf kopierte Objekte losgelassen werden und ob die
|
||
Kopie des Objekts nach einer Schreiboperation upgedated wird oder nicht. Das
|
||
RTS, das hier beschrieben wird, benutzt kopierte Objekte, fuehrt ein
|
||
Updating, nachdem Schreiboperationen erfolgreich durchgefuehrt wurden und
|
||
eine sich gegenseitig ausschliessende Synchronisation durch, die ueber das
|
||
verteilte, upgedatede Protokoll zustande kommt.
|
||
|
||
Das Kopierschema wurde gewaehlt, wegen seiner Einfachheit und der guten
|
||
Leistung innerhalb der Applikationen. Eine Alternative ist es, das RTS
|
||
dynamisch entscheiden zu lassen, wo die Kopien gespeichert werden sollen.
|
||
Diese Strategie wird in einer anderen Implementierung verwendet.
|
||
|
||
Wir haben uns aus zwei Gruenden fuer das Update-Schema gegenueber dem
|
||
Invalidationsschema entschlossen:
|
||
|
||
1. In vielen Applikationen enthalten Objekte grosse Summen (100k Bit
|
||
Vektoren). Eine ungepruefte Kopie eines solchen Objekt anzufertigen, ist
|
||
Verschwendung, weil bei Bedarf dieses Objekt seinen Inhalt uebertragen muss.
|
||
|
||
2. In vielen Faellen benoetigt eine upgedatede Kopie nicht viel mehr CPU-Zeit
|
||
und Netzwerkbandbreite als wenn man ungepruefte Nachrichten versenden will.
|
||
|
||
Der Einsatz von multiplen Kopien der gleichen logischen Daten fuehrt zu dem
|
||
Problem der Inkonsistenz. Wenn die Daten modifiziert sind, muessen alle
|
||
Kopien modifiziert werden. Wird der Updatevorgang nicht ueberall gleichzeitig
|
||
vorgenommen, so haben verschiedene Prozessoren voruebergehend
|
||
unterschiedliche Werte fuer die gleichen logischen Konzepte. Dies ist ein
|
||
Zustand, der nicht akzepziert werden kann.
|
||
|
||
Die Semantik von geteilten Datenobjekten in diesem Modell ist so definiert,
|
||
dass gleichzeitig ablaufende Operationen auf das gleiche Objekt konzeptionell
|
||
seriell ablaufen muessen. Die genaue Reihenfolge wie diese abgearbeitet
|
||
werden ist jedoch nicht exakt definiert. Wenn zum Beispiel eine
|
||
Leseoperation und eine Schreiboperation gleichzeitig auf ein Objekt
|
||
zugreifen wollen, kann es sein, dass die Leseoperation erst den Wert einliest
|
||
und dieser danach veraendert wird, oder aber, dass zuerst die Schreiboperation
|
||
den Wert veraendert und dann die Leseoperation diesen ausliest. Jedoch muessen
|
||
alle Prozesse, die Zugriff auf ein Objekt haben, soweit umsichtig sein, dass
|
||
sie erkennen, was die anderen Prozesse vollziehen und dass die Prozesse in
|
||
der richtigen Reihenfolge ablaufen.
|
||
|
||
Das RTS hat hier die Aufgabe, dass eben solche Inkonsistentzen nicht
|
||
vorkommen, und die Opertaionen, die Veraenderungen an einem Objekt vornehmen
|
||
in der richtigen Reihenfolge abgearbeitet werden. Ein Weg dies erfolgreich
|
||
zu realisieren wuerde darin bestehen, dass alle Kopien der Objekte fuer
|
||
jegliche Operationen gesperrt sind, mit Ausnahme der Kopie, die die hoechste
|
||
Prioritaet hat. Ungluecklicherweise verhaelt es sich aber so, dass das Sperren
|
||
von verteilten Objekten und ihren Daten aeusserst kompliziert ist. Das hier
|
||
verwendete Updateprotokoll benutzt nicht dieses Sperrverfahren. Das hier
|
||
verwendete Verfahren, soll in seinen wichtigsten Punkten kurz erlaeutert
|
||
werden:
|
||
|
||
* Jede Nachricht wird sofort an alle verfuegbaren Ziele geleitet.
|
||
* Wenn zwei Prozesse zur gleichen Zeit zwei Nachrichten (m1,m2) verschicken,
|
||
werden die Ziele immer zuerst m1 und dann m2 empfangen und auch in dieser
|
||
Reihenfolge verarbeiten.
|
||
|
||
Gemischte Formen, so dass einige Ziele erst m1 und dann m2, andere wiederum
|
||
erst m2 und dann m1 empfangen, werden durch geeignete Softwareprotokolle
|
||
verhindert.
|
||
|
||
Diese Punkte werden im allgemeinen von der untersten Schicht verwaltet, die
|
||
zu einem spaeteren Zeitpunkt beschrieben wird. Zum jetzigen Zeitpunkt nehmen
|
||
wir einfach nur an, dass eine einfache unteilbare sichere Uebertragung
|
||
existiert.
|
||
|
||
Das RTS benutzt einen Objektmanager fuer jeden Prozessor. Der Objektmanager
|
||
ist ein Leichtgewicht unter den Prozessen. Er ist mit der Aufgabe bertraut,
|
||
darauf zu achten, dass alle upgedateden Kopien der Objekte auf seinem
|
||
Prozessor gespeichert sind. Objekte und die Kopien davon werden in
|
||
Adressraeumen gespeichert. Diese werden durch den Objektmanager und den
|
||
Userprozessen aufgeteilt. Benutzerprozesse koennen lokale Kopien direkt
|
||
lesen, ohne dass sie mit dem Objektmanager in Beruehrung kommen.
|
||
Schreiboperationen, die auf geteilte Objekte zugreifen, muessen (werden) von
|
||
dem Objektmanager verwaltet werden, der auch dann dafuer sorgt, dass die Kopie
|
||
upgedated wird und dass die neuen Informationen an alle anderen Kopien, seien
|
||
sie lokal oder remote, geschickt werden.
|
||
|
||
Jeder Objektmanager ist fuer eine Schlange von Mitteilungen verantwortlich,
|
||
die er von Prozessen, die ein Objekt veraendern, erhalten hat. Wenn alle
|
||
Prozessoren die empfangenen Nachrichten in der gleichen Reihenfolge
|
||
verarbeiten wie sie eingetroffen sind, wird eine korrekte Arbeit ermoeglicht.
|
||
|
||
Der Objektmanager von jedem Prozessor "handelt" eine Schlange nach dem FIFO
|
||
Prinzip. Eine eingetroffene Nachricht wird dann bearbeitet, wenn sie am Kopf
|
||
der Schlange eingetroffen ist. Um eine Nachricht der Art GloablOperation
|
||
(obj, op, parameters) zu "handeln" wird diese Nachricht aus der Schlange
|
||
herausgenommen. Die lokalen Kopien des betreffenden Objektes werden
|
||
gesperrt. Lediglich eine Kopie ist offen, auf die die Operation zugreifen
|
||
darf. Ist der Zugriff erfolgt, gibt der Manager die Kopien wieder frei.
|
||
|
||
Schreiboperationen werden grundsaetzlich von Objektmanagern ausgefuehrt und
|
||
zwar in der gleichen Reihenfolge wie sie reinkommen. Wenn eine Leseoperation
|
||
aktiv wird und gleichzeitig eine Schreiboperation, so ist es je nach
|
||
Prioritaet moeglich, dass die Leseoperation vor der Schreiboperation oder nach
|
||
der Schreiboperation aktiv wird. Sie wird auf jeden Fall niemals zur
|
||
gleichen Zeit ausgefuehrt. Dieses Verhalten hat mit dem seriellen Prinzip zu
|
||
tun, welches oben beschrieben wurde.
|
||
|
||
4.3 Unterste Ebene: Sichere Uebertragung
|
||
|
||
In diesem Kapitel wird das einfache Protokoll beschrieben, das einer
|
||
bestimmten Gruppe von Nodes erlaubt, Nachrichten ueber die sichere
|
||
Uebertragung zu uebermitteln. Das Protokoll garantiert, dass alle Empfaenger
|
||
innerhalb der Gruppe, die entsprechende Nachricht auch empfangen koennen und
|
||
dass die Nachrichten auch in der richtigen Reihenfolge ankommen. Der
|
||
Hauptaspekt dieses Kapitels ist darzustellen, dass ein Protokoll mit einer
|
||
einfach gehaltenen Semantik effektiv arbeiten kann, ohne dass es noetig ist
|
||
genaue Details davon zu kennen.
|
||
|
||
Mit den derzeit verfuegbaren Mikroprozessoren und der LANtechnik ist das
|
||
Risiko, dass Pakete bzw. Nachrichten verloren gehen, sehr gross, von evtl.
|
||
enstehenden Hardwareschaden mal abgesehen. Daher ist die Wahrscheinlichkeit,
|
||
dass ein Fehler nahezu nie auftritt, nicht gegeben. Man muss mit den Fehlern
|
||
leben. Aus diesem Grund wird hier beschrieben, wie es moeglich ist, bereits
|
||
bestehenden Wege so zu nutzen, dass eine vernuenftige Kommunikation moeglich
|
||
ist. Dies ist aber nur dann moeglich, wenn das Errorhandling extrem komplex
|
||
ist.
|
||
|
||
Das grundlegende Protokoll der sicheren Uebertragung arbeitet wie folgt:
|
||
|
||
Wenn das RTS eine Message uebertragen moechte (M), schickt es diese Nachricht
|
||
an den Kernel. Dieser kapselt die Nachrichten dann in eine einfache
|
||
pointer-zu-Pointer Message und sendet sie zu einem besonders dafuer
|
||
einegrichteten Kernel, dem sogenannten Sequenzer. Dieser Sequenzer hat eine
|
||
Node. Diese Node hat die gleiche Hardware und den gleichen Kernel wie alle
|
||
anderen auch. Der einzige Unterschied besteht darin, dass einem Prozess ueber
|
||
ein Flag mitgeteilt wird, dass eine Nachricht fuer ihn vorhanden ist. Wenn nun
|
||
aber dieser Sequenzer zusammenbricht, versucht das System durch geeignete
|
||
Suche einen neuen Sequenzer, der dann das gleiche wie sein Vorgaenger
|
||
versucht. Ein System enthaelt im allgemeinen mehrere Sequenzer. Ganz moderne
|
||
Systeme haben sogar die Moeglichkeit, Sequenzer selbsstaendig zu erzeugen.
|
||
|
||
Der Sequenzer sortiert die Anfrage von allen Broadcast-Nachrichten indem er
|
||
jeder Nachricht eine Sequenznummer zuteilt. Wenn der Sequenzer alle
|
||
Nachrichten mit einem Pointer verbunden hat, beginnt er am Anfang und
|
||
arbeitet sich bis zur letzten Nachritennumer durch. Unter der Voraussetzung,
|
||
dass keinerlei Pakete verloren gegangen sind, ist nun leicht zu erkenen, was
|
||
passiert, wenn das RTS zwei Nachrichten auf einmal erhaelt. Eine davon kommt
|
||
als erste bei dem Sequenzer an und wird auch als erste an alle anderen Nodes
|
||
weitergeleitet fuer die sie bestimmt ist. Erst wenn diese Broadcast komplett
|
||
verarbeitet ist, wird die naechste in Angriff genommen. Der Sequenzer haelt
|
||
fuer das Handling von Nachrichten einen bestimmten Zeitpuffer bereit. Ist
|
||
dieser Zeitpuffer erfuellt, kann eine sichere Uebertragung garantiert werden.
|
||
|
||
Obwohl die meisten der modernen Netzwerke sehr sicher sind, sind sie nicht
|
||
perfekt. Daher ist es notwendig, dass jedes Protokoll mit Fehlern rechnen
|
||
muss. Die Gruende, die fuer eine fehlerhafte Uebertragung in Betracht kommen
|
||
koennen, liegen darin, dass die Kommunikation an sich fehlschlaegt, dass der
|
||
Puffer zu klein ist oder dass irgendwo ein Loch im Netz ist. Wenn eine
|
||
Broadcastnachricht ankommt wird ihr der Kernel sofort die Nummer geben, die
|
||
frei ist. Er ermittelt die letzte vergebene Nummer s und gibt ihr die Nummer
|
||
von s + 1. Ensteht nun ein Abstand zwischen der letzten Nummer und der nun
|
||
vergebenen, der groesser ist als 2, weiss der Sequenzer, dass ein Fehler
|
||
aufgetreten ist.
|
||
|
||
Wie bekannt ist, hat der Sequenzer nur eine bestimmte Kapazitaet zum
|
||
Speichern von Nachrichten. Somit ist nicht gewaehrleistet, dass er Nachrichten
|
||
fuer immer und ewig speichern kann. Jedoch kann er feststellen ob eine
|
||
bestimmte Anzahl k, von ihm verschickte Nachrichten ihr Ziel erreicht haben.
|
||
Ist ihm dies bekannt, kann er diese Nachrichten bei sich loeschen.
|
||
|
||
Das Protokoll bietet mehrere Moeglichkeiten an, dem Sequenzer mitzuteilen, ob
|
||
Informationen fuer ihn vorhanden sind oder nicht. Jede Nachricht, die zu dem
|
||
Sequenzer durchdringt, enthaelt ein Header-Feld, die letzte Nummer, die der
|
||
versendende Prozess ihm mitgegeben hat. Auf diese Art und Weise kann der
|
||
Empfaenger (Sequenzer) feststellen, ob eine Nachricht unterwegs verloren
|
||
gegangen ist oder nicht. Er wird also solange warten, bis er alle
|
||
Nachrichten lueckenlos empfangen hat. Hat er diese dann in der richtigen
|
||
Reihenfolge weitergeleitet und von dem Ziel eine Empfangsbestaetigung
|
||
erhalten, kann er die entsprechenden Mails aus seinem Puffer loeschen.
|
||
|
||
Sollte der Fall eintreten, dass ein Node keinerlei Uebertragung zu bewaeltigen
|
||
hat, kann dies der Sequenzer nicht wissen; er bleibt in dem aktuellen Modus.
|
||
Nach einem defaultmaessigen Zeitintervall wird jedoch seine Prioritaet
|
||
herabgestuft. Wenn das Gegenteil eintritt, der Speicherplatz fuer die
|
||
Nachrichten also ueberlaeuft, so hat der Sequenzer die Moeglichkeit, Teile der
|
||
Nachrichten an einen anderen Sequenzer weiterzuleiten. Allerdings muss darauf
|
||
geachtet werden, dass die Nachrichten, die versendet werden, auch als ganzer
|
||
Block zusammenh<6E>ngen. Dies ist aber recht leicht zu realisieren, da alle
|
||
Nachrichten ja bekanntlich ueber eine Indexnumerierung verfuegen.
|
||
|
||
Beide der hier vorgestellten Protokolle sollen implementiert werden. Das
|
||
zweite Protokoll unterscheidet sich zum Ersten dahingehend, dass es keine
|
||
Nachrichten an den Sequenzer schickt. Stattdessen verschickt der Sender die
|
||
entsprechende Nachricht sofort. Dies hat natuerlich auf der einen Seite den
|
||
Vorteil, dass die Nachrichten schneller uebertragen werden, jedoch ist der
|
||
Nachteil, dass die Nachrichten durcheinander und nicht vollstaendig ankommen,
|
||
viel groesser.
|
||
|
||
Beide Protokolle haben die gleiche Semantik. Jedoch verhalten sich beide
|
||
Konzepte unterschiedlich, je nachdem unter welchen Bedingungen (Hardware)
|
||
sie laufen. In der ersten Methode wird grundsaetzlich jede Nachricht zweimal
|
||
versendet (einmal zum Sequenzer und einmal vom Sequenzer zu der eigentlichen
|
||
Zieladresse). Methode 2 hingegen benoetigt weniger Bandbreite auf dem
|
||
Netz.(Die Nachrichten tauchen also nur einmal auf). Um TQ zu implementieren,
|
||
wurde die erste Methode verwendet, weil die Nachrichten vom RTS verwaltet
|
||
werden und weiterhin weniger Interrupts benoetigt werden, um die
|
||
Applikationen zu handeln.
|
||
|
||
Man kann dies alles auch noch philosophischer sehen, dann aber weicht man
|
||
von den grundlegenden Konzepten ab und landet im Nirvana. In unserem Fall
|
||
kann eine Nachricht zwischen zwei Usern am schnellsten gehandelt werden, da
|
||
die einzelnen Nodes der Sequenzer immer bereit sind, Nachrichten zu
|
||
empfangen und sie als Pakete schnellstmoeglich zu versenden. Hinzu kommt
|
||
noch, dass im Normalfall weniger Kontrollmoeglichkeiten notwendig sind. Das
|
||
hier erwaehnte Protokoll ist in diesem Punkt besonders effizient. Es setzt
|
||
jedoch voraus, dass die Operationen stets als "normal" angesehen werden.
|
||
Weiterhin werden ja nur zwei Packete benoetigt, um Nachrichten von einem USER
|
||
zum naechsten zu verschicken. Ein Vergleich zwischen dem hier gezeigten
|
||
Protokoll und anderen bekannten Protokollen folgt weiter unten.
|
||
|
||
4.4 Ein Vergleich mit einem auf RPC-basierendem Protokoll.
|
||
|
||
Wie wir oben bei der Beschreibung der Implementierung von TQ gesehen haben,
|
||
basiert dieses System auf dem Kopieren von Objekten auf einem verteilten
|
||
Updateprotokoll. Hierbei wird die sichere Datenuebertragung benutzt. Nun
|
||
werden wir sehen, wie es in einem anderen Fall, dem Remote Procedure Call,
|
||
aussieht.
|
||
|
||
Das Arbeiten mit Kopien unter RPC ist ein weitaus komplizierterer Fall, als
|
||
wenn man sie in der sicheren Uebertragung einsetzt. Das Problem besteht
|
||
darin, dass alle Kopien auf eine konsistente Weise upgedated werden muessen.
|
||
Um diese Konsistenzen sicher zu stellen, verfuegt das RPC System ueber ein
|
||
zwei-Phasen Modell-Protokoll. Waehrend der ersten Phase werden alle Kopien
|
||
upgedated und gelockt. Sind alle Updates fertig, beginnt die zweite Phase.
|
||
Diese hat nun die Aufgabe die Kopien wieder zu unlocken.
|
||
|
||
Jedoch ist dieses Protokoll recht teuer, da die Zeit bis das Update gefahren
|
||
ist davon abhaengt, wie viele Kopien vorhanden sind, die upzudaten sind.
|
||
Daher macht es viel Sinn, eine partitiale Kopiestrategie einzusetzen. Diese
|
||
hat die Aufgabe nur die Kopien zu erstellen und eben nur die upzudaten, die
|
||
auch wirklich gebraucht werden. Das RPC Modell verfuegt ueber eine Statisktik,
|
||
mit der es erfahren kann, wieviel Schreib/Leseprozesse von einem Prozess fuer
|
||
jedes Objekt ausgehen. Auf dieser Information basierend, entscheidet es
|
||
dynamisch, wo das Objekt zu speichern und ob eine Kopie anzufertigen ist und
|
||
wo sich diese zu befinden hat. Das System kann dynamisch feststellen, ob
|
||
eine Kopie zu erzeugen oder zu loeschen ist.
|
||
|
||
Die Statistik steht praktisch ueber den einzelnen Operationen. Jedoch ist es
|
||
meistens so, dass in der Realitaet diese Statistiken oft ueber den Haufen
|
||
geworfen werden, weil je nach Anwendung oder Auslastung starke Abweichungen
|
||
herrschen. In den meisten Faellen hat das RPC System hoehere Kosten als das
|
||
das Broadcastsystem, wenn es um die Kommunikation geht. Fuer das TSP Program
|
||
zum Beispiel ist es effizienter die global gebundene Variable ueber eine
|
||
einzelne Broadcastmessage upzudaten als ueber multiple RPCs.
|
||
|
||
Das RPC System ist jedoch effizienter wenn die Rate der
|
||
Schhreib/Lesezugriffe auf ein Objekt niedrig ist. In diesem Fall wird das
|
||
Broadcastsystem eine Kopie anfertigen jedoch das RPC System wird erst das
|
||
Verhalten der Operationen beobachten und dann dynamisch entscheiden, das
|
||
Objekt nicht zu kopieren.
|
||
|
||
5. Leistung einer Applikation
|
||
|
||
In diesem Kapitel werden wir einen kurzen Ueberblick ueber die
|
||
Leistungsfaehigkeit von Programmen geben, die in TQ geschrieben sind. Ziel
|
||
ist es zu zeigen, dass mit TQ besonders im Bereich der
|
||
Geschwindigkeitsvorteile gute Ergebnisse zu erzielen sind.
|
||
|
||
5.1 Das parallele Problem des Verkaeufers.
|
||
|
||
Dieses Problem wurde bereits weiter vorne beschrieben. Das Programm benutzt
|
||
zwei geteilte Objekte:
|
||
|
||
Eine JobQueue und ein InObject, welches die Laenge des besten Pfades
|
||
beinhaltet. Es sollte klar sein, dass das Lesen des aktuellen besten Pfades
|
||
ein Vorgang ist, der sehr oft wiederholt wird. Jedoch (oder
|
||
gluecklicherweise) handelt es sich hierbei um eine lokale Operation. Es ist
|
||
keinerlei Kommunikation notwendig. Das Updaten des besten Weges passiert
|
||
nicht so haeufig. Trotzdem verlangt dies eine Broadcastnachricht.
|
||
|
||
Obwohl Updates des besten Pfades unregelmaessig geschehen, ist es wichtig, die
|
||
dazugehoerigen Nachrichten so schnell wie moeglich an den richtigen Platz zu
|
||
bringen. Benutzt naemlich ein Benutzer einen alten Wert, so kann es
|
||
vorkommen, dass er als neuen Pfad einen ermittelt, der nicht mehr aktuell ist
|
||
bzw. der schon vergeben ist. Mit anderen Worten, der Benutzer wuerde mehr
|
||
Nodes berechnen als notwendig. Dieser unnoetige Suchweg macht sich bei
|
||
mehreren Wiederholungen zu einem negativen Faktor breit, der unschoene
|
||
Seiteneffekte hat.
|
||
|
||
5.2 Das parallele "All-pairs shorttest Path" Problem
|
||
|
||
Die zweite Applikation, die wir beschreiben m<>chten ist die ASP. Hierbei
|
||
geht es darum, die Laenge des kuerzesten Pfades zu finden, wobei zwei Punkte
|
||
gegeben sind (i,j), die durch einen Graphen abgebildet werden. Der parallele
|
||
Algorithmus ist der FLOYD-Algorithmus. Die Abst<73>nde zwischen den Nodes
|
||
werden in einer Matrix dargestellt. Jeder Prozessor berechnet einen Teil der
|
||
Gesamtmatrix. Der Algorithmus verlangt eine nicht triviale Kommunikation
|
||
zwischen den einzelnen Prozessoren, was sich ebenso auf die Synchronisation
|
||
auswirkt.
|
||
|
||
5.3 Successive Overrelaxtion
|
||
|
||
Beide Probleme (TSP und ASP) haben von dem Broadcasting-System profitiert.
|
||
Wir betrachten nun eine Applikation, die nur eine einfache Message Passing
|
||
Methode benoetigt. Diese Applikation nennt man Successive Overrelaxtion.
|
||
Hierbei handelt es sich um eine iterative Methode diskrete Laplace
|
||
Gleichungen in einem Gatter zu loesen. W<>hrend jeder Iteration besucht der
|
||
Algorithmus alle Punkte innerhalb des Gatters. Fuer jeden Punkt berechnet es
|
||
den Wert seiner 4 Nachbarn und fuehrt dann ein Update auf den aktuellen Punkt
|
||
mit dem eben berechneten Wert.
|
||
|
||
Wir haben SOR parallelisiert indem wir das Gatter in verschiedene Regionen
|
||
eingeordnet und jede Region einem anderen Prozessor zugeteilt haben. Die
|
||
Aufteilung des Gatters ist der erste Schritt der Iteration. Jeder Prozessor
|
||
muss Werte mit einem anderen Prozessor austauschen. Der Algorithmus selbst
|
||
jedoch benoetigt nur ein einfaches Message Passing. Mit der derzeitigen
|
||
Prototyp Implementierung, bei der die Kommunikation auf dem Broadcasting
|
||
beruht, ist das so nicht moeglich bzw. es schleichen sich imense Fehler ein,
|
||
so dass eine genaue Berechnung nicht mehr moeglich ist. Das Message Passing
|
||
wird in TQ dadurch simuliert, dass der Sender und der Empfaenger ein geteiltes
|
||
Pufferobjekt gemeinsam benutzen. Da aber alle Objekte durch das Broadcasting
|
||
upgedated werden, erhalten alle Prozessoren ein Update, also auch die, die
|
||
gar kein Update benoetigen, weil sie entweder wirklich keins brauchen oder
|
||
dann, wenn sie eins bekommen, ein falsches erhalten und mit einem falschen
|
||
Wert dann weiterrechnen. Somit ist festzustellen, dass dieses Beispiel fuer TQ
|
||
so ungeeignet ist wie ein Porzelanladen fuer einen Elefanten.
|
||
|
||
6. Sonstige Arbeiten
|
||
|
||
In diesem Kapitel wollen wir unsere Sprache mit bereits existierenden
|
||
relationalen Sprachen und Systemen vergleichen. Im einzelnen werden wir uns
|
||
mit Linda's Tupel Space und geteiltem virtuellem Speicher beschaeftigen.
|
||
|
||
Objekte
|
||
Objekte werden in den meisten objekt-basierenden Sprachen fuer die parallele
|
||
oder distributiere Programmierung eingesetzt. Emerald, Amber und ALPS sind
|
||
hierfuer typische Beispiele. Objekte bestehen im allgemeinen aus zwei Teilen:
|
||
|
||
1. Die eingekapselten Daten und
|
||
2. Ein Managerprozess, der ueber diese Daten wacht.
|
||
|
||
Auf die Daten wird durch das Senden einer Mitteilung an den Managerprozess
|
||
zugegriffen. Es wird also eine Art Antrag gestellt. Dieser Vorgang wird fuer
|
||
jede Operation erneut wiederholt. Wenn auf die entsprechenden Objekte schon
|
||
eine Operation laeuft, wird dem neuen Prozess dies mitgeteilt. Gleiches gilt
|
||
fuer die Daten innerhalb des Objektes.
|
||
|
||
Obwohl in einigen Faellen objekt-orientierte Sprachen es zulassen, dass
|
||
Prozesse (Objekte) auf geteilte Daten (Objekte) ohne groessere
|
||
Sicherheitsvorkehrungen zugreifen duerfen, ist es ratsam, zumindest ein
|
||
Message Passing in diese Aufgabe zu integrieren. In ALPS zum Beispiel muessen
|
||
alle Operationen, die auf ein Objekt zugreifen wollen, eben durch den oben
|
||
erwaehnten Prozessmanager. Dieser regelt dann die Reihenfolge, wie die
|
||
entsprechenden Operationen abgearbeitet werden. Wenn man diese
|
||
Marschrichtung einschlaegt, muss man wie folgt vorgehen:
|
||
|
||
Man muss das Objekt auf einem genau spezifizierten Prozessor speichern. Man
|
||
darf aber nicht vergessen, dass der dazugehoerige Managerprozess und alle mit
|
||
ihm und dem Objekt verbundene Operationen ebenfalls dort vorhanden sein
|
||
muessen.
|
||
|
||
Unser Modell verfuegt ueber keine solche zentralisierte Kontrolle. Objekte in
|
||
TQ sind passive "Gegenstaende", die lediglich Daten enthalten, jedoch nicht
|
||
ueber einen Managerprozess verfuegen. Die Zugriffskontrolle auf die geteilten
|
||
Datenobjekte ist verteilt. Sie wird durch folgende Regeln kontrolliert:
|
||
|
||
1. Operationen muessen unteilbar ausgefuehrt werden.
|
||
2. Operationen sind solange gesperrt, solange ihre Waechter den Zustand FALSE
|
||
einnehmen.
|
||
|
||
Daher kann das Modell auf multiplen Prozessorsystemen laufen und mit
|
||
kopierten Datenobjekten arbeiten. Wies dies funktioniert, haben wir in
|
||
Kapitel 4 gesehen. Leseoperationen koennen ohne irgendeine Nachricht auf
|
||
Objekte zugreifen. Darueber hinaus koennen Leseprozesse, die von verschiedenen
|
||
Prozessoren kommen, gleichzeitig auf ein Objekt zugreifen, ohne dass der
|
||
Parallelismus dadurch beeintraechtigt wird.
|
||
|
||
Linda's Tupel Space
|
||
|
||
Linda ist eine der ersten Sprachen, die die Nachteile eines zentralisierten
|
||
Managerprozesses erkannt hat, wenn es um die Ueberwachung von geteilten Daten
|
||
geht. Linda unterstuetzt die sogenannten verteilten Datenstrukturen. Auf
|
||
diese kann gleichzeitig durch mehrere Prozesse zugegriffen werden. Im
|
||
Gegensatz zu objekt-basierenden Sprachen, die typischerweise alle seriellen
|
||
Zugriff auf geteilte Datenstrukturen haben. Linda benutzt das sog. 'Tupel
|
||
Space' Modell um verteilte Datenstrukturen zu implementieren.
|
||
|
||
Im allgemeinen werden die verteilte Datenstrukturen mit Hilfe von multiplen
|
||
Tupeln zusammengebaut. Auf die verschiedenen Tupeln kann unabhaengig von
|
||
einander zugegriffen werden. Auf diese Art und Weise koennen Prozesse auf
|
||
verschiedene Tupel innerhalb der gleichen Datenstruktur zugreifen. Im
|
||
Prinzip koennen multiple Leseoperationen auf ein und das gleiche Tupel
|
||
simultan vollzogen werden. Tupel werden (konzeptionell) erst dann
|
||
modifiziert, wenn sie aus dem Tupel Space entfernt wurden. Daher ist es nur
|
||
moeglich, Tupel sequentiell zu modifizieren.
|
||
|
||
Obwohl die Idee von verteilten Datenstrukturen recht neu und teilweise auch
|
||
gut ist, denken wir, dass sie doch entscheidende Nachteile hat. Fuer verteilte
|
||
Systeme werden die Datenstrukturen aus einzelnen Tupeln und explizter
|
||
Synchronisation automatisch zusammengebaut, weil es schlicht und ergreifend
|
||
keinen anderen Weg gibt. Operationen auf komplexe Datenstrukturen (bestehend
|
||
aus multiplen Tupeln) muessen vom Programmierer explizit angegeben werden.
|
||
Tupel Space unterstuetzt eine bestimmte Anzahl von eingebauten Operationen,
|
||
welche als unteilbar ausgefuehrt werden. Aber die Unterstuetzung fuer sehr
|
||
komplexe unteilbare Operationen findet auf einem sehr niedrigen Niveau
|
||
statt.
|
||
|
||
In TQ jedoch kann der Programmierer seine eigenen komplexen Operationen
|
||
selbst definieren, die er dann auf die geteilten Datenstrukturen loslassen
|
||
kann. All diese Operationen werden als ungeteilt ausgefuehrt. Auf diese Art
|
||
und Weise findet die exklusive Synchronisation automatisch durch das RTS
|
||
statt. Dies bedeutet, dass es die Aufgabe der Implementation ist (Compiler
|
||
und RTS) zu pruefen, welche Operationen parallel auf eine lokale Kopie eines
|
||
Objekt aus gefuehrt werden koennen und welche nicht. Eine solche
|
||
Implementation ist natuerlich viel feinkoerniger und auch schwieriger zu
|
||
implementieren.
|
||
|
||
Geteilter verteilter Speicher SVM simuliert den physikalisch geteilten
|
||
Speicher aus einem verteilten System. Es partitioniert den globalen
|
||
Adressspeicher in einzelne Seiten, die eine feste Groesse haben. Jeder
|
||
Prozessor erhaelt die gleiche Anzahl von Seiten. Wenn ein Prozess versucht auf
|
||
eine Seite zuzugreifen, die nicht vorhanden ist, so wird ein "Page-Fault"
|
||
zurueckgegeben und das System nimmt den Prozess wieder zurueck, egal auf
|
||
welchem Prozessor er sich befindet. Leseseiten koennen zwischen den einzelnen
|
||
Prozessoren aufgeteilt werden. Seiten, die beschreibbar sind, koennen nur auf
|
||
einer Maschine sein und nicht geteilt werden. Wenn nun ein Prozessor eine
|
||
Seite modifizieren moechte, muss er zuerst alle anderen Kopien auf allen
|
||
anderen Prozessoren ueberpruefen.
|
||
|
||
Es gibt viele wichtige Unterschiede zwischen unserem Modell und dem SVM
|
||
Modell bezueglich dem Betriebssystem was die Benutzung der MMU Register
|
||
anbelangt. In TQ ist jedes Uebertragungsprotokoll ausserhalb des
|
||
Betriebssystems implementiert. Diese Tatsache gibt dem SVM einen grossen
|
||
Leistungsvorteil, dort naemlich sind diese Implementierungen in das
|
||
Betriebssystem mit eingeschlossen.
|
||
|
||
Nichts desto trotz hat unser Modell gegenueber SVM einige Vorteile. Zuerst
|
||
werden geteilte Datenobjekte nur von wohldefinierten 'High-Level'
|
||
Operationen modifiziert. SVM benutzt hierfuer low-level Operationen wie
|
||
read/write um auf die Objekte zugreifen zu koennen. Weiterhin haben wir die
|
||
Moeglichkeit, dass man zwischen einer Ueberpruefung der Objekte nach jeder
|
||
Schreiboperation oder ob man alle Kopien gleichzeitig updated (bzw. ihnen
|
||
einfach den neuen Wert zusendet). Bei SVM hat man diesbezueglich keinerlei
|
||
Wahl. Hier findet ein Ueberpruefen der einzelnen Seiten statt. In vielen
|
||
Faellen jedoch hat sich gezeigt, dass dieses Verfahren nicht so effizient ist
|
||
wie das Anfertigen und updaten von einzelnen Kopien.
|
||
|
||
Einzelne Wissenschaftler haben versucht dieses Problem zu loesen, indem sie
|
||
den Speicher als konsistent angesehen haben, was er allerdings nicht ist.
|
||
Diese Speicher haben aber trotzdem eine sehr hohe Leistungsfaehigkeit, jedoch
|
||
hat diese nur fuer einen bestimmten Zeitraum bestand und ist weiterhin davon
|
||
abhaengig, wie sehr das System belastet wird. TQ Programmierer sollten
|
||
(brauchen) sich ueber die Konsistenz des Speichers keine Sorgen zu machen.
|
||
Der Compiler soll dieses Problem uebernehmen und bei fehlerhaften Handhabung
|
||
dem Programmierer eine entsprechende Meldung ausgeben.
|
||
|
||
Ein zweiter, wichtiger Unterschied zwischen TQ und SVM sind die verteilten
|
||
Daten. Unter SVM betraegt die Groesse der geteilten Seiten 4k. In TQ wird sie
|
||
durch die Groesse der Objekte bestimmt, welche wiederum vom Benutzer
|
||
festgelegt wird. Somit kann es durchaus passieren, dass eine Seite im SVM zu
|
||
klein ist und auf eine weitere Seite zugegriffen werden muss.
|
||
|
||
Zusammenfassung
|
||
|
||
Wir haben hier eine neue Sprache zur Erstellung paralleler Applikationen auf
|
||
verteilten Systemen vorgestellt. Im Vergleich zu den meisten anderen
|
||
Modellen erlaubt es, auf geteilte Daten von verschiedenen Prozessoren
|
||
zuzugreifen. Die Schluesselidee unseres Modells ist es, geteilte Daten in
|
||
Datenobjekte einzukapseln und auf diese Objekte mit benutzerspezifizierten
|
||
Operationen zuzugreifen. Weiterhin sind Operationen auf Objekte immer nur
|
||
unteilbare Operationen. Die exklusive Synchronisation wird automatisch
|
||
vollzogen. Dies hat Vorteile bei der Programmierung. Bedingte
|
||
Synchronisation ist bei Prozessen, die im Hintergrund ablaufen moeglich. Der
|
||
Mechanismus Operationen im Hintergrund ausfuehren zu lassen, ist einfach zu
|
||
benutzen und ist fuer den Implementierer frei verfuegbar und wird auch
|
||
offengelegt.
|
||
|
||
Die Implementierung unseres Modells nimmt starke Ruecksicht auf die
|
||
physikalische Veteilung von geteilten Daten zwischen den einzelnen
|
||
Prozessoren. Im einzelnen, kopiert die Implementierung die einzelnen
|
||
Datenobjekte so, dass jeder Prozess die Kopie als solche direkt lesen kann,
|
||
sofern die Kopie zu seinem eigenen Prozessor gehoert. Nach einer
|
||
Schreiboperation werden alle Kopien upgedated, so dass jeder Prozessor mit
|
||
der jeweils gleichen Version arbeiten kann. Dieses ist aber nur moeglich,
|
||
weil die Zugriffe auf die geteilten Daten ausschliesslich ueber
|
||
benutzerdefinierte Funktionen zugaenglich sind. SVM z.B. kann keine
|
||
effiziente Updatestrategie verfolgen, weil die Instruktionen die auf die
|
||
Datenobjekte zugreifen alle von Maschineninstruktionen vollzogen werden. Aus
|
||
der 'Low-Level' Ebene heraus eine Updatestrategie zu fahren, ist ein sehr
|
||
ineffizienter Vorgang, der eine optimale Kommunikation nur schwer
|
||
ermoeglicht.
|
||
|
||
Weiterhin haben wir TQ als eine Sprache vorgestellt,die auf geteilten
|
||
Datenobjekten basiert. TQ glaubt, die Probleme zu loesen, die andere Sprachen
|
||
haben. Sie verzichtet auf Konstrukte wie Pointer und globale Variablen. Auch
|
||
ist es das Ziel, die Sprache so klar und einfach wie moeglich zu halten. Wie
|
||
Programme aussehen koennen, haben wir an kurzen Programmausschnitten
|
||
aufgezeigt.
|
||
|
||
Wir haben gezeigt, wie eine Implementierung von TQ aussehen kann. Es ist
|
||
durchaus denkbar, dass eine solche Implementierung auf verschiedene
|
||
Prozesoren moeglich ist. Das Basissystem auf dem TQ entwickelt werden soll
|
||
ist entweder Minix 1.7.1 oder der V8-SPARC-POOL der VU-Amsterdam. TQ an sich
|
||
selbst ist nicht Netzwerkabhaengig. Das einzige was benoetigt wird, wenn man
|
||
TQ portieren moechte, ist eine neue RTS.
|