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

Tutaj można zadeklarować **zad. 9. z listy 10.**:
- Maksymilian Komarnicki
- Mikołaj Depta
-

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

## Zadanie 1
:::success
Autor: Michał Hetnar
:::
Dlaczego zastąpienie wszystkich operacji
przypisania referencji w funkcjach add() oraz remove()
operacjami compareAndSet() nie daje w wyniku poprawnej
współbieżnej implementacji zbioru?

object.CompareAndSet(objec2,objct3)
- jeżeli object =object 2 to przypisz do object <- object3
Podajmy kontr przykłady:
mamy:
h -> a -> c -> t
dwa wątki równolegle chcą
- dodać b
- usunac a

powinno być:
h->b->c->t

ale:
(Wstawianie b)
b.next <- c

(usuwamy a)
if h.next == a
to wstawiamy h.next <- c

(Wstawianie b)

if a.next == c
to wstawiamy h.next <- a.next

mamy:
h->a->c

h->a->c
___b->c

h->c
a->c
b->c

____h-> c -> t
a -> b -> c

czyli

h->c
(nie dodaliśmy b!)
oraz

mamy:
h-> a ->b -> t

usuwamy a i b

zamiast

h-> t

if a. next == b.next
a.next <- c

if h.next == a.next
h.next <- b (succ)

mamy:
h ->b -> t

Jeśli dodamy klase AtomicMarkableReference

to pole marked mówi nam że dany wierzchołek na liscie jest usuniety
i operacje add oraz remove usuną wszystkie takie zanim przejda do modyfikacji
a warunkiem do jakich zmian jest nowa operacja compareandset która sprawdza również nastepny wskaznik czy niejest do usuniecia.

## Zadanie 2
:::success
Autor: Wojciech Pokój
:::

Opisz w dokładny sposób działanie metody find() z
klasy Window oraz metod add(), remove() i contains() z klasy
LockFreeList. W szczególności, dla każdego wywołania
compareAndSet() występującego w treści tych metod wymień
wszystkie powody, dla których może ono zawieść (zwrócić
false). Dlaczego rezultat drugiego wywołania compareAndSet() w
metodzie remove() nie jest sprawdzany? Czy można je usunąć nie
tracąc poprawności implementacji?

Wskazówka: TAoMP2e, r. 9.8


Zadanie klasy window i metody find jest przejście listy w poszukiwaniu żądanego klucza po drodze usuwając fizycznie usuwając węzły które były usunięte logicznie.

Opecja CAS w linijce 17 może się nie powieść w 2 sytuacjach:

1. curr jesr zamarkowany - curr został w międzyczasie poddany logicznemu usunięciu więc nie można wskaźnika przepiąć
2. pred.next i curr są różne - został wstawiony nowy element


Dodawanie nowego elementu

CAS może się nie powieść w 2 sytuacjach:

1. curr został zamarkowany i logicznie usunięty
2. wskaźniki wskazują na różne wartości więc coś w międzyczasie zostało dodane


Usuwanie elemntu - po znalezieniu elementu usuwamy go logicznie
i CASem próbujemy go usunąć fizycznie, jeśli się nie uda, pomijamy usuwanie i pozostawiamy to findowi

UWAGA

attemptMark w linii 26 to tak naprawdę curr.next.compareAndSet(succ, succ, false, true);

CAS w linii 25 może się nie powieść gdy zmienił się następnik lub został wcześniej logicznie usunięty.

CAS w linijce 30 może się nie powieść jeśli został wstawiony nowy elemet lub poprzednik został usunięty logicznie

Wynik próby usuwania nie jest sprawdzany ponieważ bez tej próby ciągle dostajemy popraawnie działąjący algorytm (problemem usuwania pierwotnie zajmuje się find)


Przeszukujemy listę dopóki nie napotkamy elementu o właściwym kluczu

## Zadanie 3
:::success
Autor: Julia Matuszewska
:::


Jeżeli `pred` nie ma ustawionego pola `marked` to nie został logicznie usunięty z listy.
W tym wypadku nie musimy zaczynać od początku, tylko od `pred`, ponieważ jest on na liście, więc poszukiwane miejsce na dodanie elementu występuje gdzieś po `pred`, ze względu na posortowanie elementów.
Niezmiennik `pred.key < key && curr.key >= key` nadal jest aktualny.

## Zadanie 4
:::success
Autor: Marcin Sarnecki
:::

Metoda `contains` iteruje się do znalezienia elementu większego, bądź równego `key`. Nie można dodać nieskończenie wielu elementów pomiędzy `head` a szukanym elementem, więc metoda jest `wait-free`

Metody `add` i `remove` są `lock-free`, ponieważ jeśli się zapętlą, to dlatego, że inne wątki zmodyfikowały listę, zatem przynajmniej jeden wątek dokonał postępu.

## Zadanie 5
:::success
Autor: Mateusz Kisiel
:::


public class BoundedQueue <T> {
    ReentrantLock enqLock, deqLock;
    Condition notEmptyCondition, notFullCondition;
    AtomicInteger size;
    volatile Node head, tail;
    final int capacity;
    public BoundedQueue(int _capacity) {
        capacity = _capacity;
        head = new Node(null);
        tail = head;
        size = new AtomicInteger(0);
        enqLock = new ReentrantLock();
        notFullCondition = enqLock.newCondition();
        deqLock = new ReentrantLock();
        notEmptyCondition = deqLock.newCondition();
    }

    
    public void enq(T x) {
        boolean mustWakeDequeuers = false;
        Node e = new Node(x);
        enqLock.lock();
        try {
            while (size.get() == capacity)
                notFullCondition.await();
            tail.next = e;
            tail = e;
            if (size.getAndIncrement() == 0)
                mustWakeDequeuers = true;
        } finally {
            enqLock.unlock();
        }
        if (mustWakeDequeuers) {
            deqLock.lock();
            try {
                notEmptyCondition.signalAll();
            } finally {
                deqLock.unlock();
            }
        }
    }
    public T deq() {
        T result;
        boolean mustWakeEnqueuers = false;
        deqLock.lock();
        try {
            while (head.next == null)
                notEmptyCondition.await();
            result = head.next.value;
            head = head.next;
            if (size.getAndDecrement() == capacity) {
                mustWakeEnqueuers = true;
            }
        } finally {
            deqLock.unlock();
        }
        if (mustWakeEnqueuers) {
            enqLock.lock();
            try {
                notFullCondition.signalAll();
            } finally {
                enqLock.unlock();
            }
        }
        return result;
    }
}

:::info
Czy istnieje taka sekwencja wykonań metod ```enq()``` i ```deq()```, że zmienna *size()* staje się ujemna?
:::
Niech wątek 1 wykonuje enque i po wykonaniu linijki `tail.next = e;` sheduler przełacza się na drugi wątek, który wykonuje deque. W tym przypadku wątek drugi stwierdzi, że są jakieś elementy(choć ich jeszcze fizycznie nie ma) i zrobi deque zmieniając licznik na -1.

## Zadanie 6
:::success
Autor: Bartosz Szczeciński
:::


Problem zagubionej pobudki występuje w przypadku, kiedy któreś wątki czekają na wybudzenie nie zauważając, że ich warunek na wybudzenie został już spełniony.

#### Wysyłanie sygnału i czekanie na niego odbywa się w miejscach zabezpieczonych tym samym zamkiem (`enqLock` lub `deqLock`), więc przykładowo `enq()` w trakcie wykonywania nigdy nie przegapi sygnału `notFullCondition`

#### Za każdym razem wywołujemy `signalAll()`
Gdybyśmy wywoływali `signal()`, czyli budzili tylko jeden wątek to mogłoby się zdarzyć:

1. Zaczynamy od pustej kolejki
2. Wątek A wywołuje `deq()` i czeka w poczekalni na `notEmptyCondition.await()`
3. Wątek B wywołuje `deq()` i czeka w poczekalni na `notEmptyCondition.await()`
4. Wątek C wywołuje `enq(x)` i budzi jeden z wątków wywołaniem `signal()` (powiedzmy, że budzi się A i czeka na zamek `deqLock`)
5. Wątek D wywołuje `enq(x)` i wstawia element, zanim A skończy swoje `deq()`. Kolejka nie była pusta, więc D nie wywołuje `signal()`
6. Wątek A zdejmuje element wstawiony przez C.
7. Wątek B czeka, mimo że w kolejce jest jeden element wstawiony przez D.

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


Gdyby w metodzie `deq` klasy `UnboundedQueue` sprawdzenie niepustości kolejki odbywało się przed zajęciem zamka, to mogłoby dojść do następującej sytuacji:

Załóżmy, że w kolejce znajduje się tylko jeden element. Wątek $A$ wywołuje `deq`, sprawdza warunek niepustości i zostaje zatrzymany tuż przed zajęciem zamka `deqLock`. Następnie wątek $B$ wywołuje `deq`, sprawdza warunek niepustości, zajmuje zamek, modyfikuje wskaźnik `head`, zwalnia zamek i zwraca pobraną wartość. Jeśli teraz wątek $A$ zostanie wznowiony, to zajmie zamek i spróbuje odczytać `head.next.value`, ale `head.next` ma wartość `null`, więc wyrzucony zostanie wyjątek `NullPointerException`.

## Zadanie 8
:::success
Autor: Maksymilian Komarnicki
:::

public boolean add(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) {
                        return false;
                    } else {
                        Node node = new Node(item);
                        node.next = curr;
                        pred.next = node;
                        return true;
                    }
                }
            } finally {
                curr.unlock();
            }
        } finally {
            pred.unlock();
        }
    }
}

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) {
                        return false;
                    } else {
                        curr.marked = true;
                        pred.next = curr.next;
                        return true;
                    }
                }
            } finally {
                curr.unlock();
            }
        } finally {
            pred.unlock();
        }
    }
}

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

1. Add()
Punkty linearyzacji dla wywołania zakończonego:
- sukcesem - moment przyłączenia nowego węzła do listy(linia 19)
- porażką - moment zwrócenia wartości z funkcji(linia 15)
2. Remove()
Punkty linearyzacji dla wywołania zakończonego:
- sukcesem - moment ustalenia pola jako marked(linia 48)
- porażką - moment zwrócenia wartości z funkcji(linia 46)
3. Contains()
Punkty linearyzacji dla wywołania zakończonego:
- sukcesem - moment znalezienia węzła nieoznaczonego jako marked(linia 67)
- porażką:
- przypadek 1 - moment znalezienia węzła o prawidłowym kluczu, który jest oznaczony jako marked
- przypadek 2 - moment nie jest możliwy do wskazania w kodzie - bezpośrodnio przed tym, gdy nowy odpowiadający węzeł został dodany

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

public class LockFreeQueue < T > {
    AtomicReference < Node > head,
    tail;
    public LockFreeQueue() {
        Node node = new Node(null);
        head = new AtomicReference(node);
        tail = new AtomicReference(node);
    }
    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) {
                    // Logiczne enq
                    if (last.next.compareAndSet(next, node)) {
                        
                        // Fizyczne enq
                        // Zmieniamy tail, nie sprawdzamy zwracanej wartości
                        // ponieważ albo się nam udało, albo inny wątek nam pomógł
                        tail.compareAndSet(last, node);
                        return;
                    }
                } else {
                     // próbujemy pomóc "wolniejszemu" wątkowi w zmianie taila
                     // Nie sprawdzamy zwracanej wartości, bo jeśli nie pomogliśmy,
                     // to ktoś inny pomógł, albo "wolny" wątek sam zmienił taila
                    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) {
                    // Wartownik jest jedynym fizycznie dodanym elementem
                    if (next == null) {
                        // Nie ma żadnych logicznie dodanych elementów
                        throw new EmptyException();
                    }
                 
                    // Jakiś element został logicznie dodany jako następnik taila
                    // próbujemy pomóc "wolniejszemu" wątkowi
                    // Nie sprawdzamy zwracanej wartości, bo jeśli nie pomogliśmy,
                    // to ktoś inny pomógł, albo "wolny" wątek sam zmienił taila
                    tail.compareAndSet(last, next);
                } else {
                    T value = next.value;
                    if (head.compareAndSet(first, next))
                        return value;
                }
            }
        }
    }
}

:::info
Dla każdego wywołania metody **compareAndSet()** w kodzie **enq()** i **deq()** wymień wszystkie powody, dla których może ono zawieść.
:::
17: `last.next.compareAndSet(next, node)` może zawieść, gdy
- inny wątek dodał inny element do kolejki

22: `tail.compareAndSet(last, node)` może zawieść gdy:
- inny wątek nam pomógł

29: `tail.compareAndSet(last, next)` może zawieść, gdy:
- inny wątek pomógł już "wolnemu" wątkowi
- "wolny" wątek wykonał przepięcie wskaźników, w którym chcieliśmy pomóc

52: `tail.compareAndSet(last, next)` może zawieść, gdy:
- inny wątek pomógł już "wolnemu" wątkowi
- "wolny" wątek wykonał przepięcie wskaźników, w którym chcieliśmy pomóc

55: `head.compareAndSet(first, next)` może zawieść, gdy:
- inny wątek wyciągnął pierwszy element kolejki, który chcieliśmy wyciągnąć

:::info
Dla wszystkich wywołań tej metody, których wartość zwracana nie jest sprawdzana wyjaśnij, dlaczego tak jest.
:::
Wyjaśnienia w komentarzach w kodzie
:::info
Co to znaczy, że “szybsze” wątki pomagają w działaniu
wątkom “wolniejszym”?
:::
Jeżeli jakiś wątek nie wykonał jeszcze pewnego działania, np. przepięcia wskaźników, bo przykładowo system nie przydzielił mu jeszcze czasu procesora, to nazywamy go "wolnym". Wątki, które zauważyły, że wyżej wymienione działanie nie zostało wykonane pomagają "wolnemu" wątkowi poprzez wykonanie tego działania.