Programare concurenta - Relatia procese - thread -uri

La nivel conceptual, notiunile de proces si thread sunt relativ apropiate. Diferentele intre ele ies in evidenta atunci cand se au in vedere aspectele de implementare ale acestora.

Definirea procesului

Ce este un proces Un proces sau task, este un calcul care poate fi executat concurent (in paralel) cu alte calcule. El este o abstractizare a activitatii procesorului, fiind considerat ca un program in executie. Existenta unui proces este conditionata de existenta a trei factori:

o procedura - o succesiune de instructiuni dintr-un set predefinit de instructiuni, cu rolul de descriere a unui calcul - descrierea unui algoritm.

un procesor - dispozitiv hardware/software ce recunoaste si poate executa setul predefinit de instructiuni, si care este folosit, in acest caz, pentru a executa succesiunea de instructiuni specificata in procedura

un mediu - constituit din partea din resursele sistemului: o parte din memoria interna, un spatiu disc destinat unor fisiere, periferice magnetice, echipamente audio-video etc. - asupra caruia actioneaza procesorul in conformitate cu secventa de instructiuni din procedura.

Trebuie deci facuta deosebirea dintre proces si program. Procesul are un caracter dinamic, el precizeaza o secventa de activitati in curs de executie, iar programul are un caracter static, el numai descrie textual aceasta secventa de activitati.

Evolutia in paralel a doua procese trebuie inteleasa astfel:

Daca Ii si Ij sunt momentele de inceput a doua procese Pi si Pj, iar Hi si Hj sunt momentele lor de sfarsit, atunci Pi si Pj sunt executate concurent daca:

max (Ii, Ij) <= min (Hi, Hj)

Grafic, pe o axa a timpului, daca presupunem ca procesul Pi incepe primul si se termina tot primul, dar numai dupa ce a inceput Pj, evolutia lor apare ca in figura 3

Figura 2. Timpul de concurenta a doua procese

Daca sistemul dispune de doua procesoare, atunci este posibil un paralelism efectiv, in sensul ca atat Pi cat si Pj sunt executate simultan de cate un procesor. Daca exista un singur procesor, atunci acesta executa alternativ grupuri de instructiuni din cele doua procese. Decizia de comutare apartine sistemului de operare.

Reprezentarea in memorie a unui proces

In ceea ce priveste reprezentarea in memorie a unui proces, indiferent de platforma (sistemul de operare) pe care este operational, se disting, in esenta, urmatoarele zone:

Contextul procesului

Codul programului

Zona datelor globale

Zona heap

Zona stivei

Contextul procesului contine informatiile de localizare in memoria interna si informatiile de stare a executiei procesului:

Legaturi exterioare cu platforma (sistemul de operare): numele procesului, directorul curent in structura de directori, variabilele de mediu etc.;

Pointeri catre inceputurile zonelor de cod, date stiva si heap si, eventual, lungimile acestor zone;

Starea curenta a executiei procesului: contorul de program (notat PC -program counter) ce indica in zona cod urmatoarea instructiune masina de executat, pointerul spre varful stivei (notat SP - stack pointer);

Zone de salvare a registrilor generali, de stare a sistemului de intreruperi etc.

De exemplu, in [15] se descrie contextul procesului sub sistemul de operare DOS, iar in [13] contextul procesului sub sistemul de operare Unix.

Zona de cod contine instructiunile masina care dirijeaza functionarea procesului. De regula, continutul acestei zone este stabilit inca din faza de compilare. Programatorul descrie programul intr-un limbaj de programare de nivel inalt. Textul sursa al programului este supus procesului de compilare care genereaza o secventa de instructiuni masina echivalenta cu descrierea din program.

Continutul acestei zone este folosit de procesor pentru a-si incarca rand pe rand instructiunile de executat. Registrul PC indica, in fiecare moment, locul unde a ajuns executia.

Zona datelor globale contine constantele si variabilele vizibile de catre toate instructiunile programului. Constantele si o parte dintre variabile primesc valori inca din faza de compilare. Aceste valori initiale sunt incarcate in locatiile de reprezentare din zona datelor globale in momentul incarcarii programului in memorie.

Zona heap - cunoscuta si sub numele de zona variabilelor dinamice - gazduieste spatii de memorare a unor variabile a caror durata de viata este fixata de catre programator. Crearea (operatia new) unei astfel de variabile inseamna rezervarea in heap a unui sir de octeti necesar reprezentarii ei si intoarcerea unui pointer / referinte spre inceputul acestui sir. Prin intermediul referintei se poate utiliza in scriere si/sau citire aceasta variabila pana in momentul distrugerii ei (operatie destroy, dispose etc.). Distrugerea inseamna eliberarea sirului de octeti rezervat la creare pentru reprezentarea variabilei. In urma distrugerii, octetii eliberati sunt plasati in lista de spatii libere a zonei heap.

Zona stiva In momentul in care programul apeleleaza o procedura sau o functie, se depun in varful stivei o serie de informatii: parametrii transmisi de programul apelator catre procedura sau functie, adresa de revenire la programul apelator, spatiile de memorie necesare reprezentarii variabilelor locale declarate si utilizate in interiorul procedurii sau functiei etc. Dupa ce procedura sau functia isi incheie activitatea, spatiul din varful stivei ocupat la momentul apelului este eliberat. In cele mai multe cazuri, exista o stiva unica pentru fiecare proces. Exista insa platforme, DOS este un exemplu [14], care folosesc mai multe stive simultan: una rezervata numai pentru proces, alta (altele) pentru apelurile sistem. Conceptul de thread, pe care-l vom prezenta imediat, induce ca regula generala existenta mai multor spatii de stiva.

In figura 2 sunt reprezentate doua procese active simultan intr-un sistem de calcul.

Figura 2.2 Doua procese intr-un sistem de calcul

Definitia threadului

Conceptul de thread, sau fir de executie, a aparut in ultimii 10-15 ani. Proiectantii si programatorii au "simtit nevoia" sa-si defineasca entitati de calcul independente, dar in cadrul aceluiasi proces. Astfel, un thread se defineste ca o entitate de executie din interiorul unui proces, compusa dintr-un context si o secventa de instructiuni de executat.

Desi notiunea de thread va fi prezentata pe larg in capitolele urmatoare, punctam aici cateva caracteristici de baza ale acestor entitati:

Thread-urile sunt folosite pentru a crea programe formate din unitati de procesare concurenta.

Entitatea thread executa o secventa data de instructiuni, incapsulate in functia thread-ului.

Executia unui thread poate fi intrerupta pentru a permite procesorului sa dea controlul unui alt thread.

Thread-urile sunt tratate independent, fie de procesul insusi, fie de nucleul sistemului de operare. Componenta sistem (proces sau nucleu) care gestioneaza thread-urile depinde de modul de implementare a acestora.

Operatiile de lucru cu thread-uri sunt furnizate cu ajutorul unor librarii de programe (C, C++) sau cu ajutorul unor apeluri sistem (in cazul sistemelor de operare: Windows NT, Sun Solaris).

Esenta conceptuala a threadului este aceea ca executa o procedura sau o functie, in cadrul aceluiasi proces, concurent cu alte thread-uri. Contextul si zonele de date ale procesului sunt utilizate in comun de catre toate thread-urile lui.

Esenta de reprezentare in memorie a unui thread este faptul ca singurul spatiu de memorie ocupat exclusiv este spatiul de stiva. In plus, fiecare thread isi intretine propriul context, cu elemente comune contextului procesului parinte al threadului.

In figura 5 sunt reprezentate trei thread-uri in cadrul aceluiasi proces

Exista cazuri cand se prefera folosirea proceselor in locul thread-urilor. De exemplu, cand este nevoie ca entitatile de executie sa aiba identificatori diferiti sau sa-si gestioneze independent anumite atribute ale fisierelor (directorul curent, numarul maxim de fisiere deschise).

Un program multi-thread poate sa obtina o performanta imbunatatita prin executia concurenta si/sau paralela a thread-urilor. Executia concurenta a thread-urilor (sau pe scurt, concurenta) inseamna ca mai multe thread-uri sunt in progres, in acelasi timp. Executia paralela a thread-urilor (sau pe scurt, paralelism) apare cand mai multe thread-uri se executa simultan pe mai multe procesoare.

Figura 2.3 Trei thread -uri intr-un proces

Scheme de specificare a programelor concurente

Atat in proiectarea programelor cu facilitati de concurenta, cat si in specificarea lor in vederea prelucrarii de catre compilator, de-a lungul istoriei s-au utilizat diverse scheme de specificare. Nu intentionam o prezentare exhaustiva a acestora, ci le vom prezenta doar pe acelea care au fost puncte de plecare pentru tehnicile de programare concurenta actuala.

In 1.8 am facut cunostinta cu prima schema de specificare: constructia forall. In cele ce urmeaza prezentam inca alte trei scheme de specificare.

Grafuri de precedenta

Un graf de precedenta este un graf aciclic (X,U), asociat unui program, unde X este multimea instructiunilor programului, iar multimea arcelor U este formata din perechi (S_i, S_j). Un astfel de arc indica faptul ca instructiunea S_j urmeaza imediat dupa S_i si ea se poate executa numai dupa ce S_i a fost executata complet.

Sa consideram urmatorul exemplu. Un program citeste de la doua periferice diferite, doua numere a si b, dupa care tipareste suma lor. Secventa de instructiuni necesare pentru rezolvarii problemei, sunt date in figura 6

Figura 2. O secventa paralelizabila

Instructiunile S1 si S2 pot fi executate in paralel, iar S3 se executa dupa ce s-au terminat S1 si S Graful de precedenta corespunzator exemplului anterior, este ilustrat de figura 7

Figura 2. Graful de precedenta al secventei din fig. 6

Grafurile de precedenta reprezinta un model matematic util pentru descrierea concurentei, la nivelul unei secvente de cod.

Specificare FORK -JOIN-QUIT

Specificarea FORK-JOIN-QUIT a fost introdusa de Conway in 1963, fiind apoi imbunatatit de catre Denning si van Horn (1966). Acest mecanism cuprinde primele constructii de specficare a facilitatilor de concurenta din diferite limbaje de programare. Se recunosc usor (de catre informaticienii 'cu vechime') pentru ca ele sunt similare cu limbajele generatiei FORTRAN, in voga la acea ora. Constructiile corespund la trei instructiuni specifice: FORK, JOIN si QUIT.

Instructiunea FORK are sintaxa:

FORK eticheta;

Ea provoaca executia concurenta a doua secvente de cod, respectiv in doua procese distincte. Instructiunile primei secvente incep de la eticheta eticheta, iar ale celei de a doua secvente de la instructiunea ce urmeaza dupa FORK

Instructiunea JOIN are sintaxa:

JOIN nr, eticheta;

Ea asteapta terminarea a nr procese care o executa. Daca a fost executata de mai putin de nr ori, se trece la instructiunea care urmeaza, in caz contrar, se continua executia cu instructiunea din program cu eticheta eticheta.

Instructiunea QUIT are sintaxa:

QUIT;

Ea provoaca provoaca terminarea procesului care o executa.

Vom ilustra folosirea mecanismului FORK-JOIN-QUIT pentru exemplul din figura 8.

Figura 2. Descrierea FORK -JOIN-QUIT a secventei din fig. 6

Mecanismul FORK-JOIN-QUIT permite specificarea oricaror programe concurente. Din pacate, programele scrise cu aceste constructii sunt destul de putin lizibile, motiv pentru care impactul lor practic este redus. Marele lor merit este acela ca au stat la baza implementarii sub Unix a unor unor apeluri sistem omonime, folosite pentru crearea proceselor. Asupra acestora vom reveni in capitolele urmatoare.

Specificare PARBEGIN -PAREND

Specificarea PARBEGIN-PAREND, prescurtare de la PARalel BEGIN - PARalel END, a fost introdusa de Dijkstra in 1965. In unele lucrari se folosesc, in acelasi scop, cuvintele COBEGIN-COEND (de la COncurrentBEGIN COncurrentEND). Sintactic, o astfel de constructie are forma:

S₀ ; PARBEGIN S₁ | S₂ | | S_n PAREND; S_n+1 ;

si corespunde grafului de precedenta din figura 9.

Instructiunile S₁, S₂, , S_n sunt lansate in executie simultan si sunt executate concurent. Terminarea grupului are loc dupa terminarea instructiunii care dureaza cel mai mult, dupa care se executa instructiunea S_n+1.

Figura 2. Graful de precedenta al secventei PARBEGIN -PAREND

Ca exemplu, rescriem specificarea exemplului din figura 6, folosind mecanismul

PARBEGIN-PAREND.

Figura 2. Descrierea PARBEGIN -PAREND a secventei din fig. 6

In figura 11 prezentam, intr-un dialect Pascal ad-hoc, un exemplu de copiere a unui fisier 'F' intr‑un fisier 'G', situat pe un suport diferit, folosind instructiuni concurente. Pentru a se putea efectua in paralel operatiile de I/O, se folosesc doua zone tampon r, w. In paralel, in r se citeste, iar din w se scrie.

Figura 2. Copierea paralela a unui fisier

Mecanismul PARBEGIN-PAREND nu este la fel de puternic ca mecanismul FORK-JOIN-QUIT. Daca orice graf de precedenta poate fi descris folosind constructia FORK-JOIN-QUIT, exista grafuri de precedenta care nu pot fi specificate cu ajutorul construtiei PARBEGIN-PAREND. In [13,28,8] sunt prezentate astfel de exemple.

Multe limbaje, printre care este de remarcat MODULA, au preluat si implementat aceste constructii. De exemplu, intr-o excelenta lucrare de programare concurenta [34], este folosita aceasta constructie. Lucrarea este orientata strict spre Pascal, de fapt are la baza produsul PASCALFC, o extensie Pascal spre concurenta. Din pacate, utilizarea PASCALFC in aplicatiile practice este minimala, motiv pentru care el nu este tratat in aceasta lucrare.

Situatii de exceptie generate de concurenta

Executia simultana a mai multor procese/thread-uri, care acceseaza pe durata vietii lor o serie de resurse (variabile) comune, pot genera situatii ciudate de comportament al executiei programelor. Avem in vedere cazuri ce nu se intalnesc in programarea secventiala clasica. In cele ce urmeaza ilustram cateva astfel de situatii.

Rezultate inconsistente

Cunoscuta si sub numele race-condition - este o situatie generata de lipsa unei mecanism de sincronizare a thread-urilor. Intr-un context adecvat, executia intercalata a acestora genereaza rezultate inconsistente si incorecte.

Sa presupunem ca exista doua procese P1 si P2 care au dreptul sa modifice o aceeasi variabila v sub forma:

P1: v = v+1 si P2 :v = v+1

Putem presupune ca fiecare dintre cele doua procese executa aceasta incrementare concurent si de un numar neprecizat de ori. De exemplu, cele doua procese pot fi doua agentii de voiaj CFR care dau locuri simultan la acelasi tren. Variabila v poate reprezenta numarul curent al locului vandut.

Pentru a ilustra actiunile repetate ale celor doua procese, le vom descrie impreuna, in specificarea PARBEGIN-PAREND din figura 1

Figura 2. Doua procese acceseaza aceeasi variabila

Daca cele doua procese interfereaza in executia acestei instructiuni, rezultatele nu vor fi cele asteptate. Pentru clarificare, sa presupunem (ceea ce corespunde realitatii) ca executia unei instructiuni masina nu poate fi intrerupta. Pentru executia atribuirii v=v+1 sunt necesare trei instructiuni masina. Se foloseste un registru r al masinii si o instructiune masina de adunare a unui numar la un registru r=r+1. Secventa celor trei instructiuni este data in figura 13.

Figura 2.

O secventa de incrementare

Presupunem ca fiecare dintre cele doua procese P1 si P2 are cate un registru de lucru r1 si r In figura 14 si 15 sunt date doua secvente posibile a fi executate de catre cele doua procese.

Figura 2.

Prima secventa de dubla incrementare

Figura 2. A doua secventa de dubla incrementare

Presupunem ca la inceputul fiecarei secvente variabila v are valoarea 5. Executandu‑se prima secventa (fig.14), v va avea in final valoarea 7, primind valoarea 6 de la procesul P1, apoi 7 de la P

Executandu‑se secventa a doua (fig.15), variabila v va avea valoarea 6, desi a fost incrementata de catre doua procese! (V‑ar conveni sa fiti unul dintre cei doi cumparatori, sositi in acelasi timp la doua agentii, dupa ce a fost deja vandut locul 5 si primiti amandoi acelasi loc 6?).

Pentru evitarea acestor rezultate inconsistente, este necesara includerea unor mecanisme de sincronizare, astfel incat secvenetele de cod corespunzator atribuirilor v=v+1 sa nu fie executate intretesut.

Exista multe prelucrari in care apar acest gen de situatii. De exemplu, un thread citeste valoarea unei date dintr-o locatie, in timp ce alt thread atribuie o alta valoare pentru aceasta data.

Un alt exemplu: doua procese acceseaza simultan acelasi articol al aceluiasi fisier de pe disc. Fiecare dintre ele citeste continutul articolului, il prelucreaza si depune continutul inapoi. Rezultatul final este dat de ultima scriere a articolului. Normal, acest rezultat depinde de succesiunile celor doua citiri si scrieri.

Infometare

Sub denumirea de infometare (starvation, live-lock) este precizata situatia in care mai multe procese asteapta sa obtina o resursa critica, dar accesul la ea NU este oferit intr-o maniera echitabila. Spunem ca se afla in starea starvation acele procese care asteapta relativ mult, in raport cu altele care chiar se pot termina de executat, sau procesele acelea care asteapta practic un timp indefinit dupa resursa respectiva.

De exemplu, sa ne imaginam o situatie in care ai multe procese doresc sa acceseze diverse sectoare de pe acelasi disc. Coordonatorul proceselor a stabilit o disciplina de acces prin care sa reduca numarul total de deplasari a furcii cu capete de citire/scriere a discului [13]. Regula de acces este: dintre toate procesele care solicita acces la disc, va fi selectat sa acceseze discul procesul care solicita acces la sectorul cel mai apropiat de precedentul sector citit. Evident ca prin aceasta regula se reduce numarul total de deplasari a furcii.

Sa luam un exemplu concret: la un moment dat este accesat sectorul 1000. Cererile la disc sunt: un proces cere acces la sectorul 2000, in timp ce alte doua procese solicita, in mod repetat, acces la sectoarele 999 si 1001. In baza regulii de acces, vor primi dreptul de acces numai ultimele doua procese, in timp ce primul proces are mari sanse sa astepte indefinit!

Infometarea este o situatie de nedorit in programarea concurenta. Evitarea ei se poate face, spre exemplu, daca din cand in cand se schimba, intr-o maniera echitabila, regulile de acces la resursa. In 1.5 si [13] sunt prezentati algoritmi simpli de planificare prin care sa se evite infometarea.

Impas

Sa presupunem ca intr-un sistem concurent se executa doua procese P1, P2 care au nevoie, in diverse stadii ale executiei de aceleasi doua resurse nepartajabile R1, R Procesele ocupa resursele in diverse stadii ale executiei lor si le elibereaza la terminare. Procesul P1 solicita mai intai resursa R1, iar dupa un timp solicita si ocuparea resursei R2 fara sa elibereze pe R1. Procesul P2 solicita mai intai ocuparea resursei R2, iar dupa un timp solicita si ocuparea resursei R1 fara sa elibereze pe R

Deci, la un moment dat, fiecare dintre procese va ocupa ambele resurse. Evident, pe perioada in care un proces ocupa ambele resurse, celalalt proces ramane in asteptare.

Sa ne imaginam urmatorul scenariu de evolutie in timp a celor doua procese:

Procesele P1 si P2 sunt lansate in executie, iar resursele R1 si R2 sunt ambele libere.

Procesul P1 solicita resursa R1 si o ocupa, ea fiind libera.

Procesul P2 solicita resursa R2 si o ocupa, ea fiind libera.

Procesul P1 solicita resursa R2 si intra in starea de asteptare, deoarece R2 este deja ocupata de catre procesul P

Procesul P2 solicita resursa R1 si intra in starea de asteptare, deoarece R1 este deja ocupata de catre procesul P1.

Din acest moment, ambele procese se afla in starea de asteptare, din care teoretic nu vor mai putea iesi niciodata!

Acest fenomen este cunoscut in literatura sub mai multe denumiri: impas, interblocare, deadlock, deadly embrace, etc. [13,65,70,71,4]. Impasul este o stare grava care conduce la esecul executiei intregii aplicatii. Din aceasta cauza, proiectantii de aplicatii concurente trebuie sa acorde o mare atentie coordonarilor, spre a nu se ajunge la astfel de situatii.

In 1971, Coffman, Elphic si Shoshani [13,71] au indicat patru conditii necesare pentru aparitia impasului:

‑procesele solicita controlul exclusiv asupra resurselor pe care le cer (conditia de excludere mutuala

‑procesele pastreaza resursele deja ocupate atunci cand asteapta alocarea altor resurse (conditia de wait for);

‑resursele nu pot fi sterse din procesele care le tin ocupate, pana cand ele nu sunt utilizate complet (conditia de nepreemptie);

‑exista un lant de procese in care fiecare dintre ele asteapta dupa o resursa ocupata de altul din lant (conditia de asteptare circulara);

Acestei probleme i se acorda o mare importanta mai ales in domeniul sistemelor de operare [13,71,4]. Odata cu aparitia a numeroase aplicatii concurente, impasul a devenit important si pentru ele. Firesc, proiectantilor de aplicatii concurente trebuie sa aiba in vedere impasul. Practica reliefeaza cateva abordari posibile:

prima abordare, a carei utilizare nu este prea recomandata, consta in ignorarea impasului, in speranta ca acesta nu se va produce. Si daca totusi apare sistemul este oprit in mod fortat.

a doua abordare permite producerea impasului, insa detecteaza aparitia lui. Odata ce a fost detectat impasul, procesele sunt terminate selectiv sau sunt readuse la o stare anterioara si suspendate temporar pana cand "pericolul" a trecut. Aceasta solutie este partial acceptabila; in schimb NU este potrivita, spre exemplu, pentru sistemele in timp real.

A treia abordare consta in prevenirea impasului prin modificarea unor conditii care pot conduce la impas. Prezentam mai jos cateva astfel de tehnici.

O prima posibilitate de prevenire a impasului este sa se impuna ca fiecare proces sa ocupe din start toate resursele care-i sunt necesare, indiferent de momentele la care le utilizeaza efectiv. Natural, aceasta are ca efect secundar o utilizare nejudicioasa a resurselor.

O a doua posibilitate consta in stabilirea de catre sistemul de operare a unei ordini de solicitare a resurselor, la care trebuie sa se alinieze toate procesele. Daca R1, R2, Rk sunt toate resursele sistemului, atunci fiecare proces trebuie sa le solicite, pe cele dorite, numai in aceasta ordine. De exemplu, daca un proces are nevoie de resursele Ri si Rj, cu i < j, atunci el trebuie sa le solicite in aceasta ordine, NU intai Rj si apoi Ri, indiferent de momentele in care are nevoie efectiv de ele! Solutia este functionala, dar are in ea o mare doza de artificial.

A treia posibilitate este ca sistemul sa controleze, inainte de fiecare alocare, daca nu cumva este posibila aparitia impasului. Pentru aceasta se construieste un graf de alocare a resurselor [13]. Acesta este un graf orientat (X, U), avand ca noduri procesele si resursele, iar arcele sunt numai intre procese si resurse, astfel:

X

Exista un arc (Rj, Pi) in U daca procesul Pi a ocupat resursa Rj.

Exista un arc (Pi, Rj) in U daca procesul Pi asteapta sa ocupe resursa Rj.

In acest graf, daca exista un ciclu, atunci este posibil sa apara impasul. In consecinta, daca in urma alocarii unei resurse se ajunge la un graf ciclic, alocarea este anulata si procesul solicitant este pus in asteptare pana la eliberarea unei resurse, dupa care se incearca din nou alocarea s.a.m.d.