# Ćwiczenia 4, grupa śr. 12-14, 16 listopada 2022

###### tags: `PRW22` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Michał Bronowicki | | | | | | |
Wiktor Bukowski | X | X | X | X | X | X |
Jan Dalecki | X | X | ==X== | | X | X |
Mikołaj Depta | | | | | | |
Kamil Galik | X | X | | | X | |
Bartosz Głowacki | | | | | | |
Michał Hetnar | X | X | | | X | X |
Adam Jarząbek | | | | | | |
Michał Kierul | | | | | | |
Mateusz Kisiel | X | X | X | | X | |
Maksymilian Komarnicki | X | X | | | X | X |
Julia Matuszewska | X | X | ==X== | | X | X |
Andrzej Morawski | X | X | | |==X==| X |
Wojciech Pokój | X | X | X | | X | |
Marcin Sarnecki | X | X | X | | X | X |
Bartosz Szczeciński | X | X | X | | X | X |
Tomasz Wołczański | X | X | X | | X | X |
Marcin Wróbel | X | X | X | | X | X |
:::

**Poniżej można zadeklarować zadanie 8 z listy 3:**
- Wiktor Bukowski
- Tomasz Wołczański

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

## Zadanie 1
:::success
Autor: Kamil Galik
:::

class Filter implements Lock {
    int[] level;
    int[] victim;
    public Filter(int n) {
        level = new int[n];
        victim = new int[n]; // use 1..n-1
        for (int i = 0; i < n; i++) {
            level[i] = 0;
        }
    }
    
    public void lock() {
        int me = ThreadID.get(); // returns 0..n-1
        for (int i = 1; i < n; i++) { // attempt to enter level i
            level[me] = i;
            victim[i] = me;
            // spin while conflicts exist
            while (( ∃ k != me) (level[k] >= i && victim[i] == me)) {};
        }
    }
    
    public void unlock() {
        int me = ThreadID.get();
        level[me] = 0;
    }
}

*Fakt:* każdy wątek wykonujący metodę lock() znajduje się na jednym z $n-1$ poziomów, z których ostatni oznacza zajęcie zamka. Na poziomie $n - i$ znajduje się jednocześnie co najwyżej $i$ wątków.

*Uzasadnienie*:
Zrobimy indukcję po poziomach. Na poziomie 0 trywialnie znajduje się n wątków. Załóżmy indukcyjnie, że na poziomie $j - 1$ (dla $j > 0$) znajduje się co najwyżej $n - j + 1$ wątków. Pokażemy, że na poziom $j$ nie przejdzie przynajmniej 1 wątek.

Załóżmy nie wprost, że na poziomie $j$ znajduje się $n - j + 1$ wątków.
Niech $A$ będzie ostatnim wątkiem, który zapisał zmienną victim na poziomie $j$.
Wtedy dla dowolnego wątku $B$ na poziomie $j$: $Write_B(victim[j] = B)\rightarrow Write_A(victim[j] = A)$
Z kodu widzimy, że: $Write_B(level[B] = j)\rightarrow Write_B(victim[j] = B)\rightarrow Write_A(victim[j] = A)\rightarrow Read_A(level[B])$
Wątek $A$ staje się w takim razie ofiarą i nie mógł wejść na poziom $j$, ponieważ dla każdego wątku $B$: $level[B] >= j$ co jest sprzeczne z tym, że A weszło na poziom $j$.

**Wzajemne wykluczanie:** Wątek wchodzi w sekcję krytyczną, gdy znajduje się na (n-1)-szym poziomie. Niech i = 1. Z faktu przytoczonego powyżej wiemy, że na poziomie n-1 znajduje się co najwyżej 1 wątek, czyli zachodzi własność wzajemnego wykluczania.
## Zadanie 2
:::success
Autor: Wojciech Pokój
:::


D-d przez odwróconą indukcję po poziomach

Podstawa indukcji:
Poziom n - 1 posiada tę własność ponieważ jak pokazaliśmy, może tam dotrzeć conajwyżej 1 wątek, więc zagłodzenie na tym poziomie nie występuje

Krok:
Załóżmy nie wprost że A utknął na poziomie i. Z założenie indukcyjnego, po jakimś czasie na wyższych poziomach nie będzie żadnych wątków. Po tym jak A ustawi level[A] = i, wtedy wszystkie wątki oczekujące na niższych poziomach nigdy nie wejdą na poziom i-ty, ponieważ będą zblokowane przez tę wartość.

Ponieważ A będzie jedynym wątkiem który będzie konkurować na poziomie i oraz wyższych więc dostanie w końcu dostęp na poziom wyżej.

Zblokowanie nie nastąpi też gdy 2 wątki A i B utkną na jednym poziomie. Jeden wątek na pewno przejdzie wyżej, ponieważ victim nie może jednocześnie wskazywać na 2 wartości.

Na mocy indukcji algorytm nie posiada własnoci zagłodzenia

Można stąd też wywnioskować że algorytm się nigdy nie zablokuje, ponieważ w końcu zwolnią się poziomy wyżej więc kolejka może zawsze być kontynuowana

## Zadanie 3
:::success
Autor: Julia Matuszewska
:::

class Filter implements Lock  {
    //informacje o poziomie każdego wątku
    int[] level;
    //informacje o wątku który jako ostatni zgłosił chęć zdobycia poziomu
    int[] victim;
    public Filter(int n) {
        level = new int[n];
        victim = new int[n]; // use 1..n-1
        for (int i = 0; i < n; i++) {
            level[i] = 0;
        }
    }
    public void lock() {
        int me = ThreadID.get(); // returns 0..n-1
        for (int i = 1; i < n; i++) { // attempt to enter level i
            level[me] = i;
            victim[i] = me;
            // spin while conflicts exist
            // inny wątek jest na wyższym lub równym poziomie
            // i nasz wątek jako ostatni zgłosił chęć zdobycia poziomu
            while (( ∃ k != me) (level[k] >= i && victim[i] == me)) {};
        }
    }
    public void unlock() {
        int me = ThreadID.get();
        level[me] = 0; //zerujemy poziom wątku
    }
}

:::info
:::

SW - sekcja wejściowa (instrukcje przypisania `level[me]` i `victim[i]`)
Załóżmy, że uruchamiamy algorytm z użyciem 3 wątków

me = ThreadID.get();

---

1. Wątek 1 wchodzi do `lock` i wykonuje SW (`level[me] = 1`, `victim[1] = me`) i zostaje wywłaszczony
2. W wątku 2 to samo co w kroku 1., jest ustawiony jako `victim`, zostaje wywłaszczony
3. W wątku 3 to samo co w kroku 2., jest ustawiony jako `victim`, zostaje wywłaszczony
4. Wątek 2 zostaje kontynuowany, wchodzi na wyższy poziom (`victim[1] = 3`). Warunek czekania w pętli `while` (linijka 21) nie jest spełniony, więc może przejść przez wszystkie następne poziomy, co też mu się udaje i wchodzi do CS. Po wykonaniu znów wykonuje `lock()`. Jest ustawiony jako `victim` i zostaje wywłaszczony.
5. W wątku 3 to samo co w kroku 4.

Może wystąpić sytuacja taka, że kroki 4 i 5 będą powtarzały się dowolną liczbę razy, zwiększając liczbę udanych wejść na wyższy poziom dla wątków 2 i 3, i nie zmieniając dla wątku 1, zatem ta różnica dla wątku 1 i któregoś z wątków 2 i 3 może być dowolnie duża, nie istnieje taka stała $r$, że operacja przejścia na kolejny poziom ma własność $r$-ograniczonego czekania

Niech $LU$ oznacza osiągnięcie nowego poziomu

$D_0^0 \rightarrow D_1^0 \rightarrow D_2^0 \rightarrow LU_1^0 \rightarrow D_1^1 \rightarrow LU_2^0 \rightarrow D_2^1 \rightarrow \dots \rightarrow D_1^r \rightarrow D_2^r \rightarrow LU_1^r \rightarrow LU_0^0$

z czego mamy

$D_0^0 \rightarrow D_1^0$
$LU_1^r \rightarrow LU_0^0$

## Zadanie 4
:::success
Autor: Wiktor Bukowski
:::
### 1.

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

Oznaczmy jako A ten z wątków, który jako pierwszy wykonał sekcję wejściową. Drugi z nich oznaczmy jako B. Załóżmy, że B jako pierwszy wykonał sekcję krytyczną.
$D_A \rightarrow D_B$
$CS_B \rightarrow CS_A$
$D_A \rightarrow W_A \rightarrow CS_A$
$D_B \rightarrow W_B \rightarrow CS_B$
Wtedy z przechodniości $\rightarrow$:
$D_A \rightarrow D_B \rightarrow CS_B \rightarrow CS_A$

Jeśli B jako drugi wykonał sekcję wejściową, to ustawił zmienną `victim` na samego siebie, przez co musiał potem czekać w sekcji oczekiwania do wykonania przez A sekcji krytycznej i zmiany jego flagi. W związku z tym B nie mógł wykonać sekcji krytycznej przed A.

### 2.
Ustalmy, że wątek A jako pierwszy wykonał ustawienie flagi. Natomiast niech wątek B jako pierwszy wykona ustawienie zmiennej `victim`. Następnie wątek A nadpisze tę zmienną, dzięki czemu B będzie mógł wejść do sekcji krytycznej.

### 3.

#### a)
Oba wątki odczytają to samo niezależnie od kolejności, a więc nie ma możliwości rozróżnienia, który tak naprawdę wykonał tę instrukcję szybciej.

### b)
Jeśli oba zapisy nastąpią jeden po drugim, a dopiero potem oba wątki przejdą do kolejnych instrukcji, to nie do rozróżnienia będzie, który wątek jako pierwszy zapisał do swojej komórki.

### c)
Gdy drugi wątek nadpisze wspólną komórkę, stan zamka będzie nierozróżnialny ze stanem, w którym pierwszy wątek w ogóle nie próbował zdobyć blokady. W związku z tym wątek drugi może cały czas wykonywać instrukcje i dostać się do sekcji krytycznej.

## Zadanie 5
:::success
Autor: Mateusz Kisiel
:::


Sekwencyjny porządek:

r.write(1)
r.read(1)
r.write(2)
r.read(2)

Sekwencyjny porządek:

r.write(2)
r.write(1)
r.read(1)
r.read(1)

Po wykonaniu jako pierwsze `p.enq(x)` nie może zostać zwrócone y z `p.deq()`


## Zadanie 6
:::success
Autor: Marcin Wróbel
:::


### Diagram 1
Historia H

B r.write(1) 
A r.read()
C r.write(2)
A r: 1
C r: void
B r: void
B r.read()
B r: 2

Legalna sekwencyjna historia S

B r.write(1)
B r: void
A r.read()
A r: 1
C r.write(2)
C r: void
B r.read()
B r: 2

$\rightarrow_H=$
$\{r.read(1) \rightarrow r.read(2)$
$r.write(1) \rightarrow r.read(2)$
$r.write(2) \rightarrow r.read(2)\}$

$\rightarrow_S=$
$\{r.write(1) \rightarrow r.read(1)$
$r.read(1) \rightarrow r.write(2)$
$r.write(2) \rightarrow r.read(2)\}$

### Diagram 2
Historia H

B r.write(1)
A r.read()
C r.write(2)
A r: 1
C r: void
B r: void
B r.read()
B r: 1

Legalna sekwencyjna historia S

C r.write(2)
C r: void
B r.write(1)
B r: void
A r.read()
A r: 1
B r.read()
B r: 1

$\rightarrow_H=$
$\{p.read(1) \rightarrow r.read(1)$
$p.write(1) \rightarrow r.read(1)$
$p.write(2) \rightarrow r.read(1)\}$

$\rightarrow_S=$
$\{r.write(2) \rightarrow r.write(1)$
$r.write(1) \rightarrow r.read(1)$
$r.read(1) \rightarrow r.read(1)\}$

### Diagram 3

Historia H

A p.enq(x)
A p: void
B p.enq(y)
B p: void
A p.deq()
A p: y

Historia H nie odpowiada żadnej legalnej sekwencyjnej historii S, ponieważ
mamy $p.enq(x) \rightarrow p.enq(y) \rightarrow p.deq(y)$
Po wykonaniu $p.enq(y)$ kolejka będzie zawierać x jako pierwszy element, więc p.deq() zwróci x, a nie y.

$\rightarrow_H=$
$\{p.enq(x) \rightarrow p.enq(y)$
$p.enq(y) \rightarrow p.deq(y)\}$
### Diagram 4

Historia H

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

Historia H nie odpowiada żadnej legalnej sekwencyjnej historii S, ponieważ
mamy $p.enq(x) \rightarrow p.enq(y) \rightarrow p.deq(y)$
Po wykonaniu $p.enq(y)$ kolejka będzie zawierać x jako pierwszy element, więc p.deq() zwróci x, a nie y.

$\rightarrow_H=$
$\{p.enq(x) \rightarrow q.enq(y)$
$q.enq(y) \rightarrow q.enq(x)$
$q.enq(x) \rightarrow p.enq(y)$
$p.enq(y) \rightarrow p.deq(y)$
$p.deq(y) \rightarrow q.deq(x)\}$