---
# System prepended metadata

title: Współbieżne 5

---

# Współbieżne 5

:::success
## Zadanie 1
:::

![](https://i.imgur.com/Ld2IOSW.png)
**Sekwencyjnie spójne:**
![](https://i.imgur.com/Vo5GppV.png)
![](https://i.imgur.com/2CDhqXT.png)

![](https://i.imgur.com/JzSgTdy.png)

**Sekwencyjnie niespójne:**
![](https://i.imgur.com/dn6gS37.png)
![](https://i.imgur.com/DQQkXAp.png)

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 
:::
![](https://i.imgur.com/rXCFopT.png)


## 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

![](https://i.imgur.com/6mK3YV9.png)
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
:::
![](https://i.imgur.com/jx5DeRH.png)

![](https://i.imgur.com/646Ovq4.png)
Gdy oba wskaźniki wskazują na to samo miejsce, i wywołujemy jednocześnie enqueue/dequeue to w 
:::success
## Zadanie 4
:::
![](https://i.imgur.com/xoJY7wH.png)
![](https://i.imgur.com/UnlmeH6.png)

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
![](https://i.imgur.com/3eJ1fIg.png)
![](https://i.imgur.com/XfDEJoD.png)

:::success
## Zadanie 6
:::
![](https://i.imgur.com/djDl1aX.png)
```java=
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
:::
![](https://i.imgur.com/Wo9rmFO.png)
![](https://i.imgur.com/n263XRE.png)
```java=
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)
![](https://media.discordapp.net/attachments/895259310702088223/910269439616909362/unknown.png)

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)
![](https://media.discordapp.net/attachments/895259310702088223/910269890009636874/unknown.png)

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.
![](https://images-ext-2.discordapp.net/external/_cH3ky6nTMmQa_o1vN6rnqWt34UkDEyXJAzAdTW68EA/https/media.discordapp.net/attachments/891385625360629812/910274645683499018/unknown.png)

## Rozwiązanie 2
a)
![](https://i.imgur.com/ySKLPhm.png)
```
A enq(0)
B enq(1)
B deq(1)
```

b)
![](https://i.imgur.com/pBT6Zll.png)
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:
![](https://i.imgur.com/TSu8CnA.png)

## Zadanie 8
![](https://i.imgur.com/Rsepsxv.png)
