# PW - lista 11

## Zadanie 1

a)

Wątek A usuwa węzeł `a` i wątek B w tym samym czasie dodaje węzeł `b`:
- `head.next.compareAndSet(a, a.next)`
- `a.next.compareAndSet(b.next, b)`

Oba przypisania się powiodą, ale węzeł `b` nie zostanie prawidłowo dodany.

b)

Wątek A usuwa węzeł `a` i wątek B w tym samym czasie usuwa węzeł `b`:
- `head.next.compareAndSet(a, a.next)`
- `a.next.compareAndSet(b, b.next) `

Obie operacje się powiodą, ale tylko węzeł `a` będzie prawidłowo usunięty.

<br/>

Chcemy zapewnić, żeby pole `next` usuniętego węzła nie mogło być zmodyfikowane.

W tym celu zmieniamy typ pola `next` na `AtomicMarkableReference<T>`, tak aby oprócz referencji zawierało flagę `marked`. Węzeł, którego pole `next` ma ustawioną flagę `marked` jest logicznie usunięty.

Klasa `AtomicMarkableReference<T>` udostępnia metodę

compareAndSet(T expectedReference, T newReference, boolean expectedMark, boolean newMark)

którą można wykorzystywać podczas dodawania i usuwania węzła, żeby upewnić się, że w międzyczasie nie została zmodyfikowana referencja do następnego węzła ani nie został on usunięty.




## Zadanie 2



### CompareAndSet
#### 17
Wywołanie mające na celu usunięcie martwego wierzchołka. Zawiedzie, gdy:
1) pred przestanie być żywy - inny wątek logicznie go usunie, wtedy jego flaga next będzie true != false
2) Zmieni się kolejny element - inny wątek fizycznie usunie w metodzie find lub zostanie dodany nowy wierzchołek.
#### 39
Wywołanie mające na celu dodanie nowego wierzchołka. Zawiedzie, gdy:
1) pred przestanie być żywy - inny wątek logicznie go usunie, wtedy jego flaga next będzie true != false
2) Zmieni się kolejny element - zostanie dodany nowy wierzchołek.
#### 55
Wywołanie mające na celu logiczne usunięcie danego wierzchołka.
1) Zmieni się next w curr. To może się zdarzyć na skutek add i remove na kolejnym wierzchołu.
2) Zmieni się mark w usuwanym wierzchołku. Wtedy
#### 58
Wywołanie mające na celu fizyczne usunięcie danego wierzchołka.
1) Zostanie dodany element bezpośrednio wcześniejszy
2) Zostanie usunięty element bezpośrednio wcześniejszy

### Dlaczego rezultat drugiego wywołania compareAndSet() w metodzie remove() nie jest sprawdzany? Czy można je usunąć nie tracąc poprawności implementacji?

Ponieważ logicznie element został usunięty, nie ma różnicy czy zostanie on usunięty fizycznie przez remove, czy metodę find, która ma za zadanie te elementy czyścić. Usunięcie tego pola nie powoduje więc utraty poprawności.

## Zadanie 3


### Treść
#### Polecenie
Załóżmy, że w metodzie $add()$ klasy $LockFreeList$ okazało się, że niezbędny jest kolejny obrót pętli $while(true)$, ponieważ $pred$ nie wskazuje już na curr, ale pred nie ma ustawionego pola marked.
Czy w tej sytuacji koniecznie musimy przeglądać całą listę od początku?
#### Kod

public boolean add(T item) 
{ 
    int key = item.hashCode(); 
    while (true) 
    {
        Window window = find(head, key);
        Node pred = window.pred, curr = window.curr; 
        if (curr.key == key) 
        {
            return false; 
        } 
        else 
        {
            Node node = new Node(item);
            node.next = new AtomicMarkableReference(curr, false);
            if (pred.next.compareAndSet(curr, node, false, false))
            {
                return true; 
            }
        }
    }
}

### Rozwiązanie
Pytanie dotyczy konieczności uruchomienia find od head listy. Nie jest to konieczne w podanym przypadku, ponieważ pred nie został oznaczony marked. Oznaczo to, że pred jest logicznie na liście (w konsekwencji także fizycznie). Ponieważ interesowało nas "okienko" od pred do jakiegoś większego elementu, a z założenia elementy na liście są posortowane, wystarczy rozpocząć poszukiwanie od pred.

## Zadanie 4



## Zadanie 5


public class BoundedQueue <T> {
    ReentrantLock enqLock, deqLock;
    Condition notEmptyCondition, notFullCondition;
    AtomicInteger size;
    volatile Node head, tail;
    final int capacity;
    public BoundedQueue(int _capacity) {
        capacity = _capacity;
        head = new Node(null);
        tail = head;
        size = new AtomicInteger(0);
        enqLock = new ReentrantLock();
        notFullCondition = enqLock.newCondition();
        deqLock = new ReentrantLock();
        notEmptyCondition = deqLock.newCondition();
    }

    
    public void enq(T x) {
        boolean mustWakeDequeuers = false;
        Node e = new Node(x);
        enqLock.lock();
        try {
            while (size.get() == capacity)
                notFullCondition.await();
            tail.next = e;
            tail = e;
            if (size.getAndIncrement() == 0)
                mustWakeDequeuers = true;
        } finally {
            enqLock.unlock();
        }
        if (mustWakeDequeuers) {
            deqLock.lock();
            try {
                notEmptyCondition.signalAll();
            } finally {
                deqLock.unlock();
            }
        }
    }
    public T deq() {
        T result;
        boolean mustWakeEnqueuers = false;
        deqLock.lock();
        try {
            while (head.next == null)
                notEmptyCondition.await();
            result = head.next.value;
            head = head.next;
            if (size.getAndDecrement() == capacity) {
                mustWakeEnqueuers = true;
            }
        } finally {
            deqLock.unlock();
        }
        if (mustWakeEnqueuers) {
            enqLock.lock();
            try {
                notFullCondition.signalAll();
            } finally {
                enqLock.unlock();
            }
        }
        return result;
    }
}

:::info
Czy istnieje taka sekwencja wykonań metod ```enq()``` i ```deq()```, że zmienna *size()* staje się ujemna?
:::

`
suppose a thread is in the process of inserting a new node: It has acquired the enqLock and redirected the last node to point to the new node, but has not yet redirected the tail field. A concurrent dequeuing thread could acquire the deqLock, read and return the new node’s value, redirect the head to the new node, and decrement size, all before the enqueuer redirects tail to the newly inserted node. In this example, size would be negative temporarily because the dequeuer decrements it before the enqueuer increments it. The enqueuer need not wake any waiting dequeuers in this case, because the item it enqueued has already been dequeued.
`

## Zadanie 6


Problem zagubionej pobudki występuje w przypadku, kiedy któreś wątki czekają na wybudzenie nie zauważając, że ich warunek na wybudzenie został już spełniony.

W przypadku enquerów, sprawdzamy czy size jest równe capacity. Mimo, że zmienna ta nie jest zabezpieczona lockiem, to podczas wysyłania sygnału z deque nakładamy locka na enquerów, więc między sprawdzeniem warunku a ciałem warunku nie może zostać do tego wątku wysłany sygnał.

W przypadku dequerów sytuaja jest praktycznie taka sama - sprawdzamy, czy head jest nullem, następnie czekamy na sygnał, którego nie możemy dostać pomiędzy sprawdzeniem warunku i ciałem funkcji.

## Zadanie 7


public T deq() throws EmptyException {
    T result;
    deqLock.lock();
    try {
        if (head.next == null) {
            throw new EmptyException();
        }
        result = head.next.value;
        head = head.next;
    } finally {
        deqLock.unlock();
    }
    return result;
}

Wątek A: sprawdza czy `head.next == null` (false)
Wątek B: sprawdza czy `head.next == null` (false)

Wątek A: usuwa element i `head.next` staję się nullem
Wątek B: próbuje operować na węźle, którego już nie ma (`result = head.next.value`)