---
# System prepended metadata

title: 'Ćwiczenia 11, grupa cz. 16-18, 4 stycznia 2024'
tags: [pwit, ćwiczenia, PRW23]

---

# Ć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	
:::

![image](https://hackmd.io/_uploads/r1ccnrEO6.png)

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ę 

![image](https://hackmd.io/_uploads/BJ8yCHEOp.png)

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

![image](https://hackmd.io/_uploads/Skgx1INu6.png)

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
:::
![image](https://hackmd.io/_uploads/BJbe_ZmuT.png)

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

![image](https://hackmd.io/_uploads/BJlfOZmOT.png)

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

    
![image](https://hackmd.io/_uploads/SyLY_-XuT.png)

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().
    
    
![image](https://hackmd.io/_uploads/BJNcd-mup.png)


## Zadanie 3
:::success
Autor:	Dominik Olejarz	
:::
![image](https://hackmd.io/_uploads/rkV-aS4dp.png)
![image](https://hackmd.io/_uploads/B1XiaSNOp.png)
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
:::
```java=
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
:::

![image](https://hackmd.io/_uploads/HkFKpSQOT.png)
![image](https://hackmd.io/_uploads/SyrqaSXup.png)
![image](https://hackmd.io/_uploads/SkVi6rmOa.png)

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