Modelarea Modelarea ii evaluareaevaluarea performanperformanelorelorn n sistemelsistemelee de calculde calcul
Curs, anul I Master Calculatoare
Modelare dinamic cu reele Petri
Captura caracteristicilor dinamice ale sistemelor discrete prin modele cu RPn Elemente constitutive (structurale) ale RPn Dinamica sistemelor cu RPTipuri simple de RP. Exemple
RP ordinare
Sumar
n RP ordinare n RP generalizateAlte proprieti i clasificri derivateMetode de analiz si sinteza (modelare) folosind RPordinare si generalizateExtensii ale modelelor de baza cu RP: n RP temporizaten RP stochasticen RP de nivel inalt
Caracteristici dinamice in sistemele cu evenimente discrete
SED sunt inerent dinamice si paralele, pot fi caracterizate prin 3 trsturi eseniale de comportament,superpozabile:
n Concurena: posibilitatea ca mai multe evenimente s aib loc de o manier independent unul fa de altul
Sincronizarea: se refer la necesitatea ca execuia n Sincronizarea: se refer la necesitatea ca execuia anumitor evenimente s atepte producerea altor evenimente
n Conflictele (interblocajele): o manier de a ine cont de competiia ntre aciuni multiple simultane sau de anumite fenomene, precum excluderea mutual
ReeleReelelele PetriPetri
Utilizeaz stri distribuite i tranziii localeAu permis iniial modelarea unor sisteme cu componente concurente n interaciune, fiind extinse ca instrumente matematice generale ulteriorModelarea dinamic necesita astfel de descrieri de tip Modelarea dinamic necesita astfel de descrieri de tip calitativ (logic) care s poat servi ca baz pentru analiza i sinteza SDED Accentul este pus pe modelarea dependenelor cauzale, fr sincronizare global (doar transmitere de mesaje)Pe lng anumite proprieti analitice, caracterul vizual al RP poate fi un element important n modelare
Elemente constitutive structurale(Logic)n Condiii
Pot fi ndeplinite sau nu.n Evenimente
Pot avea loc daca anumite condiii sunt ndeplinite.Relaii (flux de control) n Relaii (flux de control) Arata relaiile intre condiii si evenimente.
Condiiile, evenimentele si relaiile formeaz un graf bipartit (graf cu doua tipuri de noduri)
(Grafic)n Locaii (cercuri)n Tranziii (dreptunghiuri)n Arce, ce conecteaz locaiile cu tranziii sau tranziiile
cu locaii
Concept dinamic cheie: Tranziia strilor
Logic, reprezint apariia unui eveniment/ o aciuneGrafic, este micarea unor jetoane (token-uri), notate ca puncte negre, din locaie n locaie, prin aprinderea tranziiilor Aceasta din urma depinde de condiiile de intrare simbolizate de disponibilitatea jetoanelorsimbolizate de disponibilitatea jetoanelorSpunem ca o tranziie este validata daca exista un numr suficient de jetoane in locaiile sale de intrareO tranziie validata se poate aprinde oricndDup aprindere, token-urile vor fi transferate de la locaiile de intrare (stare veche) ctre cele de ieire, fiind astfel un element de identificare si in acelai timp o notaie pentru noua stare
Arce si capacitiArcele au implicit capacitatea 1; daca este diferita de 1, capacitatea este marcata pe arc Locaiile au implicit capacitate infinitaO tranziie este validata daca numrul de jetoane in fiecare din
Locaie cu token
numrul de jetoane in fiecare din locaiile sale de intrare este cel puin egal cu capacitatea arcului ce o unete cu o locaie de intrare
P1
P2
T1
Arc de capacitate 1
TranziieLocaie
Exemplul 1Automat de distribuie (vnzare): n Distribuie dou tipuri de batoane, de 20 de
bani si de 15 banin Doar dou tipuri de monede pot fi folosite, de n Doar dou tipuri de monede pot fi folosite, de
10 bani si de 5bn Nu returneaz rest
Reprezentare prin DTS, ca automat cu stri finite (FSM)
5 bani 15 baniDepunere 10b
Ia baton de 15b
0 bani
10 bani 20 baniDepunere 10b
Ia baton de 20b
Reprezentare prin RP
5b
Ia baton de 15b
Depunere 5b
Depunere 10b15b
0b
Depunere 10b
Depunere5b
10b
Depunere5b
Depunere 10b20b
Depunere5b
Ia baton de 20b
Scenarii de evolutie
Scenariul 1: n Depunere 5b, depunere 5b, depunere 5b, depunere
5b, ia baton de 20b.Scenariul 2:n Depunere 10b, depunere 5b, ia baton de 15b.n Depunere 10b, depunere 5b, ia baton de 15b.
Scenariul 3:n Depunere 5b, depunere 10b, depunere 5b, ia baton
de 20b.
Dinamica sistemului
5b
Ia baton de 15b
Depunere 5b
Depunere 10b15b
0b
Depunere 10b
Depunere5b
10b
Depunere5b
Depunere 10b20b
Depunere5b
Ia baton de 20b
Tipuri de reele PetriTipuri de reele Petri (crit. structural)RP ordinare, n care fiecare arc nu poate avea dect capacitatea (funcia de ponderare) egala cu 1n Mainile de stare (MS) RP unde orice tranziie are exact
o locaie de intrare i o locaie de ieire:n Grafurile de evenimente (grafurile marcate, GM) - RP n
Tttt "== ,1||||n Grafurile de evenimente (grafurile marcate, GM) - RP n
care orice locaie are exact o tranziie de intrare i o tranziie de ieire:
n Reelele cu alegere liber (AL) RP n care, dac o locaie are mai multe tranziii de ieire, ea constituie singura lor locaie de intrare:
n Reelele cu alegere liber extinse (ALE) RP n care, dac doua locaii au o tranziie comuna de ieire, vor avea toate tranziiile de ieire comune
Pppp "== ,1||||
1|)(|1||, =>" ppPp
Tipuri Tipuri simple simple de reele Petride reele Petri (cont.)n Reelele cu alegere asimetric (AA) RP n care, dac dou
locaii au o tranziie comuna de ieire, atunci una din ele are toate tranziiile de ieire ale celeilalte (posibil altele in plus)
RP
PN
RP
AA ALE AL MS GM
RP generalizate, unde pot fi aplicate ponderi generale arcelor
Reele Petri clasice (C/E)Sunt cele folosite n introducerea RP: o subclas de reele Petri in care locaiile pot avea 1/0 simboluri, ce pot modela attcondiii ct i evenimente:
locaiile reprezint condiii, ce pot avea inscrise valori true/ falsen locaiile reprezint condiii, ce pot avea inscrise valori true/ falsen tranziiile reprezint evenimente locale
Un eveniment este validat d.d. n toate pre-condiiile sale (conectate prin arce incidente) sunt true n toate post-condiiile sale sunt false
Apariia unui eveniment neag pre- i post-condiiile sale
Reele C/E (cont.)Evenimentele cu aceleai pre- sau post-condiii sunt in conflict Doar evenimentele non-conflictuale validate pot aprea concurentTerminologie:
Marcajul reelei = distribuia token-urilorn Marcajul reelei = distribuia token-urilorn Sistem C/E= reea C/E + marcajn Configuraii: marcaje posibile ale unei reele C/En Cazuri ale unui sistem C/E: configuraii accesibile din
marcajul iniial ( case graph)
Automatele sunt o subclas secveniala a sistemelor C/Eexact o condiie este adevrata,
fiecare eveniment are o singura pre- si post-condiie
Descrieri formaleGrafice (grafuri bipartite)/ matematice: au semanticformal i posibiliti de analizn Caracteristici importante: stri distribuite i tranziii locale
Sistemice: RP = P = {l0, l1, , lm} setul poziiilor (locaiilor)P = {l0, l1, , lm} setul poziiilor (locaiilor)T = {t0, t1, , tn} setul tranziiilorPre : T L+, funcia de intrare, ce definete locaiile care
furnizeaz intrri unei tranziiiPost : T L+, funcia de ieire, definete locaiile de ieire
pentru fiecare tranziieM : L {0,1}, funcia de marcaj, definete numrul de
simboluri din fiecare locaie
Condiii i resurseReelele de tip C/E modeleaz fluxurile de informaii, la nivel fundamental (true/false)
Aplicaii: cele in care fluxul de resurse si/sau numarul de resurse disponibile este important (document workflow, data flow, linii de fabricaie, reele de comunicaie, www)data flow, linii de fabricaie, reele de comunicaie, www)
2
3
Reelele de tip P/T reprezint o generalizare (extensie) imediata:n Elementele de stare sunt echivalente locaiilor
unde sunt stocate resurse (jetoanele)n Elementele de aciune sunt reprezentate de
tranziiile locale sau transportul resurselorn Poate fi aplicata o descriere matematic
similar cu cea a RP C/E
Sunt reprezentri de forma (P, T, A, C, w, M0), formate dintr-o parte structural i o parte dinamicPartea structural este un graf orientat bipartit unde:n P este o mulime finit de poziii (locaii)n T este un set finit de tranziii
Reele P/TReele P/T marcatemarcate
n T este un set finit de tranziiin A este o mulime de arce, o submulime a mulimii (PT)(TP) n C: P (N {}) \{0} este o funcie de capacitate a poziiilor
(capacitatea unei poziii se consider implicit nelimitat)n w este o funcie de ponderare aplicat arcelor, w:A{1,2,3 ...}
(ponderea unui arc se consider implicit unitar)
Prin M0: P N notm funcia numit marcaj iniialPartea dinamic a reelei PT const n evidenierea modalitilor (legilor) de evoluie a marcajului iniial
Starea Starea i evoluia reelelor PTi evoluia reelelor PTStarea unei reele PT date (definit structural) e complet descris de marcajul su M=[M(p1), M(p2),,M(pn)]Spaiul strilor unei RPT marcate este complet definit de marcaje, adic de toi vectorii n-dimensionali ale cror elemente sunt pozitive, M={0, 1, 2, }nO tranziie tjT ntr-o RPT marcat este validat dac:O tranziie tjT ntr-o RPT marcat este validat dac:n M(pi) w(pi, tj), pentru orice piI(tj);n M(pk) C(pi)-w(tj, pk), pentru orice pkO(tj)- I(tj);n M(p) C(p)-w(tj, p) + w(p, tj), pentru orice pO(tj) I(tj),
unde I(ti) este mulimea locaiilor de intrare n tranziia tiiar O(ti) mulimea locaiilor de ieire din tranziia ti
Aprinderea unei tranziii este echivalent cu:n M(pi) = M(pi) - w(pi, tj), pentru orice piI(tj) - O(tj)n M(pk) = M(pk) + w(tj, pk), pentru orice pkO(tj) - I(tj)n M(p) = M(p) - w(p, tj) + w(tj, p), pentru orice pO(tj)I(tj)
Exemplul 2: Evoluia reelelor P/T
p1 t1 p2
2
2 2
n figura din stnga-sus, tranziia nu este validat i deci nu se poate produce n a doua variant de marcaj tranziia este validat n dreapta apare noul marcaj dup producerea tranziiei
p1 t1 p2
2
p1 t1 p2
2
Exemplul 3: Cazuri, configuraia iniial
p1
p2
p
p4 t2
M0 = [2, 0, 0, 1]
n configuraia iniial singura tranziie valid este t1. Cnd tranziia t1 se aprinde este eliminat un jeton din locaia p1 i se plaseaz cte un jeton n locaiile p2 i p3 (se poate aplica de asemenea formula pentru a se obine noua stare)
p3 t1
t3
Exemplul 3: Cazuri, pasul 1
p1
p2
p4t2
M1 = [1, 1, 1, 1]
n aceast stare toate cele trei tranziii sunt valideDac se aprinde tranziia t2, e eliminat un jeton din locaiile de intrare p2 i p3 i plasat n locaiile de ieire p2 i p4
p3t1
t3
Exemplul 3: pasul 2
p1
p2
p4 t2
M2= [1, 1, 0, 2]
S-a eliminat un jeton din locaiile de intrare p2 i p3 i s-a plasat un jeton n locaiile de ieire p2 i p4Dac ns n starea precedent s-ar aprinde tranziia t3, atunci s-ar obine starea descrisa pe urmtorul slide
p3 t1
t3
Exemplul 3: pasul 3
p1
p2
p4 t2
M2 = [0, 1, 0, 0]
n aceast stare nu mai este activat nici o tranziie i nu sunt posibile schimbri de stare
p3 t1
t3
Metode de analiz a RP ordinareAnaliza dinamic (analiza accesibilitii) are ca scop determinarea mulimii strilor (accesibile)n Utilizeaz reguli algebrice ce descriu validarea i aprinderea
tranziiilor n Acestea conduc la reprezentarea evoluiei dinamice a RP
prin formarea unor ecuaii prin formarea unor ecuaii Analiza structural are ca idee de baz eliminarea derivrii spaiului strilor i prin aceasta evitarea problemei exploziei strilor. n Aceast abordare nu poate furniza o informaie la fel de
bogat ca priman De multe ori o asemenea detaliere nici nu este necesar, ci
sunt dorite doar anumite caracteristici calitative ale RP i sistemului modelat (de ex. determinarea invarianilor)
Ecuaiile de accesibilitateDefinim al k-lea vector de evoluie uk, un vector m-dim.de forma: uk = [0, 0, .., 0, 1, 0, , 0], unde 1 apare n poziia j si arata c tranziia j este a k-a tranziie aprinsTrebuie definit i matricea de inciden I, matrice mxn, unde m este numrul de tranziii, n numrul de locaii, iar intrarea (i, j) este de forma: iar intrarea (i, j) este de forma: n Iij = w(pi, tj) - w(tj, pi)
Folosind matricea de inciden putem scrie o ecuaie de stare vectorial Mk = Mk-1+ukI, valabil pentru orice kN, si deduce o condiie necesar de accesibilitate a unui marcaj:
, ce se poate scrie si ca:
unde:
IuMMd
k
kd )(
10
=
+= MxI D=
=
=d
k
kux1
Exemplul 3 (cont.)Se vor folosi ecuaiile anterioare pentru exemplul 3Marcajul iniial este M = [2, 0, 0, 1]. Matricea de inciden pentru aceast reea Petri este:
- 0111
Dac se aprinde tranziia t1 dup marcajul iniial M0:
M1 = [2 0 0 1] + [1 0 0] = [2 0 0 1]+[-1 1 1 0]= [1 1 1 1]
----
-=
110111000111
I
----
-
110111000111
Exemplul 3 (cont.)n cazul n care n continuare se aprinde tranziia t2 vom obine:
M2 = [1 1 1 1] + [0 1 0] = [1 1 1 1] +
----
-
110111000111
+[0 0 -1 1] = [1 1 0 2]
Avnd marcajul iniial M0 se pot genera toate secvenele de marcaje Acordnd marcajelor semnificaia de stare, se observ similaritatea cu o ecuaie de stare din teoria sistemelor
--- 1101
Exemplul 4: Calculul algebric (1)p1
p2p3
t2p4t3
p5
t6t1
p8
p5 p6 p7t4 t5
Exemplul 4 (2)p1
p2 p3
t6t1
p8
t2 p4t3
7654321
001010100000010000001000100000000100000010000001
Pre
pppppppp
=
p5p5 p6 p7t4 t5
654321
87
001010tttttt
p
654321
87654321
010100010000001000000001000100000010000001100000
Post
tttttt
pppppppp
=Matricea de inciden
---
--
--
--
==
011110110000011000001001100100000110000011100001
Pre-PostI
Exemplul 4 (3)p1p2 p3
p5
t6t1 p8
t2 p4
p5
p
p7
t3
t t
=
=000014
)()5()4()3()2()1(
pMpMpMpMpMpM
M
=
000104
Mp6t4 t5
110
)8()7()6(
pMpMpM
p5 p7
p1p2 p3
p5
t6t1 p8
t2 p4
p6
t3
t4 t5
010
t2 este validata si se declanseaza
),(),(Post),(Pre'
tCMttMM
+=+-=
Modelarea conceptelor dinamice in RP (1)(C/E si PT)
A B
concuren
A B A B
concuren sincronizare comunicare
A B
conflict/alegere
A B
resurse/multiplicitate
A B
date/individualitate
Modelarea conceptelor dinamice in RP (2)
(a) secveniere; (b) ramificaie; (c) sincronizare;(d) conflict la resurse; (e) concuren
Concluzii (modelare cu reele Petri elem.)
Se poate utiliza pentru a testa i valida anumite proprieti utile ale sistemelorn Sigurana: este garantat prin faptul c numrul de
simboluri nu crete nedefinitFuncionalitatea: este garantat prin lipsa blocajelor n Funcionalitatea: este garantat prin lipsa blocajelor va exista ntotdeauna cel puin o tranziie care poate fi declanat
Avantaj: modelarea sistemelor concurenteDezavantaj: nu este util pentru sisteme complexe
Alte proprieti i clasificri derivate Autonomie. O reea Petri se numete autonom dac nici timpul i nici alt constrngere de sincronizare extern nu sunt implicate n modeln O RP autonom se pstreaz ca o descriere pur calitativ a
sistemului observatn Reeaua din exemplul 3, anterior, este autonomn Reeaua din exemplul 3, anterior, este autonom
Simplitate. O RP se numete simpl dac elementele ei distincte (locaii sau tranziii) nu pot avea mulimi de intrare sau ieire similaren Reeaua din exemplul anterior este simpl
Puritate. O RP se numete pur dac nu conine cicluri n Reeaua din exemplul 3 nu e pur, deoarece exist ciclul (p2,t2)
Alte proprieti i clasificri (2)Mrginire (limitare). O RP se numete (n) mrginit dac numrul de jetoane din fiecare locaie poate atinge cel mult valoarea n n Reeaua din exemplul anterior este mrginit
Siguran. O RP se numete sigur dac marcajul fiecrei locaii poate fi doar 0 sau 1 (marcaj boolean), iar arcele au pondere unitarlocaii poate fi doar 0 sau 1 (marcaj boolean), iar arcele au pondere unitarViabilitate. O RP se numete viabil dac, indiferent de marcajul iniial i de evoluia sa, nici o tranziie nu poate deveni inactiv de o manier permanent. n Reeaua din exemplul anterior eueaz ntr-o stare terminal i
deci nu este viabilInvariani. O RP poate prezenta o serie de caracteristici invariante n timpul evoluiei sale dinamice, n principal referitoare la marcajele sau strile sale
Alte proprieti i clasificri (3)Conservativitate. O RP se numete conservativ dac numrul total de jetoane este constant (un invariant al reelei)n Reeaua din exemplul anterior nu este conservativ
Sub-conservativitate. O RP se numete sub-conservativ dac numrul total de jetoane este Sub-conservativitate. O RP se numete sub-conservativ dac numrul total de jetoane este constant sau n descretere pe parcursul evoluiei (dinamicii) salen Reeaua din exemplul anterior nu este sub-conservativ
Reversibilitate. O RP se numete reversibil dac din fiecare marcaj accesibil se poate ajunge din nou la marcajul iniialn Reeaua din exemplul anterior nu este reversibil
RP generalizateRP cu arce multiple (sau capacitate a arcelor > 2)n Numrul de arce intre o locaie de intrare si o tranziie
determina numrul de jetoane necesare in prima, pentru a o valida pe cea de-a doua
n Numrul de arce determin i numrul de jetoane ce n Numrul de arce determin i numrul de jetoane ce se consuma/ se produc
wait enter before make_picture after leave gone
free
Extensii ale modelului de baza:RP temporizate
Timpul nu este prins in modelul RP de bazaModalitile de extensie temporizata a lor au in vedere introducerea ntrzierilor deterministe att pentru locaii, cat si pentru tranziiiPot fi derivate concepte noi, de ex. timpul de ciclare (t): pp. reeaua consistenta, t este timpul completrii unei pp. reeaua consistenta, t este timpul completrii unei secvene de declanri ce reface marcajul initial:n ntrzieri pentru locatiiw tmin=max{ykTD (A+) Tx/ykTM0}
n ntrzieri pentru tranzitiiw tmin=max{ykT(A-) TDx/ykTM0}
n Rezulta pentru o RP temporizata simpla (GM)w tmin = max{total delay in Ck/M0 (Ck)}
RP stochasticeAsemntoare RP temporizate, diferena e in intarzierile introduse, care sunt nedeterministe n De ex., putem avea ntrzieri de tranzitare modelate ca v.a.
distribuite exponenialApar proprieti noi: n graful de accesibilitate al unei RP stochastice mrginite este n graful de accesibilitate al unei RP stochastice mrginite este
izomorf cu un lan Markov finitn O RP stochastica reversibila genereaz un lan Markov ergodic, in
care distribuiile de probabilitate in starea stabila dau estimatorii de performanta:w Probabilitatea unei condiii particularew Valoarea ateptata a numrului de simboluri (jetoane)w Numrul mediu de declanri in unitatea de timp
RP stochastice generalizate adaug tranziii imediate pentru a reduce spaiul strilor
RP de nivel inaltIncludem in aceasta categorie:n RP cu predicate/tranziiin RP coloraten RP cu simboluri individualizate
Orice RPNI poate fi translatat intr-o reea ordinara:Orice RPNI poate fi translatat intr-o reea ordinara:n Fiecare locaie se translateaz intr-un set de locaii,
de ex. cate una pentru fiecare culoare a jetoanelor coninute
n Fiecare tranziie se translateaz intr-un set de tranziii, cate una pentru fiecare modalitate de declanare
RPNI: exemple
a,ad,d
2xa
d
2
2
e+
e
Invarianti numerici
In toate cazurile
A#A < n
n
A|A| - #A < nn
A B (|A| - #A < n) n m
pot fi aplicate metode logice pentru retele P/T, folosindinegalitati asupra numarului de resurse ca propozitii elementare
tehnicile numerice specifice pot fi insa mai eficiente
Evenimente moarte (nevalidabile) Invarianti sistem (fapte)
(|A| - #A < n) and (|B| - #B < n)
A
B (#A < n)or (|B| - #B < n)
n
m
Invariani, tehnici numerice
+-
=altfel,0
la la de arce exista daca, la la de arce exista daca,
:, ptnntpnn
C tp
pnnm p locatiain jetoane exista daca ,:=
Matricea de incidenta C a unei retele P/T pure (fara cicluri):
Vectorul marcajelor m al unei retele P/T: t
pn
Contributialui t la ppnnm p locatiain jetoane exista daca ,:=
ori de adeclanseaz se tranzitiadaca ,: ntnf t =Vectorul de aprindere f al unui multi-set de tranzitii (fara reprezentarea ordinii!):
Vectorul pondere i al unor locatii: set de locatii cu suma jetoanelor constanta
''**)'(:', mimimimimmmm tpp
ppp
pt ===" a
Conditia necesara, nu si suficienta de accesibilitate:
00)'(' ==-= Cimmimimi tttt
lui t la p
'mfCm t =+
Propoziii si predicate
17 x+y=z
P
a Scheme cu conditiibPa Pb
1 7
Retele predicate/tranzitii: jetoanele individuale sunt extensii de predicate si inlocuiesc conditii propozitionale cuantificatori si specificatori intr-o logica a predicatelor permit grupari de evenimente la nivel propozitional in scheme cu evenimente la nivel de predicate
P
Q
R
7
2
x
y
z
x+y=z
Scheme cu evenimente
P
QR
7
2
1
2
27
3
9
Aplicabilitatea RP ord. i de NI n analiza performanelor sistemelor
Are n vedere 3 direcii principale:n Demonstrarea fezabilitii unui concept,
metode, tehnici sau algoritmCompararea a mai multe metode, tehnici n Compararea a mai multe metode, tehnici sau algoritmi
n nelegerea impactului diferiilor factori i parametri din sistemul modelat asupra performanelor cantitative, scalabiliti sau robusteii sistemului
Analiza performanelor (rev.)
n studiile de performan se evideniaz trei mari metode:n Abordri analiticew Folosesc modele matematice elementare/abstracte, w Folosesc modele matematice elementare/abstracte,
lanuri Markov, teoria ateptrii, reele Petri, etcn Simulriw Proiectarea i execuia experimentelor de simulare i modelelor simplificatoare de performan
n Abordri experimentalew Folosesc msurri asupra sistemelor reale
Analiza cu RP
Urmrete s determine:n Proprietile comportamentale (contextuale)
ale modelului cu reele Petrin Graful de cazuri (arborele de acoperire)n Graful de cazuri (arborele de acoperire)n Evoluia algebric a RP (matrici de inciden)n Evoluia ecuaiilor de stare
Proprieti comportamentale (1)Sunt acele proprieti care depind de marcajul
iniial M0 al RPAccesibilitatea n Se refer la posibilitatea de atingere a unei stri,
codificate de un marcaj al reelei, dintr-o alt starecodificate de un marcaj al reelei, dintr-o alt staren Marcajul Mn e accesibil din M0 dac exist o secven
de tranziii ce transform M0 n Mnn Accesibilitatea este decidabil, dar exponenial
Mrginire (limitare)n O RP e (n)mrginit dac numrul de jetoane din fiecare locaie
nu depete valoarea n pentru orice marcaj ce deriv din M0n O RP este sigur dac este 1-mrginit
Proprieti comportamentale(2)Viabilitatean O RP se numete viabil dac, indiferent de marcajul
atins, este posibil declanarea unei tranziiin Este echivalent cu lipsa blocajelor to deadlock-freen strong property, different levels of liveness are
defined (L0=dead, L1, L2, L3 and L4=live)defined (L0=dead, L1, L2, L3 and L4=live)Reversibilitaten O RP este reversibil dac pentru orice marcaj M
accesibil din M0, M0 este acesibil din Mn Condiia relaxat: marcajul M s.n. stabil (home state)
dac pentru orice marcaj M accesibil din M0, M este acesibil din M
Behavioral properties (3)Coverabilityn a marking is coverable if exists M reachable from
M0 s.t. M(p)>=M(p) for all places pPersistencePersistencen a PN is persistent if, for any two enabled
transitions, the firing of one of them will not disable the other
n then, once a transition is enabled, it remains enabled until its fired
n all marked graphs are persistentn a safe persistent PN can be transformed into a
marked graph
Behavioral properties (4)Synchronic distancen maximum difference of times two transitions are
fired for any firing sequence)()(max 2112 ttd sss -=
n well defined metric for condition/event nets and marked graphs
Fairnessn bounded-fairness: the number of times one
transition can fire while the other is not firing is bounded
n unconditional(global)-fairness: every transition appears infinitely often in a firing sequence
2112 s
Analysis methods (1)Coverability treen tree representation of all possible markingsw root = M0w nodes = markings reachable from M0w arcs = transition firings
n if net is unbounded, then tree is kept finite by introducing the symbol w
n Propertiesw a PN is bounded iff w doesnt appear in any nodew a PN is safe iff only 0s and 1s appear in nodesw a transition is dead iff it doesnt appear in any arcw if M is reachable form M0, then exists a node M that
covers M
Coverability tree example
t3p1
M0=(100)
p2
t2
t1
p3
t0
Coverability tree example
t3p1
M0=(100)
M1=(001)
t1
p2
t2
t1
p3
t0
M1=(001)dead end
Coverability tree example
t3p1
M0=(100)
M1=(001)
t1 t3
M3=(1w0)
p2
t2
t1
p3
t0
M1=(001)dead end
M3=(1w0)
Coverability tree example
t3p1
M0=(100)
M1=(001)
t1 t3
M3=(1w0)
p2
t2
t1
p3
t0
M1=(001)dead end
M3=(1w0)
t1
M4=(0w1)
Coverability tree example
t3p1
M0=(100)
M1=(001)
t1 t3
M3=(1w0)
p2
t2
t1
p3
t0
M1=(001)dead end
M3=(1w0)
t1
M4=(0w1)
t3
M3=(1w0)old
Coverability tree example
t3p1
M0=(100)
M1=(001)
t1 t3
M3=(1w0)
p2
t2
t1
p3
t0
M1=(001)dead end
M3=(1w0)
t1
M4=(0w1)
t3
M6=(1w0)old
t2
M5=(0w1)old
Coverability tree example
100M0=(100)
M1=(001)
t1 t3
M3=(1w0)t1 t3
1w0001M1=(001)dead end
M3=(1w0)
t1
M4=(0w1)
t3
M6=(1w0)old
t2
M5=(0w1)old
t1
1w0001
0w1
t3
t2
coverability graph coverability tree
Analysis methods (2)Incidence matrixn n transitions, m places, A is n x mn aij = aij+ - aij-
a is the number of tokens changed in n aij is the number of tokens changed in place j when transition i fires once
State equationn Mk = Mk-1 + ATukn uk=ei unit vector indicating transition i fires
Necessary reachability condition
Md reachable from M0, thenMd = M0 + AT (u1+u2+...+ud)AT x = DM
then then DM range(AT)DM ^ null(A)Bf DM = 0
where the rows of Bf span null(A)
Analysis methods (3)Reduction rules that preserve liveness, safeness and boundednessn Fusion of Series Places
Fusion of Series Transitionsn Fusion of Series Transitionsn Fusion of Parallel Placesn Fusion of Parallel Transitionsn Elimination of Self-loop Placesn Elimination of Self-loop Transitions
Help to cope with the complexity problem