# PW - lista 9
## Zadanie 1
**Zasada lokalności odwołań** - w danym czasie jest bardzo prawdopodobne, że procesor będzie wykonywał wiele dostępów do tej samej komórki pamięci, albo pobliskich komórek. Wykorzystanie tej zasady - wykonując odczyt/zapis do pamięci operacyjnej, ściągamy blok danych do pamięci podręcznej (*cache*). Ze slajdów:
:::info
Dlaczego systemy wieloprocesorowe wymagają zastosowania protokołów spójności pamięci podręcznych?
:::
Mamy wiele procesorów, z których każdy ma swoją własną pamięć podręczną, w których być może są kopie tej samej zmiennej $x$. Jeśli np. jeden procesor zapisuje do $x$ nową wartość, to inne procesory muszą się jakoś o tym dowiedzieć. Ze slajdów:
:::info
Jak działa protokół **MESI**?
:::
Mamy model jak wyżej, tj. wiele procesorów, *cache* dla każdego z nich i wspólną pamięć. Każda linia pamięci podręcznej ma pewien stan:
* **M** (modified) - linia jest obecna tylko w tej pamięci podręcznej i została zmodyfikowana. Musi więc zostać kiedyś zapisana do pamięci głównej.
* **E** (exclusive) - linia jest obecna tylko w tej pamięci podręcznej, ale nie została jeszcze zmodyfikowana.
* **S** (shared) - linia nie została zmodyfikowana (jest zgodna z główną pamięcią), być może mają ją też inne procesory
* **I** (invalid) - linia nie zawiera wiarygodnych informacji - np. inny procesor zmodyfikował pewną zmienną z tej linii.
# Zadanie 2
Wydajność mierzy się poprzez wykonanie krótkiej sekcji krytycznej dla `n` wątków.
Każdy procesor (wątek) ma swoją pamięć cache. Jest ona aktualizowana tylko wtedy, gdy zmienna jest oznaczona jako invalid. TAS oznacza zmienną jako invalid kiedykolwiek jest ona wywoływana, niezważając na to, czy ustawienie wartości było pomyślne (czy wartość się zmieniła). To powoduje duży koszt czasowy.
Przez to wszystkie wątki kontynuują "unieważnianie" pamięci podręcznej cały czas. W TTAS z kolei, unika się wywoływania TAS tak często, przez co "unieważnia" się pamięć podręczną rzadziej(tylko podczas wywołania TAS oraz zwolnieniu blokady).
# Zadanie 3
**Zalety w stosunku do poprzedników** - ideą tego algorytmu jest ustawianie flag invalid do minimum. Aktywne czekanie będzie się wykonywało tylko na lokalnych zmiennych w danych wątkach.
**False sharing** - Oczekiwalibyśmy, że skoro przy unlocku wątek zmienia tylko flagę kolejnego wątku, to tylko kolejny wątek będzie miał tę wartość oznaczoną jako invalid. Okazuje się jednak, że pamięc podzielona jest na ciągle bloki, z tego powodu jak jakiś wątek łąduje swoją flagę do cache'a to może załadować także flagi obok, ponieważ znajdują się w jednym spójnym ciągu pamięci. Przez co przy zmianie swojej flagi, zamiast zrobić invalid na pojedynczej zmiennej zrobi an całym bloku i unieważni, wszystkie pozostałe wątki.
Aby problem false sharingu nie występował, należałoby sprawić, aby każdy wątek zapisywał swoją flagą w oddzielnym bloku pamięci, przez co przy zmianie kolejnej flagi, unieważniał by ją tylko w kolejnym wątku.
# Zadanie 4
W pierwszej implementacji wszystkie wątki współdzielą tą są linię w cachu, która zawiera licznik. Każda inkrementacja tego licznika inwaliduje tą linię w cachu dla wszystkich innych wątków, powodując duży ruch na szynie danych podczas każdej inkrementacji.
W drugiej implementacji, zakładając, że elementy tablicy są przypisane do cachu, linia cachu jest inwalidowana tylko wtedy, gdy wątek `i-1` osiąga barierę, wtedy wątek `i` może zaaktualizować wartość swojej linii w cachu. W takim razie tylko jedna inwalidacja może wystąpić między wątkami, pomijając moment, gdy dojdziemy do ostatniego elementu.
**Pomijamy efekt false sharingu, który w implementacji 2 prawdopodobnie by wystąpił**
Druga implementacja jest bardziej "bus friendly" od pierwszej, ale wymaga więcej miejsca w pamięci i konroli. Dla wysokiego obciążenia druga implementacja powinna działać lepiej, a dla małego ta pierwsza.
# Zadanie 5
```java
public class CLHLock implements Lock {
AtomicReference<QNode> tail;
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());
}
class QNode {
volatile boolean locked = false;
}
}
```
# Zadanie 6
Może wystąpić deadlock.
Dla wątku A:
- A zajmuje zamek:
Tail -> A(locked=true)
- A zwalnia zamek:
Tail -> A(locked=false)
- A ponownie zajmuje zamek:
Tail -> A(locked=true) -> A(locked=true)
To znaczy może dojść do sytuacji, gdzie ten sam node jest jednocześnie poprzednikiem i następnikiem, więc wywołując `lock()` ustawimy go na `true`, i pętla `while (pred.locked) {}` nigdy się nie zakończy.
# Zadanie 7
Chcemy napisać metode tryLock wykorzystując CLH, która będzie próbowąć zdobyć wyłączność na sekcję krytyczną, przez okreslony czas. Jeżeli dany czas minie, tryLock ma zakończyć się z zwróconą wartością false. Jeżeli udało się zdobyć sekcję krytyczną, funkcja ma zwrócić true.
* **predPred == AVAILABLE** to poprzednik zrobił locka i unlocka
* **predPred == null** to poprzednik nie starał się o locka, lub go zwolnił
* **predPred != null i predPred != AVAILABLE** to poprzednik dostał timeout
```java=
public class TOLock implements Lock {
static QNode AVAILABLE = new QNode();
AtomicReference<QNode> tail;
ThreadLocal<QNode> myNode;
public TOLock() {
tail = new AtomicReference<QNode> (null);
myNode = new ThreadLocal<QNode>() {
protected QNode initialValue() {
return new QNode();
}
};
}
public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
long startTime = System.currentTimeMillis();
long patience = TimeUnit.MILLISECONDS.convert(time, unit);
QNode qnode = new QNode();
myNode.set(qnode);
qnode.pred = null;
QNode myPred = tail.getAndSet(qnode);
////!!! jezeli poprzednik nie istnieje, lub zakończyłswoje zadanie
if (myPred == null || myPred.pred == AVAILABLE) {
return true;
}
while (System.currentTimeMillis() - startTime < patience) {
QNode predPred = myPred.pred;
if (predPred == AVAILABLE) {
return true;
} else if (predPred != null) {
// myPred dostał timeout, więc czekamy na jego poprzednika (predPred)
myPred = predPred;
}
}
if (!tail.compareAndSet(qnode, myPred))
qnode.pred = myPred;
return false;
}
public void unlock() {
QNode qnode = myNode.get();
if (!tail.compareAndSet(qnode, null))
qnode.pred = AVAILABLE;
}
static class QNode {
public volatile QNode pred = null;
}
}
```
# Zadanie 8
Architektura NUMA charakteryzuje się tym, że nie ma protokołu synchronizacji pamięci, takiego jak np. MESI.
Dlatego nie możemy odczytać danych które należa do innego wątku. Jedynym sposobem komunikacji jest wysłanie informacji do innego wątku, że nastąpiła jakaś zmiana, wysyłanie informacji jest operacją dosyć kosztowną, dlatego należy ją minimalizować.
```java
public class MCSLock implements Lock {
AtomicReference<QNode> tail;
ThreadLocal<QNode> myNode;
public MCSLock() {
tail = new AtomicReference<QNode>(null);
myNode = new ThreadLocal<QNode>() {
protected QNode initialValue() {
return new QNode();
}
};
}
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 successor fills in its next field
while (qnode.next == null) {}
}
qnode.next.locked = false;
qnode.next = null;
}
class QNode {
volatile boolean locked = false;
volatile QNode next = null;
}
}
```
# Zadanie 9
### TAS
```java=
class TASlock {
AtomicBoolean state = new AtomicBoolean(false);
void lock() {
while (state.getAndSet(true)) {}
}
void unlock() {
state.set(false);
}
public boolean isLocked(){
return state.get();
}
}
```
### CLH
```java
public class CLHLock implements Lock {
AtomicReference<QNode> tail;
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());
}
public boolean isLocked(){
return tail.get().locked; /// kolejka jest pusta
}
class QNode {
volatile boolean locked = false;
}
}
```
### MCS
```java=
public class MCSLock implements Lock {
AtomicReference<QNode> tail;
ThreadLocal<QNode> myNode;
public MCSLock() {
tail = new AtomicReference<QNode>(null);
myNode = new ThreadLocal<QNode>() {
protected QNode initialValue() {
return new QNode();
}
};
}
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 successor fills in its next field
while (qnode.next == null) {}
}
qnode.next.locked = false;
qnode.next = null;
}
public boolean isLocked(){
QNode pred = tail.get();
return pred != null; /// kolejka jest pusta
}
class QNode {
volatile boolean locked = false;
volatile QNode next = null;
}
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
