 |
|
 |  |
|
|
| |
 | Biologie | Chimie | Didactica | Fizica | Geografie | Informatica |
| Istorie | Literatura | Matematica | Psihologie |
Scopul cursului: furnizarea de cunostinte de baza despre tehnologiile fundamentale de programare concurenta: aspectele teoretice privind procesele si threadurile, precum si instrumentele de coordonare a acestora.
Structura : Concepte abstracte utilizate in descrierea concurentei (paradigme de programare nesecventiala, notiunile de proces si thread, relatia procese - thread-uri, scheme de specificare a programelor concurente, situatii de exceptie generate de concurenta, mecanisme de control al concurentei, comunicare si sincronizare, mecanisme de control asincron sau partial sincron, probleme specifice care se rezolva cu ajutorul concurentei),
Programare concurenta la
nivel de proces (procese
Unix, Windows, Java, comunicarea prin pipe intre procese, comunicarea intre
procese folosind mecanismul de memorie partajata, sincronizarea proceselor
folosind semafoare, comunicarea prin cozi de mesaje).
Programare concurenta la nivel de thread-uri (caracteristici generale, exemple de probleme
rezolvabile prin thread-uri pe diverse platforme : Unix, Windows, evaluarea
unor performante ale programelor cu thread-uri.
Scop laborator : aspectele practice tratate au in vedere facilitatile de lucru cu procese si threaduri oferite de catre sistemele de operare Unix (Linux), Windows si de catre distributia Java (standard).
Structura
Bibliografie
1. BACON J., Concurrent Systems, Addison-Wesley, England, 1998.
2. BARRY A., Concurrent Programming, https://www.csm.uwe.ac.uk/personal/am-barry/ Q2H611/ concprog.html
3. BOIAN F.M., FERDEAN C. M., BOIAN R.F. DRAGOS R.C. Programare concurenta pe platforme Unix, Windows, Editura Albastra - grupul Microinformatica, Cluj, 2002.
4 FLYNN M. J., Some Computer Organizations and their Effectiveness, IEEE Transactions on Computers, C-21, 1972
1.1 Introducere
In sistemele de operare programele ruleaza sub forma de procese. La randul lor, programele pot fi formate din secvente de cod ce pot rula in paralel si concurent (secvente numite fire de executie-threaduri).
Asa cum s-a invatat la sistemele de operare se va folosi termenul de proces in sens mai larg - privit ca si o sarcina de calcul, sau o entitate de calcul - atat pentru procesul propriu-zis, cat si pentru thread. Aceste procese sau secventele lor necesita calcule concurente ce pot interactiona si necesita resurse . din acest motiv trebuie studiata concurenta la nivelul unui proces si la nivelul unui fir de executie - thread
Conceptele care vor fi prezentate in acest curs sunt folosite, in principal, la nivelele de proces si thread. Ele raman insa valabile, cu adaptarile de rigoare, atat in programarea distribuita.
Programarea concurenta este activitatea de construire a unui program continand procese multiple care se executa in paralel. Aceste procese sunt in competitie pentru accesarea resurselor critice si coopereaza pentru realizarea anumitor task-uri. Avand data specificatia problemei care trebuie rezolvata decizia care trebuie luata este cum trebuie ea impartita in procese si cate anume sunt necesare si mai ales cum trebuie acestea sa interactioneze. Aceste decizii sunt influentate de natura aplicatiei si de hardware-ul pe care va fi rulat programul. O alta problema critica ce se cere a fi rezolvata este modul in care interactiunea intre procese este sincronizata.
In cursul de fata ne vom axa pe programele imperative care admit o concurenta, comunicare si sincronizare explicite. In particular , procesele sunt programe secventiale care executa o secventa de instructiuni; procesele comunica si se sincronizeaza prin operatii de scriere si citire a variabilelor partajate sau prin emiterea si receptionare de mesaje. Aceasta comportare vine in contrast cu programele declarative, ca de ex. programele din programarea functionala sau logica, in care concurenta este in cele mai multe cazuri implicita si nu exista conceptul de stare a programului. In programele declarative, parti independente din program se pot executa in paralel; ele comunica si se sincronizeaza in mod implicit in momentul in care o parte depinde de rezultatul produs de o alta.
Programele sunt adesea modelate ca un numar de sarcini de calcul distincte, care interactioneaza pentru a executa serviciul sau pentru a produce rezultatul dorit. In cazul programarii secventiale, un program este implementat ca o singura entitate complexa, care executa mai multe functii (parti diferite din program). Functiile se executa intr-o ordine bine determinata: reluarea executiei in acelasi context conduce intotdeauna la aceeasi succesiune a functiilor.
In general, executia unui program secvential este determinista. Astfel, pentru acelasi set de date de intrare, programul executa aceeasi secventa de instructiuni si produce aceleasi rezultate. Paradigma programarii secventiale are doua caracteristici de baza:
Nici una dintre aceste doua proprietati de baza nu sunt valabile in cazul programarii nesecventiale.
Programarea nesecventiala presupune implementarea mai multor entitati de program, care pot fi executate in acelasi timp si carora li se asociaza sarcini de calcul distincte ce furnizeaza parti ale rezultatului final. Deoarece executiile entitatilor se pot desfasura simultan, ordinea lor nu este complet previzibila, existand un oarecare grad de nedeterminism in timpul executiei.
Paradigmele de programare nesecventiala difera intre ele prin tipul sistemului de calcul pe care se executa entitatile concurente: sistem monoprocesor, multiprocesor, sistem distribuit. De asemenea, paradigmele difera si dupa modul cum sunt partajate de catre entitati informatiile de context si resursele sistemului. In sfarsit, paradigmele mai difera dupa gradul de interactiune intre entitati si in functie de existenta unei 'autoritati tutelare' care sa asigure coordonarea entitatilor.
Paradigmele de programare nesecventiala pot fi grupate in trei mari categorii:
Dintr-un anumit punct de vedere, fiecare dintre ele include pe cele dinaintea ei. In sectiunile urmatoare vom vedea ce este specific fiecareia, avantaje, dezavantaje si sfere de aplicabilitate.
Programarea paralela presupunde dezvoltarea de programe care lanseaza mai multe sarcini de calcul: entitati de executie, taskuri, procese, thread-uri (dupa caz). Acestea sunt executate simultan si coopereaza in vederea realizarii unui scop comun. Deosebirea fundamentala (conceptual vorbind) a programarii paralele fata de alte paradigme nesecventiale consta in faptul ca sarcinile de calcul se coordoneaza numai prin operatii de asteptare a inceperii sau a terminarii altor entitati implicate. Astfel, lansarea in executie a unei sarcini de calcul poate fi conditionata de startul prealabil al altora, respectiv de terminarea activitatilor altor sarcini de calcul.
Domeniul calculului numeric abunda in algoritmi paraleli, necesari pentru a realiza mai repede acele calcule uriase. La loc de cinste in cadrul acestora sunt algoritmii paraleli specifici algebrei liniare: determinanti, matrice etc.
Punctam cateva trasaturi caracteristice ale programelor paralele:
Un program paralel consta din unul sau mai multe sarcini de lucru (task-uri). Aceste task-uri se executa simultan si numarul lor poate varia in timpul executiei programului.
Fiecare task incapsuleaza un program secvential si o memorie locala. De fapt, un task reprezinta o masina virtuala von Neumann. (O masina von Neumann contine o unitate centrala de procesare -CPU - conectata la o unitate de memorare si executa operatii de citire si scriere asupra unor date din memoria atasata.)
Task-urile pot fi atasate procesoarelor fizice in diverse moduri, dar aceasta atasare nu afecteaza semantica programului. In particular, unui singur procesor ii pot fi atasate mai multe taskuri.
Se pot defini interfete de comunicare intre aceste task-uri si, de asemenea, modalitati de acces la resursele comune, in conformitate cu modelul de paralelism folosit.
In practica sunt utilizate mai multe modele de paralelism, diferentiate dupa caracteristicile task-urilor. Prezentam in continuare cateva dintre acestea.
Modelul de paralelism bazat pe task-uri si canale se caracterizeaza prin faptul ca fiecare task are asociat un set de porturi de intrare (inports) si un set de porturi de iesire (outports), conectate intre ele prin cozi de mesaje numite canale. Aceste canale pot fi create sau sterse dinamic. Un task poate executa operatiile:
creare / stergere canale;
citiri de la porturile de intrare / scrieri la porturile de iesire;
creare / stergere de alte taskuri.
Figura 2.1 prezinta imaginea globala a unui proces de calcul. El consta dintr-un set de task-uri reprezentate prin cercuri si imaginea detaliata a unui singur task. In cadrul unui task s-a evidentiat pe de o parte setul lui de instructiuni (primul dreptunghi), iar pe de alta parte unitatea de memorie locala (celalalt dreptunghi). Interfata externa este asigurata printr-un set de porturi (ilustrate prin sagetile ce pleaca de la instructiuni spre exterior). Task-urile sunt conectate prin canale, reprezentate prin sageti. Un canal reprezinta o coada de mesaje in care sunt plasate, respectiv din care sunt extrase mesaje.
Figura 0.
Modelul taskuri si canale
Modelul bazat pe schimb de mesaje (message-passing) Programele dezvoltate dupa acest model, la fel ca si programele create pe modelul taskuri si canale, creeaza task-uri multiple. Fiecare task este identificat printr-un nume si incapsuleaza date locale. Task-urile interactioneaza trimitand si primind mesaje la, respectiv de la task-uri specificate prin nume. Cele doua modele difera numai prin mecanismul folosit pentru transferul datelor. La primul model se vorbeste de 'trimis mesaje pe canalul x", iar la al doilea 'trimis mesaje task-ului n".
Modelul de paralelism al datelor exploateaza concurenta care deriva din aplicarea aceleiasi operatii mai multor elemente dintr-o structura de date. De exemplu, "adauga 2 la elementele unui tablou" sau "mareste salariul tuturor angajatilor cu x lei". Programatorul are sarcina de a preciza cum sunt partitionate datele in task-uri.
Din trasaturile si din modelele prezentate mai sus, se desprind patru proprietati de baza ale programelor paralele: concurenta, scalabilitate si modularitate
Concurenta se refera la posibilitatea de a executa mai multe actiuni simultan. Ea este o proprietate esentiala, mai ales daca programul se executa pe un sistem multiprocesor.
Scalabilitatea presupune functionarea programului, cel putin la aceiasi parametri de performanta, daca numarul de procesoare creste.
Modularitatea implica descompunerea unor entitati de executie complexe in componente mai simple. Evident, aceasta proprietate nu este specifica numai programarii paralele, ci si altor paradigme de programare si proiectare.
Elementul esential prin care se deosebeste programarea concurenta de cea paralela este faptul ca sarcinile de calcul coopereaza intre ele in timpul executiei. Desi problema este descompusa in subprobleme relativ independente, executia acestor task-uri poate sa fie intercalata si urmeaza un scenariu de paralelism la nivel logic. Doua task-uri active pot face schimb de informatii, pot sa astepte unul dupa altul etc.
Pentru comunicarea si sincronizarea elementelor de executie implicate in programul concurent, s-au dezvoltat diverse mecansime specifice, asupra carora vom reveni in sectiunile urmatoare. Tot in sectiunile urmatoare vom da cateva exemple de probleme care implica utilizarea paradigmei programarii concurente.
Una dintre problemele tipice de programare concurenta este problema producatorului si a consumatorului. Pe scurt, ea se enunta astfel: Exista un recipient capabil sa depoziteze in el un numar maxim de obiecte. Asupra recipientului actioneaza doua categorii de procese: procese producatoare si procese consumatoare. Un producator fabrica un obiect si il depune in recipient. Un consumator extrage un obiect din recipient. Se presupune ca exista cel putin un proces producator, cel putin un proces consumator si ca procesele producatoare si consumatoare evolueaza in paralel. Pentru disciplinarea accesului la recipient, se impun trei conditii:
In sectiunile urmatoare vom reveni asupra acestei probleme, precizand inclusiv modelul formal de descriere a executiei. Tot acolo vom prezenta si alte probleme tipice.
Atat concurenta cat si paralelismul necesita acces controlat la resurse partajate precum: dispozitive de I/O, fisiere, inregistrari din baze de date, structuri de date globale, etc. Conceptul de paralelism este implicit mai apropiat de hardware, fiind dependent mai mult de caracteristicile masinii. Conceptul de concurenta este mai apropiat de software, fiind o proprietate stabilita in principal de proiectantul programului.
Tehnicile de programare concurenta se folosesc pentru a structura programe care implica mai multe activitati, consumatoare de timp sau computational intensive, executate concurent sau programe care trateaza evenimente asincrone.
Pentru a concepe modele de programare concurenta independente de hardware, se asociaza fiecarei entitati executabile din program un procesor logic. Fiecare procesor logic este o masina secventiala care executa pe rand instructiunile din procesul alocat. Mai multe procesoare logice corespund unui procesor fizic. Acesta are implementat un mecanism de planificare pentru a da controlul procesoarelor logice aflate in gestiunea sa.
Nu se fac ipoteze cu privire la vitezele relative ale operatiilor corespunzatoare procesoarelor logice. Din acest punct de vedere, paralelismul poate fi considerat un caz particular al concurentei, pentru sisteme multiprocesor, in care fiecarui procesor logic ii corespunde un procesor fizic. De obicei, sistemele de operare implementeaza concurenta asa cum am aratat in 1.5.
Din cele expuse rezulta ca gestiunea entitatilor concurente presupune, pe langa creare si terminare, operatii de sincronizare adica de coordonare a task-urilor care nu sunt complet independente, de comunicare schimb de informatii intre taskuri si de planificare adica stabilirea prioritatilor task-urilor de executat.
Aceste operatii, precum si mecanismele specifice, formale sau implementate pe diverse platforme, sunt subiectele principale ale prezentei lucrari.
Printre avantajele paradigmei de programare concurenta amintim:
Alte motive pentru care subiectul concurenta prezinta interes pentru programatori
Programarea distribuita implica procesarea logica, simultana, la distanta, a unor task-uri pe platforme eterogene, plasate in diferite puncte din retea. Contextele proceselor distribuite sunt strict separate. Procesele nu partajeaza intre ele parti ale mediului de executie. Doua procese active pot schimba informatii numai prin transfer de mesaje. Spre deosebire de programarea concurenta, in contexte distribuite nu exista o autoritate centrala de coordonare a proceselor, si nici nu se gestioneaza stari globale ale proceselor.
In plus fata de celelalte paradigme de programare nseceventiala, in cazul programarii distribuite pot sa apara probleme de gestiunea intarzierilor de comunicare. De asemenea, pot sa apara probleme de administrare a retelelor (securizate mai mult sau mai putin), sau a calculatoarelor din retea in momentul cand acestea nu mai functioneaza la parametrii normali.
Metodele si tehnicile specifice programarii distribuite au astazi un spectru extrem de larg. In [11] am descris doar elementele de baza ale suporturilor software pentru aplicatii distribuite. In prezent, sub termenul de middleware sunt cunoscute tehnologiile de nivel 6 din modelul OSI [11,102]. In prezenta lucrare vom aborda doar tangential elemente de programare distribuita
Printre cele mai reprezentative exemple de probleme care implica o abordare distribuita sunt: serviciile Internet, aplicatii client/server in care programul server si aplicatiile client se gasesc pe masini diferite dar interconectate, solutii client/server ale bazelor de date aflate la distanta, agenti mobili, etc.
In modelul de aplicatii distribuite client/server, programul client se executa pe masina locala si comunica printr-o conexiune de retea cu programul server, executat pe masina aflata la distanta. Programul client implementeaza o interfata utilizator si gestioneaza interactiunile cu utilizatorul. Utilizatorul vede din intreaga aplicatie doar programul client, care accepta intrari si produce rezultate. De fapt, aplicatia client trimite cererile utilizatorului la server si prezinta utilizatorului raspunsurile primite de la server. In unele cazuri, clientul participa, de asemenea, la procesarea cererilor si raspunsurilor. De exemplu, filtreaza sau sorteaza raspunsurile serverului, pe baza unui profil al utilizatorului, cunoscut numai programului client. In figura 2.2 este schitat modelul client/server pentru aplicatii distribuite.
Figura 0. Client / server in context distribuit
O clasa importanta de aplicatii distribuite o reprezinta programele care au la baza arhitecturi precum CORBA (Common Object Request Broker Architecture), standardizata de OMG (Object Management Group) sau DCOM (Distributed Component Object Model) dezvoltata de Microsoft . Aceste arhitecturi de tip middleware ofera suportul tehnic necesar pentru ca aplicatiile distribuite sa coopereze indiferent de protocolul de comunicatie sau de arhitectura sistemului gazda.
CORBA [59,82] reprezinta o arhitectura multiplatforma care permite crearea de aplicatii orientate-obiect, distribuite, -obiecte diferite se pot gasi pe masini diferite din retea- si eterogene -diferite tehnologii de retea, platforme hardware sau sisteme de operare; implementarea obiectelor poate folosi limbaje de programare diferite-.
Tehnologia Microsoft OLE/COM [78,79] ofera un model de gestiune a unor componente integrabile in interfete utilizator. Arhitectura DCOM (Distributed COM) extinde tehnologia COM, pentru a oferi suport pentru comunicarea obiectelor aflate pe calculatoare diferite, dintr-o retea LAN, WAN sau chiar din Internet.
Programarea distribuita este o paradigma puternica de programare, printre avantajele ei de baza putem enumera:
In loc de o concluzie, punctam observatia ca paradigmele programarii paralele si concurente sunt caracterizate de relatia:
Algoritm = date + procese/thread-uri
iar paradigma programarii distribuite de relatia:
Algoritm distribuit= processe + messaje
Iata o fragment abstract dintr-un program secvential:
P Q R
Executia acestuia are loc astfel incat P va precede Q si Q va precede R.
Formal se poate scrie:
Ve P -> Q -> R,
unde -> este operatorul de precedenta si Ve se va citi 'pentru orice executie legitima a unui program'
se va citi 'este adevarat ca'
Daca avem: X:=1; Y:=X+1; X:=Y+2;
Valorile lui X si Y depind de ordinea efectuarii operatiilor.
Paradigma secventiala are urmatoarele doua caracteristici:
ordinea textuala a instructiunilor specifica ordinea executiei lor;
instructiunile succesive trebuie executate fara nici o suprapunere (in timp).
Indepartarea de paradigma secventiala
Daca secventa de instructiuni de mai sus ar fi:
X:=0; Y:=0; Z:=0;
Nu este necesar sa se insiste ca :
P^ Q^R,
ordinea
R^Q^P
fiind la fel de corecta. Adica executia programului este constransa intr-un mod care nu
este necesar relativ la logica algoritmului.
Aceasta observatie nu este un exercitiu superfluu ci poate avea consecinte practice. Sa presupunem ca avem la dispozitie cate procesoare dorim. In cazul de mai sus avem nevoie de 3. Astfel putem aloca fiecarei dintre instructiunile de mai sus un procesor al sau si ele se pot executa in paralel. De aici rezulta un plus de viteza. De asemenea trebuie observat ca acest paralelism nu se poate aplica asupra intregului program, deoarece in unele cazuri logica algoritmului presupune secventialitate.
Vom introduce unele notatii pentru a indica cand executia paralela este posibila si cand nu. Intr-un program avem o mixtura de executii paralele si secventiale.
J;
K;
cobegin
P;
Q;
R; coend L; M;
Notatia de mai sus inseamna:
Ve.J^K^(cobegincoend) -^L^M
Intre cobegin si coend poate avea loc executia in paralel a lui P, Q si R pe procesoare
separate.
Acest lucru va fi simbolizat astfel:
P || Q || R, unde || este operatorul de concurenta. Ultima notatie fiind una algebrica cae este utila atunci cand se rationeaza despre comportarea proceselor, cobegin/coend fiind cea care apare in limbajele de programare.
Avem urmatoarea echivalenta:
P || Q <-> 3e not(P^Q) and not(Q^P)
In cuvinte: " P si Q sunt concurente daca si numai daca exista cel putin o executie legala a programului in care P si Q se suprapun".
Procesoare logice
Cu scopul de folosi o abstractie care este independenta de hardware putem spune ca doua procese concurente P si Q se executa pe doua procesoare logice. Fiecare procesor logic este la randul sau o masina secventiala care executa cate o instructiune in fiecare moment. Aceste isntructiuni sunt preluate din procesele care au alocat respectivul procesor logic.
Modul de mapare al procesoarelor logice pe procesoarele fizice este un detaliu de implementare.
In scopul de a mentine portabilitatea programelor se vor face urmatoarele presupuneri:
Nu se poate face nici o presupunere privind viteza de operare a procesoarelor logice unul relativ la altul;
Nu exista nici o relatie intre viteza de operare a procesoarelor logice si timpul real (procesoarele logice nu au o rata de procesare constanta).
Programarea concurenta ofera o viziune de ordine partiala asupra lumii.
Pentru secventa:
cobegin
P;
Q;
R; coend;
executiile :
P Q R R Q P Q R P
sunt legitime. Ar exista 6 executii de acest gen, insa admitand suprapunerea ele sunt mult mai multe.
De aici rezulta ca
operatiile se pot, dar nu este obligatoriu, sa se suprapuna in timp;
ordinea textuala nu defineste ordinea de executie;
A doua proprietate defineste o relatie de ordine partiala.
Observatie: programele concurente pot sa aiba o comportare non-deterministica, adica pot produce rezultate diferite cand sunt rulate pe aceleasi date de intrare.
Acest din urma aspect nu este de dorit in cele mai multe cazuri. Acest aspect se datoreaza numarului mare de executii legale care difera prin ordinea de executie a operatiilor componente ale unui program. Unele cazuri sunt favorabile programului altele nu. De aceea limbajele de programare concurenta trebuie sa furnizeze un mod de a restrictiona executia programului astfel incat doar cazurile in care operatiile se executa intr-o ordine compatibila cu scopul urmarit sa aiba loc. Limbajele fac acest lucru furnizand facilitati pentru sincronizarea proceselor. Studiul acestora si modul in care pot fi folosite pentru a elimina toate cazurile nefavorabile sunt tema centrala de studiu al programarii concurente.
Procesele uneori au nevoie sa comunice intre ele. Unele limbaje utilizeaza in acest scop variabile ordinare (precum programele secventiale) si programatorul poate folosi facilitatile de sincronizare ale limbajului pentru a permite proceselor sa cunoasca cand o informatie valida este disponibila. Alteori sincronizarea si comunicarea sunt cuprinse impreuna in constructii de nivel inalt.
Exemplu de probleme unde nu toate cazurile de ordonare a operatiilor sunt si valide. Problema rezervarii locurilor
Avem un calculator central conectat la terminale utilizate pentru rezervarea automata de locuri la un concert. Terminale plasate in birouri de rezervare care sunt raspindite geografic. Cind un client intra in birou, functionarul afiseaza pe ecran situatia din acel moment al rezervarilor. Clientul alege unul dintre locurile libere si functionarul introduce la terminal numarul locului ales. Un bilet pentru acel loc este eliberat pe loc. In mod clar este necesara eliminarea situatiilor in care se fac rezervari multiple pentru acelasi loc.
O prima incercare de solutionare
Presupunem ca dorim sa dam o solutie folosind un singur program. O solutie rezonabila este sa se scrie un modul handler de terminal care gestinoneaza input-ul si afiseaza informatia pe un singur terminal. Avand n terminale vom avea n instante ale acestui modul care se executa concurent:
cobegin;
HANDLER1;
HANDLER2;
HANDLER3;
HANDLERn; coend; In pseudocod continutul fiecarui handler va fi:
repeat
afiseaza locurile pe ecran;
read(ALEGERE_CLIENT);
SEAT[ALEGERE_CLIENT] := RESERVED;
Elibereaza bilet forever
Slide 4 Problema rezervarii locurilor. Solutia 1
Nu este o solutie buna:
user-ul nu este impiedicat sa rezerve un loc deja rezervat;
se pot rezerva simultan aceleasi locuri fara ca sistemul sa poata inlatura acest lucru;
Proprietatile unui program concurent
Se numeste proprietate a unui program concurent un atribut al sau care este adevarat in orice istoric posibil al sau. Toate proprietatile pot fi formulate in termenii a doua proprietati speciale: safety (siguranta) si liveness. Proprietate safety sustine ca programul nu intra niciodata in stari rele, adica in unele in care variabilele sa aiba valori nedorite. Proprietatea liveness sustine ca programul va intra eventual in stari bune, in care toate variabilele sa aiba valori dorite.
Corectitudinea partiala este un exemplu de proprietate safety. Ea spune ca daca programul se termina atunci starea finala este corecta, adica a fost calculat un rezultat corect. Daca programul nu se termina atunci se poate ca sa nu se produca niciodata un rezultat corect, dar nu exista nici un istoric in care programul sa se termine si sa nu se obtina un rezultat corect.
Terminarea unui program este un exemplu de proprietate liveness. Ea spune ca un program eventual se va termina, adica ca orice istoric al programului este finit. Corectitudinea totala este proprietatea care le combina pe cele doua. Ea spune ca un program se termina intotdeauna si o face cu un rezultat corect.
Excluderea mutuala este un alt exemplu de proprietate safety.
Absenta deadlock-urilor (interblocajelor) este un alt exemplu. O stare rea in acest caz este aceea in care toate procesele sunt blocate, adica nu se poate alege o actiune care sa poata fi executata.
Intrarea unui proces intr-o sectiune critica este un alt exemplu de proprietate liveness. Stare buna pentru un proces in acest caz este aceea in care sectiunea sa critica este eligibila pentru a fi executata.
Fiind dat un program si o proprietate care se doreste ca acesta sa o aiba se pune problema cum se poate demonstra ca acel program satisface respectiva proprietate? O abordare intalnita este aceea a testarii si depanarii, care se rezuma la ' da drumul la program si vezi ce se intampla'. Aceasta consta in a enumera unele dintre istoricele posibile ale programului si sa se verifice daca ele sunt toate acceptabile. Dezavantajul este ca nu se poate deminstra in acest mod absenta istoricelor inacceptabile.
O a doua abordare este aceea ce foloseste rationarea operationala (operational reasoning), care poate fi caracterizata ca o analiza exhaustiva. In acest caz toate istoricele de executie posibile sunt enumerate, prin considerarea tuturor modurilor in care operatiile pot fi executate si se pot suprapune in timp. Din nefericire numarul istoricelor care trebuie considerate este imens. Daca avem un program care are n procese fiecare avand m actiuni atomice numarul de istorice este (n*m)!/(m!)n Pentru 3 procese cu doua actiuni atomice fiecare rezulta 90 istorice.
Copyright © 2024 - Toate drepturile rezervate
