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

Rozważmy architekturę NUMA (non-uniform memory access). Procesory niech będą podzielone na klastry. Wiemy, że zmienne współdzielone w obrębie jednego klastra będą działać znacznie szybciej od zmiennych współdzielonych między klastrami. Zauważmy, że dla takiej architektury rozwiązanie typu 'Back-off Lock' nie jest zbyt dobrze dostosowane. Tj. wydajność znacznie spadnie w sytuacji, gdy zamek będzie często 'przechodził' między klastrami (tak naprawdę jego 'zajętość'). Możemy zmodyfikować koncept Back-off Lock -> właśnie poprzez zamek HBOLock.

Rozwiązanie to zmniejsza (w przypadku średnim) częstotliwość przechodzenia zamka między klastrami. Rozwiązanie opiera się o różne czasy 'back-off'-u dla wątków z tego samego klastra co wątek który obecnie posiada zamek w stosunku do pozostałych.

Tj. przeciętny czas backoff dla wątków w tym samym klastrze (co wątek posiadający zamek) jest średnio istotnie mniejszy niż dla pozostałych wątków. Dokładne wartośći {LOCAL/REMOTE}_{MIN/MAX}_DELAY podobnie jak dla Back-off Lock'a muszą zostać ustalone z uwzględnieniem szczegółów systemu.

Zatem jego wady są podobne jak w przypadku zwykłego Back-off Lock'a:

Zalety również są podobne, jest to zamek stosunkowo łatwy w implementacji. HBOLock w kodzie:

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

Zamki kohortowe pozwalają na użycie zamków na różnych poziomach w hierarchii pamięci. Mamy niezależne zamki dla każdej kohorty oraz wspólny,
globalny zamek umożliwiający komunikację pomiędzy kohortami. Dany wątek otrzymuje dostęp do sekcji krytycznej, jeśli zajmie zarówno zamek lokalny
dla swojej kohorty, jak i zamek globalny. Aby to osiągnąć wątek najpierw zajmie lokalny zamek, a następnie przed zajęciem zamka globalnego musi
się upewnić, że jego kohorta zajęła zamek globalny.

Przy wywołaniu unlock() wątek najpierw sprawdza, czy pewien wątek z jego kohorty nie próbuje zająć globalnego zamka. Jeśli taka sytuacja ma
miejsce, to musi mu ustąpić nie zwalniając globalnego zamka. W przeciwnym razie wątek zwalnia obydwa zamki, dzięki czemu wątki z innych kohort mają
możliwość zajęcia globalnego zamka. Aby jedna z kohort nie miała wyłączności na dostęp do zamków, takie rozwiązanie musi uwzględniać jakiś sposób
na odbieranie kohorcie globalnego zamka po upływie pewnej ilości czasu. Odpowiada za to klasa TurnArbiter.

Metoda alone() zwraca false, jeśli jakiś inny wątek z tej samej kohorty próbuje zająć globalny zamek.


## Zadanie 3
:::success
Autor: Patryk Mazur
:::

### 1.

Niezmiennik reprezentacji - Warunki, które muszą być spełnione przed wywołaniem metody i po jej wywołaniu
Mapa abstrakcji - Zbiór jaki przechowuje dana lista

Na przykładzie CoarseList:
Niezmiennik reprezentacji:

Mapa abstrakcji:
Element jest w zbiorze wtw gdy jest osiągalny z head

### 2.

add - 24 linijka
remove - 43 linijka
cotains - Zajęcie locka

### 3.
W momencie zajęcia zamka element nie został jeszcze dodany, przez co mapa abstrakcji z poprzedniego punktu nie jest poprawna (Element, który miałbyć dodany nie jest osiągalny z heada)
Analogicznie remove

### 4.
Element x należy do zbioru wtw.
(Element x jest osiągalny z head lub istnieje wykonanie add(x)) i nie istnieje wywołanie remove(x)

## Zadanie 4
:::success
Autor: Kamila Goszcz
:::


Zasady: Wartości $\infty$ oraz $-\infty$ nigdy nie są dodawane ani usuwane, węzły są sortowane według wartości klucza bez duplikatów, a element jest w zestawie wtedy i tylko wtedy, gdy jego węzeł jest osiągalny z głowy listy

public boolean add(T item) {
    int key = item.hashCode();
    head.lock();
    Node pred = head;
    
    try {
        Node curr = pred.next;
        curr.lock();
        try {
            while (curr.key < key) {
                pred.unlock();
                pred = curr;
                curr = curr.next;
                curr.lock();
            }
            if (curr.key == key) {
                return false;
            }
            Node newNode = new Node(item);
            newNode.next = curr;
            pred.next = newNode;
            return true;
        } finally {
            curr.unlock();
        }
    } finally {
        pred.unlock();
    }
}

public boolean remove(T item) {
    Node pred = null, curr = null;
    int key = item.hashCode();
    head.lock();
    try {
        pred = head;
        curr = pred.next;
        curr.lock();
        try {
            while (curr.key < key) {
                pred.unlock();
                pred = curr;
                curr = curr.next;
                curr.lock();
            }
            if (curr.key == key) {
                pred.next = curr.next;
                return true;
            }
            return false;
        } finally {
            curr.unlock();
        }
    } finally {
        pred.unlock();
    }
}

Punkt linearyzacji będzie zależał od wyniku metody `add()`:
* udało się wstawić element: moment podpięcia elementu `pred.next = newNode`. Mamy spełnione wszystkie niezmienniki:
* lista jest posortowana wg kluczy: `pred.key < newNode.key < curr.key` - `while` w linii 10
* lista nie posiada duplikatów `if` w linii 16
* nowy element jest osiągalny z głowy listy - przepięcie wskaźników w linii 21
* nie udało się wstawić: ostatnie wywołanie `curr.lock()` - linia 8 albo 14.

Punkt linearyzacji będzie zależał od wyniku metody `remove()`:
* udało się usunąć element - moment przepięcia wskaźnika wskazującego na usuwany element `pred.next = curr.next`. Mamy spełnione wszystkie niezmienniki:
* lista jest posortowana wg kluczy: `pred.key < deletedNode.key < curr.key` $\rightarrow$ `pred.key < curr.key`
* lista nie posiada duplikatów
* wszystkie elementy są osiągalne: przepięcie wskaźników w linii 17
* nie udało się usunąć: ostatnie wywołanie `curr.lock()` - linia 8 albo 14.

## Zadanie 5
:::success
Autor: Daniel Boguszewski
:::

Zadanie 5. Podaj implementację metody contains() dla klasy FineList. Uzasadnij jej poprawność.

public boolean add(T item) {
    head.lock();
    int key = item.hashCode();
    Node pred = head;
    try {
	Node curr = pred.next;
        while (curr.key <= key) {
            curr.lock();
            pred.unlock();
            pred = curr;
            curr = pred.next;
        }
    } finally pred.unlock();
    return pred.key == key;
}

public boolean contains(T item) {
int key = item.hashCode();
head.lock();
Node pred = head;
try {
Node curr = pred.next;
curr.lock();
try {
while (curr.key < key) {
pred.unlock();
pred = curr;
curr = curr.next;
curr.lock();
}
return (curr.key == key);

}
return true;
} finally {
curr.unlock();
}
} finally {
pred.unlock();
}
}

## Zadanie 6
:::success
Autor: Wiktor Hamberger
:::

Skrócone działanie:
* znajdź odpowiednie wierzchołki jak w FineList, ale bez używania "fine-grained locking"
* zablokuj zamki na tych wierzchołkach
* sprawdź, że:
* *pred* nadal jest osiągalny z HEAD
* *pred.next* nadal wskazuje na *curr*
* jeżeli tak, to wykonaj operację, jak nie to wróć do HEAD

1. Istnieje jakiś węzeł z key >= szukanego.
2. Remove() go znajduje.
3. Inny wątek go w tym czasie usuwa.
4. Remove() robi locki, failuje validate() i zdejmuje locki.
5. Jakiś wątek dodaje z powrotem ten węzeł.
6. Remove() wraca na początek listy.
7. Wracamy do 1.
## Zadanie 7
:::success
Autor: Jan Jankowicz
:::

> [name=Piotr Witkowski]Refleksja po ćwiczeniach: poprawność tego rozwiązania trzeba przemyśleć ponownie:

class StrongOptimisticList {

	private AtomicInteger version = new AtomicInteger(0);

	public boolean add(T item) {
		int key = item.hashCode();
		while (true) {
            /* change */
			int currentVersion = version.get();
			
			Node pred = head;
			Node curr = pred.next;
			while (curr.key <= key) {
				pred = curr; curr = curr.next;
			}
			pred.lock(); curr.lock();
			try {
                /* change */
				if (validate(currentVersion)) {
					if (curr.key == key) {
						return false;
					} else {
						Node node = new Node(item);
						node.next = curr;
						pred.next = node;
									
                        /* change */
                        version.increment();
						
						return true;
					}
				}
			} finally {
				pred.unlock(); curr.unlock();
			}
		}
	}
	
	public boolean remove(T item) {
		int key = item.hashCode();
		while (true) {	
            
            /* change */
            int currentVersion = version.get();
			
			Node pred = head;
			Node curr = pred.next;
			while (curr.key < key) {
				pred = curr; curr = curr.next;
			}
			pred.lock(); curr.lock();
			try {
                /* change */
				if (validate(currentVersion)) {
					if (curr.key == key) {
						pred.next = curr.next;
						
                        /* change */
						version.increment();
						
						return true;
					} else {
						return false;
					}
				}
			} finally {
				pred.unlock(); curr.unlock();
			}
		}
	}
	
	public boolean contains(T item) {
		int key = item.hashCode();
		while (true) {
            /* change */
			int currentVersion = version.get();
		
			Entry pred = this.head; // sentinel node;
			Entry curr = pred.next;
			while (curr.key < key) {
				pred = curr; curr = curr.next;
			}
			try {
				pred.lock(); curr.lock();
                /* change */
				if (validate(currentVersion)) {
					return (curr.key == key);
				}
			} finally {
				// always unlock
				pred.unlock(); curr.unlock();
			}
		}
	}
	
    /* change */
	private boolean validate(int savedVersion) {
		return version.get() == savedVersion;
	}
	
}

## Zadanie 8
:::success
Autor: Zuzanna Kania
:::

Motywacją jest to, że nie chcemy, żeby contains zajmowało zamek - jest to operacja wykonywana często, a nic nie modyfikuje.

Implementacja LazyList różni się od OptimisticList tym, że wprowadza rozróżnienie na usunięcie węzła logiczne (zaznaczenie go jako nieaktualny) i fizyczne (faktyczne wypięcie z listy). Powoduje to również drobną zmianę w mapie abstrakcji - teraz element jest w zbiorze, jeśli jego węzeł jest osiągalny i nieoznaczony.

Dzięki temu walidacja jest prostsza, bo nie wymaga ponownego przechodzenia listy. Natomiast sprawdzenie węzła w contains wymaga jedynie sprawdzenia, czy znaleziony węzeł nie jest oznaczony.

---

Metoda add jest taka sama jak w OptimisticList (nie licząc nowej metody walidacji), metoda remove ma jedynie dodane usuwanie logiczne, a metoda contains jest dużo prostsza, ponieważ wymaga tylko sprawdzenia, czy węzeł nie jest oznaczony.


---

Nie można zrealizować metody remove() z tylko jednym zamkiem.

Na powyższym przykładzie otrzymujemy sytuację, kiedy w łańcuchu węzłów pozostaje wpięty węzeł "do usunięcia". Węzeł ten nie zostanie nigdy usunięty przez garbage collector, ponieważ wskazuje na niego poprzednik. Ponadto, nie będzie można nigdy więcej dodać/usunąć wartości z tego węzła ani dodać/usunąć jego następnika, ponieważ nie pozwoli na to walidacja. Zatem taka implementacja jest niepoprawna.

## Zadanie 9
:::danger
Autor: Wiktor Hamberger

:::

To show that a concurrent data structure is a linearizable implementation of a sequential object, it suffices to identify a linearization point, an atomic step where the method call “takes effect”; we say it is linearized at this point. [...] Here, add(a) adds a to the abstract set, remove(a) removes a from the abstract set, and contains(a) returns true or false, depending on whether a was already in the set.

Niech zmodyfikowana metoda contains() nie zajmuje żadnych zamków w OptimisticList:

Zauwżmy, że funkcja zakończy się tylko i wyłącznie jeżeli nastąpi poprawne wykonanie validate(). W takim wypadku istniał moment w czasie, w którym końcowy pred i curr były osiągalne z głowy listy i pred wskazywał na curr i w tym momencie wartość zwracana w contains() była prawidłowa względem abstrakcyjnego zbioru, więc możemy wybrać ten moment w czasie jako punkt linearyzacji, więc odpowiedź na zadanie brzmi: tak.

---


Nie, ponieważ wątek A może usunąć element logicznie (punkt linearyzaji remove()) i zasnąć, wątek B może wykonać contains() na elemencie usuniętym przez A i zwrócić true, pomimo, że w abstrakcyjnym zborze element nie istnije, więc nie da się wybrać punktu linearyzacji, bo od początku wynik zwrócowny przez contains() będzie błędny.