# Ćwiczenia 13, grupa cz. 14-16, 9. czerwca 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | | |
Mateusz Burdyna | | | | | | | | | |
Dariusz Ciesielski | | | | | | | | | |
Dawid Dudek | X | X | X | X | X | X | X | X | |
Mikołaj Dworszczak | | | | | | | | | |
Przemysław Grochal | X | X | X | X | X | X | | | |
Adam Jarząbek | X | X | | X | X | | | | |
Anna Karykowska | X | X | X | X | X | | | | |
Oleś Kulczewicz | | | | | | | | | |
Pola Marciniak | X | X | X | X | X | X | X | | |
Mikołaj Mroziuk | X | X |==X==| X | X | X | X | X | |
Marcelina Oset | X | X | X | X | | X | | | |
Natalia Piasta | X | X | X | X | X | X | X | | |
Krzysztof Piekarczyk | ==X== | X | X | X | X | X | | | |
Marcin Płaza | X | ==X== | X | X | X | X | X | X | |
Paweł Richert | X | X | X | X | X | X | X | X | |
Rafał Starypan | X | X | X | X | X | | | | |
Dawid Strojek | X | X | X | X | X | | | | |
Mateusz Suszek | X | X | X | X | X | X | X | | |
Wojciech Śniady | X | X | X | X | X | X | X | X | |
Volha Tsekalo | x | x | x | x | x | x | | | |
Yana Vashkevich | x | x | x | x | x | | | | |
Konrad Woźniak | X | X | X | X | X | X | X | X | |
Natalia Czerep | | | | | | | | | |
Joanna Stachowicz | X | X | X | X |==X==| X | X | X | |
:::

Tu można do-deklarować zadanie 7 z listy 12.:
-
-

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

## Zadanie 1
:::success
Autor: Krzysztof Piekarczyk
:::

*Sytuacja wyścigu ma miejsce, kiedy możemy otrzymać różne wartości współdzielonych przez procesy zmiennych w zależności od tego, w jakiej kolejności wykonujemy instrukcje.*

W przypadku tego zadania możemy otrzymać 2 wartości: **1** oraz **2**

Ad **(1)** (będzie to w sytuacji, kiedy będą powtarzane analogiczne instrukcje przez procesory P1 i P2):

$$regP1 \leftarrow counter [counter = 0]\\
regP2 \leftarrow counter [counter = 0]\\
regP1 \leftarrow regP1 + 1 [regP1 = 1]\\
regP2 \leftarrow regP2 + 1 [regP2 = 1]\\
counter \leftarrow regP1 [counter = 1]\\
counter \leftarrow regP2 [counter = 1]$$

Ad **(2)** (sytuacja, gdy najpierw wykonujemy instrukcje dla P1, a potem dla P2)

$$regP1 \leftarrow counter [counter = 0]\\
regP1 \leftarrow regP1 + 1 [regP1 = 1]\\
counter \leftarrow regP1 [counter = 1]\\
regP2 \leftarrow counter [counter = 1]\\
regP2 \leftarrow regP2 + 1 [regP2 = 2]\\
counter \leftarrow regP2 [counter = 2]$$

Więc mamy tutaj sytuację wyścigu.

## Zadanie 2
:::success
Autor: Marcin Płaza
:::

P1 wczytuje c=0
P2 wykonuje petle 49 razy
P1 zapisuje c=1
P2 wczytuje c=1
P1 wykona petle do konca
P2 zapisze c=2

Najmniejsza możliwa wartość zmiennej counter wynosi 2, dzieje się to wtedy, gdy pierwszy proces wczytuje counter o wartości 0, drugi wykonuje pętle, pierwszy zapisuje counter 1, drugi wczytuje 1, pierwszy wykonuje pętle, drugi zapisuje 2.

Największa możliwość zmiennej counter wynosi 100, wtedy gdy pierwszy proces wykonuje całość, a następnie drugi całość.

## Zadanie 3
:::success
Autor: Mikołaj Mroziuk
:::

### warunki
1. **Wzajemne wykluczanie** Jeśli proces $P_i$ działa w swojej sekcji krytycznej, to żaden inny proces nie działa w sekcji krytycznej.
2. **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 odwlekany w nieskończoność.
3. **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.

### uzasadnienie
1. Wzajemne wykluczanie
sekcja krytyczna wątku zostanie uruchomiona dopiero po zakończeniu sekcji w drugim wątku (gdy flaga będzie ustawiona na fałsz)

2. Postęp
jeden wątek oczekujący na wejście do sekcji krytycznej może ustawić swoją flagę na wartość true i zostać wywłaszczony. W międzyczasie drugi wątek może zakończyć działanie w sekcji krytycznej, ustawić flagę na false i ponownie próbować wejść do sekcji krytycznej ustawiając znowu swoją flagę na true. Wówczas dochodzi do sytuacji patowej - obie flagi są ustawione na true

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

## Zadanie 4
:::success
Autor: Adam Jarząbek
:::
Warunek wzajemnego wykluczania:

Warunek ten oznacza, że P0 i P1 nie będą jednocześnie w sekcji krytycznej. Jest on spełniony, poniważ jak wykonuje się P0 to zmienna turn jest ustawiona na 0 i analogicznie jak wykonuje się P1 to zmienna turn jest ustawiona na 1.

Postęp:

Jeśli postęp nie jest spełniony to zachodzi:
flag[0]==true && turn == 1 oraz flag[1] == true && turn == 0
Co jest oczywistym fałszem

Ograniczone czekanie:

Jest spełniony, ponieważ procesy wzajemnie ustawiają turn na id przeciwnika.

## Zadanie 5
:::success
Autor: Joanna Stachowicz



:::

## Zadanie 6
:::success
Autor: Dawid Dudek
:::

## Zadanie 6


void lock(){
    flag[me] = true;
    turn = me
    while(flag[other] && turn == other)
}

Nie ma wzajemnego wykluczenia:

A: flag[A] = true
B: flag[B] = true
A: turn = A
A: wchodzi do sekcji krytyczne
B: turn = B
B: wchodzi do sekcji krytycznej

Deadlock:

nie może wystąpić bo turn jest tylko w jednym stanie na raz

Starvation:

A: flag[A] = true
B: flag[B] = true
B: turn = B
B: sleep
A: turn = A
B: budzi się i widzi, że nie może wejść
A: wchodzi do sekcji krytycznej i będzie do niej już zawsze wchodzić.

## Zadanie 7
:::success
Autor: Natalia Piasta
:::

* Wzajemne wykluczenie
* Podczas wykonywania się sekcji krytycznej procesu (tj. tylko gdy `turn = my_id`), to wtedy nie może w tym samym czasie wykonywać się inny proces. Wynika to z tego, że `turn` zmienia się dopiero w funckji `unlock`.
* Postęp
* Jeżeli będziemy mieć dwa procesy, które czekają na dostęp do sekcji krytycznej, tj. flaga `=true`, to proces aktualny odblokuje na etapie `turn != my_id` wartość flagi, dzięki czemu to ten drugi uzyska dostęp do sekcji krytycznej.
* Ograniczone czekanie
* Jeśli proces P0 znajduje się na etapie `while(turn!my_id);`, tj. nie dostał dostepu, ze względu na ustawienie wartości `false`, to wtedy proces P1 jest wykonywany gdyż w `unlock, turn = 1`. Można więc powiedzieć, że zachowuje dostęp do sekcji krytycznej tylko dla siebie.

## Zadanie 8
:::success
Autor: Konrad Woźniak
:::


boolean TestAndSet (boolean *target)
{
    boolean rv = *target;
    *target = true;
    return rv;
}

void lock(int my_id) 
{
    while (TestAndSet(&lock));
}
void unlock(int my_id) 
{
    lock = false;
}

*TestAndSet to instrukcja atomowa.*

**Warunek postępu** - zachowany

Gdy jeden wątek ustawi lock = false, to oba wątki mogą ponownie wejść

**Warunek ograniczonego czekania** - niezachowany

P1 : lock
P0 : czeka w while (TestAndSet(&lock));
P1 : unlock
P1 : lock

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