# Ćwiczenia 8, grupa cz. 16-18, 7 grudnia 2023

###### 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | X | X | | | | | X |
Paweł Borek | X | X | | | | | |
Arti Brzozowski | | | | | | | |
Mateusz Golisz | X | X | X | | X | X | X |
Kacper Jóźwiak | X | X | X | | X | X | X |
Julia Konefał | | | | | | | |
Adam Korta | X | X | X | | X | X | |
Jakub Mikołajczyk | X | X | X | | X | | X |
Bartosz Morasz | X | X | X | | X | | X |
Andrzej Morawski | | | | | | | |
Aleksandra Nicpoń | x | x | x | | x | x | |
Mateusz Reis | X | X | X | | | | X |
Tomasz Stachurski | x | x | | | x | x | x |
Marcel Szelwiga | X | X | X | X | | | |
Volha Tsekalo | x | x | x | | x | x |==x==|
Martyna Wybraniec | x | x | x | | x | x | |
Denys Zinoviev | | | | | | | |
Dominik Olejarz | x | x | x | | ==x== | x | x |
:::

Tutaj można zadeklarować zadania **4** i **7** z **listy 7**

:::danger
| | 7.4 | 7.7 |
| ----------------------:| ----- | ----- |
| Volha Tsekalo | | x |
| Jakub Mikołajczyk | X | |
| Tomasz Stachurski | | x |
| | | |
:::

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

## Zadanie 1
:::success
Autor: Dominik Olejarz
:::
robimy dowod nie wprost zakladamy ze takie drzewo istnieje
Rozwazam mozliwe operacje na rejestrach RMW zmieniajace stan
Wybieram watek C

Skoro A zapisal rejestr RAC to byl przed C
identyczna sytuacja zadziala sie z rejestrem RBC dla B.
C jednak nie ma dostepu do RAB i nie wie ktory watek zapisal wartosc

## Zadanie 2
:::success
Autor: Bartosz Morasz
:::


W tym przypadku nie mamy już problemu z poprzedniego zadania. Gdy dotrzemy do stanu krytycznego, w którym wątki A i B, decydują nad tym czy przejdziemy w stan 0-valent lub 1-valent, to np. gdyby wygrał wątek A, to poza ustawieniem RAB, może ustawić również RAC. Wątek B nie będzie w stanie ustawić RBC, bo RAB jest ustawione na wątek A. Stąd wątek C będzie mógł rozróżnić te dwie ścieżki.

## Zadanie 3
:::success
Autor: Mateusz Golisz
:::
### więcej niż n wątków (nie wprost):
Załóżmy, że wątków mamy dowolne $m$, gdzie $m\in \mathbf N > n$
Nie wprost: załóżmy, że poziom konsensusu wynosi $m$.
Rozważmy stan krytyczny w drzewie przebiegu procesu; załóżmy, że każdy z $m$ wątków wykona operację compareAndSet() dokładnie raz, a wątek X wykona ją jako ostatni i działa solo (a jako, że będzie to m-te wykonanie to otrzyma ⊥); przypadki:
a) najpierw wykonuje się wątek A, następnie cała reszta, ostatni będzie wątek X
b) najpierw wykonuje się wątek B, następnie cała reszta, ostatni będzie wątek X
(itp.; kolejność początkowych wykonań nie ma znaczenia)
W obu przypadkach wątek X otrzymał ⊥, czyli stan obiektu jest według niego identyczny; ponieważ wyszliśmy jednak ze stanu krytycznego, to zwrócone zostaną różne wyniki - Sprzeczność, czyli poziom konsensusu wynosi co najwyżej n.

### co najmniej n wątków:
Używamy rozumowania z wykładu - skoro compareAndSet() można użyć do rozwiązania konsensusu nieskończenie wielu wątków, to wersja, która działa analogicznie dla pierwszych $n$ użyć jest w stanie rozwiązać ten problem dla przynajmniej n wątków.

### dokładnie n
Ponieważ wykazaliśmy, że poziom konsensusu jest $<=n$ oraz jednocześnie $>=n$, to otrzymujemy, że wynosi on dokładnie $n$.

## Zadanie 4
:::success
Autor: Marcel Szelwiga
:::

class assign23{
    AtomicInteger[] arr = new AtomicInteger[3];
    
    public void assign(int ind1, int ind2, int val1, int val2){
        int old1 = arr[ind1].get();
        int old2 = arr[ind2].get();
        
        arr[ind1].compareAndSet(old1, val1);
        arr[ind2].compareAndSet(old2, val2);
    }
    
    public int get(int ind){
        return arr[ind].get();
    }
};

Dlaczego działa -- chcemy pokazać, że historia wywołań jest linearyzowalna, możemy rozważyć trzy przypadki:

* obie operacje `compareAndSet` zakończyły się powodzeniem, w takim przypadku żaden z wątków nie ustawił swojej wartości pomiędzy naszym odczytem, a zapisem. Możemy zatem w prosty sposób wykonać linearyzacje -- inne wątki, które wykonują aktualnie tą procedurę będą później w linearyzacji,

* tylko jedna z operacji `compareAndSet` zakończyła się powodzeniem, oznacza to, że metoda wykonuje się współbieżnie z innym wątkiem. Biorąc pod uwagę, że nie udało nam się ustawić wartości, to możemy uznać, że nasze wywołanie będzie wcześniej w linearyzacji,

* żadna z operacji `compareAndSet` nie zakończyła się powodzeniem, zatem inne wątki musiały wykonywać współbieżnie naszą metodę, aby zlinearyzować to wywołanie możemy umieścić nasze wywołanie przed nimi.

Komentarz do zadania po ćwiczeniach: wypadałoby dospecyfikować założenia zadania -- mamy dane dwa wątki, które modyfikują tablicę, na różnych parach indeksów, w przeciwnym przypadku można pokazać, że nie istnieje punkt linearyzacji dla powyższej implementacji.

## Zadanie 5
:::success
Autor: Adam Korta
:::

public class  QuasiConsensus {
    int propose[] = [-1, -1];
    
    public int decide(int v) {
        if (ThreadID.get() == A) return decideA(v);
        return decideB(v);        
    }
    
    public int decideA(int v) {
        if (v == 1) return 1;
        
        propose[A] = 0;        
        if (propose[B] == 1)
            return 1;
        
        return 0;
    }
    
    public int decideB(int v) {
        if (v == 0) return 0;
        
        propose[B] = 1;        
        if (propose[A] == 0)
            return 0;
        
        return 1;
    }
}

Pokażmy, że poziom konsensusu QuasiConsensus nie wynosi 2.

Weźmy stan krytyczny. Rozważmy przypadki:

1. Wątki A i B wywołują decide() z tą samą wartością

Załóżmy bez straty ogólności że tą wartością jest 0. Wtedy zarówno `decide_A(0) -> decide_b(0)` jak i `decide_B(0) -> decide_A(0)` prowadzą do takiego samego stanu, jednak jedno jest w poddrzewie 0-walentnym, a drugie w 1-walentnym

2. Wątki A i B wywołują decide() z różnymi wartościami

Załóżmy bez straty ogólności że `A: decide(1)` oraz `B: decide(0)`. Zgodnie z definicją w takim wypadku algorytm albo uzgodni jedną z wartości, albo A otrzyma 1 a B otrzyma 0. Oznacza to że `decide_A(1) -> decide_B(0)` jest nierozróżnialne od `decide_B(0) -> decide_A(1)`.

## Zadanie 6
:::success
Autor: Martyna Wybraniec
:::


W dowodzie niemożliwości skonstruowania obiektu dwuwątkowego konsensusu przy pomocy atomowych rejestrów korzystaliśmy z faktu, że w pewnym momencie dojdziemy do stanu krytycznego oraz skończymy w stanie uniwalentnym. Było to możliwe dzięki właściwości wait-free algorytmu, która gwarantowała, że praca wątków wykona się w skończonej liczbie kroków, zatem nigdy nie będziemy tkwili w nieskończoność w stanie biwalentnym. Dokładnie tak samo działa algorytm lock-free - zawsze mamy przynajmniej jeden taki wątek, który postępuje nawet jeśli pozostałe wątki są uśpione.

## Zadanie 7
:::success
Autor: Volha Tsekalo
:::
Pokażemy, że metoda z listy 7., zad. 6. jest niehamowana.
Zauważmy, że jeśli algorytm wykonują dwa wątki A i B, to jeden z nich skończy działanie(np. A), a drugi (np. B) będzie wykonywał go w izolacji.
Chcemy pokazać, że ten drugi wątek (B) kiedyś skończy swoje działanie.
Przyjrzyjmy się funkcji decide:
1. przypadek - position_B < position_A. Wtedy w kolejnym obrocie pętli while wejdziemy w else if i zwrocimy proposed_A.
2. przypadek - position_B >= position_A. A już nie zwiększy swojej pozycji, natomiast wartosc zmiennej position_B bedzie wzrastać z każdym obrotem pętli, więc w skończonej liczbie kroków dojdziemy do momentu, w którym position_B > position_A + speed_A i zwrocimy proposed_B.