---
# System prepended metadata

title: 'Ćwiczenia 4, grupa śr. 16-18, 16 listopada 2022'
tags: [PRW22, pwit, ćwiczenia]

---

# Ćwiczenia 4, grupa śr. 16-18, 16 listopada 2022

###### tags: `PRW22` `ć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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Daniel Boguszewski       |   X   |  X  |  X  |     |  X  |     |  
Marcin Dąbrowski         |       |     |     |     |     |     |
Jakub Gałecki            |       |     |     |     |     |     |
Kamila Goszcz            |   X   |  X  |  X  |     |  X  |  X  |
Wiktor Hamberger         |       |     |     |     |   X |   X |
Jan Jankowicz            |       |     |     |     |     |     |
Mikołaj Jaszcza          |   X   |  X  |  X  |     |  X  |  X  |
Zuzanna Kania            |   X   |  X  |     |     |  X  |  X  |
Wiktoria Kuna            |       |     |     |     |     |     |
Patryk Mazur             | ==X== |   X |  X  |     |  X  |  X  |
Hubert Obrzut            |   X   |  X  |  X  |  X  |  X  |  X  |
Magdalena Rzepka         |   X   |  X  |  X  |     |  X  |  X  |
Joanna Stachowicz        |   X   |  X  |  X  |     |==X==|  X  |
Rafał Starypan           |   X    |  X   |  X   |     |  X   |  X   |
Maria Szlasa             |   X   |  X  |  X  |     |  X  |  X  |
Daniel Wiczołek          |   X   |  X  |  X  |  X  |  X  |  X  |
Adam Jarząbek            |   X    |     |     |     |     |     |
:::



**Poniżej można zadeklarować zadanie 8 z listy 3:**
- Magdalena Rzepka


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




## Zadanie 1
:::success
Autor:	Patryk Mazur	
:::
![](https://i.imgur.com/nZXYHuN.png)
![](https://i.imgur.com/Ze1Cswc.png)

Lemat:
Dla $i$ (od $0$ do $n-1$) jest co najwyżej $n-i$ wątków na poziomie $i$.

Dowód indukcyjny po poziomach:

Przypadek bazowy:

Na poziomie $0$ jest $n-0$ wątków

Krok Indukcyjny

Z założenia indukcyjnego
Na poziomie $i-1$ jest co najwyżej $n-i+1$ wątków

Załóżmy nie wprost, że na poziomie $i$ jest $n-i+1$ wątków

Niech $A$ będzie ostatnim wątkiem na poziomie $i$, który ustawił $victim[i]$
Zatem dla każdego $B$ na poziomie $i$ następuje:

$$write_B(victim[i]) \rightarrow write_A(victim[i])$$

Z kodu:

$$write_b(level[B] = i) \rightarrow write_B(victim[i]) \rightarrow write_A(victim[i])$$

$$write_b(level[B] = i) \rightarrow write_B(victim[i]) \rightarrow write_A(victim[i]) \rightarrow read_A(level[B])$$

Za każdym razem, gdy $A$ odczytuje $level[B]$ widzi wartość większą lub równą $i$ (Ponieważ $B$ jest na poziomie $i$)
Zatem $A$ nie mogłoby opuścić pętli, co przeczy z naszym założeniem.

Skoro na poziomie $n - i$ znajduje się jednocześnie co najwyżej $i$ wątków, a sekcja krytyczna jest poziomem $n-1$. To znaczy że algorytm spełnia warunek wzajemnego wykluczenia. 
($n-(n-1)=1$)


## Zadanie 2
:::success
Autor:	Daniel Boguszewski	
:::
![](https://i.imgur.com/V89b8eW.png)

Niezagłodzenie: Jeśli wątek próbuje wejść do SK, zrobi to w skończonym czasie
Załóżmy, że wątek $k$ zamierza wejść do SK. Z definicji metody $lock$, znajdzie się na jednym z poziomów $1..n-1$.
Jeśli na wyższych poziomach nie znajduje się żaden wątek, wtedy $k$ przechodzi wyżej (wątki będące wyżej mają swego rodzaju pierwszeństwo). W innym wypadku czeka, aż przestanie być ofiarą (inny wątek wejdzie na dany poziom), w zależności od tego, co się stanie szybciej.
Po pewnym czasie wątek $k$ będzie musiał przejść poziom wyżej.
Ponieważ liczba poziomów jest ograniczona, wątek $k$ w końcu dotrze na poziom $n-1$, a tam będzie się znajdował nie więcej niż 1 inny wątek, to $k$ na wejście do SK z tego poziomu będzie czekał nie dłużej, niż czas przebywania aktualnego wątku w SK. Mógłby wejść od razu, gdyby SK była wolna. QED.

Niezakleszczenie: Do SK, jeśli jest wolna, zawsze wejdzie pewien wątek. 
Do poziomu $n-1$ zawsze dociera przynajmniej jeden wątek, a maksymalnie 2.
Jeden z nich zostaje dopuszczony do SK. QED.

## Zadanie 3
:::success
Autor:	Kamila Goszcz	
:::

![](https://i.imgur.com/RymV9Of.png)

**r-Bounded Waiting**  to górne ograniczenie na ilość wątków, które mogą uzyskać dostęp do CS przed wątkiem A mimo że same zgłosiły chęć uzyskania dostępu później.

![](https://i.imgur.com/1GVRGKh.png)

Wątki 1, 2, 3 chcą wejść do CS, `victim[1] = 3`, jeden z pozostałych wątków (bez straty ogólności załóżmy, że to wątek 1) dostaje się do CS, wychodzi z niej i ponownie chce wejść do CS (`victim[1] = 1`), teraz wątek 2 może wejść do CS, wyjść i ustawić (`victim[1] = 2`). Zauważmy, że uwolniliśmy teraz wątek 1 z victim. Zatem dopóki wątek 3 nie otrzyma czasu procesora to będzie przepuszczał na zmianę wątki 1 i 2.

Zagłodzenie jest wtedy, gdy to inne wątki blokują dostęp do sekcji krytycznej. W tym wypadku jeżeli któryś z pozostałych wątków ustawi na siebie zmienną victim oraz wątek 3 otrzyma czas procesora to napewno zmieni poziom. 

## Zadanie 4
:::success
Autor:	Daniel Wiczołek	
:::

![](https://i.imgur.com/6S5peBs.png)
![](https://i.imgur.com/xNuT1Yx.png)

1. przypomnienie
Załóżmy $D_{A}^k → D_{B}^j$
Przypomnienie: $→$ zachodzi tylko gdy nienachodzą na siebie.
następnie 
a) 
$readA(flag) → writeB(flag)$ więc wykonuje się $readA(flag)$ czyli $CS_{A}^k → CS_{B}^j$
b) 
$writeB(flag) → readA(flag)$ ale to oznacza, że nastąpi $writeB(victim)$, więc $readA(victim) \neq A$, więc $CS_{A}^k → CS_{B}^j$

2. nie, bo może być tak, że:

- A: ustawia flagę, (czyli $D_{A}^k → D_{B}^j$) 
- B obie linijki,
- A victim 
- B wchodzi


3. Załóżmy nie wprost, że istnieje.
- **odczyt tej samej komórki pamięci lub różnych komórek, w zależności od wątku**
    - **a) odczyt tej samej**
        - A odczytał pierwszy wiec wszedl 1szy -- tylko 1 chcial wejsc
        - B odczytał A odczytał, stan sie nie zmienił w por. z powyzszym więc A wszedl pierwszy, 
        - sprzecznosc z **FCFS**
    - **b) roznych**
        - A odczytał swoją i wszedl -- tylko 1 chcial wejsc
        - B swoją A odczytal swoją stan sie nie zmienil od powyzszego przypadku wiec A wszedl, 
        - sprzecznosc z **FCFS**

- **zapis do różnych komórek**
    - B zapis A zapis B pierwszy wiec wszedl (bo FCFS)
    - A zapis B zapis A wchodzi bo FCFS
    - stan ten sam w obu przypadkach po zapisach, bo rozne komorki wiec oba musza wejsc, 
    - sprzecznosc z **mutex**

- **zapis do tej samej komórki**
    - A zapis, B zapis A wchodzi
    - B zapis B wchodzi
    - oba ten sam stan wiec w 1. B powinien wejsc 
    - sprzeczne z **mutex**.

4. Nie istnieje algorytm FCFS z tą definicją sekcji wejściowej. W porównaniu do oryginalnej definicji skróciliśmy ją o stałą liczbę instr.

## Zadanie 5
:::success
Autor:	Joanna Stachowicz	
:::
![](https://i.imgur.com/RANEzka.png)

![](https://i.imgur.com/QlhhkGT.png)

![](https://i.imgur.com/r3rfIGs.png)

![](https://i.imgur.com/ZXIZRrs.jpg)



## Zadanie 6
:::success
Autor:	Maria Szlasa	
:::

:::info
Powtórz zadanie 5, tym razem używając formalnej definicji linearyzacji (slajd 132). Dla każdego diagramu zdefiniuj odpowiadającą mu historię 𝐻. Jeśli to możliwe, zdefiniuj historię 𝐺 oraz legalną sekwencyjną historię 𝑆 spełniające warunki z definicji.
:::

![](https://i.imgur.com/OTieVQj.png)
![](https://i.imgur.com/kSM9uyN.png)


**Linearyzacja** formalna definicja 
* Historia $H$ jest linearyzowalna jeśli może być zmodyfikowana do historii $G$ przez:
    * dodanie 0 lub więcej powrotów do oczekujących wywołań
    * usuwanie oczekujących wywołań

* Zatem historia $G$ jest równoważna względem legalnej/poprawnej sekwencyjnie historii $S$ takiej, że $\rightarrow_G {\subset} \rightarrow_S$

***
W naszych przykładach nie ma niedokończonych wywołań funkcji, daltego nie będziemy rozszerzać H do G.

***
![](https://i.imgur.com/O3vLTth.png)
**Formalnie**
Mamy historie $H$ i równoważną poprawnej sekwencyjnie historii $S$:
```
Historia H      Historia S
B r.write(1)    B r.write(1)
A r.read(1)     B r: void
C r.write(2)    A r.read()
A r: 1          A r: 1
B r: void       C r.write(2)
C r: void       C r: void
B r.read(2)     B r.read()
B r: 2          B r: 2
```

oraz ${\rightarrow}_H \subset \rightarrow_S$
* $\rightarrow_H = \{B.write(1) \rightarrow B.read(2), A.read(1) \rightarrow B.read(2), C.write(2) \rightarrow B.read(2)\}$
* $\rightarrow_S = \{B.write(1) \rightarrow A.read(1) \rightarrow C.write(2) \rightarrow B.read(2)\}$
***

![](https://i.imgur.com/KL5vYth.png)
**Formalnie**
Mamy historie $H$ i równoważną poprawnej sekwencyjnie historii $S$: 
```
Historia H      Historia S
B r.write(1)    C r.write(2)
A r.read(1)     C r: void
C r.write(2)    B r.write(1)
A r: 1          B r: void
C r: void       A r.read()
B r: void       A r: 1
B r.read(1)     B r.read()
B r: 1          B r: 1
```

oraz ${\rightarrow}_H \subset \rightarrow_S$
* $\rightarrow_H = \{C.write(2) \rightarrow B.read(1), B.write(1) \rightarrow B.read(1), A.read(1) \rightarrow B.read(1)\}$
* $\rightarrow_S = \{C.write(2) \rightarrow B.write(1) \rightarrow A.read(1) \rightarrow B.read(1)\}$
***

![](https://i.imgur.com/g1CYP7D.png)
**Formalnie**
Mamy historie $H$, którą nie możemy rozszerzyć do równoważnej poprawnej sekwencyjnie historii $S$, w której wcześniej wyciągamy element $x$ z $p$. 
```
A p.enq(x)
A p: void
B p.enq(y)
B p: void
A p.deq()
A p: y
```

***

![](https://i.imgur.com/6gHGZ1i.png)
**Formalnie**
Mamy historie $H$, którą nie możemy rozszerzyć do równoważnej poprawnej sekwencyjnie historii $S$, w której instrukcje wykonają się poprawnie.
```
A p.enq(x)
A p: void
B q.enq(y)
B q: void
A q.enq(x)
A q: void
B p.enq(y)
B p: void
A p.deq()
A p: y
B q.deq()
B q: x
```
