# Ćwiczenia 14, grupa cz. 10-12, 13 czerwca 2024

###### tags: `SYK24` `ć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!**
**UWAGA: Wszystkie zadania są bonusowe.**

:::success
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ---| ---| ---| ---| ---| ---| ---| ---| ---|
Borys Adamiak | | | | | | | | | |
Michał Chawar | | | | | | | | | |
Julia Cygan | | | | | | | | | |
Maciej Dengusiak | | | | | | | | | |
Patryk Flama | | | | | | | | | |
Szymon Fluder | X | X | X | X | X | | | | |
Aleksandra Jędrzejak | | | | | | | | | |
Mikołaj Karapka | | | | | | | | | |
Viktoriia Kashpruk | | | | | | | | | |
Wiktor Małek | X | X | X | X | X | | | | |
Błażej Molik | | | | | | | | | |
Andrzej Morawski | | | | | | | | | |
Konrad Oleksy | | | | | | | | | |
Lucjan Pucelak | | | | | | | | | |
Aleksandra Sęk | | | | | | | | | |
Radosław Śliwiński | | | | | | | | | |
Piotr Traczyński | | | | | | | | | |
Katarzyna Trzos | | | | | | | | | |
Piotr Warząchowski | | | | | | | | | |
Olga Zaborska | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Szymon Fluder

### Najmniejsza

*poprawka*
1. $P_0$ odczytuje `temp0 = 0` i idzie spać
2. $P_1$ wykonuje 49 iteracji. Po tym `counter=49`
3. $P_0$ się budzi i zapisuje `1` do zmiennej `counter`
4. $P_1$ odczytuje wartość zmiennej `counter`. Jest to `0`. Wtedy `temp1 = 1`. Następnie idzie spać.
5. $P_0$ wykonuje się do końca. Wartość `counter = 50`
6. $P_1$ się budzi i wykonuje jedną inkrementację wartości zapisanej w `temp1=1`. Zapisuje `2` do zmiennej `counter`.

:::danger
*źle*
Najmniejsza możliwa wartość zmiennej counter to $50$. Wystąpi to gdy oba procesy odczytają na początku zmienną `counter = 0`. Zanim pierwszy zdąży zapisać wynik pierwszej iteracji pętli, drugi skończy już działanie. Spowoduje to, że zmienna `counter = 50` zostanie nadpisana przez pierwszy proces wartością `counter = 1`. Pierwszy proces dokończy wtedy wszystkie iteracje pętli, więc końcowy wynik to będzie `counter = 50`.
:::

### Największa
`counter = 100` w momencie gdy odczyty i zapisy dwóch procesów wykonują się na przemian ($O_1, Z_1, O_2, Z_2, O_1, Z_1...$)
:::

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

### Mutual exclusion
To jest zapewnione, ponieważ warunkiem wejścia do sekcji krytycznej jest opuszczenie flagi przez drugi proces, który to robi dopiero po opuszczeniu sekcji krytycznej.

### Progress
Ten warunek nie jest zapewniony. Może zajść sytuacja, gdzie $P_0$ da swoją flagę na `true`, tuż po czym proces $P_1$ też ustawi swoją na `true`. Wtedy oba procesy się zawieszą ($P_0$ będzie myślał, że $P_1$ się wykonuje i vice versa).

### Bounded waiting
Proces $P_0$ czeka dopóki flaga procesu $P_1$ jest podniesiona. W momencie wyjścia z sekcji krytycznej przez $P_1$, opuszcza on flagę. Proces $P_0$ to widzi, więc wie, że może wejść do sekcji krytycznej. To samo zachodzi w drugą stronę.
:::

## Zadanie 3
:::success
Autor: Szymon Fluder

### Mutual exclusion
Dwa na raz się wykonują $\implies$
- `flag[0] = true oraz flag[1] = true`
- `turn = 0` aby $P_0$ się wykonywał
- `turn = 1` aby $P_1$ się wykonywał

`turn` nie może mieć dwóch wartości jednocześnie.

### Progress
Jeśli $P_0$ chce wejść do sekcji krytycznej, a $P_1$ w niej nie jest, to `flag[1] = false`, więc pętla `while` się nie wykona, więc $P_0$ wejdzie do sekcji krytycznej.

### Bounded waiting
Podczas wchodzenia do sekcji krytycznej proces ustawia zmienną `turn` na swojego "przeciwnika", więc jeśli chce on wejść do sekcji krytycznej, będzie tak mógł zrobić.
:::

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

Taka zamiana kolejności psuje ten algorytm i pozwala aby dwa procesy były jednocześnie w sekcji krytycznej.

*Bounded waiting* oraz *Progress* są nadal spełnione.
:::

## Zadanie 5
:::success
Autor: Szymon Fluder

### Mutual exclusion
Dwa procesy mogą wtedy jednocześnie być w sekcji krytycznej.
1. $P_0$ wchodzi w sekcję krytyczną => `flag[0] = true; turn=0`
2. $P_1$ podnosi flagę oraz ustawia turę na siebie => `flag[1] = true; turn = 1`
3. $P_1$ wchodzi w sekcję krytyczną, bo `turn != 1 - 1`

### Progress
Z wyjściem z sekcji krytycznej opuszczamy flagę, więc nawet jeśli tura będzie źle ustawiona, flaga będzie miała wartość `false`, więc proces, który chce wejść do sekcji krytycznej będzie mógł tak zrobić.

### Bounded waiting
Jeśli proces czeka na wejście, to od razu po tym jak inny proces skończy swoją sekcję krytyczną, to (ponieważ flaga tamtego procesu będzie opuszczona) ten, który czeka będzie mógł wejść do swojej sekcji krytycznej.
:::

## Zadanie 6
:::danger
Autor:
:::

## Zadanie 7
:::danger
Autor:
:::

## Zadanie 8
:::danger
Autor:
:::

## Zadanie 9
:::danger
Autor:
:::