Re¸tele Petri s¸i Aplica¸tii - profs.info.uaic.rootto/Referate/intro_PN.pdf · TS1, TS2 - teste...

Retele Petri si AplicatiiAsist. Dr. Oana Captarencu

http://www.infoiasi.ro/˜otto/pn.html

[email protected]

Retele Petri si Aplicatii – p. 1/45

Evaluare

Nota finala: 40% TS1 + 20% TS2 + 40%LSATS1, TS2 - teste scrise

Activitate laborator/seminar (LSA):lucrare (30%)proiect (50%)activitatea în timpul seminarului (20%)

Referat (optional): 2 puncte (se adauga la nota finala)

Conditii minimale: LSA ≥ 5, TS1 + TS2 ≥ 7

Nota finala: minim 5.


Retele Petri

Retele Petri: o metoda formala (matematica) folosita pentrumodelarea si verificarea sistemelor (concurente/distribuite)


Retele Petri

Retele Petri: o metoda formala (matematica) folosita pentrumodelarea si verificarea sistemelor (concurente/distribuite)Notiunea de sistem:

A regularly interacting or interdependent group of items forming a unified whole(Webster Dictionary)

A combination of components that act together to perform a function not possible

with any of the individual parts (IEEE Standard Dictionary of Electrical and

Electronic Terms)


Retele Petri

Retele Petri: o metoda formala (matematica) folosita pentrumodelarea si verificarea sistemelor (concurente/distribuite)Notiunea de sistem:

A regularly interacting or interdependent group of items forming a unified whole(Webster Dictionary)

A combination of components that act together to perform a function not possible

with any of the individual parts (IEEE Standard Dictionary of Electrical and

Electronic Terms)

Sistemele:

alcatuite din componente care interactioneaza

îndeplinesc o anumita functionalitate

evenimente si stari

concurenta, comunicare, sincronizare


Retele Petri

Exemple de sisteme:

sisteme automatizate de productie

sisteme de control al traficului aerian

sisteme de monitorizare si control în industrie

retele de comunicare

sisteme software distribuite

etc...


Modelarea si verificarea sistemelor

Verificarea sistemelor reale: are drept scop verificarea unorproprietati dezirabile, înca din stadiul de proiectare

Un model surprinde caracteristici esentiale ale sistemului

Modele (formale) pentru verificarea sistemelor:automate/sisteme tranzitionalealgebre de proceselogici temporaleretele Petrietc...


Retele Petri pentru modelarea sistemelor

Retele Petri:

Carl Adam Petri, 1962



Retele Petri:


grafuri bipartite



Retele Petri:


grafuri bipartite

reprezentare explicita starilor si evenimentelor dintr-unsistem



Retele Petri:


grafuri bipartite


reprezentare grafica intuitiva



Retele Petri:


grafuri bipartite



semantica formala



Retele Petri:


grafuri bipartite



semantica formala

expresivitate (concurenta, nedeterminism,comunicare,sincronizare)



Retele Petri:


grafuri bipartite



semantica formala


existenta metodelor de analiza a proprietatilor



Retele Petri:


grafuri bipartite



semantica formala


existenta metodelor de analiza a proprietatilor

numeroase unelte software pentru editarea/verificareaproprietatilor retelelor Petri


Retele Petri

Domenii de aplicabilitate:

Protocoale de comunicare, retele

Sisteme software si hardware

Algoritmi distribuiti

Protocoale de securitate

Biologie, Chimie, Medicina

Economie (fluxuri de lucru)

etc..


Retele de tip P/T

Definitie

Regula de producere a tranzitiilor (comportament)

Proprietati


Retele de tip P/T - Definitie

Definitie 1 O retea Petri este un 4-uplu N = (P, T, F,W ) astfelîncât :

1. P multime de locatii, T multime de tranzitii, P ∩ T = ∅;

2. F ⊆ (P × T ) ∪ (T × P ) relatia de flux;

3. W : (P × T ) ∪ (T × P ) → N ponderea arcelor(W (x, y) = 0 ddaca (x, y) 6∈ F ).

P = {p1, p2, p3}

T = {t1, t2, t3}

F = {(p1, t1), (t1, p2), (t1, p3),

(p3, t3), (t3, p1), (p2, t2)}

W (p1, t1) = 1, W (t1, p2) = 1,W (t1, p3) = 1, W (p3, t3) = 1,

W (t3, p1) = 1,W (p2, t2) = 2

p1 t1 p2

t2

2

p3t3


Retele de tip P/T

Daca x ∈ P ∪ T , atunci:

- Premultimea lui x: •x = {y|(y, x) ∈ F};

- Postmultimea lui x: x• = {y|(x, y) ∈ F} .

p1 t1 p2

t2

2

p3t3

- •t1 = {p1}, •t2 = {p2}, •t3 = {p3}

- t1• = {p2, p3}, t2• = ∅, t3• = {p1}

- •p1 = {t3}, •p2 = {t1}, •p3 = {t1}

- p1• = {t1}, p2• = {t2}, p3• = {t3}


Retele de tip P/T

Definitie 2 O retea este pura daca, pentru orice x ∈ P ∪ T ,•x ∩ x• = ∅.

2

p1

t2

p2t1

Definitie 3 O retea este fara elemente izolate, daca, pentruorice x ∈ P ∪ T , •x ∪ x• 6= ∅


Marcare a unei retele de tip P/T

Definitie 4 (Marcare, retele marcate)

Fie N = (P, T, F,W ) o retea P/T. O marcare a lui N este ofunctie M : P → N.

Fie N = (P, T, F,W ) o retea P/T si M0 : P → N. Atunci(N,M0) se numeste retea Petri marcata.

p1 t1 p2

t2

2

p3t3M = (1, 0, 0)

Distributia punctelor în locatiile unei retele = marcarearetelei (starea sistemului modelat)


Retele Petri

Tranzitii: reprezinta actiuni sau evenimente din sistemulmodelat

Punctele din locatii: pot modela resurse/valori booleene

Locatiile input: contin resurse (reprezentate de punctele dinlocatie) care vor fi folosite de catre actiune, preconditiipentru producerea unui eveniment

Ponderea unui arc input: câte resurse de un anumit tip suntnecesare producerii actiunii

Ponderea unui arc output: numarul de resurse de un anumittip rezultate prin producerea actiunii


Exemplu

Model producator consumator:

Producatorul (P) poate produce câte un produs (într-unbuffer)

Un consumator (C) preia câte doua produse din buffer

Stari producator: producator activ (pregatit sa produca),producator în repaus.

Evenimente: P produce un produs, C consuma produse, Predevine activ


Exemplu


Producatorul (P) poate produce câte un produs (într-unbuffer)

Un consumator (C) preia câte doua produse din buffer

Stari producator: producator activ (pregatit sa produca),producator în repaus.

Evenimente: P produce un produs, C consuma produse, Predevine activ

p1 t1 p2

t2

2

p3t3

buffer

consuma

producatorin repaus

revine

producator activ produce


Regula de producere a tranzitiilor

Fie N = (P, T, F,W ) o retea Petri, M o marcare a lui N si t ∈ T

o tranzitie a lui N .





Tranzitia t este posibila la marcarea M (M [t〉N ) dacaW (p, t) ≤ M(p), pentru orice p ∈ •t.





Tranzitia t este posibila la marcarea M (M [t〉N ) dacaW (p, t) ≤ M(p), pentru orice p ∈ •t.

Daca t este posibila la marcarea M , atunci t se poateproduce, rezultând o noua marcare M ′ (M [t〉NM ′), undeM ′(p) = M(p)−W (p, t) +W (t, p), pentru toti p ∈ P .


Exemplu

o tanzitie este posibila daca locatiile input contin suficientepuncte:

p1

p2

t1

t2

p3

p4

t3 p52

3

2

2


Exemplu

o tanzitie este posibila daca locatiile input contin suficientepuncte:

p1

p2

t1

t2

p3

p4

t3 p52

3

2

2

Producerea unei tranzitii modifica marcarea retelei


Exemplu I



Exemplu I


p1 t1 p2

t2

2

p3t3

buffer

consuma

producatorin repaus

revine

producator activ produce


Exemplu II

Automat care furnizeaza produse


Exemplu II

Automat care furnizeaza produse

produse

produse consumate

C introduce moneda

monezi acceptate

ofera produs

reincarca monezi introduse

A accepta moneda

A respinge moneda

A repaus


Secvente de aparitie a tranzitiilor

Regula de producere a tranzitiilor se poate extinde la secventede tranzitii:

Definitie 5 (secvente de aparitie)

Fie σ = t1t2 . . . tk ∈ T ∗ si M o marcare. σ se numeste secventafinita de aparitie, posibila la M, daca exista marcarileM1,M2, . . . ,Mk astfel încât:

M [t1〉M1[t2〉M2 . . .Mk−1[tk〉Mk

Se mai noteaza: M [σ〉Mk.

Secventa vida de tranzitii, notata cu ǫ, este secventa de aparitieposibila la orice marcare M a retelei, si are loc: M [ǫ〉M .

O secventa infinita de tranzitii σ = t1, t2, . . . este secventa infinitade aparitie, posibila la marcarea M , daca: M [t1〉M2[t2〉M3 . . ..


Notatii

Fie γ = (N,M0) o retea P/T marcata . Se definesc urmatoarelefunctii:

t− : P → N, t−(p) = W (p, t),∀p ∈ P

t+ : P → N, t+(p) = W (t, p),∀p ∈ P

∆t : P → Z, ∆t(p) = W (t, p)−W (p, t)

Daca σ ∈ T ∗ este o secventa de tranzitii, se defineste∆σ : P → Z:

Daca σ = ǫ, atunci ∆σ este functia identic 0.

Daca σ = t1, . . . , tn, atunci ∆σ =∑n

i=1∆ti.


Secvente de aparitie

p1

p2

p3

t1

3

2

t−1(p1) = 2, t−

1(p2) = 1, t−

1(p3) = 0

t+

1(p1) = 1, t+

1(p2) = 3, t+

1(p3) = 1

∆t1(p1) = −1,∆t1(p2) = 2,∆t1(p3) = 1


Secvente de aparitie

p1

p2

p3

t1

3

2

t−1(p1) = 2, t−

1(p2) = 1, t−

1(p3) = 0

t+

1(p1) = 1, t+

1(p2) = 3, t+

1(p3) = 1

∆t1(p1) = −1,∆t1(p2) = 2,∆t1(p3) = 1

Propozitie 1 Fie t o tranzitie, σ ∈ T ∗ si M,M ′ marcari.

Daca M [t〉M ′, atunci M ′ = M +∆t.

Daca M [σ〉M ′, atunci M ′ = M +∆σ


Marcari accesibile

Definitie 6 Fie γ = (N,M0) o retea P/T marcata.

O marcare M ′ este accesibila din marcarea M , daca existao secventa finita de aparitie σ astfel încât: M [σ〉M ′.


Marcari accesibile



Marcarea M este accesibila în γ, daca M este accesibiladin marcarea initiala M0.


Marcari accesibile




Multimea marcarilor accesibile dintr-o marcare M , în γ, senoteaza [M〉γ ([M〉 când este clar despre ce retea estevorba).


Marcari accesibile




Multimea marcarilor accesibile dintr-o marcare M , în γ, senoteaza [M〉γ ([M〉 când este clar despre ce retea estevorba).

[M0〉γ se numeste multimea marcarilor accesibile în reteauaγ.


Proprietati pentru secvente de aparitie

Propozitie 2 Fie M o marcare si σ o secventa finita deaparitie, astfel încât M [σ〉M ′. Daca σ′ este o secventa deaparitie (finita sau infinita) posibila la marcarea M ′, atunciσσ′ este secventa de aparitie posibila la M .




Propozitie 3 O secventa infinita de aparitie σ este posibilala o marcare M ddaca orice prefix finit al lui σ este posibil laM .




Propozitie 3 O secventa infinita de aparitie σ este posibilala o marcare M ddaca orice prefix finit al lui σ este posibil laM .

Propozitie 4 Fie M si M marcari, σ o secventa de aparitieposibila atât la M cât si la M , astfel încât: M [σ〉M ′ si

M [σ〉M′. Atunci M ′(p)−M(p) = M

′(p)−M(p), pentru

orice locatie p ∈ P .



Propozitie 5 Fie M , M ′ si L marcari, σ ∈ T ∗ o secventa detranzitii, posibila la M .

Daca σ finita si M [σ〉M ′, atunci (M + L)[σ〉(M ′ + L).

Daca σ infinita si M [σ〉, atunci (M + L)[σ〉

Demonstratie:

σ finita: inductie dupa |σ| = n.

σ infinita: se arata ca orice prefix finit al lui σ este posibil la M + L.

M = (2, 1, 1, 0)[t1t2〉(1, 0, 1, 2) = M ′

(3, 2, 2, 0)[t1t2〉?



Definitie 7 Fie M si M ′ doua marcari.

M ≥ M ′ ddaca M ′(p) ≥ M(p), ∀p ∈ P .

M > M ′ ddaca M ≥ M ′ si ∃p ∈ P : M(p) > M ′(p).

Propozitie 6 Fie M si M ′ doua marcari astfel încât M ≥ M ′.Atunci orice secventa de aparitie posibila la marcarea M esteposibila si la marcarea M ′.

M ′ ≥ M =⇒ ∃L marcare astfel încât M ′ = M + L

σ infinita: M [σ〉 =⇒ M ′ = (M + L)[σ〉

σ finita: M [σ〉M si M ′ = (M + L)[σ〉(M + L)



Lema 1 Fie N o retea oarecare, U, V ⊆ T astfel încâtV • ∩ • U = ∅. Daca σ ∈ (U ∪ V )∗ astfel încât M [σ〉M ′, atunciM [σ|Uσ|V 〉M

′.

t1 p t2

UV

t1 ∈ V si t2 ∈ U .t1 • ∩ • t2 = ∅M [t1t2〉M

′, atunci:M [t2t1〉M

′



Lema 1 Fie N o retea oarecare, U, V ⊆ T astfel încâtV • ∩ • U = ∅. Daca σ ∈ (U ∪ V )∗ astfel încât M [σ〉M ′, atunciM [σ|Uσ|V 〉M

′.

Demonstratie:Fie N o retea oarecare, t1, t2 ∈ T astfel încât t1 ∈ V si t2 ∈ U . Deci t1 • ∩ • t2 = ∅.Se arata ca:

M [t1〉M2[t2〉M ′ =⇒ M [t2〉M ′2[t1〉M ′

M [t2〉 (adica ∀p ∈ •t2 : W (p, t2) ≤ M(p)).

Fie M [t2〉M ′2. Se arata ca M ′

2[t1〉.

Se arata ca M [t2〉M ′2[t1〉M ′.


Exemplu

U = {t1, t2}, V = {t3, t4} M = (0, 1, 0, 1, 0)


Exemplu

U = {t1, t2}, V = {t3, t4} M = (0, 1, 0, 1, 0)

p1

p2 p3 p4 p5

t1

t2 t3 t4

2


Exemplu

U = {t1, t2}, V = {t3, t4} M = (0, 1, 0, 1, 0)

σ = t2t4t3t1t4M = (1, 0, 1, 0)[t2t4t3t1t4〉(0, 0, 2, 0, 2) = M ′

M [t2t1t4t3t4〉M′

p1

p2 p3 p4 p5

t1

t2 t3 t4

2


Proprietatea de marginire

Fie γ = (M,M0) o retea Petri marcata.

Definitie 8 (marginire)





O locatie p este marginita daca:

(∃ n ∈ N)(∀M ∈ [M0〉)( M(p) ≤ n)






(∃ n ∈ N)(∀M ∈ [M0〉)( M(p) ≤ n)

Reteaua marcata γ este marginita daca orice locatie p ∈ P

este marginita.






(∃ n ∈ N)(∀M ∈ [M0〉)( M(p) ≤ n)

Reteaua marcata γ este marginita daca orice locatie p ∈ P

este marginita.

Reteaua N este structural marginita, daca exista o marcareM astfel încât (N,M) este marginita.


Marginire-exemple

p1 t1

p2t2


Marginire-exemple

p1 t1

p2t2

reteaua este marginita: M(p) ≤ 1, ∀p ∈ P


Marginire-exemple

p1 t1

p2t2


p1

p2t1

p3

t2


Marginire-exemple

p1 t1

p2t2


p1

p2t1

p3

t2

reteaua este nemarginita:

p2 poate contine o infinitate de puncte!



Propozitie 7 O retea P/T marcata γ = (N,M0) estemarginita ddaca multimea [M0〉 este finita.




(=⇒) Fie n astfel încât (∀M ∈ [M0〉)(∀p ∈ P )(M(p) ≤ n). Numarul maxim demarcari este (n+ 1)|P |.

(⇐=) Se considera n = max{M(p)|M ∈ [M0〉, p ∈ P}.






Propozitie 8 Daca γ = (N,M0) este marginita, nu existadoua marcari M1,M2 ∈ [M0〉 astfel încât M1[∗〉M2 siM2 > M1.






Propozitie 8 Daca γ = (N,M0) este marginita, nu existadoua marcari M1,M2 ∈ [M0〉 astfel încât M1[∗〉M2 siM2 > M1.

Daca M1[σ〉M2 si M2 > M1 =⇒ M2[σ〉M3 (prop. 6) si M3 > M2 (prop. 4). Deci

M3[σ〉M4, M4 > M3, etc.


Proprietati: pseudo-viabilitate

Fie γ = (N,M0) o retea Petri marcata.

Definitie 9 (pseudo-viabilitate)

O tranzitie t ∈ T este pseudo-viabila din marcarea M ,daca exista o marcare M ′ ∈ [M〉 astfel încât M ′[t〉.

O tranzitie t ∈ T este pseudo-viabila daca estepseudo-vaibila din M0 (exista o marcare accesibilaM ∈ [M0〉 astfel încât M [t〉). O tranzitie care nu estepseudo-viabila se numeste moarta.

Reteaua marcata γ este pseudo-viabila daca toatetranzitiile sale sunt pseudo-viabile.


Exemple

p1

p2

p3

p4

p5t1

t2

t3


Exemple

p1

p2

p3

p4

p5t1

t2

t3

t1 este tranzitie moarta

t2 pseudo-viabila

t3 este tranzitie moarta


Proprietati: blocaje


Definitie 10 (blocaje)

O marcare M a retelei marcate γ este moarta daca nuexista o tranzitie t ∈ T astfel încât M [t〉.

Reteaua γ este fara blocaje, daca nu exista marcariaccesibile moarte.


Exemple

p1

p2

p3

p4

p5t1

t2

t3


Exemple

p1

p2

p3

p4

p5t1

t2

t3

Marcarea (0,0,0,1,0) este moarta, deci reteaua are blocaje.


Proprietati: viabilitate

Definitie 11 (viabilitate)Fie N = (P, T, F,W ) o retea de tip P/T si γ = (N,M0) o reteaPetri marcata.

O tranzitie t ∈ T este viabila daca ∀M ∈ [M0〉, t estepseudo-viabila din M (∃M ′ ∈ [M〉 astfel încât M ′[t〉).

Reteaua marcata γ este viabila daca orice tranzitie t ∈ T

este viabila.

reteaua N este structural viabila daca exista o marcare M

astfel încât (N,M) este viabila.


Exemple

2

2

p1 t1 p2

t2p3t3

Retea pseudo-viabila, viabila si fara blocaje.


Exemple


Exemple

t1,t2,t3: nu sunt viabile

t4,t5: viabile

reteaua este pseudo-viabila


Reversibilitate

Definitie 12 Reteaua marcata γ este reversibila daca marcareasa initiala este accesibila din orice marcare M ∈ [M0〉.


Reversibilitate

Definitie 12 Reteaua marcata γ este reversibila daca marcareasa initiala este accesibila din orice marcare M ∈ [M0〉.

2

2

p1 t1 p2

t2p3t3


Proprietati ale retelelor Petri


Propozitie 9 Orice retea marcata viabila este sipseudo-viabila.





Propozitie 10 Orice retea marcata viabila, având cel putino tranzitie, este fara blocaje.






Propozitie 11 Daca o retea fara locatii izolate este viabila,atunci orice locatie poate fi marcata, din orice marcareaccesibila.







Propozitie 12 O retea marcata reversibila este viabiladdaca este pseudo-viabila.







Propozitie 12 O retea marcata reversibila este viabiladdaca este pseudo-viabila.

Propozitie 13 O retea marcata reversibila este fara blocaje.


Exemple

Q: orice retea pseudo-viabila este si viabila?

Q: orice retea pseudo-viabila este si fara blocaje?

Q: orice retea viabila este si reversibila ?


Exemple




p1 p2

p3

p4

t1 t2


Exemple




p1 p2

p3

p4

t1 t2

Retea pesudo-viabila (toate tranzitiile pseudo-viabile).Reteaua are blocaje (marcarea (0, 0, 1, 1) este moarta).Reteaua nu este viabila!


Exemple

Retea viabila, care nu este reversibila:

p1

t1

p2

t2 p3 t3 p4

(1, 0, 0, 0)[t2〉(0, 1, 1, 0)[t1〉(1, 0, 1, 0)[t3〉(1, 0, 0, 1).Marcarea initiala (1, 0, 0, 0) nu este accesibila din (1, 0, 0, 1).


Exemple

Q: Exista o relatie între proprietatea de marginire si cea deviabilitate?


Exemple


p1 t1

p2t2


Exemple


p1 t1

p2t2

(1, 0)[t1〉[t2〉(0, 1)[t1〉[t2〉(0, 1)...

Retea marginita si este viabila


Exemple


p1 t1

p2t2

(1, 0)[t1〉[t2〉(0, 1)[t1〉[t2〉(0, 1)...


p1

p2t1

p3

t2


Exemple


p1 t1

p2t2

(1, 0)[t1〉[t2〉(0, 1)[t1〉[t2〉(0, 1)...


p1

p2t1

p3

t2Retea nemarginita, este viabila


Exemple

t1

t2

p2 t3 t4

p3

p5

t5 p4p1


Exemple

t1

t2

p2 t3 t4

p3

p5

t5 p4p1

Retea nemarginita (locatia p4), neviabila (M = (0, 0, 0, 2, 1) si t1)


Marginire si viabilitate

Teorema 1 Orice retea conexa (fara elemente izolate) marginitasi viabila este tare conexa.




Demonstratie: Se arata ca pentru orice (x, y) ∈ F , exista un drum de la y la x.

Caz 1: x ∈ P, y ∈ T .Fie V = {t ∈ T |exista drum de la y la t} (y ∈ V )U = {t ∈ T |nu exista drum de la y la t}

V • ∩ • U = ∅.

x y

VU




Demonstratie: Se arata ca pentru orice (x, y) ∈ F , exista un drum de la y la x.

Caz 1: x ∈ P, y ∈ T .Fie V = {t ∈ T |exista drum de la y la t} (y ∈ V )U = {t ∈ T |nu exista drum de la y la t}

V • ∩ • U = ∅.

x y

VU

t


ExempleReteaua nu este tare conexa ⇒ nu este viabila sau marginita:

p1

t1

t2

t3

p2

Reciproca teoremei nu este adevarata: reteaua este tare conexa, dar nu este viabila.

p1

t2

t3

p2

2


Re¸tele Petri s¸i Aplica¸tii - profs.info.uaic.rootto/Referate/intro_PN.pdf · TS1, TS2 - teste...

Documents

Transcript of Re¸tele Petri s¸i Aplica¸tii - profs.info.uaic.rootto/Referate/intro_PN.pdf · TS1, TS2 - teste...