# Ćwiczenia 12, grupa cz. 16-18, 11 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 | 7 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | | X | X | | | | |
Paweł Borek | | | | | | | |
Arti Brzozowski | | | | | | | |
Mateusz Golisz | | x | x | | x | x | x |
Kacper Jóźwiak | | x | | | | | |
Julia Konefał | | | | | | | |
Adam Korta | | x | x | | | | |
Jakub Mikołajczyk | X | X | X | | X | X | X |
Bartosz Morasz | | x | x | | x | x | x |
Andrzej Morawski | | x | x | | x | x | |
Aleksandra Nicpoń | | x | | | | | |
Mateusz Reis | | x | x | | x | x | x |
Tomasz Stachurski | | X | X | | X | X | X |
Marcel Szelwiga | | X | X | | | | |
Volha Tsekalo | | | | | | | |
Martyna Wybraniec | | | | | | | |
Denys Zinoviev | | | | | | | |
Dominik Olejarz | | x | x | | | | |
:::
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::
## Zadanie 1
:::success
Autor: Andrzej Morawski
:::
```java=
public class LockFreeQueue<T> {
AtomicReference<Node> head, tail;
public LockFreeQueue() {
Node node = new Node(null);
head = new AtomicReference(node);
tail = new AtomicReference(node);
}
public class Node {
public T value;
public AtomicReference<Node> next;
public Node(T value) {
this.value = value;
next = new AtomicReference<Node>(null);
}
}
public void enq(T value) {
Node node = new Node(value);
while (true) {
Node last = tail.get();
Node next = last.next.get();
if (last == tail.get()) {
if (next == null) {
if (last.next.compareAndSet(next, node)) {
tail.compareAndSet(last, node);
return;
}
} else {
tail.compareAndSet(last, next);
}
}
}
}
public T deq() throws EmptyException {
while (true) {
Node first = head.get();
Node last = tail.get();
Node next = first.next.get();
if (first == head.get()) {
if (first == last) {
if (next == null) {
throw new EmptyException();
}
tail.compareAndSet(last, next);
} else {
T value = next.value;
if (head.compareAndSet(first, next)) {
return value;
}
}
}
}
}
}
```
### 1.
Z założenia wiemy, że wywołanie metody ```deq()``` kończy się sukcesem. Możemy wybrać instrukcje odczytania wartości z węzła jako punkt linearyzacji, ponieważ będzie to wartość zwrócona przez funkcję.
### 2.
Wykonując metodę enq(x) mamy 2 etapy wpinania nowego węzła do listy:
* Logiczne → przepięcie wskaźnika ```last.next.compareAndSet(next, node);```
* Fizyczne → przepięcie wskaźnika ```tail.compareAndSet(last, next/node);```
Jako punkt lienaryzacji możemy wybrać dowolne wykonanie instrukcji ```compareAndSet``` ponieważ jest to instrukcja, która daje efekt w wykonywanej metodzie. Jeżeli węzeł zostanie dodany logicznie na koniec kolejki wówczas zależy nam na zaktualizowaniu pola tail. Niezależnie od tego, które wywołanie metody ```compareAndSet``` weźmiemy nowy węzeł zostanie wpięty jako nowy ogon, albo jej wykonanie przybliży nas do tego, żeby wpiąć ten węzeł na koniec kolejki. Zatem metoda będzie miała widoczny efekt.
## Zadanie 2
:::success
Autor: Dominik Olejarz
:::
Problem ABA – rodzaj błędu w synchronizacji procesów wielowątkowych, polegający na tym, że w
przypadku dwukrotnego odczytu lokacji pamięci, gdy odczytana wartość jest taka sama w obu odczytach,
to „taka sama wartość” jest interpretowana jako „nic się nie zmieniło”. Jednak inny wątek mógł, między
odczytami w pierwszym wątku, zmienić wartość tej lokacji, wykonać jakieś zadania, a następnie ponownie zmienić
wartość lokacji do wartości równej pierwotnej, niejako oszukując pierwszy wątek, że „nic się nie zmieniło”, mimo
że drugi wątek wykonał pracę, która narusza to założenie.
Przyklad
-Wątek A próbuje zmienić head z a na b
-w tym czasie wątek B wyjmuje z kolejki b oraz a.
-Jeszcze inny wątek ponownie przywraca w to miejsce a
-Teraz wątek A kończy działanie, za pomocą CompareAndSet() zmienia poprzednika, tak, że node usunięty przez niego wskazuje na b zamiast na c
-Tutaj się wszystko załamuje, bo b jest usunięte
Do naprawy tego błędu używamy AtomicStampedReference<T>.
Klasa ta przechowuje referencję do następnego obiektu i stamp, który służy do zidentyfikowania czy nastąpił problem opisany wyżej.
CAS jednocześnie sprawdza referencję i stamp, a gdy używamy CAS, zwiększamy stamp.
## Zadanie 3
:::success
Autor: Dominik Baziuk
:::
:::info
Na przykładzie SynchronousQueue wyjaśnij, czym są synchroniczne struktury danych i do czego mogą służyć?
:::
Synchroniczne struktury danych pomagają rozwiązać problem producent-konsument.
:::info
Czym jest spotkanie (ang. rendezvous)?
:::
Producenci i konsumenci spotykają się ze sobą: Producent, który umieszcza artykuł w kolejce, blokuje się do czasu usunięcia go przez konsumentem i odwrotnie.
## Zadanie 4
:::success
Autor: Tomasz Stachurski
:::
Dualną wersje kolejki wprowadzamy, aby ograniczyć koszt synchronizacji. Poprzednio mieliśmy wielu producentów i wielu konsumentów, ale tylko jeden z nich może operować na kolejce i przy każdej wymianie (producent <-> konsument) budziły się wszystkie wątki (kwadratowo nadmiarowa ilość pobudek)...
IDEA kolejki:
Wyróżniamy 3 stany kolejki:
* pusta
* zawiera tylko rezerwacje konsumentów
* zawiera tylko elementy producentów
Jeśli kolejka jest pusta i zaczyna producent, to dodajemy. Jak przyjdzie konsument, to będzie ściągał kolejno dodane elementy, aż do pustej kolejki
Jeśli kolejka jest pusta i zaczyna producent, to odwrotnie.
Na początku sprawdzamy, czy kolejka jest pusta albo zawiera elementy producentów.
Jeśli ma rezerwacje (warunek else), to ściągamy pierwszą z nich [wiersze 24-32]. Następnie sprawdza, czy wszystkie wartości są poprawne [wiersze 25-27]. Jeśli tak to próbuje wypełnić rezerwację i przestawia głowę na kolejny element w kolejce. W przypadku gdy wymiana się nie udała (`success` = false), to ktoś nas ubiegł i musimy ponownić działanie `enq()`, wpp. kończymy działanie.
Jeśli kolejka jest pusta albo mamy w niej elementy od producentów zachowujemy się tak jakbyśmy pracowali na zwykłej kolejce z tą różnicą, że każdy element wiruje nad samym sobą w oczekiwaniu na konsumenta. Jak w końcu zostanie zabrany przez konsumenta, próbuje po sobie posprzątać czyniąc się strażnikiem `head` [linia 29-30], wyręczając konsumenta.
## Zadanie 5
:::success
Autor: Bartosz Morasz
:::
Problemem w algorytmie Boba pojawia się gdy jeden wątek wykonuje pop, a drugi push. Możemy mieć sytuację w której:
- Najpierw pop wyciągnie i = x
- Push wyciągnie po nim i = x - 1
- Push wykona resztę swoich operacji, podmieniając element, który nie powinien być nadpisany
- Pop zwróci wartość powyżej
Moglibyśmy to rozwiązać dodając analogicznego while do push
## Zadanie 6
:::success
Autor: Andrzej Morawski
:::
```java=
public interface Rooms {
public interface Handler {
void onEmpty();
}
void enter(int i);
boolean exit();
public void setExitHandler(int i, Rooms.Handler h) ;
}
public class Stack<T> {
private AtomicInteger top;
private T[] items;
private Rooms rooms; // new
public Stack(int capacity) {
top = new AtomicInteger();
items = (T[]) new Object[capacity];
rooms = new Rooms(2);
}
public void push(T x) throws FullException {
rooms.enter(0) // new
int i = top.getAndIncrement();
if (i >= items.length) { // stack is full
top.getAndDecrement(); // restore state
throw new FullException();
}
items[i] = x;
rooms.exit() // new
}
public T pop() throws EmptyException {
rooms.enter(1) // new
int i = top.getAndDecrement() - 1;
if (i < 0) { // stack is empty
top.getAndIncrement(); // restore state
throw new EmptyException();
}
T result = items[i]
rooms.exit() // new
return result;
}
}
```
### Czemu ta implementacja nie działa?
Analogicznie jak w zadaniu 5 może dochodzić do nadpisywania wartości w komórkach.
Rozpatrzmy następujące wykonanie programu dla wątków A,B,C:
```
A:push(x)
B:push(y)
C:pop()
```
Wątek A:
1. int i = top.getAndIncrement(); → i = 0, top = 1;
2. Wątek A idzie spać;
Wątek C:
1. int i = top.getAndDecrement() - 1; → i = 1 - 1 = 0, top = 0;
2. Wątek C idzie spać;
Wątek B:
1. int i = top.getAndIncrement(); → i = 0; top = 1;
2. Wątek B przechodzi przez instrukcję warunkową
3. Wątek B wpisuje swoją wartość do tablicy
4. Budzi się wątek A
5. Wątek A przechodzi przez instrukcję warunkową
6. Wątek A nadpisuje poprzednią wartość w tablicy
7. Budzi się wątek C
8. Wątek C zdejmuje nadpisaną wartość.
9. W tablicy nie została żadna wartość mimo tego, że wykonaliśmy 2 instrukcje push i jedną pop.
## Zadanie 7
:::success
Autor: Mateusz Reis
:::
```java=
public interface Rooms {
public interface Handler {
void onEmpty();
}
void enter(int i);
boolean exit();
public void setExitHandler(int i, Rooms.Handler h) ;
}
public class Stack<T> {
private AtomicInteger top;
private T[] items;
private Rooms rooms;
public Stack(int capacity) {
top = new AtomicInteger();
items = (T[]) new Object[capacity];
rooms = new Rooms(2);
rooms.setExitHandler(0, this::resize);
}
public void push(T x){
rooms.enter(0) // new
int i = top.getAndIncrement();
if (i >= items.length) { // stack is full
top.getAndDecrement(); // restore state
rooms.exit();
this.push(x);
}
items[i] = x;
rooms.exit() // new
}
public T pop() throws EmptyException {
rooms.enter(1) // new
int i = top.getAndDecrement() - 1;
if (i < 0) { // stack is empty
top.getAndIncrement(); // restore state
throw new EmptyException();
}
T result = items[i]
rooms.exit() // new
return result;
}
private void resize() {
T[] newItems = (T[]) new Object[items.length * 2];
System.arraycopy(items, 0, newItems, 0, items.length);
items = newItems;
}
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
