# Ćwiczenia 2, grupa śr. 16-18, 16 października 2024

###### tags: `PRW24` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Bartosz Borecki | X | X | X | X | X | | X | X | |
Miriam Bouhajeb | X | X | X | X | | | | | |
Marceli Buczek | X | X | X | X | X | | X | X | |
Maciej Ciepiela | X | X | X | X | X | | X | X | |
Maciej Dominiak | X | X | X | X | X | | X | X | |
Michał Hajahmadov | X | X | X | ==X== | | | X | X | |
Adam Majchrowski | X | X | X | X | ==X== | | X | X | X |
Hanna Makowska | X | X | X | X | X | | X | ==X== | |
Cezary Miłek | X | X | X | X | X | | X | X | |
Błażej Molik | X | X | X | X | X | | X | X | |
Konrad Oleksy | X | X | X | X | | | | | |
Kacper Osadowski | X | X | X | X | | | X | X | |
Yurii Pryimak | | | | | | | | | |
Aliaksandr Tyszecki | | | | | | | | | |
Miłosz Urbanik | X | X | X | X | | | X | | |
Yana Vashkevich | | | | | | | | | |
Piotr Warząchowski | X | X | X | X | | | | | |

:::

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

## Zadanie 1
:::success
Autor: Konrad Oleksy

:::


### Wzajemne wykluczanie

Dowód nie w prost

Załóżmy, że oba wątki są wchodzą do sekcji krytycznej

Z kodu:

write_A(turn = A) -> read_A(busy==false) -> write_A(busy=true) -> read_A(turn == A) -> CS_A
write_B(turn = B) -> read_B(busy==false) -> write_B(busy=true) -> read_B(turn == B) -> CS_B

Założenia:

read_A(turn = A) -> write_B(turn = B)
read_B(turn = B) -> write_A(turn = A)

Kolejność zdarzeń:

read_A(turn = A) -> write_B(turn = B)
write_B(turn = B) -> read_B(busy==false) -> write_B(busy=true) -> read_B(turn == B)
read_B(turn = B) -> write_A(turn = A)
write_A(turn = A) -> read_A(busy==false) -> write_A(busy=true) -> read_A(turn == B

Występuje cykl, który jeśli mamy porządek nie powinien sie pojawić

### Niezagłodzenie

Nie spełnia np w tym przyapadku:

1. write_A(turn =A)
2. read_A(busy == false)
3. write_A(busy = true)
4. read_A(turn == A)
5. write_B(turn =B)
6. read_B(busy == true)
7. CS_A
8. write_A(busy= false)
9. goto 1

### Niezakleszczanie

nie spełnia w przypadku:

1. write_A(turn =A)
3. read_A(busy == false)
2. write_B(turn =B)
3. read_A(turn == B)
5. write_A(busy = true)
6. read_B(busy == true)

## Zadanie 2
:::success
Autor: Miriam Bouhajeb
:::

a) zakleszczenie (brak)
Wątek zablokowany w while (flag[j] == true){}
Gdy sam jest w unlock to drugi wątek idzie dalej (flaga pierwszego zostaje opuszczona) a wątek także opuszcza swoją flagę.
Gdy oba w unlock to analogicznie, oba opuszczaja flagi i wychodza

b) zagłodzenie (jest)
wątek 0:
jest w unlock, sprawdza while (flag[1] == true)

wątek 1:
jest w lock, ustawia flag[1] = true
wchodzi do unlock, ustawia flag[1]=false, po czym sprawdza (flag[0] == true) i nie wchodzi do pętli. jak jest szybszy to może od razu zawołać lock() i znowu ustawić flag[1]=true

## Zadanie 3
:::success
Autor: Piotr Warząchowski

Własność r-ograniczonego czekania oznacza, że po tym, jak dany proces zgłosi chęć wejścia do sekcji krytycznej, nie może być zablokowany więcej niż przez r innych procesów, zanim sam wejdzie do tej sekcji. Innymi słowy, proces nie musi czekać dłużej niż określona liczba r innych procesów. Jeśli r=0r=0, oznacza to, że algorytm ma własność 0-ograniczonego czekania, co jest równoznaczne z tym, że procesy są obsługiwane w kolejności zgłoszeń (FCFS).

*Sekcja wejściowa* w algorytmie Petersona to część kodu, gdzie proces informuje o swojej chęci wejścia do sekcji krytycznej.

*Sekcja oczekiwania* to część, gdzie proces sprawdza, czy może wejść do sekcji krytycznej, czekając na spełnienie odpowiednich warunków.

Aby pokazać, że algorytm Petersona zapewnia własność *0-ograniczonego czekania* (jest FCFS), musimy pokazać, że procesy są obsługiwane w kolejności zgłoszeń.

#### Sytuacja, gdy oba procesy chcą wejść do sekcji krytycznej:

1. Jeśli proces \(i\) ustawi flag[i] = true i victim = i, a proces \(j\) również ustawi flag[j] = true, to w zmiennej victim ostatni zapis zostanie wykonany przez proces \(i\).

2. Z powodu mechanizmu "ofiary" (victim), proces, który ustawił się jako „ostatni” (tu \(i\)), będzie musiał poczekać. Proces \(i\) zostanie zablokowany w pętli while, ponieważ:
- flag[j] == true (proces \(j\) chce wejść do sekcji krytycznej),
- victim == i (proces \(i\) jest „ofiarą”).

3. W tej sytuacji proces \(i\) poczeka, a proces \(j\) będzie mógł wejść do sekcji krytycznej jako pierwszy. Po zakończeniu sekcji krytycznej przez \(j\), proces \(j\) ustawi flag[j] = false, co pozwoli procesowi \(i\) opuścić pętlę i wejść do sekcji krytycznej.

#### Sytuacja, gdy jeden proces chce wejść pierwszy:

Jeśli proces \(i\) chce wejść do sekcji krytycznej, a proces \(j\) nie ustawił jeszcze flag[j] na true, proces \(i\) od razu wejdzie do sekcji krytycznej, ponieważ warunek flag[j] == true będzie fałszywy.

-----

Załóżmy, że $D_A^{k} \rightarrow D_B^{j}$, ale wątek B wszedł do sekcji krytycznej wcześniej niż wątek A. Pokażemy, że to prowadzi do sprzeczności.

Dowód:

Ponieważ wątek B wszedł do sekcji krytycznej, to $read_B[flag[A] == false]$ lub $read_B[victim == A]$. Z założenia jest
$write_A[flag[A] == true] \rightarrow D_B^{j}$. Ponieważ $D_B^{j} \rightarrow W_B^{j}$ to jest $read_B[flag[A] == true]$.
A zatem, żeby wątek B wszedł do sekcji krytycznej wcześniej, niż wątek A, to musi być $read_B[victim == A]$. Ale tak nie jest, bo z $D_A^{k} \rightarrow D_B^{j}$ wynika, że $write_A[victim = A] \rightarrow write_B[victim=B]$. Sprzeczność

:::

## Zadanie 4
:::success
Autor: Michał Hajahmadov
:::

public void unlock() {
    flag[i] = false;
}

- Kiedy proces chce wejść do sekcji krytycznej, wybiera numer biletu, który jest większy niż numer biletu innych procesów
- Proces, który ma mniejszy numer biletu, ma pierwszeństwo w dostępie do sekcji krytycznej. Jeśli dwa procesy mają taki sam numer biletu, rozstrzyga się to na podstawie numeru procesu.

**1. Wzajemnie wykluczanie**
Załóżmy nie wprost, że wątek $A$ i wątek $B$ znalazły się w sekcji krytycznej w tym samym momencie i bez straty ogólności: label[$A$] < label[$B$] (*) .

Gdy B wchodziło do sekcji krytycznej, to flag[$A$] musiało być równe false (z *).

write$_B$(label[$B$] = $max(label[0], ..., label[n-1]) + 1)$ → read$_B$(flag[$A$] == false) → write$_A$(flag[$A$] = true) → write$_A$(label[$A$] = $max(label[0], ..., label[n-1]) + 1)$

sprzeczność z *.

**2. Niezakleszczanie**
Załóżmy nie wprost, że doszło do zakleszczenia. Zatem wszystkie zakleszczone wątki mają podniesione flagi i ustawione labele. Jeśli mają one takie same labele, to do CS wejdzie ten o najmniejszy numerze, a jeżeli nie, to ten z najemniejszym labelem.

**3. Niezagłodzenie**
Załóżmy nie wprost, że wątek A jest głodzony. To oznacza, że ma podniesioną flagę i ustawiony label (bo chce wejść). Rozpatrzmy 2 możliwe przypadki:
1. Jeśli żaden inny wątek nie ma podniesionej flagi, to wchodzimy.
2. Jeśli jakiś inny wątek ma podniesioną flagę, to wejdzie ten o najmniejszym labelu, a potem uwolni sekcję. Jest skończona ilość wątków, więc kiedyś wjedziemy do sekcji krytycznej.

(label(A), A)

Sprzeczność.

## Zadanie 5
:::success
Autor: Adam Majchrowski

:::

## Zadanie 6
:::danger
Autor: do zadeklarowania na następnych ćwiczeniach
:::

## Zadanie 7
:::success
Autor: Błażej Molik
:::



a) **Wzajemne wykluczanie** - nie zachodzi

Kiedy oba wątki mogą się znaleźć w sekcji krytycznej?

`write_0(x=0) => read_0(y==-1) => write_1(x=1) => read_1(y==-1) => write_0(y=0) => write_1(y=1)`

Zatem żaden wątek nie został zatrzymany przez pętlę while, czyli:

`read_1(x==1) => sekcja krytyczna`
`read_0(x!=0) => lock.lock => sekcja krytyczna`

b) **Niezagłodzenie** - nie zachodzi

`write_0(x=0) => read_0(y==-1) => write_0(y=1) => read_1(y!=-1)`

Jeżeli wątek 0 wyjdzie z sekcji krytycznej i będzie szybszy niż wątek 1, to wątek 1 może być zagłodzony.

c) **Niezakleszczenie** - zachodzi

Za każdym razem, gdy wątek opuszcza sekcję krytyczną, ustawia `y` na -1, więc jeśli jakiś wątek czeka, zobaczy to i wejdzie do sekcji krytycznej. Zatem nie będzie zakleszczenia.

## Zadanie 8
:::success
Autor: Hanna Makowska

:::

## Zadanie 9
:::success
Autor: Maciej Dominiak
:::
1. Rozpatrzmy jakiś obiekt klasy Bouncer, nazwijmy go B
Wiemy że istnieje taki zbiór wątków które wejdzą do B i otrzymają jakąś odpowiedź.
W szczególności zbiór ten może być pusty. Nazwijmy ten zbiór B_n. Niech m = |B_n|.

Jeżeli B zwróciło STOP dla wątku i, następny obiekt otrzymuje do przetworzenia zbiór B_n / { i }.
Gdyby B zawsze zwracało STOP dla jakiegoś wątku to w ostateczności B_n będzie zbiorem pustym.
Co oznacza iż wszystkie wątki otrzymały odpowiedź STOP

Wystarczy więc pokazać, że rzeczywiście B zawsze zwraca STOP dla jakiegoś wątku z B_n
Wiemy, że jeżeli wątek wejdzie do obiektu typu bouncer sam to zwróci nam STOP

Rozważmy więc taką sytuację gdy B nie zwraca STOP dla żadnego wątku.
Oznaczałoby to iż B musiało zawsze zwracać albo RIGHT albo DOWN.
Załżmy więc że nie istnieje taki wątek który otrzymałby odpowiedź STOP

musiało więc nastąpić jedna z dwóch sytuacji:
write_i( last = i ) -> read_i( goRight == false ) -> write_i( goRight = true ) -> read_i( last != i ) -> Return_i(DOWN)
write_i( last = i ) -> read_i( goRight == true ) -> Return_i(RIGHT)

Wiemy z poprzedniego zadania, że RIGHT oraz DOWN może być zwrócone maksymalnie n-1 razy
Aby wątek zwrócił Right musiałby istnieć inny który wszedł przed nim i ustawił zmienną goRight

Wystarczy jeden, jednakże może być ich więcej. Wybierzmy z nich tego który wszedł do przedsionka jako ostatni.
Jedyną sytuacją aby nie zwrócił Down musiałoby być że jakiś wątek nadpisał zmienną last - musiał to być wątek idący w prawą stronę.

Jednakże wiemy, że wątki mogą wykonywać akcje z różną prędkością więc raz za razembędzie działa się sytuacja że żaden wątek nie nadpisze zmiennej last i wątek ewentualnie zwróci Stop. Wtedy ilość elementów zbioru będzie się zmiejszać i dojdzie do 0 w skończonej ilości operacji

2. Dokładna ilość wierzchołków grafu
Powiedzmy, że mamy n wątków. zgodnie z wnioskami z poprzedniego zadania dostaniemy co najwyżej n-1 razy polecenie RIGHT i tyle samo DOWN
Więc tworzymy strukturę drzewa binarnego. Głębokość tego drzewa wynosi n;
Wtedy ilość wierzchołków to n * (n + 1)/ 2