# Ćwiczenia 13, grupa śr. 10-12, 24 stycznia 2024

###### tags: `PRW23` `ć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!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | X | X | X | X | | | |
Konrad Kowalczyk | | | | | | | |
Jakub Krzyżowski | X | X | X | X | | | |
Łukasz Magnuszewski | | | | | | | |
Marcin Majchrzyk | X | X | X | X | | | |
Jan Marek | X | X | X | X | | | |
Marcin Mierzejewski | | | | | | | |
Juan Jose Nieto Ruiz | | | | | | | |
Konrad Oleksy | | | | | | | |
Javier Rábago Montero | X | X | X | | | | |
Michał Mękarski | X | X | X | X | | | |
:::

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

## Zadanie 1
:::success
Autor: Mikołaj Balwicki
:::

## Zadanie 2
:::success
Autor: Jakub Krzyżowski
:::
**Zadanie 2.** Omów działanie klasy EliminationBackoffStack. Jaką
rolę pełni w niej klasa RangePolicy? Wskaż punkty linearyzacji
metod push() i pop().

public class EliminationBackoffStack<T> extends LockFreeStack<T> {
    static final int capacity = ...;
    EliminationArray<T> eliminationArray = new EliminationArray<T>(capacity);
    static ThreadLocal<RangePolicy> policy = new ThreadLocal<RangePolicy>() {
        return new RangePolicy();
    }
    
    public void push(T value) {
        RangePolicy rangePolicy = policy.get();
        Node node = new Node(value);
        while (true) {
            if (tryPush(node)) {
                return;
            } else try {
                T otherValue = eliminationArray.visit(value, rangePolicy.getRange());
                if (otherValue == null) {
                    rangePolicy.recordEliminationSuccess();
                    return; // exchanged with pop
                }
            } catch (TimeoutException ex) {
                rangePolicy.recordEliminationTimeout();
            }
        }
    }
    
    public T pop() throws EmptyException {
        RangePolicy rangePolicy = policy.get();
        while (true) {
            Node returnNode = tryPop();
            if (returnNode != null) {
                return returnNode.value;
            } else try {
                T otherValue = eliminationArray.visit(null, rangePolicy.getRange());
                if (otherValue != null) {
                    rangePolicy.recordEliminationSuccess();
                    return otherValue;
                }
            } catch (TimeoutException ex) {
                rangePolicy.recordEliminationTimeout();
            }
        }
    }
}

`EliminationBackoffStack` działa podobnie do `LockFreeStack` z tą różnicą, że w przypadku niepowodzenia `tryPop`, lub `tryPush` zamiast wycofać się i odczekać wątki wykorzystują `EliminationArray` - listę obiektów typu `LockFreeExchanger` w celu wymiany wartości pomiędzy kolejnymi wywołaniami `push` i `pop`. Wątki wybierają losowe miejsce w swoim zakresie listy i tam próbują wymienić wartości z innym wątkiem.

Klasa `RangePolicy` pilnuje, aby zakres z którego wątki wybierają swoje miejsce na `EliminationArray` był optymalny - jeśli mało wątków odnosi się do listy zakres powinien być mały, aby zwiększyć liczbę spotkań wątków, a przy dużej ilości wątków powinien być on większy, aby zmniejszyć ilość wątków czekających gdy ich wybrany exchanger ma stan BUSY.

Punkty linearyzacji:
`push()` - mamy 2 przypadki:
Nowy węzeł zostaje wstawiony na stos: wtedy punktem linearyzacji jest udany `top.compareAndSet(oldTop, node)`
Wartość zostaje wyeliminowana przez `pop()`: punktem będzie ustawienie slota na null i stanu na EMPTY w wybranym exchangerze.

`pop()` - podobnie

## Zadanie 3
:::success
Autor: Marcin Majchrzyk
:::

Klasa ```CombiningTree``` wykorzystuje drzewo binarne do współdzielenia licznika. Każdy wątek dostaje współdzielony z co najwyżej jednym innym wątkiem liść na którym może dokonywać zmian.

Kiedy wątek dokona zmiany na liczniku to nowa wartość zostaje przeniesina do wyższych węzłów.

Gdy dwie wątki spotykają się w węźle to zmiany zostają sumowane i przenoszone wyżej przez jeden, aktywny, wątek, a drugi, pasywny, wątek oczekuje aż aktywny wątek zakończy pracę.

W momencie gdy zmiana dotrze do korzenia to główny licznik zostaje zaktualizowany i nowa wartość zostaje rozprowadzona do wszystkich liści.

## Zadanie 4
:::success
Autor: Jan Marek
:::



Flaga `locked` pełni rolę jednego z dwóch zamków, który jest zakładany na wierzchołek w drzewie (synchronizacja krótkoterminowa - metody `synchronized`, zmienna `locked` - synchronizacja długoterminowa). Jeśli `locked == true`, to oznacza, że wierzchołek uczestniczy aktualnie w jakimś innym wykonaniu `getAndIncrement()`, a więc musimy poczekać, aż zostanie on zwolniony.

1)

`Precombining:` ponieważ może wystąpić sytuacja, że inny wątek już w tym wierzchołku skończył metodę combine(), a więc nie chcemy do tego wierzchołka wejść, czyli cierpliwie czekamy.

`Combining:` ponieważ może się zdarzyć, że do wierzchołka przybył inny wątek, ale jeszcze nie skończył swojej pracy, a więc czekamy, aż zdeponuje on swoją wartość, by połączyć obie wartości.

2)

Jeśli wątek wykonuje metody `op()`/`distribute()`, to mamy pewność, że żaden inny wątek mu nie przeszkodzi, tzn. wykonując te metody, operujemy na zablokowanych poddrzewach. Kiedy wątek będzie schodził w dół poddrzewa, będzie wtedy zwalniał blokady.

3)

**precombine()**

(wiersz 26)
Napotkany wierzchołek jest w stanie `first`, a więc jesteśmy drugim wątkiem, który przybył do tego wierzchołka, więc zakładamy zamek, żeby drugi wątek (szybszy) poczekał, aż obliczymy wartość sumy z naszego poddrzewa

**combine()**

(wiersz 37)
Ponownie idziemy ścieżką od liścia w górę i w każdym napotkanym wierzchołku zakładamy zamek, ponieważ nie chcemy, aby inne spóźnione wątki wykonujące `precombine()` weszły do tych wierzchołków.

**op()**

(wiersz 56)
Byliśmy wolniejszym wątkiem i właśnie skończyliśmy przechodzić swoje poddrzewo w fazie `combine`, a więc ustawiamy wartość `secondValue` na wyliczoną sumę `combined` i zwalniamy zamek, aby szybszy wątek mógł kontynuować i iść dalej.

(wiersz 59)

**distribute()**

(wiersz 71)
Wracamy z wartością licznika w dół. Jeśli węzeł ma stan `first`, to oznacza, że nie pojawił się tam drugi wątek, ale wierzchołek ten miał założony zamek, więc go ściągamy. Gdy jednak do wierzchołka przyszedł drugi wątek (czyli miał stan `second`), to zostawiamy zwolnienie zamka w tym wierzchołku drugiemu wątkowi.

## Zadanie 5
:::danger
Autor:
:::

## Zadanie 6
:::danger
Autor:
:::

## Zadanie 7
:::danger
Autor:
:::