# Ćwiczenia 12, grupa śr. 12-14, 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Michał Bronowicki | | | | | | | |
Wiktor Bukowski | | X | X | X | X | X | X |
Jan Dalecki | | X | X | | | | |
Mikołaj Depta | X | X | X | X | | | |
Kamil Galik | | | | | | | |
Bartosz Głowacki | | | | | | | |
Michał Hetnar | x | x | x | x | x | x | x |
Adam Jarząbek | | | | | | | |
Michał Kierul | | | | | | | |
Mateusz Kisiel | X | | X | | | | |
Maksymilian Komarnicki | X | X | X | | | | |
Julia Matuszewska | |==X==| X | X | | | |
Andrzej Morawski | | | | | | | |
Wojciech Pokój | | X | X | | | | |
Marcin Sarnecki | X | X | | | | | |
Bartosz Szczeciński | X | X | X | | | | |
Tomasz Wołczański | | X | X | | | | |
Marcin Wróbel | X | X | X | X | X |==X==| X |
:::

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

## Zadanie 1
:::success
Autor: Mikołaj Depta
:::

!--*--*--*--A'--(A)--*--!
!--D'--(D)--*--*--!
!--*--*--B'--(B)--*--*!
!--*--C'--(C)--*--!

------(D)---(C)--(B)-(A)----------
------(D')---(C')--(B')-(A')----------

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


Tak można, skoro metoda kończy się sukcesem to znaczy, że operacja CAS na head się uda.

T value = next.value;
if (head.compareAndSet(first, next))
    return value; 

Skoro operacja ta się powiedzie to znaczy, że wcześniej zapisana wartość była poprawna.
Późniejsze wątki na pewno zobaczą zmianę wprowadzoną przez CAS.


Tak, ponieważ metoda `enq` odbywa się w dwóch korkach:
1. dodanie logiczne - przepięcie wskaźnika `last.next`
2. dodanie fizyczne - zaktualizowanie wskaźnika `tail`.

Od momentu wstawienia logicznego, nawet jeśli wstawienie fizyczne się nie uda to wszystkie przyszłe operacje najpierw naprawią listę a dopiero potem wykonają swoją operację. Każde przyszłe wykonanie zobaczy wprowadzone zmiany (nawet jeśli samo będzie musiało dokończyć część operacji). Wiemy, że na pewno zanim wykonana zostanie następna operacja wykonane zostanie też dodawanie logiczne. Tym samym możemy bezpiecznie umiejscowić tam punkt linearyzacji.

## Zadanie 2
:::success
Autor: Julia Matuszewska
:::


**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.

1. proces P1 czyta wartość A z pamięci dzielonej
2. proces P1 jest wywłaszczony, a uruchamiany jest proces P2
3. proces P2 zmienia wartość w pamięci dzielonej z A na B, a następnie z powrotem na A przed wywłaszczeniem
4. proces P1 jest ponownie uruchamiany i widząc, że wartość w pamięci dzielonej się nie zmieniła, kontynuuje pracę

Mimo że P1 może kontynuować działanie, jest także możliwe, że takie zachowanie nie będzie prawidłowe z powodu „ukrytych” zmian w pamięci dzielonej.


**Jak to naprawić**
Do naprawy tego błędu można użyć `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.

**Przykład użycia**


## Zadanie 3
:::success
Autor: Tomasz Wołczański
:::

W synchronicznych strukturach danych producenci "spotykają się" z konsumentami: po włożeniu elementu do struktury producent zostaje uśpiony do momentu, gdy element zostanie pobrany przez konsumenta.


## Zadanie 4
:::success
Autor: Michał Hetnar
:::
**dualnych**: oznacza że producent i konsument zachowywóją się w ten sam sposób,
wiec kolejkujemy albo produkcje albo zamówienia.

private enum NodeType {ITEM, RESERVATION};
private class Node {
    volatile NodeType type;
    volatile AtomicReference<T> item;
    volatile AtomicReference<Node> next;
    Node(T myItem, NodeType myType) {
        item = new AtomicReference<T>(myItem);
        next = new AtomicReference<Node>(null);
        type = myType;
    }
}
public SynchronousDualQueue() {
        Node sentinel = new Node(null, NodeType.ITEM);
        head = new AtomicReference<Node>(sentinel);
        tail = new AtomicReference<Node>(sentinel);
    }
    public void enq(T e) {
        Node offer = new Node(e, NodeType.ITEM);
        while (true) {
            Node t = tail.get(), h = head.get();
            if (h == t || t.type == NodeType.ITEM) { //czy pusta lub czy zawiera pozycje oczekujace na usuniecie
                Node n = t.next.get();
                if (t == tail.get()) { // sprawdzamy czy sa zgodne
                    if (n != null) { // jesli nie ostatni to pomóz przepiac ogon i koniec
                    tail.compareAndSet(t, n); //25
                    } else if (t.next.compareAndSet(n, offer)) { //26 //dołaczamy nowy wezeł jak sie uda..
                        tail.compareAndSet(t, offer); //27 // przepinamy ogon
                        while (offer.item.get() == e); // czekamy az ktoś usunie nasz element
                        h = head.get(); 
                        if (offer == h.next.get()) //jezeli nasz element nadal jest pierwszy to ustawiamy go na head (wyreczamy tego kto usunął)
                        head.compareAndSet(h, offer); //31
                        return;
                    }
                }
            } else {
                Node n = h.next.get();// bierzemy z za head'a element
                if (t != tail.get() || h != head.get() || n == null) { // sprawdzamy czy spójne
                    continue;
                } // jak tak..
                boolean success = n.item.compareAndSet(null, e); //40  //zabieramy wartosc, ustawiamy stara na null
                head.compareAndSet(h, n);    //41 // przesuwamy głowe
                if (success) // zwracamy succes
                return;
            }
        }
}

**25 tail.compareAndSet(t, n); TEN**
sprawdzamy czy ktoś nie przepiął już ogona jak nie to to robimy. (25,27)
jeśli ktoś to zrobił nie ma powodu reagować

**26 t.next.compareAndSet(n, offer)**
ktoś mógł przypisać szybciej inny offer, bylismy drudzy.(26)

**27 tail.compareAndSet(t, offer); TEN**
sprawdzamy czy ktoś nie przepiął już ogona jak nie to to robimy. (25)
jeśli ktoś to zrobił nie ma powodu reagować

**31 head.compareAndSet(h, offer); TEN**
mógł to zrobić korzystający z produkcji (lub symetrycznie zamówienia) w (41)
nie trzeba tego sprawdzac bo jak się nie powiodło to nie ma powodu reagować bo jest już przepięte

**40 n.item.compareAndSet(null, e);**
ktoś już to zabrał jesteśmy drudzy

**41 head.compareAndSet(h, n); TEN**
mógł to zrobić tworzący produkcje (lub symetrycznie zamówienie) w (31) lub w (41) ten który był drugi
nie trzeba tego sprawdzac bo jak się nie powiodło to nie ma powodu reagować bo jest już przepięte

## Zadanie 5
:::success
Autor: Wiktor Bukowski
:::



Rozważmy następujący scenariusz na pustym stosie:
- wątek A wykonuje metodę `push(a)`
- wątek B wykonuje metodę `push(b)`
- wątek C wykonuje metodę `pop()`

Załóżmy, że opearcje na liczniku `top` wykonują się w kolejności A -> C -> B

Wtedy wątek A będzie wstawiać element na pozycję 0, C będzie odczytywać wartość z pozycji 0, a następnie B znów będzie zapisywać na pozycję 0. Jeśli A najpierw zapisze swoją wartość, a B ją nadpisze, to C zdejmie ze stosu wartość B, po czym pozostawi stos pustym.

Na pierwszy rzut oka, rozwiązaniem może być dodanie pętli analogicznej do tej z funkcji `pop()`, która będzie oczekiwać na ustawienie flagi `full` na false. Nie rozwiąże to jednak problemu. Prawidłową metodą poradzenie sobie z problemem jest używanie instrukcji `compareAndSet()` na konkretnych polach tablicy.

## Zadanie 6
:::success
Autor: Marcin Wróbel
:::
**Fig. 11.11**

public interface Rooms {
    public interface Handler {
        void onEmpty();
    }
    void enter(int i);
    boolean exit();
    public void setExitHandler(int i, Rooms.Handler h);
}

**Fig. 11.12**

public class Stack<T> {
    private AtomicInteger top;
    private T[] items;
    public Stack(int capacity) {
        top = new AtomicInteger();
        items = (T[]) new Object[capacity];
    }
    public void push(T x) throws FullException {
        int i = top.getAndIncrement();
        if (i >= items.length) { // stack is full
            top.getAndDecrement(); // restore state
            throw new FullException();
        }
        items[i] = x;
    }
    public T pop() throws EmptyException {
        int i = top.getAndDecrement() - 1;
        if (i < 0) {
            // stack is empty
            top.getAndIncrement(); // restore state
            throw new EmptyException();
        }
        return items[i];
    }
}

1. Problem:
nie ma gwarancji, że element zostanie zapisany do tablicy items przed ściągnięciem.
Przykład:
Mamy początkowo pustą tablicę `items`.
`Wątek A`, po wykonaniu pierwszej instrukcji w `push()` (`top.getAndIncrement()`) zmienia `top` na `-1`.
`Wątek B` wykona całe `pop()` i odczyta niepoprawną wartosć z `items[0]`, ponieważ `wątek A` nie zdążył umieścić elementu w tablicy `items`.
2. Rozwiązanie:

public class Stack<T> {
    private Rooms rooms;
    private AtomicInteger top;
    private T[] items;
    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) { // stack is full
            top.getAndDecrement(); // restore state
            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) {
            // stack is empty
            top.getAndIncrement(); // restore state
            rooms.exit();
            throw new EmptyException();
        }
        T item = items[i];
        rooms.exit();
        return item;
    }
}

## Zadanie 7
:::success
Autor: Marcin Wróbel
:::

Rozwiązanie:

public class Stack<T> {
    private Rooms rooms;
    private AtomicInteger top;
    private boolean isFull = false;
    private T[] items;
    
    private onEmpty() {
        if (!isFull) return;
        items = doubleArraySize(items);
        isFull = false;
    }
    
    public Stack(int capacity) {
        top = new AtomicInteger();
        items = (T[]) new Object[capacity];
        rooms = new Rooms();
    }
    public void push(T x) throws FullException {
        while (true) {
            while (isFull);
            rooms.enter(0);
            int i = top.getAndIncrement();
            if (i >= items.length) { // stack is full
                top.getAndDecrement(); // restore state
                isFull = true;
                rooms.exit();
                continue;
            }
        }
        items[i] = x;
        rooms.exit();
    }
    public T pop() throws EmptyException {
        rooms.enter(1);
        int i = top.getAndDecrement() - 1;
        if (i < 0) {
            // stack is empty
            top.getAndIncrement(); // restore state
            rooms.exit();
            throw new EmptyException();
        }
        T item = items[i];
        rooms.exit();
        return item;
    }
}