---
# System prepended metadata

title: Współbieżne - Lista 6

---

# Współbieżne - Lista 6

:::success
## Zadanie 1
:::
![](https://i.imgur.com/pmJ2yDM.png)

### Zdefiniuj następujące własności postępu: nieczekanie (ang. wait-freeness),

Każde wywołanie metody zakończy się w skończonej liczbie kroków.

Tj. każdy wątek, który aktualnie się wykonuje, dokonuje postępu

### niewstrzymywanie (ang. lock-freeness).
Jakieś wywołanie metody (dla jakiegoś wątku) zakończy się w skończonej liczbie kroków.

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

### Dlaczego te własności nazywane są nieblokującymi (ang. non-blocking) i niezależnymi (ang. independent)?

Nieblokujące - bo nie dopuszczają możliwości, że któryś wątek będzie czekał (będzie zablokowany) na locka.

Niezależne - bo nie zależą od spełnienia jakiegoś warunku przez system operacyjny

### Dlaczego niezakleszczenie i niezagłodzenie są blokujące i zależne?

Blokujące - dopuszczają możliwość, że któryś wątek będzie czekał na locka

Zależne - zależą od spełnienia warunku przez system operacyjny (fair scheduling)

### Czy współbieżna metoda w nietrywialny sposób wykorzystująca zamki może być nieczekająca? 

Nie, bo jeśli wątek A zajmie lock i wątek B będzie na niego czekał, to B nie będzie dokonywał postępu.

### Dana jest metoda weird(), której każde i-te wywołanie powraca po wykonaniu 2^i instrukcji. Czy ta metoda jest nieczekająca? 

Tak, bo każde wywołanie zakończy się w skończonej liczbie kroków (po 2^i krokach)

### A nieczekająca z limitem kroków (ang. bounded wait-free)?

Nie, bo liczba kroków zależy od argumentu funkcji, więc nie możemy podać stałej ograniczającej liczbę kroków.
![](https://i.imgur.com/6x1os9U.png)

:::success
## Zadanie 2
![](https://i.imgur.com/QpY42Zj.png)
:::



1. **Bezpieczny**

Ponieważ komórki pamięci są rejestrami MRMW to może wystąpić sytuacja, że będą sie pokrywać dwa *write*

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


W tym przypadku do naszego 64-bitowego (złożonego z dwóch 32-bitowych) rejestru może zostać zapisana górna połowa bitów rejestru `w1` z jednego *write* i dolna połowa bitów rejestru `w2` z drugiego *write*. Gdy następnie zrobimy *read*, który się nie nakłada z nimi to oczekujemy, że dostaniemy dobrą wartość całego 64-bitowego rejestu ale zamiast tego czytamy połowę rejestu `w1` i połowę rejestru `w2`. Czyli warunek **bezpiecznego** rejestru jest **niespełniony**.

2. **Regularny**

Gdy rejestr nie jest bezpieczny to nie jest też regularny.

3. **Atomowy**

Gdy rejestr nie jest regularny to nie jest też atomowy.


## Zadanie 3
![](https://i.imgur.com/qO8P7nA.png)

## Rozwiązanie 1:
### Algorytm Petersona
```= java
public void lock() {
 flag[i] = true; 
 victim  = i; 
 while (flag[j] && victim == i) {};
}
public void unlock() {
 flag[i] = false;
 }
```
### Rozwiązanie
Zachowanie rejestrow atomowych i regularnych rozni sie w sytuacji, gdy na rejestrze jednoczesnie dokonywany jest zapis i odczyt. Sprawdzmy czy w takiej sytuacji wymienione wartosci zostaja zachowane. 
Do odczytu dochodzi tylko w linii 4. Niech watkiem dokomujacym odczytu jest A, a jednoczesnie zapisu dokonywac bedzie B. 
B zapisuje na linii 2
A odczytuje stara wartosc flag[B] falsz i wchodzi do sekcji krytycznej. B czeka (wzajemne wykluczanie) az A zmieni swoja flage w unlock po sekcji krytycznej (co sie wydarzy) (niezaglodzenie)
A odczytuje nowa wartosc i czeka. B ustawia jako ofiare siebie, wiec A przestaje czekac i wchodzi w sekcje krytyczna, a B czeka, bo flag[A] nie została zmienionia (wzajemne wykluczanie), dalszy przebieg jak wyzej (niezaglodzenie). 
B zapisuje na linii 7
A odczyta albo jedna iteracje wczesniej albo w takim samym momencie (jak przy rejestrach atomowych) flag[B] falsz i przejdzie do sekcji krytycznej (niezaglodzenie), ale B juz wyszlo z sekcji krytycznej (wzajemne wykluczanie).
## Rozwiązanie 2:
![](https://i.imgur.com/0iDh4Tj.png)

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


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

Intuicja: regularny od atomowego różni się tym, że wywołanie nie musi być linearyzowalne.  Jednak jak mamy dwa wątki to nie powinno to mieć znaczenia. 

Wiemy, że jeśli zapis i odczyt się nie nakładają to rejest atomowy i regularny zachowa się tak samo.

Zobaczmy zatem co się wydarzy jeśli nałożą nam wykonania read i write. Wiemy, że Peterson jest algorytmem dwuwątkowych.  

Zobaczmy zatem co stanie się gdy wątek A będzie zapisywać Flag[A] = true a wątek B będzie czytać Flag[A] (czyli będzie w while)

Wiemy, że poprzednią wartością flag[A] było false. Zatem B przeczyta false albo true

Rozrysujsmy to na osi czasu

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

Zauważmy jednak, że obojętnie co wtawimy w znak zapytania to wywołanie to będzie linearyzowalne.

Zatem w przypadku tego algorytmu rejest regularny zachowuje się tak samo jak rejest atomowy. 

Zatem można zastąpić rejest atomowy rejestrem regularnym.

A: ---<A.read(flag[B] == true)>--<A.read(flag[B] == false)>---
B: ---<B.write(flag[B] = false)>--<B.write(flag[B] = true)>---
:::success
## Zadanie 4
:::
![](https://i.imgur.com/PnVsCrj.png)
![](https://i.imgur.com/BzxKmhp.png)

## Rozwiązanie 1:
Idea:
* Wykorzystujemy 2 $\lceil \log M+1\rceil$ boolowskich rejestrów do przechowywania wartości w zapisie dwójkowym (nazwane DATA[0] oraz DATA[1]).
* Wykorzystujemy 1 boolowski rejestr do przechowania informacji o porządku zapisu danych (nazwany INDEX).

### Funkcja write(x)
* Odczyta stan INDEX
* Wyznaczy NEWINDEX równy NOT(INDEX)
* Zapisze wartość x do DATA[NEWINDEX]
* Zapisze NEWINDEX do INDEX

### Funkcja read()
* Odczytuje wartość INDEX
* Odczytuje wartość DATA[INDEX]

### Uzasadnienie 
#### Wywołanie read bez współbieżnych wywołań write
W takim przypadku nie zmieni się zawartość INDEX i DATA[INDEX].Oznacza to, że będziemy odczytywać ostatnią zapisaną wartość.

#### Wywołanie read ze współbieżnym wywołaniem write
Możliwe przypadki:
1) read odczyta wartość sprzed współbieżnego write (przeczyta wartość zmiennej INDEX, zanim zmieni ją write)
2) Przeczyta zmienioną wartość INDEX i oznacza to, że wczyta wartość nowego i gotowego do odczytu rejestru DATA.

#### Wiele współbieżnych wywołan write
W takim przypadku przeczytana wartość może być dowolna. Podczas próby odczyty bufory zmienią się wielokrotnie, w wyniku read może odczytać fragment z każdego write.

:::success
## Zadanie 5
:::
![](https://i.imgur.com/mA2jj7Q.png)
![](https://i.imgur.com/iPec1gQ.png)


:::success
**Twierdzenie**
dobry rejestr MRSW jest **regularny** *wtedy i tylko wtedy*, gdy dla każdego ciągu dostępów:
* dla każdego $i$ nie jest prawdą, że $𝑅^i \rightarrow W^i$ (\*), oraz
* dla każdych $i$ oraz $j$ nie jest prawdą, że $𝑊^i \rightarrow W^j \rightarrow R^i$ (\*\*).
:::

:::info
**Definicja**
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”).
:::

$\implies$

Załóżmy, że mamy regularny rejestr MRSW. Weźmy dowolny ciąg dstępów.

* **(\*)**

Nie może zajść $R^i\rightarrow W^i$, bo rejestr jest regularny (w rejestrze nie znajduje się, nie jest do niego zapisywana $i$-ta wartość.).

* **(\*\*)**

Nie może zajść $W^i\rightarrow W^j \rightarrow R^i$, bo rejestr jest regularny (podczas gdy miałoby zajść $R^i$, $i$-tej wartości już w tym rejestrze nie ma).

$\impliedby$

Załóżmy, że mamy dobry rejestr MRSW, taki że dla każdego ciągu dostępów zachodz: 
* dla każdego $i$ nie jest prawdą, że $𝑅^i \rightarrow W^i$ (\*), oraz
* dla każdych $i$ oraz $j$ nie jest prawdą, że $𝑊^i \rightarrow W^j \rightarrow R^i$ (\*\*).

1. read() ($R^k$) jest niewspółbieżny z żadnym write().

    Z (\*):  $W^k \rightarrow R^k$.
    Z (\*\*): nie istnieje takie $j$, że $𝑊^k \rightarrow W^j \rightarrow R^k$.
    
    A zatem, $W^k$ jest ostatnik zapisem poprzedzającym $R^k$.
    
    (jak reg dla sytuacji 1.)
    
2. read() ($R^x$) jest współbieżny z write()

    ![](https://i.imgur.com/IA7333C.png)
    
    $$
    x \leq k +l \text{, bo (*)}\\
    x \geq k \text{, bo (**)}
    $$
    
    (jak reg dla sytuacji 2.)
    
A zatem twierdzenie zachodzi.

## Rozwiązanie 2:
![](https://i.imgur.com/r7vg5fo.png)

1) Załóżmy, że rejestr MRSW jest regularny. Wtedy dla każdego ciągu współbieżnych dostępów:
    - jeśli odczyt nie był współbieżny z żadnym zapisem, zwrócił ostatnią zapisaną wartość
    - jeśli odczyt był współbieżny z jednym lub większą liczbą zapisów, zwrócił ostatnią zapisaną wartość lub którąś z wartości zapisanych przez te zapisy

    Dla każdego $i$ nie jest prawdą, że $R^i \rightarrow W^i$, bo wartość zapisana przez $W^i$ nie była ostatnią zapisaną wartością w momencie odczytu $R^i$ oraz $R^i$ i $W^i$ nie są współbieżne.

    Dla każdych $i$ oraz $j$ nie jest prawdą, że $W^i \rightarrow W^j \rightarrow R^i$, ponieważ wartość zapisana przez $W^i$ nie była ostatnią zapisaną wartością w momencie odczytu $R^i$ oraz $R^i$ i $W^i$ nie są ze sobą współbieżne.
    
    
2) Załóżmy, że rejestr MRSW jest dobry i spełnia następujące warunki:
    - dla każdego $i$ nie jest prawdą, że $R^i \rightarrow W^i$ (*),
    - dla każdych $i$ oraz $j$ nie jest prawdą, że $W^i \rightarrow W^j \rightarrow R^i$ (**).

    Weźmy dowolny ciąg współbieżnych dostępów i rozważmy dowolny odczyt z tego ciągu.
    
    a) Odczyt nie jest współbieżny z żadnym zapisem.
    
    Załóżmy, że odczytana wartość jest różna od ostatniej zapisanej wartości. Ponieważ rejestr jest dobry, odczytana wartość musiała występować wśród wartości zapisanych. Z warunku (*) zapis tej wartości musiał mieć miejsce przed jej odczytem (albo współbieżnie z nim, ale ten odczyt nie jest współbieżny z żadnym zapisem). W takim razie wystąpiła sytuacja:
    $$
    W^i \rightarrow W^j \rightarrow R^i,
    $$
    
    gdzie $W^j$ to ostatnia niewspółbieżnie zapisana wartość (w momencie odczytu $R^i$). Jest to sprzeczne z warunkiem (**).
    
    Jeśli odczyt nie jest współbieżny z żadnym zapisem, to odczytana wartość jest ostatnią zapisaną wartością.
    
    b) Odczyt jest współbieżny z zapisami.
    
    Załóżmy, że odczytana wartość jest różna od ostatniej zapisanej wartości i od wartości zapisywanych przez te współbieżne zapisy.
    
    Rejestr jest dobry i spełniony jest warunek (*), więc odczytana wartość musiała być wartością zapisaną przed odczytem lub współbieżnie z nim. Z założenia nie mogła być zapisana współbieżnie z odczytem, więc otrzymujemy sytuację
    $$
    W^i \rightarrow W^j \rightarrow R^i
    $$
    
    gdzie $W^j$ to ostatnia niewspółbieżnie zapisana wartość (w momencie odczytu $R^i$).
    
    Jeśli odczyt jest współbieżny z zapisami, to odczytana wartość jest ostatnią zapisaną wartością lub wartością zapisaną przez te współbieżne zapisy.

:::success
## Zadanie 6
:::
![](https://i.imgur.com/QhybD1D.png)

Rejestr **atomowy** musi też być **regularny**, więc (\*) oraz (\*\*) mamy z poprzedniego zadania.

Teraz (\*\*\*):

Załóżmy, że rejestr jest atomowy. Implikuje to, że dla każdego i, j $$ R^i -> R^j \implies i \leq j $$
Dowód: jeżeli i > j to nie mamy poprawnej linearyzacji. A rejestr atomowy jest linearyzowalny.

Załóżmy, że rejestr jest regularny oraz dla każdego i, j $$ R^i -> R^j \implies i \leq j (W^i -> W^j) $$
Jest to wtedy rejestr atomowy.

Dowód: Jedyną różnicą między rejestrem atomowym a regularnym jest to, że dla rejestru regularnego może wystąpić sytuacja: $$ R^i -> R^j, i > j W^j -> W^i)$$

:::success
## Zadanie 7
:::

![](https://i.imgur.com/cCDMA8Q.png)
![](https://i.imgur.com/2HfhD27.png)

Załóżmy, że w tej implementacji jest podobnie jak w podręczniku, czyli na początku zapalony jest zerowy bit.

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

Lemat: Wywołanie read() zawsze zwróci wartość odpowiadającą bitowi ze zbioru 0...M-1, ustawioną przez jakieś wywołanie write().
Na początku write() zapalany jest najpierw nowy bit, dopiero później wszystkie wcześniejesze wartości są gaszone, czyli zawsze jakiś bit jest zapalony.

Załóżmy, że x jest poprzednio ustawioną wartością przez jakieś write(), czyli dla dowolnego *i<x*, wszystkie bity *i* są zgaszone.
Niech jakiś wątek wykonuje operację read(). Wówczas jeśli ten wątek odczyta wartość *bit[j] == true*, gdzie *j<x* to oznacza to, że jakiś współbieżny wątek wykonał write(), co jest zgodne z lematem i dowodzi twierdzeniom 4.1.1 i 4.1.2.

## Rozwiązanie 2:
```java=
public class RegMRSWRegister implements Register{
  RegBoolMRSWRegister[M] bit; // tutaj możemy chcieć zaznaczyć 0 na początku
    
  public void write(int x) {
    this.bit[x].write(true);
    for (int i=x-1; i>=0; i--) 
      this.bit[i].write(false);
  }
    
  public int read() {
    for (int i=0; i < M; i++)
      if (this.bit[i].read())
        return i;
   }
}
```
Definicja regularnego rejestru:
![](https://i.imgur.com/11rIAgx.png)
Lemat: Read zawsze zwróci wartość
Zauważmy, że usunięcie wartości poprzedza zapisanie większej. Oznacza to, że największa zapisana wartość zawsze jest zapalona.

Jeśli podczas read nie występuje write:
Wtedy wszystkie bity do ostatnio zapisanej wartości są zgaszone więc zostanie ona przeczytana.

Jeśli read występuje podczas write:
Jeśli zostanie zwrócona wartość mniejsza od x, to musiała ona zostać wprowadzona po ostatnim poprzedzającym write, ponieważ pola te zostały wyzerowane podczas jego zapisu. 
Jeśli zwrócone zostanie coś większego od $v^i$ (w tym x) dla dow. $i \in 0..k$ to $v^i$ musiał zostać usunięty przez write - czyli wszystkie bity do $v^j$ - wartości wprowadzonej w między czasie przez write, zostały wyzerowane. Więc zostanie zwrócona wartość $v^l$ dla $l \in 1..k$
## Zadanie 8
![](https://i.imgur.com/lKNDe4e.png)


## Zadanie 9
![](https://i.imgur.com/EE3B9Us.png)
