Bevor ich die nebenläufige Berechnung in ToonTalk erläutere und daruf eingehe weshalb es schwierig ist, sequentielle Sprachen auf Parallelität zu erweitern, werde ich die Beziehung zwischen Nebenläufigkeit, Parallelität und verteiltes Berechnen erklären.Parallele Prozesse sind Prozesse, die alle auf dem selben Computersystem ausgeführt werden. Das System hat typischerweise mehr als einen Prozessor. Verteilte Prozesse sind Prozesse, die auf verschiedenen Computersystemen, die durch ein Netzwerk verbunden sind, ablaufen. Der Unterschied zwischen parallel und verteilt ist wichtig, da eine verteilte Berechnung typischerweise eigentums- oder organisationsübergreifend durchgeführt wird. Deshalb muß nur bei der veteilten Berechnung Sicherheit, Allokierung von Ressourcen, Recovery bei Hardwarefehlern etc. berücksichtigt werden.Wo im folgenden der Unterschied nicht wichtig ist, werde ich diese Prozesse als nebenläufige Prozesse bezeichnen, d.h. Prozesse, die entweder parallel oder verteilt ausgeführt werden.
ToonTalk ist durch und durch eine nebenläufige Programmiersprache, da alle Teilberechnungen als neue unabhängige Prozesse ausgedrückt werden. Falls ein Roboter einen anderen Roboter benötigt, um einige Teilberechnungen auszuführen, muß er so trainiert werden, daß er einen Lastwagen mit den anderen Robotern belädt. Das neue Haus, das von dieser Crew im Lastwagen gebaut wird, ist ein neuer Prozeß.
Im Gegensatz zu üblichen Programmiersprachen (C, Java, Logo, Lisp, Fortran, Cobol, Perl, Basic, etc.) gibt es in ToonTalk keine Möglichkeit, eine Unterroutine aufzurufen. Ein Prozeduraufruf überträgt die Kontrolle an die Prozedur, so daß das Program so lange warten muß bis die Prozedur beendet ist. Manchmal liefert sie nach dem Beenden auch einen Wert zurück. Danach führt das aufrufende Programm seine Ausführung dort fort, wo sie sie vor dem Prozeduraufruf unterbrochen hat. Man kann das selbe Verhalten generieren, wenn man einen Roboter trainiert, einen Lastwagen mit Robotern und einer Schachtel mit einem Vogel darin zu beladen. Der Roboter braucht nicht anderes zu tun, als das Nest des Vogels in seine Schachtel zu legen. Der Roboter oder andere Mitglieder seines Team müssen dann nur noch so programmiert werden, daß er auf Gegenstände in dem Nest wartet. Dieser Prozeß unterbricht solange die Berechnung bis einer der Roboter, mit denen der Lastwageen beladen wurde, dem Vögel etwas für das Nest geben. Nachdem der Vogel dann etwas in das Nest legt, führt der wartende Roboter die Berechnung fort. Mit anderen Worten ist der Aufruf einer Unterroutine oder einer Prozedur nur eine bestimmte Benutzung von Lastwagen, Vögeln und Robotern. ToonTalk stellt dem Programmierer hier nur die viel generellere Funktionalität des Aufspannens von neuen Prozessen zur Verfügung.
Das Fehlen von Unterroutinen führt dazu, daß man in ToonTalk die Möglichkeit hat, viel mehr Prozesse aufzuspannen als in konventionellen Programmiersprachen. In konventionellen Programmiersprachen ist der Aufruf von Unterroutinen mit einer Dataenstruktur implementiert, die man als Keller bezeichnet. Ein Keller ist eine sehr effiziente Art, den Aufruf von Unterroutinen inklusive rekursiver Aufrufe zu implementieren. Das Problem bei mehreren Prozessen hierbei ist, daß jeder Prozeß (auch wenn er wartet ) im Prinzip seinen eigenen Keller benötigt. Das führt dazu, daß Prozesse ziemlich aufwendig in der Implementierung sind. In ToonTalk benötigt jeder Prozeß nur 2 Zeiger: zum Programm (Team der Roboter) und zu den Daten (einer Schachtel). Ein Prozeß benötigt keinen Keller; und sonst auch nichts. Wir haben ToonTalk mit zehntausenden von Häusern (d.h. Prozessen) getestet. Im Gegesatz dazu war Java schon bei wenigen hundert Prozessen nicht mehr funktionsfähig.
Konventionelle Programmiersprachen haben einen gemeinsamen Zustandsraum. Die gleichen Variablen, Datenstrukturen und Objekte können von verschiedenen Prozessen aus zugegriffen werden. Der gemeinsame Zustandsraum ist in diesen Sprachen für die Kommunikation von sog. Threads notwendig (Prozesse mit gemeinsamen Daten werden oft auch als Threads bezeichnet). Das Teilen eines gemeinsamen Bereichen mit anderen Therads kann aber auch sehr gefährlich sein. Es kann zu sog. Race Bedingungen führen. Betrachtet man z. B. eine Variable A, die den aktuellen Stand auf einem Bankkonto speichert (A kann eine globale Variable oder die Instanz eines Objekts sein ß beides führt zu Problemen). Eine Unterroutine kann z. B. einen Betrag X von dem Konto nur dann abheben, falls X kleiner oder gleich dem aktuellen Kontostand von A ist, d. h. das Abheben ist nur erlaubt, falls genug Geld auf dem Konto ist. Das Abheben wird z. B. durch die Operation A-X imlementiert. Jetzt kommt Parallelität ins Spiel. Angenommen auf dem Konto sind 10 Euros, ein Prozeß möchte gern 9 Euros und eine anderer Prozeß möchte gern 8 Euros abheben. Wenn es unglücklich läuft, können beide Aktionen durchgeführt werden. Wenn es ganz unglücklich kommt, kann der endgültige Kontostand nach dem Beenden der beiden Aktionen1 Euro, 2 Euros oder sogar -7 Euros sein. Wie kann das sein? Man stelle sich folgende Reihenfolge vor:
Prozeß 1 überprüft, daß X weniger als A ist und berechnet A-X (10-9=1) mit 1. Bevor aber 1 and A zugewiesen wird, fängt Prozeß 2 mit der Berechnung an, sieht, daß A immer noch 10 ist, berechnet 10-8=2 und setzt den Kontostand A auf 2. Dies wird von Prozeß 1 nicht bemerkt, der den Kontostand A schließlich auf 1 setzt.
Wie gehen konevtionelle Sprachen mit diesen Race Bedingungen um? Sie führen neue Programmierkonstrukte wie Locks oder kritische Regionen ein. Z. B. kann der Prozeduraufruf eines Prozeßes zum Abheben ein Lock auf A durchführen (d. h. die Variable A sperren), so daß kein anderer Prozeß auf die Variable zugreifen darf. Der Prozeß kann jetzt die Variable A sicher mit dem Wert X vergleichen, A-X berechnen, und das Ergebnis A zuweisen. Schließlich muß der Lock auf A aufgehoben werden sonst kann nie wieder ein anderer Prozeß auf die Variable A zugreifen. Dieses Verfahren bedeutet nicht nur erhöhten Programmieraufwand, sondern es führt auch zu einem neuen Problem, dem sog. Deadlock Angenommen Prozeß 1 führt ein Lock auf A durch und benötigt bei der Berechnung den Wert von Variable B, auf die ein Lock von Prozeß 2 durchgeführt wurde. Daraufhin suspendiert Prozeß 1 wartet bis der Lock von Prozeß 2 augehoben wird. Was passiert aber, wenn umgekehrt Prozeß 1 den Wert von Variable A benötigt? Variable A ist mit einem Lock belegt, so daß Prozeß 2 auch suspendiert. Dieser Zustand wird auch als tödliche Umarmung bezeichnet. Man könnte meinen, daß es einfach ist, so zu programieren, um diese Art von Abhängigkeit zu erkennen und zu vermeiden. Die Abhängigkeit kann aber hunderte von Prozeßen betreffen.
Wieso treten diese Probleme nicht bei ToonTalk auf? Der Grund ist, daß Prozeße in ToonTalk keinen gemeinsamen Zustand haben. Eine Schachtel kann immer nur an einem Ort sein. Und Roboter in gleichen Haus haben eine Reihenfolge - sie arbeiten niemals mit der gleichen Box zur selben Zeit. Hierdurch werden in ToonTalk Races und Deadlocks vermieden. Aber leidet heirdurch nicht die Ausdrucksstärke der Sprache? Dies würde der Fall sein, wenn es keine Vögel gäbe. Die Tatsache, daß Kopien eines Vogel zum selben Nest fliegen können, stellt die Möglichkeit einer n:1-Kommunikation zur Verfügung, die anstelle von gemeinsamen Variablen (eines gemeinsamen Zustands) verwendet werden können. Betrachtet man z. B. das Beispiel des ToonTalk Bankkontos. Mehrere Prozesse können von ein und dem selben Konto Geld abheben. Roboter aus verschiedenen Häusern können Aufträge zum Abheben senden indem sie einen Vogel mit einer Schachtel, die den abzuhebenden Betrag beinhaltet, absenden. Jeder Prozeß hat die Kopie eines Vogels dessen Nest sich in der Schachtel befindet, die dem Konto entspricht. Roboter in verschiedenen Häusern können den Vögeln Aufträge in form von Schachteln mit abzuhebenden Beträgen übergeben. Es kann nicht vorhergesagt werden, welcher Auftrag als oberstes auf dem Nest landet - es werden aber alle auf dem Nest gestapelt, d.h. die Aufträge werden auf dem Nest gesammelt und können dann abgearbeitet werden. Die Roboter sehen die ankommenden Aufträge, die auf dem Nest gesammelt werden und arbeiten sie dann einyeln der Reihe nach ab. Dies führt somit zu keinem Problem slebst dann nicht, wenn der neue Kontostand zusätzliche Teilberechnungen benötigt. Der Roboter belädt dann einen Lastwagen mit einem Behälter und anderen Robotern zur Berechnung des neuen Kontostands. Das Nest mit der Antwort des neuen Kontostands wird dann an dem Ort plaziert an dem der aktuelle Kontostand gespeichert ist. Der nächste Auftrag wird nicht bearbeitet bevor nicht der Wert des neuen Kontostands von dem Vogel zurückgeliefert wurde.
Zusammenfassend läßt sich festhalten, daß alle Versuche
Programmiersprachen mit Unterroutinen und gemeinsamen Zustandsraum um Nebenläufigkeit
zu erweitern zu erhöhter Komplexität, aufwendigen Implementierungen
und Fehlern im Programmieren, die schwer zu beheben sind, führten.
Im Gegegsatz hierzu wurde ToonTalk hinsichlichlich inhärenter Nebenläufigkeit
neu entworfen.ToonTalk benötigt keine Locks oder kritische Abschnitte
und verhindert Race Bedingungen und Deadlocks; die so implementierten Prozeße
kosten wenig Ressourcen.
WM 12/4/99