Kapitel 7 State-Machines/Zustandsautomaten

Page 175-205

Vorgetragen von:

Ulrich Dinger

Inhalt

(1) Einfacher Zustandsautomat+Statecharts

(2) Anwendung auf Objektorientierte Software

(3) Das „FREE-state“- Modell(4) Das „fault“- Modell

(5) Test- Modell- Entwicklung

(6) N+ als Beispiel

(7) Macht und Grenzen der Zustandsautomaten

(1)(1)Was ist ein Zustandsautomat?

Ein System, dessen Ausgabe durch aktuelle und vergangene Eingaben bestimmt wird.

Effekt vergangener Eingaben wird durch Zustand symbolisiert.

Hintergrund ist mathematisches Model der „endlichen Automaten“

Aufbau eines Zustandsautomaten(Mealy- Automat)

Zustand (state) Übergang (transition) =

Ausgelöst duch Ereignis Ereignis (event) Aktion (action) = Ergebnis

oder Ausgabe

Weitere Erläuterungen (1/2)

Begonnen wird mit „Start-Zustand“ Zu einem Übergang gehört ein Paar von

Zuständen: akzeptierender und resultierender Zustand (können identisch sein)

Der Automat kann nur in genau einem Zustand zu einem bestimmten Zeitpunkt sein

Im Endzustand werden keine Ereignisse mehr akzeptiert

Weitere Erläuterungen (2/2)

Der Automat wartet auf Ereignis für unbestimmte Zeit

Ereignisse präsentieren sich dem Automaten selbst Nicht akzeptiertes Ereignis wird ignoriert Wenn Ereignis akzeptiert, wird Übergang ausgeführt

und resultierender Zustand wird aktueller Zustand Wiederholt sich, bis der aktuelle Zustand

Endzustand ist

Beschränkungen

Prozess, von dem Ereignisse erzeugt, .. Ist nicht Teil des Modells

Ereignisse werden einmal erkannt, Übergang einmal ausgeführt

Aktuelle Zustand kann nur durch Übergang geändert werden

Modell ist statisch Algorithmen etc. nicht Teil des Modells Black-Box-

Prinzip Keine Angaben über Zeit

Beispiele

Verhalten von GUI Lebenszyklen von Klassen Kommunikationsgeräten Geräte-Treibern Parsern

ist modellierbar.

Zustands-Übergangs-Diagramm

Graphische Darstellung Knoten repräsentieren

Zustände (1 und 2) An Übergangen stehen

Ereignisse (A und B) und Aktionen (X,Y und Z)

(phi) als „keine Aktion“

Bsp: Automatisches Füllen eines Wassertanks

Einige Eigenschaften der endlichen Zustandsautomaten

Übergänge aller möglichen Ereignis/Zustand-Paare (sonst nicht komplett)

Äquivalenz von Zuständen

Minimale Zustandsautomaten

Erreichbarkeit

Erreichbarkeit

Dead state – „tote“ Zustände

Dead loop – Unendliche Schleife

Magic state – extra Startzustand

Überwachte Übergänge

Bevor Übergang ausgeführt wird muß erfüllt sein:

1. Zustand muß erreicht sein

2. Überwachtes Ereignis tritt auf

3. Überwachendes Prädikat gibt TRUE zurück

UML: ereignis-name argument-liste [ überwachungs-bedingung ] / aktions-ausdruck

Arten von ZustandsautomatenMealy vs. Moore

Sind mathematisch äquivalent Gibt Algorithmen zur Umwandlung

untereinander Mealy- Automaten werden bevorzugt

angewandt

Mealy: Eigenschaften

Nur Übergänge können Ausgaben produzieren Jede Ausgabe kann in mehreren Übergängen

benutzt werden Keine Ausgaben in Zuständen erlaubt

Zustände sind passiv

Moore: Eigenschaften

Übergänge haben keine Ausgaben Ausgaben sind mit Zuständen verbunden

Zustände sind aktiv Jede Ausgabe hat mindestens einen

entsprechenden Zustand

Zustands- Übergangs- Tabellen

Diagramme nur für relative wenige (bis max. 20) Zustände geeignet

Deshalb tabellarische Form:

1. Zustand- zu- Zustand- Tabelle (state to state)

2. Ereignis- zu Zustand- Tabelle (event to state)

3. Erweitertes Zustand- zu- Zustand- Tabelle (expanded state to state)

Alle Modelle gleichen Informationsgehalt

Grenzen des einfachen Modells

(1) Ist nicht spezifisch für OO-Systeme (später)

(2) Begrenzte Skalierbarkeit (bei großen Projekten schwer, Namen für Zustände zu finden, ...) Lösung ist Hierarchiebildung

(3) Keine Nebenläufigkeit modellierbar (Lösung wäre „product machine“ oder Statecharts)

Statecharts – Erweiterterung der Zustandsautomaten

Modellierung von „control requirements of complex reactive systems“

Zustand kann Zusammenfassung mehrerer Zustände (=superstate) oder alleinstehender Zustand sein

Repräsentieren „single-thread“ und nebenläufige Zustandsautomaten

Modell innerhalb einer Zusammenfassung ist ein Prozess

Nebenläufigkeit mit Statecharts

2 oder mehr unabhängige aber verwandte Prozesse

dargestellt durch geteilte „superstates“ AND-decomposition

Statecharts - Zusammenfassung

Statecharts = Zustandsdiagramm + Tiefe + Orthogonalität + Broadcast Kommunikation– Tiefe: Vereinfachung, die durch Hierarchiebildung

erreicht wird– Orthogonalität: Nebenläufigkeit von 2 oder mehr

Prozessen– Broadcast: Alle Automaten sehen sich

untereinander und Ausgabe des einen kann Eingabe des anderen sein

(2)Zustandautomaten und OO-Entwicklung

Statecharts wurden in verschiedenen Analysesystemen und UML eingebunden

Gibt verschiedene Umsetzungen, z.B. Harel, UML, ...; z.B. bei Umsetzung der Nebenläufigkeit

In diesem Buch wird UML benutzt

Implementierung von Zustandsautomaten

1. „hard-code“ der Tabellenstruktur mit switch und ifelse- Ausdrücken (aber: fehleranfällig und schwer zu übersehen)

2. Object for state pattern3. Martin‘s Tree-Level FSM4. State-pattern5. Schmidt‘s Reactor pattern6. Dyson und Anderson

(3)Das „FREE-state“-Modell (Überblick)

Flattened Regular Expression (FREE) = „abgeflachter regulärer Ausdruck“

Klasse, die getestet wird, wird „abgeflacht“ Jeder Zustandsautomat hat äquivalenten

regulären Ausdruck FREE-state-Modell-Beschränkungen und –

Definitionen nicht in UML festgehalten

Objekt-Zustand bei Methoden-Aktivierung und –Deaktivierung von Interesse

Ausgehende Nachricht zu Server modelliert als Übergang mit Aktion

Grenzen des OOA-Verhaltensmodellen

Nützlich für Entwurf, nicht ausreichend für Testen

Testbares Modell muß folgendes erfüllen:– Komplett (alles zu Testende enthalten)– Abstraktion dessen, was Test unmöglich machen

würde– Enthält essentiell wichtige Details– Enthält alle Ereignisse, auf die geantwortet werden

muß

– Definiert Zustand so, daß Folgezustand automatisch gecheckt werden kann

– Wächter in ausführbarem Syntax– Manuelles Testen nicht ausschließen

Wenn Modell in UML diesen Bedürfnissen entspricht, folgt es den FREE-Defininitonen und Conventionen.

Fin