---
# System prepended metadata

title: 'Ćwiczenia 5, grupa cz. 16-18, 16 listopada 2023'
tags: [pwit, ćwiczenia, PRW23]

---

# Ćwiczenia 5, grupa cz. 16-18, 16 listopada 2023

###### tags: `PRW23` `ć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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk           |       |   X  |     |   X  |  X   |  X   |  X   |     |  
Paweł Borek              |    X   |  X   |     |  X   |     |     |     |     |  
Arti Brzozowski          |       |     |     |     |     |     |     |     |  
Mateusz Golisz           |       |     |     |     |     |     |     |     |  
Kacper Jóźwiak           |    X  | X   | X   |  X  | X   | X   |     |     |  
Julia Konefał            |       |     |     |     |     |     |     |     |  
Adam Korta               |   x    |     |     |  x   |  x   |  x   |     |     |  
Jakub Mikołajczyk        |   X   |  X  |     |  X  |  ==X==  |  X  |  X  |     |  
Bartosz Morasz           |       |     |     |     |     |     |     |     |  
Andrzej Morawski         |   x   |  x  |  x  |  x  |  x  |  x  |     |     |  
Aleksandra Nicpoń        |    x  |     |     |  x  |  x  |  x  |     |     |  
Mateusz Reis             |    X  |  X  |  X  |  X  |  X  |     |     |     |  
Tomasz Stachurski        |    x   |   x  |   x  |  x   |   x  |   x  |  ==x==   |     |  
Marcel Szelwiga          |   X    |  X   |  X   |  X   |  X   |  X   |   X  |   X  |  
Volha Tsekalo            |    x  | x   |     |  ==x==  |  x  |   x |  x  |     |  
Martyna Wybraniec        |    x  |     |     |  x  |  x  |  x  |  x  |     |  
Denys Zinoviev           |       |     |     |     |     |     |     |     |  
Dominik Olejarz          |    x  |   x  |     |  x   |   x  |  x   |   x  |     |  
:::





Tutaj można zadeklarować zadanie 7 z listy 4:
:::success
|                        | 4.7     | 
| ----------------------:| -----   |
|                        |         |  
|                        |         |  
|                        |         |  
|                        |         |  
:::





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



## Zadanie 1
:::success
Autor: Paweł Borek	
:::
![image](https://hackmd.io/_uploads/Hyw7Qh7N6.png)

```java=
class IQueue<T> {
	AtomicInteger head = new AtomicInteger(0);
	AtomicInteger tail = new AtomicInteger(0);
	T[] items = (T[]) new Object[Integer.MAX_VALUE];
	
	public void enq(T x) {
		int slot;
		do {
			slot = tail.get();
		} while (!tail.compareAndSet(slot, slot+1));
		items[slot] = x;
	}
	
	public T deq() throws EmptyException {
		T value;
		int slot;
		do {
			slot = head.get();
			value = items[slot];
			if (value == null)
				throw new EmptyException();
		} while (!head.compareAndSet(slot, slot+1));
		return value;
	}
}
```

Diagram:
```
compareAndSet(slot, slot+1)         items[slot] = x
     ↓                                          ↓ 
A: [          q.enq(x)                            ]
B:    [ q.enq(y) ]    [ q.deq : EmptyException ]
```

Historia G(=H):
```
A q.enq(x)
B q.enq(y)
B q: void
B q.deq()
B q: throws EmptyException
A q: void
```

Historia S:
```
  (1)
B q.enq(y)
B q: void
  (2)
B q.deq()
B q: throws EmptyException
  (3)
```

Nie ważne gdzie ((1), (2) czy (3)) wstawimy
```
A q.enq(x)
A q: void
```
to i tak S nie będzie legalną historią, bo nie spełnia sekwencyjnej specyfikacji `IQueue`.  Tj. zgłasza wyjątek `EmptyException` w momencie gdy kolejka nie jest pusta.  Skoro H nie da się rozszerzyć do G równoważnej z legalną sekwencyjną historią S, to H nie jest linearyzowalna.

## Zadanie 2
:::success
Autor: Dominik Olejarz	
:::
![image](https://hackmd.io/_uploads/HkTlmh74T.png)
![image](https://hackmd.io/_uploads/HyPGmnQEp.png)
a)
int i = tail.getAndIncrement();
wA : |A.enq(x)----------------|
wB : ---  |B.enq(y)|  |B.deq(y)|
Jeżeli chcielibyśmy zlinearyzować tą  względem pierwszej instrukcji metody enq() 
otrzymamy nastepującą kolejność:

A: enq(x)
B: enq(y)
B: deq(y)
Ponieważ wątek B jako piewszy przed wątekiem A zapisze swoją zmienną do kolejki to podczas wykontywania metody deq() kolejka zwróci wartość y, ponieważ cały czas komurka x bedzie rowna  null. 

b)
items[i].set(x);
wA : |------A.enq(x)-------|
wB : --  |B.enq(y)|        |B.deq(x)|

Jeżeli chcielibyśmy zlinearyzować tą  względem drugiej instrukcji metody enq() 
otrzymamy nastepującą kolejność:

B: enq(y)
A: enq(x)
B: deq(x)
Pomimo, że wątek B zapisuje zmienną y do pamięci wcześniej niż wątek A, to index elementu x będzie mniejszy zatem podczas wyciągania elementu z kolejki najpierw zostanie wyciągnięty element x.Zatem jest to sprzeczne. Wedlug linearyzacji kolejnosc elementow powinna byc y x


## Zadanie 3
:::success
Autor: Kacper Jóźwiak	
:::
W dowodzie poprawności `HWQueue<T>` przydadzą się następujące obserwacje
wynikające z atomowości metod:

1. `getAndIncrement` gwarantuje, że wartości będą wstawiane do osobnych komórek,
   czyli do dowolnej komórki element będzie wstawiony przez co najwyżej jeden
   wątek.
2. Podobnie `getAndSet` zapewnia, że każdy element będzie zdjęty przez co
   najwyżej jeden wątek.

Dodatkowo wiemy, że wszystkie elementy kolejki znajdują się pod indeksami
od 0 do tail, dlatego metoda `deq` je wyciągnie.

Teza: $\text{enq}(x) \rightarrow \text{enq}(y) \implies \text{deq}(x) \rightarrow \text{deq}(y)$

Dowód: Założmy nie wprost, że $\text{enq}(x) \rightarrow \text{enq}(y)$ oraz $\text{deq}(y) \rightarrow \text{deq}(x)$.

Z pierwszego założenia wynika, że $x$ znajdzie się pod indeksem mniejszym niż
indeks, pod którym jest $y$. Zatem mamy następujący porządek $\text{enq}(x)
\rightarrow \text{enq}(y) \rightarrow \text{deq}(y) \rightarrow \text{deq}(x)$.
W szczególności zachodzi $\text{enq}(x) \rightarrow \text{deq}(y)$

Niemniej wiemy z kodu, że w takim wypadku `deq` trafi w swojej pętli `for` na
element $x$ przed elementem $y$.

Drugim przypadkiem byłaby sytuacja gdy wywołania `enq` na siebie nachodzą, ale tę sytuację rozważyliśmy w zadaniu 2.


## Zadanie 4
:::success
Autor: Volha Tsekalo
:::
Nieczekanie - każda operacja skończy się w skończonej liczbie kroków.

Niewstrzymanie - cały system dokonuje postępu, ale konkretny wątek niekoniecznie.

Nieblokujące - wstrzymanie jednego procesu (wątku) nie spowoduje wstrzymanie innych.

Niezależne - nie zależą od systemu operacyjnego.

Niezakleszczenie i niezagłodzenie są blokujące, dlatego że zablkowanie jednego wątku może spowodować zablokowanie innych i zależne, bo zależą od tego, czy system operacyjny sprawiedliwie przydziela czas procesora.

Czy współbieżna metoda w nietrywialny
sposób wykorzystująca zamki może być nieczekająca? Nie, bo niektóre wątki nie będą robić progresu.

Metoda weird() jest nieczekająca (wykona się po skończonej liczbie kroków), ale nie jest nieczekająca z limitem kroków, ponieważ 2^i nie jest stałą.

## Zadanie 5
:::success
Autor: Jakub Mikołajczyk	
:::

```java=
class Reg64bit {
    Reg32bit reg1, reg2;
    
    read() {
        val = reg1;
        val += reg2 << 32;
        return val;
    }
    
    write(x) {
        reg1 = x;
        reg2 = x >> 32;
    }
}
```

Rejest jest bezpieczny, ponieważ w przypadku niewspółbieżnych wywołań zawsze zwraca wartość ostatnio zapisaną.

Rejest nie jest regularny, ponieważ w przypadku wpółbieżnego odczytu i zapisu może zwrócić wartość, która nigdy wcześniej nie została zapisana.

Skoro nie jest regularny to nie jest atomowy.

## Zadanie 6
:::success
Autor: Andrzej Morawski	
:::

```java=
public void lock() {
    flag[i] = true;
    victim = i;
    while (flag[j] && victim == i) {}
}

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

Czy algorytm Petersona spełnia warunki wzajemnego wykluczania i niezagłodzenia, gdy dla $flag[0]$ i $flag[1]$ użyjemy rejestrów regularnych?

Rozpatrzmy przypadki:

**1. Zapis do komórek i odczyty są rozłączne**
Algorytm działa tak samo jak dla rejstrów atomowych.

**2. Zapis do komórek i odczyty zachodzą na siebie**

Rozpatrzmy następujące wykonanie metody $lock()$:

$Write_A(flag[A]=True) \rightarrow Write_A(vicitm=A) \rightarrow ...$

Następnie wątek B wywołuje metodę $lock()$ i wykonuje $Write_B(flag[B] = True)$

W tym czasie wątek A odczytuje wartości zmiennych w pętli while. Musimy rozpatrzyć dwa przypadki w których wątek A odczytuje nową i starą wartość zmiennej $flag[B]$

* $flag[B] == False$

Wątek $A$ wchodzi do sekcji krytycznej, natomiast wątek $B$ po ustawieniu zmiennej $victim$ będzie czekał na swoją kolej do wejścia do SK.

* $Flag[B] == True$

W takiej sytuacji do momentu ustawienia przez wątek B zmiennej $victim$ wątek A będzie czekał w pętli. Gdy wątek $B$ wykona $Write_B(victim=B)$ to wątek A będzie mógł wejść do sekcji krytycznej.


## Zadanie 7
:::success
Autor: Tomasz Stachurski	
:::

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


Do przechowywania 1-regularnego SRSW potrzeba 2 M-wartości, z czego pierwsza będzie reprezentować aktualną wartość, a druga poprzednią. 
Dodatkowo skorzystamy z dodatkowej zmiennej (np. *which*), która będzie wskazywać, która z tych wartości jest najświeższa.

Mamy zatem 2log(m) + 1, czyli O(log(m)) boolowskich rejestrow.

**read()** - czyta wartość `which` i zwraca `rejestr[which]`
**write()** - czyta wartość `which`, który rejestr jest aktualny i zapisuje nową wartość do starego rejestru. Na końcu neguje `which`

Przypadki:
1. **read() który nie jest współbieżny** - czyta `rejestr[which]`
2. **read() współbieżny z dokładnie 1 write()** - czyta `rejestr[which]`, czyli jeśli write() zdążył zmienić wartość `which` to read() odczyta nową wartość, wpp. starą
3. **read() współbieżny w wieloma write()** - czyta `rejestr[which]`, czyli zwróci dowolną wartość, bo write() ciągle zmienia `which`

## Zadanie 8
:::success
Autor: Marcel Szelwiga	
:::
W zadaniu mamy *dobry* rejestr. Rejestr nazwiemy *dobrym*, jeśli dla każdego ciągu współbieżnych dostępów do tego rejestru (zapisów i odczytów) każda wartość odczytana występuje wśród wartości zapisanych (tzn. wartości odczytane nie biorą się “z powietrza”).

Rejestr regularny to taki, w którym gdy read i write się nakładają to dostajemy wartość nową lub poprzednią (tą sprzed zapisu).

* Własność (1) nie istnieje takie $i$, że $R^i \rightarrow W^i$.

* Własność (2) nie istnieją takie $i$, $j$, że $W^i \rightarrow W^j \rightarrow R^i$.

Chcemy pokazać, że nasz rejestr jest regularny $\Leftrightarrow$ rejestr ma własności (1) i (2);

Dowód przeprowadzimy poprzez pokazanie implikacji w dwie strony:

Rejestr jest regularny $\Rightarrow$ rejestr ma właności (1) i (2).

* (1) Zakładamy nie wprost, że istnieje takie $i$, że $R^i \rightarrow W^i$.
Z definicji $R^i$ zwraca to co zapisal $W^i$, a z regularności mamy, że zwracamy poprzedni lub aktualny, biorąc pod uwagę, że mamy jedno $W^i$ to zachodzi oczywista sprzeczność.

* (2) Zakładamy nie wprost, że istnieje takie $i$, $j$, że $W^i \rightarrow W^j \rightarrow R^i$.
Regularny rejestr zwraca wartość poprzednią lub aktualną jednak skoro $W^j \rightarrow R^i$ to wiemy, że aktualne jest $W^j$, zachodzi więc oczywista sprzeczność.

Dobry rejestr z własnościami (1) i (2) $\Rightarrow$ rejestr regularny.
Rozważmy dwa przypadki: 

* Odczyt nie jest współbieżny z żadnym zapisem.
Załóżmy wtedy nie wprost, że odczytał z innego zapisu niż z poprzedniego. Z faktu, że rejestr jest dobry wiemy, że wartość musi pochodzić z jakiegoś zapisu. 
Jeśli odczytana pochodzi z przyszłego zapisu to mamy sprzeczność na podstawie (1).
W przeciwnym przypadku mamy sprzeczność na podstawie (2).

* Odczyt $R^i$ jest współbieżny z zapisami $W^a, W^b, \dots W^z$.
Przez $W^A$ oznaczmy ostatni zapis nie współbieżny z $R^i$. Na podstawie (1) wiemy, że zapis nie pochodzi z przyszłości co w połączeniu z faktem, że rejestr jest dobry wiemy, sprawia że odczytana wartość pochodzi z jednego z zapisów $W^a, W^b, \dots W^z$ lub $W^A$ lub zapisu $W^B$ takiego, że $W^B \rightarrow R^i$. Jednak na podstawie (2) wiemy, że opcja odczytu z $W^B$ nie jest możliwa, ponieważ ostatni zapis to $W^A$. 