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 ä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ä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 ä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ä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ä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.