Lezione 7. Modelli a stati

[GJM91, sez. 5.5.2], [BRJ99, Capp. 19, 20, 21]

Finite State Machines - definizioni, applicabilita’, esempi
Prodotto di FSM
XFSM: Extended FSM
Reti di XFSM
Esempio: Dispatcher
UML State diagrams e Statecharts
UML Activity diagrams






Slide 1
Formalismi rispetto Data/Function/Control
FSM = Finite State Machines
XFSM = Extended FSM
PN = Petri Net
Pr/T = Predicate/Transition
O-O = Object-Oriented Design
DFD = Data Flow Diagrams
ER = Entity-Relation diagrams
ADT = Abstract Data Types
Z
Slide 2
FSM - Definizioni










Un FSM e’ una quintupla M = (Q, q0, F, I, d), dove:
Q insieme finito di stati
q0  Q
stato iniziale
FQ
stati finali
I alfabeto finito di inputs
d funzione di transizione d : Q x I --> Q, tipicam. parziale
Un FSM e’ rappresentato da un grafo diretto:
i
Arco q1
q2 sse d(q1, i) = q2
Mealy FSM: viene associato anche un output a ogni transizione
Moore FSM: viene associato un output a ogni stato
Slide 3
Applicabilità di FSMs
input
FSM
output
* Descrive aspetti di controllo del sistema. Lo stato della FSM è il ‘luogo’ corrente del
controllo, come il program counter
* Caratterizza la reattività del sistema: il suo comportamento in risposta a stimoli
* Descrive anche aspetti funzionali del sistema, modellando una funzione che trasforma il
flusso di input in flusso di output
Data flow e FSM sono entrambi modelli comportamentali. Una FSM non mostra il flusso dei dati fra
parti del sistema, ma è associabile a un nodo di un data-flow diagram
* Utilizzabile in fase Requirements per modelli astratti del sistema, per software
specification, e in fase di (Detailed) Design per modellare algoritmi
Slide 4
Esempio - Controllo di impianto chimico
Restart
Versione base
Raffinamento
Slide 5
FSM per generazione/riconoscimento di linguaggi regolari
a
m
o
i
a
a
m
o
Linguaggio
finito
n
t
e
Linguaggio
infinito
Slide 6
Esercizio

Con quale State Machine si genera il linguaggio
infinito delle espressioni di parentesi bilanciate?


()
( () ( ( ) ) )

()

……...
(
( ( ) ( ) ) (( ) ( ) (( ))) ( ) )
( ( ) ( () ) )
Slide 7
Composizione di FSM
Per ottenere un modello a stati di un sistema complesso
a partire dai modelli a stati dei sottosistemi, assumendo interazione a
rendez-vous (transizioni condivise).
produce
Producer
consume
write
Buffer
read
Consumer
Questa composizione in LOTOS si esprime così:
(Producer[produce, write]
|[read, write]|
Buffer[read, write]
|||
Consumer[read, consume])
Slide 8
FSM di Producer[produce, write]...
produce
p1
p2
write
Slide 9
...Consumer[read, consume]...
c1
read
consume
c2
Slide 10
...Buffer[read, write]
b0
b1
b2
read
read
write
write
Slide 11
Prodotto degli stati
b0
b1
c1
read
b2
c1
read
c1
produce
p1
read
p2
write
p2
p1
p2
consume
c2
p1
p1
write
p2
c2
p1
write
p2
c2
p1
p2
Slide 12
verso Producer  Consumer  Buffer...
b2
b1
c1 produce
read
c1 produce
read
produce
c2
p1
consume
produce
p2
write
write
c2
produce
p1
p2
p1
write
consume
write
p2
consume
read
p1
consume
write
p2
consume
consume
p1
c1
write
write
produce
p2
produce
consume
b0
c2
p1
p2
Slide 13
Producer  Consumer  Buffer
produce
produce
write
produce
consume
consume
consume
write
consume
produce
consume
consume
write
produce
produce
write
Slide 14
Extended FSM (XFSM)
Trattano anche i dati, e la loro trasmissione
Slide 15
XFSM = (States, Vars, Trans, InQs, OutQs)





States = insieme di stati, con stato iniziale
Vars = insieme di variabili (locali)
Trans = insieme di transizioni etichettate
InQs = insieme di code di segnali/messaggi in input
OutQs = insieme di code di segnali/messaggi in output
Slide 16
Formato generale di una transizione
Input
da qualche InQs
From
state
Output
su qualche OutQs
Se...
Condizione su Vars
To
state
Effetto su Vars
…allora
Esempio
s5
In3 ? incr(dy)
[x = 0 AND y  99]
Out2 ! ‘ok’
y := y + dy
s7
Slide 17
Rete di XFSM’s = (X, Q)



X = {X(1), …, X(n)} insieme di XFSM’s
Q = insieme di code incluso in (Q’  Q”)
Q’ = {q(1), …, q(n)}
•

Q” = {q(i,j) | 1i n, 1 j  n, i  j}
•


Q(i) = coda in input a X(i)
q(i,j) = coda da X(i) a X(j)
X(i) usa le code q(j) in Q’
X(i) usa le code q(i,j) in Q”
(j  i)
(j  i)
Slide 18
Esempio - Dispatcher a 2 input
ChanA
ReplA
ChanA ? a1: msg
[Parity(a1) = OK,
lengthQ < 10]
ChanB...
ChanB
lengthQ := 0
...
Q := append (Q, a1);
lengthQ := lengthQ+1
ReplB
[lengthQ = 10]
ProcessingUnit ! Q;
Q := nil; lengthQ := 0
Processing
Unit
Q := nil
ChanA ? a1: msg
[Parity(a1)  OK]
ReplA! ‘nack’
s1
Control ? ‘stop’
ChanB...
s2
Control
...
Slide 19
Statecharts - generalità


Interaction diagrams modellano cooperazione fra parecchi
oggetti nell’ambito di una singola use-case;
statecharts
•
•

modellano comportam. di singolo oggetto (che deve rispondere a stimoli
asincroni, a comportamento dipendente dal passato) nell’ambito di parecchie
use case.
Ma modellano anche: interfacce, sotto-sistemi
Activity diagrams enfatizzano attività e passaggio di controllo;
statecharts enfatizzano
•
•
•
•
stati, transizioni di stato dovute a una serie di possibili
eventi,
risposte del sistema agli eventi (reattività),
e ordinamento delle transizioni
Slide 20
Esempio di statechart
Slide 21
Stati
Struttura generale
Puo’ mancare
(stato anonimo)
Inoltre lo stato puo’ avere sottostati, sequenziali o concorrenti
Puo’ essere un’altra
SM, o una sequenza di
azioni.
Entrambe sono
interrompibili da eventi
che fanno uscire da
‘Tracking’
Slide 22
Transizioni

Source state
•

Event trigger
•
•

valutata subito dopo trigger event; se
FALSA, trigger event è perduto; puo’
riferirsi a stati di altre SM.
/ Action
•

signal, op call,
time (‘after’), state change (‘when’)
[Guard condition]
•

anche piu’ di uno
..
.
atomica - signal, op call su questo o
altri oggetti visibili; creaz. / distr. di
oggetti
Target state
•
anche piu’ di uno
Slide 23
Eventi
Eventi asincroni:
- segnale,
- pass. di tempo,
- cambio di stato
- operation call asincrona
Eventi sincroni
- operation call
(sincrona, di default)
Eventi interni ed esterni...
Slide 24
- Segnale (evento asincrono)

E’ un oggetto che viene spedito (thrown) dall’oggetto A e ricevuto
(caught) dall’oggetto B
•


Tipicamente modella ‘eccezioni’ (C++, Java)
Appare come
•
•
•

Subito dopo la spedizione, A è libero di procedere; non attende risultati
causa o effetto di una trans. in una state machine
etichetta di una interazione in interaction diagram
effetto di una operazione di un dato oggetto
che possono
essere ricevuti
Un segnale è simile a una classe
•
•
puo’ avere attributi (i parametri trasmessi), e operazioni
puo’ formare gerarchie di generalizzazione
Slide 25
Gerarchie di segnali - Eccezioni
Gerarchie di segnali:
modellano i tipi di segnale che un oggetto attivo può ricevere
Una transizione causata da HardwareFault puo’ essere causata
anche da BatteryFault, MovementFault, ...
Template class
(parametric)
Le eccezioni che un oggetto
puo’ spedire (throw)
attraverso le sue operazioni
Slide 26
- Call (evento sincrono)

L’oggetto A chiama Op() di B, e B ha una state machine
SM(B):
•
•
•
•
•
il controllo passa da A a B, con A in attesa
la transizione (s1) ==> (s2) con trigger event Op() in SM(B) viene
iniziata
Op() viene completamente eseguita (è una delle operazioni di B)
Lo stato finale (s2) viene raggiunto in SM(B)
Il controllo torna ad A, che riceve anche l’eventuale risultato della
operazione
Tuttavia sono possibili anche call asincrone, e call a oggetti senza SM.
Messaggi non previsti vengono lasciati cadere.
Slide 27
- Passaggio di tempo, cambiamento di stato
(eventi asincroni)
Passaggio di tempo:
- ‘after’ + espressione temporale
Cambiamento di stato o condizione:
- ‘when’ + espressione booleana
che viene valutata continuamente
Oppure:
‘when altitude < 1000’
Oppure:
‘after 1 ms since exiting idle’
Slide 28
Sottostati sequenziali - History state
I sottostati
ereditano le transizioni
dei superstati
(H*) denota deep history state
Lo stato finale cancella la storia
Slide 29
Sottostati concorrenti (ortogonali)
In alternativa a un oggetto la cui SM ha sottostati concorrenti, si possono usare piu’ oggetti attivi
Slide 30
Esempio da [F77]
/ get first item
[not all items checked]
/ get next item
Checking
do / check item
[all items checked
&& some items not in stock]
[all items checked
&& all items available]
Dispatching
do/ initiate delivery
Item Received [all items available]
Delivered
Item Received
[some items not in stock]
Waiting
Delivered
Xxx = Trigger event
Slide 31
/ get first item
[not all items checked]
/ get next item
[all items checked
&& all items available]
Checking
do / check item
[all items checked
&& some items not in stock]
Item Received
[some items not in stock]
Dispatching
do/ initiate delivery
Item Received [all items available]
Delivered
Waiting
Cancelled
Delivered
Delivered
Slide 32
cancelled
Cancelled
Waiting
Checking
Dispatching
delivered
Delivered
Authorizing
Authorized
Rejected
Slide 33
Oggetti con/senza state machine

Oggetti senza state machine
•
reagiscono solo a messaggi sincroni, cioè operation calls
» se arrivano messaggi asincroni, cioe segnali, sono ignorati
•

Oggetti con state machine
•
•

comportamento indipendente dalla loro storia
devono reagire anche a segnali, e
in modo dipendente dalla storia
Anche le interfacce possono avere statemachines, che vengono regolarmente ereditate
Slide 34
Activity diagrams




Mentre interaction diagrams (simili a Gantt charts)
enfatizzano le interazioni fra oggetti che si scambiano
messaggi (e flusso di controllo)
… activity diagrams enfatizzano le attività che vengono
svolte dagli oggetti, e lo scambio di flusso di controllo da
attività a attività.
Sono simili a flow charts, e a Pert charts usati per
documentare il workflow di un progetto.
In UML sono usati anche per modellare la dinamica di:
•
•
•
•
sistema, sottosistema, classe
operazione (==> flow-chart delle singole azioni)
uno scenario di una use case
collaborations
Slide 35
Esempio
(another activity diagram)
Slide 36
Action state / activity state; branch
Action (esecuzione atomica, e rapida…):
- call operation
- send signal
- create/destroy an object
- compute expression and assign var.
(i messaggi che etichettano i link
degli interaction diagrams,
e le transizioni delle statecharts)
Un activity state può avere entry/exit actions,
come gli stati delle statecharts
= nested activity diagram, o state machine
Unico tipo di trans.;
esecuzione istantanea
Slide 37
Join, fork; swimlanes
1 ==> N
M ==> 1
(*) Fork e join si devono bilanciare, come le
parentesi in una espressione.
(**) La state machine di Synch mouth()
puo’ mandare messaggi
alla state machine di Stream audio()
(***) La presenza di oggetti manipolati dalle attività
rende i diagrammi simili ai data flow
Slide 38
Activity diagram come flow-chart...
…per descrivere il funzionamento di operazioni (di classi)
Slide 39