# Ćwiczenia 2, grupa cz. 14-16, 17 października 2024

###### tags: `PRW24` `ć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 |
| --------------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Justyna Adamczyk | X | X | X | X | X | | X | X | |
Kalina Białek | X | ==X== | X | X | X | | | | |
Mateusz Budzyński | X | X | X |==X==| X | X | X | X | X |
Karol Burczyk | | | | | | | | | |
Krystian Ćwikliński | X |==X==| X | X | X | X | X | X | X |
Mikołaj Dygoń | X | X |==X==| X | X | X | X | X | X |
Jose Javier Garcia Torrejon | ==X== | X | X | X | X | X | X | X | X |
Mateusz Garncarczyk | X | X | X | | | | | | |
Mikołaj Komarnicki | X | X | X | X | X | X | X | X | |
Beata Łakoma | X | X | X | X | X | | X | | |
Jakub Malczak | X | X | X | X | X | X | ==X== | X | X |
Wiktor Małek | X | X | X | X | ==X== | X | X | X | X |
Piotr Stachowicz | X | X | X | X | X | X | X | X | X |
Dominik Walecko | X | X | X | X | | | X | | |
Natalia Zychowicz | 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: Dominik Walecko
:::

**a. Czy implementuje wzajemne wykluczanie?**
Załóżmy, że dwa wątki dostały się w tym samym momencie do sekcji krytycznej. Wtedy z kodu:
$Write_A(turn=A) \rightarrow Read_A(busy = False) \rightarrow Write_A(busy = True) \rightarrow Read_A(turn = A)$$Write_B(turn=B) \rightarrow Read_B(busy = False) \rightarrow Write_B(busy = True) \rightarrow Read_B(turn = B)$

Możemy też wywnioskować:
$Read_A(turn = A) \rightarrow Write_B(turn = B)$
$Read_B(turn = B) \rightarrow Write_A(turn = A)$

Możemy utworzyć cykl, więc mamy sprzeczność i w algorytmie nie może dojść do sytuacji, w której 2 wątki znajdą się w sekcji krytycznej.

**b. Czy implementuje niezagłodzenie?**
Jeśli wątek $A$ jest bardzo szybki, to może ustawiać *turn = me* zanim wątek $B$ zdąży sprawdzić warunek w zewnętrznej pętli *do while*. Może więc dojść do zagłodzenia.

**c. Czy implementuje niezakleszczenie?**
$Write_A(turn = A)$
$Write_A(busy = True)$
$Write_B(turn = B)$

$Read_A(turn = B)$
$Write_A(turn = A)$
$Read_B(turn = A)$
$Write_B(turn = B)$
$Read_A(turn = B)$
$...$

Może więc dojść do zakleszczenia.

## Zadanie 2
:::success
Autor: Krystian Ćwikliński
:::
Wyglad nowego algorytmu:

public void lock() {
    flag[i] = true;
    victim = i;
    while (flag[j] && victim == i) {};
}
public void unlock() {
    int i = ThreadID.get(); /*returns 0 or 1*/
    flag[i] = false;
    int j = 1 - i;
    while (flag[j] == true) {}
}

**a) Warunek niezakleszczenia - zachodzi**

W algorytmie Petersona blokada lock() nie powoduje zakleszczenia, ponieważ w każdym momencie przynajmniej jeden z wątków może wejść do sekcji krytycznej. W wersji z modyfikacją unlock() wątki, które wychodzą z sekcji krytycznej, opuszczają swoje flagi, co zapobiega zakleszczeniu w pętli while.

Rozpatrzmy przypadki:

1) Jeśli jeden wątek jest w ***unlock()***, a drugi w ***lock()***, wątek w ***lock()*** może wejść do sekcji krytycznej, ponieważ flaga pierwszego wątku jest opuszczona.
2) Jeśli oba wątki są w ***unlock()***, to obie flagi są opuszczone, co uniemożliwia zakleszczenie.
3) Nawet gdy oba wątki są w ***lock()***, zmienna victim zapewnia, że jeden z wątków ostatecznie wejdzie do sekcji krytycznej.

**b) Warunek niezagłodzenia - nie zachodzi**

Przykład głodzenia w algorytmie:

1) Wątek 0 wychodzi z sekcji krytycznej, ustawia flag[0] = false i wchodzi do pętli unlock(), czekając na zakończenie wątku 1.
2) Wątek 1 ustawia flag[1] = true i wchodzi do sekcji krytycznej.
3) Wątek 1 kończy sekcję krytyczną, ustawia flag[1] = false, i natychmiast ponownie ustawia flag[1] = true, wchodząc ponownie do sekcji krytycznej (bo flag[0] = false).
4) Wątek 1 może teraz stale wchodzić i wychodzić z sekcji krytycznej, blokując wątek 0, który stale czeka w pętli unlock()

## Zadanie 3
:::success
Autor: Mikołaj Dygoń


:::

## Zadanie 4
:::success
Autor: Mateusz Budzyński

Etykiety nie muszę być unikatowe, może się tak wydarzyć gdy oba wątki "zarządają" numerków zanim zostanie jednomu z nich przydzielony, wtedy "patrzą" one na ten sam zbiór liczb i przydzielają sobie max(E) + 1 gdzie E to zbiór etykiet. Każdy wątek ma unikatowy Id
zatem jednoznacznie możemy "ustalić", który z naszych wątków jest najmniejszy. Najpierw porównując etykiety, potem porównując ewentualnie Id.

1. Wzajemne wykluczanie
Załóżmy, że dwa wątki (A i B) próbują jednocześnie wejść do sekcji krytycznej. Bez utraty ogólności, załóżmy, że A ma mniejszy numer (mniejszy label). Aby B mógł wejść do sekcji krytycznej, musiałby zauważyć, że A nie jest w stanie gotowości (czyli flaga A musi być false) albo że jego numer (label) jest większy od numeru B. To oznacza, że kiedy B wszedł do sekcji krytycznej, A nie mógł być w stanie gotowości, co jest sprzeczne z założeniem, że A ma mniejszy label. Dlatego tylko jeden wątek może być w sekcji krytycznej na raz. Jeśli oba wątki mają ten sam label, do sekcji krytycznej wejdzie wątek o mniejszym id.

2. Brak zakleszczeń
Zakleszczenie oznaczałoby, że kilka wątków chce wejść do sekcji krytycznej, ale żaden nie może. To oznacza, że wszystkie wątki (który chcą wejść czyli defakto podzbiór wątków) mają ustawione swoje flagi na true i przypisane labele. Jeśli wątki mają takie same labele, to ten o mniejszym id wejdzie do sekcji krytycznej. Jeśli mają różne labele, wejdzie ten z najmniejszym. To oznacza, że zawsze któryś z wątków wejdzie do sekcji krytycznej, co wyklucza możliwość zakleszczenia.

3. Brak zagłodzenia
Zagłodzenie miałoby miejsce, gdyby któryś z wątków czekał na wejście do sekcji krytycznej, ale nigdy nie mógł tam wejść. Jeśli wątek ma podniesioną flagę i przypisany label, a sekcja krytyczna jest wolna (inne wątki nie mają podniesionych flag), to od razu może wejść. Jeśli inne wątki też chcą wejść do sekcji krytycznej, to wejdzie ten najmniejszy w porządku leksykograficznym (label, id), a po jego wyjściu sekcja będzie dostępna dla innych. W ten sposób, każdy wątek w końcu wejdzie do sekcji krytycznej, co wyklucza zagłodzenie. Wątki które będą później dostawały numery zostaną dodane "na koniec kolejki" co gwarantuje nam ,że wątek który był dodany przed nimi wejdzie pierwszy.

:::

## Zadanie 5
:::success
Autor: Wiktor Małek
:::

Algorytm Petersona:

Przykładowe drzewo dla 16 wątków:
*numery w liściach, to numery wątków.*

#### a)
Tak, skoro w każdym węźle drzewa mamy zamek obsługiwany algorytmemt Petersona, to z danego poziomu drzewa na wyższy poziom drzewa(bliżej $CS$) przejdzie tylko połowa wątków, stąd do $CS$ wejdzie tylko jeden wątek.

#### b)
Tak jak w a), skoro każdy zamek obsługuje algorytm Petersona, to każdy zamek jest niegłodzący, więc całe drzewo jest niegłodzące(patrz $unlock()$)

#### c)

Jak poprzednio, na żadnym zamku nie dochodzi do zakleszczenia, więc na całym drzewie również nie dochodzi do zakleszczeń.

## Zadanie 6
:::success
Autor: Piotr Stachowicz

**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.

1. Nie istnieje taka liczba r, ponieważ jeden z wątków w prawym poddrzewie, który jest już wyżej niż w liściu może być bardzo wolny i w tym czasie wątki z lewego poddrzewa mogą cały czas wchodzić na szczyt, tym samym dostając się do sekcji krytycznej.

3. Algorytm wymaga prostej zmiany:

int flags;

public void lock() {
  flags += 1; /* uwaga musi być atomowe */
  victim = getThreadID();
  while (flags == 2 && victim == getThreadID()) {}
}

public void unlock() {
  flags -= 1; /* uwaga musi być atomowe */
}

**Czemu to działa?**
Każdy wątek ma *unikalne id*, więc możemy zastąpić 0 i 1 tymi unikalnymi id. Pojedyncze flagi można zastąpić flags, ponieważ flags == 1 będzie oznaczało, że tylko flaga aktualnego wątku jest podniesiona, natomiast flags == 2 będzie oznaczało, że flaga moja i rywala są podniesione.

:::

## Zadanie 7
:::success
Autor: Jakub Malczak
:::

### a) Wzajemne wykluczanie
$$write_A(x = A) \to read_A(y == -1)$$
$$write_B(x = B) \to read_B(y == -1)$$
$$write_A(y = A)$$
$$write_B(y = B)$$
$$read_A(x \neq A) \to CS_A$$
$$read_B(x == B) \to lock.lock() \to CS_B$$
Zatem wzajemne wykluczanie nie występuje.
### b) Niezagłodzenia
$$write_B(x = B)\to read_B(y == -1)\to write_B(y = B)$$
$$write_A(x = A)\to read_B(y \neq -1)$$
A czeka w while loop.
B wchodzi teraz do sekcji krytycznej. Robi w niej coś. Używa unlock() i znów wchodzi do lock() przechodząc odrazu do sekcji krytycznej.
Zatem dochodzi do zagłodzenia wątku A.
### c) Niezakleszczenie
Załóżmy nie wprost, że doszło do zakleszczenia. Mogło do tego dojść tylko w pętli while. W takim razie zachodzi:
$$read_A(y \neq -1) \to ...$$
$$read_B(y \neq -1) \to ...$$
Ale to oznacza, że któryś z wątków musiał być za pętlą, żeby ustawić y na wartość $\neq -1$. Sprzeczność.

## Zadanie 8
:::success
Autor: Jose Javier Garcia Torrejon
:::success

The statement asks me to determine 3 questions which are these:
At most one thread will receive the value STOP.
At most n-1 threads will receive the value DOWN.
At most n-1 threads will receive the value RIGHT.

So I go one by one

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

At most one thread will receive STOP?
I think so, at most one thread will receive STOP. Let's see why. The variable last
holds the thread ID (i) that has executed the visit() method. The value STOP is
returned only when last is equal to the thread ID that is currently calling the method,
i.e. when last == i.

The important thing is that once a thread sets goRight = true, all threads that call visit() after it will no longer be able to receive STOP because the code will return RIGHT directly when checking if (goRight) and will never hit the last == i condition. This means that only one thread can receive STOP before goRight changes to true.

At most n-1 threads will receive the value DOWN?
Here the analysis changes. No thread will be able to receive the DOWN value because of the way last is immediately updated with the value of i. As I explained before, last will always be equal to i for the thread that is executing visit(), which will cause the if condition (last == i) to always be true and return STOP instead of DOWN.

At most n-1 threads will receive RIGHT?
Yes, this statement is correct. Once goRight is set to true, all threads that call visit() afterwards will receive RIGHT. No thread will be able to receive STOP or DOWN after goRight is set to true, as the code will return RIGHT directly.

## Zadanie 9
:::success
Autor: Natalia Zychowicz
:::
część 1
Podstawa indukcji (nie zawarta na zdjęciu)
l = 0, n wątków

część 2