# Ćwiczenia 2, grupa śr. 12-14, 26 października 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 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Michał Bronowicki | | | | | | | | |
Wiktor Bukowski | X | X |==X==| X | X | X | X | |
Jan Dalecki | X | X | X | X | | | X | X |
Mikołaj Depta | ==X== | X | X | X | X | X | X | |
Kamil Galik | | | | | | | | |
Bartosz Głowacki | X | X | X | X | | X | X |==X==|
Michał Hetnar | x | x | x | x | x | | | |
Adam Jarząbek | X | | X | | | | | |
Michał Kierul | | | | | | | | |
Mateusz Kisiel | x | x | | x | | x | x | |
Maksymilian Komarnicki | X | X | X | X | | | | |
Julia Matuszewska | X | X | X | X | | X | X | |
Andrzej Morawski | X | X | X | | | | X | |
Wojciech Pokój | X | X | X | X | | X | X | |
Marcin Sarnecki | 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 | X | X | X |
:::

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

## Zadanie 1
:::success
Autor: Mikołaj Depta
:::

Poniższy algorytm ma w zamierzeniu implementować interfejs Lock dla dowolnej liczby n wątków. Czy ten algorytm spełnia warunek 1. wzajemnego wykluczania (ang. mutual exclusion), 2. niezagłodzenia (ang. starvation–freedom), 3. niezakleszczenia (ang. deadlock–freedom)? Zmiennymiwspółdzielonymi przez wątki są `turn` i `busy`.

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;
    }
}

## 1. Wzajemne wykluczenie

Założmy, nie wprost, że dwa wątki dostały się do sekcji krytycznej.

Z kodu oznacza to, że zaszły następujące relacje między zdarzeniami:

`Write_B(turn=B) → Read_B(busy==false) → Write_B(busy=true) → Read_B(turn==B)`
`Write_A(turn=A) → Read_A(busy==false) → Write_A(busy=true) → Read_A(turn==A)`

Oraz z fakty, że oba wątki są w sekcji krytycznej, wiemy że:

`Read_B(turn==B) → Write_A(turn=A)`
`Read_A(turn==A) → Write_B(turn=B)`

Wówczas:

`Read_B(turn==B) → Write_A(turn=A)`

`Write_A(turn=A) → Read_A(busy==false) → Write_A(busy=true) → Read_A(turn==A)`

`Read_A(turn==A) → Write_B(turn=B)`

`Write_B(turn=B) → Read_B(busy==false) → Write_B(busy=true) → Read_B(turn==B)`

Mamy cykl co jest sprzeczne z antyzwrotnością relacji `→`.

## 2. niezagłodzenia

Może dojść do zagłodzenia w następującym scenariuszu.

A: 
    lock()
        Write_A(turn=A)
        idzie spać
B:
    lock()
        Write_B(turn=B)
        Read_B(busy==false)
        Write_B(busy=true)
        
        // teraz A może zostać obudzony ale i tak będzie kręcił się w pętli
        
        Read_B(turn==B)
        wykonuje sekcję krytyczną 
    unlock()
        Write_B(busy)
    znowu wykonaj lock() do momentu Write_B(busy=true)

Nie ma żadnego mechanizmu gwarantującego, że wątek `B` w końcu ustąpi `A`.

## 3. niezakleszczenia

A:
    lock()
        Write_A(turn=A) 
        Read_A(busy==false)
        Write_A(busy=true)
        idzie spać
B:
    lock()
        Write_B(turn=B) 
        Read_B(busy==true)
        zapętla się
        idzie spać
A:
    kontunuacja lock()
        Read_A(turn==B)
        wraca do Write_A(turn=A)
        Read_A(busy==true)
        pętli się
Mamy deadlock

Deadlock występuje tutaj ponieważ, wątek oznajmia, że sekcja krytyczna jest zajęta (`busy==true`) przy czym nie ma gwarancji, że faktycznie do niej wejdzie a co za tym idzie, potencjalnie z niej nie wyjdzie i nie wywoła `unlock()`.

## Zadanie 2
:::success
Autor: Marcin Sarnecki
:::

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) {}
}

**Zakleszczenie**
Rozważmy możliwość zakleszczenia w miejscu dodanych linijek. Założmy, że doszło do zakleszczenia. Bez straty ogólności założmy, że wątek 0 jest w funkcji unlock. Wtedy flag[0] = false, zatem wątek 1 nie zakleszczy się w funkcji lock() w linijce 4. W przypadku, w którym oba wątki znajdą się w lock() nie dojdzie do zakleszczenia ze względu na zmienną victim. W przypadku, w którym oba wątki będą w unlock() również nie dojdzie do zakleszczenia ze względu na linijki 9 i 11.

**Głodzenie**
Głodzenie występuje. Rozważmy przypadek w którym wątek 0 właśnie skończył sekcję krytyczną, ustawia flag[0]=false, zaczyna czekać w linijce 11 (wątek 1 czeka na wejście do sekcji krytycznej, więc flag[1]=true) i oddaje procesor wątkowi 1. Wątek 1 wchodzi do sekcji krytycznej, wykona ją i przechodzi do sekcji unlock. Przechodzi przez nią bez problemu, ponieważ flag[0]=false. Może więc wejść ponownie do funkcji *lock*, ustawić swoją flagę na true i wejść do sekcji krytycznej. Wątek 1 może teraz cały czas przechodzić przez unlock() i blokować wątek 0.

## Zadanie 3
:::success
Autor: Wiktor Bukowski
:::

**Właśność r-ograniczonego czekania** oznacza, że wątek, który wykonał sekcję wejściową będzie "wyprzedzony" co najwyżej r razy przez taki wątek, który wykonał tę sekcję po nim.
**Sekcja wejściowa** to część, w której ustawiana jest flaga oraz victim.
**Sekcja oczekiwania** to pętla ```while(flag[j] && victim == i) {};```

Algorytm Petersona:

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.

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

**a) wzajemne wykluczanie**
Dowód indukcyjny, teza:
W danym wierzchołku co najwyżej jeden wątek zajął lock'a.

n=liczba wątków

Dla **n==2**
Dla liści jest to prawdziwe, ze względu na to, że algorytm Petersona działa.

Dla **n>2**
Rozpatrzmy korzeń v.
W dzieciach wierzchołka v co najwyżej jeden wątek dostał lock'a z założenia indukcyjnego. Więc co najwyżej 2 wątki mają dostęp do wierzchołka v. Stąd z działania algorytmu Petersona w wierzchołku też co najwyżej jeden wątek dostał lock'a wierzchołka v.
**b) zakleszczenie**
Dowód indukcyjny, teza:
W danym wierzchołku jeżeli w jego poddrzewie jest wątek chcący uzyskać dostęp do sekcji krytycznej to zajmie lock'a w danym wierchołku.

Dla **n==2**
Dla liści jest to prawdziwe, ze względu na to, że algorytm Petersona działa.

Dla **n>2**
Rozpatrzmy korzeń v.
W dzieciach wierzchołka v wiemy, że jakiś wątek uzyska lock'a z założenia indukcyjnego. Łącząc to z tym, że wiemy, że algorytm Petersena działa, jakiś wątek dostanie lock'a w wierzchołku v.

Stąd jakiś wątek zajmie lock'a w korzeniu. Wiemy, więc, że ten wątek dostanie dostęp do sekcji krytycznej.

**c) zagłodzenie**
Wiedząc, że algorytm Petersona nie zagładza żadnego wątku, wiemy, że żadne poddrzewo wierzchołka nie zostanie zagłodzone. Stąd indukcyjnie

Dla **n==2** nie nastąpi zagłodzenie, ze względu na to, że algorytm Petersona działa.

Dla **n>2**
Korzeń v ma dwoje dzieci, w których żaden wątek nie zostaje zagłodzony, z założenia indukcyjnego. Z tego, że algorytm Petersona działa żadne poddrzewo nie zostanie zagłodzone, więc żaden wątek z obu poddrzew nie zostanie zagłodzony.

## Zadanie 5
:::success
Autor: Michał Hetnar
:::
1.Czy istnieje taka liczba r, być może zależna od n, że
algorytm tree-lock spełnia własność r-ograniczonego
czekania (ang. r-Bounded Waiting)? Jako sekcję wejściową
(ang. doorway section) algorytmu przyjmij fragment kodu
przed pętlą while zamka w odpowiednim liściu.

Jeżeli nie założymy że wątkom przydzielany czas jest równomiernie:

możemy mieć sytułację że wątek który przejdzie doorway section w swoim liściu nie dostanie wiecej czasu procesora, nic nie powstrzyma procesów wyżej od przejścia przed nim nieskończoną liczbę razy.

Możemy założyć że wątkom przydzielany czas jest równomiernie:
w tym przypadku przed 8 wykonały się wszystkie wątki ale 8 i 7 (bo musiała być przed nią ) nie liczymy wiec
R= N-2

2. Pokaż, być może modyfikując nieco oryginalny algorytm, że
założenie o numerach wątków w poprzednim zadaniu może być
łatwo usunięte.

Każdy z zamków traktuje
jeden z rywalizujących o niego wątków jako wątek o numerze 0 a
drugi jako wątek 1.

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

int flags = 0;

 public void lock() {
 flags += 1;
 victim = ThreadID.get();
 while (flags==2 && victim == ThreadID.get()) {};
}
public void unlock() {
 flags -=1;

## Zadanie 6
:::success
Autor: Wojciech Pokój
:::

W dobrze zaprojektowanym programie wielowątkowym
rywalizacja o zamki powinna być niewielka. Najbardziej
praktyczną miarą wydajności algorytmu implementującego zamek
jest więc liczba kroków potrzebna do zajęcia wolnego zamku,
jeśli tylko jeden wątek się o to ubiega. Poniższy kod jest
propozycją uniwersalnego wrappera, który ma przekształcić
dowolny zamek na zamek wykonujący tylko stałą liczbę kroków w
opisanym przypadku. Czy ten algorytm spełnia warunek a)
wzajemnego wykluczania, b) niezagłodzenia, c)
niezakleszczenia? Załóż, że oryginalny zamek spełnia te
warunki.

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();
    }
}

**Wzajemne wykluczenie**

Własność nie jest spełniona

Przykład dla dwóch wątków:

Oba wątki dochodzą do linii 8 jednocześnie.
w tym miejscu x ma już jakąś ustaloną wartość (wskazuje na jeden z wątków), więc jeden wątek zajmnie kłódkę (lock.lock), a drugi wyjdzie z zamka, w efekcie czego oba wątki uzyskają dostęp do sekcji krytycznej

**Niezagłodzenie**

Własność nie jest spełniona i jest już widoczna dla dwóch wątków:

Wystarczy że powolny wątek utknie w linijce 7 w czasie gdy drugi wątek będzie bardzo szybko wchodzić i wychodzić do i z sekcji krytycznej

**Niezakleszczenie**

Własność jest spełniona

Załóżmy nie wprost że któryś z wątków zablokował się na pętli w linii 7,
tj. zmienna y ma wartość różną od -1 ale żaden wątek nie wykonuje sekcji krytycznej. Ale żeby tak było któryś z wątków musiał wcześniej wyjść z sekcji krytycznej więc ustawił y na wartość -1. Sprzeczność

## Zadanie 7
:::success
Autor: Jan Dalecki
:::


$X$ - zbiór wszystkich wątków

**a)**

Załóżmy, że co najmniej 2 wątki otrzymały wartość STOP.

Z kodu:
$$
read_A(last == A) \rightarrow return_A(STOP)
$$
$$
write_A(last = A) \rightarrow read_A(goRight == false) \rightarrow write_A(goRight = true)
$$
$$
write_B(last = B) \rightarrow read_B(goRight == false) \rightarrow write_B(goRight = true)
$$

Założenia:

$$
\forall C \in X\backslash A \ read_A(last == A) \rightarrow write_{C}(last = C)
$$
$$
\forall C \in X\backslash B \ read_B(last == B) \rightarrow write_{C}(last = C)
$$

Z założeń wynika, że procesy nie mogą wykonać zapisau pod `last` dopóki dany proces nie odczyta wartości `last`. Dany proces zmieni wartość `goRight` na `true`.

Zmienna `goRight` nie będzie miała wartości `false` dla drugiego procesu.

**b)**

Załóżmy, że wszystkie wątki otrzymały wartość DOWN.

Z kodu
$$
read_X(last \not= X) \rightarrow return_X(DOWN)
$$

Założenia $\forall A \in X$, $\exists B \in X\backslash A$:
$$
write_A(last = A) \rightarrow write_{B}(last = B) \rightarrow read_A(last \not= A)
$$

staje się jasne, że to nie może zajść dla procesu który jako ostatni wykona podstawienie pod `last`.

c)

Załóżmy, że wszystkie wątki otrzymały wartość RIGHT.

Z kodu:
$$
read_X(goRight == true) \rightarrow return_X(RIGHT)
$$

$$
read_A(goRight == false) \rightarrow write_A(goRight = true) \rightarrow return_A(STOP)
$$
lub
$$
read_A(goRight == false) \rightarrow write_A(goRight = true) \rightarrow return_A(DOWN)
$$

Założenia:
$$
\forall A \in X \ read_A(goRight == true) \rightarrow return_A(RIGHT)
$$
$$
\exists B \in X \ read_B(goRight == false) \rightarrow write_B(goRight = true)
$$
Widzimy, że $B$ nie zwróci RIGHT.

## Zadanie 8
:::success
Autor: Bartosz Głowacki
:::


Wiemy że:
1) w pierwszym wierzchołku na początku znajduje się N wątków
2) w każdym wierzchołku co najwyżej k-1 (gdzie k to liczba wątków w tym wierzchiłku) wątków idzie na prawo to samo dotyczy lewa
3) na każdym poziomie drzewa sumaryczna liczba wątków wynosi maksymalnie N (wynika to z fakty że w każdym kroku wątek schodzi dokładnie poziom w drzewie niżej)
4) gdy w wierzchołku znajduje się 1 wątek dostanie on STOP

### Policzmy więc ile maksymalnie wątków może znaleźć się w każdym wierzchołku

W wierzchołku $0$ znajduje się $N$ wątków
#### Weźmy teraz wierzchołki $2, 5, 9, ...$ (wierzchołki wysunięte maksymalnie w lewo)
Wątki w tych wierzchołkach mogą znaleźć się tam tylko idąc w lewo z wierzchołka wyżej a z **(2)** wiemy że maksymalna liczba wątków będzie w każdym kroku zmniejszać się o jeden mamy zatem
maksymalnie $N-1$ wątków w wierzchołku $2$
maksymalnie $N-2$ wątków w wierzchołku $5$
...

#### Weźmy teraz wierzchołki $1, 3, 6, ...$ (wierzchołki wysunięte maksymalnie w prawo)
Dla nich możemy przeprowadzić analogiczne co wyżej rozumowanie

#### Weźmy teraz wierzchołek 4
mogą do niego wejść wątki z wierzchołków $1$ i $2$
załóżmy że w wierzchołku $1$ mamy $K_1$ wątków a w wierzchołku 2 $K_2$ wątków.

wiemy że $K_1, K_2 \in [0, N-1]$
z **(2)** wiemy że do wierzchołka 4 trafi co najwyżej $max(K_1-1, 0) + max(K_2-1,0)$ wątków
z **(3)** wiemy że $K_1+K_2 \le N$
w takim razie w wierzchołku $4$ znajduje się maksymalnie $N-2$ wątków

#### Rozumowanie indukcyjne
widzimy więc że na $0$ poziomie drzewa wierzchołki mają maksymalnie $N$ wątków
na pierwszym $N-1$ wątków na drugim $N-2$ możemy więc wysnuć hipotezę że na wysokości $k$ drzewa w każdym wierzchołku może znaleźć się maksymalnie $N-k$ wierzchołków

żałóżmy więc że na poziomie $k$ mamy $N-k$ maksymalnie wątków ma wierzchołek i pokażmy że na poziomie $k+1$ mamy maksymalnie $N-k-1$ wątków na wierzchołek

zatem weźmy dowolny wierzchołek $c$ i wierzchołki $a$, $b$ z krótych można przejść do wierzchołka $c$.
Wierzchołki $a$ i $b$ mają odpowiednio $K_a$, $K_b$ wątków

mamy zatem:
wiemy że $K_a, K_b \in [0, N-k]$
z **(2)** wiemy że do wierzchołka $c$ trafi co najwyżej $max(K_a-1, 0) + max(K_b-1,0)$ wątków
z **(3)** wiemy że $K_a+K_b \le N$
w takim razie w wierzchołku $c$ znajduje się maksymalnie $N-k-1$ wątków co dowodzi tezy

#### Konkluzja
wiemy zatem że na poziomie $k$ drzewa wierzchołki mają co najwyżej $N-k$ wątków

można zatem zauważyć że na poziomie $N-1$ drzewa mamy maksymalnie $1$ wątek a z **(4)** wiemy że w takim razie jeśli wątek tam dojdzie dostanie STOP

1) w takim razie każdy wątek dostanie kiedyś STOP ponieważ prędzej czy później natrafi na wierzchołek w którym będzie jedyny lub dostanie STOP wcześniej
2) zatem sumując odpowiednio liczbę wierzchołków z każdego poziomu liczbę wierzchołków można ograniczyć do $1 + 2 + \ldots + N=\frac{N+1}{2} \times N$