# Ćwiczenia 14, grupa śr. 14-16, 12 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!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----| ---| --- | ---| ---|--- |--- |--- |--- |
Krzysztof Chorzempa | X | X | X | X | X | | | | |
Maciej Ciepiela | | | | | | | | | |
Szymon Fica | ==X== | X | X | | | | | | |
Agnieszka Grala | | | | | | | | | |
Karolina Jędraszek | | | | | | | | | |
Katarzyna Jodłowska | | | | | | | | | |
Dominik Kiełbowicz | X | | | | | | | | |
Michał Kolasa | X | | | | | | | | |
Rafał Krysa | X | X | X | X | X | X | X | | |
Miłosz Krzysiek | | | | | | | | | |
Łukasz Kulczycki | | | | | | | | | |
Leon Lepkowski | | | | | | | | | |
Hanna Makowska | | | | | | | | | |
Jan Marek | | | | | | | | | |
Cezary Miłek | | | | | | | | | |
Anna Pierzchała | | | | | | | | | |
Alan Pietrasz | X | X | X | X | X | X | | | |
Kacper Ponikowski | | | | | | | | | |
Dominik Walecko | | | | | | | | | |
Michał Włodarczak | | | | | | | | | |
Błażej Molik | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Szymon Fica
:::


counter = counter + 1

1) temp = counter
2) temp = temp + 1
3) counter = temp

MAX:
Jeżeli oba procesy wykonają swoje pętle for bez żadnych interferencji, to każdy proces wykona dokładnie 50 inkrementacji. Sumaryczna liczba inkrementacji wyniesie więc: 50 + 50 = 100

MIN:
| Proces | Iteracja | Instrukcja | counter | temp |
|--------|----------|------------|---------|------|
|P1 | 1 | 1 | 0 | 0 |
|P1 | 1 | 2 | 0 | 1 |
|P2 | 1 | 1 | 0 | 0 |
|... | ... | ... | ... | ... |
|P2 | 49 | 3 | 49 | 49 |
|P1 | 1 | 3 | 1 | 1 |
|P2 | 50 | 1 | 1 | 1 |
|P2 | 50 | 2 | 1 | 2 |
|P1 | 2 | 1 | 1 | 1 |
|... | ... | ... | ... | ... |
|P1 | 50 | 3 | 50 | 50 |
|P2 | 50 | 3 | 2 | 2 |

Minimalny wynik: counter = 2

## Zadanie 2
:::success
Autor: Krzysztof Chorzempa
:::

while(true){
    flag[my_id] = true;
    while(flag[1-my_id] == true);
    /* sekcja krytyczna */
    flag[my_id] = false;
}

### Wzajemne wykluczanie - Mutual exclusion
Tak, dwa procesy nie mogą jednocześnie wykonywać sekcji krytycznej, bo któraś musiałaby wykonywać sekcję krytyczną z wyłączoną flagą, co jest niemożliwe.
### Postęp - Progress
Nie, mogą się dosyć łatwo zablokować:
P0: `flag[0]=true;`
P1: `flag[1]=true;`
P0: `while(flag[1]==true);` (prawda)
P1: `while(flag[0]==true);` (też prawda)
Oba oczekują, żaden nigdy nie wejdzie.
Zmienna *turn* służyła rozstrzyganiu w właśnie takich sytuacjach, nie możemy się jej tutaj po prostu pozbyć.
### Ograniczone czekanie - Bounded waiting
Tak, nastąpi co najwyżej jedno wykonanie sekcji krytycznej w innym procesie podczas czekania.
Będzie tak dlatego, że nawet dużo szybszy np. proces P2 zatrzyma się w *while* jeśli drugi proces czeka (bardzo łatwo może wtedy nastąpić sytuacja opisana wyżej, ale *bounded waiting* nie mówi nic o blokowaniu się).

## Zadanie 3
:::success
Autor: Alan Pietrasz
:::
**Wzajemne wykluczanie**

Ustawienie swojej flagi na true sygnalizuje, że proces chce wejść do swojej sekcji krytycznej. Następnie ustawiamy zmienną turn na przeciwnika. Proces następnie czeka na jedno z dwóch zdarzeń: albo przeciwnik ustawi flagę na false, co jest równoważne opuszczeniu sekcji krytycznej, albo turn będzie ustawione na nas i wtedy przeciwnik nie będzie mógł wejść do sekcji krytycznej, bo jeśli ma on ustawioną flagę na true, to warunek pętli będzie spełniony.

**Postęp**

1) Dwa procesy rywalizują o wejście
Wtedy o tym kto wejdzie decyduje zmienna turn.

2) Jeden proces chce wejść do sekcji krytycznej
Wtedy flaga przeciwnika jest opuszczona i proces może wejść.

**Ograniczone czekanie**

Jeśli dwa procesy P1 i P2 chcą wejść do sekcji krytycznej to wchodzi tylko jeden z nich (niech to będzie P2) i po wyjściu ustawia flagę na false. Jeśli P2 wykona pozostałą sekcję bardzo szybko i zdąży znowu ustawić flagę na true, to następnie ustąpi procesowi P1 i sam poczeka.

## Zadanie 4
:::success
Autor: Rafał Krysa
:::
Warunek wzajemnego wykluczenia nie jest spełniony – jeżeli P1 wchodzi do sekcji krytycznej, to albo flag[0] == false (więc P0 nie jest w sekcji krytycznej) albo turn == 1 (po ustawieniu turn = 0 obudził się P0 i ustawił turn = 1. Nie ma jednak gwarancji, że flag[1] == true, więc P0 może być w sekcji krytycznej kiedy P1 do niej wchodzi)
Warunek postępu jest spełniony – jeżeli oba procesy czekałyby w tym samym momencie, to turn musiałoby mieć dwie różne wartości.
Warunek ograniczonego czekania jest spełniony – jeżeli P1 spróbuje wejść do swojej sekcji krytycznej po raz drugi podczas gdy P0 czeka na pętli while, P1 ustawi zmienne na takie spełniające warunki własnej pętli while, z turn które nie spełnia warunków pętli while P0. Symetrycznie.

## Zadanie 5
:::success
Autor: Krzysztof Chorzempa
:::

flag[my_id] = true;
turn = my_id;
while(flag[1-my_id] == true && turn == 1-my_id);
/* sekcja krytyczna */
flag[my_id] = false;

### Wzajemne wykluczanie - Mutual exclusion
Nie:
P0: `flag[0] = true;`
P1: `flag[1] = true;`
P0: `turn = 0;`
P0: **wchodzi do sekcji krytycznej**
P1: `turn = 1;`
P1: **wchodzi do sekcji krytycznej**
Dzieje się tak dlatego, że nie będzie spełniony warunek czekania o turze pozostałego procesu.
### Postęp - Progress
Zablokowanie się nie jest możliwe, argumentacja jak bez zmiany ("sytuacje sporne" rozstrzyga *turn*).
### Ograniczone czekanie - Bounded waiting
Nie:
P0: `flag[0] = true;`
P0: `turn = 0;`
P1: `flag[1] = true;`
P1: `turn = 1;`
P1: **wchodzi do sekcji krytycznej**
P1: `flag[1] = false;`
P1: `flag[1] = true;`
P1: `turn = 1;`
P1: **wchodzi do sekcji krytycznej**
... (i tak w kółko, P1 wykonuje się cały czas, P0 nie wykonuje się wcale)
(P0 może nie zdążyć się zorientować, że już "może" wejść do sekcji krytycznej)

## Zadanie 6
:::success
Autor: Alan Pietrasz
:::
**Postęp**

1) Dwa procesy rywalizują o wejście
Wtedy o tym kto wejdzie decyduje kto pierwszy uruchomi TestAndSet i zablokuje przeciwnika.

2) Jeden proces chce wejść do sekcji krytycznej a drugi nie jest w sekcji krytycznej
Wtedy zamek jest otwarty i proces może wejść.

**Ograniczone czekanie**

Nie jest spełnione, ponieważ może się zdarzyć, że proces P1 czeka w pętli, ale P2 zdąży zawsze odblokować i zablokować lock tak, że P1 nie zdąży uruchomić funkcji w warunku zakończenia pętli w międzyczasie.

## Zadanie 7
:::success
Autor: Rafał Krysa
:::
Warunek wzajemnego wykluczenia jest spełniony – w pętli while waiting[my_id] jest false tylko jeśli inny proces ustawił ją na false – robi to dla dokładnie jednego procesu. Key będzie false tylko jeżeli lock jest false, a lock jest false tylko przez jedną iterację. Key nie będzie więc false jeżeli jakikolwiek inny proces już jest w sekcji krytycznej. O ile funkcja unlock wykonywać będzie się jednocześnie tylko dla jednego procesu, waiting będzie ustawione na false tylko dla jednego z czekających procesów. Zmiany umożliwiające przerwanie czekania następują w jednej z dwóch możliwych ostatnich instrukcji funkcji unlock, więc funkcja unlock jest wykonywana jednocześnie tylko przez jeden proces o ile sekcja krytyczna również ma tą właściwość. W związku z powyższymi, kiedy proces wchodzi do sekcji krytycznej albo jest jedynym z oczekujących procesów który ma waiting false, albo lock jest false. Ze sposobu w jakie te sytuacje następują, nigdy nie występują jednocześnie. W związku z tym w sekcji krytycznej znajduje się naraz tylko albo taki proces, którego waiting zostało ustawione na false, albo taki, który jako pierwszy się obudził po ustawieniu lock na false, c.k.d.

Warunek postępu jest spełniony z dodatkowym założeniem, że początkową wartością lock jest false – W momencie zakończenia funkcji unlock, po jej ostatniej instrukcji istnieje taki proces, że w obecnej lub następnej iteracji jego pętli while w lock jej warunek nie będzie spełniony.
Jeżeli początkową wartością lock jest true, trywialnie żaden proces nigdy nie wejdzie do sekcji krytycznej, gdyż key zawsze będzie true.

Warunek ograniczonego czekania jest spełniony - jeżeli istnieje jakiś czekający proces, funkcja unlock ustawi jego waiting na false. To ustawianie odbywa się zawsze w kolejności od 0 do n-1 (cyklicznie), więc kiedy proces zacznie czekać, jego waiting zostanie ustawione na false przy mniej niż n wykonaniach sekcji krytycznych innych procesów. Poza tym jeden proces na wejściu do sekcji krytycznej nie zacznie natychmiast ponownie swojej sekcji krytycznej o ile lock nie jest false, a lock będzie false tylko wtedy, kiedy przy wywołaniu unlock nie istniał żaden czekający proces.

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

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