---
# System prepended metadata

title: 'Ćwiczenia 13, grupa śr. 10-12, 24 stycznia 2024'
tags: [pwit, ćwiczenia, PRW23]

---

# Ć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	
:::
![image](https://hackmd.io/_uploads/rkW5P8AYp.png)


## 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().

```java=
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	
:::

![image](https://hackmd.io/_uploads/rJKySziFp.png)

![image](https://hackmd.io/_uploads/BkRYQE2F6.png)
![image](https://hackmd.io/_uploads/r13cmEhtT.png)
![image](https://hackmd.io/_uploads/BkIjQVhK6.png)
![image](https://hackmd.io/_uploads/r1F27E3tp.png)
![image](https://hackmd.io/_uploads/ByXTXV2Kp.png)

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: 	
:::


