# Ćwiczenia 12, grupa śr. 16-18, 18 stycznia 2023

###### 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 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | | X | X | X | X | | |
Marcin Dąbrowski | | | | | | | |
Jakub Gałecki | | | | | | | |
Kamila Goszcz | | | | | | | |
Wiktor Hamberger | X | X | X | | X | | |
Jan Jankowicz | | X | X | X | | | |
Mikołaj Jaszcza | | X | X | | | | |
Zuzanna Kania | | X | X | X | | | |
Wiktoria Kuna | | | | | | | |
Patryk Mazur | | X | X | | | | |
Hubert Obrzut | | | | | | | |
Magdalena Rzepka | | X | X | | | X | X |
Joanna Stachowicz | | X | X | | | | |
Rafał Starypan | | X | X |X | | ==X== | X |
Maria Szlasa | | X | X | | | | |
Daniel Wiczołek | | | | | | | |
Adam Jarząbek | | ==X== | X | X | X | X | X ||
:::

Tutaj można zadeklarować **zad. 8. z listy 11.**:
-
-
-

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

## Zadanie 1
:::success
Autor: Wiktor Hamberger
:::


Jeżeli patrzymy tylko na wykonanie z sukcesem, to oznacza, że CAS w linii 48 zwrócił true, więc wtedy dany węzeł istniał i był z przodu kolejki, co oznacza, że w linii 47 ten węzeł też istniał i był z przodu kolejki.


Tak, ale tylko dlatego, że deq() najpierw usuwa luźny koniec, a inne enq() w przypadku konflikówsame zamykają te luźne końce, dopiero później ściąga.

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

Problem "ABA" to rodzaj błędu synchronizacji. Dotyczy zwyczajowo operacji CAS (compare-and-set). Bazuje on na (błędnym) założeniu w niektórych miejscach programu, że jeżeli wartość jest taka sama jak wcześniej to nie nastąpiła dla niej żadna zmiana. Tj. może zajść że mimo braku zmiany wartości pojedynczej referencji system zmienił jej znaczenie.

W szczególności przykład opowiedziany na wykładzie dotyczył programu, który dla współbieżnej kolejki używa "node'ów", które nie są usuwane przy operacji deque (tylko umieszczane we wspólnej puli pustych wierzchołków). Może więc zajść jak poniżej:


Tj. wątek A chce przez operację CAS zmienić head'a listy z wierzchołka a na wierzchołek b (w trakcie deque, gdy a jest pierwszym elementem po strażniku). Załóżmy jednak, że w trakcie nastąpi poniższe:
- inny wątek/inne wątki usuwają (deque) element b z kolejki oraz jego następnik (element a). Powoduje to umieszczenie node'ów a i b w puli "wolnych" obiektów
- może teraz nastąpić deque elementów, potem enque d, c, a (tak jak oznaczono na rysynku powyżej)
- i w końcu uprzednio wywłaszczony wątek A kończy swoje działanie - przez operację CAS powoduje że head listy zamiast wskazywać na a będzie wskazywał na b, ale element b nie należy już do listy

Można uogólnić powyższą sekwencję do kroków typu:
- wątek A odczytuje pewną wartość a
- wątkowi A zostanie odebrany procesor przez systemowego planistę
- inne wątki modyfikują wartość a -> ... (np. do wartości b), oraz z powrotem ... -> a. Stąd nazwa ABA.
- wątek A dostaje powrotnie dostęp do procesora
- działa dalej bez świadomości, że wartość dla obiektu 'a' została zmieniona, co nie jest dla niego rozróżnialne od sytuacji, że żadna zmiana nie miała miejsca

Rozwiązanie:

"AtomicStampedReference< T >" to klasa która oprócz samego wskaźnika na obiekt zawiera w sobie też dane, które pozwalają identyfikować czy sytuacja opisana powyżej miała miejsce - zawiera informacje pozwalające zidentyfikować czy miała miejsce jakakolwiek modyfikacja na wskaźniku. Zatem jeśli operacja CAS modyfikuje wskaźnik - zostanie to też zawarte w 'stampie' wewnątrz AtomicStampedReference.

## Zadanie 3
:::success
Autor: Zuzanna Kania
:::

**Synchroniczna struktura danych** to taka, która paruje ze sobą operacje producenta i konsumenta (np. enq i deq, push i pop)

**Spotkanie** - moment, kiedy na kolejce synchronicznej działa zarówno enq jak i deq. Wtedy enq przekazuje swój element do deq.


## Zadanie 4
:::success
Autor: Daniel Boguszewski
:::

Uzasadnieniem jest ograniczenie kosztów synchronizacji. Podstawowa kolejka może posiadać wiele enquerów (producentów), którzy próbują dodać element do kolejki oraz wiele konsumentów (dequerów) oczekujących na element, ale tylko jeden (albo dequer, albo enquer) jest w stanie aktualnie działać na kolejce. Mimo to przy każdej wymianie (dequer - enquer) budzą się wszystkie oczekujące wątki, powodując kwadratowo nadmiarową liczbę pobudek (n enquerów, n dequerów, n-1 enquerów, n-1 enquerów, ...).
Dualna wersja kolejki rozwiązuje wyżej opisany problem.

Intuicyjny model działania:
Kolejka może być pusta, posiadać jedynie rezerwacje dequerów, albo same elementy enquerów.
Jeśli kolejka jest pusta, kolejne dequery będą wypełniały ją rezerwacjami, a enquery FIFO je uzupełniać (opróżniając w efekcie kolejkę), natomiast jeśli to producent pierwszy zacznie wypełniać kolejkę, będzie odwrotnie.

Pusta kolejka posiada dwóch strażników, głowę i ogon, które jeśli wskazują na siebie, oznaczają, że kolejka pozostaje pusta. Rozważmy metodę enq().

Sprawdzamy, czy kolejka jest pusta lub wypełniona elementami enquerów, a jeśli nie, próbujemy znaleźć w kolejce rezerwację do wypełnienia, będzie to pierwszy element od głowy (wiersze 36 - 43). Jeśli wartości ogona, głowy i dodanego elementu posiadają poprawne wartości, enq() próbuje wypełnić rezerwację pierwszego elementu. Niezależnie od tego, czy się to uda, czy nie, głowa jest przestawiana na kolejny element. Dopiero teraz, jeśli rezerwacja się powiodła, enquer kończy działanie. Porażka oznaczałaby, że rezerwacja została wcześniej wypełniona, więc ponawia się działanie.

Jeśli kolejka była pusta lub wypełniona elementami enquerów, początek przypomina działanie bezzamkowej kolejki. Różnica w tym, że gdy ten element zostanie wreszcie wyciągnięty przez dequera, wirujący na swoim elemencie enquer próbuje zamienić swój element na strażnika głowy (wyciągane elementy są z przodu kolejki) i kończy działanie. Ta część odpowiada zaznaczonemu niżej blokowi kodu z LockFreeQeueue (pogrubione linie zastępują dodatkowe instrukcje SynchronousDualQueue):

Dodatek:
Przypadek dodawania elementów do kolejki wypełnionej elementami enquerów (lub pustej):
Enquer 1 otrzymuje zadanie dodania elementu do kolejki:

Enquer 1 stwierdza, że ostatni element wskazuje na null, a ogon wskazuje na strażnika.
W tym samym czasie Enquer 2 otrzymuje zadanie dołożenia kolejnego elementu do kolejki:

Enquer 2 wykonuje tę samą czynność, ale wyprzedza Enquera 1 i dokłada element na koniec kolejki:

Enquer 1 próbuje dołożyć siebie za strażnika, jednak compareAndSet tym razem zawodzi (strażnik nie wskazuje na null). Wobec tego do kolejki wydano polecenie dodania więcej niż jednego elementu i Enquer 1 spróbuje dołożyć swój element jeszcze raz.

W tym przypadku Enquer 2 nie zdążył jeszcze przestawić strażnika, Enquer 1 go w tym wyręczy i spróbuje jeszcze raz dołożyć się na koniec.

Enquer 2 wreszcie wraca do działania i metodą compareAndSet() próbuje przestawić ogon na siebie, ale nie zależy mu na wyniku. Jeśli zamiana się nie powiodła, znaczy że ktoś go w tym wyprzedził. Enquer 1, gdy się obudzi, ustawi ogon na siebie.

Oba enquery czekają, aż ktoś odbierze ich element (nastąpi deq() na ich elemencie):

Pojawia się Dequer i zabiera element z początku kolejki:

Gdy Enquer 2 to zauważy, spróbuje przestawić głowę dalej i usunąć się z obiegu, jeśli to mu się nie uda, oznacza to, że ktoś go w tym wyprzedził (zrobił to Dequer, sytuacja analogiczna niżej).

Problem jest prostszy, gdy enq() próbuje wywołać się na kolejce wypełnionej rezerwacjami. Na początek enq() upewnia się, że może bezpiecznie pracować na kolejce:

Następnie próbuje wypełnić pierwszą rezerwację swoim elementem poprzez compareAndSet() oraz zapisuje, czy mu się to powiodło:

Teraz enquer próbuje przestawić głowę dalej. To służy jedynie zwiększeniu wydajności, w poprzednim przypadku zapewniono, że głowa zostanie przeniesiona. Wobec tego nawet jeśli się nie uda, enquer nie przejmuje się, bo oznacza to, że ktoś go w tym uprzedził:

Jeśli wypełnianie rezerwacji nie powiodło się, oznacza to, że poprzednim elementem nie było null, zatem rezerwację zdążono już wcześniej wypełnić (inny enquer otrzymał polecenie działania), w tym wypadku należy ponowić enq() i wypełnić inną rezerwację. Natomiast jeśli się powiodło, kończymy działanie.

## Zadanie 5
:::success
Autor: Adam Jarząbek
:::
W tym zadaniu mamy wyjaśnić co jest nie tak z podaną implementacją stosu i zaproponować rozwiązanie.


W tej implementacji dzielimy metody push() i pop() na dwa etapy - rezerwacji i wypełniania. W fazie rezerwacji metody push() wykonujmy getAndIncrement() lub getAndDecrement() na górnym indeksie stosu, żeby zarezerwować miejsce. Następnie w fazie wypełniania wstawiamy element w zarezerowawane miejsce i oznaczamy je jako wypełnione.
Podobnie pop() najpierw próbuje wykonać getAndDecrement() na górnym indeksie stosu, a następnie pętli się dopóki flaga wypełnienia elementu nie zostanie podniesiona i zwraca ten element.

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

1. Element dodawany przez metodę push() może nie zostać zapisany w tablicy przed wykonaniem metody pop().

Rozważmy następującą sytuację: Wątek A wykonuje push(x) na pustym stosie. Po wykonaniu instrukcji w linii 9 zmienna top została ustawiona na 1, po czym wątek A został wywłaszczony. Teraz wątek B próbuje wykonać pop(). Do zmiennej i trafi wartość 0 (top - 1 = 1 - 1 = 0). W tablicy items w komórce o indeksie 0 nie ma żadnej wartości, więc pop() nie będzie mógł zwrócić poprawnego wyniku.

2.

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

    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: Magdalena Rzepka
:::


Jeżeli kolejka już jest pełna to nie wątek nie wejdzie dalej tylko się zawiesi między while a if isFull.
Jeżeli kolejka stanie się pełna po rooms.enter(0) to wycofujemy się z wykonanych akcji i zgłaszamy, że nastąpiło zapełnienie isFull i wracamy do początku while aby się zapętlić.

Ostatni wątek wychodzący z push() czyli z rooms(0) uruchomi funkcję onEmpty.
Po zwiększeniu kolejki wątki czekające będą mogły wejść do pokoju 0 i zostawić swoją wartość.

Do klasy Stack dodajemy zmienną boolean isFull = false;

public void old_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 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(0);
       continue;
}
items[i] = x;
rooms.exit(0);
return;
}
}

void onEmpty(){
if(isFull == false) return;
T[] newArray = new T[items.length * 2];
for(int i = 0; i<items.length; i++)
{
    newArray[i] = items[i];
}
items = newArray;
isFull = false;
return
}