Post on 03-May-2015
transcript
Slide 1
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 2
Formalismi rispetto Data/Function/ControlFSM = Finite State MachinesXFSM = Extended FSMPN = Petri NetPr/T = Predicate/TransitionO-O = Object-Oriented DesignDFD = Data Flow DiagramsER = Entity-Relation diagramsADT = Abstract Data Types
Z
Slide 3
FSM - Definizioni
Un FSM e’ una quintupla M = (Q, q0, F, I, ), dove: Q insieme finito di stati q0 Q stato iniziale
F Q stati finali I alfabeto finito di inputs funzione di transizione : Q x I --> Q, tipicam. parziale
Un FSM e’ rappresentato da un grafo diretto: Arco sse (q1, i) = q2
Mealy FSM: viene associato anche un output a ogni transizione Moore FSM: viene associato un output a ogni stato
q1 q2i
Slide 4
Applicabilità di FSMs
FSMinput 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 outputData 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 5
Esempio - Controllo di impianto chimico
Versione base Raffinamento
Restart
Slide 6
FSM per generazione/riconoscimento di linguaggi regolari
a m
o
i a m o
at e
n
Linguaggiofinito
Linguaggioinfinito
Slide 7
Esercizio
Con quale State Machine si genera il linguaggio infinito delle espressioni di parentesi bilanciate?
( ) ( () ( ( ) ) )
( ) ( ( ( ) ( ) ) (( ) ( ) (( ))) ( ) ) ( ( ) ( ( ) ) ) ……...
Slide 8
Composizione di FSM
Producer ConsumerBuffer
consume
readwrite
produce
Questa composizione in LOTOS si esprime così:
(Producer[produce, write] ||| Consumer[read, consume])|[read, write]| Buffer[read, write]
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).
Slide 9
p1 p2write
produce
FSM di Producer[produce, write]...
Slide 10
c2
c1
consumeread
...Consumer[read, consume]...
Slide 11
b2b0 b1
read read
write write
...Buffer[read, write]
Slide 12
c1
c2
c1
c2
p1 p2
p1 p2p1 p2
p1 p2
p1 p2
p1 p2write
produce
Prodotto degli stati
c2
c1
consumeread
b2b0 b1
read read
write write
Slide 13
verso Producer Consumer Buffer...
c1
c2
c1
c2
p1 p2
p1 p2p1 p2
p1 p2
p1 p2
p1 p2write
produce
c2
c1
consumeread
b2b0 b1
read read
write write
produce
produceproduceproduce
produceproduce
write
write write
write
read rea
d
read rea
d
con
sum
e
con
sum
e
con
sum
e
con
sum
e
con
sum
e
con
sum
e
Slide 14
Producer Consumer Buffer
produce
produceproduceproduce
produceproduce
write
write write
write
read rea
d
read rea
d
con
sum
e
con
sum
e
con
sum
e
con
sum
e
con
sum
e
con
sum
e
Slide 15
Extended FSM (XFSM)
Trattano anche i dati, e la loro trasmissione
Slide 16
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 17
Formato generale di una transizione
Fromstate Output
su qualche OutQs
Input da qualche InQs
Tostate
Condizione su Vars
Effetto su Vars
s5Out2 ! ‘ok’
s7[x = 0 AND y 99]
y := y + dy
In3 ? incr(dy)
Esempio
Se...
…allora
Slide 18
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(i) = coda in input a X(i)
Q” = {q(i,j) | 1i n, 1 j n, i j}• q(i,j) = coda da X(i) a X(j)
X(i) usa le code q(j) in Q’ (j i) X(i) usa le code q(i,j) in Q” (j i)
Slide 19
Esempio - Dispatcher a 2 input
ChanA
s2
Control
Q := nil
lengthQ := 0
ChanB
ReplAReplB
ProcessingUnit
s1
ChanA ? a1: msg[Parity(a1) = OK,lengthQ < 10]
Q := append (Q, a1);lengthQ := lengthQ+1
ReplA! ‘nack’
ChanA ? a1: msg[Parity(a1) OK]
[lengthQ = 10]ProcessingUnit ! Q;Q := nil; lengthQ := 0
ChanB...
...
...
Control ? ‘stop’
ChanB...
Slide 20
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 21
Esempio di statechart
Slide 22
Stati
Struttura generale
Inoltre lo stato puo’ avere sottostati, sequenziali o concorrenti
Puo’ mancare(stato anonimo)
Puo’ essere un’altraSM, o una sequenza di azioni.Entrambe sono interrompibili da eventi che fanno uscire da ‘Tracking’
Slide 23
Transizioni
Source state• anche piu’ di uno
Event trigger• signal, op call,
• time (‘after’), state change (‘when’)
[Guard condition]• valutata subito dopo trigger event; se
FALSA, trigger event è perduto; puo’ riferirsi a stati di altre SM.
/ Action• atomica - signal, op call su questo o
altri oggetti visibili; creaz. / distr. di oggetti
Target state• anche piu’ di uno
. ..
Slide 24
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 25
- Segnale (evento asincrono)
E’ un oggetto che viene spedito (thrown) dall’oggetto A e ricevuto (caught) dall’oggetto B
• Subito dopo la spedizione, A è libero di procedere; non attende risultati
Tipicamente modella ‘eccezioni’ (C++, Java) Appare come
• 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
Un segnale è simile a una classe• puo’ avere attributi (i parametri trasmessi), e operazioni
• puo’ formare gerarchie di generalizzazione
che possonoessere ricevuti
Slide 26
Gerarchie di segnali - EccezioniGerarchie di segnali:modellano i tipi di segnale che un oggetto attivo può ricevereUna transizione causata da HardwareFault puo’ essere causata anche da BatteryFault, MovementFault, ...
Le eccezioni che un oggetto puo’ spedire (throw)attraverso le sue operazioni
Template class(parametric)
Slide 27
- 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 28
- Passaggio di tempo, cambiamento di stato (eventi asincroni)
Oppure:‘after 1 ms since exiting idle’
Passaggio di tempo: - ‘after’ + espressione temporale
Cambiamento di stato o condizione: - ‘when’ + espressione booleana che viene valutata continuamente
Oppure:‘when altitude < 1000’
Slide 29
Sottostati sequenziali - History state
(H*) denota deep history state
Lo stato finale cancella la storia
I sottostati ereditano le transizioni dei superstati
Slide 30
Sottostati concorrenti (ortogonali)
In alternativa a un oggetto la cui SM ha sottostati concorrenti, si possono usare piu’ oggetti attivi
Slide 31
Esempio da [F77]
Checking Dispatching
Waiting Delivered
[all items checked&& all items available]
[all items checked&& some items not in stock] Item Received [all items available] Delivered
do / check item do/ initiate delivery
/ get first item
[not all items checked]/ get next item
Item Received [some items not in stock]
Xxx = Trigger event
Slide 32
Checking Dispatching
Waiting
Delivered
[all items checked&& all items available]
[all items checked&& some items not in stock] Item Received [all items available] Delivered
do / check item do/ initiate delivery
/ get first item
[not all items checked]/ get next item
Item Received [some items not in stock]
Delivered
Cancelled
Slide 33
Waiting
Delivered
Checking Dispatching
Cancelled
Rejected
Authorizing Authorized
cancelled
delivered
Slide 34
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
• comportamento indipendente dalla loro storia
Oggetti con state machine• devono reagire anche a segnali, e• in modo dipendente dalla storia
Anche le interfacce possono avere state-machines, che vengono regolarmente ereditate
Slide 35
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 36
Esempio
(another activity diagram)
Slide 37
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)
= nested activity diagram, o state machine
Un activity state può avere entry/exit actions, come gli stati delle statecharts
Unico tipo di trans.;esecuzione istantanea
Slide 38
Join, fork; swimlanes
1 ==> NM ==> 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 39
Activity diagram come flow-chart...
…per descrivere il funzionamento di operazioni (di classi)