# Ćwiczenia 6, grupa śr. 12-14, 30 listopada 2022

###### 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!**

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

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

## Zadanie 1
:::success
Autor: Bartosz Szczeciński
:::

### Zdefiniuj następujące własności postępu: nieczekanie (ang. wait-freeness),

Każde wywołanie metody zakończy się w skończonej liczbie kroków całego systemu

Tj. każdy wątek, który aktualnie się wykonuje, dokonuje postępu

### niewstrzymywanie (ang. lock-freeness).

Jakieś wywołanie metody (dla jakiegoś wątku) zakończy się w skończonej liczbie kroków całego systemu.

Tj. cały system dokonuje postępu, ale konkretny wątek niekoniecznie dokonuje postępu.

### Dlaczego te własności nazywane są nieblokującymi (ang. non-blocking) i niezależnymi (ang. independent)?

Nieblokujące - bo nie dopuszczają możliwości, że czekanie któregoś wątku zablokuje inne.

Niezależne - bo nie zależą od spełnienia jakiegoś warunku przez system operacyjny

### Dlaczego niezakleszczenie i niezagłodzenie są blokujące i zależne?

Blokujące - dopuszczają możliwość, że czekanie któregoś wątku zablokuje inne

Zależne - zależą od spełnienia warunku przez system operacyjny (fair scheduling)

### Czy współbieżna metoda w nietrywialny sposób wykorzystująca zamki może być nieczekająca?

Nie, bo jeśli wątek A zajmie lock i wątek B będzie na niego czekał, to B nie będzie dokonywał postępu.

### Dana jest metoda weird(), której każde i-te wywołanie powraca po wykonaniu 2^i instrukcji. Czy ta metoda jest nieczekająca?

Tak, bo każde wywołanie zakończy się w skończonej liczbie kroków (po 2^i krokach)

### A nieczekająca z limitem kroków (ang. bounded wait-free)?

Nie, bo liczba kroków zależy od argumentu funkcji, więc nie możemy podać stałej ograniczającej liczbę kroków.

## Zadanie 2
:::success
Autor: Michał Hetnar
:::

public:
int32 a;
int32 b;
const s = 2 << 32;

read(){
int64 c = a * s;
c = c + b; 
return c;
}
write(int64 d){
a = b / s; 
b = d % s;
}

Czy takie rozwiązanie spełnia warunek rejestru bezpieczniego?
Tak,
jeżeli nachodzą na siebie
x było t
x zapisało się na z
z x przeczytano ?

A: -------x.read()--
B: ---x.write(a)----

A: -------(a-b---)--
B: ---(-a-----b)----

a = z(1)
b = t(2)

przeczytane x nie jest ani t ani z ale należy do wartości dopuszczalnych

regularności i atomowości.

## Zadanie 3
:::success
Autor: Marcin Sarnecki
:::

### Algorytm Petersona

public void lock() {
 flag[i] = true; 
 victim  = i; 
 while (flag[j] && victim == i) {};
}
public void unlock() {
 flag[i] = false;
}

W rejestrze regularnym może wystąpić sytuacja, w której jeśli nachodzą na siebie read() i write(x), to read() odczyta starą wartość.

Zauważmy, że algorytm Petersona jest dwuwątkowy. Jeśli jeden z wątków wykonuje write(x) na swojej fladze, a drugi wątek odczytuje flagę pierwszego wątku, to niezależnie od odczytanej wartości ta sytuacja jest linearyzowalna

## Zadanie 4
:::success
Autor: Wiktor Bukowski
:::


Zasada działania rejestru 1-regularnego:

           <--read()-->
<--write(x)-->         | 
                       ^
        najwcześniejsze możliwe wykonanie kolejnego write()

class OneRegularSRSW implements Register {
    int SIZE = log(M);
    boolean[] value[] = {new boolean[SIZE], new boolean[SIZE]};
    boolean valid = 0;
    
    public OneRegularSRSW() {
        for(int i = 0; i < SIZE; i++) {
            value[0][i] = 0;
            value[1][i] = 0;
        }
    }
    
    public void write(int x) {
        boolean to_write = 1 - valid;
        for(int i = 0; x > 0; i++) {
            value[to_write][i] = x % 2;
            x /= 2;
        }
        valid = to_write;
    }
    
    public int read() {
        boolean my_valid = valid;
        int val = 0;
        for(int i = SIZE - 1; i >= 0; i++) {
            val = 2 * val + value[my_valid][i];
        }
        return val;
    }
}

W działaniu sekwencyjnym poprawność działania jest oczywista.

W działaniu równoległym mamy 3 przypadki:

- odczyt `valid` jest wykonany po modyfikacji go przez równoległe wywołanie `write`

`write` skończył działanie, a więc sytuacja jest równoważna wykonaniu sekwencyjnemu.

- odczyt `valid` jest wykonany przed modyfikacją go przez równoległe wywołanie `write`

`write` jest w trakcie zapisywania nowej wartości. W całości odczytamy starą wartość, która nie zostanie zmodyfikowana, ponieważ może istnieć tylko jedno równoległe wykonanie `write`.

- odczyt `valid` jest wykonany w trakcie modyfikacji go przez równoległe wywołanie `write`

`write` już zapisał całą nową wartość. Nieistotne jest więc, którą z dwóch wartości odczytamy.

## Zadanie 5
:::success
Autor: Tomasz Wołczański
:::
:::info
**Definicja**
Rejestr nazwiemy dobrym, jeśli dla każdego ciągu współbieżnych dostępów do tego rejestru (zapisów i odczytów) każda wartość odczytana występuje wśród wartości zapisanych (tzn. wartości odczytane nie biorą się “z powietrza”).
:::

Weżmy dowolny dobry rejestr MRSW $r$ i dowolny ciąg $H$ współbieżnych dostępów do $r$.

### $(\Rightarrow)$
Załóżmy, że $r$ jest regularny. Pokażemy, że dla $H$ zachodzi $(*)$ i $(**)$.

$(*)$
Weźmy dowolne $i$ i załóżmy nie wprost, że $R^i \rightarrow W^i$. Ponieważ rejestr jest regularny, to odczyt $R^i$ nastąpił po zapisie $W^i$ lub współbieżnie z nim. Jest to sprzeczne z tym, że w ciągu dostępów do rejestru może być co najwyżej jeden zapis $W^i$ (tutaj mamy dwa zapisy: jeden przed lub w trakcie odczytu, a drugi po odczycie).

$(**)$
Weźmy dowolne $i,j$ i załóżmy nie wprost, że $W^i \rightarrow W^j \rightarrow R^i$. Ponieważ rejestr jest regularny, to odczyt $R^i$ nastąpił po zapisie $W^i$ i pomiędzy zapisem $W^i$ a odczytem $R^i$ nie było żadnego zapisu, lub współbieżnie z zapisem $W^i$. W obu przypadkach otrzymujemy sprzeczność z założeniem, bo zapis $W^i$ może być co najwyżej jeden.

### $(\Leftarrow)$
Załóżmy, że dla $H$ zachodzi $(*)$ i $(**)$. Pokażemy, że $r$ jest regularny. Weźmy dowolny odczyt $R$ i rozważmy dwa przypadki:
1. odczyt $R$ nie pokrywa się w czasie z żadnym zapisem
Ponieważ rejestr $r$ jest dobry, to zbiór możliwych wartości zwróconych przez $R$ jest równy zbiorowi wartości zapisanych przez wszystkie zapisy. Niech $W^i$ będzie ostatnim zapisem, który nastąpił przed $R$. Z $(*)$ wynika, że dla $j>i$ odczyt $R$ nie może zwrócić wartości zapisanej przez $W^j$, więc zbiór możliwych wartości zwróconych przez $R$ redukuje się do wartości zapisanych przez $W^1,W^2,\dots,W^i$. Skoro $W^i$ jest ostatnim zapisem, który nastąpił przed $R$, to dla $j<i$ mamy $W^j \rightarrow W^i \rightarrow R$, więc zgodnie z $(**)$ wartość zapisana przez $W^j$ nie może zostać zwrócona przez $R$. Zatem jedyną wartością, którą może zwrócić $R$ jest wartość zapisana przez $W^i$, co odpowiada zachowaniu rejestru regularnego.
2. odczyt $R$ pokrywa się w czasie z pewnym zapisem
Niech $W^i$ będzie ostatnim zapisem, który nastąpił przed $R$, a $W^{i+1}, W^{i+2},\dots,W^{j}$ zapisami, które pokrywają się w czasie z $R$. Podobnie jak w przypadku 1. zbiór możliwych wartości zwróconych przez $R$ można zredukować do wartości zapisanych przez $W^1, W^2,\dots,W^j$. Analogicznie jak w przypadku 1. dla $k < i$ wartość zapisana przez $W^k$ nie może zostać zwrócona przez $R$. Zatem zbiór wartości, które może zwrócić $R$ jest równy zbiorowi wartości zapisanych przez $W^i, W^{i+1},\dots, W^{j}$. To odpowiada zachowaniu rejestru regularnego, ponieważ $W^i$ jest ostatnim zapisem poprzedzającym $R$, a $W^{i+1},W^{i+2},\dots,W^{j}$ zapisami pokrywającymi się w czasie z $R$.

## Zadanie 6
:::danger
Autor: dodeklarować
:::

## Zadanie 7
:::success
Autor: Jan Dalecki
:::


### Lemat 1

**Wywołanie funkcji read zawsze zwróci wartość z przedziału $0...M-1$ ustawioną przez pewien zapis.**

Zauważmy, że zawsze co najmniej jeden bit ma wartość true.

Załóżmy, że wątek czyta $bit[j]$ oraz $bit[k] = true$ dla $k \ge j$.

Jeżeli zacznie czytać $j+1$ to oznacza, że $bit[j] = false$ i $k > j$.

Zapisujący wątek wyczyści $bit[k]$ tylko wtedy gdy pewien $bit[t]$, $t > k$ jest ustawiony na true.

Wywołanie funkcji odczytu odczyta wartość ustawioną przez pewne wywołanie zapisu.

Załóżmy, że wątek czyta $bit[j]$ oraz wszytkie bity dla $i > j$ mają wartość false.

### Lemat 2

**Dana implementacja jest rejestrem $M$ regularnym MRSW.**

Załóżmy, że dla dowolnego wywołania funkcji read $x$ będzie ostatnio zapisaną wartością przez nierównoległy wątek.

Mamy $bit[x] = true$ oraz $bit[i] = false$ dla każdego $i < x$. Jeżeli czytelnik zwróci wartość inną niż $x$ np. $k$ to $bit[k]$ musiał być ustalony przez współbieżny zapis.

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

Do implementacji tego rejestru dla n wątków użyjemy tablicy `n x n` rejestrów atomic SRSW.

Wątek piszący pisze do komórek na przekątnej (jest ich writerem) nową wartość oraz timestamp.

`i`'ty reader będzie postępować w następujący sposób:
1. odczytaj komórkę z przekątnej `[i][i]`
2. Sprzawdź czy inny reader nie odczytał nowszej wartości poprzez przeczytanie swojego wiersza (komórki `[_][i]` poza `[i][i]`) i ewentualnie zaktualizuj wartość.
3. Wpisz swoją nową wartość do swojej klumny (komórki `[i][_]` poza `[i][i]`)

Każdy reader jest również writerem dla swojego wiersza, jest on jedynym piszącym co jest wymagane dla rejestru SRSW.


1. Nigdy nie zajdzie $R^i$ → $W^i$ - spełnione w oczywisty sposób.
2. Nigdy nie zajdzie $W^i$ → $W^j$ → $R^i$ - Po zakończonym zapisie $W^j$ przekątna zawiera już wartości z nowym największym timestampem, więc porównania z potencjalnie mniejszymi lub równymi wartościami w kolumnach nie wpłyną na wybór wartości zwracanej.
3. $R^i$ → $R^j$ to $i \le j$ - ta właściwość mówi, że odczyt z rejestru atomowego musi odczytać tą samą lub nowszą wartość co wcześniejszy odczyt. Zapis do wierszy gwarantuje nam tę właściwość. Każdy odczyt $A$ → $B$ oznacza, że $A$ wpisał najnowszą zaobserowaną przez niego wartość do wiersza $B$. Tym samym podczas odczytu $B$ trafi na tę wartość w swojej kolumnie przez co zwróci wartość o nie mniejszym timestampie niż $A$.

Te 3 właściwości definiują rejestr atomowy.

## Zadanie 9
:::success
Autor: Julia Matuszewska
:::



**Działanie w dużym skrócie:**
- **Tworzymy** tablicę, która w każdej komórce (po jednej komórce na każdy wątek) ma atomowy rejest MRSW (z wartością wstępną).
- Przy **zapisie** wątek czyta całą tablicę by wybrać najwyższy timestamp i do swojej komórki zapisać (max_timestamp+1, wartość).
- Przy **czytaniu** wątek czyta wszystkie komórki i wybiera tę z najwyższym timestampem.
- **Remisy** w timestampach rozwiązujemy na korzyść mniejszego `THREAD.id()`

**Dowód poprawności:**
Łatwo można zauważyć, że wywołanie read() nie może przeczytać wartości z naszej tablicy, dopóki nie zostanie ona tam zapisana.

###
Załóżmy, że mamy wątki A, B i C takie, że A wykonało `write(x)` całkowicie przed wywołaniem `write(y)` w B, oraz wątek C wykonał `read` całkowicie po wywołaniu `write(y)` B.

Pokażmy, że nie odczytamy `x`, jeżeli `read` został wywołany całkowicie po zapisaniu `y`

A  <write(x)>[timestamp]
B                          <write(y)>[timestamp+1]
C                                                   <read()>

**Przypadki:**

**1. A!=B**
C odczyta wartość zapisaną przez B (`y`), bo ma wyższy timestamp.

**2. A=B (tj. jest to ten sam wątek)** czyli wykonany zostaje zapis sekwencyjny
C odczyta wartość zapisaną przez B (`y`), bo zapis A (`x`) został przez B nadpisany.

### (***)
Załóżmy, że mamy wątki A, B, C i D, takie, że:
- `read_A()` całkowicie poprzedza `read_B()`
- `write_C(x)` wykonany w porządku zapisu przed `write_D(y)`

Pokażmy, że jeżeli A zwróci `y` (wartość zapisana przez D), to B nie zwróci `x`

**Przypadki:**

1. $timestamp_C < timestamp_D$
Jeżeli A odczyta i zwróci wartość `y`, B odczyta również tę wartość lub wartość z wyższym timestampem, więc nie zwróci `x`

2. $timestamp_C = timestamp_D$
Wtedy wątki wykonywały zapis współbieżnie.
Jeżeli A odczyta i zwróci wartość `y` (`a_table[D]`), to B również odczyta wartość w `a_table[D]` skojarzoną z $timestamp_D$ lub większym, nawet jeśli odczytał $timestamp_C$ z `a_table[C]`, bo $C<D$