# Ćwiczenia 13, grupa śr. 12-14, 25 stycznia 2023

###### tags: `PRW22` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::success
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Michał Bronowicki | | | | | | | |
Wiktor Bukowski | ==X== | X | X | X | | | |
Jan Dalecki | | | | | | | |
Mikołaj Depta | X | X | X |==X==| X | | |
Kamil Galik | | | | | | | |
Bartosz Głowacki | | | | | | | |
Michał Hetnar | | | | | | | |
Adam Jarząbek | | | | | | | |
Michał Kierul | | | | | | | |
Mateusz Kisiel | | | | | | | |
Maksymilian Komarnicki | X | X | X | | | | |
Julia Matuszewska | | | X | | | | |
Andrzej Morawski | | | | | | | |
Wojciech Pokój | X | X | X | X | | | |
Marcin Sarnecki | | | | | | | |
Bartosz Szczeciński | | | | | | | |
Tomasz Wołczański | X | X | X | | | | |
Marcin Wróbel | X | X | X | X | | | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Wiktor Bukowski
:::



Powody niepowodzeń `compareAndSet()`:
- linijka 16: inny wątek ustawił się jako pierwszy w Exchangerze
- linijka 24: jakiś wątek zdążył ustawić się jako drugi w exchangerze, pomimo timeoutu (a więc zakończymy wywołanie z sukcesem)
- linijka 34: inny wątek ustawił się jako drugi w Exchangerze

**Dlaczego w pewnych dwóch miejscach w kodzie ustawia się zmienną slot przy pomocy set() a nie compareAndSet()?**
Ponieważ tylko jeden wątek może wykonać operację "zwolnienia" Exchangera, a więc może to zrobić bezwarunkowo.

## Zadanie 2
:::success
Autor: Tomasz Wołczański
:::



Klasa `RangePolicy` odpowiada za dynamiczne ustalanie zakresu, z którego będą losowane indeksy tablicy eliminacji. Zakres powinien być dostosowany do liczby wątków; najprostsza polityka polega na zmniejszaniu zakresu, gdy liczba wymian zakończonych niepowodzeniem zwiększa się (`recordEliminationTimeout`) i zwiększaniu zakresu, gdy zwiększa się liczba wymian zakończonych sukcesem (`recordEliminationSuccess`).

Wywołania metod `push` i `pop`, które kończą się po wywołaniu `tryPush` lub `tryPop` mogą zostać zlinearyzowane tak, jak w `LockFreeStack`. Punkty linearyzacji wywołań zakończonych eliminacją są takie same, jak punkty linearyzacji wywołań `exchange` zakończonych sukcesem.

## Zadanie 3
:::success
Autor: Wojciech Pokój
:::

Opisz w sposób wysokopoziomowy (tzn. bez
odwoływania się do kodu) algorytm implementowany przez metodę
getAndIncrement() klasy CombiningTree.

Każdy wątek zaczyna z przypisanego do siebie liścia z pełnego drzewa binarnego.

Wątek podróżuje do góry drzewa dopuki nie napotka węzła które jest już zajęte. Jeżeli węzeł jeszcze nie został zablokowany, tj wątek szybszy jeszcze czeka na inne wątki to blokujemy węzeł na czas zliczania, wpp czekamy aż tamten wątek skończy pracę nad swoim wywołaniem getAndIncrement i idziemy dalej do góry.

Jeśli dotrze do węzła które jest już zajęte to zbiera informację o aktualizacji licznika od wątków które przegrały na poprzednich poziomach i połączony stan umieszcza w polu value węzła w którym przegrał.

Jeśli dotrze do korzenia drzewa to aktualizuje w nim wartość licznika.

Gdy dostanie spowrotem zaktualizowaną wartość licznika to dystrybuuje zaktualizowane wartości wdół aż do liścia z którego przyszedł, po czym zwraca z nowym licznikiem.

## Zadanie 4
:::success
Autor: Mikołaj Depta
:::


Flaga `locked` pełni rolę jednego z dwóch zamków zakładanych na węzły drzewa podczas operacji na nim. Jest to zamek zakładany podczas okresów kiedy węzeł może być potencjalnie długo niedostępny bo np. wątek wykonuje oprację `combine` na gałęzie drzewa do której on należy.


1.1. `precombine` - Rozpatrzmy wątek W, gdzie flaga te jest podniesiona. Może być tak, że wcześniejsza "iteracja" naszego algorytmu jeszcze się nie skończyła. Może być, że szybki wątek jest w czasie wykonywania combine po przejściu przez W lub jest w trakcie wracania i wykonywania `distribute` albo w przypadku gdy w wątku W doszło do spotkania dwóch wątków, wolny wątek nie odczytał wartości, którą szybszy wątek wpisał do result.
1.2. `combine` - Ponownie rozpatrzmy wątek W, gdzie ta flaga jest poniesiona. Oznacza to, że wątek szybki przechodząc po gałęzi drzewa do węzłą `last` został zarzymany przez wątek wolny rywalizujący o węzeł W jeszcze nie wykonał swoich operacji `combine` i `op` - to znaczy, nie wpisał wartości sumy z węzłów ze swojego poddrzewa do `secondValue`.

2. Metody `op` i `distribute` operują już na zablokowanych gałęziach drzewa schodząc po nich na dół.

3. Wpływ locked na inne wątki
`precombine` - jeśli jesteśmy drugim wątkiem to chcemy, żeby szybszy poczekał aż obliczymy wartość sumy z naszego poddrzewa.
`combine` - chcemy zająć zamki na całej gałęzi drzewa po której przeszliśmy precombine - nie chcemy, żeby nowy wątek wykonujący precombine spóźnione od teraz cokolwiek zmieniał.
`op` - zamka dotykamy przy dwóch okazjach:
- raz - tylko gdy byliśmy wolniejszym wątkiem i właśnie skończyliśmy przechodzić nasze poddrzewo z kroku combine i ustawiamy wartość secondValue na wartość obliczonej sumy.
- dwa - skończyliśmy czekanie na powrót wątku szybszego, odczytujemy wartość którą nam zostawił i zwracamy.
`distribute` - i wykonywaliśmy `combine` i wracamy z wartością na dół. Jeśli w danym węźle nie było rywalizacji (stan FIRST), to zwalniamy sami zamek i idziemy dalej. W przypadku gdy do rywalizacji doszło chcemy zostawić zwolnienie zamku czekającemu wolnemu wątkowi, żeby żadne przyszłe szybkie iteracje `precombine`, `combine`, `op` i `distribute` przypadkiem nie nadpisały mu wartości result obliczonej przez aktualne wykonanie.

:::info
Pozostałe zadania uznajemy za bonusowe.
:::

## Zadanie 5
Exercise 12.2. Implement a trinary CombiningTree , that is, one that allows up to three
threads coming from three subtrees to combine at a given node. Can you estimate the
advantages and disadvantages of such a tree when compared with a binary combining
tree?

:::danger
Autor: Mikołaj Depta
:::

:::info
Przedstawiane rozwiązanie zaczerpnięto z https://github.com/wolvre/trinary-combining-tree/blob/master/src/Combine/TriTree.java
:::

public class TriTree {
  volatile int stamp = 0;
  final static int THREADS = 12;
  final static int TRIES = 1024 * 1024;
  static boolean[] test = new boolean[THREADS * TRIES];
    
  TriNode[] leaf;
  
  /** Creates a new instance of Combine */
  public TriTree(int size) { //size=27
    TriNode[] nodes = new TriNode[size/2];
    nodes[0] = new TriNode();
    for (int i = 1; i < nodes.length; i++) {
      nodes[i] = new TriNode(nodes[(i-1)/3], i);
    }
    leaf = new TriNode[(size + 1)/3];
    for (int i = 0; i < leaf.length; i++) {
      leaf[i] = nodes[nodes.length - i - 1];
    }
  }
  
  public int getAndIncrement() throws InterruptedException {
    Stack<TriNode> stack = new Stack<TriNode>();
    int tid = ThreadID.get();
    TriNode myLeaf = leaf[tid % 9];//[tid / 3];
    TriNode node = myLeaf;
    // phase one
    while (node.precombine()) {
      //System.out.printf("%d: Thread %d precombining done at Node %d.\n", stamp++, tid, node.nid);
      node = node.parent;
    }
    TriNode stop = node;
    //System.out.printf("%d: Thread %d stops precombining at Node %d.\n", stamp++, tid, stop.nid);
    // phase two
    node = myLeaf;
    int combined = 1;
    while (node != stop) {
      combined = node.combine(combined);
      // System.out.printf("%d: Thread %d combining done at Node %d.\n", stamp++, tid, node.nid);
      stack.push(node);
      node = node.parent;
    }
    // phase 3  
    int prior = stop.op(combined);
    if (test[prior]) {
        System.out.printf("ERROR duplicate value %d by Thread %d, Node %d\n", prior, tid, stop.nid);
        return prior;
    }
    else
        test[prior] = true;
    //System.out.printf("%d: Thread %d operation done at Node %d.\n", stamp++, tid, stop.nid);

    // phase 4
    while (!stack.empty()) {
      node = stack.pop();
      node.distribute(prior);
      //System.out.printf("%d: Thread %d distribution done at Node %d.\n", stamp++, tid, node.nid);
    }
    //System.out.printf("%d: Thread %d returns %d.\n", stamp++, tid, prior);
    return prior;
  }
  
}

## Zadanie 6
Exercise 12.3. Implement a CombiningTree using Exchanger objects to perform the
coordination among threads ascending and descending the tree. What are the possi-
ble disadvantages of your construction when compared to the CombiningTree class
presented in Section 12.3?

:::danger
Autor:
:::

## Zadanie 7

Exercise 12.4. Implement the cyclic array-based shared pool described in Sec-
tion 12.2 using two simple counters and a ReentrantLock per array entry.

:::danger
Autor:
:::