owned this note
owned this note
Published
Linked with GitHub
# Ćwiczenia 14, grupa cz. 16-18, 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 punkty są bonusowe.**
:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ---:| --- | --- | --- | --- | --- | --- | --- | --- | --- |
Marcin Banak | | | | | | | | | |
Bartosz Borecki | | | | | | | | | |
Karol Burczyk | | | | | | | | | |
Yelyzaveta Ilman | | | | | | | | | |
Antoni Kamiński | | | | | | | | | |
Jan Kamyk | | | | | | | | | |
Bartosz Kruszewski | | | | | | | | | |
Hanna Laszkiewicz | ==X== | | | | | | | | |
Kaja Matuszewska | | | | | | | | | |
Dominik Muc | | | | | | | | | |
Franciszek Przeliorz | X | X | X | | | | | | |
Yaryna Rachkevych | | | | | | | | | |
Mikołaj Kalitka | | | | | | | | | |
Piotr Thamm | X| | | | | | | | |
Taras Tsehenko | | | | | | | | | |
Wiktor Małek | | | | | | | | | |
Piotr Warząchowski | | | | | | | | | |
Piotr Salamon | X | X | | | | | | | |
Viktoriia Kashpruk |x|x|x|x|x|x|x|x |
Błażej Molik | X | X | X | X | X | X | | | |
:::
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::
## Zadanie 1
:::success
Autor: Hanna Laszkiewicz
![obraz](https://hackmd.io/_uploads/SkOLxYOSC.png)
![obraz](https://hackmd.io/_uploads/ryG_etOrA.png)
Największa wartość: 100, osiągniemy ją wtedy, kiedy każdy proces po zmianie wartości natychmiast ją zapisze, przed odczytaniem wartości przez drugi proces. Dzięki temu każdy proces będzie miał dostęp do rzeczywistej bieżącej wartości countera, a nie tej, która nie została jeszcze zapisana, ale mogła już zostać obliczona przez drugi proces.
:::
## Zadanie 2
:::success
Autor: Piotr Salamon
![image](https://hackmd.io/_uploads/H1K8bduHA.png)
Czy zawsze jest co najwyżej jeden aktywny proces?
Tak bo jeżeli oba weszły by jednocześnie do lock to jeden by był w while:
P_0 = 0, 1 - my_id = 1.
P_1 = 1, 1 - my_id = 0.
Oba zaznaczyłyby flagę ale jeden by czekał w while na drugiego
Zawsze działa jeden?
Nie - może być tak że 2 procesy będa oznaczą flagi i będą w while do nieskończoności.
Czy jest ograniczenie na czekanie?
Tak, jeżeli jeden proces się wykonał to nie może od razu wykonać się kolejny raz.
Inny proces już zaznaczył swoją flagę i czekał w while.
:::
## Zadanie 3
:::success
Autor: Franciszek Przeliorz
:::
Oto implementacja funkcji lock() i unlock():
```
void lock(int my_id) {
flag[my_id] = true;
turn = 1 - my_id;
while (flag[1 - my_id] == true && turn == 1-my_id);
}
void unlock(int my_id) {
flag[my_id] = false;
}
```
### Mutual exclusion
Proces czeka, gdy flaga drugiego procesu jest `true` i `turn` wskazuje na przeciwny proces. Zatem oba procesy nie mogą jednocześnie być w sekcji krytycznej.
### Progress
Jeśli oba procesy ustawiają swoje flagi na `true`, to wartość zmiennej `turn` decyduje, który proces wejdzie do sekcji krytycznej.
Rozwiązuje to problem z poprzedniego zadania, w której dwa procesy będą czekały na siebie nawzajem.
#### Przykład:
```
flag[0] = true
flag[1] = true
turn = 0
```
W $P_0$ w pętli `while` w `lock()`, zdanie `flag[1 - my_id] == true && turn == 1-my_id` jest nieprawdziwe więc proces jest dopuszczony do sekcji krytycznej.
### Bounded waiting
Podczas `fazy wejściowej `proces ustawia zmienną turn na przeciwny proces, dając mu szansę na wejście do sekcji krytycznej.
#### Program rozwiązuje problem sekcji krytycznej ✅😄
## Zadanie 4
:::success
Autor: Błażej Molik
:::
![obraz](https://hackmd.io/_uploads/r1LKsD_BC.png)
Przez taką zmianę może dojść do sytuacji, w której 2 procesy znajdą się jednocześnie w sekcji krytycznej.
Mamy sytuację gdy:
```
while(true){
turn = j /*zamiana
flag[i] = true /*
while(flag[j] == true and turn == j)
/*sekcja krytyczna*/
flag[i] = false
/*reszta*/
}
```
* **Wzajemne wykluczenie**
Nie będzie spełniony ten warunek. Przykład poniżej:
![obraz](https://hackmd.io/_uploads/r1CuiPOBC.png)
| Proces | Operacja |
| -------- | -------- |
| P0 | turn = 1 |
| P1 | turn = 0 |
| P1 | flag[1] = true |
| P1 | wchodzi do sekcji krytycznej |
| P0 | flag[0] = true |
| P0 | wchodzi do sekcji krytycznej |
* **Postęp** - spełnione, bo jeżeli oba by czekały, to turn musiałoby mieć różne wartości.
* **Ograniczone czekanie** - jeśli dwa procesy P0 i P1 chcą wejść do sekcji krytycznej to wchodzi tylko jeden z nich (niech to będzie P1) i po wyjściu ustawia flagę na false. Jeśli P1 wykona pozostałą sekcję bardzo szybko i ustawi turn na P0 oraz ustawi flagę na true, to sam poczeka i do sekcji krytycznej wejdzie P0.
## Zadanie 5
:::success
Autor: Błażej Molik
:::
![obraz](https://hackmd.io/_uploads/B1a9gd_rA.png)
![obraz](https://hackmd.io/_uploads/SylWbO_BC.png)
* **Wzajemne wykluczenie**
| Proces | Operacja |
|--------|----------------------------------|
| P0 | flag[0] = true |
| P0 | turn = 0 |
| P0 | wchodzi do sekcji krytycznej |
| P1 | flag[1] = true |
| P1 | turn = 1 |
| P1 | wchodzi do sekcji krytycznej |
Nie czekamy na wykonanie się procesu.
* **Postęp** - bez zmian
* **Ograniczone czekanie** - nie działa
| Proces | Operacja |
|--------|----------------------------------|
| P0 | flag[0] = true |
| P0 | turn = 0 |
| P1 | flag[1] = true |
| P1 | turn = 1 |
| P0 | wchodzi do sekcji krytycznej |
| P0 | flag[0] = false |
| P0 | flag[0] = true |
| P0 | turn = 0 |
| P0 | wchodzi do sekcji krytycznej |
itd..
## Zadanie 6
:::success
Autor: Błażej Molik
:::
![obraz](https://hackmd.io/_uploads/Hy0oqOOHA.png)
![obraz](https://hackmd.io/_uploads/r1KhcudSC.png)
* **Postęp**
Jeżeli dwa procesy rywalizują to wygra ten, który był szybszy. Ustawi jako pierwszy wartość true (w sposób atomowy).
* **Ograniczone czekanie**
Nie jest spełnione, ponieważ P1 może czekać w pętli, jednak w momencie kiedy P0 będzie wychodzić z sekcji krytycznej, będzie "szybsze" tzn. odblokuje i zablokuje lock szybciej niż P1, który dalej będzie czekać.
## Zadanie 7
:::success
Autor: Viktoriia Kashpruk
![image](https://hackmd.io/_uploads/rkrZ_wdSR.png)
Załóżmy, że warunek wzajemnego wykluczania nie jest spełniony. Oznacza to, że dwa różne procesy P_i i P_j mogą jednocześnie znajdować się w sekcji krytycznej.
### Wzajemne wykluczanie
Proces P_i ustawia waiting[my_id] na true i próbuje ustawić lock na true za pomocą TestAndSet(&lock).
W tym samym czasie proces P_j również ustawia waiting[my_id] na true i próbuje ustawić lock na true za pomocą TestAndSet(&lock).
Ponieważ TestAndSet(&lock) jest operacją atomową, tylko jeden z tych procesów może ustawić lock na true w danym momencie, a drugi proces zobaczy wartość true i będzie musiał czekać.
Jeśli proces P_i ustawi lock na true, proces P_j będzie musiał czekać w pętli while (waiting[my_id] && key).
To samo dotyczy odwrotnej sytuacji, jeśli proces P_j ustawi lock na true, proces P_i będzie musiał czekać.
Oznacza to, że oba procesy nie mogą być jednocześnie w sekcji krytycznej.
### Postęp
Załóżmy, że warunek postępu nie jest spełniony. Oznacza to, że istnieje sytuacja, w której proces P_i chce wejść do sekcji krytycznej, ale nie może tego zrobić, mimo że żaden inny proces nie jest w sekcji krytycznej.
Proces P_i ustawia waiting[my_id] na true i próbuje ustawić lock na true za pomocą TestAndSet(&lock).
Jeśli lock jest false, TestAndSet(&lock) ustawi lock na true i proces P_i wejdzie do sekcji krytycznej.
Jeśli lock jest true, oznacza to, że inny proces jest w sekcji krytycznej
Gdy inny proces opuszcza sekcję krytyczną, ustawia lock na false i przegląda tablicę waiting, aby znaleźć pierwszy proces, który czeka.
Proces opuszczający sekcję krytyczną ustawia waiting[j] na false dla procesu, który czeka, umożliwiając mu wejście do sekcji krytycznej.
Zatem proces P_i nie może być zablokowany na zawsze, ponieważ w końcu lock zostanie ustawiony na false i proces P_i będzie mógł ustawić lock na true i wejść do sekcji krytycznej.
### Ograniczone czekanie
Załóżmy, że warunek ograniczonego czekania nie jest spełniony.
Proces P_i ustawia waiting[my_id] na true i próbuje ustawić lock na true za pomocą TestAndSet(&lock).
Jeśli lock jest false, TestAndSet(&lock) ustawi lock na true i proces P_i wejdzie do sekcji krytycznej.
Jeśli lock jest true, oznacza to, że inny proces jest w sekcji krytycznej lub właśnie opuszcza sekcję krytyczną.
Gdy inny proces opuszcza sekcję krytyczną, ustawia lock na false i przegląda tablicę waiting, aby znaleźć pierwszy proces, który czeka.
Proces opuszczający sekcję krytyczną ustawia waiting[j] na false dla procesu, który czeka, umożliwiając mu wejście do sekcji krytycznej.
Proces P_i może być zablokowany na krótki czas, ale nie na zawsze, ponieważ w końcu lock zostanie ustawiony na false i proces P_i będzie mógł ustawić lock na true i wejść do sekcji krytycznej.
:::
## Zadanie 8
:::success
Autor: Viktoriia Kashpruk
![image](https://hackmd.io/_uploads/H1Pb0PuB0.png)
Semafory i mutexy są narzędzami niskopoziomowymi przez co są bardzo podatne na błędy. Na przykład bardzo łatwo doprowadzić do zablokowania wątków (wątki zaczynają oczekiwać na mutexie, który nigdy nie zostanie zwolniony). Bardzo łatwo jest zapomnieć o zwalnianiu mutexu na każdej ścieżce w programie.
Monitor jest wysokopoziomowym narzędziem, który stara się zapobiec wadom mutexów i semaforów.
![image](https://hackmd.io/_uploads/HJ0IG2wrR.png)
Monitor jest obiektem, który wprowadza dodatkową synchronizację - każda z procedur może zostać wykonana przez jeden wątek jednocześnie, czyli wszystkie procedury podlegają wzajemnemu wykluczeniu
![image](https://hackmd.io/_uploads/SkFQBhvHA.png)
Domyślnie z monitorem jest związany obiekt zamka. Przed wejściem do każdej z procedur musimy zająć ten zamek, a po wyjściu zwolnić.
Zmienna warunkowa implementuje możliwość oczekiwania na warunek i informowania o zajściu warunku.
![image](https://hackmd.io/_uploads/Syf8BnDH0.png)
Na zmiennej warunkowej mamy operacje wait oraz signal, które mogą być wykonywane z wnętrza monitora.
1) wait() - będąc wewnątrz procedury tymczasowo zwalniamy zamek, który zajęliśmy wchodząc do tej procedury i usypiamy się w kolejce czekając na spełnienie tego warunku, dzięki czemu inne wątki mogą wchodzić do procedur monitora.
2) signal() - operacje, która informuje, że warunek na który nasz pierwotny proces oczekiwał własnie nastąpił. Wtedy pierwszy czekający proces jest budzony i ustawia się w kolejce procesów oczekujących na zajęcie zamka. Kiedy zostanie mu przydzielony zamek, to będzie mógł się wykonywać od miejsca, w którym rozpoczął oczekiwanie na zajście warunku.
**Problem producenta i konsumenta**
Tymczasowow oddać sterowanie wątka, który jest w sekcji krytycznej
Proces producenta produkuje wartość i zapisuje ją do bufora.
Proces konsumenta wyciąga wartość z bufora i ją konsumuje.
Bufor ma ograniczoną liczbę miejsc, więc jeśli producent spróbowałby zapisać wartość do pełnego bufora, to zasypia on na zmiennej warunkowej, która oznacza pełność bufora. Konsument po każdym skonsumowaniu wartości z bufora sprawia, że przestaje on być pełny i wtedy może to zasygnalizować co spowoduje obudzenie producenta.
:::
## Zadanie 9
:::danger
Autor:
:::