# Ćwiczenia 13, grupa śr. 17-19, 8. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | | | | |
Kamila Brzozowska | X | X | X | X | X | X | X | X | |
Adam Ciężkowski | X | X | X | X | X | X | X | X | X |
Natalia Czerep | X | X | X | X | X | X | | | |
Jan Dalecki | X | X | X | X | X | X | X | ==X== | X |
Marko Golovko | X |==X==| X | X | X | X | | | |
Adam Górkiewicz | | | | | | | | | |
Piotr Gunia | X | X | X | X | X | X | | | |
Krzysztof Jadłowski | ==X== | X | X | X | X | X | X | | |
Magdalena Jarecka | X | X | X | X | X | X | | | |
Mikołaj Jaszcza | | | | | | | | | |
Monika Jędrzejkowska | | | | | | | | | |
Michał Kierul | | X | X | X | X | X | X | X | |
Damian Lukas | | | | | | | | | |
Karol Ochman-Milarski | | | | | | | | | |
Piotr Piesiak | | | | | | | | | |
Damian Ratajski | | | | | | | | | |
Aleksandra Rozkrut | X | X | X | X | X | X | | X | |
Marcin Sarnecki | | | | | | | | | |
Maria Szlasa | X | X | X | X | X | X | | | |
Mateusz Burdyna | X | X | X | X | X | X | X | X | |
Magdalena Słonińska | | | | | | | | | |
Nikola Wrona | | | | | | | | | |
Marcin Wróbel | X | X | X | X | X | X | X | X | X |
:::

**Tutaj można dodeklarować zad. 7. z listy 12.:**
*
*
*

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

## Zadanie 1
:::success
Autor: Krzysztof Jadłowski
:::
Ma tu miejsce sytuacja wyścigu, możemy uzyskać różny wynik zależnie od kolejności wykonania instrukcji w kodzie maszynowym równoczesnego wykonywania procesów. Możliwe końcowe wartości to 1 i 2.

### Dla 1

register_1 = count [register_1 = 0]
register_2 = count [register_2 = 0]
register_1 = register_1 + 1 [register_1 = 1]
register_2 = register_2 + 1 [register_2 = 1]
count = register_1 [count = 1]
count = register_2 [count = 1]
### Dla 2

register_1 = count [register_1 = 0]
register_1 = register_1 + 1 [register_1 = 1]
count = register_1 [count = 1]
register_2 = count [register_2 = 1]
register_2 = register_2 + 1 [register_2 = 2]
count = register_2 [count = 2]

## Zadanie 2
:::success
Autor: Marko Golovko
:::


P2 wczytuje counter 0
P1 wykonuje pętlę do ostatniego obrotu
P2 zapisuje counter 1
P1 wszytuje counter 1
P2 wykonuję pętlę do końca
P1 zapisuję 2

min 2

P1 wykonuję pętlę do końca
P2 wykonuję pętlę do końca

max 100

## Zadanie 3
:::success
Autor: Michał Kierul
:::

Kod nie rozwiązuje problemu sekcji krytycznej, nie spełnia wszystkich warunków. Spełnia warunek wyłączności: sekcja krytyczna wątku zostanie uruchomiona dopiero po zakończeniu sekcji w drugim wątku (gdy flaga będzie ustawiona na fałsz). Nie spełnia pozostałych warunków, gdyż jeden wątek oczekujący na wejście do sekcji krytycznej może ustawić swoją flagę na wartość true i zostać wywłaszczony. W międzyczasie drugi wątek może zakończyć działanie w sekcji krytycznej, ustawić flagę na false i ponownie próbować wejść do sekcji krytycznej ustawiając znowu swoją flagę na true. Wówczas dochodzi do sytuacji patowej - obie flagi są ustawione na true (nie jest spełniony warunek postępu). Warunek ograniczonego oczekiwania jest spełniony (wątek oczekujący na dostęp do sekcji krytycznej blokuje dostęp drugiemu wątkowi).

## Zadanie 4
:::success
Autor: Maria Szlasa
:::
****
Rozwiązanie problemu sekcji krytycznej musi spełnić trzy warunki:

1. **Wzajemne wykluczanie** Jeśli proces $P_i$ działa w swojej sekcji krytycznej, to żaden inny proces nie działa w sekcji krytycznej.
2. **Postęp** Jeśli żaden proces nie działa w sekcji krytycznej oraz istnieją procesy, które chcą wejść do sekcji krytycznych, to tylko procesy nie wykonujące swoich reszt mogą kandydować jako następne do wejścia do sekcji krytycznych i wybór ten nie może odwlekany w nieskończoność.
3. **Ograniczone czekanie** Musi istnieć wartość graniczna liczby wejść innych procesów do ich sekcji krytycznych po tym, gdy dany proces zgłosił chęć wejścia do swojej sekcji krytycznej i zanim uzyskał na to pozwolenie.
****
Zobaczmy, jak algorytm będzie wyglądał dla procesów $P_0$ i $P_1$

Uzasadnienie poprawności:
1. **Wzajemne wykluczenie**
Jeden z dwóch procesów wchodzi do sekcji krytycznej wtedy i tylko wtedy, kiedy flaga procesu przeciwnego ma wartość false lub gdy zmienna numer zawiera jego identyfikator. Może zaistnieć sytuacja, w której oba procesy będą miały ustawione flagi, ale zmienna numer może przyjąć tylko jedną wartość, a więc jeden z nich będzie wykonywał pętlę while, a drugi wejdzie do sekcji krytycznej.
2. **Postęp**
Załóżmy, że proces o numerze 0 chce wejść do sekcji krytycznej, a proces o numerze 1 nie jest nią zainteresowany (bo wykonuje swoją resztę). Zmienna numer będzie miała wartość 1, ale flaga procesu o numerze 1 nie będzie ustawiona, a więc proces 0 nie zostanie powstrzymany przed wejściem do sekcji krytycznej.
3. **Ograniczone oczekiwanie**
Instrukcja przypisania (flaga\[id] = false) z sekcji wyjściowej gwarantuje, że proces będzie czekał na wejście do sekcji krytycznej tylko do momentu, gdy drugi z procesów zakończy swoją sekcję krytyczną i wykona sekcję wyjściową.

## Zadanie 5
:::success
Autor: Piotr Gunia
:::

void lock(){
    turn = other_id;
    flag[my_id] = true;
    while(flag[other_id] && turn == other_id);
}


**Postęp:** TAK

Wartość turn może mieć jedną wartość - ktoś zostanie wpuszczony

**Ograniczone czekanie:** TAK

Pierwszy wątek który będzie miał możliwość wykonania się przepuśi drugi ustawiając turn.

**Wzajemne wykluczenie:** NIE

Process 1: turn = 0
Process 0: turn = 1
Process 0: flag[0] = true
Process 0: while(flag[1] && turn==1)
Process 0: enter critical section 0
Process 1: flag[1] = true;
Process 1: while(flag[0] && turn==0)
Process 1: enter critical section 1

## Zadanie 6
:::success
Autor: Mateusz Burdyna
:::


void lock(int my_id) {
    flag[my_id] = true;
    turn = my_id;
    while(flag[1 - my_id] == true && turn == 1-my_id);
}

void unlock(int my_id) {
    flag[my_id] = true;
}

- Mutual Exclusion
Kontrprzykład:

P0: flag[0] = true
P0: turn = 0
P0: while(flag[1] == true && turn == 1) // pętla się przerywa
P0: Wchodzi do CS
P1: flag[1] = true
P1: turn = 1
P1: while(flag[0] == true && turn == 0) // pętla się przerywa
P1: Wchodzi do CS

- Progression
Zachowane, bo turn nie może być jednocześnie 0 i 1.

- Bounded Waiting
Kontrprzykład

P1: flag[1] = true;
P1: turn = 1;
P0: flag[0] = true;
P0: turn = 0;
P0: while(flag[1] == true && turn == 1) //przerywa się
P0: wchodzi do CS
P1: while(flag[0] == true && turn == 0) //czeka
P0: flag[0] = true
P0: turn = 0
P0: while(flag[1] == true && turn == 1) //przerywa się
P0: wchodzi do CS
P1: while(flag[0] == true && turn == 0) //czeka
...

## Zadanie 7
:::success
Autor: Kamila Brzozowska
:::


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;
}


Wzajemne wykluczenie :heavy_check_mark:
Proces może wejść do sekcji krytycznej tylko wtedy, gdy wartość `turn` jest równe `my_id`. Wartość ta zmienia się, gdy drugi proces opuszcza sekcję krytyczną.

Postęp :heavy_check_mark:
Gdy oba procesy rozpoczną czekają na wejście do secji krytycznej (ustawią `flag[my_id] = true`), proces, który ma `my-id != turn` zwolni `flag`, pozwalając temu drugiemu wejście do sekcji krytycznej.

Ograniczone czekanie :x:

P0

flag[0] = false;               (5)
while (turn != 0);             (6)
flag[0] = true;            (7)

P1
unlock(1);
    turn = 0;                  (13)
...
lock(1);
    while (flag[0] == true);   (3)
...
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: Jan Dalecki
:::

:::info
Oto implementacja protokołu wzajemnego wykluczania
przy pomocy instrukcji maszynowej TestAndSet. Przeanalizuj ją i
stwierdź, które z pozostałych dwóch warunków poprawnego
rozwiązania problemu sekcji krytycznej zawodzą. Procesy
współdzielą zmienną lock, o początkowej wartości false.
:::

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 - zachowany

Jedyna możliwość aby procesy nie mogły dostać się do sekcji krytycznej następuje, gdy zmienna lock jest ustawiona na true. Na początku wykonywania zmienna lock jest ustawiona na false zatem jeden proces dostanie się do sekcji krytycznej. Każdy proces opuszczający sekcję krytyczną zmienia wartość lock na false. W tym momencie jeżeli są procesy czekające na dostęp do sekcji krytycznej to proces który pierwszy wykona TestAndSet będzie mógł ją wykonać.

#### Ograniczone czekanie - niezachowane
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.

## Zadanie 9
:::success
Autor: Adam Ciężkowski
:::



* **Mutual-exclusion**: do sekcji krytycznej wejdziemy tylko jeśli żaden inny proces jej nie wykonuje (jeśli wykonywał, to zrobił unlock i "pozwolił" nam tam wejść).
* **Progress**: Albo żaden proces nie chce przejść do sekcji krytycznej, albo przechodzą do niej "cyklicznie". Jeśli któryś z procesów wykonuje unlock, to wpuszcza kolejny. Jeśli jakiś proces chce wejść do sekcji krytycznej, a żadne inne jej nie wykonują, to po prostu tam wchodzi i ustawia zmienną lock.
* **Bounded-waiting**: procesy są wykonywane "cyklicznie" - jeśli jakiś chce się wykonać, to wystarczy, że poczeka na swoją kolej