TECHNISCHE Spezifikationssprachen UNIVERSITÄT … · Flache Struktur (keine Hierarchie) ... Zustandsautomat . ... der Aufzeichnung der Anforderungen und der detailierten Abarbeitung

Verhaltensbeschreibung und Spezifikationssprachen TECHNISCHE

UNIVERSITÄT

ILMENAU

Inte

grie

rte

Kom

mun

ikat

ions

syst

eme

http

://w

ww

.tu-il

men

au.d

e/ik

s

Verhaltensmodelle Zustandsautomaten (FSM) Nicht-deterministische

Zustandsautomaten (NDFSM) Parallele Zustandsautomaten Petri-Netz (PN) Datenflussgraph (DFG) Kontrollflussgraph (CFG) Kontroll-Datenflussgraph (CDFG)

Spezifikationssprachen StateCharts SDL VHDL SystemC ...

Grundkonzepte Nebenläufigkeit Hierarchie Kommunikation Synchronisation Ausnahmebehandlung Nicht-Determinismus Timing

Integrated Communication Systems 2 Andreas Mitschele-Thiel 14-Nov-16

Zustandsautomaten: Finite State Machines (FSM)

Funktionelle Dekomposition in (Bearbeitungs- oder System-) Zustände

Endliche (finite) Zustandsmenge, Ein- und Ausgangsalphabet Verarbeitet Eingangszeichenfolge zu Ausgangszeichenfolge Zeichen = Wert einer Variablen (SW) oder eines Vektors

(Belegung) (HW) Zustandsübergänge (Transitionen): zeitlos, ereignisgesteuert, deterministisch Ausgänge schalten synchron oder asynchron zu

Zustandsübergängen, deterministisch Keine Nebenläufigkeit (sequentieller Automat) Flache Struktur (keine Hierarchie)

Typische Anwendungen:

reaktive (Steuerungs-)Systeme Protokolle (Telekommunikation, Systembaugruppen, …)


Beispiel Fahrstuhlsteuerung

Identifikation des zu entwickelnden Systems (Analyse) Umgebung/Schnittstellen: - Aktoren (Antrieb) für Auf- und Abfahrt - Aktoren (Antriebe) für Türen - Aktoren (Anzeigen) auf Etage und im

Aufzug - Bediensensoren (auf Etagen und im

Aufzug) - Zustandssensoren (Etagen, Türen) - Sicherheitsspezifische Sensorik

System: - Steuerung der Aktoren auf Basis der

Eingaben/Sensorik


Beispiel Fahrstuhlsteuerung: Identifikation des Systems


Beispiel Fahrstuhlsteuerung: Identifikation des Systems Identifikation der Schnittstellen der Steuerung und Abgrenzung von der Umgebung

?

?


Beispiel Fahrstuhlsteuerung: Spezifikation der Schnittstellen Identifikation der Schnittstellen: Sensorik/Input und Aktorik/Output der Steuerung

Sensorik: x0 - x3: Eingabe Zieletage im Aufzug X4 - x7: Kontakt zur Meldung der Position (Etage) des Aufzugs x8 - x10: Eingabe zur Anforderung des Aufzugs in Abwärtsrichtung je Etage x11- x13: Eingabe zur Anforderung des Aufzugs in Aufwärtsrichtung je Etage X14 – x15: Bedientaste im Aufzug zum Öffnen bzw. Schließen der Tür

Aktorik: y0 – y1: Antriebssteuerung auf und ab y2- - y7: Anzeige zur Bestätigung der Aufzugsanforderung für auf und ab (je Etage) y8 – y11: Anzeige der gewählten Zieletage(n) im Aufzug y12 – y15: Anzeige der Aufzugsposition (Etage 1-4) im Aufzug (ggf. auch auf Etagen) y16 – y17: Antriebssteue-rung für Türantrieb


Beispiel Fahrstuhlsteuerung: Spezifikation der Schnittstellen

Sensorik: Realisierung von Tastern und Schaltern? Taster, z.B für Fahrstuhlanforderung

Einfacher Taster: kurzzeitige “1” des Tasters wird von Fahrstuhlsteuerung abgetastet und in FSM gespeichert

Intelligenter Taster: Event wird an Steuerung geschickt und resultiert in Speicherung der Anforderung in FSM

Schalter, z.B. für Signalisierung der Etage oder der Türenendlagen Einfacher Schalter => Ein- oder Ausschaltungen werden als zwei

verschiedene Zustände des Schalters von Fahrstuhlsteuerung periodisch abgetastet; explizite Speicherung des Zustands in FSM nicht mehr nötig

Intelligenter Schalter: Ein- oder Ausschaltungen werden als zwei verschiedene Events an Fahrstuhlsteuerung gesendet und entsprechend in FSM gespeichert; Besondere Maßnahmen für/nach Reset der FSM nötig

Intelligente Sensorik: Einfache Steuerung => Kommunikationssystem, Verteiltes System


Beispiel Fahrstuhlsteuerung: Spezifikation der Schnittstellen

Aktorik: Ansteuerung von Motoren und Anzeigeelementen? Türantrieb

Einfache Ansteuerung mit 3 Zuständen: auf, zu, halt; Motor läuft während Signal anliegt, sonst nicht

Intelligente Türsteuerung: Steuersignale (Events) zum Öffnen und Schließen der Tür, integrierte automatische Endabschaltung und Meldung der Endabschaltung (Sensorik)

LED-Etagenanforderungsanzeige auf Etage (bzw. im Fahrstuhl) Einfache Ansteuerung jeder LED die direkt aus Zustand der FSM

(Ausgabelogik) abgeleitet wird Integriertes Fahrstuhl-Anforderungsmodul (kombinierte

Sensorik/Aktorik): Generierung von Events wenn Taste (auf/ab) gedrückt wird und lokale Einschaltung der LED, Empfang eines Events zum Löschen der LED wenn Aufzug ankommt

Intelligente Sensorik/Aktorikmodule: Einfache Steuerung => Kommunikationssystem, Verteiltes System


Moore Automaten: nicht-reaktiv

(nur um 1 Takt verzögerte Reaktion) Einfach zu entwerfen

(Zustandsübergang bei Ausgangswechsel) für Implementierung in SW geeignet

software is always “slow”

Mealy Automaten: reaktiv (unmittelbare Reaktion auf Eingangsänderungen) Schwieriger zu entwerfen für SW-Implementierung weniger gut geeignet

Wegen unmittelbarer Reaktion auf Eingangsänderungen (interrupts/polling) Software muss schnell genug sein (Echtzeitforderung) “fast enough”

In Hardware für schnelle Reaktion sinnvoll, aber asynchron!

Hier: typischerweise eventgetriggerte Automaten => Event (statt Takt) löst sofortigen Zustandsübergang aus

Abgrenzung zu Moore und Mealy Automaten

d d d X

aZ Y nZ

d d d X

aZ

Y nZ


Unterschiede zw. Event- und Zeitgetriebenen Automaten

Eventgetriebe Automaten verhalten sich etwas anders als über Eingangsvariablen gesteuerte Mealy- oder Moore-Automaten

Eventgetriebene Automaten: Events ähneln semantisch den Flanken der Eingangsvariablen

zeitgetriebener Automaten, d.h. Event führt zu einer Transistion, d.h. Taktung der FSM

Der “Zustand” der Eingangsvariable muss, wenn er für das System auch später noch relevant ist, anders als bei Mealy- oder Moore-Automaten sich im Zustand es Automaten niederschlagen und darüber implizit gespeichert werden

d ggf. Vergrößerung des Zustandsraums d modifizierte Ansteuerung der Ein- und Ausgabeschnittellen, d.h.

Events können sich zeitlich überschneiden und werden evtl. sequentiell abgearbeitet

d Zeitliches Verhalten kann sich ändern Beispiel Fahrstuhlsteuerung: hier könnten die Eingaben als Variable oder

auch als Events realisiert werden, mit entsprechenden Folgen für die Realisierung des Steuerungsautomaten


Beispiel Fahrstuhlsteuerung: Zustandsautomat


Finite State Machines – Diskussion

Vorteile: Einfach nutzbar (Graphische Darstellung) Mächtiges Ausdrucksmittel für

Synthese (SW and HW) Verifikation

Nachteile:

manchmal über-spezifizierte Implementierung (z.B. Zählfolge (Bsp: alle Etagen) vollständig als

Zustandsübergänge spezifiziert) Anzahl der Zustände kann unbeherrschbar werden (im Bsp. viele

Etagen, mehrere Aufzüge) Numerische Berechnungen können nicht kompakt (z.B. in Form

von Operationen) spezifiziert werden

=> erweiterte FSMs (informal, formal)


Beispiel Fahrstuhlsteuerung: Vereinfachung der Spezifikation

Vereinfachung durch Divide & Conquer-Strategie: - Parallele Automaten: Entkopplung z.B.

- der detailierten Türsteuerungen mit automatischer Endabschaltung von der abstrakten Fahrstuhl-Etagensteuerung,

- der detailierten Aufzugsmotorsteuerung und Geschwindigkeitsregelung von der abstrakten Etagensteuerung (Missionssteuerung)

- der Aufzeichnung der Anforderungen und der detailierten Abarbeitung der Anforderungen

- Hierarchie: - Trennung der Steuerung des Systems bei fahrendem

Aufzug vom Betrieb bei stehendem Aufzug (Tür) - Vererbung:

- Detailverhalten der Tür je Etage ist identisch - Kopplung der Automaten über Hierarchiewechsel und

Kommunikation (Variable oder Events)


Finite State Machines – Erweiterungen

Prinzip: “Divide and conquer” d Nichtdeterminismus

d Parallele Automaten

d Prozesse

d Hierarchie

d Kommunikation

d Timer

d Grafische Unterstützung

d erweiterte (formale) Semantik


FSM => NDFSM: Zeitbereichsspezifikation

Nichtdeterminismus: Spezialfall von unspezifiziertem bzw. unbekanntem Verhalten, aber geeignet zur effizienten Beschreibung (nichtdeterminierter Zustandsübergang = nicht bestimmt, welcher Folgezustand aus einer Menge gültiger Folgezustände angenommen wird) Beispiel: nichtdeterministische Verzögerung (z.B. zwischen 6 und 10 s)

0

1 2 3 4

5

6

7 8

9

START => SEC =>

SEC => END

SEC => SEC =>

SEC =>

SEC =>

SEC => SEC =>

SEC =>

START =>

SEC => END

SEC => END

SEC => END


NDFSMs und FSMs

Formal sind FSMs und NDFSMs äquivalent (Rabin-Scott construction, Rabin ‘59)

Praktisch sind NDFSMs meist kompakter (weniger Zustände) (exponentielle Zustandsexplosion um Determiniertheit zu erreichen)

Beispiel: nicht-deterministische Auswahl von Übergang a in Zustand s1

s1

s2 s3

a a

b

a

c

s1

s2,s3

a

s3 b

a

s2

c

b a

c

äquivalente deterministische FSM


Modellierung von Parallelität – parallele Automaten

Systeme bestehen typisch aus Teilen mit relativ unabhängigen Funktionen, z. B. Sicherheitsgurt-Steuerung || timer || Fahrer Systeme können physisch verteilt sein, z. B. Kommunikationsprotokolle mit verteilten Automaten Teile, die mit FSMs beschrieben sind, müssen zusammengebracht (“komponiert”)

werden Konstruktion eines vollständigen Systemmodells Kartesisches Produkt aller Zustände führt zu Zustandsexplosion Ansatz: Systembeschreibung mit separaten FSMs und deren Verbindung (Kopplung) Problem Wie kommunizieren die gekoppelten FSMs?

a) alle FSMs wechseln Zustand gleichzeitig (synchronicity), d.h. Systemzustand = kartesisches Produkt der Zustände der Komponenten oder

b) FSMs laufen asynchron und sind über (asynchrone) Events gekoppelt => SDL


FSM Komposition – Beispiel

Beispiel: Sicherheitsgurt || timer

Beispiel Sicherheitsgurt-Steuerung: •5 sec nach Betätigen des Zündschlüssels soll ein Alarmsignal solange ertönen, wie der Gurt nicht angelegt ist. •Nach 10 sec soll der Alarm beendet werden.

KEY_ON => START_TIMER

END_TIMER_5 => ALARM_ON

KEY_OFF or BELT _ON =>

END_TIMER_10 or BELT_ON or KEY_OFF => ALARM_OFF

WAIT

ALARM

OFF

Belt

Control

Timer



Beispiel: seat belt control || timer

0

1 2 3 4

5 6 7 8 9

START_TIMER =>

START_TIMER =>

SEC =>

SEC => END_TIMER_10

SEC => SEC => SEC => END_TIMER_5

SEC => SEC => SEC => SEC =>

Belt

Control

Timer

KEY_ON => START_TIMER

END_TIMER_5 => ALARM_ON

KEY_OFF or BELT _ON =>

END_TIMER_10 or BELT_ON or KEY_OFF => ALARM_OFF

WAIT

ALARM

OFF



OFF, 0 WAIT, 1

KEY_ON and START_TIMER => START_TIMER muss zusammen passieren

WAIT, 2

SEC and not (KEY_OFF or BELT_ON) =>

OFF, 1

not SEC and (KEY_OFF or BELT_ON) =>

OFF, 2

SEC and (KEY_OFF or BELT_ON) =>

Kartesisches Produkt


Finite State Machines – Erweiterungen: parallele Automaten


Finite State Machines – Beispiel: Zustandsdiagramm (informal)


FSM Erweiterungen – Beispiel: Interaktion/Prozesse

Start (Inter-)aktion (Re-)aktionsfolge . . . . Ende (vs. FSM: zyklisch)


FSM Erweiterungen – Kommunikation (MSC)


Hierarchische FSM Modelle – StateCharts

Problem: Wie reduziert man die Repräsentationgröße? Harel’s Veröffentlichung: StateCharts (language) and bounded concurrency (model): 3 orthogonale exponentielle Reduktionen Hierarchie:

Zustand a “encloses”, d.h. schließt eine FSM ein “in a” bedeutet: eine FSM in a ist aktiv Zustände von a heißen OR-Zustände Nützlich zur Modellierung von Voraussetzungen

und Ausnahmen (z. B. “Reset”) Parallelität:

2 oder mehr FSMs sind gleichzeitig aktiv Zustände heißen AND-Zustände

Nichtdeterminiertheit: Zur Verhaltensabstraktion

error

a

recovery

odd

even

done

a1 a2


StateCharts – Grundprinzipien

Grundlagen: Erweiterung konventioneller FSMs konventionelle FSMs für komplexe Verhaltensbeschreibungen ungeeignet

flach und unstrukturiert von Natur aus sequentiell

StateCharts unterstützen wiederholte Zerlegung von Zuständen in Sub-Zustände mit AND/OR, sowie synchrone Kommunikation (unmittelbare Übertragung an alle (Broadcast))

Zustandsdekomposition: OR-Zustände haben sub-Zustände, die in einer exclusive-or Relation stehen AND-Zustände haben “orthogonale” d. h. parallele Zustandskomponenten (synchrone FSM Komposition)

AND-Dekomposition auf jeder Hierarchiestufe von Zuständen erlaubt (besser handhabbar als nur eine Stufe (Strukturebene) kommunizierender FSMs)

Basis-Zustände (Basic states) haben keine sub-Zustände (unterste Hierarchie) Root-Zustände haben keine “Eltern”-Zustände (oberste Hierarchieebene)


StateCharts – OR Dekomposition

S

V

T

S

V

T

f

f

f

e

h

e

h

g g

Um in Zustand U zu sein, muss das System entweder in Zustand S oder in Zustand T sein

U

Zustand U ist eine Abstraktion der Zustände S und T

Documents

TECHNISCHE Spezifikationssprachen UNIVERSITÄT … · Flache Struktur (keine Hierarchie) ... Zustandsautomat . ... der Aufzeichnung der Anforderungen und der detailierten Abarbeitung