# Ćwiczenia 2, grupa śr. 16-18, 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | x | x | x | x | x | | | |
Marcin Dąbrowski | | | | | | | | |
Jakub Gałecki | | | | | | | | |
Kamila Goszcz | X | X | | X | | X | X | |
Wiktor Hamberger | X | X | ==X== | | | | | |
Jan Jankowicz | X | X | X | | | | | |
Mikołaj Jaszcza | x | x | x | x | | x | x | |
Zuzanna Kania | | X | X | | | | | |
Wiktoria Kuna | | | | | | | | |
Patryk Mazur | X | X | X | | | | | |
Hubert Obrzut | X | X | X | X | X | X | X |==X==|
Magdalena Rzepka | ==X== | X | X | X | X | X | X | X |
Joanna Stachowicz | X | | X | | | | | |
Rafał Starypan | | | | | | | | |
Maria Szlasa | X | X | X | X | X | X | ==X== | X |
Daniel Wiczołek | 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: Magdalena Rzepka
:::


**a)wzajemne wykluczanie - spełnia**

Załóżmy, że mamy dwa wątki o id 1 i 2, które mogą przejść razem do sekcji krytycznej.

**Wiemy, że:**
W~1~(turn = 1) -> R~1~(busy == false) -> W~1~(busy == true) -> R~1~(turn == 1)
(analogicznie dla wątku 2):

**Z tego wynika, że:**
R~1~(turn == 1) -> W~2~(turn = 2) -> R~2~(turn == 2) -> W~1~(turn = 1) -> R~1~(turn == 1)

R~1~ -> R~1~ co jest sprzecznością.

Poprawne sprawdzenie czy jest nasza kolej musi nastąpić zanim inny wątek nam go nadpisze.
Nadpisanie wątka musi nastąpić przed sprawdzeniem czy ciągle jest nadpisany.
Z kolei sprawdzenie czy ciągle jest nasza kolej musi nastąpić przed tym jak inny wątek nam go nadpisze.
A to musi być przed sprawdzeniem czy to nasza kolej.

Zrobiliśmy pętelkę i doszliśmy do sprzeczności.
Musi zachodzić wzajemne wykluczanie.

**b)niezagłodzenie - nie spełnia**

Wystarczy pokazać na jednym przykładzie, że może dojść do zagłodzenia.

W~1~(turn = 1)
R~1~(busy != true)
W~1~(busy = true)
i wychodzi z pętli

W~2~(turn = 2)
R~2~(busy = true) - zawiesza się

W~1~(busy = false) - robi unlock()
Wątek 1 od razu wchodzi do funkcji lock(), ustawia turn = 1 i idze dalej zablokować busy = true.
Wątek 2 jest wolniejszy i zanim się zorientował znowu został zamknięty w pętli.
Wątek 2 jest wątkiem głodzonym.

**c)niezakleszczenie - nie spełnia**

Wątek 1 ustawia turn = 1 i busy = true.
Wątek 2 ustawia turn = 2 i zapętla się bo busy = true.
Wątek 1 sprawdza while ale turn != 1.
Wraca więc i ustawia turn = 1.
Wątek 1 również się zapętla bo busy = true.

## Zadanie 2
:::success
Autor: Patryk Mazur
:::

### Niezakleszczenie
Wiemy, że `lock()` w algorytmie Petersona nie może powodować zakleszczenia, ponieważ w tej wersji `unlock()` wątek, który wyszedł z sekcji krytycznej nadal obniża swoją flagę. Oba wątki, które przejdą do `unlock()`, opuszczają swoją flagę, przez co niemożliwe jest zakleszczenie w tym while'u

### Niezagłodzenie

W tej wersji algorytmu moze dojść do zagłodzenia

Watek `A` może zablokować się w `unlock()` i przesypiać momenty gdy `flag[B]=false`. Wątek `B` będzie mógł wchodzić do sekcji krytycznej z tytułu `flag[A]=false`.

## Zadanie 3
:::success
Autor: Wiktor Hamberger
:::
:::info
**Zadanie 3.** Przypomnij, co to znaczy że algorytm ma własność r-ograniczonego czekania (ang. r-Bounded Waiting). Czym są sekcja wejściowa (ang. doorway section) i sekcja oczekiwania (ang. waiting section) w algorytmie Petersena? Pokaż, że ten algorytm ma własność 0-ograniczonego czekania, tzn, że jest FCFS (First Come First Served).
:::
1. Przypomnij, co to znaczy że algorytm ma własność r-ograniczonego czekania (ang. r-Bounded Waiting).

2. Czym są sekcja wejściowa (ang. doorway section) [zielony] i sekcja oczekiwania (ang. waiting section) [czerwony] w algorytmie Petersena?
3. Pokaż, że ten algorytm ma własność 0-ograniczonego czekania, tzn, że jest FCFS (First Come First Served).
Należy udowodnić że:
$$
D^k_A \to D^j_B \Rightarrow CS^k_A \to CS^j_B
$$
rozpiszmy lewą stronę implikacji:
$$
write_A(flag[A]=true)\to write_A(victim=A) \to^{1.} write_B(flag[B]=true) \to^{2.} write_B(victim=B)^{3.}
$$
Dla warunku w $W_A$ i $W_B$ istnieją 3 momenty w czasie, w takcie których wątek/wątki mogą się chcieć dostać do $CS$ oznaczone powyżej jako $1.$, $2.$ i $3.$. Rozpiszmy sobie możliwości stnanów sarunków w sekcjach wejściowych:
1. $flag[B]==false \Rightarrow CS_A \to CS_B$
2. $flag[B]==true, victim==A \Rightarrow nic\quad się\quad nie\quad dzieje$
3. $flag[B]==true, flag[A]==true, victim==B \Rightarrow CS_A \to CS_B$

C.b.d.U.

## Zadanie 4
:::success
Autor: Daniel Boguszewski
:::

Algorytm można zwizualizować jako pełne drzewo binarne o n/2 liściach, przy czym od każdego z liści wychodzą dodatkowe dwa 'węzły', będące wątkami, na których wykonuje się program (razem n wątków). Aby dany wątek przeszedł do sekcji krytycznej programu, musi przejść całą drogę od liścia do korzenia tego drzewa, przy czym każdy z węzłów jest zamkiem działającym w algorytmie Petersona. Można powiedzieć, że w każdym z węzłów znajduje się sekcja krytyczna, do której o dostęp spierają się jego dzieci. Faktyczna sekcja krytyczna programu znajduje się w korzeniu, reszta węzłów służy jako kolejka dla wątków, które próbują się dostać do sekcji krytycznej. Aby się do niej dostać, wątek musi zostać dopuszczony do każdego węzła na swojej ścieżce. Wątki traktowane są jako 0 lub 1, w zależności od tego, czy są lewym czy prawym dzieckiem danego węzła. Ma to następujące konsekwencje:

Algorytm posiada własność wzajemnego wykluczania:
Załóżmy, że Ai wykonuje SC, zatem zamek na każdym węźle ścieżki przez którą przechodził przepuścił Ai. Oznacza to, że flag[i] = true i żaden inny wątek nie przejdzie przez jego sekcje oczekiwania (flag[0] oraz flag[1] będą równe true). Tym samym sekcję krytyczną wykonuje maksymalnie jeden wątek.

Algorytm posiada własność niezagłodzenia:
Załóżmy, że Ai próbuje się dostać do SC, ale tę wykonuje aktualnie inny wątek (flag[i] = flag[j] = true, victim = i). Oznacza to, że na ścieżce do SC zostanie zatrzymany na jednym z węzłów. Ten węzeł zostanie wreszcie zwolniony, wówczas flag[j] = false. Jeśli wątek wznowi działanie, nim do sekcji dostępu dotrze inny wątek, zostanie przepuszczony węzeł wyżej. W innym wypadku pewien wątek Aj zastąpi wartości na flag[j] = true oraz victim = j. Ze względu na wartość zmiennej victim, nie zostanie dopuszczony dalej przed wątkiem Ai. Wobec tego wątek Ai będzie posuwać się po pewnym skończonym czasie coraz wyżej, aż wreszcie dotrze do SC.

Algorytym posiada własność niezakleszczenia:
W dowolnym z węzłów, jeśli 2 wątki domagają się przejścia do SC, uda się to tylko jednemu. Załóżmy, że wątek Ai oraz Aj próbują przejść przez zamek. Wówczas w czasie wykonywaniu sekcji dostępu oba z nich będą musiały nadać wartość zmiennej victim, ta jednak może posiadać tylko jedną wartość. Niedopuszczony zostanie wątek, który nie przydzielił victim swojej wartości, drugi wątek przejdzie dalej, a przepływ pozostanie niezaburzony. Ponieważ na drodze jest skończona liczba wątków, w końcu dotrze do sekcji krytycznej.

## Zadanie 5
:::success
Autor: Daniel Wiczołek
:::

1.

Nie ma ograniczenia bo unlock moze byc wolny i to główne prawe poddrzewo może być wielokrotnie
wykorzystane. (bez strat na ogólności patrzę na skrajnie lewe)
L1 - wątek w lewym liściu
L2 - drugi z lewego
P1, P2 - analogicznie prawy

L1: próbuje wejść do CS
L2: robi unlock w root ale powoli
P2: nie probuje wejsc do CS
P1: wchodzi $n$ razy
wniosek: P1 może wejść dowolną liczbę razy zanim L2 oblokuje liść z L1

2. Do każdego dochodzą 2 więc wystarczy pamiętać, z którego poddrzewa przychodzimy

## Zadanie 6
:::success
Autor: Mikołaj Jaszcza
:::

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.


a) **wzajemne wykluczenie**
**NIE**

Rozważmy sytuację dla 2 wątków. Niech oba wejdą do linijki $$while (y != -1) {} $$ w tym samym momencie. Zauważmy, że wtedy zmienna x ma nadaną jakąś wartość inną niż -1 (bo oba wątki przeszły przez linijkę $$ x = i; $$, a jest to jedyna linijka zmieniająca początkową wartość zmiennej x (bo rozważamy aktualnie tylko lock, ponieważ interesuje nas nielegalne wejście do sekcji krytycznej)). Zatem (BSO) niech x = 0. Wtedy jeden wątek spełni warunek (x != i) i wejdzie do funkcji lock.lock(), a drugi wejdzie bezpośrednio do sekcji krytycznej. Zatem oba jednocześnie mogą znaleźć się w sekcji krytycznej.

b) **niezagłodzenie**
**NIE**

Własność również nie jest spełniona. Niech jeden z dwóch wątków wejdzie do linijki $$ while (y != -1) {} $$ i będzie działał w sposób bardzo wolny. Wtedy drugi wątek może wchodzić i wychodzić nieprzerwanie do sekcji krytycznej. Tj mamy kolejność:

-> wątek 1 wywołuje lock
-> wątek 1 wchodzi do sekcji krytycznej
-> wątek 2 wywołuje lock
-> wątek 2 zatrzymuje się w linijce while (y != -1) {}
-> wątkowi 2 odebrany zostaje procesor
-> wątek 1 wychodzi z sekcji krytycznej i ustawia y := -1

W dalszej części:
-> wątek 1 wywołuje lock
-> wątek 1 wchodzi do sekcji krytycznej
-> wątek 2 dostaje z powrotem procesor, ale nie może wejść do sekcji krytycznej
-> wątek 2 czeka, i zostaje mu odebrany procesor
-> wątek 1 wychodzi
-> powyższe kroki można powtarzać nieskończenie wiele razy, więc wątek 2 może zostać zagłodzony

c) **niezakleszczenie**
**TAK**

Nie wprost. Jeżeli zaszłoby zakleszczenie, to wątki musiałyby się zakleszczyć w 'lock' (oba wątku musiałyby być w 'lock', bo 'unlock' nie zależy od żadnej współdzielonej zmiennej). Zauważmy również, że zakleszczenie musiałoby nastąpić w linijce while (y != -1) {}, bo oprócz tego jedyne miejsce gdzie korzystamy ze współdzielonych zmiennych to 'lock.lock()', ale o tej funkcji wiemy, że nie może zostać zakleszczona, bo wszystkie współdzielone zmienne są dostępne tylko wewnątrz niej. Tzn - nie ingerujemy bezpośrednio w ciele FastPath.lock w ich wartości, czyli zależności między nimi zawsze są poprawne, bo wiemy, że klasyczny 'lock' działa. Jednak jeśli zakleszczenie nastąpiło w linijce while (y != -1) {} to wartość y (różna od -1) musiała zostać ustawiona przez pewien wątek który aktualnie jest w sekcji krytycznej w linijce y = i. Ale wtedy nie mielibyśmy do czynienia z zakleszczeniem, bo po jego wyjściu z sekcji krytycznej wartość y będzie równa -1, więc kolejny wątek (lub wątki) będą miały dostęp do sekcji krytycznej. CKD

## Zadanie 7
:::success
Autor: Kamila Goszcz
:::


**a) Co najwyżej jeden wątek może zwrócić STOP**

Załóżmy, że jakieś 2 lub więcej wątków się przebiło przez

if(goRight)
    return RIGHT;

(Gdyby się przebił tylko jeden, to pozostałe zwróciłyby RIGHT, więc aby miały jakąkolwiek szansę coś innego zwrócić niż RIGHT musiały przejść przez tego ifa)
i są na etapie:

goRight = true;
if(last == i) 
    return STOP;

last jest wspólne i może mieć tylko jedną wartość, zatem tylko jeden wątek zwróci STOP

**b) co najwyżej n-1 wątków otrzyma wartość DOWN**
Spróbujmy to zepsuć.
Niech n wątków się przebije przez ifa i będzie na tym etapie:

goRight = true;
if(last == i) 
    return STOP;
else 
    return DOWN;

wiemy, że last wskazuje na któreś i, zatem przynajmniej jeden wątek wejdzie w `return STOP`

**c) Co najwyżej n-1 wątków otrzyma wartość RIGHT**
Aby jakis wątek wszedł w ifa

if(goRight)
    return RIGHT;
goRight = true;

to pierwsze goRight musi być równe true.
Jednak, aby ustawić goRight na true, przynajmniej jeden wątek musiał nie wejść w ifa.

## Zadanie 8
:::success
Autor: Maria Szlasa
:::
:::info
:::
Zauważmy, że kiedy zostanie 1 wątek to dostanie on wartość STOP.

Policzmy, ile maksymalnie wątków będzie w każdym wierzchołku.
* W wierzchołku 0 będzie N wątków. - początek algorytmu.
* W wierzchołkach skrajnie lewych (2,5,9...) można się znaleźć idąc ciągle w lewo. Z zadania 7, wiemy, że w każdnym wywołaniu algorytmu w lewo może iść max n-1 wątków. Dlatego w wierzchołku 2 będzie ich N-1, w 5 N-2...,
* Analogicznie do poprzedniego podpunktu w skrajnie prawych wierzchołkach (1,3,6) ich ilość będzie się zmiejszała o 1.
* Do wierzchołka 4, możemy dojść z wierzchołka 1 lub 2. Załóżmy, że w wierzchołku 1 mamy k1 wątków i w dół poszło k1-1, a w wierzchołku 2 było ich k2 i poszły one w prawo k2-1, więc na 4 mamy max(k1-1,0) + max(k2-1,0) wątków. Ponieważ k1+k2<=N, w 4 mamy N-2 wątki.

Możemy zauważyć, że w każdej przekątnej maksymalna ilość wątków będzie o 1 mniejsza od ich ilości na poprzedniej przekątnej.

Możemy zauważyć, że w każdej przekątnej maksymalna ilość wątków będzie o 1 mniejsza od ich ilości na poprzedniej przekątnej.
Można to udowodnić przeprowadzając analogiczne rozwiązanie co w przypadku wierzchołka nr 4.

***

Ponieważ w każdej przekątnej zmniejsza się ich ilość o 1, to dojdziemy do momentu, aż na przekątnej będzie ich 0, zatem każdy wątek otrzyma numer (wynik STOP).

Stąd można też wywnioskować, że kształt będzie wyglądał tak jak na obrazku, a liczbę wierzchołków możemy ograniczyć przez ilość przekątnych $1 + 2 + 3 + ... + N = \frac{(N+1)\cdot N}{2}$