# Ćwiczenia 11, grupa cz. 16-18, 4 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- |
Dominik Baziuk | X | X | X | X | | |
Paweł Borek | | | | | | |
Arti Brzozowski | | | | | | |
Mateusz Golisz | | | | | | |
Kacper Jóźwiak | | | X | X | | X |
Julia Konefał | | | | | | |
Adam Korta | | | | | | |
Jakub Mikołajczyk | X | X | X | X | | X |
Bartosz Morasz | x | x | x | x | | x |
Andrzej Morawski | x | x | x |==x==| | x |
Aleksandra Nicpoń | | | | | | |
Mateusz Reis | x | x | x | x | | x |
Tomasz Stachurski | x | x | x | x | |==x==|
Marcel Szelwiga | X | X | X | X | X | |
Volha Tsekalo | | | x | x | | x |
Martyna Wybraniec | | | | | | |
Denys Zinoviev | | | | | | |
Dominik Olejarz | x | x | x | x | | |
:::

Tutaj można zadeklarować zaległe zadanie 8 z listy 10:

:::danger
| | 10.8 |
| ----------------------:| ----- |
| | |
| | |
:::

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

## Zadanie 1
:::success
Autor: Jakub Mikołajczyk
:::


Wątek A zamierza usunąć węzeł a, natomiast wątek B chce dodać węzeł b. Jeśli wątek A wykona metodę ```compareAndSet()``` na polu ``head.next``, natomiast wątek B tę samą metodę na polu ``a.next``. Efektem będzie poprawne usunięcie a, ale b nie zostanie wstawione na listę


Wątek A chce usunąć a, natomiast wątek B chce usunąć węzeł b, na który wskazuje a. Wątek A wykonuje metodę ```compareAndSet()``` na polu ``head.next``, a wątek B na polu ``a.next``. Efektem będzie usunięcie wezła a, ale nie węzła b.

**W jaki sposób użycie pola marked oraz klasy AtomicMarkableReference<T> pomaga w rozwiązaniu powstałego problemu?**


Klasa ta posiada metode compareAndSet, która atomowo potrafi sprawdzić pole marked. Dzięki czemu jesteśmy w stanie wyłapać moment w którym modyfikujemy usunięty węzeł.

## Zadanie 2
:::success
Autor: Bartosz Morasz
:::

Find zwraca nam parę wierzchołków: pred i curr, takie że w add() nasz nowy node wstawimy pomiędzy pred i curr, natomiast w remove() usuniemy curr.

W find CAS może zawieść:
- pred.next != curr
oznacza to, że curr już nie jest następnikiem prev. Curr mógł zostać usunięty lub pojawil sie nowy node miedzy nimi
- pred.next.isMarked() != false
oznacza ze pred został usunięty w między czasie


W add CAS może zawieść:
- pred.next != curr
oznacza to, że curr już nie jest następnikiem prev. Curr mógł zostać usunięty lub pojawil sie nowy node miedzy nimi
- pred.next.isMarked() != false
oznacza ze pred został usunięty w między czasie


W remove CAS może zawieść:
1.

- curr.next != succ
oznacza to, że succ już nie jest następnikiem curr. Succ mógł zostać usunięty lub pojawil sie nowy node miedzy nimi
- curr.next.isMarked() != false
oznacza ze curr został usunięty w między czasie

2.

- pred.next != curr
oznacza to, że curr już nie jest następnikiem prev. Curr mógł zostać usunięty lub pojawil sie nowy node miedzy nimi
- pred.next.isMarked() != false
oznacza ze pred został usunięty w między czasie

Nie musimy robić tego ostatniego CAS, bo może za nas to zrobić find().


## Zadanie 3
:::success
Autor: Dominik Olejarz
:::
Nie musimy przeglądac całej listy, ponieważ pred nie zostało usunięte(nie ma zmienionego marka). W związku z tym, musimy przejrzeć fragment listy, zaczynając od pred do końca, ponieważ lista jest posortowana, a wcześniej wiedzieliśmy, że pred.key < key, a curr.key >= key.

## Zadanie 4
:::success
Autor: Andrzej Morawski
:::

### Metoda $contains()$ jest wait-free

Metoda $contains$ wykonuje się do momentu aż nie znajdziemy elementu o kluczu $\ge$ od szukanego. Zatem zawsze zakończy się w skończonej liczbie kroków, ponieważ lista na której wykonujemy operacje jest skończona.

### Metody $add()$ i $remove()$ są lock-free

Metody $add$ i $remove$ mogą się zapętlać w nieskończoność. Ale następuje to tylko gdy dochodzi do modyfikacji listy w trakcie wykonywania tych metod. Zatem istnieje takie wywołanie metody $add$ lub $remove$, które zakończyło się sukcesem. Cały program wykonuje postęp, więc te metody są lock-free.

## Zadanie 5
:::success
Autor: Marcel Szelwiga
:::

class Window {
	public Node pred, curr;
	Window(Node myPred, Node myCurr) {
		pred = myPred; curr = myCurr;
	}
}
Window find(Node head, int key) {
	Node pred = null, curr = null, succ = null;
	boolean[] marked = {false};
	boolean snip;
	retry: while (true) {
		pred = head;
		curr = pred.next.getReference();
		while (true) {
			succ = curr.next.get(marked);
			while (marked[0]) {
				snip = pred.next.compareAndSet(curr, succ, false, false);
				if (!snip) continue retry;
				curr = succ;
				succ = curr.next.get(marked);
			}
			if (curr.key >= key)
				return new Window(pred, curr);
			pred = curr;
			curr = succ;
		}
	}
}
public boolean add(T item) {
	int key = item.hashCode();
	while (true) {
		Window window = find(head, key);
		Node pred = window.pred, curr = window.curr;
		if (curr.key == key) {
			return false;
		} else {
			Node node = new Node(item);
			node.next = new AtomicMarkableReference(curr, false);
			if (pred.next.compareAndSet(curr, node, false, false)) {
				return true;
			}
		}
	}
}
public boolean remove(T item) {
	int key = item.hashCode();
	boolean snip;
	while (true) {
		Window window = find(head, key);
		Node pred = window.pred, curr = window.curr;
		if (curr.key != key) {
			return false;
		} else {
			Node succ = curr.next.getReference();
			snip = curr.next.compareAndSet(succ, succ, false, true);
		if (!snip)
			continue;
		pred.next.compareAndSet(curr, succ, false, false);
		return true;
	}
}
public boolean contains(T item) {
	int key = item.hashCode();
	Node curr = head;
	while (curr.key < key) {
		curr = curr.next.getReference();
	}
	return (curr.key == key && !curr.next.isMarked())
}

Chcemy pokazać, że wywołania funkcji `add`, `remove` i `contains` są linearyzowalne, pokażmy zatem ich punkt linearyzacji, w zależności od tego w jaki sposób się zakończyły:

* punktem linearyzacji funkcji `add` może być miejsce, w którym funkcja wykonuje instrukcję ```pred.next.compareAndSet(curr, node, false, false)``` gdy funkcja zakończyła się powodzeniem lub moment odczytu ```marked[0]``` jako false w funkcji `find`.

* punktem linearyzacji funkcji `remove` może być miejsce, w którym funkcja wykonuje instrukcję ```curr.next.compareAndSet(succ, succ, false, true);```, w przypadku gdy funkcja zakończyła się powodzeniem lub w momencie odczytu ```marked[0]``` jako false w funkcji `find`.

* punktem linearyzacji funkcji contains może być sprawdzenie poprawności warunku ```(curr.key == key && !curr.next.isMarked())```.

## Zadanie 6
:::success
Autor: Tomasz Stachurski
:::


Przykład:

Wątek A wykonuje `enq()` na pustej kolejce i kończy działanie na `tail.next = e`. Wchodzi wątek B i wykonuje `deq()`. B nie zostanie zatrzymane w `while (head.next == null)`, bo A wstawił element. B usunie wstawiony przez A element i zmniejszy `size` o 1, czyli `size = -1`.