# PW - lista 10
:::success
## Zadanie 1
:::

Mamy wielopoziomową hierarchię pamięci podzieloną na clustery zwierające w sobie procesory. Np. dwupoziomową i od pierwszego poziomu odwołujemy się szybko, a operacje na drugim poziomie są bardziej kosztowne. W takim przypadku może przydać sie HBOLock.

HBOLock to rozszrzenie idei Back-off Lock ktora polega na tym, aby wątek robił coraz dłuższego sleepa w pętli w funkcji lock. Dzięki temu wątki oczekujący 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 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);
    }
}

:::success
## Zadanie 2
:::


Ideą zamków kohortowych jest to, aby wykorzystać dwa zamki:
- lokalny: rywalizują o niego wątki znajdujące się w tym samym klastrze
- globalny: rywalizują o niego całe klastry

Aby wątek mógł wejść do sekcji krytycznej, musi zająć obydwa zamki.

Gdy dany wątek wywołuje metodę `unlock()` sprawdza czy inne wątki w jego klastrze oczekują na założenie zamka lokalnego (metoda `alone()`). Jeżeli tak, to zwalnia on tylko zamek lokalny. W przeciwnym przypadku zwalnie również zamek globalny, pozwalając metodom z innego klastra wejść do swoich sekcji krytycznych.
Aby uniknąć sytuacji, w której wykonują się wątki z tylko jednego klastra, a reszta jest głodzona, wporowadzona zostaje klasa `TurnArbiter`. Jeżeli zamek globalny zbyt długo trzymany jest przez jeden klaster, decyduje on o zwolnieniu go nawet jeśli metoda `alone()` zwraca `false`.

public class TurnArbiter {
  private final int TURN_LIMIT;
  private int turns = 0;
  public LocalPassingArbiter(int limit) {
    TURN_LIMIT = limit;
  }
  public boolean goAgain() {
    return (turns < TURN_LIMIT);
  }
  public void wentAgain() {
    turns++;
  }
  public void passed() {
    turns = 0;
  }
}

public class CohortLock implements Lock {
  final Lock globalLock;
  final ClusterLocal<CohortDetectionLock> clusterLock;
  final TurnArbiter localPassArbiter;
  ClusterLocal<Boolean> passedLocally;
  public CohortLock(Lock gl, ClusterLocal<CohortDetectonLock> cl, int passLimit) {
    globalLock = gl;
    clusterLock = cl;
    localPassArbiter = new TurnArbiter(passLimit);
  }
  public void lock() {
    clusterLock.get().lock();
    if (passedLocally.get()) return;
    globalLock.lock();
  }
  public void unlock() {
    CohortDetectionLock cl = clusterLock.get();
    if (cl.alone() || !localPassArbiter.goAgain()) {
      localPassArbiter.passed();
      passedLocally.set(false);
      globalLock.unlock();
    } else {
      localPassArbiter.wentAgain();
      passedLocally.set(true);
    }
    cl.unlock();
  }
}

:::success
# Zadanie 3
:::

public class CoarseList<T> {
    private Node head;
    private Lock lock = new ReentrantLock();
    public CoarseList() {
        head = new Node(Integer.MIN_VALUE);
        head.next = new Node(Integer.MAX_VALUE);
    }
    
    public boolean add(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 false;
            } else {
                Node node = new Node(item);
                node.next = curr;
                pred.next = node;
                return true;
            }
        } finally {
            lock.unlock();
        }
    }
    
    public boolean remove(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) {
                pred.next = curr.next;
                return true;
            } else {
                return false;
            }
        } finally {
            lock.unlock();
        }
    }
    
    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();
        }
    }
    
    



1. Punkty linearyzacji gwarantujące zachowanie mapy abstrakcji "element należy do zbioru $\Leftrightarrow$ węzeł na liście, w którym znajduje się element jest osiągalny z węzła **head**":

- **add($x$)**
- $x$ nie występował w zbiorze: `pred.next = node` (linia 25)
- $x$ występował w zbiorze: zajęcie zamka,
- **remove($x$)**
- $x$ występował w zbiorze: `pred.next = curr.next` (linia 45),
- $x$ nie występował w zbiorze: zajęcie zamka
- **contains(x)**
- zajęcie zamka

2. Mapa abstrakcji: element należy do zbioru $\Leftrightarrow$ węzeł na liście, w którym znajduje się element jest osiągalny z węzła head

add - po 25 linii, remove - po 44 linii, cotains - po zajęciu locka

Przyjmijmy, że **add()** jest linearyzowalna w momencie zajęcia zamka.

Wtedy w momencie linearyzacji wywołania **add(x)** na pustej liście, reprezentacja listy wygląda następująco:

    head -> tail

czyli węzeł na liście, w którym znajduje się **x** nie jest osiągalny z węzła **head**, co jest sprzeczne z tym, że **x** należy już do zbioru.

3. Element **x** należy do zbioru wtedy i tylko wtedy gdy:
* Gdyby punktem linearyzacji w funkcji add było zrobienie locka, to w tym momencie powinna zajść zmiana w strukturze. Zmiana zajdzie jednak dopiero w momencie wykonania: pred.next = node;

4. Mapa abstrakcji: Element istnieje w naszym zbiorze, jeżeli węzeł na liście, w którym znajduje się element jest osiągalny z węzła head lub jeśteśmy po zrobieniu locka w funkcji add. Dodatkowo robimy wyjątek, gdy jesteśmy w locku w metodzie remove - wtedy element nie istnieje.

:::success
# Zadanie 4
:::

### ```add()``` z *FineList*

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

Wybieramy punkt linearyzacji w zależności od wyniku metody ```add()```:
* udało się wstawić element (```return true```): instrukcja 21, czyli ```pred.next = newNode```. Mamy spełnione wszystkie niezmienniki -
* wiemy, że naszego elementu nie ma w liście (przeszliśmy przez *if*'a w linii 16)
* lista jest posortowana, czyli $pred.key < newNode.key < curr.key$
* *newNode* jest osiągalny z początku listy
* nie udało się wstawić (```return false```): ~~linia 17, czyli ```return false```~~ zajęcie węzła w linii 8 albo 14. Punkt linearyzacji nie może być w ```return false``` - w takim wypadku, po zwolnieniu zamków w blokach *finally*, inne wątki mogłyby "wyprzedzić" instrukcję ```return false``` i np. usunąć element, o którym właśnie wywnioskowaliśmy, że jest na liście. Ten problem znika, gdy punkt linearyzacji jest w miejscu zajęcia zamka.
1. Sukces - linia 21
2. Porażka:
- linia 8 lub 14 zależnie czy wchodzimy do `while` czy nie.

### ```remove()``` z *FineList*

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

Podobnie jak w przypadku metody ```add()```:
* udało się usunąć element - instr. 17, czyli ```pred.next = curr.next;```
* lista oczywiście dalej jest posortowana
* wszystkie elementy dalej są osiągalne
* nie udało się usunąć - ~~```return false```, czyli instr. 20~~ zajęcie węzła w linii 8 albo 14. Argumentacja analogiczna jak przy metodzie ```add()```.

1. Sukces - linia 17
2. Porażka:
- linia 8 lub 14 zależnie czy wchodzimy do `while` czy nie.
:::success
# Zadanie 5
:::

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();
            }
            return curr.key == key; 
        } finally {
            curr.unlock();
        }
    } finally {
        pred.unlock();
    }
}

Implementacja ta jest poprawna, ponieważ szuka ona takiej pary <pred, curr>, że $pred.next == curr$ oraz $pred.key < key$ i $curr.key \geq key$. Na oba węzły zakładane są zamki, co gwarantuje, że przed linijką 15 oba węzły nie zmienią się i $curr.key == key$ zwróci poprawny wynik. Jeśli otrzymamy true, to wtedy element jest na liście, wpp. jeśli otrzymamy false, to wiemy, że $pred.key < key$ i $curr.key > key$, czyli elementu nie ma na liście, ponieważ jest ona posortowana.

# Zadanie 6


---

Załóżmy, że mamy listę:
-inf -> a -> b -> +inf

Wątek A chce wykonać `remove(b)`. Kiedy znajdzie już wartość b na liście, jesteśmy w linijce 38 i mamy `pred = a` i `curr = b`. Zwróćmy uwagę, że wątek A nie zajął jeszcze zamków.

Wtedy wątek B chce wykonać `add(a')` i udaje mu się zająć zamki a i b przed wątkiem A.

Zatem lista wygląda następująco:
-inf -> a -> a' -> b -> +inf

Wątkowi A udaje się zając zamki i wykonuje `validate(pred, curr)`. Zwraca ona fałsz, ponieważ teraz następnikiem a jest a', a nie b. Metoda remove ma pętle while, a więc wątek A będzie próbował usunać element b aż do skutku.

Tym razem po znalezieniu na liście a mamy: `pred = a'` i `curr = b`.

Wątkowi B ponownie udaje się zając zamki przed wątkiem A i wykonuje `remove(a')`. Po wykonaniu tej metody lista wygląda następująco:
-inf -> a -> b -> +inf

Wątek A znów wykonuje `validate(pred, curr)` i otrzymuje false, bo na liście nie ma już a'.

Zatem dopóki wątek B będzie wyprzedzał wątek A i na zmiane dodawał i usuwał element przed a, wątek A w nieskończoność będzie próbował usunąć element b.