(SS09-07) Verteilte Event-Simulation mit einem Actor-Modell in Scala

Aus Verteilte Systeme - Wiki
Zur Navigation springen Zur Suche springen

Einleitung

Bei dem Projekt sollte auf Basis der Arbeit von Matthias Klein [1], der in seiner Diplomarbeit einen Simulator zur Simulation von verteilten Algorithmen geschrieben hatte, versucht werden einen verteilten diskreten Simulator zu bauen der auf Scala und dem Actor Model aufsetzt.

Die ausführliche Aufgabenbeschreibung ist hier zu finden:

Die Implementierung kann hier heruntergeladen werden(intern):

Grundlagen

Ereignisorientierte Simulationen

In einer ereignisgesteuerten Simulation (engl. Discrete-Event Simulation) wird ein System durch eine Abfolge von chronologisch geordneten Ereignisse dargestellt. Jedes Ereignis erfolgt zu einem bestimmten Zeitpunkt und ändert den aktuellen Zustand des Systems [2]

Der aktuelle Zeitpunkt indem sich das System befindet wird von letzten Ausgeführten Ereignis gesetzt.

Time Warp Synchronisation

Bei einer verteilten diskreten Simulation wird der Simulationsraum auf verschiedene Processing Units(PE's) verteilt, wobei jede dieser Units eine Untermenge des vorhandenen Simulationsraums übernimmt. Jede PE simuliert intern sequenziell und verschickt Nachrichten an andere PE's wenn ein Event über den lokalen Simulationsraum hinausgeht. Da die PE's unabhängig voneinander rechnen ist es notwendig ablaufende diese so zu synchronisieren das keine Kausalitätskonflikte auftreten. Kausalitätskonflikte treten immer dann auf wenn ein externes Event empfangen wird das eigentlich schon in der Vergangenheit hätte ausgeführt werden müssen, dieses jedoch wegen der parallelität nicht passiert ist und die PE ohne das Wissen über diesen Event simuliert hat.

Die Time Warp Synchronisation [3] wurde entwickelt da die konservativen Lösungen zu diesem Problem einige Probleme mit sich bringen. Diese versuchen die Kausalitätskonflikte durch Blockieren zu verhindern wenn kausale Abhängigkeiten zwischen Prozessen gefunden werden. Prozesse können nur ausgeführt werden wenn garantiert kein Event mehr eintreffen kann das vor der aktuellen Zeit ausgeführt werden soll. Zusätzlich muss das Deadlock-Problem gelöst werden da bei zyklischen Prozessabhägigkeiten alle Prozesse blockieren können.

Das Time Warp Verfahren geht einen anderen Weg. Es gehört zu den optimistischen Synchronisationsverfahren da hier jegliche Blockaden des Programmflußes vermieden werden. Ein PE kann immer rechnen auch wenn dabei Kausalitätskonflikte auftreten, wird ein solcher erkannt findet ein sogenannter Time Warp statt der die Simulation zum Zeitpunkt des Event der den Konflikt verursacht hat zurücksetzt. Als nächstes wird der aktuelle Event ausgeführt und danach die Events die schon einmal berechnet wurden, diesmal jedoch in der richtigen kausalen Reihenfolge.

Durch dieses Verfahren was komplett auf das Blockieren von PE's verzichtet sind Deadlocks ausgeschlossen, es entstehen aber andere Probleme durch die mögliche komplexität eines Time Warps. Dieser muss nämlich nicht nur lokal durchgeführt werden sondern kann sich über das ganze System erstecken wenn sich in einer frühzeitig ausgeführten Eventkette externe Events befanden. Nach David Jefferson [4] ist dieser Aufwand jedoch vertretbar und kann in effizienter Weise durch Anti-Events gelöst werden.

Actors

Actors allgemein

Die erste Veröffentlichung zum Actor Modell ist aus dem Jahre 1973 von Hewitt [5]. Hewitt beschreibt Actors folgendermaßen: "An ACTOR is an active agent which plays a role on cue according to a script". Nach Hewitt sind unter anderem Datenstrukturen, Funktionen, Semaphoren, Demons, Zahlen, Identifier oder Prozesse alles Spezialfälle von Actors, alle ihre Verhaltensweisen können durch das Senden von Nachrichten an Actors repliziert werden.

Eine einflussreiche Arbeit ist die Arbeit von Gul A. Agha [6] in der die parallelität des Actor Models Untersucht wird.

Eine weitere Interessante Arbeit ist das Paper von Paul Mackay [7] dass zu erklären versucht warum sich das Actor Model bis zum heutigen Tage noch nicht durchsetzen konnte.

Allgemein sollte ein Actor Modell zwei fundamentalen Prinzipien folgen:

  • Kontroll- und Datenfluss sind untrennbar
  • Berechnungen sollten intrinsisch statt extrinsisch durchgeführt werden. d.h. Jeder Actor sollte ein Problem lösen oder es an einen Actor weitergeben der es lösen kann.

Im Actor Modell wird alles als ein Actor betrachtet und diese sind von Natur aus Nebenläufig. Ein Actor ist eine Processing Entity die:

  • Nachrichten an andere Actors verschicken kann
  • Nachrichten von anderen Actors empfangen kann
  • Neue Actors erstellen kann
  • Für die nächste eintreffende Nachricht ein bestimmtes Verhalten festlegen kann

Wobei es keine Reihenfolge der oben genannten Punkte gibt, diese können auch nebenläufig ablaufen, hinzu kommt ausserdem das die Kommunikation zwischen Actors asynchron stattfindet.

Nachrichtenempfänger werden über Adressen identifiziert, d.h. eine Nachricht kann nur an einen bekannten Actor geschickt werden.

Actors in Scala

Scala Actors sind Thread ähnliche Objekte die eine Mailbox zum empfangen von Nachrichten besitzen. Um einen Actor zu nutzen erbt man von scala.actors.Actor und implementiert die act Methode.

Ein einfaches Beispiel wäre:

object SimpleActor extends Actor {
  def act() {
    println("acting")
  }
}

SimpleActor.start()
acting
acting
acting
...

Zur Kommunikation zwischen Actors gibt es die Methoden ! und receive/react die zum Senden und Empfangen von Nachrichten genutzt werden können. Die "receive" Methode benutzt eine Threadorientierte handhabung von Nachrichten d.h. Nachrichten werden durch den Thread des Actors bearbeitet. "react" nutzt einen anderen Ansatz und zwar einen Eventorientierten, hier wird der Thread des Senders benutzt und es entsteht kein overhead bei der Nachrichtenbearbeitung.

case object Ping
case object Pong

object Ping(pong:Actor) {
  def act() {
    pong ! Ping
    while(true) {
      receive{
        case Pong => {
          println("Pong")
          pong ! Ping
        }
      }
    }
  }
}
object Pong() {
  def act() {
    while(true) {
      receive{
        case Ping => {
          print("Ping ")
          sender ! Pong
        }
      }
    }
  }
}

val ponger = Pong()
val pinger = Ping(ponger)

ponger.start()
pinger.start()

ping pong
ping pong
ping pong
...


Will man Actors über ein Netzwerk kommunizieren lassen so ist es Notwendig die RemoteActor methoden alive, register und select zu verwenden. alive meldet den aktuellen Actor auf dem angegebenen Port zugänglich, Register weist dem Actor einen bezeichner zu über den dieser angesprochen werden kann und mit select kann eine Referenz auf einen entfernten Actor geholt werden damit dieser wie ein localer Actor verwendet werden kann.

object Receiver extends Actor {
  def act() {
    alive(6666)
    register('receiver, self)
    receive {
      case msg => println(msg)
    }
  }
}

object Sender extends Actor {
  def act() {
    var receiver = select(Node("192.13.42.123", 6666),'receiver)
    receiver ! "Hallo Receiver"
  }
}

Konzept

Framework

Es soll ein verteilter Simulator auf Basis von Scala Actors entwickelt werden. Hierzu wurde ein Framework entwickelt auf dem später die eigentlichen Simulationsbeispiele implementiert werden sollen.

Der Simulator sowie SimUnits sind Actors, anders als in der Implementierung von Klein[1] basiert die komplette Komunikation im System auf dem Actor Modell, d.h. die externe Komunikation zwischen Simulatoren verschiedener Simulationsengines sowie auch die Komunikation zwischen SimUnits.

Klassendiagramm-core.png

Simulator

Der Simulator ist der Kernprozess der eine Simulation vorranschreiten läßt und Events managed. Soll ein Simulator implementiert werden muss von der Simulator klasse abgeleitet werden und die Reaktionen auf verschiedene Nachrichtentypen implementiert werden.

Jede SimUnit die mit einer anderen SimUnit über Events kommunizieren will schickt den Event der den Empfänger enthält an den Simulator. Der Simulator reiht ankommende Events in die EventQueue ein und arbeitet sie sequenziell ab.

EventQueue

Der Simulator besitzt eine EventQueue in der zukünftige Events gespeichert und bei Bedarf rausgenommen werden können. Es werden ausserdem bereits ausgeführte Events gespeichert und können über den Timewarp mechanismus Rückgängig gemacht werden.

SimUnit

Eine SimUnit ist ein agierender Knoten in der Simulation der Events empfangen und versenden kann und auf empfangene Events in entsprechender Weise reagiert. Der Simulator verwaltet nur die Arbeit in der Simulation, diese wird in den SimUnits gemacht.

Event

Events werden benutzt um nachrichten zwischen SimUnits und Simulatoren zu versenden. Hier gibt es die Unterscheidung in InternalEvent und External Events. InternalEvents werden verwendet um interne Nachrichten zwischen SimUnits zu verschicken und ExternalEvent zur Kommunikation zwischen Simulatoren über ein Netzwerk.

UndoManagement

Um einen Erfolgreichen Timewarp hinzubekommen der das System auf einen früheren Zeitpunkt zurücksetzt, ist neben dem Zurücksetzen der Events in der Eventqueue auch die Wiederherstellung der SimUnit zustände Notwendig. Die Klasse UndoManagement regelt dieses Zurücksetzen der Zustände. Diese speichert nach jeder Zustandsänderung einer SimUnit deren Zustand auf einem Stack und kann gegenfalls alte Zustände Wiederherstellen. Jede SimUnit implementiert das Trait Memento, welche eine Methode zum Speichern sowie eine zum Laden des Zustands enthält, wie genau diese Speichern und Laden funktioniert hängt von der Implementierung der SimUnit ab. Beim Speichern und Laden werden Objekte der Klasse MementoObject zwischen SimUnits und UndoManagement ausgetauscht, ein solches Object enthält einen Zustand zu einem bestimmten Zeitpunkt.

Shopping Center Beispiel

Um die Implementierung von Simulator besser zu verstehen sollte zuerst ein einfaches Beispiel ohne Timewarp implementiert werden. Hier wurde ein Shoppingcenter-Simulator implementiert, der ein Kaufhaus mit zwei Gebäuden simuliert. Die Gebäude sind dabei Simulatoren die über ein Netzwerk kommunizieren. Jedes Gebäude verfügt über einen BuildingTunnel der es mit dem anderen Gebäude verbindet, über diese gehen ExtenalEvents.

Die EntranceDoor ist eine SimUnit die neue CustomerEvents generiert und an die Aufzüge oder Rolltreppen, in dem Beispiel haben alle SimUnits Wahrscheinlichkeitswerte über die entschieden wird welche SimUnit von einem CustomerEvent als nächstes angesteuert wird.

Klassendiagramm-shoppingcenter.png

Für dieses Beispiel wurde zum besseren Verständnis eine GUI geschrieben die folgendermaßen aussieht:

Shoppingcentergui.png

TimeWarp Beispiel

Um zu testen ob der TimeWarp mechanismus funktioniert wurde ein weiteres Beispiel implemententiert. Dieses Beispiel ist sehr simpel gehalten. Die SimulationEngine empfängt Events die einen Counter enthalten und gibt sie auf der Konsole aus. Die SimUnitNode stellt diese Events her und hat den Counter als derzeitigen Zustand.

Der TimeWarpSimulator erzeugt zufällige Zahlen und sendet diese an die SimulationEngine, die daraufhin TimeWarps zu den empfangenen Zeiten durchführt.

Klassendiagramm-timewarp.png

Die Konsolenausgabe dieses Beispiels sieht folgendermaßen aus:

Simulator register: simEng port 7777
time: 0 state: 1
time: 1 state: 3
time: 2 state: 5
time: 3 state: 7
time: 4 state: 9
time: 5 state: 11
time: 6 state: 13
time: 7 state: 15
TimeWarp::time::1 <-- Timewarp-Zeit empfangen
time: 1 state: 3
time: 2 state: 5
time: 3 state: 7
TimeWarp::time::1 <-- Timewarp-Zeit empfangen
time: 1 state: 3
time: 2 state: 5
time: 3 state: 7
time: 4 state: 9
time: 5 state: 11
time: 6 state: 13
time: 7 state: 15
time: 8 state: 3
TimeWarp::time::6 <-- Timewarp-Zeit empfangen
time: 6 state: 13
time: 7 state: 15
time: 8 state: 3
time: 9 state: 5

Implementierung

Tools

Maven2

Für das Management des Projekts wurde Maven2 verwendet. Maven2 ist ein Build-Management Tool der Apache Software Foundation welches auf Java basiert. Um das Projekt kompilieren zu können ist eine Maven2 installation auf dem System notwendig. In der settings.xml muss ein lokales repository mit dem Namen M2_REPO angegeben werden, dieses kann dann unter Eclipse im Build-Path verlinkt werden und das Projekt kann in Eclipse verwendet werden. Es ist außerdem möglich das Projekt ohne Eclipse zu bauen, hier muss in dem Projektordner der Befehl mvn compile ausgeführt werden.

Bewertung

Der Speed-Up durch die Verteiltheit des System ist für den Fall dass keine Timewarps stattfinden linear, weil die Simulatoren vollkommen unabhängig voneinander Arbeiten und keine Synchronisierung stattfindet. Mit der Zahl der notwendigen TimeWarps sinkt dieser Speed-Up, es kommt also immer auf die Implementierten Beispiele an.

Quellen:

  1. 1,0 1,1 Klein, Matthias: "Simulation verteilter Algorithmen in einer e-Learning-Umgebung", interne Diplomarbeit, FH Wiesbaden, FB Informatik, August 2003 [1]
  2. Stewart Robinson, Simulation - The practice of model development and use, Wiley 2004
  3. Von Otte, Ingo: "Time-Warp Synchronisation", Seminararbeit 1997 [2]
  4. Jefferson, D.R., Virtual Time ACM Transactions on Programming Languages and Systems, Vol 7, No. 3, Juli 1985[3]
  5. Carl Hewitt, Peter Bishop, Richard Steiger ,A Universal Modular ACTOR Formalism for Artificial Intelligence [4]
  6. Gul A. Agha: "Actors: A Model Of Concurrent Computation In Distributed System" [5]
  7. Paul Mackay :"Why has the actor model not succeeded?" [6]