grile anii trecuti Flashcards
Ce inseamna un “split binary semaphore”?
Un grup de semafoare care au suma valorilor cel mult egala cu 1
Problema filozofilor reprezinta o situatie in care se paote ajunge la
deadlock
Avem un program cu un deadlock:
uneori se va bloca la nesfarsit
Minim de cate semafoare este nevoie pentru a rezolva problema bărbierului? (Se considera cele 3 constrangeri ale problemei discutate la curs: barbierul fara clienti, venirea unui client, respectiv frizerie plina)
3
Alegeți afirmația incorecta referitor la tehnica Split binary semaphore:
Fiecare cale de execuție începe cu o operație P (luare resursa) pe unul dintre semafoare din set și se termină cu o operație V (eliberare resursa) pe respectivul semafor
In problema Producători și consumatori, M Producători, N Consumatori si k dimensiune buffer, de cate semafoare este nevoie pentru implementare, daca nu se mai poate folosi nici un alt mecanism de sincronizare?
4
Care este un dezavantaj la soluția Reader priority (prioritate Cititorilor) pentru problema Cititori si Scriitori?
un flux continuu de cititori pot bloca ulterior pe toți potențialii scriitori
Care este una dintre diferențele dintre un semafor binar si un mutex?
apare eroare daca un task care nu deține mutexul încearcă sa îl elibereze (însă nu si la semafor binar)
Considerand problema filosofilor cu 4 filosofi, cate furculite sunt asezate pe masa?
4 ( atatea cat filosofi wow)
Care dintre urmatoarele afirmatii este falsa in cadrul problemei cititori - scriitori?
Un singur cititor are dreptul sa citeasca la un moment dat
Ce inseamna excludere mutuala?
doar un proces poate fi la un moment dat intr-o regiune critica
Care este diferenta dintre mutex si semafor binar?
mutexul are constrangeri aditionale, impuse chiar la nivelul sistemului de operare
Cum se poate delimita o zona critica in Java?
Folosind synchronized
Un thread poate fi creat implementand interfata Runnable / Thread-urile sunt pornite apeland metoda thread.start()
adevarat / adevarat
Care este diferenta dintre metodele run() si start() ale unui obiect de tip Thread in Java?
start() va crea un thread nou care va rula metoda run()
Ce inseamna ca un lock este re-entrant?
Daca un thread a luat deja lock-ul respectiv, va putea sa-l ia de oricate ori cat timp il detine
Avem un semafor in Java declarat cu “Semaphore s = new Semaphore(-2)”. De cate “s.release()” este nevoie astfel incat un thread care apeleaza “s.acquire()” sa se deblocheze din asteptare?
3
Cand avem in Java o metoda de tipul “public synchronized void f()” intr-o clasa C, pe monitor lock-ul carui obiect se face sincronizarea?
this
In Java nu se poate folosi pentru sincronizare:
un tip de date primitiv
Care este semnificatia unei sectiuni synchronized in Java?
Un singur thread poate executa sectiunea synchronized la acelasi moment de timp
Implementarea Java Thread face ca toate thread-urile sa se execute pe un singur CPU indiferent de cate procesoare are masina pe care ruleaza / Folosind Java Threads programatorul poate crea mai multe thread-uri decat numarul de CPU-uri de pe masina
fals/adevarat
In Java folosim synchronized pentru a marca o zona critica / In Pthread folosim pthread_barrier_t pentru a marca o zona critica
adevarat/fals
Care este rezultatul apelarii metodei .run() a unui thread Java?
Executia, pe firul curent, a continutului metodei.
Apelul this.wait() intr-o metoda non-statica sincronizata produce exceptie / In Java se poate initializa un Semaphore cu o valoare negativa (corespunzator numarului de permise)
fals/adevarat
De ce poate aparea exceptia IllegalMonitorStateException in Java atunci cand apelam wait() pe un obiect?
Thread-ul curent nu detine monitor lock-ului obiectului pe care apelam wait()
In Java, ce face metoda submit(Runnable task) din ExecutorService?
Submite task-ul dat ca parametru in thread pool
In Java notify() pune un thread din starea waiting in running / notifyAll() trezeste toate threadurile din waiting, punandu-le in running
adevarat / adevarat
Considerati in Java clasa A ce are definita o metoda statica astfel: “public static synchronized f() {…}” ? Cum se realizeaza sincronizarea in acest caz?
la nivel de clasa A
Care este costul pentru Cautarea binara Paralela - varianta 2 (original pentru SIMD - CREW) ?
O(P * log (P+1)(N+1))
Care este condiția pentru adăugarea unei noi regine (la problema Reginelor)? Oricare doua regine nu trebuie sa fie:
pe aceeași linie, coloana, diagonala principala sau secundara
De cate procese este nevoie pentru implementarea calcului polinomial cu Pipeline, considerând ca ultima putere a lui x este 6:
cel mult 7, se vor împarți in mod egal coeficienții
Care este complexitatea algoritmului de Căutare binara paralela in sistemele SIMD - EREW (Exclusive Read Excusilve Write)? Se considera P procesoare si o secvență ordonata de N numere.
O(logP)
Alegeți varianta ce nu reprezintă un pas in Sortarea (crescătoare) folosind Pipeline. Primul proces (Rank 0) va primi rând pe rând cate un element. Fiecare proces:
transmite valoarea mai mica vecinului din dreapta
Algoritmul lui Dekker functioneaza doar pentru 2 thread-uri/procese?
adevarat
Ce reprezinta “starvation” in contextul lucrului paralel cu thread-uri?
Un thread asteapta indefinit sa ia resursa pentru a rula
Care este complexitatea temporala a difuzarii paralele a unei valori, pentru P = N / 2?
O(log2N)
In sisteme SIMD nu este nevoie ca programatorul sa foloseasca mecanismul de bariera.
Adevarat
Care este complexitatea Parallel Merge Sort?
O(log n^2)
Care este complexitatea pentru a calcula (eficient) in paralel distanta din fiecare punct al unei liste pana la sfarsitul acesteia? Lista are N elemente.
O(logN)
Ce complexitate are cautarea paralela pe un vector cu N elemente si un sistem cu N/2 procesoare?
O(1)
Care este complexitatea algoritmului de Căutare binara paralela in sistemele SIMD - EREW (Exclusive Read Excusilve Write)? Se considera P procesoare si o secvență ordonata de N numere.
O(logP)
Consideram un sistem cu n procesoare pe care dorim sa realizam in paralel suma partiala a elementelor unui vector ce contine n elemente. Sumele partiale se vor stoca la nivelul fiecarui proces. Care este regula ca la un anumit pas (j) un proces sa lucreze? (j porneste cu valoarea 1)
rank_proces - pow(2,j-1) >= 1
Considerati urmatorul cod pentru sumele prefix, executat pe un sistem MIMD:
process suma[k=1 to n] {
for (j = 1; j < sup(log2 n); j++) {
temp[k] = a[k];
if (k - 2j-1 >= 1)
a[k] = temp[k-2j-1] + a[k];
}
}
Este nevoie sa se adauga mecanisme de sincronizare?
da, 2 bariere
Considerati urmatorul cod pentru sumele prefix, executat pe un sistem SIMD:
process suma[k=1 to n] {
for (j = 1; j < sup(log2 n); j++) {
temp[k] = a[k];
if (k - 2j-1 >= 1)
a[k] = temp[k-2j-1] + a[k];
}
}
Este nevoie sa se adauga mecanisme de sincronizare?
Nu :)
Care este complexitatea de difuzare a unei valori intr-un sistem SIMD - EREW cu P procesoare?
O(logP)
In cadrul modelului genetic Master-Slave,
functia de fitness se evalueaza in paralel si operatorii de selectie si evolutie se aplica pe toata populatia
In cadrul Selecției de tip turneu
Se aleg soluții (cromozomi) doua cate doua, soluția mai buna este aleasa
Care este rezultatul operației de Crossover in doua puncte, după poziția a4a si a9a pentru următorii 2 cromozomi:
Cromozom1: 1101 | 00100 | 110100
Cromozom2: 1010 | 11000 | 011110
Descendent1: 1010 00100 011110
Descendent2: 1101 11000 110100
Atunci cand se intoarce, apelul MPI_Send indica faptul ca:
Informatia a fost copiata in bufferele de trimitere
Ce face MPI_Comm_size?
Returneaza numarul de procese asociate cu un comunicator
Ce face MPI_Comm_rank?
Returneaza rank-ul procesului curent
Ce se poate intampla daca facem foarte multe send-uri dintr-un proces MPI, dar nu facem recv in procesul destinatie?
Operatia de send poate deveni blocanta la umplerea bufferului de sistem
In cazul modelului distribuit de pasare a mesajelor, canalele de comunicare trebuie sa garanteze ca:
mesajele nu se vor pierde
In modelul distribuit de comunicare prin pasarea mesajelor:
se garantează ca mesajele trimise pe canal nu se vor pierde
operatia send este blocanta?
da
MPI este un standard pentru programarea multi-thread / MPI vine de la Message Passing Interface.
fals / adevarat
