# L6 - GRUPA 1
## 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
```java
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()
```
```java=
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$
Sign in with Wallet
Connect another wallet