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

#### Zdefiniuj zasadę lokalności odwołań

1. Lokalność czasowa - komórki pamięci, który były niedawno używane zostaną z dużym ppb. ponownie użyte w niedalekiej przyszłości.
2. Lokalność miejscowa - komórki pamięci położone blisko siebie są często używane w krótkich odstępach czasu

#### W jaki sposób tę zasadę wykorzystują pamięci podręczne?

Ładując komórkę do pamięci podręcznej, przenosi się tam wiersz bliskich sobie komórek.

#### Dlaczego systemy wieloprocesorowe wymagają zastosowania protokołów spójności pamięci podręcznych?

Żeby uniknąć sytuacji korzystania z nieaktualnych danych (tzn. proces A czyta stare dane, które zsotały chwile temu zmienione przez proces B)

#### Jak działa protokół MESI?

https://pl.wikipedia.org/wiki/MESI

Każda linia pamięci podręcznej ma przydzielony jeden z czterech stanów:

1. **M**odified - procesor zmodyfikował komórkę pamięci podręcznej i musi zapisać ją do pamięci głównej
2. **E**xclusive - tylko 1 pamięć podręczna ma dostęp do danych oraz pamieć główna
3. **S**hared - pamięć dostępna dla kilku pamięci podręcznych i w pamięci głównej
4. **I**nvalid - pamięć już nieaktualna i może zostać zmieniona

## Zadanie 2
:::success
Autor: Dominik Olejarz
:::





1.W jaki sposób mierzy się wydajność implementacji zamków?
Wydajność mierzy się poprzez wykonanie krótkiej sekcji krytycznej (np increment)dla n wątków
2.
Każdy wątek ma swoją pamięć cache. Jest ona aktualizowana tylko wtedy, gdy zmienna jest oznaczona jako invalid. W TAS problemem jest ciągłe użycie getandset(),bo oznacza zmienną jako invalid niezależnie czy ustawienie wartości było pomyślne (czy wartość się zmieniła).
To powoduje duży koszt czasowy bo zmienna musi byc na nowo aktualizowana we wszystkich watkach co jest wolne.

W TTAS unika się wywoływania getandset() tak często, przez co “unieważnia” się pamięć podręczną rzadziej. Tylko podczas wywołania getandset() oraz zwolnieniu blokady.

## Zadanie 3
:::success
Autor: Paweł Borek
:::
Wątki rezerwują kolejne sloty w tablicy. Gdy jeden wątek kończy pracę to zwalnia następny w tablicy.

Zalety:
* first-come-first-served fairness
* brak głodzenia

Problem fałszywego współdzielenia:

## Zadanie 4
:::success
Autor: Adam Korta
:::

**Podpunkt 1**
W pierwszej implementacji dokonujemy modyfikację i odczyt wartości jednej komórki (zmienna licznika). Zauważmy że takie podejście będzie powodowało że pamięc podręczna dla poszczególnych watkow bardzo często będzie wchodziła w stan Invalid. Kazde zwiększenie licznika będzie powodowało tłok na szynie danych co spowoduje spowolnienie programu.
**Podpunkt 2**
To rozwiązanie jest podobne do zamka kolejkowego Andersona a zatem przejścia w stan Invalid będą występowały znacznie rzadziej. Każdy wątek, poza n-tym, będzie odpowiedzialny za jedno przejście do stanu ‘Invalid’ cache’a pojedynczego wątku.

## Zadanie 5
:::success
Autor: Martyna Wybraniec
:::

Zamek CLH działa podobnie do zamka Andersona, ale zamiast tablicy komórek mamy niejawną listę wiązaną. W momencie, kiedy wątek chce przejść do sekcji krytycznej, alokuje nowy węzeł z domyślną wartością `true` oraz zamienia się wskaźnikami z ogonem (ogon wskazuje na nowy węzeł, a wątek na stary ogon). Dopóki `pred` nie zmieni swojej wartości na false, wątek wiruje w pętli. Kiedy sekcja krytyczna zostaje zwolniona, węzeł wskazywany przez `pred` zmienia swoją wartość na `false` i czekający wątek może wejść do sekcji krytycznej.

Aby ograniczyć liczbę alokacji węzłów listy po zwolnieniu locka przez wątek A może on użyć węzła `pred` do kolejnej próby wejścia do sekcji krytycznej.

## Zadanie 6
:::success
Autor: Andrzej Morawski
:::

public class BadCLHLock implements Lock {
    AtomicReference<Qnode> tail = new AtomicReference<QNode>(new QNode());
    ThreadLocal<Qnode> myNode = new ThreadLocal<QNode> {
    	protected QNode initialValue() {
    	    return new QNode();
    	}
    };
    public void lock() {
    	Qnode qnode = myNode.get();
    	qnode.locked = true; // I’m not done
    // Make me the new tail, and find my predecessor
    	Qnode pred = tail.getAndSet(qnode);
    	while (pred.locked) {}
    }
    public void unlock() {
    	// reuse my node next time
    	myNode.get().locked = false;
    }
    static class Qnode { // Queue node inner class
        volatile boolean locked = false;
    }
}

Rozpatrzmy następujące wykonanie programu:

1. Wątek A wykonuje metodę $lock()$
2. Wątek A wykonuje metodę $unlock()$
3. Wątek A ponownie wykonuje metodę $lock()$

Implementacja jest błędna, ponieważ dochodzi do zapętlenia się pojedynczego wątku w metodzie $lock()$

## Zadanie 7
:::success
Autor: Andrzej Morawski
:::

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();
                }
            };
    }
    static class QNode {
        public volatile QNode pred = null;
    }
    
    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);
    	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 = 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;
    }
}

Zamek CLH z czasem ważności posiada metodę $tryLock$, dzięki której wątek moze określić ile czasu jest w stanie poświęcić na zajmowanie zamka. Jeżeli wątek nie zajmie zamka w określonym czasie porzuca tę próbę.
Próba zajęcia zamka kończy się zwróceniem zmiennej boolowskiej.
W klasycznym zaku CLH przerwanie wykonywania metody $lock$ przez wątek skutkowałoby zagłodzeniem wątków czekających za nim w kolejce. Metoda $tryLock$ rozwiązuje ten problem przez oznaczenie wątku, który porzucił wykonywanie metody. Dzięki temu pozostałe wątki czekające w kolejce mogą wejść do sekcji krytycznej.

## Zadanie 8
:::success
Autor: Volha Tsekalo
:::

**MCS działa w następujący sposób**

*Funkcja lock*: zamek ustawia się na końcu kolejki. jeśli kolejka nie była pusta, to wskaźnik next ustawia na siebie i czeka aż będzie ona miała wartość false.

*Funkcja unlock*:
Sprawdzamy, czy next jest nullem i jeśli tak, to próbujemy ustawić tail na null. Jeśli nam się to udaje, to znaczy, że żaden wątek nie chce w tym momencie zająć locka i na tym kończymy.
wpp wiemy, że CAS zwrócił fałsz to znaczy że jakiś wątek chce wejść do sekcji krytycnzej i po to jest pętla while, w której czekamy aż ten wątek dołączy do kolejki.
Następnie ustawiamy wartość węzła na fałsz.

**Dlaczego w systemie NUMA jego wydajność może być lepsza niż zamka CLH?**

Często spotykane zjawisko w systemie NUMA to brak pamięci podręcznej. W przypadku CLH wątki wirowały na kopii lokalnej węzła innego wątku. W przypadku, gdy pamięci podręcznej nie ma, wirowanie na węźle innego wątku zrobi się bardzo czasochłonne. Co do MCS, to wątki wirują na własnej komórce - jest to o wiele szybsze.

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


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



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



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