grile anii trecuti Flashcards
1
Q
Ce inseamna un “split binary semaphore”?
A
Un grup de semafoare care au suma valorilor cel mult egala cu 1
2
Q
Problema filozofilor reprezinta o situatie in care se paote ajunge la
A
deadlock
3
Q
Avem un program cu un deadlock:
A
uneori se va bloca la nesfarsit
4
Q
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)
A
3
5
Q
Alegeți afirmația incorecta referitor la tehnica Split binary semaphore:
A
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
6
Q
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?
A
4
7
Q
Care este un dezavantaj la soluția Reader priority (prioritate Cititorilor) pentru problema Cititori si Scriitori?
A
un flux continuu de cititori pot bloca ulterior pe toți potențialii scriitori
8
Q
Care este una dintre diferențele dintre un semafor binar si un mutex?
A
apare eroare daca un task care nu deține mutexul încearcă sa îl elibereze (însă nu si la semafor binar)
9
Q
Considerand problema filosofilor cu 4 filosofi, cate furculite sunt asezate pe masa?
A
4 ( atatea cat filosofi wow)
10
Q
Care dintre urmatoarele afirmatii este falsa in cadrul problemei cititori - scriitori?
A
Un singur cititor are dreptul sa citeasca la un moment dat
11
Q
Ce inseamna excludere mutuala?
A
doar un proces poate fi la un moment dat intr-o regiune critica
12
Q
Care este diferenta dintre mutex si semafor binar?
A
mutexul are constrangeri aditionale, impuse chiar la nivelul sistemului de operare
13
Q
Cum se poate delimita o zona critica in Java?
A
Folosind synchronized
14
Q
Un thread poate fi creat implementand interfata Runnable / Thread-urile sunt pornite apeland metoda thread.start()
A
adevarat / adevarat
15
Q
Care este diferenta dintre metodele run() si start() ale unui obiect de tip Thread in Java?
A
start() va crea un thread nou care va rula metoda run()
16
Q
Ce inseamna ca un lock este re-entrant?
A
Daca un thread a luat deja lock-ul respectiv, va putea sa-l ia de oricate ori cat timp il detine
17
Q
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?
A
3
18
Q
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?
A
this
19
Q
In Java nu se poate folosi pentru sincronizare:
A
un tip de date primitiv
20
Q
Care este semnificatia unei sectiuni synchronized in Java?
A
Un singur thread poate executa sectiunea synchronized la acelasi moment de timp
21
Q
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
A
fals/adevarat
22
Q
In Java folosim synchronized pentru a marca o zona critica / In Pthread folosim pthread_barrier_t pentru a marca o zona critica
A
adevarat/fals
23
Q
Care este rezultatul apelarii metodei .run() a unui thread Java?
A
Executia, pe firul curent, a continutului metodei.
24
Q
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)
A
fals/adevarat
25
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()
26
In Java, ce face metoda submit(Runnable task) din ExecutorService?
Submite task-ul dat ca parametru in thread pool
27
In Java notify() pune un thread din starea waiting in running / notifyAll() trezeste toate threadurile din waiting, punandu-le in running
adevarat / adevarat
28
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
29
Care este costul pentru Cautarea binara Paralela - varianta 2 (original pentru SIMD - CREW) ?
O(P * log (P+1)(N+1))
30
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
31
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
32
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)
33
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
34
Algoritmul lui Dekker functioneaza doar pentru 2 thread-uri/procese?
adevarat
35
Ce reprezinta “starvation” in contextul lucrului paralel cu thread-uri?
Un thread asteapta indefinit sa ia resursa pentru a rula
36
Care este complexitatea temporala a difuzarii paralele a unei valori, pentru P = N / 2?
O(log2N)
37
In sisteme SIMD nu este nevoie ca programatorul sa foloseasca mecanismul de bariera.
Adevarat
38
Care este complexitatea Parallel Merge Sort?
O(log n^2)
39
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)
40
Ce complexitate are cautarea paralela pe un vector cu N elemente si un sistem cu N/2 procesoare?
O(1)
41
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)
42
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
43
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
44
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 :)
45
Care este complexitatea de difuzare a unei valori intr-un sistem SIMD - EREW cu P procesoare?
O(logP)
46
In cadrul modelului genetic Master-Slave,
functia de fitness se evalueaza in paralel si operatorii de selectie si evolutie se aplica pe toata populatia
47
In cadrul Selecției de tip turneu
Se aleg soluții (cromozomi) doua cate doua, soluția mai buna este aleasa
48
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
49
Atunci cand se intoarce, apelul MPI_Send indica faptul ca:
Informatia a fost copiata in bufferele de trimitere
50
Ce face MPI_Comm_size?
Returneaza numarul de procese asociate cu un comunicator
51
Ce face MPI_Comm_rank?
Returneaza rank-ul procesului curent
52
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
53
In cazul modelului distribuit de pasare a mesajelor, canalele de comunicare trebuie sa garanteze ca:
mesajele nu se vor pierde
54
In modelul distribuit de comunicare prin pasarea mesajelor:
se garantează ca mesajele trimise pe canal nu se vor pierde
55
operatia send este blocanta?
da
56
MPI este un standard pentru programarea multi-thread / MPI vine de la Message Passing Interface.
fals / adevarat
57
In cadrul modelului Foster de calcul al complexitatii algoritmilor distribuiti, ce reprezinta S in formul: Tmsg-b = ts + twSL
numarul de proceasoare ce comunica simultan pe acelasi canal in acelasi sens
58
In cadrul modelului LogP de calcul al complexitatii algoritmilor distribuiti, ce reprezinta “gap-ul”?
intervalul minim dintre 2 transmiteri/ receptii succesive ale aceluiasi modul
59
Care este varianta corecta de apel de MPI_SEND pentru o variabila int x =3?
MPI_SEND(&x, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
60
In MPI, care este scopul operatiei Scatter?
distribuirea unui array catre toate procesele dintr-un comunicator
61
Cum este definiti timpul total de executie al unul algoritm distribuit?
Timpul scurs de la inceperea executiei primului proces pana la terminarea executiei ultimului proces
62
Care din urmatoarele solutii de sincronizare pe baza de ceas este descentralizata?
Network Time Protocol (NTP)
63
Considerand relatia de petrecut înainte (->) si doua evenimente a şi b:
dacă a -> b şi b -> c, atunci a -> c
64
Care dintre urmatoarele este o solutie de ceas fizic centralizat?
Algoritmul Berkeley
65
Care este timpul de trimitere a unui mesaj intr-un sistem distribuit, unde timpul de serializare este de 30 unități, un caracter se trimite in 6 unități si dimensiunea mesajului este 8?
78
66
Care este timpul de trimitere a unui mesaj intr-un sistem distribuit, unde timpul de serializare este de 20 unități, un caracter se trimite in 5 unități si dimensiunea mesajului este 7?
55
67
In comunicarea intre procese, overhead-ul este definit ca:
durata pentru care procesorul este angajat în transmiterea sau recepția unui mesaj
68
In cazul algoritmului arbore de alegere a liderului, numărul de mesaje trimise in sistem este:
4N - 4
69
Care este complexitatea (dpdv al numarului de mesaje transmise) algoritmului arbore de alegere a liderului cu N procese?
O(N)
70
Pentru analiza unui algoritm paralel consideram: P=numar procesoare, T=timpul de executie a algoritmului paralel si G=timpul celui mai rapid algoritm secevential. Costul (C) reprezinta:
T * P
71
Succesiunea a doua operatii atomice este atomica / Succesiunea a trei operatii atomice este atomica
fals / fals
72
Algoritmul fazelor (heartbeat) este un algoritm unda
adevarat
73
Numarul de mesaje pentru algoritmul LeLann este:
O(N^2)
74
Numarul de mesaje pentru algoritmul LeLann-Chang-Robert, cazul cel mai favorabil, este:
2N - 1
75
Numarul de mesaje pentru algoritmul LeLann-Chang-Robert, cazul cel mai defavorabil, este:
N(N+1)/2
76
In cazul algoritmului Bully, un proces devine lider daca:
trimite mesaje de Alegere si nu ii se raspunde
77
Cu ce difera ipoteza algoritmului Hirschberg - Sinclair de cea a agloritmilor LeLann si LeLann-Chang-Robert?
procesele pot sa se transmita bidirectional
78
Care este numarul de mesaje pentru algoritmul LeLann-Chang-Robert, cazul cel mai bun (Procesele sunt ordonate crescator in sensula celor de ceasornic)? Obs.: Toate procesele sunt initiatoare.
2N - 1
79
Numarul de mesaje pentru algoritmul Hirschberg-Sinclair, cazul cel mai defavorabil, este:
O(NlogN)
80
Pe ce algoritm secvential de sortare se bazeaza Odd Even Transposition Sort?
Bubble sort
81
In cazul algoritmului unda de tip arbore cu N noduri, numărul de mesaje trimise in sistem este:
N
82
In cazul algoritmului unda de tip arbore cu N noduri, timpul de execuție este:
O(D)
83
In cazul algoritmului unda de tip inel cu N noduri, timpul de execuție este:
O(N)
84
In cautarea binara in varianta paralela (solutia optimizata), numarul de pasi (sau iteratii) necesari acoperirii intregului vector se face cautarea (notat cu g) este:
sup(log(n+1)/log(P+1))
85
La care dintre urmatorii algoritmi de tipa unda este necesar cunoasterea diametrului retelei?
algoritmul fazelor
86
La replicarea cu lider (cvorum), cate procese indisponibile putem suporta daca n = 5, w = 3, r =3?
2
87
La algoritmii cu mesaje de sondaj cu ecou, in cazul topologiilor de tip arbore (initiatorul fiind radacina arborelui):
Mesajele de sondaj se propaga de la radacina la frunze / Mesajele de ecou se propaga de la frunze la initiator
88
In MPI cum se primesc mesajele trimise prin apelul functiei MPI_Bcast?
Prin apel MPI_Bcast
89
In algoritmul lui Huang, pentru a detecta terminarea:
se folosesc ponderi
90
Detecția terminării folosind marcaje: Un proces porneste algoritmul de terminare:
dupa ce primeste marcaj de la parinte
91
Intr-un program care foloseste pthreads, daca un thread face lock de 2 ori consecutiv pe acelasi mutex, se produce un deadlock / Intr-un program multithreaded in Java, daca un thread face lock de 2 ori consecutiv pe acelasi obiect, se produce un deadlock
adevarat / fals
92
In care din algoritmii urmatori este necesar ca inainte de terminare sa se confirme toate mesajele care au fost trimise in topologie?
Algorimul Dijsktra - Scholten
93
Alegerea liderului cu algoritmul arbore:
un proces incepe algoritmul de alegere dupa ce primeste wake-up pe fiecare canal
94
Care dintre următoarele NU reprezintă un tip de consistență?
distributed consistency
95
Ce inseamna scalabilitate buna in programarea paralela?
Pe masura ce numarul de thread-uri pe care se executa un program creste, durata de rulare scade
96
In recuperarea de eroare, prin efectul domino:
procesele revin la starea initiala, pierzand progresul realizat pana la aparitia erorii
97
Un program ce foloseste MPI se compileaza folosind mpicc / Un program ce foloseste Pthread se compileaza folosind gcc
adevarat / adevarat
98
Stabilirea empirica a scalabilitatii unei implementari presupune:
Rularea cu numar diferit de thread-uri/procese si urmarirea timpului de executie.
99
Ce poate cauza un comportament nedeterminist al unui program paralel?
Scrierea simultana a doua thread-uri in aceeasi zona de memorie
100
Ce face aplicatia mpirun?
Porneste un program distribuit MPI
101
Algoritmul Pulsatiilor: Care este complexitatea in timp?
O(D)
102
Care este avantajul crearii unui thread in Java prin implementarea interfetei Runnable?
Ne permite sa mostenim o alta clasa din clasa noastra
103
Care este complexitatea inmultirii a doua matrici in paralel?
O(N^3/P)
104
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
105
Ce reprezinta accesul concurent la o variabila x?
Doua sau mai multe thread-uri acceseaza variabila in acelasi timp
106
Ce face MPI_Barrier?
Sincronizeaza procesele dintr-un comunicator
107
Care dintre urmatoarele variante nu este o proprietate a algoritmilor de unda?
ordonare
108
In practica, timpul de executie scade intotdeuna liniar cu numarul de procesoare. / Inmultirea de matrici este un exemplu de algoritm care
NU poate fi paralelizat.
fals / fals
109
In pthread, alocarea de cuante de timp pe CPU pentru thread-uri se face de catre:
Sistemul de Operare
110
Execuția in paralel a operației logice a|b (unde a si b sunt doua numere întregi) este un exemplu de paralelism la nivel de:
bit
111
Clock drift (deplasarea unui ceas) reprezinta
diferenta dintre ceasul local al unui calculator si un ceas de referinta
112
In cazul solutiei lui Lamport, fiecare proces la prornire isi initializeaza ceasul logic cu
0
113
Considerând următorul pseudo-cod:
chan Can (int);
process P1{ int v1 =0;
v1 = v1+7; (ev1)
send Can(v1);} (ev2)
process P2{ int v2 =0;
v2 = v2+1; (ev3)
receive Can(v2); (ev4)
v2++;} (ev 5)
Se poate garanta ca pentru orice execuție:
evenimentele ev2 si ev4 sunt concurente
114
Folosind tehnica de semafor splitat (split binary semaphore) in problema Cititori-Scriitori, se ofera prioritate:
atat la cititori cat si la scriitori
115
Doua thread-uri au o variabila partajata "int a = 0". Daca fiecare thread executa in paralel (si fara sincronizare) operatia "a++", ce rezultate se pot obtine la finalul rularii celor doua thread-uri?
1 sau 2
116
Un exemplu de defect de tip omisiune:
un proces nu reuseste sa mai trimita un mesaj, datorita incarcarii procesorului
117
Metoda folosita pentru inchiderea unui Executor Service (oprirea tututor task-urilor active) in Java este:
.shutdownNow()
118
Intr-un program Pthread, o variabila declarata global poate fi vazuta de toate thread-urile / Intr-un program Pthread, o variabila declarata global poate fi modificata de toate thread-urile
adevarat / adevarat
119
Semaforul in programarea paralela NU poate fi folosit pentru:
ordonarea executiei intre thread-uri
120
Un sistem distribuit care pica o milisecunda la fiecare ora:
este disponibil, dar non-fiabil
121
Cum se porneste un thread in Pthread?
pthread_create()
122
Ce face MPI_Finalize?
Termina un program distribuit
123
Ce face MPI_Init?
Initializeaza un program distribuit
124
Cum este definita eficienta paralela ( E )? Se considera T - Timpul total necesar execuției algoritmului paralel; P - Numărul de procesoare utilizate G =Timp execuție cel mai rapid algoritm secvențial
G / ( T * P )
125
Cine controleaza numarul de thread-uri pornite intr-un program Pthread?
Programatorul
126
Considerând următorul pseudo-cod:
chan Can (int);
process P1{ int v1 =0;
v1+=7; (ev1)
send Can(v1); (ev2)
v1+=8;} (ev 3)
process P2{ int v2 =0;
v2++; (ev4)
receive Can(v2); (ev5)
v2+=10;} (ev 6)
Se poate garanta ca pentru orice execuție:
ev1 -> ev5
127
Cum se poate masura timpul de executie din linia de comanda?
Folosind programul time
128
Care dintre urmatoarele variante nu este o proprietate a algoritmilor de unda?
Tranzitivitate
129
Cine decide pe ce core va rula un anumit thread?
Sistemul de operare
130
Care dintre urmatoarele operatii creeaza o conditie de cursa atunci cand este apelata simultan de mai multe thread-uri?
Inmultirea cu 3 a unei variabile
131
In cazul problemei Reginelor (pentru 4 regine), solutia 0 2 1 3
este invalida: conflict pe diagonala
132
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
133
Care este eficienta pentru sortarea Parallel Rank Sort in cazul rularii pe P procesoare? Se considera N dimensiunea vectorului de sortat
logN/N
134
Care este complexitatea de difuzare a unei valori intr-un sistem SIMD - EREW cu P procesoare?
O(logP)
135
Orice algoritm poate fi paralelizat / Pentru orice algoritm paralel, cresterea numarului de procesoare ale sistemului duce la un timp de executie mai bun
fals / fals
136
Ce reprezinta Producer - Consumer?
O problema de sincronizare
137
Un program poate folosi un procesor cu 4 nuclee fizice la maxim daca este:
Paralelizat pe cel putin 4 thread-uri
138
Fie o variabila globala a initializata cu 0 si doua thread-uri care executa (fara sincronizare) operatia a = a + 2. Considerand ca operatia de scriere in memorie este atomica, multimea completa de valori pe care le poate avea variabila in urma executiei ambelor thread-uri este:
{2, 4}
139
Succesiunea a doua operatii atomice este atomica / Succesiunea a trei operatii atomice este atomica
fals / fals
140
Care este eficienta pentru inmultirea a doua matrici NxN in cazul rularii pe P procesoare?
1
141
În algoritmul Dijkstra-Scholten, deficitul unei legături înseamnă:
diferența dintre numărul de mesaje de date transmise şi numărul de semnale de confirmare primite pe acea legătură
142
Ce se va intampla daca porniti un program Pthread cu mai multe thread-uri decat core-uri?
Programul va functiona normal
