# Ćwiczenia 13, grupa śr. 10-12, 31 maja 2023

###### tags: `SYK23` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk | | | | | | | | | |
Mikołaj Dworszczak | | | | | | | | | |
Kacper Jóźwiak | X | X | X | X | X | X | X | | |
Dominik Kiełbowicz | | | | | | | | | |
Michał Kolasa | | | | | | | | | |
Konrad Kowalczyk | X | X | X | X | X | X | X | | |
Oskar Kropielnicki | X | X | X | X | X | | | | |
Anna Krysta | X | X | X | X | X | X | X | X | X |
Jakub Krzyżowski | X | X | X | X | X | X | | | |
Oskar Kubkowski | X | X | X | X | | | | | |
Mateusz Mazur | X | X | X | X | X | | | | |
Barbara Moczulska | ==X==| X | X | X | X | X | | | |
Kacper Sojda | X | X | X | X | X | X | X | | |
Marta Strzelec | | | | | | | | | |
Mikołaj Swoboda | X | X | X | X | X | X | X | X | X |
Filip Szczepański | X | ==X== | X | X | X | X | | | |
Julian Włodarek | X| X | ==X== | X | X | X | | | |
Beata Łakoma | X | X | X | X | X | X | X | | |
Michał Łukasik | X | X | X | X | X | X | X | | |
:::

Tu można zadeklarować zad 7 z listy 12:
- Anna Krysta
- Oskar Kropielnicki
-

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

## Zadanie 1
:::success
Autor: Barbara Moczulska
:::


**sytuacja wyścigu -** Do takiej sytuacji zachodzi gdy, kiedy kilka wątków jednocześnie modyfikuje jedną zmienną, która do takiej zmiany nie jest przystosowana. W dowolnym czasie algorytm planowania wątków może przełączać się między wątkami, nigdy nie znamy dokładnej kolejności.

1. Jeżeli procesy wykonają się jeden po drugim:
P1_counter = counter (0)
P1_counter += 1 (1)
counter = P1_counter (1)
P2_counter = counter (1)
P2_counter += 1 (2)
counter = P2_counter (2)

2. Jeżeli procesy rozpoczną się równolegle:
P1_counter = counter (0)
P2_counter = counter (0)
P1_counter += 1 (1)
P2_counter += 1 (1)
counter = P1_counter (1)
counter = P2_counter (1)

Jest wyścig

## Zadanie 2
:::success
Autor: Filip Szczepański
:::
temp = counter
temp = temp + 1
counter = temp

Największa wartość zmiennej counter wynosi 100, wtedy gdy procesy wykopnują się po kolei.

Najmniejsza wartość:
* P1, P2 wczytuje c=0
* P2 wykonuje petle 49 razy (c = 49)
* P1 zapisuje c=1
* P2 wczytuje c=1
* P1 wykona petle 49 razy (c = 2)
* P2 zapisze c=2

## Zadanie 3
:::success
Autor: Julian Włodarek
:::
**Wzajemne wykluczanie -** jeśli proces Pi działa w swojej sekcji krytycznej, to żaden inny proces nie działa w sekcji krytycznej.

Sekcja krytyczna wątku zostanie uruchomiona dopiero po zakończeniu sekcji w drugim wątku, czyli gdy flaga będzie ustawiona na *false*.

Dowód nie wprost:
Załóżmy nie wprost, że oba procesy znajdują się w sekcji krytycznej. B.s.o. załóżmy również, że P0 wszedł do niej jako ostatni. Skoro P1 jest już w sekcji krytycznej to wykonał instrukcje flag[1] = true. Aby P0 mógł wejść do sekcji krytycznej to musiał przejść przez linię while(flag[1] == true) więc mamy sprzeczność.

**Postęp -** jeśli żaden proces nie działa w sekcji krytycznej oraz istnieją procesy, które chcą wejść do sekcji krytycznych, wybór nie może być odwlekany w nieskończoność.

Może wystąpić sytuacja, że flagi obu procesów są ustawione na *true* przez co bedą czekać na siebie w nieskończoność.

Kontrprzykład:
P0: flag[0] = true
P1: flag[1] = true
P0: while(flag[1] == true);
P1: while(flag[0] == true);

**Ograniczone czekanie -** musi istnieć wartość graniczna liczby wejść innych procesów do ich sekcji krytycznych po tym, gdy dany proces zgłosił chęć wejścia do swojej sekcji krytycznej i zanim uzyskał na to pozwolenie.

Wątek oczekujący na dostęp do sekcji krytycznej blokuje dostęp drugiemu wątkowi.

Dowód nie wprost:
Załóżmy nie wprost, że b.s.o. proces P0 cały czas wykonuje swoje sekcje krytyczne, a proces P1 cały czas czeka. Skoro P1 czeka, to flag[1] = true. Z tego wynika, że P0 nie może wykonywać swoich sekcji krytycznych, bo nie przejdzie przez funkcję lock. Mamy więc sprzeczność, z czego wynika, że P0 i P1 muszą wykonywać się na zmianę.

## Zadanie 4
:::success
Autor: Michał Łukasik
:::

* Warunek Wzajemnego Wykluczania jest spełniony, mimo iż istnieje sytuacja, gdy obie flagi są ustawione na true, to zmienna turn może przyjąć tylko jedną wartość, czyli wybrać tylko jeden wątek do wejścia do sekcji krytycznej.

Możemy to bardziej formalnie pokazać przez następujące rozumowanie:
Załóżmy, że oba procesy weszły do sekcji krytycznej. Oznacza to, że oba procesy przeszły przez funkcję lock. Skoro P0 przeszedł przez funkcję lock, to flag[0] = true, oraz flag[1] != true lub turn != 1.
Wiemy też, że skoro P1 przeszedł przez funkcję lock, to flag[1] = true, flag[0] != true lub turn != 0.
Czyli flag[0] = true, flag[1] = true, więc aby P0 przeszedł przez lock, to turn = 0, ale skoro P1 też przeszedł przez lock, to turn = 1, czyli sprzeczność.
* Warunek Postępu jest spełniony, ponieważ aby nie był spełniony, musiałoby zachodzić flag[0]==true && turn == 1 oraz flag[1] == true && turn == 0, co jest niemożliwe.
* Warunek Ograniczonego Czekania jest spełniony, ponieważ procesy ustawiają zmienną turn na ID drugiego z nich, czyli czas oczekiwania jest ograniczony przez drugi proces.

## Zadanie 5
:::success
Autor: Beata Łakoma
:::


void lock(int my_id) {
    turn = 1 - my_id;
    flag[my_id] = true;
    while (flag[1 - my_id] == true && turn == 1-my_id);
}

void unlock(int my_id) {
    flag[my_id] = false;
}

Wzajemne wyklucznie: nie spełnione
kontrprzykład:
wartości początkowe: flag[0] = false; flag[1]=false; turn=0;

P0: turn= 1;
P1: turn= 0;
P1: flag[1]=true;
P1: while (flag[0]==true && turn==0) //false, flag[0]=false
P0: flag[0]=true;
P0: while(flag[1]==true && turn ==1) //false, turn=0

Oba procesy, mają false, w tym samym czasie i wchodza do sekcji krytycznej.

Postęp: spełnione
Wartość turn jest jedna czyli jakiś proces zostanie wpuszczony

Ograniczone oczekiwanie: spełnione
Wątek po wpuszczeniu, ustawia turn drugiemu wątkowi
## Zadanie 6
:::success
Autor: Jakub Krzyżowski
:::

void lock(int my_id) {
    flag[my_id] = true;
    turn = my_id;
    while (flag[1 - my_id] && turn == 1 - my_id);
}

**Wzajemne wykluczenie**
turn = 1 - my_id będzie zawsze fałszywe, więc warunek nie będzie zachowany

**Postęp**
Procesy same pozwalają sobie wejść do sekcji krytycznej ustawiając turę na swoją, więc warunek zachowany

**Ograniczone czekanie**
Procesy same ustawiają swoją turę w sekcji wejściowej, co pozwala im od razu wchodzić do sekcji krytycznej, przez co może zajść sytuacja w której kiedy np. P0 czeka na wejście do sekcji krytycznej P1 wejdzie do niej nieograniczoną liczbę razy. Więc warunek nie jest zachowany

## Zadanie 7
:::success
Autor: Konrad Kowalczyk
:::

Warunek wzajemnego wykluczenia:
<b>Jest spełniony.</b>
Aby proces wszedł do sekcji krytycznej, warunek ``while (flag[1 - my_id] == true)`` musi nie być spełniony, tzn. ``flag[1 - my_id] = false``. Możemy jednak zauważyć, że kiedy proces wejdzie do sekcji krytycznej, to jego flaga będzie ustawiona na ``true``, a więc niezależnie od wywłaszczeń nie może nastąpić sytuacja, kiedy jeden z procesów będzie wykonywał sekcję krytyczną, a drugi będzie mógł do niej wejść.

Warunek postępu:
<b>Jest spełniony.</b>
Jeśli oba procesy będą oczekiwać na wejście do sekcji krytycznej, tzn. ``flag[0] = true`` oraz ``flag[1] = true``, to oba procesy będą chciały wykonać instrukcję ``if (turn != my_id)``. Zmienna ``turn`` nie może przyjmować dwóch wartości jednocześnie, a więc tylko jeden z tych procesów przejdzie przez warunek, a następnie ustawi swoją flagę na ``false`` oraz zatrzyma się na pętli ``while (turn != my_id)``. Po powrocie do drugiego procesu ``flag[1 - my_id]`` będzie ustawiona na ``false``, a więc proces ten będzie mógł opuścić pętlę ``while`` i rozpocząć wykonywanie sekcji krytycznej.

Warunek ograniczonego oczekiwania:
<b>Nie jest spełniony.</b>
Przejście do sekcji krytycznej zależy wyłącznie od pętli ``while (flag[1 - my_id] == true)``. Jeżeli ``flag[1 - my_id] = false``, to funkcja ``lock(my_id)`` nie patrzy na zmienną ``turn``. W takim razie jeśli flaga jednego z procesów ustawiona jest na ``false`` (np. nie rozpoczął się wykonywać lub zakończył wykonywanie sekcji krytycznej i wykonał funkcję ``unlock(my_id)``), to drugi z procesów może wejść do sekcji krytycznej. Po zakończeniu wykonywania swojej funkcji krytycznej jednak ten proces znowu może do niej wejść (ponieważ ``flag[1 - my_id]`` dalej jest ustawiona na ``false``), a zatem jeśli dostanie dużo czasu procesora to liczba jego możliwych wykonań przed przejściem z powrotem do pierwszego procesu jest potencjalnie nieograniczona.

## Zadanie 8
:::success
Autor: Anna Krysta
:::


- WARUNEK POSTĘPU: Ten warunek jest spełniony. Każdy proces, który skończył wykonywać kod z sekcji krytycznej będzie odblokowywać lock, czyli ustawiać go na wartość false. Tym sposobem następny proces, który czeka na sekcje krytyczną, będzie mógł do niej wejść.

- WARUNEK OGRANICZONEGO CZEKANIA: Niespełniony. Jeden z procesów może cały czas blokować drugi proces przed wejściem do sekcji krytycznej, tym samym będąc zagładzanym. Kontrprzykład:

P0: lock(0)
P1: zapętlenie w while
P0: unlock(0)
P0: lock(0)
P0: unlock(0)
P0: lock(0)

## Zadanie 9
:::success
Autor: Mikołaj Swoboda
:::

**Wzajemne wykluczanie**
Załóżmy, że $P_1$ i $P_0$ są jednocześnie w sekcji krytycznej i jest to pierwszy taki przypadek w czasie wykonywania programu. To znaczy, że oba przeszły w pewnym momencie przez warunek pętli `while`.
Przypadki:
1. Zamknęły zamek w tym samym momencie - niemożliwe (atomowe TestAndSet).
2. Zostały wpuszczone przez ten sam wychodzący proces (bo wcześniej w SK nie mogło być więcej). Jednak wychodzący proces może wpuścić tylko jeden inny.
3. Jeden zamknął zamek, a drugi został wpuszczony. Jednak proces wychodzący z SK albo otwiera zamek, albo wpuszcza inny proces.

Być może więc jeden proces, np. $P_0$, był w SK, a wtedy wszedł proces $P_1$. Jednak wówczas zamek był cały czas zamknięty oraz nie było możliwości zmiany wartości `waiting[1]`, gdyż żaden proces nie wychodził.

**Postęp**
Proces wychodzący albo otwiera zamek, albo bezpośrednio wpuszcza inny.

**Ograniczone czekanie**
Załóżmy, że $P_0$ czeka na wejście, podczas gdy $P_1$ jest w sekcji krytycznej. Gdy $P_1$ będzie wychodzić, zacznie przeglądać cyklicznie tablicę `waiting`. Jeśli wpuści proces inny niż $P_0$, tamten proces po swoim wyjściu będzie kontynuował przeglądanie w tym samym kierunku, zatem za każdym przepuszczeniem tura $P_0$ przybliża się co najmniej o 1. Stąd w najgorszym wypadku $P_0$ przepuści *n* - 1 procesów.