# Ćwiczenia 13, grupa cz. 14-16, 1 czerwca 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!**
**Wyrównajcie plz te tabelkę w markdownie (jestem ze spektrum) ~ Michał**
:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | ----- |:----- | ----- | ----- | ----- |:-----:| ----- | --- |
| Mikołaj Balwicki | | | | | | | | | |
| Wojciech Bogucki | X | X | X | X | X | X | | X | X |
| Mateusz Cerulewicz | X | X | X | X | | | | | |
| Mateusz Garncarczyk | X | ==X== | X | X | X | X | X | X | |
| Mateusz Golisz | X | X | ==X== | X | X | X | X | X | X |
| Mateusz Kitzol | X | X | X | X | | | | | |
| Piotr Mańkowski | | | | | | | | | |
| Aleksandra Nicpoń | X | X | X | X | | | | | |
| Ksawery Plis | X | X | X | X | X | X | X| | |
| Patryk Rybak | X | X | X | X | X | ==X== | X | X | |
| Rafał Spyra | X | X | X | X | | | | | |
| Dominik Szczepaniak | X | X | X | X | X | X | X | ==X== | X |
| Taras Tsehenko | | | | | | | | | |
| Maksymilian Wiśniewski | ==X== | X | X | X | X | X | X | X | |
| Martyna Wybraniec | | | | | | | | | |
| Natalia Zychowicz | X | X | X | X | X | X | ==X== | X | |
| Patryk Maciąg | X | X | X | X | X | X | X | | |
| Michał Mękarski | X | 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: Maksymilian Wiśniewski
:::
Dwa procesy wykonują funckję `inc()` 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 ang.*race condition*?
Race Condition(ang. sytuacja wyścigu) - to jest sytuacja w której dwa
wątki wykonujące pracę współbierznie modyfikują wspólne zmienne, które powinny byc zabezpieczone
przed jednoczesnym modyfikowaniem.
---
Jeśli najpierw wykona się proces pierwszy, następnie proces drugi:
```cpp
p1_counter = counter //counter = 0
p1_counter += 1 // counter = 1
counter = p1_counter
p2_counter = counter // counter = 1
p2_counter += 1 // counter = 2
counter = p2_counter
```
*counter* wynosi 2.
---
Jeśli procesy się przeplatają:
```cpp
p1_counter = counter // counter = 0
p2_counter = counter // counter = 0
p1_counter += 1 //po wykonaniu counter = 1
p2_counter += 1 //po wykonaniu counter = 1
counter = p1_counter
counter = p2_counter
```
Występuje *race condition*.
---
## Zadanie 2
:::success
Autor: Mateusz Garncarczyk
:::
**Najmniejsza wartość**
operacja ``counter = counter + 1`` jest podzielna
```
reg = counter // odczyt
reg = reg + 1 // modyfikacja
counter = reg // zapis
```
**P1 - proces 1
P2 - proces 2**
| Instrukcja | Counter |
| -------------------------------------------------------- | ------- |
| P1 wczytuje counter | 0 |
| P2 wczytuje counter | 0 |
| P1 dodaje 49 razy jedynkę | 49 |
| P2 zwiększa counter o 1 i nadpisuje wartość 49 wartością 1 | 1 |
| P1 wczytuje counter | 1 |
| P2 dodaje 49 razy jedynkę | 50 |
| P1 wykonuje dodanie 1 i nadpisuje wartość 50 wartością 2 | 2 |
## Zadanie 3
:::success
Autor: Mateusz Golisz
:::
### Wzajemne wykluczanie
Spełnione:
Nie wprost załóżmy, że oba procesy są w sekcji krytycznej, bez utraty ogólności uznajmy, że P1 wszedł do niej jako drugi.
Oznacza to, że nie zachodziło flag[1-1]==true, czyli flag[0] było równe false. Jednak, jedynym możliwym momentem gdzie flaga może zostać zmieniona na false występuje w sekcji wyjściowej, a w sekcji wejściowej flaga jest ustawiana na true, stąd P0 nie może być w sekcji krytycznej, co jest sprzeczne z założeniem.
### Postęp
Nie spełnione:
Załóżmy, że żaden proces nie wykonuje sekcji krytycznej. Załóżmy też, że oba procesy weszły do sekcji wejściowej w tym samym czasie, więc obie mają ustawione wartości flag true. Wtedy
```while (flag[1 - my_id] == true)``` wejdzie do nieskończonej pętli dla obu procesów.
### Ograniczone czekanie
Spełnione:
Załóżmy, bez straty ogólności, że proces P0 wykonuje swoją sekcję krytyczną a P1 czeka w sekcji wejściowej (ponieważ flaga P0 jest ciągle równa true). Po wyjściu z sekcji krytycznej, proces P0 ustawi swoją flagę na false, co oznacza, że proces P1 będzie mógł wejść do sekcji krytycznej, tj. nie ma możliwości, aby proces P0 się "wepchnął" przed niego.
## Zadanie 4
:::success
Autor: Michał Mękarski
:::
### ✅ Warunek Postępu
**Załóżmy nie wprost, że** oba procesy są zapętlone, czyli zachodzi jednocześnie *warunek zapętlenia dla procesu 0*
```cpp
flag[0] == true;
turn == 1;
```
oraz *warunek zapętlenia dla procesu 1*
```cpp
flag[1] == true;
turn == 0;
```
Otrzymujemy **sprzeczność, bo** zmienna `turn` nie może być jednocześnie w stanie `0` i `1`.
$\Rightarrow$ ⬛
### ✅ Waruenk Ograniczonego Czekania
Czas ograniczenia jest ograniczony czasem wykonania drugiego procesu z uwagi na ustawienie wartości zmiennej `turn` na `ID` drugiego procesu.
### ✅ Warunek Wzajemnego Wykluczenia
Pomimo możliwości zajścia sytuacji w której obie flagi są ustawione na true, dzięki wykorzystaniu zmiennej trun nie zajdzie sytuacja, w której oba procesy uzyskają dostęp do sekcji krytycznej.
## Zadanie 5
:::success
Autor: Ksawery Plis
:::
**Zmodyfikowany algorytm:**
```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;
}
```
**Warunki:**
* **Wzajemne wykluczanie - NIE**
```
P0: turn = 1;
P1: turn = 0;
P1: flag[1] = true;
P1: while (flag[0] == true && turn == 0) //false, bo flag[0] = false
P0: flag[0] = true;
P0: while(flag[1] == true && turn == 1) //false, bo turn = 0
```
Oba procesy mają false w tym samym czasie i wchodzą do sekcji krytycznej
* **Postęp - TAK**
Turn będzie mieć równocześnie tylko jedną wartość, czyli jakiś proces zostanie wpuszczony i nie wpadniemy w nieskończoną pętlę
* **Ograniczone czekanie - TAK**
Chętny do wejścia do sekcji krytycznej proces będzie oczekiwał do momentu aż wykonujący się proces opuści swoją flagę w unlocku lub wpuści go, ustawiając turn w locku
## Zadanie 6
:::success
Autor: Patryk Rybak
:::
Wzajemne wykluczanie - niespełniony
Przez turn = my_id warunek w pętli while będzie niespełniony co powoduje przejście do sekcji krytycznej nawet wtedy, gdy jest ona używana przez inny proces
Warunek postępu - spełniony
Dzięki turn = my_id proces może sam sobie odblokować dostęp do sekcji krytycznej Nie ma więc sytuacji, w której nikt nie wykonuje sekcji krytycznej i jednocześnie ktoś czeka na dostęp.
Warunek ograniczonego oczekiwania - niespełniony
Może dojść do głodzenia procesu.
przykład:
## Zadanie 7
:::success
Autor: Natalia Zychowicz
:::
```
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;
}
```
**W algorytmie występuje:**
* 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 sekcji krytycznej (ustawią flag[my_id] = true), proces o ```my-id != turn``` tymczasowo zwolni flag, pozwalając temu drugiemu wejście do sekcji krytycznej.
**Nie występuje:**
* 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: Dominik Szczepaniak
:::
```c
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;
}
```
Postęp i wzajemne wykluczenie zachodzi.
Zawodzi ograniczone czekanie. Załóżmy, że do sekcji krytycznej chce się dostać wiele procesów, w takim przypadku może okazać się, że niektóre procesy nie będą w stanie wykonać TestAndSet gdy sekcja krytyczna będzie wolna, ponieważ inne procesy będą zawsze “szybsze”. Nie możemy zatem określić ograniczenia górnego czasu czekania na dostęp. Poniżej mamy przedstawiony taki przykład, gdy np Thread1 jest szybszy od Thread0 i zawsze będzie lockował szybciej po swoim unlocku.
Thread1 : lock
Thread0 : czeka w while (TestAndSet(&lock));
Thread1 : unlock
Thread1 : lock
## Zadanie 9
:::success
Autor: Wojciech Bogucki
:::
```
void lock(int my_id) {
waiting[my_id] = true;
bool key = true;
while (waiting[my_id] && key)
key = TestAndSet(&lock);
waiting[my_id] = false;
}
void unlock(int my_id) {
int j = (my_id + 1) % n;
while ((j != my_id) && !waiting[j])
j = (j + 1) % n;
if (j == my_id)
lock = false;
else
waiting[j] = false;
}
```
Podane funkcje `lock()` i `unlock()` implementują rozwiązanie problemu sekcji krytycznej dla dowolnej liczby `n` procesów, spełniając warunki wzajemnego wykluczania, postępu i ograniczonego czekania. Opiszę, jak dokładnie działają te funkcje:
1. Wzajemne wykluczanie (mutual exclusion):
- Każdy proces, który chce wejść do sekcji krytycznej, ustawia swoją flagę `waiting[my_id]` na `true`, sygnalizując swoje zainteresowanie wejściem do sekcji krytycznej.
- Następnie proces wykonuje operację TestAndSet(&lock), która jest atomowa (niepodzielna) i zwraca wartość poprzednią zmiennej `lock`, jednocześnie ustawiając `lock` na `true`.
- Jeśli wartość zwrócona przez TestAndSet() jest równa `true`, oznacza to, że inny proces aktualnie znajduje się w sekcji krytycznej (wartość `lock` była już `true`).
- W takim przypadku proces wchodzi w pętlę while, czekając, aż jego flaga `waiting[my_id]` zostanie ustawiona na `false`. Jednocześnie wykonuje TestAndSet(&lock) w każdej iteracji, aby sprawdzić, czy inny proces nadal jest w sekcji krytycznej.
- Gdy proces opuszcza pętlę while, oznacza to, że ma dostęp do sekcji krytycznej i ustawia swoją flagę `waiting[my_id]` na `false`, aby oznaczyć zakończenie próby wejścia do sekcji krytycznej.
2. Postęp (progress):
- Proces, który chce wejść do sekcji krytycznej, otrzymuje szansę na dostęp do sekcji krytycznej, gdy tylko jego flaga `waiting[my_id]` zostanie ustawiona na `true`.
- Proces, który aktualnie jest w sekcji krytycznej i opuszcza ją, sprawdza kolejne flagi w tablicy `waiting` w cyklicznej kolejności, zaczynając od `(my_id + 1) % n`. Szuka procesu, który oczekuje na wejście do sekcji krytycznej.
- Jeśli znajdzie taki proces, ustawia jego flagę na `false`, umożliwiając mu wejście do sekcji krytycznej.
- Jeśli nie znajdzie żadnego procesu oczekującego, ustawia zmienną `lock` na `false`, co oznacza, że żaden proces nie jest obecnie w sekcji krytycznej.
3. Ograniczone czekanie (bounded waiting):
- Algorytm zapewnia ograniczone czekanie, ponieważ każdy proces, który chce wejść do sekcji krytycznej, zostaje uwzględniony po kolei.
- Procesy oczekujące na wejście do sekcji krytycznej są analizowane w cyklicznym porządku `(my_id + 1) % n`.
- Jeśli proces oczekujący jest już w sekcji krytycznej (jego flaga `waiting[j]` jest ustawiona na `true`), to kolejny proces oczekujący otrzymuje szansę na wejście do sekcji krytycznej.
- Każdy proces oczekujący na wejście do sekcji krytycznej będzie miał szansę wejść do niej w ciągu `n-1` obrotów pętli while.
Wnioski:
Algorytm zaprezentowany w podanych funkcjach `lock()` i `unlock()` spełnia warunki wzajemnego wykluczania, postępu i ograniczonego czekania, co czyni go poprawnym rozwiązaniem problemu sekcji krytycznej dla dowolnej liczby `n` procesów.
Google Drive
Gist
Clipboard
Sign in with Wallet
