# L6 - GRUPA 2

## Zadanie 1
:::success
Autor: Adam Jarząbek
:::

**Nieczekanie** - każdy operacja skończy się w skończonej liczbie kroków (gwarancja, że każdy wątek robi progres).

**Niewstrzymywanie** - pojedyncze wątki mogą głodować, ale system jako całość dokonuje progresu.

Te własności nazywane są nieblokującymi, ponieważ porażka lub wstrzymanie jednego porocesu nie spowoduje zablokowania innego procesu.

Niezależne, ponieważ wystąpienie tych własności nie zależy od systemu operacyjnego.

Niezakleszczenie i niezagłodzenie są blokujące, ponieważ, w przeciwieństwie do w.w., istnieje możliwość zablokowania jednego wątku przez problemy drugiego.

Są zależne, ponieważ zależą od tego, czy system operacyjny sprawiedliwie rozdysponuje czas procesora.

Współbieżna metoda wykorzystująca zamki nie będzie nieczająca, ponieważ niektóre wątki będą czekać na dostęp do zamka i nie będą dokonywać postępu.

Metoda weird() jest nieczekająca, ponieważ wykona się po skończonej liczbie kroków. Nie jest bounded wait-free, ponieważ liczba kroków nie jest stała.

## Zadanie 2
:::success
Autor: Zuzanna Kania
:::

class Reg64bit {
    Reg32bit reg1, reg2;
    
    read() {
        val = reg1;
        val += reg2 << 32;
        return val;
    }
    
    write(x) {
        reg1 = x % (1 << 32);
        reg2 = x >> 32;
    }
}

Rejest jest bezpieczny, ponieważ w przypadku wywołań sekwencyjnych zawsze zwraca wartość ostatnio zapisaną. Nie jest jednak regularny, ponieważ w przypadku współbieżnego odczytu i zapisu odczyt rejestru może zwrócić wartość, która nie została nigdy wcześniej zapisana. Skoro nie jest regularny, to nie jest też atomowy.

## Zadanie 3
:::success
Autor: Rafał Starypan
:::

:::spoiler Nieczytelna wersja
Z definicji rejestrów regularnego i atomowego wynika, że jeśli zapis i odczyt się nie nakładają, to to zachowują się one w ten sam sposób.

Można zauważyć, że w tym algorytmie odczyt następuje tylko w jednym miejscu w pętli while(), jeżeli wątek A jest w pętli while, a drugi pisze flag[B]=true.

Dowód wzajemnego wykluczania dalej działa niech
writeB(Flag[B]=true) oznacza koniec wykonania flag[B]=true

(1)writeB(Flag[B]=true)→writeB(victim=B)

(2)writeA(victim=A)→readA(flag[B])→readA(victim)

(3)writeB(victim=B)→writeA(victim=A) (można to założyć ponieważ victim jest nadal atomowe)

writeB(victim=B)→readB(flag[A])→readB(victim)

(1)+(3)+(2)
writeB(Flag[B]=true)→writeB(victim=B)→writeA(victim=A)→readA(flag[B])→readA(victim)

A nie mogło wejść do sekcji krytycznej
:::

:::spoiler Czytelna wersja
Z definicji rejestrów regularnego i atomowego wynika, że jeśli zapis i odczyt się nie nakładają, to to zachowują się one w ten sam sposób.

Można zauważyć, że w tym algorytmie odczyt następuje tylko w jednym miejscu w pętli $while$, jeżeli wątek $A$ jest w pętli $while$, a drugi pisze $flag[B]=true$.

Dowód wzajemnego wykluczania dalej działa.
Niech $\text{write}_B(\text{flag}[B]=true)$ oznacza koniec wykonania $\text{flag[B]}=true$.

1) $\text{write}_B(\text{flag}[B]=true)$ $\rightarrow$ $\text{write}_B(\text{victim}=B)$.
2) $\text{write}_A(\text{victim}=A)$ $\rightarrow$ $\text{read}_A(\text{flag}[B])$ $\rightarrow$ $\text{read}_A(\text{victim})$
3) $\text{write}_B(\text{victim}=B)$ $\rightarrow$ $\text{write}_A(\text{victim}=A)$ (*można to założyć ponieważ victim jest nadal atomowe*)

$\text{write}_B(\text{victim}=B)$ $\rightarrow$ $\text{read}_B(\text{flag}[A])$ $\rightarrow$ $\text{read}_B(\text{victim})$

$\text{1.}$ + $\text{3.}$ + $\text{2.}$
$\text{write}_B(\text{flag}[B]=true)$ $\rightarrow$ $\text{write}_B(\text{victim}=B)$ $\rightarrow$ $\text{write}_A(\text{victim}=A)$ $\rightarrow$ $\text{read}_A(\text{flag}[B])$ $\rightarrow$ $\text{read}_A(\text{victim})$

Wątek $A$ nie mógł wejść do sekcji krytycznej.
:::

## Zadanie 4
:::success
Autor: Kamila Goszcz
:::


Do przechowywania pojedynczej M-wartości potrzebujemy $log\ m$ rejestrów boolowskich - będziemy zapisywać M-wartość jako jej reprezentacje w systemie dwójkowym.

Do rejestru 1-regularnego SRSW będziemy potrzebować dwóch M-wartości: jedna z nich reprezentować będzie poprzednią wartość, a druga aktualną, na której będą wprowadzane zmiany. Dodatkowo będziemy potrzebowali jednego rejestru który będzie reprezentował, która z tych wartości jest aktualna - nazwijmy ja current. Razem O(log m)

1. read():
Czyta ze zmiennej current, z którego rejestru ma czytać M-wartość i ją zwraca
2. write():
Czyta ze zmiennej current, która M-wartość jest aktualna i d tej drugiej zapisuje nową M-wartość po czym zmienia wartość current na przeciwną

- read(), które nie jest współbieżne z żadnym write zczyta sobie wartość która została wpisana jako ostatnia
- read(), współbieżne z dokładnie jednym write(). Jeżeli write() zdąży zmienić zmienną current to read przeczyta świeżo wpisaną wartość. W p.p. read() odczyta starą wartość, z write() zapisze do tej drugiej
- read(), współbieżne z wieloma write(). Write() będzie wielokrotnie zmieniał current, zatem zapisywane będzie do obu M-wartości, również do tej z ktrej read() będzie aktualnie czytał - wynik może być dowolny

## Zadanie 5
:::success
Autor: Daniel Wiczołek
:::

<!--  -->

regularny czyli gdy overlapping read&write to current lub prev wartosc, a gdy nie to prev ofc.
"wb" - współbieżny

- $\rightarrow$
- zalozmy nie wprost ze:
- **a)** istnieje takie $i$ ze $R^i \to W^i$,
- z definicji Ri wraca to co zapisal Wi
- sprzecznosc bo z regularnosci wiemy, że zwracamy poprzedni albo wb, a $\to$ mowi ze są rozdzielne, istnieje tylko jeden zapis Wi
- lub
- **b)** istnieą $i,j$, t. że $W^i \to W^j \to R^i$
- to samo sprzecznosc z regularnoscia (wynik to wb lub prev zapis, a "$\to$" mówi, że są rozdzielne)
- $\leftarrow$
- **a)** odczyt nie jest wb z zapisem
- załóżmy nie wprost, że odczytał z innego zapisu niż poprzedniego
- z dobroci wiemy ze wartosc musi pochodzic z jakiegos zapisu
- jeśli ten inny to przyszły to sprzecznośc z *
- wpp sprzeczność z własnością **
- **b)** $R^i$ jest wb z $W^p .. W^q$
- $W^k$ - ostatni zapis nie wb z $R^i$
- pokaŻ prev lub obecny
- załóżmy, że był to $W^x$
- z * wiemy, że $x <= q$ (nie mógł odczytać z przyszłości)
- z wlasnosci 2 wiemy ze $x >= k$ (nie mógł odczytać z jakiegoś który w poprzedza $W^k$)

## Zadanie 6
:::success
Autor: Hubert Obrzut
:::


## Zadanie 7
:::success
Autor: Patryk Mazur
:::


**Lemat 1.**
Wywołanie *read()* zawsze zwraca bit odpowiadający wartości $(0, M-1)$ ustalony przez jakieś wywołanie *write()*

- *$r\_{bit}[0]$* jest początkowo ustawiony na *true*
- *write* ustawia *$r\_{bit}[j]$* na *true* a następnie, dla każdego $i < j$ ustala *$r\_{bit}[i]$* na *false*

**Lemat 2.**
Powyższy rejestr jest regularnym M-wartościowym rejestrem MRSW

Niech $x$ będzie wartością zapisaną przez ostatnie wywołanie *write()*. Po zakończeniu *write()* *$r\_{bit}[x]$* jest ustawiony na *true* oraz *$r\_{bit}[i]$* jest ustawione na *false* dla każdego $i < x$. Jeżeli *read()* zwróci wartość, która nie jest $x$ to (z lematu 1.) musiał natknąć się na jakieś *$r\_{bit}[j]$* ($j \neq x$) ustawiony na *true*. Więc ten bit musiał być ustawiony przez współbieżne wykonanie *write()*, co dowodzi regularności tego rejestru.

## Zadanie 8
:::success
Autor: Joanna Stachowicz
:::


## Zadanie 9
:::success
Autor: Daniel Wiczołek
:::

write idzie po tablicy (od 0 w prawo)
i bierze max timespamp
new_timestamp = max+1
zapisz do tablicy z stamped val z new_timestamp
Każdy thread zapisuje do swojej tablicy czyli na podst swojego id


*
Timestamp zapisany przez wi jest > niz to co odczyta read (bo bierzemy max+1), więc read
nie mógł go odczytać.

**
Znowu: timestamp Wj bedzie wiekszy niz timestamp Wi, a read czyta z max timestamp.
-> ozancza, że są rozdzielne.

\***

read_A -> read_B
write_C -> write_D
Jeśli A zwraca wartość D to B nie zwróci C
(czytli to czym różni się atomic od regular)
- $t_C < t_D$ A czyta D, więc B nie mógł przeczytać mniejszego timestampu, więc nie przeczytał C.
- t_C == t_D wtedy CD wykonały zapis współbierznie A czyta D, B też ten timestamp lub większy, bo C < D, a w pętli idziemy od najmniejszego leksykalno-graficznie do największego, od 0 do max id, więc jeśli
i < j oraz t_i == t_j to read zwróci wartosc j