# Ćwiczenia 5, grupa śr. 16-18, 23 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 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | X | X | | | | | | |
Marcin Dąbrowski | | | | | | | | |
Jakub Gałecki | | | | | | | | |
Kamila Goszcz | X | X | | X | | X | X | |
Wiktor Hamberger | X | X | | X| | | | |
Jan Jankowicz | | X | | X | | | | |
Mikołaj Jaszcza | X | X | | X | X | X | X | |
Zuzanna Kania | X | X | | X | | | | |
Wiktoria Kuna | | | | | | | | |
Patryk Mazur | X | X | | X | | | | |
Hubert Obrzut | X | X | X | X | X | X | X | X |
Magdalena Rzepka | X |==X==| | X | | X | X | |
Joanna Stachowicz | X | X | | | | | | |
Rafał Starypan | ==X== | 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 | X | | X | ==X== | X | | |
:::

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

## Zadanie 1
:::success
Autor: Rafał Starypan
:::

1. Sekwencyjnie spójne

2. Sekwencyjnie niespójne

Aby można było wykonać p.deq(y), to p.enq(y) musi być przed q.enq(x). Spowoduje to, że q.enq(y) będzie przed p.enq(x), czyli również przed q.enq(x).
Zatem q.deq(x) nie zwróci poprawnej wartości

## Zadanie 2
:::success
Autor: Magdalena Rzepka
:::

**Własność kompozycji** - jeżeli dla każdej składowej x historii H H|x ma jakąś ceche, to historia H też ją ma.

**Sekwencyjna spójność nie ma własności kompozycji.**

Przykład:


A p.enq(x) #1
B q.enq(y) #2
A q.enq(x) #3
B p.enq(y) #4
A p.deq(y) #5
B q.deq(x) #6

Sekwencyjna spójność składowych p i q wystąpi, po zmianie #1 i #4 miejscami oraz po zmienie #2 i #3.

H|p
B p.enq(y) #4
A p.enq(x) #1
A p.deq(y) #5

H|q
A q.enq(x) #3
B q.enq(y) #2
B q.deq(x) #6

#4 -> #1 -> #5
#3 -> #2 -> #6

Ale w obrębie wątku nie możemy zmieniać miejscami, więc musi zachodzić również:

#1 -> #3 -> #5
#2 -> #4 -> #6

Podsumowując:

#4 -> #1 -> #3 -> #2 -> #4
#4 -> #4

Akcja 4 musi nastąpić przed samą w sobie.
Sprzeczność!

## Zadanie 3
:::success
Autor: Hubert Obrzut
:::


## Zadanie 4
:::success
Autor: Patryk Mazur
:::

Zał. że wątek A wszedł do sekcji krytycznej:
`write_A(flag[A] = true) -> write_A(victim = A) -> read_A(flag[B] == false || victim == B)`

Żeby B wszedł musiałoby zachodzić:
`write_B(flag[B] = true) -> write_B(victim = B) -> read_B(flag[A] == false || victim == A)`

Jako, że A jest w sekcji krytycznej to `flag[A] == true` oraz `victim == B` ponieważ B ustawił na siebie zmienną victim.

W modelu procesora słabszym niż sekwencyjna spójność może się okazać, że procesor zamieni kolejność operacji w celu optymalizacji (domyślnie `flag[] = false`):

`read_A(flag[B] == false) -> read_B(flag[A] == false) -> write_A(flag[A] = true) -> write_B(flag[B] = true)`

Zatem oba wątki wejdą do sekcji krytycznej

## Zadanie 5
:::success
Autor: Adam Jarząbek
:::

Ponieważ mamy model pamięci słabszy niż sekwencyjna spójność, może się zdarzyć, że instrukcje nie zostaną wykonane w takiej kolejności, jak są w kodzie. W szczególności w klasie wstawiającej element do kolejki możemy ustalić wartość `tail % capacity`, następnie zwiększyć wartość `tail` i dopiero zapisać nowy element pod wyliczonym indeksem. Jeżeli pomiędzy zwiększeniem wartości zmiennej, a zapisem do tablicy wątek odczytujący będzie chciał odczytać wartość zapisaną pod zwiększonym już `tail`, odczyta nieprawidłową wartość. Z tego powodu współdzielone między wątkami zmienne takie jak `tail` powinny być przechowywane w odpowiednio przystosowanych obiektach.

## Zadanie 6
:::success
Autor:Mikołaj Jaszcza
:::


Aby pokazać fakt, iż IQueue nie jest poprawnym obiektem współ. pokażę, że nie jest linearyzowalny. Aby to zrobić posłużę się podaniem przykładu nielinearyzowalnej historii:

(tj. w tym scenariuszu zajdzie, że wątek A zostanie wywłaszczony po wyjściu z pętli).
Możemy więc to interpretować jako sytuację, gdzie zajęliśmy slot w tablicy, ale jeszcze go nie zapełniliśmy. Zauważmy, że w trakcie wykonywania funkcji deq przez wątek B 'head' będzie wskazywał na wartość null (komórka zajęta przez A, jak opisane powyżej). A zatem skoro head wskazuje na null - funkcja 'zwróci' EmptyException.

Zauważmy jednak, że historia opisana powyżej nie może zostać zlinearyzowana. Ponieważ wywołujemy deq już po zakończeniu jednego enq, wiadomo więc, że kolejka nie jest pusta, lecz uzyskujemy EmptyException. Uzyskaliśmy tym samym sprzeczność - zatem pokazaliśmy, że przedstawiona implementacja jest niepoprawna.

## Zadanie 7
:::success
Autor: Maria Szlasa
:::
:::info
:::
**AtomicInteger** An int value that may be updated atomically. An AtomicInteger is used in applications such as atomically incremented counters, and cannot be used as a replacement for an Integer. However, this class does extend Number to allow uniform access by tools and utilities that deal with numerically-based classes.
**AtomicReference\<T\>** An object reference that may be updated atomically.
**Punkt linearyzacji** miejsce w którym metoda daje efekt.
****
Pokażemy, że enq nie ma pojedynczego punktu linearyzacji.

### Dla instrukcji *i = tail.getAndIncrement()*

Najpierw wątek A zwiększy licznik, a następnie wątek B. Potem wątek B umieści swoją wartość w kolejce i zacznie się wykonywać q.deq. Ponieważ wątek A nie wstawił jeszcze swojej wartości, pod zajętym przez niego indeksem będzie null. Pętla for obróci się ponownie i ściągniemy y.

### Dla instrukcji *items[i].set(x)*
Wątek A otrzyma indeks i, a wątek B otrzyma i+1. Mimo, że punkt linearyzacji wątku B zakończy się szybciej (wątek B szykciej skończy wykonywać enq), to ponieważ wątek A otrzymał mniejszy indeks, to wątek C przeczyta wartość zapisaną przez A.

### Czy z tego wynika, że historia nie jest linearyzowalna?
Nie! Punktem linearyzacji może być grupa instrukcji.
## Zadanie 8
:::success
Autor: Hubert Obrzut
:::