Laborator 10

• Exercitii

1. In algoritmul de coada limitata lock-based introdus in cadrul cursului (si descris in exercitiul 1 din laboratorul anterior), presupunem ca in loc de utilizarea conditiilor notFullCondition si notEmptyCondition, si a flagurilor mustWakeDequers, respectiv mustWakeEnqueuers, pentru notificari intre threaduri, metodele enq si deq se vor folosi pur si simplu de o operatie de spinning, ca mai jos. Ce problema credeti ca apare in aceasta situatie in functionarea algoritmului pentru coada? (1 punct)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public void enq(T x) {
	boolean mustWakeDequeuers = false; 
  	
	enqLock.lock();
	try { 
  		while (size.get() == capacity) {}; //spinning
  		Node e = new Node(x);
  		tail.next = e;
  		tail = tail.next;
		size.getAndIncrement();
 	} finally {
   		enqLock.unlock();
 	}
  }

  public T deq() {
  	boolean mustWakeEnqueuers = false;
  	T v;
  
	deqLock.lock();
  	try {
    		while (head.next == null) {}; //spinning
      		v = head.next.value;
    		head = head.next;
    		size.getAndDecrement();
  	} finally { 
		deqLock.unlock(); 
		return v;
  	} 

  }

2. Implementati algoritmul de coada limitata lock-based introdus in cadrul cursului (si descris in exercitiul 1 din laboratorul anterior). Considerati dimensiunea cozii 1000. Masurati eficienta implementarii calculand o medie a timpului pe operatie pentru n = 100000 operatii enq (t_enq_size) si respectiv deq (t_deq_size) executate de 4 thread-uri rulate simultan (2 enq si 2 deq).
Executati si un test de corectitudine prin scaderea numarului de operatii executate de un thread deq la o valoare intre 99501 si 99999, si verificarea diferentei intre adaugari si eliminari ca numar de elemente asteptat sa ramana in coada la finalul executiei. (1 punct)

3. Eficientizati algoritmul de coada limitata lock-based din exercitiul anterior, prin impartirea contorului de dimensiune in doua contoare separate pentru operatiile de enq() si respectiv deq(), cu scopul de a reduce interferenta intre acestea. Testati implementarea modificata in acest mod in aceleasi conditii cu exercitiul anterior folosind 4 threaduri rulate simultan (2 enq si 2 deq) si 100000 de operatii per thread, calculand mediile timpului pe operatie (t_enq_split pentru enq, t_deq_split pentru deq). Comparati rezultatele obtinute in cele doua varianta calculand ratiile t_enq_split/t_enq_size, respectiv t_deq_split/t_deq_size.
Executati si un test de corectitudine similar cu exercitiul anterior.(2 puncte)

Hint: O idee de impartire a contorului size din algoritmul original in doua contoare separate poate pleca de la folosirea unui contor cu incrementare enqSize pentru operatia enq, si respectiv a unui contor cu decrementare deqSize pentru operatia deq. Initial ambele contoare vor fi zero. Dimensiunea cozii va fi la orice moment egala cu suma acestor doua contoare ce indica numarul de elemente adaugate, respectiv numarul de elemente eliminate din coada (deqSize este in permanenta egal cu zero sau negativ).
Un thread ce adauga elemente va testa in metoda enq() dimensiunea contorului enqSize si va realiza adaugarea atat timp cat respectivul contor este mai mic decat capacitatea cozii. La atingerea capacitatii, threadul respectiv poate incerca obtinerea deqLock, pentru a realiza urmatoarele operatii ce folosesc ambele contoare:
a) enqSize = enqSize + deqSize - actualizarea efectiva a dimensiunii listei
b) deqSize = 0 - resetarea contorului elementelor eliminate
Adaptarea algoritmului initial (inclusiv partea deq) si integrarea mecanismului de mai sus poate imbunatati performanta prin sincronizarea contoarelor doar periodic cand se estimeaza posibila depasire a capacitatii, spre deosebire de varianta de baza care implica utilizarea aceluiasi contor atomic simultan in orice apel enq sau deq.

Bonus points: Se acorda 1 punct bonus pentru prima prezentare completa a fiecarui exercitiu. In plus, la exercitiul 3 orice implementare ce obtine ratii mai bune decat precendentele prezentate poate obtine de asemenea 1 punct de bonus.
Termen rezolvare: end-of-lab-time minus 15 minute.