. Modelarea Si Evaluarea Performantelor Sistemelor de Calcul Prin Retele Petri

Introducere

Sistemele de calcul cu prelucrare distribuita a datelor sunt concepute ca un ansamblu de subsisteme, care, la randul lor, sunt supuse unor constrangeri de functionare in paralel. Definirea unei confguratii a sistemului de calcul, destinata sa functioneze intr-un anumit context, trebuie sa corespunda, in general, unor restrictii de performanta si de cost specific. In ceea ce priveste restrictiile de performanta se urmareste asigurarea caracteristicilor functionale impuse de tipul aplicatiilor carora le este destinat sistemul de calcul si aceasta la un nivel acceptabil, in sensul satisfacerii timpului de raspuns, puterii de procesare a fiabilitatii, tolerantei la defecte etc.

Caracteristicile functionale si de performata ale sistemului elaborat sunt determinate printr-o activitate de modelare a contextului real in care urmeaza sa functioneze. Modelul de referinta adoptat trebuie sa captureze toate proprietatile si caracteristicele viitorului sistem. Precizia si completitudinea definirii acestor proprietati si caracteristici sunt de o importanta vitala pentru obtinerea unui sistem corespunzator obiectivului pentru care a fost construit. Scopul unui model este de a defini caracteristicele si proprietatile sistemului de construit si de a prevedea o baza pentru verificarea acestora. Diferite modele pot fi folosite pentru a exprima proprietati diferite: in mod alternativ pentru a exprima o proprietate a sistemului dintr-o clasa de modele se alege sau se construieste un model adecvat pentru a reprezenta aceste proprietati. Exista mai multe modele bazate pe metode, tehnici si formalisme in mod potential ce pot fi folosite pentru a descrie proprietati de comportare ale sistemelor de calcul distribuie: functii matematice, ierarhia functionala, masini cu stari finite, logica temporala, retele de sisteme de asteptare, retele Petri etc. In general nu exista un model prin care pot fi reprzentate toate proprietatile sistemului studiat. De regula, aceste modele sunt folosite in mod complementar, in cadrul unor metode si tehnici dublate de instrumente de modelare, verificare, analiza si evaluare a performantelor sistemului de proiectat.

Prezenta lucrare isi propune o descriere a conceptelor teoretice si a realizarilor practice ale tehnicilor de modelare si evaluare a performantelor sistemelor de calcul prin retele Petri de cateva modificatii. Selectarea materialului a fost facuta pentru a crea, pe cat posibil, o imagine de ansamblu a stadiului actual a problematicii folosirii tehnicilor de specificare, modelare, validare si evaluare a performantelor executarii proceslor paralele ale sistemelor de calcul cu retele Petri markovine.

In primul capitol sunt prezentate unele elemente de baza a teoriei proceselor stochastice, astfel ca lanturile Markov si procesele Markov discrete in timp continuu. Tot aici sunt determinate si proprietatile de conservare a fluxului de probabilitate in graful de trecere al unui lant Markov.

In capitilul doi este prezentata o interpretare a temporizarilor aleatorii ale tranzitiilor retelelor Petri, in baza careia este definita in forma generala o retea Petri stochastica, ceea ce da posibilitatea de a descrie in continuare retele Petri markoviene si retele Petri markoviene generalizate. Sunt determinate proprietatile de conservare ale proceselor de marcare a locatiilor si de declansare a tranzitiilor si se aduc conditiile necesare si suficiente de ergocitate ale retelelor Petri markoviene. Un loc aparte il ocupa matricea dinamica si caracteristicile numerice de performanta ale retelelor Petri markoviene, in baza carora sunt efectuate unele studii de caz.

Elemente de procese stochastice

Generalitati

Procesele stochastice permit modelarea matematica a numeroaselor componente ale sistemelor tehnice, economice, sociale etc.

Prin definitie, un proces stochastic este o familie de variabile aleatoare X(τ) ce apartin unui spatiu Wx(τ), numit spatiu de stari si care sunt indexate dupa un parametru τ. Atunci un proces il putem reprezenta astfel:

{ X(τ)Wx(τ), τ}. (1.1)

Ansamblurile Wx(τ) si pot fi de tip discret sau continuu. Se poate adopta terminologia de proces sau lant in functie de variabila continua sau discreta a parametrului , care in mod frecvent reprezinta timpul.

Pentru a evalua starea unui sistem, trebuie utilizat un vector X de stare, reprezentat printr-o familie de variabile aleatoare X(τi), independente intre ele:

X={X(τ1), X(τ2),…, X(τi),…} (1.2).

Este necesara introducerea notiunii de probabilitate de stare, x():

x()=Prob{X(τ)=x}, (1.3)

care este si ea o functie de parametrul , reprezentand probabilitatea ca variabila X sa ia valoarea x la momentul ; este de fapt, probabilitatea absoluta a starii X(τ).

Probabilitatea conditionata a trecerii de la o stare x1 la o alta x2 , prin unul sau mai multe salturi temporale, se noteaza prin:

(1.4)

si reprezinta probabilitatea trecerii intre cele doua stari, eveniment ce se desfasoara in intervalul de timp ∆=2-1.

Procesele stochastice se analizeaza urmarindu-se, functia de repartitie a probabilitatilor FX(X,):

FX(X,)=Prob{X(τ1)x1, X(τ2)x2,…, X(τi)xi,…} (1.5).

Pe aceasta linie procesele stochastice se impart in:

procese stationare

Un proces X(τ) este stationar daca functia de repartitie a probabilitatilor ramane egala cu ea insasi pentru orice traslatie ∆ τ pe axa timpului, adica:

FX(X,+∆)= FX(X,) (1.6).

procese independente

Conceptul de independenta intre variabilele X(τi) se traduce prin:

(1.7).

procese Markov

In aceasta categorie se incadreaza procesele ale caror variatie aleatoare are loc, astfel incat fiecare dintre starile X(τo), X(τ1), …, X(τi), … care corespund momentelor succesive τo, τ1, … , τi, … care nu depind decat de un numar finit k de stari precedente. Daca spatiul starilor este discret, atunci este cazul unui lant Markov de ordin k. Clasa cea mai frecventa de procese Markov este aceea pentru care k=1. Aceasta inseamna ca, fiind data o succesiune de stari X(τk) ale unui asemenea proces, starea X(τj+1) depinde de starea precedenta X(τj), adica in termeni probabilistici:

Prob{ Xj+1(τj+1)=Xj+1|X(τ0)=X0, X(τj)=Xj}=Prob{X(τj+1)=Xj+1| X(τi)=Xi} (1.8).

Aceasta reprezinta proprietatea fundamentala a proceselor markoviene:

O stare viitoare nu depinde decat de starea prezenta, adica tot trecutul este continut in prezent. Cu alte cuvinte, procesele Markov sunt procese fara memorie.

Lanturi Markov

In domeniul de interes al sistemelor de calcul se afla procesele Markov cu spatiul discret de stari si cu parametrul temporal discret, numit lanturi Markov (LM).

Starile unui asemenea proces sunt reprezentate printr-o variabila aleatoare M() ce parcurge ansamblul numerelor intregi nenegative N+. parametrul temporal poate parcurge la randul lui ansamblul numerelor intregi succesive, reprezentate de exemplu prin litera j, cu j0 ce formeaza un lant discret.

Deci, starea M(j) a sistemului, a carei evolutie se analizeaza, este prezentata prin nj, ceea ce se citeste ca starea n la momentul j.

Daca are loc trecerea de la starea nj in starea nk cu k>j, atunci, inseamna, ca are loc o tranzitie.

Conform definitiei proceselor Markov se poate scrie ca:

Prob {Mk = nk | M(1)=n1, …, M(j)=nj}=Prob{Mk=nk | M(j)= nj} (1.9)

Adica starea viitoare la momentul j+1 nu depinde decat de cunoasterea celei prezente din momentul actual j.

Daca este probabilitatea absoluta a starii ni, atunci, spatiul probabilitatilor la momentul j este prezentat printr-o matrice-linie (j) ale carei componente sunt 0(j), 1(j),…, fiecare din ele avand valori inferioare sau egale cu unitatea, adica:

(j) = [ 0(j), 1(j),…, k(j),…] (1.10)

si stiind ca pentru orice nj0 exista: cu .

Daca sistemul executa trecerea intre doua momente succesive j si j+1, adica daca trece din starea nj=n in starea nj+1 = k, atunci este probabilitatea conditionata de trecere.

In graful de trecere al LM din fig 1.1 este reprezentat spatiul starilor unui sistem. Prin noduri sunt reprezentate starile posibile {0, 1, 2, …, n} la momentul j, iar arcele orientate arata trecerile spre starea k la momentul j+1. Aceste arce sunt ponderate cu probabilitatile de trecere rn,k respective.

Respectand caracteristica procesului Markov, se poate scrie ca:

(1.11)

dar aceasta presupune ca la momentul j sistemul se afla intr-o stare oarecare M(j) si are loc trecerea pentru ca el sa ajunga in starea k(j+1) la momentul j+1, adica:

(1.12)

ceea ce in termeni de probabilitate se exprima ca:

(1.13)

adica in general:

(1.14)

Aceasta expresie este forma de redare matematica a caracterului markovian al procesului in care starea viitoare k nu depinde decat de starea prezenta n. De asemenea, exista o independenta totala intre evenimentele n(j) si trecerile de tip realizate dinspre toate celelalte, oricare ar fi valorile lui n.

In consecinta, probabilitatea intersectiei acestor evenimente este egala cu produsul probabilitatilor lor individuale.

Probabilitatile de trecere rn,k se pot grupa intr-o matrice patrata R, numita matrice stochastica de treceri, in care suma elementelor pe fiecare linie este egala cu unitatea.

In concluzie se poate scrie ca spatiul probabilitatilor este caracterizat prin relatia matriciala:

(k+1)=(k)R sau (+∆)=()R (1.15)

ceea ce conduce la a scrie ca:

(k)=(0)Rk (1.16)

Ecuatiile (1.14) si (1.15) sunt ecuatiile Kolmogorov ce descriu comportarea unui lant Markov.

Procese Markov in timp continuu

Prin contributia lui Erlang la studiul sistemelor de telecomunicatii s-a introdus notiunea de echilibru stochastic. Orice retea de telecomunicatii functioneaza intr-un asemenea echilibru in care apelurile (cererile de serviciu) se nasc, asteapta servirea, traiesc o viata, ca apoi in final sa moara.

Procesele de nastere si moarte, ca o subclasa importanta a proceselor Markov cu spatiu discret de timp continuu se adapteaza perfect modului de aparitie si de servire a traficului in sistemul global de telecomunicatii si in retele de calcul. Ele sunt caracterizate de un spatiu discret de stari si de un parametru temporal continuu.

Prin definitie un proces de nastere si moarte autorizeaza pentru un sistem, care la momentul are starea X() de marimea n, trecerea la momentul urmator ’ (’>) numai catre starile adiacente k=n+1 sau k=n-1; evident ca starea k=n poate fi eventual mentinuta si la momentul ’.

Evolutia dinamica a unui sistem conform unui proces de nastere si moarte poate fi reprezentata ca in Fig.1.2 , sub forma unui lant Markov liniar cu un numar finit de N+1 stari.

Pentru simplificarea desenului nu s-a reprezentat decat pentru n trecerea de tip (fluxul intern de probabilitati rn,n); de asemenea nu este marcat nici intervlul ∆=’- in care se pot produce trecerile, controlate prin termeni de tipul rn,k()∙∆. De fapt, factorul rn,k() apare ca o rata a schimbarii de stare, care multiplicata prin ∆ masoara chiar probabilitatea trecerii . Pe durata intervalului ∆ nu poate avea loc decat, cel mult, o singura trecere, iar aceasta este permisa doar intre stari adiacente. Deci conform relatiei (1.13) se poate scrie ca:

(1.17).

Dupa cum s-a precizat deja anterior, pentru orice proces Markov se poate forma matricea R stochastica de trecere, ale carei elemente sunt probabilitati de trecere intre stari.

Daca procesul este caracterizat de un parametru temporal continuu atunci se pot determina coeficientii unei matrice A, matricea infinitezimala, ale carei elemente sunt:

– pentru n≠k: (1.18)

– pentru n=k: ,

Stiind ca: , (1.19)

atunci un proces Markov cu o distributie continua in timp este caracterizat de o ecuatie a viitorului, numita ecuatia ChaRPman-Kolmogorov, a carei forma este:

(1.20)

Daca insa probabilitatile de trecere sunt conforme unor procese omogene si stationare, atunci este adevarat ca:

(1.21)

Cu este notat indicele Landau, o marime ce tinde la zero mai rapid decat timpul elementar , adica:

In consecinta, in conditiile echilibrulu
In consecinta, in conditiile echilibrului statistic, se obtine ecuatia echilibrului global scrisa in relatia (1.22) si care probabilistic exprima faptul ca suma fluxurilor de probabilitati de iesire dintr-o stare este identica cu suma fluxurilor de intrare:

(1.22)

Se poate observa ca fluxurile de intrare si de iesire asociate starilor interne nu intervin, desi au fost luate in calcule, inseamna de fapt ca omiterea lor din fig.1.2 nu prejudiciaza cu nimic rezultatul corect al calculului probabilitatilor.

Conservarea fluxului de probabilitate

Fie dat un proces Marcov omogen cu un spatiu de stari discret in timp continuu, asociat la un fenomen de asteptare, al carui numar de stari este finit (sau infinit), pentru care exista un regim stationar, adica evolutia sa este independenta de distributia sa initiala si momentul de timp observat.

Se poate construi graful de trecere LM dintr-o stare in alta intre doua momente τ si infinitezimal vecine. Nodurile grafului simbolizeaza starile;

arcele reprezinta trecerile de probabilitate nenule din starea Mi in starea Mj , adica (o probabilitate in este considerata ca nula). Probabilitatea de a trece din starea Mi in starea Mj este de forma probabilitatea de a ramane in Mi: , avand in vedere omogenitatea procesului Marcov, aceste probabilitati nu depind de τ, ci numai de Δτ.

Fie acest graf, unde este multimea nodurilor, iar A multimea arcelor. Fie, de asemenea, o submultime de noduri. Vom numi S-taietura asociata la submultimea nodurilor S multimea de arce , ce au o extremitate si numai una in S.

Prin definitie, vom numi flux de probabilitate a trecerilor din starea Mi spre starea Mj marimea , unde πi este probabilitatea starii Mi a sistemului in regim stationar, iar λi,j rata de trecere a .

Teorema 1.1 Pentru orice graf al unui lant Marcov in regim stationar fluxul de probabilitate a trecerii spre exteriorul intregii S-taieturi, este egal cu fluxul de probabilitate al trecerilor spre interiorul ei:

Demonstratie:

1) Presupunem ca taietura S={Mi} este redusa la un singur nod Mi (fig. 1.3.). Calculam probabilitatea starii Mi in momentul τ+Δτ:

(1.23)

Intr-adevar, in momentul τ lantul LM era fie in starea Mi si acolo el va ramane sau fie in starea Mj, (i≠j) si in intervalul de timp Δτ a trecut in starea Mi .

In regim stationar avem . Folosind ecuatia (1.23) si simplificand prin Δτ, obtinem :

(1.24)

adica: ce exprima faptul ca fluxul de probabilitate al trecerilor din starea Mi spre starile Mj, (i≠j) este egal cu fluxul de probabilitate al trecerilor din aceste stari spre starea Mi.

2) Presupunem ca taietura S este constituita din doua noduri S={Mi, Mk}; conform relatiei (1.24) se poate de scris urmatoarele ecuatii:

pentru Mi : ,

pentru Mk : .

Sumarea membru cu membru a acestor ecuatii, dupa simplificarea termenilor corespunzatori, prezinta fluxul de probabilitate al trecerilor intre Mi si Mk :

,

adica: (1.25).

3) In sfarsit, prin inductie asupra numarului de noduri ale taieturii S, urmeaza ca ecuatia (1.25) de mai sus este justa pentru orice taietura .

Exemplu de aplicare a teoremei de conservare. Fie dat un proces general de nastere si moarte a cererilor asociat la un sistem cu asteptare (SA) intr-un nod de comunicatie al unei retele de calcul, graful de trecere al LM ce descrie acest proces ete reprezentat in (fig.1.4); ce presupune ca regimul stationar este posibil si poate fi atins. Prin noduri Mk , sunt reprezentate starile posibile ale sistemului, numerotate incepand cu M0, iar prin arce sunt figurate posibilele treceri intre stari. Pe fiecare arc sunt notate probabilitatile conditionate de nastere sau moarte caraceristice starii de plecare si sensului trecerii.

Un proces general de nastere si moarte a cererilor in SA se caracterizeaza prin urmatoarele:

– procesul este omogen in timp;

– singurele treceri sunt cele care fac sistemul aflat intr-o stare k sa evolueze catre starile vecine k-1 si k+1 sau sa se mentina in starea prezenta,

– plecand de la starea , probabilitatile conditionate de trecere intr-un interval de timp Δτ catre starile vecine sunt stabilite de catre relatiile ce urmeaza:

Prob

Prob

Prob

– probabilitatea ca pe durata intervalului sa apara mai mult de o trecere este infinit mai mica decat Δτ si este exprimata prin O(Δτ).

Plecand de la acest graf de trecere al LM din (fig. 1.4), se pot scrie usor ecuatiile echilibrului global si ale echilibrelor locale.

Fie S3={ M0,…, Mk} o taietura (fig. 1.4 si fig. 1.5). Aceasta revine la faptul de a efectua o taietura intre Mk si Mk+1 ; teorema 1.1 indica, ca fluxul de probabilitate al cererilor de la Mk spre Mk+1 este egal cu fluxul de probabilitate al trecerii in sens inver, adica:

Aceasta ecuatie este o ecuatie recurent multiplicativa, ceea ce permite de a deduce rezultatul clasic, care este:

Pentru orice sistem este valabila relatia de normalitate, care reflecta, de fapt, certitudinea ca sistemul se afla in orice moment intr-o stare a sa, oricare ar fi ea, adica:

Aceasta conduce la a determina ca:

(1.26)

In final: (1.27)

Daca numarul total Ns de stari ale sistemului este infinit, atunci πk este definita numai daca numitorul din expresia (1.26) este o serie convergenta. Aceasta are loc daca pentru orice k; de fapt, in caz contrar nu s-ar putea ajunge nici la echilibrul static al procesului. Daca Ns este finit, atunci acest numitor este in mod obligatoriu finit.

Relatia (1.27) are un caracter de maxima generalitate. Specificitatea sistemelor SA apare prin alegerea unor anumite dimensiuni pentru multimea surselor, a resurselor si a pozitiilor de asteptare, precum si prin alegerea unor procese de servire adecvata.

Aplicarea metodei diferentiale obisnuite revine la aplicarea teoremei de conservare a fluxului de probabilitate pentru un singur nod Mk (taietura S), notat nod k in fig. 1.5 si ca rezultat se obtine:

si rezolvarea ei este mai dificila. Observam, ca in aceasta recursie avem un invariant: care este nul (din cauza starii M0). Acest invariant corespunde intocmai conservarii fluxului de probabilitate a trecerilor intre starile Mk si Mk+1.

Astfel, daca intr-un graf de treceri starea Mk este incadrata cu o taietura S, atunci ea poate fi folosita la inventarierea, cu semnul corespunzator, a tuturor fluxurilor de probabilitati ce o traverseaza, obtinandu-se astfel simplu si rapid ecuatia echilibrului general. Alegand, de exemplu, taieturile S, S1, S2 si S3 care separara un grup de stari de restul starilor din graful din (fig. 1.5) se poate, raportand fluxurile la suprafetele rezultate, sa se obtina, simplu si rapid, ecuatiile de echilibru local si anume:

pentru S:

pentru S1:

pentru S2 :

pentru S3 :

Ultimele doua relatii indica faptul ca in ecuatia echilibrului global (1.22) termenii din membrul stang si cel drept sunt egali doi cate doi, adica, de fapt, pentru o stare Mk trecerile ascendenta si descendenta sunt echiprobabile. De asemenea, se precizeaza ca orice solutie a ecuatiilor echilibrelor locale sunt si solutii ale echilibrului global, dar nu si invers.

Elementele teoriei proceselor stochastice ce au fost considerate in acest capitol se vor folosi in continuare la definirea retelelor Petri stochastice ca modele matematice ce descriu diverse fenomene de functioare ale sistemelor de calcul distribuite.

Retele Petri colorate

Notiuni introductive

Tehnicile de modelare prin retele Petri s-au dovedit a fi bine adaptate la descrierea functionarii sistemelor cu prelucrare distribuita a datelor, unde intervin fenomene de concurenta si de sincronizare ale proceselor paralele. Deseori intr-un sistem de calcul putem intalni mai multe parti sau procese ce au o descriere identica si deci ele pot fi modelate de catre aceeasi retea Petri, motiv care trebuie repetat de atatea ori cate parti identice sunt folosite in sistemul modelat. Indata ce numarul acestor motive devine important, putem constata ca talia unui astfel de model devine inexploatabila. Intr-o retea Petri informatia de stare este determinata de locatiile sale. Prezenta unui marcher intr-o locatie poate de exemplu modela o resursa disponibila. Daca aceasta locatie este vida, aceasta inseamna ca resursa consderata este ocupata. Prezenta mai multor marcheri in aceiasi locatie poate reprezenta de exemplu un numar de cereri identice intr-un sistem cu asteptare. Daca se doreste imbogatirea semnificativa a informatiei aduse de catre o locatie a unei retele Petri este necesar de a avea posibilitatea de a distinge intre cei doi marcheri ce se afla in aceiasi locatie. In acest caz fiecarui marcher al locatiei considerate i se va asocia un identificator sau o culoare si astfel, informatia necesara se va reprezenta de catre ansamblul locatie-culoare. Astfel, putem defini un nou formalism de modelare: retele Petri colorate (RPC). Exista mai multe variante de retele RPC. Modelul care se va prezenta si folosi in continuare pentru definirea retelelor Petri colorate stochastice, a fost introdus de catre K. Jensen [1984]. Intr-o retea RPC fiecare tranzitie poate fi declansata in diferite moduri, fiind reprezentate astfel prin diferite culori de declansare, asociate cu tranzitia respectiva. Relatia intre culorile de declnasare si marcajul colorat, astfel constituit, este definita de culoarea respectiva, asociata cu arcele retelei. O culoare asociata la un marcher poate reprezenta un exemplu si poate purta o informatia complexa astfel ca de exemplu, natura si pozitia unei entitati in sistem. Astfel intr-o retea RPC, ca rezultat al declansarii tranzitiilor colorate, poate avea loc disparitia unor culori si crearea unor noi culori.

Exemplu 2.1: Inainte de a defini in mod formal retele RPC vom introduce acest model printr-o prezentare intuitiva a unei retele RPC1, care descrie comporatrea a doua elemente de prelucrare PEi , i=1,2 neidentice (alb si rosu) si nefiabile ale unui sistem multiprocesor, formula descriptiva a carora FLi, i=1,2 este: FLi=(ai/ri)*, i=1,2 (2.1)

unde ai, respectiv ri reprezinta starea locala activa de buna functionare a elementului PEi.

Retelele Petri RP, redate de catre formule FLi respective din (2.1) sunt reprezentate in Fig. 2.1.

Fiecare locatie a acestor retele RP reprezinta o stare locala a sistemului considerat. Pentru fiecare element PEi locatiile p1a si p1r reprezinta starea locala de buna functionare, iar locatiile p2a si p2r reprezinta faptul ca elemetul de prelucare respectiva este defectat.

Schimbarea starilor este redata de catre declansarea tranzitiilor t1a (respectiv t1r), sau t2a (respectiv t2r), care modeleaza faptul caderii in pana si depanarea elementului PEi.

Starea initiala de buna functionare este determinata pentru fiecare element PEi.

Analizand modelul acestui sistem din Fig. 2.1, constatam ca acest model este constituit din doua retele RP identice. Daca vom contopi aceste doua retele RP in una singura, atunci vom obtine reteaua RP reprezentata in Fig 2.2a redata de formula FL=(2a/r)*. Aceasta retea nu descrie corect functionarea sistemului si a elementelor PEi, (i=1,2), fiindca cunoasterea marcajului accesibil respectiv este insuficient pentru a reda starea locala a fiecarui din aceste elemente. De exemplu, indata ce doua locatii p1 si p2 sunt marcate, nu se stie care element PE1 sau PE2 se afla in starea buna de functionare sau in pana. Pentru a modela corect sistemul multiprocesor din doua elemente PE diferite este necesar de a distinge marcherii intre ei in reteaua RP din Fig 2.2a. Pentru aceasta vom asocia o culoare la fiecare marcher. Fie un marcher a – de culoare alba pentru elementul PE1 si un marcher r – de culoare rosie pentru elemente PE2. Locatiile p1 si p2 pot atunci sa contina marcheri colorati si deci aceste valori vor apartine multimi {a, r}. Tranzitia t1 este declansabila in raport cu culoarea r. Declansarea tranzitiei t1 consta in a retrage un marcher de culoare r din locatia p1 si de a ajuta un marcher de aceeasi culoare r .

In retele RPC o functie de colorare este, de asemenea asociata la fiecare arc, pentru a reda relatia ce are loc intre culoarea respectiva asociata la o tranzitie (culoare de declansare) de a o selecta pentru a declansa aceasta tranitie si a reda culoarea asociata la locatia respectiva de iesire din aceasta tranzitie (culoarea marcherilor).

Culori si functii de colorare

In reteau RPC1 din Fig 2.2c functia identitate de colorare, notata “Id” este asociata la toate arcele unei tranziii in raport la o anumita culoare corespunde simplu de a retrage un marcher de aceeasi culoare din locatia de intrare si de a depune un marcher de aceeasi culoare in locatia de iesire. Acest fapt in Fig 2.2b este redat in mod implicit. In alte exemple care vor fi prezentate in continuare, vom folosi aceeasi notatie conventionala, adica daca functia de colorare asociata la un arc este o functie identitate, atunci se poate omite aceasta scriere.

Astfel noi am prezentat un exemplu simplu de functie de colorare cum este functia identitate Id, insa este posibil de asemenea de a defini functii de colorare mai complexe. De exemplu daca vom observa starea locala a unui element PE, constatam urmatoarea similitudine: indata ce un element PE este defectat, el va fi reparat si va trece in starea activa de buna functionare. Deci are loc o alternativa de diferite doua stari locale considerate. De asemenea aceste stari locale pot fi reprezentate si printr-o singura locatie pa (Fig 2.3), de exemplu pentru elementul PE1 (redata de reteaua RP din Fig 2.1a) asocind doua culori suplimentare b si d cu aceasta locatie, pentru a deosebi astfel starea de buna functionare de starea element PE1 – defectat. Multimea de culori { b, d } este asociata la tranzitia ta , pentru a deosebi tranzitiile t1a si t2a dupa contopirea lor intr-o singura tranzitie ta. Astfel dupa declansarea tranzitiei ta are loc schimbarea culorii marcherului b in culoarea d, pentru a exprima faptul ca elementul PE1, fiind in starea de buna functionare b, va trece in starea defectata d. Aceasta inseamna ca declansarea tranzitiei ta, in raport cu culoarea b, consta in a scoate un marcher de culoarea b din locatia de intrare pa si de a adauga un marcher de culoarea d in locatia de iesire, care de asemenea este aceeasi locatie pa. In mod analog are loc schimbarea culorii d in b. Aceasta transformare de culori este modelata printr-o functie de colorare f, care determina ponderile arcului ce leaga tranzita ta cu locatia pa. Aceasta functie este astfel incat f(b)=d si f(d)=b. In fig.2.3 este reprezentata evolutia marcajului retelei RPC respective.

In cazul exemplului studiat observam ca putem construi o retea RPC folosind doua modalitati diferite: colorarea in raport cu doua elemente PE diferite sau colorarea in raport cu sensul starilor locale. De asemenea, pot fi folosite concomitent aceste doua modalitati, pentru a construi o retea RPC structura grafica care se identifica cu cea din fig.2.3 insa care se deosebeste prin faptul ca ea va descrie functionarea simultana a doua elemente PE1 si PE2. In acest caz, pentru a descrie in aceeasi locatie p1 sensul schimbarii locale si tipul de elementul PE , este necesar de a defini culori complexe compuse din doua culori simple. De exemplu, cuplul <b, r> in locatia p1 indica faptul ca elementul PE2 se afla in stare de buna functionare. Asadar vom asocia la locatia p1 si la tranzactia t1 multimea de culori CL={<b, r>,<d, r>,<d, r>}. Aceste patru culori reprezinta diferite stari ale sistemului considerat. Functia de colorare f modeleaza in acelasi timp schimbarea sensului de stari, astfel incat:

f(<b,r>)=<d,r> , f(<d,r>)=<b,r>;

f(<b,a>)=<d,a> , f(<d,a>)=<b,a>

Aceasta functie transforma informatiile tip b si d si in acelasi timp va conserva informatiile tip a si r.

In Fig 2.4 este reprezentata reteaua RPC3, asociata celor doua elemente diferite PE1 si PE2 unde colorarea este efectuata concomitent in raport cu tipul starii locale si cu tipul de element PE.

In caz general, intr-o retea RPC o culoare se prezinta printr-un n-uplu Ck=<ck1, ck2,…, ckn>. Acest n-uplu este necesar in cazul cand un marcher trebuie sa reprezinte o informatie complexa. De exemplu, intr-un sistem distribuit cu asteptare, tripletul <e, j, k> poate reprezenta urmatoarele trei elemente: e – natura unei cereri, j – pozitia sa in sirul de asteptare si k – server-ul unde trebuie sa fie deservita aceasta cerere. Functiile de colorare asociate cu arcele retelei, pot fi arbitrare, in particular, imaginea unei culori simple poate fi o combinatie liniare de culori simple sau complexe.

Informatia ce este in reteaua RPC1 din Fig 2.2c este identica acelei ce contine reteaua RPC3 din Fig 2.4.

Trecerea de la o retea RP ordinara la o retea RPC corespunde efectuarii unei operatii de infasurare. Operatiei inverse ii corespunde o desfasuratoare a unei retele RPC intr-o retea RP ordinara. In Fig.2.5 este reprezentat un astfel de exemplu. O retea RPC este generala in structura sa si ea permite de a avea o mare coincizie in ce consta informatia despre starile locale ale componentelor sistemului modelat.

In unele cazuri putem avea nevoie de a nu deosebi marcherii intre ei, atunci se va folosi o culoare neutra notata <>. Reteaua RPC4 din Fig.2.5 reprezinta partajarea a doua resurse identice intre doi consumatori a si b. Fiecare RPC4 corespunde urmatorului caz: o alta resursa este disponibila, iar o alta resursa este utilizata de catre consumator. In Fig.2.5b este reprezentata o retea RP ordinara, ce este echivalenta cu reteaua RPC4, obtinuta prin desfasurarea acestei retele colorate.

Definitia unei retele Petri colorate

Definitie: O retea Petri colorata, abreviat RPC, este un 6-uplu

RPC=<P,T; Pre, Post, Mo, C> (3.2)

unde:

P – este multimea nevida a locatiilor;

T – este multimea nevida a tranzitiilor, astfel incat PT= si

C={c1, c2, …} este multimea finita nevida de culori definite de o functie de colorare asupra reuniunii a doua multimi P si T :

– Pre (respectiv Post) este o aplicatie de incidenta inainte (respectiv inapoi) definita pe PT, astfel incat Pre(p, t) apartine [C(t) [C(p) N*]] pentru toate perechile de arce (p, t), ce apartin PT.

– Mo : P N* este marcajul initial ce determina o functie de marcare definita pe multimea locatiilor P, astfel incat Mo(p) apartine [C(p)N*] pentru pP. Aici [AB] denota multimea functiilor de la A catre multimea B, iar N* este multimea numerelor intregi negative.

Astfel o retea Petri colorata difera de o retea Petri obisnuita prin adaugarea unui ansamblu de culori asociate cu locatiile si tranzactiile retelei RPC. O culoare Ck=<ck1, ck2, … , ckn> poate fi notata in mod global Ck, fie redata de catre un n-uplu, care o defineste.

In reprezentarea sa grafica, o retea RPC ca orice retea RP, contine doua tipuri de noduri: locatii si tranzitii, ce sunt respectiv conectate de catre arce orientate.

O locatie a unei retele RPC cum si pentru o retea RP, este reprezentata de un cerculet. Ea poate contine marcheri colorati, unde mai multi marcheri de aceeasi culoare pot sa se afle in aceeasi locatie cum, de exemplu este cazul pentru o subretea RPC din Fig.2.6. In aceasta figura locatia p1 a subretelei RPC contine 5 marchei <b>, 3 marcheri <v> si 2 marcheri <o>.

Deci marcajul unei retelei RPC este un vector, in care fiecare componenta este o suma ponderata de marchari colorati. Astfel, pentru reteaua RPC din Fig.2.6 avem urmatorul marcaj initial:

O tranzitie este reprezentata de catre o bara. La fiecare tranzitie este asociat un ansamblu de culori, unde fiecare din aceste culori indica o posibilitate distincta de declansare a tranzitiei considerate. Asa de exemplu, tranzitia t1 a retelei RPC5 din Fig.2.6 poate fi declansata relativ la culoarea <b>, la culoarea <v> sau la culoarea <o>, daca aceasta tranzitie este sensibilizata de catre marcajul curent.

Un arc orientat leaga o locatie cu o tranzitie sau o tranzitie cu o locatie. Ponderea unui arc este o functie Pre sau Post care stabileste o corespondenta univoca intre fiecare culoare a tranzitiei si culorile locatiei respective •t sau t• (locatia de intrare sau iesire conform sensului arcului). In raport cu retele RP obisnuite, functiile Pre si Post ale unei retele RPC vor avea un atribut suplimentar care este culoarea Ck de declansare a tranzitiei tj. Astfel , functiile Pre(pi, tj, Ck) si Post (pi, tj, Ck), corepund in caz general unei combinatii liniare de culori ale marcherilor relativ la locatia pi. De exemplu pentru reteaua RPC5 din Fig 2.5 avem:

Pre(pi, tj, <v>) = f(<v>) = 3<h>+<v>

Cum si pentru o retea RP obisnuita pentru o retea RPC se defineste o matrice de incidenta Wc. Elementul Wc(i,j) al acestei matrice este egal cu diferenta a doua functii de incidenta Post(pi, tj) si Pre(pi, tj).

De exemplu matricea de incidenta a retelei RPC4 din Fig 2.5 este:

t1 t2

In rezultatul declansarii unei tranzitii relativ la o culoare in retea poate avea loc o transformare de culori. Astfel declansarea tranzitiei t1 relativ la culoarea <v> va retrage din locatia p1 respectiv 3 marcheri de culoarea <b> si un marcher de culoarea <v> si va adauga cate un marcher de culoarea <o> si <v> in locatie p1.

Evolutia marcajelor

Marcajul M(pi) al unei laocatii pi reprezinta numarul de marcheri de fiecare culoare ce ii contine locatia pi. Marcajul initial al retelei RPC5 din Fig.2.6 este redat de marcajul locatiilor p1 si p2 adica M(p1) = 5<b>+3<v>+2<o> si M(p2) = 0. Suma simbolica a marcajului M(p1) inseamna ca acest marcaj este compus din cinci marcheri de culoarea <b> trei marcheri de culoare <v> si doi marcheri de culoare <o>.

Tranzitie validata. Fie C(tj) ansamblul de culori asociate la tranzitia tj. Aceasta tranzitie poate fi declansata relativ la oricare din aceste culori . Fie Ck o culoare oarecare din C(tj) si M un marcaj curent al retelei RPC. Tranzitia tj este validata adica sensibilizata in raport cu culoarea Ck pentru marcajul curent M, daca si numai daca numarul de marcheri de culoare respectiva, ce contine orice locatie la intrarea acestei tranzitii tj este supeior sau egal cu Pre(pi, tj, Ck) adica:

M(pi)

Aceasta relatie va fi notata M[ti, Ck > si ea determina preconditia de declansare a tranzactiei tj relative la culoarea Ck . Marimea este imaginea culorii Ck in functia de ponderea arcului ce leaga locatia pi cu tranzitia tj in aceasta retea Petri colorata.

Asa de exemplu in Fig 2.6 tranzitia t1 este validate relative la culoarea <b> fiindca f(<b>) = 2<v> si locatia p1 contine cinci marcheri de culoarea <v> si deci sunt suficienti numai doi marcheri de aceasta culoare pentru a declansa aceasta tranzitie adica si ca urmare avem . Aceasta tranzitie de asemenea este validata in raport cu culoarea <o>, fiindca pentru aceasta este necesar de cate un marcher de culoarea <b> si trei marcheri de culoarea <o>, iar locatia p1 nu contine decat doi marcheri de culoarea <o>.

Declansarea unei tranzitii validate. Astfel o tranzitie tj a unei retele RPC, validate de marcajul curent M in raport cu o culoare Ck poate fi declansata. Declansarea acestei tranzitii care va fi notata tj, Ck consta in a efectua simultan urmatoarele doua operatii:

1) se va retrage din orice locatie pi de intrare in tranzitie tj ( ) un numar de marcheri egal cu ;

2) se va adauga in toate locatiile pi de iesire din tranzitia tj () un numar de marcheri egal cu

Fie M’ marcajul obtinut dupa declansarea tranzitiei tj in raport cu culoarea Ck ceea ce va fi notat M[tj.Ck > M’. Acest marcaj este dedus din marcajul curent M, redat de urmatoarea relatie:

In cazul retelei RPC din Fig 2.6 observam faptul ca tranzitia t1 fiind validata de catre marcajul Mo in raport cu culoarea <b> poate fi declansata relative la aceasta culoare <b>. Aceasta declansare consta, pe de o parte de a retrage doi marcheri de culoarea <v> din locatie p1 fiindca f(<b>) = 2<v> si pe de alta parte de a adauga un marcher de culoarea <b> in locatie p2 fiindca g(<b>) = <b>.

Astfel idea de baza care este folosita in retele RPC la schimbarea marcajelor, consta in faptul ca indata ce o tranzitie este declansata relative la o culoare data, anume aceasta culoare si va fixa regurile de declansare. Toate imaginile functiilor de colorare ce sunt associate fie la un arc ce intra, fie la un arc ce iese din aceasta tranzitie, sunt calculate relative la aceasta culoare.

Deci toate definitiile redate mai inaite sunt similare celor ale retelelor RP necoloarte si reiese ca toate aceste proprietati pot fi generalizate si pentru retele Petri colorate.

Proprietatile unei retele Petri colorate

Indata ce o retea RPC a fost deja constituita este posibil de a valida specificarile pe care ea le reprezinta. Cum s-a si aratat mai inainte, o retea RPC nu este decat o reprezentare cu un grafism condensate al unei retele RP obisnuite, obtinuta prin desfasurarea acestei retele RPC. De aici reiese ca proprietatile retelelor RPC sunt aceleasi ca si cele ale retelelor RP necolorate, insa deseori ele se prezinta in mod diferit. In continuare vom revedea principalele notiuni si proprietati ale retelelor Petri colorate. Pentru aceasta mai intai vom introduce notiunea de secventa admisibila de declansare intr-o retea RPC.

Astfel declansarea unei tranzitii t1 relativ la o culoare Ch1 (notata cu t1.Ch1) dintr-un marcaj M1 da un marcaj nou M2. Conform notatiei obtinute in [83] putem nota acest fapt astfel: M1[t1, Ch1 >M2, fiindca acum t1.Ch1 are acelasi rol ca tranzitia t1 in reteaua RP necolarata. Acest nou marcaj M2 de asemenea poate valida o tranzitie t2.Ch1 , declasari = t1.Ch1 , … , tk.Chk ale tranzitiilor respective, in rezultatul carora se obtine un marcaj Mk+1 accesibil din M1 adica M1[ >Mk+1. Marcajul Mk+1 astfel obtinut este calculat conform urmatoarei expresii:

Astfel pentru reteaua RPC6 din Fig.2.7, secventa admissibila de declansare 1 = t1.C1 t2.C1 t2.C2 este o secevnta de declansari repetitive, fiindca ea poate fi declansata de o infinitate de ori si la fiecare declansare a sa duce la marcajul initial. Seceventa de declansari 2 = t1.C1 t2.C2 a acestei retele de asemenea este o secventa de declansari repetitive.

Secventa de declansari 1 contine o declansare a tranzitiei t1 relativ la culoarea C1 si adoua declansari ale tranzitiei t2 relativ la culoarea C1 si C2. De aici putem deduce ca vectorul characteristic 1 al acestei secvente de declasari este:

In mod similar cum si o retea RP necoloarata , marcajul Mk accesibil din marcajul Mi printr-o secventa de declansari pentru o retea RPC s-a obtinut ecuatia fundamentala: .

Definitia 2.2. Multimea marcajelor accesibile din marcajul initial Mo ale retelei RPC, este definita ca multimea tuturor marcajelor { Mi }, pentru care exista cel putin o secventa admisibila de declansari i , incepand cu marcajul Mi:

Definitia 2.3. Graful de marcaje accesibile ale retelei RPC din marcajul initial Mo, (notat GA(RPC,Mo) = ( Acc( RPC, Mo).U) ), este un graf orientat, etichetat astfel, incat Acc(RPC, Mo) constituie multimea varfurilor, iar U este multimea arcelor (Mi , Mj), definite prin relatia:

Arcele grafului de marcaje accesibil din marcajul initial Mo al retelei RPC sunt etichetate cu tranzitiile respective, declansarea carora la culoarea data permite schimbarea marcajului curent M al retelei RPC.

Astfel, pentru reteaua RPC1 din Fig.2.1 gaful sau de marcaje accesibile GA(RPCI, Mo) este prezentat in Fig.2.8.

Acelasi graf GA(RPCI,Mo) poate fi redat si in forma de urmatoarea lista:

Fig2.9 Graful de marcaje accesibile ale retelei RPC1 în forma de lista

Pentru reteaua RPC6 din Fig 2.7 obtinem urmatorul graf GA(RPC6,M0):

Definitiile considerate mai inainte pentru retelele RPC sunt similare cu cele ale retelelor RP necolorate [10,49]. De aici reiese ca toate proprietatile sale care au fost definite si considerate in [83] pentru retele RP necolorate, sunt direct generalizabile si pentru retelele RPC. Aceste consideratii sunt relatate in continuare pentru unele din proprietatile retelei RPC.

Reteaua marginita

In acest caz generalizarea este evidenta. O retea RPC este marginita daca pentru orice marcaj accesibil toate locatiile contin un numar finit de marcheri. De asemenea, putem vorbi despre o retea RPC sigura daca eventual vom defini aceasta retea ca o infasurare a unei RP necolorate, care este o retea sigura. O retea RPC sigura este o astfel de retea, in orice locatie care are, cel mult un marcher de culoare.

Viabilitate si blocaj

O retea RPC este viabila daca reteaua sa RP desfasurata este viabila, ceea ce inseamna ca pentru orice marcaj accesibil este posibil declansarea oricarei tranzitii relative la oricare din culoarile sale de declansare. O retea RPC este considerata fara blocaj, atunci cand pentru orice marcaj accesibil exista cel putin o tranzitie declansabila relativ la cel putin una din culoarile sale.

Conflict

Generalizarea notiunii de conflict intr-o retea RPC este putin delicata. Considerand conflictele structurale, generalizarea conflictelor effective este usor de efectuat: de exemplu intr-o retea RP necolorata are loc un conflict structural intre doua tranzitii ti si tj daca locatia pk este o locatie comuna de intrare la ti si tj adica pk={ti, tj}. intr-o retea RPC conflictul are loc intre doua cupluri (tranzitie, culoare), de exemplu: pk* ={ti.cn, ti.ck}. tranzitiile ti si tj eventual pot fi aceleasi tranzitii (cu cn ck) sau culorile cn si ck, eventual pot avea aceeasi culoare (ti tj). De exemplu in Fig.2.5a in reteaua RPC4 are loc un conflict efectiv , care poate fi regasit si in Fig.2.5b pentru reteaua RP necolorate.

Invariante de marcaje

Intr-o retea RP necolorata un vector – coloana T care verifica sistemul de ecuatii ∙Wc= 0, este un vector de numere intregi negative. Insa intr-o retea RPC componentele P – semifluxul (redate de vectorul-coloana T), sunt functii, deoarece matricea de incidenta Wc la randul sau este o matrice de funcitii colorate. Solutionarea sistemului de ecuatii ∙Wc = 0 este o problema dificila. Metodele de solutionare a acestui sistem de ecuatii exista in literatura [10,83]. Noi nu vom da aici decat solutiile direct obtinute.

Astfel de exemplu pentru reteaua RPC4 din Fig 2.5a, mai intai observam ca functia de culoare f, care apare in aceasta retea, este o functie de decolorare matricea de incidenta a care este:

Un P–semiflux al acestei retele este vectorul–linie =(Id, Dec), cu ajutorul caruia deducem un P–invariant de marcaj al locatiilor, redat de catre relatia ∙M=∙M0. Pentru acest caz obtinem:

Astfel consideram ca in reteaua RPC4 poate avea loc o schimbare de culoare a marcherilor, adica marcherul de culoare <a> este schimbat intr-un marcher de culoare <>. Acest P–invariant ne indica faptul ca in ansamblul de locatii p1 si p2 ale retelei RPC4 exista exact doi marcheri.

Invariante de declansari

Un T–invariant de declansari ale tranzitiilor intr-o retea RPC este un vector–linie de T–semifluxuri, componentele carora sunt niste functii si el verifica sistemul de ecuatii: . Pentru aceeasi retea RPC4 din Fig 2.5a obtinem un T–semiflux: . Acestui vector caracteristic ii corespund doua secevente de declansari admisibile sau . Declansarea tranzitiilor t1 si t2 in raport cu aceeasi culoare din marcajul initial M0 duce la marcajul M0. Secvenetele de declansari admisibile 1 si 2 sunt niste secevente repetitive.

Analiza proprietatilor de functionare

Cum s-a relatat on partea I a acestei lucrari [83], exista patru mari clase de metode pentru analiza proprietatilor unei retele RP necolorate. Este lesne de inteles ca aceste metode pot fi folosite si pentru analiza retelelor RP necolorate, obtinute prin desfasurarea retelelor RPC considerate, insa aceasta abordare deseori poate duce la retele RP de o mare dimensiune. Deci unele metode considerate in [10, 49] pot fi generalizate si pentru retele RPC.

Construirea grafului de marcaje accesibile ale retelei RPC este posbila, insa in caz general acest lucru este dificil de efectuat si deci nerealist, deoarece talia grafului pe care el o atinge este destul de mare.

Metodele de reducere a retelei RPC ce nu schimba unele proprietati de comportare necesita determinarea proprietatilor forte pentru functiile de colorare, care intervin in reteaua RPC. Insa in caz general ele sunt putin aplicabile.

Utilizarea metodelor algebrei liniare, cum s-a demonstrat mai inainte, este posibila, insa folosirea lor este foarte complicata. Astfel cautarea sistematica a proprietatilor retelei RPC este foarte dificila. Insa verificarea proprietatilor care se stie ca trebuie sa existe este cu mult mai usoara. Incepand cu aceste specificari se poate, de exemplu, gasi in mod intuitiv invariantele de marcaj [49, 83]. Verificarea faptului ca aceste invariante intr-adevar exista si permite validarea descrierii sistemului.

Modelarea proceselor de calcul prin retele Petri colorate

La modelarea sistemelor de calcul prin retele Petri RPC este necesar de a preciza principalele elemente de constituire a unei retele RPC. Ne putem usor da seama ca la constituirea unui model de retea RPC s-ar putea considera mai multe nivele de colorare. Natural apare urmatoarea intrebare: pana la ce nivel de colorare putem merge? Cazul extrem este colorarea totala a locatiilor si a tranzitiilor unei retele RP ordinare, asa cum este aratat in Fig 2.11.

Reteaua RPC7 astfel obtinuta contine numai o singura locatie si numai o singura tranzitie, ce sunt conectate intre ele cu doua arce, unde locatia p rezulta din contopirea locatiilor pi, i=1,…,n si a tranzitiei t ce rezulta din contopirea tranzitiilor tj , j = 1, …, m. Multimea de culori asociata la locatia p intocmai este multimea locatiilor pi, adica , iar multimea de culori associate la tranzitia t este . Ponderile arcului de intrare la tranzitia t corepunzatoare functiei Pre a retelei RP, iar ponderile arcului de iesire din tranzitia i corespunde functiei Post a retelei RP. Marcajul initial al retelei RP astfel obtinute corespunde sumei tuturor marcherilor initiali, adica fiecare marcher al locatiei pi in retele RP necolorate corespunde unui marcher de culoarea <pi> in reteaua RPC. Astfel avem:

Exemplu 2.2. Reteaua RP ordinara din Fig 2.12a reprezinta un sistem format din doi consumatori, redati de locatiile respective p1 si p2 care partajeaza aceeasi resursa comuna din locatia p3. Colorarea totala a acestui model conduce la reteaua RPC8 din Fig 2.12b.

Este evident ca la modelarea unui sistem real cu ajutorul unei retele RPC nu se va folosi nici unul dintre cele doua cazuri limite: primul caz corespunde la o retea RP ordinara si alt doilea – la o retea RP total colorata. In mod general primul caz furnizeaza o retea de o talie important de mare. Concizia extrema a cazului doi reda o retea cu totul ilizibila: ea poarta un interes teoretic. De fapt interesul essential al unui model graphic, cum este reteaua RP, consta in a reprezenta in mod comod mecanismele de baza ale sistemelor cu evenimente discrete cum ar fi: concurenta, paralelismul si/sau sincronizarea lor. Pentru a conserva intr-un astfel de model avantajele unui formalism graphic, pastrand in acelasi timp o talie rezonabila este necesar de a gasi un compromis in colorarea retelei RPC cautate. Pentru aceasta noi vom prelua elementele de baza care intervin intr-o retea RPC, insa de data aceasta le vom caracteriza din punctul de vedere al modelarii.

Pentru a efectua o alegere rationala a culorilor intr-o retea, conform [70] putem folosi urmatoarea abordare:

1) alegerea care se da culorilor este arbitrara. Intr-o retea RPC totalmente colorata se poate da acelasi nume C1 concomitent la culoarea <t1> si la culoarea <p1> deoarece aceste doua culori nu sunt niciodata in acelasi ansamblu (intr-adevar, culoarea <t1> nu este o culoare de marcheri in locatia p, iar <p1> nu este o culoare de declansare a tranzitiei). Atunci in Fig 2.12 vom avea Pre(c1)=c3. Astfel von avea o retea RPC, numarul culorilor careia va fi max(n,m) in loc de a fi n+m. In caz general fie N(tj) numarul de culori ale marcherilor care pot fi in locatie pi. Numarul minimal de culori necesare pentru o retea RPC este max(N(t1), N(t2), …, N(p1), N(p2), …). In practica nu se va considera necesara minimizarea acestui numar, insa mai degraba conservarea cu fiecare culoare a unei semnificatii, care va facilita intelegerea functionarii sistemului astfel descris;

2) modelele in care marcherii sunt identificati sunt numite retele Petri de nivel inalt. O retea RP de nivel inalt, in care nu sunt niciodata doi marcheri identici, a fost introdusa in [43]. Fiecare marcher reprezinta un obiect identificat de catre o lista de attribute si deci este posibil de a urmari astfel in mod individual fiecare obiect, ceea ce da posibilitatea de a efectua o modelare mai precisa si mai rafinata, care este deseori utila pentru unele tipuri de aplicatii.

Intr-o retea RPC cum este definita in acest capitol, culorile respective pot fi alese in asa mod inact ele vor avea aceasta proprietate.

Alegerea culorilor

Intr-o retea RP ordinara marcherii unei aceeasi locatii nu se deosebesc intre ei, adica informatia relativa la un marcher este redusa de o locatie. Deci intr-o locatie data nu este posibil de a caracteriza decat un singur tip de obiecte de orice cantitate. Intr-o retea RPC informatia este redata de catre cuplul (locatie-culoarea marcherului). O culoare reprezinta o informatie, care permite distingerea a doua elemente diferite intre ele, de exemplu, doua task-uri distincte intre ele sau doua resurse distincte intre ele. Astfel in acest caz noi putem avea doua multimi de culori: Sa={<ai>}, care corespunde unei multimi de sarcini sau Rs={<ri>}, care corespunde unei multimi de resurse. Aceste culori sunt numite culori simple, fiindca ele sunt definite cu ajutorul unei singure componente. In continuare vom ilistra printr-un exemplu folosirea culorilor simple la constituirea unui model in forma de retea RPC.

Exemplu 2.3. Intr-un sistem de calcul cu multiprogramare sunt prelucrate pe doua nivele consecutive in mod ciclic la doua elemente PEi, (i=1,2) doua tipuri de pachete–cadre c1 si c2, care formeaza la fiecare element PEi cate un sir de asteptare la intrare. Toate pachetele–cadre sunt prelucrate de catre fiecare element PEi in mod alternativ: c1, c2, c1, c2, … . Se presupune ca initial toate pachetele–cadre n1 de tipul c1 si n2 de tipul c2 se afla in sirul de asteptare la intrarea elementului PE1.

Se cere de a elabora modelul retelei RPC respectiv, care va descrie logica interactiunii proceselor de functionare a acestui sistem. Pentru a efectua aceasta modelare vom determina starile locale ale fiecarui tip de cadru si ale fiecarui element de prelucrare PEj, j=1,2.

Fie Sj – starea locala, care indica daca cadrul respectiv se afla in sirul de intrare la elementul PEj, j=1,2 sau nu;

Li – indica starea locala a elementului PEj, respectiv este liber sau nu;

Oj – indica starea locala a elementului PEj, respectiv este alocat si prelucreaza cadrul respectiv sau nu.

Luand in consideratie logica schimbarii starilor locale ale procesului de prelucrare a cadrului respective, mai intai vom constitui formula descriptive FL1 care reda traseul acestui proces:

Aceasta formula FL1 descrie reteaua RP ordinara subiacenta retelei RPC cautate.

Reteaua RPC9 construita in baza formulei descriptive FL1, este reprezentata in Fig 2.13, unde culorile c1 si c2 respectiv sunt associate la cadrele de tipul 1 si tipul 2. In acest model este efectuata colorarea cadrelor si astfel multimea de culori {c1,c2} este asociata la toate locatiile si la toate tranzitiile retelei RPC9, unde semnificatia acestor tranzitii este urmatoarea:

tj – incarcarea elementului PEi;

t’j – eliberarea elementului PEj.

Multimea locatiilor S1, O1, S2 si O2 reprezinta starea fizica a sistemului, iar locatiile L1 si L2 exprima faptul ca un element PE este o resursa unica partajata intre mai multe cadre.

Functia culoare este o functie successor, notata Succ, astfel incat Succ(ci)=ck, unde k=(i+1) mod 2. Acesta functie reprezinta ordonarea cadrelor: este prelucrat cadrul de tipul c1, apoi cadrul de tipul c2 etc.

Marcajul initial M0 al acestui model exprima urmatoarea situatie:

1) M0(S1)=n1 <c1>+n2<c2>, adica in sirul de intrare al elementului PE1 initial sunt n1 cadre de tipul c1 si n2 cadre de tipul c2.

Arcele neetichetate ale retelei RPC9 au ca pondere functia culoare identitate Id (vezi reteaua de la Fig 2.5a). Initial un cadru tip c1, poate ocupa elementul PE1, fiindca tranzitia t1 este declansabila relative la culoarea c1 (doua locatii S1 si L1 contin fiecare cate un marcher tip c1). Declansarea tranzitiei t1 va retrage cate un marcher de tip c1 din fiecare locatie S1 si L1 si va depune un marcher de tipul c1 in locatia O1. In continuare, elementul PE1 este eliberat, ceea ce corespunde declansarii tranzitiei t’1 in raport cu culoarea c1, care va depune in locatia L1 un marcher de culoarea Succ(c1)=c2, iar elementul PE1 este disponibil pentru cadrul tip c2. In acelasi timp un marcher tip c1 este depus in locatia S2. Astfel obtinem un nou marcaj, care va valida doua tranzitii:

1. tranzitia t1 in raport cu culoarea c2: incarcarea elementului PE1 de catre un cadru de tip c2;

2. tranzitia t2 in raport cu culoarea c1: incarcarea elementului PE2 de catre un cadru de tip c1;

Aceste doua declansari vor depune respectiv un marcher tip c2 in locatia c2 si un marcher tip c1 in locatia O2. In continuare, elementul PE2 este eliberat prin declansarea tranzitiei t’2 si cadrul de tip c1 revine in primul sir de asteptare, redat de catre locatia S1. In acelasi timp secventa de declansari =t’1.c2t2.c2t’2.c2 va elibera elemntul PE1 si va incarca elementul PE2 cu un cadru tip c2 pe urma il va elibera. Astfel cadrul de tip c2 va fi reintors in primul sir de asteptare.

Folosirea culorilor simple la constituirea unei retele RPC nu intotdeauna este o alegere dintre cele mai adecvate. De exemplu daca numarul de elemenete PE in sistem creste atunci modelul global devine foarte complex. Una din solutii consta in colorarea modelului de retea RPC din Fig 2.13 in raport cu elementele PE. Modelul in forma de retea RPC10 din Fig 2.14 descrie functionarea sistemului considerat in cazul colorarii retelei in raport cu tipul cadrelor si in raport cu tipul elementelor PE.

In reteaua RPC10 culoarea de baza <ci, ej> leaga un cadru tip ci la un element PEj de tipul ej. Un marcher de culoarea <ci, ej> in locatia S inseamna ca un cadru de tipul c2 se afla in sirul de intrare la elemental PEj. Un marcher de aceeasi culoare in locatia L inseamna ca elementul PEj este disponibil in asteptarea unui cadru de tipul ci. Functia Succ1 indica pentru un element PEj dat, ordinea in care cadrele respective sunt prelucrate de catre acest element. Aceasta functie indica faptul ca elemental PEj dupa prelucrarea cadrului tip c1 va urma un alt cadru tip c2, apoi va urma un cadru tip c1 etc. alteranandu-se astfel culorile cadrului respective. Este vorba de o functie successor (modulo(2)), aplicata la prima componenta <ci, ej>, adica:

.

Functia Succ2 corespunde gamei de prelucrare a cadrelor. Ea reda oridinea in care cadrul tip c1 va fi prelucrat de catre cele doua elemente PEi, i = 1,2. Aceasta functie de asemenea este o functie succesoare, insa aici incrementarea se face asupra componentei a doua a cuplului <ci, ej>:

Marcajul initial M0 are urmatoarea semnificatie:

1) M0(S) = n1<c1,e1> + n2<c2,e1> indica ca n1 cadre de tipul de tipul c1 si n2 cadre de tipul c2 sunt in primul sir de asteptare la intrarea elementului PE1;

2) M0(L) = n1<c1,e1> + <c2, e1> indica faptul ca elementele PE1 si PE2 sunt disponibile in asteptarea unui tip c1.

Functionarea retelei RPC10 din Fig 2.14 este identica cu functionarea retelei RPC9 din Fig 2.13 , fiindca grafurile de marcaje accesibile ale retelei RP ordinare respective obtinute prin desfasurarea retelei RPC9 si RPC10 sunt grafuri identice.

Observatia 1. Daca se doreste modelararea unui sistem ce prelucreaza un ansamblu de I tipuri de cadre pe J tipuri de elemente PE, atunci structura retelei RPC din Fig 2.14 ramane neschimbata. Este suficient de a introduce numai urmatoarele modificatii:

1) functiile Succ1 si Succ2 sunt definite respective ca modulo(I) si modulo(J);

2) marcajul initial M0(S)=<ci ,e1>, 1 i I corespunde ansamblului de cadre ce asteapta initial in primul sir;

3) marcajul initial M0(L)=<c1,ej>, 1 j J, indica faptul ca toate elementulele PEj sunt gata de a primi cate un cadru de tipul c1.

Exemplul 2.4. Vom considera un alt sistem, care este similar cu cel studiat in exemplul precedent, insa in cazul dat el este compus din trei elemente PEj (j = 1,2,3), fiecare avand la intrare sirul sau de asteptare. Acest sistem prelucreaza doua tipuri de cadre: c1 si c2. Setul de prelucrari ale unui cadru tip c1 corespunde prelucrarii lui mai intai la elementul PE1, apoi la elementul PE2, iar gama de prelucrarii ale unui cadru tip c2 corespunde prelucrarii lui mai intai la elementul PE1 apoi la elementul PE3. Elementul PE1 este o resursa partajata pentru care este impusa o ordine stricta de prelucrare in mod alternativ a diferitelor tipuri de cadre: cadre de tip c1, apoi cadrul de tip c2 etc. Sistemul dispune de n1 cadre tip c1 si n1 cadre de tip c2 . Initial toate aceste cadre se afla in sirul de asteptare la intrarea elementului PE1.

Folosind culorile <c1> si <c2> pentru a reprezenta tipul cadrelor si procedand in mod similar, cum s-a constituit si modelul retelei RPC9 din Fig 2.13, vom construi reteaua RPC respectiva, ce descrie functionarea acestui sistem. Pentru aceasta vom defini urmatoarele stari locale ale sistemului considerat:

Sj – starea locala de aflare a cadrului respective in sirul de asteptare la intrarea elementului PEj , j=1,2,3;

Lj – starea locala ca elementul PEj respectiv este liber;

Oj – starea locala ca elementul PEj este ocupat si prelucreaza cadrul respectiv;

Formula descriptiva FL3, care reda logica de schimbare a starilor traseului procesului de functionare al acestui sistem: FL3=FL1FL2, unde FL1 este formula descriptive ce descrie structura RPC9, iar formula FL2 este:

Formula descriptive FL2 descrie traseul prelucrarii unui cadru la elementul PE3.

Astfel imbinand structurile retelelor RPC9 si RPC, construita in baza formulei FL2, obtinem reteaua RPC11, reprezentata in Fig 2.15 ce descrie functionarea sistemului considerat. In acest model colorarea {c1, c2} este efectuata relativ la cadre. Semnificatia locatiilor acestei retele este aceeasi ca si pentru reteaua RPC9.

Astfel in reteaua RPC11 distingem 3 parti, fiecare reprezentand prelucrarea cadrului la elementul PE respectiv. Ansamblul de culori {<c1>,<c2>} este asociat la tranzitia t1, fiindca cadrele de tipul c1 si c2 sunt prelucrate la elementul PE1. La elementul PE2 (respectiv PE3) este asociat ansamblul {<c1>} (respectiv {<c3>}), deoarece numai cadre de tipul c1, sunt prelucrate la elementul PE2. Structura grafica a retelei este construita relativ la gama de cadre prelucrate iar ordonarea prelucrarii cadrelor la elementul PE1 este realizata de catre functia Succ.

La elementele PE1 si PE2 sunt prelucrate numai un singur tip de cadre deci la aceste elemente nu este necesar de a efectua o ordonare a cadrelor cum ea este efectuata pentru elementul PE1.

Daca la modelarea acestui sistem vom folosi colorarea retelei RPC obtinute in raport atat cu tipul cadrelor, cat si in raport cu tipul elementelor PE, atunci vom obtine reteaua RPC12, reprezentata in Fig 2.16, structura careia este identica cu a celei din Fig 2.14. Diferentele constau in ansamblurile de culori associate la tranzitii, in functiile de culoare associate la arcele respective si in marcajul initial.

Functia SET:

Functia ORDO:

Functii de colorare a retelei Petri

Cum deja s-a relatat in sectiunile precedente, functiile de colorare ale arcelor unei retele RPC realizeaza o transformare liniara de culori associate la o tranzitie. O functie arbitrara de colorare este definita calculand imaginea fiecarei culori a tranzitiei. Insa de asemenea o functie poate fi predefinita, de exemplu functia successor, care a fost folosita mai inaite. Experienta modelarii proceselor de prelucrare distribuita a datelor a demostrat ca exista un nucleu de functii de colorare elementare ce se intalnesc intr-o mare diversitate de modele-tip de retele RPC [70, 84]. Aceste functii de colorare pot interveni sub forma lor simpla, insa, de asemenea, este posibil de a construe functii noi prin compunerea intre ele a functiilor simple. Un set de astfel de functii predefinte este prezentat in tabelul de mai jos:

Functiile de colorare, care sunt prezentate in prima parte a tabelului au ca argument numai culori simple. Se poate de asemenea, de a defini si functii de colorare, argumentul carora este o culoare compusa, mai complexa. Asa de exemplu astfel de functii cum sunt functiile Succ1 si Succ2 folosite in tabelul de mai sus. In mod similar se vor defini si functiile Prec1 sau Prec2 ce corespund respectiv, la o decrementare a componentelor 1 sau 2. Deseori pentru o locatie data nu apare necesitatea de a avea toata informatia adusa de catre culoarea complexa. Se va utiliza atunci o functie de proiectie, care consta in suprimarea uneia sau a mai multor componente. De exemplu pentru cuplul de culori <ci, cj> se poate defini o protectie ce va suprima prima componenta, adica Proj1 (<ci,cj>)=<cj> sau alta protectie ce va suprima a doua componenta, adica Proj2 (<ci,cj>)=<ci> etc. Remarcam faptul ca functia de decoloarare este un caz particular al functiei de proiectie.

O functie de colorare, predefinita a unei retele RPC, corespunde unui grafic particular intr-o retea RP obisnuita, ce este obtinuta prin desfasurarea acestei retele RPC. In Fig 2.17 este ilustrata functia successor (Succ) si functia de decolorare (Dec).

Constatam pe aceasta figura o simetrie, care nu intotdeauna poate fi usor de observat in modelul global.

Extensii. Toate extensiile retelelor RP necolorate pot fi generalizate si retele RPC. Se pot obtine retele RP colorate temporizate, sincronizate, interpretate, stochastice [22,49,84,87]. Tot ce este asociat la o locatie intr-o retea RP necolorata este de asemenea asociat la un cuplu (locatie – culoarea marcherului) intr-o retea RPC de exemplu, o temporizare model Sifakis colorata. Tot ce este asociat la o tranzitie intr-o retea RP necolorata este asociat un cuplu (tranzitie – culoare de declansare) intr-o retea RPC, de exemplu o rata de declansare intr-o retea RP stochastica marckoviana. Descrierea unei retele RPC poate deveni putin greoaie, insa in general, nu se va intampla nici o dificultate la construirea acestui tip de retele.

Retele petri stochastice colorate

Retele petri markoviene colorate

In cele ce urmeaza noi vom defini retelele Petri markoviene colorate (RMC), obtinute prin extinderea retelelor Petri markoviene (RPM), studiate in [83]. Intr-un astfel de model sunt colorati marcherii, sunt colorate tranzitiile, precum si este colorata masura de probabilitate a duratei aleatorii de detasare a tranzitiilor retelei.

Retelele RMC permit de a simplifica considerabil modelul de baza, asociat procesului markovian si de a obtine repede si cu usurinta aceleasi rezultate ce pot fi obtinute cu ajutorul retelelor RPM.

Dupa o definire formala a unei RMC, a metodei de determinare a proceselor markoviene asociate lor, a metodei de construire a matricei dinamice colorate si a metodei de calcul a probabilitatii de stare colorata, vom exemplifica aplicarea retelelor RMC la modelarea si evaluarea performantelor unui sistem multiprocesor specializat.

Definirea unei retele markoviene colorate

Definitia 1. O retea Petri stochastica markoviana colorata, abreviat RMC, este cuplul:

RMC = < RPC, Q > (3.1)

unde RPC este o retea Petri colorata marcata, conform (2.2), iar Q este o masura de probabilitate definita de familia de probabilitati:

unde GA(RMC, M0) este graful de marcaje accesibile din marcajul initial M0 al retelei RMC, iar este o functie definita pe multimea numerelor reale pozitive R+ , astfel incat:

pentru orice valori reale τ de tip strict pozitive marimea

determina probabilitatea de declansare pentru prima data a tranzactiei th in raport cu culoarea ch din marcajul curent Mi , altfel aceasta probabilitate

este egala cu zero ;

pentru orice valori τ reale, egale cu zero pentru orice marcaj accesibil Mi din M0, de asemenea, are loc si relatia .

Definitia 3.2. Vom numi marimea rata de declansare a trazitiei th in raport cu culoarea ch din marcajul Mi determinata ca derivata finita, cand ea exista, a probabilitatii raporatata la τ:

Proprietatea 3.1. Masura de probabilitate Q, asociata retelei RMC poate fi definita de familia ratelor de declansare a tranzitiilor respective:

Pentru orice tranzitie th declansabila din marcajul curent Mi si pentru orice culoare ch, sunt verificate urmatoarele relatii:

si ca urmare .

Totdeauna este posibil de a construi o retea markoviana RPM, echivalenta oricarei retele RMC, obtinuta printr-o simpla “desfasurare” a culorilor asociate la locatii, la tranzitii si la ratele de declansare ale retelei RMC si invers, de asemenea, este posibil de a asocia oricarei retele RPM o retea RMC echivalenta prin “infasurarea” culorilor respective.

Pentru obtinerea unor rezultate cantitative se vor aplica metodele traditionale relatate in [83]; mai intai, ele constau in construirea grafului de marcaje accesibile GA(RMC, M0) al retelei RMC marcate si apoi a matricei dinamice A, asociate cu graful GA(RMC, M0).

Solutionarea sistemului de ecuatii:

permite de a determnina vectorul-linie al probabilitatii stationare de declasare in starile respective ale grafului GA(RMC, M0), cu ajutorul carora pot fi calculate unele rezultate cantitative necesare la evaluarea performantelor sistemelor de calcul, modelate prin acest tip de retele.

Construirea grafului de marcaje accesibile

O stare Mi a lantului Markov colorat (LMC) al grafului GA(RMC, M0) este o functie definita pe multimea locatiilor P ale retelei RMC, astfel incat pentru orice locatie p are loc relatia:

de o multime finita de culori C(Mi) este asociata starii (marcajului) Mi si corespunde diferitelor modalitati de a obtine la marcajul Mi.

Un arc ce uneste marcajele Mi si Mj este definit de catre triplul (th, h(Mi), fi,j), in care:

– th identifica tranzitia declansata

– h(Mi) desemneaza functia ratei de declansare, care apartine aplicatiei

– fij(ci)(cj) desemneaza functia de corespundere a culorilor intre starea de plecare si starea Mj de sosire.

Functia fij(ci)(cj) apartine aplicatiei si ea asociaza o culoare ch, ce apartine la C(th), la o culoare cj, apartinand la C(Mi) la o culoare cj, apartinand la C(Mj). Astfel, in exemplul reprezentat in Fig.3.1 declansarea tranzitiei th de culoare ch va scoate un numar NPRE(h) de marcheri de culoarea ci in locatia pi si va adauga un numar NPOST(h) de marcheri de culoare cj din locatia pj pentru orice locatie pi de intrare a tranzitiei th si pentru orice locatie pj de iesire din tranzitia th, unde:

NPRE(h)=Pre(pi .ci, th .ch) si NPOST(h)=Post(pi .ci, th .ch).

Astfel, graful GA(RMC, M0) determina un proces Markov, ce poate fi utilizat pentru studierea performantelor modelului considerat [83].

Matricea dinamica colorata

Matricea dinamica A, asociata unei retele RMC, este o matrice patrata de ordinul ce este egal cu numarul de marcaje accesibile ale GA(RMC, M0).

Matricea dinamica a unei retele RMC este A=(Ai,j), unde:

Ai,j apartine aplicatiilor , astfel incat:

unde

Remarca. Fie A o matrice dinamic6a, asociata unei retele RP markoviene RPM si echivalenta cu reteaua RMC. Matricea A, 6de asemenea, este o matrice a procesului Markov, determinata de catre graful GA(RMC, M0).

Astfel, avem A=Ai(k), j(k), unde i, j sunt indicii starilor, iar k, l sunt culorile acestor marcaje: k=ci, ce partine la ansamblul C(Mj):

unde .

Proprietatea 3.2. Intre doua matrici A si A au loc urmatoarele relatii: Ai,j=(A i(k),j(l))k,l;

Ai,j(k)(l)=A i(k),j(k),

ceea ce inseamna ca unui element al matricei A, a retelei RMC ii corespunde un bloc al matricei dinamice A a retelei RPM.

Probabilitati stationare de stare colorata

Propozitia 3.1. Fie data o retea RMC. Daca aceasta retea este o retea marginita, viabila si are un marcaj initial M0, ce este o stare interna de receptie, atunci procesul Markov determinat de graful GA(RMC, M0) poseda un regim stationar [45,83].

Consecinta: In regim stationar este posibil de a calcula vectorul-linie al probabilitatilor de stare i, solutionand sistemul de ecuatii tip Chapman-Kolmogorov:

unde =(i)i este un vector-linie, iar |||| este norma vectorului , obtinuta prin sumarea tuturor normelor componentelor acestui vector.

Astfel, avem .

Proprietatea 3.3. Pentru o retea RPM, asociata la reteaua RMC, este posibil de a gasi un vector-coloana al probabilitatilor stationare de stare in doua moduri echivalente:

desfasurand vectorul ,

rezolvand sistemul de ecuatii:

Probabilitatile de stare i in regim stationar permit de a calcula unele caracteristici de performanta, ale sistemului modelat de exemplu [2,45,83];

frecventa de declansare in regim stationar a tranzitiei th in raport cu culoarea ch;

numarul mediu de marcheri de culoarea ci in locatia piP;

durata medie de aflare in regim stationar a marcherilor de culoarea ci in locatia pi, calculata dupa formula lui Little colorata.

Frecventa medie de declansare in regim stationar a tranzitiei th in raport cu culoarea ch, ce apartine la C(th), este speranta matematica a ratelor de declansare a tranzitiilor respctive:

Numarul mediu de marcheri in regim stationar de culoare ci in locatia pi este determinat de urmatoarea relatie:

.

Formula lui Little colorata. Durata medie de aflare in regim stationr a unui marcher de culoare ci in locatia pi este egala cu produsul dintre durata medie, care separa evenimentele de sosire succesiva a doi marcheri de culoarea ci in locatia pi si numarul mediu de marcheri de culoarea ci, prezenti in locatia pi :

,

adica durata medie de aflare in locatia pi a unui marcher de culoarea cj este egalacu raportul dintre numarul mediu de marcheri de culoarea cj in aceasta locatie si suma ponderata (ponderata de catre ponderile arcelor de intrare) a frecventelor medii de declansare ale tranzitiilor de intrare la aceasta locatie.

In continuare, pentru a ilustra folosirea retelelor RMC la modelarea si evaluarea performantelor proceselor paralel in sisteme de calcul, vom considera, mai intai, un sistem multiprocesor specializat, apoi un protocol de gestiune a bazelor de date distribuite.

Modelarea unui sistem multiprocesor specializat

Sistemul multiprocesor specializat SMP pentru realizarea proceselor iterative de calcul este constituit dintr-un ansamblu de elemente de prelucrare PEi, i=1, …, n, dintr-un ansamblu de module-memorie de date MDi, i=1, …, n si de module-memorie de instructiuni MIi, i=1,…, n care sunt conectate in inel prin canale respective. Structura acestui sistem multiprocesor pentru cazul n=5 este reprezentata in Fig. 3.2.

Fiecare element PEi lucreaza in doua regimuri. In primul regim el va aloca concomitent ambele module adiacente MDi si MDi+1, folosindu-l pe cel din stanga pentru extragerea datelor initiale, necesar la efectuarea iteratiei curente, iar pe modului din dreapta MDi+1 – pentru citirea rezultatelor iteratiei precedente. Dupa terminarea prelucrarii iteratiei curente elementul PEi va memora in modului din dreapta MDi+1 rezultatelor obtinute si apoi va elibera ambele module alocate MDi si MDi+1. In al doilea regim elementul PEi va lucra cu datele sale interne. Regimul respectiv este indicat de catre instructiunea respectiva, care este citita de catre PEi din modului – memorie de instructiuni MIi.

Vom descrie functionarea acestui sistem multiprocesor, construind mai intai modelul in forma de retea RPM, apoi in forma de retea RMC.

Modelul de retea RPM

Pentru descrierea retelei RP, subiacente acestei retele RPM, vom proceda in acelasi mod cum s-a procedat si mai inainte, determinand astfel starile locale ale sistemului modelat si formula descriptiva FL, ce reda aceasta retea RP.

Fie ci este starea locala a elementului PEi, ce se afla in primul regim, iar ai este starea locala a elementului PEi , ce se afla in al doilea regim.

Fie, de asemenea, bi – stare locala a modulului memorie MDi, aflat in stare libera.

Formula descriptiva FL, ce determina logica interactiunii proceselor de functionare a PEi, i=1,…,n este urmatoarea :

unde k=(i+1) mod n .

Reteaua RMP5 redata de catre formula FL din (3.2) pentru cazul n=5, este reprezentata in Fig. 3.3.

Semnificatiile locatiilor si tranzitiilor retelei RPM5 sunt :

ai – elementul PEi in stare activa de prelucrare a datelor interne ;

bi – modului-memorie MDi este liber;

ci – elementul PEi este in stare activa de prelucrare a datelor iteratiei curente;

ti – alocarea concomitenta a resurselor bi si bk de catre elementul PEi si prelucrarea iteratiei curente ;

t`i – prelucrarea datelor interne de catre PEi si eliberarea resurselor bi si bk la terminarea activitatilor in al doilea regim.

Rata de declansare a tranzitiei tk (respectiv tranzitiei t`k) este marimea λi (respectiv μi), care este o rata limitata si independenta de marcajul curent pentru orice i=1,…,5.

Reteaua RP subiacenta RPM5 este o retea marginita, sigura, viabila si reinitializabila. Aceste proprietati sunt totdeauna valide, fiindca ele sunt determinate de catre cele zece P-invariante ale retelei RP. Intr-adevar, un element PEi poate sa se afle fie in starea locala ai, fie in starea locala ci si, ca urmare, cele cinci P-invariante ale retelei considerate sunt determinate in modul urmator :

(3.3)

De asemenea, un element PEi in acelasi moment de timp nu poate sa se afle ca si elementele PEi-1 si PEi+1, in stare activa de prelucrare a iteratiei curente. Deci avem cinci P-invariante, care sunt determinate de urmatoarele relatii :

(3.4)

unde k=(i+1) mod 5.

Din relatiile 3.3 si 3.4 determinam urmatoarea ecuatie:

(3.5)

unde k=(i+1) mod 5.

Astfel, din ecuatia 3.5 deducem faptul ca marcajele accesibile ale acestei retele Acc(RP, M0) pot fi determinate de catre marcajele M(ci) ale celor cinci locatii ci=1,…,5. Lista marcajelor accesibile ale retelei RPM5 este prezentata in Tab. 3.1.

Tabelul 3.1

Garful de marcaje accesibile GA(RP, M0) al retelei RP, subiacente retelei RPM5, este reprezentat in Fig. 3.4 sub forma de lista.

Lantul Markov LM5, ce descrie comportarea retelei Petri markoviene RPM5, este przentat in Fig. 3.5. Graful starilor acestui lant Markov este un graf conex, deci el este un lant Markov ergodic si, astfel, exista un regim stationar de functionare al sistemului multiprocesor SMP, modelat de catre reteaua RPM5.

Fig. 3.4 Graful de marcaje accesibile ale retelei RP subiacente retelei RPM5

Fig. 3.5 Lantul LM5 al retelei RPM5

Matricea dinamica A a lantului LM5 este prezentata in Tabe. 3.2.

Tabelul 3.2

In baza acestei matrice dinamice A sau scriind ecuatiile de echilibru local al fluxului de probabilitate in regim stationar pentru fiecare stare a lantului LM5, obtinem urmatorul sistem de ecuatii tip Chapman-Kolmogorov:

(3.6)

In rezultatul solutionarii sistemului de ecuatii 3.6 obtinem urmatoarea repartizare a probabilitatilor stationare de stare:

unde marimile ui, i=1,…,10 sunt redate de catre urmatoarele expresii analitice:

(3.7)

In expresiile analitice (3,7) sunt folosite urmatoarele notatii:

In cazul cand elementele de prelucrare PEj si modulele de memorare MDj sunt respectiv elemente si module identice, atunci ratele de declansare ale tranzitiilor respective sunt aceleasi, adica pentru tj avem: , iar pentru t`j avem: , pentru orice j=1, …,5.

In acest caz solutionarea sistemului de ecuatii (3.6) se simplifica cu mult. Ca rezultat obtinem urmatoarea expresie, ce reda repartizarea probabilitatilor stationare de stare respective:

unde .

Determinand repartizarea robabilitatilor stationare de stare , i=0,…,10 se pot evalua diferite caracteristici de performanta ale sistemului SMP, care au fost deja analizate in acest compartiment.

Modelul de retea RMC

Aceleasi rezultate pot fi obtinute si cu ajutorul unui model in forma de retea RMC, care poate determinat prin infasurarea retelei RPM5, introducand colorarea respectiva a locatiilor, tranzitiilor si a ratelor de declansare ale acxestor tranzitii.

Reteaua RMC2 – modelul acestui sistem multiprocesor specializat este reprezentat in Fig. 3.6. Fiecare element PEi de culoarea <ci>, i=1, …, 5 poate sa se afle in una din urmatoarele doua stari:

in stare de prelucrare a datelor interne, redata de locatia p1;

in stare activa de prlucrare a datelor iteratiei curente cu datele initiale din memoria MDi si rezultatul iteratiei precedente din memoria MDk, k=(i+1) mod 5 . Aceasta stare este redata de locatia p2.

Astfel, cinci locatii ci, i=1, …,5 ale retelei RPM5 sunt inlocuite cu o singura locatie p2 a retelei RMC2, care reda faptul ca elementul respectiv PEi se afla in stare de prelucrare a datelor interne. Cu aceasta locatie este asociata si multimea de culori C={<ci>, i=1, …, 5}.

Locatia p3 reprezinta multimea de resurse disponibile, adica cinci module de memorie MDi, ce sunt redate de catre culorile <bi>. Prin urmare, cu aceasta locatie este asociata multimea de culori B={<bi>, i=1, …, 5}. Pentru a fectua regimul de prelucrare a datelor iteratiei curente, elementul PEi va aloca concomitent modulului de memorie din stanga MDi si modulului de memorie din dreapta MDk, k=(i+1) mod 5. Acest fapt duce la necesitatea de a defini functia de colorare Res(<ci>)=<bi>+<bk>, unde k=(i+1) mod 5, i=1,…,5, care este folosita pentru reprezentarea operatiei de alocare si de restituire a resurselor MDi si MDk.

Fig. 3.6 Reteaua RMC2 – modelul sistemului multiprocesor din Fig. 3.2

Cinci tranzitii tj (respectiv t`j), j=1, …, 5 ale RPM5 sunt inlocuite cu o tranzitie colorata t1 (respectiv t2) a retelei RMC2.

Multimea de culori C={<c1>, <c2>, <c3>, <c4>, <c5>}, asociate la tranzitiile t1 si t2 ale retelei RMC2, este multimea de elemente PEi, iar sisunt ratele respective de declansare ale tranzitiilor t1 si t2 in raport cu culoarea <ci>, ea fiind asociata la elementul respectiv PEi. De exemplu, pentru ca elementul PE3 sa treaca din starea de prelucrare a datelor iteratiei curente in starea activa de rpelucrare a datelor interne determinata de instructiunea din modulul MIk, trebuie ca locatia p1 sa contina marcheri Res(<c3>)=<b3>+<b4>. Se poate atunci de declansat tranzitia t1 cu rata in raport cu culoarea <c3> etc.

Astfel, cu tranzitia t1 (respectiv cu tranzitia t2) este asociata multimea (respectiv ) ratelor (respectiv ), i=1,…,5 de declansare a tranzitiei validate in raport cu culoarea <ci>.

Matricea de incidenta a retelei RPC, subiacente retelei RMC2 din Fig.3.6 este:

marcajul initial M0 al retelei RMC2 este :

Aceatsa retea RMC2 este o retea marginita, viabila, reinitializabila si conservativa, fiindca sistemul de ecuatii poseda doua solutii simple, care da posibilitatea de a obtine P-semifluxurile respective :

si

care determina un support minimal de P-invariante. Cu ajutorul vectorului obtinem P-invariantul I1, care exprima conservarea numarului de elemente PEi in sistem :

Invariantul I1 este:

In acelasi mod, cu ajutorul vectorului obtinem si invariantul I2, care reda faptul conservarii numarului de resurse MDi in sistem.

Invariantul I2 este :

Analizand al doilea invariant, putem constata faptul ca doua elemente PEi si PEi+1, nu pot efectua concomitent prelucrarea datelor a doua iteratii curente. Inr-adevar, sa presupunem ca marcajul curent este M(p2)=<c2> + <c3> atunci :

Res(M(p2))=Res(<c2>)+Res(<c3>)=<b2>+<b3>+<b3>+<b4>,

Care inseamna ca

Res(M(p2))=<b2>+2<b3>+<b4>.

Insa aceasta ultima relatie este imposibila, tinand cont de invariantul I2.

Graful de marcaje colorate accesibile si lantul markov colorat LMC1 al retelei RMC2 sunt reprezentate in Fig 3.7. Starile lantului LMC1 ale acestei retele constituie urmatoarele trei marcaje colorate :

pentru

sau

Fig. 3.7. Lantul LMC1 al retelei RMC5

Multimea de culori C1={<ci>, i=1, …, 5} este asociata cu marcajul M1c, iar multimea de culori C2={<ci>+<cj>}, i=1, …, 5 j=(i+2) mod 5 sau

j=(i+3) mod 5 este asociata cu marcajul M2c.

Acelasi graf al LMC1 poate fi obtinut si prin colorarea lantului LM din Fig. 3.5.

Astfel, cinci stari Mi, i=1, …,5 ale LM din Fig. 3.5 vor fi infasurate in starea colorata M2c, care poate fi accesibila prin zece cai diferite ce corespund celor zece combinatii de activitate concomitenta de prelucrare a doua iteratii curente de catre doua elemente diferite PEi si PEj, ij.

Starea M0 a lantului LM coincide cu starea Moc a lantului LMC1, fiindca ea este unica stare de aceasta culoare.

Un arc al lantului LMC1 din Fig.3.7 este etichetat cu un triplu care indica faptul ca la declansarea tranzitiei colorate tk in raport cu culoarea respectiva c(tk), cu rata de declansare , asociata cu aceasta tranzitie, marcajul colorat curent Mxc se va schimba in alt marcaj colorat Myc, adica . Functia culoare fxy determina functia care leaga culorile starii colorate Mxc de iesire cu culorile respective ale starii colorate Myc prin declansarea tranzitiei th in raport cu culoarea c(th):

.

Construind astfel lantul LMC1, putem determina matricea dinamica colorata a retelei RMC2.

Matricea dinamica colorata

Fie si sunt doua multimi de culori, care sunt respectiv asociate cu starile Mxc si Myc ale LMC1 din Fig. 3.7. o submultime de elemente ale matricei dinamice A a RPM5 (cum este aratat in Fig. 3.2), ce este legata cu starile Mxc si Myc, consta :

dintr-o linie pentru fiecare element din ;

dintr-o coloana pentru fiecare element din .

Tabelul 3.3

Astfel, o submultime de elemente a matricei A corespunde unui element functional din , care determina pentru o retea RMC un element al matricei dinamice colorate A care este redata de o functie , unde:

Deci fiecare element al matricei dinamice colorate A1 a retelei RMC2 reprezinta o submultime echivalenta lui a matricei dinamice A a retelei RPM5. matricea dinamica colorata A1 este prezentata in Tab. 3.3.

Elementele matricei A1 au urmatoarele semnificatii:

Cum s-a mentionat mai inainte, reteaua RMC5 este o retea marginita viabila si reinitializabila, iar functiile ratelor de declansare sunt marimi finite. Ca urmare, conform [45,83], procesul markovian colorat are un regim stationar, iar vectorul-linie Π al probabilitatilor stationare de stare colorata Π=( Π0, Π1, Π2) este solutia urmatorului sistem de ecuatii :

(3.9)

unde Π0=π0, Π1=(π1, π2, π3, π4, π5), Π2=(π6, π7, π8, π9, π10).

Astfel, sistemul de ecuatii (3,9) da aceleasi ecuatii, care sunt prezentate de catre sistemul de ecuatii (3,6) pentru descrierea comportarii retelei RPM5. Acest exemplu de modelare si analiza a functionarii sistemulu multiprocesor specializat SMP demonstreaza faptul ca abordarea de retea RMC este echivalenta abordarii de retea RPM si ea are avantajul ca modelul in forma de retea RMC este modelul mai concis mai usor de inteles si de utilizat in aplicatiile de modelare. Generalizarea retelei RMC2 este evidenta, daca vom considera cazul unui sistem SMP cu n elemente PEi, i=1, …, n.

Mentionam ca reteaua RMC2, de asemenea, descrie in mod echivalent protocolul clasic de comportare a celor conci filozofi chinezi Fili, (i=1, …, 5), care se afla in jurul unei mese rotund, fiecare din ei dispunand de doua din cele cinci betisoare bi, (i=1, …,5), pentru a putea manca din farfuria lor personala [10, 38], astfel cum este reprezentat in Fig. 3.8. Un filozof poate avea doua stari distincte esentiale: el “mediteaza” sau el “mananca”. Pentru a manca el are nevoie de doua betisoare, ce se afla respectiv, in partea stanga si in partea dreapta a sa. In starea initiala se presupune ca toti filozofii sunt in starea de a medita si toate betisoarele sunt puse pe masa la locul lor.

Protocolul de comportare a celor cinci filozofi este urmatorul: daca un filozof doreste sa manance, el va lua concomotent cele doua betisoare din partea stanga si din partea dreapta, apoi el va incepe sa manance. Dupa ce termina de mancat, el va depune concomitent cele doua betisoare la locul lor pe masa.

Astfel, doi filozofi vecini nu pot sa manance in acelasi timp, fiindca un betisor va fi ocupat de vecinul sau.

Fig. 3.8. Schema protocolului celor 5 filozofi

Interpretarea retelei RMC2 din Fig.3.6 in raport cu descrierea protocolului de comportare a celor cinci filozofi este urmatoarea. Fiecare filozof Fili se afla in una din cele doua stari :

in stare de repaus, cand el mediteaza, redata de locatia colorata p1;

in starea de a manca, redata de locatia colorata p2.

Locatia p3 reprezinta ansamblul de resurse disponibile, adica cele cinci betisoare reprezentate de catre culorile <bi>, i=1, …, 5.

Functiile culoare Id si Res au acelasi sens.

Deci daca vom inlocui respectiv in RMC2 elementele PEi prin filozofi Fili, i=1, …, 5 si modulele-memorie MDi prin betisoare bi, vom obtine aceleasi caracteristici pentru descrierea protocolului comportarii celor cinci filozofi.

In particular, retelele RMC sunt folosite in acelasi mod ca si pentru retelele RPM la modelarea si analiza cantitativa a sistemelor de calcul. Totusi retelele RMC sunt mai bine adaptate la descrierea sistemelor de calcul distribuite si la evaluarea performantelor protocoalelor de comunicatie, de unde si reies avantajele sale de descriere concisa s de simplitate a acestor tipuri de metode.

Mai mult, abordarea calculului repartizarii probabilitatilor stationare de stare este dein timp structurata, iar folosirea rezultatelor astfel obtinute se inscriu intr-un demers traditional.

O extindere a retelelor Petri markoviene colorate consta in a efectua colorarea retelelor Petri markoviene generalizate [83], obtinand astfel modele semimarkoviene prin a considera doua tipuri de tranzitii colorate: tranzitii colorate immediate, ce modeleaza actiuni si/sau procese rapide si tranzitii colorate temporizate, ce modeleaza actiuni si/sau procese lente.

Bibliografie

Brams G.W. – Reseaux de Petri : Theorie et pratique. Paris : Edition Masson, 1983 [10]

Florin G., Natkin S. – Proprietes ergodiques de reseaux de Petri stochastiques // Rapport de recherche Cnam, fevrier, 1984 [22]

Kotov V.E. – Seti Petri, Moskva: NAUKA 1984 [38]

Murata T. – Petri nets: Proprietes, Analysis and Aplications // Proceding of the IEEE, vol. 77, no. 4, pp.541-580, 1989 [49]

Alla H., David R. – De Grafcet aux reseaux de Petri, Ed. Hermes, Paris, 1992 [70]

Gutuleac E. – Modelarea si evaluarea performantelor sistemelor de calcul prin retele Petri, Partea I, Ed. U.T.M., Chisinau, 1989 [83]

Gutuleac E. – Modelarea si evaluarea performantelor sistemelor de calcul prin retele Petri, Partea II, Ed. U.T.M., Chisinau, 1999 [83]

Jensen K. – Coloured Petri Nets and Invariant Method, Theoretical Computer Sciences, 1981, vol. 44, pp 317-337 [84]

Peterson J.L. – A Note on Coloured Nets, Inf. Process Letters, vol. 11, nr. 1, 1981, pp. 40-43