2 Concepte abstracte utilizate în descrierea concurentei
Asa cum am precizat în capitolul precedent, în tot restul lucrarii ne vom concentra atentia asupra concurentei la nivelul unui proces si la nivelul unui fir de executie - thread. Pentru concizia expunerii, vom folosi termenul de thread în loc de fir de executie. De asemenea, atunci când nu exista posibilitatea de confuzie, vom folosi termenul de proces în sens mai larg – privit ca si o sarcina de calcul, sau o entitate de calcul – atât pentru procesul propriu-zis, cât si pentru thread.
Conceptele care vor fi prezentate în acest capitol sunt folosite, în principal, la nivelele de proces si thread. Ele ramân însa valabile, cu adaptarile de rigoare, atât în programarea distribuita, cât si la unele dintre nivelele inferioare de concurenta prezentate în capitolul precedent.
2.1 Paradigme de programare nesecventiala
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 într-o ordine bine determinata: reluarea executiei în acelasi context conduce întotdeauna 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:
- ordinea textuala a instructiunilor furnizeaza ordinea de executie a acestora.
- instructiuni succesive se vor executa fara a se suprapune, în timp, una cu cealalta.
Nici una dintre aceste doua proprietati de baza nu sunt valabile în cazul programarii nesecventiale.
Programarea nesecventiala presupune implementarea mai multor entitati de program, care pot fi executate în 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, existând un oarecare grad de nedeterminism în timpul executiei.
Paradigmele de programare nesecventiala difera între ele prin tipul sistemului de calcul pe care se executa entitatile concurente: sistem monoprocesor, multiprocesor, sistem distribuit, asa cum rezulta din ceea ce am prezentat în capitolul 1. De asemenea, paradigmele difera si dupa modul cum sunt partajate de catre entitati informatiile de context si resursele sistemului. In sfârsit, paradigmele mai difera dupa gradul de interactiune între entitati si în functie de existenta unei "autoritati tutelare" care sa asigure coordonarea entitatilor.
Paradigmele de programare nesecventiala pot fi grupate în trei mari categorii:
1. paradigme de programare paralela;
2. paradigme de programare concurenta;
3. paradigme de programare distribuita.
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.
2.1.1 Programare paralela
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 în vederea realizarii unui scop comun. Deosebirea fundamentala (conceptual vorbind) a programarii paralele fata de alte paradigme nesecventiale [58] consta în faptul ca sarcinile de calcul se coordoneaza numai prin operatii de asteptare a începerii sau a terminarii altor entitati implicate. Astfel, lansarea în executie a unei sarcini de calcul poate fi conditionata de startul prealabil al altora, respectiv de terminarea activitatilor altor sarcini de calcul.
De exemplu, fazele executiei pipeline, descrise în 1.3, pot fi privite ca si sarcini executabile în paralel.
Domeniul calculului numeric [21,22,74] abunda în algoritmi paraleli. La loc de cinste în cadrul acestora sunt algoritmii paraleli specifici algebrei liniare: determinanti, matrice etc.
Punctam câteva trasaturi caracteristice ale programelor paralele:
1. 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 în timpul executiei programului.
2. Fiecare task încapsuleaza un program secvential si o memorie locala. De fapt, un task reprezinta o masina virtuala von Neumann [9]. (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.)
3. Task-urile pot fi atasate procesoarelor fizice în diverse moduri, dar aceasta atasare nu afecteaza semantica programului. In particular, unui singur procesor îi pot fi atasate mai multe taskuri.
4. Se pot defini interfete de comunicare între aceste task-uri si, de asemenea, modalitati de acces la resursele comune, în conformitate cu modelul de paralelism folosit.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
