# Ćwiczenia 10, grupa śr. 12-14, 4 stycznia 2023

###### 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 | | |
Jan Dalecki | X | | X | X | X | ==X== | X | X | |
Mikołaj Depta | X | X | X | X | X | X | X | | |
Kamil Galik | | | | | | | | | |
Bartosz Głowacki | | | | | | | | | |
Michał Hetnar | x | x | x | x | x | x | x | | |
Adam Jarząbek | | | | | | | | | |
Michał Kierul | | | | | | | | | |
Mateusz Kisiel | 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 | | | |
Marcin Sarnecki | X |==X==| X | X | X | | | | |
Bartosz Szczeciński | X | X | X | X | X | X | X | | |
Tomasz Wołczański | X | | X | X | X | X | X | | |
Marcin Wróbel | 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: Mateusz Kisiel
:::


Mamy wielopoziomową hierarchię pamięci podzieloną na clustery zwierające w sobie procesory. Np. dwupoziomową i do pierwszego poziomu odwołujemy się szybko, a operacje na drugim poziomie są bardziej kosztowne. W takim przypadku warto zastąpić BOLock(Back-off Lock) poprzez HBOLock.

HBOLock to rozszrzenie idei Back-off Lock ktora polegała na tym, aby wątek robił coraz dłuższego sleepa w pętli w funkcji lock. Dzięki temu wątki oczekujące na dany zasób nie będą spamować zpytaniami o stan zmiennej i zmniejszy się użycie procesora.

Rozszerzenie w HBOLock polega na uwzględnieniu tego, że odpytanie o stan zmiennej niesie za sobą różny koszt czasowy w zalezności od tego na którym poziomie hierarchi była ta zmienna. Chcemy, aby kosztownych zapytań było jak najmniej. HBOLock z tego powodu będzie zwiększać czas sleepa w wątkach z innego clusteru bardziej niż w wątkach w obrębie tego samego clusteru.

public class HBOLock implements Lock {
    private static final int LOCAL_MIN_DELAY = ...;
    private static final int LOCAL_MAX_DELAY = ...;
    private static final int REMOTE_MIN_DELAY = ...;
    private static final int REMOTE_MAX_DELAY = ...;
    private static final int FREE = -1;
    AtomicInteger state;
    public HBOLock() {
        state = new AtomicInteger(FREE);
    }
    public void lock() {
        int myCluster = ThreadID.getCluster();
        Backoff localBackoff =
            new Backoff(LOCAL_MIN_DELAY, LOCAL_MAX_DELAY);
        Backoff remoteBackoff =
            new Backoff(REMOTE_MIN_DELAY, REMOTE_MAX_DELAY);
        while (true) {
            if (state.compareAndSet(FREE, myCluster)) {
                return;
            }
            int lockState = state.get();
            if (lockState == myCluster) {
                localBackoff.backoff();
            } else {
                remoteBackoff.backoff();
            }
        }
    }
    public void unlock() {
        state.set(FREE);
    }
}

## Zadanie 2
:::success
Autor: Marcin Sarnecki
:::

Pomysł polega na uzyciu wielu zamków na różnych poziomach hierarchii pamięci. Każda kohorta wątków ma swój własny zamek oraz kohorty mają wspólny, globalny zamek.

Wątek utrzymuje lock() jeśli utrzymuje zarówno lokalny, jak i globalny zamek

Wątek najpierw próbuje zablokować lokalny zamek, a następnie upewnia się, że kohorta, do której należy, zablokowała globalny zamek.

Przy odblokowaniu wątek najpierw sprawdza, czy inny wątek z jego kohorty nie próbuję zablokować zamka. Jeśli tak, to przepuszcza go, nie zwalniając globalnego zamka (występuje limit na liczbę takich sytuacji). Jeśli kohorta była pusta, to zwalnia oba zamki.

Metoda `alone()` zwraca fałsz, jeśli $na \space pewno$ inny wątek z tej samej kohorty próbuje dostać się do zamka. Nie działa to w drugą stronę - jeśli zwróci prawdę, to może istnieć wątek próbujący dostać się do zamka, jednak takie przypadki są rzadkie.

`TurnArbiter` służy niezagłodzeniu innych kohort


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


public boolean contains(T item) {
    Node pred, curr;
    int key = item.hashCode();
    lock.lock();
    try {
        pred = head;
        curr = pred.next;
        while (curr.key < key) {
            pred = curr;
            curr = curr.next;
        }
        if (key == curr.key) {
            return true;
        } else {
            return false;
        }
    } finally {
        lock.unlock();
    }
}

:::info
Na przykładzie zbioru zaimplementowanego przy pomocy
CoarseList wyjaśnij, czym są niezmiennik reprezentacji
(ang. representation invariant) oraz mapa abstrakcji
(ang. abstraction map).
:::


W skrócie:
- niezmiennik reprezentacji to pewien warunek który musi istnieć przed wywołaniem metody i musi zostać przywrócony wraz z wyjściem z metody
- mapa abstrackji - zbiór który jest otrzymywalny z zadanej listy - w przypadku CoarseList jest że element jest w zbiorze <=> gdy jest odnajdywalny z głowy listy

:::info
Przypomnij, jakie punkty linearyzacji należy wybrać w
metodach add(), remove() i contains() by następująca mapa
abstrakcji była poprawna: “element należy do zbioru ⇔
węzeł na liście, w którym znajduje się ten element jest
osiągalny z węzła head”.
:::

add(x) - linia 24 - przepięcie wskaźnika poprzednika
remove(x) - linia 43 - j.w.
contains(x) - zajęcie zamka

:::info
Pokaż, że mapa abstrakcji z poprzedniego punktu nie jest
poprawna, jeśli metody będą linearyzowane w momencie
zajęcia zamka.
:::

Chcemy żeby punkt linearyzacji wyznaczał nam moment kiedy żadany efekt operacji miał swój efekt i żeby mapa abstracji uwzględniała zmianę

W przypadku add i remove nie może to być moment zajęcia zamka, ponieważ w tym momencie żadna zmiana nie miała miejsca i dopiero nastąpi w przyszłości

:::info
Zmodyfikuj powyższą mapę abstrakcji tak, by dla metod
linearyzowanych w momencie zajęcia zamka, CoarseList
nadal była poprawną implementacją zbioru.
:::

x należy do zbioru jeśli:
- jest osiągalny z głowy listy i zamek nie jest zajęty przez metodę remove(x)

lub

- zamek jest zajęty przez metodę add(x)

## Zadanie 4
:::success
Autor: Maksymilian Komarnicki
:::

public boolean add(T item) {
    int key = item.hashCode();
    head.lock();
    Node pred = head;
    try {
        Node curr = pred.next;
        curr.lock();
        try {
            while (curr.key < key) {
                pred.unlock();
                pred = curr;
                curr = curr.next;
                curr.lock();
            }
            if (curr.key == key) {
            return false;
            }
            Node newNode = new Node(item);
            newNode.next = curr;
            pred.next = newNode;
            return true;
        } finally {
            curr.unlock();
        }
    } finally {
        pred.unlock();
    }
}
public boolean remove(T item) {
    Node pred = null, curr = null;
    int key = item.hashCode();
    head.lock();
    try {
        pred = head;
        curr = pred.next;
        curr.lock();
        try {
            while (curr.key < key) {
                pred.unlock();
                pred = curr;
                curr = curr.next;
                curr.lock();
            }
            if (curr.key == key) {
                pred.next = curr.next;
                return true;
            }
            return false;
        } finally {
            curr.unlock();
        }
    } finally {
        pred.unlock();
    }
}

Metody add() oraz remove() są linearyzowalne, bo można wyznaczyć dla nich punkty linearyzacji, czyli momenty, w których funkcje "mają efekt". Punkty te są różne w zależności, czy wywołanie metody zakończy się sukcesem, czy porażką.

Metoda add() ma efekt, bo możemy zapewnić, że po dodaniu elementu znajduje się on w zbiorze. Wynika to z podpięcia nowo utworzonego węzła z węzłami pred i curr, które znajdują się w zbiorze, co wynika z tego, że są osiągalne z głowy listy.

Metoda remove() ma efekt, bo możemy zapewnić, że skasowany element znajdował się w zbiorze, bo był osiągalny z głowy listy.

1. Wywołanie add() zakończone sukcesem - linearyzowalne w momencie, gdy następny większy klucz jest zablokowany(linia 7 albo 13).

2. Wywołanie add() zakończone porażką - linearyzowalne w momencie, gdy węzeł z dodawaną wartością jest zablokowany(linia 7 albo 13).

3. Wywołanie remove() zakończone sukcesem - linearyzowalne w momencie, gdy poprzedni węzeł w stosunku do usuwanego jest zablokowany(linia 36 albo 42).

4. Wywołanie remove() zakończone porażką - linearyzowalne w momencie, gdy pierwszy węzeł zawierający większą wartość niż ten usuwany jest zablokowany(linia 36 albo 42).

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

public boolean contains(T item) {
    int key = item.hashCode();
    head.lock();
    Node pred = head;
    try {
        Node curr = pred.next;
        curr.lock();
        try {
            while (curr.key < key) {
                pred.unlock();
                pred = curr;
                curr = curr.next;
                curr.lock();
            }
            // tutaj zamiana względem add / remove       
            return curr.key == key;
        } finally {
            curr.unlock();
        }
    } finally {
        pred.unlock();
    }
}

Ponieważ przechodzimy listę, zawsze trzymając zamki dla sąsiednich węzłów mamy gwarancję, że szukany węzeł nie zostanie wstawiony pomiędzy aktualnie rozpatrywaną parą. Nasza lista jest posortowana, musimy więc jedynie znaleźć pierwszy węzeł o kluczu niemniejszym od szukanego klucza i sprawdzić czy ten klucz i klucz szukany są tym samym.

## Zadanie 6
:::success
Autor: Jan Dalecki
:::
Optymistyczna implementacja zakłada, że problemy synchronizacji pojawiają się dość rzadko. Z tego powodu wątki chcące wykonać operację na elementach listy nie zakładają zamków podczas przejścia przez listę. Zamki są zakładane dopiero na modyfikowane węzły listy.

Zaletą takiego podejścia jest zmniejszenie opóźnienia jeżeli problemy z synchronizacją faktycznie nie wystąpią często.

Zakładamy, że element, który chcielibyśmy usunąć znajduje się początkowo w zbiorze. Niech wątek $A$ stara się usunąć wierzchołek $v$.

Aby metoda remove została zagłodzona `validate` powinno zawsze zwracać `fałsz`.

+ Zatrzymajmy $A$ w linii 33 przed próbą wzięcia zamków.
+ Załóżmy teraz, że wątek $B$ dodaje między $pred_A$ oraz $curr_A$ węzeł $w$.
+ Dajemy $A$ kontynuować i okazuje się, że validate zwróci fałsz.
+ W czasie gdy $A$ zaczyna pętlę while od nowa usuwamy węzeł $w$.
## Zadanie 7
:::success
Autor: Wiktor Bukowski
:::


Potrzebny nam będzie globalny licznik, którego stan będziemy zapisywać lokalnie na początku pętli `while(true)`. W miejscu metody `validate()` musimy zdobyć zamek na globalnym liczniku. Następnie sprawdzamy, czy jego wartość jest równa lokalnej. Jeśli nie, przechodzimy do kolejnego obiegu pętli `while(true)`. Jeśli tak, zwiększamy licznik o 1 i wykonujemy te same operacje co w oryginalnych metodach.

Implementacja na przykładzie `add()`:

Lock counterLock;
volatile int counter = 0;

public boolean add(T item) {
    ...
    int localCounter;
    while (true) {
        localCounter = counter;
        ...    
        curr.lock();
        try {
            counterLock.lock();
            try {
                if (localCounter == counter) {
                    ...
                    counter += 1;
                }
            }
            finally {
                counterLock.unlock();
            } 
        }
        ...
    }
}

## Zadanie 8
:::success
Autor: Marcin Wróbel
:::

W LazyList każdy węzeł może zostać oznaczony (marked) jako usunięty. Usuwanie elementu składa się z dwóch etapów:
- usunięcie logiczne - oznaczenie odpowiedniego węzła jako usunięty
- usunięcie fizyczne - przepięcie odpowiedniego wskaźnika

Dzięki takej różnicy możemy zmodyfikować metodę contains() tak, aby była wait-free.

add() jest taki sam jak w OptimisticList (wywoływana w add() metoda validate() jest zdefiniowana inaczej)

public boolean add(T item) {
    int key = item.hashCode();
    while (true) {
        Node pred = head;
        Node curr = pred.next;
        while (curr.key < key) {
            pred = curr;
            curr = curr.next;
        }
        pred.lock();
        try {
            curr.lock();
            try {
                if (validate(pred, curr)) {
                    if (curr.key == key) {
                        return false;
                    } else {
                        Node node = new Node(item);
                        node.next = curr;
                        pred.next = node;
                        return true;
                    }
                }
            } finally {
                curr.unlock();
            }
        } finally {
            pred.unlock();
        }
    }
}

remove() jest prawie takie samo jak w OptimisticList, tylko została dodana linijka 15

public boolean remove(T item) {
    int key = item.hashCode();
    while (true) {
        Node pred = head;
        Node curr = head.next;
        while (curr.key < key) {
            pred = curr; curr = curr.next;
        }
        pred.lock();
        try {
            curr.lock();
            try {
                if (validate(pred, curr)) {
                    if (curr.key == key) {
                        curr.marked = true;
                        pred.next = curr.next;
                        return true;
                    } else {
                        return false;
                    }
                }
            } finally {
                curr.unlock();
            }
        } finally {
            pred.unlock();
        }
    }
}

public boolean contains(T item) {
    int key = item.hashCode();
    Node curr = head;
    while (curr.key < key)
        curr = curr.next;
    return curr.key == key && !curr.marked;
}

private boolean validate(Node pred, Node curr) {
    return !pred.marked && !curr.marked && pred.next == curr;
}

Czy można, bez straty poprawności, zmodyfikować metodę
**remove()** klasy **LazyList** tak, by zajmowała tylko jeden zamek?

Gdyby LazyList zajmował w metodzie remove() tylko zamek na elemencie
1. **usuwanym** (curr)
to tuż przed przepięciem wskaźników w węźle poprzedzającym. Inny wątek mógłby usunąć węzeł poprzedzający i przepięcie wskaźników nie zmieni ścieżki z head do tail.
Przykład:

Załóżmy, że wątek B chce usunąć element b, wątek C chce usunąć element c.
`-inf -> a -> b -> c -> d -> inf`
Wątek B przepina wskaźniki usuwając element b

-inf → a
       ↓
   b → c → d → inf

Wątek C przepina wskaźniki chcąc usunąć element b

-inf → a
       ↓
       c → d → inf
           ↑
           b

Choć metoda `C.remove(c)` zwróciła true, to element `c` nie został fizycznie usunięty (został usunięty logicznie wartość pola marked jest ustawiona na true). Chociaż mapa abstrakcji jest poprawna, to element C nigdy nie zostanie z tej listy usunięty (problem z wydajnością). Co najważniejsze nie będą działały wywołania metod add(b) (metoda validate(a, c) zawsze będzie zwracać fałsz i add(b) będzie wykonywać pętle while w nieskończoność). Dodatkowo nie będzie działać add( c ). Skoro kolejne wywołania niektórych metod nie będą działać, to implementacja będzie niepoprawna.

2. **poprzedzającym usuwany** (pred)
Po zajęciu pred.lock(), wiemy, że add() w innym wątku nie popsuje nic ze wskaźnikami w tym miejscu, ponieważ nie zajmie zajętego zamka. Załóżmy, że wątek B chce usunąć element b, wątek C chce usunąć element c.
`-inf -> a -> b -> c -> d -> inf`
Wątek B zajął lock a
Wątek C zajął lock b
Oba wątki wykonują metodę validate i wszystko jest ok.

Wątek B przepina wskaźniki

-inf → a
       ↓
   b → c → d → inf

Wątek C przepina wskaźniki

-inf → a
       ↓
       c → d → inf
           ↑
           b

Choć metoda `C.remove(c)` zwróciła true, to element `c` nie został fizycznie usunięty (został usunięty logicznie wartość pola marked jest ustawiona na true). Chociaż mapa abstrakcji jest poprawna, to element C nigdy nie zostanie z tej listy usunięty (problem z wydajnością). Co najważniejsze nie będą działały wywołania metod add(b) (metoda validate(a, c) zawsze będzie zwracać fałsz i add(b) będzie wykonywać pętle while w nieskończoność). Dodatkowo nie będzie działać add( c ). Skoro kolejne wywołania niektórych metod nie będą działać, to implementacja będzie niepoprawna.


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


public boolean contains(T item) {
    int key = item.hashCode();
    while (true) {
        Entry pred = this.head; // sentinel node;
        Entry curr = pred.next;
        while (curr.key < key) {
            pred = curr; 
            curr = curr.next;
        }
        try {
            // pred.lock(); curr.lock(); <- tego nie robimy
            if (validate(pred, curr)) {
                return (curr.key == key);
            }
        } finally { // always unlock
            pred.unlock(); 
            curr.unlock();
        }
    }
}

Kontrprzykład:

Funkcję `contains(x)` wykonuje sam wątek `A` do linijki 12 włącznie (`validate` jest ok).
Następnie pojawia się nowy wątek `B`, który usuwa element `x` i kończy swoje działanie.
Następnie wątek `C` wykonuje `contains(x)` sam, kończy swoje działanie i zwraca `false`.
Wówczas wybudza się `A` i kontynuuje swoje działanie od linijki 13 i zwraca `true`.

Takie wykonanie nie jest linearyzowalne.


public boolean contains(T item) {
    int key = item.hashCode();
    Node curr = head;
    while (curr.key < key)
        curr = curr.next;
    return curr.key == key /* && !curr.marked; <- tego nie robimy */
}

Pominięcie badania bitu mark powoduje, że nasz algorytm nie przestrzega mapy abstrakcji. Element powinien być uważany za usunięty ze zbioru, gdy jest albo usunięty fizycznie lub oznaczony przez bit mark (usunięty logicznie). Algorytm pomijający sprawdzanie tej wartości jest niepoprawny.