Sintassi- Semantica operazionale
• Dato un linguaggio definito da una sintassi
esprimere il suo significato
• Ci sono vari modi …..
• Uno possibile e’ “tradurre” i suoi costrutti in
un altro linguaggio noto
ad es: da C as ASSEMBLER
1
Linguaggio FSP
• La sua sintassi e’ data come insieme di
operatori che compongono processi
• Operatori: prefisso, scelta, parallelo, …..
• Processi: STOP,
espressioni che compongono azioni
espressioni che compongono processi
2
Quale linguaggio per la sua semantica
operazionale?
Le Reti di Automi Sovrapposti (SA Net):
un linguaggio
concorrenti
per
la
specifica
di
sistemi
grafico ma con una base formale ben definita
sintassi molto semplice ma potente
approccio composizionale (come FSP)
3
Il punto di vista
“Un sistema è una parte del mondo che una persona o un gruppo di
persone, durante un certo intervallo di tempo, sceglie di
considerare come un tutto formato di componenti interagenti”
Ciascuna componente ha propri stati ed evolve per effetto di
azioni, scelte locali e per effetto di interazioni con altre
componenti.
4
La potenza espressiva
• Stati, azioni e interazioni
• Localita’ di stati e azioni
• Il comportamento globale ‘emerge’ dalla composizione di
comportamenti locali
• Facilita’ di cogliere la natura distribuita dei processi reali
5
Semantica ben definita
• Derivano dalle Reti di Petri un modello
matematico sottostante
• Operatori , leggi di composizione e
strumenti modellistici potenti e ben fondati
• Tools di supporto per descrizioni complesse
6
Pochi costrutti: struttura delle attivita’
• Stati
:
• Azioni :
• Causalita’:
detto posto
detta transizione
detto flusso
• Le transizionizioni sono etichettate:
– a, b, c, … azioni visibili
– tau
azioni invisibili
7
Un esempio
A
B
s1
a
e
s5
s3
a
s4
b
b
s2
s7
g
c
s6
s8
d
d
8
Localita’
• ogni stato e’ definito dalle azioni locali che
lo producono e che sono da esso dipendenti
• ogni transizione e’ definita dagli stati locali
da cui dipende e che essa genera
9
Pochi costrutti: il comportamento
• Lo stato corrente e’ rappresentato da una
‘marca’ :
• Stato = condizione vera/falsa
• Il comportamento e’ rappresentato in
termini di cambiamento di stato:
– Regola di scatto di una transizione
10
Concessione e regola di scatto
di una transizione
Un transizione può scattare quando sono marcati tutti i suoi posti di ingresso:
un’azione può avere luogo quando tutte le sue precondizioni sono verificate.
scatto
Lo scatto di una transizione toglie la marca da tutti i suoi posti di ingresso e mette
una marca in tutti i suoi posti di uscita: il verificarsi dell’azione rende false le
sue precondizioni e rende vere le postcondizioni.
11
Un esempio ….
A
B
s1
a con B
e con X
s5
s3
a con A
s4
b
b
s2
s7
c con Y
s8
g
s6
d con A e C
d con B e C
12
Modellazione di realta’ complesse
• Una disciplina per costruire il modello
basata su:
– Approccio bottom-up
• Derivare le componenti del sistema dalla realta’
• Costruzione di modelli per ciascuna di esse
(componenti elementari)
• Comporre tali modelli nel sistema complessivo
13
componente elementare
Non contiene concorrenza ma solo non determinismo.
È una macchina a stati (un automa a stati finiti) con:
• il nome della componente elementare che rappresenta
• i posti interpretati come stati locali della componente elementare
• le transizioni interpretate come azioni individuali
o di interazione
• la marcatura iniziale definita dal posto che rappresenta
lo stato iniziale
14
Un esempio con una notazione particolare
mi alzo
fork
mi vesto
faccio colazione
join
esco
15
Convenzione
In una componente elementare,
FORK-JOIN indica che le transizioni
comprese possono essere eseguite in ogni
ordine possibile, rispettando le relazioni
causali espresse.
16
Dalle componenti al sistema
Un sistema e’ costruito per composizione dei
modelli delle sue componenti elementari
Due operazioni di composizione che si basano
sulla dualita’ tra posti e transizioni
17
T- composizione
La T- composizione avviene in tre fasi:
1- distinguendo le azioni locali alla componente dalle sue interazioni con
altre componenti:
etichettatura delle transizioni
2- sovrapponendo le transizioni con la stessa etichetta
e attribuendo alla transizione risultante come posti di ingresso/uscita
l’insieme dei posti di ingresso/uscita delle transizioni sovrapposte.
3- se in ciascuna componente compaiono più transizioni che
rappresentano la stessa interazione, la sovrapposizione di transizioni è
operata solo dopo aver generato in ogni componente un opportuno
numero di copie di tali transizioni.
18
Un esempio semplice
19
Un esempio
A
A
B
s1
a con B
s5
a con A
s2
a
e con X
s5
s4
s3
s3
s4
b
b
b
s1
s2
e con X
B
g
s7
s6
g
s7
b
s6
c con Y
c con Y
d con A e C
s8
d con B e C
s8
d con C
20
S-composizione (opzionale)
• Identificando i posti che rappresentano lo stesso stato in
diverse componenti
• Sovrapponendo tali posti e attribuendo al posto risultante
come transizioni di ingresso/uscita l’insieme delle
transizioni di ingresso/uscita dei posti sovrapposti.
– Consente la semplificazione del modello
in alcune situazioni (Buffer)
– Consente la costruzione incrementale del modello
(simulando gli operatori di scelta e di prefisso del
linguaggio FSP)
21
Esempi
Utente
Componente A
invio
Componente B
ricezione
Il posto in rosso e’ un buffer
Decide di
fare altro
Fa altro
Decide di usare
la risorsa
Usa la
risorsa
Rilscia la
risorsa
Il posto in giallo si puo’ sovrapporre ad un posto
della componente utente, generando una scelta
22
Il modello risultante
Una rete SA è un grafo orientato con due tipi di nodi, posti e
transizioni, alternativamente connessi da archi orientati in modo
tale che:
a)
non ci siano nodi isolati
b)
due posti o due transizioni non siano mai connessi
c)
ogni transizione abbia lo stesso numero di archi entranti e
uscenti (a meno dei buffer)
d)
l’insieme dei posti sia ripartibile in classi disgiunte
che costituiscono gli stati di ciacuna componente
(a meno dei buffer)
23
Un esempio
s1
s2
a
e con X
s5
s3
s4
b
g
s7
b
s6
c con Y
s8
d con C
24
Conflitto e concorrenza
Due transizioni si dicono in conflitto tra loro quando hanno
entrambe concessione e condividono almeno un posto di
ingresso.
a
c
b
d
e
f
Due transizioni si dicono concorrenti quando hanno concessione
sotto la stessa marcatura e non sono in conflitto fra loro
25
Non-determinismo globale e locale
• Quale componente decide il comportamento
congiunto?
B
s1
s2
A
B
t3
t1
A
t2
A
t4
s1
s3
s2
s4
t2
t1
s3
s7
s5
s6
s8
B
t3
t2
s4
26
Uso del modello risultante
Il modello risultante serve per provare proprietà del sistema tramite
strumenti capaci di trattare la complessità di sistemi reali, facendo
uso del modello matematico sottostante:
costruzione del modello complessivo
generazione delle possibili evoluzioni
(Grafo di raggiungibilita’)
calcolo di proprieta’ invarianti
calcolo di performance
ecc.
27
Dato il sistema SA
A
B
A
s1
B
s2
a con B
s5
a con A
s4
s1
s2
a
e con X
s3
b
b
g
s7
s3
d con B e C
s4
s6
b
d con A e C
s7
c con Y
s8
s5
b
g
s6
c con Y
s8
d con C
28
Il suo Grafo di Raggiungibilità e’:
< s1, s2 >
e con x
a
< s 3 , s2 >
b
< s 5 , s4 >
g
b
< s1, s2 >
< s7, s4 >
c con y
g
< s 8 , s4 >
g
< s5, s6 >
b
< s7, s6 >
c con y
< s8, s6 >
d con C
< s1, s2 >
tutti i
comportamenti
possibili
29
Il corrispondente FSP e’:
A = (e_conX --> b --> A |
a_conB --> b --> c_conY --> d_conBeC -->A)
B = (a_conA --> g --> d_conAeC --> B
A_B = (A || B ) (i colori indicano le azioni da sovrapporre)
Il cui LST e’ isomorfo al precedente grafo di raggiungibilita’:
stesso numero di nodi (stati),
stesso numero di archi con eguale etichettatura
30
Nozione di osservabilita’
e di Equivalenza all’Osservazione
La nozione di osservabilita’ consente di modellare un sistema
focalizzandosi sul modo in cui esso comunica con
l’ambiente,
astraendo dalla sua organizzazione interna (cioe’ dalla sua
suddivisione in componenti e dalle modalità con cui queste
interagiscono)
Due sistemi sono equivalenti all’osservazione
se non sono distinguibili da nessun possibile ambiente
31
Operativamente …
• Si identificano le azioni interne e le si etichetta
convenzionalmente con tau
• Un osservatore non le puo’ distinguere
• Si etichettano con tau anche le interazioni tra
componenti
• Un osservatore non le puo’ distinguere
• [Si riduce il sistema (in modo automatico)
eliminando le tau non necessarie]
32
Operativamente …
• Quello che resta e’ la struttura delle interazioni
con l’ambiente
– Comunicazioni (visibili)
– Alcune tau che servono per esprimere la struttura
causale
• Il confronto tra sistemi si fa seguendo tutti i
cammini possibili (in modo automatico)
33
Un esempio
C1
C
a
C2
s2
tau
a
s4
b
C3
b
s6
tau
c
c
tau
34
Attenzione
• I contenuti delle slide che seguono NON
fanno parte del programma del corso
• Si lasciano per completezza rispetto all’uso
delle Reti SAcome linguaggio di specifica
35
Motivazione per strumenti di supporto
• La modellazione di un sistema puo’ avvenire in modo
incrementale in diversi modi:
– Aggiungendo cammini alternativi
– Precisando la definizione di una azione in una struttura di azioni
piu’ elementari
– Modificando il numero di componenti che costituiscono il sistema
• Necessita’ di concetti specifici per governare questo
processo
36
Tre nozioni per la modellazione incrementale:
•
Estensione funzionale
•
Raffinamento/astrazione funzionale
•
Raffinamento/astrazione organizzativo
37
Estensione funzionale
L’Estensione Funzionale amplia i possibili comportamenti
di un sistema e/o di una o più delle sue componenti:
si realizza tramite la S-composizione
Le estensioni funzionali consentono di considerare sistemi
con funzionalita’ man mano più complesse.
La duplicazione delle transizioni per consentire la T-composizione e’ un caso di
raffinamento funzionale.
Si ricordi l’esempio precedente .....
38
Raffinamento funzionale
Il Raffinamento Funzionale isola una transizione o un posto
e la/lo sostituisce con una sottorete
in modo che sia comunque garantita la trasformazione di stato
definita nel modello di partenza.
39
Raffinamento funzionale: esempi
40
Raffinamento organizzativo
Il Raffinamento Organizzativo isola una componente di un sistema
e la sostituisce con un insieme di componenti
in modo che sia comunque mantenuto
il comportamento che la componente esibisce al suo ambiente.
Sono necessarie delle nozioni di supporto ...
41
T-Scomposizione
E’ l’operazione inversa alla T-Composizione: permette di estrarre
dal sistema il modello di una componente elementare o di alcune
componenti elementari.
42
Passi da eseguire iterativamente
• Fissare un livello di astrazione
– Quali componenti ?
– Quale atomicita’ delle azioni e interazioni?
• Verificare la coerenza delle descrizioni locali identificando
le diversita’ dei punti di vista di chi fornisce la conoscenza
• Allineare le descrizioni per raggiungere la coerenza
• Eventualmente modificare il livello di astrazione, su tutto o
parte del sistema, a seconda degli scopi
e ripetere i passi precedenti
43
Documentare il processo di acquisizione
• Il team può sviluppare tutti i modelli necessari,
esplicitando quelli che lascia impliciti (ambiente),
legando gli uni e gli altri con relazioni dal significato
rigorosamente definito (gli operatori applicati),
fissando per ciascun modello l’opportuno livello di
astrazione
• La distinzione in componenti facilita la localizzazione di
possibili incoerenze e la estensione del comportamento
attraverso la progettazione di componenti di correzione.
44