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

Tutaj można zadeklarować **zad. 9. z listy 10.**:
- Wiktor Hamberger
-
-

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

## Zadanie 1
:::success
Autor: Maria Szlasa
:::
:::info
Rozważmy standardową sekwencyjną (jednowątkową) implementację listową zbioru (elementy przechowywane na liście uporządkowanej względem kluczy, bez powtórzeń, ze strażnikami). Dlaczego zastąpienie wszystkich operacji przypisania referencji w funkcjach add() oraz remove() operacjami compareAndSet() nie daje w wyniku poprawnej współbieżnej implementacji zbioru? W jaki sposób użycie pola marked oraz klasy AtomicMarkableReference\<T\> pomaga w rozwiązaniu powstałego problemu?
Wskazówka: TAoMP2e, Fig. 9.21
Polska wersja: str 247-249 Fig. 9.22
:::

Zastąpienie wszystkich operacji przypisania referencji operacjami compare and set nie daje poprawnego wyniku, ponieważ może nastąpić nieprawidłowe wykonanie poleceń (nie uwzględniamy pola mark):


AtomicMarkableReference\<T\> posiada metodę:

compareAndSet(T expectedReference, 
    T newReference, 
    boolean expectedMark, 
    boolean newMark)

Aby rozwiązać problem, musimy zapewnić, żeby pole next usuniętego węzła nie było modyfikowane.

Zmieniamy typ pola next na AtomicMarkableReference\<T\>, którą aby upewnić się, że w międzyczasie nie została zmodyfikowana referencja do następnego węzła ani nie został on usunięty.

## Zadanie 2
:::success
Autor: Jan Jankowicz
:::

class Window {
	public Node pred, curr;
	Window(Node myPred, Node myCurr) {
		pred = myPred; curr = myCurr;
	}
}
	
public Window find(Node head, int key) {
	Node pred = null, curr = null, succ = null;
	boolean[] marked = {false};
	boolean snip;
	retry: while (true) {
		/* ustawiamy początkowe wartości pred i curr, zaczynając od head */
		pred = head;
		curr = pred.next.getReference();
		while (true) {
			succ = curr.next.get(marked);
			while (marked[0]) { /* dopóki następnik curr musi zostać fizycznie usunięty */
				snip = pred.next.compareAndSet(curr, succ, false, false);	/* próba fizycznego usunięcia logicznie usuniętego węzła */
				if (!snip) continue retry;  /* jeśli fizyczne usunięcie się nie uda, to zaczynamy od początku */
				curr = succ; /* jeśli fizyczne usunięcie się uda, to aktualizujemy element curr */
				succ = curr.next.get(marked); /* sprawdzamy kolejny węzeł na liście, czy też powinien zostać fizycznie usunięty i jeśli tak, to ponawiamy pętlę */
			}
			
			
			if (curr.key >= key)
				return new Window(pred, curr); /* w tym momencie dotarliśmy do pred i curr logicznie znajdujących się na liście i następujących bezpośrednio po sobie, przy okazji fizycznie eliminując napotkane węzły usunięte logicznie */
			
			/* przechodzimy do następnych elementów */
			pred = curr;
			curr = succ;
		}
	}
}

public boolean add(T item) {
	int key = item.hashCode();
	while (true) {
		Window window = find(head, key); /* znajdujemy miejsce wstawienia */
		Node pred = window.pred, curr = window.curr;  /* rozpakowujemy wskaźniki */
		if (curr.key == key) {
			return false;  /* jeśli klucz istnieje, to nie wstawiamy go */
		} else {
			/* tworzymy nowy węzeł, który wskazuje na znaleziony element curr */
			Node node = new Node(item);
			node.next = new AtomicMarkableReference(curr, false); 
			
			/* próbujemy dokonać przepięcia referencji pred na nowy węzeł */
			if (pred.next.compareAndSet(curr, node, false, false)) {
				return true; /* udało się zmienić następnika pred, gdyż był on nieusunięty, a jednocześnie dalej wskazywał na curr (czyli od momentu znalezienia Windowa żaden inny wątek nie zakłócił struktury listy w tym miejscu) */
			}
			/* nie udało się zmodyfikować, co oznacza, że udało się to już innemu wątkowi w międzyczasie; musimy powtórzyć operację wstawiania elementu od początku */
		}
	}
}

public boolean remove(T item) {
	int key = item.hashCode();
	boolean snip;
	while (true) {
		Window window = find(head, key); /* znajdujemy miejsce wstawienia */
		Node pred = window.pred, curr = window.curr; /* rozpakowujemy wskaźniki */
		if (curr.key != key) {
			return false; /* klucz nie istnieje w liście */
		} else {
			Node succ = curr.next.getReference(); /* pobieramy następnik obiektu usuwanego curr */
			snip = curr.next.attemptMark(succ, true); /* próbujemy logicznie usunąć element curr */
			if (!snip)
				continue; /* nie udało się usunąć curr, ponieważ przestał on już wskazywać na węzeł succ jako swojego następnika; ponawiamy próbę wykonania operacji remove od początu */
			pred.next.compareAndSet(curr, succ, false, false); /* podejmujemy od razu jedną próbę fizycznego usunięcia elementu */
			return true; /* niezależnie od wyniku fizycznego usunięcia wychodzimy z funkcji */
		}
	}
}

public boolean contains(T item) {
	boolean[] marked = false{};
	int key = item.hashCode();
	Node curr = head;
	while (curr.key < key) { /* przechodzimy przez całą listę bez fizycznego usuwania napotkanych logicznie usuniętych elementów jak w przyapdku add i remove */
		curr = curr.next;
		Node succ = curr.next.get(marked);
	}
	return (curr.key == key && !marked[0]) /* gdy dojdziemy do miejsca, w którym musi się ewentualnie znajdować szukany element, sprawdzamy, czy faktycznie jest nim curr, i czy jest jednocześnie logicznie nieusunięty.
}

Niepowodzenie wykonania instrukcji pred.next.compareAndSet(curr, ..., false, false) może wynikać z usunięcia elementu pred przez inny wątek (marked = true, a nie false, jak oczekujemy) lub z tego, że pred przestał wskazywać na curr, tak jak gdy zostało to ustalone przez find(); może to być skutkiem wstawienia przez inny wątek elementu x, takiego że pred.key < x < curr.key.

>Dlaczego rezultat drugiego wywołania compareAndSet() w metodzie remove() nie jest sprawdzany? Czy można je usunąć nie tracąc poprawności implementacji?

Wywołanie instrukcji pred.next.compareAndSet(curr, succ, false, false) w metodzie remove odpowiada za fizyczne usunięcie elementu. Nie ma konieczności sprawdzania jego skuteczności, gdyż jeśli nie uda się to teraz, to inny wątek podczas operacji add lub remove dokona fizycznego usunięcia takiego węzła albo już tego dokonał w międzyczasie.

## Zadanie 3
:::success
Autor: Wiktor Hamberger
:::

Z definicji Window:
> The find() method takes a head node and a key $a$, and traverses the list, seeking to set $pred$ to the node with the largest key less than $a$, and $curr$ to the node with the least key greater than or equal to $a$

Jako że $pred$ nie ma ustawionego $marked$, nie został usunięty (tylko $curr$ jest usunięty), zatem $pred$ dalej jest miejszy od $a$, a nowy $curr$ większy od $pred$, więc para $pred_x<a<=curr_x$ dalej istnieje w liście i wiadomo, że $pred<=pred_x$, więc można nie wracać do początku i iterować dalej.

## Zadanie 4
:::success
Autor: Adam Jarząbek
:::
Metoda jest lock-free, jeżeli przynajmniej jeden wątek zawsze dokonuje postępu.
W metodach add() i remove() wątki mogą się pętlić. Ale jeżeli się pętlą, to znaczy, że jakiś inny wątek dokonuje modyfikacji listy (tj add lub remove). A jeżeli inny wątek modyfikuje listę, to znaczy, że dokonuje postępu, więc te moetody są lock-free.

Metoda jest wait-free, wtedy, kiedy każdy wątek dokonuje postępu.
Metoda contains() jest wait-free, ponieważ szuka ona elementu >= kluczowi zaczynając od head. Elemetów < key jest skończenie wiele, więc każdy wątek dokonuje postępu.

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


Rozważmy następującą sytuację:
Wątek A wykonuje operację enq na pustej kolejce. Po wykonaniu instrukcji
tail.next = e; przechodzimy do wątku B, który wykonuje deq().
Wtedy wątek B nie zatrzyma się w pętli while (head.next == null),
co z kolei spowoduje wywołanie size.getAndDecrement(), po którym rozmiar kolejki size będzie wynosił -1.

## Zadanie 6
:::success
Autor: Daniel Boguszewski
:::

Zagubiona pobudka dla obiektów Condition jest podobną sytuacją do zakleszczenia dla zamków. Występuje w sytuacji, w której czekający na dopuszczenie do działania obiekt przegapił moment, w którym powinien przystąpić do pracy. W kolejce byłaby to sytuacja w której dequer (enquer działa w analogiczny sposób) nie otrzymałby sygnału do wyjęcia elementu z kolejki.

W ograniczonej kolejce istnieje mechanizm, w którym dequery trafiają do poczekalni, jeśli żadanie deq() pojawią się w momencie, w którym kolejka pozostaje pusta. Taki dequer zaczyna oczekiwać, aż warunek notEmptyCondition zostanie spełniony. Problem mógłby się pojawić, gdyby próbowano zoptymalizować proces i sygnalizować tylko jeden oczekujący dequer, gdy pusta kolejka zostanie uzupełniona o element. Jeśli do kolejki dodanoby kilka elementów, a w oczekiwaniu znajdowało się wiele dequerów, to ponieważ metoda signal() losowo wybiera, który dequer o tym powiadomić, mogłoby dojść do sytuacji, w której jeden dequer zostałby powiadomiany kilka razy, a pozostałe dequery niepotrzebnie by oczekiwały (przegapiły swoją pobudkę).

Kolejka z tego zadania rozwiązuje ten problem powiadamiając zawsze wszystkie oczekujące dequery metodą signalAll(). Jest to nieoptymalne o tyle, że będzie zdarzać się, że dequer z powrotem wróci do poczekalni, gdy kolejka okaże się pusta po jego pobudce, jednak opóźnienie, które to powoduje (a także walka o zamek deqLock), jest mniejszym problemem niż przegapione wyciągnięcie elementu z kolejki.

## Zadanie 7
:::success
Autor: Kamila Goszcz
:::


public T deq() throws EmptyException {
    T result;
    deqLock.lock();
    try {
        if (head.next == null) {
            throw new EmptyException();
        }
        result = head.next.value;
        head = head.next;
    } finally {
        deqLock.unlock();
    }
    return result;
}

Rozpatrzmy sytuację, gdy wątki A i B będą próbowały usunąć element z kolejki jednoelementowej:
1. Wątek A sprawdza czy zachodzi `head.next == null`, ale lista jest jednoelementowa a więc false
2. Wątek B sprawdza czy zachodzi `head.next == null` - może to zrobić ponieważ A nie założył locka
3. Wątek A usuwa element. Teraz head = head.next oraz head.next = null
4. Wątek B będzie chciał zrobić `result = head.next.value`, ale `head.next == null` a więc otrzymamy wyjątek `NullPointerException`

Zatem zajęcie locka jest konieczne

## Zadanie 8
:::danger
Autor: dodeklarować?
> [name=Piotr Witkowski]Wskazówka: TAoMP2e, str. 218
:::

## Zadanie 9
:::success
Autor: Zuzanna Kania
:::


Zasada konstrukcji LockFreeQueue jest podobna do UnboundedQueue, przy czym wskaźniki na węzły są teraz typu `AtomicReference<Node>`, co oznacza, że możemy wykonywać na nich operację `compareAndSet`. Dzięki temu możemy zrezygnować z zamków.

### enq()

* linia 25 - może zawieść, gdy inny wątek wstawi swój węzeł już po sprawdzeniu przez nasz wątek warunku w linii 24
* linia 26 - może zawieść, gdy inny wątek pomoże nam przesunąć ogon na nowo wstawiony węzeł. Nie wymaga sprawdzenia, ponieważ skoro inny wątek pomógł nam w naszej pracy, to wszystko jest w porządku
* linia 30 - może zawieść, gdy inny wątek wyprzedzi nas w pomaganiu w przesuwaniu ogona. Nie wymaga sprawdzenia, ponieważ nie jest to zasadniczy zakres obowiązków funkcji - tu tylko pomagamy innym i operacja dalej będzie poprawna, jeśli się to nie uda

### deq()

* linia 45 - może zawieść, gdy inny wątek wyprzedzi nas w pomaganiu w przesuwaniu ogona. Nie wymaga sprawdzenia, ponieważ tu tylko pomagamy innym
* linia 48 - może zawieść, gdy inny wątek wykona deq już po sprawdzeniu warunku `first == head.get()`