# Ćwiczenia 11, grupa śr. 10-12, 10 stycznia 2024
###### 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 |
| ----------------------:| --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | X | X | X | X | X | X |
Konrad Kowalczyk | | X | X | X | | |
Jakub Krzyżowski | X | X | X | X | X | |
Łukasz Magnuszewski | | | | | | |
Marcin Majchrzyk | X | X | X | X | | X |
Jan Marek | X | | X | X | | X |
Marcin Mierzejewski | | | | | | |
Juan Jose Nieto Ruiz | | | | | | |
Konrad Oleksy | | | | | | |
Javier Rábago Montero | X | X | X | X | X | X |
Michał Mękarski | | | | | | |
:::
Tutaj można zadeklarować zaległe zadanie 8 z listy 10:
:::danger
| | 10.8 |
| ----------------------:| ----- |
| Javier Rábago Montero | X |
| | |
:::
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::
## Zadanie 1
:::success
Autor: Jan Marek
:::
a) Wątek $A$ przymierza się do usunięcia węzła $a$, natomiast wątek $B$ przymierza się do dodania węzła $b$. Przypuśćmy, że wątek $A$ wykona metodę $compareAndSet()$ na polu $head.next$, a wątek $B$ również $compareAndSet()$ na polu $a.next$. Efektem będzie poprawne usunięcie węzła $a$, ale węzeł $b$ nie zostanie wstawiony na listę.
b) Wątek $A$ chce usunąć węzeł $a$, natomiast wątek $B$ chce usunąć węzeł $b$ ($a$ wskazuje na $b$). Przypuśćmy, że wątek $A$ wykona $compareAndSet()$ na polu $head.next$, natomiast wątek $B$ również wykona $compareAndSet()$ na polu $a.next$. Efekt będzie taki, że usunięty zostanie węzeł $a$, ale nie węzeł $b$.
Aby rozwiązać powyższe problemy, chcemy zapewnić aby pole $next$ usuniętego węzła nie mogło być zmodyfikowane.
Zmieniamy typ pola $next$ na $AtomicMarkableReference$, tak aby oprócz referencji zawierało flagę $marked$. Węzeł, którego pole $next$ ma ustawioną flagę $marked$ jest logicznie usunięty.
Klasa `AtomicMarkableReference<T>` posiada metodę:
Wykorzystujemy ją podczas dodawania i usuwania węzła, aby atomowo upewnić się, że w międzyczasie nie została zmodyfikowana referencja do następnego węzła (next), ani że nie został on w międzyczasie usunięty.
## Zadanie 2
:::success
Autor: Mikołaj Balwicki
:::
## Zadanie 3
:::success
Autor: Javier Rábago Montero
:::
If pred does not have the marked field set it means it hasn't been logically removed, but is was already compared and deemed smaller than the argument we are trying to add, so we only have to look after pred.
## Zadanie 4
:::success
Autor: Marcin Majchrzyk
:::
#### add() i remove()
Obie metody pozostają wewnątrz pętli ```while(true)``` tylko wtedy, gdy lista została zmodyfikowana. Pomimo zapętlenia zawartość listy jest modyfikowana, co oznacza, że jeden z wątków dokonał postępu, więc z definicji metody są lock-free.
#### contains()
Metoda iteruje się po elementach pętli do momentu aż znajdzie element o wartości większej od szukanego, a ponieważ rozmiar listy jest skończony, to metoda jest wait-free.
## Zadanie 5
:::success
Autor: Jakub Krzyżowski
:::
**Zadanie 5. Uzasadnij, że metody add(), remove() oraz
contains() klasy LazyList są linearyzowalne. Czy dla każdej z
tych metod jesteś w stanie wskazać konkretny punkt
linearyzacji w jej kodzie?**
Żeby pokazać, że metoda jest linearyzowalna należy podać jej punkt linearyzacji, czyli punkt w kodzie po którym jej efekty są widoczne dla innych metod.
1. `add(x)`
`add` w klasie `LazyList` jest takie samo jak w `OptimisticList`, po prostu wywołuje inne validate
```java=
public boolean add(T item) {
int key = item.hashCode();
while (true) {
Node pred = head;
Node curr = pred.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
pred.lock();
try {
curr.lock();
try {
if (validate(pred, curr)) {
if (curr.key == key) {
return false;
} else {
Node node = new Node(item);
node.next = curr;
pred.next = node;
return true;
}
}
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
}
```
W przypadku powodzenia punktem linearyzacji będzie tutaj linia 19, czyli moment przepięcia wskaźnika poprzednika na nowy węzeł, gdyż dopiero wtedy będzie osiągalny z head, a zatem będzie należeć do zbioru. W przypadku niepowodzenia będzie to walidacja curr z kluczem równym wstawianemu.
2. `remove(x)`
Remove w tej klasie ma jeden dodatkowy krok niż remove z `OptimisticList` - logiczne usunięcie węzła.
```java=
public boolean remove(T item) {
int key = item.hashCode();
while (true) {
Node pred = head;
Node curr = head.next;
while (curr.key < key) {
pred = curr; curr = curr.next;
}
pred.lock();
try {
curr.lock();
try {
if (validate(pred, curr)) {
if (curr.key == key) {
curr.marked = true;
pred.next = curr.next;
return true;
} else {
return false;
}
}
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}
}
```
Tutaj punktem linearyzacji w przypadku powodzenia jest logiczne usunięcie węzła, czyli linia 15. W przypadku niepowodzenia będzie to poprawna walidacja węzła z kluczem większym od szukanego.
3. `contains`
```java=
public boolean contains(T item) {
int key = item.hashCode();
Node curr = head;
while (curr.key < key)
curr = curr.next;
return curr.key == key && !curr.marked;
}
```
Tutaj punktem linearyzacji będzie ostatnia instrukcja.
## Zadanie 6
:::success
Autor: Jan Marek
:::
Rozpatrzmy nast. wykonanie:
Wątek A jest w trakcie wykonywania `enq()` - zajął zamek `enqLock`, przeszedł przez `while`, przepiął wskaźnik z ostatniego węzła na nowo dodany węzeł i poszedł spać (czyli zatrzymał się po wykonaniu `tail.next = e`).
Czyli `size` nadal równa się `0`.
Teraz wątek B wykona `deq()` - zajmie zamek `deqLock`, przejdzie przez `while (head.next == null)`, przeczyta wyciągany element, przepnie wskaźnik `head` i wykona `size.getAndDecrement()`.
Teraz `size` będzie równe `-1`.
Google Drive
Gist
Clipboard
Sign in with Wallet
