UNIVERSITATEA TEHNIC A MOLDOVEI

Emilian GUULEAC

Verificarea i evaluarea performanelor sistemelor concurente

Chiinu 2011

UNIVERSITATEA TEHNIC A MOLDOVEI

Facultatea Calculatoare, Informatic i MicroelectronicCatedra Calculatoare

Emilian GUULEAC

Verificarea i evaluarea performanelor sistemelor concurenteCiclu de prelegeri

Chiinu U.T.M. 2011

1

C.Z.U.: 004.03: 004.7 Ciclul de prelegeri este adresat studenilor ciclul II studii de masterat, specializrile 526.1 "Calculatoare" i 526.2 "Automatica i Informatica", Facultatea Calculatoare, Informatic i Microelectronic, UTM pentru a fi utilizat la studierea cursului " Verificarea i evaluarea performanelor sistemelor concurente". Lucrarea poate fi util doctoranzilor i specialitilor de cercetare, proiectare i exploatare a sistemelor concurente cu prelucrare distribuit a datelor. Este prezentat o parte din materialul teoretic predat n cadrul prelegerilor la disciplina menionat mai sus. Subiectele descrise conin aspecte teoretice i practice de modelare, verificare i evaluare a performanelor sistemelor concurente prin modele descriptivcompoziionale de reele Petri stochastice generalizate. Sunt definite formule descriptive i extensii de reele Petri concepute ca formalism de referin n aplicaii i tehnici de modelare a proceselor paralele de prelucrare distribuit a datelor, folosind produsele program instrumentale VPNP i VHPN.

Elaborare: conf. univ., dr. hab. Emilian GUULEAC Recenzent: prof. univ., dr. hab. Anatol POPESCU

Aprobat la edina Consiliului tiinific al Facultii Calculatoare, Informatic i Microelectronic din 16 februarie 2011 Redactor responsabil: conf. univ., dr. Victor ABABII

Procesare computerizat: conf. univ., dr. hab. Emilian GUULEAC

U.T.M., 2011

2

Cuprins Prefa Introducere

4 6

1. Aspecte de modelare a proceselor sistemelor concurente prin reele Petri 9 generalizate descriptiv-compoziionale 1.1. Aspecte arhitecturale i de analiz a proceselor de calcul concurente........... 9 1.2. Modelarea, verificarea i evaluarea performanelor ....... 11 1.3. Reele Petri generalizate............................................................................................. 14 1.4. Expresii descriptive ale reelelor Petri generalizate........................................... 23 2. Modelarea i evaluarea performanelor proceselor de calcul prin reele 35 Petri generalizate markoviene 2.1. Temporizarea stocastic a reelelor Petri ........... 35 2.2. Reele Petri generalizate markoviene ............. 37 2.3. Reele Petri generalizate markoviene extinse .......... 43 2.4. Modele cu automodificare ........................................................................................ 48 2.5. Algebra tensorial i compunera modelelor.......................................................... 52 3. Modelarea i evaluarea performanelor sistemelor multiprocessor................. 59 3.1. Aspecte arhitecturale de modelare.......................................................................... 59 3.2. Sistem multiprocesor cu o magistral i memorie comun.............. 61 3.3. Sistem multiprocesor cu magistrale i memorii comune multiple.................. 70

ConcluziiBibliografie Lista abrevierilor Anexe A.1. Produse program pentru simularea animat, verificarea funcional i evaluarea performanelor modelelor de reele Petri stocastice ...........

77 79 84 85 85

A1.1 Prezentarea produselor software............................................................................ 85 A1.2. Structur i formele interfeei grafice utilizator................................................ 87

3

PrefaSistemele de calcul i reelele de calculatoare cu aplicaii concurente sunt sisteme complexe formate dintr-o multitudine de componente elementare de tipuri diferite, interconectate dup o structur convenabil, avnd caracteristici proprii ce decurg att din constituia lor fizic, precum i din natura proceselor la care sunt supuse. Caracteristicile funcionale i de performan ale sistemului de elaborat sunt determinate printr-o activitate de modelare i verificare a contextului real n care urmeaz s funcioneze. Modelul de referin adoptat trebuie s captureze toate proprietile i caracteristicile viitorului sistem.Pentru abordarea problematicii specifice elaborrii sistemelor de calcul, s-a fcut apel la diverse procedee de formalizare, exploatndu-se o arie vast a matematicilor moderne. n acest context, un loc aparte n spaiul relativ neomogen al tratrii matematice a proceselor de calcul, l ocup formalismul reelelor Petri de diferite extensii. Stadiul actual de dezvoltare al formalismului reelelor Petri de diferite extensii permite investigaii att calitative, axate pe aspecte logice, ct i cantitative, axate pe aspecte temporale stochastice ale dinamicii sistemelor de calcul. Actualmente acest formalism ocup o arie att de mare nct este puin probabil de a o percepe integral, innd contul n mod deosebit de faptul c aceast teorie este n continu dezvoltare.

Lucrarea de fa i propune o descriere a conceptelor teoretice i realizrilor practice ale tehnicilor de modelare, verificare funcional i evaluare a performanelor sistemelor concurente prin modele descriptiv- compoziionale de reele Petri stocasice generalizate. n primul capitol sunt considerate unele aspecte de modelare a proceselor sistemelor de calcul cooperante prin reele Petri generalizate descriptiv-compoziionale. Este definit o clas de reele Petri generalizate etichetate (GeN) cu arce reversibile de cardinalitate marcajdependent i reguli de funcionare a acestora. n acelai context sunt considerate i unele aspecte de compunere a modelelor. Sunt formulate criterii de integrare n modele de reele GeN a proprietilor compoziionale, este introdus conceptul de expresii descriptive prin definirea unui set de operaii compoziionale, ntr-un spaiu de condiii-evenimente, care permite de a crea, dup anumite reguli, specificate de conceptor, modele de reele GeN ale proceselor de calcul. n acest context este elaborat o metod de creare a modelelor proceselor de calcul concurente, care permite de a formaliza etapa de trecere logic de la o descriere informal a arhitecturii i a specificaiilor comportamentale ale sistemului la determinarea unor expresii descriptive i maparea lor n modele de reele GeN ale acestor procese, subiacente modelelor de reele Petri stocastice. Unele aspecte de temporizare stocastic a reelelor GeN, n baza creia sunt definite modele de reele Petri markoviene generalizate extinse (RMG) cu regulile lor de funcionare, care dau 4

posibilitatea de a descrie concomitent att procese de calcul lente, ct i procese rapide de gestionare a logicii interaciunii acestora sunt abordate n Capitolul II. Modelele de reele RMG redau particularitile proceselor de calcul concurente i micoreaz considerabil spaiul de stri al lanurilor Markov timp continuu (LMTC) inclus, ceea ce a permis de a defini un set de caracteristici numerice de performan ale unui sistem de calcul, care pot fi evaluate n baza distribuiei probabilitilor de stare ale acestui lan. n acest context sunt prezentate dou modele, care descriu procesul de prelucrare a cererilor de procesare a datelor de ctre o unitate aritmetic-logic (ALU) a procesorului conform programului memorat n memoria central (MC). Cu scopul de a diminua complexitatea analizei modelelor RMG i a utiliza mai eficient spaiul de memorie la formarea matricei dinamice de o talie foarte mare este propus o metod de analiz prin compunerea sincron a subreelelor RMG constituente, efectuat de tranziiile care aparin diferitor subreele sincronizate. n Capitolul III sunt abordate unele aspecte arhitecturale, de modelare i evaluare a performanelor sistemelor de calcul multiprocesor cu resurse multiple prin reele RMG. Sunt descrise metode i tehnici de sintez formal a modelelor descriptiv-compoziionale de reele RMG ale unor arhitecturi de sisteme multiprocesor cu magistrale comune multiple i masive de procesoare, n baza crora a fost efectuat evaluarea performanelor acestor tipuri de sisteme. Lucrarea se adreseaz n primul rnd specialitilor de cercetare, proiectare i exploatare a sistemelor de calcul cu prelucrare distribuit a datelor, precum i studenilor din nvmntul tehnic superior de specialitate. Lucrarea, fiind una dintre primele n domeniul dat care abordeaz o astfel de problematic, este susceptibil de mbuntiri. Eventualele sugestii parvenite din partea cititorilor vor fi acceptate cu interes i recunotin. Autorul i exprim n acest mod sincera recunotin celor care m-au sprijinit n conceperea i realizarea acestei lucrri. Fiind, subordonate programului de nvmnt, noiunile i conceptele prezentate n aceast lucrare apar, n mod firesc, ntr-o succesiune logic i sunt supuse unor restricii temporale i de spaiu ce conduc adeseori la dezvoltri teoretice limitate. Lucrarea, care abordeaz o astfel de problematic, este susceptibil de a fi mbuntit. Eventualele sugestii parvenite din partea cititorilor vor fi acceptate cu interes i recunotin.

5

IntroducereSistemele de calcul concurente in timp real actuale cunosc o dezvoltare rapid, att sub aspectul complexitii sau performanelor, ct i a ariei de rspndire. Acest tip de sisteme prezint un grad ridicat de complexitate, datorit numeroaselor interaciuni dintre componentele acestuia, cum sunt: concurena, sincronizarea, partajarea resurselor, ateptare etc. Ca urmare, atunci cnd sunt procesate o nou aplicaie sau reconfigurri de calcul, care trebuie prelucrate urgent, n sistem apar conflicte ntre componente, blocri ale acestora, fenomene de ateptare i incertitudini de funcionare a sistemului. Verificarea i evaluarea performanelor sistemelor concurente constituie una din componentele importante ale activitilor de concepie, realizare i ntreinere, inclusiv i a sistemelor concurente cu aplicaii distribuite reconfigurabile. La nivelul activitilor de concepie i realizare, interesul verificrii i estimrii performanelor viitoare ale noilor sisteme concurente tinde s creasc n condiiile sporirii complexitii sistemelor de realizat i, implicit, a riscului de a obine produse insuficient adaptate destinaiei i cerinelor de performane specificate [20, 53]. Este bine cunoscut faptul c o eroare de concepie depistat la etapele de verificare formal a proprietilor comportamentale i/sau evaluare a cerinelor fa de performanele sistemului de realizat devine de circa 43 ori mai ieften, dect cea depistat dup realizarea acestui sistem [26]. Mai mult, peste 65% din reuita proiectului este condiionat de efectuarea cu succes a acestor etape. Caracteristicile de performan ale unui sistem de calcul: viteza de concurente, puterea de procesare, debitul traficului de date, fiabilitatea, tolerana la defecte, timpul de rspuns, etc. capt valori diferite n raport cu arhitectura sistemului i clasa de aplicaii prelucrate. ntr-un context tehnologic, aceasta este o expresie a caracteristicilor funcionale i topologico-spaiale ale sistemului, reprezint modalitatea de rezolvare a cerinelor de performan. Una din caracteristica de baz a SC este timpul de rspuns, care reflect perioada necesar sistemului pentru a genera un rspuns adecvat la un eveniment extern. Dintre cerinele de performan ce asigur Calitatea Serviciilor (eng. QoS Quality of Service) impuse acestor tip de sisteme se disting dou elemente, i anume: Viteza de reacie a la evenimentele din exterior Sistemul trebuie s asigure timpi de rspuns care s se ncadreze n limite posibile, de cele mai multe ori deosebit de severe. Sigurana n funcionare - Sistemul trebuie s aib o fiabilitate, disponibilitate i o securitate deosebit. De asemenea, trebuie s aib capacitatea de a evita situaiile critice i de a limita consecinele unor defeciuni grave. Dup o ntrerupere accidental sistemul trebuie repus ct mai repede n funciune.

6

Sistemele concurente actuale prezint un grad ridicat de complexitate, datorit numeroaselor interaciuni dintre componentele acestora, cum sunt: concurena, sincronizarea, partajarea resurselor, ateptare etc. Ca urmare a acestor interaciuni, atunci cnd sunt procesate o nou aplicaie sau reconfigurri de concurente, care trebuie prelucrate urgent, n sistem apar conflicte ntre componente, blocri ale acestora, incertitudini de funcionare. Problematica i amploarea efortului de cercetare, investit recent n domeniul evalurii performanelor sistemelor cu evenimente discrete i hibride, inclusiv i a sistemelor de concurente, este de larg notorietate, fiind reflectate de numeroasele articole pe aceast tem, publicate n cele mai prestigioase reviste de specialitate [4, 9,18, 23, 33, 40, 52, 62]. Totui, n pofida rezultatelor obinute, o problem major n analiza performanelor acestor tip de sisteme const n descrierea fenomenelor stocastice care reprezint defectarea i repararea componentelor, variaia timpurilor de prelucrare a aplicaiilor. n acest scop, pot fi utilizate tehnici de simulare a funcionrii sistemului [53, 56] sau metode analitice de analiz. Dezavantajul simulrii const n faptul c aceasta nu permite verificarea funcional, obinerea unor rezultate exacte i ea necesit mult timp. Metodele analitice de analiz a unui sistem de concurente sunt metode deductive, care permit obinerea rapid a soluiei problemei de modelare i evaluare a performanelor acestui sistem printr-un raionament pe baz de algoritm. Deopotriv este bine cunoscut faptul c direciile de cercetare din cadrul domeniului performanelor sistemelor de concurente s-au dezvoltat independent, n funcie de motivaia tiinifica a colectivelor ce au promovat respectivele direcii, bazate pe diferite abordri: (i) lanuri Markov timp continuu [14, 18], ns acestea pot fi folosite doar pentru modelarea unei clase restrnse de procese de concurente ce au un spaiu de stri mic, deoarece el poate fi construit numai n mod manual i apar probleme cu validarea acestor tipuri de modele; (ii) sistemele i reelele de ateptare sunt un formalism de un nivel mai nalt, ceea ce permite de a obine rezultate analitice n form multiplicativ cu anumite restricii. Acestea au fost folosite cu succes pentru modelarea i evaluarea performanelor unei clase restrnse de procese de concurente n cercetrile efectuate n lucrrile [53, 72] ns nici cu acest formalism nu se poate efectua compunerea submodelelor i nu pot fi descrise astfel de fenomene ale proceselor de concurente cum ar fi: sincronizarea, cooperarea, excluderea mutual, partajarea resurselor, mobilitatea, reconfigurabilitatea, etc.; (iii) algebre ale proceselor stocastice [27, 34], cu ajutorul crora poate fi efectuat compoziia (sub)modelelor i se pot descrie fenomenele proceselor de concurente menionate anterior, dar nici n cadrul acestui formalism nu poate fi descris mobilitatea, reconfigurabilitatea i nu se efectueaz n mod automat verificarea proprietilor comportamentale;

7

(iv) reelele Petri stocastice [2, 20, 28, 30, 36]) actualmente sunt recunoscute ca un puternic formalism de modelare a sistemelor cu evenimente discrete concurente i paralele, ns lipsa construciilor compoziionale, integrate n astfel de modele, face ca utilizarea lor s fie dificil i deseori nepotrivit la modelarea diverselor sisteme reale. Compunerea acestor tipuri de modele prin reele Petri plate devine mai degrab o art dect o activitate cotidian. La etapa actual de cunoatere, domeniului i lipsete un context unificator al manierelor de tratare i abia n ultimii ani s-a pus problema studierii compatibilitii dintre diversele abordri existente 4, 6, 23, 27, 72], integrarea proprietilor compoziionale din submodele ale componentelor constituente i descrierea particularitilor proceselor de concurente mobile i reconfigurabile. Mai mult, aceasta se resimte i prin prisma instrumentelor software la care fac apel colectivele angrenate n diverse direcii de cercetare la evaluarea performanelor proceselor discret-continue de concurente [48, 49, 65, 69]. Pentru abordarea problematicii specifice elaborrii sistemelor de concurente, s-a fcut apel la diverse procedee de formalizare, exploatndu-se o arie vast a matematicilor moderne. n acest context, un loc aparte n spaiul relativ neomogen al tratrii matematice a proceselor de concurente, l ocup formalismul reelelor Petri. Stadiul actual de dezvoltare al formalismului reelelor Petri de diferite extensii permite investigaii att calitative, axate pe aspecte logice, ct i cantitative, axate pe aspecte temporale stochastice ale dinamicii sistemelor de concurente. Interesul nostru s-a ndreptat nspre reele Petri stocastice (RPSG) [35] ca model de referin, deoarece acestea constituie un formalism grafic simplu i intuitiv de reprezentare a sistemelor cu evenimente discrete n care au loc fenomene de paralelism, de sincronizare, resurselor i restructurare n timp real. Pentru a efectua modelarea funcionrii sistemului distribuit cu aplicaii concurente i evaluarea indicatorilor de performan dinamic a acestuia prin reele RPSG este necesar de a lua n consideraie astfel de fenomene cum ar fi: competiia, sincronizarea, situaii de conflict, excludere mutual, ateptare i interdependena prilor hardware i software, deoarece defectarea unor componente ale prii hardware influeneaz direct starea de bun funcionare a aplicaiei software, care duce la rezultate incorecte. partajare a

8

1. Aspecte de modelare i verificare a sistemelor concurente prin reele Petri generalizate descriptiv-compoziionale1.1 Aspecte arhitecturale i de analiz a proceselor concurenteDezvoltarea tehnicilor de comunicaie, de procesare a informaiei i a microelectronicii sunt unii din factorii fundamentali ai progresului tehnologic actual i vor constitui i n continuare prghiile de baz pentru realizarea sistemelor de concurente i a reelelor de calculatoare tot mai performante, n care rularea aplicaiilor se face prin intermediul unor module cooperante de prelucrare distribuit a datelor. Un sistem de calcul cu aplicai concurente (SC) este constituit dintr-un ansamblu de componente funcionale fizice (hardware) procesoare, memorii private sau comune, magistrale comune, dispozitive periferice etc. i logice (software de baz) sistem de operare, programe utilitare, programe de gestiune a datelor, care interacioneaz n scopul satisfacerii unei diversiti de cerine, adesea contradictorii. Definiia sistemelor concurente prezentat n [56] este suficient de general pentru a acoperi multitudinea de variante arhitecturale cunoscute, rezultat al evoluiei contextului tehnologic i al cerinelor de performan i de utilizare ale acestora. Exist o strns legtur ntre arhitectura sistemelor de concurente, nivelul de performan i software-ul care urmeaz s-i pun n valoare caracteristicile funcionale. Pe baza disponibilitii tehnice i structurale ale acestor elemente i a combinaiilor arhitecturale dintre ele, se obine mulimea modelelor, imaginabile teoretic, ale sistemelor concurente. n realitate, doar o submulime destul de restrns este viabil sub aspectele fezabilitii tehnologice i a acceptabilitii n raport cu criteriile de performan, utilitate i cost. Un principiu de baz pentru concepia arhitecturii unui sistem de concurente n scopul mbuntirii calitii i al creterii performanelor sale este paralelismul i cooperarea resurselor de concurente concurente folosite, care i gsete aplicabilitatea att la nivel hardware, ct i software [10, 18, 26, 64]. La nivel hardware, de exemplu, creterea puterii de procesare a datelor, a fiabilitii i a toleranei la defectri pot fi mbuntite prin realizarea unor dispozitive numerice integrate pe scar foarte larg pe baza utilizrii extensive a paralelismului la diferite niveluri de granularitate redundante i dezvoltarea unor arhitecturi avansate care permit restructurarea lor n mod dinamic la prelucrarea concurent a aplicaiilor. La nivelul software, se pune problema identificrii i exploatrii paralelismului, n contextul hardware disponibil, cu un potenial mare de prelucrri paralele. n general, detectarea i realizarea paralelismului este o problem dificil din cauza dependenei de date i a modalitii 9

de reprezentare a proceselor concurente cooperante. n [35] sunt descrise unele ci de introducere a paralelismului n arhitectura sistemelor de concurente. Sistemele de calcul concurente de tip MIMD (Multiple Instruction Multiple Data) cu fluxuri de instrucuni i date multiple prezint, prin caracteristicile arhitecturale i capabilitile funcionale, cel mai mare potenial de exploatare a paralelismului. Acest tip de sisteme este constituit dintr-un ansamblu de elemente de prelucrare, care au acces la module de memorii comune (sisteme cu interconectare strns) sau proprii. n acest caz comunicarea dintre elementele de prelucrare este efectuat numai prin mesaje (interconectare moderat sau slab), care coopereaz n mod transparent pentru realizarea funciilor de control i prelucrare, adic permit identificarea i exploatarea paralelismului la un nivel mai mic de granularitate, dar cu perspectiva de a ameliora unele aspecte de ineficien, menionate anterior. Un model arhitectural, fiind considerat ca o referin de ctre fiecare conceptor al unui sistem cu prelucrare distribuit i concurent a datelor n activitatea sa de proiectare, trebuie s includ aspecte structurale statice sau dinamic reconfigurabile, de funcionalitate i implementare. Aceste aspecte pot fi sintetizate prin patru principii de baz [35]: modularitate, funcionalitate, transparen minim, performane maxime. Principiul modularitii presupune structurarea sistemului ntr-un ansamblu de entiti reale i abstracte ncapsulate n obiecte avnd diverse grade de granularitate. Principiul funcionalitii const n asigurarea funcionrii autonome i integrate a elementelor sistemelor concurente. De asemenea, funcionalitatea trebuie neleas ca avnd o finalitate precis la orice nivel de abstractizare. Indiferent de nivelul de detaliere considerat, acest principiu presupune folosirea unui model de execuie paralel, distribuit i/sau concurent de exemplu, modelul client-server care s permit evoluia cooperante. Transparena utilizrii funciilor/serviciilor, oferite n raport cu localizarea obiectelor i eterogenitatea componentelor sistemului de concurente, este un criteriu de ncadrare n clasa sistemelor cu prelucrare distribuit a proceselor concurente. Asigurarea transparenei minime presupune definirea gradului de transparen la un nivel nu mai mare dect cel cerut de anumite aplicaii. Principiul performanei maxime prevede alegerea combinaiilor arhitecturale i atributele acestora cele mai adecvate, pentru a satisface ct mai amplu cerinele de performan ale unor clase de aplicaii. Transparena, cerinele de deschidere, evoluie dinamic sau de standardizare reprezint elemente care influeneaz semnificativ opiunile care conduc la ncadrarea n acest principiu. proceselor aplicaiilor

10

1. 2 Modelarea, verificarea i evaluarea performanelor1.2.1 Metode de modelare, verificarea i evaluare Studierea performanelor constituie una din componentele importante ale activitilor de concepie, de realizare i de ntreinere ale sistemelor de calcul concurente. La nivelul activitilor de concepie i realizare, interesul estimrii performanelor viitoare ale noilor sisteme de concurente tinde s creasc n condiiile sporirii complexitii sistemelor de realizat i implicit a riscului de a obine produse insuficient adaptate destinaiei i cerinelor de performane propuse. n mod asemntor, alegerea unui sistem de calcul adecvat cerinelor proprii unei clase de aplicaii presupune investigaii preliminare privind comportarea sistemelor disponibile n contextul viitor de utilizare [35, 71]. Mrimile care caracterizeaz performanele unui sistem de calcul concurent depind n mare msur de scopul urmrit prin efectuarea evalurii respective. n cele mai multe cazuri performanele, raportate la o anumit ncrcare, se pot exprima n timp de rspuns, debit de lucrri, randamentul utilizrii resurselor, puterea de procesare a sistemului, etc. Modelarea sistemelor de concurente i a altor tipuri de sisteme este folosit pentru descrierea funcionrii i evalurii performanelor lor n stadii de elaborare sau de exploatare. Mai mult, modelarea este unicul mijloc, care poate fi folosit de conceptori, cnd el trebuie s aleag ntre mai multe opiuni viabile ce sunt, la rndul lor inaccesibile la experimentare din cauza constrngerilor de cost i timp. Strategiile de folosire a potenialului de calcul oferit de multitudinea resurselor depind de relaiile de interdependene dintre procese, ntrzierile de comunicaie, frecvena comunicaiilor dintre elemente de prelucrare, strategia de folosire a resurselor specifice aplicaiei. Principalele metode de verificare i evaluare a performanelor, utilizabile n diverse etape ale duratei de existen a unui sistem de concurente, sunt: analiza pe baza modelelor matematice, modelelor de simulare i msurarea performanelor, inclusiv experimentarea prototipurilor. Primele dou metode sunt, de obicei, utilizate pentru estimarea performanelor unui nou sistem de concurente i pentru studierea gradului de adaptabilitate a sistemelor de concurente la cerinele de performan i cost impuse de diverse clase de aplicaii [9, 10, 71, 73]. Msurarea performanelor, presupune existena sistemului real, ale crui caracteristici funcionale trebuie investigate i ameliorate. Noiunea de model, folosit de toate metodele de evaluare n sensul de a reprezenta printr-un procedeu mai mult sau mai puin formal sistemele reale, inclusiv i modul lor de funcionare, inerent, este legat de concretizarea unor detalii funcionale i arhtecturale. Gradul de detaliere a

11

descrierii unui sistem determin apropierea acestui model de realitate i influeneaz direct complexitatea i, deci, costul modelului obinut. La modelarea sistemelor de calcul concurente apar probleme de complexitate major: (i) probleme care pot fi formalizate i soluionate n mod analitic; (ii) cele care pot fi formalizate, ns nu se tie cum ele pot fi soluionate; (iii) cele care nu pot fi formalizate, ns poate fi descris un mecanism de funcionare a sistemelor. Dac simularea asistat de concurenteator poate s ncadreze aceste trei domenii de probleme, atunci modelarea matematic se limiteaz la folosirea primelor dou cazuri (n al doilea caz se vor gsi metode numerice apropiate). Pentru primul caz aceste dou apropieri, se vor valida mutual, n al doilea caz se poate de efectuat concurentee necesare de precizie a unei metode n raport cu altele, al treilea caz rmne apanajul simulrii. n continuare considerm o abordare de analiz sistem, care are ca punct de plecare faptul c funciile unui sistem de concurente se realizeaz prin aciunile unor procese de calcul concurente cooperante. n acest context, cooperarea presupune nu doar capacitatea proceselor de a comunica, ci i corelarea aciunilor lor n vederea realizrii sarcinilor commune, lund n consideraie astfel de fenomene cum ar fi: competiia, sincronizarea, situaii de conflict, excludere mutual, ateptare, etc. [35]. 1. 2. 2 Validarea i dezvoltarea modelelor de evaluare Proiectarea i dezvoltarea unui (sub)sistem n baza principiului reducerii complexitii are avantaje directe privind nelegerea i stpnirea paradigmelor sistemelor cu evenimente discrete i creaz premiza construirii n paralel a componentelor acestuia. Dup dezvoltarea i verificarea independent a componentelor, trebuie asigurat integrarea acestora ntr-un tot unitar, care, prin prisma utilizatorului, apare ca un sistem unic ce trebuie s corespund specificaiilor dorite. Integrarea se face n mod progresiv, incremental, fiecare subsistem nou integrat fiind dependent, sub aspect funcional i al performanelor, de toate celelalte. Validarea specificaiilor se bazeaz pe funcionalitatea fiecrui subsistem i ele au o importan vital n demonstrarea funcionalitii globale a sistemului. n ceea ce privete performanele globale ale sistemului situaia este mai complicat, deoarece verificrile pariale, fcute pentru fiecare subsistem n parte, nu totdeauna permit obinerea direct a unor informaii referitoare la performanele globale ale sistemului. Concepia unui sistem de calcul concurent bazat pe paralelism i coperarea componentelor de la specificaia sa iniial pn la verificarea faptului c dezvoltarea propus satisface cerinelor de performan, necesit, de asemenea, un mediu de dezvoltare care s permit exprimarea specificaiei, descrierea proceselor de prelucrare, compunerea acestor procese pentru a defini interaciunile dintre acestea, etc. n plus, este de dorit ca ntr-un astfel de mediu de concepie i 12

dezvoltare s fie folosit un singur formalism, care s aib capabiliti suficiente pentru exprimarea algoritmilor distribuii, descrierea aciunilor proceselor cooperante, protocoalelor de comunicaie, reconfigurarea dinamic n construirea i validarea modelului sistemului analizat. Dup [18, 21, 23, 33], tehnicile de descriere formal a sistemelor cu evenimente discrete pot fi clasificate n tehnici orientate pe proprietate i tehnici orientate pe model, care descriu funcionarea sistemului prin construirea i analiza modelului su. Exemple de tehnici orientate pe proprietate: logica temporal, limbaje formale sau algebre ale proceselor [33]. ns acestea nu permit evaluarea performanelor sistemului n cadrul folosirii aceluia formalism. Tehnicile orientate pe model dezvolt modelul sistemului, care se supune apoi studiului. Acestea au fost elaborate pentru a reprezenta comportamentul sistemelor cu prelucrare distribuit, modelul stare-tranziie este cel mai cuprinztor i mai rspndit [66, 67, 70]. Elementele de baz ale acestuia sunt: o mulime de comenzi sau evenimente, o mulime de stri sau condiii, funcii de tranziie i o stare iniial, care furnizeaz valorile variabilelor de stare. Fiecare eveniment este asociat cu o funcie stare-tranziie, care provoac schimbarea sistemului dup anumite reguli. n general, fiecare tranziie este indivizibil, n sensul c un eveniment este tratat izolat. Funcionarea poate fi nedeterminist: de la o stare sunt posibile mai multe tranziii care conduc la stri diferite. Modelele cu reele Petri (RP) i extensiile lor [2, 50, 55, 57, 63] pot fi considerate modele stare-tranziie care permit verificarea comportrii globale sau specifice ale proceselor componente unui sistem. Concepute s descrie sisteme distribuite cu evenimente discrete, n care concurena, sincronizarea, comunicarea i paralelismul ocup un loc central, RP au devenit n scurt timp un model de referin n acest domeniu. Fa de alte formalisme, RP au urmtoarele avantaje: simplitatea - teoria RP face apel la un numr redus de concepte elementare care sunt combinate ntr-o varietate de forme; generalitatea cu ele putem modela toate tipurile de sisteme cu evenimente discrete; adaptabilitatea este evideniat prin faptul c modificri minore aduse modelului clasic de RP conduc la modele speciale ce pot surprinde aspecte de temporizare, probabilitate i incertitudine, capabile s le fac utile n domenii ct mai variate. RP li se pot asocia relativ uor diverse tipuri de semantici: secvene de tranziie finite sau infinite, limbaje formale, urme, procese, etc. Multe proprieti comportamentale importante ale sistemelor modelate prin RP pot fi exprimate din punct de vedere al cooperrii proceselor concurente, n special, celor de a fi mrginit, viabil, reversibil, sigur, etc., n baza crora se poate stabili, de exemplu, corectitudinea interaciunii componentelor structurilor corespunztoare 13

n raport cu respectarea restriciilor iniial specificate. RP prezint, de asemenea, un mare interes datorit claritii grafice i intuitive de reprezentare a fluxului controlului ntr-un sistem cu activiti interdependente, iar extensiile lor la RP stocastice [ 2, 63] permit studiul sistemelor de calcul concurente sub aspectul evalurii performanelor.

1.3 Reele Petri generalizate1.3.1 Noiuni introductive i definiii de baz n RP legtura cauz-efect dintre evenimente este redat printr-o mulime de relaii de tipul condiii-evenimente, condiiile fiind asociate cu locaiile reelei, iar evenimentele cu tranziiile respective. Succesiunea de evenimente este exprimat de declanarea tranziiilor validate. Satisfacerea unei condiii este determinat de mrimea marcajului locaiei ce corespunde acestei condiii. Conveniile referitoare la regulile de declanare ale tranziiilor determin metoda de exprimare a concepiei legturilor cauz-efect dintre condiiile i evenimente ce au loc n sistem [63]. Numai dup satisfacerea pre-condiiilor pot aprea unele evenimente, apoi se realizeaz post-condiiile, care, la rndul lor, sunt pre-condiiile unor altor evenimente etc. Astfel, cauzele iniiale pot disprea, dar pot i s-i continue aciunea, ntruct n RP exist destule resurse de marcaje pentru a se asigura regenerarea lor. Pentru ca o tranziie s se poat produce trebuie ndeplinite o serie de condiii, reprezentate prin intermediul locaiilor. Unele locaii sunt considerate intrri ntr-o tranziie i sunt asociate cu condiiile care trebuie ndeplinite pentru ca acea tranziie sa se produc. Alte locaii sunt considerate ieiri ale tranziiei i sunt asociate cu condiiile care sunt afectate de apariia acestei tranziii. Pentru a descrie n mod adecvat interaciunile ce se ntlnesc n sistemele reale destul de complexe, au fost propuse mai multe extensii ale RP [2, 50, 55, 57, 63]. n vederea considerrii locaiilor vide, ca eventuale condiii de declanare ale tranziiilor, au fost definite arce de un tip deosebit, numite arce inhibitoare. Alte extensii ale reelelor Petri sunt cele care permit specificarea unor prioriti la declanarea tranziiilor ce sunt concomitent validatate i cele care includ limite de timp pentru declanarea tranziiilor sau cele care asociaz fiecrui arc o pondere variabil ce se automodific n funcie de marcajul curent al reelei [75, 76]. Puterea de modelare a reelelor RP obinuite este mai mic dect maina Turing, dar orice extensie a acestor tipuri de reele este echivalent cu ea [76]. n prezent reelele Petri au numeroase aplicaii i sunt utilizate n diverse domenii: sistemelor de producie, inginerie, telecomunicaii, modelarea proceselor de afaceri i n nvmnt, deoarece dispun de o reprezentare grafic foarte accesibil, au o semantic bine definit care permite o analiz formal a comportamentului i proprietilor acestora. 14

n ultimul deceniu, o atentie deosebit s-a acordat studiului fenomenelor de asteptare cu cereri negative. Cand o cerere negativ soseste ntr-un sistem de ateptare, ea nlatur imediat una sau mai multe cereri pozitive (ordinare sau normale) prezente. De la introducerea conceptului de cereri negative de Gelenbe [31], cercetarea asupra sistemelor de ateptare cu sosiri negative a fost motivat puternic de aplicaii practice, cum ar fi reelele neuronale, reelele de calculatoare, sisteme de producie i reele de comunicaii, etc. Intr-o reea de calculatoare, o baz de date, cererile negative pot fi reprezentate de virui sau comenzi de a sterge unele tranzacii. Intr-o reea neuronal, cererile negative i pozitive pot reprezenta respectiv semnale inhibitorii i excitatorii. Pentru a descrie n cadrul aceluiai formalism i n mod adecvat procesele de calcul concurente, a efectua verificarea i apoi evaluarea caracteristicilor numerice de performan ale sistemelor de concurente distribuite, n [35], a fost introdus o nou clas de reele Petri generalizate (eng. Generalized Petri Nets (GeN)), cu capaciti negativ-pozitive ale locaiilor i arce reversibile de cardinalitate marcaj dependent, subiacente reelelor Petri stocastice generalizate. n continuare, vom defini o extensie de reele GeN etichetate care permit de a descrie n mod adecvat logica interaciunii proceselor de concurente cooperante. Fie IZ este mulimea numerelor ntregi, iar IN+ este mulimea numerelor naturale. n acelai context, definim L mulimea de etichete L = L P LT , LP LT = asociate respectiv locaiilor i tranziiilor. Locaiile pi etichetate l ( pi ) LP exprim acelai tip de condiii (stri locale, resurse, etc.) l ( pi ) = i , iar fiecare tranziie tj etichetat l (t j ) LT descrie tipul de aciune l (t j ) = j . Definiia 1.1. O reea Petri generalizat etichetat cu capaciti negativ-pozitive ale locaiilor i arce reversibile cu o cardinalitate marcaj-dependent, numit GeN, este o structur de obiecte , redat de urmtorul 10-tuplu: = < P, T, Pre, Post, Test, Inh, Kp , Pri, G, l >, unde: - P este mulimea nevid de locaii, |P| = k. Locaiile pot s conin un numr ntreg negativ ori pozitiv de jetoane. n reprezentarea grafic locaiile sunt redate prin cerculee (vezi Fig.1.1); - T este mulimea nevid de tranziii, |T| = n i PT=. n reprezentarea grafic tranziiile sunt redate prin bare subiri sau dreptunghiuri negre; - Pre, Test i Inh : P T IZ | P | IZ respectiv sunt funcii de inciden inainte ale arcelor cu cardinalitate marcaj-dependent: Pre este funcia de inciden nainte la tranziii, Test este funcia promotor ce descrie eventualele bucle ale reelei impure, adic Pre(t,p)=Post(t,p), iar Inh

15

este funcia de inhibiie a tranziiilor; Post :T P IZ | P | IZ este funcia de inciden napoi la tranziii. Aceste funcii mapeaz mulimea arcelor A n mulimea numerilor ntregi IZ

(negative/pozitive) care determin cardinalitatea marcaj-dependent a arcelor ce conecteaz locaiile (tranziiile) cu tranziiile (locaiile) respective. Mulimea arcelor A este partiionat n trei submulimi A=Ad Ah At, Ad Ah At= . Submulimea Ad determina mulimea arcelor normale directe prin care se consum din pre-locaii sau se produc n post-locaii jetoane (relaie

consumator-productor). Aceste arce sunt reprezentate prin sgei. Submulimea Ah i/sau Atdetermina mulimea arcelor inhibitoare i/sau test. Acestea nu consum jetoane. Un arc inhibitor este reprezentat printr-o linie cu un cercule mic la sfrit, iar un arc test este reprezentat printr-o sgeat cu linie ntrerupt. Dac cardinalitatea unui oarecare arc este egal cu 1, ea nu se menioneaz explicit; - K p : P IZ | P | IZ este funcia de capacitate a locaiei i pentru fiecare pi P aceastamin max este redat respectiv de capacitatea minim K pi i de capacitatea maxim K pi , astfel nct

min max < K pi < K pi < + n locaia pi poate s se afle zero, un numr ntreg pozitiv (negativ) de min max jetoane (antijetoane). Implicit: K pi = 0 , iar K pi este considerat nelimitat;

- Pri: T IZ |+P |IN+ este funcia de ordonare parial a lui T care introduce prioriti dinamice de declanare a tranziiilor validate de marcajul curent. Implicit prioritile nemenionate ale unor tranziii t j sunt considerate nule, adic Pri( t j )= 0; - G : T IZ |P | {true, false} este o funcie de gard (eng. Guard-function), care pentru orice

t determin o funcie Boolean g(t, M) n marcajul current M. Dac tranziia t este validat demarcajul curent M relativ la arce i g(t, M) are valoarea true, atunci tranziia t rmne validat i eventual ea poate fi declanat, iar dac g(t, M) are valoarea false - aceast tranziie nu este validat. Implicit g(t, M)=true. - l : (T P) L este funcia de etichetare a nodurilor (tranziii i locaii) reelei care

mapeaz respectiv locaiile i tranziiile n tipuri de condiii i aciuni, astfel nct

l (t j ) = l (t k ) = pentru t j t k sau l ( pi ) = l ( pn ) = pentru pi p n .Funciile Pre i Post pot fi redate cu ajutorul unor matrice de inciden nainte C + i de inciden napoi C de dimensiunea n k, unde n linii corespund numrului de locaii, iar k coloane corespund numrului respectiv de tranziii. Se va nota cu Pre(t, p) i Post(t, p) elementele acestor matrice, care corespund ponderilor arcelor respective (t, p) i (t, p). Cu Pre(, p) i Post(, p) vor fi notate liniile matricei asociate cu o locaie pP, iar cu Pre(t,) i Post(t,) vor fi notate coloanele acestor matrice ce sunt asociate unei tranziii t T.16

Structura reelei poate fi considerat i deci reprezentat de un graf orientat bipartit (GR), arcele cruia sunt ponderate, iar P T este mulimea vrfurilor acestui graf [11, 27, 161]. Pentru a descrie dinamica funcionrii reelei trebuie considerate GeN marcate i definite regulile de schimbare a marcajelor.Definiia 1. 2. O reea GeN marcat este sistemul redat de cuplul N =< , M0 >, unde este structura reelei considerat n Definiia 1.1, iar M 0 este marcajul iniial al reelei GeN ce

determin o funcie de marcare curent a locaiilor M : P IN + . Marcajul curent M este descris de ctre un vector coloan M = (mi pi , mi 0) , i = 1,..., n ,

n =| P | ,

unde

mi p i ,

min max K pi mi K pi este numrul intreg pozitiv (sau negativ) mi = M ( pi ) de jetoane (sau

antijetoane) n fiecare locaie. Jetoanele (antijetoanele) grafic sunt reprezentate prin puncte negremin (cerculee mici). Astfel, dac K pi mi < 0 , atunci numrul de antijetoane ai n locaia pi este min egal cu ai = K pi mi .

n cele ce urmeaz, pentru a defini regulile de funcionare a unei reele N, introducem urmtoarele notaii:

t = { p P / Pre (t , p) 0} i t = { p P / Post ( p, t ) 0} este, respectiv, mulimea de

locaii incidente la intrarea i la ieirea tranziiei t; - p = {t T / Post (t , p) 0} i p = {t T / Pre (t , p) 0} tranziii incidente la intrarea i la ieirea locaiei p; - o t = { p P / Inh (t , p) 0} i *t = { p P / Test (t , p) 0} este mulimea locaiilor de control al tranziiei t prin arce inhibitoare i arce test; p o = {t T / Inh (t , p) 0} i p * = {t T / Test (t , p) 0} este mulimea tranziiilor este, respectiv, mulimea de

controlate de locaia p, respectiv, prin arce inhibitoare i arce test; n acelai context, pentru a reda regulile de validare a lui t, introducem i urmtoarele notaii: Dac ( Pre(t j , pi ) < 0 ) atunci I j, i = Pre(t j , pi ) ; Dac ( Post (t j , pi ) < 0 ) atunci

O , i = Post (t j , pi ) ; j

Dac ( Inh(t j , pi ) < 0 ) atunci In , i = Inh(t j , pi ) ; Dac ( Test (t j , pi ) < 0 ) atunci jTs , i = Test (t j , pi ) . j

Structura reelei GeN determina logica interaciunii evenimentelor, iar executarea regulilor de funcionare a reelei N determin dinamica sa de comportare, preciznd modul, in care declanarea tranziiilor permite de a modifica numrul de jetoane n locaiile reelei.17

1.3.2 Funcionarea unei reele marcate

La definirea comportamentului dinamic al reelelor GeN marcate sunt acceptate urmtoarele dou ipoteze fundamentale: Ipoteza 1. Atomicitate. Evaluarea condiiei de validare i/sau de executare a regulilor de declanare a unei tranziii este o aciune individual, indivizibil i instantanee; Ipoteza 2. Nedeterminism. Nu exist nici o ordine n privina declanrii tranziiilor care sunt simultan validate (declanabile), adic alegerea unei declanri nu este determinist. Aceste dou ipoteze indispensabile sunt folosite la modelarea proceselor cooperante n sistemele de concurente.Definiia 1.3. (Regula de validare a unei tranziii). O tranziie t j este validat de marcajul

curent M, notat M[ t j >, dac i numai dac, pentru ea este verificat funcia Boolean, ce determin condiia sa de validare (eng. enabling condition) ec( t j , M ) : ec( t j , M ) = ecPr e ( t j , M ) ec Post ( t j , M ) ec Inh ( t j , M ) ecTest ( t j , M ) g ( t j , M ) , unde: (1.1) ecPr e ( t j , M ) = pi t jmax (( mie Pre(t j , pi ) ) (( K p mi ) I , i ) ) este condiia de ji

validare relativ la arce normale incidente nainte la tranziia t j i la capacitile locaiilor pi t j ,min iar mie = mi K pi este numrul efectiv de jetoane n locaia pi ;

max ec Post ( t j , M ) = (( mie Post (t j , pi ) ) (( K pi mi ) O , i ) ) j

pi t j

este

condiia

de

validare relativ la arce normale, care sunt incidente napoi la tranziia t j , i la capacitile locaiilor pi t ; j ec Inh ( t j , M ) = pi ot j

(( mie < Inh(t j , pi ) ) (mie < In , i ) ) este condiia de validare relativ j

la arce inhibitoare; ecTest ( t j , M ) = pi t j

(( mie Test (t j , pi ) ) (mie Ts , i ) ) este condiia de validare j

relativ la arce test. Mulimea tranziiilor validate de marcajul curent M este notat ( ). Validarea unei tranziii nu implic declanarea sa imediat. La un moment dat putem avea mai multe tranziii validate, dintre care una singur poate fi selectat pentru a fi declanat imediat. Declanarea tranziiei trebuie neleas doar ca o posibilitate ce decurge din validare. Nu exist sincronism n N i nici definirea ordinii de declanare a tranziiilor validate concurent. Totodat, declanarea unei tranziii trebuie considerat ca o aciune indivizibil. Dei conceptul 18

de durat nu este folosit ntr-o N , poate fi util s asociem declanarea unei tranziii cu o durat zero, pentru a facilita nelegerea conceptului de indivizibilitate a acestei aciuni.Definiia 1.4. (Regula declanrii unei tranziii validate). Tranziia t j T (M ) este

declanat dac nu exist o alt tranziie cu o prioritate superioar ei, Pri( t j )>Pri( tk ), pentru care sunt verificate precondiiile sale de validare t k T (M ) . Declanarea tranziiei t j din M conduce la un nou marcaj M = M + Post (t j , ) Pre (t j ,) , unde Pre (t j ,) i Post (t j ,) , sunt funcii induse de matricele Pre, Post pe P. Faptul declanrii t j de marcajul M va fi notat M [t j ] > M . Jetoanele i antijetoanele, ce se afl n aceeai locaie, se vor anihila imediat unele pe altele. Anihilarea este posibil n fiecare marcaj cu mi 0 i ai 0 n aceeai locaie pi . Aceast aciune produce un marcaj instabil (engl. vanishing state) , care imediat schimb cuplul ( mi , ai )) ) ) n marcajul ajustat la ( mi ai , ai mi ), unde xi yi este definit astfel:

x y, ) xi yi = 0,

x y 0, altfel.

Aceasta implic faptul c n fiecare locaie pi putem avea un marcaj current, fie cu mi p i ,max min 0 mi K pi , fie cu ai pi , K pi ai 0 .

n rezultat, dac ( Pre(t j , pi ) > 0 ), atunci declanarea tranziiei t j T (M ) consum din (produce n) locaia pi un numr Pre(t j , pi ) > 0 de jetoane (antijetoane), altfel ea produce n (consum din) aceeai locaie un numr Pre(t j , pi ) < 0 de antijetoane (jetoane). De asemenea, dac ( Post (t j , pi ) > 0 ), atunci declanarea tranziiei t j T (M ) produce n (consum din) locaia pi un numr Post (t j , pi ) de jetoane (antijetoane), altfel ea consum din (produce n) aceeai locaie un numr Post (t j , pi ) < 0 jetoane (antijetoane). Exemplul 1.1. Un exemplu de reea N1 cu capaciti negative ale locaiilor i arce reversibile, cardinalitatea marcaj-dependent a crora poate fi negativ este prezentat n Fig.1.1a, n caremin capacitatea minim a locaiilor este K pi = 3 , i=1,...,4, iar ponderile arcelor respectiv sunt:

Pre(t1 , p1 ) = 3 , Pre(t1 , p2 ) = 1 , Post (t1 , p3 ) = 2 i Pre(t1 , p4 ) = 2 .

Marcajul iniial al reelei N1 este M 0 = (2, 2, 3, 1) . Declanarea tranziiei t1 produce 3 jetoane n p1, 2 jetoane n p3, 1 antijeton n p2 i 2 antijetoane n p4, adic ponderea negativ a

19

arcelor duce la schimbarea direciei fluxului de jetoane, modelnd astfel arce reversibile. n Fig. 1.1b este reprezentat schimbarea marcajului M 0 n M 1 = (1, 1, 1, 3) , adic M 0 [t1 > M 1 .

a)

b)

Figura 1.1. Declanarea tranziiei reelei N1 Notm c putera de modelare a reelelor GeN marcate este egal cu maina Tiuring, deoarece ea conine arce inhibitoare [50]. n [3], a fost demonstrat faptul c, pentru o reea RP cu arce de resetare (eng. reset arcs), proprietatea de accesibilitate nu este decidabil. n general, pentru GeN marcate, proprietile de accesibilitate nu sunt decidabile, deoarece n aceast reea, prin funcii marcaj-dependente Pre(t j , pi ) = M ( pi ) ale arcelor normale, pot fi redate arce de resetare a locaiilor pi . ns, unele proprieti comportamentale, pentru cazuri particulare, sunt decidabile.min max Reelele GeN cu capacitai < K pi < K pi < + negative ale locaiilor i arce reversibile

cu automodificare ( pi , t j ) sau (t j , pk ) de cardinalitate < Wi , j < + sau < W j ,k < + pot fi descrise prin reele GeN+ ce au numai capaciti pozitive ale locaiilor i numai arce cu automodificare de cardinalitate pozitiv. Pentru a obine GeN+ din GeN este necesar de a modifica unele atribute ale acesteia: a) pentru pi a GeN+ punem+

min K pi = 0 i

+

max max min K pi = K pi K pi - capacitile pozitive

min respective ale locaiilor, iar + M 0 ( pi ) = M 0 ( pi ) K pi - marcajul lor iniial;

b) dac cardinalitatea unor arce ( pi , t j ) sau (t j , pk ) poate primi valori < Wi , j < 0 sau < W j ,k < 0 , atunci pentru fiecare t j , cu mulimea arcelor { ( pi , t j ) , ( pl , t j ) } i mulimea locaiilor { pi , pl } ( t j o t j *t j ) incidente nainte i celor incidente napoi { (t j , pk ) , (t j , pn ) } cu{ pk , pn } t , introducem cte o nou tranziie t j , astfel nct incidena arcelor { ( pl , t j ) }, jpl ( t j o t j *t j ) i { (t j , pn ) }, pn t j este aceeai ca i pentru t j .

Arcul

( pi , t j ) sau

(t j , pk ) ce are pondere negativ este replicat cu sens invers relativ la t j , adic (t j , pi ) sau ( pk , t j ) , iar cardinalitatea acestora respectiv devine +W j , i = Wi , j > 0 sau +Wk , j = W j ,k > 0 ; 20

c) pentru GeN+ funcia de gard a tranziiei t j , n dependen de orientarea arcelor considerate,+

devine,

respectiv,

+

g (t j , + M ) = g (t j , M ) & (Wi , j > 0)

sau

g (t j , + M ) = g (t j , M ) & (W j , k > 0) . n mod similar, pentru tranziia t j respectiv punem g (t j , + M ) = g (t j , M ) & (Wi , j < 0) sau + g (t j , + M ) = g (t j , M ) & (W j , k < 0) .

+

Obinnd astfel reeaua GeN+, ea poate fi analizat folosind metodele clasice cunoscute [63, 67]. n Fig. 1.2, este prezentat un exemplu de o astfel de transformare pentru reeaua N2 n N+2. Din punct de vedere al modelrii, reelele GeN i GeN+ sunt echivalente, deoarece ele genereaz grafuri de marcaje accesibile izomorfe. ns, reeua GeN este cu mult mai compact i flexibil dect GeN+.p1

p3

p4

p1k p3 =5

p3

p4

k p3 =5t1

g1m1 m3

t23

g2

t1 p2

g1

t2

g2m3 m13

t3g3

m1 m3

p2

p5

p5

Figura 1.2. Transformarea reelei N2 n N+2 n [11, 32] sunt considerate diferite metode de astfel de analiz.1.3.3 Compoziionalitatea modelelor

Compoziionalitatea este un concept fundamental i o proprietate dorit n definirea metodelor de construire a modelelor sistemelor de concurente folsind modele resurs-aplicaie, modele ale proceselor de concurente sau aplicaii i o interfa sau o mapare ce combin aceste modele [72]. Cu toate c actualmente RP sunt recunoscute ca un puternic formalism de modelare a sistemelor cu evenimente discrete concurente i paralele, lipsa construciilor compoziionale integrate face ca utilizarea lor sa nu fie eficient i nepotrivit n modelarea diverselor sisteme reale. Construirea acestor modele n form de reele RP plate devine mai degrab o art dect o rutin. ncorporarea compoziionalitii n RP [55, 62] a fost i rmne un topic de mare interes de studii n mai multe directii, cum ar fi: sale; reprezentarea i analiza sistemelor resurs/program aparte i apoi integrate; 21 abilitatea de a construi sistemul ntr-un mod compoziional i modular, permind n acelasi timp deducia i/sau pstrarea proprietilor componentelor din analiza subcomponentelor

-

rafinarea sau compunerea modelelor; analiza compoziional a proprietilor modelului.

Studiile asupra definiiei semanticii reelelor RP compoziionale, reprezint o abordare modular a construciei i analizei acestora. De exemplu, n [33] sunt propuse unele abordri compoziionale bazate pe semantica algebrei proceselor CSP (Communicating Sequential Processes), n care se discut necesitatea teoretic i practic de elaborare a metodelor de generare compoziional a spaiului de stri. Kotov [40] descrie o semantic de control al structurilor RP ordinare i a unor operaii, n termenii unei reele structurate, pentru care este caracteristic construirea lor topologic regulat. De la reele atomice (corespunzatoare cuvintelor program), reele RP ordinare mai complexe pot fi formate aplicnd operaii compoziionale. Aceasta d posibilitatea de a partiiona procesul de analiz i construire a unor atare reele ntr-o multitudine de etape, unde este mai uor de a reda fragmente de reele mai simple. ns aceast subclas de reele RP, din cauza constrngerilor puterii de modelare i de inciden topologic, care au loc la redarea analitic a reelelor RP, nu poate descrie adecvat reele GeN, subiacente reelelor GeN stocastice, ce sunt caracteristice la modelarea proceselor de funcionare ale sistemelor de concurente. n continuare, pentru a aborda aceste inconveniente, vom defini un set de operaii compoziionale ntr-un spaiu de condiii-evenimente, care va permite de a descrie interaciunea proceselor specifice sistemelor de concurente. Astfel, avem posibilitatea de a formaliza etapa de trecere logic de la descriera informal a arhitecturii, specificaiilor comportamentale ale sistemului ctre modelul su n form de GeN. Pentru a defini o metod compoziional potrivit de compunere i analiz a modelelor de GeN, vom lua n consideraie urmtoarele criterii: etc.; definiia unei componente de baza: ar trebui s fim n stare s construim modelul ntr-o maniera regular i progresiv, pornind de la componente ce au caracteristici comune, asemanatoare. n acest mod, conceptorul poate identifica, ce va constitui o component de baz i va putea construi modelul, folosind operaiile de compoziie respective; operaiile compoziionale ale GeN ar trebui s suporte reprezentarea diferitelor tipuri de interaciuni ale resurselor, diferitelor tipuri de abloane comportamentale i structuri simetrice, comune proceselor cooperante ale sistemelor de concurente paralele i distribuite; marcajul iniial al componentelor. Starea sistemelor este modelat n GeN printr-o distribuie de jetoane n locaiile reelei. Considernd sistemul compus din subsisteme, starea 22 relaia model sistem: modelul sistemului i modul n care el a fost construit ar trebui s reflecte structura sistemului: (sub)sistemele, componentele, procesele sale i relaiile dintre ele,

sistemului ar trebui compus sau dedus din starea subsistemelor. n acelai mod, ntr-o reea compoziional GeN ar trebui sa fie posibil deducerea strii unei componente date din compoziia starilor subcomponentelor sale; reutilizarea submodelelor. Compoziionalitatea i modularitatea ar trebui s implice i posibilitatea de reutilizare a lor. Pentru a avea posibilitate de a reutiliza o component, funcionalitatea acesteia trebuie cunoscut. Cu toate c aceasta nu este menionat explicit, ca fiind una din metodele compoziionale studiate, toate metodele ce asociaza o funcionalitate componentelor, implicit, permite reutilizarea acestora.

1.4 Expresii descriptive ale reelelor Petri generalizatePentru a modela procesele sistemelor de calcul concurente prin GeN marcate este necesar s definim un set de operaii compoziionale care vor exprima interaciuni sincrone i asincrone ale componentelor. Exist un consens n privina obinerii comunicrii asincrone prin contopirea locaiilor (metoda de cutie potal) dintre componente sau folosind locaii etichetate [40]. n acelai context, exist dou metode de baz n modelarea comunicaiei sincrone: prin contopirea tranzitiilor (metoda randez-vous) sau folosind tranziii etichetate. Locaiile i tranziiile etichetate sunt, n unele cazuri, folosite i ca pai intermediari pentru a identifica nodurile reelei ce urmeaz a fi contopite. Metodele, ce utilizeaz direct contopirea nodurilor, se bazeaz pe cunoasterea de ctre conceptor a nodurilor, ce urmeaz a fi contopite. Pentru a reutiliza o component cu locaii etichetate sau tranziii etichetate, se poate s fie necesar redenumirea acestora. Fie = {a, b, c,...} sau = { p1 , p2 , p3 ,...} este mulimea de simboluri-locaii, iar

= {x, y, z,...} sau = {t1 , t 2 , t3 ,...} este mulimea de simboluri-tranziii n spaiul c _ e decondiii-evenimente ce determin suportul traseelor unor procese n acest spaiu. n baza acestor suporturi i vom defini un set de operaii copoziionale pe c _ e redate de expresii descriptive elementare (A), (B) sau compuse, ce descriu relaiile de interaciune a ocurenelor evenimentelor, componentelor i sub-sistemelor constituente. Aceste operaii compoziionale vor reda legturile locaii-tranziii-locaii (cauz-efect) n clasa reelelor GeN, subiacente reelelor GeN stocastice. Pentru a reda reelelor GeN proprietai compoziionale, n mod similar cu noiunea de pixel, vom introduce noiunea de dexel (descriptive expression element) cu un set de atribute care permite de a construi, dupa anumite reguli specificate de conceptor, orice model de reea GeN, folosind un set de operaii compoziionale ntroduse n continuare. 23 [40], generalizate i prezentate n

Definiia 1.5. Numim bDE dexel elementul de expresie descriptiv al GeN primitive bN :

bDE =

j j gj tj

|

m0i ki yii [Wi + ,Wi ] kk | kk , g t

p unde y { p, p, ~} este simbolul-locaie ce determin respectiv tipul de arc ({ normal, inhibitor, test}) cu ponderea Wi {Pr e(t k , pi ), Inh(tk , pi ), Test (t k , pi )} incident nainte la tranziia | tk , iar Wi + {Post (t j , pi )} este ponderea arcului normal ce iese din tranziia | t j i intr n locaia pi . Atributele locaiei pi respectiv sunt: m0i -marcajul iniial; ki - capacitile locaiei; i eticheta locaiei red tipul de condiii. Atributele tranziiilor t j i tk respectiv sunt: g j i g k funciia de gard; j i k - funciia de prioritate; j i k - eticheta tranziiei ce red tipul de aciune. Maparea unor derivative ale bDE n reele GeN primitive bN este prezentat n Fig. 1.3. Unele attribute pot fi omise. De exemplu, dac bDE = | t j yi [Wi + ,Wi ]|tk implicit avem:min max m0i = 0 ; K pi = 0 , iar K pi este considerat nelimitat;

i = {} , j = {} , k = {} ;

g j = g k ="true " ; j = k = 0 . n cazul n care Wi = Wi + = 1 paranteza ptratic se va omite:

bDE =

j j gj tj

|

m0i ki yii [1, 1] kk | kk = g t

j j gj tj

|

m0i ki yii

k k g k tk

|

.

n Fig. 1.3d - Fig. 1.3f sunt prezentate unele derivative ale bDE pentru pi = , W i

k = 0 , bDE = g jj | t j j m0i i yi i [Wi ]

cu locaie pi de ieire la tranziia t j i pentru

k pi = , Wi + = 0 , bDE = m0i i yi i [Wi ] gkk | tkk

cu locaie pi de intrare la tranziia tk . Cu ajutorul diferitor derivative ale bDE i operaii compoziionale unare i/sau binare, folosind un raionament adecvat ce red interaciunea condiiilor i evenimentelor sistemului specificat, putem compune expresii descriptive ale modelelor GeN (sub)sistemelor considerate.Definiia 1.6. O expresie descriptiv (DE) a unei reele N tip GeN este:

DE :: = bDE | DE DE | o DE , unde reprezint operatorul unei operaii binare compoziionale a expresiilor descriptive, iar o represent operatorul unei operaii unare. Implicit, la aplicarea acestor operaii locaiile i tranziiile ce au acelai nume se vor contopi respectiv. 24

j

jtjj j gj tj

Wi+ ki

pim0 i

gj

i

Wi

k

ktk

j

jtjj j gj tj

Wi+ ki

pim0 i

Wi

k

ktk

ca)

gk

gj

i

cb)

gk

|

m0i ki pii [Wi + ,Wi ] kk | kk g t

|

m0i ki pii [Wi + ,Wi ] kk | kk g t

j

jtjj j gj tj

Wi+ ki

pim0 i

Wi

k

ktk

j

jtjj j gj tj

Wi ki

pim0 i

gj

i

|

m0 i

ki

c ~ i [W + , W ] k | k pi i i g k tkc)

gk

gj

i

cm0i ki pii [Wi ]d)

|

pikim0 i

ii

Wi

k

ktk ki

pim0 i

c

gkk k g k tk

i

Wi

k

ktk

m0i pi [Wi ]e)

ki

|

m0 i ki ~i i [Wi ] kk | kk p g tf)

c

gk

Figura 1.3. Maparea unor derivative ale bDE n reele GeN primitive bN ntr-o DE, orice simbol-locaie sau simbol-tranziie poate fi folosit n orice ordine de mai multe ori. Astfel, se va subnelege c n reele GeN respective, redate de expresia DE, aceleai locaii (tranziii), cu acelai simbol vor fi contopite ntr-un singur simbol-locaie (simboltranziie). Ca rezultat al aplicrii acestor operaii compoziionale, obinem o nou clas de subreele Ni, interconectarea crora, conform DE, va determina reeaua N rezultant, redat de aceast expresie. n continuare, dac nu va fi menionat explicit, la definirea operaiilor compoziionale i ale expresiilor descriptive, vom omite unele atribute ale locaiilor i tranziiilor, deoarece ele, fiind implicite, nu influeneaz structura reelei. Astfel, deseori vom folosit derivativul:

bDE = | t j j m0i yi [Wi + , Wi ] | kk sau bDE = | t j j m0i yi | kk n cazul n care Wi + = Wi = 1 . t tn acest context, pentru a reda clasa reelelor GeN, vom defini setul de operaii compoziionale: 25

1. Operaia Inhibiie, redat de operatorul pi , este o operaie unar. Ea descrie faptul c la ocurena pre-condiiiei pi , nu mai poate avea loc ocurena evenimentului specificat, adic operaia pi va interzice (va inhiba) ocurena evenimentului asociat cu aceast pre-condiie pi .k Acestei operaii i corespunde dexel-ul DE1 = m0i i pi i [Wi ] gkk | tkk ce red o reea primitiv,

constituit din locaia pi i arcul inhibitor ce duce din aceast locaie n tranziia tk , cu atributele respective, legat de declanarea evenimentului specificat (vezi Fig 1.3e). 2. Operaia Sincronizare, (AND-Join), redat de operatorul sau , este o operaie binar ce descrie sincronizarea pre-condiiilor legate cu pi t j , i = 1, n ale unui eveniment t j , ocurena cruia va avea loc numai atunci, cnd concomitent aceste pre-condiii sunt verificate. Acest fapt este redat de urmtoarea expresie descriptiv:DE 2 = (m01K p1

y1 [W1 ] ... m0i

K pi

yi [Wi ] ... m0 n

K pn

yn [Wn ] ) | t j j = ( m0 ii =1

n

K pi

yi [Wi ] ) | t j j .

Cu ajutorul acestei operaii compoziionale, se poate reda operatorul Join(a, b) proces.

n

programarea paralel, ce determin jonciunea a dou sau a mai multor procese ntr-un singur Dac cardinalitatea arcelor ( ( pi , t j ) , i = 1, n ale reelei n DE2 este egal cu 1, adic Wi = 1 , obinem DE 3 = ( mi0 yi ) | t j j . Maparea expresiei DE2 n N2 este prezentat n Fig. 1.4a.i =1 n

pl m 0 l pk m 0 k pL m0 L

Wl Wk aj

m0 p

Wp

aj

WL

tj

tj

a)

b)

Figura 1.4. Maparea expresiei DE2 n N2 (a) i a expresiei DE2 r n N2r (b) Aceast operaie este comutativ, asociativ i reflexiv. Astfel, n conformitate cu proprietatea K reflexiv, dac pi = pr din DE 2 obinem DE 2 r = m0 r pr pr [Wr ]| t j j (Fig. 1.4b), undem0 r = m0 i , Ki =1 n

pr r

=

Wi =1

n

i

, Wr = Wi .i =1

n

3. Operaia Secvenialitate, redat de operatorul |, este o operaie binar ce determin logica cauz-consecin a relaiei dintre dou stri locale pi (pre-condiie) i pk (post-

26

condiie), determinat de aciunea t j . Operaia Secvenialitate, exprimat de expresia DE3, este asociativ, reflexiv i tranzitiv, ns necomutativ:DE 3 = m0i pi [Wi ] | t j j m0 k pk [Wk ] m0 k pk [Wk ] | t j j m0i pi [Wi ] . Maparea DE3 n N3 este prezentat n Fig. 1.5. Operatorul | d posibilitatea de a descrie secvene de evenimente i, astfel, de a reda traseul secvenial al unui proces.j

pi kim0 i

Wi

jtj

Wk kk

pkm0 k

i

gj

k

pkm0 k

Wk

j j

Wi ki

pim0 i

kk

k

gj

tj

i

Figura 1.5. Maparea expresiei DE3 n N3Modelarea operaiei iteraie poate fi redat prin contopirea locaiilor de la inceputul expresiei cu cea de la sfritul ei care au acelai nume (operaia nchidere). Un exemplu de aplicare a acestei operaii, descris de expresiile DE4 i DE5: DE 4 = 3 p1 W

[ ]| 1

t1

p2 W2+ , W

[

2

]|

t

2

+ 2 p3 W 3 , W

[

3

]|

t3

p1 W

[ ],+ 1

DE 5 = 3 p1 | t 1 p2 | t 2 2 p3 | t 3 p1

este pezentat n Fig. 1.6a i Fig. 1.6b.p1 W1 t1 W2 + p2 W2 t2W3 +

p3

N4: a)

W3 t3

W1+

p1

p2 t1 t2

p3 t3

N5: b)

Figura 1.6. Maparea expresiei DE4 n N4 (a) i a expresiei DE5 n N5 (b)3. Operaia Test cu operatorul ~i , descrie o bucl a reelei impure N6 redat de p

DE 6 = m0i pi [Wi ] | t j j m0 k pk [Wi ] = m0i ~i [Wi ] | t j j , ea reprezint operaia cu test arc (Fig. 1.4f). p

4. Operaia AND-Split sau Fork, redat de operatorul , descrie faptul c la ocurena unui eveniment specificat t j se vor produce concomitent dou sau mai multe post-condiii. Aceasta operaie binar este exprimat de urmtoarea expresie descriptiv:DE 7 = | t j j ( m01 p1 [W1 ] ...m0i pi [Wi ] ...m0 n pn [Wn ] ) = | t j j ( () n =1m0 k pk [Wk ] ) . k

Dac Wi = 1 , atunci cardinalitatea arcelor ( t j , pi ), i = 1, n a reelei n DE7 este egal cu 1,

27

K obinem DE8 = | t j j ( () k =1m0 k pk ) . Maparea expresiei DE7 n N7 este prezentat n Fig. 1.7a.

Wl aj tj Wk WL

ml00 mk0 mL

pl pk pL aj tj Wp m0 p

N7 a)

N8 b)

Figura 1.7. Maparea expresiei DE7 n N7 (a) i a expresiei DE7r n N7 r (b) Aceast operaie este comutativ, asociativ i reflexiv. Cu acest operaie copoziional se poate reda operatorul Fork(a, b) n programarea paralel ce determin ramificarea unui singur proces n dou sau mai multe procese. Ca i pentru operaia sincronizare, folosind proprietatea reflexiv, pentru pi = pr dinDE 7 obinem DE 7 r = m0 rK pr

p r [Wr ]| t j j , unde m0 r = m0 i , Ki =1

n

pr r

=

Wi =1

n

i

, Wr = Wi .i =1

n

5. Operaia Paralelism competitiv, redat de operatorul . Aceast operaie copoziional binar descrie relaiile logice de paralelism competitiv ale condiiilor i evenimentelor ntre dou sau mai multe procese concurente. Ea este aplicat pentru a efectua compunerea unor modele de subreele, ce descriu funcionarea subsistemelor respective, ntr-un model rezultant al sistemului considerat. Fie dou subreele NA i NB sunt redate de expresiile respective DEA = A i DEB = B, atunci la compunerea lor prin aplicarea operatorului , relativ la aceste dou expresii descriptive, obinem o reea rezultant NR redat de DER = R = A B n care locaiile i tranziiile, ce au acelai nume, respectiv, vor fi contopite. Nodurile contopite vor pstra atributele i incidena arcelor din fiecare subreea. Aceast operaie este comutativ, asociativ i reflexiv. Pentrun i =1

a

ilustra

folosirea

acestui

operator

vom

considera

expresia

DE 8 = ( m0 i ai [Wai ]| ti bi [Wbi ] ) cu marcajul iniial m0i = 1 care descrie n procese paralele. Aceste

n componente au o similaritate descriptiv structural, care descrie n subreele izomorfe. n conformitate cu proprietatea de reflexivitate a acestei operaii, n cazul n care ai=a, bi=b i tj =t , obinem n componente identice (simetrie), la contopirean

crora

obinem

DE8r = ma a[Wa1 ]| 1 b[Wb1 ] , unde marcajul iniial rezultant este ma = m0 i . t1i =1

28

Pentru n = 3 reelele N8 i N8

r

, obinute prin maparea expresiilor DE8 i DE8r sunt

prezentate n Fig. 1.8a i Fig. 1.8b respectiv.

atj

644 7444 4 8pi

a

pi

a

pi

a

pi Wi ma j Wk

Wi

Wi

Wi

j t jWk pk

j t jWk pk

jWk pk

t

b

b

b

b

pk

Figura 1.8. Maparea expresiei DE8 n N8 (a) i a expresiei DE8r n N8 r (b) 6. Operaia Abstracie funcional, redat de operatorul \ L ,

L = { j , i } ,

t j T L , pi P L . Aceast operaie unar permite de a ascunde (elimina) mulimea de etichete

L ale tranziiilor i/sau locaiilor, astfel nct aciunile i/sau condiiile (resursele) asociate cu De exemplu, aplicnd la DE11 = ( 3 p1 5 p6 2 [2] | 12 p2 | t 2 2 p3 | 31 p4 | t 3 1 p5 1 | 42 ( p14 p3 1 [3]) t t t

ele devin invizibile (luntrice sau private) i ele nu pot fi partajate la cooperarea proceselor.

aceast operaie unar cu mulimea de etichete invizibile L1 = { 2 , 1 } , obinem: DE12 = DE11\ L1 = ( 3 p1 5 p6 2 [2] | t 1 p2 | t 2 2 p3 | 31 p4 | t 3 1 p5 | t 4 ( p1 4 p3 [3]) . t

7. Operaia Reetichetare funcional, redat de operatorul / + L , permite de a reeticheta unele aciuni i/sau condiii din+

L = {l (t k ) = j , l ( pn ) = i } , t j T + L , pi P+ L , astfel nct

acestea devin vizibile i ele pot fi folosite la descrierea proceselor ce coopereaz prin + L . De exemplu, expresia DE11 este obinut din DE12 dac vom aplica aceast operaie unar la DE11 = DE12 / +L2 cu + L = {l (t1 ) = l (t 4 ) = 2 , l ( p3 ) = l ( p5 ) = 1 } . 8. Operaia Cooperare funcional, redat de operatorul p Lc f .

Aceast operaie binar

permite de a descrie cooperarea unor procese concurente. Ea este aplicat pentru a efectua compunerea unor modele de subreele, ce descriu funcionarea subsistemelor respective, ntr-un model rezultant al sistemului, considerat prin contopirea unor locaii i/sau tranziii etichetate specificate de etichete din mulimea Lc . Fie dou subreele NAc i NBc sunt redate de expresiile respective DEAc = Ac i DEBc = Bc, atunci, la compunerea lor prin aplicarea operatorului p Lc f

relativ la aceste dou expresiip Lc f

descriptive, obinem o reea rezultant NRc redat de DERc = Rc = Ac

Bc , n care locaiile i 29

tranziiile ce au aceleai etichete respectiv vor fi contopite. Nodurile contopite i apoi renumite vor pstra atributele i produsul cartezian al incidenelor arcelor din fiecare subreea. La contopirea locaiilor { pi PAc , pn PBc : l ( pi ) = l ( pn ) = Lc } { t j TAc , t k TBc : l (t j ) = l (t k ) = Lc } specificate de de { pi , pn } , obinem respectiv: PRc = PAc ( PB c \ { pi , pn }) { pi _ n } i TRc = TAc (TB c \ {t j , t k }) {t j _ k } . Capacitile i marcajul locaiilor { pi _ n } respectiv sunt determinate de urmtoarele relaii:min min min max max max { < K pi _ n = K pi + K pn < K pi _ n = K pi + K pn < +} i {M Rc ( pi _ n ) = M Ac ( pi ) + M Bc ( pn )} .

i ale tranziiilor

p Lc f

cu incidena arcelor determinate

Funciile de gard ale tranziiilor {t j _ k } sunt {g ( t j _ k , M Rc ) = g (t j , M Ac ) & g (tk , M Bc )} . Aceast operaie este comutativ, asociativ i reflexiv. Menionm c n cazul n care mulimea Lc este vid, Lc = , operaia p f devine . n Fig. 1.9 este prezentat un exemplu de cooperare funcional a urmtoarelor subreele: Ac1 = p1 |t1 p2 p1 |2 p3 cu Bc2 = p4 |t3 p5 p6 |t4 p7 i Ac3 = p1[3] | p2 cu Bc4 = p3[3] | p4[4] . t t1 t1

Ca rezultat al aplicrii operaiei binare cooperare, obinem urmtoarele expresii descriptive:Rc1_ 2 = Ac1p f

Bc 2 , unde Rc1_ 2 = p1 |t1 p2 ( p1 p4 ) |2 _ 3 ( p3 p5 ) ( p1 p6 ) |2 _ 4 ( p3 p7 ) i t tp , f

Rc3 _ 4 = Ac3

Bc 4 , unde Rc3_ 4 = p1_ 3[3] |_ 2 ( p2 p4[4]) . t1

La cooperarea lor funcional prin L = { , } obinem Rc 1 = Ac 1 p Lc f Bc 1 ,n care tranziiile respective t1 i t5 etichetate sunt contopite n t1 _ 5 , iar t3 i t6 etichetate sunt contopite n t3 _ 6 . 9. Operaia Marcare Inial, redat de operatorul ny. Aceast operaie unar descrie numrul n de jetoane n locaiile y respective ale DE pentru marcajul iniial. Semantica acestei operaii este urmtoarea: 1) n este un numr ntreg indicat naintea unui simbol-locaie y, adic ny, arat la numrul iniial de n jetoane (antijetoane) n aceast locaie. Dac n = 0 atunci n este omis. La contopirea locaiilor y din dou subreele N i i N j diferite cu marcaje curente respective ni y i n j y , numrul rezultant de jetoane n aceste locaii se va aduna, adic obinem: (ni + n j ) y . 2) notaia n(A) arat la numrul de n jetoane n fiecare locaie al formulei descriptive A; 3) un singur jeton n =1, de asemenea, se va indica. Dac un oarecare simbol-locaie (sau o formul descriptiv) nu este marcat, aceasta nseamn c naintea simbolului (respectiv expresiei descriptive) nu este indicat, numrul n egal cu zero jetoane, adic n este omis.

30

N1 p1 p4

N2 p6 p1

N1_ 2 p4 p6

t1 p2 p3 t2

p f

t3 p5 p7

t4

t1 p2 t2 _ 3 p3 p5

t2 _ 4 p7

N3 p1

N4

N3_ 4 p1 _ 3

p3

3

t1

p , f t2 4

3

p2

3

t1 _ 24

p2

p4

p4p f

Figura 1.9. Cooperarea funconal a subreelelor: Rc1_ 2 = Ac1

Bc 2 i Rc3 _ 4 = Ac3

p f

Bc 4 .

Deseori, simbolurile locaiilor i ale tranziiilor n expresia descriptiv vor fi notate, respectiv, prin simbolul yk i t j indexat cu un singur indice sau de simbolul cu doi indici de tipulyi , k i ti , j , primul indic numrul componentei, iar al doilea indic numrul de ordine al locaiei

i tranziiei n aceast component.

Astfel, se va stabili o corespundere biunivoc ntre

subreelele GeN i respective ale modelului i simbolurile locaii i tranziii ale expresiei descriptive ce red GeN i . n clasa reelelor GeN una i aceeai reea poate fi redat prin diferite expresii descriptive cu diferii operatori, pe care le vom considera expresii echivalente, care pot fi transformate unele n altele cu ajutorul unei secvene finite de transformri echivalente. De exemplu, DE 2 = ( m0i K yi [Wi ] ) | , de asemenea, poate fi exprimat folosind i tpi j

n

i =1

j

operatorul , innd cont de faptul c tranziiile cu acelai nume t j vor fi contopiteDE 2 =

(mi =1

n

0i

K pi

yi [Wi ] | t j j ) .

Fie A, B, C sunt trei expresii descriptive arbitrare, iar n este numrul de jetoane. Transformrile echivalente ale expresiilor descriptive se vor efectua, lund n consideraie proprietile operaiilor compoziionale definite anterior i anume: 1) comutativitate ( A B) = ( B A) , ( AB) = ( B A) , ( A p Lc f B) = ( B p Lc f A) ; 31

2) asociativitate ((A|B)|C) = (A|(B|C))= A|B|C, (( A B) C ) = ( A ( B C )) = ( A B C ) , (( A B) C ) = ( A( BC )) = ( ABC ) , (( A B) C ) = ( A ( B C )) = ( A B C ) , (( A p Lc1 f B) p Lc 2 f C ) = ( A p Lc1 f ( B p Lc 2 f C )) = ( A p Lc1 f B p Lc 2 f C ) ; n continuarie, pentru a micora numrul de paranteze n expresiile descriptive, vom lua n consideraie proprietatea asociativ a operaiilor respective i vom scrie expresii de acest tip fr paranteze luntrice. De asemenea, cnd nu va aprea nici o ambiguitate, vom omite i parantezele exterioare, lund n consideraie urmtoarele prioriti de folosire a operaiilor compoziionale la evaluarea expresiilor descriptive: operaiile se vor aplica de la stnga spre dreapta; o operaie unar leag mai puternic ca cele binare; operaia i este superioar operaiei | , care, la rndul ei, este superioar operaiilor \ L , / + L , i p Lc f . Acolo, unde este necesar de a schimba ordinea folosirii acestor operaii, se vor utiliza paranteze respective, innd cont de urmtoarele proprieti: distributivitate (AB)|C = (A|C)(B|C) sau C|(AB) = (C|A)( C|B), (A B)|C = (A|C) (B|C) sau C|(A B) = (C|A) ( C|B); reflexivitate A = nA, p f A = A = nA ;i =1 n

n

n

i =1

i =1

marcare n( A B) = nA nB , n( A B) = (nA nB) , n( AB) = (nAnB) .

n dependen de contextul modelrii i analizei sistemului, vom folosi varianta cea mai simpl. O aplicare a operaiilor compoziionale considerate este prezentat n continuare pentru maparea structurei reelei N9 din Fig. 1.10 redat de expresia descriptiv DEN 9 :

Figura 1.10. Maparea DEN 9 n N9 DEN 9 = p1[3] |t7 p2 [2] |t6 p3 ( p3 [2] p2 ) |t5 p4 ( p3 p4 ) |t3 p2 [7]) DE N 9 , DE N 9 = ( p4 p5 ) |t4 ( p1[14] p7 [7,7] |t2 p8 p6 ) ( p6 p8 ) |t1 ( p1 p5 ) .

32

Compunerea unui model de reea GeN, ce descrie funcionarea unui sistem de calcul cuaplicaii concurente real sau n curs de realizare, este deci un aspect crucial i mult mai dificil

dect verificarea i analiza lui (printr-o metod exact sau aproximativ) i interpretarea rezultatelor obinute. Cea mai mare dificultate rezid n faptul c procesele din cadrul unui sistem folosesc, la un moment dat, mai mult de o resurs de calcul O abordare practic pentru a conturna astfel de dificulti const n structurarea modelului de sistem, lund n consideraie abordarea complexitii sistemului prin partiionarea sa n subsisteme cooperante n [89, 111], este prezentat o metodologie de construire a modelelor de reele GeN descriptiv-compoziionale, ce exprim cooperarea proceselor de calcul. n mod general, pentru a descrie funcionarea unui sistem cu evenimente discrete, folosind formalismul GeN, modelarea const n a exprima, cu un anumit nivel de detaliere, comportamentul logic al interaciunii proceselor cooperante ale (sub)sistemului considerat. Avnd o descriere informal, aceasta implic faptul c la elaborarea modelului de reea GeN este indispensabil de a cunoate: structura, componentele sistemului, atributele i strile lor locale, care pot s le primeasc; condiiile i evenimentele ce pot schimba strile, fie c ele provin de la un proces aleatoriu, fie de la o decizie specificat; condiiile de sincronizare i cooperare, care determin ocurena unor evenimente, etc.; atributele calitative i cantitative ce determin restriciile de funcionare ale sistemului; specificaiile condiiilor interaciunii evenimentelor i nivelul de detaliere a modelrii, redate de o descriere informal a funcionrii sistemului considerat. ndat ce aceste elemente diferite sunt identificate, folosind atributele specificate, o descriere informal a proceselor interaciunii lor i un raionament adecvat, este posibil de a compune o expresie descriptiv a unei reele GeN, ce constituie o descriere logic a comportamentului sistemului de concurente considerat. Pentru a efectua compunerea modelelor sistemelor de concurente n form de expresii descriptive ale GeN, vom folosi urmtoarele abordri: 1. Se va determina nivelul de detaliere al sistemului i respectiv al modelului. Pentru aceasta se vor evidenia aparte acele componente ale sistemului, funcionarea crora poate fi reprezentat n forma de interaciunea unor procese cooperante, de sincronizare, replicare, etc.; 2. Pentru fiecare tip de elemente, componente se va descrie traseul procesului ce determin fazele de funcionare, strile locale respective, n care poate s se afle fiecare element i logica schimbrii acestor stri;

33

3. Se vor identifica starile locale ale procesului, specificnd astfel variabilele descriptive ce determin semantica elementelor, resursele alocate, relaiile temporale ale evenimentelor, pentru a accesa aceste stri; 4. Se vor determina atributele numerice pentru elementele de fiecare tip i starea lor iniial; 5. Pentru fiecare traseu al procesului ce determin schimbul de faze (stri locale) ale subsistemelor cooperante, folosind operatorii necesari, se va compune o expresie descriptiv care red o subreea GeN elementar, unde fiecrei faze (stri locale) a procesului i va corespunde o locaie, i schimbului de faze i va corespunde o tranziie specificat, iar numrul de elemente resurse n aceste faze corespunde numrului de jetoane n locaie cu capacitatea respectiv; 6. Se va determina semantica i atributele numerice ale locaiilor i tranziiilor subreelelorGeN, lund n consideraie politicile de executare a tranziiilor validate (declanarea prioritar,

funciile de gard, selectarea probabilistic, etc., dac ele sunt folosite n sistem); 7. Folosind operatorii respectivi i p L f i operaia de contopire a locaiilor i tranziiilor etichetate ce au aceeai esen semantic ale subreelelor GeN, redate de expresiile descriptive identificate, obinem modelul global al sistemului n form de reea GeN plat. Reeaua GeN astfel construit, urmnd metoda redat mai sus, descrie ntr-o form explicit cooperarea, paralelismul, concurena, excluderea mutual, sincronizarea i alte forme de interaciuni ale proceselor concurente ale sistemului modelat. Pentru efectua analiza proprietilor comportamentale dinamice i structurale ale modelelor de reele GeN astfel construite vom folosi metode i tehnici descrise n [11, 32], aplicnd un mediu instrumental [38, 47], de exemplu, VHPN elaborat i realizat de autor [38].Modelele matematice, n care unul sau mai muli parametri sunt definii prin distribuii de

probabilitate, impun o analiz stocastic [2].Reelele Petri stocastice reprezint, n general, un formalism mai adecvat pentru modelarea,

analiza corectitudinii prelucrrii distribuite i evaluarea performanelor sistemelor cu evenimente discrete. Utilizarea lor a condus la definirea unor noi extensii i construirea unor instrumentesoftware, care permit validarea i evaluarea modelului sau simularea, furniznd date referitoare

la funcionalitatea i performanele sistemului analizat . Tehnica de modelare i evaluare a performanelor este fondat pe folosirea reelelor GeN, subiacente reelelor Petri markoviene sau semimarkoviene. n prima etap, va fi efectuat analiza caracteristicilor comportamentale ale sistemului prin analiza proprietilor GeN, iar n a doua etap, prin evaluarea caracteristicilor de performan ale modelului.

34

2. Modelarea i evaluarea performanelor proceselor de calcul prin reele Petri generalizate markoviene2.1 Temporizarea stocastic a reelelor PetriTeoria reelelor Petri autonome trateaz ordinea evenimentelor i, n consecin, dinamica reelei este considerat ca o succesiune de evenimente (de tranziii) restrns numai la considerente de logic (o tranziie se poate declana numai dac este validat). n acest context ntrebarea ct timp consum un eveniment? nu se pune. Dar, pentru a rspunde la ntrebri relativ la performanele reelei i sistemului modelat cu reeaua (de pild, ct de repede poate produce sistemul?), este necesar a lua n consideraie timpul. Se pot asocia cu locaiile i cu tranziiile durate pe calea urmtoare:

durate asociate tranziiilor: durate care separ nceputul (consumul de jetoane din locaiile premrgtoare) i finalizarea aciunii (producerea de jetoane destinate locaiilor urmtoare), corespunztoare tranziiilor. Aceste durate au primit numele de timpi de aciune;

durate asociate cu locaiile: duratele minime pentru ca jetoanele s devin permanente ntro locaie, nainte de a fi capabile a contribui la validare (i declanarea) unei tranziii urmtoare. Duratele acestea se numesc timpi de ateptare. Se poate demonstra, c din punct de vedere putere de modelare, aceste dou tipuri de

temporizri sunt echivalente [11, 27]. n continuare, vom considera GeN temporizate, n care durate de timp sunt asociate cu tranziiile, deoarece specificul proceselor de calcul analizate este determinat de secvene paralele de evenimente i aciuni concurente. Modelnd procese reale, tranziiile GeN pot avea durate de timp de declanare cu valori concrete sau valori aleatoare, n ultimul caz este vorba despre GeN cu temporizare stocastic. Deci durata de timp asociat unei tranziii temporizate reprezint producerea unei activiti i respect o anumit distribuie de probabilitate corespunztoare duratei de timp considerate. Unele clase de reelele Petri stocastice (RPS) au fost definite pentru modelarea i rezolvarea problemelor de evaluare a performanelor sistemelor de producie, reele de telecomunicaii i ale sistemelor cu prelucrare distribuit a datelor [184, 203]. Reelele RPS, fiind unele dintre formalisme ale sincronizrii, actualmente, sunt utilizate, preponderent, din urmtoarele considerente [10]: pot fi exprimate sub forma unui limbaj paralel ori grafic bine adaptat la deprinderile utilizatorului;

35

extind regulile de funcionare a reelelor cu sisteme de ateptare (ReSA); evoluia jetoanelor n clasa particular a reelelor Petri, care constituie mainile de stri discrete, este identic cu acea de clieni ntr-o reea ReSA; permit obinerea automat a grafului de stri accesibile ale unui proces aleatoriu, oferind astfel o soluie sistematic a problemei de construire a spaiului discret de stri i schimbrii lor; interesul fa de RP, subiacente RPS, const n existena multor rezultate teoretice i practice, care le confer un loc preponderent n calitate de formalism de descriere a sincronizrii. Metodele de analiz, care au fost i sunt dezvoltate n cadrul teoriei reelelor RP i RPS particulare de diferite extensii, respectiv, ofer soluii unor probleme de modelare, validare calitativ i evaluare a performanelor diferitor sisteme cu evenimente discrete. n continuare, vom introduce reele GeN markoviene generalizate care vor fi folosite la modelarea i evaluarea performanelor proceselor ale sistemelor de calcul. Ipoteza principal, ce o vom reine, const n identitatea complet a proprietilor structurale ale GeN temporizate [107], deorece numeroase proprieti ale acestora se bazeaz pe proprietile calitative ale GeN ei subiacente. Este posibil de a defini numeroase interpretri ale temporizrii tranziiilor unei GeN (vezi [11,27]). n cadrul acestei lucrri adoptm urmtoarele interpretri:

o funcionare ct mai devreme, tradus prin ipoteza modelului concurenial [7], ceea ce

de fapt presupune, c ntr-un marcaj dat fenomenele active acioneaz n mod independent i c prima operaie ce sosete la termen este cea care provoac o schimbare de stare;

o temporizare a tranziiilor, traduse prin faptul c activitatea unui fenomen se o modelare explicit a sincronizrii: jetoanele nu sunt deci amorsate, n perioadele de

caracterizeaz prin posibilitatea de declanare a unei tranziii; activitate ale unui fenomen; aceast ipotez este esenial pentru a asigura identitatea proprietilor calitative ale reelei GeN. Astfel obiectul matematic RPS satisface cerinele criteriilor de temporizare definite mai sus [7]. La fiecare tranziie t j a reelei asocim o variabil aleatorie Z j , unde Z j reprezint o lucrare, care trebuie s fie realizat pentru ca o operaie s aduc i s produc declanarea acestei tranziii. Se presupune c funcia F j ( ) de repartiie a variabilei aleatorii Z j este continu. n fiecare marcaj M j , n care t j este declanabil, o anumit cantitate de lucru este realizat. Aceast cantitate, definit printr-o funcie G j ( M j , ) , depinde de durata de aflare n marcajul considerat. ndat ce lucrul cumulat LW j de la ultima declanare a t j pe una din traiectorii TW j

36

de secvene admisibile va atinge valoarea Z j , atunci tranziia se va declana i acest lucru va fi readus la zero. Ipoteza modelului concurent duce la considerarea c tranziia declanat n fiecare marcaj este acea, pentru care valoarea Z j este prima atins (funcionarea ct mai devreme). Notm, c ipoteza modelrii complete a sincronizrii de ctre RPS se traduce la cooperarea lucrrilor realizate n fiecare marcaj i pentru fiecare tranziie. Reelele RPS pot fi utilizate pentru obinerea unor rezultate numerice sub ipoteze teoretice cele mai generale. ns singura analiz numeric a unei atare tip de reele RPS, care, actualmente, pare posibil, poate fi efectuat prin simularea comportrii lor. Pentru obinerea unor modele analizabile printr-un calcul numeric este necesar de a considera unele submulimi de RPS astfel definite i anume: RPS markoviene sau RPS semimarkoviene.

2.2 Reele Petri generalizate markoviene2.2.1 Noiuni introductive i definiii

Dac toate funciile de repartiie ale variabilelor aleatorii U j ,M i sunt exponenial-negative, procesul de marcare M ( ) al RPS este descris de un proces Markov n timp continuu omogen. Datorit faptului absenei de memorie a legii exponenial-negative, la fiecare instantaneu, are locpierderea memoriei lucrrilor cumulate [181]. n acest caz vom avea urmtoarele funcii de

repartiie a duratei aleatorii: U j ,M i : f j ( M i , ) = 1 exp( j ( M i ) ) , unde j ( M i ) este rata de declanare a tranziiei t j . Astfel obinem reele Petri generalizate markoviene (RPM), care sunt analizabile.Definiia 2.1. O reea Petri generalizat markovian, abreviat RPM, este sistemul redat de

ctre cuplul de obiecte NM=, unde: N este o reea GeN marcat definit n conformitate cu Definiia 1.2; : T IN t T (M )| P| +

IR + este funcia ce determin rata (t , M ) de declanare a tranziiei validate

n marcajul M, adic parametrul legii exponenial-negative, astfel nct

0 (t , M ) < + . IR + este mulimea mrimelor reale nenegative.

Pentru a reda compoziionalitate reelelor RPM vom folosi noiunea de dexel stocastic

bMDE al bNM:bMDE =< bDE , { j , k } > =j j gj tj

|

m0i ki yii [Wi + ,Wi ] kk | kk , { j , k } > . g t

n general, dac funcionarea unui sistem este descris de ctre un proces Markov sau semimarkovian n timp continuu ce determin un lan Markov n timp continuu (LMTC) simplu 37

sau inclus cu o comportare ergodic, atunci el determin existena unui regim staionar i se poate efectua estimarea valorilor medii ale caracteristicilor numerice de performan ale sistemului. Un regim staionar de funcionare al unui sistem este un astfel de regim, n care evoluia sa n timp nu depinde de condiiile iniiale de demarare a procesului i nu depinde de momentul de timp considerat. Dac LMTC este ireductibil - recurent - nenul, adic toate strile pot fi atinse ntr-o durat de timp finit din orice stare, atunci exist o distribuie staionar a probabilitilor de aflare n strile respective [181, 183]. n continuare, ne vom interesa de indicatori de performan ai funcionrii sistemului n perioade de timp destul de mari, unde efectele regimului tranzitoriu sunt neglijate. Dac sistemul are o caracteristic de degradare progresiv a funcionrii, atunci evaluarea acestor indicatori de performane poate fi efectuat la fiecare nivel de degradare dup efectele tranzitorii, ca rezultat al unor ocurene de cdere n pan sau erori. n majoritatea cazurilor, evaluarea indicatorilor de performan se va efectua n regim staionar de funcionare al sistemului modelat cu RPM. Sistemul modelat cu o RPM are un regim staionar de funcionare, dac reeaua GeN subiacent este mrginit, viabil i, n plus, dac reeaua este reiniializabil, atunci sistemul nu va avea marcaje tranzitorii [8, 107]. Aceste trei proprieti comportamentale ale GeN garanteaz faptul c graful de marcaje accesibile sau de acoperire este un graf tare conex i, n consecin,LMTC respectiv este izomorf comportrii stocastice a reelei R