Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
AUTOMAZIONE II
ANALISI DI RETI DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STRUTTURA DEL NUCLEO TEMATICO
•
•
•
RETI DI PETRI TEMPORIZZATE
ANALISI DI RETI DI PETRI
IMPLEMENTAZIONE SOFTWARE DELLE RETI DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI
TEMPORIZZATE
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
STRUTTURA DI CLOCK
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , data una transizione 𝑡𝑗 ∈ 𝑇 si definisce struttura
di clock della transizione 𝑡𝑗 l’insieme:
𝑽𝑗 = 𝑣𝑗,1 , 𝑣𝑗,2 , … , 𝑣𝑗,𝑘 , …
𝑣𝑗,𝑘 𝜖ℝ\ 0
La struttura di clock assume il seguente significato: quando la transizione 𝒕𝒋 è
abilitata per la k-esima volta essa viene sparata dopo 𝒗𝒋,𝒌 unità di tempo.
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x possiamo partizionare l’insieme delle transizioni in
due insiemi disgiunti, 𝑇0 e 𝑇𝐷 , detti rispettivamente insieme delle transizioni non
temporizzate e insieme delle transizioni temporizzate.
𝑇 = 𝑇0 ⋃𝑇𝐷
𝑇0 ⋂𝑇𝐷 = ∅
Le transizioni temporizzate subiscono un ritardo di scatto determinato dalla propria
struttura di clock, a differenza delle transizioni non temporizzate che scattano subito.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x , si definisce struttura di clock di una rete di
Petri il seguente insieme:
𝑽 = 𝑽𝑗 | 𝑡𝑗 ∈ 𝑇𝐷
DEFINIZIONE
Si definisce rete di Petri temporizzata la seguente sestupla:
𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x, V
OSSERVAZIONE
Data una rete di petri temporizzata 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x, V , per distinguere le transizioni non
temporizzate da quelle temporizzate, queste ultime vengono rappresentate con un
rettangolo invece che con una barra.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
ESEMPIO
Consideriamo un sistema informatico client-server come quello rappresentato in figura:
Buffer infinito
Arrivo richiesta
da un Client
•
•
•
•
•
Server
Elaborazione richiesta
di un Client
I sistemi client richiedono un insieme di servizi ad un sistema server;
Le richieste vengono memorizzate in un buffer di memoria di dimensione infinita;
Il server processa le richieste in maniera seriale con una politica di scheduling
FIFO;
Quando il server inizia ad elaborare una richiesta essa viene eliminata dal buffer;
Quando il server ha elaborato una richiesta diventa di nuovo disponibile per elaborare
la successiva richiesta presente nel buffer.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
EVENTI e TRANSIZIONI
Gli eventi che caratterizzano il sistema sono pertanto:
1. L’arrivo di una richiesta di servizio, ovvero l’ingresso di tale nella coda;
2. L’inizio della elaborazione da parte del server di una richiesta e sua eliminazione dalla
coda;
3. Termine della elaborazione da parte del server di una richiesta.
Ad ogni evento possiamo associare una transizione;
STATI e POSTI
Lo stato del sistema è costituito da:
1. Numero di richieste presenti nel buffer;
2. Stato del server attivo, se sta processando una richiesta;
3. Stato del server in condizioni di riposo, se non sta processando alcuna richiesta.
Pertanto è intuitivo associare ad ogni elemento dello stato un posto.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Definiamo pertanto l’insieme dei posti:
𝑃 = 𝑝1 , 𝑝2 , 𝑝3
Dove:
• 𝑝1 rappresenta il buffer;
• 𝑝2 rappresenta il server in condizioni di attività;
• 𝑝3 rappresenta il server in condizioni di riposo.
Definiamo l’insieme delle transizioni:
𝑇 = 𝑡1 , 𝑡2 , 𝑡3
Dove:
• 𝑡1 rappresenta l’evento associato all’arrivo di una nuova richiesta;
• 𝑡2 rappresenta l’evento di inizio elaborazione di una richiesta;
• 𝑡3 rappresenta l’evento termine elaborazione di una richiesta.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Disegniamo posti e transizioni ed identifichiamo l’insieme delle azioni e relativi pesi.
Arrivo nuova
richiesta
Buffer
Inizio processamento
richiesta
Server attivo
Termine processamento
richiesta
t1
p1
t2
p3
t3
Server riposo
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Disegniamo posti e transizioni ed identifichiamo l’insieme delle azioni e relativi pesi.
Arrivo nuova
richiesta
Buffer
Inizio processamento
richiesta
Server attivo
Termine processamento
richiesta
t1
p1
t2
p3
t3
Server riposo
p2
L’arrivo di una nuova richiesta può scattare
incondizionatamente, pertanto I(t1)= ∅.
L’arrivo di una nuova richiesta aumenta di uno la
coda di attesa nel buffer pertanto lo scatto di tale
transizione aggiunge un token al posto p1.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Disegniamo posti e transizioni ed identifichiamo l’insieme delle azioni e relativi pesi.
Arrivo nuova
richiesta
Buffer
Inizio processamento
richiesta
Server attivo
Termine processamento
richiesta
t1
p1
t2
p3
t3
Server riposo
L’inizio del processamento di una richiesta può
avvenire solo se:
1. c’è almeno una richiesta nel buffer;
2. il server è a riposo.
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Disegniamo posti e transizioni ed identifichiamo l’insieme delle azioni e relativi pesi.
Arrivo nuova
richiesta
Buffer
Inizio processamento
richiesta
Server attivo
Termine processamento
richiesta
t1
p1
t2
p3
t3
Server riposo
L’inizio del processamento di una richiesta attiva il
server.
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Disegniamo posti e transizioni ed identifichiamo l’insieme delle azioni e relativi pesi.
Arrivo nuova
richiesta
Buffer
Inizio processamento
richiesta
Server attivo
Termine processamento
richiesta
t1
p1
t2
p3
t3
Server riposo
Per terminare il processamento di una richiesta è
necessario che il server sia attivo.
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Disegniamo posti e transizioni ed identifichiamo l’insieme delle azioni e relativi pesi.
Arrivo nuova
richiesta
Buffer
Inizio processamento
richiesta
Server attivo
Termine processamento
richiesta
t1
p1
t2
p3
t3
Server riposo
Quando termina il processamento di una richiesta
il server torna a riposo.
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
La marcatura (ovvero lo stato) iniziale è di buffer vuoto e server a riposo.
Arrivo nuova
richiesta
Buffer
Inizio processamento
richiesta
Server attivo
Termine processamento
richiesta
t1
p1
t2
p3
t3
Server riposo
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Supponiamo che:
• le richieste da parte dei client (transizione t1) arrivino in istanti noti a priori;
• una richiesta venga processata non appena il server è a riposo;
• ogni richiesta richieda un tempo noto a priori per essere terminata.
Dunque:
t1, v1
𝑇 = 𝑇0 ∪ 𝑇𝐷 = 𝑡2 ∪ 𝑡1 , 𝑡3
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Definiamo i seguenti istanti:
• ak sia l’istante di arrivo della k-esima richiesta;
• sk sia l’istante di inizio elaborazione della k-esima richiesta;
• ek sia l’istante di terminazione dell’elaborazione della k-esima richiesta;
• P1,k sia l’istante in cui il posto p1 (buffer) riceve il k-esimo gettone;
• P2,k sia l’istante in cui il posto p2 (server pronto) riceve il k-esimo gettone;
• P3,k sia l’istante in cui il posto p3 (server occupato) riceve il k-esimo gettone.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
All’istante di tempo t = 0 abbiamo la Rete di Petri nello stato iniziale.
Nello stato iniziale il posto p2 ha un token, pertanto P2,1 = 0.
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
All’istante di tempo t = a1, abbiamo:
1. Lo scatto della transizione t1 (pertanto v1 = a1) che porta il primo token in p1
pertanto P1,1 = a1;
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
All’istante di tempo t = a1, abbiamo:
1. Lo scatto della transizione t1 che porta il primo token in p1 pertanto P1,1 = a1;
2. La transizione t2 non è temportizzata, pertanto scatta e un token viene aggiunto
nel posto p3 pertanto P3,1 = a1;
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
All’istante di tempo t = a1, abbiamo:
1. Lo scatto della transizione t1 che porta il primo token in p1 pertanto P1,1 = a1;
2. La transizione t2 non è temportizzata, pertanto scatta e un token viene aggiunto
nel posto p3 pertanto P3,1 = a1 = s1;
3. Notiamo che la transizione t3 è temportizzata, pertanto NON scatta prima di v3,1
unità di tempo
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Notiamo che negli istanti di tempo t > a1 abbiamo:
1. La transizione temporizzata t1 che scatterà nuovamente al tempo a2 = a1 + v1,2 ;
2. La transizione temporizzata t3 che scatterà nuovamente al tempo e1 = P3,1 + v3,1;
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
All’istante di tempo t = P3,1 + v3,1 abbiamo:
1. La terminazione della elaborazione della prima richiesta, pertanto e1 = P3,1 + v3,1;
2. Lo scatto della transizione t3 che porta il secondo token in p2 pertanto P2,2 = e1;
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
All’istante di tempo t = a1 + v1,2 abbiamo il secondo scatto della transizione temporizzata
t1 che:
• è rappresentativo dell’arrivo della seconda richiesta a2 = a1 + v1,2
• porta il secondo token in p1 pertanto P1,2 = a2 ;
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
OSSERVAZIONE
Non sappiamo quale delle due transizioni temporizzate scatterà per prima.
Ma sappiamo che per scattare, la transizione non temporizzata t2 ha necessità che
entrambe le transizioni siano scattare. Ovvero:
s2 = max {P1,2 ; P2,2 }
t1, v1
p1
t2
p3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3, v3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Per la prima richiesta abbiamo:
• a1 = v1,1
• s1 = P1,1
• e1 = P3,1 + v3,1
• P1,1 = a1
• P2,1 = 0
• P3,1 = s1
Per la seconda richiesta abbiamo:
• a2 = a1 + v1,2
• s2 = max {P1,2 ; P2,2 }
• e1 = P3,1 + v3,1
• P1,2 = a2
• P2,2 = e1
• P3,2 = s2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
Pertanto ipotizzando che a0 = e0 = 0 sia ha che:
• ak = ak-1 + v1,k
k = 1,2,…
• sk = max {P1,k ; P2,k }
k = 1,2,…
• ek = P3,k + v3,k
k = 1,2,…
• P1,k = ak
k = 1,2,…
• P2,k = ek-1
k = 1,2,…
• P3,k = sk
k = 1,2,…
Sostituendo P1,k , P2,k e P3,k si ottiene:
• ak = ak-1 + v1,k
k = 1,2,…
• sk = max {ak ; ek-1}
k = 1,2,…
• ek = sk + v3,k
k = 1,2,…
Da cui si ottiene che ogni chiamata viene terminata nei seguenti istanti:
ek = max {ak ; ek-1} + v3,k
k = 1,2,…
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RETI DI PETRI SINCRONIZZATE
L’equazione appena trovata rappresenta un modello degli istanti di tempo di fine servizio:
ek = max {ak ; ek-1} + v3,k
k = 1,2,…
SI
ek =
v3,k +
ak
ak > ek-1 ?
NO
ek-1
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ANALISI
DI RETI DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x una marcatura x′′ϵℕ 𝑃 si dice raggiungibile da
una marcatura x′ϵℕ 𝑃 se esiste una sequenza di scatti la cui esecuzione a partire dalla
marcatura x′ porta la rete nella marcatura x′′.
OSSERVAZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x ogni marcatura xϵℕ 𝑃 è raggiungibile da sé
stessa, in quanto è sufficiente considerare la sequenza di scatti nulla.
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 si definisce insieme delle marcature
raggiungibili dallo stato iniziale 𝒙𝟎 l’insieme:
𝑅 𝑁 = x𝜖ℕ 𝑃
∃𝑠 𝑓 x0 , 𝑠 = x
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 una marcatura x ϵ ℕ 𝑃 si dice marcatura di
base se essa è raggiungibile da qualsiasi altra marcatura x′ϵℕ 𝑃 .
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 se la marcatura iniziale x0 è una marcatura di
base allora la rete si dice reversibile.
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 una transizione 𝑡𝑗 𝜖 𝑇 dicesi viva se per ogni
marcatura raggiungibile da x0 , x ϵ 𝑅 𝑁 esiste una marcatura x′, raggiungibile da x (e
quindi x′ ϵ 𝑅 𝑁 ) che abilita 𝑡𝑗 . Se una transizione non è viva dicesi morta.
OSSERVAZIONE
Una transizione viva può scattare infinite volte, infatti ogni suo scatto porta la rete
in una marcatura raggiungibile e quindi, per definizione, può nuovamente scattare.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
ESEMPIO
Calcoliamo l’insieme di raggiungibilità della seguente rete di Petri:
1
𝑰= 0
0
0 0
1 0
0 1
0 0
𝑶= 1 0
0 1
0
1
0
1
𝑿𝟎 = 0
0
Innanzitutto tracciamo il grafo di Petri:
p1
t1
p2
t2
p3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
Notiamo che:
• quando scatta t1, p1 non avrà più modo di guadagnare token, in quanto nessuna
transizione alimenta tale posto;
0
𝑿𝟏 = 1
0
p1
t1
p2
t2
p3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
Notiamo che:
• quando scatta t1, p1 non avrà più modo di guadagnare token, in quanto nessuna
transizione alimenta tale posto;
• quando scatta t2, non sia né perdita né generazione di token;
0
𝑿𝟐 = 0
1
p1
t1
p2
t2
p3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
Notiamo che:
• quando scatta t1, p1 non avrà più modo di guadagnare token, in quanto nessuna
transizione alimenta tale posto;
• quando scatta t2, non sia né perdita né generazione di token;
0
• quando scatta t3, non sia né perdita né generazione di token;
𝑿𝟑 = 1
0
p1
t1
p2
t2
p3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
Notiamo che:
• quando scatta t1, p1 non avrà più modo di guadagnare token, in quanto nessuna
transizione alimenta tale posto;
• quando scatta t2, non sia né perdita né generazione di token;
• quando scatta t3, non sia né perdita né generazione di token;
• Le uniche marcature possibili sono 𝑿𝟏 e 𝑿𝟐 che scattano infinitamente.
𝑿𝟑 = 𝑿𝟏
p1
t1
p2
t2
p3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
Pertanto:
𝑹 𝑵 = 𝑿𝟎 , 𝑿𝟏 , 𝑿𝟐 =
1
0
0
0 , 1 , 0
0
0
1
Notiamo inoltre che le transizioni t2 e t3 sono vive, mentre la transizione t1 è morta.
p1
t1
p2
t2
p3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
DEFINIZIONE
Se tutte le transizioni di una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 sono vive allora 𝑁 è
detta rete viva.
DEFINIZIONE
Data una rete di petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 essa è detta bloccante se esiste una marcatura
raggiungibile da x0 in cui nessuna transizione è abilitata.
OSSERVAZIONE
Una rete di petri bloccante è sicuramente non viva. Ma non tutte le reti non vive sono
necessariamente bloccanti. La rete vista nell’esempio precedente è una caso di rete non
viva, ma non bloccante.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
OSSERVAZIONE
Tutte le transizioni di una rete bloccante sono morte.
• Se per assurdo una rete bloccante avesse una transizione viva, per definizione per
ogni marcatura raggiungibile dalla marcatura inziale, esisterebbe un’altra marcatura
raggiungibile che abilita tale transizione.
• Ma dato che la rete è bloccante esiste almeno una marcatura raggiungibile da quella
iniziale in cui non è abilitata alcuna transizione. Pertanto, non potendo evolvere, tale
marcatura non può raggiungere altra marcatura se non sé stessa. Ma, essendo
bloccante, nessuna transizione è attiva.
• Pertanto è impossibile che esista una transizione viva!
ESEMPIO
La rete di Petri
in figura è bloccante.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
DEFINIZIONE
Data una rete di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 un posto 𝑝𝑖 ϵ𝑃 è detto k-limitato se:
∀ x 𝜖 𝑅 𝑁 → x 𝑝𝑖 ≤ 𝑘
𝑘 𝜖 ℕ ,𝑘 < ∞
Ovverosia se per ogni marcatura raggiungibile dallo stato iniziale il numero di token in un
determinato posto è limitato (in particolare minore o uguale a k). Un posto per cui non
esiste un k che lo renda k-limitato è detto posto illimitato.
DEFINIZIONE
Se tutti i posti di una rete di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 sono k-limitati allora la rete è detta
rete limitata.
DEFINIZIONE
Un rete di Petri limitata per k = 1 è detta safe o binaria.
DEFINIZIONE
Un rete di Petri che ammette un posto illimitato è detta illimitata.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
RAGGIUNGIBILITÀ
ESEMPIO
Consideriamo la rete di Petri in figura:
p1
t1
p2
t2
p3
Possiamo notare che:
• Tutte le transizioni sono vive. Quindi la rete è viva.
• I posti p1 , p2 e p3 sono k-limitati per k=1, ma è illimitato;
• La rete è pertanto illimitata.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
t3
p4
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ANALISI GRAFICA
DELLE RETI DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
DEFINIZIONE
Per semplificare l’analisi della raggiungibilità di una rete di Petri è utile introdurre una
notazione grafica detta albero di raggiungibilità. In particolare:
• Ogni nodo dell’albero di raggiungibilità rappresenta una marcatura;
• Il nodo radice è la marcatura iniziale;
• I nodi che si trovano ad un livello k dell’albero sono tutte e sole quelle marcature
raggiungibili da quella iniziale almeno con k scatti di transizioni;
• Gli archi orientati che connettono un nodo di livello k ai suoi figli al livello k+1 sono
le transizioni.
OSSERVAZIONE
Per come è definito l’albero di raggiungibilità:
• Rappresenta in maniera grafica l’insieme di raggiungibilità;
• Mostra tutte le sequenze di scatti ammissibili.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
Tracciamo l’albero di raggiungibilità della rete di Petri in figura e studiamone le proprietà
di raggiungibilità.
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
Partiamo dalla marcatura iniziale e procediamo con una politica depth-first. Ovvero
scendiamo in ogni foglia prima di passare all’elemento successivo dello stesso livello.
[0 1 0 1]
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
L’unica transizione che può scattare è t1.
[0 1 0 1]
t1
[1 1 0 0]
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
L’unica transizione che può scattare è t2.
[0 1 0 1]
t1
[1 1 0 0]
t2
[0 0 1 1]
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
Possono scattare sia t1 che t3 . Senza perdita di generalità facciamo scattare t1.
[0 1 0 1]
t1
[1 1 0 0]
t2
t1
[0 0 1 1]
[1 0 1 0]
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
Facciamo scattare t3 . Si giunge ad una foglia che è una marcatura già visitata, pertanto
tale ramo dell’albero è terminato.
[0 1 0 1]
t1
[1 1 0 0]
t2
t1
[0 0 1 1]
[1 0 1 0]
t3
p4
t1
t2
p1
[1 1 0 0]
Già visitato
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
Ritorniamo alla marcatura [0 0 1 1] e facciamo scattare t3 . Si giunge ad una foglia che è
una marcatura già visitata, pertanto tale ramo dell’albero è terminato.
[0 1 0 1]
t1
[1 1 0 0]
t2
t1
[0 0 1 1]
p4
t3
[1 0 1 0]
t2
[0 1 0 1]
Già visitato
t1
t2
p1
[0 0 1 1]
Già visitato
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
ESEMPIO
Si deduce che l’insieme di raggiungibilità è:
𝑹 𝑵 =
[0 1 0 1]
1
0
1
0
1 , 1 , 0 , 0
0
0
1
1
1
0
0
1
t1
[1 1 0 0]
t2
Inoltre possiamo notare che:
• Comparendo solo 0 ed 1, la rete è safe (binaria);
• Essendo la marcatura iniziale una foglia, e dato che tutte le
foglie sono marcature già visitate da cui si può sempre
raggiungere la marcatura iniziale, la rete è reversibile. t
[0 0 1 1]
t1
t3
[1 0 1 0]
[0 1 0 1]
Già visitato
2
[0 0 1 1]
Già visitato
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
OSSERVAZIONE
Fintanto che l’insieme di raggiungibilità di una rete di Petri è finito, è possibile tracciare
l’albero di raggiungibilità. Ma come si fa a tracciare l’albero di raggiungibilità di una rete
illimitata?
ESEMPIO
Riprendiamo l’esempio del sistema client-server con buffer infinito.
t1
p1
t2
p3
t3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Tracciamo l’albero di raggiungibilità
[0 1 0]
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Facciamo scattare t1.
t1
[0 1 0]
[1 1 0]
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Possiamo far scattare sia t1 che t2.
t1
t1
[0 1 0]
[1 1 0]
t2
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Possiamo far scattare sia t1 che t2. Facciamo scattare t2
t1
t1
[0 1 0]
[1 1 0]
t2
[0 0 1]
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Possiamo far scattare sia t1 che t2. Facciamo scattare t2 e poi t3
t1
t1
[0 1 0]
[1 1 0]
t2
[0 0 1]
t3
[0 1 0]
Già visitato
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Torniamo alla marcatura [1 1 0] e facciamo scattare t1.
[0 1 0]
t1
t1
[1 1 0]
t2
[0 0 1]
[2 1 0]
t1
t2
t3
[0 1 0]
Già visitato
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Torniamo alla marcatura [1 1 0] e facciamo scattare t1. È facile notare che possiamo far
scattare t1 infinite volte, giungendo sempre in nuove marcature…
[0 1 0]
t1
t1
[1 1 0]
t2
[0 0 1]
[2 1 0]
t1
t2
…
…
[0 1 0]
Già visitato
[n 1 0]
t1
t3
t1
p1
t2
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
DEFINIZIONE
Data una rete di Petri 𝑁 = 𝑃, 𝑇, 𝐴, 𝜔, x0 , date due marcatura x, y ϵ 𝑅 𝑁
marcatura 𝐱 copre 𝐲 se:
1. x 𝑝𝑖 ≥ 𝑦 𝑝𝑖 ∀ 𝑖 = 1,2, … , 𝑃 ;
2. ∃ 𝑖𝜖 1,2, … , 𝑃 | x 𝑝𝑖 > 𝑦 𝑝𝑖 ;
si dice che la
OSSERVAZIONE
Quando si genera l’albero di raggiungibilità, se troviamo che un nodo x ricopre un nodo
𝑦, allora sostituiamo tutti gli elementi di x 𝑝𝑖 per cui vale x 𝑝𝑖 > 𝑦 𝑝𝑖 con il simbolo w.
Tale simbolo indica un numero di gettoni teoricamente infinito.
DEFINIZIONE
Un albero in cui compare il simbolo w è detto albero di copertura.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Tracciamo l’albero di raggiungibilità dell’esempio precedente usando gli alberi di
copertura.
[0 1 0]
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Facciamo scattare t1. E notiamo che [1 1 0] ricopre [0 1 0].
t1
[0 1 0]
[1 1 0]
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Facciamo scattare t1. E notiamo che [1 1 0] ricopre [0 1 0]. Sostituiamo pertanto il primo
elemento con w. Due sono le transizioni che possono scattare: t1 e t2
t1
[0 1 0]
[w 1 0]
t1
t2
w
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Facciamo scattare t1. Giungiamo in un nodo già visitato, perciò questo ramo si chiude.
t1
[0 1 0]
[w 1 0]
t1
t2
w
[w 1 0]
Già visitato
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Facciamo scattare t2. Due sono le transizioni che possono scattare: t1 e t3
[0 1 0]
t1
[w 1 0]
t2
t1
[w 1 0]
Già visitato
[w 0 1]
t1
w
t3
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Facendo scattare t1 si va in uno stato già visitato.
[0 1 0]
t1
[w 1 0]
t2
t1
[w 0 1]
[w 1 0]
Già visitato
t1
[w 0 1]
w
t3
t1
p1
t2
Già visitato
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Facendo scattare t1 si va in uno stato già visitato.
[0 1 0]
t1
[w 1 0]
t2
t1
[w 0 1]
[w 1 0]
Già visitato
t1
w
t3
[w 0 1]
[w 1 0]
Già visitato
Già visitato
t1
p1
t2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
ALBERO DI RAGGIUNGIBILITÀ
Analizzando l’albero di copertura ottenuto si ha che:
• L’albero di raggiungibilità è illimitato;
• Il posto illimitato è p1;
• La rete è reversibile, in quanto il nodo [w 1 0]
contiene il nodo radice ed è sempre possibile
ricondurvisi attraverso una opportuna combinazione di
transizioni.
[0 1 0]
t1
[w 1 0]
t2
t1
[w 0 1]
[w 1 0]
t1
Già visitato
t3
[w 0 1]
[w 1 0]
Già visitato
Già visitato
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
IMPLEMENTAZIONE SOFTWARE
DELLE RETI DI PETRI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
PROBLEMA
Consideriamo la necessità di implementare in codice SFC un modello a rete di Petri.
Il principale problema consiste nel fatto che lo stato di una rete di Petri, definito dalla
sua marcatura, è un concetto distribuito tra i posti e può assumere un numero
potenzialmente infinito di configurazioni.
RETI BINARIE
Limitiamo l’analisi ad un caso particolare delle reti di Petri, ovvero le reti binarie, in cui il
numero di possibili stati è al massimo 2|P|.
Facciamo la seguente assunzione:
• Ad ogni posto corrisponde uno stato;
• Se un posto ha un gettone, il corrispondente stato è attivo.
• Se un posto non ha gettoni, il corrispondente stato è inattivo.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
ESEMPIO
Traduciamo la rete di PETRI in figura nel corrispettivo diagramma SFC.
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Abbiamo tanti stati quanti sono i posti. Numeriamoli da 1 a 4. Gli stati 2 e 4 sono stati
iniziali.
1
2
p4
3
t1
t2
p1
4
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Ad ogni transizione ti associamo una condizione ci.
1
2
p4
3
t1
t2
p1
4
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Notiamo che per attivare lo stato 1 è sufficiente che la condizione c1 sia verificata e che lo
stato 4 sia attivo.
1
2
p4
3
c1
t1
t2
p1
4
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Notiamo che per attivare lo stato 2 è sufficiente che la condizione c3 sia verificata e che lo
stato 3 sia attivo.
1
2
p4
c3
3
c1
t1
t2
p1
4
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Notiamo che per abilitare la condizione c2 è necessario che gli stati 1 e 2 siano attivi.
Pertanto è necessario aggiungere una sincronizzazione.
3
4
c3
c1
p4
2
1
t1
t2
p1
c2
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Quando la condizione c2 è attivata, si abilitano, in parallelo, gli stati 3 e 4.
È necessario introdurre uno stato dummy.
true
3
4
c3
c1
p4
2
1
t1
c2
d
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
RETI LIMITATE
Se la rete di Petri è limitata si possono identificare un numero di stati pari al numero di
marcature e tracciare il diagramma SFC a partire dall’albero di raggiungibilità.
ESEMPIO
Consideriamo la rete di Petri in figura:
p4
t1
t2
p1
p3
t3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità...
[0 2 0 1]
t1
p4
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità...
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
t1
[0 1 1 1]
t3
t1
t2
p1
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
t1
[0 1 1 1]
t3
[1 1 1 0]
t2
t1
t2
p1
t3
p2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
[0 1 1 1]
t1
t3
[1 1 1 0]
t2
t1
t1
t2
p1
t3
[0 0 2 1]
p2
t3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
[0 1 1 1]
t1
t3
[1 1 1 0]
t2
[1 0 2 0]
t1
t2
p1
t3
[0 0 2 1]
t3
t1
p2
t3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
[0 1 1 1]
t1
t3
[1 1 1 0]
t2
[1 0 2 0]
t1
t2
p1
t3
[0 0 2 1]
t3
t1
p2
t3
[1 1 1 0]
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
[0 1 1 1]
t1
t3
[1 1 1 0]
[1 0 2 0]
t3
[0 0 2 1]
t3
t2
p1
[0 2 0 1]
t2
t1
t1
p2
t3
[1 1 1 0]
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
[0 1 1 1]
t1
t3
[1 1 1 0]
[1 0 2 0]
t3
[0 0 2 1]
[1 2 0 0]
t3
t2
p1
[0 2 0 1]
t2
t1
t1
p2
t3
[1 1 1 0]
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
La rete è non binaria, infatti la marcatura iniziale presenta due token nel posto p2.
Tracciamo l’albero di raggiungibilità…
[0 2 0 1]
t1
[1 2 0 0]
p4
t2
[0 1 1 1]
t1
t3
[1 1 1 0]
[1 0 2 0]
[1 1 1 0]
t3
[0 0 2 1]
[1 2 0 0]
t3
t2
p1
[0 2 0 1]
t2
t1
t1
p2
t3
[0 1 1 1]
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
p3
t3
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Dall’albero di raggiungibilità tracciamo il digramma SFC, identificando i 6 stati…
[0 2 0 1] = 1
t1
[1 2 0 0] = 2
t2
[0 1 1 1] = 3
t1
6=
[1 0 2 0]
t3
4 = [1 1 1 0]
t2
5 = [0 0 2 1]
t1
t3
[1 1 1 0]
[0 2 0 1]
t3
[1 2 0 0]
t3
[0 1 1 1]
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Dall’albero di raggiungibilità tracciamo il digramma SFC, identificando le 3 condizioni…
[0 2 0 1]
t1
c1
[1 2 0 0]
c2 t
2
[0 1 1 1]
t1
t3
[1 1 1 0]
[0 2 0 1]
t2
[1 0 2 0]
t1
t3
[0 0 2 1]
[1 2 0 0]
t3
[1 1 1 0]
c3
t3
[0 1 1 1]
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DALLE RETI DI PETRI AI DIAGRAMMI SFC
Dall’albero di raggiungibilità tracciamo il digramma SFC.
[0 2 0 1] = 1
t1
c1
t3
4 = [1 1 1 0]
t2
5 = [0 0 2 1]
t1
t3
[1 1 1 0]
c1
[0 2 0 1]
c2
t3
t3
[0 1 1 1]
c3*not(c1)
4
c3
[1 2 0 0]
2
3
[0 1 1 1] = 3
t1
[1 0 2 0]
c2
[1 2 0 0] = 2
c2 t
2
6=
c1
1
5
c3*not(c2)
c1
6
c3*not(c1)
c3
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea: INGEGNERIA
Insegnamento:
AUTOMAZIONE II
Docente:
PROF: ALESSANDRO DE CARLI
DR. VINCENZO SURACI
Facoltà di Ingegneria
BIBLIOGRAFIA
Sezione 8.3.4, 8.5.1, 8.5.2, 8.7
TITOLO
Sistemi di automazione industriale
Architetture e controllo
AUTORI
Claudio Bonivento
Luca Gentili
Andrea Paoli
EDITORE
McGraw-Hill
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it