Despre Petri Nets

Nevoia introducerii unei tehnici care sa permita intelegerea si alegerea unor solutii optime pentru problemele legate de concurenta sistemelor l-a condus pe Carl Adam Petri la implementarea unei metode complexe dar usor de inteles si aplicat in acelasi timp. Petri Nets sau P/T net (place/transition net) este un model de analiza si reprezentare a sistemelor distribuite si concurente. Acest concept a fost definit pentru prima data in anul 1962 de catre Carl Adam Petri. In iulie 1961 Petri si-a depus teza de doctorat la Universitatea Tehnica din Darmstadt, urmand ca un an mai tarziu sa o sustina. Conform unor surse, Petri a inventat aceasta metoda la varsta de 13 ani, dorind sa explice mai usor procesele chimice.Retelele Petri descriu o metoda puternica de modelara formala in informatica si sistemele ingineresti si nu numai. Teoria matematica se imbina cu reprezentarea grafica a sistemelor dinamice. Modificarea unei stari a sistemului poate fi vizualizata. Acesta este motivul principal datorita caruia aceste retele au o raspandire larga.Astfel sistemele de evenimente discrete pot fi privite dintr-o alta perspectiva. Ele sunt formate din noduri intre care exista un anumit tip de interactiune. Aceste interactiuni se pot declansa concurent adica o componenta poate incepe executarea unei functii in timp ce o alta termina aceiasi functie. Cel mai simplu exemplu il reprezinta cel al unui ATM (Automated Teller Machine). Presupunem ca intr-o locatie cineva doreste sa realizeze o depunere, in timp ce intr-un alt loc, dar in cadrul aceleiasi retele, altcineva doreste sa retraga numerar. Din punctul de vedere al sistemului, aceste doua operatiuni nu sunt independente: ele modifica starea sistemului prin cresterea sau scaderea depozitului bancar. Dar ce se intampla daca unui cont i se asociaza doua carduri de credit, care se folosesc simultan?Intr-un sens mai restrans, conceptul de retea Petri realizeaza descrierea intr-un limbaj matematic a structurii unui sistem analitic. In esenta, PN este un tip special de graf. Asftel o descriere scurta a teorie grafurilor este necesara.

Grafuri - GeneralitatiUn graf este o structura matematica folosita pentru a modela relatiile binare. Este compus din doua element: noduri si muchi (sau arce) intre care se afla o anumita relatie de interconectare. Un graf reprezinta o pereche ordonata de multimi: , unde: V este o multime finita si nevida de elemente numite varfurile grafului; E este o multime de perechi de varfuri din graf. Daca graful este neorientat, atunci perechile de varfuri din multimea E se numesc muchii. Perechea neordonata formata din varfurile x si y se noteaza [x,y]; varfurile x si y se numesc extremitatile muchiei.In cazul in care graful este orientat, perchile de varfuri din multimea E sunt ordonate si se numesc arce. Perechea ordonata formata din varfurile x si y se noteaza (x, y). Varful x se numeste extremitatea initiala a arcului iar varful y se numeste extremitatea finala a arcului.Figura 1 Graf neorientatFigura 2 Graf Orientat

Daca toate arcele unui graf sunt orientate, atunci graful se numeste graf orientat sau digraf (directed graf). Un astfel de exemplu este in Figura 2.Daca exista un arc sau o muchie cu extremitatile in x si y, atunci varfurile x si y sunt adiacente; fiecare extremitate a unei muchii/ a unui arc esce considerata incidanta cu muchia/arcul respectiv[1]. Nodurile nu au o reprezentare fixa, adica pot fi descrise doar de puncte. Ele pot lua si alte forme, in functie de particularitatile aplicatiei in care se utilizeaza.Daca intre doua varfuri exista mai multe muchii/arce atunci structura se numeste multigraf. Figura 3 Nu este un multigraf

Figura 4 - Multigraf

O proprietate importanta a unui multigraf este multiplicitatea unui arc. Aceasta se refera la numarul de tokenuri necesar unei stari pentru a initia o tranzitie.O retea Petri este un graf bipartit,. Un graf bipartit este un graf , cu propietatea ca exista doua multimi N si M, NU si MN, astfel incat: NM=, NM=U toate muchiile grafului au o extremitate in N si cealalta in MUn graf bipartit complet este un graf in care pentru orice varf din x din N si orice varf y din M exista muchia (x, y).Figura 5 Graf bipartitFigura 6 Graf bipartit complet

In limbajul Petri exista doua tipuri de noduri. Primul timp de nod se numeste stare si este reprezentat printr-un cerc sau o elipsa. Cel de al doilea tip de nod se numeste tranzitie si poate fi un dreptunghi sau o bara verticala solida. Conexiunile se fac doar cu arcuri. Nu exista muchii. Arcurile sunt intotdeauna orientate.Figura 7 - StareFigura 8 - TranzitieFigura 9 - Arc

Un graf bipartit are o propietate speciala: un arc poate conecta doua noduri de tipuri diferite. Asadar poate exista o legatura intre o stare si o tranzitie, de la o tranzitie la un stare, dar niciodata de la o stare la o alta stare sau intre doua tranztii[2].Retele Petri uzualeO retea Petri este un graf bipartit orientat definit astfel:, unde reprezinta un numar finit de stari reprezinta un numar finit de tranzitii reprezinta o legatura corespunzatoare unui set de arce orientate de la o stare la o tranzitie reprezinta o legatura corespunzatoare unui set de arce orientate de la o tranzitie la o stare

Figura 10 Exemplu de retea PetriExemplul de mai sus poate fi definit astfel:

O bucla intre tranzitie si o stare este posibila daca starea reprezinta atat un element de intrare cat si un element de iesire pentru bucla. O retea Petri este pura daca nu contine nicio bucla.Un exemplu de este in figura de mai jos.

Figura 11 Retea Petri care nu este puraSubretea PetriConceptul de subretea se bazeaza pe teoria grafurilor, interpertata in contextul Petri [3]Fie o retea Petri: . O subretea Petri este , unde PSP, TST iar IS si OS sunt restrictii ale lui I si O la respectiv . In Figura 11 este posibila o subretea:, unde , , si .DrumulUn drum reprezinta un set de k noduri si k-1 arce, unde . Drumul este orientate pentru toate arce care conecteaza nodul i cu nodul i+1.Un drum care parcurge un arc o singura data se numeste drum simplu. Un drum care trece prin acelasi nod o singura data se numeste drum elementar. Desigur, orice drum elementar este un drum simplu, insa reciproca este falsa. In Figura 11 drumul p1, t2, p5, t3, p3, t4, p2 este elementar. Drumul p1, t2, p5, t3, p4, t3, p3, t4, p2 nu este elementar deoarece t2 este parcursa de doua ori.ConectivitateaO retea Petri este conectata daca si numai daca exista un drum nu neaparat direct - intre oricare doua noduri. Notiunea conectivitate la o retea Petri este echivalenta cu un graf complet.Conectivitate tareO retea Petri este tare conectata daca si numai daca exista un drum direct intre oricare doua noduri.Circuit orientatUn circuite este orientat daca exista un drum care are ca punct de plecare un nod si se punctul de sosire este acelasi nod. Un circuit orientat elementar este un drum in care fiecare nod apare doar o singura data. Un exemplu de circuit elemetar orientat in Figura 10 este lantul: p1 t2 p3 t5 p4 t3 p1 t2 p2 t4 p5 t2Algebra liniara in retele PetriPN pot fi descrise si matematic. Avantajul principal al posibilitatii reprezentarii retelelor Petri si in limbaj algebric este principalul motiv pentru care a devenit un instrument atractiv in aplicatiile asistate de calculator, unde utilizatorul poate intercationa grafic cu reteaua vizualizata. In acest sens se defineste matricea de incidenta.Structura topologica a unei retele Petri pura poate fi reprezentata cu ajutorul unei matrici C numita matrice de incidenta sau matrice flux. Dimensiunile sale sunt unde m este corespunzator tranzitiilor iar n este corespunzator starilor. Matricea C este definita astfel:, unde si .Matricea de incidenta este definita doar pentru retelele Petri pure. In cazul unei retele care nu este pura, bucla nu se poate defini in matricea de incidenta.O si I se pot determina plecand de la matricea de incidenta folosind relatiile: si Matricea de incdenta pentru Figura 10 este:

Retelele Petri nu ar mai fi atat de utile daca ar permite doar reprezentarea nodurilor. Acest lucru se poate realiza intr-o maniera mult mai usoara folosind softuri informatice dedicate. Insa avantajul PN este ca pot fi executate. Se poate observa si studia ineractiunea intre componentele dinamice ale unui sistem. Pe langa de cele doua tipuri de noduri stari si tranzitii si arce, un al patrulea element este introdus in vederea descrierii dinamicii PN. Acest obiect se numeste token (jeton).[2] Este reprezentat printr-un punct solid ca in Figura 12.

Figura 12 Token-uriIn PN uzuale, tokenul nu reprezinta o informatie semnificativa, ci doar indica prezenta sau absenta unei conditii. Numarul de tokenuri pe care il poate avea o stare poate fi restirctionat sau arbitrar. Prezenta unui arc intre o tranzitie si o stare indica faptul ca respectiva tranzitie necesita ca starea sa detina un token (in cele mai multe cazuri) pentru a se declansa. MarcareaO marcare PN notata cu M reprezinta urmatoarea mapare: P {0, 1, 2 ..}, in care se asociaza fiecarei stari din retea un numar specific de tokenuri. Marcarea se reprezinta printr-un vector cu dimensiunea n .Un exemplu de astfel de vector (pentru o retea cu cinci stari) este urmatorul:

In sens restrans, vectorul marcare defineste reteaua Petri. Procesul prin care are loc redistribuirea tokenurilor se numeste declansarea/realizare/tragere/consumare/actionare/activarea tranzitiei.In procesul de modelare al majoritatii sistemelor, propietatile multgrafurilor reprezinta un avantaj. Insa un conceptul de multigraf intr-o retea Petri determina o complexitatea ridicate. De aceea, in retelele uzuale, nu se folosesc multigrafuri. Acestea apar insa in extensiile Petri cum ar fi Colored Petri Nets.