# Programowanie współbieżne - lista 7

:::success
# Zadanie 1
:::

* Funkcja collect zrobi nam kopię tablicy. W trakcie robienia kopi mogły np. nastąpić dwa updaty na początku i na końcu tablicy, przez co w kopi pojawi się zmiana tylko ta z dołu tablicy (w tym momencie nasza kopia nie jest prawidłowym snaphotem).

Załóżmy nie wprost, że atomowa migawga SimpleSnaphot nie działa prawidłowo i zwróciła błędny wynik. Wykonanie metody scan zwróciło nam pewien stan tablicy, który nigdy nie istniał. W pewnym momencie funkcji scan musiało wykonać się `Array.equals(oldCopy, newCopy)` i zwrócić true. Mogło to nastąpić tylko jeżeli nie zmienił się żaden timestamp, a skoro się nie zmienił to znaczy w szczególności, że nie nastąpiła żadna zmiana w trakcie wykonania drugiej kopii tablicy. Zatem druga kopia tablicy jest prawidłowym snapshotem. A skoro pierwsza kopia jest równa drugiej to także jest prawidłowym snapshotem. Sprzeczność.

Timestampy są potrzebne, aby mieć pewność, że bład nie nastąpił 2 razy w ten sam sposób.

* W najgorszym przypadku, gdy jest dużo updatów będziemy ponawiać scan w nieskończoność, jeżeli jednak zatrzymamy drugi wątek i pozwolimy pracować scan'owi w odizolowaniu na pewno się on zakończy, zatem jest obstruction-free.
* update wykonuje się atomowo, bez żadnych pętli, zatem jest lock-free, a zatem cały system jest lock-free


:::success
# Zadanie 2
:::

Weźmy dowolne $n > 2$ i załóżmy nie wprost, że istnieje taka nieczekająca implementacja protokołu binarnego konsensusu dla tego $n$. Rozważmy następujące wykonanie.

Wątki $1$ i $2$ rozpoczynają i kończą wykonanie protokołu przed rozpoczęciem jego wykonania przez pozostałe wątki. Jest to możliwe ze względu na to, że implementacja jest nieczekająca. Wątek $1$ zaczyna z wartością $a$, a wątek $2$ z wartością $b$, gdzie $a,b\in\{0,1\}$. Wartością konsensusu jest $a$ lub $b$.

Powyższe wykonanie jest równoważne z rozwązaniem problemu konsensusu binarnego dla dwóch wątków, przy użyciu nieblokującego protokołu używającego jedynie rejestrów atomowych. Ale taka implementacja nie istnieje.

A zatem sprzeczność.
:::success
# Zadanie 3
:::

# Zadanie 4

:::success
# Zadanie 5
:::


* Wartość zwracana przez decide() jest jedną z wartości zaproponowanych przez wątki
Jeżeli wątek 1 jest daleko przed wątkiem 2 to zwracane jest proposed wątku 1, które było wcześniej do tej tablicy zapisane.
Jeżeli wątek 1 jest za wątkiem 2 zwracane jest proposed wątku 2 (które musiało zostać wcześniej zapisane, ponieważ wątek 2 jest przed nami)
* metoda zwraca tę samą wartość obu wątkom
Załóżmy nie wprost, że funkcja zwróciła inną wartość, wtedy mamy następujące możliwości
1. w obu przypadkach spełniła się klauzula position[i] < position[j]
`Read(position[0] < position[1]) -> Read(position[1] < position[0])`
Pomiędzy readami może się tylko zwiększyć `position[1]` zatem sprzeczność.
2. w obu przypadkach spełniła się klauzula position[i] > position[j] + speed[j]
`Read(position[0] > position[1] + speed[1]) -> Read(position[1] > position[0] + speed[0])`
* Jezeli nie zwiększyliśmy `position[1]`, wiemy, że `position[0] > position[1] + speed[1]`, zatem `position[1] < position[0]` zatem wejdzie to else ifa
* Załóżmy że zwiększyliśmy `position[1]` o `speed[1]` zatem w warunku else if mamy: `position[1]+speed[1] < position[0]`
Z `Read(position[0] > position[1] + speed[1])` wiemy, że ten warunek jest spełniony, zatem wejdzie do elseifa i zakończy dziłanie

* Dlaczego ten wynik nie jest sprzeczny z faktem, że poziom konsensusu dla rejestrów atomowych wynosi 1?
Tam naszym wnioskiem była niemożliwość zbudowania takiego konsensusu, ale wtedy gdy decide() jest wait-free, tutaj mamy pętlę while(true), która nie zagwarantuje nam, że pętla się zakończy

:::success
# Zadanie 6
:::

### Rozwiązanie:
### 1
Weźmy n wątków które zapisują jednocześnie do StickyBit.
1) Jeśli wszystkie zapisywały A to StickyBit zwróci A.
2) Jeśli część wątków zapisywała "1" a pozostałe "0" to zapisy wszystkich wątków poza pierwszym zostanie zignorowany i zostanie zwrócony zapis wywołany przez pierwszy wątek.

### 2

Mamy ${\log_2 m}$ obiektów typu StickyBit.

Każdy wątek rozpoczyna zapis od najmniejszego indexu w tablicy. Po próbie zapisu sprawdza jego stan (zapisujemy kolejne bity z liczby którą chcemy zapisać).

W przypadku jego powodzenia zapisuje kolejny bit z w kolejnej komórce i wykonuje porównanie.

W przypadku niepowodzenia przeszukuje wszystkie wątki (próbujące zapisać) w poszukiwaniu liczby, która odpowiada obecnie zapisanym bitom. Zapisuje ją do własnego rejestru i kontynuuje od momentu, w którym się zatrzymał.

1) Tworzy lokalną zmienną 'i=0', liczbę, którą chcemy zapisać nazwiemy NUMBER
2) Jeśli 'i' >= $\log_2 M$ to kończymy działąnie
3) Zapisujemy i-ty bit do tablicy o indexie 'i'
4) Jeśli zdołał zapisać to inkrementujemy 'i' i przechodzimy do kroku 2
5) W przeciwnym przypadku przeszukujemy NUMBER innych wątków w celu znalezienia wartości która zgadza się o obecnie zapisanymi bitami
6) Nadpisujemy własny NUMBER i przechodzimy do kroku 2

# Zadanie 7

:::success
# Zadanie 8
:::

### Rozwiązanie
#### Protokół konsensusu

class FIFOConsensus<T>
{
    FIFO f;
    T[] props;
    T decide(T val)
    {
        props[thr_id] = val;
        f.enq(thr_id);
        return props[f.peek()];
    }
}

#### Uzasadnienie
##### Nieczekający
Nasz konsensus korzysta z nieczekającej kolejki FIFO i "skończonych" odczytów i zapisów, nie występuje natomiast żadna pętla. Konsensus jest zatem nieczekający.
##### Spójny
Nie wprost. Jeżeli dwa wątki wskazały rózne wartości to f.peek() musiało zwrócić różne wartości. Jest to jednak niemożliwe, ponieważ metoda ta zwraca pierwszy element kolejki, który był w obu momentach ten sam, bo nigdy nie został usunięty, ani "zepchnięty" przez innego (ze względu na działanie enq w FIFO). Sprzeczność, wszystkie wątki wskażą tą samą wartość.
##### Poprawny
W linii 9 wskazywana jest wartość z tablicy props o indeksie odpowiadającym pewnemu wątkowi. W tej samej tablicy wątek ten zapisał w tym indeksie wartość, którą proponował. Ustalona zatem będzie wartość zaproponowana przez któryś z wątków.
##### Dla $\infty$ wątków
Wszystkie powyższe obserwacje zostały dokonane bez założeń co do liczby wątków, są słuszne dla $1,2,...$ wątków. Poziom konsensusu wynosi zatem $\infty$.
# Zadanie 9