Analiza Si Proiectarea Sistemelor Concurente

CUPRINS

=== l ===

CUPRINS

1. Introducere 3

2. Modele obiect de concurență 6

2.1. Clasificări și caracteristici generale 6

2.2. Metode de analiză și proiectare orientată-obiect concurentă 14

Metoda Eiffel// 15

Ciclul de viață al obiectelor (Object Life-Cycles) 16

Diagrame de tranziție a stărilor 17

Hărți de obiecte (Objectcharts) 18

Analiza sistemelor orientate-obiect (OSA) 18

ObjChart 19

Intermediate Object Notation – ION 19

MOSES 20

UML 21

3. Modelarea comportamentului obiectelor active 25

3.1. Hărți de stări 26

3.2. Specificarea UML a diagramelor de tranziție a stărilor 30

4. Modelarea diagramelor de tranziție a stării 37

4.1. Metamodele statice ale diagramelor de tranziție a stării 38

Modelarea diagramelor de stări în UML 38

Modelarea diagramelor de stări în Rocase 40

4.2. Formalizarea diagramelor de stări 42

5. Bibliografie 51

1. Introducere

În ultimele două decenii proiectarea de modele obiect având trăsături legate de concurență a reprezentat o preocupare constantă în lumea informaticii. Cel puțin două motive importante stau la baza acestui fapt. Pe de o parte, ca efect al progreselor tehnologice obținute, în această perioadă au fost proiectate o multitudine de limbaje de programare orientate-obiect care iau în considerare aspecte legate de executarea în paralel a unor activități (peste 100 de astfel de limbaje au fost analizate și sistematizate în [PHI95]). Pe de altă parte, este cunoscut faptul că programarea orientată pe obiecte s-a dezvoltat având ca și model lumea înconjurătoare (privită ca o multitudine de obiecte între care există diverse relații și care comunică între ele prin intermediul mesajelor). În lumea reală însă, obiectele sunt în mod natural concurente, ceea ce conduce la tendința firească de a transpune acest lucru și în programare.

Este interesant cum două criterii distincte, unul obiectiv (determinat de creșterea performanțelor și a complexității sistemelor de calcul) și altul subiectiv (determinat practic de "bun simț", care ne îndeamnă să rezolvăm diverse probleme abstracte căutând similarități cu lumea reală) au condus în final la dezvoltarea unor concepte, a unor tehnici de programare și implicit a unor metode de analiză și proiectare de aplicații eficiente.

Programarea concurentă a apărut înaintea programării orientate obiect. Ea a fost aplicată prima dată în cadrul limbajelor procedurale unde principalele probleme studiate au fost cele legate de sincronizarea execuției paralele a unor secvențe de instrucțiuni și de transmiterea de informații între mai multe activități (procese) concurente.

Odată cu apariția programării orientate obiect modalitatea de realizare a programelor informatice a cunoscut un salt calitativ semnificativ. Astfel, dezvoltarea acestor programe (sau aplicații) nu mai implică descompunerea problemelor în unități algoritmice (proceduri) ci în obiecte independente care interacționează între ele.

Ideea introducerii de trăsături de concurență în programarea orientată-obiecte este pe cât de atractivă pe atât de dificil de realizat. Astfel majoritatea limbajelor de programarea orientate-obiect concurente dezvoltate până în prezent nu au reușit să combine aceste două concepte astfel încât să permită realizarea unui grad ridicat de paralelism fără a afecta, uneori dramatic, trăsăturile fundamentale ale programării orientate obiect. Unul dintre cele mai importante conflicte care apar în cadrul acestor limbaje este acela dintre concurență și moștenire, conflict care a fost tratat pentru prima dată în [MAT93] unde a fost referit ca anomalie de moștenire. Acest conflict a constituit și subiectul primului referat de doctorat al autorului [SUC98] în cadrul căruia au fost identificate tipuri de conflicte similare dar cu un grad mai ridicat de generalitate și care au fost denumite aici anomalii de reutilizare.

Problema integrării concurenței în cadrul programării orientate obiect a reprezentat preocuparea principală a mai multor cercetători. De asemenea au fost dezvoltate mai multe modele obiect pentru concurență ([SHL88], [ELI92], [BER94], [PAP96], [RAT97], [HEN97]) și au fost depuse eforturi pentru clasificarea acestora ([PAP92], [BER94]).

Prezentul referat își propune să trateze modelarea aspectelor de concurență în cadrul metodele de analiză și proiectare orientate obiect existente.

În cadrul secțiunii a doua este realizată o trecere în revistă a principalelor modele obiect dezvoltate până în prezent insistând asupra aspectelor de concurență specifice. În centrul atenției acestei analize se va afla limbajul UML (Unified Modeling Language – [RAT97]) care reprezintă metoda de analiză și proiectare orientată obiect acceptată ca standard de OMG.

Secțiunea a treia a lucrării este dedicată aspectelor de modelare dinamică a comportamentului obiectelor, realizându-se o descriere a diagramelor de tranziție a stărilor (statecharts) așa cum au fost prezentate în [HAR87] și a modului în care aceste diagrame au fost integrate în UML.

În acest sens se vor propune mai multe modificări (extensii și constrângeri) ale diagramelor de stări descrise în UML, precum și un metamodel static al acestora.

Modelul diagramelor de stări descris în secțiunea a patra este parțial implementat în cadrul intrumentului CASE de analiză și proiectare orientată obiect Rocase, care a fost realizat in cadrul Laboratorului de Cercetare în Informatică al Universității "Babeș-Bolyai" din Cluj-Napoca.

În finalul secțiunii a patra va fi prezentată și o modalitate de formalizare a acestor diagrame, având la bază rezultatele obținute în [GIR97].

2. Modele obiect de concurență

În această secțiune vom realiza un studiu asupra metodelor de analiză și proiectare orientate obiect dezvoltate până în prezent care conțin elemente de modelare a concurenței. Aceste elemente pot fi clasificate în două categorii distincte și anume:

elemente care au în vedere suportul metodologic

aspecte privind notația utilizată .

Scopul modelelor obiect pentru concurență este acela de a integra într-un model de programare unic trăsături ale programării orientate obiect (clasă, moștenire etc) și trăsături de concurență (cum ar fi inițierea paralelismului sau sincronizarea). Multitudinea de modele obiect dezvoltate până în prezent a permis determinarea unor categorii distincte de astfel de modele luind în considerare mai multe aspecte.

Clasificările redate mai jos au la bază în principal studiile realizate în [PAP92], [PHI95], [BER94] și [MAI97]. Dacă în primele două lucrări sunt tratate doar aspectele privind suportul metodologic (ele având ca obiectiv clasificarea și proiectarea de limbaje de programare orientate-obiect concurente), următoarele două tratează și notațiea utilizată pentru aplicarea metodologiei.

2.1. Clasificări și caracteristici generale

Vom enumera în cele ce urmează câteva dintre caracteristicile pe care Bergmans în [BER94] consideră că trebuie să le întrunească o metodă pentru analiza și proiectarea orientată-obiect a aplicațiilor concurente. Aceste caracteristici sunt în mare parte valabile și numai în cazul aplicațiile orientate-obiect secvențiale, mai ales cele care se referă la notația utilizată de către o metodă.

Prima și cea mai importantă caracteristică pe care trebuie să o dețină o astfel de metodă constă, evident, în posibilitatea modelării și rezolvării aspectelor legate de concurență. Aceasta este una dintre caracteristicile pe care majoritatea metodelor de analiză și proiectare dezvoltate până în prezent nu o au în adevăratul sens al cuvântului.

Deși tratarea elementelor de concurență și sincronizare este specifică modelării dinamice a unui sistem, se știe că luarea în considerare a acestor elemente poate afecta structura statică și relațiile dintre elementele acestuia. Astfel, aspecte ca specificarea și moștenirea constrângerilor de sincronizare, tratarea concurenței intra-obiect și inter-obiect sau comunicarea inter-procese sunt elemente care trebuie să fie tratate și integrate cât mai natural în cadrul unei metode.

În acest context, o altă caracteristică importantă a metodelor de dezvoltare a aplicațiilor orientate obiect concurente și care este strâns legată de cea amintită anterior, se referă la integrarea concurenței cu conceptele orientate-obiect. Cu alte cuvinte, metoda trebuie să păstreze și în cazul obiectelor dinamice (active) sensul și trăsăturile pe care concepte cum ar fi încapsularea, moștenirea, polimorfismul sau transmiterea de mesaje le aveau în cazul secvențial. Mai mult, este deosebit de util ca metoda să permită aplicarea acestor concepte și asupra unor elemente legate strict de concurență, cum ar fi de exemplu reutilizarea constrângerilor de sincronizare.

Acest ultim exemplu introduce o altă trăsătură foarte importantă care trebuie să caracterizeze o metodă, și anume să ofere suport pentru reutilizarea softului. Acest lucru poate fi realizat prin punerea la dispoziția dezvoltatorilor de soft a unor modalități de construcție a obiectelor reutilizabile pe de o parte, și prin furnizarea de tehnici de obținere a reutilizabilității pe de altă parte. Acest lucru este deosebit de important și util mai ales în cazul dezvoltării de aplicații concurente, deoarece aspectele dinamice ale acestora sunt mult mai dificil de analizat, specificat și implementat, și prin urmare este cu atât mai utilă reutilizarea unor componente deja existente.

Suportul pentru dezvoltarea iterativă și capacitatea unei metode de a fi cât mai intuitivă reprezintă alte două caracteristici importante care, după cum bine se știe, au fost în centrul atenției la dezvoltarea metodelor de dezvoltare orientată-obiect a softului secvențial. Cu atât mai mult aceste două caracteristici trebuie să fie prezente în cazul tratării concurenței, deoarece modelele dezvoltate în acest ultim caz au un grad mai mare de complexitate. În plus, experiența a arătat că aspectele legate de concurență și sincronizare sunt tratate după ce a fost realizat modelul static, și uneori și cel comportamental (secvețial), lucru care necesită reluarea analizei modelului și care implică, deci, un proces iterativ de dezvoltare.

Bineînțeles, calitatea unei metode de a fi intuitivă depinde în mare măsură și de notația grafică utilizată de aceasta. Au fost propuse mai multe condiții care trebuie respectate atunci când este stabilită notația pentru o anumită metodă, astfel încât ea să contribuie cât mai mult la o bună înțelegere a modelelor realizate. Dintre acestea următoarele șase se disting ca fiind cele mai importante:

notația trebuie să fie compusă dintr-un număr redus de simboluri de bază;

modelele realizate trebuie să poată fi desenate cu ușurință (cu mâna sau folosind instrumente automate);

notația trebuie să fie intuitivă, sau mai precis, impactul vizual al unui model realizat din diverse simboluri de bază ale notației trebuie să sugereze cât mai bine semantica acestui model;

trebuie evitat ca simbolurile alese să conducă la o notație ambiguă;

este posibilă aplicarea elementelor notației polimorfic altor elemente;

notația trebuie să fie expresivă (de ex. comparativ cu codul sursă).

Figura 2.1. Notații grafice pentru reprezentarea claselor/obiectelor active în

a) ION, b) UML, c) MOSES, d) ESA-HOOD

Nu am luat în discuție aspectele legate de implementarea efectivă a aplicațiilor pe baza modelelor realizate cu ajutorul unei metode de analiză și proiectare. În [BER94] Bergmans consideră că o calitate foarte importantă a unei metode ar fi aceea de a reduce cât mai mult dificultățile de implementare, el sugerând în acest sens dezvoltarea de metode în care implementarea modelelor într-un limbaj de programare particular (a conceptelor statice și de bază) să reprezinte în mare parte o activitate automată. De asemenea, din punct de vedere al notației, Bergmans consideră că ea trebuie să dețină semantici bine definite, astfel încât modelele realizate cu o astfel de notație să poată fi "translatate" cu mai multă ușurință în modele de implementare.

După cum se știe însă, în prezent există o mulțime foarte mare de limbaje de programare orientate-obiect concurente (în [PHI96] au fost analizate și clasificate peste 100 de astfel de limbaje), fiind implementate o diversitate de mecanisme de specificare a concurenței și de comunicare și sincronizare între activitățile concurente. Prin urmare, pentru a respecta pricipiul de mai sus, atunci când este realizată o metodă este necesar să se aleagă un limbaj de programare particular care să fie luat ca model și ale cărui mecanisme de specificare a concurenței, de sincronizare și de comunicare să fie transpuse (aproape) întocmai în cadrul metodei (Bergmans, de exemplu, a pornit de la limbajul SINA).

Această abordare este destul de restrictivă, și impune într-o oarecare măsură ca o metodă să se conformeze limitărilor pe care le are respectivul limbaj de programare. Considerăm că este mult mai potrivit ca modelarea aspectelor de concurență să fie realizată independent de un limbaj de programare particular, urmând bineînțeles ca implementarea să se realizeze cu un grad de dificultate corespunzător diferențelor dintre metodă și limbajul ales. Astfel metoda va putea fi utilizată pentru realizarea de modele cu un grad sporit de generalitate, urmărindu-se la dezvoltarea ei să fie respectate cele patru principii enunțate în [PHI95] care stau la baza evitării conflictelor dintre conceptele orientate-obiect și cele de concurență:

sincronizarea se realizează la nivelul obiectului apelat,

existența concurenței intra-obiect, a execuției dependente de stare și de istoric,

separarea sincronizării (realizarea unei distincții clare între descrierea sincronizării și descrierea funcționalității unei metode sau acțiuni)

posibilitatea izolării sincronizării (adică permiterea moștenirii separate a codului pentru sincronizare și a codului de descriere a funcționalității)

După cum s-a arătat în [SUC98a] nici unul dintre mecanismele de sincronizare și comunicare implementate în limbajele de programare orientate-obiect imperative existente până în prezent nu urmează în totalitate aceste patru principii. În cele mai multe cazuri s-a renunțat chiar la concepte fundamentale (cum ar fi moștenirea sau concurența intra-obiect) pentru a se evita apariția de conflicte între mecanismele orientate-obiecte și cele ale programării concurente. Unul dintre conflictele de acest gen cel mai atent studiate este .anomalia de moștenire [MAT93].

În opinia lui L. Bergmans o metodă de analiză și proiectare de aplicații orientate-obiect concurente nu trebuie să aibă în vedere în special specificarea comportamentului actual al obiectelor (specificarea secvenței de evenimente). În schimb, se va acorda o atenție mai mare constrângerilor care trebuie să fie satisfăcute pentru a se garanta consistența obiectelor sau a sistemului din care fac parte acestea. Astfel, Bergmans în metoda dezvoltată în [BER94] ia în considerare un (sub)sistem format dintr-o mulțime de obiecte și o mulțime de fire de execuție care execută metodele acestor obiecte. În principiu nu vor exista restricții asupra numărului proceselor care pot fi active la un moment dat într-un obiect; de asemenea numărul de procese și numărul de obiecte poate varia în cadrul unui sistem.

Descrierea completă a unui astfel de sistem nu reprezintă un proces simplu. O primă problemă se referă la nivelul la care este realizată această descriere: la nivel global sau pe anumite componente (module, obiecte etc). Descrierea la nivel global a unui sistem informatic bazat pe obiecte concurente nu este deloc potrivită, în primul rând datorită faptului că multe dintre părțile sale se pot modifica sau extinde de-a lungul dezvoltării, lucru care va afecta implicit și descrierea globală. În al doilea rând, descrierea globală a sincronizării, de exemplu, este foarte dificilă datorită faptului că trebuie avut în vedere sistemul poate cunoaște modificări și în timpul execuției sale, prin distrugerea unor obiecte existente sau crearea altora noi.

Având în vedere acest lucru L. Bergmans este de părere că o metodă de analiză și proiectare a unei aplicații orientate – obiect concurente trebuie să aibă la bază următoarele afirmații:

descrierea aspectelor dinamice trebuie să fie făcută la un nivel mai ridicat din punct de vedere al descompunerii sistemului și nu la nivel global. Modelarea comportamentului la nivelul obiectelor, de exemplu, cu luarea în considerare a constrângerilor de sincronizare pare a reprezenta o alegere bună (deși în unele cazuri nici acest nivel de detaliere nu este suficient)

trebuiesc descrise constrângerile minime care să fie satisfăcute astfel încât să se asigure consistența, oferindu-se posibilitatea apariției unui număr infinit de secvențe de evenimente. Secvențele de evenimente posibile vor putea fi mai apoi restrânse de implementarea metodelor sau de configurația obiectelor.

Majoritatea metodelor de analiză și proiectare a obiectelor concurente au ca și scop determinarea cât mai riguroasă a unor astfel de secvențe, bazându-se pe specificarea relațiilor de cauzalitate dintre evenimente. Pe de altă parte există abordări care încearcă să surprindă doar constrângerile necesare fiecărei componente din sistem (este și cazul [BER94]) argumentând că în acest fel componentele sunt mai puțin dependende de un context particular.

Este evident faptul că o metodă de analiză și proiectare de aplicații orientate obiect concurente trebuie să ofere un model obiect care să asigure respectarea celor patru principii de mai sus. Bineînțeles, alegerea limbajului de programare pentru implementarea aplicației va determina în mod inevitabil deprecierea anumitor caracteristici calitative deținute de modelul inițial.

Un prim aspect deosebit de important care caracterizează modelele obiect de concurență este dat de natura relației dintre obiectele unui sistem și firele de execuție. Din acest punct de vedere există trei abordări: ortogonală, omogenă și heterogenă.

În abordarea ortogonală obiectele și firele de execuție sunt independente. Implicit obiectele nu sunt protejate sub nici o formă de apeluri concurente ale metodelor proprii (în orice moment un obiect va putea fi apelat din cadrul oricărui fir de execuție). Prin urmare protejarea stării interne a obiectelor de execuțiile concurente ale propriilor metode va trebui să fie realizată explicit de către programator (prin intermediul unor mecanisme de sincronizare de nivel scăzut, specifice limbajelor de programare procedurale cum ar fi semafoarele sau regiunile critice condiționale).

Abordarea omogenă introduce un concept nou, și anume acela de obiect activ. În funcție de punctele de vedere ale autorilor care le-au caracterizat, obiectele active au cunoscut mai multe definiții. Una dintre definițiile cele mai des întâlnite este aceea că un obiect activ reprezintă un obiect în cadrul căruia pot exista două sau mai multe fire de execuție (cu alte cuvinte, metodele obiectului se pot executa în fire de execuție distincte). Ulterior a fost adoptată o definiție mai completă în care obiectele active sunt privite ca obiecte ce pot controla și planifica execuția propriilor metode. Astfel, obiectele dețin fire de execuție proprii care (în majoritatea modelelor obiect omogene) sunt create implicit atunci când este recepționat un mesaj. Astfel de obiecte pot sau nu să fie protejate implicit de invocări concurente din exterior și conțin mecanisme specifice pentru protejarea explicită a stării interne (mulțimi de activare, condiții de activare, gărzi de metode, etc).

Abordarea eterogenă permite existența în cadrul unui sistem a două tipuri de obiecte: active (având înțelesul descris mai sus) și pasive. Obiectele pasive nu dețin fire de execuție proprii, nu sunt protejate (implicit sau explicit) de apeluri concurente din exterior iar propriile metode sunt executate în cadrul firelor de execuție ale obiectelor care le apelează. În modele obiect eterogene există trei tipuri de abordări ale obiectelor pasive.

Un prim caz ar fi acela în care în obiectele pasive nu poate exista mai mult de un fir de excuție în orice moment de timp (astfel de obiecte sunt echivalente obiectelor existente în cadrul limbajelor de programare secvențiale). Un al doilea caz este acela al obiectelor pasive partajate, care permit executarea în interiorul lor a mai multor fire de control și care pot fi apelate de către orice alt obiect din sistem (activ sau pasiv). In fine, al treilea caz este cel al obiectelor pasive care reprezintă "proprietatea" unui obiect activ. În acest ultim caz obiectele pasive nu pot fi apelate decât de către obiectele active care le dețin (și care vor realiza și protejarea acestora).

Un alt criteriu de clasificare a modelelor obiect pentru concurență este dat de tipul de concurență internă a obiectelor. Din acest punct de vedere există modele cu cu obiecte secvențiale, cvasi-concurente și concurente.

Modelele cu obiecte secvențiale nu permit execuția a mai mult de un fir de execuție în interiorul unui obiect. Mai mult, toate mesajele care sunt recepționate in timpul execuției unei metode vor fi luate în considerare abea după ce execuția respectivei metode a luat sfârșit. Se poate spune că în cazul acestor tipuri de modele nu există concurență internă.

Modelele cu obiecte cvasi-concurente sunt caracterizate de faptul că obiectele pot deține mai multe fire de execuție, însă numai unul dintre acestea este activ la un moment dat. De asemenea, există posibilitatea ca la un moment dat firul de execuție activ să fie blocat și să se realizeze activarea unui alt fir de execuție aflat în așteptare.

Modelele cu obiecte concurente sunt cele "ideale" ele permițând existența a mai mult de un fir de execuție în interiorul unui obiect. Firele de execuție pot fi create atât implicit cât și explicit. Cele implicite sunt create în momentul recepționării unui mesaj, când în cadrul noului fir de execuție este executată metoda corespunzătoare mesajului. Crearea explicită de fire de execuție se realizează prin intermediul așa-numitelor mecanisme de inițiere a concurenței [SUC98]. Majoritatea modelelor obiect pentru concurență propun crearea implicită a firelor de execuție. Modelele care folosesc cea de-a doua variantă utilizează mecanisme preluate din limbajele de programare procedurală (fork-join, parbegin-parend etc).

Un ultim criteriu de clasificare a modelelor este legat de caracteristicile mecanismelor de specificare a interacțiunii (sincronizare sau comunicare) dintre obiectele concurente. Așa cum am arătat, obiectele comunică între ele prin intermediul transmiterii de mesaje. Din punct de vedere al sursei mesajului interacțiunea (comunicarea) poate fi unidirecțională (fără primirea unui răspuns) sau bidirecțională (obiectul căruia îi este destinat mesajul răspunde mesajului obiectului sursă). În acest ultim caz se pune problema dacă obiectul sursă așteaptă răspunsul (situație comună programării orientate-obiect) sau își continuă activitatea, urmând a lua în considerare răspunsul într-o fază ulterioară (cazul variabilelor future de exemplu).

Din perspectiva obiectului destinație, interacțiunea cu obiectul sursă este privită prin prisma acceptării mesajului transmis de acesta și a modalității în care se realizează acceptarea.

Dacă interacțiunea dintre obiecte este controlată direct de către sistem, fară a se putea specifica explicit, prin mecanisme oferite de limbaj, constrângeri privind această interacțiune, modelul este cu control extern (modele cu monitoare). Următoarea categorie este aceea a modelelor cu control mixt, în care responsabilitatea coordonării interacțiunilor între activitățile concurente ale obiectelor este împărțită între sistem și impementarea obiectelor respective (modelele cu actori, metode gardate, mulțimi de acceptare, etc). În fine, din cea de-a treia categorie fac parte modelele cu control reflectiv, în care constrângerile de sincronizare sunt exprimate cu ajutorul unei meta-clase.

2.2. Metode de analiză și proiectare orientată-obiect concurentă

Metodele de analiză și proiectare orientată-obiect existente în prezent abordează în mod diferit modelarea concurenței în principal în ceea ce privește următoarele două aspecte:

suportul metodologic privind comportamentul dinamic;

notația și modelul de reprezentare a comportamentului dinamic.

Din punct de vedere al suportului metodologic pentru dezvoltarea aplicațiilor orientate-obiect concurente rezultatele sunt până în prezent destul de modeste. Practic nu există până în prezent un suport metodologic clar și o notație pentru tratarea sincronizării obiectelor.

Majoritatea metodelor de dezvoltarea a aplicațiilor orientate obiect se concentrează asupra modelării relațiilor de cauzalitate dintre evenimente. Astfel de metode (OMT – [RUM91], OOD [BOO90], OOA&D [SHL88], Objectory [JAC92], sau cele derivate din acestea, Syntropy [COO94] și UML [RAT97]) realizează acest lucru construind un model bazat pe mașinile cu stări finite sau pe hărțile de stări. O problemă comună acestor abordări este aceea că modelele de stări propuse au o putere de modelare insuficientă și nu sunt integrate perfect cu elemente conceptuale de bază orientate obiect (cum ar fi moștenirea). În plus, modul în care diagramele de stări se concretizează în faza de implementare a aplicației reprezintă deocamdată un subiect de studiu ([SCU97]), în cadrul majorității metodelor acest aspect nefiind definit sau realizându-se o integrare improprie a sa în cadrul obiectelor aplicației. Din punct de vedere al concurenței și a sincronizării și comunicării între procesele concurente, majoritatea metodelor nu oferă instrumente de tratare a acestora, ele putând fi utilizate cu succes doar în cazul implementării aplicațiilor în limbaje de programare orientate-obiect concurente care dețin mecanisme de sincronizare cu control extern (ex. monitoare).

În cele ce urmează vor fi trecute în revistă metodele semnificative dezvoltate până în prezent insistând în primul rând pe aspecte metodologice de modelare a concurenței și pe cele privnd notația utilizată. Nu vom discuta în cadrul acestui referat elemente specifice analizei și proiectării sistemelor distribuite, cum ar fi partiționarea, alocarea la noduri fizice, migrarea și replicarea obiectelor sau securitatea comunicării.

Metoda Eiffel//

Această metodă este bazată pe modelul de programare din Eiffel// dezvoltat de Denis Caromel și descris în [CAR90]. Această metodă poate fi descrisă pe scurt prin enumerarea pașilor de dezvoltare tratați în cadru ei, și anume:

1. Proiectare și programare secvențială: aici sunt adoptate tehnicile orientate obiect convenționale

2. Identificarea proceselor: metoda asociază claselor descrieri de procese (corespondent al rutinelor de vitalizare). Aici se analizează care dintre clasele secvențiale vor trebui să conțină o astfel de activitate inițială, după care se vor lua toate obiectele care pot fi partajate de două sau mai multe astfel de clase proces. Obiectele găsite vor determina la rândul lor considerarea claselor din care fac parte ca și clase proces (deoarece reprezintă singura modalitate ca acestea să poată sincroniza cereri venite din exterior).

3. Programarea proceselor: cea mai importantă activitate a acestui pas este (re)definirea rutinelor de vitalizare care determină controlul și sincronizarea proceselor. O observație importantă este aceea că orice modificare a acestora atrage după sine redefinirea completă a rutinei de vitalizarea pentru toate clasele derivate.

4. Adaptarea la constrângeri: acest pas se referă în primul rând la modificări aduse sistemului pentru a putea fi modelate specificații de timp real. Sunt luate în considerare aspecte privind asocierea proceselor (obiectelor) la procesoare și definirea de noi procese pentru gestionarea (stocarea și distribuirea) activităților și pentru priorități diferite. Acest pas este unul tipic iterativ de "reglare" a sistemului.

Metoda Eiffel// nu conține nici un suport (notațional sau de altă natură) pentru derivarea constrângerilor de sincronizare.

Ciclul de viață al obiectelor (Object Life-Cycles)

Această metodă propusă în [SHL88] este constituită din două submetode complementare, una privind modelarea statică și cea de-a doua modelarea dinamică a sistemelor orientate obiecte, ele fiind descrise de către autori la momente de timp diferite. Cele mai importante componente ale acestei metode sunt modelele de informații, modelele de stări și modelele de procese.

Modelele de informații sunt similare cu diagramele entitate-relație clasice și realizează o descriere statică a unui sistem. Modelele de stări descriu ciclul de viață al unor obiecte și relații individuale și ele reprezintă mașini de stări finite. Fiecărei stări îi este asociată o acțiune care este realizată atunci când, în urma apariției unui eveniment, se intră în starea respectivă. Acțiunile pot genera la rândul lor noi evenimente care pot fi destinate altor obiecte. Aceste interacțiuni între obiecte sunt descrise într-un model de comunicare între obiecte, iar acțiunile sunt detaliate într-un model de flux de date (adică un model de procese). Accesul detelor între obiecte rezultat este descris de un model de acces la obiecte, care reprezintă la rândul său un model de procese.

Modelele de stări pentru obiecte descriu relațiile cauzale dintre acțiuni (ele nu dețin informații privind concurența sau sincronizarea). De asemenea, modelele de stări pot fi aplicate relațiilor dintre obiecte (numite obiecte relație). Pentru a trata evenimentele concurente, aceste obiecte pot fi transformate în construcții de tip monitor care vor serializa evenimentele. Modelele de stări pot fi descrise aici atât folosind o notație grafică cât și prin intermediul unor tabele echivalente de tranziție a stărilor.

Relativ la problemele legate de inițierea și coordonarea proceselor concurente, alături de construcțiile de tip monitor amintite mai sus, metoda mai permite specificarea creerii de fire de execuție. În faza de proiectare, metoda identifică trei tipuri de clase, și anume clase pasive, active și assigner.

Clasele pasive sunt cele care nu au asociat un model de stări și corespund unei clase secvențiale convenționale. Clasele active au asociat un model de stări (implementatarea acestui model de stări se face moștenind de la clasa abstractă Active_Instance – această clasă furnizează o interfață către un obiect care simulează o mașină finită de stări; prin intermediul uni inițializări corespunzătoare, fiecărui eveniment recepționat obiectul care simulează mașina de stări determină noua stare). Clasele assigner sunt similare cu clasele active, ele însă conținând numai un model de stări.

În concluzie, deși este oferită o manieră completă și pramatică de analiză a sistemelor, metoda nu poate fi utilizată pentru a se modela constrângeri de sincronizare complexe și furnizează doar un suport parțial pentru realizarea modelelor de stări. De asemenea , metoda nu oferă suport pentru implementarea și sincronizarea firelor de execuție concurente.

Diagrame de tranziție a stărilor

Există diverse abordări de modelare a compotamentului dinamic al obiectelor (comportament privit prin prisma relațiilor cauzale dintre acțiuni). Practic toate abordările se bazează într-un anumit fel pe mașinile cu stări finite, care descriu o mulțime de stări în care se poate afla un sistem la un moment dat și tranzițiile posibile între aceste stări. Din punct de vedere grafic, un arc orientat de la starea A la starea B descrie un eveniment care a determinat tranziție de la starea A la starea B. Exită două abordări distincte ale mașinilor de stări în funcție de modul de adăugare a acțiunilor:

modelul Moore, în care acțiunile sunt atașate la intrarea într-o nouă stare,

modelul Mealy, în care acțiunile sunt asociate tranzițiilor.

De notat că mașinile de stări definesc relațiile cauzale dintre evenimente succesive, ceea ce nu reprezintă același lucru cu descrierea constrângerilor de sincronizare între acțiuni.

Hărțile de stări reprezintă o abordare importantă, expresivă și intuitivă a modelării relațiilor cauzale între evenimentele unui sistem. Acest lucru a determinat ca ele sa reprezinte modelul și notația alese în cazul unei game largi de metode de dezvoltare a softului.

Diagramele de tranziție a stărilor vor fi tratate în detaliu în cadrul secțiunilor trei și patru.

Hărți de obiecte (Objectcharts)

În [COL92] a fost prezentată o notație pentru specificarea comportamentului obiectelor, numită Objectcharts (hărți, sau diagrame, de obiecte). Hărțile de obiecte aunt bazate pe hărțile de stări ale lui Harel dar nu adoptă mecanismul de broadcast, și integrează tranzițiile cu invocarea mesajelor (modelul cerere-răspuns) din modelul orientat obiect. Hărțile de obiecte furnizează o notație grafică la care se adugă detalii prin intermediul specificărilor formaleale tranzițiilor și ale invarianților (de stare).

Un aspect interesant privitor la aceste hărți de obiecte este că modelul permite descrierea comportamentului sistemului prin descrierea interacțiunilor dintre obiecte. O primă restricție a acestui model este aceea că numărul de obiecte al sistemului este fix (nu poate fi adăugat sau distrus nici un obiect în timpul rulării). Alte restricții sunt legate de inexistența specificării unei modalități de moștenire a hărților de obiecte sau de imposibilitatea transmiterii de mesaje spre alte obiecte în timpul execuției unei metode.

Analiza sistemelor orientate-obiect (OSA)

În OSA (Object-oriented Systems Analysis descrisă în [BER94]) pentru modelarea comportamentului dinamic al sistemelor se folosește o notație numită rețea de stări. Rețelele de stări reprezintă o extensie a diagramelor de tranziție a stărilor, iar dintre cele mai importante caracteristici ale acestora amintim:

o tranziție este formată dintr-o condiție și o acțiune. O tranziție va avea loc doar atunci când condiția asociată ei este satisfăcută. De asemenea tranziția nu este considerată ca fiind atomică, adică ea se va realiza într-o anumită perioadă de timp (în care este executată acțiunea care îi este asociată)

modelul permite specializarea rețelelor de stări în subclase

o tranziție poate avea mai multe stări de pornire și stări țintă. Acest lucru oferă posibilitatea definirii sincronizărilor (de exemplu, o tranziție poate avea loc doar atunci când obiectul se află în toate stările de pornire). De asemenea poate fi modelată concurența intra-obiect permițând ca după efectuarea unei tranziții obiectul să se afle în mai multe stări din care ulterior pot avea loc independent noi tranziții.

modelul aferă posibilitatea tratării excepțiilor și specificarea de constrângeri de timp-real.

Modelul OSA are o putere deosebită de analiză, dar din păcate nu este foarte clar definită modalitatea de tranziție de la un model de analiză la un model de proiectare și, eventual, la implementare.

ObjChart

ObjChart reprezintă un formalism vizual pentru specificarea obiectelor și a comportamentului lor reactiv. Aici un sistem este privit ca fiind format dintr-o colecție de obiecte care comunică asicron și care sunt reprezentate într-o ierarhie de tip parte-intreg (moștenirea nu este modelată). La rândul său, fiecare obiect din sistem deține o mașină finită de stări care îi definește comportamentul reactiv relativ la mesajele recepționate. Mesajele obținute de către un obiect reprezintă evenimente care declanșează tranziții de stări. Fiecare tranziție este asociată cu o acțiune care transmite unul sau mai multe mesaje asincrone obiectului însuși, componentelor sale sau unuia din porturile sale. Relațiile dintre obiecte pot fi exprimate atât prin utilizarea de invarianți funcționali asupra atributelor cât și prin specificarea dependențelor comportamentale dintre porturile obiectelor prin intermediul mașinilor de stări finite.

Caracteristica ce deosebește ObjChart de celelalte metode este aceea că modelele construite aici sunt executabile, adăugarea anei noi specificații putând fi testată imediat. Fiecare obiect conține o singură mașină de stări (nu sunt modelate mașinile de stări ortogonale ale lui Harel), iar prin compunerea obiectelor se poate preveni creșterea explosivă a numărului de stări amintită anterior.

Intermediate Object Notation – ION

ION este utilizat pentru documentarea grafică a deciziilor de implementare și oferă suport pentru modelarea anumitor aspecte ale sistemelor distribuite (cel mai interesant fiind acela privind modul de descriere a sincronizării utilizate de către o clasă) [ATK95].

Majoritatea notațiilor furnizează elemente pentru modelarea semanticilor de comunicare. Booch, în cadrul metodei sale ([BOO91]), face distincție între comunicarea asincronă și cea sincronă în cadrul diagramelor de obiecte. În ION unei metode îi poate fi atașat un simbol care indică faptul că metoda respectivă se execută asincron cu apelatorul său.

În ceea ce privește controlul concurenței în ION este utilizată o bibliotecă cu șase protocoale de sincronizare (cum ar fi excluderea mutuală, protocolul scriitor/cititori etc). Specificarea protocolului urmat de către o clasă se realizează prin reprezentarea unui simbol caracteristic în cadrul clasei sau prin intermediul moștenirii. În figura 2.2 este reprezentată o clasă folosind notația ION, și ale cărei metode sunt executate ciclic.

Figura 2.2. Specificarea protocoalelor de concurență în ION

MOSES

MOSES reprezintă una dintre cele mai complete metode pentru modelarea sistemelor orientate-obiect distribuite [HEN97]. O parte dintre conceptele existente aici au stat la baza limbajului de modelare OML, care a reprezentat principalul contracanditat al UML în competiția stabilira a unui standard.

Pentru descrierea concurenței MOSES utilizează ciclul de viață al obiectelor descris în [SHL88], însă modelul și notația folosite aici sunt mult mai precise (din punct de vedere al rafinării conceptelor). După cum am văzut în sub-secțiunea precedentă, comunicarea poate fi privită din două puncte de vedere: prin prisma obiectului client și respectiv a obiectului receptor (server). În primul caz comunicare poate fi sincronă sau asincronă. În cazul al doilea comunicarea poate fi privită ca realizându-se imediat sau prin excludere mutuală.

Figura 2.3. Notația utilizată în MOSES pentru reprezentarea

diferitelor tipuri de comunicare

În figura 2.3 este sunt date notațiile folosite în MOSES pentru comunicare sincronă (folosind un dreptunghi plin – a), comunicare asincronă (dreptunghi gol – b), comunicare asincronă în cazul în care serverul este ocupat iar clientul nu așteaptă până când aceasta este gata să răspundă ( c), comunicare mutual exclusivă (d) și comunicare imediată (e). Pentru cazul în care clientul întrerupe activitatea serverului există alte două notații speciale indicând faptul că clientul așteaptă sau nu atunci când nu este permisă întreruperea serverului.

UML

UML (Unified Modeling Language – [RAT97]) este un limbaj vizual de modelare a aplicațiilor orientate-obiect. UML reunește cele mai bune tehnici și practici din domeniul ingineriei programării și care și-au dovedit eficiența de-a lungul timpului în dezvoltarea unor sisteme complexe. El a fost proiectat pe baza a trei metode importante de analiză și proiectare orientată-obiect: OMT (Object Modeling Technology- [RUM91]), OOD (Object Oriented Design – [BOO91]) și Objectory ([JAC92]).

În cadrul specificației limbajului UML modelul de concurență nu se bucură de o tratare distinctă și independentă. Dimpotrivă, informații relative la elementele de concurență pot fi întâlnite pe întreg cuprinsul acestor specificații, localizate la nivelul definițiilor unor elemente specifice, cum ar fi clasa, obiect, operație (metodă), stare compusă sau mașină de stări.

Din punct de vedere al relației dintre clase și firele de execuției modelul UML este un model eterogen, deoarece permite modelarea a două tipuri de clase distincte: active și pasive. Obiectele claselor active dețin un fir de execuție propriu și pot fi executate în paralel cu alte obiecte active (mai precis, firul de execuție al unui obiect activ poate fi executat în paralel cu firele de execuție ale altor obiecte active).

În cazul obiectelor pasive, specificația UML sugerează că metodele acestora vor fi întotdeauna executate în cadrul unui fir de execuție deținut de către un obiect activ. De asemenea, metodele definite în cadrul claselor pasive pof fi de trei tipuri, și anume: secvențiale, gardate și concurente. Metodele secvențiale nu pot fi executate în paralel cu nici o altă metodă aparținând clasei în care au fost definite. Acest lucru însă nu înseamnă că ele sunt protejate implicit de către sistem de execuție paralelă cu alte metode. În acest caz, protejarea integrității stării obiectelor de apelul concurent de metode secvențiale cade în sarcina proiectantului.

Metodele gardate (condiționate) sunt asemănătoare cu cele secvențiale, singura diferență fiind dată de faptul că sistemul este cel care protejează obiectul de apelul concurent a mai multor metode.

În ceea ce privește metodele concurente nu există restricții cu privire la execuția paralelă cu alte metode.

În UML specificarea aspectelor privind concurența se realizează atât în modelul static (diagrame de clase) cât și în modelele dinamice (diagrame de tranziție a stărilor, diagrame de colaborare, diagrame de secvențe).

Diagramele de tranziție a stărilor vor face subiectul uneia dintre secțiunile care urmează. O metodă complementară de descrierea (modelare) a comportamentului dinamic al sistemului este utilizarea diagramelor de colaborare. În cadrul acestor diagrame potențialul paralelism între două mesaje se realizează prin numerotarea mesajelor folosind secvențe disjuncte (figura 2.4 – mesajul B1 poate fi executat în paralel cu mesajul A1 și/sau A2). În UML comunicarea sincronă este reprezentată printr-o săgeată plină în timp ce comunicarea asincronă se reprezintă prin intermediul unei jumătăți de săgeată. De asemenea, în cadrul diagramelor de secvențe timpul necesar pentru ca un mesaj să ajungă la receptor poate fi considerat atomic (reprezentat printr-o săgeată orizontală) sau nu (caz în care săgeata este oblică).

Figura 2.4. Specificarea concurenței în

diagrama de colaborare (UML)

Abordarea elementelor legate de concurență în UML este interesantă și flexibilă, dar în același timp mult prea ambiguă și permisivă, nefiind impuse prea multe restricții la nivel de metodă și "aruncând" o mare responsabilitate pe umerii proiectanților de aplicații concurente. Practic aceștia au o libertate mare de interpretare a conceptelor introduse.

Între ceea ce definea M. Papathomas sau L. Bergmans ca fiind obiecte active și modul în care sunt percepute acestea în UML este o mare diferență.

Astfel, un obiect activ în UML deține un fir de execuție și numai unul. De asemenea se specifică faptul că metodele unei clase active sunt implicit secvențiale. Prin urmare, deși nu dețin nici un fir de execuție, obiectele pasive par a fi mai "active" decât obiectele active, ele oferind posibilitatea modelării de obiecte cu concurență internă, chiar dacă firele de execuție care se execută în paralel în cadrul acestor obiecte nu sunt în proprietatea lor.

De asemenea nu se specifică nimic în legătură cu controlul apelurilor de metode (atât la nivelul obiectelor active cât și la nivelul celor pasive). Deși se amintește de un gestionar de evenimente și a unei cozi de eveniment în cadrul specificării diagramelor de tranziție a stărilor, nu se arată dacă el întreține această coadă de evenimente sau doar extrage cel mai recent eveniment sosit. Mai mult, așa cum vom vedea în secțiunea următoare, evenimentele care nu pot fi tratate la un moment dat de către un obiect sunt pur și simplu ignorate, nefiind re-depozitate în coadă în vederea unei tratări ulterioare.

Faptul că diagramele de tranziție a stărilor pot fi asociate atât claselor active cât și celor pasive, fără nici o diferență semantică, face și mai dificil de înțeles utilizarea atributului "pasiv" în acest context. Distincția dintre cele două tipuri de clase a fost impusă foarte probabil din dorința de a stabili o legătură clară între obiecte și fire de execuție. De asemenea, având în vedere modelele obiect precedente, o astfel de abordare pare a fi mai degrabă confuză, constatând că în UML nu există practic obiecte pasive în adevăratul sens al cuvântului (care nu dețin un fir de execuție propriu, iar toate metodele lor se execută în excludere mutuală).

3. Modelarea comportamentului obiectelor active

De-a lungul timpului s-au dezvoltat o serie de tehnici de descriere a comportamentului sistemelor. Dintre toate aceste tehnici se desprinde ca leader incontestabil din puct de vedere al popularității hărțile de stări (statecharts, diagrame de stări, diagrame de tranziție a stărilor) propuse de Harel [HAR87]. Aceste diagrame de stări reprezintă o extensie a mașinilor cu stări finite. Ele sunt foarte potrivite în special pentru descrierea comportamentului sistemelor reactive, deși au existat încercări de dezvoltare de tehnici derivate din diagramele de stări pentru descrierea sistemelor transformaționale (cum ar fi proiectarea de organigrame).

Un (sub)sistem transformațional (figura 3.1) este un (sub)sistem ale cărui intrări sunt complet cunoscute în momentul invocării sale și ale cărui ieșiri se produc după o anumită perioadă de calcul.

Figura 3.1. "Schema de funcționare" a unui sistem transformațional

Sistemele de achiziție a datelor, sistemele de compresia a vocii, sau simple proceduri care calculează radicalul sau logaritmul unui număr reprezintă exemple de sisteme transformaționale.

Pe de altă parte sistemele reactive (figura 3.2) sunt caracterizate ca fiind condus de către evenimente, reacționând încontinuu la stimuli interni și externi.

Figura 3.2. Reprezentarea schematică a unui sistem reactiv

și a interacțiunii sale cu mediul înconjurător

Unul dintre cele mai bune exemple de sistem reactiv este sistemul de control al luminii de trafic. Acest sistem nu va avea niciodată intrările pregătite, ele sosind în secvențe infinite și nedeterminate. Este imposibil de proiectat un sistem transformațional pentru un astfel de control (majoritatea sistemelor de control sunt de fapt reactive și nu transformaționale).

Aproape toate sistemele conțin câte o componentă reactivă, deoarece rareori un sistem este izolat de mediul în care activează. Dimpotrivă, motivul existenței sistemelor este chiar acela de a colabora sau interacționa cu anumite entități din mediul înconjurător.

3.1. Hărți de stări

S-a arătat că folosind stări și evenimente se poate modela (descrie) comportamentul unui astfel de sistem reactiv. Un element esențial al acestui model îl constituie, bineînțeles, starea sistemului la un moment dat, reprezentată grafic cu ajutorul unui dreptunghi cu colțurile rotunjite (figura 3.3). Un al doilea element este tranziția între stările unui sistem. Ea se reprezintă grafic cu ajutorul unui arc de cerc orientat și etichetat care leagă două stări. Eticheta unei tranziții este formată dintr-un nume de eveniment precedat (opțional) de o condiție logică. Semnatica unei tranziții care "unește" starea A1 cu starea A2 fiind orientată spre starea A2 și care este etichetată cu "c1/e1" este următoarea: "dacă sistemul se află în starea A1, apariția unui eveniment e1 va afea ca efect trecerea sistemului în starea A2 în cazul în care condiția c1 este verificată.

Figura 3.3. Exemplu de mașină cu trei stări și trei tranziții între acestea

a căror declanșare depinde de apariția a două evenimente

În cele ce urmează vom descrie pe scurt formalismul hărților de stări care înglobează o serie de extensii ale mașinilor cu stări finite și care a fost utilizat (cu unele modificări) în majoritatea metodelor și tehnicilor de analiză orientată – obiect a aplicațiilor (OMT [RUM91], Syntropy [COO94], UML[RAT97] etc.) pentru descrierea comportamentului obiectelor, chiar dacă în momentul dezvoltării lor hărțile de stări nu au fost asociate cu paradigma orientată-obiect.

Extinderea noțiunii de mașină finită de stări la așa-numita hartă de stări a fost realizată de către David Harel în [HAR87]. Una din problemele mașinilor finite de stări era aceea că în anumite cazuri complexitatea și dimensiunile lor creșteau nejustificat. De exemplu, adăugarea a două noi stări ortogonale unei mașini care conținea n stări necesita definirea a 2n stări noi. În cazul hărților de stări s-a încercat rezolvarea unor astfel de probleme de creștere a complexității prin definirea a două noi operații (reprezentate grafic) de combinare a stărilor, și anume: combinarea ortogonală și rafinarea.

Astfel, hărțile de stări au extins mașinile finite de stări cu trei noi trăsături:

1. Adâncimea. Această trăsătură se referă la posibilitatea rafinării (ierarhizării) unei hărți de stări. Astfel, pentru fiecare stare pot fi definite o mulțime de substări împreună cu tranziții între acestea.. Conceptul de adâncime permite gestionarea complexității prin contruirea unei ierarhii de hărți de stări încuibărite (figura 3.4).

Figura 3.4. Starea D este rafinată în substările A și B (dacă sistemul se află în starea

D atunci, în mod obligatoriu, el se va afla în una și numai una dintre stările A sau B)

2. Ortogonalitatea. Această trăsătură oferă posibilitatea combinării hărților de stări astfel încât să poată fi modelată situația în care un sistem se află în două sau mai multe stări în același timp. Ortogonalitatea reprezintă o altă trăsătură de tratare a complexității prin construirea descrierii unui sistem combinând mai multe hărți de stări (figura 3.5).

Figura 3.5. Reprezentarea mașinilor de stări ortogonale.

Sistemul aflat în starea D se va afla în câte o stare din fiecare componentă ortogonală

(oricare din combinatzille de stări din {A, B} {E, F})

3. Broadcast. Evenimentele asociate tranzițiilor sunt transmise întregului sistem. Această trăsătură permite comunicarea între hărți de stări ortogonale de obicei independente. Această proprietate însă întră în conflict cu paradigma orientată-obiect în care comunicare dintre obiecte este bazată strict pe transmiterea de mesaje punct-la-punct.

Tot în [HAR87] a fost introdus conceptul de stare inițială (implicită) prin intermediul căreia se este specificată substarea activă în momentul în care sistemul intră în strea sa compusă (figura 3.6). Reprezentarea grafică a stării inițiale este dată printr-un cerc plin. De asemenea, starea inițială poate fi prezentă și la nivelul diagramei de stări, caz în care se specifică starea în care ve intra sistemul în momentul creerii sale.

Figura 3.6. Specificarea (sub)stărilor inițiale

(în configurația de mai sus, intrarea sistemului în starea D va însemna, implicit, activarea substării A)

Starea inițială este numită și pseudostare (sistemul nu se va afla niciodată în starea respectivă ci va efectua o tranziție în plus pentru a intra într-o stare concretă. Alte pseudostări utilizate în cadrul diagramelor de stări sunt stările de ieșire și stările istoric. Tranziția într-o stare de ieșire semnifică încheierea ciclului de viață al sistemului și (în unele abordări) distrugerea acestuia.

Figura 3.7. Pseudostări de intrare (a), de ieșire (b) și istoric (c)

Pseudostarea istoric se poate afla poziționată doar ca și substare a unei stări compuse și o tranziție spre acea stare semnifică intrarea sistemului în ultima substare activă a stării compuse respective. Notațiile utilizate pentru simbolizarea acestor pseudostări sunt date în figura 3.7.

Deși, așa cum am arătat, diagramele de tranziție a stărilor au fost proiectate inițial pentru modelarea comportamentului sistemelor reactive, ele au fost foarte natural incluse în cadrul modelelor orientate-obiect.

Acceptarea generală a diagramelor de stări pentru definirea modelului dinamic al obiectelor din cadrul unei aplicații s-a datorat în principal următoarelor aspecte:

diagramele de stări permit descrierea lizibilă a comportamentului la un nivel ridicat de abstractizare

permit efectuarea de verificări la nivel semantic

codul generat din diagramele e stăi asigură păstrarea consistenței obiectelor în timpul "funcționării" sistemului; extinderea diagramelor de stări cu adnotări formale duce la creșterea semnificativă a procentului de cod generat pentru aplicația modelată;

permit realizarea de simulări grafice a funcționării sistemului și încurajează prototipizarea

În plus, în ceea ce privește aspectele legate de concurență, aceste diagrame permit o decriere intuitivă și precisă a sincronizării mesajelor dintre obiecte.

3.2. Specificarea UML a diagramelor de tranziție a stărilor

În UML diagramele de tranziție a stărilor sunt utilizate pentru modelarea comportamentului atât a claselor cât și a activităților. În cele ce urmează vom considera tratarea acestora numai din perspectiva claselor insistând în special pe aspectele legate de concurență. Așa cum am arătat în secțiunile precedente toate clasele contruite în UML pot fi asociate cu una sau mai multe diagrame de tranziție a stărilor. Acest fapt constituie după părerea noastră un element de confuzie. În documentația UML se arată că în majoritatea cazurilor va fi suficientă specificarea unei singure mașini de stări pentru descrierea comportamentului unei clase (sau, mai general, al unui element din modelul intern) fără a se preciza care ar fi cazurile în care este benefică specificarea mai multor astfel de mașini (probabil că într-o fază timpurie de analiză, când decizia stabilirii unui anumit model este amânată).

În UML sunt definite mai multe tipuri de evenimente, a căror semnificație va fi descrisă în secțiunea următoare. Un eveniment general este descris în UML ca reprezentând specificarea unui “incident” semnificativ care poate fi localizat în timp și spațiu. Fiecare tranziție are asociată un eveniment care o declanșează.

Alături de pseudostările de ieșire, de intrare și istoric, UML mai introduce alte trei pseudostări fără semnificație semantică, având ca rol creșterea lizibilitații diagramei: stările ramificație (branch – pentru reprezentarea a două sau mai multe tranziții dintr-o stare sursă comună, declanșate de același eveniment, dar cu gărzi diferite), fork și join (pentru tranziții în și din stări aflate în componente ortogonale) – figura 3.8. De asemenea pseudostările istoric au două variante: superficiale și profunde. Pseudostările istoric profunde activează recursiv ultima substare activată a ultimei stări compuse active.

Figura 3.8. Pseudostările ramificație (a), fork (b) și join (c)

O stare compusă poate conține cel mult o pseudo-stare istoric (în variantele sale superficială și profundă), o pseudo-stare istoric poate fi sursă pentru cel mult o tranziție. Același lucru este valabil și pentru starea inițială, restricție impusă de ideea că dintr-o stare inițială nu poate pleca decât o singură tranziție. Acest fapt însă nu este natural, deoarece astfel nu poate fi permisă modelarea activării implicite a unei substări în raport cu o mulțime de condiții complementare.

Se consideră că evenimentele sunt stocate într-o coadă de așteptare pe măsură ce ele apar. De asemenea se presupune că există un gestionar al acestor evenimente. Acest gestionar asigură faptul că tratarea unui eveniment de către o mașină de stări va avea loc după ce precedentul eveniment a fost complet tratat. O tratare completă se referă la modificarea stării obiectului (dacă este cazul) și la încheierea execuției tuturor acțiunilor lansate ca efect al tratării respectivului eveniment (acțiuni care fac parte din secvențele entry și exit ale stărilor, respectiv secvențele atașate tranzițiilor). În cazul unei stări compuse concurente, terminarea tratării unui eveniment presupune încheierea tratării sale în cadrul fiecărei componente concurente ale acesteia (o altfel de abordare ar duce la complicarea nejustificată a implementării unei mașini de stări). Acest sistem propus de UML pentru tratarea evenimentelor contribuie la păstrarea consistenței interne a obiectelor (evenimentul este tratat de către un obiect care se află într-o configurație stabilă, bine definită de stări), însă nu oferă suport pentru modelarea concurenței interne (cazul obiectelor secvențiale concurente!).

În cadrul documentului de specificare al UML apar în mai multe rânduri, disparat, fraze care sugerează că un eveniment poate declanșa mai multe tranziții care nu se află în componente concurente! Acest aspect este tratat cu superficialitate, făcându-se referire doar la modalitatea de alegere a tranziției care se va declanșa efectiv dintre cele posibile. Astfel, în cazul în care un eveniment poate declanșa mai multe tranziții în cadrul aceleași regiuni (secvențiale) va fi declanșată o singură tranziție (cea cu prioritatea cea mai mare, în cazul în care sunt specificate priorități, sau este aleasă o tranziție în mod nedeterminist în caz contrar).

Considerăm că trebuie evitate situațiile nedeterministe în modelarea comportamentului deoarece este afectată atât înțelegerea modelului cât și verificarea automată a acestuia (din nou facem referire aici la cazul utilizării unui instrument de modelare). Prin urmare UML nu impune restricții de eliminare a nedeterminismului, așa cum se întâmplă de exemplu în Syntropy [COO94] unde pentru două tranziții plecate din aceeași stare și declanșate de același eveniment se impune ca expresiile gărzilor să fie complementare. De asemenea se lasă la latitudinea proiectantului ca reprezentarea unor astfel de tranziții să fie făcute folosind tranziții simple sau cu prin pseudostări de ramificație. O soluție simplă și în același timp naturală constă în evitarea trasării mai multor tranziții declanșate de același eveniment dintr-o anumită stare prin utilizarea exclusivă pentru acest scop a pseudostărilor ramificație, ale cărei ramuri vor fi etichetate cu expresii booleene complementare.

Un alt element de noutate introdus este noțiunea de tranziție de completare (sau terminare). O astfel de tranziție este neetichetată cu un nume de eveniment (eventual ea poate avea o gardă). Dacă în urma tratării unui anumit eveniment un obiect se află într-o configurație de stări ce permite declanșarea de tranziții de terminare atunci spunem că obiectul respectiv a atins o configurație instabilă.

Figura 3.9. Exemplu de utilizare a unei tranziții de terminare

Tratarea următorului eveniment se va realiza în acest caz doar după efectuarea unui număr corespunzător de pași, până când se atinge o configurație stabilă (în exemplul din figura 3.9 obiectul va atinge o configurație instabilă imediat după tratarea evenimentului e; în această fază se realizează un nou pas de trecere a obiectului în starea C, înainte de tratarea următorului eveniment din coadă). În cazul unei proiectări incorecte se poate ajunge în situația în care nu se atinge niciodată o configurație stabilă. Pentru a preîntâmpina astfel de situații UML propune stabilirea inițială a unui număr maxim de pași care să poată fi efectuați după încheierea tratării unui eveniment. La interpretarea următorului eveniment, componenta instabilă nu va participa.

Așa cum am văzut într-una din subsecțiunile anterioare, stările pot fi active sau inactive. O stare devine activată în urma declanșării unei tranziții a cărei destinație este respectiva stare. În cazul stărilor compuse, dacă acestea nu sunt concurente atunci o sigură substare a sa poate fi activă la un moment dat. În cazul concurenței vor fi active toate subregiunile stării compuse.

Figura 3.10. Activarea stărilor în cazul unei tranziții (e1) în cadrul unei stări compuse (B)

a) intrare implicită – C va fi starea activă, b) intrare explicită – stare activă D

c) intrare prin istoric – dacă se intră pentru prima dată în B de la crearea obiectului

starea activă va fi C, altfel stare activă este ultima sub-stare activă a stării B (C sau D)

În diagramele de stări din UML există trei modalități prin care o sub-stare devine activă în cazul unei tranziții într-o stare compusă: implicit, explicit și prin intermediul pseudostării istoric. În figura 3.10 sunt reprezentate grafic toate aceste cazuri, cu remarca suplimentară că în cazul în care sub-stările sunt la rândul lor stări compuse, activarea se va face analog recursiv. Indiferent de modalitatea în care se realizează tranziția în cadrul unei stări compuse se va executa secvența de acțiuni entry specificată pentru această stare. Un caz deosebit este cel în care starea compusă conține mai multe componente concurente (variabila membru isConcurent are valoarea de adevăr true – v. figura 4.1). În acest caz se va utiliza o tranziție complexă cu ajutorul pseudostării fork, și fiecare regiune (componentă) concurentă în care va intra o astfel de tranziție va activa o substare a sa după modelul stărilor compuse prezentat anterior. Pentru regiunile în care nu intră nici o tranziție se va activa starea implicită (care este destinație a unei tranziții inițiale).

Se definește tranziția de terminare ca fiind o tranziție a cărei sursă este o stare simplă sau stare compusă și care este neetichetată. O astfel de tranziție este activată atunci când starea sursă a atins o stare finală. De asemenea, se definește termenul de tranziție de nivel înalt ca fiind acea tranziție a cărei sursă este o stare compusă.

Sun mai multe cazuri distincte în care putem avea într-un model tranziții neetichetate:

tranziții din stări inițiale care nu aparțin stării compuse de la nivelul unu (opțional – câteodată poate apare ca etichetă o expresie booleană;

tranziții de terminare;

tranziții spre stări finale aflate în cadrul stării compuse de nivel unu care sugerează simpla distrugere a obiectului prin apelul destructorului (opțional – pot apare ca etichete nume de evenimente care determină distrugerea obiectului);

tranziții care ies din pseudostările istoric și fork și care intră în pseudostarea join;

Ieșirea din cadrul unei stări compuse este tratată foarte pe scurt în documentația UML, neinsistându-se prea mult cu explicații pe marginea tranzițiilor de terminare.

Fiecare subregiune a unei stări compuse concurente poate avea stări inițiale și stări finale. O tranziție spre o stare compusă este echivalentă cu o tranziție spre starea de intrarea a stării compuse. O tranziție spre o stare finală reprezintă încheierea activității în regiunea părinte, iar încheierea activității tuturor regiunilor concurente semnifică încheierea activității în starea compusă părinte și declanșează un "eveniment de încheiere a activității" spre aceasta. Apariția unui astfel de eveniment în cadrul stării compuse de la nivelul cel mai exterior reprezintă distrugerea obiectului (apelarea destructorului acestuia).

UML permite realizarea tranzițiilor între regiuni concurente fără însă a se explica sensul unei astfel de reprezentări. Foarte probabil că astfel de tranziții nu își au sensul și sunt inconsistente cu faptul că un sistem aflat într-o stare compusă cu mai multe regiuni ortogonale se va afla de fapt în câte o stare din cadrul fiecărei componente ortogonale.

În momentul creerii unui obiect se realizează o tranziție din starea inițială a stării compuse de la nivelul cel mai de sus. Rafinarea unei stări în substări concurente se realizează prin împărțirea stării în mai multe subregiuni care pot avea, opțional, nume.

În [RAT97] se specifică faptul că un eveniment care nu declanșează nici o tranziție este ignorat. Acest lucru conduce la presupunerea implicită (nu se face nici o precizare explicită în acest sens) că în cadrul unei diagrame de stări vor fi trasate tranziții pentru toate evenimentele posibile. O astfel de abordare este incomodă deoarece reprezentarea grafică a tranzițiilor declanșate de apelul unui observator de exemplu, conduce la încărcarea nejustificată a diagramei de stări cu câte o autotranziție pentru fiecare stare..

O altă întrebare care nu își găsește răspunsul în documentele UML este “Ce se întâmplă atunci când apare un eveniment al cărei nume se află în eticheta a cel puțin unei tranziții din diagramă dar nici una dintre acestea nu poate fi declanșată?” Este acest eveniment reținut, într-o coadă de așteptare, în vederea unei tratări ulterioare sau este ignorat?

În altă ordine de idei unei tranziții îi este asociată o secvență de acțiuni care se execută în momentul declanșarii tranziției respective. Poate apărea însă următoarea problemă în cazul claselor secvențiale: ce se întâmplă atunci când există o tranziție declanșată de un eveniment de apelare al unei metode gardate, iar condiția asociată acesteia se verifică însă garda metodei nu? Specificațiile date de UML pot duce la mai multe răspunsuri, unele dintre ele contradictorii. Spre exemplu ar putea exista posibilitatea ca tranziția să se efectueze, să fie executată secvența de acțiuni însă execuția metodei gardate să nu se realizeze. În acest caz există din nou două alternative: evenimentul de apel de metodă este repus în coada de evenimente sau nu.

Aceste ambiguități sunt generate în mare parte de “grija” creatorilor UML de a nu intra în prea multe detalii și de a nu impune prea multe constrângeri și restricții care ar putea să reducă din flexibilitatea modelului (în unele cazuri chiar este precizat faptul că anumite elemente sunt lăsate intenționat la latitudinea proiectantului). Din păcate acest lucru la care se adaugă și absența unei bune sistematizări a informațiilor (de exemplu sunt descrise aspecte semantice la prezentarea notației) conduc în multe cazuri la abordări greșite de modelare.

4. Modelarea diagramelor de tranziție a stării

Așa cum am arătat în secțiunile precedente mașinile de stări sunt foarte populare în lumea ingineriei softului. Calitățile și neajunsurile acestora au fost îndelung discutate în multe lucrări de specialitate, mai ales după extinderea acestora cu noi trăsături [HAR87]. În cele mai multe cazuri însă descrierea și caracterizarea acestora s-a făcut în absența unui meta-model.

Specificațiile UML surprind însă acest aspect și conțin un meta-model static (diagramă de clase) al acestor diagrame. Astfel de meta-modele sunt utile deoarece ele stau la baza implementării diagramelor de stări în cadrul unor instrumente de analiză și proiectare (orientate obiect sau nu) a aplicațiilor. Meta-modelul UML prezentat în [RAT97] de exemplu, a stat la baza implementării insttrumentului CASE Rational Rose.

De asemenea, necesitatea verificării corectitudinii și a consistenței unei diagrame de stări implică construirea unui sistem formal robust care să descrie aceste diagrame.

În cele ce urmează vor fi prezentate în detaliu două meta-modele statice ale diagramelor de stări care au stat la baza a două instrumente CASE, și anume meta-modelul prezentat în specificațiile UML și un meta-model realizat în cadrul Laboratorului de Cercetare în Informatică al Universității și care a fost implementat în instrumentul Rocase [CHI97].

De asemenea, în ultima sub-secțiune este prezentată o formalizare a diagramelor de stări care ale la bază rezultate prezentate în [GIR97].

4.1. Metamodele statice ale diagramelor de tranziție a stării

Modelarea diagramelor de stări în UML

În figura 4.1. este prezentată diagrama de clase corespunzătoare diagramelor de tranziție a stărilor a cărei specificare am rezumat-o în secțiunea precedentă.

Figura 4.1. Metamodelul diagramelor de stări în UML

În această diagramă Event reprezintă o clasă abstractă care modelează toate evenimetele care pot declanșa o tranziție în cadrul unei diagrame de stări (acestea sunt împărțite în SignalEvent, CallEvent, TimeEvent și ChangeEvent). Evenimentele de apel (call events) reprezintă recepționarea unei cereri de invocare a unei operații. Aceste evenimente au în meta-modelul UML asociate operații (metode ale claselor), specificându-se existența a două operații speciale, și anume cele de creare și distrugere de obiecte.

Evenimentele generate de modificări aduse unor atribute sau relații (de asociere) care compun o anumită expresie booleană. Aceste modificări pot fi aduse în urma execuției uneia sau mai multor acțiuni (care nu au fost generat de către un eveniment de modificare). Aceste evenimente au asociate câte o expresie booleană, expresie care este periodic evaluată. În momentul în care expresia este adevărată se emite evenimentul care la rândul său poate declanșa una sau mai multe tranziții.

Clasa ce modelează starile compuse este descendentă a clasei State și conține una sau mai multe substări (una sau mai multe instanțe ale clasei StateVertex). Această clasă are două variabile membru foarte importante, care precizează dacă starea compusă este concurrentă (isConcurrent) și dacă ea este o substare a unei stări concurente (isRegion).

Clasa SimpleState a fost introdusă doar din rațiuni de “simetrie” cu CompositeState, ea neavând nici o altă trăsătură în plus față de clasa State. Instanțele acestei clase reprezintă stări care nu conțin substări.

O stare este asociată cu două secvențe de acțiuni care vor fi executate la intrarea (entry) respectiv la ieșirea (exit) din starea respectivă prin intermediul unei tranziții. Aceste acțiuni sunt atomice și ele nu sunt executate în cazul în care are loc o auto-tranziție. De asemenea o stare are asociată o listă de evenimente care sunt amânate.

O mașină de stări este compusă din tranziții și stări. Stările conținute de o mașină de stări formează un graf ale cărui arce sunt tranzițiile între aceste stări. O mașină de stări modelează comportamentul unui anumit element din model. Acest element reprezintă contextul mașinii de stări. Pentru o mașină de stări există o singură stare (compusă sau nu), numită Top care are ca și părinte “direct” mașina de stări. Toate celelalte stări conținute de mașina de stări reprezintă de fapt extesia stării compuse Top.

Clasa abstractă StateVertex reprezintă o clasa de bază pentru toate tipurile de stări definite în UML, relațiile outgoing și incoming specificând faptul că o stare poate fi sursa și destinația unui număr nedefinit de tranziții.

Clasa SubmachineState reprezintă o mașină de stări încuibărită (sub-mașină de stări). Așa cum se precizează și în documentația UML o submașină de stări este echivalentă din punct de vedere semantic cu o stare compusă precizânduse că ea a fost introdusă cu scopul de a ușura în primul rând reutilizabilitatea. Din păcate nu se precizează și modul în care s-ar putea realiza efectiv reutilizarea unei submașini de stări și nici nu sunt impuse anumite constrângeri care să granteze independența submașinilor.

Modelarea diagramelor de stări în Rocase

Diagramele de stări implementate în instrumentul Rocase se bazează pe cele descrise în UML.

Figura 4.2. Metamodelul diagramelor de tranziție a stărilor din Rocase

Modelul static propus pentru modelarea acestor diagrame (figura 4.2) este după părerea noastră mult mai robust și bine definit, eliminând redundanțele existente în alte modele. De asemenea definirea legăturilor dintre o clasă și diagrama sa de stări, respectiv dintre o stare compusă și substările sale este mult mai clară și naturală.

În cele ce urmează vom prezenta doar elementele noi care au fost introduse relativ la specificațiile date de UML.

Un prim element de noutate este dat de faptul că în Rocase stările nu sunt împărțite în stări simple – stări compuse sau în stări ortogonale – neortogonale așa cum au fost gândite mai multe modele anterioare. Prin urmare nu sunt definite clase speciale pentru a modela fiecare dintre aceste categorii de stări.

În Rocase există doar două tipuri de stări: pseudostări (de ieșire, intrare, istoric) – clasa Pseudostate- și stări concrete – clasa ConcreteState. O stare concretă poate conține una sau mai multe regiuni (claa Region). Aceste regiuni corespund substărilor ortogonale din modelul UML. Astfel, o stare concretă este concurentă dacă conține mai mult de o regiune. Fiecare dintre aceste regiuni poate conține oricâte stări (aceste stări sunt practic vazute de către proiectant ca și substări ale stării compuse care deține regiunea). O stare se reprezintă grafic prin intermediul unui dreptunghi cu capetele rotunjite care are trei compartimente separate între ele prin linii orizontale.

Prima secțiune va conține numele stării respective. Secțiunea a doua va conține toate regiunile care compun starea, despărțite prin linii verticale. Regiunile nu au o reprezentare grafică propriuzisă, ele fiind transparente proiectantului. Cea de-a treia secțiune va conține:

secvențele de acțiuni entry și exit asociate stării;

o expresie booleană (invariant) care definește starea (pentru testarea consistenței obiectelor);

evenimentele acceptate explicit de către oricare dintre substări fără a se declanșa nici o tranziție (vor fi acceptate implicit evenimentele corespunzătoare apelurilor de metode declarate ca observatori);

variabile de stare (variabile intermediare pentru stocarea anumitor valori în timpul declanșării unei tranziții).

O stare concretă va conține cel puțin o regiune. Dacă aceasta nu conține nici o substare atunci este o stare simplă, în caz contrar fiin stare compusă.

Prin urmare o stare simplă este o stare compusă care conține o singură regiune, iar aceasta la rândul său nu conține nici o stare.

Rezumând cele spuse până acum, în Rocase o stare simplă este percepută ca o stare compusă cu zero substări, iar o stare neconcurentă ca o stare cu o singură componentă ortogonală. Această modalitate simplă de a gândi o diagramă de stări conduce la descongestionarea vizibilă a meta-modelului acesteia, eliminând clasele redundante (în UML de exemplu clasa SimpleState a fost modelată doar pentru "simetrie", ea însă neavând nici o trăsătură în plus față de părintele său State).

Un alt element de noutate esențial este acela că o clasă în Rocase nu va conține o diagramă de stări sau o mașină de stări ci o stare concretă. Această stare concretă reprezintă practic părintele tuturor celorlalte stări ce vor fi definite. Acestă stare va avea numele clasei căreia i-a fost atașată.

În alte modele realizate până în prezent o clasă putea sau nu să aibă asociată o diagramă de stări care să-i modeleze comportamentul. Considerăm că este util să impunem ca o clasă să aibă întotdeauna să aibă atașată o stare. În cazul unei clase oarecare al cărui comportament dinamic nu este semnificativ, atunci această stare va fi una simplă (nu va conține nici o substare). Invariantul acestei stări va defini condiția de consistență a obiectelor clasei respective. În cazul unei clase complexe, cu un comportament ce necesită să fie modelat, starea atașată va conține practic diagrama de stări a clasei. În momentul în care va fi creată o instanță a unei clase, obiectul său va intra în starea asociată acesteia, stare care se va comporta ca o stare compusă obișnuită activând una dintre stările inițiale ale acesteia.

Această abordare uniformă este mult mai naturală și mai comodă din punct de vedere al unui proiectant de aplicații. Practic noțiunea de diagramă de stări a dispărut, comportamentul claselor fiind descris prin intermediul unei ierarhii de stări între care există diverse tranziții.

4.2. Formalizarea diagramelor de stări

În [MEY93] consideră că extinderea limbajelor de programare orientate-obiect cu trăsături de concurență trebuie să permită utilizarea moștenirii și a celorlalte caracteristici orientate-obiect fără nici o restricție, să asigure consistența stărilor obiectelor (caracterizate prin invarianți de clasă), să ofere suport pentru evitarea situațiilor de impas și să fie poată fi aplicată la mai multe forme de concurență (cu memorie partajată, procese distribuite, timp-real etc). Așa cum bine se știe aceste cerințe caracterizează un limbaj ideal. Nici unul dintre limbajele orientate obiect concurente dezvoltate până în prezent nu întrunește în totalitate aceste cerințe (fie că ele au fost proiectate prin extinderea unor limbaje orientate obiect sau nu).

Cerința privind păstrarea proprietăților de bază ale programării orientate obiect este naturală. Din păcate însă în foarte multe cazuri dificultățile întâmpinate în proiectarea limbajelor datorate conflictelor dintre moștenire și concurență (numite anomalii de moștenire sau reutilizare) au determinat eliminarea moștenirii din cadrul acestora.

Cea de a două cerință se referă la comportamentul dinamic al sistemelor și presupune că un obiect server este accesibil unui obiect client numai în cazul în care primul se află într-o stare consistentă (adică într-o stare în care obiectul server, conform constrângerilor de sincronizare care i-au fost definite, este capabil să proceseze mesajul transmis sau serviciu cerut de client).

A treia cerință de bază propusă de Meyer se referă la o problemă bine-cunoscută în programarea concurentă, și anume problema impasului. La rândul său și această cerință este naturală: obiectele pot comunica între ele concurent, iar în cadrul fiecărui obiect pot fi executate un număr nedeterminat de fire de execuție (concurență internă). În cazul în care două sau mai multe fire de execuție întră în impas nu implică faptul că obiectele care le dețin sunt în impas, ele putând să rezolva acest impas prin intermediul unor mecanisme speciale puse la dispoziție de către limbajul de programare.

Modelele de calcul care oferă suport pentru concurență sunt numeroase. Unul dintre cele mai populare astfel de modele azi este firul de execuție (thread-ul) în care o mulțime de procese secvențiale operează asupra aceeași date. Există însă și modele de concurență mult mai "sofisticate", cum ar fi procese secvențiale comunicante (Comunicating Sequential Processes – CSP- dezvoltat de C. A. R. Hoare), -calculul dezvoltat de Robin Milner, rețelele de procese etc. Am numit aceste modele mai "sofisticate" deoarece ele permit proiectarea mult mai ușoară a unor sisteme concurente complexe.

Așa cum am văzut însă, diagramele de stări reprezintă o modalitate elegantă, vizuală de modelare a concurenței. Vom încerca în cele ce urmează să propunem o formalizare a acestor diagrame, pe baza rezultatelor obținute în [GIR97] pornind de la definirea mașinilor cu stăi finite.

Definiție. O mașină cu stări finite reprezintă un tuplu cu cinci elemente:

(Q, , , , q0) (1)

unde: Q este o mulțime finită de simboluri numite stări,

este o mulțime de simboluri reprezentând intrări posibile,

este o mulțime de simboluri reprezentând ieșiri posibile,

este o funcție de tranziție definită astfel: :Q Q,

q0 Q reprezinta starea inițială.

La o reacție o mașină cu stări finite asociază unei stări curente p Q și unui simbol de intrare a o stare q Q și un simbol de ieșire b, unde (p,a) = (q, b). Dându-se un cuvânt (o secvență de simboluri din alfabetul de intrare ) și o stare inițială o secvență de reacții o secvență de stări și un cuvât de ieșire (format din simboluri ale alfabetului de ieșire ).

După cum am arătat în secțiunea a treia, mașinile cu stări finite pot fi reprezentate grafic sub forma unui graf orientat (numit și diagramă de tranziție a stărilor). Într-un astfel de graf (figura 4.3) fiecare nod reprezentat printr-un dreptunghi cu colțurile rotunjite este o stare și fiecare arc de cerc este o tranziție, acestea din urmă fiind etichetate după șablonul "condiție (sau gardă)/acțiune", unde garda aparține alfabetului și reprezintă simbolul de intrare care declanșează tranziția, iar acțiunea aparține alfabetului și este simbolul de ieșire unde este declanșată tranziția. Arcul de cerc ce nu are o stare sursă desemnează starea inițială a sistemului. În timp ce are loc o reacție a mașinii cu stări finite este declanșată o anumită tranziție, aleasă din mulțimea tranzițiilor admisibile, unde prin tranziție admisibilă înțelegem o tranziție care pleacă din starea curentă și a cărei expresie de gardă corespunde simbolului de intrare curent. Noua stare curentă a mașinii cu stări finite va fi starea destinație a tranziției declanșate și se va produce simbolul de ieșire indicat de acțiunea atașată acestei tranziții.

Figura 4.3. Mașină cu stări finite simplă

În cele ce urmează vom studia în detaliu mașinile cu stări finite deterministe și reactive.

O mașină cu stări finite (care va fi referită în continuare prin prescurtarea FSM) este deterministă dacă din oricare stare a sa pleacă cel mult o tranziție acceptabilă pentru fiecare simbol de intrare. De asemenea, spunem despre o FSM că este reactivă dacă din oricare stare a sa pleacă cel puțin o tranziție acceptabilă pentru fiecare simbol de intrare. Pentru simplificarea notației și pentru a asigura reactivitatea mașinilor de stări cu care vom lucra în continuare, vom presupune că fiecare stare are o autotranziție implicită pentru fiecare simbol care nu este gardă a unei tranziții explicite care pleacă din starea respectivă. Fiecare astfel de tranziție are ca acțiune un simbol de ieșire implicit, notat cu care aparține lui (uneori acest simbol este considerat ca reprezentând simbolul vid, și este exclud din cuvântul de ieșire).

Pentru exemplul din figura 4.3 presupunând că:

Q = {, }, = {a, b}, = {, u, v}, q0= și :QQ

astfel încât (, b) = (, v) și (, a)=(, u), vom putea adăuga auto-tranzițiile implicite (, a)=(, ) și (, a)=(, ). O posibilă urmă (secvență de reacții) este dată în tabelul 4.1.

Tabel 4.1.

De obicei interacțiunea FSM cu mediul necesită o modelare mai detaliată (se poate întâmpla ca impunerea unui singur simbol de intrare pentru o FSM să fie o condiție prea restrictivă). Având acest lucru în minte pare naturală modelarea intrărilor și ieșirilor multiple. Pentru a realiza un astfel de model alfabetul de intrare poate fi factorizat și definit sub forma unui produs cartezian:

= 12…M.

Prin urmare intrarea într-o FSM este compusă din M semnale, în care al i-lea semnal reprezintă o secvență de evenimente formată din simbolurile alfabetului de semnale i. O FSM reacționează simultan la M simboluri din M semnale. Alfabetul de ieșire poate fi la rândul său factoriza în mod analog. Reacțiile emit evenimente peste semnale.

În cele ce urmează vor fi definite două tipuri aparte de mașini de stări utile în continuare, și anume mașini de stări pure și de evaluare.

Definiție. Spunem despre o FSM că este pură dacă dimensiunea mulțimii simbolurilor de intrare este o putere a lui 2 (||=2M), și fiecare alfabet de semnale are dimensiunea doi (|i|=2, pentru 1 i M.

Cu alte cuvinte, în momentul unei reacții fiecare semnal are un eveniment care este prezent sau absent (deoarece |i|=2). O notație des utilizată la FSM pure este aceea în care este atribuit un nume (“a” de exemplu) fiecărui semnal, iar alfabetul corespunzător acestui semnal va fi de forma i={a,} și va fi interpretat ca {a este prezent, a este absent}. Să luăm ca exemplu o FSM cu două semnale de intrare l = {a, b} și două semnale de ieșire O={u, v}. Alfabetul de intrare va fi ={} și alfabetul de ieșire ={}, unde = reprezintă simbolul implicit.

Definiție. Spunem despre o FSM că este de evaluare în cazul in care alfabetele de intare și de ieșire sunt factorizate in alfabete de semnale, dar cel puțin unul dintre aceste alfabete de semnale are dimensiunea mai mare decât 2 (poate fi chiar infinită).

Putem interpreta și în acest caz un element al unui astfel de alfabet ca exprimând absența unui eveniment, celelalte elemente specificând prezența unui eveniment și o valoare a acestui eveniment. FSM-urile de evaluare sunt folosite deseori pentru reprezentarea automatelor cu operații aritmetice, utilizarea în acest caz a FSM-urilor pure fiind groaie.

Într-o FSM pură dimensiunea alfabetului de intrare crește exponențial cu numărul semnalelor de intrare. Prin urmare definirea unei FSM reactive prin specificarea explicită a tranzițiilor (de plecare) pentru fiecare stare și pentru fiecare simbol de intarer poate fi în dese cazuri incomodă (deoarece poate exista un număr foarte mare de tranziții). Pentru a evita astfel de situații putem folosi o notație astfel încât unei tranziții să îi asociem ca și gardă o submulțime a lui , și nu doar un singur simbol. În acest mod un ansamblu de tranziții poate fi reprezentat compact. O submulțime oarecare a lui poate fi definită de o expresie booleană asupra semnalelor de intrare. De exemplu, dacă ={}, expresia booleana “¬ab” (not a sau b) reprezintă submulțimea {}. Prin urmare pentru FSM-urile pure vom reprezenta in continuare gărzile sub formă de expresii booleene de semnale de intrare.

Figura 4.4. Exemplu de mașină cu stări finite pură

În figura 4.4 este reprezentată o FSM cu stările Q={,} și alfabetul de semnale de ieșire O={u, v}. Garda “ab” asociată tranziției de la la este satisfăcută pentru orice intrare din mulțimea {}. De asemenea, garda “a” a autotranziției stării este acceptabilă pentru orice intrare din {}.

Pentru FSM-urile de evaluare pot fi utilizate pentru gărzi expresii booleene mult mai complexe. Să presupunem de exemplu că într-o FSM oarecare al i-lea semnal are numele “a” și alfabetul i= (mulțimea numerelor reale). O gardă poate conține atunci operatori de comparație și numere reale (de exemplu “a<10”). Această reprezentare compactă permite descrierea unui număr infinit de tranziții. Bineînțeles există și în acest caz un “revers al medaliei”: o astfel de reprezentare face mult mai dificilă analiza mașinilor de stări, putânduse ajunge foarte simplu în cazul utilizării unor limbaje de expresii suficient de “bogate”, la situații indecidabile.

Modelul pe care îl utilizăm este unul eterogen, motiv pentru care FSM-urile de evaluare nu măresc critic complexitatea analizei. Astfel, în modelul nostru în loc să avem “a<10” vom folosi o gardă oarecare, numită spre exemplu b, gardă care va fi definită ulterior, extern modelului dinamic (în modelul de flux de date de exemplu) astfel:

(2)

Prin folosirea unui model eterogen complexitatea FSM-urilor pure și de evaluare scade fără a compromite expresivitatea acestora.

În cazul FSM-urile pure specificarea acțiunile se realizează printr-o notație compactă. Vom presupune de asemenea că ieșirea implicită pentru fiecare semnal reprezintă un eveniment absent.

De aceea o acțiune va “transmite” doar semnalele de ieșire care au evenimente prezente în reacția curentă (cu alte cuvinte toate evenimentele de ieșire care nu sunt emise explicit se consideră a fi absente). Pentru exemplul din figura 4.4 acțiunea “u” a autotranziției stării implică simbolul de ieșire , adică semnalul de ieșire u este prezent, iar semnalul v este absent atunci când tranziția este declanșată. E important de reținut faptul că absența lui v este implicită, nu explicită (vom vedea utilitatea sa la modelarea FSM-urilor ierarhice). Dacă toate evenimentele unei acțiuni sunt absente implicit, atunci acțiunea va fi complet omisă. Întorcându-ne din nou la exemplul din figura 4.4, observăm că în cazul în care este declanșată tranziția de la la care are garda “ab”, ambele semnale u și v sunt absente implicit.

În cazul FSM-urilor de evaluare o acțiune reprezintă orice valoare de ieșire diferită de cea implicită (care este transmisă automat și care semnifică absența unui eveniment). Deoarece numărul de tranziții a unei FSM este finit rezultă că mulțimea valorilor posibil emise este la rândul său finită și, deci, poate fi reprezentată printr-un număr finit de semnale booleene. Prin urmare pot fi folosite FSM-urile pure fără a exista riscul pierderii puterii de exprimare, chiar dacă FSM-urile de evaluare sunt mai convenabile din punct de vedere al sintaxei.

Utilizarea FSM-urilor în forma prezentată până acum (plate și secvențiale) prezintă un dezavantaj major, semnalat și în cadrul secțiunilor anterioare: reprezentarea și analiza unor sisteme cu un număr mare de stări duce la o creștere semnificativă a numărului de tranziții. După cum am văzut soluția propusă de Harel care să contracareze acest dezavantaz a fost ierarhizarea. Astfel, într-o FSM ierarhică o starea poate fi rafinată în alte sub-mașini de stări. În figura 4.5 este prezentată o rafinare a stării din exemplul precedent.

Figura 4.5. Exemplu de rafinare a unei stări

Reamintim că ierarhizarea nu modifică modelul de calcul, și nici nu minimizează numărul de stări folosit la modelare (chiar dimpotriva). În schimb implică reducerea semnificativă a numărului de tranziții și, în plus, conferă o mai bună înțelegerea a FSM-urilor. De exemplu, tranziția de la la din figura 4.5 reprezintă o notație compactă pentru tranzițiile de la la și de la la . Mulțimea stărilor pentru mașina de stări plată echivalentă este Q ={ , ,}.

Alfabetul de intrarea pentru sub-mașina de stări este o submulțime a alfabetului de intrare a super-mașinii. În cazul unei FSM pure sau de evaluare semnalele de intrare pentru o sub – mașină de stări formează o submulțime a mulțimii semnalelor de ieșire a super – mașinii sale. Analog, mulțimea semnalelor de ieșire a sub-mașinii este o submulțime a mulțimii semnalelor de intrare a super-mașinii sale.

Semanticile ierarhiei definesc modul în care sub-mașinile reacționează la reacțiile mașinii părinte. Cea mai evidentă semantică ce poate fi definită este următoarea: dacă o stare curentă nu este rafinată mașina de stări ierarhică se comportă analog cu una de bază, plană; dacă însă starea curentă este rafinată atunci reacționează mai întâi sub-mașina și apoi mașina părinte, fiind declanșate două tranziții și realizânduse 2 acțiuni. Aceaste două acțiuni vor trebui să fie combinate într-un anumit mod în una singură.

În cazul FSM-urilor pure combinarea acțiunilor este simplă, evitânduse clonflictele dintre definițiile ieșirilor între părinte și sub-mașină. Astfel, vom considera un eveniment de ieșire ca fiind prezent dacă acțiunea părintelui și a oricărei sub-mașini a acestuia emite un eveniment. Nu vor apărea conflicte de nici o natură datorită faptului că o acțiune nu emite explicit un simbol pentru absența unui eveniment. Pentru exemplul din figura 4.5, dacă este prezent a în semnalul de intrare în starea , și în substarea acțiunea declanșată de sub-mașină va fi “v” iar acțiunea declanșată de mașina părinte va fi “u”. Prin urmare ișirea FSM-ului ierarhic din figura 4.5 va fi uv (ambele semnale de ieșire sunt prezente. În tabelul 4.2 este dată o posibilă urmă a mașinii ierarhice.

Tabel 4.2. Exemplu de urmă generată de FSM-ul ierarhic din figura 4.5

Pentru o FSM de evaluare vom adopta din nou convenția în care o acțiune nu face nici o mențiune explicită relativ la absența unui eveniment. Totuși, deoarece două acțiuni pot emite un eveniment cu valori diferite sintaxa va permite definirea conflictelor de ieșiri. În Esterel [BER92], există posibilitatea specificării unei combinații de conflicte de definiții De exemplu, pentru cazul a două numere reale valorile acestora pot fi adunate. În modelarea noastră vom prefera să considerăm acest aspect ca și o condiție de eroare, deoarece valorile pot fi combinate extern (într-un model de calcul mai potrivit pentru calcul numeric)într-un mod mai convenabil. Prin urmare nu vom permite declanșarea a două tranziții care să emită același semnal de ieșire într-o FSM de evaluare.

În exemplu din figura 4.5 mașina ierarhică de stări are doar două nivele. Pentru cazul în care mașina de stări va avea un număr de sub-mășini oarecare, pe mai multe nivele, semanticile prezentate mai sus se pot generaliza cu ușurință.

5. Bibliografie

La acest material bibliografic se adaugă o serie de discuții personale purtate împreună cu domnii lect. Dan Chiorean (șef al Laboratorului de Cercetare în Informatică al Universității "Babeș-Bolyai", Cluj-Napoca), Marian Scuturici (doctorand, Lyon) și Iulian Ober (doctorand, Toulouse).