# Ćwiczenia 10, grupa cz. 16-18, 21 grudnia 2023

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

Tutaj można zadeklarować zaległe zadanie 7 z listy 9:

:::success
| | 9.7 |
| ----------------------:| ----- |
| | |
| | |
:::

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

## Zadanie 1
:::success
Autor: Kacper Jóźwiak
:::

Jeśli mamy procesory zgrupowane w klastry, to przekazywanie zamka między
procesorami z różnych klastrów zajmuje znacznie więcej czasu niż między takimi,
które należą do tego samego klastra. Przekazywanie zamka między wątkami z tego
samego klastra to idea stojąca za `HBOLock`.

public class HBOLock implements Lock {
	private static final int LOCAL_MIN_DELAY = ...;
	private static final int LOCAL_MAX_DELAY = ...;
	private static final int REMOTE_MIN_DELAY = ...;
	private static final int REMOTE_MAX_DELAY = ...;
	private static final int FREE = -1;
	AtomicInteger state;

	public HBOLock() {
		state = new AtomicInteger(FREE);
	}

	public void lock() {
		int myCluster = ThreadID.getCluster();
		Backoff localBackoff =
			new Backoff(LOCAL_MIN_DELAY, LOCAL_MAX_DELAY);
		Backoff remoteBackoff =
			new Backoff(REMOTE_MIN_DELAY, REMOTE_MAX_DELAY);
		while (true) {
			if (state.compareAndSet(FREE, myCluster)) {
				return;
			}
			int lockState = state.get();
			if (lockState == myCluster) {
				localBackoff.backoff();
			} else {
				remoteBackoff.backoff();
			}
		}
	}
	public void unlock() {
		state.set(FREE);
	}
}

Poprzez zwiększenie czasu odczekiwania wątków z innych klastrów od wątku
trzymającego zamek, względnie do wątków w tym samym klastrze, lokalne wątki będą
mogły założyć zamek z większym prawdopodobieństwem. Żeby to osiągnąć, musimy
zapisać klaster, do którego przynależy wątek trzymający zamek.

## Zadanie 2
:::success
Autor: Dominik Baziuk
:::

:::info
Czym są zamki kohortowe?
:::

Rozwijają rozwiązanie problemu z przeskakiwaniem między clusterami.

Każdy cluster/cohort ma swój zamek i mamy zamek globalny.

Aby wejść do sekcji krytycznej wątek musi zająć dwa zamki.

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 wątek z jego cohorty nie próbuje zająć globalnego zamka.
Jeśli tak 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.
:::info
Czemu służy klasa TurnArbiter oraz metoda alone()?
:::
TurnArbiter sprawdza czy wątki mają z tej samej kohorty zadługo nie mają zamka na wyłączność i odbiera im dostęp ustawiając TURN_LIMIT.

alone() zwraca false gdy jakiś wątek

:::info
Przedstaw i wyjaśnij przykładową implementację tych zamków.
:::

## Zadanie 3
:::success
Autor: Martyna Wybraniec
:::



**Niezmiennik reprezentacji** - warunek, który musi zostać zachowany przed i po wywołaniu metody, dla CoarseList jest to:

1. Klucz dowolnego węzła musi być mniejszy od klucza swojego następnika (zatem lista jest posortowana i klucze są unikatowe)
2. Klucz dowolnego węzła dodanego, usuniętego lub wyszukanego musi być mniejszy od taila i większy od heada.

**Mapa abstrakcji** - zbiory otrzymywalne z list, dla CoarseList jest to:

Element znajduje się w zbiorze wtedy i tylko wtedy, kiedy jest osiągalny z węzła head.

**Punkty linearyzacji dla add(), remove() i contains()**

a) add()
`pred.next = node` (linijka 24)

b) remove()
`pred.next = curr.next` (linijka 43)

c) contains()
`lock.lock()`

**Pokaż, że mapa abstrakcji z poprzedniego punktu nie jest poprawna, jeśli metody będą linearyzowane w momencie zajęcia zamka.**

W metodach add() i remove() zajmujemy zamek zanim dokonamy wstawienia lub usunięcia węzła, zatem ustawiając w tym miejscu punkt linearyzacji twierdzenie "Element znajduje się w zbiorze wtedy i tylko wtedy, kiedy jest osiągalny z węzła head." nie jest poprawne.

**Zmodyfikuj powyższą mapę abstrakcji tak, by dla metod linearyzowanych w momencie zajęcia zamka, CoarseList nadal była poprawną implementacją zbioru.**

"Element x znajduje się w zbiorze wtedy i tylko wtedy, kiedy (*) jest osiągalny z węzła head i zamek nie jest zajęty przez metodę remove(x) lub (**) zamek jest zajęty przez metodę add(x)"

## Zadanie 4
:::success
Autor: Marcel Szelwiga
:::

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

Chcemy pokazać, że metody `add` i `remove` są linearyzowalne -- to jest -- istnieje takie miejsce w kodzie (punkt linearyzacji), w którym wywołanie metody będzie miało efekt. Punkt linearyzacji nie musi być taki sam dla różnych wywołań metod.

Metoda `add` będzie miała efekt w momencie, w którym element znajdzie się w zbiorze -- będzie osiągalny z węzła `head` listy. W przypadku wywołania `add` zakończonego sukcesem, punktem linearyzacji może być moment zajęcia zamka z większym elementem od wstawianego (dwa możliwe miejsca w kodzie). W przypadku wywołania `add` zakończonego porażką punktem linearyzacji może być zajęcie zamka z dodawaną wartością (mamy na to dwa możliwe miejsca w kodzie).

Metoda `remove` będzie miała efekt w momencie, w którym element zostanie usunięty ze zbioru lub stwierdzimy, że takiego nie ma. W przypadku wywołania `remove` zakończonego sukcesem, punktem linearyzacji może być moment zajęcia zamka z elementem usuwanym (dwa możliwe miejsca w kodzie). W przypadku wywołania `remove` zakończonego porażką punktem linearyzacji może być zajęcie zamka z wartością większą niż usuwany (mamy na to dwa możliwe miejsca w kodzie).

## Zadanie 5
:::success
Autor: Andrzej Morawski
:::

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

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

Iterując się po liście po kolei blokujemy kolejne pary węzłów, zatem mamy pewność, że żaden wątek nie wstawi nam pomiędzy nowego węzła. Dodatkowo dzięki niezmiennikom listy mamy pewność, że nie będzie dwóch takich elementów i wszystkie elementy są ułożone w kolejności ściśle rosnącej. Zatem jeżeli znajdziemy węzeł, który nie spełnia warunku $(curr.key < key)$ mamy pewność, że ten węzeł jest albo naszą szukaną wartością albo tej wartości nie ma na liście.

## Zadanie 6
:::success
Autor: Dominik Olejarz
:::
Optymistyczna implementacja zakłada, że problemy synchronizacji pojawiają się dość rzadko. Z tego powodu wątki chcące wykonać operację na elementach listy nie zakładają zamków podczas przejścia przez listę.Zamki są zakładane dopiero gdy chcemy modyfikowac listę.

Przyklad sytuacji zaglodzenia remove():
-inf -> a -> b -> c -> d -> +inf

chcemy zrobić remove(b)

Zauważmy, że jak znajdziemy miejsce gdzie wartość ta może wystąpić to będziemy

Wtedy prev = a
curr = b

Z drugiej strony wątek B chce dodać a’ (a < a’ < b)

zauważmy, że może on zająć zamek prev + curr przed tym wątkiem

jak wtedy wygląda lista:

-inf -> a -> a’ -> b -> c -> d-> +inf

Teraz wątek A wywołuje validate(pred, curr) == validate(a,b)

widzimy, że teraz warunek pred.next == curr jest nieprawdziwy bo a wskazuje na a’ zamisat na b

Teraz metoda A: remove(b) zaczyna sie jeszcze raz. Znowu dochodzi do tego miejsca co wcześniej więc ma

prev = a’
curr = b

Jednak ponownie zamiast wątek A zajmie zamki to wątek B je zajmie poprzez wywołanie metody remove(a’)

Widzimy, że mu się uda czyli lista będzie wyglądać tak:

-inf -> a -> b -> c -> d-> +inf

Teraz wątek A odpala validate i widzimy, że ponownie dostajemy false ponieważ prev =a’ nie istnieje w liście więc cały while przeleci i zwróci false

Widzimy, że doszliśmy do stanu początkowego więc możemy w nieskończoność powtarzać

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

Będziemy potrzebować globalnego licznika oraz blokady na ten licznik. Na początku pętli ```while(true)``` zapisujemy lokalnie timestamp. W miejscu metody ```validate()```, zajmujemy zamek na liczniku, a następnie sprawdzamy czy licznik jest równy wartości zapisanej lokalnie. Jeśli tak zwiększamy licznik o 1 i wykonujemy orginalne operacje. Jeśli nie przechodzimy do kolejnego obiegu ```while(true)```

public boolean add(T item){
    int key = item.hashCode();
    while(true){
        int localCounter = counter; //<- Zmiana
        Node pred = head;
        Node curr = pred.next;
        while(curr.key <= key){
            pred = curr; curr = curr.next;
        }
        pred.lock(); curr.lock();
        try{
            counterLock.lock();
            try{
                if(localCounter == counter){ // <- Zmiana
                    if(curr.key == key){
                        return false;
                    }
                    else {
                        Node node = new Node(item);
                        node.next = curr;
                        pred.next = node;
                        counter++;    //<- Zmiana
                        return true;
                    }
                }    
            }
            finally{
                counterLock.unlock();
            }
        }
        finally{
            pred.unlock(); curr.unlock();
        }
    }
}

public boolean remove(T item){
    int key = item.hashCode();
    while(true){
        int localCounter = counter; //<- Zmiana
        Node pred = head;
        Node curr = pred.next;
        while(curr.key <= key){
            pred = curr; curr = curr.next;
        }
        pred.lock(); curr.lock();
        try{
            counterLock.lock();
            try{
                if(localCounter == counter){ // <- Zmiana
                    if(curr.key == key){
                        pred.next = curr.next;
                        counter++; // <- Zmiana
                        return true;
                    }
                    else {
                        return false;
                    }
                }    
            }
            finally{
                counterLock.unlock();
            }
        }
        finally{
            pred.unlock(); curr.unlock();
        }
    }
}

## Zadanie 8
:::success
Autor: Marcel Szelwiga
:::
W `LazyList` możemy naznaczać wierzchołki jako przeznaczone do usunięcia. W ten sposób usunięcie elementu będzie składło się z dwóch etapów:

* Naznaczenie elementu jako element do usunięcia.

* Realne przepięcie wskaźników, aby element nie był już dłużej przepiany.

Dzięki temu możemy zaimplementować metodę `contains` bez użycia zamków.

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) {
                        curr.marked = true;
                        pred.next = curr.next;
                        return true;
                    } else {
                        return false;
                    }
                }
            } 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;
	if (curr.key == key && !curr.marked){
		return true;
	} else {
		return false;
	}
	
}
private boolean validate(Node pred, Node curr) {
	if (!pred.marked && !curr.marked && pred.next == curr){
		return true;
	} else {
		return false;
	}
}

Rozważmy teraz blokowanie węzła poprzedniego i usuwanego, ale nie razem:

* Blokujemy węzeł usuwany.

Rozważmy listę $-\infty \rightarrow a \rightarrow b \rightarrow \infty$.
Usuwamy teraz węzły $a$ i $b$. Bo usunięciu $a$ dostaniemy:

$$-\infty \rightarrow b \rightarrow \infty, a \rightarrow b$$

A po usunięci $b$ będziemy mieli:

$$a \rightarrow \infty, -\infty \rightarrow b \rightarrow \infty$$

Przez co element został w liście co prawda naznaczony jednak nie usunięty.
Nie możemy na coś takiego pozwolić, stracimy wtedy na wydajności. Ponadto w naszej implementacji już nigdy nie będziemy mogli już nigdy poprawnie wywołać `add(`$a$`)`, metoda `validate` nie powiedzie się, gdy będziemy trzymać węzły $-\infty$ i $b$. Oczywiście to nie wszystkie problemy, które będzie powodował węzeł $b$.

* Blokujemy węzeł poprzedzający usuwany.

Rozważmy ponownie listę $-\infty \rightarrow a \rightarrow b \rightarrow \infty$.
Będziemy ponownie usuwać $a$ i $b$. Załóżmy, że oba wywołania `remove`, zajeły już zamki na $a$ i $b$, funkcja `validate` dla obu zakończy się sukcesem. Po przepięciu wskaźników w odpowiedniej kolejności dostajemy dokładnie taką samą systuację jak w poprzednim przypadku.

## Zadanie 9
:::success
Autor: Volha Tsekalo
:::
linijki *67, 69, 75 i 78* zostaną usunięte.
1) Funkcja **contains()** zwraca true wtedy, gdy true zwróciła funkcja **validate()**. Oznacza to, że w pewnym momencie ten element znajdował się na liście i był osiągalny z heada. Można wybrać ten moment za punkt linearyzacji metody contains(), zatem otrzymany algorytm jest nadal linearyzowalny.

Usunięte zostanie wyrażenie *!curr.marked*
2) Są dwa rodzaje usunięcia elementu - **usunięcie logiczne** i **usunięcie fizyczne**. Jeśli nie będziemy sprawdzać wartości bitu mark, to może się okazać, że zwrocimy true pomimo, że element został usunięty ze zbioru, co implikuje, że przy takim założeniu nie da się wybrać punktu linearyzacji.