# Ćwiczenia 9, grupa śr. 12-14, 21 grudnia 2022

###### tags: `PRW22` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Michał Bronowicki | | | | | | | | | |
Wiktor Bukowski | X | X | X | X | X | X | X |==X==| X |
Jan Dalecki | X | X | X | X | | X | ==X== | | |
Mikołaj Depta | X | X | X |==X==| X | X | X | X | |
Kamil Galik | | | | | | | | | |
Bartosz Głowacki | | | | | | | | | |
Michał Hetnar | x | | | | | | | | |
Adam Jarząbek | | | | | | | | | |
Michał Kierul | | | | | | | | | |
Mateusz Kisiel | X | X | X | X | | X | X | X | X |
Maksymilian Komarnicki | X | X | X | X | | X | X | X | |
Julia Matuszewska | X | X | | X | | X | | | X |
Andrzej Morawski | | | | | | | | | |
Wojciech Pokój | X | X | | X | | X | X | X | X |
Marcin Sarnecki | X | X |==X==| X | | X | | |X |
Bartosz Szczeciński | X | X | X | X | | X | X | X | X |
Tomasz Wołczański | X | X | X | X | X | X | | X | |
Marcin Wróbel | X | X | X | X | X |==X==| | X | X |
:::

**Tutaj** można zadeklarować zad. 4 z listy 8.:

-
-
-

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

## Zadanie 1
:::success
Autor: Maksymilian Komarnicki
:::

_Lokalność czasowa_
Komórki pamięci, które były ostatnio używane będą z wysokim prawdopodobieństwem używane ponownie w niedalekiej przyszłości.

_Lokalność przestrzenna_
Komórki pamięci o pobliskich adresach mają tendencje do bycia używanymi w krótkich odstępach czasu.

(Lokalność czasowa) Pamięci podręczne wykorzystują lokalność odwołań poprzez pamiętanie w liniach komórek pamięci, które były ostatnio używane. Dzięki temu ponowny dostęp do tych samych danych jest bardzo szybki, o ile dane nie zostały usunięte z pamięci.
(Lokalność przestrzenna) Pamięci podręczne wykorzystują także lokalność poprzez umieszczanie linii o pobliskich adresach w różnych zbiorach pamięci podręcznej, co umożliwia trzymanie w niej większego kawałka spójnej pamięci.

Procesor A i B posiadają swoje pamięci podręczne. Przypuśćmy, że oba wczytały dane pod adresem X do swoich pamięci podręcznych. Jeśli jeden z procesorów dokona modyfikacji tej danej, to pamięci podręczne procesorów A i B przestaną być spójne. Z tego względu potrzebne są protokoły spójności pamięci podręcznej.

_MESI_, czyli każda z linii pamięci podręcznej może byc oznaczona jako
- Modified - dane pamięci podręcznej zostały zmienione, muszą zostać zapisane do pamięci operacyjnej,
- Exclusive - dane niemodyfikowane, jedyna kopia w jakiejkolwiek pamięci podręcznej,
- Shared - dane niemodyfikowane, mogą być też w innej pamięci podręcznej,
- Invalid - zawartość pamięci podręcznej nie jest spójna/zgodna.

## Zadanie 2
:::success
Autor: Wojciech Pokój
:::

:::info
W jaki sposób mierzy się wydajność implementacji zamków?
:::

Układa się prosty program z krótką sekcją krytyczną (na przykład licznik) i mierzy się czas wykonania programu i średni czas potrzeby na zajęcie zamka

:::info
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.
:::

Różnica wynika z konstrukcji pętli czekającej. TAS aktywnie zagląda do pamięci współdzielonej, przez co szyna komunikacyjna staje się obciążona. TTAS wykorzystuje fakt że pamięć znajduje się w cachu i dopuki nie zmieni stanu nie trzeba sięgać do pamięci współdzielonej

## Zadanie 3
:::success
Autor: Marcin Sarnecki
:::
* Przypomnij zasadę działania i podaj implementację zamka kolejkowego Andersona

Mamy współdzieloną tablicę zmiennych boolowskich (flag), na poczatku wszedzie są wartości `false` z wyjatkiem poczatku, mamy współdzieloną zmienną `next`. Aby wziąć zamek, wątek atomowo wykonuje `getAnIncrement()` na zmiennej `next`, nastepnie czeka, aż nie pojawi sie tam wartosc `true`, stanie się to gdy poprzedni wątek wykona `unlock()`


* Jakie zalety ma ten zamek w stosunku do zamków TAS/TTAS/Backoff?


* Czego dotyczy problem fałszywego współdzielenia wierszy pamięci podręcznej (ang. false sharing) w tym algorytmie i jak go rozwiązać?

Kolejne komórki z tablicy `flags` będą znajdowały się w tych samych wierszach pamięci, każda zmiana pojedynczej flagi spowoduje zmianę stanu całego wiersza, zatem będzie więcej niepotrzebnego współdzielenia.
Rozwiązaniem jest takie rozmieszczenie flag w tablicy, aby na jedną flagę przypadał jeden wiersz pamięci.

## Zadanie 4
:::success
Autor: Mikołaj Depta
:::


W pierszym podejściu wiele wątków aktywnie modyfikuje i odczytuje wartość jedenj, komórki. Będzie to przyczyną ciągłych inwalidacji pamięci cache i wymuszenie odczytu z pamieci głównej, co jest bardzo kosztowne.

W drugim przypadku mamy podejście podobne do algorytmu Anderson'a, gdzie każdy wątek aktywnie czeka i pisze tylko do jendej komórki, poza ostatnią. Pomijając aspekt kolizji linii cache'u, który można objeść, inwalidajce pamięci podręcznej wystąpią nie więcej niż dwa razy dla każdego wątku. Raz gdy wątek `i - 1` naszpie do swojej komóki i ewentuanie gdy `n`'ty wątek napisze do swojej.

Druga implementacja powinna być dużo szybsza, ponieważ generuje stałą liczbę inwalidacji per wątek, a nie jak w pierwszym przypadku proporcjonalnie do ilości wątków.

## Zadanie 5
:::success
Autor: Tomasz Wołczański
:::

W zamku CLH, podobnie jak w zamku Andersona, każdy wątek oczekuje w pętli na zmianę wartości komórki pamięci, która może zostać zmodyfikowana tylko przez jeden wątek. Dzięki temu liczba niepotrzebnych dostępów do szyny danych jest minimalna i narzut czasowy związany z rywalizacją wątków jest prawie zerowy. W przeciwieństwie do zamka Andersona, zamek CLH wykorzystuje (niejawną) listę wiązaną, więc osiąga lepszą złożoność pamięciową. Gdy w systemie mamy $L$ zamków i maksymalnie $n$ wątków, to algorytm Andersona musi zaalokować tablicę rozmiaru $n$ dla każdego zamka, co daje złożoność pamięciową $O(nL$). Natomiast złożoność algorytmu CLH wynosi $O(n+L)$.

W algorytmie CLH wątek, który chce uzyskać dostęp do sekcji krytycznej tworzy węzeł `QNode` i inicjalizuje jego wartość na `true` (jeśli wątek nie uzyskał jeszcze dostępu do sekcji krytycznej, to wartość w jego węźle jest równa `true`, w przeciwnym razie `false`). Następnie przy pomocy metody `getAndSet` atomowo odczytuje i ustawia ogon niejawnej listy na swój węzeł. Jeśli wartość w odczytanym ogonie jest równa `true`, to znaczy, że w sekcji krytycznej znajduje się jeszcze jakiś wątek, więc trzeba na niego poczekać. Zwolnienie zamka przez wątek polega na ustawieniu wartości w węźle tego wątku na `false`. Zamek można zaimplementować w następujący sposób:

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

Aby ograniczyć liczbę alokacji węzłów `QNode`, można w metodzie `unlock` ustawiać węzeł `myNode` na węzeł występujący przed nim na liście - wątek odpowiadający temu węzłowi wyszedł już z sekcji krytycznej, więc ten węzeł jest nieużywany.

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
:::success
Autor: Marcin Wróbel
:::

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

Implementacja jest błędna, ponieważ może dojść do zakleszczenia.
Niech `X_myNode(y)` oznacza, że zmienna `myNode` wątku `X` jest obiektem `QNode` z wartością `locked` równą `y`;
Działa tylko jeden wątek nazwany A.
- A.lock()
Po wykonaniu `tail == A_myNode(true)`
- A.unlock()
Po wykonaniu `tail == A_myNode(false)`
- A.lock()
`qnode.locked = true;` sprawi, że
`tail == A_myNode(true)`
`Qnode pred = tail.getAndSet(qnode);` po tej instrukcji
`pred == A_myNode(true)`
Program w nieskończoność będzie wykonywał pętlę `while (pred.locked) {}`, choć jest jedynym wątkiem chcącym uzyskać zamek.

## Zadanie 7
:::success
Autor: Jan Dalecki
:::



Zamek implementuje timeout poprzez metodę `tryLock`, którą może wywołać każdy wątek w bloku try...catch. Metoda przyjmuje jako argument czas, który wątek wywołujący jest w stanie czekać na dostanie zamka. Próba otrzymania zamka jest porzucana jeżeli minie okrelony czas.

W algorytmnie CLH zwykłe porzucenie próby dostania się do zamka spowodowałoby zagłodzenie wątków czekających w kolejce. Z tego powodu porzucone węzły są przejmowane przez kolejne przychodzące wątki.

W strukturze `QNode` przechowujemy wskaźnik pod polem `pred` na inny `QNode`. Pole `pred` jest na początku zawsze `null`, a jeżeli nie zostanie podmienione na strukturę `AVAILABLE` tylko na inną strukturę, to oznacza, że wątek z niepowodzeniem wykonał metodę `tryLock`.

Jeżeli poprzednik (wskazywany przez `tail`) miał wartość `null` lub przechowywał `AVAILABLE` możemy otrzymać zamek. W przeciwnym przypadku wchodzimy w pętlę na ustalony przez nas czas.

W pętli czekamy, aż pole `pred` poprzedniego wątku stanie się `AVAILABLE` - wtedy dostajemy zamek.
Jeżeli zmieni się na inną wartość (poprzednik porzucił próbę dostania się do zamka) zmieniamy naszego poprzednika na tego, który jest wskazywany przez `pred`.

Jeżeli minie nasz czas musimy ustawić `tail` na naszego poprzednika, jeżeli jesteśmy ostatni w kolejce (`tail` wskazuje na nas). W przeciwnym przypadku ustawiamy nasze pole `pred` na naszego poprzednika.

## Zadanie 8
:::success
Autor: Wiktor Bukowski
:::



Zamek opiera się na następującej idei:
Gdy zamek próbuje zająć blokadę, ustawia się na końcu kolejki. Jeśli jest już tam jakiś wątek, modyfikuje jego wskaźnik `next` na samego siebie, a następnie czeka aż ten wątek ustawi jego zmienną `locked` na fałsz.

Aby zwolnić zamek musimy sprawdzić, czy żaden wątek nie ustawił się za nami. Sprawdzamy więc swój wskaźnik `next`. Jeśli nie jest nullem, ustawiamy jego zmienną `locked` na fałsz i kończymy algorytm. Jeśli jednak jest nullem, możliwym jest powolne ustawianie tego wskaźnika przez inny wątek. Aby wyeliminować ten problem, próbujemy ustawić zmienną `tail` (trzymającą koniec kolejki) na nulla. Jeśli się to uda, wiemy, że jesteśmy jedynym wątkiem i możemy zakończyć algorytm. Jeśli się to nie uda, to inny wątek powinien zaraz zmodyfikować nasz wskaźnik `next`, więc czekamy na to i ustawiamy jego zmienną `locked` na fałsz. Po wszystkich tych krokach żaden wątek nie może już skorzystać z naszego węzła, a więc możemy go użyć ponownie.

W systemie o architekturze NUMA wydajność tego zamka jest satysfakcjonująca, ponieważ każdy z wątków pętli się na komórce znajdującej się w jego własnej pamięci.

## Zadanie 9
:::success
Autor: Mateusz Kisiel
:::

### TAS

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

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

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