# Ćwiczenia 2, grupa cz. 16-18, 19 października 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 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | X | X | X | | X | | ==X== | X | |
Paweł Borek | | | | | | | | | |
Arti Brzozowski | | | | | | | | | |
Mateusz Golisz | | | | | | | | | |
Kacper Jóźwiak | | | X | X | X | | X | | |
Julia Konefał | | | | | | | | | |
Adam Korta | X | X | X | X | X | | X | | |
Jakub Mikołajczyk | X | X | X | X | | | | X | |
Bartosz Morasz | X | X | X | | | | X | X | |
Andrzej Morawski | X | X |==X==| X | X | | X | X | |
Aleksandra Nicpoń | X | X | X | X | X | | | X | |
Mateusz Reis | | | | | | | | | |
Tomasz Stachurski | X | X | X | X | X | | X | | |
Marcel Szelwiga | X | X | X | X | X | X | X | X | ==X== |
Volha Tsekalo | x | x | x | ==x== | x | | x | x | |
Martyna Wybraniec | X | X | X | X | X | | | X | |
Denys Zinoviev | | | | | | | | | |
Dominik Olejarz | x | x | x | x | | | | | |
:::

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

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

class Foo implements Lock {
    private int turn;
    private boolean busy = false;
    public void lock() {
        int me = ThreadID.get(); /*get id of my thread*/
        do {
            do {
                turn = me;
            } while (busy);
            busy = true;
        } while (turn != me);
    }
    
    public void unlock() {
        busy = false;
    }
}

a) wzajemne wykluczenie

Założenie (bez straty ogólności): wątek o numerze 1 wchodzi do sekcji krytycznej jako drugi. Pierwszy wszedł ten o numerze 0 (i przebywa nadal w s. kryt.).

Wynika:

$$write_0(busy == true) -> ... -> read_0(turn == 0) -> ... -> write_1(turn = 1) -> ... -> read_1(busy == false) -> ... -> read_1(turn == 1)$. Sprzeczność! (wśród ... nie ma instrukcji ustawiającej $busy = false$)

b) niezagłodzienie
$write_0(turn = 0) -> read_0(busy == false) -> write_0(busy = true) -> read_0(turn == 0) -> CS_0$
$write_1(turn = 1) -> read_1(busy == true)$

0 wątek robi unlock i od razu wchodzi do lock
$write_0(busy = false)$
$write_0(turn = 0) -> read_0(busy == false) -> write_0(busy = true) -> read_0(turn = 0) -> CS_0$

Wątek 1 głoduje

c) niezakleszczenie

$write_0(turn = 0) -> read_0(busy == false) -> write_0(busy = true)$
$write_1(turn = 1) -> read_1(busy == true)$
$read_0(turn == 1) -> write_0(turn = 1) -> read_0(busy == true)$

Następuje zakleszczenie

## Zadanie 2
:::success
Autor: Tomasz Stachurski
:::


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

public void unlock() {
  int i = ThreadID.get(); 
  flag[i] = false;
  int j = 1 - i;
  while (flag[j] == true) {}
}

#### Niezakleszczenie - OK

Z wykładu wiemy, że lock() w algorytmie nie powoduje zakleszczeń, a w tej wersji z unlock() wątek dalej obniża swoją flagę po wyjściu z sekcji krytycznej.

Gdy oba wątki są w lock() również nie dojdzie do zakleszczenie, bo mamy zmienną victim.

Gdy oba wątki są w unlock() również nie dojdzie do zakleszczenia, bo pilnuje tego kod z lini 9 i 11.

#### Niezagłodzenie - NIE OK

Rozważmy przypadek, w którym wątek A właśnie skończył sekcję krytyczną (ustawia flag[A]=false) i czeka w pętli while w wierszu 11 oddając procesor wątkowi B.

Wątek B czeka na wejście do sekcji krytycznej, więc flag[B]=true, a jednocześnie flag[A]=false, bo zostło to ustawione w wierszu 9. Wątek B wchodzi do sekcji krytycznej, wykonuje ją i przechodzi do unlock(). Przechodzi przez nią od razu, bo flag[A]=false.
Może więc ponownie wejść do lock(), ustawić flag[B]=true i wejść do sekcji krytycznej.

Wątek A jest głodzony

## Zadanie 3
:::success
Autor: Andrzej Morawski
:::

Algorytm Petersona:

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

### r-ograniczone czekanie:

Algorytm spełania własność r-ograniczonego czekania jeżeli dla wątków A i B zachodzi:

$D_A^j$ → $D_B^k \Rightarrow CS_A^j$ → $CS_B^{k+r}$

r → ilość przejść sekcji krytycznej przez wątek A zanim B będzie mogło wejść do sekcji krytycznej.

### Sekcja wejściowa:

flag[i] = true;
victim = i;

### Sekcja oczekiwania

while (flag[j] && victim == i) {};

### Algorytm Petersona jest FCFS

Chcemy pokazać, że algorytm Petersone jest FCFS czyli zachodzi:

$D_A^j$ → $D_B^k \Rightarrow CS_A^j$ → $CS_B^{k}$

$L = Write_A(flag[A]=True) \Rightarrow Write_A(victim=A) ^{1} \Rightarrow Write_B(flag[B]=True) ^{2} \Rightarrow Write_B(Victim=B) ^{3} \Rightarrow ...$

$(1)$ Wątek B nie zaczął sekcji wejściowej.

while (flag[B] == False && victim== A) => A wchodzi pierwsze do sekcji krytycznej.

$(2)$
while (flag[B] == True && victim==A) => A czeka

$(3)$
while (falg[B] == True && victim == B) => A wchodzi pierwsze do sekcji krytycznej.

Zatem algorytm jest FCFS
## Zadanie 4
:::success
Autor: Volha Tsekalo
:::
Algorytm spełnia poniższe warunki:
1) Wzajemne wykluczanie
Załóżmy nie wprost, że wątki A i B są jednocześnie w sekcji krytycznej. Bez straty ogólności załóżmy, że A ma mniejszy label.
Kiedy B wszedł do sekcji krytycznej, to zobaczył, że flag(A)==false lub label(A) > label(B).
Z założenia więc mamy, że flag(A)==false.
Mamy:
labeling(B) => read_B(flag(A)==false) => write_A(flag(A)) => labeling(A)
Co jest sprzeczne z założeniem, że A ma mniejszy label.
W przypadku, gdy A i B mają ten sam label, do sekcji krytycznej wejdzie ten wątek, który ma mniejszy numer, czyli w sekcji krytycznej bedzie co najwyżej jeden wątek.
3) Brak zakleszczeń
Załóżmy nie wprost, że doszło do zakleszczenia, tzn kilka wątków chcą wejść do sekcji krytycznej, ale nie mogą. To znaczy, że mają one podniesione flagi i ustawione labele. Jeśli mają one takie same labele, to do sekcji krytycznej wejdzie wątek o najmniejszym numerze. Wpp. wejdzie wątek, który ma najmniejszy label. Sprzeczność.
5) Niezagłodzenie
Załóżmy nie wprost, że doszło do zagłodzenia, tzn któryś z wątków czeka na wejście do sekcji krytycznej, ale nie może tam wejść. To znaczy, że ma on podniesioną flagę i ustawiony label. Jeśli inne wątki nie mają podniesionych flag i sekcja jest wolna, to ten wątek od razu może wejść do sekcji krytycznej. Jeśli są wątki, które też mają podniesione flagi i chcą wejść do sekcji krytycznej, to wejdzie ten o najmniejszym label a potem zwolni sekcję. Z tego wynika, że kiedyś nadejdzie kolej wybranego wątku. Sprzeczność.

## Zadanie 5
:::success
Autor: Adam Korta
:::

### zadanie 5

:::spoiler algorytm Petersona

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

:::

:::spoiler tree_lock

            CS
          /    \
         0      1
        / \    / \
       0   1  0   1
      / \ / \/ \ / \
      A B C DE F G H

:::

:::spoiler a) wzajemne wykluczanie
Jeśli wątek A założy blokadę w liściu, to zostanie "przeniesiony" na następny poziom. Wtedy jeśli wątek B będzie chciał założyć blokadę to zostanie na tym samym poziomie bo
flag[B] == true, flag[A] == true, victim == B. Inne wątki C,D,... mogą również chcieć założyć blokady na swoich liściach. Zauważmy, że tylko połowa z tych wątku przejdzie do następnego poziomu. Kontnuujemy ten proces dla kolejncyh poziomów, aż zostanie nam tylko 1 wątek, które wejdzie do sekcji krytycznej. Skoro każdy node spełnia warunek wzajemnego wykluczania, stąd całe drzewo spełnia ten warunek.
:::

:::spoiler b) niezagłodzenie
Każdy lock Petersona spełnia warunek niezaglodzenia, zatem każdy node jest starvation-free, stąd na każdym poziomie drzewa nie dochodzi do zagłodzenia, czyli każdy wątek kiedyś przejdzie do następnego poziomu, zatem tree_lock spełnia warunek niezagłodzenia.
:::

:::spoiler c) niezakleszczenie
Niech wątek A wejdzie do CSA. Po wyjściu A z CSA wiemy, że metoda **unlock** zwalnia wszystkie zajęte wcześniej zamki przez A, zatem wszystkie wątki, które wcześniej "przegrały" z A wejdą na następny poziom, stąd tree_lock spełnia warunek niezakleszczenia.
:::

## Zadanie 6
:::success
Autor: Marcel Szelwiga
:::
#### Uogólnienie dla algorytmu Petersona

class lock_for_tree_node implements lock{
    private int D;
    /* all threads from left subtree have ID <= D */
    public lock_for_tree_node(int d){
        D = d;
    }
    private int getId() {
        if (ThreadID.get() <= D)    return 0;
        else                        return 1;
    }
    public void lock() {
        i = getId();
        j = 1 - i;
        flag[i] = true;
        victim = i;
        while (flag[j] && victim == i) {};
    }
    public void unlock() {
        i = getId();
        j = 1 - i;
        flag[i] = false;
    }
};

#### Uogólnienie dla $N\neq2^k$
Tworzymy nie pełne drzewo binarne. O możliwie najmniejszej wysokości. Takie drzewo możemy stworzyć, z użyciem standardowych metod.

#### Oszacowanie stałej $r$
> Zadanie ma sens tylko dla odpowiedniego założenia o to czym jest "doorway section", okazało sie, że opacznie je zrozumiałem i poprawnym rozwiązaniem dla tego zadania jest: stwierdzenie, że nie jestnieje odpowiednie oszacowanie stałej $r$ wynikające z tego, że wątek po wygraniu walki w jakimś wierzchołku może nie zgłosić się do walki w rodzicu (sen pomiędzy wywołaniami ```lock()```) proces może wtedy zostać dowolną liczbę razy "zdublowany" .

Obserwacja pierwsza algorytm Petersona w każdym wierzchołku, tak naprawdę (oczywiśclie jeśli chętnych jest dwóch) to przepuszcza na zmianę kandydata z prawego i lewego wierzchołka.

Obserwacja druga gdy wyliczamy stałą $r$ dla określonego procesu to możemy założyć, że zawsze on przegrywa. Policzmy zatem ilu procesom może udać się wepchnąć przed niego.

Nazwijmy proces, dla którego będziemy szacowali stałą $r$ jako $A$.

Niech $T(h)$ -- ile procesów może wepchnąć się przed określony proces po tym gdy $A$ zgłosi swoją chęć do dostępu do sekcji krytycznej, dla drzewa wysokości $h$. Zauważmy, że $T(h) = 2^{(h-1)}$, ponieważ na podstawie obserwacji pierwszej $T(h) = 2 * T(h-1)$ - zakładamy, że nasz proces $A$ wydostał się jako ostatni z poddrzewa, w którym był i tyle samo dostało się z drugiego poddrzewa.

Współcznynnik $r$ możemy określić jako ile razy jakiś proces dostał się do sekcji krytycznej po tym jak proces $A$ zgłosił chęć dostępu do sekcji krytycznej. Zauważmy, że możemy stałą $r$ szacować dla korzenia, wtedy mamy najbardziej pesymistyczny przypadek.

W takim razie na podstawie $T(h)$ wiemy, że nasz proces $A$ wydostanie się po $2^{(h-1)}$ dostępach. Zauważmy, że aż połowę tych dostępów może stanowić jeden określony wątek (pochodzący nie z poddrzewa korzenia, z którego pochodzi $A$). Zatem stała $r$ może być oszacowana przez $\frac{2^{(h-1)}}{2} = 2^{(h-2)}$. A $h=\lceil log_2(\frac{n}{2})\rceil-1$.

#### Założenie, dla którego powyższy tok rozumowania jest poprawny:

public void bigLock(){
    /* Doorway section: */
    /* odszukujemy liść, w którym zaczyna dany wątek */
    tree_node u(ThreadID.get());
    /* Waiting section: */
    u.lock();
    while (u.has_parent()){
        u = u.parent;
        u.lock();
    }
}

Niezbędnym założeniem jest stwierdzenie, że wątek nie zostaje przerwany pomiędzy wywołaniami funkcji ```lock```.

## Zadanie 7
:::success
Autor: Dominik Baziuk
:::

class FastPath implements Lock {
private Lock lock;
private int x, y = -1;
public void lock() {
int i = ThreadID.get();
x = i; // I’m here
while (y != -1) {} // is the lock free?
y = i; // me again?
if (x != i) // Am I still here?
lock.lock(); // slow path
}

public void unlock() {
y = -1;
lock.unlock();
}
}

### a) wzajemnego wykluczania
Przykład że oba wątki są w sekcji krytycznej:

Mamy dwa wątki $A$ i $B$

Niech oba wątki zrobią:
$write_B(x=i) 🠆 read_B(y!=-1)$
$write_A(x=i) 🠆 read_A(y!=-1)$

Przeszły przez pierwszego $while$, ponieważ jeszcze nikt nie nadpisał zmiennej $y$.

Teraz wątek który ostatni nadpisał zmienną $X$ zrobi (powiedzmy, że to był B):

$write_B(y=i)🠆read_B(x != i)🠆CS_B$

A drugi natomiast:
$write_A(y=i)🠆read_A(x == i)🠆 lock.lock()🠆CS_A$

Zatem oba lądują w $CS$.

### b) niezagłodzenia
Przykład zagłodzenia:

Mamy dwa wątki $A$ i $B$

Wątek $B$ robi:
$write_B(x=i) 🠆 read_B(y==-1) 🠆 write_B(y=i)$

Wtedy wątek $A$ czeka w pętli $while$
$read_A(y!=-1)$

Wątek $B$:
- wchodzi do sekcji krytyczne
- robi coś w niej
- robi unlock

i szybko dubluje wątek $A$ przez pętle $while$ głodząc tym samym wątek $A$.

### c) niezakleszczenia
Załóżmy nie wprost, że doszło do zakleszczenia dwóch wątków.
Mogło do tego dojść w pętli while.
Wtedy wiemy, że jakiś wątek musiał nadpisać $y = -1$ na swoje $i$. Ten wątek, który to zrobił nadpisuje $y$ i wchodzi do sekcji krytycznej. Również musiał następnie wyjść z sekcji krytycznej i unlockiem ustawić $y = -1$. Zatem wątki nie są zakleszczone, bo $y$ nie może być równy $-1$, gdy wszystkie wątki czekają.<-Sprzeczność.

## Zadanie 8
:::success
Autor: Martyna Wybraniec
:::


a) Załóżmy nie wprost, że dwa wątki A i B mogą otrzymać wartość zwracaną STOP.
Oznacza to, że:

Write_A(last = A) -> Read_A(goRight == false) -> Write_A(goRight = true) -> Read_A(last == A) -> Write_B(last = B) -> Read_B(goRight == true) - SPRZECZNOŚĆ, wątek B otrzyma wartość RIGHT.

b) Załóżmy nie wprost, że n wątków może otrzymać wartość zwracaną DOWN.

Oznacza to, że każdy wątek musi spełnić last != i. Natomiast aby dojść do tego warunku, każdy z wątków musi wykonać instrukcję last = i. N-ty z kolei wątek, który nadpisał tą zmienną spełni warunek last == i zwróci wartość STOP. SPRZECZNOŚĆ

c) Załóżmy nie wprost, że n wątków możę otrzymać wartość zwracaną RIGHT.

Jest to niemożliwe, ponieważ zmienna goRight jest początkowo równa false. Pierwszy z kolei wątek nie spełni warunku goRight == true i nie zwróci RIGHT. SPRZECZNOŚĆ

## Zadanie 9
:::success
Autor: Marcel Szelwiga
:::

class Bouncer {
    public static final int DOWN = 0;
    public static final int RIGHT = 1;
    public static final int STOP = 2;
    private boolean goRight = false;
    private int last = -1;
    int visit() {
        int i = ThreadID.get();
        last = i;
        if (goRight)
            return RIGHT;
        goRight = true;
        if (last == i)
            return STOP;
        else
            return DOWN;
    }
}

Z danego wierzchołka wątki mają przynajmniej dwa różne "wyjścia". Jak pokazaliśmy w poprzednim zadaniu jedno "wyjście" może być odwiedzone $n-1$ razy.
Obserwacja: jeśli tylko jeden wątek dotyka określonego ```visit()``` to dostanie ```STOP```.
W szczególności jakiś proces na pewno zostanie na pierwszym poziomie. W każdym wierzchołu przynajmniej jeden wątek, albo poprzez otrzymanie ```STOP```, albo poprzez ```goRight```, zostanie na tym samym poziomie. Jest tak ponieważ ```Down``` można dostać maksymalnie $n-1$, a jeśli mamy tylko jeden proces w danym wierzchołku to dostanie on ```STOP```.
Analogicznie na każdym poziomie jeden wątek będzie musiał na nim pozostać.
Zatem proces jest skończony.
Możemy dotrzeć do dowolnego wierzchołka w odelgłości manhattańskiej co najwyżej $n-1$ od źródła.
A zatem mamy $\frac{n\cdot(n+1)}{2}$ odwiedzonych wierzchołków.
Realną liczbę odwiedzonych wierzchołków możemy oszacować przez zależność rekurencyjną $F$:
$F(0) = 0$
$F(1) = 1$ -- jeśli tylko jeden wątek jest w wierzchołku to w nim zakończy.
$F(i) = max_{a+b=i}(F(a)+F(b))+1$
Rozwiązaniem tej zależności rekurencyjnej jest $2\cdot(n-1)$, dowodem jest prosty dowód indukcyjny.