Home

kastens für Verteilte Algorithmen

Contents

1. Abbildung 5 13 Einstellungen Topology Zur Bearbeitung der Topologie werden folgende Werkzeuge angeboten R Move nach Auswahl dieses Werkzeugs k nnen die Positionen einzelner Agenten verschoben werden 4 Connect mit diesem Werkzeug k nnen Verbindungen zwischen zwei Agenten gezogen werden 33 Connect from file dieses Werkzeug funktioniert hnlich zu dem voran gegangenen mit dem Unterschied dass hier eine Klasse gew hlt werden kann aus der neue Connection Instanzen erzeugt werden k nnen Auf die sem Weg k nnen eigene Verbindungen siehe Abschnitt 5 2 3 eingebunden werden 5 3 Die Oberfl che 63 4 Disconnect l scht die Verbindung auf die geklickt wurde a Remove all connections hebt alle Verbindungen wieder auf s7 position the agents stellt die vom Topologiemanager festgelegten Po sitionen wieder her Topologiemanager bernehmen die l stige Aufgabe Agenten miteinander zu verbinden Zus tzlich legen sie die Anordnung der Agenten fest Es besteht die Auswahl zwischen verschiedenen Topologiemanagern 1 _ userdefined diese Auswahl zeigt an dass die Verbindungen und Positio nen manuell erstellt worden sind oder noch erstellt werden m ssen Wird die von einem Topologiemanager erstellte Umgebung ge ndert z B durch L schen einer Verbindung wird automatisch diese Auswahl aktiv Durch einen Eingriff in die Arbeit eines Topologiemanagers verzichtet der Benut zer
2. und V 1 d Solange 1 lt r lt f 1 p sendet alle noch nicht gesendeten Werte V r V r 1 an alle anderen Prozesse und 3 3 Koordination und bereinstimmung 32 tr gt alle bisherigen Werte an die n chste Stelle des Vektors Vir 1 Viel Bei Erhalt einer Nachricht mit V von p wird die erhaltene Menge mit der n chsten eigenen vereint V r 1 Vi r 1 UV Nach Ablauf von f 1 Runden wird d min V f 1 gesetzt Ein Vorteil dieses Algorithmus ist das Erkennen von Ausf llen wodurch aller dings eine hohe Netzauslastung aufgewendet werden muss da der Algorithmus f 1 mal durch gef hrt wird vgl Coulouris et al 02 S 527f Problem der byzantinischen Gener le Eine L sung des Problems der by zantinischen Gener le sollte ber cksichtigen dass einige Gener le Verr ter sind In der Computerwelt w rde das bedeuten dass einige Prozesse falsche oder ber haupt keine Nachrichten ausliefern Der folgende Algorithmus l st dieses Problem mit einer Einschr nkung Ein verteiltes System mit f fehlerhaften Prozessen muss mindestens aus N gt 3f 1 Prozessen bestehen um eine Einigung zu erzielen Abbildung 3 15 zeigt dass es unm glich ist zwischen P und P eine ber einstimmung zu erreichen da beide einen unterschiedlichen Wert vorgeschlagen haben auf den sie sich einigen m ssten Kommandeur Abbildung 3 15 Drei byzantinische Gener le A
3. IVi K d h alle Mengen m ssen die gleiche Anzahl Prozesse beinhalten Jeder Prozess p ist in M der W hlermengen V enthalten Die optimale L sung dieses Algorithmus tritt laut Maekawa dann ein wenn K so klein wie m glich gew hlt wird so dass K x VN und M K ist Der Ablauf des Algorithmus sieht wie folgt aus Jeder Prozess erh lt eine gew hlt Markierung die anzeigt ob er schon einem Prozess eine Zusage zum Betreten des kritischen Abschnitts gesendet hat oder nicht Bei der Initialisierung wird dieser Wert auf false gesetzt Bei Eintrittswunsch von p sendet dieser eine Anfrage an alle Gruppen mitglieder V p seiner Wahlmenge und wartet bis er von allen eine Antwort erh lt Nachdem alle Antworten bei ihm eingetroffen sind kann er den kritischen Abschnitt betreten Bei Erhalt einer Anfrage pr ft der Empf nger ob er sich im kritischen Abschnitt befindet oder ob er jemandem bereits eine Zusage gesendet hat 1 Ist dies der Fall wird die Anfrage in einer Warteschlange eingereiht 2 Ansonsten sendet er eine Zusage und setzt seine gew hlt Markierung auf true Nach dem Verlassen des kritischen Abschnitts teilt p dies allen seinen Gruppenmitgliedern mit 3 3 Koordination und bereinstimmung 20 Bei Erhalt einer Nachricht die die Freigabe des kritischen Abschnitts bein haltet wird die Warteschlange gepr ft 1 Ist diese nicht leer bekommt der erste dieser Schlange ei
4. N BE next ib Clock 2 Counter 0 a Clock 2 Counter 1 Clock 2 Counter 2 Clock 2 Counter 3 2 Counter 4 Clock 3 Counter 0 Clock 3 Counter 1 Clock 3 Counter 2 v Abbildung 5 19 Steuerung Der Ablauf selbst kann ebenfalls angepasst werden Der Benutzer kann ei ne Geschwindigkeit einstellen mit der er die Simulation gerne ablaufen lassen m chte wobei er entscheiden kann ob die Visualisierung dieser Simulation nun animiert werden soll oder nicht Neben diesen Einstellungen kann der Benutzer hier den Simulationsmodus w hlen und entscheiden ob die Simulation manu ell gesteuert werden soll oder von einem der beiden automatischen Ablaufmodi Abbildung 5 20 zeigt die Oberfl che die diese Einstellungen erm glicht Die ma nuelle Steuerung erlaubt dem Benutzer selbst in den Ablauf des Algorithmus einzugreifen Auf diese Weise kann das nicht deterministische Verhalten von ver teilten Systemen simuliert oder diverse Speziallf lle durchgespielt werden 5 3 Die Oberfl che 68 speed asynchronous z synchronous animated kS asynchronous manual Abbildung 5 20 Steuerungsmodi Steuerung Zun chst soll aber auf die einfache automatische Steuerung der Simulation eingegangen werden Play mit diesem Befehl wird der automatische Ablauf eines Algorith mus gestartet oder wieder aufgenommen Dieser wird nun schrittweise im eingestellten Tempo ausgef hrt Il Pause
5. TopologyManager class A Klassen bersicht 150 disaster view AgentRenderer class DefaultAgentRenderer class AgentPreferencesPane class Renderer class SequenceViewAgentRenderer class zu AgentRendererPane class x ButtonCellEditor class ChangeRendererAction class LevelUpAction class SequenceView class SequenceViewClockRenderer class SequenceViewConstants class SequenceViewMessageRenderer class MessagePreferencesPane class TopologyViewAgentRenderer class AgentRendererPane class x ButtonCellEditor class x ChangeRendererAction class LevelUpAction class TopologyView class TopologyViewConnectionRenderer class m ConnectionPreferencesPane class StrokeCellRenderer class TopologyViewMessageRenderer class MessagePreferencesPane class View class ViewUtils class
6. V j 1 und Vi k lt Vilk k 5 Nach dem Entfernen dieser Nachricht aus der Warteschlange wird Vili Vilj 1 gesetzt Ein m glicher Ablauf dieser Methode wird in Abbildung 3 14 dargestellt Der Algorithmus kann feststellen dass sich die Nachrichten m und ma bei P ver tauscht haben und bringt sie in die richtige Reihenfolge Es besteht die M glichkeit dieses Verfahren um einen Sequenzer wie er f r eine totale Reihenfolge eingesetzt wird zu erweitern um eine total kausale Reihenfolge zu erhalten vgl Coulouris et al 02 S 519fF 3 3 4 bereinstimmungsprobleme Bisher wurde bei allen vorgestellten Algorithmen ein korrektes Verhalten der Pro zesse vorausgesetzt Dieser Abschnitt besch ftigt sich mit der Problematik dass 3 3 Koordination und bereinstimmung 30 P P2 P3 0 0 0 0 0 0 0 0 0 1 0 0 mi 1 0 0 1 0 gt m H Ir 1 1 0 m mm mm Abbildung 3 14 Kausale Reihenfolge durch Vektoruhren Prozesse untereinander einen Konsens erreichen m ssen auch wenn einer oder mehrere von ihnen fehlerhaft arbeiten oder gar ausfallen Dabei werden drei Pro bleme vorgestellt 1 Konsens 2 interaktiver Konsens und 3 das Problem der byzantinischen Gener le Die einzelnen Probleme werden im Folgenden behandelt wobei die L sungsver fahren zun chst als Blackbox vorliegen Konsens In einem System mit N Prozessen schl gt jeder Prozess p mit Bed N einen Wert d aus
7. hnlich dem Inhaltsverzeichnis mit Hilfe einer XML Konfigurationsdatei erzeugt Listing 7 8 zeigt den Aufbau dieser Konfigurations datei lt index version 1 0 gt lt indexitem text Ablauf und Steuerung target node26 gt lt indexitem text Views target nodei16 gt 1 2 3 4 Eras yag S 5 6 7 lt index gt Listing 7 8 Konfiguration f r den Index Der Index wird mit dem index Tag eingeleitet jeder Eintrag wird durch ein indexitem erzeugt Da das Anlegen der einzelnen Eintr ge mit gro em Aufwand verbunden ist wurde das Programm Helen getestet Helen dient zur Erstellung von Helpsets und soll die Erzeugung von Inhaltsverzeichnis Index und Volltext suche unterst tzen Da das Inhaltsverzeichnis und die Volltextsuche ohne Hilfe bereits erstellt wurden blieb nur noch der Index Die Hoffnung lag dabei auf einer intelligenten Untersuchung der Hilfetexte die eine Liste an W rtern liefert aus denen die relevanten W rter in den Index aufgenommen werden k nnen Leider blieb diese Form der Unterst tzung aus Statt dessen konnten nur die einzelnen Kapitel in den Index aufgenommen werden Ein weiteres Produkt Javahelp Plug In von Light Development bietet eine hnliche Funktionalit t an Aus diesem Grund wurde zun chst auf einen ausf hrlichen Index verzichtet Um den Index in das Hilfesystem zu integrieren wird dem Helpset eine neue Ansicht hinzugef gt siehe Listing 7 9 http www
8. Ist die eigene ID gr er und der Empf nger noch kein Teilnehmer einer Wahl tr gt er seine eigene ID in die Nachricht ein sendet sie weiter und setzt sich als Teilnehmer Ansonsten wird die Nachricht verworfen 3 Ist die empfange ID gleich der eigenen dann ist der Empf nger der neue Anf hrer Dieser setzt sich als Nicht Teilnehmer und sendet eine Wahlergebnisnachricht mit seiner eigenen ID an den n chsten Prozess Bei Empfang einer Wahlergebnisnachricht merkt sich der Empf nger die ID des neuen Anf hrers markiert sich selbst als Nicht Teilnehmer und sendet die Nachricht an den n chsten Prozess weiter falls er nicht selbst Anf hrer ist Abbildung 3 9 zeigt einen m glichen Ablauf dieses Algorithmus Die Initiali sierung wurde in diesem Beispiel von Prozess 19 gestartet Abbildung 3 9 Wahlverfahren im Ring Wird dieses Verfahren von nur einem Prozess initiiert werden im schlimmsten Fall 3N 1 Nachrichten ben tigt um den neuen Anf hrer bestimmen zu k nnen Dieser Fall tritt genau dann ein wenn der zuk nftige Anf hrer der Prozess ist der in der Ringreihenfolge vor dem Initiator kommt Dann ben tigt die Wahl nachricht N 1 Schritte um zu ihm zu gelangen und noch mal N Schritte bis dessen Wahl best tigt werden kann Um das Ergebnis um den Ring zu schicken werden weitere N Nachrichten verwendet Im besten Fall startet der zuk nftige 3 3 Koordination und bereinstimmung 23 Anf
9. RemoveRendererAction class RemoveViewAction class disaster gui actions d DeleteMessageAction class o EditMenuAction class o ExitAction class o FileMenuAction class o HelpMenuAction class o LaFMenuAction class o MoveDownAction class d MoveUpAction class o NewAction class Cd NextAction class A Klassen bersicht ern NextStepAction class OpenAction class OptionsMenuAction class PauseAction class PlayAction class PreviousAction class SaveAction class SaveAsAction class ShowAboutDialogAction class ShowHelpAction class ShowPreferencesAction class ShowViewPreferencesAction class StopAction class ViewMenuAction class disaster gui util ClassFileChooser class ClassFileFilter class DSEFileFilter class GIFFileFilter class JPEGFileFilter class MessageListTableModel class PNGFileFilter class A Klassen bersicht 149 disaster model Agent class AgentComponent class AgentLog class AgentLogEntry class AgentLogListener class CompleteTopology class Connection class EnvironmentChangeListener class Environment class EnvironmentState class EnvironmentUpdateListener class History class HistoryEntry class InitMessage class Message class MessageQueueChangeListener class MessageQueue class Request class Response class StateCopyFactory class TimeoutMessage class TokenRing class TokenRingConnection class Topology class
10. Voraussetzung dieses Verfahrens ist dass ein Prozess die Zeit t absch tzen kann d h wie lan ge eine Nachricht h chstens braucht um beim Empf nger anzukommen Unter dieser Voraussetzung verl uft der Algorithmus wie folgt Eine Nachricht m wird mit der gesch tzten Zeit t die die Nachricht zum Empf nger ben tigt in der Form lt m t gt gesendet Bei Erhalt einer Nachricht lt m t gt wird diese gepuffert Eine Nachricht wird aus dem Puffer entfernt und ausgeliefert sobald der Zeitpunkt t erreicht ist Wird eine Nachricht empfangen deren gesch tzte Ankunftzeit bereits ab gelaufen ist wird diese verworfen Nachteil dieser Methode ist zum einen dass die Nachrichten erst nach Ablauf der gesch tzen Zeitspanne ausgeliefert und verarbeitet werden k nnen Wird diese Zeitspanne zu hoch gesetzt verlangsamt sich der Algorithmus Wird sie zu niedrig gew hlt besteht die Gefahr dass mehrere Nachrichten gar nicht erst ausgeliefert werden vgl Oechsle02 S 20 Totale Reihenfolge durch Folgenummern Die Methode eine totale Rei henfolge durch Folge oder Ordnungsnummern zu erhalten hnelt ein wenig dem zentralen Verfahren ber einen Sequenzer In diesem Fall wird die Ornungsnum mer einer Nachricht aber nicht von einer zentralen Instanz festgelegt sondern wird von allen Prozessen gemeinsam bestimmt Der Ablauf dieser Einigung sieht folgenderma en aus 3 3 Koordination und bereinstimmung 28 E
11. bergebene Datenpaket bernommen werden Selbstdefinierte Attribute werden bei diesem Verfahren bergangen da sie dem System nicht bekannt sind Diese Einschr n kung wurde gew hlt um dem Entwickler zu ersparen die clone Methode zu berschreiben Zus tzlichen Informationen sollten statt in den neuen Nachrich tentyp in das versendete Paket gesteckt werden F r dieses Paket kann dann eine neue Klasse definiert werden die alle ben tigten Zusatzinformationen beinhaltet Dieses Paket wird dann auch in die jeweilige Kopie der Nachricht gepackt Allein die Serialisierbarkeit muss gew hrleistet sein Gegen ber dem berschreiben der clone Methode ist dieser Schritt mit geringerem Aufwand f r den Anwender verbunden 5 2 3 Verwendung und Implementierung von Topologiemanagern und Verbindungen Nachdem die Agenten vorgestellt wurden und der Umgang mit Nachrichten er kl rt wurde soll nun darauf eingegangen werden welche Schritte notwendig sind um die Kommunikation zwischen den einzelnen Agenten zu gew hrleisten Denn eine Kommunikation zwischen zwei Agenten kann nur stattfinden wenn beide miteinander verbunden sind Solch eine Verbindung stellt die Klasse Connection disaster model Connection dar In Abschnitt 5 3 3 wird erkl rt wie solche Verbindungen manuell erzeugt werden k nnen Es gibt allerdings auch die M g lichkeit Verbindungen nach festen Regeln automatisch erzeugen zu lassen Diese Arbeit bernehmen die Topologiemanage
12. che einzubinden Der Vorteil dieser Anordnung ist dass alle Informationen eines Agenten in einem Fenster aufgef hrt werden anstatt diese Informationen in weiteren Fenstern zu pr sentieren wodurch die Desktopober fl che unn tig berf llt werden w rde Ausgabestr me Neben den Fenstern die auf der Desktopoberfl che der An wendung angezeigt werden befinden sich am unteren Rand zwei durch Reiter 5 3 Die Oberfl che 59 Router1 ib W lt hide Message Message Destination Routeri RouterO Abbildung 5 8 Agentenmessagequeue getrennte Textfelder in welche die Standardausgabe System out und die Stan dardfehlerausgabe System err gelenkt werden Abbildung 5 9 Dadurch muss der Anwender nicht auf die gewohnten Ausgaben oder Stacktraces verzichten die zum Testen und zur Fehlerbehebung sehr hilfreich sind MV java lang NullPointerException at javax swing plaf basic Basic5crollPaneUl paint Basic5crollPaneVUl EZ at con jgoodies plaf plastic Plastic5crollPaneUl paint Plastic crol at javax swing plaf ComponentUI update ComponentUI java 142 at javax swing JConponent paintComponent JComponent java 54l v System out System err Abbildung 5 9 Ausgabestr me Die zwei Textfelder sind durch Reiter getrennt Sollte eine Ausgabe in dem nicht angezeigten Reiter erfolgen beginnt dieser zu blinken um anzuzeigen dass sich sein Inhalt ge ndert hat Sta
13. classpath bin gt 16 lt link href http java sun com j2se 1 4 1 docs api gt 17 lt javadoc gt 18 lt target gt 19 20 lt target name jar depends compile javadoc gt 21 lt jar destfile jarfile basedir bin 22 manifest manifest update true gt 23 lt jar gt 24 lt target gt 25 lt project gt Listing 7 1 Ant build Datei Um nun ein solches Antskript ausf hren zu lassen gen gt es in das Ver zeichnis zu wechseln in dem sich dieses Skript befindet und den ant Befehl aufzurufen Besitzt die Datei den Namen build xml wird sie automatisch erkannt und ausgef hrt Andernfalls kann dem Befehl die Datei mit dem zu erzeugenden Skript bergegeben werden Die beiden unterschiedlichen Versionen von DisASTer lassen sich mit Hilfe eines einzigen Antskripts generieren Dieses erzeugt zwei Zip Archive in denen sich die unterschiedlichen Versionen befinden Zus tzlich befindet sich in jeder dieser Versionen eine build Datei um das Programm erneut erzeugen zu lassen Um also aus der wesentlich kleineren Quellcode Version die vollst ndige Version zu erhalten gen gt es das beiliegende Antskript auszuf hren 7 8 Hilfesystem Das Kapitel 5 ber die Verwendung von DisASTer wird zusammen mit der API Dokumentation JavaDoc als Online Hilfe bereitgestellt Dadurch sind alle wichtigen Informationen ber und f r das Programm aus diesem abrufbar Da durch muss kein zus tzliches Programm ge
14. environmentUpdated void a a EnvironmentChangeListener EnvironmentUpdateListener environmentChanged void environmentUpdated void Abbildung 6 3 Observermodell des Environments erzeugt und verwaltet Die Teilnehmer dieses Systems werden Agenten genannt Die Topologie wird als Graph dargestellt wobei die Agenten die Knoten und die Verbindungen die Kanten beschreiben Die Verwaltung der Agenten ihre Posi tionen und Verbindungen kann durch Topologiemanger erfolgen Eine Topologie selbst kann eine Reihe solcher Manager besitzen Der Anwender kann dann ent scheiden ob er einen dieser Topologiemanager verwenden will oder ob er die Positionierung und die Verbindungen manuell einstellt Wenn ein Manager aus gew hlt wird bernimmt dieser beim Hinzuf gen oder Entfernen von Agenten die Aufgabe diese zu positionieren und Verbindungen mit den anderen Teilnehmern zu setzen Eine m gliche Konstellation die aus der Arbeit eines Topologiema nagers entstehen kann ist z B ein Verbundring in dem nur die benachbarten Agenten miteinander verbunden werden hnlich einem Token Ring Eine weitere M glichkeit w re es alle Agenten untereinander zu verbinden Um eine hohe Er weiterbarkeit des Systems zu garantieren k nnen diese Elemente Topologiema nager TopologyManager Verbindungen Connection oder Agenten Agent vom Benutzer erweitert werden Abbildung 6 4 zeigt den Aufbau der Topologie bei der bereits die zwei vorgestellten Manager
15. hrer die Wahl selbst was 2N Nachrichten ben tigt Die Markierung als Teil nehmer wodurch zus tzliche Zweitwahlen vermieden werden erspart weitere Netzwerkbandbreite vgl Coulouris et al 02 S 502f Alternatives Ringverfahren Um den worst case bei dem vorangegangenen Algorithmus 3N 1 zu verbessern kann eine alternative Variante zur Wahl eines Anf hrers in einer Ringstruktur verwendet werden Der Initiator einer Wahl sendet eine Wahlnachricht mit einer ID Liste in der zun chst nur seine eigene Kennung enthalten ist an den Ring Bei Empfang einer Wahlnachricht tr gt der Prozess seine ID in die Liste ein und sendet sie weiter Kommt die Liste aller IDs an den Initiator zur ck bestimmt dieser daraus das Maximum und sendet eine Wahlergebnisnachricht Mit diesem Verfahren wird der schlimmste Fall auf 2N Nachrichten redu ziert Eine Wahl mit dieser Methode ben tigt immer 2N Nachrichten Nachteil dieses Verfahrens ist allerdings der gro e Speicheraufwand der Nachricht Der Einsatz einer Teilnahmemarkierung w rde bei dieser Methode ebenfalls zu einer Erniedrigung der Bandbreite f hren da es ausreicht einen Wahlgang zu beenden vgl Oechsle02 Seite 16 Bully Algorithmus Beim Bully Algorithmus von Garcia Molina wird voraus gesetzt dass jeder Prozess eines verteilten Systems die Prozess IDs der anderen Prozesse kennt Ein Wahlgang mit diesem Verfahren l uft wie folgt ab 1 Merkt ein Prozess dass
16. nen sollte es auch in hohem Grad erweiterbar sein Hierzu geh rt die Er weiterbarkeit des Funktionsumfangs und die der Darstellungen Neben den gerade vorgestellten Anforderungen denen das Programm und die Bibliothek auf jeden Fall gerecht werden sollten gibt es noch einige Punkte die sich lohnen w rden integriert zu werden Diese Nice To Haves m ssen allerdings nicht um jeden Preis realisiert werden Zu ihnen geh ren Das Einbinden von Jar Archiven die die Erweiterungen der Bibliothek bein halten Es k nnte mit Hilfe eines Dateiauswahlfensters eine Klasse ausge w hlt werden die sich in einem Archiv befindet Hierzu m sste der Klassen pfad angepasst werden und das Dateiauswahlwerkzeug m sste den Inhalt dieser Archive anzeigen k nnen Das Programm k nnte netzwerkf hig gemacht werden um die entwickelten Algorithmen in einem realen Netzwerk einsetzen zu k nnen Die Visualisierung k nnte als Grafik oder sogar als Film exportiert werden wodurch die erzielten Ergebnisse besser dokumentiert werden k nnten Au Berdem k nnten diese Filme oder Grafiken in Vortr gen Vorlesungen oder Dokumentationen verwendet werden 3 Verteilte Algorithmen 6 3 Verteilte Algorithmen Dieses Kapitel gibt einen Einblick in die Thematik verteilte Algorithmen um den Hintergrund und die Motivation dieser Arbeit zu vermitteln Verteilte Algorithmen finden sich in vielen verteilten System wieder einige davon sogar im gr ten v
17. vgl auch Kaynar03 DSP Distributed Systems Platform Die Distributed Systems Platform DSP wurde entwickelt um verteilte Algorithmen zu implementieren zu simu lieren und zu testen Die Topologie und das Verhalten des Algorithmus werden in einer eigenen Skriptsprache der DSPL DSP Language beschrieben Die Simu lation geschieht ber eine Client Server Architektur bei der der Client den in der DSPL verfassten Algorithmus an einen Server schickt Dieser kompiliert das ber gebene Programm h lt diesen Vorgang in seiner Datenbank fest und f hrt die Simulation aus die dann beim Client dargestellt wird vgl auch Terrevoli97 YACSIM YACSIM Yet Another CSIM ist eine Erweiterung der Sprache C Es handelt sich dabei um eine Bibliothek die Subroutinen und Datenstruktu ren enth lt um ereignisgesteuerte oder prozessorientierte Simulationen zu erzeu gen Unter Zuhilfenahme dieser Komponenten k nnen so verschiedene Simula tionen nach dem Baukastenprinzip entwickelt werden Die daraus resultierende Anwendung enth lt gleichzeitig die Simulation und deren Laufzeitumgebung vgl auch Jump93 Seite 4 SimUTC SimUTC wurde entwickelt um Zeitsynchronisationsprobleme zu l sen Algorithmen werden mit C Sim einer C Erweiterung die SIMULA Eigenschaften mitbringen soll programmiert F r seine prozessorientierte Simu lation verwendet SimUTC Threads vgl auch Weiss et al 99 DAP Distributed Algorithms Platform DAP ist e
18. www dis uniromal it alcom it proprog nodel2 html Weiss et al 99 B Weiss G Gridling U Schmid K Schossmaier 1993 The SimUTC Fault Tolerant Distributed Systems Simulation Toolkit http citeseer nj nec com weiss99simutc pdf Zaroliagis02 C Zaroliagis G Prasinos A Poulakidas I Chatzigiannakis 2002 Distributed Algorithms Platform Basic Design Implemen tation and Functionality http www rul cti gr LEP DAP papers basic design and impl ps gz A Klassen bersicht s A Klassen bersicht disaster DisASTer class disaster control Controller class ControllerState class ControllerStateListener class Manual class Paused class Running class Stopped class disaster examples BullyAgent class ByzantinicGeneral class ByzantinicTraitor class CentralServerExclusionAgent class LamportClockAgent class MaekawaAgent class MutualExclusionAgent class RingExclusionAgent class RingLeaderOlAgent class RingLeaderO2Agent class RIPAgent class RoutingTable class A Klassen bersicht 145 SnapshotAgent class TotalPrimAgent class TotalTimeControlledAgent class UniqueClockAgent class VectorClockAgent class disaster gui AgentConsoleInfoFrame class AgentMessageQueuelnfoFrameGroup class OpenAllInfoFramesAction class AgentPane class AddAgentAction class AddInitMessageAction class CopyAgentAction class MessageReceiverCellRen
19. 1 1 in Java portiert wer den da sich dieser Code in der Regel auf das Verhalten der einzelnen Prozesse und nicht auf das Verhalten des ganzen Systems bezieht Konfigurationsm g lichkeiten wie der Topologieeditor in DisASTer finden sich in hnlicher Form bei DAP und ViSiDiA Mit Ausnahme von ns besitzen nahezu alle anderen Projek te eine hnliche Form der Simulation mit wenigen Abweichungen wie z B die Verwendung mehrerer Threads 10 Zusammenfassung und Ausblick 140 10 Zusammenfassung und Ausblick Es hei t ja Nomen est Omen Dieser Ausspruch trifft allerdings nicht auf diese Diplomarbeit zu Die Probleme bei der Entwicklung von DisASTer hatten zu keinem Zeitpunkt katastrophale Ausma e angenommen Auch das Programm selbst wird diesem Namen nicht gerecht denn es l uft stabil und zuverl ssig Die Arbeit an diesem Projekt war sehr interessant da sie viele verschiede ne Bereiche abgedeckt hat Ein erster wesentlicher Aspekt war der Entwurf in dem einige Entwurfmuster eingesetzt wurden die viele Problemstellungen der objektorientierten Programmierung vereinfachen konnten Dadurch konnten die aus vorherigen Vorlesungen erlangten Kenntnisse ber objekorientierte Analyse und objektorientiertes Design mit Hilfe von UML noch einmal aufgefrischt und vertieft werden Besonders facettenreich war die Arbeit mit Java In dem entstandenen Pro gramm konnten viele n tzliche Techniken eingebracht werden auch solche die bisher ka
20. 1 zeigt dass Nachrichten die eine Aktion ausl sen sollen nicht von einem anderen Teilnehmer stammen m ssen Die init Nachricht wird beispielsweise von keinem Agenten sondern vom System gesendet Andernfalls kann ein Agent sich selbst benachrichtigen um bestimmte Aktionen durchzuf h ren Aus der Abbildung wird ebenfalls ersichtlich dass verschiedene Aktionen init reminder Pi Aktion A Aktion C AktinD a request response P2 AktionB gt Abbildung 4 1 Nachrichtengesteuerte Simulation durch unterschiedliche Nachrichtentypen ausgel st werden Das Eintreffen eines bestimmten Nachrichtentyps kann durch eine extra f r sie definierte Methode abgefangen werden Das erleichtert dem Anwender die Trennung und Ausl sung der unterschiedlichsten Aktionen durch unterschiedliche Nachrichtentypen Eine Nachricht besitzt unabh ngig von ihrem Typ folgende Attribute sender der Agent der die Nachricht verschickt hat receiver der Agent der die Nachricht erh lt Ein Empf nger muss in jedem Fall angegeben werden und mit dem Sender verbunden sein sofern sich der Sender nicht selbst eine Nachricht sendet sendTime beschreibt den Zeitpunkt an dem die Nachricht gesendet wurde receptionTime legt zun chst fest wann eine Nachricht ausgeliefert wer den soll Der daf r angegebene Zeitpunkt ist nicht verbindlich Sobald die Nachricht bei ihrem Empf nger angek
21. 11 Durch die Initialisierung eines Agenten wird zugleich eine neue Wahl initiiert Dabei sendet der Agent eine Anfrage mit seiner Kennung ber den Ring 8 2 Koordination und bereinstimmung 126 12 public void init InitMessage message 13 sendToAll new Request null new Integer getID 14 setState MEMBER 15 setRole ROLE_SLAVE 16 Erh lt ein Agent eine Anfrage vergleicht er die empfangene ID mit seiner eigenen Ist seine eigene gr er und er noch nicht Teilnehmer einer Wahl sendet er diese anstatt der empfangenen an den Ring weiter Ist seine eigene kleiner als die empfangene leitet er die Nachricht weiter In beiden F llen setzt er sich als Teilnehmer einer Wahl Beinhaltet die empfangene Nachricht seine eigene ID bedeutet das dass er der neue Anf hrer ist und er teilt seine Erkenntnis ber einen Response dem Ring mit 17 public void onReception Request message 18 int id Integer message getPayload intValue 19 20 if getID lt id 21 sendToAll new Request null new Integer id 22 setState MEMBER 23 24 else if getID gt id amp amp getState MEMBER 25 sendToAll new Request null new Integer getID 26 setState MEMBER 27 28 else if getID id 29 sendToAll new Response null new Integer getID 30 setState NO_MEMBER 31 setRole ROLE_MASTER 32 leader getID 33 34 Bei Erhalt einer
22. 6 1 en e ie 6 1 6 4 7 4 gt Eintrittswunsch 8 1 gt gt Einverst ndnis kritischer Abschnitt 9 1 E E 10 4 kritischer Abschnitt Abbildung 3 6 Wechselseitiger Ausschluss nach Ricart und Agrawala Nachteil dieser Methode ist ebenfalls der hohe Bandbreitenverbrauch da f r einen Eintritt in den kritischen Abschnitt bei einem System mit N Teilnehmern immer 2 N 1 Nachrichten versendet werden m ssen vgl Coulouris et al 02 S 496ff 3 3 Koordination und bereinstimmung 19 Wahl Algorithmus von Maekawa Maekawa hat sich zum Ziel gesetzt die bei den anderen Algorithmen zu hoch ausfallende Netzbandbreite m glichst ge ring zu halten Dabei verfolgt er die Idee dass ein Prozess nicht von allen eine Zustimmung braucht sondern von einer Teilmenge der vorhandenen Prozesse gew hlt wird was ihn dazu berechtigt den kritischen Abschnitt zu betreten Um beide oben gesetzten Ziele zu verfolgen unterteilt Maekawa ein Netzwerk in W hlergruppen ein Einzige Voraussetzung die er an diese Teilmengen stellt ist dass sich die Teilmengen zweier beliebiger Prozesse berlappen D h jeder Prozess p i 1 2 N wird einer W hlergruppe V zugeordnet wobei Vi C P1 P2 PN F r die Mengen V und alle j 1 2 N gelten folgende Regeln e peVi V N V d h es gibt mindestens ein gemeinsames Element von zwei beliebigen Teilmengen
23. 7 6 View Integration des Inhaltsverzeichnisses Eine solche View verf gt ber einen Namen name und ein Label label wel ches sp ter im Reiter mit Inhalt Suche und Index angezeigt wird Zus tzlich wird in type die Klasse angegeben die zur Darstellung der View verwendet werden soll In diesem Fall wird die Klasse javax help TOCView verwendet die Teil der Javahelp Bibliothek ist Das data Element zeigt auf die Konfigurationsdatei in der vorhin das Inhaltsverzeichnis definiert wurde Javahelp besitzt eine Volltextsuche ber den gesamten Inhalt der Hilfe Diese Suche erfolgt allerdings nicht ber die HTML Seiten sondern ber eine eigens f r diesen Zweck erstellte Suchdatenbank Diese Datenbank wird mit jhindexer ei nem einfachen Konsolenprogramm das der Javahelp Bibliothek beiliegt erzeugt Um die Suchfunktion in dem angelegten Helpset zu verwenden wird eine neue View erzeugt und hinzugef gt Listing 7 7 7 8 Hilfesystem 106 1 lt view gt 2 lt name gt Search lt name gt 3 lt label gt Search lt label gt 4 lt type gt javax help SearchView lt type gt 5 lt data engine com sun java help search DefaultSearchEngine gt 6 JavaHelpSearch 7 lt data gt 8 lt view gt Listing 7 7 View Integration der Volltextsuche Eine weitere hilfreiche Ansicht ist der Index Hier findet der Benutzer wich tige Stichworte die ihn zu dem entsprechenden Kapitel f hren alphabetisch geordnet Der Index wird
24. Antwort tr gt der Empf nger die empfangene Kennung als die des jetzigen Anf hrers ein Falls er nicht selbst der Anf hrer ist leitet er die Nachricht an den Ring weiter 35 public void onReception Response message 36 leader Integer message getPayload intValue 37 38 if getID leader 39 sendToAll new Response null new Integer leader 40 setState NO_MEMBER 41 42 a Um diesen Algorithmus korrekt ausf hren zu k nnen wird die TokenRing Topologie ben tigt Die Anzahl der Agenten sollte mindestens zwei besser noch mehr als drei betragen Interessant ist in diesem Fall die Initialisierung des Agen ten der nach dem Agenten mit der h chsten Kennung kommt Um den Algorith mus noch interessanter zu gestalten kann die Reihenfolge der Agenten durchein andergebracht werden bevor sie mit der TokenRing Topologie verbunden werden 8 2 Koordination und bereinstimmung 127 da dadurch die IDs nicht in aufsteigender Reihenfolge sondern willk rlich verteilt werden Alternatives Ringverfahren Das alternative Ringverfahren soll den worst case der einfachen Ring basierten Wahl abfangen und die Nachrichtenanzahl reduzieren Hierzu wird anstatt nur eine Kennung ber den Ring zu senden eine Liste aller IDs gesammelt und der Initiator der Wahl bestimmt davon das Maximum Der Aufbau und der Konstruktor ist quvalent zum vorangegangenen Beispiel public class RingLeaderAgent extends
25. H chstens ein Prozess kann den kritischen Abschnitt betreten ME2 Terminierungsaspekt Anforderungen in den kritischen Bereich einzutreten oder ihn zu verlassen sind irgendwann erfolgreich ME3 Fairnessaspekt Wenn ein Prozess vor einem anderen anfordert in den kritischen Bereich einzutreten wird der Eintritt in den kritischen Bereich in dieser Reihenfolge erteilt Um der letzten Anforderung gerecht zu werden wird auf eindeutige logi sche Uhren zur ckgegriffen die eine eindeutige Reihenfolge der Anfragen den kritischen Bereich zu betreten garantiert vgl Coulouris et al 02 S 492ff Wechselseitiger Ausschluss mit zentralem Server Eigentlich sollte bei dem wechselseitigen Ausschluss auf einen zentralen Server verzichtet werden Es ist allerdings m glich dass dieser von allen gleichberechtigten Prozessen gew hlt wird siehe Abschnitt 3 3 2 Aus diesem Grund wird auch diese Variante hier vorgestellt Um den kritischen Abschnitt zu betreten sendet ein Prozess p seinen Ein trittswunsch an diesen Server Dieser verwaltet eine Warteschlange in die die 3 3 Koordination und bereinstimmung 17 Anfragen eingehen und nach dem FIFO Prinzip beantwortet werden sobald der kritische Abschnitt wieder betreten werden kann Nach dem Erhalt der Zusage des Servers kann der Prozess in den kritischen Abschnitt eintreten und teilt sein Ver lassen dem Server mit damit dieser dem n chsten Prozess in der Warteschlange den Eintrit
26. Unter klassen dieses Typs nicht erkannt Aus diesem Grund wurde der Pseudopoly morphismus mit Hilfe der Reflection API erzeugt Bevor eine Nachricht an einen Agenten ausgeliefert wird berpr ft die MessageQueue ob der Agent ber eine Methode verf gt die genau diesen Typ abf ngt Ist dies nicht der Fall wird eine Methode gesucht die die Oberklasse dieses Typen abf ngt bis eine passende onReception Methode gefunden wurde oder bis die Oberklasse Message er reicht ist f r die durch die Klasse Agent bereits eine Empfangsmethode existiert Dabei wird die Klasse des Nachrichtentyps mit den Parametern der Methoden verglichen die onReception hei en Wird eine passende Methode gefunden wird 7 5 Oberfl chengestaltung 98 das entsprechende Method Objekt mit der invoke Object Object Methode aufgerufen Der erste Parameter dieser Methode beschreibt das Objekt auf dem diese Methode ausgef hrt wird Der zweite Parameter das Objekt Feld stellt die zu bergebenen Parameter dar Auf diese Weise kann der Benutzer f r jeden Nachrichtentyp den er verwendet eine neue onReception Methode definieren und sicher sein dass diese auch aufgerufen wird sobald eine Nachricht dieses Typs ankommt 7 5 Oberfl chengestaltung Karsten Lentzsch ist der Meinung dass es wirklich einfach ist schlechte Ober fl chen mit Swing zu bauen vgl Lentzsch03 S 31 womit er den Nagel auf den Kopf getroffen hat H sslich langsa
27. Zwischenraum unterschieden Im obigen Bei spiel wird also immer ein Teilst ck der L nge 8 0 Pixel gezeichnet gefolgt von einem Zwischenraum von 5 0 Pixel Dieses Schema erstreckt sich ber die ge samte L nge einer Linie Es k nnen auch Felder mit mehr als zwei Segmenten angegeben werden um z B eine Punkt leer Strich Abfolge zu erzeugen Eine weitere Funktionalit t die in den Visualisierungen von DisASTer eine Verwendung findet ist der Farbverlauf Gradient Ein Farbverlauf kann alternativ zu einer einfachen F llfarbe verwendet werden Der folgende Code zeigt wie die aktuelle F llfarbe auf einen Farbverlauf gesetzt wird g2 setPaint new GradientPaint x1 y1 Color BLUE x2 y2 Color RED Die Erzeugung eines solchen Verlaufs kann man sich einfach vorstellen Auf einem Tablett werden an zwei verschiedenen Punkten zwei Farbeimer mit unterschied lichen Farben ausgeleert Die Farben verteilen sich gleichm ig ber das ganze Tablett bis sie zusammensto en An dieser Stelle vermischen sie sich und bil den den eigentlichen Verlauf Der Konstruktor der Klasse GradientPaint der im obigen Beispiel zu sehen ist verdeutlicht dieses Vorgehen Es werden zwei Punkte x1 y1 und x2 y2 angegeben auf die jeweils eine andere Farbe gegos sen wird In der Visualisierung werden Farbverl ufe vor allem f r die Darstellung der Agenten verwendet Durch einen Farbverlauf sieht es so aus als bes en die Agenten Schattierungen
28. aber w hrend einer Animation mehrfach aktualisieren Da der Controller weiss wann und in welchen Abst nden das Neuzeichnen erfol gen soll bernimmt er die Aufgabe die Ansichten zu benachrichtigen die dann den Zustand des Modells grafisch darstellen k nnen Auf diese drei Komponen ten setzt schlie lich die GUI auf die den Zugriff und die Steuerung aller anderen Komponenten besitzt In der Regel w rde die grafische Oberfl che unter die An sichten fallen aber in diesem Fall bernimmt sie doch einige Aufgaben mehr als nur die Darstellung des Modells ber sie wird das Modell gespeichert oder geladen der Controller angesteuert und die Ansichten eingebettet 6 3 Model 75 6 3 Model Dieser Abschnitt beschreibt das Datenmodell der Anwendung Kern des Mo dells ist das Environment Das Environment verwaltet alle einzelnen Teile des Systems wie in Abbildung 6 2 dargestellt wird Zu diesen Teilen z hlen die To pologie die das Netzwerk beschreibt in dem der Algorithmus eingesetzt wird die MessageQueue die als Ereignisliste angesehen werden kann der Verlauf der alle bereits abgearbeiteten Ereignisse und Aktionen speichert sowie das Agent log in dem die Textausgaben der Teilnehmer gespeichert und verwaltet werden Ausserdem werden alle gesendeten Nachrichten in einer zus tzlichen Liste verwal tet Das Environment selbst wird als Singleton implementiert d h es gibt nur eine Instanz dieser Klasse auf die ber die sta
29. anzuzeigen oder auch individuelle Einstellungen vorzunehmen gibt es die M glichkeit eigene Swing Komponenten zu jedem Agenten zu definieren Die entsprechende grafische Oberfl che wird in einer Klas se die von AgentComponent abgeleitet ist beschrieben Eine solche Komponente leitet sich aus JComponent ab und besitzt eine Referenz auf einen Agenten Von diesem k nnen Informationen abgegriffen werden die ber die grafische Ober fl che angezeigt oder sogar ver ndert werden k nnen F r den Aufbau dieser Oberfl che stehen dem Benutzer alle Klassen der Swing Bibliothek zur Verf gung Allerdings muss die Serialisierbarkeit der Oberfl che gew hrleistet werden Damit w ren alle Schritte erkl rt die zur Entwicklung von Agenten verteil ter Algorithmen notwendig sind Um Programme zu testen und zu debuggen oder einfach nur ein paar Informationen zu erhalten greifen viele Entwickler auf 5 2 Die Bibliothek 47 Textausgaben zur ck Die eben erstellten Agenten bilden hier keine Ausnahme Wer es gew hnt ist kann beim altbew rten System out println bleiben Die Standardausgabe System out und Standardfehlerausgabe System err wer den f r diesen Zweck in das Programm umgeleitet Ein eleganterer Weg w re jedoch der Einsatz der println Methode eines Agentenobjekts Die hier er folgten Eingaben werden in eine extra Konsole geleitet wobei jeder Eintrag eines bestimmten Agenten farblich hervorgehoben wird Eine genauere Beschreib
30. auf dessen weitere Untest tzung 2 TokenRing der Tokenring ordnet die Agenten in einem Ring an und verbin det jeweils die benachbarten Agenten miteinander Die dabei verwendeten Verbindungen lassen nur eine unidirektionale Kommunikation zu 3 _Complete Topology dieser Topologiemanager verbindet alle Agenten mit einander Wenn eigene Regeln f r das Verbinden der Agenten benutzt werden sollen k n nen mit f eigene Topologiemanager ausgew hlt und eingebunden werden Beim allgemeinen Umgang mit Topologiemanagern sei zu beachten dass bei der Wahl eines neuen Topologiemanagers alle bisherigen Einstellungen sowohl Verbindun gen als auch Positionen verloren gehen und durch die des neuen ersetzt werden Alle hier get tigten nderungen sowohl im Agenten als auch im Topologie bereich k nnen wieder verworfen werden Abbrechen Erst mit OK werden alle nderungen wirkungsvoll ViewPreferences In diesem Abschnitt wird erkl rt wie vorhandene Ansich ten angepasst werden indem zus tzliche Renderer hinzugef gt oder bestehende gel scht werden oder wie die Renderer angepasst werden Es wird auch gezeigt welche Schritte notwendig sind um eine eigene Ansicht in das Programm zu inte grieren Bei den folgenden nderungen sei zu beachten dass diese im Gegensatz zu den Einstellung des vorangegangenen Abschnitts sofort wirkungsvoll werden und und nicht mehr verworfen sondern nur r ckg ngig gemacht werden k nnen Abbil
31. auf die Umsetzung der Algorithmen konzentrieren Die Simulation und Visualisierung wird ihm von dem beiliegenden Programm abgenommen Im 2 Kapitel wird die genaue Aufgabenstellung dieser Arbeit vorgestellt in der die zu erreichenden Ziele gesteckt werden Zus tzlich findet sich in diesem Kapitel eine Anforderungsanalyse in der die Eigenschaften und Punkte aufgef hrt werden die im Laufe der Arbeit erf llt werden sollen Das darauf folgende Kapitel f hrt den Leser in das Thema ein Dort werden Algorithmen zu den Themen Uhrensynchronisation globale Zust nde Koordi nationsprobleme wie Festlegung einer Nachrichtenreihenfolge Wahl eines An f hrers oder bereinstimmungsprobleme z B das der byzantinischen Gener le vorgestellt Kapitel 4 gibt einen berblick ber das entstandene Programm und f hrt den Leser in die entscheidenden Konzepte ein Das Benutzerhandbuch des entstandenen Programms findet sich in Kapitel 5 Dort werden die Funktionen des Programms DisASTer sowie die Benutzung der entwickelten Bibliothek beschrieben Kapitel 6 widmet sich dann dem objektorientierten Entwurf der Arbeit Dieser besteht im Wesentlichen aus dem Model View Controller Paradigma und stellt die jeweiligen Komponenten vor In Kapitel 7 werden besondere Programmteile herausgepickt deren Imple mentierung entweder problematisch oder trickreich ist Das Kapitel wird mit der Beschreibung der Tests dieses Programms abgeschlossen Um einen weiteren Einb
32. aufgef hrt werden Die MessageQueue ist neben der Topologie und dessen Agenten ein weiterer wichtiger Bestandteil der Simulationsumgebung Sie bernimmt die Nachrich tensteuerung Alle Ereignisse werden in Form von Nachrichten aufgefasst Dazu geh ren nicht nur die Nachrichten die sich die Agenten untereinander schicken sondern auch jene die ein Agent sich selbst schickt oder die die er vom Sys tem erh lt Bevor ein Agent eine gesendete Nachricht erh lt wird diese zun chst in die MessageQueue aufgenommen Ab diesem Zeitpunkt bernimmt die Kon trollinstanz siehe Abschnitt 6 5 die Entscheidung wann eine Nachricht an den 6 3 Model TT Topolo TopologyManager Systemklasse Par list of managers Buebeeayanegerz Vom Benutzer used manager 0 1 erweiterbar doConnections void doPositions void Connection Agent TokenRing CompleteTopology Abbildung 6 4 Aufbau der Topologie entsprechenden Empf nger ausgeliefert wird Die MessageQueue dient als glo bale Nachrichten oder Ereignisliste Daneben verwaltet sie aber auch eine ei gene MessageQueue f r jeden Agenten In diesen finden sich ausschlie lich die Nachrichten die f r diesen Agenten bestimmt sind Die AgentMessageQueues beinhalten keine weiteren MessageQueues Wird die Simulation vom Anwender selbst gesteuert siehe Abschnitt 6 5 hat dieser die M glichkeit diese Listen zu ver ndern indem Na
33. aufgelistet state Variable die den Zustand des Agenten beschreibt M gliche Zu st nde k nnen besch ftigt wartend oder normal sein Sollten diese Zust nde nicht ausreichen kann ein Agent um weitere Zust nde erweitert werden role Variable welche die Rolle des Agenten beschreibt Die Rolle kann vor allem im Vergleich mit anderen Agenten ausschlaggebend sein M gliche 6 3 Model Bee JComponent 2 Systemklasse from javax swing Vom Benutzer C erweiterbar Agent String Tani description from java lang AgentComponent f 1 state int ole int send message Message void send packet Object receiver Agent void send packet Object receiver Agent duration int void send packet Object connection Connection void 2 send packet Object connection Connection duration int void sendToAll message Message void sendToAll payload Object void sendToAll payload Object duration int void Point setTimeout duration int void setTimeout payload Object duration int void lt init message lnitMessage void position timeout message TimeoutMessage void onReception message Message void Connection from java awt Abbildung 6 6 Aufbau der Agenten Rollen sind Master oder Slave Diese beiden Werte k nnen auch unter mehreren Bedingungen eingesetzt werden Die Rolle Master kann z B f r den Anf hrer oder einen zentralen Server eines Systems g
34. besitzt Repr sentiert wird diese Kennung durch einen einfachen int Wert der mit jeden neuen Agen ten inkrementiert wird Die Zuordnung einer Kennung erfolgt automatisch so dass der Anwender sicher sein kann dass jeder Agent eine andere Ken nung besitzt Zugriff auf die Kennung erfolgt ber die Methode getID state dieses Attribut beschreibt den Zustand des Agenten Dabei handelt es sich erneut um einen int Wert dem der Benutzer vordefinierte Konstan ten oder eigene Werte bergeben kann Bereits definierte Zust nde sind STATE_NORMAL beschreibt den normalen Zustand eines Agenten STATE_WAITING kann dazu verwendet werden einen Agenten als wartend z B auf eine Nachricht zu kennzeichnen _ _STATE_WORKING sagt aus dass der Agent zur Zeit besch ftigt ist Die vordefinierten Zust nde k nnen auch f r andere Zwecke verwendet wer den Hierbei handelt es sich nur um Vorschl ge die einen Zustandswechsel kennzeichnen k nnen Wichtig dabei ist dass die Visualisierungen auf die se vordefinierten Zust nde eingehen und diese grafisch darstellen k nnen Der Zugriff auf den Zustand wird durch die Methoden getState und setState int newState gew hrleistet role beschreibt die Rolle des Agenten Eine Rollenbeschreibung ist vor allem im Vergleich mit anderen Agenten von Vorteil Fungiert ein Agent als zentraler Server als Anf hrer oder hnliches kann das durch die Rollen verdeutlicht werden Als Kon
35. besitzt eine Gr e von ca 8 MB Die Quellcode Version besitzt folgende Dateien und Verzeichnisse doc in diesem Verzeichnis befindet sich das Benutzerhandbuch des Pro gramms im HTML Format lib dieses Verzeichnis beinhaltet zur Zeit nur die zus tzliche Javahelp Bibliothek jhall jar saved dieser Ordner enth lt bereits gespeicherte Beispielealgorithmen src ist das Verzeichnis indem die Java Quelldateien des Programms zu finden sind DisASTer bat diese Stapelverarbeitungsdatei und DisASTer sh k nnen sp ter zum Starten der Anwendung verwendet wer den license txt beinhaltet die Lizenz GNU General Public License unter der dieses Programm erh ltlich ist build xml ist das Ant Skript zum Kompilieren der Quelldateien MANIFEST MF wird zur Erzeugung des Jar Archivs verwendet in dem sich die Anwendung sp ter befindet Readme txt beinhaltet diese Informationen 5 1 Inhalt und Installation 41 Die fertige Version des Programms enth lt ebenfalls diese Struktur und noch einige zus tzliche Dateien und Ordner bin in diesem Verzeichnis finden sich die kompilierten Javaklassen des Programms lib zus tzlich zur Javahelp Bibliothek finden sich hier zwei weitere Ar chive disaster jar in dem sich die Anwendung befindet disaster dev jar in dem sich nur die zur Entwicklung n tigsten Klassen befinden Neben diesen Archiven m ssen alle neue
36. categoryopenimage tocopen topicimage topic gt lt tocitem text Benutzung target node2 gt lt tocitem text Installation target node3 gt Sie res gt lt tocitem gt vosou PwnPnN MH lt toc gt Listing 7 5 Auszug Inhaltsverzeichnis Jedes Kapitel jedes Unterkapitel und jede Seite wird durch ein tocitem repr sentiert Diese k nnen beliebig tief ineinander geschachtelt werden wodurch die Baumstruktur entsteht Jedes tocitem besitzt einen text der im Inhaltsver zeichnis angezeigt wird Die Seite auf die der Eintrag zeigt wird durch target festgelegt Hier wird das f r die entsprechende Seite definierte Mapping verwen det Ein weiterer Einsatz der Mappings wird im Wurzelelement toc deutlich ber categoryclosedimage categoryopenimage und topicimage kann je weils das Mapping einer Grafik angeben werden die f r diesen Elementtyp ge ff netes Verzeichnis geschlossenes Verzeichnis oder Thema verwendet werden soll Den einzelnen Eintr gen k nnen zus tzlich spezielle Grafiken zugewiesen werden Nachdem das komplette Inhaltsverzeichnis mit der oben vorgestellten Technik er stellt wurde muss es noch dem HelpSet bekannt gemacht werden indem diesem eine View hinzugef gt wird Listing 7 6 lt view gt lt name gt TOC lt name gt lt label gt Contents lt label gt lt type gt javax help TO0CView lt type gt lt data gt DisasterTOC xml lt data gt lt view gt ou AUNE Listing
37. d und f der Fall Beispielsweise stellt Ereignis b bei P das Senden der Nachricht m dar Das Ein treffen von m wird bei P gt als Ereignis c festgehalten Damit stehen diese beiden Ereignisse in einer logischen und kausalen Reihenfolge Im Gegensatz dazu sind die Ereignisse a und e unabh ngig voneinander was als nebenl ufig bezeichnet wird Um diesen beiden Ereignissen eine Reihenfolge zuzuordnen werden logische Uhren verwendet Lamport Methode Lamport hat einen einfachen Mechanismus erfunden mit dem es m glich ist eine logische Zeit zu erstellen Hierf r wird der sogennante Lamport Zeitstempel verwendet Dabei handelt es sich um einen monoton stei genden Softwarez hler dessen Wert keinerlei Beziehung zu einer physikalischen Uhr haben muss Jeder Prozess p eines verteilten Systems f hrt seine eigene logische Uhr L Das Ereignis e des Prozesses p wird dem Zeitstempel L e zugewiesen Um eine solche Lamport Uhr zu verwenden m ssen folgende zwei Regeln befolgt werden 3 1 Physikalische und logische Uhren 11 LC1 L wird inkrementiert bevor ein Ereignis in Prozess p veranlasst wird LC2 a Wenn ein Prozess p eine Nachricht m sendet gibt er m auch den Wert t L mit b Beim Empfang von lt m t gt berechnet ein Prozess p den Wert L maz L t und wendet dann LC1 an bevor er dem Ereignis receive m einen Zeitstempel zuweist Abbildung 3 3 zeigt das Beispiel aus Abbildung 3 2 mit logischen Uhren wobei d
38. dann in das Programm DisASTer Distributed Algorithms Si mulation Terrain geladen werden Hauptaufgabe dieses Programms ist die Ablaufsteuerung der Algorithmen sowie deren Visualisierung Die nachrichtengesteuerte Simulation kann dabei automatisch oder manuell gesteuert werden Die Visualisierung erfolgt z B in Form eines animierten Sequenzdiagramms Inhaltsverzeichnis Einleitung 1 Aufgabenstellung 3 Verteilte Algorithmen 6 3 1 Physikalische und logische Uhren 22222222 6 3 2 Globale Zust nde 242 2 en ernennen 13 3 3 Koordination und bereinstimmung oo aaa 15 berblick und Grobkonzept 34 4 1 Programmkomponenten oaoa a 34 4 2 Eigenschaften verteilter Algorithmen 2 22 2222 34 4 3 Kontrolle und Steuerung 2 2222 a nme 36 4 4 Visualisierung o oosa ceace reetan pitao dinaa 39 Benutzung des Programmes 40 5 1 Inhalt und Installation 00 aa a RL ae 40 5 2 Die Bibliothek ooa aaa send 42 52 Die Oberfl che oaa aa kenn 52 Entwurf 71 6 1 Eigenschaften verteilter Algorithmen 2 222 222 71 6 2 Erkenntnisse f r den eigenen Entwurf 2 2222222 72 GS Model ee ie anne ine ed 75 GA Wian u Sa eat hentai 83 65 Koll e sau omar air 85 6 6 Grafische Benutzeroberfl che GUI oaa aaa aaa 87 Implementierung und Test 91 7 1 Topologieeditor 2 4 2 a 91 7 2 Visualisierung und Animation aoaaa none 93 7 3 Klassenladen ooa aaa Ka un na de 95 7 4 Reflection und Pseudopolymorphismus 2 2 2
39. dem er die Zeit seiner eigenen Anfrage speichern kann 1 2 3 4 5 6 7 8 9 10 11 12 13 public class MutualExclusionAgent extends Agent private Arraylist buffer private int answers private int clock private int sentTime public MutualExclusionAgent setDescription MutEx Agent getID clock 0 getID sentTime 0 buffer new Arraylist setState STATE_NORMAL Der Eintrittswunsch wird durch die Initialisierung des Agenten ausgel st Da bei erh ht er seine logische Uhr und sendet eine Anfrage an die anderen Agenten Er merkt sich den Zeitpunkt an dem er die Anfrage gestellt hat und setzt den Z hler der Antworten auf 0 16 17 18 19 20 21 22 public void init InitMessage message clock 10 sendToAll new Request null new Integer clock setState STATE_WAITING sentTime clock answers 0 Erh lt ein Agent eine Anfrage muss er seinen momentanen Zustand berpr fen Hegt er selbst einen Eintrittswunsch vergleicht er die Sendezeit der Anfrage mit seiner eigenen Ist diese kleiner als seine eigene muss er dem Sender Vor rang lassen und sendet ihm sein OK ansonsten puffert er die Anfrage Will der Agent selbst nicht den kritischen Abschnitt betreten sendet er unmittelbar sein 8 2 Koordination und bereinstimmung 122 OK Befindet sich der Agent im kritischen Abschnitt wird die Anfrage ebenfalls gepuffert 23 public void onRecep
40. der automatische Ablauf kann mit diesem Befehl angehalten werden Der aktuelle Schritt wird dabei allerdings noch zu Ende gef hrt Stop anders als der Pause Befehl h lt dieser Befehl den Ablauf nicht an sondern bricht ihn regelrecht ab und setzt den Algorithmus auf seinen Anfangszustand zur ck 4l Previous mit diesem Befehl kann der letzte Zustand eines Algorithmus wieder hergestellt werden Diese Funtionalit t erinnert an den Verlauf ei nes Webbrowsers Wie dort k nnen auch hier mehrere Schritte auf einmal r ckg ngig gemacht werden in dem der gew nschten Zeitpunkt aus einer Liste gew hlt wird IP Next f hrt einen Einzelschritt durch sofern der Algorithmus durch II oder E unterbrochen ist Mit Hilfe des Einzelschritts kann der Anwender die Geschwindigkeit der Simulation selbst betimmen Diese Methode ist jedoch nicht mit der manuellen Steuerung zu vergleichen da in diesem Fall der Ablauf schon feststeht Im Falle der manuellen Steuerung kann der Anwender noch in den Ablauf des Algorithmus eingreifen Steuerungsmodi Die Einstellungsm glichkeiten die f r den Ablauf eines Al gorithmus zur Verf gung stehen werden in diesem Abschnitt n her erl utert Dabei wird unter anderem auf die einzelnen Modi die f r die Steuerung vorge sehen sind eingegangen Die Geschwindigkeit wird durch einen Schieberegler bestimmt und zwar von langsam ganz links bis schnell ganz rechts Dadurch wird die Zeitspanne die f r einen
41. der derzeitige Anf hrer ausgefallen ist startet er eine Wahl sofern er nicht die nunmehr h chste Kennung besitzt bei h chster Kennung Schritt 5 2 Um eine Wahl zu starten werden Wahlnachrichten an alle Prozesse mit einer h heren ID gesendet und auf dessen Antwort gewartet 3 Trifft nach einem Timeout keine Antwort von einem Prozess ein gilt dieser als ausgefallen 4 Beim Eintreffen einer Wahlnachricht initiiert der Empf nger eine eigene Wahl 1 5 Stellt ein Prozess fest dass er die h chste ID im System hat z B dadurch dass er keine Antwort von einem Prozess mit h herer ID erhalten hat sendet er eine Koordinatornachricht an alle anderen Prozesse um ihnen dies mitzuteilen 3 3 Koordination und bereinstimmung 24 Das Beispiel in Abbildung 3 10 wird durch P initiiert der zuerst bemerkt hat dass P ausgefallen ist Nachdem P festgestellt hat dass er die h chste Kennung besitzt kann er dies den anderen Prozessen mitteilen a O X R Anwo awon twort twort Wal Wahia Waha Koordinator O O Ko oniiir Abbildung 3 10 Wahl durch Bully Algorithmus Im besten Fall ben tigt diese Methode N 2 Nachrichten n mlich genau dann wenn der Prozess mit der zweith chsten Kennung feststellt dass der Ko ordinator ausgefallen ist Dann kann dieser unmittelbar allen anderen Prozessen mitteilen dass er der neue Koordinator ist Im schlimmsten Fall werden O N Nachrichten ben t
42. es sehr umst ndlich ist diese zu testen Auch hierbei wurden bertriebene Eingaben gemacht wie das schnelle ndern der Gr e des Fensters oder st ndiges Zoomen der Ansichten Das Laden und Speichern der Umgebung wurde ebenfalls einem Systemtest unterzogen Wichtig war hier zum einen das korrekte Einlesen der gespeicherten Daten aber auch das korrekte Verhalten des Programms dessen Bedienelemente 7 9 Test 109 sich an die neue Umgebung anpassen m ssen Wird z B eine Umgebung mit ih rem Verlauf gespeichert muss es m glich sein nach dem Laden dieser Umgebung in den Verlauf direkt eingreifen zu k nnen Das Klassenladen wird noch einmal gesondert betrachtet Der Benutzer be kommt an vielen Stellen die M glichkeit eigene Klassen in das System zu in tegrieren Dabei muss das Programm korrekt entscheiden ob es sich bei der ausgew hlten Datei um eine Javaklasse handelt ob diese Klasse berhaupt gela den werden kann hierzu muss sie sich im Klassenpfad der Anwendung befinden und ob die Klasse den ben tigten Anforderungen entspricht und ber kurz oder lang die gew nschte Klasse erweitert oder das ben tigte Interface implementiert Allgemein ist es wichtig dass der Benutzer bei auftretenden Fehlern eine R ckmeldung erh lt die ihm Aufschluss ber die Gr nde des Fehlschlagens gibt Auch diese F lle werden im Systemtest ber cksichtigt 7 9 3 Klassentests Klassentests auch Unittests genannt werden dazu verwend
43. in der Regel Abweichungen auf Um diese Synchronisationfehler zu beheben gibt es zwei unterschiedliche Methoden 1 die externe Synchronisation und 2 die interne Synchronisation 3 1 Physikalische und logische Uhren 7 Bei der externen Synchronisation wird eine externe Quelle z B eine UTC Quelle verwendet die interne Synchronisation hebt Abweichungen zwischen zwei Pro zessen auf Die interne Synchronisation ziehlt somit nicht auf die Genauigkeit der Uhren im Vergleich zu einer externen Quelle sondern auf eine m glichst genaue Stimmigkeit zwischen den einzelnen Prozessen Um eine interne Synchronisation zu gew hrleisten wurden bereits mehrere Verfahren entwickelt Christian Bei der Methode von Christian wird ein Zeit Server verwendet Die ser erh lt seine Zeit zun chst von einer externen Quelle Coulouris Dollimore und Kindberg beschreiben die weitere Arbeitsweise dieser Methode wie folgt Ein Prozess p fordert die Zeit in einer Nachricht m an und empf ngt den Zeitwert t in einer Nachricht m t wird in m zum letzten m glichen Zeitpunkt vor der bertragung vom Computer von S eingetragen Der Prozess p zeichnet die Gesamt Round Trip Zeit T ouna auf die ben tigt wurde um die Anforderung m zu senden und die Antwort m zu empfangen Eine einfache Sch tzung der Zeit auf die p seine Uhr setzen soll ist t Tina wobei vorausgesetzt wird dass die vergangene Zeit gleichm ig auf geteilt wurde be
44. in das Programm zu integrieren wird der Benutzer mit einem Datei auswahldialog der Klasse JFileChooser aus der Swing Bibliothek aufgefordert diese aus dem Dateisystem auszuw hlen Um das Ausw hlen anderer Dateity pen zu vermeiden verwendet dieser Dialog einen sogenannten FileFilter mit dem es m glich ist nur bestimmte Dateitypen in diesem Fall class Dateien anzuzeigen Von der Auswahl der Klassendatei aus dem Dateisytem bis hin zu einem Java Objekt dieser Klasse ist es allerdings noch ein weiter Weg Zun chst muss die Klasse in die Virtuelle Maschine geladen werden Diese Aufgabe bernehmen die Klassenlader ClassLoader Die gew hlte Klasse liegt zun chst nur als File Objekt vor aus dem noch kein Objekt erzeugt werden kann und mit dem auch kein Klassenlader etwas anfangen kann Es besteht jedoch die M glichkeit den Pfad der Datei mit Hilfe der Methode toURL der Klasse File in eine URL umzuwandeln Ein URLClassLoader java net URLClassLoader kann was sein Name schon ver t diese URLs benutzen um eine Klasse zu laden Beim Erzeu gen einer neuen Instanz dieses Klassenladers wird diesem ein Feld von URLs im Konstruktur bergeben Aus diesem Feld k nnen dann zus tzliche Klassen in das System geladen werden Diese Arbeitsweise funktioniert allerdings nur solange die Klassen in keinem Package liegen Das File Objekt weiss nicht dass es eine Javaklasse repr sentiert und es weiss auch nicht welchem Package diese Klas
45. inittialisiert wird ist nebens chlich Gegenseitiger Ausschluss von Ricart und Agrawala Die L sung des wech selseitigen verteilten Ausschlusses von Ricart und Agrawala wurde f r ein Netz werk mit Multicast Funktionalit t entwickelt Er l sst sich wie folgt beschreiben Eintrittswunsch ber Multicast an alle anderen Prozesse senden und auf deren Antworten warten Nachdem eine Antwort von jedem anderen Prozess eingetroffen ist kann der kritische Abschnitt betreten werden Beim Eintreffen einer Anfrage zum Eintritt in den kritischen Abschnitt 8 2 Koordination und bereinstimmung 121 falls selbst kein Eintrittswunsch vorliegt Einverst ndnis zum Eintritt senden falls selbst Eintrittswunsch vorliegt und Zeitstempel der Anfrage klei ner als der der eigenen Anfrage Einverst ndnis senden Falls der ei gene Eintrittswunsch vor der empfangenen Anfrage erfolgte wird die Anfrage gepuffert falls selbst im kritischen Abschnitt Anfragen puffern und nach Aus tritt Einverst ndnisse aller gepufferter Anfragen senden Ein Agent der den Algorithmus von Ricart und Agrawala implementiert muss daher einige Informationen speichern Zun chst einmal muss er ber einen Puffer verf gen in dem Anfragen anderer Agenten gespeichert werden Er braucht einen Z hler um die Antworten der anderen Agenten auf seine Anfragen aufzuneh men eine logische Uhr um das Verfahren fair ausf hren zu k nnen und einen Wert in
46. langsam zu laufen Um m gliche Ausrei er auszuschlie en wird eine maximal erlaubte Round Trip Zeit festgelegt die gleichzeitig die Genauigkeit des Algorithmus bestimmt Ausrei er werden aus diesem Verfahren eliminiert wodurch ein fehlertoleranter Mittelwert entsteht Anstatt den einzelnen Prozessen die neue aktuelle Zeit zu senden er halten diese die Zeitdifferenz die ausgeglichen werden muss Dabei kann es sich sowohl um einen negativen als auch um einen positiven Wert handeln Die einzige Gefahr die bei diesem Verfahren besteht ist ein Ausfall des Mas ter Prozesses Sollte dies der Fall sein m ssen die briggebliebenen Prozesse einen neuen Master bestimmen Algorithmen die sich dieser Problematik wid men werden in Abschnitt 3 3 2 beschrieben vgl Coulouris et al 02 S 457f NTP Network Time Protocoll Die beiden oben vorgestellten Algorithmen BTP und die Methode von Christian sind ausschlie lich f r den Einsatz in lokalen Netzwerken vorgesehen Um Computer auch ber das Internet zu synchronisieren wurde das NTP Protokoll entwickelt Dabei verfolgt NTP folgende Ziele 1 _ Synchronisierung mit einer UTC Quelle ber das Internet 2 berstehen l ngerer Verbindungsunterbrechungen 3 Gew hrleistung ausreichend h ufiger Synchronisierung 4 Schutz vor St rung der Zeitdienste Das NTP Protokoll wird durch eine mehrschichtige Server Architektur reali siert Diese Schichten entstehen durch eine logische Hierarchie be
47. mit der ID ersetzt 15 public void onReception Message message 16 int rlc Integer message getPayload intValue 17 18 uniqueClock Math max uniqueClock rlc 19 uniqueClock 10 20 uniqueClock uniqueClock 10 21 uniqueClock getID 22 printin received lt message getSender 23 rlc gt at uniqueClock 24 25 Aufbau Verbindung und Initialisierungen k nnen vom vorigen Beispiel ber nommen werden Vektoruhren Vektoruhren sind eine Alternative zu den Lamport Uhren Dabei verwaltet jeder Prozess einen Vektor mit den Zeitstempeln der anderen Prozesse nach folgenden Regeln 8 1 Logische Uhren 114 VC1 Zun chst ist V j 0 f r i j 1 2 N VC2 Unmittelbar bevor p einem Ereignis einen Zeitstempel zuweist setzt er Vili Vili 1 VC3 p gibt jeder versendeten Nachricht den Wert t V mit VC4 Wenn p einen Zeitstempel t in einer Nachricht empf ngt setzt er Vilj mai f r j 1 2 N Diese komponenetenweise Bildung des Maximalwerts f r zwei Vektor Zeit stempel wird auch als merge Operation bezeichnet Bevor dem Empfang der Nachricht ein Zeitstempel zugewiesen wird wird VC2 angewendet Eine Implementierung dieses Verfahrens in DisASTer k nnte wie folgt aus sehen wobei der Vektor noch mit null initialisiert wird da beim Aufruf des Konstruktors noch nicht alle anderen Prozesse bekannt sind public class VectorClockA
48. muss zuverl ssig sein d h jede gesendete Nachricht kommt irgendwann bei ihrem Empf n ger an 3 3 Koordination und bereinstimmung 15 Die Kan le sind unidirektional und agieren nach dem FIFO Prinzip First In First Out Alle Prozesse sind in beiden Richtungen miteinander verbunden Ein Schnappschuss kann von jedem Prozess jederzeit initialisiert werden Die Ausf hrung einzelner Aktionen der Prozesse wird durch den Schnapp schuss nicht beinflusst Der eigentliche Algorithmus unterteilt sich in zwei Regeln 1 Marker Empfangsregel f r Prozess p Nachdem p eine Marker Nachricht ber Kanal c empfangen hat if pi hat seinen Zustand noch nicht aufgezeichnet then zeichnet er seinen Prozesszustand jetzt auf zeichnet er den Zustand von c als leere Menge auf aktiviert er die Aufzeichnung von Nachrichten die ber an dere Eingangskan le ankommen else pi zeichnet den Zustand von c als die Menge der Nachrichten auf die er ber c seit der letzten Zustandsaufzeichnung emp fangen hat end if 2 Marker Senderegel f r Prozess p Nachdem p seinen Zustand aufgezeichnet hat erfolgt f r jeden Ausgangskanal c pi sendet eine Marker Nachricht ber c bevor er andere Nach richten ber c sendet Es ist durchaus m glich dass die ber den Schnappschuss Algorithmus auf gezeichneten Zust nde nie wirklich gleichzeitig eingetreten sind vgl Coulouris et al 02 S 471ff 3 3 Koordinatio
49. nimmt Ist diese H rde erst einmal genommen steht der Ent wicklung ergonomischer Oberfl chen nichts mehr im Weg Es bleibt nur noch das Problem mit dem Look and Feel Aber auch hier finden sich immer mehr L sun gen Die Anzahl neu entwickelter Look and Feesls steigt stetig Angefangen hat 7 5 Oberfl chengestaltung 99 diese Entwicklung mit dem Kunststoff Look and Feel von Incors Daneben fin den sich mittlerweile diverse Simulationen verschiedenster Betriebssysteme oder Windowmanager sowie L sungen die sich auf Geschwindigkeit oder Einfach heit spezialisiert haben Unter dieser Auswahl unterschiedlichster Look and Feels findet sich mittlerweile ein passendes f r jedes Anwendungsgebiet In DisASTer wurde das Ziel verfolgt eine schnelle aber auch eine optisch an sprechende Oberfl che anzubieten Hierf r wurde zun chst das bereits erw hn te Kunststoff Look and Feel in Betracht gezogen doch dessen Einsatz hat die Leistung des Programms gerade im Visualisierungsbereich deutlich verringert Aus diesem Grund wurde ein Look and Feel gesucht welches weniger Ressour cen ben tigt Mit dieser Zielsetzung arbeitet das JGoodies Projekt von Karsten Lentzsch In diesem finden sich eine Reihe von Anwendungen und Look and Feels die schnell und leistungsorientiert arbeiten Eines der dort zu findenden Look and Feels ist das PlasticXP Look and Feel was auch f r diese Anwendung verwendet wurde Dieses simuliert zum Teil das Ausseh
50. st Die wichtigste Datei hierbei ist das HelpSet Ein HelpSet wird durch eine XML Datei repr sentiert die die Endung hs besitzt Hier werden alle weiteren XML Konfigurationsdateien und Einstellungen der An sichten Views angegeben Diese Views sind unter anderem f r den Aufbau des Inhaltsverzeichnisses der Volltextsuche und des Index verantwortlich Die folgenden Abschnitte erkl ren Schritt f r Schritt die Erzeugung des HelpSets ausgehend von dessen Rumpf Listing 7 2 7 8 Hilfesystem 104 lt xml version 1 0 encoding IS0 8859 1 gt lt DOCTYPE helpset PUBLIC Sun Microsystems Inc DTD JavaHelp HelpSet Version 1 0 EN http java sun com products javahelp helpset_1_0 dtd gt lt helpset version 1 0 gt lt title gt DisASTer Help lt title gt Sl aa ar lt helpset gt vosou PwnpnMH en oO Listing 7 2 Helpset Rumpf Die zweitwichtigste Datei eines HelpSets ist die Mapping Datei Endung jhm in der alle verwendeten HTML Seiten aber auch Grafiken einer eindeutigen Be zeichnung zugeordnet gemapt werden Ein Auszug der verwendeten Mapping Datei in Listing 7 3 zeigt die Arbeitsweise 1 lt map version 1 0 gt 2 lt Mapping einer Grafik gt 3 lt mapID target tocopen url images toc_open gif gt 4 lt Mapping einer Webseite gt 5 lt mapID target api url api overview summary html gt 6 Ze FE 7 lt map gt Listing 7 3 A
51. von Schleifendurchl ufen 7 9 2 Systemtest Mit Hilfe zahlreicher Beispiele und Konfigurationen wurde das Programm auf m gliche Programmierfehler und falsche Eingaben des Anwenders getestet aber auch auf korrektes Verhalten Dabei wurde schon bei der Implementierung darauf geachtet dem Benutzer die M glichkeit zu nehmen falsche Eingaben zu machen So wird beispielsweise die Funktionalit t des Einzelschritt Knopfes aufgehoben solange ein Zeitschritt noch animiert wird Der Benutzer k nnte diesen Knopf zwar weiter sehr h ufig hintereinander dr cken allerdings ohne irgendeine Wir kung zu erzielen V llig unn tze Eingaben werden von vorne herein unterbunden So wird beispielsweise der Startknopf deaktiviert nachdem er gedr ckt wurde und wird erst wieder aktiviert sobald der Anwender die Simulation ber Stopp oder Pause anh lt Die Deaktivierung von Kn pfen deren Funktionalit t nicht verf gbar ist wird sehr h ufig angewendet Gerade die Steuerung hat einen hohen Stellenwert bei den Tests erhalten da hier die meisten Fehler auftreten k nnen So wurde auch h ufig der Wechsel zwischen den unterschiedlichen Steuermodi getestet um sicher zu gehen dass dieser auch wirklich ohne negative Nebenwirkungen von statten geht Ein anderer Punkt der vor allem bei den Systemtests zum Tragen kam waren die Ansichten Diese sind nur sehr schwer mit anderen Testverfahren zu pr fen da sie in der grafischen Oberfl che dargestellt werden und
52. wodurch ein einfacher aber optisch ansprechender 3D Effekt erzielt wird Ein gro er Vorteil eines Graphics2D Objekts ist dass es sich problemlos ska lieren l sst Diese Technik wird zum Zoomen der Ansichten verwendet Mit ei nem einfachen Graphics Objekt ist eine Skalierung nur mit dem Einsatz eines BufferedImage m glich Dabei h tte dann die Ansicht in ein solches Bild por tiert werden m ssen um dieses dann zu vergr ern oder zu verkleinern Dieser Weg w rde allerdings viel Rechenleistung in Anspruch nehmen wohingegen die Skalierung des Graphics2D Objekts wesentlich performanter ist Um die Visualisierung ein wenig lebendiger zu gestalten werden Animationen verwendet Diese werden vom Controller Abschnitt 6 5 mit Hilfe von Threads realisiert Dabei wird ein neuer Thread gestartet der im Laufe eines Zeitschritts die Ansichten in regelm igen Abst nden benachrichtigt sich neu zu zeichnen Der prozentuale Fortschritt eines Zeitschrittes wird mit der double Variablen progress an die Ansichten und deren Renderer weitergegeben Eine genaue Be schreibung der Erzeugung von Animationen mit Hilfe dieser Variablen findet sich in Abschnitt 5 2 4 7 3 Kilassenladen 95 7 3 Klassenladen DisASTer ist hochgradig erweiterbar Der Anwender kann an sehr vielen Stellen eigene Klassen verwenden Hierunter fallen z B Erweiterungen der Klasse Agent Connection TopologyManager View oder Renderer Um seine selbst geschriebe nen Klassen
53. zu erh hen wird er in Zehnerschritten erh ht und an die Einer stelle wird die Kennung des jeweiligen Prozesses eingef gt Voraussetzung f r dieses Verfahren ist eine H chstzahl von 10 Agenten mit einer Kennung von 0 bis 9 Um das Verfahren f r noch mehr Agenten zu verwenden k nnte die Z hlung auch in Hunderterschritten usw erfolgen Die Implementierung eines Agenten mit einer eindeutigen Uhr wird im Folgen den vorgestellt Der Agent verf gt ber einen Integer Wert der die Zeit angibt Dieser wird im Konstruktor mit der ID des Agenten initialisiert public class UniqueClockAgent extends Agent private int uniqueClock uniqueClock getID 1 2 3 4 public UniqueClockAgent 5 6 description UniqueClockAgent getID 7 Die Initialisierung sendet wie im vorangegangenen Beispiel eine Nachricht an den n chsten Agenten Vor dem Senden dieser Nachricht die den Zeitstempel des Agenten enh lt wird dieser erh ht 8 public void init InitMessage message 9 uniqueClock 10 10 send new Message getOthers O J new Integer uniqueClock 11 12 printin sending Message to getOthers 0 13 at uniqueClock 14 Nach dem Empfang einer solchen Nachricht wird wie vorher auch die Uhr auf das Maximum beider gesetzt Dabei k nnte aber die Kennung des Senders in die logische Uhr des Empf ngers geraten Um dies zu verhindern wird die letzte Stelle entfernt und
54. 16 public void onReception Message message 17 initVector 18 19 int vm int message getPayload 20 int senderID message getSender getID 21 22 for int i 0 i lt v length i 23 v i Math max vli vml i 24 25 v getID 26 println received lt message getSender 27 print vm gt at print v 28 Bei der Initialisierung des Vektors wird zun chst berpr ft ob dieser schon in itialisiert wurde sprich sein Wert noch null ist Ist dies nicht der Fall wird er nach Regel VC1 mit 0 an allen Eintr gen initialisiert 29 private void initVector 30 if v null 31 v new int getOthers 1length 1 32 for int i 0 i lt v length i 33 v i 0 34 35 36 Um alle Werte des Vektors in einer angemessenen Form v1 V2 un ausgeben zu k nnen wird folgende Hilfsmethode verwendet 37 private String print int v 38 StringBuffer sb new StringBuffer 39 for int i 0 i lt v length i 40 if i lt v length 1 41 sb append v i 42 else 43 sb append v i 44 45 return new String sb 46 47 Auch dieses Beispiel l sst sich mit der Konfiguration der vorangegangenen ausf hren zwei oder mehr Agenten die jeweils miteinander verbunden sind 8 2 Koordination und bereinstimmung 116 8 2 Koordination und bereinstimmung 8 2 1 Verteilter wechsel
55. 2222 96 7 5 Oberfl chengestaltung ooa Coon 98 7 6 Speichern von Umgebungszust nden 2 22 2222 100 7 7 Verteilung mit Ant 222222 Coon 101 28 Hilfesystem oc sceo eretara e a e a 102 DE VE 2 E 107 8 Beispiele 8 1 Logische ben 2 0 za 208 saw anne ei 8 2 Koordination und bereinstimmung 22 22 22 22 20 9 Verwandte Projekte 9 1 Vorstellung der Projekte 9 2 Zusammenfassung und Vergleich 10 Zusammenfassung und Ausblick Literaturverzeichnis A Klassen bersicht vi 111 111 116 135 135 137 140 142 144 1 Einleitung 1 1 Einleitung Verteilte Algorithmen ist ein Teilgebiet aus der Vorlesung verteilte Systeme Die Schwierigkeit dieses Themas liegt in der umst ndlichen Umsetzung von bun gen Es muss eine Umgebung geschaffen werden in der die Algorithmen ablaufen k nnen Dabei beschr nkt sich die Ausgabe dieser Umgebung h ufig auf Text ausgaben auf der Konsole die das Verst ndnis f r die Arbeitsweise der einzelnen Algorithmen nicht f rdern Diese Arbeit besch ftigt sich mit der Entwicklung und Umsetzung eines Sys tems das diese bungen betr chtlich vereinfachen soll Dabei handelt es sich um einen Baukasten und ein Programm die es dem Anwender erlauben verteil te Algorithmen in Java zu beschreiben Aus diesem Baukasten k nnen Klassen erweitert werden die Methoden bereitstellen solche Algorithmen zu implemen tieren Dabei muss sich der Anwender nur
56. 3 Ljava lang Objec Message 4 Router2 Router4 Ljava lang Objec Message l4 Router Routeri IL iawa lann Ohiec _ Messane Abbildung 5 7 Messagequeue In einer Tabelle wird angezeigt wann eine Nachricht gesendet wurde von wem sie stammt und an wen sie ausgeliefert werden soll Des weiteren ist erkennbar welches Objekt verschickt und welcher Nachrichtentyp verwendet wurde Diese Tabelle gibt Aufschluss ber den geplanten Ablauf des Algorithmus da dort erkennbar wird welche Aktion von welchem Agenten als n chstes ausgef hrt wird AgentMessageQueues F r jeden Agenten existiert eine separate Message Queue die alle Nachrichten enth lt die an diesen Agenten adressiert sind Da durch kann der Benutzer sein Augenmerk auf einzelne Prozesse eines Algorithmus richten In diesen Fenstern Abbildung 5 8 befinden sich zus tzlich die Steuer elemente die ben tigt werden um in den Ablauf eines Algorithmus einzugreifen Mit Hilfe dieser Befehle kann die Nachrichtenreihenfolge ebenso ge ndert wie Nachrichten gel scht werden Im Abschnitt 5 3 4 wird genauer auf dieses Thema eingegangen Abgesehen von den Nachrichten die an den speziellen Agenten gerichtet sind wird in diesem Fenster noch zus tzlich die Agentenkomponente AgentComponent angezeigt Bei der Agentenkomponente handelt es sich um die Swing Komponente die verwendet werden kann um zus tzliche Informationen oder Befehle in die gra fische Benutzeroberfl
57. 32 public void onReception Message message 33 if buffer isEmpty 34 voted false 35 36 else 37 send new Response Agent buffer remove 0 null 38 voted true 39 40 Nach einem Timeout verl sst ein Agent wieder den kritischen Abschnitt und teilt dies seinen Gruppenmitglieder ber eine einfache Nachricht mit 41 public void timeout TimeoutMessage timeout 42 setState STATE_NORMAL 43 sendToAll new Message 44 45 Auch f r diesen Algorithmus wird nur eine Klasse verwendet Die Verbin dungen zwischen den einzelnen Agenten sollte in diesem Fall allerdings manuell durchgef hrt werden um die Gruppen herstellen zu k nnen denen die Agenten zugeordnet sind 8 2 2 Wahl eines Anf hrers Die Wahl eines Anf hrers ist ein Problem dass bereits von einigen vorangegan genen Algorithmen verwendet wurde um beispielsweise einen zentralen Server zu bestimmen Eine genaue Beschreibung der Problematik ist in Abschnitt 3 3 2 zu finden 8 2 Koordination und bereinstimmung 125 Ringbasierte Wahl Chang und Roberts haben ein Verfahren entwickelt um einen Anf hrer in einer Ringstruktur festzulegen Um die Wahl zu initiieren wird eine Wahlnachricht mit der eigenen ID an den n chsten Prozess gesendet Zus tzlich merkt sich der Prozess dass er bereits Teilnehmer einer Wahl ist Bei Erhalt einer Wahlnachricht berpr ft der Empf nger seine ID mit der der Nachrich
58. Abschlie end wird auf die Tests des Programms eingegangen 7 1 Topologieeditor Der Topologieeditor ist ein Teil der Einstellungen und wird dazu verwendet die einzelnen Agenten der Umgebung zu positionieren und Verbindungen zwischen ihnen zu erzeugen Die Arbeitsweise des Topologieeditors hnelt der eines Gra fikprogramms und wird auch wie ein solches implementiert Zur Umsetzung wird aus diesem Grund das Entwurfsmuster State verwendet Die Struktur und die Vorgehensweise dieses Entwurfsmusters wurde bereits im Entwurf der Kontrollin stanz Abschnitt 6 5 beschrieben Kurz zusammengefasst kann festgehalten wer den dass eine Klasse die dieses Entwurfsmuster verwendet mehrere Zust nde annehmen kann die das Verhalten dieser Klasse bzw einer Instanz dieser Klasse beinflussen Im Falle eines Grafikprogramms und des Topologieeditors werden die einzelnen Zust nde als Werkzeug bezeichnet Das Objekt das diese Werkzeuge verwendet stellt die Grafikoberfl che in diesem Fall eine Ansicht der Topologie dar Diese Oberfl che f ngt Mausbewegungen und eingaben ab und leitet diese an das aktuelle Werkzeug weiter Dieses Werkzeug entscheidet schlie lich wel che nderungen an der Oberfl che vorgenommen werden Abbildung 7 1 zeigt die Struktur des Editors Der Topologieeditor registriert sich als MouseListener und MouseMbotionLis tener Die Events die bei ihm eingehen leitet er an seinen aktuellen Zustand bzw sein aktuelles Werkzeug wei
59. Abschnitt nun belegt ist Ansonsten muss er die Anfrage zun chst puffern 41 public void onReception Request message 42 if getRole ROLE_MASTER 43 if buffer isEmpty amp amp voted false 44 voted true 45 send new Response message getSender 46 47 else 48 buffer add message getSender 49 50 Der Nachrichtentyp Response wird f r zwei Ereignisse verwendet Zum einen sendet der Server einen Response um dem Empf nger mitzuteilen dass dieser den kritischen Abschnitt betreten darf Zum anderen senden die Agenten die den kritischen Abschitt verlassen einen Response an den Server um ihm mitzuteilen dass der kritische Abschitt wieder betreten werden darf 51 public void onReception Response message 52 if getRole ROLE_MASTER 53 if buffer isEmpty 54 voted false 55 56 else 57 Agent agent Agent buffer remove 0 58 if agent this 59 setState STATE_WORKING 60 setTimeout 3 8 2 Koordination und bereinstimmung 118 61 62 else 63 send new Response agent 64 voted true 65 66 67 68 else 69 setState STATE_WORKING 70 setTimeout 3 71 72 Ein Timeout wird dazu verwendet die Zeit zu simulieren die ein Agent im kri tischen Abschnitt verbringt Nach Ablauf des Timeouts kann dieser dann dem Server mitteilen dass er wieder frei ist Falls sich der Server selbst im kriti
60. Agent public static final int MEMBER STATE_WORKING public static final int NO_MEMBER STATE_NORMAL public RingLeaderAgent setDescription RingLeader getID setState NO_MEMBER 10 leader 1 11 1 2 3 4 5 private int leader 6 7 8 9 Bei der Initiierung einer Wahl wird in diesem Fall aber keine einzelne ID sondern eine Liste losgeschickt In dieser wird zun chst nur die Kennung des Initiators eingetragen 12 public void init InitMessage message 13 ArrayList ids new ArrayList 14 ids add new Integer getID 15 send new Request Agent BROADCAST ids 16 setState MEMBER 17 Erh lt ein Agent diese Liste tr gt er seine eigene Kennung ein merkt sich dass er an einer Wahl teilnimmt und sendet die Liste an den Ring weiter Hat der Agent diese Wahl selbst initiiert wertet er die Liste aus indem er das Maximum bestimmt Das Ergebnis sendet er in Form eines Response ber den Ring 18 public void onReception Request message 19 ArrayList ids ArrayList message getPayload 20 if Integer ids get 0 intValue getID 21 setState NO_MEMBER 22 int max getID 23 for Iterator iter ids iterator iter hasNext 24 Integer id Integer iter next 25 max Math max max id intValue 26 27 leader max 28 send new Response BROADCAST new Integer max 29 if max getID 30 setRole Agent ROLE_MAST
61. Agent eine Nachricht k nnte es sein dass er diese unmittelbar wieder weiterleiten m chte W rde an dieser Stelle dieselbe Nachricht und nicht eine Kopie versendet w rde das das ganze System durcheinander bringen denn die Nachricht befindet sich bereits in der Liste der gesendeten Nachrichten Bei einer Weiterleitung w rde sich die gesamte Situation dieser Nachricht Sender Empf nger Sendezeit usw ndern obwohl sie eigentlich unver nderbar in der Liste der bereits gesendeten Nachrichten liegt Aus diesem Grund wird jede Nachricht die von einem Agenten gesendet werden soll zun chst kopiert und dann erst gesendet Eine Besonderheit der Agenten ist der Pseudopolymorphismus der bei den onReception Methoden zum Tragen kommt Polymorphismus bedeutet Viel seitigkeit und bewirkt die Zuweisung unterschiedlicher Klassen zu einem Objekt So kann z B ein Objekt des Typs Fahrzeug den Wert eines Autos oder den eines Fahrrads annehmen Methoden legen mit ihren Parametern ein hnliches Verhal ten an den Tag Urspr nglich wurde damit gerechnet dass der Polymorphismus bei den unterschiedlichen Nachrichtentypen sofort greift der Benutzer f r jeden dieser Typen eine eigene onReception lt NachrichtenTyp gt Methode definieren kann und diese automatisch aufgerufen werden Dadurch dass die Nachrich ten bei der Auslieferung zun chst von der MessageQueue die diese Nachrichten ausliefert auf den einfachen Typ Message gecastet werden werden die
62. Das in dieser Arbeit entstandene Programm nennt sich DisASTer was f r Dis tributed Algorithms Simulation Terrain steht Das Programm besteht aus zwei Teilen 15 einer Klassenbibliothek die Klassen enth lt um verteilte Algorithmen im plementieren zu k nnen Diese Bibliothek ist der eigentliche Baukasten aus dem ein Entwickler Klassen und Methoden verwenden kann um verteilte Algorithmen zu programmieren 2 einem Programm mit einer grafischen Oberfl che in der die mit der Bi bliothek erstellten Algorithmen simuliert visualisiert und getestet werden k nnen 4 2 Eigenschaften verteilter Algorithmen Bevor die Arbeitsweise von DisASTer beschrieben wird werden die Gr nde auf gef hrt die zu der jetzigen Architektur von DisASTer gef hrt haben Ziel der Entwicklung von DisASTer war es m glichst viele verteilte Algorithmen rea lisieren zu k nnen Um diesem Ziel gerecht zu werden wurden zun chst die Eigenschaften zusammengetragen die alle verteilten Algorithmen besitzen Da verteilte Algorithmen in verteilten Systemen wie Netzwerken eingesetzt werden lassen sich schnell einige triviale Eigenschaften festhalten die mit dem Aufbau eines verteilten Systems eng verbunden sind 1 Ein verteiltes System besteht aus mehreren Teilnehmern oder Prozessen die bestimmte Zust nde besitzen oder unterschiedliche Rollen annehmen k nnen 2 Diese Prozesse sind ber Kommunikationskan le miteinander verbunden 3 ber diese Kan le ta
63. Der Befehl der am h ufigsten empfangen wurde wird ausgef hrt Wenn kein Befehl die absolute Mehrheit bekommen hat wird der Standardbefehl 1 zur ckgeliefert 40 public int avg 41 HashMap valueCounter new HashMap 42 for Iterator i commands iterator i hasNext 43 Integer command Integer i next 44 if valueCounter containsKey command 45 valueCounter put command new Integer 0 46 int counter 47 Integer valueCounter get command intValue 48 valueCounter put command new Integer counter 1 49 50 Iterator i valueCounter keySet iterator 51 Integer max Integer i next 52 boolean equal false 53 while i hasNext 54 Integer command Integer i next 55 int commandValue 56 Integer valueCounter get command intValue 57 int maxValue 58 Integer valueCounter get max intValue 59 if commandValue gt maxValue 60 max command 61 equal false 62 63 else if commandValue maxValue 64 equal true 65 66 if equal 67 return 15 68 else 69 return max intValue 70 71 Die Implementierung eines Verr ters sieht dagegen ein wenig einfacher aus 8 2 Koordination und bereinstimmung 133 Hierbei f llt die Liste der Befehle weg da sich ein Verr ter sowieso nicht um das schert was die anderen sagen 1 public class ByzantinicTraitor extends Agent 2 public ByzantinicTraitor 3 if ge
64. ER 31 32 33 else 8 2 Koordination und bereinstimmung 128 34 35 36 37 38 39 40 if getState MEMBER return setState MEMBER ids add new Integer getID send new Request BROADCAST ids Erh lt ein Agent ein Response merkt er sich den neuen Anf hrer und sendet die Nachricht an den Ring weiter Ist er selbst der neue Anf hrer setzt er seine Rolle auf ROLE_MASTER 41 42 43 44 45 46 47 48 49 50 51 52 53 public void onReception Response message int max Integer message getPayload intValue if leader max send new Response BROADCAST message getPayload setState NO_MEMBER if max getID setRole Agent ROLE_MASTER leader max setState NO_MEMBER Dieser Algorithmus sollte wie der im vorangegangenen Beispiel konfiguriert werden Bully Algorithmus Der Bully Algorithmus von Garcia Molina setzt voraus dass alle Prozesse die Kennungen der anderen Prozesse kennen Der Algorith mus arbeitet wie folgt 1 Merkt ein Prozess dass der derzeitige Anf hrer ausgefallen ist startet er eine Wahl sofern er nicht die nunmehr h chste Kennung besitzt Um eine Wahl zu starten werden Wahlnachrichten an alle Prozesse mit einer h heren ID gesendet und auf dessen Antwort gewartet Trifft nach einem Timeout keine Antwort von einem Prozess ein gilt dieser als ausgefallen Beim Eintreffen einer Wahlnachricht initiiert der Em
65. Entwurf und Implementierung eines Bau kastens f r Verteilte Algorithmen Tim Gottwald Diplomarbeit November 2003 Betreuung Prof Dr Rainer Oechsle stonswsen Allntormati Fachbereich Design und Informatik Fachhochschule Trier University of Applied Sciences FACHHOCHSCHULE TRIER UNIVERSITY OF APPLIED SCIENCES Fachbereich DESIGN UND INFORMATIK Autor Tim Gottwald Titel Entwurf und Implementierung eines Baukastens f r Verteilte Algorithmen Studiengang Angewandte Informatik Betreuung Prof Dr Rainer Oechsle November 2003 Es wird hiermit der Fachhochschule Trier University of Applied Sciences die Erlaubnis erteilt die Arbeit zu nicht kommerziellen Zwecken zu verteilen und zu kopieren Unterschrift des Autors Copyright Tim Gottwald 2003 Ein besonderer Dank gilt Prof Dr Rainer Oechsle f r viele wertvolle Hinweise und eine gute Betreuung Meiner Freundin Angela Otting die so tapfer war und diese Arbeit Korrektur gelesen hat und in schwierigen Phasen f r die n tige Aufheiterung sorgte Daniel R der der das Programm einem ersten praktischen Test unterzogen und die Tauglichkeit des Benutzerhandbuchs berpr ft hat Meinem Kommilitonen Ralph Weires mit dessen Hilfe viele Probleme gel st wer den konnten und der mir vor allem im Bereich Software Testen viele n tzliche Tipps geben konnte Den Freunden der Robotik Florian Adolf Bernhard Kloss und Dirk Simon f r Zei
66. Graphics2D gecastet werden protected void paintComponent Graphics g Graphics2D g2 Graphics2D g Grund f r diesen Schritt ist der hohe Funktionsumfang der 2D Graphics API der f r eine ordentliche grafische Darstellung ben tigt wird Hierbei ist vor allem das Antialiasing hervorzuheben das zur Abrundung von Linien verwendet wird Ohne diese Technik w rden Linien wie sie von den Pfeilen der Ablaufansicht oder den Verbindungen der Topologieansicht verwendet werden h ufig eckig erscheinen was in Abbildung 7 2 gezeigt wird Be Abbildung 7 2 Vergleich Kein Antialiasing Antialiasing Diese sauber gezeichneten Linien k nnen mit der 2d Graphics API noch weiter bearbeitet werden was bei den Einstellungen der Verbindungen der Topologie ansicht zum Einsatz kommt Es besteht die M glichkeit die Linien gestrichelt gepunktet dicker oder d nner zu zeichnen Diese Anpassungen erfolgen ber Strokes Objekte die den Verlauf von Linien beschreiben Im folgenden Code wird ein Stroke Object erzeugt mit dem Linien gestrichelt dargestellt werden BasicStroke dashed new BasicStroke 1 0f BasicStroke CAP_BUTT BasicStroke JOIN_ROUND 7 2 Visualisierung und Animation 94 10 0f new float 8 0f 5 0f 0 0f Das dort angegebenene float Feld new float 8 0f 5 0f gibt die einzel nen Segmentabst nde an die im Laufe einer Linie wiederholt werden Dabei wird zwischen sichtbarem Segment und
67. Prinzip ausgeleert Das bedeutet dass die Nachrichten die zuerst in die MessageQueue eingegangen sind auch zuerst ausgeliefert werden Dabei kann der Benutzer zwischen dem synchronen und dem asynchronen automatischen Modus w hlen 1 Im synchronen Modus werden die Nachrichten quasi in Echtzeit ausgelie fert d h dass alle Nachrichten deren Ankunftzeiten mit der aktuellen Zeit bereinstimmen auf einen Schlag aus der MessageQueue entfernt und an ihre Empf nger ausgeliefert werden 4 3 Kontrolle und Steuerung 38 2 Der asynchrone Modus unterteilt einen Zeitpunkt in dem mehrere Nach richten ausgeliefert werden sollen in Zeitschritte Dabei wird in jedem Zeitschritt immer nur eine Nachricht ausgeliefert Die Ankunftzeit bleibt dabei die gleiche um die Konsistenz zwischen dem synchronen und dem asynchronen Modus zu gew hrleisten Dieser Modus dient vor allem der bersichtlichkeit da in vielen F llen die Vorgehensweise eines Algorith mus besser nachvollzogen werden kann wenn er Nachricht f r Nachricht abl uft Die automatische Steuerung verhindert allerdings die Willk r die in verteil ten Systemen auftritt in denen es zu Verz gerungen oder Nachrichtenverlusten kommen kann Um diese St rfaktoren auch in DisASTer einbringen zu k nnen wird eine manuelle Steuerung angeboten die dies erm glicht Um die manuelle Steuerung zu gew hrleisten wird die MessageQueue aufgeteilt F r jeden Agen ten existiert eine separate M
68. Queue keinen Einflu auf die Reihenfolge der Nachrichten in der eigentlichen Messagequeue hat Wird die Nachrichtenreihenfolge im manuellen Modus ge ndert und dann wieder in den automatischen gewech selt l uft die Simulation so ab wie vor der nderung 6 Entwurf 71 6 Entwurf Dieses Kapitel besch ftigt sich mit dem objektorientierten Entwurf der zu er stellenden Anwendung Hierzu wird zun chst eine Analyse verteilter Algorithmen durchgef hrt um deren allgemeine Eigenschaften bestimmen zu k nnen An schlie end wird mit diesem Hintergrundwissen der Entwurf beschrieben der sich in vier Teile untergliedert dem Modell den Ansichten der Kontrollinstanz und der Grafischen Oberfl che 6 1 Eigenschaften verteilter Algorithmen Neben der Recherche anderer Projekte Kapitel 9 und deren Herangehensweise an die vorliegende Problematik wird eine eigene Analyse durchgef hrt bei der die allgemeinen Eigenschaften verteilter Algorithmen untersucht werden Ziel dabei ist es die Eigenschaften zu finden die nahezu alle verteilten Algorithmen in sich vereinen Unter Ber cksichtigung dieser Eigenschaften soll das Programm sp ter in der Lage sein m glichst alle verteilten Algorithmen simulieren zu k nnen Ganz allgemein l sst sich hier festhalten dass verteilte Algorithmen aus meh reren Teilnehmern bestehen Diese besitzen meist einen bestimmten Zustand der z B anzeigt dass sie gerade besch ftigt sind oder sie auf eine Best tig
69. Schritt ben tigt wird ver ndert 5 3 Die Oberfl che 69 Um einen Algorithmus in DisASTer ablaufen zu lassen bestehen drei M g lichkeiten 1 synchronous bedeutet dass alle Nachrichten die zu einem Zeitpunkt ausgeliefert werden sollen auch zeitgleich ausgeliefert werden Diese Ein stellung stellt das normale Verhalten des Algorithmus dar 2 asynchronous bedeutet dass Nachrichten die zum selben Zeitpunkt aus geliefert werden sollen zwar zum selben Zeitpunkt nicht aber im selben Zeitschritt ausgeliefert werden Ein Zeitpunkt kann aus mehreren Zeit schritten bestehen Pro Zeitschritt kann nur eine Nachricht ausgeliefert werden Beim synchronen Ablauf werden alle Zeitschritte parallel ausge f hrt In dieser Einstellung geschieht dies der bersichtlichkeit halber nacheinander F r den Algorithmus selber macht diese Einstellung keinen Unterschied 3 manuell mit dieser Einstellung kann auf Handbetrieb geschaltet werden um den Ablauf des Algorithmus individuell zu bestimmen Das Umschalten zwischen den einzelnen Modi ist jederzeit m glich Das ist von Vorteil wenn der Ablauf eines Algorithmus nur an einer bestimmten Stelle durch ein manuelles Eingreifen ge ndert werden soll Nach diesem Eingriff kann die Simulation wieder automatisch erfolgen In der Regel laufen die Simulationen animiert ab Vor allem bei Verwen dung der Topologieansicht ist dies sinnvoll um die Kommunikation zwischen den einzelnen Pr
70. aber mit Sicherheit im Laufe der Zeit noch einige Optimierungen und Ver nderungen vorgenommen die entweder vom Entwickler selbst oder im Rah men von Projektarbeiten durchgef hrt werden Zu den m glichen nderungen 10 Zusammenfassung und Ausblick 141 geh ren unter anderem die in der Anforderungsanalyse spezifizierten Nice to Haves 1 Exportieren der Visualisierungen als Film z B in Form von avi Dateien Diese Aufgabe wurde bereits untersucht und im Java Media Framework wurde evtl schon eine L sung gefunden 2 Erweitern der Visualisierung um neue Renderer 3 Komplettierung des Index der Online Hilfe 4 Realisierung neuer Algorithmen oder Verbesserung und Erweiterung der bestehenden Beispiele Vor allem aber wird DisASTer einen Platz in der Vorlesung verteilte Systeme bekommen und dort Studenten helfen das Thema verteilte Algorithmen besser zu ben und zu verstehen 16http java sun com products java media jmf Literaturverzeichnis 142 Literaturverzeichnis Coulouris et al 02 G Coulouris J Dollimore T Kindberg 2002 Verteil te Systeme Konzepte und Design Addison Wesley ISBN 3 8273 7088 1 Gamma et al 96 E Gamma R Helm R Johnson J Vlissides 1996 Ent wurfsmuster Addison Wesley ISBN 3 89319 950 0 Lentzsch03 K Lentzsch 2003 Erste Hilfe f r Swing die g bsten Schnitzer in Swing Oberfl chen vermeiden Software amp Support Verlag Java magaz
71. ace ControllerState implementieren Manual dieser Zustand wird angenommen wenn die Simulation vom Be nutzer selbst gesteuert wird Running beschreibt den Zustand wenn die Simulation automatisch ab l uft unabh ngig davon ob dies synchron oder asynchron animiert oder 6 6 Grafische Benutzeroberfl che GUI 87 nicht animiert geschieht Die Geschwindigkeit dieses Ablaufs kann ver n dert werden Paused wird angenommen wenn die Simulation unterbrochen wird Stopped bezeichnet den Zustand der zu Beginn einer jeden Simulation steht Die Arbeitsweise dieser Zust nde wird im Zustandsdiagramm der Abbildung 6 11 sichtbar A Zustandswechsel wird vom Anwender veranlasst Manual Stopped next previous next Abbildung 6 11 Zustandswechsel des Controllers Zus tzlich findet sich nochmals das Entwurfsmuster Observer im Controller wieder Beobachter des Controllers werden bei jedem Zustandswechsel benach richtigt und bekommen den neuen Zustand mitgeteilt Von dieser Technik wird vor allem bei den Kn pfen der GUI Gebrauch gemacht die diese Zustandswech sel hervorrufen sollen denn diese Kn pfe sollen nicht jederzeit bedient werden k nnen So w re es beispielsweise sinnlos den Pausenknopf bet tigen zu k nnen wenn sich der Controller schon im Pausenzustand befindet Um nur eine einzige Kontrollinstanz zu garantieren steht auch der Control ler nur al
72. alit t entwickelt Voraussetzung dieses Algorithmus ist erneut eine eindeutige logische Uhr siehe Abschnitt 3 1 2 Der Algorithmus l uft wie folgt ab Eintrittswunsch ber Multicast an alle anderen Prozesse senden und auf deren Antworten warten Nachdem eine Antwort von jedem anderen Prozess eingetroffen ist kann der kritische Abschnitt betreten werden Beim Eintreffen einer Anfrage zum Eintritt in den kritischen Abschnitt 1 falls selbst kein Eintrittswunsch vorliegt Einverst ndnis zum Eintritt senden 3 3 Koordination und bereinstimmung 18 2 falls selbst Eintrittswunsch vorliegt und Zeitstempel der Anfrage klei ner als der der eigenen Anfrage Einverst ndnis senden Falls der ei gene Eintrittswunsch vor der empfangenen Anfrage erfolgte wird die Anfrage gepuffert 3 falls selbst im kritischen Abschnitt Anfragen puffern und nach Aus tritt Einverst ndnisse aller gepufferter Anfragen senden Abbildung 3 6 zeigt einen Ablauf des wechselseitigen Auschlusses nach Ricart und Agrawala Bei diesem Beispiel liegt ein verteiltes System mit vier Prozessen P mit i 1 4 vor Prozess P und P u ern ihren Eintrittswunsch ber Multicast bei allen anderen Prozessen Dadurch dass der Eintrittswunsch von P durch die eindeutige logische Uhr hier 1 1 vor der von P 1 4 eingetreten ist L 1 1 lt L 1 4 muss P zun chst P den Vorrang lassen P P P P4 RN 2 2 1 4 41 a2 5 3
73. andere wurden gar nicht mehr angeboten und wieder andere sind nicht frei erh ltlich Zu letzteren geh rt LEDA welches in nahezu jedem Projekt ein gesetzt wurde Die meisten Programme waren zudem ausschlie lich f r Linux 9 2 Zusammenfassung und Vergleich 138 erh ltlich Das setzt zum einen ein solches Betriebssystem voraus zum anderen sind hier oft unz hlige Konfigurationen und Installationen notwendig um das Programm berhaupt zum Laufen zu bringen Alle diese Stolpersteine haben da zu gef hrt dass viele der vorgestellten Projekte keinem Praxistest unterzogen werden konnten Keine Regel ohne Ausnahme Diese wurde in DAJ und ViSiDiA gefunden Beide Projekte sind in Java realisiert und sind somit plattformunab h ngig Die Installation und das Ausf hren dieser Programme ist auch einfach und schnell durchf hrbar Bei beiden gen gt es ein Zip Archiv zu entpacken Das Starten von DAJ geschieht ber einen Doppelklick auf die gelieferte Jar Datei Bei ViSiDiA gen gt das Aufrufen eines Shell Skripts Ein weiterer Vergleichspunkt ist die Art wie der Anwender verteilte Algorith men mit den einzelnen Projekten erzeugen kann Bei einigen kann der Anwen der auf eine bekannte Sprache wie C C oder Java zur ckgreifen in der er schon Programmiererfahrung sammeln konnte und f r die er seine favorisierte Programmierumgebung verwenden kann Andere wiederum verwenden eine ei gene Beschreibungs oder Skriptsprache mit der sich der Benut
74. ar In DisASTer sind bereits zwei Ansichten integriert die diese Aufgabe berneh men Es handelt sich hierbei zum einen um die Ablaufansicht SequenceView siehe Abbildung 5 3 die den zeitlichen Ablauf eines Algorithmus in Form ei nes Sequenzdiagramms visualisiert Es wird gezeigt wann eine Nachricht von wem gesendet wurde und wann diese bei welchem Empf nger angekommen ist Zus tzlich werden Rolle und Status jedes Agenten durch verschiedene Darstel lungen und Farben hervorgehoben Ebenso kann der Nachrichtentyp durch eine bestimmte Farbgebung hervorgehoben werden x Sequenceview Zoom Abbildung 5 3 Ablaufansicht Die Topologieansicht TopologyView Abbildung 5 4 ist die zweite Ansicht die zur Verf gung steht Sie geht auf die Verbindungen der einzelnen Agenten untereinander ein und zeigt die Nachrichten an die gerade ber die Leitungen laufen Aus diesem Grund ist anzuraten die Simulation animiert ablaufen zu lassen wenn die Topologieansicht verwendet wird Wie auch in der Ablaufan sicht k nnen sowohl Status und Rolle der Agenten als auch der Nachrichtentyp durch unterschiedliche Darstellungen hervorgehoben werden Zus tzlich kann das Aussehen der einzelnen Verbindungen ge ndert werden Bei allen Ansichten sind noch weitere n tzliche Zusatzfunktionen integriert Mit Hilfe eines Schiebereglers kann die Ansicht vergr ert oder verkleinert wer den Die Ansicht selbs
75. ceiver Message Messagetype 4 5 RingLeader 0 RingLeader 1 3 4 5 0 1 2 Request 5 6 RingLeader 4 RingLeader 5 0 1 2 3 4 5 Request 5 6 RingLeader 1 RingLeader 2 3 4 5 0 1 2 Request 6 7 RingLeader 5 RingLeader 0 0 1 2 3 4 5 Request 6 7 RingLeader 2 RingLeader 3 3 4 5 0 1 2 Request 7 8 RingLeader 0 RingLeader 1 disaster example Response 7 8 RingLeader 3 RingLeader 4 disaster example Response 8 9 RingLeader 1 RingLeader 2 disaster example Response 8 9 RingLeader 4 RingLeader 5 disaster example Response E Rinnl eade Rinal eade disaster examnle Abbildung 5 6 Gesendete Nachrichten Die einzelnen Nachrichten werden in einer Tabelle zusammengefasst die an zeigt wann die Nachrichten gesendet und empfangen wurden wer der Sender und wer der Empf nger war welches Objekt mit dieser Nachricht verschickt wurde und welchem Typ die Nachricht zugeordnet werden konnte MessageQueue Nachrichten die zwar gesendet jedoch noch nicht ausgelie fert wurden finden sich in der MessageQueue Abbildung 5 7 wieder 5 3 Die Oberfl che 58 MessageQueue sent Sender Receiver Message Messagetype 4 Routeri Router3 Ljava lang Objec Message 4 Router Router Ljava lang Objec Message 4 Router3 Router Ljava lang Objec Message 4 Router3 Router4 Ljava lang Objec Message 4 Router3 Routeri Ljava lang Objec Message 4 Router2 RouterO Ljava lang Objec Message 4 Router Router
76. chrichten an andere Knoten zu senden um einen Algorithmus zu durchlaufen Das macht DAJ zu einem nachrichtengesteuerten System vgl Schreiner98 ViSiDiA ViSiDiA ist ein Werkzeug zur Implementierung Simulation Visuali sierung und zum Testen von verteilten Algorithmen Das Programm ist in und f r Java geschrieben Es untergliedert sich in zwei Teile 1 einem Grapheditor in dem die einzelnen Prozesse angeordnet und deren Verbindung gelegt werden 2 einer Simulationsumgebung in der unterschiedliche Algorithmen f r die an gelegte Topologie ausgew hlt und simuliert werden k nnen Dabei helfen Funktionen wie Start Stopp Pause oder Reset Die Simulationsgeschwin digkeit kann ebenfalls bestimmt werden und einige Informationsfenster ge ben einen zus tzlichen berblick ber den Zustand des Systems und der Umgebung so z B ein Thread Z hler Das Programm verwendet Threads f r die Realisierung der einzelnen Prozesse vgl Bauderon et al 03 9 2 Zusammenfassung und Vergleich Nach der Untersuchung der einzelnen Projekte werden im folgenden deren Ei genschaften er rtert welche Vor und Nachteile sie haben und welche Gemein samkeiten zwischen den einzelnen Projekten existieren Ein gro er Nachteil vieler oben vorgestellter Programme ist dass sie auf Bi bliotheken von Drittanbietern zur ckgreifen oder diese erweitern Gerade dieser Punkt hat den Einsatz dieser Projekte erschwert Bei einigen gab es Versionspro bleme
77. chrichten gel scht werden oder deren Reihenfolge durchein andergebracht wird Gesendete Nachrichten werden aber nicht aus dem System entfernt sondern finden sich in einer gesonderten Liste die das Environment selbst verwaltet wieder Abbildung 6 5 zeigt den Aufbau der MessageQueue Systemklasse Vom Benutzer erweiterbar MessageQueue AgentMessageQueues 0 1 Object from java lang payload Message Sender sentTime int receptionTime int lt gt lt gt Agent InitMessage TimeoutMessage Request Response Abbildung 6 5 Aufbau der MessageQueue In der Abbildung wird ebenfalls der Aufbau einzelner Nachrichten ersichtlich Diese setzen sich aus folgenden Elementen zusammen 6 3 Model 78 sentTime legt fest an welchem Zeitpunkt die Nachricht gesendet wurde receptionTime hat zwei Aufgaben Nachdem die Nachricht beim Emp f nger angekommen ist zeigt dieser Wert den Zeitpunkt des Eintreffens an Bevor die Nachricht jedoch die MessageQueue verl sst findet sich hier die Zeit zu der die Nachricht ausgeliefert werden soll Wenn dieser Wert ber dem aktuellen Zeitpunkt liegt bleibt die Nachricht zun chst in der Mes sageQueue liegen bis dieser Zeitpunkt erreicht ist Auf diesem Weg ist es m glich Nachrichten mit einer bestimmten Zeitverz gerung auszuliefern payload repr sentiert die eigen
78. chwort trifft auch nur bedingt auf das Thema verteilte Algorithmen zu Um diese darzustel len werden h ufig Sequenzdiagramme verwendet Bei Algorithmen bei denen ein hoher Nachrichtenaustausch n tig ist nehmen diese Diagramme aber betr cht liche Ausma e an und f hren h ufig dazu den Betrachter zun chst einmal zu erschlagen Diese Arbeit soll helfen den Benutzer f r das Thema verteilte Algorithmen zu sensibilisieren die Darstellung zu verbessern und vor allem praktische bungen zu erleichtern Um diesem Ziel gerecht zu werden soll eine Java Bibliothek ent worfen werden mit deren Hilfe das Erzeugen verteilter Algorithmen zu bungs zwecken kein Problem mehr darstellt Daneben soll ein Programm entwickelt werden dass diese Algorithmen ausf hren und in einer bersichtlichen Form vi sualisieren kann Die Arbeitsweise soll der eines Baukasten entsprechen wobei der Nutzer der Bibliothek und des Programms eine Auswahl aus Klassen und Me thoden erh lt mit denen er einen verteilten Algorithmus implementieren kann Die Bibliothek sollte folgenden Anforderungen gerecht werden Die angebotenen Klassen und deren Methoden sollten schnell verstanden und leicht eingesetzt werden k nnen Dadurch soll dem Anwender eine lange Einarbeitungszeit erspart bleiben die ihm dann zur Entwicklung der Algorithmen zur Verf gung steht Um das Programm auch in Gebieten einzusetzen an die zur Zeit noch nicht gedacht wird sollte es ei
79. d in der Regel wie ein Film erzeugt bei dem in einer bestimmten Zeit mehrere Bilder hintereinander angezeigt werden wodurch dem Betrachter eine Bewegung vorget uscht wird Diese Methode wird bei den Ansichten ebenfalls verwendet 6 5 Controller 85 public void paintComponent JComponent for Iterator i renderer iterator i hasNext from javax swing PreferencesPane Systemklasse Renderer renderer Renderer i next renderer draw g progress q o Vom Benutzer h erweiterbar j N T 1 i View N Renderer 1 1 KO 1 I addRenderer renderer Renderer boolean draw g Graphics progress double void removeRenderer renderer Renderer boolean AEI paintComponent g Graphics void TopologyView SequenceView AgentRendererComposite z AgentRenderer Agent L m gt Abbildung 6 9 Aufbau der Ansicht Aus diesem Grund besitzt die Zeichenmethode der Renderer einen Parameter der den prozentualen Fortschritt eines solchen Animationsschritts angibt Die ser Parameter besitzt einen Wert von 0 0 f r 0 bis 1 0 f r 100 Falls der Anwender auf Animationen verzichten will z B aus Effizienzgr nden betr gt dieser Wert immer 1 0 um den finalen Zustand der Animation darzustellen Ein Renderer ist falls er nur f r eine statische Darstellung verantwortl
80. den Token besitzt bekommt die Rolle ROLE_MASTER Zu Begin des Algorithmus erh lt der erste Agent mit der ID 0 das Token Damit die Agenten wissen ob eine Anfrage besteht und sie bei Erhalt des Token diesen wieder weitersenden k nnen bekommt jeder Agent eine boolsche Variable die diesen Zustand beschreibt setRole ROLE_MASTER public class RingExclusionAgent extends Agent 2 private boolean gotRequest 3 4 public RingExclusionAgent 5 description RingExcl Agent getID 6 if getID 0 7 8 Der Wunsch den kritischen Abschnitt zu betreten wird durch die Initialisierung ausgel st Besitzt der initialisierte Agent bereits das Token kann er den kritischen Abschnitt betreten Andernfalls sendet er eine Anfrage ber den Ring 9 public void init InitMessage message 10 if getRole ROLE_MASTER 11 setState STATE_WAITING 12 sendToAll new Request 13 14 else 15 setState STATE_WORKING 16 setTimeout 3 17 18 Trifft eine Anfrage bei einem Agenten ein der den Token selbst nicht besitzt leitet er die Anfrage an den Ring weiter H lt er sich selbst im kritischen Abschnitt auf merkt er sich dass eine Anfrage gestellt wurde Besitzt der Agent das Token ohne selbst einen Abschnittswunsch zu haben sendet er es in Form einer Antwort Response weiter 19 public void onReception Request message 20 if getState STATE_WORKING amp amp getRo
81. der einfachen Form vgl Coulouris et al 02 S 513ff P P2 P3 P P P3 P Pi P3 T Le i Te Lo E Totale FIFO Kausale Reihenfolge Reihenfolge Reihenfolge Abbildung 3 11 Totale FIFO und kausale Reihenfolge Im Folgenden werden einige L sungen f r die einzelnen Formen vorgestellt 3 3 Koordination und bereinstimmung 26 Totale Reihenfolge mit Prim rempf nger Die einfachste Methode eine to tale Reihenfolge zu gewinnen ist einen Prim rempf nger zu bestimmen der alle Nachrichten abf ngt und an die anderen Prozesse weiterleitet Der Prim rempf n ger k nnte vorher aus den Prozessen gew hlt worden sein siehe Abschnitt 3 3 2 Einzige Voraussetzung dieses Algorithmus ist dass die Kommunikationskan le vom Prim rempf nger zu den anderen Prozessen FIFO sind Abbildung 3 12 zeigt den Ablauf dieses Verfahrens P P2 P3 Prim rempf nger ee es Abbildung 3 12 Totale Reihenfolge durch Prim rempf nger Nachteil dieser Methode ist nat rlich die Abh ngigkeit von einer zentralen Komponente und ein m glicher Nachrichtenverlust bei deren Ausfall sowie die Verz gerungszeit die durch den Umweg ber den Prim rempf nger auftritt vgl Oechsle02 S 20 Totale Reihenfolge mit Sequenzer Eine Variante des Verfahrens mit Pri m rempf nger ist die mit dem Einsatz eines sogenannten Sequenzers Dieser kann ebenfalls aus den Pro
82. deren Anwendungen bekannte Men strukturen und Elemente wieder wodurch eine schnelle und intuitive Benutzung gew hrleistet werden soll http www incors org http www jgoodies com http developer java sun com developer techDocs hi repository 9http dev eclipse org viewevs index cgi org eclipse jdt debug ui icons 7 6 Speichern von Umgebungszust nden 100 7 6 Speichern von Umgebungszust nden Der Verlauf der Simulation siehe Kapitel 6 Seite 84 ist eine gro e Navigati onshilfe f r den Benutzer Mit ihm hat der er die M glichkeit die Simulation zur ck zu spulen um den Algorithmus entweder erneut oder unter ver nder ten Bedingungen ablaufen zu lassen Um dies zu gew hrleisten speichert der Verlauf die einzelnen Zust nde der Umgebung ab Dies geschieht ber Seriali sierung eines Objekts der Klasse EnvironmentState Dieses serialisierte Objekt wird allerdings zun chst nicht wie blich in eine Datei geschrieben oder ber ein Netzwerk geleitet sondern es soll in die Liste des Verlaufs aufgenommen werden Ein solches serialisiertes Objekt zu erhalten ist zun chst nicht ganz einfach denn es wird in einen Strom ObjectOutputStream geschrieben Um nun dieses Ob jekt aus diesem Strom wieder herauszulesen ohne den Umweg ber eine Datei zu machen werden die Klassen PipedInputStream und PipedOutputStream ver wendet Objekte dieser beiden Klassen werden miteinander verbunden wodurch es m glich ist den Inha
83. derer class MoveAgentDownAction class MoveAgentUpAction class PasteAgentAction class ReceptionTimePane class RemoveAgentsAction class RemoveInitMessageAction class BackButton class BackButtonAction class ListMouseHandler class ListMouseMotionHandler class ConsoleInfoPane class ControlPane class DefaultInfoFrameAction class A Klassen bersicht 146 Desktop class InfoFrame class InfoFrameGroup class OpenAllInfoFramesAction class MainFrame class Menubar class MessageQueuelnfoFrame class m AgentComponentAction class AgentMessageQueueCellRenderer class MessageQueuelnfoFrameAction class PreferencesPane class SentMessagesInfoFrame class SentMessagesInfoFrameAction class Splashscreen class Closer class SplashDialog class SplashWindow class StatusBar class ToolBar class TopologyEditor class ConnectChosenTool class ConnectTool class A DisconnectTool class MoveTool class Tool class TopologyPane class A Klassen bersicht le J AddTopologyManagerAction class ConnectChosenToolAction class ConnectToolAction class DisconnectToolAction class DoPositionAction class m MoveToolAction class RemoveAllConnectionsAction class e ViewInfoFrame class ScreenshotAction class e ViewPreferences class AddRendererAction class AddViewAction class MoveDownAction class MoveUpAction class
84. dert werden Die Integration eigener Ansichten oder eigener Renderer erfolgt im laufenden Programm Abschnitt 5 3 3 Seite 64 5 3 Die Oberfl che Dieser Abschnitt besch ftigt sich mit der grafischen Oberfl che von DiSASTer Diese setzt sich aus Informationsfenstern zusammen die Aufschluss ber den Zustand des Systems geben oder die Visualisierung anzeigen aus den Ober fl chenelementen die den Ablauf eines Algorithmus erm glichen und diversen Einstellungsdialogen mit denen die Umgebung oder die Visualisierung angepasst werden kann 5 3 1 Dateioperationen Die Dateioperationen finden sich in dieser Form in nahezu allen g ngigen Pro grammen unter dem Men punkt Datei bzw File wieder Abbildung 5 1 Zu den Dateioperationen z hlen F New ein neues verteiltes System wird erzeugt Bei Aufruf dieses Men ein trags wird der Einstellungsdialog Abschnitt 5 3 3 gezeigt ber den das System in der ein Algorithmus agiert konfiguriert wird 5 Open bereits gespeicherte Algorithmen sogenannte DisAS Ter Stored Environments k nnen mit diesem Befehl geladen werden Save mit diesem Men eintrag wird das aktuelle System als DisASTer Stored Environment gespeichert Dabei werden die wichtigsten Objekte 5 3 Die Oberfl che 53 Eie view Options Help B New Strg N Open Strg O B amp Exit Abbildung 5 1 Dateioperationen des Systems serialisiert Darunter fallen die Topolog
85. die bereits bestehenden 5 3 Die Oberfl che 65 Renderer zu bearbeiten und dabei ihr Aussehen zu ver ndern Hierbei handelt es sich zwar oft nur um kleinere Einstellungen wie Farbe oder Form aber genau diese nderungen machen schon viel aus Diese Einstellungen werden beim Ausw hlen eines Renderers sichtbar sofern dieser die M glichkeit bietet Die Einstellm g lichkeiten der bereits vorhandenen Renderer werden in den folgenden Abschnitten beschrieben Zun chst werden die Renderer vorgestellt die f r das Zeichnen der Agenten zust ndig sind Diese bestehen sowohl in der Topologie als auch in der Ablau fansicht aus einer Liste von weiteren Renderern und zwar f r jeden Agenten einer Abbildung 5 15 zeigt eine Tabelle die zum einen die einzelnen Agenten des System und zum anderen den f r diesen Agenten verwendeten Renderer Es Agent Renderer MutEx Agent 0 Default gentRenderer M MutEx Agent 1 Test gentRenderer MutEx Agent 2 Default gentRenderer M MutEx Agent 3 Default gentRender E Abbildung 5 15 Renderereinstellungen Agentenliste besteht die M glichkeit den Renderer eines speziellen Agenten auszutauschen indem eine neue Klasse ausgew hlt wird die diese Aufgabe bernimmt Nach Auswahl einer Zeile wird ein Knopf sichtbar mit beschriftet der eine Da teiauswahl aufruft ber diese wird die Klasse des neuen Renderers ausgew hlt Ein Doppelklick auf eine Zeile
86. dung 5 14 zeigt die Oberfl che die das Bearbeiten der Ansichten erm g licht und die die Befehle beinhaltet die f r diesen Zweck zur Verf gung stehen 5 3 Die Oberfl che 64 lt lt Sequenceview b SequenceViewClockRend SequenceviewMessageR Sequenceview gentRen Abbildung 5 14 Einstellungen View Add View f gt dem System eine neue Ansicht hinzu Hierzu wird eine Klasse ausgew hlt die die Klasse View erweitert Genaueres ber das Erstellen eigener Ansichten ist in Abschnitt 5 2 4 zu lesen Remove View entfernt die gerade ausgew hlte Ansicht Add Renderer erweitert die aktuelle Ansicht um eine Instanz der aus gew hlten Renderer Klasse Remove Renderer entfernt die ausgew hlten Renderer A Up setzt den ausgew hlten Renderer eine Position in der Liste nach oben Down setzt den ausgew hlten Renderer eine Position nach unten Beim Erreichen der Listengrenzen wird der Renderer einfach am anderen Ende angeh ngt Die Reihenfolge der Renderer in dieser Liste bestimmt auch die Reihenfolge in der die Renderer ausgef hrt werden Dies ist nicht un wichtig da ein Renderer Teile des vor ihm agierenden Renderers bermalen kann Eigene Renderer zu implementieren ist mit unter sehr zeitaufw ndig beson ders wenn hierbei nur kleine Anderungen an der Darstellung vorgenommen wer den sollen Aus diesem Grund gibt es die M glichkeit
87. e mit Vektoruhren Die Nebenl ufigkeit zweier Ereignisse e und e ist dann gegeben wenn weder V e lt V e noch V e lt V e gilt Nachteil dieser Methode ist die hohe Speichernutzung da f r jeden Prozess pi ein Eintrag in jedem Vektorzeitstempel vorhanden sein muss vgl Coulouris et al 02 S 464ff 3 2 Globale Zust nde Ein Prozess p besitzt zu einem bestimmten Zeitpunkt t einen eindeutigen rekon strulerbaren Zustand Dieser kann in einem Verlauf festgehalten werden und ist somit jederzeit wieder abrufbar Einen globalen Zustand eines verteilten Systems festzulegen ist hingegen nicht so einfach Durch die Schwierigkeit der Zeitsyn chronisierung der einzelnen Prozesse kann kein fester Zeitpunkt bestimmt werden an dem ein solcher Zustand aufgenommen werden kann Ein anderes Problem ist dass eine Nachricht die zwischen zwei Prozessen ausgetauscht wird zu dem Zeit punkt der Zustandsaufnahme zwar schon gesendet jedoch noch nicht empfangen wurde Der Inhalt dieser Nachricht w re bei der Rekonstruktion des Zustands ver loren Es ist allerdings m glich unter Einbeziehung der Kommunikationskan le und der lokalen Zust nde der einzelnen Prozesse einen globalen Zustand herzu stellen Aufgaben die mit Hilfe globaler Zust nde gel st werden k nnen sind Verteilte Abfallsammlung Distributed Garbage Collection Freigabe des 3 2 Globale Zust nde 14 Speichers eines Objekts von dem kein Verweis mehr in ei
88. ei teres Eingreifen in den Algorithmus nicht mehr von Interesse Die einzige Aufgabe einer Verbindung besteht darin festzulegen welche Agenten sich untereinander Nachrichten senden k nnen Eigene Topologiemanager haben schon eher einen Einfluss auf den aktuellen Algorithmus Sie bekommen eine Referenz auf die von der Umgebung verwendeteten Topologie disaster model Topology die alle Agenten und deren Verbindungen beinhaltet ber diese Topologie kann der Ma nager in den Methoden doConnections und doPositions die Verbindungen und die Positionen der einzelnen Agenten bestimmen Diese Methoden k nnen vom Entwickler eines neuen Topologiemanagers berschrieben werden Das Ein binden eigener Verbindungen oder Topologiemanager in das Programm wird in Abschnitt 5 3 3 beschrieben 5 2 4 Verwendung und Implementierung von Ansichten Die Hauptaufgabe von DisASTer ist die grafische Darstellung von verteilten Al gorithmen Diese Aufgabe wird von den Ansichten bernommen Eine Ansicht disaster view View ist eine Swing Komponente JComponent die auf meh rere Objekte Zugriff hat welche die unterschiedlichsten Elemente einer Simulati on auf diese Komponente zeichnen Ein solches Zeichenobjekt wird als Renderer 5 2 Die Bibliothek 50 disaster view Renderer bezeichnet Elemente die von einem solchen Rende rer gezeichnet werden k nnen sind z B Agenten Nachrichten oder Verbindungen Die Arbeitsweise der Ansichten und der Renderer wu
89. ei Zaroliagis ns IOA DSP YACSIM und SimUTC vorgestellt vgl Zaroliagis02 Seite 3ff Mit Lydian und DAJ wur den noch zwei weitere davon unabh ngige Projekte untersucht In den folgenden Abschnitten werden diese Programme kurz vorgestellt um sp ter ihre Vor und Nachteile zu diskutieren ns Network Simulator ns was f r Network Simulator steht beschr nkt sich auf die Simulation von Netzwerkprotokollen wie TCP um Probleme wie Routing oder Multicast zu simulieren und zu testen Zudem k nnen kabellose Netzwerke wireless network simuliert werden sei es lokal oder ber Satellit Um ein solches Netzwerk f r ns zu erzeugen muss eine eigene Skriptsprache verwendet werden Bei dieser Scriptsprache handelt es sich um OTcl eine objektorientierte Erweiterung der im MIT entwickelten Tcl Animation und Simulation verlaufen bei ns nicht zeitgleich Zun chst wird die Simulation durchgef hrt und dabei eine Log Datei erstellt Die in dieser Datei eingetragenen Ereignisse werden dann in der Animation verwendet und dargestellt vgl auch McCanne Floyd 03 IOA I O Automata IOA stellt eine formale Sprache dar mit der verteil te Systeme oder Algorithmen modelliert werden k nnen Mit dem OA Toolkit werden Programme zur Simulation zur Verifikation und zum Testen ausgeliefert Zus tzlich kann Java Code erzeugt werden um die beschriebenen Systeme und 9 1 Vorstellung der Projekte 136 Algorithmen in einem realen Netzwerk einzusetzen
90. eilung mit Ant Das Programm wird in zwei unterschiedlichen Versionen ausgeliefert siehe Ab schnitt 5 1 1 Um beide Versionen mit den n tigen Dateien auszustatten wurde Ant verwendet Bei Ant handelt es sich um ein Java basiertes build Werkzeug Es hnelt ein wenig dem aus der Unix Linux Welt bekannten Make Die Entwick ler von Ant wollten mit ihrem Projekt vor allem die Schwierigkeiten beheben die Make mit sich bringt Neben einer plattformunabh ngigen L sung wollten sie vor allem eine einfache Syntax anbieten die bei Make nicht gegeben ist Beides l sst sich durch das Dreamteam Java und XML l sen Java als plattformunabh n gige Programmiersprache und XML als plattform bergreifendes Dateiformat Die Entscheidung Ant zu verwenden l sst sich durch zwei Gr nden belegen zum einen wurde DisASTer unter Eclipse entwickelt das eine sehr gute Integra tion von Ant besitzt und zum anderen hat sich Ant in der Java Welt mittlerweile als Quasistandard durchgesetzt und wird von vielen Entwicklern eingesetzt Ant arbeitet mit den sogenannten build Dateien die im XML Format vorlie gen In einer solchen build Datei werden Befehle aufgelistet die das Programm dann beim Aufruf ausf hrt Ein Befehl wird in Ant auch als Task bezeichnet Gerade f r die Javaentwicklung stellt Ant eine Reihe n tzlicher Tasks zur Verf gung So gibt es beispielsweise Tasks zum Kompilieren javac zum Ausf hren java zum Archivieren jar oder zum E
91. eine Initialisierung kann er den Sender der Nachricht aus der Liste der ausgefallenen Prozesse streichen 43 public void onReception Response message 44 corrupted remove message getSender 45 Empf ngt ein Agent eine einfache Nachricht wei er dass der neue Anf hrer der Sender dieser Nachricht ist 46 public void onReception Message message 47 leader message getSender 48 setState STATE_NORMAL 49 setRole ROLE_SLAVE 50 F r jede gesendete Initialisierung eines Agenten mit h herer Kennung l uft ein Timeout Inhalt des Timeouts ist die Referenz auf den Agenten der in einer bestimmten Zeit eine Antwort senden muss um nicht als ausgefallen zu gelten Sind alle Timeouts abgelaufen hat inits den Wert 0 Befinden sich zus tzlich noch Agenten in der Liste der Ausgefallenen ist dieser Agent der neue Anf hrer und teilt dies den anderen Agenten mit 51 public void timeout TimeoutMessage timeout 52 if getState STATE_NORMAL 53 return 54 55 inits 56 if inits 0 amp amp corrupted size gt 0 57 setRole ROLE_MASTER 58 leader this 59 sendToAll new Message null leader 60 61 62 Dieser Algorithmus ben tigt die CompleteTopology Um den Algorithmus interessanter zu gestalten und evtl einige Ausf lle zu simulieren k nnte die Konstante TIMEOUT erniedrigt oder Nachrichten w hrend des Ablaufs gel scht werden 8 2 Koo
92. einer Liste m glicher Werte d V1 Vm vor Am Ende des Verfahrens haben sich alle korrekt arbeitenden Prozesse auf den selben Wert V geeinigt Wenn alle Prozesse denselben Wert vorgeschlagen haben m ssen sie sich auch auf diesen geeinigt haben interaktiver Konsens Der interaktive Konsens ist eine Erweiterung des Kon sens Problems Wie vorher auch schl gt jeder Prozess p einen Wert d aus einer Reihe m glicher Werte vor Die einzelnen Vorschl ge jedes Prozesses werden jeweils in einem Vektor D aufgenommen Ziel des Verfahrens ist es dass alle korrekt arbeitenden Prozesse auch denselben Entscheidungsvektor besitzen Daraus folgt dass wenn ein korrekter Prozess p einen Wert d vorschl gt so befindet sich dieser Wert im Vektor aller korrekten Prozesse Vil d 3 3 Koordination und bereinstimmung 31 byzantinische Gener le Das Problem der byzantinischen Gener le wird durch ein Szenario beschrieben in welchem es mehrere Gener le und einen be fehlshabenden Kommandeur gibt Dieser erteilt allen Gener len entweder den Befehl Angriff oder R ckzug Die Gener le m ssen sich nun auf einen dieser beiden Befehle einigen Dabei soll ber cksichtigt werden dass es Gener le gibt die sich dem Kommandeur gegen ber nicht loyal verhal ten und vorgeben sie h tten einen anderen Befehl erhalten Es k nnte aber auch der Fall sein dass der Kommandeur sich als nicht loyal entpuppt und den einzelnen Gener len
93. eits bestehenden angeh ngt Somit werden durch die Agentenkonsole ebenfalls doppelte Ausgaben verhindert Die Farbgebung der unterschiedlichen Agenten und die Abh ngigkeit zum aktuellen Zeitpunkt tragen damit vornehmlich zur bersichtlichkeit bei SentMessages Die Ansichten sind wichtige Informationsquellen um zu erfah ren was w hrend dem Ablauf des Algorithmus vor sich geht Neben der grafischen 5 3 Die Oberfl che 57 E AgentConsole MutEx Agent 0 MutEx Agent 0 MutEx Agent 0 MutEx Agent 5 MutEx Agent 1 MutEx Agent 4 got response of MutEx Agent 2 at 60 entering critical section at 60 got request of MutEx Agent 3 at 70 got request of MutEx Agent 3 at 25 got request of MutEx Agent 3 at 21 got request of MutEx Agent 3 at 24 MutEx Agent 2 MutEx Agent 3 MutEx Agent 3 MutEx Agent 3 MutEx Agent 3 got request of MutEx Agent 3 at 22 got response of MutEx Agent 5 at 33 got response of MutEx gent 1 at 43 got response of MutEx Agent 4 at 53 got response of MutEx Agent 2 at 63 Bl MutEx Agent 0 leaving critical section v Abbildung 5 5 Agentenkonsole ist aber auch die rein textuelle Darstellung wichtig Zus tzlich zur Agentenkonso le in der textuelle Informationen der Agenten ausgegeben werden k nnen steht eine textuelle Auff hrung der bereits ausgelieferten Nachrichten zur Verf gung Abbildung 5 6 SentMessages sent Sender Re
94. ellungsformen Ansichten angeboten 1 _ SequenceView zeigt den Algorithmus in einem Sequenzdiagramm an 2 TopologyView stellt die Topologie des Systems grafisch in Form eines Graphen dar Die Ansichten verwalten eine Reihe von Renderern die zur Darstellung unter schiedlicher Elemente der Umgebung z B Agenten Verbindungen oder Nach richten verantwortlich sind Abbildung 4 4 zeigt die Zusammenarbeit der Topo logieansicht und ihrer Renderer Renderer f r Agenten Renderer f r Verbindungen Renderer f r Nachrichten Abbildung 4 4 Ansicht und Renderer Die bereits bestehenden Ansichten k nnen vom Benutzer angepasst oder er weitert werden Sollten die angebotenen Ansichten nicht ausreichen besteht zu s tzlich die M glichkeit eigene Ansichten zu implementieren 5 Benutzung des Programmes 40 5 Benutzung des Programmes 5 1 Inhalt und Installation 5 1 1 Inhalt DisASTer wird in zwei Versionen ausgeliefert Zum einen die Quellcode Variante src in der alle wichtigen Dateien enthalten sind um das Programm neu zu er zeugen Alternativ dazu kann die bereits fertig entfaltete Version bin verwendet werden Die Versionen finden sich in zwei unterschiedlichen Zip Archiven 1 disaster src zip beinhaltet die Quellcode Variante und hat eine Gr e von ca 1 2 MB 2 disaster bin zip beinhaltet alle f r den Programmablauf ben tigten Dateien und
95. elten position beschreibt die Position des Agenten in seiner Topologie id ist ein eindeutiger Zahlenwert der als Unterscheidungskriterium ver wendet wird Besonders wenn f r einen Algorithmus nur ein einziger Agen tentyp verwendet wird ist die ID der einzige Unterschied zwischen den Agenten Zudem kann mit den IDs eine Hierarchie unter den Agenten er zeugt werden wobei z B eine niedrigere ID hierarchisch unter einer h heren steht connections beinhaltet alle Verbindungen zu anderen Teilnehmern Hier f r wird eine Hashtabelle verwendet in der die Verbindung zu einem Agen ten mit ihm als Schl ssel gespeichert wird Dadurch wird zus tzlich verhin dert dass ein Agent mehrere Verbindungen zu einem anderen aufnehmen kann agentComponent Swingkomponente durch die der Anwender grafische Informationen und zus tzliche Befehle zu seinen Agenten hinzuf gen kann 6 3 Model 80 description stellt eine einfache textuelle Beschreibung des jeweiligen Agenten dar Zu allen aufgef hrten Eigenschaften gibt es entsprechende Zugriffsmethoden getXXXO setXXX um mit diesen Werten auch au erhalb der Klasse Agent arbeiten zu k nnen Daneben finden sich noch eine Reihe weiterer n tzlicher Me thoden die im Folgenden aufgef hrt werden Um die Nachrichtensteuerung zu verwenden bietet die Klasse Agent einige Methoden zum Senden von Nachrich ten send Message message sendet die bergebene Nachr
96. en Das Bereitstellen einer solchen Komponente ist zudem nicht zwingend notwendig Sollten die vorhanden Ansichten und die M glichkeit eigene Renderer in die se Ansichten zu integrieren noch nicht ausreichen k nnen ohne weiteres eigene Ansichten entwickelt und zu den bereits bestehenden hinzugef gt werden Mit dieser Strategie k nnen direkt viele eigene Renderer die in einer neuen Ansicht liegen ber diese eingebunden werden Ein solcher Schritt erspart ein erneutes Anpassen der bestehenden Ansichten nach jedem Programmstart Durch das Ab leiten der Klasse disaster view View stehen schon alle wichtigen Methoden und Funktionalit ten die eine Ansicht ben tigt zur Verf gung Damit die neue An sicht nicht ohne Renderer in das System integriert wird werden ihr mit Hilfe der http java sun com j2se 1 4 1 docs api http java sun com docs books tutorial 2d index html gt 2 B http www javabuch de 5 3 Die Oberfl che 52 Methode addRenderer Renderer innerhalb des Konstruktors die ben tigten Renderer hinzugef gt was im folgenden Beispiel verdeutlicht wird import disaster view View public class MyView extends View public MyView super MyView addRenderer new MyAgentRenderer addRenderer new MyMessageRenderer Zun chst werden die Renderer in der Reihenfolge gezeichnet in der sie der An sicht hinzugef gt wurden Diese Reihenfolge kann sp ter im Programm wieder ge n
97. en an seine Nachbarn senden kann um damit eine Kettenreaktion auszul sen Dadurch sind diese ersten Initialisierungen die Voraussetzung f r den Ablauf eines Algo rithmus Anders als bei Applets oder Servlets k nnen Agenten auch mehrmals initialisiert werden Welcher Agent zu welchem Zeitpunkt initialisiert werden soll wird bei der Einrichtung der Umgebung festgelegt Um seinen Agenten einmal eine kleine Auszeit zu g nnen oder eine bestimmte Aktion verz gert ausf hren zu lassen kommt ein weiterer Nachrichtentyp zum Einsatz ber die setTimeout Methoden sendet ein Agent eine Nachricht vom Typ disaster model TimeoutMessage an sich selbst Nach einer angegebenen Zeit wird die Methode timeout TimeoutMessage aufgerufen ber die diese Nachricht verarbeitet werden kann Eine Broadcast Nachricht ob ber sendToAl1 oder send Agent BROADCAST gesendet erhalten grunds tzlich nur alle erreichbaren Nachbarn des sendenden Agenten Ein erreichbarer Nachbar hat die Eigenschaft mit diesem Agenten ver bunden zu sein Diese Verbindungen werden in einer Hashtabelle der Klasse HashMap verwaltet und k nnen ber die Hashtabelle selbst oder ber die Methode getOthers abgefragt werden Eine Hashtabelle wird mit Schl ssel Wert Paaren gef llt wobei eine Verbindung den Wert darstellt und der Agent zu dem die se Verbindung f hrt den Schl ssel Dadurch wird garantiert dass es nur eine Verbindung zu einem Agenten gibt Um weitere Informationen
98. en der Windows XP Ober fl che bietet aber zus tzlich eigene Elemente wie z B ein Farbverlauf in Men und Toolbars um einen einfachen 3D Effekt zu erzielen Zus tzlich enth lt es 18 Schrift und Farbschemas die auf den unterschiedlichsten Plattformen ein gesetzt werden k nnen um dort ein m glichst einheitliches Erscheinungsbild zu garantieren Ganz ohne Anpassungen lie sich das Look and Feel aber doch nicht in Di sASTer einbinden Das gr te Problem stellten hier die Reiter einer JTabbedPane dar Diese wurden f r das PlasticXP Look and Feel so angepasst dass sie alle dieselbe Farbe verwenden und sich diese Farbe auch nicht mit blichen Befehlen ndern l t Das ndern der Hintergrundfarbe dieser Reiter wird aber f r die Ausgabestr me siehe Abschnitt 5 3 2 Seite 59 verwendet Ein weiterer Aspekt bei grafischen Oberfl chen sind die verwendeten Sym bole Icons Diese sollten gut erkennbar sein und sich farblich weitgehend mit dem Aussehen der restlichen Anwendung decken Sun stellt eine Sammlung der g ngigsten Symbole bereit die sich ausgezeichnet in Swing Oberfl chen inte grieren lassen F r DisASTer wurden haupts chliche diese und einige selbst er zeugte verwendet In der Online Hilfe finden sich einige Symbole der Eclipse Symbolsammlung Neben dem Aussehen steuert der Aufbau einer grafischen Oberfl che einen wesentlichen Teil zu einer guten Benutzbarkeit bei Aus diesem Grund finden sich in DisASTer aus an
99. en k nnen Zu den Informationsfenstern geh ren MessageQueueInfoFrame in dem die MessageQueue in Tabellenform ab gebildet wird SentMessagesInfoFrame in diesem Fenster werden alle bereits ausgelie ferten Nachrichten dargestellt Die Darstellung erfolgt in einer hnlichen Weise wie die der MessageQueue in einer Tabelle ConsoleInfoFrame zeigt das Agentlog an ViewInfoFrame in solchen Fenstern werden die Ansichten dargestellt Die Fenster der Ansichten werden in einer InfoFrameGroup und in einem ent sprechenden Untermen der Men leiste verwaltet Die vom Anwender hin zugef gten Ansichten finden sich dann ebenfalls in dieser Gruppe wieder 6 6 Grafische Benutzeroberfl che GUI 90 AgentMesssageQueueInfoFrames hier befinden sich jeweils die Nachrich ten die an einen bestimmten Agenten adressiert wurden Zus tzlich werden in diesen Fenstern die AgentComponents dargestellt Auch diese Fenster bil den eine eigene Gruppe Die genaue Funktionsweise der einzelnen Oberfl chenelemente wird im Benutzer Handbuch Kapitel 5 beschrieben 7 Implementierung und Test 91 7 Implementierung und Test Im vorangegangenen Kapitel wurde der Entwurf des Programms vorgestellt Auf den folgenden Seiten wird auf ein paar besondere F lle eingegangen die in der Implementierungsphase aufgetreten sind Hierbei handelt es sich neben ein paar besonders kniffligen Programmteilen um verwendete Werkzeuge oder Bibliothe ken
100. er angegebenen Zeitver z gerung ausgeliefert send Object payload Connection connection mit dieser Methode wird ein Agent nicht direkt sondern ber die Verbindung zu ihm ange schrieben send Object payload Connection connection int duration diese Methode funktioniert wie die vorherige mit dem Unterschied dass hier wieder eine Zeitverz gerung stattfindet Die bisherigen Methoden werden haupts chlich dazu verwendet eine Nachricht an einen Empf nger zu senden Daneben gibt es Methoden die eine Nach richt gleichzeitig an alle mit dem Agenten verbundenen Agenten senden Al ternativ dazu kann bei den bisher vorgestellten Methoden die Broadcast Adresse Agent BROADCAST angegeben werden Das Verhalten entspricht den hier vorge stellten sendToAll Message message mit dieser Methode wird eine Art Broad cast bzw Multicast simuliert Alle ber bestehende Verbindungen mit dem aktuellen Agenten erreichbaren Teilnehmer erhalten eine Kopie der ber gebenen Nachricht ber diese Methode besteht die M glichkeit unter schiedliche Nachrichtentypen zu versenden 5 2 Die Bibliothek 45 sendToAll Object payload ber diese Methode kann ein Agent ein bestimmtes Paket an alle seine erreichbaren Nachbarn schicken Es wird der Standardnachrichtentyp verwendet sendToAll Object payload int duration bei dieser Methode wird wieder eine Zeitverz gerung bestimmt Neben der Kommunikation mit andere
101. er ein solcher Timeout abl uft k nnen weitere Nachrichten eintreffen und der Agent weitere Aktionen durch f hren Dem Anwender bleibt an dieser Stelle berlassen ob und wie er solche Aktionen w hrend eines Timeouts unterbindet Auf den Ein satz von Threads sollte grunds tzlich verzichtet werden da die Agenten keine Thread Sicherheit implementiert haben und eine Blockierung des laufenden Threads durch z B Thread sleep das ganze System lahm legen kann Dieses Programmierverhalten erinnert an die Handhabung von Swing Elementen speziell dem ActionListener die von dem EventDispatchingThread verwaltet werden und dieser ebenfalls nicht unterbrochen werden sollte setTimeout Object payload int duration sendet erneut einen Ti meout Hierbei kann allerdings noch zus tzlich ein Objekt verschickt wer den dass mit dem Timeout ausgeliefert wird Neben dem Senden ist vor allem das Empfangen von Nachrichten eine wichti ge Funktion der Agenten Um bei jedem Nachrichtentyp eine andere Methode aufrufen zu k nnen und damit besser zwischen den einzelnen Ereignissen unter scheiden zu k nnen wird an dieser Stelle ein Pseudopolymorphismus verwendet Eine Nachricht wird ber die Methode onReception lt Nachrichtentyp gt emp fangen Gibt es f r den bergebenen Typ keine entsprechende Methode wird eine Methode gesucht die die Oberklasse dieses Typs empfangen kann Diese 6 3 Model 82 Suche wird solange fortgesetzt bis der S
102. eren Rechnern ausgef hrt werden Die vom Benutzer erzeugten Klassen und Erweiterungen sollten einfach in das Programm eingebunden werden k nnen Die Ablaufsteuerung der Simulation sollte dem Anwender viele M glichkei ten bieten Zum einen soll er die M glichkeit haben Algorithmen automa tisch ablaufen zu lassen zum anderen soll er in den Ablauf eingreifen und ihn ver ndern k nnen Dies soll mit einer manuellen Steuerung erm glicht werden Um auch hier eine m glichst schnelle und intuitive Bedienung zu garantieren k nnten bekannte Funktionen wie Start Stopp Pause und Einzelschritt verwendet werden Die wichtigste Aufgabe des Programms ist allerdings die Darstellung und Visualisierung der Algorithmen Diese sollte in einer bekannten Form statt finden Wie oben bereits erkl rt geschieht dies oft ber Sequenzdiagram me Eine Alternative dazu w re eine Ansicht auf die Topologie des verteilten Systems Da die starren Ablaufdiagramme auf den ersten Blick zun chst sehr un bersichtlich wirken k nnte die Visualisierung in einer bewegten Animation stattfinden Diese Art der Darstellung erh ht die bersicht lichkeit und erleichtert das Verst ndnis der Arbeitsweise eines verteilten Algorithmus Um die bersichtlichkeit um noch einen weiteren Faktor zu 2 Aufgabenstellung 5 steigern sollte diese Visualisierung vom Anwender angepasst werden k n nen Um das Programm in m glichst vielen Themengebieten einsetzen zu k n
103. erteilten System dem Internet Damit sind verteilte Al gorithmen allgegenw rtig obwohl sie h ufig unerkannt im Hintergrund fungieren Viele von ihnen sind dazu da Fehler zu vermeiden oder Probleme zu l sen die in verteilten Systemen auftreten k nnen Dabei spielt die Zeit eine gro e Rolle In diesem Zusammenhang stehen Probleme wie Uhrensynchronisation logische Zeit oder globale Zust nde Die Uhrensynchronisation der einzelnen Teinehmer eines Netzwerks ist oft die Voraussetzung um weitere Probleme z B im Bereich Koordination und bereinstimmung zu l sen Unter diesen Punkt fallen zum Beispiel die Wahl eines Anf hrers oder der gegenseitige Ausschluss Auf die einzelnen Probleme und deren L sungen wird in den folgenden Ab schnitten eingegangen 3 1 Physikalische und logische Uhren Dieser Abschnitt besch ftigt sich mit dem Problem der Zeit Dabei wird zun chst ein Unterschied zwischen der physikalischen und der logischen Zeit gemacht Die physikalische Zeit bezieht sich auf die reale Zeit die auf Uhren dargestellt wird Mit Hilfe logischer Uhren soll unabh ngig von der jeweiligen physikalischen Zeit festgelegt werden k nnen ob ein Ereignis vor einem anderen eintritt 3 1 1 Uhrensynchronisation Ein Problem in verteilten Systemen ist die Uhrensynchronisation Jeder Prozess eines verteilten Systems besitzt eine physikalische Zeit Diese muss aber nicht unbedingt identisch mit denen der anderen Prozesse sein sondern es treten
104. essageQueue in der sich alle Nachrichten befinden die an diesen Agenten adressiert sind Um auch hier die Konsistenz zu bewah ren werden diese AgentMessageQueues von der MessageQueue in der sich alle gesendeten Nachrichten befinden verwaltet Abbildung 4 3 zeigt die Aufteilung der Nachrichten in der MessageQueue in die einzelnen AgentMessageQueues MessageQueue MessageQueue m lt receiver P gt m _MessageQueue P MessageQueue P lt receiver P gt m m m gt lt receiverP gt lt receiver P gt lt receiver P gt lt receiverP gt Abbildung 4 3 AgentMessageQueues Bei der manuellen Steuerung hat der Anwender nun den vollen Zugriff auf alle Nachrichten innerhalb dieser separaten Listen die durch die Aufteilung un abh ngig von einander bearbeitet werden k nnen Dort kann er die Reihenfolge ndern die Auslieferung von Nachrichten die eigentlich zu einem sp teren Zeit punkt erfolgen sollte kann vorgezogen werden oder es k nnen Nachrichten aus den Listen entfernt werden ber diese nderungen k nnen die oben angespro chen Szenarien wie Nachrichtenverlust oder verz gerung simuliert werden um 4 4 Visualisierung 39 zu testen wie das System auf diese Probleme reagiert 4 4 Visualisierung Um die Visualisierung muss sich der Anwender in der Regel nicht k mmern Es werden bereits zwei unterschiedliche Darst
105. et Methoden auf korrektes Verhalten zu berpr fen Darunter f llt z B die R ckgabe eines kor rekten Wertes auch unter Eingabe fehlerhafter Parameter Um Klassentests in Java durchf hren zu lassen wird das Rahmenwerk JUnit eingesetzt Dieses ist in Opensource verf gbar und hat sich mittlerweile als g ngigstes Testwerkzeug f r die Javaentwicklung etabliert Die Klassentests die f r DisASter durchgef hrt wurden beziehen sich haupt s chlich auf das Verhalten der Kontrollinstanz die die nderungen des Modells beinflusst Ein Problem das in vielen Artikeln oder Einf hrungen ber Unittests speziell mit JUnit bergangen wird sind Methoden ohne R ckgabewert die in der Klasse Controller ausschlie lich vorhanden sind Um diese Methoden auf m gliche Fehler zu berpr fen m ssen die von den Methoden erzeugten Seiten effekte berpr ft werden Die zu berpr fenden Seiteneffekte umfassen Zeit Uhr Die Umstellung der Zeit muss korrekt erfolgen Das bedeutet sie darf nicht stehen bleiben Nach einem Zeitschritt muss sie um einen Wert erh ht sein Bei einem R ckschritt muss die korrekte alte Zeit wieder herge stellt worden sein Dabei wird zwischen dem synchronen und asynchronen Modus unterschieden Konsistenz Die Umgebung muss konsistent bleiben Es d rfen z B keine Nach richten verloren gehen oder doppelt auftauchen Kommunikation ber den Controller wird ebenfalls die Umgebung getestet 15http www junit or
106. et Objekt kann schlie lich die JHelp Komponente erzeugt werden Listing 7 10 ClassLoader cl getClass getClassLoader URL hsURL HelpSet findHelpSet cl disaster hs HelpSet hs new HelpSet null hsURL JHelp help new JHelp hs AUNE Listing 7 10 Erzeugen eines JHelp Objekts Um die fertige Online Hilfe anzuzeigen muss nur noch das Fenster in dem sich die JHelp Komponente befindet ge ffnet werden vgl Sun03 7 9 Test Dieser Abschnitt besch ftigt sich mit den eingesetzten Testtechniken die ver wendet wurden um das Programm auf Fehler zu pr fen 7 9 Test 108 7 9 1 Statische Analyse W hrend und nach der Implementierungsphase wurde eine statische Analyse des Quellcodes durchgef hrt Im Normalfall sollte diese allerdings nicht vom Ent wickler selber sondern von einem projektfremden Entwickler erfolgen um eine objektivere Betrachtung zu erhalten Da dies im Falle einer Diplomarbeit nicht blich ist wurde die statische Analyse zeitversetzt zur Implementierung durch gef hrt um dadurch einen gewissen Abstand zu den erstellten Programmteilen zu bekommen der es erlaubt den Quelltext ein wenig objektiver zu sehen Dadurch dass die Analyse h ufig zu Optimierungen des bestehenden Codes f hrt muss diese in mehreren Schritten erfolgen um auch den optimierten Code erneut zu berpr fen Ergebnisse dieser Optimierungen sind in der Regel bessere Aufteilung von Methoden oder Reduzierungen
107. f hrt den Anwender direkt zu den Einstellungen des gew hlten Renderers Die Einstellungsm glichkeiten der einzelnen Renderer k nnen bei dieser Gele genheit ebenfalls vorgestellt werden Abbildung 5 16 zeigt den Dialog ber den dies geschieht Der Dialog zeigt die m glichen Zust nde die der gew hlte Agent STATE_WAITING STATE_NORMAL B STATE_WORKING E Show ID Abbildung 5 16 Renderereinstellungen Agenten 5 3 Die Oberfl che 66 annehmen kann und in welcher Farbe dieser Zustand in der gew hlten Visua lisierung dargestellt wird Nach einem Mausklick auf ein solches Farbfeld wird ein Dialog sichtbar ber den eine andere Farbe f r diesen Zustand festgelegt werden kann Zus tzlich kann verhindert werden dass die ID des entsprechenden Agenten in der Visualisierung angezeigt wird Die hier gemachten Einstellungen werden allerdings nur bei diesem Agenten und nur in dieser Ansicht aktiv Wenn das ver nderte Farbschema ebenso bei allen anderen Agenten verwendet werden soll muss der Anwender die nderungen bei jedem Agenten einzeln durchf hren oder eigene Renderer oder eigene Ansichten verwenden Neben den Agenten k nnen auch die Nachrichten angepasst werden Der hierf r zust ndige Dialog wird in Abbildung 5 17 gezeigt F r jeden bereits exis TimeoutMessage E InitMessage WE Message E Request o E Response Abbildung 5 17 Renderereinstellungen Nachrichten tierenden Nachrichtentyp kann wie zuvor be
108. f P2 Wartet auf Ps Wartet auf P Abbildung 3 8 Wechselseitiger Ausschluss nach Maekawa mit Verklemmung 3 3 2 Wahl eines Anf hrers Die meisten der vorangegangenen Algorithmen haben auf eine zentrale Instanz verzichtet Bei einigen ist dies jedoch unumg nglich Um aus einem verteilten System bestehend aus gleichberechtigten Prozessen einen bestimmten Prozess zu bestimmen der die Rolle dieser zentralen Instanz bernimmt werden Wahl Algorithmen verwendet Eine wichtige Eigenschaft solcher Wahl Verfahren ist dass jeder Prozess p jederzeit eine Wahl initiieren kann Die Initiierung einer neuen Wahl kann bei spielsweise dann erfolgen wenn ein Prozess merkt dass der derzeit gew hlte Prozess nicht mehr verf gbar ist vgl Coulouris et al 02 S 501f Ringbasierte Wahl Chang und Roberts haben eine Methode entwickelt um einen Anf hrer in einer Ringstruktur festzulegen Dabei wird der Prozess mit der h chsten ID gew hlt Das Verfahren l uft wie folgt ab Um die Wahl zu initiieren wird eine Wahlnachricht mit der eigenen ID an den n chsten Prozess gesendet Zus tzlich merkt sich der Prozess dass er bereits Teilnehmer einer Wahl ist Bei Erhalt einer Wahlnachricht berpr ft der Empf nger seine ID mit der der Nachricht 3 3 Koordination und bereinstimmung 22 1 Ist die eigene ID kleiner als die empfangene sendet er die Nachricht an den n chsten Prozess weiter und setzt sich als Teilnehmer 2
109. frage an alle Gruppenmitglieder des Agenten gesendet 11 public void init InitMessage message 12 setState STATE_WAITING 13 answers 0 14 sendToAll new Request 15 Bei Erhalt einer solchen Anfrage berpr ft der Empf nger ob er schon einem anderen Agenten die Zusage gemacht hat oder ob er sich selbst im kritischen Abschnitt befindet Ist dies der Fall puffert er die Anfrage ansonsten sendet er sein OK zur ck und merkt sich dass er seine Stimme bereits abgegeben hat 16 public void onReception Request message 17 if voted true getState STATE_WORKING 18 buffer add message getSender 19 20 else 21 send new Response message getSender null 22 voted true 8 2 Koordination und bereinstimmung 124 23 24 Erh lt ein Agent eine Antwort auf seine Anfrage erh ht er deren Anzahl Sind mit dieser Antwort alle eingetroffen kann er den kritischen Abschnitt betreten 25 public void onReception Response message 26 answerstt 27 if answers get Others length 28 setState STATE_WORKING 29 setTimeout 3 30 31 Der Erhalt einer einfachen Nachricht deutet an dass der Sender dieser Nachricht den kritischen Abschnitt verlassen hat und dieser wieder frei ist Hat der Emp f nger noch Anfragen in dem Puffer wird die erste beantwortet Dabei muss sich der Agent erneut merken dass er jetzt seine Stimme abgegeben hat
110. g 7 9 Test 110 Diese muss die Nachrichten korrekt ausliefern die Empfangszeiten richtig setzen und die Nachrichten in die richtigen Listen eintragen Controller Zust nde Die Zust nde des Controllers m ssen korrekt arbeiten Ist ein bestimmter Zustand gew hlt muss auch dieser agieren und kein an derer Die Umstellung auf einen anderen Controller Zustand muss ebenfalls auf Fehler getestet werden 8 Beispiele 111 8 Beispiele In diesem Kapitel werden einige Beispiele der beschriebenen Algorithmen aus Ka pitel 3 vorgestellt Hierbei wird vor allem Wert auf die Implementierung gelegt um zu zeigen wie diese Algorithmen f r DisASTer umgesetzt werden k nnen Da zu wird in der Regel eine Klasse pro Algorithmus vorgestellt in der das Verhalten eines Prozesses in dem betreffenden Algorithmus erzeugt wird 8 1 Logische Uhren Das Problem der logischen Uhren wird in Abschnitt 3 1 2 beschrieben Es geht dabei um die Beziehungen zwischen Ereignissen in unterschiedlichen Prozessen Logische Uhren sollen dabei helfen festzulegen in welcher logischen Reihenfolge diese Ereignisse zueinander stehen also welches Ereignis zeitlich vor welchen Ereignissen anzusiedeln ist Lamport Methode Die logische Uhr von Lamport wird durch einen einfachen Z hler repr sentiert der bei jedem Ereignis hochgez hlt wird Ein Ereignis k nnte eine Aktion sein die ein Prozess ausf hrt darunter fallen auch das Senden und das Empfangen von Nach
111. g kann n tzlich sein um die einzelnen Agenten vonein ander zu unterscheiden F r manche Algorithmen wird eine eindeutige Kennung sogar vorrausgesetzt Neben einer Kennung verf gen die Agenten ber ein At tribut das ihren Zustand beschreibt Ein m glicher Zustand w re beispielsweise das Warten auf eine Nachricht Ein Agent besitzt zudem eine Rolle die er im Zu sammenspiel mit anderen Agenten erf llt Die wichtigsten Methoden die durch die Klasse Agent geerbt werden sind Methoden zum Senden und Empfangen von Nachrichten Die Bedeutung der Kommunikation und die des Nachrichtenflusses wird sp ter beschrieben Die Topologie eines verteilten Systems ist allerdings erst mit den Verbindun gen komplett Diese werden nicht in den Agentenklassen oder in einer anderen Klasse definiert sondern erst im Programm wo die gesamte Umgebung konfigu riert wird Dadurch kann der Anwender entscheiden mit wie vielen Agenten er den Algorithmus testen will und wie diese Agenten miteinander verbunden sind und muss sich nicht im Vorfeld darauf festlegen 4 3 Kontrolle und Steuerung 36 4 3 Kontrolle und Steuerung Die Simulation in DisASTer verl uft nachrichtengesteuert Das erkl rt den hohen Stellenwert der Sende und Empfangsmethoden der Agenten Nachrichtengesteu ert bedeutet dass eine Aktion oder eine bestimmte Handlungsweise eines Agen ten nicht durch ein Ereignis sondern durch das Eintreffen einer Nachricht ausge l st wird Abbildung 4
112. gangene Abschnitt beschreibt die Problematik noch nicht bekannte Klassen aus dem Dateisystem zu laden Dieser Abschnitt geht noch einen Schritt weiter und besch ftigt sich mit der Problematik diese neu geladenen Klassen mit Hilfe der Reflection API zu bearbeiten Die Reflection API gibt Aufschluss ber Methoden Felder oder Konstruktoren von einer Klasse Diese werden durch Java Objekte repr sentiert und k nnen ber diese abgefragt oder aufgerufen werden Die wichtigste Klasse in diesem Zusammenhang ist die Klasse Class Ein Objekt dieser Klasse enth lt Informationen ber Methoden Konstruktoren oder Attribu te einer Klasse aber auch die Klassenhierarchie die Klasse aus der sie abgelei tet ist oder implementierte Interfaces Diese Informationen werden bereits zum Klassenladen verwendet Oft m ssen die ausgew hlten Klassen eine bestimmte andere erweitern Erh lt man ber die im vorigen Abschnitt beschriebene Me thode eine Klasse wird berpr ft welche sie erweitert bzw welche Interfaces sie implementiert um sicherzugehen dass Objekte dieser Klasse zur weiteren Verarbeitung verwendet werden k nnen Wird die ausgew hlte Klasse diesen An spr chen gerecht kann nun ein Objekt dieses Typs erzeugt werden Um dies zu erreichen k nnen entweder Aufrufe der Contructor Objekte der Klasse oder die Methode newInstance verwendet werden Die Methode newInstance setzt allerdings einen leeren Konstruktor voraus da ber sie noch keine Para
113. gent extends Agent private int v description VectorClockAgent getID v null 1 2 3 4 public VectorClockAgent 5 6 to F Auch in diesem Beispiel beschr nkt sich die Ereignisspezifikation auf das Sen den und den Empfang von Nachrichten Zum Senden einer Nachricht wird die init Methode verwendet Dort wird zun chst der Vektor initialisiert VC1 sofern dies noch nicht geschehen ist Die Initialisierung erfolgt in der Methode initVector die sp ter vorgestellt wird Nach der Initialisierung und vor dem Senden der Nachricht an den n chsten Nachbarn wird die eigene Uhr im Vektor laut VC2 erh ht Die Nachricht enth lt laut VC3 die eigene Vektoruhr Um ein Ereignis zu simulieren wird eine Textausgabe verwendet Diese greift auf die Hilfsmethode print int zu die zur Darstellung der Vektoren verwendet und sp ter beschrieben wird 8 public void init InitMessage message 9 initVector 10 11 v getID 12 send v getOthers 0 13 println sending Message to getOthers 0 14 at print v 15 Falls der Vektor beim Empfang einer Nachricht noch nicht initialisiert wurde wird dies zun chst nachgeholt Dann wird nach Regel VC4 der eigene Vektor 8 1 Logische Uhren 115 v mit dem empfangenen Vektor um verglichen und die einzelnen Zeiten auf das Maximum der beiden Vektoren gesetzt Das eigentliche Ereignis stellt erneut eine Textausgabe dar
114. genten mit einer h heren ID Diese tr gt er zun chst in die Liste der ausgefallenen Prozesse ein bis sie ihm eine Antwort auf die gerade gesendete Nachricht schicken Zus tzlich zur Initialisierung wird ein Timeout ausgel st der den gerade angeschriebenen Agenten enth lt damit der Agent berpr fen kann ob er schon eine Antwort nach dem entsprechenden Timeout bekommen hat Die Variable inits zeigt an wie viele andere Agenten initialisiert wurden Stellt er bei dieser Gelegenheit fest dass kein Agent eine h here Kennung hat als er selbst ist er der neue Anf hrer und teilt dies allen anderen Agenten mit 12 public void init InitMessage message 13 if message getSender null 14 send new Response message getSender 15 16 17 if getState STATE_WAITING leader this 18 return 19 20 setState STATE_WAITING 21 inits 0 22 leader null 23 24 boolean isLeader true 25 for int i 0 i lt getOthers length i 26 Agent other get Others i 27 if other getID gt getID 28 isLeader false 29 send new InitMessage other 8 2 Koordination und bereinstimmung 130 30 setTimeout other TIMEOUT 31 corrupted add other 32 initst 33 34 35 36 if isLeader 37 leader this 38 setRole ROLE_MASTER 39 sendToAll new Message null leader 40 setState STATE_NORMAL 41 42 Erh lt ein Agent eine Antwort auf
115. gesendet aber noch nicht an den betreffenden Empf nger ausgeliefert wurden AgentMessageQueues dieses Men gew hrt Zugriff auf die Message queues der einzelnen Agenten d h alle Nachrichten die an einen speziellen Agenten adressiert sind finden sich in einer separaten Liste wieder Neben dieser Liste werden aber auch Zugriffsbefehle angezeigt um die Nachrich tenreihenfolge zu ndern oder Nachrichten zu l schen In diesem Fenster wird zus tzlich die agentenspezifische Swing Komponente angezeigt so fern diese vom Entwickler realisiert wurde Neben diesen Fenstern die im Desktopbereich der Anwendung angezeigt wer den gibt es noch zwei weitere Komponenten die Informationen ber das System liefern Ausgabestr me die Standardausgabe System out und die Standardfeh lerausgabe System err werden in das Programm umgeleitet und befin den sich unterhalb der Desktopoberfl che in zwei durch Reiter getrennten Textfeldern Statusleiste wie viele Agenten sich in einer Umgebung befinden wie viele Nachrichten in der Messagequeue liegen wie viele Nachrichten gesendet wurden und an welchem Zeitschritt die Simulation angekommen ist wird in der Statusleiste angezeigt In den folgenden Abschnitten werden diese Informationsfenster n her erl u tert 5 3 Die Oberfl che 55 Views Die Ansichten sind wohl die wichtigste Schnittstelle zwischen dem An wender und DisASTer Sie stellen den Ablauf eines Algorithmus grafisch d
116. ginnend mit einem Prim r Server als Wurzelelement und Sekund r Servern in den darunter liegenden Schichten wobei die Prim r Server direkt mit einer UTC Quelle ver bunden sind Der Aufbau einer solchen Hierarchie wird durch Abbildung 3 1 dar gestellt Eine Schwierigkeit der NTP entgegenwirkt ist dass Server mit einer hohen Schichtennummer sehr wahrscheinlich ungenauer sind als Server aus einer ber geordneten Hierarchieebene NTP l st das Problem ber eine Bewertung der Qualit t der Zeitnahmedaten Die Synchronisierung zwischen den einzelnen Servern und den anfragenden Computern kann ber drei Modi erfolgen 3 1 Physikalische und logische Uhren 9 1 Abbildung 3 1 NTP Hierarchie Multicast Modus wird zur Serversynchronisierung in einem Hochgeschwin digkeits LAN Low Area Network eingesetzt Coulouris Dollimore und Kindberg beschreiben diesen Modus wie folgt Ein oder mehrere Server senden in bestimmten Zeitabst n den Multicasts mit der Zeit an die Server die auf anderen an das LAN angeschlossenen Computern ausgef hrt werden die ihre Uhren unter der Ber cksichtigung einer kleinen Verz ge rung setzen Dieser Modus kann nur relativ geringe Genauigkeit erzielen die aber f r viele Aufgabenstellungen als ausreichend erachtet werden Coulouris et al 02 S 459 Prozeduraufruf Modus wird eingesetzt falls eine h here Genauigkeit als bei der Multicast Methode ben tigt wird oder Multicast nicht unte
117. gorithmus wiederherstellen Ein Umschalten zwischen den drei Modi ist jeder Zeit m glich Dadurch kann der Anwender z B einen Gro teil der Simulation automatisch ablaufen lassen und nur an Stellen eingreifen die f r ihn interessant sind Abbildung 6 10 zeigt den Aufbau des Controllers Dieser wurde mit dem Ent wurfmuster State Zustand realisiert Mit Hilfe dieses Entwurfsmusters kann ein Objekt seinen internen Zustand ndern so dass es so aussieht als ob das Objekt seine Klasse ge ndert hat vgl Gamma et al 96 S 357ff Es werden aber nur die internen Zust nde durch jeweils andere Objekte repr sentiert L public void start ControllerStateChangeListener state start z controllerStateChanged state ControllerState void 1 l j l 1 Controller l 1 Jinstance Controller 1 1 speed int ControllerState 1 77 getlnstance Controller 5 S pause void start void next void stop void start void pause void stop void next void next mq MessageQueue void next mq MessageQueue void A addControllerStateListener listner ControllerStateChangeListener boolean removeControllerStateListener listener ControllerStateChangeListener boolean Manual Running Stopped Paused Abbildung 6 10 Aufbau des Controllers Der Controller verf gt ber folgende Zust nde die alle das Interf
118. her machen Ereignisse die in irgendeinem Verh ltnis zu einander stehen werden zu einem Prozess zusammengefasst Die Aus f hrungszeit eines solchen Prozesses dauert in der Regel mindestens einen 9 2 Zusammenfassung und Vergleich 139 Zeitschritt Zus tzlich verf gt der Prozess ber einen Zustand der seine momentane Ablaufphase beschreibt Im Gegensatz zur ereignisgesteuerten Simulation ist die Steuerung der prozessorientierten Simulation wesentlich komplizierter da hier Funktionen zum Erschaffen Auslaufen Beenden oder Pausieren von Prozessen gegeben sein m ssen Hinzu kommen Funktionen die ben tigt werden um eine Kommunikation oder Synchronisation zwi schen mehreren Prozessen zu erm glichen Dieser prozessorientierte Ansatz erinnert stark an die Funktionsweise von Betriebssystemen die ebenfalls mehrere Prozesse verwalten m ssen DisASTer l sst sich am besten mit den beiden Java L sungen DAJ und ViSi DiA vergleichen Wobei ein entscheidender Unterschied auftritt Im Gegensatz zu DisASTer werden die Algorithmen in den beiden anderen Programmen in einer einzigen Klasse definiert in der das Verhalten der einzelnen Prozesse beschrieben wird Bei DisASTer entscheiden die Prozesse selbst wie sie auf welche Ereignisse reagieren und werden dadurch nicht von aussen gesteuert Dieser Punkt spiegelt die Innovation von DisASTer wieder denn auf diese Weise k nnen verschiedene Algorithmen die beispielsweise in Pseudocode vorliegen
119. i den Zust nden der Agenten eine Farbe gew hlt werden Auch hier werden die Einstellungen nur f r die aktuelle Ansicht wirkungsvoll Der ConnectionRenderer ist nur in der Topologieansicht zu finden Dieser hat die Aufgabe die Verbindungen zwischen den Agenten zu zeichnen Verbindungen werden durch Linien dargestellt Die Farbe und das Aussehen dieser Linien kann hier eingestellt werden Das Aussehen der Linie unterscheidet sich in ihrer Breite oder ob sie gestrichelt oder durchgezogen sind Der hierf r verantwortliche Dialog wird in Abbildung 5 18 dargestellt 5 3 4 Ablauf und Steuerung Da ein Algorithmus in endlich vielen Schritten abl uft stellt DisASTer eine Steue rung bereit die der eines Video oder CD Spielers hnelt Abbildung 5 19 Ab gesehen von dem automatischen Ablauf des Algorithmus besteht die M glichkeit den Algorithmus in Einzelschritten ablaufen zu lassen und diese Schritte sogar wieder r ckg ngig zu machen Diese R ckw rtsbewegung erinnert an die Ver laufsfunktion eines Browser 5 3 Die Oberfl che 67 Connection MutEx Agent 0 MutEx gent 1 Connection MutEx Agent 0 MutEx Agent 2 EEE Connection MutEx Agent 0 MutEx Agent 3 F je Connection MutEx Agent 1 MutEx Agent 2 Connection MutEx Agent 1 MutEx gent 3 E Connection MutEx Agent 2 MutEx Agent 3 Abbildung 5 18 Renderereinstellungen Verbindungen Al Previous
120. ich ist nicht gezwungen auf diesen Parameter zur ckzugreifen 6 5 Controller Der Controller hat die Aufgabe die Simulation zu steuern F r diesen Zweck wurden zwei bzw drei verschiedene Modi gew hlt Zum einen die manuelle Steuerung bei welcher der Anwender den Ablauf des Algorithmus weitgehend selbst bestimmen kann Er kann entscheiden welche Nachrichten wann ausgelie fert werden oder ob er Nachrichten aus dem System entfernen m chte Neben der manuellen Steuerung stehen ihm noch zwei automatische zur Verf gung Hier wird zwischen synchron und asynchron unterschieden Der synchrone Ab lauf entspricht dem wirklichen Ablauf Hier wird jeder Zeitpunkt nacheinander ausgef hrt Beim asynchronen Ablauf wird ein solcher Zeitpunkt in Zeitschritte aufgeteilt Pro Nachricht wird ein Einzelschritt dargestellt Dieser Modus erleich tert die Betrachtung eines Algorithmus wenn viele Nachrichten zur selben Zeit ber die Leitungen wandern Logisch gesehen geschieht das dann zwar immer 6 5 Controller 86 noch aber die Darstellung wird in kleinere Schritte geteilt Der automatische Ablauf soll wie ein Video oder CD Player gesteuert werden k nnen Funktionen wie Start Stop Pause Einzelschritt oder R ckschritt sollen diese Arbeitsweise wiedergeben wobei das R ckw rtslaufen eher mit dem Verlauf eines Webbrow sers verglichen werden sollte Die Stop Funktion soll zum einen die Simulation anhalten und zum anderen den Startzustand des Al
121. ichenoperationen festgelegt werden um das entsprechende Element grafisch darzustellen und 3 einer Swingkomponente ber die der Renderer modifiziert werden kann Um die Position und die Abmessungen zu bestimmen wird ein Rechteck auf gezogen das seine linke obere Ecke an dem von x und y beschriebenen Punkt hat und eine Breite des Wertes width und eine H he des Wertes height be sitzt Eine Ansicht die diesen Renderer verwendet h lt den Platz den dieses Rechteck beschreibt frei und passt seine Gr e gegebenenfalls an Es ist auch m glich ausserhalb der angegebenen Grenzen zu zeichnen Allerdings ist dann nicht sichergestellt dass dieser Teil auch wirklich dargestellt wird da der Platz nicht von der Ansicht reserviert wurde Die Grenzen mehrerer Renderer k nnen sich durchaus auch berdecken In diesem Fall spielt die Reihenfolge in der die Renderer aufgerufen werden eine Rolle da sie sich gegenseitig bermalen k nnen Die eigentliche Arbeit des Renderers verrichtet die Methode draw Graphics g double progress 5 2 Die Bibliothek 51 Gezeichnet wird auf das bergebene Graphics Objekt das selbst schon viele Methoden bereitstellt um einfache Formen zu zeichnen Eine umfassende Hilfe ber den Umgang mit diesem Objekt bieten die API Dokumentation das Sun Tutorial oder ein gutes Javabuch Ein wenig komplizierter ist hierbei der ber gebene double Wert Falls eine Simulation animiert abl uft zeigt dieser Wert de
122. icht an den oder die eingetragenen Empf nger Durch diese Methode k nnen auch unter schiedliche Nachrichtentypen versendet und damit verschiedene Ereignisse ausgel st werden send Object payload Agent receiver mit dieser Methode wird ein Objekt an einen bestimmten Empf nger gesendet Hierbei wird der Stan dardnachrichtentyp disaster model Message verwendet send Object payload Agent receiver int duration diese Metho de sendet ebenfalls eine Standardnachricht an den bergebenen Empf nger allerdings wird diese Nachricht fr hestens nach der angegebenen Zeitverz gerung ausgeliefert Der bergebene Wert wird relativ zum Zeitpunkt des Sendens gesehen send Object payload Connection connection mit dieser Methode wird ein Agent nicht direkt sondern ber seine Verbindung angesprochen send Object payload Connection connection int duration diese Methode funktioniert wie die vorherige mit dem Unterschied dass hier wieder eine Zeitverz gerung mit angegeben werden kann sendToAll Message message mit dieser Methode wird eine Art Broad cast simuliert Alle ber bestehende Verbindungen mit dem aktuellen Agen ten erreichbaren Teilnehmer erhalten eine Kopie der bergebenen Nach richt Das bergeben eines Empf ngers an eine Nachricht die ber diese Methode versendet wird hat keine Wirkung Ist der bergebene Empf nger mit dem Sender dieser Nachricht verbunden bekommt er wie alle ande ren a
123. ie bestehend aus den einzelnen Agenten und ihren Verbindungen die MessageQueue die bereits gesendeten Nachrichten und der bisherige Verlauf des Algorithmus Save As dieser Men eintrag speichert die momentane Umgebung in eine neue Datei Exit ber diesen Men eintrag wird das Programm beendet 5 3 2 Informationsfenster Hinter den Befehlen im Men punkt View verbergen sich viele n tzliche Fens ter die Aufschluss ber den momentanen Zustand der Umgebung geben siehe Abbildung 5 2 File Options Help views D Sequenceview D AgentConsole E SsentMessages EI MessageQueue lt Topologyview Abbildung 5 2 Informationsfenster Es handelt sich dabei um x Views in diesem Men werden die Ansichten der Visualisierung auf gef hrt Hier befinden sich auch die vom Anwender erstellten Ansichten nachdem diese dem System hinzugef gt wurden 5 3 Die Oberfl che 54 SequenceView zeigt eine Ansicht um den zeitlichen Ablauf der Si mulation zu verdeutlichen TopologyView ruft die Topologieansicht auf die eine Draufsicht der aktuellen Umgebung liefert BF AgentConsole gibt die Testausgaben der einzelnen Agenten aus die ber die Methode printin erzeugt wurden SentMessages in diesem Fenster wird eine Liste mit den bereits aus gelieferten Nachrichten angezeigt i MessageQueue in diesem Fenster werden alle Nachrichten aufgef hrt die zwar schon
124. ie Uhr jedes Prozesses p mit 0 initialisiert wurde 1 P o gt a b m 3 4 P2 gt c d m 1 5 P3 gt e f Abbildung 3 3 Ereignisabfolge mit logischen Uhren Mit dieser Methode kann genau bestimmt werden ob ein Ereignis vor einem anderen ausgel st wurde Weiter l sst sich festhalten dass wenn ein Ereignis e das Ereignis e ausgel st hat e e dann gilt e gt e gt L e lt L e Diese Feststellung l sst sich allerdings nicht umdrehen Aus L e lt L e folgt nicht unmittelbar e e Wie aus der Abbildung ebenfalls erkennbar kann es passieren dass zwei von einander unabh ngige Ereignisse einen identischen Zeitstempel besitzen Dies ist bei a und e der Fall Um auch diese Ereignisse in eine logische Reihenfolge zu bringen wird das Verfahren der Lamport Uhr erweitert indem ein Zeitstempel T eines Prozesses p um die ID des Prozesses erweitert wird Damit erhalten 3 1 Physikalische und logische Uhren 12 die Zeitstempel die Form T i Dann gilt T i lt T 5j wenn entweder T lt T oder T T und i lt j Diese Reihenfolge erfolgt meist willk rlich da die Prozess IDs keiner Hierarchie untergeordnet sein m ssen Hierf r k nnten z B die IP Adressen einzelner Netzwerkteilnehmer verwendet werden Der hieraus resultierende Zeitstempel ist nun eindeutig vgl Coulouris et al 02 S 463f Vektoruhren Eine Alternative zu Lamport Zeitstempeln stellen die Vekto
125. iert werden k nnen der das Verhalten der einzelnen Teilnehmer beschreibt Als n chstes wird der Simulationstyp bestimmt Zur Auswahl stehen die er eignisgesteuerte oder die prozessorientierte Simulation siehe Kapitel 9 Eine Unterart der ereignisgesteuerten ist die nachrichtengesteuerte Simulation Dieser Ansatz wird in diesem Entwurf weiterverfolgt da sich die einzelnen Teilnehmer untereinander ber Nachrichten verst ndigen deren Eintreffen als Ereignis ein gestuft werden kann Anstatt eine Liste von Ereignissen zu verwalten wird eine Nachrichtenliste die MessageQueue verwendet Diese enth lt im Verlauf einer Simulation alle gesendeten Nachrichten bevor diese dem eigentlichen Adressaten zugestellt werden anstatt sie direkt an diesen auszuliefern Mit Hilfe dieser Zwi schenstation ist es nun m glich in den Verlauf des Algorithmus einzugreifen und diesen gegebenfalls zu ndern indem die MessageQueue bearbeitet wird Um eine Kommunikation zwischen den einzelnen Teilnehmern zu erm glichen m ssen diese miteinander verbunden werden Dieser Verbund bildet schlie lich 6 2 Erkenntnisse f r den eigenen Entwurf 73 einen Graphen bestehend aus Knoten und Kanten n mlich den Teilnehmern und ihren Verbindungen Dieser Graph beschreibt die Topologie des nun entstan denen verteilten Systems Eine solche Topologie soll sich ebenfalls im Entwurf wiederfinden Mit ihr k nnen die Positionen der einzelnen Prozesse bestimmt werden Dad
126. igt vgl Coulouris et al 02 S 503ff 3 3 3 Nachrichtenreihenfolge In Abschnitt 3 1 2 wurde gezeigt wie wichtig es ist zu wissen in welcher Rei henfolge bestimmt Ereignisse auftreten hnlich verh lt es sich mit Nachrichten eines verteilten Systems und der Reihenfolge in der sie von den verschiede nen Prozessen bearbeitet werden Dieses Problem tritt vor allem bei Netzwerken 3 3 Koordination und bereinstimmung 25 auf in denen mit Multicast oder einem simulierten Multicast gearbeitet wird Dort kann die eigentliche Reihenfolge mehrerer Nachrichten durch l ngere Ver z gerungszeiten bei den einzelnen Prozessen vertauscht werden Es gibt mehrere M glichkeiten die Reihenfolge dieser Nachrichten zu definieren FIFO Wenn ein Prozess p zuerst Nachricht m versendet hat und anschlie end m dann wird auch die Nachricht m vor der Nachricht m bei den Emp f ngern ausgeliefert kausal Eine Nachrichtenreihenfolge ist kausal wenn der Emfang von Nachricht m das Senden der Nachricht m ausl st und diese Nachrichten auch in dieser Reihenfolge ausgeliefert werden total Unter der totalen Reihenfolge wird eine einheitliche Reihenfolge bei allen Prozessen verstanden Diese muss aber weder FIFO noch kausal sein Liegt eine kausale Reihenfolge vor impliziert dies auch die FIFO Reihenfolge Zus tzlich zu den drei Formen gibt es die Hybridformen FIFO total kausal total Abbildung 3 11 zeigt ein Beispiel zu je
127. ilter Algorithmus agieren kann Sowohl bei der Erstellung einer neuen Umgebung E als auch beim Aufruf der Einstellungen H wird ein Dialog sichtbar der sich in zwei Kategorien unterteilt 1 Agents hier werden die Agenten die f r den Algorithmus ben tigt werden eingebunden und initialisiert 5 3 Die Oberfl che 61 2 Topology hier k nnen die vorher erstellten Agenten positioniert und Ver bindungen zwischen den einzelnen Agenten erstellt werden In der Kategorie Agents werden die einzelnen Teilnehmer eines Algorithmus verwaltet Abbildung 5 12 Agents Topology w B 8 Abbildung 5 12 Einstellungen Agenten F r diesen Zweck gibt es eine Reihe von Befehlen Add Agent ffnet einen Dialog der die Auswahl einer class Datei erm glicht Von der ausgew hlten Klasse wird eine neue Instanz erzeugt sofern es sich bei der Klasse um eine Erweiterung der Agent Klasse handelt Der daraus entstandene Agent wird dann in das System integriert Remove Agent mit diesem Befehl werden die ausgew hlten Agenten wieder aus dem System entfernt B Copy die Klasse des ausgew hlten Agenten wird in eine interne Zwi schenablage unabh ngig zur Systemzwischenablage kopiert Paste f gt eine neue Instanz der Agentenklasse aus der internen Zwi schenablage ein Diese Funktionalit t ist vor allem dann praktisch wenn f r einen Algorithmus mehrere Objekte einer K
128. in 11 03 Oechsle02 R Oechsle 2002 Verteilte Algorithmen Kapitel 9 aus dem Skript Verteilte Systeme an der Fachhochschule Trier Fachbereich Angewandte Informatik Bauderon et al 03 M Bauderon M Moshbah Y Metevier A Zemmari A Sellami B Derbel R Ossamy 2003 The ViSiDiA Project Visua lization and Simulation of Distributed Algorithms http www labri fr Recherche LLA visidia Jump93 J R Jump 1993 YACSIM Reference Manual http www owinet rice edu lec428 yacsim yacsim man ps Kaynar03 Dilsun Kirli Kaynar 2003 IOA Language and Toolset http theory Ics mit edu tds ioa Lydian Lydian An Extensible Educational AnimationEnvironment for Lear ning Distributed Algorithms http www cs chalmers se Iydian McCanne Floyd 03 S McCanne S Floyd 2003 The Network Simulator ns 2 http www isi edu nsnam ns Schreiner98 W Schreiner 1998 DAJ A Toolkit for the Simulation of Dis tributed Algorithms in Java http www risc uni linz ac at software daj report Sinclair02 J B Sinclair 2002 Simulation of Computer Systems and Computer Networks A Process Oriented Approach http www owinet rice edu lec428 yacsim book ps Literaturverzeichnis 143 Sun03 Sun 2003 Javahelp A New Standard for Application Help and Online Documentation http java sun com products javahelp Terrevoli97 P Terrevoli 1997 Distributed Systems Platform DSP http
129. ine Erweiterung der LEDA Bibliothek und wurde entworfen um verteilte Algorithmen zu implementie ren zu simulieren und zu testen F r die Implementierung wird C verwendet Die Einrichtung und Simulation erfolgt ber eine grafische Benutzeroberfl che zu der unter anderem ein Topologieeditor geh rt Mit Hilfe einer zus tzlich bei liegende Bibliothek k nnen die Algorithmen in einem realen Netzwerk eingesetzt werden Lydian Lydian wird f r Lernzwecke eingesetzt Hauptaufgabe dieses Programms ist die Simulation und Visualisierung von verteilten Algorithmen Diese werden ber eine eigene Beschreibungssprache definiert Lydian setzt auf einige externe Bibliotheken wie z B LEDA POLKA oder DIAS auf die die Aufgaben der Netz werkstrukturen oder die Darstellung der Algorithmen bernehmen vgl Lydian 9 2 Zusammenfassung und Vergleich 137 DAJ Distributed Algorithms in Java DAJ wurde an der Universit t Linz entwickelt Es handelt sich um eine Java Bibliothek um verteilte Algorithmen zu implementieren zu simulieren zu visualisieren und zu testen In der Bibliothek finden sich Klassen zur Erzeugung eines verteilten Algorithmus Zudem wird eine Umgebung mitgeliefert in der diese Algorithmen ablaufen k nnen Die Ausf h rung kann lokal als Applikation oder ber das Web als Applet erfolgen In DAJ erstellte Systeme werden durch einen Graphen der aus Knoten und Kanten be steht beschrieben Die Knoten haben die M glichkeit Na
130. ine Nachricht m wird mit einer eindeutigen ID und der momentanen Fol genummer n des sendenden Prozesses hnlich einer eindeutigen logischen Uhr lt m i n gt verschickt Bei Empfang einer solchen Nachricht setzt der Empf nger p seine Fol genummer n mazx n n 1 und antwortet dem Sender mit einer Nachricht die die Kennung der empfangenen Nachricht i und seine neue Folgenummer n beinhaltet lt i n gt Die empfangene Nachricht wird mit der neuen Folgenummer in eine R ckhalte Warteschlange einsortiert in der die Nachricht mit der kleinsten Folgenummer vorne steht Sind alle Antworten einer Nachricht eingetroffen wird dieser die gr te empfangene Folgenummer n bergeben und eine Zuordnungsnachricht mit der Nachrichtenkennung und der endg ltigen Folgenummer n wird an alle Prozesse gesendet Empf ngt ein Prozess diese Zuornungsnachricht ndert er gegebenenfalls die Folgenummer der Nachricht und anschlie end seine eigene momentane Folgenummer n auf n max n n Sollte sich die Nachricht deren Folgenummer nun feststeht am Anfang der R ckhalte Schlange befinden wird sie ans Ende der Auslieferungsschlange eingeordnet Abbildung 3 13 zeigt ein Beispiel bei dem zwei Nachrichten m und m in eine totale Reihenfolge sortiert werden Nachteil dieser Methode ist die h ufige Kommunikation Bevor eine Nachricht ausgeliefert werden kann m ssen jeweils drei Nachrichten zwischen dem Sender und den ein
131. istoryEntry EnvironmentState elock int elock int iimestep int iimestep int updateEnvironment void Environment lt gt Anstance Environment speichert oder aktualisiert getInstance Environment Zustand Abbildung 6 8 Aufbau des Verlaufs soll die Visualisierung stattfinden Die Zeichenoperationen selbst werden von den Implementierungen den Renderern durchgef hrt von denen eine View mehrere besitzen kann Wird diese Komponente dann mittels paintComponent neu ge zeichnet wird von allen enthaltenen Renderern die draw Methode aufgerufen in der die eigentlichen Darstellungen definiert werden Der Aufbau der Ansicht und der darin enthaltenen Br cke die zwischen View und Renderer geschlagen wird wird in Abbildung 6 9 gezeigt Die Renderer erhalten das Graphics Objekt der View und verwenden diese als Zeichenfl che Einen Spezialfall stellen die AgentRenderer dar Diese besitzen eine Referenz auf einen Agenten und werden von einem weiteren Renderer verwal tet F r jeden Agenten kann ein solcher AgentRenderer verwendet werden Der Ansicht sollte aber nur der Renderer bekannt sein der diese verwaltet Innerhalb dessen Zeichenoperation werden die der einzelnen AgentRenderer aufgerufen Diese Vorgehensweise zeigt dass Renderer auch beliebig tief geschachtelt werden k nnen wenn z B diese AgentRenderer erneut mehrere Renderer beinhalten Die Visualisierung sollte zudem animiert ablaufen k nnen Eine Animation wir
132. it InitMessage message 17 if getRole ROLE_MASTER 18 Integer command new Integer 0 19 sendToAll new Message null command 20 printlin sending command command 21 22 Erh lt ein General einen Befehl vom Kommandeur nimmt er diesen zun chst in seine Liste mit den empfangenen Befehlen auf und sendet ihn an alle anderen Gener le 23 public void onReception Message message 24 commands add message getPayload 25 for int i 0 i lt getOthers length i 26 Agent general get Others i 27 if general getRole ROLE_MASTER 28 send new Response general message getPayload 8 2 Koordination und bereinstimmung 132 29 30 31 Nach Erhalt eines Befehls von einem anderen General wird der Befehl der Lis te hinzugef gt Stellt der Agent fest dass er von allen Gener len den Befehl empfangen hat f hrt er den Befehl aus den er am h ufigsten erhalten hat Um festzustellen welcher Befehl das ist wird die Hilfsmethode avg verwendet 32 public void onReception Response message 33 printin got message getSender getID 34 message getPayload 35 commands add message getPayload 36 if commands size get Others length 37 printin Doing command avg 38 39 Diese Methode soll den Befehl berechnen den ein Agent durchzuf hren hat Dabei wird gez hlt wie h ufig ein Befehl empfangen wurde
133. lasse verwendet werden Die daraus entstandene Liste kann weiterhin bearbeitet werden Die Reihenfol ge kann ber A und ge ndert werden Diese Reihenfolge k nnte bei einigen To pologiemanagern eine Rolle spielen Im Falle des TokenRing Topologiemanagers wird z B jeder Agent mit dem in der Liste folgenden verbunden 5 3 Die Oberfl che 62 Um einen Algorithmus starten zu k nnen muss mindestens ein Agent in itialisiert werden Die Initialisierung erfolgt ber eine InitMessage die als eine erste ausl sende Aktion verstanden werden kann Eine solche Nachricht kann f r jeden in der Liste ausgew hlten Agenten ber gt der Messagequeue und der Lis te die diese Nachrichten anzeigt hinzugef gt werden Aus dieser Liste k nnen die Nachrichten aber auch wieder mit entfernt werden Unterhalb der Liste mit den Initialisierungsnachrichten kann eine Verz gerungszeit angegeben wer den falls einige Agenten zu einem sp teren Zeitpunkt starten sollen Es ist auch m glich einen Agenten mehrfach zu initialisieren Hinter dem Topology Reiter Abbildung 5 13 befinden sich die eben er stellten Agenten wieder Diese stehen allerdings noch f r sich allein und m ssen nun mit den anderen Teilnehmern verbunden werden Zus tzlich k nnen hier die Positionen der einzelnen Prozesse festgelegt werden Agents Topology ke M a o userdefined Ez userdefined Tokenring E Complete Topology
134. le ROLE_MASTER 21 sendToAll new Response 22 setRole ROLE_SLAVE 23 gotRequest false 24 25 else if getState STATE_WORKING 26 gotRequest true 27 28 else 29 sendToAll message 30 gotRequest false 8 2 Koordination und bereinstimmung 120 31 32 Erh lt ein Agent einen Response erh lt er gleichzeitig das Token Hegt dieser Agent selbst einen Eintrittswunsch kann er den kritischen Abschnitt betreten Andernfalls leitet er das Token wieder weiter 33 public void onReception Response message 34 setRole ROLE_MASTER 35 if getState STATE_WAITING 36 setState STATE_WORKING 37 setTimeout 3 38 39 else 40 sendToAll message 41 setRole ROLE_SLAVE 42 gotRequest false 43 44 Der Ablauf eines Timeouts deutet dem Agenten an dass er seine Arbeit im kritischen Abschnitt abgeschlossen hat und diesen wieder verlassen kann Ist immer noch eine Anfrage eines anderen Agenten offen sendet er das Token auf den Ring 45 public void timeout TimeoutMessage timeout 46 setState STATE_NORMAL 47 if gotRequest 48 sendToAll new Response 49 setRole ROLE_SLAVE 50 gotRequest false 51 52 53 Dieser Algorithmus ben tigt auch nur Agenten dieser Klasse Es sollten min destens zwei besser noch mehr als drei Agenten eingebunden werden die den Topologiemanager TokenRing verwenden Welcher Agent dabei
135. lick in den Funktionsumfang von DisASTer zu geben werden in Kapitel 8 einige Beispiele aufgef hrt die zeigen wie mit der entstan denen Bibliothek gearbeitet werden kann DisASTer ist nicht das einzige Projekt dass sich mit der Simulation verteilter 1 Einleitung 2 Algorithmen besch ftigt hat Einige vergleichbare Projekte die zu Beginn dieser Arbeit untersucht wurden finden sich in Kapitel 9 In Kapitel 10 werden noch einmal die Ergebnisse dieser Diplomarbeit reflek tiert und ein Ausblick auf die weitere Entwicklung und den Einsatz von DisASTer gegeben 2 Aufgabenstellung 3 2 Aufgabenstellung Das Thema verteilte Algorithmen bildet einen Teil der Vorlesung verteilte Sys teme Kurz und knapp beschrieben l sen verteilte Algorithmen Probleme inner halb eines verteilten Systems Was genau unter diesem Begriff zu verstehen ist wird im n chsten Kapitel genauer erkl rt Verteilte Algorithmen sind bei dem immer h ufigeren Einsatz von Netzwerken und dementsprechend auch dem Internet allgegenw rtig Allerdings agieren sie h ufig im Hintergrund und ohne Kenntnis der Benutzer Dabei handelt es sich um Mechanismen die zun chst sehr schwer zu verstehen sind Praktische bungen sind bislang nur sehr umst ndlich zu l sen da der Aufwand sie zu realisieren sehr hoch ist Dadurch f rdern diese bungen nicht gerade dem Verst ndnis sondern schrecken eher ab Ein Bild sagt mehr als tausend Worte Dieses Spri
136. lock 10 55 setState STATE_NORMAL 56 answers 0 buffer iterator i hasNext 57 for Iterator i 58 Agent agent Agent i next 8 2 Koordination und bereinstimmung 123 59 send new Response agent new Integer clock 60 i remove 61 62 63 Dieser Algorithmus arbeitet ausschlie lich mit Agenten dieser Klasse Die eingebunden Agenten sollten ber die CompleteTopology miteinander verbunden werden Interessant w re in diesem Fall die gleichzeitige Initialisierung mehrerer Agenten Wahl Algorithmus von Maekawa Maekawas Algorithmus hnelt dem von Ricart und Agrawala Er teilt die Prozesse allerdings in Teilgruppen auf um die Kommunikation zu reduzieren Die genaue Beschreibung des Algorithmus befindet sich in Abschnitt 3 3 1 ab Seite Seite 19 Ein Agent der diesen Algorithmus implementiert besitzt eine boolsche Va riable die anzeigt ob er schon einem anderen Agenten die Zusage gemacht hat den kritischen Abscnitt zu betreten Des weiteren hat er einen Puffer um weitere Anfragen zu speichern und einen Z hler der die eingegangenen Antworten z hlt public class MaekawaAgent extends Agent private boolean voted private Arraylist buffer private int answers public Maekawaigent description Maekawa getID buffer new Arraylist 1 2 3 4 5 6 7 8 9 voted false 10 Mit der Initialisierung wird der Eintrittswunsch ausgel st Dabei wird eine An
137. lt des Ausgabestroms sofort wieder einzulesen Ein kleines Problem dabei ist dass hier eine Verklemmungsgefahr besteht wenn sich Lesen und Schreiben gegenseitig behindern Aus diesem Grund wird die Leseoperation in einem separaten Thread ausgef hrt Das Verfahren aktuelle Zust nde der Umgebung zu speichern und einzule sen wird im Programm zus tzlich bei den Einstellung verwendet Sobald die vorgenommen Einstellungen mit OK best tigt werden wird eine Kopie der dort erstellten Umgebung auf die tats chliche Umgebung bertragen Um einen schnellen und einfachen Zugriff auf diese Kopien zu erhalten wurde das Ent wurfsmuster Fabrikmethode gew hlt Hierbei stellt die sogennante Fabrik eine statische Methode bereit die ein solches Objekt zur ckliefert Diese Methode wird als Fabrikmethode bezeichnet Dadurch bleibt den Objekten die auf diese serialisierten Zust nde der Umgebung zur ckgreifen erspart diesen umst ndli chen Vorgang mit den Str men selbst durchzuf hren vgl Gamma et al 96 S 115ff Letzendlich kann der Zustand der Umgebung in einer Datei abgespeichert werden Das erm glicht den schnellen Aufruf eines Algorithmus ohne ihn jedes mal neu zu konfigurieren Im Falle der Auslagerung der Umgebung in eine Datei wird zus tzlich der Verlauf gespeichert Im Falle des Verlaufs und der Einstellun gen ist dies nicht n tig und w rde unn tigen Speicher verbrauchen 7 7 Verteilung mit Ant 101 7 7 Vert
138. m und verunstaltet so sind viele Swing Programme Aber dagegen kann man was tun und zwar schnell so Lentzsch weiter Lentzsch03 S 31 Dass Swing als h sslich erachtet wird liegt wohl haupts chlich am Look and Feel Zur Darstellung der einzelnen Ober fl chenelemente verwendet Swing die plugable Look and Feels Diese lassen sich zu Begin einer Anwendung bestimmen oder sogar w hrend dem Verlauf ndern Standardm ig ist das Metal Look and Feel eingestellt was mit beissenden Far ben und einer unfreundlichen Oberfl che ausgestattet ist Dass Swing langsam ist liegt daran dass es im Gegensatz zu AWT oder SWT plattformunabh ngig ist und nicht auf native Elemente zur ckgreift Allerdings r ckt dieser Angriffs punkt bei der Rechenleistung heutiger Computer immer weiter in den Hintergrund und stellt nicht mehr wirklich ein Hindernis f r den Einsatz von Swing dar Ein weiterer Knackpunkt ist die komplizierte Erstellung von grafischen Benutzero berfl chen mit Swing Die meisten GUI Designer helfen dabei nur bedingt Hier treten sehr oft dann Probleme auf wenn der Entwickler die generierten Ober fl chen manuell ndern m chte da diese Designer mit eigenen Konfigurationen arbeiten und sobald diese ge ndert werden kann der n tzliche Helfer nichts mehr mit der vorliegenden Oberfl che anfangen Eine Oberfl che in Swing per Hand zu erstellen erfordert hingegen ein gewisses Ma an Erfahrung was zun chst einige Zeit in Anspruch
139. me ter bergabe m glich ist Ein Konstruktoraufruf mit Parametern erfolgt ber die Constructor Objekte Die Erzeugung neuer Objektinstanzen ber die Reflection API findet in Di sASTer sehr h ufig ihre Anwendung Oberfl chlich gesehen scheint sich dieser Vorgang zun chst nur auf das Laden systemfremder Klassen zu beschr nken jedoch geht die Anwendug weit dar ber hinaus Jede Nachricht die ein Agent versendet wird zun chst mit Hilfe der Reflection API kopiert indem eine neue Instanz der Klasse dieser Nachricht erzeugt wird und die Attribute bernommen werden F r dieses Vorgehen sprechen zwei wichtige Gr nde 7 4 Reflection und Pseudopolymorphismus 97 1 Broadcast Ein Agent besitzt die M glichkeit eine Nachricht an alle sei ne erreichbaren Nachbarn zu senden Diese Art der Kommunikation kann man als simulierten Broadcast oder besser noch als simulierten Multicast bezeichnen Dabei muss er nur eine einzige Nachricht angeben trotzdem erh lt jeder andere Agent der mit ihm verbunden ist diese Nachricht Ge nauer gesagt bekommt keiner wirklich die urspr nglich gesendetet Nach richt sondern jeder bekommt eine Kopie Damit ist sichergestellt dass nicht jeder Agent gleichzeitig auf dasselbe Objekt zugreift Eine Alterna tive zu dieser Methode w re die berschreibung der clone Methode durch den Anwender Um ihm diese Arbeit aber zu ersparen wird die Re flection AP verwendet 2 Weiterleitung Erh lt ein
140. n Eine Beschreibung dieses Ent wurfsmusters findet sich ebenfalls bei der Gang of Four vgl Gamma et al 96 S 257ff In diesem Entwurf findet sich eine vierte Komponente die Grafi sche Benutzeroberfl che GUI des Programms Da die anderen drei Komponen ten m glichst unabh ngig voneinander arbeiten sollen und das soweit m glich ohne eine grafische Benutzeroberfl che wurde eine vierte hinzugef gt Diese hat Zugriff auf die anderen drei Komponenten In der urspr nglichen Idee des MVC Musters w rde die Aufgabe der grafischen Benutzeroberfl che auf die Ansichten zur ckfallen Da f r dieses Programm aber die Visualisierung eine wichtige Rolle spielt wurde sie getrennt von der brigen grafischen Oberfl che betrachtet und entworfen Abbildung 6 1 zeigt den Aufbau der hier verwendeten Variante des MVC Paradigmas Controller Abbildung 6 1 MVC Modell Aus dem Diagramm wird ersichtlich dass sowohl Controller als auch die Views mehrere sind m glich auf die Daten des Modells zugreifen Sobald der Control ler eine nderung am Modell vorgenommen hat benachrichtigt er die Ansichten und nicht wie blich das Modell Diese Vorgehensweise h ngt mit der Art der Visualisierung zusammen da der Controller zus tzlich f r die Regelung der Ani mationen zust ndig ist Die nderung des Modells findet bereits vor dem Ablauf einer Animation statt und w rden folglich nur einmal den Ansichten mitgeteilt werden Diese sollen sich
141. n Agenten besitzt ein Agent die M g lichkeit sich selbst Nachrichten zu schicken um gewisse Aktionen aus eigener Hand zu starten F r diesen Zweck wurde ein spezieller Nachrichtentyp der Ti meout disaster model TimeoutMessage bereitgestellt Die folgenden Me thoden f hren zum Senden eines Timeouts setTimeout int duration mit dieser Methode sendet der Agent ei ne Timeoutnachricht an sich selbst die nach der angegebenen Zeit an kommt Dadurch kann eine geplante Aktion zu einem sp teren Zeitpunkt ausgef hrt und der entsprechende Agent schlafen gelegt werden Dieser Mechanismus sollte als Ersatz f r Thread sleep verwendet werden da sich Thread sleep auf die Systemzeit und nicht auf die Simulationszeit bezieht Zu beachten w re hier allerdings dass der Agent zwischen dem Senden und dem Empfangen eines Timeouts weitere Aktionen durchf hren kann setTimeout Object payload int duration mit dieser Methode be kommt der Agent ebenfalls eine Auszeit kann sich aber selbst noch ein bestimmtes Objekt zusenden was er dann nach der angegebenen Zeit er h lt Im Gegensatz zu den vorangegangenen sende Methoden muss zum Senden eines Timeouts kein Empf nger festgelegt werden da die Nachricht an den Sender zur ckkommt Es ist aber auch m glich eine Timeoutnach richt an einen anderen Agenten zu senden Dies geschieht dann ber die einfache sende Methode send Message bzw send TimeoutMessage Nachdem bekannt ist
142. n Fortschritt der Animation in einem Zeitschritt an Die draw Methode wird pro Zeitschritt mehrfach aufgerufen wobei sich der Wert von progress gleich m ig von 0 0 bis 1 0 erh ht Wird keine Animation verwendet hat progress den Wert 1 0 Zur Veranschaulichung wird ein kleines Beispiel gezeigt dass eine Linie w hrend eines Zeitschritts in der Mitte des Renderers zeichnet die mit jedem Animationsschritt l nger wird und nach Ablauf der Animation am rechten Rand des Renderers angekommen ist public void draw Graphics g double progress int yPosition y height 2 int linewidth x int width progress g drawLine x yPosition linewidth yPosition Bei einer Animation wird diese Methode sehr oft hintereinander ausgef hrt wo bei sich progress st ndig erh ht Je h her der Wert von progress wird desto l nger wird die Linie Auf diesem Weg k nnen viele Vorg nge durch Bewegungen veranschaulicht werden Um bestimmte Einstellungen an einem Renderer vorzunehmen wird eine Swing Komponente verwendet Die Methode showRendererPreferences der Klasse Renderer soll diese Komponente zur ckliefern Die Einstellungen die hier vor genommen werden k nnen unterscheiden sich von Renderer zu Renderer Eine m gliche Einstellung w re z B eine Farbwahl f r den Zustand eines Agenten oder eine Linienart f r Verbindungen An dieser Stelle steht es aber frei welche Einstellungen letztendlich zur Verf gung gestellt werd
143. n Klassen in dieses Verzeichnis gelegt werden doc neben dem Benutzerhandbuch findet sich in diesem Ordner nun auch die APl Dokumentation aller Klassen 5 1 2 Systemvoraussetzungen Um DisASTer zu verwenden wird eine Java Runtime Environment bzw ein Ja va 2 Software Developement Kit der Version 1 4 oder h her vorausgesetzt Der Rechner auf dem das Programm eingesetzt wird sollte folglich die System voraussetzungen besitzen die auch schon f r die Laufzeitumgebung vorgeschla gen werden das bedeutet ein Prozessor mit mindestens 166MHz und einen Ar beitsspeicher von 48 MB Um die Quellcode Version zu installieren wird Ant von Apache in der Version 1 5 oder h her vorausgesetzt Die vollst ndige Installation von DisASTer ben tigt mindestens 16 MB freien Speicher auf der Festplatte 5 1 3 Installation und Start Bei beiden angebotenen Versionen ist die Installation einfach und in nur wenigen Schritten abgeschlossen 1 Die bereits vollst ndige Version muss nur in ein beliebig w hlbares Ver zeichnis entpackt werden 2 Um aus der Quellcode Version das vollst ndige Programm zu erzeugen wird Ant von Apache eingesetzt Sollte sich der ant Befehl im Pfad befin den gen gt es in das Verzeichnis zu wechseln in dem die Version entpackt http ant apache org 5 2 Die Bibliothek AT wurde und den Befehl ant auszuf hren Andernfalls muss beim Aufruf des ant Befehls das enthaltene Antskript build xml bergeben we
144. n und bereinstimmung Ein schwieriges Problem in verteilten System ist die Koordination oder die ber einstimmung der einzelnen Prozesse Eine zentrale Kontrollinstanz w rde dieses 3 3 Koordination und bereinstimmung 16 Problem beseitigen allerdings wollte man sich eine zeitlang nicht auf eine sol che verlassen und es sind Algorithmen entstanden die diese Probleme auch ohne einen zentral agierenden Koordinator beseitigen k nnnen Die Problematik der Koordination und bereinstimmung wird in mehrere Teilbereiche untergliedert Hierzu geh ren der wechselseitige Ausschluss die Wahl eines Anf hrers die Festlegung der Nachrichtenreihenfolge und die Behebung von bereinstimmungsproblemen die alle in den folgenden Abschnitten erl utert werden 3 3 1 Verteilter wechselseitiger Ausschluss Das Problem des verteilten wechselseitigen Ausschluss umfasst den Zugriff meh rerer Prozesse auf ein und dieselbe Ressource Es wird auch als kritischer Abschnitt Problem bezeichnet Um hier die Konsistenz sicherzustellen darf im mer nur ein Prozess auf diese Ressource zugreifen oder nur ein Prozess den kritischen Abschnitt betreten Im Folgenden werden einige Algorithmen vorgestellt die dieses Problem ohne eine zentrale Kontrollinstanz z B in Form eines Servers l sen Dabei wird eine Abstimmung der einzelnen Prozesse untereinander angestrebt An die Algorith men werden bestimmte Anforderungen gestellt MEI Sicherheitsaspekt
145. ne Zusage und die gew hlt Markierung wird auf true gesetzt 2 Befindet sich keine Anfrage in der Warteschlange wird die gew hlt Markierung auf false gesetzt Abbildung 3 7 zeigt ein Beispiel f r den Ablauf des Verfahrens von Maeka wa Bei Betrachtung dieses Beispiels wird deutlich dass f r den Eintritt in den kritischen Bereich 2 K 1 Nachrichten und f r den Austritt K 1 Nach richten ben tigt werden Tritt der Optimalfall ein dies ist bei N gt 4 der Fall beschr nkt sich die Bandbreite f r Ein und Austritt des kritischen Bereichs auf 3YN Nachrichten Gruppeneinteilung ack kritischer Abschnitt en en kritischer Abschnitt Abbildung 3 7 Wechselseitiger Ausschluss nach Maekawa Bei diesem Verfahren besteht allerdings Verklemmungsgefahr Abbildung 3 8 zeigt ein solches Szenario bei dem alle vorhandenen Prozesse den kritischen Abschnitt gleichzeitig betreten m chten Dadurch dass sie nur ber eine Stimme verf gen k nnen sie jeweils nur einer Anfrage zustimmen Um den kritischen Abschnitt zu betreten sind aber zwei Antworten n tig auf die jeder Prozess vergebens wartet Mit Hilfe eindeutiger logischer Uhren Abschnitt 3 1 2 l sst sich die Verklemmungsgefahr beseitigen vgl Coulouris et al 02 S 498ff 3 3 Koordination und bereinstimmung 21 P Ps Ps Gruppeneinteilung a Pe req Laren eq ack ack ee ack Wartet au
146. nem verteilten System existiert Verteilte Verklemmungserkennung Distributed Deadlock Recognition Erkennen einer Verklemmung durch z B gegenseitiges Warten zweier Pro zesse Verteilte Terminierungserkennung Distributed Termination Detection Erkennen der Beendigung eines verteilten Algorithmus durch Passivit t aller Prozesse Diese Passivit t kann auch nicht mehr aufgehoben werden Verteiltes Debugging Um einen konsistenten globalen Zustand Z zu garantieren muss falls ein Ereignis f enthalten ist auch das Ereignis e in Z enthalten sein sofern sich e zeitlich vor f ereignet hat Diese zeitlich vor Beziehung wird mit Hilfe logischer Uhren siehe Abschnitt 3 1 2 festgelegt D h f E ZAL e lt L fJ gt eeZ Abbildung 3 5 zeigt einen nach dieser Definition inkonsistenen und einen kon sistenten Zustand vgl Coulouris et al 02 S 466ff inkonsistent konsistent P j P2 Abbildung 3 5 Inkonsistenter und konsistenter globaler Zustand Schnappschuss Algorithmus von Chandy und Lamport Chandy und Lam port verfolgen das Ziel einen konsistenten globalen Zustand eines verteilten Systems mit Hilfe eines virtuellen Schnappschusses aufzuzeichnen Der Algo rithmus unterteilt das verteilte System in dem er eingesetzt wird in Prozesse und Kommunikationskan le zwischen diesen Prozessen Hierbei werden folgende Anforderungen gestellt Kan le und Prozesse sind fehlerfrei Die Kommunikation
147. nen hohen Grad an Erweiterbarkeit besitzen Es sollten m glichst viele Algorithmen verwirklicht werden k nnen Das setzt entweder eine sehr umfangreiche oder eine sehr allgemein gehaltene Bibliothek voraus Eine allgemein gehaltene Bibliothek gibt dem Benutzer eher die M glichkeit Erweiterungen vorzunehmen und ist auch schneller 2 Aufgabenstellung 4 verstanden Einziger Nachteil ist dass der Programmieraufwand und die hierf r n tige Eigeninitiative ein wenig ansteigt Sind die Anforderungen an die zu entwerfende Bibliothek doch eher abstrakt werden die Anforderungen an das Programm schon ein wenig konkreter Das Programm sollte eine gute Ergonomie besitzen Anordnung und Funk tionsweise der Oberfl chenelemente sollten dem aus anderen Programmen blichen Aufbau entsprechen Der Anwender sollte Elemente oder Struk turen vorfinden die ihm allgemein bekannt sind um eine schnelle und intuitive Bedienung zu garantieren Das Erstellen der verteilten Systeme in denen die Algorithmen eingesetzt werden sollte ebenfalls m glichst einfach und intuitiv erfolgen Am besten w re eine grafische Darstellung des Systems beispielsweise in Form der Topologie eines Netzwerks Um auf die erstellten Systeme jederzeit zugreifen zu k nnen und um sie nicht bei jedem Programmaufruf neu konfigurieren zu m ssen sollten sie gespeichert werden k nnen Die gespeicherten Systeme bzw Algorithmen k nnen dadurch auch ausgetauscht und auf and
148. ommen ist erh lt dieses Attribut den Zeitpunkt der tats chlichen Auslieferung 4 3 Kontrolle und Steuerung 37 payload in dem sich die Informationen befinden die ein Agent einem anderen mitteilen oder bergeben m chte W rden die Nachrichten sofort von ihrem Sender zum Empf nger geleitet g be es f r den Benutzer keine M glichkeit in den Ablauf der Simulation einzu greifen Aus diesem Grund wird die MessageQueue eine Warteschlange in die die gesendeten Nachrichten eingereiht werden eingef hrt Mit Hilfe dieser Mes sageQueue wird eine Steuerung der Kommunikation m glich Die Arbeitsweise der MessageQueue wird in Abbildung 4 2 dargestellt P P2 P Pa MessageQueue MessageQueue m m lt SP R P st 1 rtt1 gt lt S P R P stt 2 re rt m m lt SP R P sit 1 rt 1 gt lt SP R P st 1 rtt1 gt m lt SP R P stl rt 1 gt Zeitpunkt t Zeitpunkt t 1 Abbildung 4 2 MessageQueue Zun chst wird auf die automatische Steuerung der MessageQueue eingegan gen Diese erlaubt dem Benutzer den erstellten Algorithmus wie einen Film ab laufen zu lassen Dabei stehen ihm Steuerbefehle wie Start Stopp Pause oder Einzelschritt sowie der Zugriff auf den bisherigen Verlauf der Simulation um diesen zur ck zu spulen zur Verf gung Abgesehen von Nachrichten denen ei ne Wunschauslieferungszeit bergeben wurde wird die MessageQueue nach dem FIFO
149. ormationen geh ren die Anzahl der Agenten der Nachrichten in der MessageQueue die Anzahl der bereits ausgelieferten Nachrichten oder die aktuelle Simulationszeit ToolBar bietet eine Auswahl der wichtigsten Befehle des Hauptmen s Hierzu geh ren Laden Speichern oder der Aufruf der Einstellungen Preferences sind Oberfl chen um die Simulationsumgebung einzurichten und zu bearbeiten sowie die Ansichten anzupassen AgentComponent diese wurden bereits in Abschnitt 6 3 im Abschnitt ber die Agenten vorgestellt Sie werden vom Hauptfenster verwaltet und in den AgentMessageQueue Fenstern dargestellt die sp ter erl utert werden ConsolePane beinhaltet die Standardausgabe System out und die Stan dardfehlerausgabe Systen err Desktop diese Komponente nimmt den Gro teil der Anwendung in An spruch Auf dem Desktop finden sich viele weitere Fenster die wichtige Informationen beinhalten Der Inhalt dieser Fenster wird im folgenden Ab schnitt vorgestellt Auf dem Desktop finden sich Unterklassen der Klasse JInternalFrame die sog InfoFrames Sie besitzen einen Men eintrag JMenultem das dem Hauptmen MenuBar der Anwendug bergeben wird um dieses Fenster aufzurufen Falls mehrere Fenster zusammen geh ren k nnen diese in eine InfoFrameGroup auf genommen werden Eine solche Gruppe wird als ein Untermen im Hauptmen aufgef hrt wobei alle Fenster dieser Gruppe einzeln oder gemeinsam aufgerufen und dargestellt werd
150. ortClock 10 send new Integer lamportClock get Others 0 11 12 println sending Message to getOthers 0 13 at lamportClock 14 Schlie lich fehlt noch die Ereignisbehandlung nach dem Eintreffen einer Nach richt Hierbei wird nach LC2 b die empfangene Zeit mit der eigenen verglichen und die eigene Uhr auf das Maximum dieser beiden Werte gesetzt Anschlie end wird die Zeit laut LC1 erh ht bevor die Nachricht in Form einer Textausgabe weiterverarbeitet werden kann 15 public void onReception Message message 16 int rlc Integer message getPayload intValue 17 18 lamportClock Math max lamportClock rlc 19 lamportClock 20 printin received lt message getSender rlc 21 gt at lamportClock 22 23 Um diesen Algorithmus vern nftig in DisASTer ablaufen zu lassen sollten mindestens zwei dieser Agenten verwendet und miteinander verbunden werden CompleteTopology In diesem Fall w rden sich auch mehrere Initialisierungen eines Agenten lohnen oder eine abwechselnde Initialisierung aller Agenten Eindeutige Lamport Uhr Mit der einfachen Lamport Methode lassen sich von einander unabh ngige Ereignisse nicht unbedingt in eine Beziehung bringen sofern diese denselben Wert aufweisen Um die Lamport Uhr eindeutig zu ma chen wird dem Z hler die Kennung des Prozesses zugef gt Anstatt den Z hler 8 1 Logische Uhren 113 immer um eins
151. ozessen zu beobachten Sollte es aber unerwarteter Weise zu Leis tungseinbu ungen kommen k nnen die Animationen auch ausgeschaltet werden Manuelle Steuerung Der automatische Ablauf eines Algorithmus kann oft sehr praktisch sein Wie bereits oben beschrieben ist die M glichkeit gegeben die Simulation auf Handsteuerung umzuschalten Diese Art der Steuerung geschieht ber die AgentMessageQueues die nach Auswahl des manuellen Modus sichtbar werden Abbildung 5 8 auf Seite 59 zeigt bereits eine solche AgentMessageQueue Funktionen der AgentMessageQueues sind Ib Next hnlich zur automatischen Steuerung sorgt dieser Befehl daf r dass die oberste Nachricht in der Liste ausgeliefert wird Es spielt dabei auch keine Rolle ob ein sp terer Zeitpunkt f r das Ausliefern dieser Nach richt vorgesehen ist Das ist eine M glichkeit den Ablauf des Algorithmus durcheinander zu bringen Delete mit diesem Befehl wird die ausgew hlte Nachricht gel scht Dieser Schritt kann durch 4l auch wieder r ckg ngig gemacht werden 5 3 Die Oberfl che 70 A Up um die Nachrichtenreihenfolge zu ndern denn es wird immer zuerst die oberste Nachricht ausgeliefert k nnen Nachrichten nach oben oder Down nach unten verschoben werden Wird die Ober bzw Untergrenze der Liste erreicht wird die Nachricht am anderen Ende eingereiht Aller dings muss hier beachtet werden dass das ndern der Reihenfolge in einer AgentMessage
152. pf nger eine eigene Wahl 2 Stellt ein Prozess fest dass er die h chste ID im System hat z B dadurch dass er keine Antwort von einem Prozess mit h herer ID erhalten hat sendet er eine Koordinatornachricht an alle anderen Prozesse um ihnen dies mitzuteilen 8 2 Koordination und bereinstimmung 129 Bei der Implementierung eines Agenten der einen Anf hrer mit Hilfe des Bully Algorithmus bestimmen soll wird zun chst eine Konstante TIMEOUT festgelegt die festlegt wie lange ein Agent bzw dessen Antwort Zeit hat bevor dieser als ausgefallen gerechnet wird Die ausgefallenen Agenten sollen in der Liste corrupted aufgef hrt werden public class BullyAgent extends Agent public static final int TIMEOUT 5 1 2 3 4 private ArrayList corrupted 5 private int inits 6 private Agent leader 7 8 9 public BullyAgent description Bully getID 10 corrupted new ArrayList 11 Die Initialisierung eines Agenten ist gleichzusetzen mit der Initiierung der Wahl Im Gegensatz zu den bisherigen Verfahren kann die Wahl eines Agenten auch durch andere Agenten erfolgen Der Sender einer solchen Initialisierungsnachricht bekommt dann eine Antwort von ihrem Empf nger um diesem mitzuteilen dass er nicht ausgefallen ist Falls der Agent noch keine eigene Wahl initiiert hat und er selbst nicht der neue Anf hrer ist beginnt er eine neue Wahl und sendet eine Initialisierungsnachricht an alle A
153. ption Server 8 setRole ROLE_MASTER 9 buffer new ArrayList 10 voted false 11 12 else 13 description CentralServerAgent getID 14 15 Den Wunsch den kritischen Abschnitt zu betreten wird durch die Initialisierung ber die init Methode ausgel st Dabei muss der Agent feststellen wer der zentrale Server ist um ihm seine Anfrage zu senden bzw falls der Agent selbst der zentrale Server ist muss er feststellen ob er selbst den kritischen Abschnitt betreten darf oder nicht 16 public void init InitMessage message 17 if getState STATE_WORKING getState STATE_WAITING 8 2 Koordination und bereinstimmung 117 18 return 19 setState STATE_WAITING 20 21 if getRole ROLE_MASTER 22 for Iterator iter connections keySet iterator 23 iter hasNext 24 Agent agent Agent iter next 25 if agent getID 0 26 send new Request agent 27 return 28 29 30 31 else 32 if buffer isEmpty amp amp voted false 33 setState STATE_WORKING 34 setTimeout 3 35 36 else 37 buffer add this 38 39 40 Erh lt der zentrale Server nun eine Anfrage den kritischen Abschnitt zu betreten berpr ft er zun chst ob dieser frei ist und ob nicht schon Anfragen gestellt wurden Ist dies nicht der Fall kann er dem anfragenden Agenten sein OK geben und merkt sich dass der kritische
154. r disaster model TopologyManager Sie legen fest welche Agenten miteinander verbunden werden und welche nicht Zus tzlich kann ein Topologiemanager die Positionen dieser Agenten festlegen 5 2 Die Bibliothek Age wobei diese bisher ausschlie lich f r die Visualisierung durch die Topologiean sicht verwendet werden In DisASTer sind bereits zwei solche Topologiemanager zu finden 1 Zum einen die CompleteTopology die jeden Agenten mit jedem anderen verbindet In dieser Topologie erreicht jeder Agent alle anderen ber die Broadcastadresse 2 Zum anderen der TokenRing der die Agenten ringf rmig anordnet Die Kommunikation in einem Token Ring verl uft in der Regel nur einseitig Um dieses Verhalten zu erreichen verwendet der TokenRing eine eigene Connection Klasse die nur eine einseitige Kommunikation zul sst Um ei ne Nachricht auf diesen Token Ring zu senden muss die Broadcastadresse verwendet werden Mit ihr wird versucht eine Nachricht an alle benachbar ten Agenten zu senden Da das in diesem Fall aber nur in einer Richtung zugelassen wird erreicht die gesendete Nachricht nur den direkten Nach barn in Ringrichtung Auch hier steht es dem Benutzer offen eigene Verbindungen oder sogar eigene Topologiemanager zu verwenden Bei den Verbindungen wird dieser Schritt aber nicht n tig sein Da ein Objekt der Klasse Connection im Grunde nur verwendet wird um eine Verbindung zwischen zwei Agenten herzustellen ist sie f r ein w
155. r AgentComponent ConsolePane Preferences 0 1 JMenultem from javax swing InfoFrame InfoFrameGroup Systemklasse A JinternalFame Vom Benutzer from javax swing K erweiterbar MessageQueuelnfoFrame SentMessagesinfoFrae ConsolelnfoFrame ViewinfoFrame AgentMessageQueuelnfoFrame Abbildung 6 12 Aufbau der grafischen Oberfl che Wesentliche Bestandteile des Hauptfensters sind MenuBar das Men in dem sich alle wichtigen Men eintr ge wie das Laden oder Speichern der Umgebung der Aufruf der Informationsfenster oder der Einstellungen sowie der Online Hilfe befinden Da einige der hier befindlichen Befehle auch ber die ToolBar zug nglich sind werden sie als Singleton bereitgestellt ControlPane besitzt alle Kn pfe die f r das Steuern der Simulation be n tigt werden Darunter fallen die Kn pfe um die Simulation zu starten anzuhalten zu pausieren sie mittels Einzelschritt ablaufen zu lassen oder im Verlauf zur ck zu gehen Desweiteren kann hier die Geschwindigkeit und die Simulationsart eingestellt werden 6 6 Grafische Benutzeroberfl che GUI 89 StatusBar diese schmale Leiste am unteren Rand des Fensters der An wendung gibt einen kurzen berblick ber den Zustand der Umgebung Zu diesen Inf
156. ragen wird Der Aufbau des AgentLog findet sich in Abbildung 6 7 Die Speicherung der einzelnen Umgebungszust nde in einem Verlauf siehe Abbildung 6 8 wird hnlich wie das Agentlog behandelt Es handelt sich da bei um eine Liste aus Eintr gen die aus der Zeit zu der sie erstellt wurden und dem derzeitigen Zustand des Systems bestehen Ein solcher Zustand wird mit Hilfe der Klasse EnvironmentState serialisiert Diese zus tzliche Klasse ist notwendig da das Environment selbst nicht serialisiert werden kann und auch nicht soll Durch den h ufigen Einsatz von Observern m ssten diese ebenfalls serialisiert werden Dadurch w rde die Dateigr e der abgespeicherten Umge bungen nur unn tig anwachsen Teilweise sind hier auch Klassen betroffen die nicht so einfach bzw gar nicht serialisiert werden k nnen da es sich um nicht serialisierbare Klassen aus dem Javasytem handelt Aus diesem Grund speichert die Klasse EnvironmentState alle notwendigen Komponenten des Modells wie die MessageQueue die Topologie usw ber diese Klasse wird ebenfalls ein kom pletter Algrithmus abgespeichert der dann in eine Datei serialisiert wird Um 6 4 View 83 ArrayList from java util Object from java lang Systemklasse Vom Benutzer E erweiterbar AgentLog AgentLogEntry addAgentLogListener listener AgentLogListener boolean removeAgentLogListener listener AgentLogListener boolean AgentLogListener S
157. rde bereits in Abbildung 4 4 auf Seite 39 dargestellt und im entsprechenden Abschnitt erl utert DisASTer stellt bereits zwei separate Ansichten zur Verf gung die einen Algorithmus aus zwei unterschiedlichen Perspektiven darstellen Bei diesen Ansichten handelt es sich zum einen um die Ablaufansicht disaster view SequenceView die den zeitlichen Ablauf des Algorithmus in Form eines Sequenzdiagramms darstellt Da neben ist die Topologieansicht disaster view TopologyView zu finden deren Schwerpunkt auf der Darstellung der Beziehungen der einzelnen Agenten un tereinander sowie auf der animierten Visualisierung der Nachrichten liegt F r diese Ansichten gibt es bereits viele Einstellungsm glichkeiten die Darstellung nach eigenen W nschen anzupassen Durch die Verwendung unterschiedlicher Farben und Formen werden z B die Zust nde und Rollen der Agenten in der Visualisierung umgesetzt siehe dazu auch Abschnitt 5 3 3 Aber auch hier ist der Anwender nicht auf die bestehende Auswahl angewie sen Wenn andere Teile einer Simulation wie z B die Messagequeue in die Vi sualisierung mit integriert oder einfach nur bestehende Teile individuell angepasst werden sollen steht es frei eigene Renderer zu implementieren Ein Renderer be steht im wesentlichen aus drei Komponenten 1 seiner Position und seinen Abmessungen die mit x y width height und den entsprechenden Zugriffsmethoden definiert werden 2 einer draw Methode in der die Ze
158. rden Die Anwendung kann nun ber die enthaltenen Shellskripte DisASTer bat DisASTer sh gestartet werden Alternativ hierzu gen gt ein Doppelklick auf die Datei disaster jar im lib Verzeichnis falls das verwendete Betriebssystem den java jar bzw javaw Befehl mit diesem Dateityp verkn pt hat 5 2 Die Bibliothek In den folgenden Abschnitten wird die Klassenbibliothek vorgestellt mit deren Hilfe ein Entwickler schnell in der Lage sein soll eigene verteilte Algorithmen zu implementieren In Abschnitt 5 2 1 wird die Klasse Agent vorgestellt Dort wird beschrieben welche Methoden und Mechanismen angeboten werden die das Verhalten eines Teilnehmers eines verteilten Algorithmus bestimmen In Ab schnitt 5 2 2 wird gezeigt was es mit den Nachrichten auf sich hat und wie diese verwendet oder erweitert werden k nnen Anschlie end wird in Abschnitt 5 2 3 beschrieben welche M glichkeiten es gibt die Agenten miteinander zu ver binden um die Kommunikation zu gew hrleisten Zuletzt werden die Ansichten vorgestellt und erkl rt wie diese erweitert werden k nnen Um Klassen der DisASTer Bibliothek zu erweitern muss diese in den Klassen pfad der zu erstellenden Klassen eingebunden werden Hier besteht zum einen die M glichkeit die gesamte Anwendung die sich in dem Archiv disaster jar be findet einzubinden oder es kann das zur Entwicklung v llig ausreichende Archiv disaster dev jar verwendet werden Letzteres enth lt lediglich die Kla
159. rdination und bereinstimmung 131 8 2 3 bereinstimmungsprobleme Die bereinstimmungsprobleme werden in Abschnitt 3 3 4 beschrieben Diese Probleme besch ftigen sich mit der bereinstimmung korrekt laufender Prozesse trotz Einfluss von fehlerhaften Problem der byzantinischen Gener le Das Problem der byzantinischen Ge ner le ist wohl das bekannteste Beispiel f r bereinstimmungsprobleme Es geht dabei um die Auswertung eines Befehls von einem Kommandeur durch mehrere Gener le Dabei kann unter den Gener len ein Verr ter sein oder der Komman deur selbst kann fehlerhaft arbeiten In dieser Implementierung wird zum ersten Mal mehr als eine Klasse verwendet und zwar eine f r die loyalen Gener le und eine f r die Verr ter Bei beiden Klassen wird der Kommandeur durch den Agenten repr sentiert der die kleinste Kennung ID ist 0 besitzt Zun chst wird die Klasse f r die loyalen Gener le besprochen In dieser findet sich eine Liste der gesammelten Befehle commands 1 public class ByzantinicGeneral extends Agent 2 private ArrayList commands 3 4 public ByzantinicGeneral 5 if getID 0 6 description Commander 7 setRole ROLE_MASTER 8 9 else 10 description General getID 11 commands new ArrayList 12 13 Die Initialisierung besitzt nur beim Kommandeur eine Wirkung Dadurch versen det dieser seinen Befehl an alle seine Gener le 16 public void in
160. richten Die logische Lamport Uhr l sst sich mit zwei einfachen Regeln beschreiben LC1 L wird inkrementiert bevor ein Ereignis in Prozess p veranlasst wird Li Li 1 LC2 a Wenn ein Prozess p eine Nachricht m sendet gibt er m auch den Wert t L mit b Beim Empfang von lt m t gt berechnet ein Prozess p den Wert L maz L t und wendet dann LC1 an bevor er dem Ereignis receive m einen Zeitstempel zuweist Im Folgenden wird die Implementierung eines Prozesses beschrieben der eine Lamport Uhr verwendet Hierzu wird eine neue Klasse erzeugt die die Klasse Agent erweitert Die Lamport Uhr wird durch ein Integer Attribut lamportClock repr sentiert das im Konstruktor mit 0 initialisiert wird 1 public class LamportClockAgent extends Agent 2 private int lamportClock 3 8 1 Logische Uhren 112 public LamportClockAgent lamportClock 0 description LamportClockAgent getID so ur Dieses Beispiel beschr nkt die Anzahl der m glichen Ereignisse auf zwei 1 Das Senden einer Nachricht 2 Das Empfangen einer Nachricht Durch die Initialisierung eines Agenten sendet dieser eine einfache Nachricht des Typs Message mit seinem momentanen Zeitstempel LC2 a an seinen ersten Nachbarn getOther 0 Vor diesem Ereignis muss er laut LC1 seine Uhr inkrementieren Zus tzlich wird das Ereignis in einer Textausgabe festgehalten 8 public void init InitMessage message 9 lamp
161. rst tzt wird Dieser Modus wird zur Synchronisierung innerhalb eines LANs oder zwischen benachbarten LANs verwendet Die Arbeitsweise dieses Modus hnelt erneut der Methode Christians Nach einer Anforderung sendet ein Server seinen eigenen Zeitstempel Symetrische Modus sorgt f r die Synchronisierung der Server untereinan der Hierbei synchronisieren sich Server einer Hierarchieebene untereinan der um vor allem in den niedrigeren Schichten eine hohe Genauigkeit zu garantieren und diese auf l ngere Sicht aufrecht zu erhalten Der Austausch der Nachrichten ist in allen drei Modi unzuverl ssig da dort jeweils UDP eingesetzt wird vgl Coulouris et al 02 S 458ff 3 1 Physikalische und logische Uhren 10 3 1 2 Logische Uhren Wie im vorangegangenen Abschnitt gezeigt ist es sehr schwer Computer in einem verteilten System zu synchronisieren Das stellt vor allem dann ein Problem dar wenn festgelegt werden muss in welcher zeitlichen Beziehung Ereignisse zu einander stehen die auf unterschiedlichen Prozessen auftreten Mit dieser Problematik setzen sich logische Uhren auseinander In Abbildung 3 2 ist eine Ereignisabfolge in einem verteilten System zu sehen P gt a b m P2 gt c d m Ps o eo gt e f Abbildung 3 2 Ereignisabfolge in einem verteilten System Aus der Abbildung wird deutlich dass es Ereignisse gibt die wiederrum an dere Ereignisse ausl sen k nnen Dies ist bei b und c oder
162. ruh ren dar Diese wurden von Mattern und Fidge entwickelt um aus der Tatsache dass L e lt L e schlie en zu k nnen dass e e Beim Einsatz von Vek toruhren in einem verteilten System mit N Prozessen erh lt jeder Prozess einen Vektor V mit N Eintr gen wobei jeder Eintrag die einfache logische Zeit der einzelnen Prozesse beinhaltet Um Vektoruhren zu erzeugen m ssen vier Regeln befolgt werden VC1 Zun chst ist V j 0 f r i j 1 2 N VC2 Unmittelbar bevor p einem Ereignis einen Zeitstempel zuweist setzt er Vili Vili 1 VC3 p gibt jeder versendeten Nachricht den Wert t V mit VC4 Wenn p einen Zeitstempel t in einer Nachricht empf ngt setzt er V lj maz V j t j f r j 1 2 N Diese komponenetenweise Bildung des Maximalwerts f r zwei Vektor Zeit stempel wird auch als merge Operation bezeichnet Bevor dem Empfang der Nachricht ein Zeitstempel zugewiesen wird wird VC2 angewendet In Abbildung 3 4 werden die Vektor Zeitstempel der Ereignisse aus Abbil dung 3 2 gezeigt Mit dem Vektor Zeitstempel Verfahren l sst sich schnell festlegen in welcher Reihenfolge unterschiedliche Ereignisse auftreten V V amp V j V j f r j 1 2 N V lt V e Vavi f rj 1 2N V lt V SV lt V AV V 3 2 Globale Zust nde 13 1 0 0 2 0 0 P gt a b m 2 1 0 2 2 0 P2 gt c d m2 P 0gD E22 u e f Abbildung 3 4 Ereignisabfolg
163. rzeugen von JavaDoc Daneben gibt es Tasks mit denen ein Zugriff auf das Dateisystem m glich ist Dazu geh ren Kopieren Verschieben L schen und viele weitere n tzliche Befehle Zus tzlich k nnen eigene Tasks definiert werden wodurch Ant in vielen Bereichen eingesetzt werden kann Diese Tasks m ssen einer Gruppe target zugeordnet sein Eine sol che Gruppe beschreibt meist eine bestimmte Aktion Es k nnen Abh ngigkeiten zwischen den einzelnen Gruppen erzeugt werden z B kann eine Befehlsgruppe die das Erzeugen einer Jar Datei bewirken soll erst ausgef hrt werden wenn die zu archivierenden Klassen erzeugt wurden Die Befehle die zum Erzeugen dieser Klassen zust ndig sind befinden sich in einer anderen Gruppe Ein Auszug einer verwendeten build Datei wird in Listing 7 1 dargestellt lt project name DisASTer default jar gt 1 2 3 lt property name src location src gt 4 lt property name bin location bin gt 5 lt property name doc location doc gt 6 lt property name jarfile location lib disaster jar gt 7 lt property name manifest location MANIFEST MF gt 8 9 lt target name compile gt 10 lt javac srcdir src destdir bin gt 11 lt target gt 10http ant apache org Uhttp www eclipse org 7 8 Hilfesystem 102 12 13 lt target name javadoc depends compile gt 14 lt javadoc destdir doc api access protected 15 sourcepath src
164. s Singleton zur Verf gung Dieses Entwurfsmuster wurde bereits beim Modell in Abschnitt 6 3 vorgestellt 6 6 Grafische Benutzeroberfl che GUI Die grafische Benutzeroberfl che engl Grafical User Interface GUI stellt die Schnittstelle zum Benutzer her Sie bietet dem Anwender Interaktionsm glichkei ten um eine Umgebung zu erstellen zu ndern sie zu speichern oder zu laden 6 6 Grafische Benutzeroberfl che GUI 88 sie zu steuern und vor allem sie zu beobachten Um all das zu erm glichen greift die GUI sowohl auf das Modell als auch auf den Modifikator und die Ansichten zu Wie aus Abbildung 6 12 ersichtlich wird bildet die GUI eine Baumstruktur Die Wurzel stellt die Klasse MainFrame dar Die aus JFrame abgeleitete Klasse bein haltet weitere Komponenten und Container aus denen schlie lich die Anwendung entsteht F r diese Struktur wird erneut das Entwurfsmuster Composite ver wendet Damit f r jeden Programmaufruf nur ein solches Hauptfenster sichtbar wird wurde dieses ebenfalls als Singleton realisiert JMenuBar JDesktopPane JFrame JToolBar JComponent JPanel from javax swing from javax swing from javax swing from javax swing from javax swing from javax swing A A A A A A MainFrame dnstance MainFrame getlnstance MainFrame N Lo E MenuBar Desktop ControlPane StatusBar ToolBa
165. schen Abschnitt aufgehalten hat muss er noch ausstehende Anfragen beantworten 73 public void timeout TimeoutMessage timeout 74 setState STATE_NORMAL 75 if getRole ROLE_MASTER 76 if buffer isEmpty 77 voted false 78 79 else 80 Agent agent Agent buffer remove 0 81 if agent this 82 setState STATE_WORKING 83 setTimeout 3 84 85 else 86 send new Response agent 87 voted true 88 89 90 91 else 92 for Iterator iter connections keySet iterator 93 iter hasNext 94 Agent agent Agent iter next 95 if agent getID 0 96 send new Response agent 97 return 98 99 100 101 102 Voraussetzung diese Algorithmus ist dass alle Agenten miteinander verbun den sind CompleteTopology F r den Server muss auch keine separate Klasse geladen werden d h alle Agenten sind Instanzen dieser einen Klasse Es spielt keine Rolle welcher Agent wann initialisiert wird 8 2 Koordination und bereinstimmung 119 Ring basierender Ausschluss Um einen Zutritt zum kritischen Abschnitt in einer Ringstruktur zu erhalten wird im in Abschnitt 3 3 1 beschriebenen Algo rithmus ein Token um den Ring gesendet der wie als Schl ssel fungiert und den Eintritt in den kritischen Abschnitt erm glicht Bei dieser Implementierung wird der Schl ssel also das Token durch die Rolle eines Agenten definiert Der Agent der
166. se der vorangegangenen Analyse und die hnli cher Projekte Kapitel 9 verwendet um den eigenen Entwurf zu spezifizieren Als erstes wird die Sprache festgelegt Das fertige Programm sollte m glichst schnell eingesetzt werden k nnen und leicht zu bedienen sein damit sich der Anwender ganz auf die Implementierung der Algorithmen konzentrieren kann Um das zu garantieren wird keine neue Sprache entwickelt sondern eine bereits bekannte eingesetzt Hier spricht vieles f r Java Denn Java bietet eine objektorientierte plattformunabh ngige und freie L sung die zus tzlich von einer breiten Masse verwendet werden kann Gerade die Objektorientierung erlaubt eine einfache und logische Handhabung denn alle Elemente in dem simulierten Netzwerk sind als Objekt greifbar Nun gilt es den eigentlichen Algorithmus zu definieren Dieser kann wie bei DAJ oder ViSiDiA global festgelegt werden indem alle Aktionen in einer Klasse spezifiziert werden Die Logik des Algorithmus kann aber auch auf die einzelnen Teilnehmer verteilt werden indem jeder dieser Teilnehmer entscheidet wann er warum welche Aktion wie durchf hrt In diesem Fall f llt die Entscheidung f r den zweiten dezentralen Ansatz da dieser zun chst einfacher zu handhaben und verst ndlicher zu sein scheint Er l sst sich besser mit der Realit t vergleichen in der jeder Netzwerkteilnehmer selbst entscheidet wie er sich verh lt Hinzu kommt dass die meisten Algorithmen in Pseudocode defin
167. se zugeordnet wird Ein URLClassLoader braucht diese Informationen Folglich muss eine URL zu einer Klasse die in einem Package liegt wie folgt aussehen file pfad zur package JavaKlasse class Die von dem File Objekt generierte URL sieht allerdings so aus file pfad zur package JavaKlasse class Der Unterschied d rfte beim ersten Hinsehen vielleicht nicht auffallen Im ersten Fall wird das Package und die Javaklasse durch einen getrennt wie es auch vom Java Kommando bekannt ist und ben tigt wird Im zweiten Fall welcher zur Zeit noch vorliegt werden die beiden Elemente durch einen getrennt Der Versuch die gew hlte Javaklasse mit der zweiten URL zu laden w rde ei ne NoClassDefFoundError Ausnahme werfen Dieser Fehler kann aber genutzt werden um das vorliegende Problem zu beseitigen Tritt ein solcher Fehler auf 7 4 Reflection und Pseudopolymorphismus 96 wird die URL so ge ndert dass der letzte mit einem ausgetauscht wird Anschlie end wird erneut versucht die Klasse zu laden Der Vorgang wird so oft wiederholt bis das Laden erfolgreich war oder bis der letzte erste ersetzt wurde Dieser Algorithmus erlaubt das Laden von Klassen aus einer beliebig tief geschachtelten Package Struktur Ergebnis dieses Vorgangs ist ein Objekt der Klasse Class Das weitere Vorgehen mit diesem Objekt wird im n chsten Ab schnitt beschrieben 7 4 Reflection und Pseudopolymorphismus Der vorange
168. seitiger Ausschluss Der verteilte wechselseitige Ausschluss wird in Abschnitt 3 3 1 beschrieben Da bei geht es um das kritische Abschnitt Problem bei dem sich die Prozesse eines verteilten Systems darauf einigen m ssen welcher von ihnen den kritischen Abschnitt betreten darf Wechselseitiger Auschluss mit zentralem Server Beim wechselseitigen Ausschluss mit zentralem Server wird ein Prozess als zentraler Server gew hlt der von den anderen Prozessen Anfragen erh lt den kritischen Abschnitt zu betreten Fallen mehr als eine Anfrage an werden diese gepuffert und erhalten nacheinander die Zusage den kritischen Abschnitt zu betreten sobald dieser wieder frei wurde Das Problem bei der Implementierung ist die Wahl des zentralen Servers Damit diese Wahl nicht zus tzlich in den Algorithmus eingebaut werden muss wird der erste Agent der mit der ID 0 als zentraler Server festgelegt Um ihn von den anderen Agenten herauszuheben bekommt er die Rolle ROLE_MASTER zugeschrieben Dieser erh lt den Puffer der Anfragen und eine boolsche Variable die anzeigt ob der kritische Abschnitt frei ist oder nicht Auf die Implementierung des Servers in einer separaten Klasse wurde in diesem Beispiel noch verzichtet wodurch es ein wenig un bersichtlich ist 1 public class CentralServerExclusionAgent extends Agent 2 private Arraylist buffer 3 private boolean voted 4 5 public CentralServerExclusionAgent 6 if getID 0 7 descri
169. software7 de 14http www lightdev com 7 9 Test 107 lt view gt lt name gt Index lt name gt lt label gt Index lt label gt lt type gt javax help IndexView lt type gt lt data gt DisasterIndex xml lt data gt lt view gt ou AUNE Listing 7 9 View Integration des Index Zur Darstellung des Index wird die Klasse javax help IndexView verwendet Im data Tag befindet sich die Referenz auf die vorher angelegte XML Konfigura tionsdatei Um nun das fertige Hilfesystem in ein Programm einzubinden gibt es meh rere M glichkeiten Bei den Demos zu JavaHelp liegt der HelpViewer bei mit dem es m glich ist ein HelpSet auszuw hlen und dieses zu betrachten Beim Start kann bereits ein HelpSet bergeben werden das dann in diesem HelpView er angezeigt wird Eine andere M glichkeit w re ein HelpBroker dem ein HelpSet bergeben wird und der f r dieses ein Fenster anzeigt Da aber keinerlei Einfluss geschweige denn irgendwelche nderungen an diesem Fenster vorgenommen wer den k nnen wird auf eine dritte M glichkeit zur ckgegriffen Der Klasse JHelp kann ebenfalls ein HelpSet bergeben werden Hierbei handelt es sich um eine Swing Komponente die in einem selbst definierten Fenster abgebildet und bei Bedarf bearbeitet werden kann Die Komponente zeigt dann das bergebene Hil fesystem im blichen Stil an Um ein solches JHelp zu erzeugen wird zun chst das HelpSet ber seine URL gesucht Mit diesem HelpS
170. ssage from 33 message getSender 34 Anders als bei allen anderen Beispielen werden f r dieses zwei Klassen ben tigt Diese sollten nach den Vorgaben des Algorithmus eingesetzt werden d h 3f 1 Agenten wobei f die Anzahl der Verr ter ist Aus Testzwecken k nnen 8 2 Koordination und bereinstimmung 134 nat rlich auch Szenarien mit mehr Verr tern erstellt werden Die Agenten m ssen ber die CompleteTopology miteinander verbunden werden 9 Verwandte Projekte 135 9 Verwandte Projekte Dieses Kapitel besch ftigt sich mit der Untersuchung bereits bestehender Projek te welche die Problematik verteilte Algorithmen zu simulieren bereits behandelt haben Eine solche Recherche hilft das eigentliche Problem genauer zu analysie ren und sich mit Techniken vertraut zu machen die bereits f r das L sen dieser Aufgabe eingesetzt werden Nach einer genauen Untersuchung der Projekte l sst sich feststellen wieweit diese Techniken als sinnvoll betrachtet werden k nnen und welche in diesem Entwurf einen Platz finden werden 9 1 Vorstellung der Projekte F r das DAP Projekt wurde bereits eine solche Analyse durchgef hrt bei der einige Bibliotheken und Anwendungen und deren Eigenschaften beschrieben wer den Hierbei handelt es sich zum Teil um Programme die ebenfalls verteilte Algorithmen simulieren andere beschr nken sich auf die Darstellung von Netz werkprotokollen Neben DAP selbst werden b
171. ssen des Modells und der Ansichten der Anwendung die auch im folgenden vorgestellt werden Um die neu erstellten Klassen seien es eigens implementierte Agenten Verbindungen o a in das Programm integrieren zu k nnen m ssen diese im Klassenpfad der Anwendung liegen Hierzu wird der lib Ordner verwendet der einen Teil des Klassenpfades des Programms bildet Das bedeutet dass alle selbst geschriebenen Klassen class Dateien mit samt ihrer Package Struktur in das lib Verzeichnis gelegt werden m ssen 5 2 1 Verwendung und Implementierung von Agenten Die wichtigste Klasse bei der Entwicklung verteilter Algorithmen mit DisAS Ter ist die Klasse Agent disaster model Agent Ein Agent stellt in DisASTer einen Teilnehmer eines Algorithmus dar der durch die Kommunikation mit den anderen Prozessen f r den Ablauf des Algorithmus verantwortlich ist Zun chst 5 2 Die Bibliothek 43 beschr nkt sich die Aufgabe also nur darauf eigene Prozesse zu beschreiben in dem die Klasse Agent erweitert und in der neuen Klasse das Verhalten des Prozesses festgelegt wird H ufig ist es ausreichend eine einzige Klasse f r einen Algorithmus zu spezifizieren da sich das Verhalten der einzelnen Prozesse inner halb eines verteilten Algorithmus oft nicht unterscheidet Diese neue aus Agent abgeleitete Klasse erbt bereits viele n tzliche Metho den und Attribute Zu den wichtigsten Attributen geh ren ID eine eindeutige Kennung die jeder Agent
172. st die gleiche Der Unterschied besteht darin dass bevor das Werk zeug eingesetzt werden kann eine Klasse ausgew hlt wird die zum Ver binden der Agenten verwendet wird Disconnect Tool dieses Werkzeug berwacht Mausklicks und dessen Posi tion Erfolgt ein solcher in unmittelbarer N he oder auf einer Verbindung wird diese gel scht Die genaue Beschreibung der Verwendung des Topologieeditors befindet sich in Abschnitt 5 3 3 7 2 Visualisierung und Animation 93 7 2 Visualisierung und Animation Die Visualisierung ist eine der wichtigsten Komponenten von DisASTer Sie soll dem Anwender einen schnellen und leicht verst ndlichen berblick ber das Ver halten verteilter Algorithmen geben Dieser Abschnitt besch ftigt sich mit der Implementierung und den verwendeten Techniken Der Entwurf der Visualisie rung wird in Abschnitt 6 4 beschrieben Die grafische Darstellung erfolgt ber die 2D Graphics API speziell ber die Klasse java awt Graphics2D Diese Klasse erweitert die Graphics Klasse die von den einzelnen Swing Komponenten zum Zeichnen verwendet wird Mittler weile werden nur noch Graphics2D Objekte zum Zeichnen der einzelnen Kom ponenten verwendet Allerdings hat sich die Schreibweise der Methoden nicht ver ndert was den Anschein erweckt es w rde nur mit einfachen Graphics Objekten gearbeitet Um die erweiterte Funktionalit t der 2D Graphics API nut zen zu k nnen m ssen also alle Graphics Objekte nach
173. stanten vordefinierte Rollen sind ROLE_MASTER zeigt an dass dieser Agent eine bergeordnete Rolle spielt _ROLE_SLAVE beschreibt die Rolle eines einfachen Agenten Lesender und schreibender Zugriff auf die Rolle erfolgt ber die Methoden getRole und setRole int newRole 5 2 Die Bibliothek 44 Neben diesen Attributen verf gt die Klasse Agent ber viele hilfreiche Me thoden Zun chst werden die Methoden vorgestellt die die Kommunikation mit den anderen Agenten und das Senden von Nachrichten erm glichen send Message message sendet die bergebene Nachricht Diese Me thode kann dazu verwendet werden unterschiedliche Nachrichtentypen zu versenden die beim Empf nger auch unterschiedlich Aktionen ausl sen k nnen Zum Empfang dieser Nachrichten wird in diesem Abschnitt noch einiges erkl rt Bereits existierende Nachrichtentypen werden im n chsten Abschnitt vorgestellt send Object payload Agent receiver diese und die weiteren Metho den sollen dem Anwender ein wenig die Arbeit mit dem Standardnachrich tentyp vereinfachen so dass er nicht jedesmal ein neues Nachrichtenobjekt erzeugen muss ber diese Methode wird eine Nachricht mit dem berge benen Datenpaket an den angegebenen Empf nger gesendet send Object payload Agent receiver int duration diese Metho de sendet ebenfalls eine Standardnachricht an den bergebenen Empf nger allerdings wird diese Nachricht fr hestens nach d
174. startet werden in dem die externe Hilfe zu lesen ist sei es ein Webbrowser oder beispielsweise der Acrobat Reader Um ein solches Hilfesystem in Java zu realisieren wird das von Sun selbst entwickelte JavaHelp in der Version 2 verwendet JavaHelp stellt eine Biblio thek dar die bereits viele Elemente beinhaltet um Online Hilfen in der Form zu erstellen wie sie aus anderen Programmen bekannt sind Zu diesen Elementen z hlt eine bersicht in Form eines Inhaltsverzeichnisses eine Suchfunktion und ein Index ber die wichtigsten Begriffe rund um ein Programm Die Hilfetexte 12http java sun com products javahelp 7 8 Hilfesystem 103 selbst k nnen dann einfach in HTML verfasst werden Zur Ansicht dieser Texte wird eine auf Java basierte Browserkomponente benutzt Um besser durch die einzelnen Seiten zu navigieren wird ein Inhaltsverzeichnis angezeigt Dar ber hinaus bietet das System die M glichkeit eine Volltextsuche f r den gesamten Inhalt der Hilfe erzeugen zu lassen Zus tzlich zu diesen beiden Navigationshilfen kann noch ein Index erstellt werden ber den der Benutzer die wichtigsten Begriffe in alphabetischer Reihenfolge aufgelistet bekommt Im Folgenden werden die Schritte erl utert die f r das Erzeugen einer Online Hilfe mit Javahelp speziell der von DisASTer notwendig sind Zun chst gilt es einmal den Inhalt zu erzeugen Hierzu geh rt die JavaDoc Dokumentation die ja bereits in HTML vorliegt und der Te
175. t 1 Ist die eigene ID kleiner als die empfangene sendet er die Nachricht an den n chsten Prozess weiter und setzt sich als Teilnehmer 2 Ist die eigene ID gr er und der Empf nger noch kein Teilnehmer einer Wahl tr gt er seine eigene ID in die Nachricht ein sendet sie weiter und setzt sich als Teilnehmer Ansonsten wird die Nachricht verworfen 3 Ist die empfange ID gleich der eigenen dann ist der Empf nger der neue Anf hrer Dieser setzt sich als Nicht Teilnehmer und sendet eine Wahlergebnisnachricht mit seiner eigenen ID an den n chsten Prozess Bei Empfang einer Wahlergebnisnachricht merkt sich der Empf nger die ID des neuen Anf hrers markiert sich selbst als Nicht Teilnehmer und sendet die Nachricht an den n chsten Prozess weiter falls er nicht selbst Anf hrer ist Bei der Implementierung dieses Algorithmus werden zun chst einmal die Zu standskonstanten angepasst Es werden die Konstanten MEMBER und NO_MEMBER eingef hrt die anzeigen sollen ob ein Agent bereits bei einer Wahl beteiligt ist oder nicht Die ID des zuk nftigen Anf hrers wird in der Variablen leader gespeichert und mit 1 initialisiert public class RingLeaderAgent extends Agent public static final int MEMBER STATE_WORKING public static final int NO_MEMBER STATE_NORMAL 1 2 3 4 5 private int leader 6 7 public RinglLeaderAgent 8 9 description Ringleader getID setState NO_MEMBER 10 leader 1
176. t kann auch als Grafik exportiert werden Symbol I M gliche Formate hierbei sind die freien und plattformunabh ngigen Formate 5 3 Die Oberfl che 56 x Topologyview Abbildung 5 4 Topologieansicht JPEG oder PNG Die aktuelle Zoomeinstellung wird beim Exportieren der An sicht ber cksichtigt AgentConsole Zus tzlich zu der Standardausgabe System out die sehr ger ne f r Testausgaben verwendet wird bietet DisASTer eine eigene Funktionalit t an Statt der blichen System out print1n Methode kann auch die printin Methode der Klasse Agent verwendet werden Diese Methode funktioniert hn lich bringt allerdings noch einige Vorteile mit sich Die Ausgabe wird in einem separaten Fenster Abbildung 5 5 angezeigt wobei die Texte der einzelnen Agen ten durch unterschiedliche Farben hervorgehoben werden Neben dieser ber sichtlichen Gestaltung besteht ein weiterer Vorteil darin dass die mit print1n erstellten Ausgaben Teil der Simulation sind und mit dem restlichen Datenmo dell abgespeichert werden Anders als bei der Standardausgabe werden so alte Ausgaben entfernt und nur die aktuellen angezeigt Wenn nun ein bereits abge arbeiteter Zustand aus dem Verlauf wieder hergestellt wird werden die Texte die zeitlich hinter dem jetzt aktuellen Schritt liegen nicht mehr angezeigt Bei der Verwendung der Standardausgabe w re dies nicht der Fall sondern die Tex te w rden einfach an den ber
177. t zusichern kann Dieser Algorithmus arbeitet durch die zentrale Instanz sehr effizient da f r einen Eintritt nur drei Nachrichten versendet werden m ssen die Anfrage die Erlaubnis und die Freigabemitteilung vgl Coulouris et al 02 S 494f Ring basierender Algorithmus Die einfachste Methode einen wechselseiti gen Ausschluss ohne eine zentrale Komponente zu realisieren ist die Anordnung der Prozesse in einem Ring bei dem jeder Prozess einen Kommunikationskanal zu seinem benachbarten Prozess besitzt und die bertragung von Nachrichten ber diese Kan le nur in einer Richtung stattfinden kann Um den kritischen Abschnitt zu betreten ben tigt ein Prozess ein bestimm tes Token dass von den einzelnen Prozessen ber den Ring gesendet wird Dieses Token fungiert im Grunde wie ein Schl ssel der den Zugang zu dem kritischen Abschnitt erm glicht Ben tigt ein Prozess das Token fordert er es ber den Ring an was bei einem System mit N Teilnehmern zwischen 0 und N Nachrich ten erfordert Erh lt ein Prozess der kein Interesse am Betreten des kritischen Abschnitts hat das Token sendet er es an seinen Nachbarprozess weiter Ein gro er Nachteil dieses Algorithmus ist der hohe Verbrauch der Netzwerk bandbreite durch das st ndige Senden von Nachrichten vgl Coulouris et al 02 S 495f Gegenseitiger Ausschluss von Ricart und Agrawala Ricart und Agrawala haben eine L sung des Problems f r ein Netzwerk mit Multicast Funktion
178. tID 0 4 description Commander T 5 setRole ROLE_MASTER 6 7 else 8 description General T getID 9 10 Bei der Initialisierung eines verr terischen Kommandeurs sendet dieser jedem General einen anderen Befehl 11 public void init InitMessage message 12 if getRole ROLE_MASTER 13 for int i 0 i lt getOthers length i 14 Agent general Agent getOthers i 15 send new Message general new Integer i 16 printin sending command i to general 17 18 19 Erh lt ein verr terischer General einen Befehl des Kommandeurs sendet er jedem anderen General einen anderen Befehl nur nicht den den er von Kommandeur erhalten hat 20 public void onReception Message message 21 int command Integer message getPayload intValue 22 for int i 0 i lt getOthers length i 23 Agent general get Others i 24 if general getRole ROLE_MASTER 25 send new Response general new Integer command i 26 printin sending wrong command command i 27 to general 28 29 30 Diese Methode wird ben tigt da ankommende Antworten sonst in der normalen onReception Message Methode landen w rden Die ankommenden Befehle der anderen Gener le werden von einem Verr ter einfach ignoriert 31 public void onReception Response message 32 printin ignoring command me
179. tandardnachrichtentyp Message erreicht ist und f r diesen Typ stellt bereits die Klasse Agent eine Methode bereit Mit dieser Technik ist es nun m glich unterschiedliche Aktionen bei unterschiedli chen Ereignissen Nachrichtentypen auszuf hren Es werden zwei Spezialf lle mit entsprechenden Methoden behandelt init InitMessage message wird beim Empfang einer Initialisierungs nachricht aufgerufen Welcher Agent wann initialisiert wird legt der Be nutzer bei der Einrichtung des verteilten Systems fest Ein Agent kann auch mehrfach initialisiert werden Um einen Algorithmus starten zu k n nen muss allerdings mindestens ein Agent auf diese Weise angestossen werden timeout TimeoutMessage message wird nach Ablauf eines Timeouts aufgerufen println Object out ist eine weitere wichtige Methode die dem Benutzer zur Verf gung steht Diese Methode soll die Standardausgabe ersetzen Das ber gebene Objekt wird in einer separaten Konsole ausgegeben und zus tzlich mit gespeichert denn die hier get tigten Ausgaben finden sich im AgentLog wieder der im n chsten Abschnitt beschrieben wird Das Agentlog ist eine Liste in der alle ber print1n gemachten Ausgaben eingehen F r jeden Aufruf wird ein neuer Eintrag AgentLogEntry angelegt der aus einem Text und dem Agenten der die Ausgabe gemacht hat besteht Auch hier wird wieder mit Observern gearbeitet die benachrichtigt werden sobald ein neuer Eintrag in das Log einget
180. ten der Ablenkung und des Teetrinkens in denen ich zus tzlich noch einiges ber Bildverarbeitung lernen durfte Meinen Eltern die mich in den letzten 4 Jahren so toll nicht nur finanziell unterst tzt haben Kurzfassung Verteilte Algorithmen besch ftigen sich mit der L sung von Proble men die in verteilten Systemen auftreten k nnen Unter diese Pro bleme fallen z B die Uhrensynchronisation in Netzwerken globale Zust nde in verteilten Systemen oder Koordinations und berein stimmungsprobleme Ziel dieser Arbeit ist es ein Baukastensystem zu entwickeln und zu realisieren das viele Mittel bereitstellt um verteilte Algorithmen zu implementieren Der Anwender dieses Baukastens soll in der Lage sein die angebotenen Elemente schnell und intuitiv einzusetzen Ein wesentlicher Aspekt dabei ist eine hohe Erweiterbarkeit die die Fest legung der Grenzen dieses Systems erschwert Neben der einfachen Entwicklung verteilter Systeme sollen diese zus tzlich grafisch visua lisiert werden Die grafische Darstellung behebt oft Verst ndnispro bleme des Ablaufs eines verteilten Algorithmus Ergebnis der Arbeit sind eine Klassenbibliothek und ein Programm die alle gesteckten Ziele beinhalten Die Bibliothek verf gt ber Klas sen aus denen sich ein Entwickler die von ihm ben tigten herausgrei fen und erweitern kann um mit den darin enthaltenen Methoden die unterschiedlichsten Algorithmen zu implementieren Diese Klassen k nnen
181. ter Diese Weiterleitung geschieht beispielswei se folgenderma en public void mouseClicked MouseEvent e tool mouseClicked e Die Anzahl der Werkzeuge ist im Falle des Topologieeditors noch berschaubar MoveTool wird zum Bewegen der Agenten auf der Oberfl che verwendet Folglich berwacht dieses Werkzeug ob und an welcher Stelle die linke 7 1 Topologieeditor 92 JPanel MouseListener MouseMotionListener from javax swing from java awt event from java awt event mouseClicked e MouseEvent void mouseDragged e MouseEvent void mousePressed e MouseEvent void mouseMoved e MouseEvent void mouseReleased e MouseEvent void A mouseEntered e MouseEvent void mouseExited e MouseEvent void Topology TopologyEditor MoveTool ConnectTool ConnectChosenTool DisconnectTool Abbildung 7 1 Aufbau des Topologieeditors Maustaste zum Ausw hlen eines Agenten bet tigt wurde wohin die Maus sich bewegt und wo die Maustaste wieder losgelassen wird ConnectTool wird zur Erzeugung von Verbindungen zwischen jeweils zwei Agenten erzeugt Hierbei berwacht das Werkzeug die Mausklicks und die Positionen an denen diese erfolgen Hierbei wird zwischen einem ersten und einem zweiten Mausklick unterschieden wobei jeder Klick auf einen Agenten gemacht werden muss ConnectChosenTool hnelt dem vorangegangenen Werkzeug Die Arbeits weise i
182. ter Punkt betrifft die Steuerung der Simulation Zun chst w re hier ein automatischer Ablauf zu betrachten Dieser k nnte hnlich einem Video oder CD Spieler mit den Funktionen Start Stopp Pause und Einzelschritt be st ckt sein Durch einen automatischen Ablauf f llt aber zun chst die Eigenschaft der MessageQueue ver ndert werden zu k nnen unter den Tisch Durch eine zu s tzliche manuelle Steuerung wird dies wieder m glich Auf diesem Weg kann die Nachrichtenreihenfolge ge ndert oder es k nnen sogar Nachrichten gel scht wer den Der oben beschriebene Eingriff in den Verlauf der Simulation f llt ebenfalls in den Aufgabenbereich der Steuerung Die folgenden Abschnitte stellen den eigentlichen Entwurf dar Dieser wurde nach einem erweiterten MVC Modell entwickelt Das MVC Paradigma Model View Controller wird sehr h ufig in objektorientierten Entw rfen verwendet Es unterteilt eine Anwendung in drei Teilstrukturen das Modell das i d R dem Datenmodell entspricht eine oder mehrere Ansichten die dieses Modell grafisch darstellt und eine oder mehrere Kontrollinstanzen oder Modifikatoren mit deren Hilfe das Datenmodell ver ndert werden kann vgl Gamma et al 96 S Aff Um alle drei Komponenten untereinander konsistent zu halten wird h ufig das 6 2 Erkenntnisse f r den eigenen Entwurf 74 Entwurfsmuster Observer eingesetzt wodurch eine nderung des Modells den anderen Komponenten mitgeteilt werden kan
183. tion Request request 24 int rlc Integer message getPayload intValue 25 clock Math max clock rlc 26 clock 10 27 clock clock 10 28 clock getID 29 30 switch getState 31 case STATE_WAITING 32 if Integer request getPayload intValue 33 lt sentTime 34 send new Response request getSender 35 new Integer clock 36 F 37 else 38 buffer add request getSender 39 40 break 41 case STATE_NORMAL 42 send new Response request getSender 43 new Integer clock 44 break 45 case STATE_WORKING 46 buffer add request getSender 47 break 48 49 Der Erhalt einer Antwort erh ht zun chst die logische Uhr des Empf ngers dann wird die Anzahl der erhaltenen Antworten inkrementiert Hat der Agent mit dieser Antwort von allen anderen Agenten eine Zusage bekommen kann er den kritischen Abschnitt betreten 45 public void onReception Response response 46 int rlc Integer message getPayload intValue 47 clock Math max clock rlc 48 clock 10 49 clock clock 10 50 clock getID 51 52 answerstt 53 if answers get Others length 54 setState STATE_WORKING 55 setTimeout 5 56 F 57 Nach Ablauf eines Timeouts wird der kritische Abschnitt wieder verlassen Befinden sich noch Anfragen im Puffer werden diese alle beantwortet 53 public void timeout TimeoutMessage message 54 c
184. tische Methode getInstance zugegriffen werden kann Durch den Einsatz dieses Entwurfsmusters wird die Einmaligkeit des Datenmodells sichergestellt vgl Gamma et al 96 S 139ff sent Messages AgentLog Environment Message lt gt dnstance Environment getInstance Environment C Systemklasse Vom Benutzer erweiterbar Topology History MessageQueue AgentMessageQueues Abbildung 6 2 Aufbau der Umgebung Abbildung 6 3 zeigt die verwendeten Observer die bei nderungen des Mo dells benachrichtigt werden Diese Observer werden als Schnittstellen Interfa ces definiert Aus Effizienzgr nden werden zwei verschiedene verwendet Der EnvironmentChangeListener bekommt jede nderung des Modells mit wo hin gegen der EnvironmentUpdateListener nur benachrichtigt wird wenn die Um gebung neu geladen wurde Ein Neuladen der Umgebung tritt nicht nur dann auf wenn der Benutzer tats chlich eine neue Umgebung erzeugt oder eine vorher ge speicherte geladen wird sondern auch wenn ein im Verlauf enthaltener Zustand wiederhergestellt wird Die Topologie beschreibt den Aufbau des zu simulierenden verteilten Systems Hier werden alle Teilnehmer des Systems und dessen Verbindungen untereinander 6 3 Model 76 Environment N nstance Environment Benachrichtigt alle Een N EnvironmentChangeListener getinstance Environment u environmentChanged void Eee Bier
185. tliche Fracht also die Informationen die mit einer Nachricht bermittelt werden sollen sender nimmt den Wert des Senders an Falls eine Nachricht vom System gesendet wurde was bei den Initialisierungen der Fall ist ist dieser Wert null receiver hat den Wert des Empf ngers Dieser Wert kann auch die Broadcast Adresse Agent BROADCAST annehmen wodurch Kopien der Nach richt an alle erreichbaren Nachbarn des Senders weitergeleitet werden Damit die Nachrichten unterschiedliche Ereignisse ausl sen k nnen werden ver schiedene Typen verwendet die noch zus tzlich erweitert werden k nnen Es soll m glich sein jeden Nachrichtentyp in einer separaten Methode abzufangen und diesen entsprechend zu behandeln Das ist allerdings Aufgabe des Agenten der jetzt genauer beschrieben wird Die Rolle der Agenten wird im Entwurf gesondert betrachtet da der Anwen der durch sie die verteilten Algorithmen implementiert indem er die Agenten klasse erweitert Dabei wird das Verhalten eines Prozesses in einem bestimmten Algorithmus definiert Damit stellen Agenten das wichtigste Werkzeug f r die se Aufgabe dar Aus diesem Grund erhalten sie eine Reihe von Eigenschaften und Methoden auf die zur ckgegriffen werden kann um m glichst einfach und schnell einen verteilten Algorithmus f r das vorliegende System zu entwickeln Die Struktur der Agenten wird in Abbildung 6 6 dargestellt Im folgenden werden die Eigenschaften der Agenten
186. tring Agent from java lang agentLogChanged void Abbildung 6 7 Aufbau des Agentlogs einen gespeicherten Zustand sei es aus dem Verlauf heraus oder aus einer Da tei wieder herstellen zu k nnen wird die updateEnvironment Methode eines EnvironmentState Objekts aufgerufen die das Environment mit den gespeicher ten Werten aktualisiert Die Zeit der Simulation und damit des Verlaufs teilt sich in Zeit bzw Zeit punkt clock und Zeitschritt timestep wobei ein Zeitpunkt aus mehreren Zeitschritten besteht Was es genau damit auf sich hat wird in Abschnitt 6 5 beschrieben 6 4 View Die Ansichten Views der Anwendung werden f r die Visualisierung der Algorith men verwendet Um sie zu realisieren wird das Entwurfsmuster Br cke verwen det Dieses Entwurfsmuster macht eine Entkopplung einer Abstraktion und ihren Implementierung um beide unabh ngig voneinander zu variieren vgl Gamma et al 96 S 165ff In diesem Entwurf wird sogar eine Mehrfach Br cke ver wendet wobei die Abstraktion auf mehrere Implementierungen zur ckgreift Die Verbindung zwischen diesen Elementen wird als Br cke bezeichnet Die Abstrak tion wird durch die Klasse View repr sentiert Dabei handelt es sich um eine Erweiterung einer JComponent aus der Swing Bibliothek Auf dieser Komponente 6 4 View 84 ArrayList Object Serializable from java util from java lang from java io History H
187. tusleiste Eine schnelle bersicht ber den Zustand der Umgebung liefert die Statusleiste die in Abbildung 5 10 dargestellt wird Hier finden sich Informa tionen dar ber aus wievielen Prozessen der gerade geladene Algorithmus 5 3 Die Oberfl che 60 besteht wieviele Nachrichten schon ausgeliefert wurden oder wieviele sich in der Messagequeue befinden i Au erdem wird der aktuelle Zeitpunkt an gezeigt der sich in Zeit und Zeitschritt unterteilt Zeitschritte werden allerdings nur f r den asynchronen Ablauf der Simulation verwendet Dort er folgt die Darstellung von Nachrichten die zur selben Zeit empfangen werden sequenziell Der Zeitpunkt des Eintreffens ist zwar weiterhin der gleiche jedoch wird dieser Zeitpunkt nochmal in einzelne Zeitschritte geteilt Was es mit den Zeitschritten genau auf sich hat wird in Abschnitt 5 3 4 n her erl utert Systeminformations 4 E 6 a O 3 gi Abbildung 5 10 Statusleiste 5 3 3 Einstellungen Das Options Men Abbildung 5 11 enth lt eine Auswahl an Einstellungen mit denen die Simulation konfiguriert wird File View Pa R ViewPreferences Strg T Abbildung 5 11 Einstellungen W Preferences Konfiguration des Algorithmus ViewPrefereces Anpassungen der Ansichten Preferences Die hier vorgestellten Einstellungen dienen dazu ein verteiltes System zu erstellen oder es im Nachhinein zu bearbeiten in dem ein verte
188. uch eine Kopie dieser Nachricht Neben dieser Methode k nnte auch eine einfache sende Methode verwendet werden wobei als Empf nger die Broadcastadresse Agent BROADCAST angegeben wird Das Verhalten un terscheidet sich nicht Es wird ebenfalls eine Nachrichtenkopie f r jeden erreichbaren Agenten erzeugt 6 3 Model 81 sendToAll Object payload ber diese Methode kann ein Agent ein bestimmtes Paket an alle seine erreichbaren Nachbarn schicken Es wird wiederum der Standardnachrichtentyp verwendet sendToAll Object payload int duration bei dieser Methode wird erneut eine Zeitverz gerung angegeben Wenn ein Agent ein Ereignis bei sich selbst ausl sen m chte kann er nat rlich auf die obigen Methoden zur ckgreifen allerdings wurde f r diesen speziellen Fall ein weiterer Mechanismus der Timeout eingef hrt Um einen solchen Timeout zu erzeugen gibt es zwei zus tzliche Methoden setTimeout int duration mit dieser sendet der Agent eine Timeout nachricht an sich selbst Diese wird nach der angegebenen Zeit ausgeliefert Dadurch kann eine geplante Aktion zu einem sp teren Zeitpunkt ausge f hrt und der entsprechende Agent schlafen gelegt werden Dieser Me chanismus sollte als Ersatz f r Thread sleep verwendet werden denn Thread sleep bezieht sich auf die reale Zeit wo hingegen ein Timeout die Simulationszeit verwendet Allerdings schl ft der entsprechende Agent nicht wirklich In der Zeit in d
189. uf das Eintreffen einer Response wird die Methode onReception Response aufgerufen InitMessage Spezialfall Dieser Nachrichtentyp initialisiert einen Agenten Beim Empfang einer InitMessage wird die Methode init aufgerufen Eine Nachricht dieses Typs kann wie die anderen auch an einen anderen Agenten gesendet werden TimeoutMessage ein weiterer Spezialfall Nach Ablauf des Timeouts wird die Methode timeout aufgerufen Auch dieser Nachrichtentyp kann an 5 2 Die Bibliothek 48 andere Agenten gesendet werden Der Unterschied zwischen den einzelnen Nachrichtentypen besteht weitest gehend nur darin dass sie unterschiedliche Klassen repr sentieren und durch den Pseudopolymorphismus entsprechende onReception Methoden aufrufen um bei dem Empf nger unterschiedliche Aktionen auszul sen Geht eine Nachricht ein f r dessen Typ keine explizite Empfangsmethode deklariert wurde und dies ebenfalls f r die Nachrichtentypen der Fall ist aus denen dieser Typ abgelei tet ist wird die Nachricht von der Standardmethode onReception Message angenommen Bei der Verwendung eigener Nachrichtentypen sollte auf die Verwendung ei gener Attribute verzichtet werden Diese k nnten z B dazu verwendet werden zus tzliche Informationen in die Nachricht zu integrieren Die zu sendende Nach richt wird allerdings vor dem Senden kopiert wobei alle bekannten Attribute wie der Sender der Empf nger die Sende und Empfangszeit sowie das
190. um oder gar nicht bekannt waren Unter diese Techniken fallen 1 Reflection API die es erm glicht Klassen aus Datein einzulesen und dar aus Instanzen zu bilden oder bestimmte Methoden eines Objekts aufzuru fen wodurch ein Pseudo Polymorphismus realisiert werden konnte 2 Swing grafische Oberfl chen und die 2D Graphics API Ein wesentlicher Bestandteil der Arbeit war es eine ansprechende Oberfl che zu schaffen Dies ist auch unter Zuhilfenahme einiger einfacher Regeln gelungen Zu s tzlich wurde mit Look and Feels gearbeitet wodurch eine Auffrischung der Erfahrungen aus dem Praxissemester erfolgte Besonders hervorzuhe ben ist der Einsatz der 2D Graphics API die viele n tzliche Elemente be reitstellt um die Visualisierungen des Programms zu realisieren 3 Multithreading Die Verwendung von Animationen f hrte zum Einsatz mehrerer Threads wodurch das Thema Multithreading und Threadsicher heit wieder aufgegriffen wiederholt und vertieft werden konnte Neben den Erkenntnissen in objektorientierter Programmierung und speziell in Java hatte die Arbeit aber auch einen gewissen theoretischen Anspruch durch die intensive Untersuchung der verteilten Algorithmen Zus tzlich zur genauen Analyse der Algorithmen wurden viele f r das entstandene System implementiert Abschlie end soll noch ein kleiner Ausblick auf die Zukunft von DisASTer ge worfen werden Die eigentliche Entwicklung ist erfolgreich abgeschlossen worden Es werden
191. ung dieser Konsole und der weiteren Vorteile gegen ber der Standardausgabe findet sich in Abschnitt 5 3 2 Allgemein ist bei der Entwicklung eines Agenten darauf zu achten dass zu s tzliche Klassen serialisierbar sind Gerade beim Einsatz von Swing ist dies nicht immer ganz einfach Um jedoch den vollen Funktionsumfang von DisASTer nut zen zu k nnen ist die Serialisierbarkeit der verwendeten Klassen Pflicht 5 2 2 Verwendung und Implementierung von Nachrichten Bei der Vorstellung der Agenten und ihrer Arbeitsweise wurde bereits ersichtlich dass Nachrichten und unterschiedliche Nachrichtentypen ein weiterer wesentli cher Bestandteil der Entwicklung verteilter Algorithmen mit DisASTer sind Das Eintreffen einer Nachricht ruft in der Regel eine bestimmte Aktion beim Emp f nger auf Um unterschiedliche Aktionen auszul sen k nnen unterschiedliche Nachrichtentypen verwendet werden Im Package disaster model befinden sich bereits einige vordefinierte Typen Message Standardnachricht von der alle anderen Nachrichtentypen ab geleitet werden Als Reaktion auf das Eintreffen einer Message wird die Methode onReception Message aufgerufen Request ein Request kann dazu verwendet werden Anfragen an andere Agenten zu stellen Als Reaktion auf das Eintreffen einer Request wird die Methode onReception Request aufgerufen Response ein Response kann dazu verwendet werden Antworten auf eine andere Nachricht zu geben Als Reaktion a
192. ung der anderen Teilnehmer warten um eine bestimmte Aktion auszuf hren Des wei teren k nnen die Teilnehmer eine bestimmte Rolle annehmen die sie von den anderen Teilnehmern unterscheidet Ein Teilnehmer k nnte z B als Anf hrer der anderen fungieren oder als zentraler Server agieren Ein weiterer Punkt den alle verteilten Algorithmen in sich vereinen ist die Kommunikation untereinander Dies ist auch nicht weiter verwunderlich da ver teilte Algorithmen ausschlie lich in verteilten Systemen wie Netzwerken einge setzt werden Diese Kommunikation besteht aus Nachrichten die sich die Teil nehmer untereinander senden Das Eintreffen einer Nachricht l st dann beim Empf nger eine bestimmte Aktion aus bei der sich z B der Zustand des Emp f ngers ndert Dieser wiederum kann dann den anderen Teilnehmern die nde rung ber weitere Nachrichten zukommen lassen auf die diese ebenfalls reagieren k nnen Mit diesen beiden Eigenschaften den einzelnen Teilnehmern mit ihren Zu st nden und Rollen sowie der einfachen Kommunikation zwischen ihnen ber Nachrichten k nnen nahezu alle verteilten Algorithmen abgebildet werden Im folgenden Abschnitt werden nun diese Erkenntnisse mit denen der anderen Projek te zusammengefasst um einen m glichst allgemeinen und vielf ltig einsetzbaren 6 2 Erkenntnisse f r den eigenen Entwurf 72 Entwurf zu entwickeln 6 2 Erkenntnisse f r den eigenen Entwurf Im Folgenden werden die Ergebnis
193. unterschiedliche Befehle erteilt Ziel ist die Eini gung aller loyalen Gener le auf einen Befehl Ist der Kommandeur loyal m ssen die Gener le auch den von ihm vorgeschlagenen Befehl ausf hren Bisher wurde noch kein L sungsverfahren f r eines der drei Probleme vorge stellt Es w rde allerdings ausreichen nur die L sung eines dieser Probleme zu kennen da sich die L sungen der anderen aus dieser ableiten lassen Konsens byzantinische Gener le e _ Der Kommandeur p sendet seinen Befehl d an alle Gener le Diese einigen sich ber den Konsens auf einen der erhaltenen Befehle wobei p nicht korrekt arbeiten muss byzantinische Gener le interaktiver Konsens Das Problem der byzan tinischen Gener le wird N mal gel st wobei jeder Prozess p einmal der befehlshabende Kommandeur ist interaktiver Konsens Konsens Auf den durch den interaktiven Konsens entstanden Entscheidungsvektor wendet jeder Prozess p die selbe Funk tion z B maz min avg an um so einen gemeinsamen Wert zu erhalten Konsens Dolev und Strong haben einen Algorithmus entwickelt der das Pro blem des Konsens behebt Dieser wird in f 1 Runden durchgef hrt wobei h chstens f Prozesse abst rzen d rfen Jeder Prozess p besitzt einen Vektor von Mengen V in denen alle empfangenen vorgeschlagenen Werte d der ande ren Prozesse p enthalten sind Der Algorithmus l uft wie folgt ab Wird p initialisiert setzt er die Menge V 0
194. urch bekommt das System ein Gesicht und der Anwender hat die Topologie die Positionen der einzelnen Prozesse sowie deren Verbindung grafisch vor Augen Die Visualisierung stellt den schwierigsten und zugleich wichtigsten Teil des Programms dar F r die Visualisierung wurden bereits zwei Techniken aufge f hrt Zum einen kann die Visualisierung zeitgleich mit der Simulation ablaufen Zum anderen kann die Simulation eine Log Datei erzeugen aus der die Visua lisierung ihre Informationen nimmt dies hat den Vorteil dass die Visualisierung unabh ngig von der Simulation betrachtet werden kann allerdings ist hierbei an ein Eingreifen in das Geschehen nicht zu denken Aus diesem Grund soll die Vi sualisierung zeitgleich mit der Simulation ablaufen da ja die M glichkeit den Ablauf eines Algorithmus zu ndern mit der MessageQueue gegeben ist Und wenn schon ein Eingreifen m glich ist w re es auch interessant Teile der Simu lation unter ver nderten Bedingungen zu wiederholen ohne gleich den ganzen Algorithmus von neuem zu starten Diese Funktionalit t kann aber nur gegeben werden wenn das Programm wei was in den vorherigen Schritten passiert ist Um dies zu erreichen soll der Verlauf der Simulation gespeichert werden Auf diese Weise kann der Benutzer wie in einem Webbrowser an eine beliebige Stelle des Algorithmus zur ckspringen um ihn entweder einfach nur zu wiederholen oder ihn unter ver nderten Bedingungen weiterzuf hren Ein letz
195. us der Abbildung wird ebenfalls die Arbeitsweise des Algorithmus ersichtlich Der Kommandeur sendet seinen Befehl an alle Gener le Jeder General p sendet seinen vom Kommandeur erhaltenen Befehl d an alle anderen Gener le Ein General f hrt den am h ufigsten erhaltenen Befehl aus oder alle Ge ner le f hren einen Standardbefehl L aus falls keine Mehrheit erreicht wurde 3 3 Koordination und bereinstimmung 33 Abbildung 3 16 zeigt zwei Beispiele mit vier Gener len von denen einer jeweils ein Verr ter ist In beiden F llen einigen sich die Gener le auf einen Befehl Im ersten Beispiel k nnen sich die beiden fehlerlosen Prozesse P und P auf den Befehl u einigen Im zweiten Beispiel ist der Kommandeur der fehlerhafte Prozess und sendet jedem General einen anderen Befehl woraus diese keine Mehrheit gewinnen k nnen und den Standardbefehl L ausf hren Kommandeur Abbildung 3 16 Vier byzantinische Gener le Wird davon ausgegangen dass auch wirklich nur f Prozesse fehlerhaft sind kann mit Hilfe dieses Algorithmus der oder die Ver ter enttarnt werden Eine M glichkeit um dieses Verfahren weiter zu verbessern und sogar f r drei Pro zesse abzusichern w re eine Verwendung von Signaturen wodurch allerdings die Bandbreite auf O N steigen w rde vgl Coulouris et al 02 S 528ff 4 berblick und Grobkonzept 34 4 berblick und Grobkonzept 4 1 Programmkomponenten
196. uschen die Prozesse Nachrichten untereinander aus welche 4 bestimmte Aktionen und Ereignisse bei ihren Empf ngern ausl sen Der Empfang einer Nachricht k nnte z B eine Zustands nderung bewirken 4 2 Eigenschaften verteilter Algorithmen 35 Diese einfache Ablaufbeschreibung umfasst nahezu alle verteilten Algorithmen womit das Ziel eine allgemeine Beschreibung verteilter Algorithmen zu finden erreicht ist Der n chste Schritt befasst sich mit der Umsetzung dieser Erkennt nisse in DisASTer Hierzu wird zun chst auf das verteilte System eingegangen in dem ein Al gorithmus seine Aufgaben erledigt Ein solches System besitzt eine Topologie die aus den einzelnen Prozessen und deren Verbindungen besteht Dieselben Ele mente finden sich auch in der Klassenbibliothek wieder Die f r den Benutzer des Baukastens wichtigste Klasse ist die abstrakte Klasse Agent Ein Agent stellt einen Teilnehmer eines verteilten Systems dar Hauptaufgabe des Anwenders ist die Klasse Agent zu erweitern und darin die Logik eines Algorithmus abzubilden Da sich die einzelnen Teilnehmer eines Algorithmus in der Regel gleich verhalten gen gt es oft nur eine einzige Klasse pro Algorithmus zu entwickeln Um einen kurzen Einblick in die M glichkeiten zu erhalten die die Klasse Agent dem Benutzer er ffnet werden dessen Eigenschaften vorgestellt Jeder Agent eines Systems besitzt eine eindeutige Kennung die im Attribut ID festge legt wird Diese Kennun
197. uszug der Mapping Datei Jedes Element ob HTML Seite oder Grafik wird als mapID erzeugt target beinhaltet die eindeutige Bezeichnung dieses Elements und url verbindet diese Bezeichnung mit einer Datei Um diese Elemente in Zukunft zu verwenden wer den diese nur noch ber ihren mit target festgelegten Bezeichner angesprochen Hierzu aber gleich mehr denn zuerst muss die Mapping Datei in das HelpSet in tegriert werden Hierzu wird folgender Code in die HelpSet Datei hs eingef gt Listing 7 4 1 lt maps gt 2 lt homeID gt main lt homelID gt 3 lt mapref location disaster jhm gt 4 lt maps gt Listing 7 4 Integration der Mappingdatei maps leitet die Einstellungen der Mapping Datei ein Unter location wird der Ort dieser Datei angegeben Damit w ren alle Vorbereitungen abgeschlossen und es kann mit der Er stellung des Inhaltsverzeichnisses begonnen werden Dieses wird ebenfalls in ei ner separaten Konfigurationsdatei definiert Ein Inhaltsverzeichnis engl table of contents toc besitzt eine gewisse Hierarchie die aus Kapitel Unterkapitel Abschnitte usw besteht Daraus ergibt sich eine Baumstruktur mit der das In haltsverzeichniss in der Online Hilfe selbst und in der entsprechenden Konfigura tionsdatei Listing 7 5 dargestellt werden kann Ein Auszug aus der verwendeten 7 8 Hilfesystem 105 Konfigurationsdatei macht dies deutlich lt toc version 1 0 categoryclosedimage tocclosed
198. vor S t in m plaziert hat Coulouris et al 02 S 456 Ein Nachteil dieser Methode ist die Abh ngigkeit von einer zentralen In stanz da diese unter Umst nden ausfallen kann Eine Abhilfe w rde der Einsatz mehrerer Zeitserver schaffen die gemeinsam angeschrieben werden und deren schnellste Antwort verwendet wird Fehlerhafte Angaben eines Zeit Servers oder sogar Fehler der externen Quelle werden in diesem Verfahren nicht ber cksichtigt vgl Coulouris et al 02 S 456f BTP Berkeley Time Protocol Gusella und Zatti haben einen Algorith mus entwickelt um eine interne Synchronisation ohne einen zentralen Zeits erver zu bekommen Dieser wurde unter Berkeley UNIX Systemen eingesetzt wodurch er seinen Namen erhalten hat Bei dieser Methode wird ein Prozess als Koordinations Computer Master gew hlt Die anderen Prozesse werden als Slave bezeichnet Der Master f hrt in gewissen Zeitabst nden eine Umfrage bei lUTC Universal Time Coordinatet Bezeichnung f r eine f r die gesamte Erde einheitliche Zeitskala 3 1 Physikalische und logische Uhren 8 den Slaves durch und erkundigt sich nach deren aktueller Zeit Nachdem diese bei ihm angekommen sind werden die aktuellen Zeiten der anderen Prozesse mit Hilfe der Round Trip Zeit hnlich der Methode Christians gesch tzt und inklu sive seiner eigenen aktuellen Zeit gemittelt Dieser Mittelwert berdeckt bereits die Tendenzen der einzelnen Uhren zu schnell oder zu
199. wie andere Agenten angesprochen werden wird auf die Methoden eingegangen die beim Eintreffen dieser Nachrichten aufgerufen werden F r diesen Zweck bietet DisASTer einen Pseudopolymorphismus an Beim Eintreffen einer Nachricht wird die Methode onReception Message auf gerufen Diese Methode kann f r alle Nachrichtentypen berschrieben werden Um z B das Eintreffen einer Anfrage Request gesondert zu behandeln wird die Methode onReception Request definiert in der beschrieben wird was der Agent nach Erhalt einer Anfrage machen soll Existiert f r die ankommende Nach richt keine entsprechende onReception Methode wird die Standardmethode onReception Message ausgef hrt Durch diesen Mechanismus k nnen verschie dene Aktionen mit Hilfe unterschiedlicher Nachrichtentypen ausgel st werden 5 2 Die Bibliothek 46 Der Anwender ist an dieser Stelle nicht nur auf die bereits existierenden Nach richtentypen angewiesen sondern kann seine eigenen Typen definieren was im n chsten Abschnitt Verwendung und Implementierung von Nachrichten be schrieben wird Die Differenzierung der Nachrichtentypen kommt bereits zu Beginn eines verteilten Algorithmus zum Tragen Um einen Algorithmus in Gang zu setzen werden Initialisierungsnachrichten InitMessages verwendet die an einen oder mehrere Agenten adressiert sind Beim Eintreffen einer solchen Nachricht wird die init Methode des Empf ngers aufgerufen in der er weitere Nachricht
200. xt aus Kapitel 5 Um diesen in JavaHelp verwenden zu k nnen muss er in das HTML Format konvertiert werden Bisher liegt er im TeX Format vor Die Umformatierung erfolgt aber nicht von Hand An dieser Stelle kommt das Programm latex 2html zum Einsatz Hierbei handelt es sich um ein Perl Skript das wie der Name schon sagt LaTeX Dokumente in das ben tigte HTML Format konvertiert F r diese Aufgabe wurden auch an dere Programme wie z B TtH TeX to HTML getestet Allerdings berwiegten die Vorteile des Perl Skripts Der gr te Vorteil von latex2html gegen ber TtH besteht darin dass f r jedes Kapitel Unterkapitel und jeden Abschnitt eine sepa raten Seite erzeugt wird TtH stopft das ganze Kapitel auf eine HTML Seite Aber durch die Aufteilung auf mehrere Seiten wird das Hilfesystem viel bersichtlicher da auch wirklich nur das Kapitel angezeigt wird das der Benutzer eigentlich se hen will Ins n chste Kapitel zu bl ttern stellt dann immer noch kein Problem dar denn latex2html setzt automatisch Verweise auf das vorangegangene n chs te und bergeordnete Kapitel Ganz davon abgesehen dass dem Benutzer sp ter im fertigen Hilfesystem das Inhaltsverzeichnis zur Verf gung steht Da jetzt der Inhalt f r das Hilfesystem vorliegt kann detailierter auf die Ar beitsweise von JavaHelp eingegangen werden um zu sehen wie es mit diesen Webseiten arbeitet und wie diese eingebunden werden Das alles wird ber XML Konfigurationsdateien gel
201. zelnen Empf ngern ausgetauscht werden 3 N 1 Dieser Algo rithmus beschr nkt sich auf die totale Reihenfolge die entstandene Reihenfolge muss weder FIFO noch kausal sein Einen praktischen Einsatz dieses Verfahrens findet sich im ISIS System vgl Coulouris et al 02 S 516f Kausale Reihenfolge durch Vektoruhren In Abschnitt 3 1 2 wurden bereits die Vektoruhren eingef hrt um festzustellen ob ein Ereignis vor einem anderen Ereignis ausgel st wurde oder es sogar ein anderes Ereignis zur Folge hat Mit einer hnlichen Strategie l sst sich auch eine kausale Reihenfolge von Nachrichten ermitteln Jeder Prozess p eines verteilten Systems mit N Mitgliedern besitzt einen Vektor V j mit j 1 2 N in dem f r jeden Prozess p ein Eintrag dessen logischer Zeit existiert Die Arbeitsweise dieses Verfahrens ist Die Vektoren werden mit V j 0 j 1 2 N initialisiert Sendet Prozess p eine Nachricht m erh ht er zuvor seinen eigenen Zeit stempel V li Vili 1 und sendet diesen Vektor mit der Nachricht lt V m gt 3 3 Koordination und bereinstimmung 29 P P2 P3 m 31 m 42 m TA m 23 m 51 m 52 m 43 m 43 m 52 m 43 m q m 51 m mi m 52 ma gt m gt mi m m Abbildung 3 13 Totale Reihenfolge durch Folgenummern Empf ngt p die Nachricht lt Vj m gt von p wird diese zun chst in eine R ckhalte Warteschlange eingef gt bis V j
202. zer erst einmal vertraut machen muss Auch die Art der Visualisierung ist ein guter Vergleichspunkt Einige der oben vorgestellten Programme verwenden hierf r fremde Bibliotheken andere beschr nken sich auf eine einfache Textausgabe Wie bei ns erkennbar muss die Visualisierung auch nicht zeitgleich mit der Simulation geschehen sondern kann erst nach deren Ablauf angesetzt werden Bei der Simulation selbst gibt es kaum Unterschiede Die meisten sind ereignis bzw nachrichtengesteuert oder prozessorientiert Eine genaue Unterscheidung dieser zwei Typen findet sich bei Sinclair vgl Sinclair02 Seite 12ff 1 Ereignisgesteuerte Simulation ein Ereignis ist eine Zustands nderung des Modells Diese nderung ben tigt keine Zeit Das Modell entwickelt sich aus einer Folge solcher Ereignisse Um die Entwicklung des Modells zu beschreiben muss bekannt sein wann ein Ereignis auftritt und welchen Einfluss es auf das Modell nimmt Damit dies der Fall ist werden alle Er eignisse in einer Ereignis Zeit Menge aufgelistet Die daraus entstandene Liste bildet das Herz einer ereignisgesteuerten Simulation Zus tzlich wer den verschiedene Ereignistypen definiert um unterschiedliche Ereignisse auszul sen 2 Die prozessorientierte Simulation sie umschlie t die ereignisgesteuerte mit einer Reihe von Merkmalen die ein deutlich h heres Niveau an den Tag legen und die das Schreiben Debuggen und Verstehen eines Simulations modells verst ndlic
203. zessen gew hlt werden Der Algorithmus l uft wie folgt ab 1 Verhalten eines normalen Prozesses Alle Prozesse besitzen einen Z hler c der mit 0 initialisiert wird e Eine Nachricht m wird mit einer eindeutigen Nachrichtenkennung i in der Form lt m i gt gesendet e Bei Empfang einer Nachricht wird diese in eine R ckhalte Warte schlange gelegt e Bei Empfang einer Sortiernachricht des Sequenzers die eine Ord nungsnummer S und eine Nachrichtenkennung der Form lt S i gt enth lt wird solange gewartet bis die Nachricht mit der entsprechen den Kennung in der Warteschlange eingegangen ist und die Ordnungs nummer S c 1 ist Dann wird die entsprechende Nachricht aus der R ckhalte Schlange entfernt und der Z hler c S gesetzt 3 3 Koordination und bereinstimmung 27 2 Verhalten des Sequenzers e _ Der Sequenzer besitzt einen eigenen Z hler S der mit 0 initialisiert wird e Bei Erhalt einer Nachricht mit der Kennung lt m i gt wird eine Sortiernachricht mit der Kennung der empfangenen Nachricht i sowie dem Wert des aktuellen Z hlers S lt S i gt gesendet Anschlie end wird der Z hler erh ht S S 1 Aber auch dieser Algorithmus hat den Nachteil dass er auf den Sequenzer und dessen Zuverl ssigkeit angewiesen ist vgl Coulouris et al 02 S 516ff Totale Reihenfolge durch Zeitsteuerung Ein dezentraler Ansatz f r ei ne totale Reihenfolge ist der eine Zeitsteuerung zu verwenden

Download Pdf Manuals

Related Search

Related Contents

InFocus IN120 Series Datasheet (Latin Spanish)  SERVICE MANUAL - MiniDisc Community Page  Insignia NS-24LD120A13 Flat Panel Television User Manual  User Guide  Gigabar - pb-Showtechnik  Olympus FE-220 Basic manual  módulo de administración de grupos de vehículos  Manual de instalación y Guía del usuario  NMEA USB Merger  PIXE King 法文说明书 PSM15 V10.02  

Copyright © All rights reserved. Failed to retrieve file