---
# System prepended metadata

title: 'Ćwiczenia 12, grupa cz. 16-18, 11 stycznia 2024'
tags: [pwit, ćwiczenia, PRW23]

---

# Ćwiczenia 12, grupa cz. 16-18, 11 stycznia 2024

###### tags: `PRW23` `ć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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk           |       |  X   |  X   |     |     |     |     |  
Paweł Borek              |       |     |     |     |     |     |     |
Arti Brzozowski          |       |     |     |     |     |     |     |
Mateusz Golisz           |       |  x   |  x   |     |  x   |  x   |  x   |
Kacper Jóźwiak           |       |  x  |     |     |     |     |     |  
Julia Konefał            |       |     |     |     |     |     |     |  
Adam Korta               |       |  x   |  x   |     |     |     |     |  
Jakub Mikołajczyk        |  X   |  X  |  X  |     |  X  |  X  |  X  |  
Bartosz Morasz           |       |  x  |  x  |     |  x  |  x  |  x  |  
Andrzej Morawski         |       |  x  |  x  |     |  x  |  x  |     |  
Aleksandra Nicpoń        |       |  x   |     |     |     |     |     |  
Mateusz Reis             |       |  x |  x  |     |  x  |  x  |  x  |
Tomasz Stachurski        |       |  X  |  X  |     |  X  |  X  |  X  | 
Marcel Szelwiga          |       |  X   |  X   |     |     |     |     |  
Volha Tsekalo            |       |     |     |     |     |     |     |  
Martyna Wybraniec        |       |     |     |     |     |     |     |  
Denys Zinoviev           |       |     |     |     |     |     |     |  
Dominik Olejarz          |       |    x |   x  |     |     |     |     |  
:::






:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::



## Zadanie 1
:::success
Autor: Andrzej Morawski	
:::

```java=
public class LockFreeQueue<T> {
    AtomicReference<Node> head, tail;
    public LockFreeQueue() {
	    Node node = new Node(null);
	    head = new AtomicReference(node);
	    tail = new AtomicReference(node);
	}
    
	public class Node {
	    public T value;
	    public AtomicReference<Node> next;
	    public Node(T value) {
		    this.value = value;
		    next = new AtomicReference<Node>(null);
		}
	}
	
    public void enq(T value) {
        Node node = new Node(value);
        while (true) {
            Node last = tail.get();
            Node next = last.next.get();
            if (last == tail.get()) {
                if (next == null) {
                    if (last.next.compareAndSet(next, node)) {
                        tail.compareAndSet(last, node);
                        return;
                    }
                } else {
                    tail.compareAndSet(last, next);
                }
            }
        }
	}
    
	public T deq() throws EmptyException {
        while (true) {
            Node first = head.get();
            Node last = tail.get();
            Node next = first.next.get();
            if (first == head.get()) {
                if (first == last) {
                    if (next == null) {
                        throw new EmptyException();
                    }
                    tail.compareAndSet(last, next);
                } else {
                    T value = next.value;
                    if (head.compareAndSet(first, next)) {
                        return value;
                    }
                    
                }
            }
        }
	}
}
```

### 1.

Z założenia wiemy, że wywołanie metody ```deq()``` kończy się sukcesem. Możemy wybrać instrukcje odczytania wartości z węzła jako punkt linearyzacji, ponieważ będzie to wartość zwrócona przez funkcję.

### 2.

Wykonując metodę enq(x) mamy 2 etapy wpinania nowego węzła do listy:

* Logiczne &rarr; przepięcie wskaźnika ```last.next.compareAndSet(next, node);```
* Fizyczne &rarr; przepięcie wskaźnika ```tail.compareAndSet(last, next/node);```

Jako punkt lienaryzacji możemy wybrać dowolne wykonanie instrukcji ```compareAndSet``` ponieważ jest to instrukcja, która daje efekt w wykonywanej metodzie. Jeżeli węzeł zostanie dodany logicznie na koniec kolejki wówczas zależy nam na zaktualizowaniu pola tail. Niezależnie od tego, które wywołanie metody ```compareAndSet``` weźmiemy nowy węzeł zostanie wpięty jako nowy ogon, albo jej wykonanie przybliży nas do tego, żeby wpiąć ten węzeł na koniec kolejki. Zatem metoda będzie miała widoczny efekt.

## Zadanie 2
:::success
Autor: Dominik Olejarz	
:::
![image](https://hackmd.io/_uploads/ryBAvFT_6.png)
Problem ABA – rodzaj błędu w synchronizacji procesów wielowątkowych, polegający na tym, że w 
przypadku dwukrotnego odczytu lokacji pamięci, gdy odczytana wartość jest taka sama w obu odczytach, 
to „taka sama wartość” jest interpretowana jako „nic się nie zmieniło”. Jednak inny wątek mógł, między 
odczytami w pierwszym wątku, zmienić wartość tej lokacji, wykonać jakieś zadania, a następnie ponownie zmienić
 wartość lokacji do wartości równej pierwotnej, niejako oszukując pierwszy wątek, że „nic się nie zmieniło”, mimo
 że drugi wątek wykonał pracę, która narusza to założenie.

Przyklad 
-Wątek A próbuje zmienić head z a na b 
-w tym czasie wątek B wyjmuje z kolejki b oraz a.
-Jeszcze inny wątek ponownie przywraca w to miejsce a
-Teraz wątek A kończy działanie, za pomocą CompareAndSet() zmienia poprzednika, tak, że node usunięty przez niego wskazuje na b zamiast na c 
-Tutaj się wszystko załamuje, bo b jest usunięte

Do naprawy tego błędu używamy AtomicStampedReference<T>.
Klasa ta przechowuje referencję do następnego obiektu i stamp, który służy do zidentyfikowania czy nastąpił problem opisany wyżej.
CAS jednocześnie sprawdza referencję i stamp, a gdy używamy CAS, zwiększamy stamp.
![image](https://hackmd.io/_uploads/Sy8Yctp_6.png)

## Zadanie 3
:::success
Autor: Dominik Baziuk	
:::
:::info
Na przykładzie SynchronousQueue wyjaśnij, czym są synchroniczne struktury danych i do czego mogą służyć?
:::
Synchroniczne struktury danych pomagają rozwiązać problem producent-konsument.

![image](https://hackmd.io/_uploads/rybvObIdT.png)

:::info
Czym jest spotkanie (ang. rendezvous)?
:::

Producenci i konsumenci spotykają się ze sobą: Producent, który umieszcza artykuł w kolejce, blokuje się do czasu usunięcia go przez konsumentem i odwrotnie.

## Zadanie 4
:::success
Autor: Tomasz Stachurski	
:::

Dualną wersje kolejki wprowadzamy, aby ograniczyć koszt synchronizacji. Poprzednio mieliśmy wielu producentów i wielu konsumentów, ale tylko jeden z nich może operować na kolejce i przy każdej wymianie (producent <-> konsument) budziły się wszystkie wątki (kwadratowo nadmiarowa ilość pobudek)...


IDEA kolejki:
Wyróżniamy 3 stany kolejki:
* pusta
* zawiera tylko rezerwacje konsumentów
* zawiera tylko elementy producentów

Jeśli kolejka jest pusta i zaczyna producent, to dodajemy. Jak przyjdzie konsument, to będzie ściągał kolejno dodane elementy, aż do pustej kolejki

Jeśli kolejka jest pusta i zaczyna producent, to odwrotnie.

![image](https://hackmd.io/_uploads/rkMvTPKu6.png)

Na początku sprawdzamy, czy kolejka jest pusta albo zawiera elementy producentów. 

Jeśli ma rezerwacje (warunek else), to ściągamy pierwszą z nich [wiersze 24-32]. Następnie sprawdza, czy wszystkie wartości są poprawne [wiersze 25-27]. Jeśli tak to próbuje wypełnić rezerwację i przestawia głowę na kolejny element w kolejce. W przypadku gdy wymiana się nie udała (`success` = false), to ktoś nas ubiegł i musimy ponownić działanie `enq()`, wpp. kończymy działanie.

Jeśli kolejka jest pusta albo mamy w niej elementy od producentów zachowujemy się tak jakbyśmy pracowali na zwykłej kolejce z tą różnicą, że każdy element wiruje nad samym sobą w oczekiwaniu na konsumenta. Jak w końcu zostanie zabrany przez konsumenta, próbuje po sobie posprzątać czyniąc się strażnikiem `head` [linia 29-30], wyręczając konsumenta.

## Zadanie 5
:::success
Autor: Bartosz Morasz	
:::

![image](https://hackmd.io/_uploads/ryrtuKpua.png)
![image](https://hackmd.io/_uploads/SkXeFFTOa.png)
![image](https://hackmd.io/_uploads/rJd5uF6uT.png)

Problemem w algorytmie Boba pojawia się gdy jeden wątek wykonuje pop, a drugi push. Możemy mieć sytuację w której:
- Najpierw pop wyciągnie i = x
- Push wyciągnie po nim i = x - 1
- Push wykona resztę swoich operacji, podmieniając element, który nie powinien być nadpisany
- Pop zwróci wartość powyżej

Moglibyśmy to rozwiązać dodając analogicznego while do push
    
## Zadanie 6
:::success
Autor: Andrzej Morawski	
:::

![Zrzut ekranu 2024-01-11 162351](https://hackmd.io/_uploads/Bkb7OFp_a.png)
    
```java=
public interface Rooms {
    public interface Handler {
        void onEmpty();
    }
    void enter(int i);
    boolean exit();
    public void setExitHandler(int i, Rooms.Handler h) ;
}

public class Stack<T> {
    private AtomicInteger top;
    private T[] items;
    private Rooms rooms; // new
    public Stack(int capacity) {
        top = new AtomicInteger();
        items = (T[]) new Object[capacity];
        rooms = new Rooms(2);
    }
    public void push(T x) throws FullException {
        rooms.enter(0) // new
        int i = top.getAndIncrement();
        if (i >= items.length) { // stack is full
            top.getAndDecrement(); // restore state
            throw new FullException();
        }
        items[i] = x;
        rooms.exit() // new
    }
    public T pop() throws EmptyException {
        rooms.enter(1) // new
        int i = top.getAndDecrement() - 1;
        if (i < 0) { // stack is empty
            top.getAndIncrement(); // restore state
            throw new EmptyException();
        }
        T result = items[i]
        rooms.exit()  // new
        return result;       
    }
}
```

### Czemu ta implementacja nie działa?


Analogicznie jak w zadaniu 5 może dochodzić do nadpisywania wartości w komórkach.

Rozpatrzmy następujące wykonanie programu dla wątków A,B,C:

```
A:push(x)
B:push(y)
C:pop()
```

Wątek A:
1. int i = top.getAndIncrement(); &rarr; i = 0, top = 1;
2. Wątek A idzie spać;

Wątek C:
1. int i = top.getAndDecrement() - 1; &rarr; i = 1 - 1 = 0, top = 0;
2. Wątek C idzie spać;

                  
Wątek B:
1. int i = top.getAndIncrement(); &rarr; i = 0; top = 1;
2. Wątek B przechodzi przez instrukcję warunkową 
3. Wątek B wpisuje swoją wartość do tablicy
4. Budzi się wątek A
5. Wątek A przechodzi przez instrukcję warunkową
6. Wątek A nadpisuje poprzednią wartość w tablicy
7. Budzi się wątek C
8. Wątek C zdejmuje nadpisaną wartość.
9. W tablicy nie została żadna wartość mimo tego, że wykonaliśmy 2 instrukcje push i jedną pop.




## Zadanie 7
:::success
Autor: Mateusz Reis	
:::

![image](https://hackmd.io/_uploads/rylI2FaOa.png)
![image](https://hackmd.io/_uploads/BydU2FpOa.png)

                  
```java=

public interface Rooms {
    public interface Handler {
        void onEmpty();
    }
    void enter(int i);
    boolean exit();
    public void setExitHandler(int i, Rooms.Handler h) ;
}

public class Stack<T> {
    private AtomicInteger top;
    private T[] items;
    private Rooms rooms;
    public Stack(int capacity) {
        top = new AtomicInteger();
        items = (T[]) new Object[capacity];
        rooms = new Rooms(2);
        rooms.setExitHandler(0, this::resize);
    }
    public void push(T x){
        rooms.enter(0) // new
        int i = top.getAndIncrement();
        if (i >= items.length) { // stack is full
            top.getAndDecrement(); // restore state
            rooms.exit();
            this.push(x);
        }
        items[i] = x;
        rooms.exit() // new
    }
    public T pop() throws EmptyException {
        rooms.enter(1) // new
        int i = top.getAndDecrement() - 1;
        if (i < 0) { // stack is empty
            top.getAndIncrement(); // restore state
            throw new EmptyException();
        }
        T result = items[i]
        rooms.exit()  // new
        return result;
        
    }
    private void resize() {
        T[] newItems = (T[]) new Object[items.length * 2];
        System.arraycopy(items, 0, newItems, 0, items.length);
        items = newItems;
    }
}
```