# Ćwiczenia 5, grupa cz. 16-18, 16 listopada 2023

###### tags: `PRW23` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | | X | | X | X | X | X | |
Paweł Borek | X | X | | X | | | | |
Arti Brzozowski | | | | | | | | |
Mateusz Golisz | | | | | | | | |
Kacper Jóźwiak | X | X | X | X | X | X | | |
Julia Konefał | | | | | | | | |
Adam Korta | x | | | x | x | x | | |
Jakub Mikołajczyk | X | X | | X | ==X== | X | X | |
Bartosz Morasz | | | | | | | | |
Andrzej Morawski | x | x | x | x | x | x | | |
Aleksandra Nicpoń | x | | | x | x | x | | |
Mateusz Reis | X | X | X | X | X | | | |
Tomasz Stachurski | x | x | x | x | x | x | ==x== | |
Marcel Szelwiga | X | X | X | X | X | X | X | X |
Volha Tsekalo | x | x | | ==x== | x | x | x | |
Martyna Wybraniec | x | | | x | x | x | x | |
Denys Zinoviev | | | | | | | | |
Dominik Olejarz | x | x | | x | x | x | x | |
:::

Tutaj można zadeklarować zadanie 7 z listy 4:
:::success
| | 4.7 |
| ----------------------:| ----- |
| | |
| | |
| | |
| | |
:::

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

## Zadanie 1
:::success
Autor: Paweł Borek
:::

class IQueue<T> {
	AtomicInteger head = new AtomicInteger(0);
	AtomicInteger tail = new AtomicInteger(0);
	T[] items = (T[]) new Object[Integer.MAX_VALUE];
	
	public void enq(T x) {
		int slot;
		do {
			slot = tail.get();
		} while (!tail.compareAndSet(slot, slot+1));
		items[slot] = x;
	}
	
	public T deq() throws EmptyException {
		T value;
		int slot;
		do {
			slot = head.get();
			value = items[slot];
			if (value == null)
				throw new EmptyException();
		} while (!head.compareAndSet(slot, slot+1));
		return value;
	}
}

Diagram:

compareAndSet(slot, slot+1)         items[slot] = x
     ↓                                          ↓ 
A: [          q.enq(x)                            ]
B:    [ q.enq(y) ]    [ q.deq : EmptyException ]

Historia G(=H):

A q.enq(x)
B q.enq(y)
B q: void
B q.deq()
B q: throws EmptyException
A q: void

Historia S:

  (1)
B q.enq(y)
B q: void
  (2)
B q.deq()
B q: throws EmptyException
  (3)

Nie ważne gdzie ((1), (2) czy (3)) wstawimy

A q.enq(x)
A q: void

to i tak S nie będzie legalną historią, bo nie spełnia sekwencyjnej specyfikacji `IQueue`. Tj. zgłasza wyjątek `EmptyException` w momencie gdy kolejka nie jest pusta. Skoro H nie da się rozszerzyć do G równoważnej z legalną sekwencyjną historią S, to H nie jest linearyzowalna.

## Zadanie 2
:::success
Autor: Dominik Olejarz
:::
a)
int i = tail.getAndIncrement();
wA : |A.enq(x)----------------|
wB : --- |B.enq(y)| |B.deq(y)|
Jeżeli chcielibyśmy zlinearyzować tą względem pierwszej instrukcji metody enq()
otrzymamy nastepującą kolejność:

A: enq(x)
B: enq(y)
B: deq(y)
Ponieważ wątek B jako piewszy przed wątekiem A zapisze swoją zmienną do kolejki to podczas wykontywania metody deq() kolejka zwróci wartość y, ponieważ cały czas komurka x bedzie rowna null.

b)
items[i].set(x);
wA : |------A.enq(x)-------|
wB : -- |B.enq(y)| |B.deq(x)|

Jeżeli chcielibyśmy zlinearyzować tą względem drugiej instrukcji metody enq()
otrzymamy nastepującą kolejność:

B: enq(y)
A: enq(x)
B: deq(x)
Pomimo, że wątek B zapisuje zmienną y do pamięci wcześniej niż wątek A, to index elementu x będzie mniejszy zatem podczas wyciągania elementu z kolejki najpierw zostanie wyciągnięty element x.Zatem jest to sprzeczne. Wedlug linearyzacji kolejnosc elementow powinna byc y x

## Zadanie 3
:::success
Autor: Kacper Jóźwiak
:::
W dowodzie poprawności `HWQueue<T>` przydadzą się następujące obserwacje
wynikające z atomowości metod:

1. `getAndIncrement` gwarantuje, że wartości będą wstawiane do osobnych komórek,
czyli do dowolnej komórki element będzie wstawiony przez co najwyżej jeden
wątek.
2. Podobnie `getAndSet` zapewnia, że każdy element będzie zdjęty przez co
najwyżej jeden wątek.

Dodatkowo wiemy, że wszystkie elementy kolejki znajdują się pod indeksami
od 0 do tail, dlatego metoda `deq` je wyciągnie.

Teza: $\text{enq}(x) \rightarrow \text{enq}(y) \implies \text{deq}(x) \rightarrow \text{deq}(y)$

Dowód: Założmy nie wprost, że $\text{enq}(x) \rightarrow \text{enq}(y)$ oraz $\text{deq}(y) \rightarrow \text{deq}(x)$.

Z pierwszego założenia wynika, że $x$ znajdzie się pod indeksem mniejszym niż
indeks, pod którym jest $y$. Zatem mamy następujący porządek $\text{enq}(x)
\rightarrow \text{enq}(y) \rightarrow \text{deq}(y) \rightarrow \text{deq}(x)$.
W szczególności zachodzi $\text{enq}(x) \rightarrow \text{deq}(y)$

Niemniej wiemy z kodu, że w takim wypadku `deq` trafi w swojej pętli `for` na
element $x$ przed elementem $y$.

Drugim przypadkiem byłaby sytuacja gdy wywołania `enq` na siebie nachodzą, ale tę sytuację rozważyliśmy w zadaniu 2.

## Zadanie 4
:::success
Autor: Volha Tsekalo
:::
Nieczekanie - każda operacja skończy się w skończonej liczbie kroków.

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

Nieblokujące - wstrzymanie jednego procesu (wątku) nie spowoduje wstrzymanie innych.

Niezależne - nie zależą od systemu operacyjnego.

Niezakleszczenie i niezagłodzenie są blokujące, dlatego że zablkowanie jednego wątku może spowodować zablokowanie innych i zależne, bo zależą od tego, czy system operacyjny sprawiedliwie przydziela czas procesora.

Czy współbieżna metoda w nietrywialny
sposób wykorzystująca zamki może być nieczekająca? Nie, bo niektóre wątki nie będą robić progresu.

Metoda weird() jest nieczekająca (wykona się po skończonej liczbie kroków), ale nie jest nieczekająca z limitem kroków, ponieważ 2^i nie jest stałą.

## Zadanie 5
:::success
Autor: Jakub Mikołajczyk
:::

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

Rejest jest bezpieczny, ponieważ w przypadku niewspółbieżnych wywołań zawsze zwraca wartość ostatnio zapisaną.

Rejest nie jest regularny, ponieważ w przypadku wpółbieżnego odczytu i zapisu może zwrócić wartość, która nigdy wcześniej nie została zapisana.

Skoro nie jest regularny to nie jest atomowy.

## Zadanie 6
:::success
Autor: Andrzej Morawski
:::

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

public void unlock() {
    flag[i] = false;
}

Czy algorytm Petersona spełnia warunki wzajemnego wykluczania i niezagłodzenia, gdy dla $flag[0]$ i $flag[1]$ użyjemy rejestrów regularnych?

Rozpatrzmy przypadki:

**1. Zapis do komórek i odczyty są rozłączne**
Algorytm działa tak samo jak dla rejstrów atomowych.

**2. Zapis do komórek i odczyty zachodzą na siebie**

Rozpatrzmy następujące wykonanie metody $lock()$:

$Write_A(flag[A]=True) \rightarrow Write_A(vicitm=A) \rightarrow ...$

Następnie wątek B wywołuje metodę $lock()$ i wykonuje $Write_B(flag[B] = True)$

W tym czasie wątek A odczytuje wartości zmiennych w pętli while. Musimy rozpatrzyć dwa przypadki w których wątek A odczytuje nową i starą wartość zmiennej $flag[B]$

* $flag[B] == False$

Wątek $A$ wchodzi do sekcji krytycznej, natomiast wątek $B$ po ustawieniu zmiennej $victim$ będzie czekał na swoją kolej do wejścia do SK.

* $Flag[B] == True$

W takiej sytuacji do momentu ustawienia przez wątek B zmiennej $victim$ wątek A będzie czekał w pętli. Gdy wątek $B$ wykona $Write_B(victim=B)$ to wątek A będzie mógł wejść do sekcji krytycznej.

## Zadanie 7
:::success
Autor: Tomasz Stachurski
:::


Do przechowywania 1-regularnego SRSW potrzeba 2 M-wartości, z czego pierwsza będzie reprezentować aktualną wartość, a druga poprzednią.
Dodatkowo skorzystamy z dodatkowej zmiennej (np. *which*), która będzie wskazywać, która z tych wartości jest najświeższa.

Mamy zatem 2log(m) + 1, czyli O(log(m)) boolowskich rejestrow.

**read()** - czyta wartość `which` i zwraca `rejestr[which]`
**write()** - czyta wartość `which`, który rejestr jest aktualny i zapisuje nową wartość do starego rejestru. Na końcu neguje `which`

Przypadki:
1. **read() który nie jest współbieżny** - czyta `rejestr[which]`
2. **read() współbieżny z dokładnie 1 write()** - czyta `rejestr[which]`, czyli jeśli write() zdążył zmienić wartość `which` to read() odczyta nową wartość, wpp. starą
3. **read() współbieżny w wieloma write()** - czyta `rejestr[which]`, czyli zwróci dowolną wartość, bo write() ciągle zmienia `which`

## Zadanie 8
:::success
Autor: Marcel Szelwiga
:::
W zadaniu mamy *dobry* rejestr. 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”).

Rejestr regularny to taki, w którym gdy read i write się nakładają to dostajemy wartość nową lub poprzednią (tą sprzed zapisu).

* Własność (1) nie istnieje takie $i$, że $R^i \rightarrow W^i$.

* Własność (2) nie istnieją takie $i$, $j$, że $W^i \rightarrow W^j \rightarrow R^i$.

Chcemy pokazać, że nasz rejestr jest regularny $\Leftrightarrow$ rejestr ma własności (1) i (2);

Dowód przeprowadzimy poprzez pokazanie implikacji w dwie strony:

Rejestr jest regularny $\Rightarrow$ rejestr ma właności (1) i (2).

* (1) Zakładamy nie wprost, że istnieje takie $i$, że $R^i \rightarrow W^i$.
Z definicji $R^i$ zwraca to co zapisal $W^i$, a z regularności mamy, że zwracamy poprzedni lub aktualny, biorąc pod uwagę, że mamy jedno $W^i$ to zachodzi oczywista sprzeczność.

* (2) Zakładamy nie wprost, że istnieje takie $i$, $j$, że $W^i \rightarrow W^j \rightarrow R^i$.
Regularny rejestr zwraca wartość poprzednią lub aktualną jednak skoro $W^j \rightarrow R^i$ to wiemy, że aktualne jest $W^j$, zachodzi więc oczywista sprzeczność.

Dobry rejestr z własnościami (1) i (2) $\Rightarrow$ rejestr regularny.
Rozważmy dwa przypadki:

* Odczyt nie jest współbieżny z żadnym zapisem.
Załóżmy wtedy nie wprost, że odczytał z innego zapisu niż z poprzedniego. Z faktu, że rejestr jest dobry wiemy, że wartość musi pochodzić z jakiegoś zapisu.
Jeśli odczytana pochodzi z przyszłego zapisu to mamy sprzeczność na podstawie (1).
W przeciwnym przypadku mamy sprzeczność na podstawie (2).

* Odczyt $R^i$ jest współbieżny z zapisami $W^a, W^b, \dots W^z$.
Przez $W^A$ oznaczmy ostatni zapis nie współbieżny z $R^i$. Na podstawie (1) wiemy, że zapis nie pochodzi z przyszłości co w połączeniu z faktem, że rejestr jest dobry wiemy, sprawia że odczytana wartość pochodzi z jednego z zapisów $W^a, W^b, \dots W^z$ lub $W^A$ lub zapisu $W^B$ takiego, że $W^B \rightarrow R^i$. Jednak na podstawie (2) wiemy, że opcja odczytu z $W^B$ nie jest możliwa, ponieważ ostatni zapis to $W^A$.