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

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

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


**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.


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


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




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


**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.

***
**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)\}$
***

**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)\}$
***

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

***

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