Lucrare de licen ță [603933]

Universitatea Tehnica "Gheorghe Asachi" din Iași
Facultatea de Automatică și Calculatoare

Lucrare de licen ță

Studierea fenomenului de dead lock în sisteme cu
resurse partajate

Coordonator : Absolvent: [anonimizat]. Mihaela Matcovschi Cristea Laurențiu

Iași 2020

2

3
Cuprins
I. Introducere ……………………………………………………………………………………………….. 4
II. Modele de rețele de tip Petri ……………………………………………………………………….. 6
A. Modele de tip rețea Petri netemporizată ………….. ………………………………….. 6
B. Studierea propriet ăților comportamentale ………………………………………….. 10
III. Producerea fenom enului de Deadlock …………………………………………………………. 17
A. Definiție și caracteristici ………………………………………………………………….. 17
B. Grafuri pentru alocarea resurselor ………….. ………………………………………… 20
C. Fenomenul de deadlock – metode de abordare …………………………………… 22
1. Ignorarea deadlock -ului …………………………………………………………. 22
2. Detecția deadlock -ului …………………………………………………………… 22
3. Prevenire deadlock -ului …………………………………………………………. 23
IV. Aplicație practică și mediul de lucru ……………….. ………………………………………… 25
A. Mediul de lucru ……………………………………………………………………………… 25
1. Gener alități Matlab ……………………………………………………………….. 25
2. Toolboxuri Matlab ………………………………………………………………… 30
B. Implementarea aplicației și rezultate experimentale ……………………………. 34
V. Concluzii ………………………………………………………………………………………………… 42
Bibliografie

4
I. Introducere
Prin sisteme cu evenimente discrete să înțelegem fie un sistem real, fie un model matematic
(ce des crie funcționarea unui sistem real), a cărui evoluție este raportată la apariția unor
evenimente. Astfel, producerea evenimentelor joacă rolul de cauză pentru dinamica sistemului și
are drept efect modificarea stărilor sistemului, evidențiind o certă simil itudine cu așa -numita
„tratare pe stare” a sistemelor continue sau discrete în timp. M ai mult chiar, și în cazul unui sistem
cu evenimente discrete se poate vorbi despre o funcție de tranziție a stărilor, care formalizează
riguros faptul că sistemul trece dintr -o stare în alta numai ca urmare a producerii unui eveniment
și că sistemul păstr ează starea în care se află până la producerea unui nou eveniment.
Func ționarea unui num ăr mare de sisteme fizico -tehnice poate fi modelat ă utilizând
conceptul de sistem dinamic cu evenimente discrete. În construirea unui model eficient,
identificarea cor ecta a structurii spa țiului st ărilor și a mul țimii de evenimente care piloteaza
tranzi țiile în spa țiul st ărilor joac ă un rol fundamental.
Se nume ște sistem dinamic cu ev enimente discrete, un sistem dinamic care posed ă
urmatoarele doua propriet ăți:
➢ spațiul st ărilor este o mul țime discret ă;
➢ mecanismul de tranzi ție a st ărilor este pilotat de evenimente cu apari ție asincron ă.
În continuare, această lucrare este structurată d upă materialul teoretic al rețelelor Petri,
care, pe parcursul celor patru decenii scurse de la prezentarea tezei de doctorat a matematicianului
german Carl Adam Petri (Petri, 1962), au demonstrat o deosebită flexibilitate în abordarea
numeroaselor tipuri de probleme practice, precum și o mare capacitate de extindere ca sferă de
operare, prin înglobarea unor puncte de vedere tot mai complexe.
Rețelele (grafurile) propuse (în Petri, 1962) dispuneau de un mecanism capabil de a
guverna, pe principiile algebre i boolene, evoluția unui vector cu elemente numere naturale, având
semnificația de stare, făra precizia momentelor efective de timp când aveau loc modificarile stării.
Cercetările ulterioare au condus și la încorporarea informațiilor temporale (Ramamoorthy and Ho,
1980), (Ajmone Marsan et al., 1985), astfel încât, în prezent, pentru stud ierea sistemelor cu
evenimente discrete, avem la dispoziție modele de tip rețea Petri netemporizată (care permit studii

5
calitative) și, respectiv, de tip rețea Petri tempori zată (care permit studii cantitative). Introducerea
temporizării s -a realizat de aș a maieră încât să permită nuanțările de model determinist sau
stohastic, binecunoscute din cazul sistemelor clasice.
Aceste rafinări ale conceptului inițial formulat de Pet ri (rafinări care nu includ, în totalitate,
extinderile propuse în literatură) evid ențiază atât resursele oferite pentru modelare, cât și
compatibilitatea cu alte instrumente și tipuri de modele. Rețelele Petri pot modela fenomenele
specifice sistemelor cu evenimente discrete, cum ar fi succesiunea (o evoluție succede alteia),
alegerea s au conflictul (selectarea uneia din mai multe posibilitați de evoluție), concurența
(startarea unei evoluții paralele), sincronizarea (încheierea unor evolutii paralele), ex cluderea
mutuală (condiționarea reciprocă a unei evoluții), care pot fi formulate î n contexte temporizate
sau netemporizate.
Sopul lucrării este de a evidenția efectele fenomenului de deadlock în sistemele de
fabricație flexibile (Flexibile Manufacturing System – FMS) prin prezentarea unor exeple
concludente .

6
II. Modele de rețele de tip Petri
C. Modele de tip rețea Petri netemporizată
O rețea Petri se compune dintr -un graf orientat notat N și o stare inițială M₀, denumită
marcaj inițial.
Graful N al rețelei Petri est e orientat, ponderat și bipartit, constând din două tipuri de
noduri, denumite poziții sau locații și respectiv tranziții; arcele orientate unesc fie o poziție cu o
tranziție, fie o tranziție cu o poziție. Nu există arce care să conecteze două po ziții între ele, sau
două tranziții între ele. Ca simbolizare grafică, pozițiile se reprezintă prin cercuri, iar tranzițiile
prin bare sau dreptunghiuri. Arcele sunt etichetate cu ponderile lor (valori întregi, pozitive); un arc
cu ponderea k poate fi priv it ca o mulțime de k arce paralele cu ponderea unitară. Etiche tele pentru
ponderea unitară se omit în reprezentările grafice uzuale.
Un marcaj sau o stare atribuie fiecărei poziții un număr întreg mai mare sau egal cu 0. Dacă
un marcaj atribuie poziției p întregul k ≥ 0, se spune că p este marcată cu k jetoane . Din p unct de
vedere grafic, în cercul corespunzător poziției p se vor plasa k discuri. Orice marcaj M este un
vector coloană m-dimensional, unde m notează numărul total al pozițiilor. Componenta i a
vectorului M = [M (p₁) M (p₂) … M (pₘ)]ᵀ, notată M (pᵢ) reperezintă numărul de jetoane din poziția
pᵢ.
Aspectele prezentate anterior se formalizează matematic prin următoarea definiție.
O rețea Petri este un cvintuplu, PN = (P, T, F, W, M₀) în care:
• P = {p₁, p₂, …, p ₘ} este mulțimea pozițiilor sau locațiilor (finită);
• T = {t₁, t₂, …, t ₙ} este mulțimea tranzițiilor (finită);
• F ⊆ (P × T) ⋃ (T × P) este mulțimea arcelor;
• W : F → {1,2,3,…} este funcția de pondere a arcelor;
• M₀ : P → {0,1,2,3,…} este funcția de marcaj initial.
Câteva comentarii sunt necesare pentru a aprofunda detaliile acestei formalizări:
1. Mulțimile P și T sunt disjuncte, P ⋂ T = ∅.
2. Pentru a asigura obiectul definiției de mai sus, mulțimile P și T satisfac condiția
P ⋃ T ≠ ∅.

7
3. Definiția funcției de pondere se poa te extinde pe mulțimea tuturor perechilor ordonate din
(P × T) ⋃ (T × P), considerând W : (P × T) ⋃ (T × P) → {0,1,2,3,…}, cu observația că,
pentru acele perechi care nu sunt în mulțimea F, valoarea funcției W este cu 0 și aceste
perechi nu sunt reperezentate graf ic. Mulțimea F corespunde perechilor a căror pondere
este nenulă și numai acestea sunt reperezentate grafic.

4. Definiția unei rețele Petri consideră implicit că toate pozițiile rețelei pot conține un număr
oricât de mare de jetoane . Se spu ne că rețeaua este de capacitate infinită .
5. O structură de rețea Petri N = (P, T, F, W ) fără nici o specificație referitoare la marcaj se
va nota cu N, notație care desemnează topologia rețelei .
6. O rețea Petri cu un marcaj inițial M₀ se va nota prin (N,M₀).
7. O rețea Petri cu un marcaj oarecare M se va nota prin ( N,M).
În problemele de modelare ce utilizează conceptele de condiții și evenimente, pozițiile
reprezintă condiții și tranzițiile reperezinăta evenimente. O tranziție (eveniment) posedă un numr ăr
de po ziții de intrare și ieșire, care reprezintă pre -condiții și respectiv post -condiții pentru
evenimentul în cauză. Prezența unui jeton într -o poziție trebuie înțeleasă ca valoare logică
„adevărat” pentru condiția asociată respectivei propoziții.
Dacă o poziție p este atât poziție de intrare,cât și de ieșire pentru o tranziție t, atunci p și t formează
o buclă autonomă. O rețea Petri care nu conține bucle autonome se numește pură. O buclă
autonomă poate fi întotdeauna transformată într -o buclă neautono mă prin adăugarea simultan a
unei poziții și a unei tranziții formale. Orice rețea impură poate fi transformată într -o rețea pură.
O rețea Petri se numește ordinară dacă toate arcele sale au pondere unitară. Dacă într -o
rețea Petri există cel puțin un arc a cărui pondere este mai mare decât 1, atunci se spune că rețeaua
respectivă este generalizată.
Fie F mulțimea tuturor arcelor unei rețele Petri N. Se numesc mulțime predecesor și
mulțime succesor a tranziției t (fig. BT2.2.1.(a)) două mulțimi de poziții definite prin:
t = {p | (p, t) ∈ F} = mulțimea tuturor pozițiilor de intrare ale lui t;
și, respectiv, prin:
t = {p | (t, p) ∈ F} = mulțimea tuturor pozițiilor de ieșire ale lui t;
Se numesc mulțime predecesor și mulțime succesor a poziției p (figura 1-b) două
mulțimi de tranziții definite prin:

8
p = {t | (t, p) ∈ F} = mulțimea tuturor tranzițiilor de intrare ale lui p;
și, respectiv, prin:
p = {t | (p, t) ∈ F} = mulțimea tuturor tranzițiilor de ieșire ale lui p;

Figura 1 – Ilustrarea grafică a mulți milor predecessor și sucessor
Același mod de notare, și anume {*}, {*} , se utilizează pentru a desemna mulțimea
predecesor și, respectiv, succesor a unei mulțimi de tranziții sau a unei mulțimi de poziții, notata
generic {*}. Evident, mulț imile predecess or și successor ale unei mulțimi de tranziții sunt două
mulțimi de poziții, iar mulțimile predecesor și succesor ale unei mulțimi de poziții sunt două
mulțimi de tranziții.
Marcajul unei rețele Petri are semnificația de stare a rețelei și s e poate modific a în
conformitate cu următorul procedeu denumit regula tranziției (validare și executare).
a) Se spune că o tranziție t este validă dacă fiecare poziție de intrare (predecesor) p a lui t
este marcată cu cel puțin W(p,t) jetoane, unde W(p,t) notează ponderea a rcului de la p
la t.
b) O tranziție validă poate sau nu să fie executată sau declanșată, după cum evenimentul
asociat tranziției are sau nu loc.
c) Executarea unei tranziții validate îndepărtează W(p,t) jetoane din fiecare poziție de
intrare (p redecesor) p a lui t și adaugă W(t,p) jetoane la fiecare poziție de ieșire
(succesor) p a lui t, unde W(t,p) este ponderea arcului de la t la p.
O tranziție fără nici o poziție de intrare se numește tranziție sursă. O tranziție fără nici o
poziție de ieșir e se numește tranz iție receptor. Modul de operare al acestor tranziții este
următorul:
a) O tranziție sursă este necondiționat validată (fără a fi obligatoriu ca să se execute).

9
Executarea ei produce jetoane.
b) Executarea unei tranziții receptor consumă jetoane , fără a produce j etoane.
În teoria rețelelor Petri netemporizate se consideră că executarea unei tranziții nu consumă
timp și că jetoanele pot rămâne în poziții pentru orice durată de timp (oricât de mică sau oricât de
mare). Întrucât executarea unei tranziții este instan tanee, se consideră că tranzițiile se execută
numai secvențial, adică nu se poate vorbi de două tranziții executate simultan (sau în paralel).
Aceste presupuneri fac ca modelul de tip rețea Petri netemporizată să fie ut ilizat numai pentru
investigarea prop rietăților logice, calitative, care nu depind de timp.
Pentru o rețea Petri N cu un marcaj inițial M₀, urmărind executarea secvențială a tranzițiilor,
se pot determina marcajele succesive ale rețelei. Procesul de modificare al marcajului (stării)
rețelei poate fi descris într -o manieră sintetică printr -un arbore sau printr -un graf (diferit de gradul
rețelei Petri!), ce poartă denumirea de arbore, respectiv, graf de accesibilitate.
Pentru regula de validare a unei tranziții prezentată anterior s -a presupus că fiecare poziție
are capacitate infinit ă. În modelarea sistemelor fizice este firesc a considera o limită superioară a
numărului de jetoane pe care îl poate conține fiecare poziție, asociind fiecărei poziții p capacitatea
sa, notată K(p), definită ca nu marul maxim de je toane ce pot fi conținute de p. O astfel de rețea se
numește cu capacitate finită.
Într-o rețea cu capacitate finită, pentru validarea unei tranziții t este necesară următoarea
condiție suplimenta ră: numărul de jetoane în fiecare poziție de ieșire p a lui t nu poate să
depășească capacitatea poziției respective, K(p), atunci când t s-ar executa. În acest caz, regula
tranziției se va numi regula strictă a tranziției spre a o deosebi de cea enunțată în paragraful 2.3,
care mai este uneori re ferită drept regula simplă a tranziției.
Fiind dată o rețea Petri de capacitate finită ( N, M₀) este posibil de aplicat fie regula strictă
a tranziției direct pentru rețeaua ( N, M₀), fie regula simplă a tranziției pentru o rețea transformată
adecvat, notat ă (N′, M₀′). Presupunând ca rețeaua N este pură, următorul algoritm permite
construcția rețelei ( N′, M₀′) plecând de la ( N, M₀), prin metoda pozițiilor complementare:
Pas 1. Pentru fiecare poziție p, se adaugă o poziție complementară p′, al cărei marcaj in ițial este
dat de M₀′(p) = K(p) – M₀(p).

10
Pas 2. Între fiecare tranziție t și poziții complementare p′ se trasează arce suplimentare, ( t, p′) sau
(p′, t), cu ponderile W(t, p′) = W(p, t), respectiv W(p′, t) = W(t, p), astfel încât suma jetoanelor în
poziția p și în poziția complementară corespunzătoare p′ să fie egală cu capacitatea K(p), atât
înainte, cât și după executarea tranziției t (adică să se asigure satisfacerea condiției M(p) + M′(p′)
= K(p)).
Subliniem faptul că metoda nu adaugă tranziții suplime ntare. Grafurile de accesibilitate ale
rețelelor ( N, M₀) și ( N′, M₀′) sunt izomorfe în sensul ca prezintă aceleași secvențe posibile de
executare a tranzițiilor.
În unele modele de tip rețea Petri două sau mai multe tranziții modelează evenimente dintre
care unul și numai unul se poate produce la un moment d at (în conflict). Implicit se consideră că
probabilitățile de apariție a acestor evenimente sunt egale. În cazul în care această presupunere nu
este în conformitate cu sistemul fizic modelat, probabilit ățile de apariție a evenimentelor în conflict
pot fi asignate în mod explicit ca probabilități de executare a tranzițiilor care modelează
evenimentele respective.
De asemenea, atunci când se dorește a impune modul de alegere a tranziției care urmează
a fi executată dintre două sau mai multe tranziții validat e simultan se poate utiliza o rețea Petri cu
priorități care constă dintr -o rețea Petri obișnuită și o rețea de ordine parțială între tranzițiile re țelei.
Introducerea arcelor inhibitoare extinde capac itatea de modelare a rețelelor Petri. Un arc
inhibitor conectează o poziție la o tranziție și are rolul de a inversa logica de validare și executarea
acesteia. Tranziția respectivă este validată numai d acă numărul de jetoane din poziția de intrare a
arculu i inhibitor este stict mai mic decât ponderea arcului. Arcul inhibitor se reperezintă grafic
printr -un segment ce conectează cele două noduri, având un mic cerc la capătul dinspre tranziția
inhibată. Nu există arce inhibatoare care conectează o tranziție l a o poziție.
D. Studierea proprietăților comportamentale
Proprietățile comportamentale ale rețelelor Petri netemporizate sunt dependente atât de
topologia cât și de marcajul inițial al rețelei. În ceea ce privește terminologia, este absolut necesar
a face di stincție față de proprietățile structurale , care iau în considerare numai topologia rețelei,
fiind independente de marcajul inițial al acesteia.

11
Accesibilitatea – O problemă importantă în designul sistemelor distribuite constă în
capacitatea sistemului de a atinge o anumită stare sau de a prezenta un comportament funcțional
particular. În general, întrebarea la care se caută răspuns este dacă sistemul modelat cu rețele Petri
are toate proprietățile dorite, așa cum sunt ele specificate în cerințe, și nicio proprietate nedorită.
Pentru a afla dacă sistemul modelat poate atinge o anumită stare ca rezultat al
comportamentului funcțional cerut, este necesară găsirea unei astfel de secvențe de execuții a
tranzițiilor care va avea ca efect transformarea marcajulu i M 0 în M i, unde M i reprezintă starea
specifică și secvența de execuții reprezintă comportamentul funcțional cerut. Trebuie subliniat
faptul că sistemele reale pot atinge o anumită stare prin mai multe comportamente funcționale
permise. Într -o rețea Petri, acest lucru este reflectat de existența unor secvențe specifice de execuții
de tranziții, reprezentând comportamentul funcțional cerut ,care vor transforma un marcaj M 0 în
marcajul M i cerut. Dacă într -un model de rețea Petri există secvențe adiționale de execuție a
tranzițiilor care să transforme un marcaj M 0 în marcajul M i poate indi ca faptul că acel model de
rețea Petri nu reflectă cu exactitate structura și dinamica sistemului descris. De asemenea, acest
fapt poate indica și prezența unor aspecte neanti cipate pr ivind comportamentul funcțional al
sistemului real, ceea ce înseamnă că rețeaua Petri reflectă cu precizie specificațiile sistemului
descris.
Un marcaj M i este accesibil pornind de la marcajul M 0 dacă există e secvență de execuție
a tranzițiilor care trans formă marcajul M 0 în M i. Un marcaj M 1 este imediat accesibil după marcajul
M0 dacă o execuție a tranzițiilor activate din M 0 determină obținerea marcajului M 1.
Limitabilitatea și sigurnața – De regulă, locurile sunt folosite pentr u reprezentar ea unei
zone de păstrare a datelor în comunicare sau sistemele computerizate, a unor produse sau zone de
păstrare a uneltelor în sistemele de producție etc. Este foarte important de stabilit dacă strategiile
de control stabilite asigură evitar ea stării de supraîncărcar e a acestor zone. Zonele de păstrare a
datelor pot păstra, fără a le corupe, doar un număr restricționat de părți de date. În sistemele de
fabricație, încercarea de a înmagazina mai multe unelte în zona destinată acestui lucru poa te duce
la de fectarea echipamentului. Proprietatea unei rețele Petri care permite identificarea în cadrul
sistemului modelat a situației de supraîncărcare se numește limitabilitate. O rețea Petri este k –
limitată dacă numărul de jetoane în orice loc p, unde p ∈ P , este totdeauna mai mic sau egal cu k
(k este un număr întreg pozitiv), pentru orice marcaj M accesibil din marcajul inițial M 0. O re țea

12
Petri este sigur ă dacă este 1 -limitat ă (figura 2 ). Într-o astfel de re țea, niciun loc nu poate conține
mai mu lt de un jeton. O rețea Petri este nelimitată dacă există cel puțin un loc care să conțină un
număr oricât de mare de jetoane ( figura 3 , locul p4).

Figura 2 – Rețea Petri sigură

Figura 3 – Rețea Petri nelimitată
Conservati vitatea – În sistemele reale, numărul resurs elor utilizate este, în mod normal ,
limitat prin constrângeri financia re sau de alt gen. Dacă jetoanele sunt utilizate pentru
reprezentarea resurselor, al căror număr într -un sistem este fix, atunci numărul jetoanelor din
rețeaua Petri a respectivului sist em ar trebui să rămână neschimbat indiferent de marcajul curent
al sis temului. Această directivă descinde din faptul că resursele nu pot fi nici create, nici distruse,
cu excepția cazului când ar trebui să se întâmple așa. Spre exemplu, o unealtă distrusă poate fi
înlăturată din celula de fabricare, iar numărul uneltelor dis ponibile se va reduce.

13

Figura 4 – Rețea Petri conservativă în raport c u w = [1,1,2,1,1 ]

Figura 5 – Rețea Petri strict conservati vă
O rețea Petri este conservativă dacă numărul de je toane este conservat. Din punct de vedere
structur al, acest lucru este posibil doar dacă numărul de arce de intrare în fiecare tranziție este egal
cu numărul de arce de ieșire. În sistemele reale, însă, resursele sunt, în mod frecvent, combinate
astfel înc ât anumite sarcini să fie executate, apoi separate după finalizarea sarcinilo r. Spre
exemplu, într -un sistem de fabricație flexibilă un vehicul ghidat automat colectează paleții c u
produse de la o celulă de prelucrare și îi transportă la o stație de descăr care unde paleții sunt preluați
(scenariu ilustrat în figura 4 ). Tranziția t 1 modelează încărcarea unui palet într -un vehicul. Tranziția
t2 reprezintă livrarea paletului la stația de descărcare și înlăturarea acestuia de pe vehicul. Deși
numărul de jetoane se schimbă de la două la unu atunci când este executată t 1 și înapoi la două
când este executată t 2, numărul resurselor din sistem nu se modifică. Pentru a preîntâmpina această
problemă, locurilor li se pot asocia ponderi pentru ca suma ponderată a jetoan elor din rețea să
rămână constantă.

14
Se spune că o rețea Petri este conservativă dacă există un vector w, w = [ w1, w2, …., w m],
unde m este numărul de locuri și w(p) > 0 pentru fiecare ∈ , astfel încât suma ponderat ă a jetoanelor
rămâne neschimbată pentr u fiecare marcaj M c are poate fi accesat din marcajul inițial Mo. O rețea
Petri este strict conservativă dacă toate intrările vectorului w sunt unitare. Rețeaua Petri din figura
4 este conservativă în raport cu vectorul w = [1,1,2,1,1] deoarece suma ponder ată a jetoanelor în
fiecare marcaj este doi. Un exemplu de rețea Petri care n u este conservativă este prezentat în figura
3 deoarece locul p4 poate deține un număr nelimitat de j etoane. Dacă o rețea Petri este conservativă
în raport cu un vector unitar, at unci rețeaua este strict conservativă ( figura 5 ).
Nivelul de activare – Acest concept este strâns corelat cu situația de blocare (deadlock),
care a fost studiată în mod extensiv în contextul sistem elor de operare. S -a arătat că această situație
poate să a pară în patru condiții:
1) Excluderea mutuală: o resursă este fie disponibilă, fie alocată unui proces care are acces
exclusiv asupra ei.
2) Deține și așteaptă: unui proces i se permite să dețină o resursă (sau mai multe) și să
acceseze încă o resursă ( sau mai multe).
3) Fără preempțiune: o resursă (sau mai multe) alocată unui proces nu poate fi eliberată
decât de către procesul în sine.
4) Așteptare circulară: două sau mai multe procese sunt aranjat e într -un lanț în care fiecare
proces așteaptă după resursele deținute de procesul poziționat înaintea lui în lanț.

Figura 6 – Rețea Petri cu diferite niveluri de activare a tranzițiilor

15
Spre exemplu, într -un sistem flexibil de fabricație poate interveni o situație de blocare
atunci când un buffer de in trare/ieșire al unei unelte de prelucrare deține un palet cu produse
prelucrate și alt palet cu produse care trebuie prelucrate a fost trimis la buffer. Dacă buffer -ul poate
păstra doar un palet la un moment de timp și vehiculul ghidat automat, care transp ortă paleții, are
loc doar pentru un palet, atunci tocmai a intervenit o situație de blocare. Paletul cu piese prelucrate
nu poate fi mutat din buffer în mașină, iar paletul cu piese neprelucrate nu poate fi mutat din mașină
în buffer. În acest exemplu, to ate cele patru condi ții de mai sus au fost îndeplinite, dacă spațiile
pentru paleți din buffer și de pe mașină sunt privite ca resurse. Dacă în software -ul de control nu
există prevăzută o rutină pentru detectarea și ieșirea din starea de blocare, o astfel de stare, deși
apărută într -un subsistem, se poate propaga și poate afecta o mare parte a sistemului.
O rețea Petri care modelează un sistem fără stări de blocare este o rețea activă. Aceasta
înseamnă că pentru toate marcajele M, care pot fi accesate din marcajul inițial M o, este posibilă
execuția oricărei tranziții din rețea prin progresul obținut de parcurgerea a câteva secvențe de
execuții. Rețeaua Petri din figura 5 este activă. Cu toate acestea, scenariul de mai sus poate fi prea
strict pentru a repr ezenta anumite sis teme reale care prezintă comportament fără blocaje. Spre
exemplu, inițializarea unui sistem poate fi modelată de o tranziție (sau mai multe) care se execută
de un număr finit de ori. După inițializare, sistemul poate avea un comportament lipsit de blocaje,
deși rețeaua Petri reprezentând acest sistem nu mai este activă, conform cu definiția anterioară. Din
acest motiv, există mai multe niveluri de activare pentru o tranziție t și marcajul Mo. Astfel, o
tranziție t într -o rețea Petri poate f i:
➢ L0-activă (sau moartă) dacă nu există nicio secvență de execuție din L(Mo) în care t să
fie executată,
➢ L1-activă (potențial executabilă) dacă t poate fi executată cel puțin o dată în anumite
secvențe de execuție din L(Mo),
➢ L2-activă dacă t poate fi exec utată de cel puțin k ori în anumite secvențe de execuție
din L(Mo) pentru orice k întreg și pozitiv,
➢ L3-activă dacă t poate fi executată de un număr infinit de ori în anumite secvențe de
execuție din L(Mo),
➢ L4-activă (sau vie) dacă t este L1 -activă (poten țial executabilă) în orice marcaj din
R(Mo).

16
Reversibilitatea și starea de pornire – O problemă importantă în sistemele de operare
reale, precum sistemele de fabricație, sistemele de control al proceselor etc., constă în abilitatea
acestor sisteme de a -și reven i dintr -a situație de eroare. Aceste sisteme trebuie să se întoarcă din
starea care a eșuat la stări corecte anterioare. Această cerință este strâns legată de proprietățile unei
rețele Petri denumite reversibilitate și stare de pornire. Pentru marcaj ul ini țial M o, o rețea Petri este
reversibilă dacă pentru orice marcaj M din R(M o), M o este accesibil din M. Starea de pornire este
o proprietate mai puțin restrictivă, și mult mai practică din acest motiv, decât proprietatea de
reversibilitate a unei rețe le Pet ri. O stare M a unei rețele Petri este stare de pornire dacă pentru
orice marcaj M din R(M o), Mi este accesibilă din M. Rețeaua Petri din figura 2 este reversibilă, iar
rețeaua din figura 3 este nereversibilă.

17
III. Producerea fenomenului de Deadlock
A. Definiție și caracteristici
Într-un sistem de multi programare, procesele necesită resurse. Dacă aceste resurse sunt
utilizate de alte procese, atunci procesul intră într -o stare de așteptare. Cu toate acestea, dacă alte
procese sunt, de asemenea, într -o stare de așteptare, avem de -a face cu apariția fenome nului de
deadlock.
Definiția formală a deadlock -ului este următoarea:
Definiție: Un set de procese se află într-o stare de blocare (deadlock) dacă fiecare proces
din set așteaptă un eveniment care poat e fi cauzat numai de un alt proces din același set.
Deadlock -ul poate apărea dacă se stabilește un model de procese de așteptare.

Figura 7 – Exempul 1
Ambele procese au nevoie de resurse pentru a -și continua execuția. P1 necesită resurs a
suplimentar ă R1 și este în posesia unei resurse R2, P2 necesită resurs a suplimentar ă R2 și este în
posesia lui R1; nici un proces nu poate continua .
Deadlock este o problemă comună în sistemele de multiprocesare , calculul paralel și
sistemele distribuite .
Considerăm d ouă persoane care traversează un râu din direcții opuse – figura 8. Cel mult,
un picior poate fi pe o piatră la un moment dat. Pentru a traversa râul, o persoană trebuie să
folosească fiecare piatră.
Analogie: Fiecare persoană care traversează râul este u n proces, pietrele sunt resursele și
acțiunea de a p ăși pe o piatră reprezintă achiziționarea resursei necesare pentru acel proces.

18

Figura 8 – Exemplul 2
Deadlock poate apărea dacă o persoană începe să traverseze râul fără a verifica mai întâi
dacă altc ineva încearcă să tracă râul din direcția opusă. Două persoane traversează r âul din direcții
opuse și se întâlnesc în mijloc.
Pentru a evita apariția fenomenului de deadlock, fiecare persoană care traversează râul
trebuie să urmeze următorul protocol. În primul rând, fiecare persoană trebuie să se asigure că nu
traversează nimeni din direcția opusă.
Dacă da, trebuie să aștepte până cel care traversează a terminat. În caz contrar, poate trece. Trebuie
luată în considerare și situația în care două persoane vor să traverseze în același timp. Dacă
amândoi t rec, se produce un bloca j (cele două persoane ramân în mijlocul râului). Dacă amândoi
stau, se produce din nou blocaj (cele două persoane așteaptă pentru totdeauna). O soluție ar fi să
oferim prioritate mai mare unei părți a râului astel încât persoana care se afla acolo să poată trece.
Totuși, oferind resurse infinite unei singure părți, blocarea (deadlock) poate încă apărea.
Rezolvarea problemei ar fi de a schimba periodic prioritatea direcțiilor de trecere .
Un sistem are un număr finit de resurse ce pot fi împărțite între proc ese.
Secvența de utilizare a unei resurse necesare pentru producerea unui proces este:
1) Solicită resursa.
2) Folosește resursa.
3) Eliberează resursa.
Dacă resursa nu este disponibilă, atun ci procesul trebuie să aștepte elibera rea acesteia.
Fenomenul de deadlock scoate în evidență faptul că procesul nu -și termină niciodată
executarea și nu eliberează niciodată resursele. Acesta, la rândul său , împiedică alte procese să

19
obțină resursele solicitate. În cele din urmă, nici un proces nu poate continua, toate se opresc și
sistemul „se blochează”.
Un alt exemplu din lume a reală în care apare fenomenul de deadlock: Blocajul în trafic

Figura 9 – Blocaj în trafic
Patru condiții trebuie să existe pentru ca fenomenul de deadlock să apară:
1) Excluderea mutuală : numai un singur proces poate folosi o resursă într -un anumit moment.
Daca alt proces necesită aceeași resură, acesta trebuie să aștepte până cand resursa este
eliberată de primul proces.
2) Ținere și așteptare sau deținerea resurse lor: un proces deține în prez ent cel puțin o resursă
și solicită resurse suplimentare care sunt deținute de alte procese. Dacă acesta trebuie să
aștepte pentru obținerea res usrselor suplimentare, continuă să -și păstreze resursa pe care o
deține.
3) Nepreemptarea : o resursă poate fi eliberată numai în mod voluntar de procesul care o
deține.

20
4) Așteptarea circulară : fiecare proces trebuie să aștepte o resursă care este deținută de un alt
proces, care la rândul său așteaptă ca prim ul proces să elibereze resursa. În general, există
o modali tate stabilită de așteptare a proceselor , P = {P1, P2, …, PN}, astfel încât P1 așteaptă
o resursă deținută de P2, P2 așteaptă o resursă deținută de P3 și așa mai departe până la PN
care așteaptă o resursă deținută de P1.
Aceste patru condiții sunt cunoscute sub numele de Condițiile Coffman de la prima lor aparitie
într-un articol din 1971 scris de către Edward G. Coffman, Jr.
B. Grafuri pentru alocarea resurselor
Aceste grafuri sunt concepute pentru a vedea cu ușurință relațiile de alocare a proceselor și
a resurselor. Nodurile pătrate sunt folosite pentru a reperezenta resursele. Nodurile rotunde sunt
folosite pentru a reprezenta procesele.
Arcul care pornește dintr -o resursă într -un proces reperezintă resursa dețin ută de acel
proces.

Arcul care pornește de la proces la resursă reperezintă procesul care este blocat în prezent
și se află în așteptarea resursei.

Dacă oricare din situațiile anterioa re se regăsește în graf, atunci apare deadlock -ul.

21

• Exemplu de utilizare a grafu rilor pentru alocarea resurselor cu apariția deadlock -ului:
Vom lua în considerare un sistem cu trei procese (A, B, C) și trei resurse (R, S, T)

• Același sistem, dar ordon at diferit

22
C. Fenomenul de deadlock – metode de abordare
1. Ignorarea deadlock -ului
În acestă abordare se presunune că nu va apărea niciodată fenomenul de deadlock. Aceasta
este, de asemenea, o aplicare a algoritmului struțului. Ignorarea deadlock -ului a fo st inițial utilizată
de către MINIX și UNIX. Acestea se utilizează atunci când intervalele de timp dintre aparițiile
deadlock -urilor sunt mari și pierderea de date admisă este tolerabilă.
2. Detecția deadlock -ului
În acestă abordare este examinată starea sis temului pentru a detecta apariția unui blocaj
(deadlock) și ulterior corectarea acestuia. Se folosește un algoritm care urmărește alocarea
resurselor și starea proceselor, se întoarce și se repornește unul sau ma i multe procese pentru a
elimina blocajul găsit. Detectarea unui blocaj care a apărut deja este posibilă , deoarece resursele
pe care fiecare proces le -a blocat și/sau le solicită în prezent sunt cunoscute de planificatorul de
resurse al sistemului de opera re.
După ce deadlock -ul este detectat, poat e fi corectat folosind una din următoarele metode:
➢ Terminarea procesului : unul sau mai multe procese implicate în fenomenul de deadlock
pot fi întrerupte. S -ar putea alege să se anuleze toate procesele implicate în deadlock.
Acest lucru asigură faptul că b locajul este rezolvat cu certitudine și viteză, dar
cheltuielile sunt mari deoarece se v or pierde calcule parțiale. Altă modalitate ar fi să se
întrerupă un proces la un moment dat până când blocajul este rezolvat. Această
abordare are și ea cheltuieli mar i deoarece, după fiecare anulare, un algoritm trebuie să
determine dacă sistemul este încă în deadlock. Mai mulți factor i trebuie luați în
considerare în timp ce alegeți modalitatea optimă pentru terminare, cum ar fi prioritatea
și vârsta procesului.
➢ Preem ptarea resurselor : resursele alocate diferitelor procese pot fi preemptate succesiv
și alocate altor procese până când b locajul este întrerupt.

23
3. Prevenire deadlock -ului
Prevenirea deadlock -ului funcționează prin împiedicarea apariției uneia dintre cele patru
condiții Coffman.
➢ Înlăturarea condiției de excludere mutuală înseamnă că nici un proces nu va avea acces
exclusiv la o resursă. Acest lucru se dovedește imposibil pentru resursele care nu pot fi
extrase. Dar chiar și cu aceste resurse, se poate prod uce deadlock -ul. Algoritmii care evită
excluderea mutuală sunt denumiți algoritmi făra blocare de sincronizare.
➢ Cond ițiile de ținere și așteptare sau deținerea resurselor pot fi eliminate prin necesitatea
proceselor de a solicita toate resursele de care vor avea nevoie înainte de a în cepe (sau
înainte de a se angaja într -un anumit set de operațiuni) . Această cunoaștere avansată este
adesea dificil de satisfăcut și, în orice caz, este o utilizare ineficientă a resurselor. O altă
modalitate este aceea de a co ndiționa procesele să solicite resurse doar atunci când nu au.
Astfel, mai întâi trebuie să elibereze toate resursel e deținute în prezent înainte de a cere
toate resursele de care vor avea nevoie de la zero. Și acest lucru este deseori nepractic.
Aceasta s e întâmplă deoarece resursele pot fi alocate și rămân neutilizate pentru perioade
lungi de timp. De asemenea, un pro ces care necesită o resursă populară poate fi nevoit să
aștepte pe termen nelimitat, deoarece o astfel de resursă poate fi întotdeauna aloca tă unui
anumit proces, rezultând fenomenul de „resource starvation” (acești algoritmi sunt
cunoscuți sub numele de a ll or none algorithms).
➢ Condiția de nepreemptare poate fi dificil sau imposibil de evitat deoarece un proces trebuie
să poată avea o resursă pentru o anumită perioadă de timp sau rezultatul procesării poate fi
inconsistent. Cu toate acestea, incapacitatea de a aplica preemptarea poate interfera cu un
algoritm prioritar. Preemptarea unei resurse blocate implică, în general, o retrocedare și
trebuie evitată, deoarece este foarte costisitoare. Algoritmii care permit preemptarea includ
algoritmi de tipul lock -free și wait -free. Dacă un proces care deține anumite resurse și
necesită alte resurse care nu pot fi alocate imediat, condiția poate fi elim inată prin
eliberarea tuturor resurselor deținute în acel moment.
➢ Condiția finală este așteptarea circulară . Abordăr ile care evită așteptarea circulară includ
dezactivarea întreruperilor în timpul secțiunilor critice și utilizarea unei ierarhii pentru a
determina comandarea parțială de resurse. Dacă nu există o ierarhie evidentă, chiar și
adresa de memorie a resurselor este utilizată pentru a determina ordonarea și resursele sunt

24
solicitate în ordinea crescătoare a enumerării. Soluția lui Dijkstra ( problema filozofilor care
mănâncă este folosită adesea în proiectarea algoritmului concomitent pentru a ilustra
problemele d e sincronizare și tehnicile de rezolvare a acestora) poate fi de asemenea
utilizată.

25
IV. Aplicație practică și mediul de lucru
A. Mediul de l ucru
1. Generalități Matlab
MATLAB este un pache t de programe dedicat calcului numeric și reprezentă rilor grafice.
Elementul de bază cu care operează este matricea, de aici provenind ș i numele său: MATrix
LABoratory. Resursele sale de calcul și reprezentar e grafică sunt bogate, permiț ând operații
matematice fundamentale, analiza datelor, pro gramare, reprezentări grafice 2D și 3D, realizarea
de interfețe grafice etc. Din punct de vedere al construcției sale, MATLAB este alcătuit dintr -un
nucleu de bază în j urul căruia sunt grupate TOOLBOX -urile. Acestea reprezintă niște aplicații
specifice, fi ind de fapt colecții extinse de funcț ii MATLAB care dezvoltă mediul de programare
de la o versiune la alta, pentru a rezolva probleme din diverse domenii. În prelucrar ea numerică a
semnalelor cel mai des utilizat este toolbox -ul SIGNAL PROCESSING .
MATLAB operează cu două tipuri de ferestre:
1. fereastra de comenzi;
2. fereastra pentru reprezentări grafice.
La deschiderea programului MATLAB va apărea pe ecranul calculatorulu i fereastra de
comenzi, având în partea de sus bara de meniuri aferentă. Simbolul “ >>” reprezintă prompterul
MATLAB și se află la începutul fiecărei linii de comandă din fereastra de comenzi. Ferestrele
pentru reprezentări grafice vor apărea atunci când se va cere prin comenzi specifice afișarea unor
grafice.
Matlab utilizat î n calcule numerice
Se bazează pe utilizarea matricelor. Matricele pot fi alcătuite din numere reale sau
complexe. Matlab le folosește pentru a reprezenta diferite informații ca semna le (sub formă de
vectori), imagini, polinoame, date statistice multivaria bile și sisteme liniare.
Dispune de o notație simplistă – nu există o sintaxă complicată de comenzi, care să
trebuiască să fie învățată cu greutate. Acesta favorizează concentrarea d irectă pe problemele
respective si nu pe aspectele tehnice privind progra marea. Prin cuprinzătoarea bibliotecă

26
matematică Matlab, sunt puse la dispoziția utilizatorului peste 500 de funcții matematice, statistice,
științifice și tehnice.
Matlab oferă o vi teză mare de calcul, deoarece codificarea sa în C a fost optimizată cu
grijă, ciclurile interne principale fiind prelucrate în limbaj de asamblare. De aceea Matlab are
avantaje importante atât față de alte pachete software interactive pentru aplicații mate matice, cât
și față de subprogramele C si Fortran corespunzătoare.
Utilizări în calcule numerice:
Matematica generală
o operații cu matrice și câmpuri de date;
o operatori raționali și logici;
o funcții trigonometrice și alte funcții elementare;
o funcții Bessel, β și alte funcții speciale;
o aritmetica polinomială.
Algebra liniară și f uncțiile de matrice
o analiza matriceală, logaritmi, exponențiale, determinanți, inverse;
o sisteme de ecuații liniare;
o valori proprii, descompuneri după valori singulare;
o construirea de matrice;
o operații cu matrice.
Analiza datelor și transformări Fourier
Metode numerice nelianiare
Programe
Tehnici de vizualizare folosind Matlab
Arhitectura grafică bi – și tri- dimensională orientată pe obiect a Matlab -ului oferă un mediu
performant pentr u grafica și analiza vizuală a datelor.
Ca mediu grafic, Mat lab este foarte avantajos, pentru că el dispune de numeroase funcții
speciale necesare în domeniul tehnic. Funcțiile grafice cuprind principalele formate științifice și
tehnice, cum sunt scalele logaritmice, diagramele reprezentate în coordonate polare.

27
Matlab permite realizarea unor grafice performante de culori, cu funcții grafice moderne
în trei dimensiuni, ca diagrame de suprafețe, curbe de nivel tridimensionale, reprezentarea
imaginilor, ani mație, reprezentări volumetrice și multe altele. Prin utiliz area acestor cu 3,4 și chiar
5 dimensiuni este facilitată și cercetarea unor structuri mai complexe de date.
Spre deosebire de pachetele vizuale de evaluare a datelor, unde este vorba de programe
individuale (singulare), care prelucrează date din alte surs e, posibilitățile de prelucrare integrate
de Matlab oferă o libertate nelimitată de analiză, transformare și vizualizare – totul în cadrul
unui singur mediu (unitar).
Programul Handle Graphics car e stă la baza Matlab este construit după o metodă
orientată pe obiect. El oferă modalități simple și performante de adaptare și modificare a
fiecărui aspect elementar al unei diagrame.
În cadrul programului Handle Graphics pot fi deschise în același timp m ai multe ferestre
grafice, în care pot fi definite mai multe sisteme de coordonate. Se poate regla și poziția în care
va apărea imaginea pe pagina imprimată.
Un aspect și mai important este că imaginile pot fi prelucrate dinamic în continuare.
Accesul la " handles" elementare este posibil în orice moment și poate fi modificat practic
fiecare atribut al graficelor: modificarea culorii sau tipului de scris, deplasarea direcțiilor axelor
etc. Acestea și multe alte atribute pot fi definite la conceperea unui gra fic sau pot fi modificate
în timp ce graficul este afișat pe ecran.
Principalele aplicații ale tehnicii de vizualizare sunt:
Grafice bidimensionale;
Grafice tridimensionale;
Vizualizări;
Handle Graphics;
Comanda interfeței grafice cu utilizatorul.
Toolbox urile Matlab
Matlab cuprinde o serie de programe specifice de aplicații, așa -numitele "toolboxes".
Acestea reprezintă niște biblioteci foarte ample de funcții Matlab, care adaptează mediul Matlab
pentru diferite probleme și diverse domenii de utilizare

28
Bibliotecile combină avantajel e software -urilor gata produse (fabricate) cu
productivitatea și flexibilitatea inerente unui mediu tehnic de calcul:
Soluții corecte, de încredere, pentru că fiecare bibliotecă este creată pe baza unei numerici
rapide și fiabi le;
Pentru testarea rezultate lor este disponibilă biblioteca de funcții grafice și de vizualizare;
Ca sistem deschis MATLAB asigură accesul la codul sursă al bibliotecilor, astfel încât
algoritmii și funcțiile să poată fi examinate, adaptate și extinse pen tru a corespunde
necesităților;
Bibliotecile sunt disponibile pentru toate platformele pe care rulează Matlab;
Având Matlab ca bază comună, aceste biblioteci pot fi utilizate cu ușurință împreună. Astfel,
metodele de optimizare și funcțiile de la rețele ne uronale pot fi folosite în rezolvarea
problemelor complexe de prelucrare a semnalelor, iar rezultatele pot fi reprezentate sub forma
unui grafic în culori cu trei dimensiuni, toate acestea realizându -se într -un singur mediu
unitar.
Math Works oferă numero ase bibliot eci, dintre care principalele sunt în următoarele
domenii:
Prelucrarea semnalelor – funcții pentru analiza și prelucrarea semnalelor:
o proiectarea și implementarea filtrelor digitale și analogice;
o analiza spectrală;
o simularea răspunsurilor filtre lor;
o modula re și demodulare.
Prelucrarea imaginilor – funcții pentru maipularea și analiza imaginilor și a semnalelor
bidimensionale:
proiectarea filtrelor bidimensionale și realizarea filtrării;
refacerea și îmbunătățirea imaginilor;
operațiuni de colorar e, operațiu ni geometrice și morfologice;
transformări bidimensionale;

29

analiza imaginilor și statistică.
Rețele neuronale – funcțiile pentru proiectarea și simularea rețelelor neuronale:
o modele neuronale;
o funcții de transfer de rețea, funcții de activare;
o arhitecturi de rețea;
o funcții și grafice pentru analiza calității rețelei.
Logica Fuzzy – funcții pentru proiectarea sistemelor bazate pe logica Fuzzy, cu interfață
grafică cu utilizatorul (GUI):
interfețe grafice interactive cu utilizatorul pentru proiect are Fuzzy;
sprijinirea directă a mecanismelor de învățare adaptive de tip Neuro -Fuzzy;
integrat în SIMULINK pentru simulare dinamică interactivă;
generarea de cod C pentru aplicații în timp real cu Real -Time Workshop.
Statistică – funcții pentru analiza st atistică a datelor, modelare și simulare:
funcții de analiză interactive pe baza GUI;
repartiții de tip ß, binomial, Poisson, etc.;
producerea de numere aleatoare.
Tehnica reglării automate – funcții pentru proiectarea și analiza sistemelor de reglare:
tehnici tradiționale și tehnici moderne;
în timp continuu și în timp discret;
modele reprezentate în spațiul stărilor și ca funcții de transfer;
interacțiunea sistemelor;
transformări între reprezentările modelelor;
reducerea modelului;
reprezentări în domeniu l frecvenței: Bode, Nyquist.
Reglarea robustă – funcții optimizate pentru sinteza sistemelor de reglare robustă.

30

Identificarea sistemelor – prelucrarea semnalelor pentru obținerea modelelor
parametrice.
o Optimizări – Funcții de optimi zare pentru funcționale generale liniare și neliniare.
Proiectarea regulatoarelor neliniare – optimizarea modelelor liniare și neliniare din
SIMULINK, în domeniul timp.
2. Toolboxuri Matlab
Modelele logice sau netemporizate permit studierea proprietatilor calitative ale functionar ii
sistemelor dinamice cu evenimente discrete. O clasa importanta de astfel de modele o constituie
retelele Petri netemporizate. Simularea reprezinta un instrument deosebit de util pentru acest
studiu, în special în cazul în care reteaua Petri i nvestigata poseda un numar ridicat de noduri.
Instrumentul software pe l-am utilizat este reprezentat de pachetul de programe MATLAB
Petri Net Toolbox proiectat special pentru simularea si analiza modelelor de tip re tea Petri. Prin
parcurgerea acestei sedinte de laborator, studentul va acumula cunostintele necesare folosirii Petri
Net Toolbox pentru simularea modelelor de tip retea Petri netemporizata. De asemenea, studentul
va dobândi un solid suport intuitiv în înte legerea mo dului de operare a retelelor Petri netemporizate
gratie facilitatilor de animatie puse la dispozitie de acest mediu de simulare.
Petri Net Toolbox (PN Toolbox ) a fost conceput spre a oferi instrumente specifice pentru
simularea, analiza si sin teza sistem elor cu evenimente discrete. Includerea sa ca un modul de sine
statator în mediul MATLAB prezinta un deosebit avantaj (în raport cu alte software -uri dedicate
formalismului retelelor Petri) prin crearea unor multiple facilitati de calcul algebri c si statis tic
precum si de reprezentari grafice, care exploateaza rutinele disponibile în MATLAB. Schimbul de
informatii dintre utilizator si PN Toolbox se face prin intermediul unei interfete grafice (eng.
Graphical User Interface – GUI) (The MathWorks, Inc. 2000a, 2000b) care da posibilitate
utilizatorului de a desena, salva, încarca si modifica modele de tip retea Petri. De asemenea,
permite simularea si analiza retelelor Petri, exploatând toate resursele informationale ale mediului,
prin intermediul variabilelor globale pastrate în spatiul de lucru (Workspace) MATLAB. Interfata
este lansata în executie prin c omanda MATLAB .
>> pntool

31
Acest GUI consta dintr -o fereastra MATLAB continând opt componente:
➢ (1) Menu Bar,
➢ (2) Quick Access Toolbar,
➢ (3) Drawing Area,
➢ (4) Drawing Panel,
➢ (5) Simulation Panel,
➢ (6) Status Panel,
➢ (7) Draw/Explore Switch,
➢ (8) Message Box .
Figura 10 prezint a o captura a ferestrei principale a PN Toolbox, unde sunt vizibile toate
partile componente ale interfetei grafice enumerate mai sus.

Figura 10 – Interfata grafica a PN Toolbox
Menu bar (plasata orizontal, în partea de sus a ferestrei) afiseaza un set de noua meniuri
deunde utilizatorul poate selecta toate facilitatile disponibile si anume:
➢ meniul File (care contine submeniurile: New Model, Open Model, Close Model,Save
Model, Save Model As.. si Exit PNToolbox) ofera facilitati pentru lucru cu fisiere;

32
➢ meniul Modeling (ce include submeniurile Add Place, Add Transition, Add Arc, Add
Token, Add Color Set, Edit Object si Conflicting Trans itions) ofera mijloace pentru
editarea grafica (pozitii, tranzitii, arce, marcaje si etichete) în zona de dese nare (3) si
permite specificarea de informatii suplimentare (prioritati si/sau probabilitati) pentru
regula tranzitiei folosita în derularea simul arii;
➢ meniul View, (cu submeniurile: Zoom In, Zoom Out, Show Grid si Arc Weight) permite
alegerea conditiilo r pentru vizualizare s i simulare;
➢ meniul Properties (ce cuprinde submeniurile: Incidence Matrix, Behavioral – Coverability
Tree, Structural, Invaria nts) furnizeaza metode adecvate pentru analiza proprietatilor
comportamentale si structurale ale retelelo r Petri.
➢ meniul Simulation (continând submeniurile: Event, Run slow, Run fast, Breakpoints,
Reset, Log File, View History si Preferences) da utilizator ului posibilitatea de a controla
progresul simularii si de a înregistra rezultatele;
➢ meniul Performan ce (incluzînd submeniurile: Place Indices si Transition Indices) ofera
informatii asupra diferitilor indicatori de performanta globala obtinuti la sfârsitu l
simularii;
➢ meniul Max -Plus (ce cuprinde submeniurile: From PN si From Matrices) ofera
instrumente pentru studierea retelelor cu pozitii temporizate, grafuri marcate, cu ajutorul
algebrei max -plus;
➢ meniul Design permite studierea indicatorilor de performa nta în procedura de sinteza;
➢ meniul Help (continând submeniurile: Contents and Index, Demos si About PNToolbox)
ofera informatii pentru exploatarea PNToolbox de catre utilizator.
Quick Access Toolbar (plasat ca o bara orizontala sub Menu bar) contine mai multe
butoane ale caror actiuni sunt similare cu unele optiuni din meniul File si din meniul V iew.
Drawing Panel (plasat vertica l în partea stânga a ferestrei din fig ura 10 , sub Quick Access Toolbar)
este format dintr -un numar de butoane cu actiuni simila re unor optiuni din meniul Modeling.
Butonul Edit permite accesarea caracteristicilor nodurilor si arcelor retelei Petri prin intermediul
unei ferestre de dialog asociata obiectului selectat în Drawing Area.
Aceste proprietati sunt: capacitate, marcaj, i nformatii legate de temporizare si etichete –
pentru pozitii; informatii legate de temporizare si etichete – pentru tranzitii; pondere si existenta

33
functiei inhibitoare – pentru arce. Figura 11 reproduce ferestre de dialog asociate cu cele trei
elemente me ntionate anterior în cazul retelelor Petri netemporizate. Optiunea Color (care apare în
toate ac este ferestre, indiferent de natura elementului) creeaza posibilitatea de a atribui culori
diferite elementelor introduse în diferite faze ale proiectarii atunc i când se face apel la o procedura
de sinteza constând în succedarea mai multor etape.
Simulatio n Panel (plasat vertical, în partea stânga a ferestrei în fig ura 10 , sub Drawing
Panel) contine un set de butoane ale caror actiuni sunt similare celor din me niul Simulation si
asigura facilitati suplimentare pentru vizualizarea evolutiei indicilor de perfo rmanta în cazul
retelelor temporizate. Status Panel este o tabela de mesaje (plasata în coltul din stânga jos al
ferestrei din figura 10 ) unde PN Toolbox afi seaza valoarea curenta a numarului de evenimente,
timpul scurs de la începutul simularii precum si n umele fisierului activ.
Drawing Area (localizata în centrul ferestrei din figura 10 ) este o fereastra unde vor fi
plasate nodurile si arcele retelei Petri si este prevazuta cu butoane de scroll (în partea dreapta si în
partea de jos) pentru deplasare în ace asta fereastra.

Figura 11 – Ferestrele de dialog controlate de butonul Edit din Simulation Panel asociate:
pozitiilor (a), tranzitiilor (b) si arcelor (c) în cazul retelelor netemporizate
Draw/Explore Switch (plasat imediat sub Drawing Panel) permite comutarea în tre cele
doua moduri ale PN Toolbox : modul de desenare si modul de simulare/analiza . Message Box
este utilizat de PN Toolbox pentru a furniza informatii utile catre utilizator. În modul de desenare,

34
este prezentata starea lui Drawing Panel, iar în modul de simulare/analiza sunt afisate mesajele
atasate tranzitiilor.
B. Implementarea aplicației și rezultate experimentale
Acest capitol propune o ab ordare de sinteză iterativă aplicată în Petri Net (PN) bazată pe
prevenirea fenomenului de deadlock în sistemele de fabr icatie flexibile (Flexibile Manufacturing
Systems – FMS). Având în vedere modelul PN (PNM) al unui FMS predispus la apariția deadlock –
ului, obiec tivul este de a sintetiza un model PN viabil . Aplicarea sa pentru controlul FMS
garantează funcționarea fără deadlock și performanțe ridicate în ceea ce privește utilizarea
resurselor și transferul de sistem. Metoda propusă este o abordare iterati vă. La fiecare iterație, este
întâlnit un marcaj „rău” (marcaj d e deadlock) din graful de accesibilitate al unui model dat PN.
Obiectivul este de a preveni ca acest marcaj să nu atingă invarianții d e poziție ale modelului . O
metodă de control bazată pe inv arianți este folosită pentru a dobândi o poziție de control . Acest
proces se desfășoară până când modelul devine viabil . Metoda propusă este în general aplicabilă,
ușor de utilizat, eficientă și directă .
Sistemele de fabricație flexibile (Flexibile Manuf acturing Systems – FMS) constau dintr –
un număr limitat de resurs e partajate folosite pentru a produce diferite piese. Componentele intră
în FMS în funcție de o valoare predefinită (sau parțial predefinită) de operații prin setul sistemului
de resurse și su nt procesate simultan. Deadlock este o situație foarte nedorită, în care fiecare set
de poziții (sau mai multe seturi) rămân e în așteptare pe termen nelimitat până când altă funcție din
secvența de producție eliberează resursele. Deadlock -urile pot apărea ca un număr de funcții ce
trec simultan prin FMS și sunt în gene ral dificil de prezis. Prin urmare, este necesar folosirea unei
metode de control eficientă în FMS pentru a garanta că starea de deadlock nu va apărea niciodată.
Mulți cercetători au abordat p roblema deadlock -ului într -un FMS. În general, sunt folosite tre i
condiții pentru a rezolva problema apariției deadlock -ului în FMS: detecția și recuperarea, evitarea
și prevenirea deadlock -ului.
În această secțiune este prezentată o metodă de prevenire a deadlock -ului baz ată pe modele
PN provenită din lucrarea raportată la [12]. Mai întâi, să reamintim pe scurt metoda propusă în
[12]. Analiza grafului unui model PN într -un FMS este punctul de plecare pentru definire a
metodei. Graful modelului PN este real izat din zone de deadlock și zone fără deadlock. Zonele de
deadlock poate conține stări de bloc are, stări parțiale de blocare și stări care inevitabil conduc la

35
apariția fenomenului de deadlock sau livelo ck. Zonele fără deadlock sunt constituit e din stăril e
bune aflate în graf , reprezentând comportamentul optim al sistemului. Metoda se bazează pe
excluderea zonelor de deadlock din graful de accesibilita te, asigurându -se că fiecare stare din DF Z
poate fi în continuare atinsă .
Input: Modelul PN al unui FMS pr edispus la deadlock;
Output: Un model controlat PN viabil pentru FMS, (PNC);
1) Calculați graful de accesibilitate
1, 0,1,2iRG i+=
al modelului Petri Net
1, 0,1,2iPNC i+=
(
i PNC PNM= pentru prima iterație)
2) Dacă
1, 0,1,2 ,iPNC i+=
este viabil, atunci ieșiți;
3) Găsiți FBM (
1, 0,1,2i FBM i+=
) în cadrul
1, 0,1,2iRG i+=
considerând evoluți a
sistemului de la
1iLZ+ la
1, 0,1,2 ;iDZ i+=

4) Definiți un invariant de poziție (
1, 0,1,2iPI i+=
) din subsetul de poziții de tip operație al
1, 0,1,2i FBM i+=
;
5) Calculați poziția de control
1, 0,1,2 ,iCi+=
pentru invariantul de poziție
1, 0,1,2iPI i+=
folosind metoda bazată pe controlul invarianților (Capitolul 5) ; și
6) Adăugați poziția de control calculată
1, 0,1,2 ,iCi+=
în modelul PN și mergeți la pasul
1(
11: , 0,1,2 ,i i i iPNC PNC C i PNC PNM++= + = =
pentru prima iterație) .
În contextul FMS, numărul de stări „bune ” (stări ce nu conțin deadlock ) dintr -un model
PN, care pot fi furnizate în cadrul procesului de prevenirea deadlock -ului, au fost considerate ca
fiind o „măsură de calitate ”. În ceea ce privește implementarea practică a acestor metode, calitatea
modelului implică o eficiență ridicată , număr mare de cl ienti serviti î n unitatea de timp și
flexibilitate. În literatura de specialitate, există multe metode de prevenirea deadlock -ului propuse
pentru FMS, dar în general aceste metode oferă un comportament suboptimal al sistemului care
duce la degradarea perfo rmanțelor sistemului. În acest sens, metoda propusă este ușor de utilizat,
foarte eficientă și directă. A fost testată împotriva tuturor modelelor semnificative PN predispuse
la deadlock existente în literatură. Pentru orice PN (finit sau infinit), problem a stabilirii dacă o
stare este bună sau rea este NP-hard. Cu toate acestea, noi folosim un model PN finit , adică arborele
de accesibilitate conține toate marcajele accesibile. Delimitarea stărilor bune de cele rele este ușor
de observat în arborele de acce sibilitate. Pentru acest ă problemă se utilizează pntools , în care este

36
furnizat un model PN cu zone de deadlock . De la
1, 0,1,2iDZ i+=
după care alegem prima intrare
ca fiind
1, 0,1,2i FBM i+=
.
Marcajele m și m′ marchează în mod egal un set de poziții S dacă și numai dacă ∀ p ϵ S,
m(p) = m(p′) .
Observația 1: La orice FBM, cel puțin două poziții de tip operație sunt marcate.
Acest lucru se datorează faptului că, în orice model PN al unui FMS, este imposibil de a
avea deadlock dacă se ex ecută doar o singură poziție (implicând că doar o poziție de tip operație
este marcat ă). Așteptarea circulară nu este posibilă.
Considerăm exemplul FMS din figura 12 . Este compus din doi roboț i, R1 și R2, fiecare
putând să ț ină câte o piesă pe rând , și trei mașini, notate M1 – M3.

Figura 12 -Exemplu F MS

37
Figura 13 – Modelul PN al unui FMS
M1 poate procesa câte o piesă pe rând, în timp ce M2 și M3 pot procesa câte două piese.
I1 și I2 reprezintă două buffere de încărcare, O1 – O3 reprezintă trei buffere de descărcare. Zonele
de acțiune ale robotului R1 sunt I1, M1 și M2, iar pentru robotul R2 sunt M2 și M3. Din motive
de simplitate, se presupune că introducerea pieselor de la I2 la M3 și ieșirea pieselor de l a M1 la
O1, de la M3 la O2 și de la M2 la O3 reprezintă partea de operații de prelucrare.
Așa cum este prezentat în Fig. 1(b), sunt considerate două tipuri de piese: P1 și P2. P1 este
luat de la I1 de către R1 și este descărcat fie în M1 fie în M2. După c e a fost procesat de M1, P1
este mutat la O1 de către M1. După ce a fost încărcat în M2, P1 este procesat de M2 și transportat
de la M2 la M3 de către R2. După ce a fost procesat de M3, P1 mutat la O2 de către M3. Analogic,
P2 este luat de la I2 de către M 3, și după ce este procesat de M3 este transportat de la M3 la M2
de către R2. Într -un final, după ce este procesat de M2, P2 este mutat la O3 de către M2.
Figura 1 3 prezintă modelul PN. Inițial, se presupune că nu sunt piese în sistem. În modelul
PN sunt 15 poziții, P = {p1 –8, p11 –15, p21 –22}, și 11 tranziții T = {t1 –11}.

t1 Vine piesa de tipul 1 – P1 (I1).

38
p1 Transport cu robotul 1 (TR1) .
p2 Prelucrare pe mașina 1 (PM1).
p3 Prelucrare pe mașina 2 (PM2).
p4 Transport cu robotul 2 (TR2).
p5 Prelucrare pe mașina 3 (PM3).
t7 S-a terminat prelucrarea piesei de tipul 1(cu ieșire la O2).
t3 S-a terminat prelucrarea piesei de tipul 1(cu ieșire la O1).
p12 Reprezintă mașina 1 (M1).
p21 Paleta pentru piesa de tipul 1.
t8 Vine piesa de tipul 2 – P2 (I2).
p6 Prelucrare pe mașina 3 (PM3).
p7 Transport cu robotul 2 (TR2).
p8 Prelucrare pe mașina 2 (PM2).
t11 S-a terminat prelucrarea piesei de tipul 2(cu ieșire la O3).
p11 Reprezintă robotul 1 (R1).
p14 Reprezintă robotul 2 (R2).
p13 Reprezintă mașina 2 (M2).
p15 Reprezintă mașina 3 (M3).
p22 Paleta pentru piesa de tipul 2

TABELUL I
Poziția de control C 1 obținuă la prima iterație
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 μ₀
C1(p31) 0 0 0 0 -1 1 0 -1 1 0 0 2

TABELUL II
Poziția de control C2 obținuă la a doua iterație
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 μ₀

39
C2(p32) 0 0 0 -1 1 0 0 -1 1 0 0 3

TABELUL III
Poziția de control C3 obținuă la a treia iterație
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 μ₀
C3(p33) 0 0 0 -1 1 0 0 0 -1 1 0 2

Figura 14 – Modelul de control PN (PNC3) viabil și maxim permisiv
Matricea de incidență al modelului din figura 13 este:

40

1 1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1
1 1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0 1 1 0
0 0 0 0 0 1 1 1 1 0 0
1 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 1pD−−
−
 −
−
 −− 
 −
=−
−
−
−−
−−
−−
−
− 





















 

Marcajul inițial fiind

 0 1 2 3 4 5 6 7 8 11 12 13 14 15 21 22T
pX               =

 0000000001 121 175 .T
p=

Pentru a impune restricția μ₄ + μ₆ ≤ 2, folosim notația matricei după cum urmează :

  0 0 0 1 0 1 0 0 0 0 0 0 0 0 0TL= , b=2.

Model ul PN nu satisface restricția dorită fără introducerea unei poziții de control. Este
introdusă variabila μc astfel încât inegalitatea μ₄ + μ₆ ≤ 2 devine
μ4 + μ6 + μc = 2.

Matricea de incidență a controller -ului este compusă după cum urmează:

  0 0 0 0 1 1 0 1 1 0 0 .cpD LD=− = − −

41
Marcajul inițial al poziției de control este calculat după cum urmează
00 2cpbL= − = .
Poziția de control C1 (dnumită și p31 folosită in pntools) obținută la acestă iterație este prezentată
în Tabelu I.
Petru a doua iterație, modelul PN este obținut prin adăugarea lui C1 în model, adică
11: PNC PNM C=+
. Atunci când
1PNC este analizat folosind pntools se observă că sunt 360 de
stări în graful de accesibilitate RG 2. Acest lucru înseamă că atunci când adăugăm C1 la modelul
PN, numărul stărilor din RG 1 se reduce la 20. Analizând modelul PN pentru poziția de contro l 1,
vom descoperi că sunt 24 stări de deadlock și 336 stări bune.
La iterația i = 1,vom alege FBM în ca re p3 și p6 sunt marcate cu două jetoane fiecare. Prin
urmare, trebuie să impunem un invariant de poziție
2 3 6 3 PI= +  . Acesta duce la poziția de
control C2 (p32) asa cum este prezentat în Tabelul II.
Analizând modelul PN pentru poziția de control 2
2 1 2: PNC PNC C=+ vom descoperi că
sunt 16 stări de deadlock și 336 stări bune. La iterația i = 2, vom alege FBM și continuăm același
proces pentru a calcula C3 așa cum este prezentat în Tabelul III .
Pentru a patra și ultima iterație,
3 2 3: PNC PNC C=+ . Analizând modelul PN pentru poziția
de control 3, se observă că este viabil cu 336 stări bune în graful de accesibilitate. Procedura se
termină cu un model de contro PN viabil așa cum este prezentat în figura 14.

42
V. Concluzii

Starea de deadlock reprezintă o problemă majoră în sistemele de operare cât și în cele de
fabricație. În orice caz există cateva tehnici care se ocupă cu rezolvarea acestei probleme cum ar
fi evitarea, prevenirea deadlock -ului etc. și cu toate acestea starea de deadlock poate încâ apărea.
Singura modalitate de a face față dea dlock -ului atunci când apare este detecția acestuia și
rezolvarea cât mai curând posibil. În acestă lucrare sunt menționate mai multe tehnici de rezolvare
a deadlock -ului ce pot fi folosite pentru a evita aceast fenomen.
Prin lucrarea de fa ță am reu și să analizez o si tuație de apariție a fenom enului de deadlock.
Modelele logice sau netemporizate permit studierea proprietatilor calitative ale functionar ii
sistemelor dinamice cu evenimente discrete. O clasa importanta de astfel de modele o constituie
retelele Petri netemporizate. Simularea reprezinta un instrument deosebit de util pentru acest
studiu, în special în cazul în care reteaua Petri i nvestigat ă posed ă un numar ridicat de noduri.
În teoria retelelor Petri netemporizate se considera ca executarea unei tranzitii nu consuma
timp si ca jetoanele pot ramâne în pozitii pentru orice durata de timp (oricât de mica sau oricât de
mare). întrucât executa rea unei tranzitii este instantanee, se considera ca tranzitiile se executa
numai secvential, adica nu se poate vorbi de doua tranzitii executate simultan (sau în paralel).
Aceste presupuneri fac ca modelul de tip retea Petri netemporizata sa fie utilizat numai pentru
investigarea proprietatilor logice, calitative, care nu depind de timp.
Lucrarea de față este structurată pe cinci capitole ce cuprin d informații despre modele de
rețele de tip Petri, fenomenul de deadlock, toolboxul Petri Net, dar și un exemplu de proces ce
conține deadlo ck. În capitolul patru este prezentat ă o metodă iterativă pentru rețelele Petri bazată
pe prevenirea deadlock -ului pentru un sistem de fabricație flexibil (FMS). Sub condiția de
optimitate, se poate ști dacă putem sintetiza un model controlat Petri Net viabil.

43
Bibliografie
[1] Octavian Păstrăvanu, Mihaela Matcovschi, Cristian Mahulea, Aplicații ale rețelelor Petri
în studierea sistemelor cu evenimente discrete , Editura Gheorghe Asachi, 2002.
[2] http://users.metu.edu.tr/halici/courses/442/Ch5%20Deadlocks.pdf
[3] Andrew S. Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice -Hal.
[4] http://www.sjsu.edu/people/robert.chun/courses/cs159/s0/Day -7–Deadlock.pdf
[5] M. Samek, Application Note Dining Philosoph ers Problem (DPP) Example, USA:
Quantum Leaps, 2012.
[6] Reggie D avidrajuh, Verifying Solutions to the Dining Philosophers Problem with
Activity -Oriented Petri Nets, 2014 4th International Confer ence on Artificial Intelligence
with Applications in Engineering and Technology .
[7] K. Yamalidou, J. Moody, M. L emmon, and P . Antsaklis, “Feedback control of Petri nets
based on place invariants,” Automatica , vol. 32, no. 1, pp. 15 –28, Jan. 1996 .
[8] Boissel. O . (1993). Optimal fccdhach control design I’ oIdiscrete -event process systems
using simulated annealing. MS thesis. University of Notre Dame.
[9] Ramadge. P. J. G. and W. M. Wonham (1989). The control of discrete event systems.
Proc. IEEE, 77, 81 -97.
[10] Wonham. W. M. and P. J. Ramadgc (1987). On the supremal controllab le sublanguage of
a given language. SIAM J. Control Optim.. 25, 637 -659.
[11] N. Visvanadham, Y. Nahari, and T. L . Johnson, “Deadlock prevention and deadlock
avoidance in flexible manufacturing sy stems using Petri net models,” IEEE Trans.
Robot. Autom. , vol. 6, no. 6, pp. 713 –723, Dec. 1990.
[12] M. Uzam, “An optimal deadlock prevention po licy for flexible manufacturing systems
using Petri net model s with resources and the theory of regions,” Int. J. Adv. Manuf.
Technol. , vol. 19, no. 3, pp. 192 –208, 2002 .