# Ćwiczenia 12, grupa śr. 10-12, 17 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 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | X | X | X | X | | | |
Konrad Kowalczyk | | X | X | | | | |
Jakub Krzyżowski | X | X | X | X | | | |
Łukasz Magnuszewski | | | | | | | |
Marcin Majchrzyk | | X | X | X | | X | X |
Jan Marek | | X | X | | | X | |
Marcin Mierzejewski | | | | | | | |
Juan Jose Nieto Ruiz | | | | | | | |
Konrad Oleksy | | | | | | | |
Javier Rábago Montero | X | X | X | X | X | | |
Michał Mękarski | | X | X | | X | X | X |
:::

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

## Zadanie 1
:::success
Autor: Jakub Krzyżowski
:::
**Zadanie 1.** Rozważmy punkty linearyzacji metod enq() i deq() w
kolejce LockFreeQueue.
1. Czy jako punkt linearyzacji metody deq(), w przypadku gdy
odnosi ona sukces, można wybrać instrukcję która
odczytuje zwracaną wartość z węzła?

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;
                }
            }
        }
    }
}

Nie można. Punktem linearyzacji tej metody będzie zakończony powodzeniem `compareAndSet(first, next)`. Gdyby punktem linearyzacji było odczytanie wartości z węzła, to w żaden sposób nie zmieniamy stanu naszej struktury, a zatem inne wątki nie widzą efektów naszego działania pomimo tego, że wywołanie jest już zlinearyzowane, a więc efekty powinny być widoczne.

2. Czy jako punkt linearyzacji metody enq() można wybrać
instrukcję (być może wykonywaną przez inny wątek), która
z sukcesem aktualizuje pole tail?

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);
            }
        }
    }
}

Można wybrać taki punkt linearyzacji, bo po takiej instrukcji jest już zaktualizowany zarówno wskaźnik w poprzedniku, jak i pole last. Nie musi robić tego jednak wątek który wykonał `last.next.compareAndSet(next, node)`, mogą to robić inne, szybsze wątki działające współbieżnie z nim wykonujące `enq()` i `deq()`, które zauważą, że tail nie został nadal przepięty na nowy węzeł.

## Zadanie 2
:::success
Autor: Konrad Kowalczyk
:::


Problem ABA polega na zmianie referencji, na którą akurat patrzy wątek, z A na B i z powrotem na A. Wątek nie wykrył zmiany (referencja wciąż wskazuje na A) ale sytuacja wokół A mogła się znacząco zmienić.

Problem ten objawia się między innymi w algorytmach używających instrukcji `compareAndSet()`.

Przypuśćmy, że mamy kolejkę, a nieużywane węzły przechowujemy w listach poszczególnych wątków, aby móc wykorzystać je ponownie.
Niech dana będzie taka sytuacja:
- wątek 0, będący dequeuerem, patrzy na początek kolejki i widzi element A (strażnika) oraz następujący po nim element B
- wątek 0 zostaje uśpiony
- inny wątek ściąga element A z kolejki, a także element B
- jeszcze inny wątek wkłada element A z powrotem do kolejki
- wątek 0 wybudza się i aby sprawdzić poprawność swojej sytuacji, wykonuje `compareAndSet()` na początku kolejki
- `compareAndSet()` zwraca `true`, ponieważ na początku kolejki znajduje się element A
- wątek 0 przepina początek kolejki na element B, który obecnie znajduje się na liście węzłów nieużywanych

Aby zapobiec problemowi ABA, można wykorzystać referencje z sygnaturami. Każdy węzeł posiada nie tylko referencję, ale także sygnaturę, która zostaje zmieniona za każdym razem, kiedy sam węzeł ulegnie modyfikacji (w tym również przeniesieniu). Instrukcja `compareAndSet()` w momencie wybudzenia się wątku 0 zobaczy inną sygnaturę i zwróci `false`, co zapobiegnie błędnemu przepięciu.

W niektórych architekturach dostępne są również metody `load-linked/store-conditional`, które sprawdzają nie czy wartość jest taka sama w dwóch różnych momentach, tylko czy pomiędzy tymi momentami została w jakikolwiek sposób zmieniona. Jako że początek kolejki w problemie ABA zmienił się z A na B oraz z powrotem na A, metody te wykryją zmianę i nie pozwolą problemowi ABA wystąpić.

## Zadanie 3
:::success
Autor: Javier Rábago Montero
:::
The class has four instance variables, item, that stores the item to be queued or dequeued, boolean queue to indicate whether an item is being enqueued, and lock and condition for synchronization.
Method enq() first takes the lock and checks if enqueuing is true, if so it waits using condition.await(). Once it is, it set enqueuing to true and updates the item variable. It then signals all waiting threads using condition.signalAll(). It waits until the item is dequeued using another while loop and condition.await(). Finally it sets enqueuing to false and signals all waiting threads.
The deq() method takes the lock and waits while item is null if the queue is empty for the moment. Once an item is available it sets it to null, signals all waiting threads and returns the dequeued item. The lock is finally released.
The queue is implemented as a list of nodes.
In this example, we can take a thread that runs enq() as producer, and one that runs deq() as consumer. In synchronous data structures like this, a producer puts an item in the queue block until it is removed by a consumer. This action is called a rendezvous, where enq() works synchronized with deq(), the first passes the first to the second.

## Zadanie 4
:::success
Autor: Mikołaj Balwicki
:::

## Zadanie 5
:::success
Autor: Michał Mękarski
:::


### Figure 11.10


### Problematyczny moment


### Rozwiązanie


## Zadanie 6
:::success
Autor: Jan Marek
:::


Przykładowo: 2 wątki (A, B), pusta tablica `items`.

1. Wątek A wykonuje metodę `push()`. Wykona `top.getAndIncrement()` i idzie spać. Czyli teraz `top == 1`.
2. Wątek B wykonuje całą metodę `pop()`, czyli zwróci na koniec `items[0]`, ale A nie zdążył jeszcze niczego tam umieścić.

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);
    }
    public void push(T x) throws FullException {
        rooms.enter(0);
        int i = top.getAndIncrement();
        if (i >= items.length) {
            top.getAndDecrement();
            rooms.exit();
            throw new FullException();
        }
        items[i] = x;
        rooms.exit();
    }
    public T pop() throws EmptyException {
        rooms.enter(1);
        int i = top.getAndDecrement() - 1;
        if (i < 0) {
            top.getAndIncrement();
            rooms.exit();
            throw new EmptyException();
        }
        T item = items[i];
        rooms.exit();
        return item;
    }
}

## Zadanie 7
:::success
Autor: Marcin Majchrzyk
:::

public void push(T x) {
    while (true) {
        if (isFull) continue;
        
        rooms.enter(0);
        int i = top.getAndIncrement();
        
        if (i >= items.length) {
            top.getAndDecrement();
            isFull = true;
            rooms.exit();
            continue;
        }
        
        items[i] = x;
        rooms.exit();
        return;
    }
}

void onEmpty() {
    if (!isFull) return;
    
    T[] newItems = new T[items.length + 1];
    System.arrayCopy(items, 0, newItems, 0, items.length);
    items = newItems;
    isFull = false;
}