Seminar

Objekt-Orientierte Parallele Programmierung

SS 95

Das Actor- und das ActorSpace-Modell

Frank Thilo

Inhaltsverzeichnis

1 Übersicht
2 Das Actor-Modell
- 2.1 actor primitives
  - 2.1.1 send to
  - 2.1.2 become
  - 2.1.3 create
- 2.2 nähere Betrachtung
  - 2.2.1 Aktoren und actor machines
  - 2.2.2 event diagrams und garbage collection
  - 2.2.3 Beispiel
- 2.3 Zusammenfassung
3 Das ActorSpace-Modell
- 3.1 Kommunikation im ActorSpace
- 3.2 erweiterte Operationen
  - 3.2.1 make_capability
  - 3.2.2 new_actor
  - 3.2.3 new_space
  - 3.2.4 make_visible, make_invisible
- 3.3 garbage collection
- 3.4 Beispiel
- 3.5 Zusammenfassung
4 Resümee
5 Literaturverzeichnis

1 Übersicht

Das Thema dieser Abhandlung sind das Actor- und das ActorSpace-Modell. Beide stellen grundlegende Konzepte bereit, um parallele, verteilte Systeme aus einzelnen Objekten aufzubauen. Diese Objekte interagieren dabei über den Austausch von Nachrichten.

Zuerst wird das Actor-Modell behandelt. Hierbei wird auf die Grundlagen, die einzelnen Operationen und zur Vertiefung auf Möglichkeiten der bildlichen Darstellung eingegangen. Den Abschluß bildet schließlich ein einfaches Beispiel.

Es folgt eine Betrachtung des weitergehenden ActorSpace-Modells mit einer grundlegenden Behandlung der neuen Konzepte, die durch neue und erweiterte Operationen ermöglicht werden.

2 Das Actor-Modell

In diesem Modell besteht ein paralleles System aus autonomen Objekten, den sogenannten Aktoren. Es handelt sich hierbei um aktive Objekte, die selbständig Aktionen ausführen können (in realen Implementierungen könnten ihnen eigene Threads zugewiesen sein), im Gegensatz zu den passiven Objekten, auf denen objektorientierte Programmiersprachen wie Eiffel und C++ basieren.

Aktoren sind vollständig gekapselt, d.h. ihr interner Zustand ist von außen weder direkt sichtbar noch manipulierbar. Die einzige Möglichkeit, einen bestehenden Aktor zu beeinflussen, besteht darin, ihm eine Nachricht zu senden, worauf der Empfänger dann mit verschiedenen Aktionen reagieren kann. Dazu besitzt jedes Objekt eine eindeutige, statische Mailadresse mit zugehöriger Mailqueue sowie ein Verhalten (behaviour), das seinen inneren Zustand darstellt. (Wie später deutlich wird, kann ein einzelnes Objekt in Form mehrerer simultan existierender actor machines verschiedene Verhalten aufweisen).

2.1 actor primitives

Trifft nun eine Nachricht bei einem Aktor ein, so kann dieser darauf mit dem Ausführen von Operationen reagieren. Diese grundlegenden Operationen, die ihm zur Verfügung stehen, heißen actor primitives. Es gibt drei solcher Primitiven: send to, become und create, die im Folgenden besprochen werden.

2.1.1 send to

Mit send to kann ein Objekt einem anderen eine Nachricht schicken. Als Parameter erhält diese Operation die Adresse des Empfängers sowie die zu versendende Nachricht selbst. Das Zielobjekt wird über dessen eindeutige Mailadresse bestimmt, welche dem Sender bekannt sein muß. Hierbei kann man drei Möglichkeiten unterscheiden:

Die Adresse war dem Aktor schon vor Abarbeitung der aktuellen Nachricht bekannt, ist also ein Teil seines aktuellen inneren Zustands.

Die Adresse wurde dem Aktor soeben als ein Teil der Nachricht mitgeteilt.

Der Sender hat den Adressaten soeben selbst mittels create erzeugt und somit dessen Adresse erhalten.

Zu beachten ist, daß der Nachrichtenversand asynchron ist, der Sender also weder auf die Empfangsbereitschaft des Empfängers noch auf die Abarbeitung der Nachricht warten muß. Statt dessen wird vom Mailsystem garantiert, daß die abgeschickte Nachricht in die Mailqueue des Adressaten eingefügt wird. Hingegen wird über die Reihenfolge des Eintreffens keinerlei Aussage gemacht, so daß es möglich wäre, daß eine "später" abgeschickte Nachricht in der Mailqueue weiter vorne eingefügt wird. Daß hier keine Einschränkung getroffen wird, kann sich u.a. positiv auf die Effizienz des Nachrichtenversands auswirken (man denke beispielsweise an die Möglichkeit des adaptiven Routings, die es Nachrichten erlaubt, unterschiedliche Pfade zu benutzen). Ist eine Erhaltung der Reihenfolge gewünscht, kann dies explizit auf einer höheren Ebene ebenso erzwungen werden wie ein vollständig synchroner Versand, da beides nur einen Spezialfall der asynchronen Kommunikation darstellt.

2.1.2 become

Über die become-Operation legt ein Aktor sein Folgeverhalten (replacement behaviour) fest, das bestimmt, wie er auf die nächste Nachricht in der Mailqueue reagieren wird. Es muß ein neues Verhalten angegeben werden, das aus einer behaviour description besteht, die den abzuarbeitenden Programmcode enthält und parametrisiert sein kann. Diese Parameter sind Adressen anderer Objekte und werden acquaintances genannt. Der Programmcode enthält dann z.B. Anweisungen, um an solche acquaintances Nachrichten zu verschicken.

Zu beachten ist hierbei, daß lediglich das Verhalten für die Abarbeitung der nächsten Nachricht bestimmt wird, und das Verhalten, das die weitere Reaktion auf die aktuelle Nachricht definiert, nicht geändert wird. Dies ist ein wichtiger Aspekt zur Erhöhung der möglichen Parallelität und wird später in Zusammenhang mit actor machines noch einmal genauer angesprochen.

Bei anderen Objektmodellen besteht der innere Zustand aus den Werten objektlokaler Variablen. Ein Zustandsübergang geschieht dann durch Zuweisung neuer Werte an die Variablen. Da dies sequentiell geschieht, können inkonsistente Zwischenzustände entstehen. Außerdem gibt es Probleme beim gleichzeitigen Zugriff auf deise Variablen, wenn das Objekt zwei Nachrichten parallel abarbeiten soll. Durch die Verwendung eines monolithischen Verhaltens als innerer Zustand werden solche Probeme im Actor-Modell vermieden.

Ein rein funktionaler Aktor weist ein statisches Verhalten auf und ändert sein Verhalten nicht über eine become-Operation.

2.1.3 create

Mit Hilfe von create werden neue Aktoren erzeugt. Dazu muß ihr Verhalten, wie unter become beschrieben, spezifiziert werden. Dieses Verhalten legt fest, wie das Objekt auf den Empfang der ersten Nachricht reagieren wird. Ist in der behaviour description eine become-Anweisung enthalten, so kann die Reaktion auf nachfolgende Nachrichten entsprechend variieren.

Das aufrufende Objekt erhält als Ergebnis von create die identifizierende Mail-Adresse des neuen Aktors, die dann in weiteren Operationen sofort benutzt werden kann (beispielsweise als Ziel einer Nachricht).

2.2 nähere Betrachtung

Die Vorgänge, die in einem System von Aktoren ablaufen, kann man zur Verdeutlichung auch graphisch darstellen. Im Folgenden werden die oben aufgeführten Operationen anhand zweier solcher Darstellungen näher erläutert.

2.2.1 Aktoren und actor machines

ist eine abstrakte Darstellung eines Aktors. Dieser besteht aus einer beliebig großen Mail-Queue, deren Slots mit natürlichen Zahlen numeriert werden. Der Aktor X hat seine ersten n-1 Nachrichten schon abgearbeitet und bearbeitet momentan die Nachricht n. Die Operationen werden von einer sogenannten actor machine Xn ausgeführt. Eine solche actor machine besitzt einen inneren Zustand in Form eines Verhaltens, das die auszuführenden Primitiven bestimmt. Im Beispiel versendet Xn eine Nachricht an ein nicht eingezeichnetes Objekt, erzeugt einen neuen Aktor Y und legt damit gleichzeitig dessen initiale actor machine Y1 fest. Weiterhin führt die become-Operation zum Festlegen des replacement behaviour und damit zur Erzeugung der actor machine Xn+1.

Abbildung : abstrakte Darstellung eines Aktors

Wichtig ist, daß sehr viele dieser Vorgänge parallel ablaufen können. Und zwar kann man drei verschiedene Arten der Parallelität unterschieden:

Parallelität zwischen Sender und Empfänger:
Aufgrund der asynchronen Kommunikation kann der Sender einer Nachricht sofort weitere Operationen ausführen, auch wenn der Empfänger die Nachricht noch nicht vollständig bearbeitet hat oder sogar noch mit anderen Nachrichten beschäftigt ist.

Parallelität der einzelnen Operationen innerhalb einer actor machine:
Da die Operationen, die eine actor machine ausführt, im allgemeinen unabhängig voneinander sind (Ausnahme: die Mail-Adresse, die eine create-Operation liefert, muß bekannt sein, bevor diese in weiteren Primitiven verwendet werden kann), können sie gleichzeitig ausgeführt werden. In wären dies das Verschicken einer Nachricht, das Erzeugen von Y und die Bestimmung des Folgeverhaltens.

Parallelität der einzelnen actor machines:
Mehrere actor machines des gleichen Objekts können parallel arbeiten. Dies ist möglich, da sie eigene, unabhängige innere Zustände besitzen. D.h. im Beispiel kann Xn+1 arbeiten, sobald Xn den Folgezustand festgelegt hat und die Kommunikation n+1 eingetroffen ist (diese Nachricht kann natürlich schon längere Zeit in der Mail-Queue stehen), auch wenn Xn noch beschäftigt ist.

2.2.2 event diagrams und garbage collection

Die wechselseitigen Abhängigkeiten und das dynamische Erzeugen neuer Aktoren können gut in einem event diagram sichtbar gemacht werden (). Diese Diagramme bestehen aus senkrechten Linien, den lifelines (Lebenslinien), die jeweils für ein bestimmtes Objekt stehen. Auf diesen Linien wird für jedes event (das Eintreffen einer Nachricht) ein Knoten eingezeichnet. Das Versenden von Nachrichten wird mit Pfeilen verdeutlicht, die von einem Knoten zu einem anderen führen und beim Ziel-Objekt wieder ein event auslösen. Weiterhin bedeuten gestrichelte Pfeile create-Operationen, die neue Aktoren und somit lifelines erzeugen. Die Halbbögen am Anfang einer Lebenslinie bedeuten die >>Geburt<< dieses Objekts, während fehlende Bögen darauf hindeuten, daß das zugehörige Objekt schon länger existiert.

Abbildung : event diagram

Diese Diagramme drücken dabei nicht direkt zeitliche Zusammenhänge aus, wie man meinen könnte, da es in einem verteilten System aufgrund der Laufzeiten der Nachrichten keine absolute, globale Zeit geben kann (im Idealfall, also bei minimal möglichen Laufzeiten, stößt man hier auf die spezielle Relativitätstheorie). Anstelle einer solchen globalen Ordnung tritt hier einerseits eine lokale Ordnung der events jedes Aktors und andererseits eine Halbordnung Zwischen events unterschiedlicher Aktoren, die durch den Austausch von Nachrichten bestimmt wird.

Auffallend ist noch, daß die Lebenslinien kein definiertes Ende haben. Dies kommt daher, daß es keine explizite Möglichkeit zum Zerstören bestehender Aktoren gibt. Da das Löschen von nicht erreichbaren Objekten auf konzeptioneller Ebene keinerlei Bedeutung hat (bei realen Implementierungen aber durchaus Auswirkungen auf die Performance des Systems hat), wird dies der jeweiligen Implementierung überlassen. Dort geschieht dies mit dem üblichen Verfahren der garbage collection. Dabei wird ausgenutzt, daß ein Objekt, dessen Adresse keinem anderen Objekt mehr bekannt ist und das keine zur Zeit aktiven actor machines besitzt, keine Nachrichten mehr empfangen und somit auch keine Aktionen mehr ausführen kann. Daher kann es in einem solchen Fall aus dem System entfernt werden.

Beispiel

Als Beispiel eines einfachen Programms, das auf Aktoren basiert, sehen wir uns die klassische rekursive Berechnung der Fakultäts-Funktion an (s. auch [1] und [4]). Zur Vereinfachung wurde das Programm in einem Pseudocode implementiert.

Das komplette System besteht aus 3 Verhaltensbeschreibungen: der eigentlichen Fakultätsberechnung (Fakultät), einem Hilfsobjekt (Customer) und dem aufrufenden Client. Dieser Client erzeugt ein neues Fakultäts-Objekt und sendet diesem anschließend die Nachricht, 3! zu berechnen und das Ergebnis an stdout zu schicken (das Objekt stdout soll hier einfach sämtliche Nachrichten auf den Bildschirm ausgeben).



Fakultät with acquaintances self
  let communication be an integer n and an actor u
    become Fakultät(self)
    if n=0
      then send [1] to u
      else 
        let c=create Customer with acq. n and u
        {send [n-1, c] to self}

Customer with acq. an integer n and an actor u
  let communication be an integer k
    {send [n*k] to u }

Client with acquaintances stdout
  let f=create Fakultät with acquaintances f
    {send [3,stdout] to f}

Listing : rekursive Fakultätsberechnung

Der erzeugte Fakultäts-Aktor erhält also eine Nachricht mit n=3 dund u=stdout. Da es sich um einen rein funktionalen Aktor handelt, wird mit become ein identisches Verhalten festgelegt. Wenn nun n=0 ist (Basis der Rekursion), so lautet das Ergebnis 1 und wird direkt an das gewünschte Ziel u gesendet. Ansonsten würde in einer herkömmlichen Sprache einfach n*fak(n-1) berechnet. Die Bestimmung von fak(n-1) geschieht einfach durch Senden einer entsprechenden Nachricht an sich selbst. Ein Problem ist aber die anschließende Multiplikation und Senden des Ergebnisses an u (stdout).

Zu diesem Zweck dient ein sogenannter customer, der hier als Parameter bei seiner Erzeugung einen Integer n und ein Objekt u erhält. Dieser Aktor macht nun nichts anderes, als eine ihm übermittelte ganze Zahl mit n zu multiplizieren und das Ergebnis an u weiterzuleiten.

Die Fakultäts-Berechnung erzeugt nun einen solchen customer und schickt sich anschließend die Nachricht, fak(n-1) zu errechnen und das Ergebnis an eben diesen customer zu senden, der dann seinerseits dafür sorgt, daß fak(n-1) mit n multipliziert wird und an das ursprüngliche Ziel stdout geschickt wird. Zur Berechnung von fak(n-1) kann es natürlich wieder notwendig sein, einen weiteren customer zu erzeugen und fak((n-1)-1) zu errechnen usw.

In ist der Ablauf der Berechnung von 3! noch einmal als event diagram verdeutlicht. Man sieht, wie drei Customer-Objekte erzeugt werden, die für die Multiplikationen sorgen und ihre Ergebnisse jeweils an den customer senden, der einen Schritt vorher erzeugt wurde. Der zuerst erzeugte customer kommuniziert schließlich mit dem ursprünglichen Ziel stdout.

Die Rekursivität wird an den drei Nachrichten deutlich, die der Fakultäts-Aktor sich selbst schickt. Diese werden im Bild durch die drei Pfeile dargestellt, die von der Fakultäts-Lebenslinie zu ihr zurückweisen.

Abbildung : rekursive Fakultätsberechnung

2.3 Zusammenfassung

Das Actor-Modell stellt eine einfache, aber leistungsfähige Grundlage dar, auf der parallele, verteilte Systeme auf objektorientierte Weise aufgebaut werden können. Dabei wird ein höchstmöglicher Grad von Parallelität erreicht, ohne daß in Programmen explizit gemacht werden muß, an welchen Stellen ein paralleler Ablauf gewünscht ist. Dies gelingt durch die weitgehende Unabhängigkeit der einzelnen Aktoren bzw. actor machines (Informationsaustausch nur über Versenden von Nachrichten, keine gemeinsam benutzten Variablen zwischen den actor machines) und den asynchronen Nachrichtenaustausch.

Andererseits bieten die zur Verfügung stehenden primitiven Operationen nur eine Art Maschinensprache, auf der programmiersprachliche Abstraktionen aufbauen müssen (z.B. zum automatischen Erzeugen von customers), will man größere Systeme modellieren.

3 Das ActorSpace-Modell

Das ActorSpace-Modell basiert auf dem Actor-Modell und erweitert dies um einige neue Operationen. Hierzu gehören eine Möglichkeit, Aktoren in logischen Gruppen zusammenzufassen, ganze Gruppen von Objekten als Ziel einer Nachricht zu verwenden und allgemein eine abstraktere Art der Adressierung als die direkte Angabe einer Mailadresse.

Um dies zu realisieren werden einige neue Konzepte eingeführt: attributes, die Eigenschaften festlegen, die zur Auswahl eines Objekt benutzt werden können (über pattern-matching), actorspaces, die als Behälter für Aktoren dienen und schließlich capabilities, Zugriffsschlüssel, die es nur ihren Besitzern erlauben, bestimmte Aktionen auszuführen.

behaviour Printmanager(PrintSpool, numJobs)
{
  method new_job(printjob)	// NEUER AUFTRAG
  {
    if (numJobs<10)		// NOCH NICHT UEBERLASTET
    {
      send-to PrintSpool new_job(printjob)
      become Printmanager(PrintSpool, numJobs+1)
    }
    else 		// UEBERLASTUNG DROHT -> SCHICKE JOB WEITER
    {
      send-to "./*" new_job(printjob)
      make_invisible self "."
    }
  }

  method job_done	// EIN AUFTRAG ERFOLGREICH BEENDET
  {
    become PrintManager(PrintSpool, numJobs-1)
    if (numJobs=5) make_visible self "."
  }
}