# Współbieżne 5

:::success
## Zadanie 1
:::

**Sekwencyjnie spójne:**


**Sekwencyjnie niespójne:**

Z kolejności wykonania wynika:
`A write(0) -> A read(1)` oraz `B write(1) -> B read(0) `
Żeby wykonanie było poprawne musi zachodzić:
`B write(1) -> A write(0) -> B read(0)` oraz `A write(0) -> B write(1) -> A read(1)`

`A write(0) -> B read(0) -> B write(1) -> A read(1)`
lub
`B write(1) -> A read(1) -> A write(0) -> B read(0)`

Pomiędzy write(0) a read(0) nie może być write(1), bo się zepsuje read(0), ani read(1), ponieważ nie będzie ono działać.
Analogicznie dla write(1) i read(1)

Zatem jedyne możliwości to `write(1) read(1) write(0) read(0)`
oraz `write(0) read(0) write(1) read(1)`
Musi być jednocześnie zachowana kolejność funkcji w wątkach. Wątek pierszy wymaga najpierw operacji z zerami a nastepnie z jedynkami, a drugi odwrotnie. Sprzeczność.

:::success
## Zadanie 2
:::

## Rozwiązanie z hacka
Weźmy taki ciąg zdarzeń dla kolejek FIFO p i q:
A p.enq(x) #1
B q.enq(y) #2
A q.enq(x) #3
B p.enq(y) #4
A p.deq(y) #5
B q.deq(x) #6

Kolejka p potrzebuje do sekwencyjnej spójności wykonania komend w kolejności 4-1-3, kolejka q potrzebuje 3-2-6. Obie kolejki są sekwencyjnie spójne przy indywidualnym rozważeniu. Aby zachować sekwencyjną spójność całości pottrzebujemy jeszcze zachować kolejności 1-3-5 oraz 2-4-6.

Zachowanie wszystkich wymogów 4-1-3, 3-2-6, 1-3-5 i 2-4-6 prowadzi do sprzeczności np. wymusza kolejność 4-3-2-4

:::success
## Zadanie 3
:::

Gdy oba wskaźniki wskazują na to samo miejsce, i wywołujemy jednocześnie enqueue/dequeue to w
:::success
## Zadanie 4
:::

Zał. że wątek A szedł do sekcji krytycznej:
`write_A(flag[A] = true) -> write_A(victim = A) -> read_A(flag[B] == false || victim == B)`

Żeby B wszedł musiałoby zachodzić:
`write_B(flag[B] = true) -> write_B(victim = B) -> read_B(flag[A] == false || victim == A)`

Jako, że A jest w sekcji krytycznej to `flag[A] == true` oraz `victim == B` ponieważ B ustawił na siebie zmienną victim.

W modelu procesora słabszym niż sekwencyjna spójność może się okazać, że procesor zamieni kolejność operacji w celu optymalizacji (domyślnie `flag[] = false`):

`read_A(flag[B] == false) -> read_B(flag[A] == false) -> write_A(flag[A] = true) -> write_B(flag[B] = true)`

Zatem oba wątki wejdą do sekcji krytycznej

## Zadanie 5

:::success
## Zadanie 6
:::

class IQueue<T> {
    AtomicInteger head = new AtomicInteger(0);
    AtomicInteger tail = new AtomicInteger(0);
    T[] items = (T[]) new Object[Integer.MAX_VALUE];
    public void enq(T x) {
        int slot;
        do {
            slot = tail.get();
        } while (!tail.compareAndSet(slot, slot+1));
        items[slot] = x;
    }
    public T deq() throws EmptyException {
        T value;
        int slot;
        do {
            slot = head.get();
            value = items[slot];
            if (value == null)
                throw new EmptyException();
        } while (!head.compareAndSet(slot, slot+1));
        return value;
    }
}

**Rozwiązanie 1**
Problem - w procedurze enq() operacje tail.compareAndSet i items[slot] = x nie są wykonane atomowo. Nieformalnie - może to doprowadzić do sytuacji, gdy wątek zatrzyma się pomiędzy tymi instrukcjami, czyli - zarezerwował już miejsce, ale nic do niego nie wstawił. Jeśli teraz inny wątek wykona enq(), a potem deq(), to zwróci EmptyException, mimo że kolejka nie jest pusta. Formalnie:

 A: ---<A.enq(x)................>---
 B: -----<B.enq(y)>---<B.deq()>-----

1. A.enq(x)
2. B.enq(y)
3. B: void
4. B.deq()
5. B: EmptyException
6. A: void()

Taka historia nie jest linearyzowalna - B.deq() wykonuje się po operacji B.enq(y)(czyli mamy gwarancję, że w FIFO znajduje jakiś element), a mimo to dostajemy EmptyException. Jest to niezgodne z sekwencyjną specyfikacją FIFO.

**Rozwiązanie 2**
Aby pokazać, że obiekt IQueue nie jest poprawnym obiektem współbieżnym, wystarczy wskazać nielinearyzowalną historię wykonania.

Rozpatrzmy trzy wątki: A, B, C, oraz oznaczmy współdzieloną instancję klasy IQueue przez q.
Przyjrzyjmy się następującej historii wykonania.

    A q.enq(0) (wywłaszczony po pętli while)
    B q.enq(1)
    B q:void
    C q.deq()  (czyta ze slotu ustalonego przez A)
    C q:EmptyException
    A q:void

Powyższej historii nie da się zlinearyzować ponieważ B.enq poprzedza C.deq, więc każda sekwencyjna historia nie spełni sekwencyjnej specyfikacji.

:::success
## Zadanie 7
:::

public class HWQueue<T> {
    AtomicReference<T>[] items;
    AtomicInteger tail;
    static final int CAPACITY = Integer.MAX_VALUE;
    public HWQueue() {
        items = (AtomicReference<T>[]) Array.newInstance(AtomicReference.class,
        CAPACITY);
        for (int i = 0; i < items.length; i++) {
            items[i] = new AtomicReference<T>(null);
        }
        tail = new AtomicInteger(0);
    }
    public void enq(T x) {
        int i = tail.getAndIncrement();
        items[i].set(x);
    }
    public T deq() {
        while (true) {
            int range = tail.get();
            for (int i = 0; i < range; i++) {
                T value = items[i].getAndSet(null);
                if (value != null) {
                    return value;
                }
            }
        }
    }
}

## Rozwiązanie 1

### a Pierwsza instrukcja (pomarańczowa strzałka)

W momencie wystąpienia punktu linearyzacji dla wątku B zwiększamy zakres sprawdzanych indexów. Następnie dla nowego indexu odczytujemy wartość inną niż null. Zatem wcześniej odczytamy wartość z wątku B, mimo że punkt linearyzacji dla wątku A zdarzył się wcześniej.
### b Druga instrukcja (zielona strzałka)

Wątek B zapisał wartość do pamięci wcześniej niż wątek A, ale wykorzystał do tej operacji większy index. W konsekwencji wątek C wcześniej odczyta wartość z wątku A mimo że punkt linearyzacji wypadł wcześniej.

### Czy z powyższych punktów wynika, że enq() nie jest linearyzowalna?
Nie. Punktem linearyzacji nie musi być pojedyncza instrukcja.

## Rozwiązanie 2
a)

A enq(0)
B enq(1)
B deq(1)

b)
Jeśli drugi punkt będzie punktem linearyzacji to otrzymamy kolejność:

B enq(1)
A enq(0)
B deq(0)

Co jest sprzeczne z oczekiwanym działaniem kolejki.

**Czy z powyższych punktów wynika, że enq() nie jest linearyzowalna?**

Nie możemy:

## Zadanie 8