# Ćwiczenia 2, grupa śr. 10-12, 18 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | | |
Konrad Kowalczyk | | X | X | | X | | | X | |
Jakub Krzyżowski | X | X | X | X | | | | | |
Łukasz Magnuszewski | | | | | | | | | |
Marcin Majchrzyk | X | X | X | X | | | | X | |
Jan Marek | X | X | X | | | | | | |
Michał Mękarski | | | | | | | | | |
Marcin Mierzejewski | | | | | | | | | |
Juan Jose Nieto Ruiz | | | | | | | | | |
Dominik Olejarz | | | | | | | | | |
Konrad Oleksy | X | X | X | X | | | | | |
Javier Rábago Montero | ==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: Javier Rábago Montero
:::

a) Meets mutual exclusion
If we had 2 threads, 1 and 2, the algorithm would do:
write (turn = 1) -> read (busy == false) -> write (busy = true) -> read (turn == 1)
write (turn = 2) -> read (busy == false) -> write (busy = true) -> read (turn == 2)
And we know they are entering critical section, so:
read (turn == 1) -> write (turn = 2)
read (turn == 2) -> write (turn = 1)
which produces this loop:
Write (turn = 1) -> read (turn == 1) -> write2 (turn = 2) -> Read1 (turn == 2) -> write1 (turn = 1)
That turns the contradiction thread 1 came in first and last at the same time, so there is no irreflexivity.

b) Doesn’t meet starvation-freedom
Starvation can occur when for example, thread 1 use lock():
Write (turn = 1) Read (busy == false) Write (busy = true)
After this, if thread 2 wants to go into critical section:
Write (turn = 2) Read (busy == true)
And the will try unlock()
Write (busy = false)
The problem is thread 1 can go again into the lock() loop before thread 2, because there is no mechanism to prevent this, thus starving 2.

c) Doesn’t meet no deadlock
Thread 1 lock()
Write (turn = 1)
Read (busy == false)
Write (busy = true)
Thread 2 lock()
Write (turn = 2)
Read (busy == true)
Thread 1 continuation lock()
Read (turn == 1)
Write (turn = 1)
Read (busy == true)
So it loops, and there is no guarantee that it will end and will call unlock()

(tłumaczenie polskie)
a) Spełnia wzajemne wykluczenie
Gdybyśmy mieli 2 wątki, 1 i 2, algorytm zrobiłby:
write (turn = 1) -> read (busy == false) -> write (busy = true) -> read (turn == 1)
write (turn = 2) -> read (busy == false) -> write (busy = true) -> read (turn == 2)
Wiemy, że wkraczają w sekcję krytyczną, więc:
read (turn == 1) -> write (turn = 2)
read (turn == 2) -> write (turn = 1)
Jeśli połączymy te dwa stwierdzenia, otrzymamy pętlę, której nie da się wykonać w częściowym porządku, więc nie ma tu braku zwrotności.
b) Nie zapewnia wolności od głodu
Głód może wystąpić, gdy na przykład wątek 1 użyje lock():
Write (turn = 1) Read (busy == false) Write (busy = true)
Następnie, jeśli wątek 2 chce przejść do sekcji krytycznej:
Write (turn = 2) Read (busy == true)
I spróbuje unlock()
Write (busy = false)
Problem polega na tym, że wątek 1 może ponownie wejść do pętli lock() przed wątkiem 2, ponieważ nie ma mechanizmu, który mógłby temu zapobiec, co doprowadziłoby do głodu 2.
c) Nie napotyka impasu
Thread 1 lock()
Write (turn = 1)
Read (busy == false)
Write (busy = true)
Thread 2 lock()
Write (turn = 2)
Read (busy == true)
Thread 1 continuation lock()
Read (turn == 1)
Write (turn = 1)
Read (busy == true)
Zatem zapętla się i nie ma gwarancji, że się zakończy i wywoła funkcję unlock()

## Zadanie 2
:::success
Autor:Jan Marek
:::


**a) niezakleszczanie**

**a) niezakleszczanie**

Z wykładu wiadomo, że lock() nie może powodować zakleszczenia, więc w sytuacji, gdy obydwa wątki znajdą się w lock() -> któryś wejdzie do sekcji krytycznej.
Popatrzmy na przypadki, kiedy jeden z wątków lub oba znajdują się w unlock(). Najważniejszą modyfikacją unlock(), jest`while (flag[j] == true {}`.

1. Załóżmy, że wątek 0 jest w unlock(), a wątek 1 w lock(). Z tego wynika, że flag[0]=false, a flag[1]=true. Brak zakleszczenia, ponieważ wątek 1 się nie zapętli i wejdzie do sekcji krytycznej.

BARDZIEJ FORMALNIE:
`write_0(flag[0]=false) -> write_1(flag[1]=true) -> write_1(victim=1) -> read_1(flag[0]==false) -> read_1(victim==1) co oznacza, że (1) wchodzi do CS.`

Przypadek symetryczny - takie samo rozumowanie.

2. Załóżmy, że obydwa wątki znajdują się w unlock(). Wtedy flag[0]=false oraz flag[1]=false, więc w pętli while również nie dojdzie do zakleszczenia.

FORMALNIE:
np.:
`write_0(flag[0]=false) -> write_1(flag[1]=false) -> read_0(flag[1]==false) -> read_1(flag[0]==false)`

Kolejność wykonywania tych operacji może być w niektórych momentach różna, ale i tak nigdy nie dojdzie do zakleszczenia.

A więc alg. spełnia warunek niezakleszczenia.

**b) niezagłodzenie**

Przykład zagłodzenia:

- wątek 0 wyszedł z sekcji krytycznej i siedzi w unlock(). Wówczas flag[0]=false i wątek 0 czeka w pętli while.
- wątek 1 wchodzi do lock(), ustawia flag[1]=true i wchodzi do sekcji krytycznej
- wątek 1 wychodzi z sekcji kryt. i wchodzi do unlock(). Ustawia flag[1]=false i nie zawiesza się na pętli while (ponieważ flag[0]=false)
- wątek 1 z powrotem wchodzi do lock()

I tutaj taki scenariusz się zapętla, a więc w takiej sytuacji wątek 0 zostaje zagłodzony.

## Zadanie 3
:::success
Autor:Konrad Oleksy
:::



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

public void unlock() {
 flag[i] = false; 
}

**własnośc r-ograniczonego czekania:** wątek który wykonał sekcję wejściową wejdzie do sekcji krytcznej przed r-tym wejściem innego wątku do sekcji krytycznej, który wykonał sekcjie wejściową po nim

**sekcja wejściowa**

flag[i] = true; 
victim = i;

**sekcja oczekiwania**

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

### FCFS

$D_A \rightarrow D_B \implies CS_A \rightarrow CS_B$

$write_A(flag[A]=true) \rightarrow write_A(victim=A) \rightarrow(1) write_B(flag[B]=true) \rightarrow \
(2) write_B(victim=B)(3)$

Przynajmniej jeden z wątków możę wejść do CS w jednym z 3 stanów

(1)

$flag[B]==false \implies CS_A -> CS_B$

(2)

$flag[B]==true, victim = A \implies$ nic sie nie dzieje

(3)

$flag[A]==true, victim = B \implies$ nic sie nie dzieje

$flag[B]==true, victim = B \implies CS_A -> CS_B$

## Zadanie 4
:::success
Autor:Jakub Krzyżowski
:::

**Wzajemne wykluczanie:**
Zakładamy, że wątki A i B dostały się do sekcji krytycznej w tym samym momencie i $label[A] < label[B]$
Kiedy B wchodziło do CS, to musiał widzieć $flag[A] == false$ albo $label[A] > label[B]$
Więc B widziało, że $flag[A] == false$

$Write_B(label[B] = max(labels)+1) \rightarrow Read_B(flag[A] == false) \rightarrow$ $\rightarrow Write_A(flag[A] = true) \rightarrow Write_A(label[B] + 1)$
co jest sprzeczne z założeniem, że A ma wcześniejszy label.

**Niezakleszczanie:**
Zawsze istnieje wątek o najniższym label - zawsze zostanie wpuszczony do CS.
Niemożliwe jest, żeby dwa wątki miały taki sam label, bo każdy wątek zostaje oetykietowany najwyższą dotąd etykietą + 1

**Niezagłodzenie:**
Źaden wątek nie zostanie zagłodzony, ponieważ w każdym przypadku nadejdzie moment, że będzie on miał najmniejszą nieobsłużoną etykietę.
Żeby wątek A został zagłodzony przez wątek B, to w czasie gdy A oczekuje na wejście do CS B musiałby wyjść z CS i dostać niższą niż A etykietę.
## Zadanie 5
:::success
Autor: Konrad Kowalczyk
:::

Możemy rozumieć algorytm tree-lock w taki sposób, że po przejściu funkcji `lock()` wątek nie przechodzi od razu do sekcji krytycznej, ale na następny poziom drzewa. Dopiero po przejściu funkcji `lock()` w korzeniu wątek przechodzi do sekcji krytycznej.

<b>Wzajemne wykluczanie - spełnia</b>
Wiemy, że na najniższym poziomie tylko jeden wątek z dwóch zostanie wpuszczony dalej, ponieważ algorytm Petersona spełnia warunek wzajemnego wykluczania. Następnie jeśli założymy, że w dzieciach wierzchołka dalej przeszedł jeden wątek na dziecko, to w rodzicu otrzymujemy dwa wątki (ponieważ jest to drzewo binarne). Skoro w wierzchołku wykonujemy algorytm Petersona i dostajemy dwa wątki, to tylko jeden przechodzi dalej - zatem w rodzicu przejdzie tylko jeden. Dochodząc ostatecznie do korzenia, tylko jeden wątek przejdzie dalej i dostanie się do sekcji krytycznej.

<b>Niezagłodzenie - spełnia</b>
Jeżeli wątek `i` chce wejść do sekcji krytycznej, która obecnie jest zajęta, to będzie musiał poczekać w którymś z wierzchołków, ale ustawi w tym wierzchołku `flag[i]` na `true` oraz `victim` na `i`. Kiedy sekcja krytyczna się zwolni, to `flag[j] == false`. Jeżeli wątek `i` wtedy podejmie działanie, to przejdzie dalej. Jeżeli jakiś inny wątek (niech będzie `j`) go uprzedzi, to wtedy ustawi `flag[j]` na `true`, ale `victim` na `j`. Czyli w pętli `while` będzie `flag[i] == true` oraz `victim == j`, zatem ten nowy wątek nie będzie mógł przejść dalej. Z kolei kiedy wątek `i` podejmie działanie, to co prawda `flag[j] == true`, ale `victim == j`, zatem będzie mógł przejść dalej. To oznacza, że za każdym razem, kiedy zwolni się sekcja krytyczna, wątek `i` przejdzie co najmniej jeden poziom do góry, a zatem przy skończonym $n$ dojdzie do korzenia w skończonej liczbie kroków.

<b>Niezakleszczenie - spełnia</b>
Z pierwszego warunku wiemy, że do każdego wierzchołka dostają się co najwyżej dwa wątki. W każdym wierzchołku wykonujemy algorytm Petersona, w którym nie może dojść do zakleszczenia (ponieważ zmienna `victim` musiałaby przyjmować dwie wartości naraz, co jest niemożliwe). Algorytm tree-lock polega na przechodzeniu przez kolejne wierzchołki, a skoro w żadnym nie może dojść do zakleszczenia, to w całym algorytmie też nie.

## Zadanie 6
:::danger
Autor: do-deklarować
:::

Hint: use `int thread_id[2]`

main thread sets `thread_id[0]` `thread_id[1]` to numbers of threads that will use Peterson lock.

## Zadanie 7
:::success
Autor: Javier Rábago Montero
:::

Mutual exclusion
If two or more threads reach the line “y = i; “ at the same time, as x already has a value, those threads will reach critical section, one through fast pass and the other one through fast pass, so mutual exclusion is not fulfilled.
Starving
If a thread is slower than the rest it could get stuck in line 7, “while (y != -1) {}” so it would starve.
Deadlock
Every time a thread leaves CS it sets y to -1, so if there is a thread waiting it will see it, so there wouldn´t be deadlock.

Wzajemne wykluczenie
Jeśli dwa lub więcej wątków dotrze do linii „y = i; „ jednocześnie, ponieważ x ma już wartość, wątki te dojdą do sekcji krytycznej, więc wzajemne wykluczenie nie zostanie spełnione.
Głodujący
Jeśli wątek jest wolniejszy niż reszta, może utknąć w linii 7, „while (y != -1) {}”, co spowoduje śmierć głodu.
Impas
Za każdym razem, gdy wątek opuszcza CS, ustawia y na -1, więc jeśli wątek czeka, zobaczy go, więc nie będzie impasu.

## Zadanie 8
:::success
Autor: Marcin Majchrzyk
:::

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

a) Aby dwa wątki zwróciły wartość STOP, dwa razy musi być spełnione porównanie ```last == i```.
- jeżeli najpierw jeden z wątków zwróci STOP a następnie drugi wątek zacznie wykonywać funkcję ```visit``` to zwróci wartość RIGHT, ponieważ zmienna goRight będzie równa ```true```
- jeżeli conajmniej dwa wątki wykonują funkcję ```visit``` jednocześnie to ```last``` ma wartość przypisaną tylko przez jeden wątek i tylko jeden zakończy z wartością STOP

b) Aby każdy wątek zwrócił warość DOWN, dla każdego wątku porównanie ```last == i``` musi być fałszywe.
- jeżeli żaden z wątków nie zwrócił RIGHT, to wartość ```last``` jest równa id jednego z wątków. Sprzeczność.
- jeżeli conajmniej jeden z wątków jest przed sprawdzeniem ```goRight```, to musi on zwrócić wartość RIGHT. Sprzeczność.

c) Aby każdy wątek zwrócił wartość RIGHT, każdy wątek musiałby odczytać ze zmiennej ```goRight``` wartość true, co jest niemożliwe, ponieważ zmienna jest zinicjalizowana na false, a jedyne przypisanie znajduje sie po odczytaniu wartości.

## Zadanie 9
:::success
Autor: Javier Rábago Montero
:::
We know that when there’s only one thread in each vertex it stops, and at the beginning there will be n threads in 0.
For vertices 2 and 1, there will be N-1, for 5, 4, and 3 N-2, 6 through 9 N-3…, so we can see we will have one less each diagonal, so the number of vertices will be limited by the number of diagonals, that is Σ1n x, which is an arithmetic progression: [(N+1)⋅N]/2