# Ćwiczenia 10, grupa śr. 10-12, 3 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 | 7 | 8 | 9 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | | |
Konrad Kowalczyk | X | X | | X | X | | | | |
Jakub Krzyżowski | X | X | X | X | X | X | | | |
Łukasz Magnuszewski | | | | | | | | | |
Marcin Majchrzyk | X | X | X | X | X | X | X | | |
Jan Marek | X | | X | X | X | | | | |
Marcin Mierzejewski | | | | | | | | | |
Juan Jose Nieto Ruiz | | | | | | | | | |
Konrad Oleksy | | | | | | | | | |
Javier Rábago Montero | X | X | X | X | X | X | | X | X |
Michał Mękarski | X | X | X | X | X | X | X | | X |
:::

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

## Zadanie 1
:::success
Autor: Jan Marek
:::

Zamki hierarchiczne znajdują zastosowanie w przypadku architektur NUMA, kiedy procesory pogrupowane są w "klastry". Procesory znajdujące się w tym samym klastrze komunikują się wydajnie przez współdzieloną pamięć podręczną. Komunikacja pomiędzy klastrami jest znacznie kosztowniejsza niż w obrębie klastra.

Dla architektur NUMA, `Back-off Lock` nie jest zbyt dobrym pomysłem, ponieważ wydajność takiego zamka znacząco spadnie, kiedy będzie on przechodził pomiędzy klastrami.
HBOLock zmniejsza (średnio) częstotliwość przechodzenia zamka pomiędzy klastrami - a tego chcielibyśmy właśnie uniknąć. Ustalamy różne czasy `back-off'a` dla wątków z tego samego klastra, co aktualnie posiadający zamek wątek (przeciętny czas backoff dla wątków z tego samego klastra i tego, który zajął zamek jest średnio znacznie mniejszy, niż dla pozostałych wątków).
Wartości `delay`, podobnie jak dla zamka `Backoff` muszą zostać starannie dobrane dla danego systemu.

Jedną z wad `HBOLock` jest to, że lokalność może być wykorzystywana ze zbyt dużym powodzeniem. Istnieje niebezpieczeństwo, że wątki z tego samego klastra będą wielokrotnie przekazywały zamek między sobą, natomiast wątki z innych klastrów będą głodzone. Poza tym zajmowanie i zwalnianie zamka powoduje invalidację kopii
pola blokady, co moze być kosztowne w arch. NUMA ze spójną pamięcia podręczną.


Każdy klaster ma niepowtarzalny identyfikator, znany każdemu wątkowi w klastrze i dostępny za pomocą metody `ThreadID.getCluster()`. Zakładamy, że wątki nie przemieszczają się pomiędzy klastrami.

## Zadanie 2
:::success
Autor: Javier Rábago Montero
:::

Cohorts are the set of threads from a cluster waiting to acquire a lock. The idea of lock cohorting is to use multiple locks to provide exclusion at different levels of the memory hierarchy. This means that each cluster has its own lock, and the clusters share a global lock, so when a thread in a cluster acquires the global lock, it will be held until all threads that were waiting for the lock in that cohort have run CS.


To prevent a cohort to keep the lock forever and prevent starvation for threads in other cohorts, TurnArbiter sets a limit to how many times threads from the same cohort can take the lock in a row.
After a thread has finished running CS and wants to free the lock, first it will check if there are any other threads from their cohort (cl.alone() returns false), if so, the cohort will keep the global lock.

## Zadanie 3
:::success
Autor: Jakub Krzyżowski
:::
1.
Niezmiennik reprezentacji to kontrakt pomiędzy metodami klasy, dzięki któremu wiadomo, że nasza lista zachowa pewną oczekiwaną strukturę. W przypadku naszego zbioru reprezentowanego przez listę niezmiennikami reprezentacji bedą:
Posortowanie, brak duplikatów, komórki graniczne - head i tail są komórkami, które w liście zawsze występują i head jest zawsze na początku, a tail na końcu.
Mapa abstrakcji mówi nam jakie elementy znajdują się w zbiorze reprezentowanym przez naszą listę. Tutaj mapa abstrakcji jest następująca: Element jest w zbiorze jeśli jest osiągalny z head.
2.
Punktem linearyzacji dla udanego `add`, czyli takiego, gdzie rzeczywiście coś dodajemy jest przepięcie wskaźnika poprzednika na nową komórkę. Dla nieudanego `add` takim punktem może być dowolny moment kiedy dany wątek trzyma zamek.
Dla udanego `remove` punktem linearyzacji również będzie przepięcie wskaźnika poprzednika usuwanej komórki, a nieudanego również dowolny, kiedy trzyma zamek.
Ponieważ `contains` w żaden sposób nie modyfikuje naszej listy to jego punkt linearyzacji również jest dowolny przy trzymaniu zamka.
3.
Niech udane wywołania metod `add` i `remove` będą linearyzowalne w momencie zajęcia zamka. W takim razie zbiór który jest reprezentowany przez listę musi ulec zmianie wraz z zajęciem zamka przez te metody. W takim razie jeśli wywołamy `add(a)` na pustej liście, to obecna mapa abstrakcji w tym momencie nie da nam zbioru $\{a\}$, zatem taka mapa abstrakcji jest błędna jeśli w ten sposób linearyzujemy metody.
4.
element x należy do zbioru $\leftrightarrow$ (1) węzeł w którym znajduje się x jest osiągalny z head, lub zamek jest zajęty przez `add(x)` i (2) jeśli węzeł jest osiągalny z head, to zamek nie jest zajęty przez `remove(x)`.

## Zadanie 4
:::success
Autor: Konrad Kowalczyk
:::


Klasa `FineList` działa na zasadzie zamków przypisanych do każdego węzła, zamiast jednego zamka dla całej listy. Wątki przechodzące po liście zajmują zamki dla dwóch węzłów naraz i poruszają się poprzez odblokowanie zamka poprzednika obecnego węzła i zajęcie zamka następnika obecnego węzła. Dzięki temu kilka wątków może działać na liście jednocześnie (jeżeli znajdują się w innych miejscach listy), co poprawia efektywność.

Metody `add()` i `remove()` są linearyzowalne, ponieważ dla ich wywołań można wyznaczyć punkt, w którym metody te dadzą oczekiwany efekt. W przypadku `FineList` interpretujemy, że wartość znajduje się w zbiorze wtedy i tylko wtedy, gdy węzeł z tą wartością jest osiągalny z początku listy, zatem chcemy, aby metoda `add()` sprawiła, że nowo dodany element jest osiągalny, a metoda `remove()`, żeby usunięty element nie był już dłużej osiągalny.

Metoda `add()`:

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

W zależności od sukcesu lub porażki metody `add()` punkty linearyzacji będą różne.
- dla sukcesu: gdy pole `next` poprzednika dodawanej wartości wskazuje na nowo dodaną wartość (`pred.next = node`).
- dla porażki: zajęcia zamka węzła, który zawiera wartość dodawaną (`curr.lock()` gdzie `curr` jest elementem na liście równym dodawanej wartości).

Metoda `remove()`:

public boolean remove(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) {
				pred.next = curr.next;
				return true;
			}
			return false;
		}
		finally {
			curr.unlock();
		}
	}
	finally {
		pred.unlock();
	}
}

Ponownie, w zależności od sukcesu lub porażki metody `remove()` punkty linearyzacji będą różne.
- dla sukcesu: gdy pole `next` poprzednika usuwanej wartości wskazuje na następnika usuwanej wartości (`pred.next = curr.next`).
- dla porażki: zajęcia zamka pierwszego węzła, który zawiera wartość większą od usuwanej (`curr.lock()` gdzie `curr` jest pierwszym elementem na liście większym od usuwanej wartości).

## Zadanie 5
:::success
Autor: Javier Rábago Montero
:::

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);
		} finally {
			curr.unlock ();
		}
	} finally { 
		pred.unlock();
	}
}

The contains() method traverses the list the same way add or remove. When it finds the argument in the list it returns it.

## Zadanie 6
:::success
Autor: Marcin Majchrzyk
:::

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

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

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

private boolean validate(Node pred, Node curr) {
    Node node = head;
    while (node.key <= pred.key) {
        if (node == pred)
            return pred.next == curr;
        
        node = node.next;
    }
    
    return false;
}

- wątek A zatrzymuje się przed zajęciem zamków na $pred_A$ i $curr_A$
- wątek B dodaje węzeł ```w``` pomiędzy $pred_A$ i $curr_A$
- wątek A kontynuuje i metoda ```validate``` zwraca fałsz
- dowolny inny wątek usuwa węzeł ```w```

## Zadanie 7
:::success
Autor: Michał Mękarski
:::



public boolean add(T item){
    int key = item.hashCode();
    while(true){
        int localCounter = counter; 
        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){ 
                    if(curr.key == key){
                        return false;
                    }
                    else {
                        Node node = new Node(item);
                        node.next = curr;
                        pred.next = node;
                        counter++;    
                        return true;
                    }
                }    
            }
            finally{
                counterLock.unlock();
            }
        }
        finally{
            pred.unlock(); curr.unlock();
        }
    }
}


public boolean remove(T item){
    int key = item.hashCode();
    while(true){
        int localCounter = counter;
        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){
                    if(curr.key == key){
                        pred.next = curr.next;
                        counter++; 
                        return true;
                    }
                    else {
                        return false;
                    }
                }    
            }
            finally{
                counterLock.unlock();
            }
        }
        finally{
            pred.unlock(); curr.unlock();
        }
    }
}

## Zadanie 8
:::success
Autor: Javier Rábago Montero
:::



The point of the LazyList class is to not have contains() occupying the lock, as it is a frequently called operation and doesn’t write anything.
This implementation adds a boolean to each node to indicate if it is reachable or not. During a traversal, if a node it’s not found, it is not in the set or it is marked as not reachable. In this case the invariant is that only unmarked nodes are reachable, with a very similar abstraction map. The validation won’t have to traverse the list from the beginning and it won’t have to lock each node while doing it.
It is not possible to modify the remove() method to only take one lock.
List example: a - > b -> c -> d
- No pred lock:
As the list is linked, if thread 1 tries to delete c for example but b is not locked, thread 2 can delete b before 1 has rewritten the pointers but is already marked. Then a would point to c, which is marked and d would be unreachable.
- No curr lock:
Thread 1 is deleting b, and 2 is deleting c at the same time. While b is marked, c is marked too, and 2 will make b point to d although it is marked already. Then 1 will make a point to d. The method will return apparently correct, but when add is called later for b, it will make an infinite loop, so the implementation would be incorrect.

## Zadanie 9
:::success
Autor: Michał Mękarski
:::


--------------------

### 9.1


--------------------

### 9.2