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

The principle of locality of references refers to the tendency of a program to access a small, localized portion of its address space for a certain period of time. There are two main types of locality:
1. Temporal locality: if a particular memory location is accessed, it is likely to be accessed again in the near future.
2. Spatial Locality: if a particular memory location is accessed, nearby locations are also likely to be accessed.
Caches use the principle of locality to improve performance. They store the data that is frequently accessed or recently used. When the CPU requests data, the cache is checked first, and if it found there the process will be much faster than having to get the data from main memory.
When multiple processors share access to a common memory, there has to be cache coherence. If not there would be inconsistencies when multiple caches have copies of the same data. Without coherence changes made by one processor could not be immediately visible to others.
MESI stands for:
Modified: the cache line is present in the cache in a modified state, meaning that it has been altered compared to the main memory, so the changes have to be written back.
Exclusive: the cache line is present in the cache in an unmodified state, and no other caches have copy of it.
Shared: The cache line is unmodified and is shared wit other caches.
Invalid: The cache line is invalid or not present in the cache.
So for example, if a cache wants to write to a memory location, it must first ensure that no other caches have a copy in the Modified or Exclusive state. If they do the data is invalidated or updated to maintain consistency.

## Zadanie 2
:::success
Autor: Marcin Majchrzyk
:::

W jaki sposób mierzy się wydajność implementacji zamków?
- Tworzy się program z krótką sekcją krytyczną (licznikiem), mierzy się czas wykonania zadania i porównuje w zależności od liczby wątków.

class TASlock {
    AtomicBoolean state = new AtomicBoolean(false);
    void lock() {
        while (state.getAndSet(true)) {}
    }
    
    void unlock() {
        state.set(false);
    }
}

class TTASlock {
    AtomicBoolean state = new AtomicBoolean(false);
    void lock() {
        while (true) {
            while (state.get()) {}
            
            if (!state.getAndSet(true))
                return;
        }
    } 
}

Wyjaśnij, skąd bierze się różnica w wydajności zamka TAS vs. TTAS odwołując się do modelu komunikacji w systemach wieloprocesorowych ze spójnymi pamięciami podręcznymi i wspólną szyną danych.
- Zamek TAS przez próbę zapisu za każdym razem unieważnia pamięć podręczną we wszystkich procesach, przez co musi być aktualizowana z pamięci współdzielonej.
- Zamek TTAS tylko odczytuje stan, przez co wszystkie pamięci nie są unieważniane gdy nie ma możliwości zablokowania zamka, tylko wtedy gdy się to udaje.

## Zadanie 3
:::success
Autor: Mikołaj Balwicki
:::
Idea:
Korzystamy z tablicy wartości boolowskiej opisującej stan pracy kolejnych wątków. Każdy wątek korzysta tylko z dwóch komórek pamięci, tej opisującej stan swojego poprzednika i tej opisującej jego stan. Wątek wiruje na komórce poprzednika tak długo jak nie zwolni on swojego zamka. Gdy wątek skończy swoją sekcję krytyczną, zwalnia on zamek w przypisanej do niego komórce.

Kod:

public class ALock implements Lock {
	ThreadLocal<Integer> mySlotIndex = new ThreadLocal<Integer> (){
		protected Integer initialValue() {
			return 0;
		}
	};
	AtomicInteger tail;
	boolean[] flag;
	int size;
	public ALock(int capacity) {
		size = capacity;
		tail = new AtomicInteger(0);
		flag = new boolean[capacity];
		flag[0] = true;
	}
	public void lock() {
		int slot = tail.getAndIncrement() % size;
		mySlotIndex.set(slot);
		while (! flag[slot]) {};
	}
	public void unlock() {
		int slot = mySlotIndex.get();
		flag[slot] = false;
		flag[(slot + 1) % size] = true;
	}
}

## Zadanie 4
:::success
Autor: Jakub Krzyżowski
:::

W pierwszej implementacji wszystkie wątki czekają aż licznik zabezpieczony TTASLock'iem osiągnie n. Wszystkie te wątki współdzielą ten jeden licznik, a zatem za każdym razem jak jakiś wątek zmieni jego wartość nastąpi inwalidacja linii w cache pozostałych wątków. Oznacza to, że szyna danych będzie otrzymywać bardzo dużo żądań.

W drugiej implementacji mamy tablicę wartości boolowskich, gdzie każdy wątek i najpierw czeka aż komórka `b[i-1] == true` i ustawia `b[i] = true`, a następnie czeka aż `b[n-1] == true`. Tutaj występuje problem fałszywego współdzielenia, któremu można zaradzić paddingiem. Jeśli nie wykorzystamy paddingu otrzymamy niewielkie przyspieszenie względem pierwszego protokołu, bo inwalidacji nie będą zachodzić linie wszystkich wątków na raz, a jedynie paru. Jeśli natomiast zastosujemy padding to kosztem większego zużycia pamięci nie będziemy tracić czasu na dodatkowe operacje na szynie danych, a więc uzyskamy większe przyspieszenie.

## Zadanie 5
:::success
Autor: Konrad Kowalczyk
:::


Zasada działania zamka CLH jest podobna do zasady działania zamka kolejkowego Andersona, z tym że do kolejkowania zamiast jawnej tablicy komórek używa się wirtualnej listy wiązanej.

public class CLHLock implements Lock {
	AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode());
	ThreadLocal<QNode> myPred;
	ThreadLocal<QNode> myNode;
	public CLHLock() {
		tail = new AtomicReference<QNode>(new QNode());
		myNode = new ThreadLocal<QNode>() {
			protected QNode initialValue() {
				return new QNode();
			}
		};
		myPred = new ThreadLocal<QNode>() {
			protected QNode initialValue() {
				return null;
			}
		};
	}
	public void lock() {
		QNode qnode = myNode.get();
		qnode.locked = true;
		QNode pred = tail.getAndSet(qnode);
		myPred.set(pred);
		while (pred.locked) {}
	}
	public void unlock() {
		QNode qnode = myNode.get();
		qnode.locked = false;
		myNode.set(myPred.get());
	}
}

Zmienna `tail` w tej implementacji jest referencją do komórki pamięci utworzonej przez ostatni zakolejkowany procesor. Kiedy nowy procesor chce otrzymać zamek, tworzy referencję do nowej komórki `myNode` i ustawia wartość tej komórki na `true`. Następnie przypisuje obecną wartość `tail` do dodatkowej zmiennej `pred` oraz ustawia `tail` na swoją stworzoną komórkę.
Aby wejść do sekcji krytycznej, procesor czeka, aż `pred` (czyli komórka stworzona przez ostatni procesor przed nim) zostanie zmieniona na `false`. Kiedy sam wyjdzie z sekcji krytycznej, to ustawi swoją komórkę na `false`, a zatem wątek po nim będzie mógł wejść.
W ten sposób tworzy się wirtualna lista wiązana, ponieważ każdy procesor trzyma referencję do komórki utworzonej przez poprzedni procesor (`pred`) oraz referencję do komórki utworzonej przez siebie (`myNode`).


Aby ograniczyć liczbę alokacji węzłów listy, można zamiast tworzyć nową referencję `myNode` do komórki w każdej iteracji, to wykorzystać komórkę używaną wcześniej przez poprzedni procesor (`pred`). W momencie zwalniania zamka procesor ustawia sobie `myNode = pred` (który nie jest już używany), dzięki czemu w następnej iteracji może z niej korzystać tak, jakby tworzył nową.

## Zadanie 6
:::success
Autor: Jan Marek
:::


Prześledźmy następujący scenariusz, w którym działa tylko wątek (A):

- A.lock()
po wykonaniu locka otrzymamy, że:
`tail == myNode.get()` oraz `myNode.get().locked == true`

- A.unlock()
po wykonaniu unlocka:
`tail == myNode.get()` oraz `myNode.get().locked == false`

- A.lock()
`qnode.locked = true`, to ponownie
`tail == myNode.get()` oraz nadal `myNode.get().locked == false`
Po wykonaniu `Qnode pred = tail.getAndSet(qnode)` mamy:
`pred == myNode.get()` i `myNode.get().locked == true`
Następnie A wchodzi do while'a i się zapętla, bo `pred.locked == true`.

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


This lock has the method tryLock() that allows the caller to specify a timeout as a limit for the time this caller is willing to wait to acquire the lock. If this time passes before acquiring the lock the attempt is abandoned. A boolean return value will indicate if the lock succeeded or not. It requires a constant number of steps, so it is considered wait-free.
It behaves similarly to the CHL lock, where each thread spins on its predecessor’s node waiting for the lock to be released. If a thread leaves the queue node, it will mark it as abandoned, so if there is a preceding thread it notices it and can take over it.
At first, pred field is set to null it means the associated thread has not acquired the lock or has released it. If it contains “AVAILABLE”, it means the associated thread has released the lock. If the field refers to other QNode it means the associated node has been abandoned so the current thread has to wait for the abandoned node’s predecessor.

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


### Różnica w działaniu zamka MCS i CLH w architekturze NUMA.
W architekturze NUMA często spotykanym zjawiskiem jest brak pamięci podręcznej.
### CLH
W przypadku takiego właśnie braku pamięci podręcznej koszt wirowania na węźle innego wątku staje się bardzo czasochłonny.
### MCS
Tutaj nie wirujemy na węźle innego wątku tylko na własnej komórce, co jest istotnie szybsze.

### Numa architecture example

## Zadanie 9
:::success
Autor: Konrad Kowalczyk
:::


<b>TAS</b>:

public class TASLock implements Lock {
	AtomicBoolean state = new AtomicBoolean(false);
	public void lock() {
		while (state.getAndSet(true)) {}
	}
	public void unlock() {
		state.set(false);
	}
}

`isLocked()` dla <b>TAS</b>:

boolean isLocked() {
	return state.get();
}

<b>CLH</b>:

public class CLHLock implements Lock {
	AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode());
	ThreadLocal<QNode> myPred;
	ThreadLocal<QNode> myNode;
	public CLHLock() {
		tail = new AtomicReference<QNode>(new QNode());
		myNode = new ThreadLocal<QNode>() {
			protected QNode initialValue() {
				return new QNode();
			}
		};
		myPred = new ThreadLocal<QNode>() {
			protected QNode initialValue() {
				return null;
			}
		};
	}
	public void lock() {
		QNode qnode = myNode.get();
		qnode.locked = true;
		QNode pred = tail.getAndSet(qnode);
		myPred.set(pred);
		while (pred.locked) {}
	}
	public void unlock() {
		QNode qnode = myNode.get();
		qnode.locked = false;
		myNode.set(myPred.get());
	}
}

`isLocked()` dla <b>CLH</b>:

boolean isLocked() {
	return tail.get().locked;
}

<b>MCS</b>:

public class MCSLock implements Lock {
	AtomicReference<QNode> tail;
	ThreadLocal<QNode> myNode;
	public MCSLock() {
		queue = new AtomicReference<QNode>(null);
		myNode = new ThreadLocal<QNode>() {
			protected QNode initialValue() {
				return new QNode();
			}
		};
	}
	class QNode {
		boolean locked = false;
		QNode next = null;
	}
	public void lock() {
		QNode qnode = myNode.get();
		QNode pred = tail.getAndSet(qnode);
		if (pred != null) {
			qnode.locked = true;
			pred.next = qnode;
			// wait until predecessor gives up the lock
			while (qnode.locked) {}
		}
	}
	public void unlock() {
		QNode qnode = myNode.get();
		if (qnode.next == null) {
			if (tail.compareAndSet(qnode, null))
				return;
			// wait until predecessor fills in its next field
			while (qnode.next == null) {}
		}
		qnode.next.locked = false;
		qnode.next = null;
	}
}

`isLocked()` dla <b>MCS</b>:

boolean isLocked() {
	return tail.get() != null;
}