# Ćwiczenia 6, grupa cz. 12-14, 25. listopada 2021

###### tags: `PRW21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Jacek Bizub | X | X | X | X | X | X | X | X |
Michał Błaszczyk | X | X | X | | | X | | |
Dawid Dudek | X |==X==| X | | | X | X | X |
Mateusz Gil | | | | | | | | |
Wiktor Hamberger | | | | | | | | |
Krzysztof Juszczyk | X | X | X | | | X | X | X |
Kamil Kasprzak | X | X |==X==| X | | X | X | X |
Kacper Kingsford | | | | | | | | |
Kacper Komenda | | | | | | | | |
Aleksandra Kosińska | X | X | | | | X | | |
Łukasz Orawiec | X | | | X | | X | | |
Kamil Puchacz | | | | | | | | |
Paweł Sikora | X | X | | | | X | | |
Michał Sobecki | X | X | X | | | X | X | |
Cezary Stajszczyk | X | X | | | | X | | |
Piotr Stokłosa | X | X | X | | | X | X | |
Cezary Troska | X | X | | | | X | X | X |
Daniel Wiczołek | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Aleksandra Kosińska
:::

:::info
W 32-bitowym systemie komputerowym wszystkie komórki pamięci są atomowymi 32-bitowymi rejestrami MRMW. Chcesz w tym systemie zasymulować programowo 64-bitowy rejestr za pomocą dwóch rejestrów 32-bitowych. W tym celu implementujesz metody read() i write(), które odczytują i zapisują te dwa rejestry po kolei. Czy otrzymany 64-bitowy rejestr jest bezpieczny, regularny, atomowy czy też nie spełnia żadnego z tych warunków?
:::

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 2
:::success
Autor: Dawid Dudek
:::




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.

## Zadanie 3
:::success
Autor: Kamil Kasprzak
:::

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.

## Zadanie 4
:::success
Autor: Łukasz Orawiec
:::


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.

## Zadanie 5
:::success
Autor:Jacek Bizub
:::


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 $$
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 $$

-----------------


## Zadanie 6
:::success
Autor: Paweł Sikora
:::
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.

## Zadanie 7
:::success
Autor: Piotr Stokłosa
:::


## Zadanie 8
:::success
Autor: Krzysztof Juszczyk
:::


public class AtomicMRMWRegister<T> implements Register<T>{
    private StampedValue<T>[] a_table; // array of atomic MRSW registers
    public AtomicMRMWRegister(int capacity, T init) {
        a_table = (StampedValue<T>[]) new StampedValue[capacity];
        StampedValue<T> value = new StampedValue<T>(init);
        for (int j = 0; j < a_table.length; j++) {
            a_table[j] = value;
        }
    }
    public void write(T value) {
        int me = ThreadID.get();
        StampedValue<T> max = StampedValue.MIN_VALUE;
        for (int i = 0; i < a_table.length; i++) {
            max = StampedValue.max(max, a_table[i]);
        }
        a_table[me] = new StampedValue(max.stamp + 1, value);
    }
    public T read() {
        StampedValue<T> max = StampedValue.MIN_VALUE;
        for (int i = 0; i < a_table.length; i++) {
            max = StampedValue.max(max, a_table[i]);
        }
        return max.value;
    }
}

Każdy wątek posiada swój atomowy rejestr MRSW w tablicy `a_table[]`.

Zapis do rejestru `AtomicMRMWRegister` wygląda następująco: wątek znajduje w tablicy `a_table[]` największy znacznik czasu $t$ i w swoim rejestrze `a_table[me]` zapisuje wartość skojarzoną ze znacznikiem czasu `t+1`.

Aby odczytać wartość rejestru `AtomicMRMWRegister` wątek skanuje tablice `a_table[]` i wybiera wartość skojarzoną z najwyższym znacznikiem czasu. Kiedy w `a_table[]` znajduje się kilka wartości skojarzonych z tym samym maksymalnym znacznikiem czasu to wtedy wątek wybiera wartość zapisaną przez wątek o najwyższym id. Czyli kolejności współbieżnych zapisów są wykonywane zgodnie z porządkiem leksykograficznym krotek `(TimeStamp, ThreadID)`.

Pokażmy, że `AtomicMRMWRegister` wykazuje własności (\*), (\*\*), (\*\*\*)

#### (\*)
Nasz algorytm nie zwraca wartości z przyszłości.

#### (\*\*)
Załóżmy, że dla wątków $A,B,C$ następuje `A.write(x)` $\rightarrow$ `B.write(y)` $\rightarrow$ `C.read()`i pokażmy, że $C$ nie może zwrócić $x$.
* Jeśli $A=B$ czyli wykonany zostaje zapis sekwencyjny to $A$ wykona `a_table[A] = x` po czym nadpisze `a_table[A] = y`.
* Wpp. $A \neq B$ to znacznik czasu zapisany przez $A$ jest mniejszy niż znacznik zapisany przez $B$, a $C$ odczyta wartość skojarzoną z największym znacznikiem.

#### (\*\*\*)
Załóżmy, że:
* `A.read()` $\rightarrow$ `B.read()`.
* `C.write(x)` został wykonany w kolejności przed `D.write(y)`.

Pokażmy, że jeśli $A$ zwrócił $y$ to $B$ nie będzie mógł zwrócić wartości $x$.
* Jeśli $t_C < t_D$ to $A$ odczyta i zwróci wartość zapisaną w `a_table[D] = y`. Natomiast $B$ również zwróci wartość `a_table[D]` lub wartość skojarzoną ze znacznikiem $t \geq t_D > t_C$, czyli nie zwróci $x$.
* Wpp. $t_C = t_D$ czyli wątki $C, D$ wykonywały zapis współbieżnie. Ale jeśli $A$ odczyta wartość $y$ to $B$ również odczyta wartość zapisaną w `a_table[D]` skojarzoną ze znacznikiem $t_D$ (lub skojarzoną z większym znacznikiem czasu) nawet jeśli odczytał `a_table[C]` skojarzoną z $t_C$ ponieważ $C<D$.