Laborator 5
- Operatii de coordonare folosind monitorul obiectelor din Java. Conditii.
- Problema lost-wakeups.
- TEMA
- Exercitiu
Operatii de coordonare folosind monitorul obiectelor din Java. Conditii.
Pe langa cuvantul cheie synchronized prin care un thread poate sa obtina acces exclusiv in executia unei metode a unei instante prin intermediul monitorului (lock) intern al respectivei instante, acest monitor intern mai permite si urmatoarele operatii de coordonare in acest context:
- wait() - acest apel suspenda thread-ul apelant si elibereaza monitorul intern (lock-ul obtinut prin synchronized) ce poate fi preluat de alt tread; thread-ul suspendat re-obtine monitorul cand este notificat (trezit) prin unul din apelurile urmatoare
- notify() - acest apel notifica (trezeste) un thread oarecare dintre cele suspendate in urma apelului de mai sus; thread-ul trezit va obtine din nou lock-ul intern corespunzator instantei pentru blocul synchronized, dar nu inainte ca thread-ul ce a apelat notify sa incheie executia acestui bloc sau sa o re-suspende (deci thread-ul trezit va mai astepta pana la respectivul moment)
- notifyAll() - similar cu notify cu diferenta ca toate thread-urile suspendate vor fi trezite aflandu-se in competitie pentru a obtine lock-ul intern
Apelul oricarei dintre metodele de mai sus are evident sens doar in contextul unui bloc synchronized (deci doar daca thread-ul care face apelul detine monitorul intern al instantei curente a obiectului). Un exemplu de utilizare pentru o coada simpla e cel de mai jos:
class SimpleQueue{ private T [] items; private int tail = 0, head = 0, count = 0; public SimpleQueue(int size) { items = (T[])new Object[size]; } public synchronized void enq(T x) { while(count == items.length) { try { wait(); } catch (InterruptedException e) { } finally { } } System.out.println("Enqueuing " + x); items[tail] = x; if (++tail == items.length) { tail = 0; } count++; notify(); } public synchronized T deq() { while (count == 0) { try { wait(); } catch (InterruptedException e) { } finally { } } char x = items[head]; if (++head == items.length) { head = 0; } count--; System.out.println("Dequeuing " + x); notify(); return x; } }
In anumite situatii este preferabila utilizarea unui lock explicit in locul monitorului intern. In aceste situatii, exista posibilitatea de a coordona intr-un mod similar thread-urile ce acceseaza o anumita portiune de cod prin intermediul unor metode specifice unei instante Condition obtinuta pentru lock-ul respectiv prin apelul newCondition(). Aceste metode sunt respectiv await(), signal() si signalAll(). Un exemplu similar celui de mai sus, ce foloseste aceasta modalitate de coordonare ar fi urmatorul:
class SimpleQueue{ private Lock lock = new ReentrantLock(); private Condition full = lock.newCondition(); private Condition empty = lock.newCondition(); private T [] items; private int tail = 0, head = 0, count = 0; public SimpleQueue(int size) { items = (T[])new Object[size]; } public void enq(T x) { lock.lock(); try { while(count == items.length) { try { full.await(); } // asteapta cat timp coada este plina catch (InterruptedException e) { } finally { } } System.out.println("Enqueuing " + x); items[tail] = x; if (++tail == items.length) { tail = 0; } count++; empty.signal(); // semnaleaza starea cozii ca nemaifiind vida } finally { lock.unlock(); } } public T deq() { lock.lock() try { while (count == 0) { try { empty.await(); } // asteapta cat timp coada este vida catch (InterruptedException e) { } finally { } } char x = items[head]; if (++head == items.length) { head = 0; } count--; System.out.println("Dequeuing " + x); full.signal(); // semnaleaza starea cozii ca nemaifiind plina return x; } finally { lock.unlock(); } } }
Problema lost-wakeups.
In exemplul de mai sus conditiile primesc semnal la fiecare adaugare sau eliminare din coada. Aparent ar fi mai eficient ca apelul signal sa fie executat doar la momentele cand cele doua conditii devin efectiv indeplinite. Mai precis, in cazul adaugarii, ca in exemplul urmator, doar in momentul in care coada devine nevida:
public void enq(T x) {
lock.lock();
try {
while(count == items.length)
{
try { full.await(); }
catch (InterruptedException e) { }
finally { }
}
System.out.println("Enqueuing " + x);
items[tail] = x;
if (++tail == items.length) { tail = 0; }
count++;
if (count == 1) {
empty.signal();
}
} finally {
lock.unlock();
}
}
Desi aparent o optimizare, aceasta abordare creeaza o potentiala problema numita generic lost-wakeup.
Sa presupunem ca doua sau mai multe thread-uri consumator se afla in stare de asteptare a conditiei empty pentru a elimina un element din coada aflata in stare vida.
De asemenea sa presupunem ca avem doua sau mai multe thread-uri producator care adauga elemente, si acestea reusesc sa faca acest lucru inainte ca un thread consumator trezit sa elimine un element din coada.
In aceasta situatie, doar primul thread producator va semnala conditia empty trezind un singur consumator, ceilalti producatori nefacand acest lucru pentru ca avem deja un element in coada.
Consecinta este ca restul consumatorilor vor ramane suspendati, pierzand trezirea (lost wakeup), cel putin pana ce noi thread-uri consumator vor consuma restul elementelor din coada.
O alta varianta de a solutiona aceasta problema este utilizarea signalAll() in loc de signal(). Notificarea va trezi in acest caz toate thread-urile aflate in stare de asteptare. Acestea insa vor se vor afla in competitie pentru acelasi lock ceea ce va creste nivelul de contention la momentul respectiv.
TEMA
Tema se realizeaza in echipa de maxim 3 studenti. Tema se va trimite prin e-mail catre responsabilul de laborator fie ca arhiva zip cu fisiere incluzand raspunsurile si sursele implementarilor, fie ca link catre un repository, avand ca subiect TEMA TPM. In e-mailul trimis se va preciza componenta completa a echipei. Termenul strict de trimitere a temei: 10 noiembrie (inclusiv).
Finalizarea evaluarii temei se va face intr-o sesiune online in saptamana a opta la care vor participa toti membrii echipei, la o data ce va fi stabilita in functie de orarul examenelor. O programare pe sloturi orare a evaluarilor va fi anuntata la finalul saptamanii sapte, dupa termenul de trimitere a temelor.
Orice incercare de frauda in rezolvarea temei va fi penalizata cu depunctarea totala a tuturor membrilor echipei.
1. (2 puncte) Se da urmatoarea secventa (istorie) de executie de mai jos. Este aceasta linearizabila? Dar consistent secventiala? Se considera valoarea initiala r = 0.
Argumentati raspunsul oferind explicatiile (eventual secventa istoriei de executie) si/sau o diagrama cu punctele de linearizare dupa caz.
2. (3 puncte) De ce in mod obisnuit in utilizarea unui lock se prefera ca apelul lock() sa fie executat inainte de blocul try, si nu in cadrul acestuia (prima varianta de mai jos si nu a doua)? Argumentati.
lock inainte de try:
someLock.lock();
try {
.....
}
finally {
someLock.unlock();
}
lock in cadrul try:
try {
someLock.lock();
.....
}
finally {
someLock.unlock();
}
3. a) (5 puncte) O echipa de programatori a dezvoltat algoritmul de lock prezentat in pseudocodul urmator. ThreadId se considera a fi o clasa ce furnizeaza un id unic pozitiv fiecarui thread.
Grupele de la seria A: Intr-o executie concurenta a n > 1 thread-uri, este acest algoritm starvation-free? Argumentati.
Grupele de la seriile B si E: Intr-o executie concurenta a n > 1 thread-uri, este acest algoritm deadlock-free? Argumentati.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class ShadyLock { private volatile int turn; private volatile boolean used = false; public void lock() { int me = ThreadId.get(); do { do { turn = me; } while (used); used = true; } while (turn != me); } public void unlock () { used = false; } } |
In argumentatie se pot include si eventuale trace-uri demonstrative pentru executia unor thread-uri sau optional o implementare exemplificativa daca este cazul.
3. b) (5 puncte) O alta echipa de programatori a dezvoltat algoritmul de lock prezentat in pseudocodul urmator ce incapsuleaza un alt lock oarecare. Se considera ca lock-ul incapsulat asigura corect excluderea mutuala si este starvation-free. De asemenea lock-ul incapsulat permite un apel unlock fara exceptie si fara efect chiar daca nu a existat un apel lock. ThreadId se considera a fi o clasa ce furnizeaza un id unic pozitiv fiecarui thread.
Grupele de la seria A: Intr-o executie concurenta a n > 1 thread-uri, asigura acest algoritm excluderea mutuala? Argumentati.
Grupele de la seriile B si E: Intr-o executie concurenta a n > 1 thread-uri, asigura acest algoritm o garantie de fairness (niciun thread nu poate accesa o sectiune critica protejata de lock mai des ca altele)? Argumentati.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class VeryShadyLock { private Lock lock; private int x, y = 0; public void lock() { int me = ThreadId.get(); x = me; while (y != 0) {}; y = me; if (x != me) { lock.lock(); } } public void unlock() { y = 0; lock.unlock(); } } |
In argumentatie se pot include si eventuale trace-uri demonstrative pentru executia unor thread-uri sau optional o implementare exemplificativa daca este cazul.
3. c) (5 puncte) O a treia echipa de programatori s-a plictisit de programat lacate, si a implementat clasa din pseudocodul urmator. Consideram un context de executie concurenta a n > 1 thread-uri, in care fiecare thread apeleaza metoda choose. ThreadId se considera a fi o clasa ce furnizeaza un id unic pozitiv fiecarui thread.
Grupele de la seria A: Demonstrati ca maxim un thread poate obtine valoarea "red" si maxim n-1 thread-uri pot obtine valoarea "black".
Grupele de la seriile B si E: Demonstrati ca maxim un thread poate obtine valoarea "red" si maxim n-1 thread-uri pot obtine valoarea "white".
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class ShadyChoice { private boolean getWhite = false; private int last = 0; public string choose() { int me = ThreadId.get(); last = me; if (getWhite) return "white"; getWhite = true; if (last == me) return "red"; else return "black"; } } |
In argumentatie se pot include si eventuale trace-uri demonstrative pentru executia unor thread-uri sau optional o implementare exemplificativa daca este cazul.
4. (5 puncte) Consideram urmatoarea problema: Un trib de salbatici mananca dintr-o singura oala mare ce are o capacitate de N portii. Cand un membru al tribului mananca, va lua o portie din oala daca oala are cel putin o portie disponibila. Daca oala este goala, membrul de trib va ordona bucatarului sa reumple oala si va astepta pana ce aceasta este din nou complet plina. Bucatarul face exclusiv reumpleri complete (N portii). Pe scurt: membrii tribului nu pot lua o portie din oala daca aceasta este goala si bucatarul nu poate reumple oala decat daca este goala.
Scrieti un program care sa simuleze comportamentul membrilor de trib si al bucatarului, unde fiecare dintre acestia este reprezentat de un thread, iar oala este o resursa partajata, respectand constrangerile enuntate mai sus. Considerati ca fiecare dintre membrii de trib doreste sa manance doar o singura masa, dar numarul lor total este mai mare decat capacitatea oalei, deci aceasta va necesita reumpleri. Nu este permisa utilizarea in implementarea solutiei a tipurilor atomice din Java.
5. (5 puncte) Consideram algoritmul lui Peterson de excludere mutuala ce ofera o generalizare pentru n thread-uri enuntat in laboratorul 3, ale carui metode sunt redate in pseudocodul de mai jos. Reamintim ideea acestuia de a trece fiecare thread printr-un filtru de n-1 nivele pana la accesul la sectiunea critica. i poate fi considerat ca identificator al unui thread iar L ca numar al nivelului. Tabloul level asociat nivelelor retine nivelul curent pentru fiecare thread, iar tabloul victim retine identificatorul fiecarui ultim thread ce a avansat la respectivul nivel.
lock() {
for (int L = 1; L < n; L++) {
level[i] = L;
victim[L] = i;
while (( exists k != i with level[k] >= L ) &&
victim [L] == i ) {};
}
}
unlock() {
level[i] = 0;
}
De ce credeti ca algoritmul lui Peterson generalizat in acest mod nu este echilibrat (fair)? Incercati sa descrieti un exemplu concurent de executie ca raspuns.
Gasiti o varianta de imbunatatire pentru a asigura garantia de fairness si implementati algoritmul in acest mod. Odata pornite n thread-uri niciunul dintre acestea nu ar trebui sa poata accesa sectiunea critica protejata de lock mai des ca celelalte.
Exercitiu
Se da urmatoarea secventa (istorie) de executie de mai jos. Este aceasta linearizabila? Dar consistent secventiala? Se considera valoarea initiala r = 0. Argumentati raspunsul oferind explicatiile (eventual secventa istoriei de executie) si/sau o diagrama cu punctele de linearizare dupa caz. (2 puncte)
Pentru acest exercitiu nu se acorda puncte de bonus.
Termen rezolvare: end-of-lab-time minus 15 minute.