lab 1, 2, 3 (pthreads) Flashcards
Diferenta proces - thread
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
Trasaturi programe care beneficiaza de implementari multi-threading
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
Cum e cu thread-urile la inceput, inainte sa creezi un thread cu pthread_create() ? Dar la sfarsit?
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.
int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void (start_routine) (void *), void *arg);
*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
Care e nr maxim de thread-uri pe care il poti crea?
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.
Cum rezolvi problema ca poti sa primesti un singur parametru in functia executata pe thread?
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.
cum se reunesc thread-urile?
pthread_join. Prin apelul functiei, threadul care apeleaza il asteapta pe cel apelat, pana cand acessta isi termina functia de thread.
pthread_join(pthread_t thread, void** retval) ?
thread = threadul PE care il asteptam
retval = valoarea de retur a thread ului asteptat, poate fi si NULL daca nu ne intereseaza
daca threadul termina inainte de pthread_join?
nu i problema, atunci functia va returna instant
ce e mutex?
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
Ce e o zona critica?
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
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
mutex = referinta la variabila mutex
attr = atributele mutexului nou creat
Secventa tipica de folosire a unui mutex?
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
ce operatii putem face cu mutexul?
int pthread_mutex_destroy(pthread_mutex_t *mutex);
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
Cand produce mutexul comportament nedeterminist?
Cand un thread care nu detine mutexul incearca sa dea unlock pe un mutex pe care nu il detine.
ce e bariera?
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.
int pthread_barrier_init(pthread_barrier_t *barrier, const pthread_barrierattr_t *attr, unsigned count);
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”)
cum distrugi bariera? cum faci un thread sa astepte la bariera?
int pthread_barrier_destroy(pthread_barrier_t *barrier);
int pthread_barrier_wait(pthread_barrier_t *barrier);
ce returneaza pthread_barrier_wait()
PTHREAD_BARRIER_SERIAL_THREAD pentru un singur thread arbitrar de la barieră și 0 pentru toate celelalte (sau cod eroare)
Cum NU trebuie paralelizat bubble sort si de ce?
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
ce e un race condition?
o problema care poate aparea atunci cand nu sunt cincronizate bine thread-urile, adica atunci cand intra amandoua intr o zona critica
Cum functioneaza OETS?
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)
Complexitate OETS ?
O(N / P * N) , P = nr threaduri
cum functioneaza Shearsort?
ordonez liniile matricei astfel incat liniile pare sa fie ordonate crescator, liniile impare, descrescator
coloanele sa fie ordonate cel mai mic sus
Complexitate Shearsort?
elementele vor fi sortate dupa cel mult sup(log^2N) + 1, unde N = nr de elemente ce trebuie sortate
Complexitate = O (Nlog^2N)
cum functioneaza mergeSort paralelizat?
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.
Complexitate mergesort paralelizat?
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.
Cum functioneaza cautarea binara paralela?
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.
