lab 1, 2, 3 (pthreads)

Question 1

Diferenta proces - thread

Answer 1

un proces e o instanta de rulare a unui program (2 procese diferite NU NU NU partajeaza spatiul de adrese)
thread-ul e o unitate de lucru a unui proces ( un crafting table al procesului ) si mai multe thread-uri pot partaja resurse

Question 2

Trasaturi programe care beneficiaza de implementari multi-threading

Answer 2

contin componente computationale care pot fi executate in paralel
au date pe care se poate opera in paralel ( un vector )
se blocheaza ocazional asteptand I/O
trebuie sa raspunda la evenimente asincrone
anumite componente de executie au o prioritate mai mare

Question 3

Cum e cu thread-urile la inceput, inainte sa creezi un thread cu pthread_create() ? Dar la sfarsit?

Answer 3

La inceput e un singur thread ( main thread ) si de pe thread-ul asta se apeleaza pthread_create() si se fac threaduri noi. La sfarsit tMain se opreste si el.

Question 4

int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void (start_routine) (void *), void *arg);

Answer 4

*thread = un id pt threadul tocmai creat, folosit pt a opri / referi thread-ul
attr = setezi diferite atribute pt thread, de obicei il lasam pe NULL
start_routine = pointer la functia care e executata pe threadul nou creat
arg = singurul parametrul al functiei start_routin

Question 5

Care e nr maxim de thread-uri pe care il poti crea?

Answer 5

Depinde de implementarea pthreads pe care o ai in program, dar nu se recomanda sa ai mai multe thread0uri decat core-uri pe masina, pt ca dupa apare foarte mult overhead.

Question 6

Cum rezolvi problema ca poti sa primesti un singur parametru in functia executata pe thread?

Answer 6

Argumentul primit e de tip void*, deci poti sa ti faci o structura cu ce variabile vrei tu, si o dai pe aia ca variabila.

Question 7

cum se reunesc thread-urile?

Answer 7

pthread_join. Prin apelul functiei, threadul care apeleaza il asteapta pe cel apelat, pana cand acessta isi termina functia de thread.

Question 8

pthread_join(pthread_t thread, void** retval) ?

Answer 8

thread = threadul PE care il asteptam
retval = valoarea de retur a thread ului asteptat, poate fi si NULL daca nu ne intereseaza

Question 9

daca threadul termina inainte de pthread_join?

Answer 9

nu i problema, atunci functia va returna instant

Question 10

ce e mutex?

Answer 10

o primitiva de sincronizare prin care protejam accesul la date atunci cand e posibil sa avem scrieri concurente
are 2 operatii principale : lock si unlock
cand intra un thread in mutex, isi ia lock, pana cand iese, si apoi e unlocked

Question 11

Ce e o zona critica?

Answer 11

o zona critica e acolo unde se poate afla un singur thread in acelasi timp, practic o cabina de proba, unde are voie doar unul pe rand.
daca t1 incearca sa intre in zona critica “peste” t0, atunci t1 asteapta pana cand t0 temrina

Question 12

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);

Answer 12

mutex = referinta la variabila mutex
attr = atributele mutexului nou creat

Question 13

Secventa tipica de folosire a unui mutex?

Answer 13

se creaza si se initializeaza un mutex
mai multe thread-uri incearca sa inchida mutexul
doar unul reuseste si ajunge sa “detina” mutexul
threadul realizeaza operatiile pe datele “protejate”
threadul deschide mutexul iesind din zona critica
acum alt thread poate sa intre in zona critica
la final distrugem mutexul

Question 14

ce operatii putem face cu mutexul?

Answer 14

int pthread_mutex_destroy(pthread_mutex_t *mutex);
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

Question 15

Cand produce mutexul comportament nedeterminist?

Answer 15

Cand un thread care nu detine mutexul incearca sa dea unlock pe un mutex pe care nu il detine.

Question 16

ce e bariera?

Answer 16

o alta primitiva de sincronizare folosita pentru calculul paralel. Threadurile nu trec peste bariera decat toate in acelasi timp. De ex. impartim un calcul pe mai multe threaduri si apoi vrem sa mergem mai departe doar cand toate au terminat.

Question 17

int pthread_barrier_init(pthread_barrier_t *barrier, const pthread_barrierattr_t *attr, unsigned count);

Answer 17

barrier = o referinta la bariera
attr = atributele barierei , de obicei NULL
count = nr de threaduri care vor putea sa deblocheze bariera (bariera are un contor interior care numara cate threaduri asteapta acum la bariera , si compara mereu cu acest “count”)

Question 18

cum distrugi bariera? cum faci un thread sa astepte la bariera?

Answer 18

int pthread_barrier_destroy(pthread_barrier_t *barrier);
int pthread_barrier_wait(pthread_barrier_t *barrier);

Question 19

ce returneaza pthread_barrier_wait()

Answer 19

PTHREAD_BARRIER_SERIAL_THREAD pentru un singur thread arbitrar de la barieră și 0 pentru toate celelalte (sau cod eroare)

Question 20

Cum NU trebuie paralelizat bubble sort si de ce?

Answer 20

operatiile pe elemente adiacente nu se pot realiza simultan, pt ca pot s ajung la race condition

Exemplu:
9 6 8 4 2 7
^ ^
v v
6 9 8 4 2 7
nu pot sa le fac in acelasi timp pe astea

Question 21

ce e un race condition?

Answer 21

o problema care poate aparea atunci cand nu sunt cincronizate bine thread-urile, adica atunci cand intra amandoua intr o zona critica

Question 22

Cum functioneaza OETS?

Answer 22

OETS = odd even transportation sort
in primul rand, exista 2 etape, una in care compar numerele de pe pozitii pare cu cel din dreapta lor ( 0 cu 1, 2 cu 3 etc)
aceste comparatii fiecare sunt facute pe threadul ei
apoi, o sa am fara impara, care fac comparatii intre nr de pe pozitii impare cu cel din dreapta ( 1 cu 2, 3 cu 4 etc)

Question 23

Complexitate OETS ?

Answer 23

O(N / P * N) , P = nr threaduri

Question 24

cum functioneaza Shearsort?

Answer 24

ordonez liniile matricei astfel incat liniile pare sa fie ordonate crescator, liniile impare, descrescator
coloanele sa fie ordonate cel mai mic sus

Question 25

Complexitate Shearsort?

Answer 25

elementele vor fi sortate dupa cel mult sup(log^2N) + 1, unde N = nr de elemente ce trebuie sortate
Complexitate = O (Nlog^2N)

Question 26

cum functioneaza mergeSort paralelizat?

Answer 26

Putem executa toate comparatiile de pe acelasi nivel in acelasi timp, dar cand urc la urmatorul nivel, va trebui sa am o bariera, pentru ca sa nu compar ceva ce stiu, cu ceva ce inca nu a fost calculat.

Question 27

Complexitate mergesort paralelizat?

Answer 27

in cazul ideal, daca P = N, avem complexitate O(N), altfel, procesoarele vor fi fortate sa ia mai multe comparatii, si tot in jurul lui O(N) o sa fie.

Question 28

Cum functioneaza cautarea binara paralela?

Answer 28

Impart vectorul in P zone, si caut acolo numarul. totusi, va trebui sa termin de cautat in toate secventele, si abia apoi sa trecu la urmatoarea, deci inainte sa reasignez pt fiecare procesor o noua zona, pun o bariera si astept dupa toate sa termine.