# Współbieżne - Lista 6
:::success
## Zadanie 1
:::
### 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.
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.
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 któryś wątek będzie czekał (będzie zablokowany) na locka.
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 któryś wątek będzie czekał na locka
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.
:::success
## Zadanie 2
:::
1. **Bezpieczny**
Ponieważ komórki pamięci są rejestrami MRMW to może wystąpić sytuacja, że będą sie pokrywać dwa *write*
W tym przypadku do naszego 64-bitowego (złożonego z dwóch 32-bitowych) rejestru może zostać zapisana górna połowa bitów rejestru `w1` z jednego *write* i dolna połowa bitów rejestru `w2` z drugiego *write*. Gdy następnie zrobimy *read*, który się nie nakłada z nimi to oczekujemy, że dostaniemy dobrą wartość całego 64-bitowego rejestu ale zamiast tego czytamy połowę rejestu `w1` i połowę rejestru `w2`. Czyli warunek **bezpiecznego** rejestru jest **niespełniony**.
2. **Regularny**
Gdy rejestr nie jest bezpieczny to nie jest też regularny.
3. **Atomowy**
Gdy rejestr nie jest regularny to nie jest też atomowy.
## Zadanie 3
## Rozwiązanie 1:
### Algorytm Petersona
```= java
public void lock() {
flag[i] = true;
victim = i;
while (flag[j] && victim == i) {};
}
public void unlock() {
flag[i] = false;
}
```
### Rozwiązanie
Zachowanie rejestrow atomowych i regularnych rozni sie w sytuacji, gdy na rejestrze jednoczesnie dokonywany jest zapis i odczyt. Sprawdzmy czy w takiej sytuacji wymienione wartosci zostaja zachowane.
Do odczytu dochodzi tylko w linii 4. Niech watkiem dokomujacym odczytu jest A, a jednoczesnie zapisu dokonywac bedzie B.
B zapisuje na linii 2
A odczytuje stara wartosc flag[B] falsz i wchodzi do sekcji krytycznej. B czeka (wzajemne wykluczanie) az A zmieni swoja flage w unlock po sekcji krytycznej (co sie wydarzy) (niezaglodzenie)
A odczytuje nowa wartosc i czeka. B ustawia jako ofiare siebie, wiec A przestaje czekac i wchodzi w sekcje krytyczna, a B czeka, bo flag[A] nie została zmienionia (wzajemne wykluczanie), dalszy przebieg jak wyzej (niezaglodzenie).
B zapisuje na linii 7
A odczyta albo jedna iteracje wczesniej albo w takim samym momencie (jak przy rejestrach atomowych) flag[B] falsz i przejdzie do sekcji krytycznej (niezaglodzenie), ale B juz wyszlo z sekcji krytycznej (wzajemne wykluczanie).
## Rozwiązanie 2:
Intuicja: regularny od atomowego różni się tym, że wywołanie nie musi być linearyzowalne. Jednak jak mamy dwa wątki to nie powinno to mieć znaczenia.
Wiemy, że jeśli zapis i odczyt się nie nakładają to rejest atomowy i regularny zachowa się tak samo.
Zobaczmy zatem co się wydarzy jeśli nałożą nam wykonania read i write. Wiemy, że Peterson jest algorytmem dwuwątkowych.
Zobaczmy zatem co stanie się gdy wątek A będzie zapisywać Flag[A] = true a wątek B będzie czytać Flag[A] (czyli będzie w while)
Wiemy, że poprzednią wartością flag[A] było false. Zatem B przeczyta false albo true
Rozrysujsmy to na osi czasu
Zauważmy jednak, że obojętnie co wtawimy w znak zapytania to wywołanie to będzie linearyzowalne.
Zatem w przypadku tego algorytmu rejest regularny zachowuje się tak samo jak rejest atomowy.
Zatem można zastąpić rejest atomowy rejestrem regularnym.
A: ---<A.read(flag[B] == true)>--<A.read(flag[B] == false)>---
B: ---<B.write(flag[B] = false)>--<B.write(flag[B] = true)>---
:::success
## Zadanie 4
:::
## Rozwiązanie 1:
Idea:
* Wykorzystujemy 2 $\lceil \log M+1\rceil$ boolowskich rejestrów do przechowywania wartości w zapisie dwójkowym (nazwane DATA[0] oraz DATA[1]).
* Wykorzystujemy 1 boolowski rejestr do przechowania informacji o porządku zapisu danych (nazwany INDEX).
### Funkcja write(x)
* Odczyta stan INDEX
* Wyznaczy NEWINDEX równy NOT(INDEX)
* Zapisze wartość x do DATA[NEWINDEX]
* Zapisze NEWINDEX do INDEX
### Funkcja read()
* Odczytuje wartość INDEX
* Odczytuje wartość DATA[INDEX]
### Uzasadnienie
#### Wywołanie read bez współbieżnych wywołań write
W takim przypadku nie zmieni się zawartość INDEX i DATA[INDEX].Oznacza to, że będziemy odczytywać ostatnią zapisaną wartość.
#### Wywołanie read ze współbieżnym wywołaniem write
Możliwe przypadki:
1) read odczyta wartość sprzed współbieżnego write (przeczyta wartość zmiennej INDEX, zanim zmieni ją write)
2) Przeczyta zmienioną wartość INDEX i oznacza to, że wczyta wartość nowego i gotowego do odczytu rejestru DATA.
#### Wiele współbieżnych wywołan write
W takim przypadku przeczytana wartość może być dowolna. Podczas próby odczyty bufory zmienią się wielokrotnie, w wyniku read może odczytać fragment z każdego write.
:::success
## Zadanie 5
:::
:::success
**Twierdzenie**
dobry rejestr MRSW jest **regularny** *wtedy i tylko wtedy*, gdy dla każdego ciągu dostępów:
* dla każdego $i$ nie jest prawdą, że $𝑅^i \rightarrow W^i$ (\*), oraz
* dla każdych $i$ oraz $j$ nie jest prawdą, że $𝑊^i \rightarrow W^j \rightarrow R^i$ (\*\*).
:::
:::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”).
:::
$\implies$
Załóżmy, że mamy regularny rejestr MRSW. Weźmy dowolny ciąg dstępów.
* **(\*)**
Nie może zajść $R^i\rightarrow W^i$, bo rejestr jest regularny (w rejestrze nie znajduje się, nie jest do niego zapisywana $i$-ta wartość.).
* **(\*\*)**
Nie może zajść $W^i\rightarrow W^j \rightarrow R^i$, bo rejestr jest regularny (podczas gdy miałoby zajść $R^i$, $i$-tej wartości już w tym rejestrze nie ma).
$\impliedby$
Załóżmy, że mamy dobry rejestr MRSW, taki że dla każdego ciągu dostępów zachodz:
* dla każdego $i$ nie jest prawdą, że $𝑅^i \rightarrow W^i$ (\*), oraz
* dla każdych $i$ oraz $j$ nie jest prawdą, że $𝑊^i \rightarrow W^j \rightarrow R^i$ (\*\*).
1. read() ($R^k$) jest niewspółbieżny z żadnym write().
Z (\*): $W^k \rightarrow R^k$.
Z (\*\*): nie istnieje takie $j$, że $𝑊^k \rightarrow W^j \rightarrow R^k$.
A zatem, $W^k$ jest ostatnik zapisem poprzedzającym $R^k$.
(jak reg dla sytuacji 1.)
2. read() ($R^x$) jest współbieżny z write()
$$
x \leq k +l \text{, bo (*)}\\
x \geq k \text{, bo (**)}
$$
(jak reg dla sytuacji 2.)
A zatem twierdzenie zachodzi.
## Rozwiązanie 2:
1) Załóżmy, że rejestr MRSW jest regularny. Wtedy dla każdego ciągu współbieżnych dostępów:
- jeśli odczyt nie był współbieżny z żadnym zapisem, zwrócił ostatnią zapisaną wartość
- jeśli odczyt był współbieżny z jednym lub większą liczbą zapisów, zwrócił ostatnią zapisaną wartość lub którąś z wartości zapisanych przez te zapisy
Dla każdego $i$ nie jest prawdą, że $R^i \rightarrow W^i$, bo wartość zapisana przez $W^i$ nie była ostatnią zapisaną wartością w momencie odczytu $R^i$ oraz $R^i$ i $W^i$ nie są współbieżne.
Dla każdych $i$ oraz $j$ nie jest prawdą, że $W^i \rightarrow W^j \rightarrow R^i$, ponieważ wartość zapisana przez $W^i$ nie była ostatnią zapisaną wartością w momencie odczytu $R^i$ oraz $R^i$ i $W^i$ nie są ze sobą współbieżne.
2) Załóżmy, że rejestr MRSW jest dobry i spełnia następujące warunki:
- dla każdego $i$ nie jest prawdą, że $R^i \rightarrow W^i$ (*),
- dla każdych $i$ oraz $j$ nie jest prawdą, że $W^i \rightarrow W^j \rightarrow R^i$ (**).
Weźmy dowolny ciąg współbieżnych dostępów i rozważmy dowolny odczyt z tego ciągu.
a) Odczyt nie jest współbieżny z żadnym zapisem.
Załóżmy, że odczytana wartość jest różna od ostatniej zapisanej wartości. Ponieważ rejestr jest dobry, odczytana wartość musiała występować wśród wartości zapisanych. Z warunku (*) zapis tej wartości musiał mieć miejsce przed jej odczytem (albo współbieżnie z nim, ale ten odczyt nie jest współbieżny z żadnym zapisem). W takim razie wystąpiła sytuacja:
$$
W^i \rightarrow W^j \rightarrow R^i,
$$
gdzie $W^j$ to ostatnia niewspółbieżnie zapisana wartość (w momencie odczytu $R^i$). Jest to sprzeczne z warunkiem (**).
Jeśli odczyt nie jest współbieżny z żadnym zapisem, to odczytana wartość jest ostatnią zapisaną wartością.
b) Odczyt jest współbieżny z zapisami.
Załóżmy, że odczytana wartość jest różna od ostatniej zapisanej wartości i od wartości zapisywanych przez te współbieżne zapisy.
Rejestr jest dobry i spełniony jest warunek (*), więc odczytana wartość musiała być wartością zapisaną przed odczytem lub współbieżnie z nim. Z założenia nie mogła być zapisana współbieżnie z odczytem, więc otrzymujemy sytuację
$$
W^i \rightarrow W^j \rightarrow R^i
$$
gdzie $W^j$ to ostatnia niewspółbieżnie zapisana wartość (w momencie odczytu $R^i$).
Jeśli odczyt jest współbieżny z zapisami, to odczytana wartość jest ostatnią zapisaną wartością lub wartością zapisaną przez te współbieżne zapisy.
:::success
## Zadanie 6
:::
Rejestr **atomowy** musi też być **regularny**, więc (\*) oraz (\*\*) mamy z poprzedniego zadania.
Teraz (\*\*\*):
Załóżmy, że rejestr jest atomowy. Implikuje to, że dla każdego i, j $$ R^i -> R^j \implies i \leq j $$
Dowód: jeżeli i > j to nie mamy poprawnej linearyzacji. A rejestr atomowy jest linearyzowalny.
Załóżmy, że rejestr jest regularny oraz dla każdego i, j $$ R^i -> R^j \implies i \leq j (W^i -> W^j) $$
Jest to wtedy rejestr atomowy.
Dowód: Jedyną różnicą między rejestrem atomowym a regularnym jest to, że dla rejestru regularnego może wystąpić sytuacja: $$ R^i -> R^j, i > j W^j -> W^i)$$
:::success
## Zadanie 7
:::
Załóżmy, że w tej implementacji jest podobnie jak w podręczniku, czyli na początku zapalony jest zerowy bit.
Lemat: Wywołanie read() zawsze zwróci wartość odpowiadającą bitowi ze zbioru 0...M-1, ustawioną przez jakieś wywołanie write().
Na początku write() zapalany jest najpierw nowy bit, dopiero później wszystkie wcześniejesze wartości są gaszone, czyli zawsze jakiś bit jest zapalony.
Załóżmy, że x jest poprzednio ustawioną wartością przez jakieś write(), czyli dla dowolnego *i<x*, wszystkie bity *i* są zgaszone.
Niech jakiś wątek wykonuje operację read(). Wówczas jeśli ten wątek odczyta wartość *bit[j] == true*, gdzie *j<x* to oznacza to, że jakiś współbieżny wątek wykonał write(), co jest zgodne z lematem i dowodzi twierdzeniom 4.1.1 i 4.1.2.
## Rozwiązanie 2:
```java=
public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M] bit; // tutaj możemy chcieć zaznaczyć 0 na początku
public void write(int x) {
this.bit[x].write(true);
for (int i=x-1; i>=0; i--)
this.bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (this.bit[i].read())
return i;
}
}
```
Definicja regularnego rejestru:
Lemat: Read zawsze zwróci wartość
Zauważmy, że usunięcie wartości poprzedza zapisanie większej. Oznacza to, że największa zapisana wartość zawsze jest zapalona.
Jeśli podczas read nie występuje write:
Wtedy wszystkie bity do ostatnio zapisanej wartości są zgaszone więc zostanie ona przeczytana.
Jeśli read występuje podczas write:
Jeśli zostanie zwrócona wartość mniejsza od x, to musiała ona zostać wprowadzona po ostatnim poprzedzającym write, ponieważ pola te zostały wyzerowane podczas jego zapisu.
Jeśli zwrócone zostanie coś większego od $v^i$ (w tym x) dla dow. $i \in 0..k$ to $v^i$ musiał zostać usunięty przez write - czyli wszystkie bity do $v^j$ - wartości wprowadzonej w między czasie przez write, zostały wyzerowane. Więc zostanie zwrócona wartość $v^l$ dla $l \in 1..k$
## Zadanie 8
## Zadanie 9
Sign in with Wallet
Connect another wallet