# Ćwiczenia 13, grupa cz. 12-14, 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 |
| ---------------------- | ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | x | x | x | x | x | x | | | |
Adam Ciężkowski | | | | | | | | | |
Jacek Długopolski | x | x | x | x | x | x | x | x | ==x== |
Jakub Fila | x | x | x | x | x | x | | | |
Krzysztof Grynkiewicz | | | | | | | | | |
Michał Hetnar | x | x | x | x | x | x | x | | |
Hubert Jabłoński | | | | | | | | | |
Antoni Kamiński | | | | | | | | | |
Paweł Karaś | | | | | | | | | |
Emil Kisielewicz | x | x | x | x | x | x | | | |
Kacper Komenda | x | x | x | x | x | x | x | x | x |
Filip Komorowski | x | x | x | x | x | x | x | x | x |
Piotr Piesiak | x | x | x | x | x | x | x | x | x |
Artur Krzyżyński | x | x | x | x | x | x | x | x | x |
Patryk Mazur | x | x | x | ==x== | x | x | | | |
Szymon Mleczko | x | x | x | x | x | x | x | x | x |
Michał Mróz | X |==X==| X | X | X | X | X | X | X |
Dominik Olejarz | x | x | x | x | x | x | | x | |
Magdalena Słonińska | ==X== | X | X | X | X | X | | | |
Oleś Kulczewicz | X |==X==| X | X | X | X | | | |
Adam Szeruda | X | X | X | X | X | X | X | X | X |
Kamil Tasarz | X | X | X | X | X | X | | X | |
Michał Zieliński | ==X== | 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: Magdalena Słonińska
:::
> Dwa procesy wykonują funkcję `inc()` operującą na współdzielonej zmiennej `counter`, o początkowej wartości równej `0`.
```
void inc() { counter = counter + 1;}
```
> Jakie są możliwe wartości tej zmiennej po zakończeniu pracy przez obydwa procesy? Czy ma tu miejsce sytuacja wyścigu?
*Sytuacja wyścigu* ma miejsce kiedy wartości współdzielonych zmiennych zależą od kolejności wykonywania instrukcji maszynowych.
Mamy dwie możliwe sytuacje końcowe:
1. `counter = 1` jeśli w pierwszej kolejności wykonamy oba odczyty, zarówno $P_1$ i $P_2$ wywoła `inc()`, a na koniec oba procesy zapiszą wynik do pamięci
2. `counter = 2` jeśli najpierw $P_1$ wykona odczyt i zapis do pamięci, a następnie $P_2$ zrobi to samo
Powyżej skonstruowaliśmy ciągi instrukcji generujące różne wartości współdzielonej zmiennej `counter`, czyli w tym przypadku mamy do czynienia z sytuacją wyścigu.
## Zadanie 2
:::success
Autor: Oleś Kulczewicz
:::
Two processes execute the function sum
```
void sum() {
for(inti=1;i<=50;i++)
counter = counter + 1;
}
```
The operation
```
counter = counter + 1;
```
is not atomic and is in fact
```
register1 = counter
register1 = register1 + 1
counter = register1
```
:::info
we mark **FIRST** as blue process
:::
:::warning
and **SECOND** as yellow process
:::
### Max value: counter == 100
Normal execution of the processes interchangeably
**counter == 0**
:::info
register1 = counter
register1 = register1 + 1
counter = register1
:::
**counter == 1**
:::warning
register2 = counter
register2 = register2 + 1
counter = register2
:::
**counter == 2**
...
**counter == 98**
:::info
register1 = counter
register1 = register1 + 1
counter = register1
:::
**counter == 99**
:::warning
register2 = counter
register2 = register2 + 1
counter = register2
:::
**counter == 100**
### Min value: counter == 2
Both processes load the initial counter, then first process executes, only after that second process executes
```
Pierwszy czyta // counter = 0
Drugi czyta // counter = 0
Pierwszy idzie do 49, czyli jeszcze jeden krok mu został // counter = 49
Drugi zwieksza i zapisuje counter 1 // counter = 1
Pierwszy czyta // counter = 1
Drugi robi się do końca // counter = 50
Pierwszy zwiększa do 2 i zapisuje // counter = 2
```
**counter == 0**
:::info
register1 = counter
:::
:::warning
register2 = counter
:::
:::info
register1 = register1 + 1
counter = register1
:::
**counter == 1**
:::info
register1 = counter
register1 = register1 + 1
counter = register1
:::
**counter == 2**
...
**counter == 49 && register2 == 0**
:::warning
register2 = register2 + 1
counter = register2
:::
**counter == 1**
:::info
register1 = counter
:::
:::warning
register2 = counter
register2 = register2 + 1
counter = register2
:::
**counter == 2**
...
**counter == 50**
:::info
register1 = register1 + 1
counter = register1
:::
**counter == 2**
## Zadanie 3
:::success
Autor: Daniel Boguszewski
:::
1. Warunek Wzajemnego Wykluczania jest spełniony (2 procesy nie mogą wykonywać sekcji krytycznej w tym samym czasie):
- Załóżmy nie wprost, że procesy $P_0$ oraz $P_1$ znajdują się wspólnie w sekcji krytycznej.
- Wobec tego tego oba procesy musiały zakończyć wcześniej wykonywanie procedur $lock(0)$ oraz $lock(1)$.
- Aby było to możliwe, wartości $flag[0]$ oraz $flag[1]$ muszą być równe $true$.
- BSO jednak, jeśli sekcja krytyczna procesu $P_1$ zaczęła się wykonywać, wtedy proces ten musiał zakończyć wcześniej obieg pętli $while(flag[0] == true);$, implikując, iż $flag[0] = false$, co stoi w sprzeczności z założeniem $flag[0] = true$. $\blacksquare$
2. Warunek Postępu nie jest spełniony (jeżeli żaden proces nie wykonuje sekcji krytycznej, wtedy wybór kolejnego procesu do jego wykonaniu musi odbyć się w skończonym czasie):
- Zakładamy, że żaden z procesów $P_i$ nie wykonuje sekcji krytycznej, wobec czego musi wcześniej wykonać procedurę $lock(i)$.
- Rozważmy BSO ogólności sytuację, w której proces $P_0$ wykonuję instrukcję $flag[0] = true$ po czym zrzeka się prawa do procesora na rzecz procesu $P_1$.
- W wyniku tego proces $P_1$ wykonuję procedurę $lock(1)$, ustawia $flag[1] = true$ i przechodzi do wykonania pętli $while(flag[0] == true);$.
- Jednak ze względu na to, że $flag[0] = true$, procedura $lock(1)$ zawiesza się, aż wreszcie proces $P_1$ zrzeka się procesora, który przystępuje do przetwarzania procesu $P_0$.
- Proces ten jednak wznawia swoje działanie na instrukcji $while(flag[1] == true);$ i również się zawiesza, w wyniku czego sekcja krytyczna w żadnym z procesów nigdy nie zostanie wykonana (zawieszony proces $P_1$ oczekuje na zawieszone $P_0$). $\blacksquare$
3. Warunek Równoległego Oczekiwania jest spełniony (jeżeli proces zadeklarował chęć wykonania sekcji krytycznej, wtedy istnieje liczba $k \in \mathbb{N}$, ograniczająca możliwą liczbę wykonań sekcji krytycznej innych procesów):
- Załóżmy BSO, że $P_1$ oczekuje na przejście do sekcji krytycznej, w czasie gdy $P_0$ już je wykonuje. Pokażemy, że $k = 1$. Z poprzednich rozważań wiemy, że w tej sytuacji musi zachodzić $flag[0] = flag[1] = true$.
- Przyjmijmy teraz, że proces $P_0$ zakończył wykonywanie sekcji krytycznej i wykonał procedurę $unlock(0)$. Rozważmy przypadki:
1. $P_0$ zrzeka się procesora przed wykonaniem instrukcji $flag[0] = true$ procedury $lock(i)$, w wyniku czego $P_1$ wznawia działanie na pętli $while(flag[0] == true);$, kończąc tym samym jej obieg i przechodzi do wykonania sekcji krytycznej ($\implies k = 1$).
2. $P_0$ nie zrzeka się procesora przed wykonaniem $flag[0] = true$, w wyniku czego $P_1$ nie będzie w stanie wykonać sekcji krytycznej, co implikuje jednak, że nie zostanie wykonana procedura $unlock(1)$. Następuje więc zawieszenie działania obu procedur, gdyż $flag[0] = flag[1] = true$, w czasie gdy oba procesy próbują wykonać pętlę $while(flag[1-i] == true);$, gdzie $i$ to indeks procesu $P_i$ ($i \in \{0, 1\}$). Z tego powodu nigdy nie dochodzi do ponownego (w tym wypadku drugiego) wykonania sekcji krytycznej procesów różnych od $P_1$, czyli $P_0$ ($\implies k = 1$). $\blacksquare$
## Zadanie 4
:::success
Autor: Patryk Mazur
:::
### 1. Mutual Exclusion
Aby ten warunek nie był spełniony, musiałoby zachodzić
``` cpp=
!(flag[j] && turn == j) && !(flag[i] && turn == i)
```
Czyli
``` cpp=
(flag[j] == false && flag[i] == false) || (flag[j] == false && turn==j) || (turn==i && flag[i] == false) || (turn==i && turn==j)
```
### 2. Progress
Aby ten warunek nie był spełniony, musiałoby zachodzić
``` cpp=
(flag[j] && turn == j) && (flag[i] && turn == i)
```
Czyli
``` cpp=
turn == j && turn == i
```
Co z oczywistych względów jest niemożliwe
### 3. Bounded Waiting
Jeżeli proces $P_i$ chce wejść do sekcji krytycznej, w której obecnie znajduje się $P_j$, to musi poczekać aż $P_j$ po wyjściu zmieni swoją flage na false, co złamie warunek pętli i wtedy $P_i$ wejdzie do sekcji krytycznej. Więc czas oczekiwania procesu $P_i$ jest ograniczony przez proces $P_j$
## Zadanie 5
:::success
Autor: Kamil Tasarz
:::
```cpp
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;
}
```
* $\color{#B22222}{\text{Mutual Exclusion}}$
Wartości początkowe: ```flag[0] = false, flag[1] = false, turn = 0```
P0 execute:
```cpp
turn = 1; // flag[0] = false, flag[1] = false, turn = 1
```
P1 execute:
```cpp
turn = 0; // flag[0] = false, flag[1] = false, turn = 0
flag[1] = true; // flag[0] = false, flag[1] = true, turn = 0
while (flag[0] && turn == 0); //false
//P1 rozpoczął wykonywanie sekcji krytycznej..
```
P0 execute:
```cpp
flag[0] = true; // flag[0] = true, flag[1] = true, turn = 0
while (flag[1] && turn == 1); // false
//P0 rozpoczął wykonywanie sekcji krytycznej..
```
* $\color{#32CD32}{\text{Progress}}$
* $\color{#32CD32}{\text{Bounded Waiting}}$
## Zadanie 6
:::success
Autor: Jakub Fila
:::
> Teraz funkcja lock nie działa poprawnie, ponieważ wyrażenie turn == 1-my_id będzie zawsze fałszywe. Oznacza to, że nie mamy spełnionego warunku Mutual Exclusion. Z uwagi na nielimitowany dostęp do sekcji krytycznej dla procesów, warunek progress jest spełniony, bounded waiting naturalnie również.
1. Warunek wzajemnego wykluczenia **nie jest spełniony**
2. Warunek postępu **jest spełniony** - skoro procesy same mogą odblokować swoją turę, to niezależnie od flagi drugiego mogą wejść do sekcji krytycznej.
3. Warunek ograniczonego czekania **nie jest spełniony** - procesy mogą same odblokowywać swoje tury, tym bardziej mogą głodzić drugi proces:
## Zadanie 7
:::success
Autor: Adam Szeruda
:::
> Tym razem funkcje lock() i unlock() wyglądają następująco:
```c=
void lock(int my_id) {
flag[my_id] = true;
while (flag[1 - my_id] == true) {
if (turn != my_id) {
flag[my_id] = false;
while (turn != my_id);
flag[my_id] = true;
}
}
}
void unlock(int my_id) {
turn = 1 - my_id
flag[my_id] = false;
}
```
> Co można powiedzieć o tym algorytmie?
- ✅ **Wzajemne wykluczenie**
Proces może wejść do sekcji krytycznej jedynie, gdy wartość `turn` jest równe `my_id`. Wartość ta zmienia się, gdy drugi proces opuszcza sekcję krytyczną.
- ✅ **Postęp**
W przypadku, gdy oba procesy rozpoczną czekanie na wejście do secji krytycznej (ustawią `flag[my_id] = true`), proces o `my-id != turn` tymczasowo zwolni `flag`, pozwalając temu drugiemu wejście do sekcji krytycznej.
- ❎ **Ograniczone czekanie**
Rozważmy następujące wykonanie procesów:
```
P0 | P1
|
flag[0] = false; |
while (turn != 0); |
| unlock(1);
| turn = 0;
| ...
| lock(1);
| while (flag[0] == true);
| ...
| unlock(1);
| lock(1);
| ...
```
Jeżeli procesowi P0 nie zostanie przydzielony procesor, to P1 może utrzymywać dostęp do sekcji krytycznej na wyłączność.
## Zadanie 8
:::success
Autor: Kacper Komenda
:::
Nie ma deadlocka, bo w sytuacji, gdy jeden ustawia zamek na false (w metodzie unlock), to oba wątki ponownie mogą go zdobyć.
Nie zadziała za to warunek z n-bounded waiting, jeden z wątków może zostać zagłodzony (drugi w nieskończoność może zdobywać zamek)
## Zadanie 9
:::success
Autor: Jacek Długopolski
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
