---
# System prepended metadata

title: 'Ćwiczenia 8, grupa cz. 16-18, 7 grudnia 2023'
tags: [pwit, ćwiczenia, PRW23]

---

# Ć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
:::
![image](https://hackmd.io/_uploads/ryX_uD1Up.png)
robimy dowod nie wprost zakladamy ze takie drzewo istnieje
Rozwazam mozliwe operacje na rejestrach RMW zmieniajace stan 
Wybieram watek C  
![403398733_709866981105295_1071200842887235357_n](https://hackmd.io/_uploads/rkDx5OJ8a.jpg)


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

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

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	
:::
![obraz](https://hackmd.io/_uploads/By7cqIJI6.png)
### 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	
:::
```java=
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
:::
![image](https://hackmd.io/_uploads/r1tPebyLT.png)

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

![image](https://hackmd.io/_uploads/BJ9N2HRS6.png)
![image](https://hackmd.io/_uploads/ByUSJUASp.png)
![image](https://hackmd.io/_uploads/Hyf7yI0Ha.png)
![image](https://hackmd.io/_uploads/rJMVJL0Hp.png)

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

