# Ćwiczenia 9, grupa śr. 16-18, 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 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski |==X==| X | X | X | X | | X | X | |
Marcin Dąbrowski | | | | | | | | | |
Jakub Gałecki | | | | | | | | | |
Kamila Goszcz | X | X | X | X | | X | X | X | X |
Wiktor Hamberger | X | X | X | X | X |==X==| X | X | X |
Jan Jankowicz | X | X | X | X | X | X | X | X | X |
Mikołaj Jaszcza | X | X | X |==X==| | X | | X | X |
Zuzanna Kania | X | X | X | X | |==X==| | X | X |
Wiktoria Kuna | | | | | | | | | |
Patryk Mazur | X | X | X | X | X | X | | X |==X==|
Hubert Obrzut | | | | | | | | | |
Magdalena Rzepka | X | X | | X | X | X | | | X |
Joanna Stachowicz | X |==X==| X | X | X | X | | X | X |
Rafał Starypan | X | X |==X==| X | | X | | X | X |
Maria Szlasa | X | X | X | X | X | X | | X | X |
Daniel Wiczołek | X | X | X | | X | X | | | |
Adam Jarząbek | X | X | X | X | | X | | | X|
:::

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

## Zadanie 1
:::success
Autor: Daniel Boguszewski
:::

Zasada lokalności odwołań to dwie własności:
1. Lokalność czasowa:
Jeśli program korzysta z komórki pamięci, w niedługim czasie ponownie z niej skorzysta.
2. Lokalność miejscowa:
Jeśli program korzysta z komórki pamięci, w niedługim czasie skorzysta z komórki blisko niej.

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

Spójność pamięci podręcznych to spójność danych dzielonych przez różne pamięci podręczne. Gdyby spójność nie zachodziła, różne procesory, odnoszące się do jednej komórki pamięci, mogłyby odczytywać już nieaktualne dane (inny procesor zmodyfikował komórkę, ale reszta procesorów nie zaktualizowała pamięci podręcznych). Protokoły spójności temu zapobiegają.

MESI to prosty protokół spójności, działający na 4 stanach pamięci podręcznej:
1. Modified - procesor zmodyfikował komórkę pamięci podręcznej i musi zapisać ją do pamięci głównej.
2. Exclusive - wiersz pamięci podręcznej posiada te same dane, co pamięć główna, dodatkowo wyłącznie on posiada ten wiersz w swojej pamięci podręcznej.
3. Shared - jak wyżej, ale procesor może dzielić ten sam wiersz z innym procesorem.
4. Invalid - wiersz pamięci podręcznej posiada nieaktualne dane.

Gdy procesor rząda dostępu do pamięci głównej, a żaden inny nie ma go we własnej pamięci, otrzyma go w stanie Exclusive.
Gdyby inny procesor domagał się tego samego wiersza pamięci, nie otrzyma go od pamięci głównej, ale z pamięci odpowiedniego procesora, a wiersze zyskują stan Shared.
By ograniczyć wykorzystanie pamięci, gdy procesor modyfikuje wartość komórki swojej pamięci podręcznej, wiersz zyskuje stan Modified, a procesory, które go dzieliły, zmieniają własny wiersz na Invalid. Pamięć główna zapisze dane dopiero wtedy, gdy procesor opróżni wiersz z własnej pamięci (Write-Back).

## Zadanie 2
:::success
Autor: Joanna Stachowicz
:::

Wydajność programów, implementujących zamek, mierzy się, badając funkcję t(n), gdzie n to liczba wątków, a t to czas wykonania programu, zakładającego locka. Za idealną wydajność przyjmujemy stałą funkcję czasu (niezależną od liczby wątków w programie)


#### działanie TAS


każde wywołanie tej instrukcji powoduje konieczność zmiany stanów wszystkich wierszy, przechowujących zmienną state, na stan **invalid**, ponieważ przy każdym wywołaniu, zmieniana jest wartość state na **true** (często bezsensownie nadpisywane jest true). Dlatego, jeżeli w programie jest dużo wątków, przy każdym nadpisaniu state, trzeba będzie aktualizować dane we wszystkich cache'ach, zawierających tę kopię. Stąd: wykonywanie Test and Set na zajętym zamku jest bez sensu (ponieważ, gdy zamek jest zajęty, wartość state wynosi true). Ten problem także prowadzi do dwóćh pochodnych problemów - chybienia w cache'ach procesorów, mających nieaktualne dane, a także problem w sytuacji, gdy wątek chce zwolnić zamek - wówczas będzie musiał rywalizować z wątkami, wirującymi w pętlach while, co prowadzi do dużego opóźnienia w zwolnieniu zamka

#### działanie TTAS


w tym rozwiązaniu implementacyjnym pozbywamy się głównego problemu, jakim jest bezsensowne nadpisywanie wartości true, poprzez dodanie dodatkowej pętli while, która sprawi, że nie będziemy wywoływać metody get and set w sytuacji, gdy zamek jest zajęty, czyli gdy wartośc state wynosi true. Dzięki tej modyfikacji, kiedy semafor jest zajęty, po pewnym czasie wszystkie procesory będą miały w swoim cache'u wartość zmiennej state w stanie **shared**, co sprawi, że gdy będą szukać wartości zmiennej state, wystarczy, że zajrzą do pamięci podręcznej - nie muszą sięgać do współdzielonej szyny danych.

Problem, który nie został w tej implementacji zneutralizowany, pojawia się w sytuacji, gdy zamek jest zwolniony - wówczas wiersze, które dotychczas były w stanie shared, przechodzą w stan **invalid**, co powoduje konieczność zaktualizowania wartości zmiennej state przy pomocy pamięci operacyjnej

## Zadanie 3
:::success
Autor: Rafał Starypan
:::


Algorytm wykorzystuje tablicę typu boolean, mamy także współdzieloną zmienną next, która wskazuje na indeks w tablicy, który będzie odczytywał dany wątek. W celu zajęcia zamka wątek wykonuje atomowo metodę getAndIncrement() na zmiennej next, po czym wiruje, dopóki odczytywana komórka zawiera wartość false. Gdy poprzedni wątek wywoła metodę unlock(), wartość w komórce zostanie ustawiona na true, co umożliwi zajęcie zamka.




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


---
**Wersja 1:** Implementacja opisana jako pierwsza ma następującą wadę - czekające wątki wirują na zmiennej licznika w trakcie czekania na pozostałe ("późniejsze" wątki). Zauważmy, że takie działanie będzie powodowało, że pamięć cache dla poszczególnych wątków bardzo często będzie wchodziła w stan 'Invalid' (średnio O(n) razy dla pojedynczego wątku). Nastąpi wtedy komunikacja przez szynę danych co powoduje spowolnienie działania programu. Tj. każde zwiększenie licznika spowoduje "tłok" na szynie danych. Dokładniej - każde zwiększenie licznika spowoduje, że pamięć 'wcześniejszych' wątków przejdzie w stan 'Invalid'. Ponadto doliczyć trzeba 'koszt' zamku TTAS. Mimo że jest wydajniejszy od TAS, to spowoduje tłok na szynie danych gdy następuje unlock (a nastąpi n razy). Powoduje to podobne problemy wydajnościowe jak opisane powyżej.

Łącznie mamy $O(n^2)$ przejść do stanu 'Invalid' cache'y pojedynczych wątków.

---
**Wersja 2:** Natomiast drugie rozwiązanie przypomina 'Anderson Queue Lock' opisany na wykładzie, tj:

Zatem wiemy, że każdy wątek będzie miał tylko jedną "swoją" komórkę do której pisze (pomijając czytanie komórki b[n-1]), oraz jedną (inną) którą czyta. A więc, gdy zastosujemy "sztuczkę" polegającą na umieszczeniu komórek tablicy w różnych liniach cache'a (tak jak opisane w z3) przejścia do stanu 'Invalid' będą znacznie rzadsze niż w przypadku pierszej propozycji rozwiązania. Każdy wątek (poza n-tym) zapisując ma wpływ na dokładnie 1 inny wątek, a jedynie raz modyfikuje swoją wartość. Zatem każdy wątek, poza n-tym, będzie odpowiedzialny za jedno przejście do stanu 'Invalid' cache'a pojedynczego wątku.

Natomiast wątek n-ty tylko raz spowoduje przejście do stanu 'Invalid' cache'y pozostałych wątków. Łącznie mamy $O(n)$ przejść do stanu 'Invalid' cache'y pojedynczych wątków.

---
Podsumowując, w systemach wieloprocesorowych ze spójnymi pamięciami podręcznymi i wspólną szyną danych wydajniejsze będzie rozwiązanie drugie, ponieważ ilość przejść do stanu 'Invalid' jest liniowa w stosunku do liczby wątków, a dla rozwiązania pierwszego ta liczba jest zależna kwadratowo od ilości wątków.

## Zadanie 5
:::success
Autor: Jan Jankowicz
:::
>Przypomnij zasadę działania zamka CLH.

Zasada działania zamku CLH jest podobna do tej, którą prezentuje zamek Andersona z tą różnicą, że w przypadku zamku CLH do trzymania informacji o możliwości jego nabycia wykorzystujemy niejawną, elastyczną listę łączoną zamiast zwykłej tablicy o ustalonym rozmiarze.
Do implementacji wspomnianej listy służą obiekty (węzły) przechowujące wartość typu boolean, która wskazuje, czy wątek, którego dotyczy, nabył zamek lub na niego czeka (true), czy też go już zwolnił (false).
Każdy wątek, który chce nabyć zamek CLH, otrzymuje dwa takie obiekty. Pierwszy zawiera informację o nim samym (jest tworzony i posiada wartość true), natomiast drugi o jego poprzedniku w kolejce (w momencie wywołania metody lock() wskazuje na niego 'tail').
Zgodnie z opisem tego pola wątek może zająć zamek, jeśli jego poprzednik ustawił swoją flagę na false. Jeśli tak się stanie, to wątek nabywa zamek, wchodzi do sekcji krytycznej i uwalnia zamek ustawiając flagę w swoim obiekcie na false. Wątek, dla którego ten obiekt był poprzednikiem, odczytuje nową wartość (aktywnie czekając/wirując na tym polu) i podobnie jak poprzednik nabywa zamek.



>W jaki sposób ograniczyć w implementacji tego zamka liczbę alokacji węzłów listy?

Wyżej zostało wspomniane, że obiekt, który mówiący o stanie wątku oczekującego w kolejce, jest tworzony w momencie zgłoszenia chęci nabycia zamka.
Można jednak ograniczyć ilość takich alokacji poprzez przydzielenie danemu wątkowi przy ponownej próbie nabycia zamka obiektu węzła wcześniej wykorzystanego przez ten wątek. Gdy wątek zwalnia zamek, jego obiekt poprzednika nie jest już nikomu potrzebny i może zostać w ten sposób zrecyklingowany.

## Zadanie 6
:::success
Autor: Zuzanna Kania
:::

Implementacja ta jest błędna, ponieważ wątek zostawia sobie do ponownego wykorzystania węzeł, na który może jeszcze wskazywać tail lub jego następnik. W sytuacji, gdy węzeł ten jest aktualnie wskazywany przez tail może dojść do zapętlenia, ponieważ jeśli wątek zwolni zamek, ale nie będzie kolejnych oczekujących w kolejce, to kiedy ponownie ten sam wątek spróbuje zająć zamek, na swojego poprzednika ustawi on węzeł wskazywany przez tail, czyli swój własny węzeł, którego wartość locked chwilę wcześniej ustawił na true. Przez to wątek zostanie uwięziony w pętli while.


## Zadanie 7
:::success
Autor: Wiktor Hamberger
:::

## Zadanie 8
:::success
Autor: Kamila Goszcz
:::

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

Architektura NUMA charakteryzuje się tym, że nie ma również 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ć.

## Zadanie 9
:::success
Autor: Patryk Mazur
:::

a) TAS


boolean isLocked(){
    return state.get(); // Z pozdrowieniami
} 

b) CLH


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

c) MCS


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