---
# System prepended metadata

title: 'Ćwiczenia 2, grupa śr. 16-18, 16 października 2024'
tags: [pwit, ćwiczenia, PRW24]

---

# Ć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


:::

![](https://hackmd.io/_uploads/r1p4u0sZa.png)

### 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	
:::
![image](https://hackmd.io/_uploads/HJ4djHp1kg.png)

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	
:::
![image](https://hackmd.io/_uploads/S1Apor6Jkl.png)
![image](https://hackmd.io/_uploads/rymHJIT1kx.png)

```JAVA=
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	
![image](https://hackmd.io/_uploads/HJzJnHayJg.png)

:::

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

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


![obraz](https://hackmd.io/_uploads/Hk1NYbTykg.png)

![obraz](https://hackmd.io/_uploads/rJZgsbTJye.png)


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	
![462544421_1259048361937563_5734125976861314530_n](https://hackmd.io/_uploads/S1wc3STkkg.png)

:::

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


