# Ćwiczenia 14, grupa śr. 16-18, 1 lutego 2023

###### tags: `PRW22` `ć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!**

:::info
Oprócz zadań z dzisiejszej listy, do zadeklarowania pozostały jeszcze **zadania 5 -- 7** z **listy 13**. Zadania należy zadeklarować w formularzu z poprzedniego tygodnia:
[https://hackmd.io/@iiuwr-kba/Hy_gTw0ij/edit](https://hackmd.io/@iiuwr-kba/Hy_gTw0ij/edit)
:::

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | X | X | | X | X | | X | | |
Marcin Dąbrowski | | | | | | | | | |
Jakub Gałecki | | | | | | | | | |
Kamila Goszcz | | | | | | | | | |
Wiktor Hamberger | X | | | | X | | | | |
Jan Jankowicz | X | | | X | X | | | | |
Mikołaj Jaszcza | | | | | | | | | |
Zuzanna Kania | | | | | | | | | |
Wiktoria Kuna | | | | | | | | | |
Patryk Mazur | X | | | | | | | | |
Hubert Obrzut | | | | | | | | | |
Magdalena Rzepka | | | | | | | | | |
Joanna Stachowicz | X | | X | | X | | | | |
Rafał Starypan | | | | | | | | | |
Maria Szlasa | | | | | | | | | |
Daniel Wiczołek | | | | | | | | | |
Adam Jarząbek | ==X== | | X | | X | | | | |
:::

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

## Zadanie 1
:::success
Autor: Adam Jarząbek
:::

Licznik współdzielony umożliwia wielu wątkom w wydajny sposób odczytywać wartość licznika oraz zwiększać lub zmniejszać jego wartość.
Licznik współdzielony wykorzystujący sieć zliczającą ogranicza walkę wątków o dostęp do współdzielonej wartości. Wartości w takim liczniku mogą nie być podawane w kolejności jak w liczbach naturalnych, ale możemy mieć pewność, że nie będzie duplikatów oraz że żadne wartości nie zostaną pominięte.

Własność krokowa oznacza, że na wyjściach liczników znajdzie się taka sama liczba wartości, a jeżeli na którymś wyjściu ta wartość jest większa niż na innych, to jest większa maksymalnie o 1 oraz poprzednie wejścia mają również taką liczbę wartości.

Dzięki własności krokowej mamy pewność, że żadne wartości nie zostaną pominięte.

Realizacja getAndIncrement polega na przejściu tokena przez sieć, oraz zwiększenie licznika, do którego się w ten sposób dotarło.

## Zadanie 2
:::success
Autor: Daniel Boguszewski
:::

Wykażemy przez indukcję, że jeśli Bitonic[k] posiada własność kroku, Bitonic[2k] również ją posiada.

Podstawowy przypadek: Bitonic[2] posiada własność kroku z definicji.
Kolejne wartości przerzucane są kolejno na oba wyjścia balansera.

Założenie indukcyjne: Bitonic[k] ma własność kroku.
Teza indukcyjna: Bitonic[2k] również.

Budowa 2k wejściowego balansera:
Składa się z dwóch balanserów k wyjściowych i 2k wyjściowego mergera.
Kolejne wartości przekazywane przez balansery wstawiane są na co drugie wejście mergera (pierwszy balanser zaczyna od wejścia nr 1, efektywnie zajmuje k wejść, a drugi pozostałe).

Korzystając z założenia o własności kroku dla balanserów k-wejściowych sprowadzamy zadanie do udowodnienia następującej tezy:

Przyjmujemy teraz kolejne założenie indukcyjne dla mergera analogiczne do balansera.
Jeśli merger k-wyjściowy otrzyma 2 wejściowe ciągi z własnością kroku (ciągi zajmują po k/2 kolejnych wejść, razem obejmąc całe wejście) to wynikiem będzie k-rzędowy ciąg z własnością kroku:
Przypadek podstawowy Merger[2] spełnia założenie z definicji (to po prostu Bitonic[2]).

Reszta dowodu opierać się będzie na następującej budowie Merger[2k]:
Niebieskie elementy to balansery.

W dowodzie skorzystamy z dwóch następujących lematów:

Lemat 1 - jeśli ciąg wyjściowy ma własność kroku, to dzieląc ten ciąg na rzędy parzyste (niżej będą to 2, 4, 6, 8) oraz nieparzyste (1, 3, 5, 7) otrzymamy dwa poprawne ciągi z własnością kroku.

Lemat 2 - 2 ciągi wejściowe o własności kroku można przekształcić w inne 2 ciągi wejściowe, które będą różniły się od siebie co najwyżej jednym elementem, tworząc je z ciągów parzystych i nieparzystych poszczególnych wejść:
Istotnie jeśli ciągi wejściowe $A(2n + a)$ i $B(2m + b)$ o odpowiednio $2n + a$ i $2m + b$ elementach (ich parzystość zależy od $a, b \in \{0, 1\}$) oraz własnością kroku podzieli się na ciągi składające się z rzędów parzystych i nieparzystych osobnych wejść (jak na rysunku wyżej), różnica wyniesie maksymalnie 1 element: $A'(n + m + b)$, $B'(n + m + a)$, ponieważ $$n + m \leq |A|, |B| \leq n + m + 1 \Leftrightarrow n + m + b, n + m + a \leq n + m + 1 \Leftrightarrow 0 \leq a, b \leq 1$$

Reszta dowodu to korzystanie z założeń i lematów:

## Zadanie 3
:::success
Autor: Joanna Stachowicz
:::

Wystarczy użyć licznika typu AtomicInteger z wbudowaną metodą getAndIncrement

public class Balance {
    AtomicInteger n;
    
    Balancer(t) {
        this.n = new AtomicInteger(0);
    }
    
    public int traverse() {
        return n.getAndIncrement() % 2;
    }
}

## Zadanie 4
:::success
Autor: Jan Jankowicz
:::
Za pomocą równoważników z jednym wejściem i dwoma wyjściami można utworzyć sieć zliczającą (a tym samym i współdzielony licznik) ustawiając je w strukturę drzewa.

Drzewo tworzone jest indukcyjnie.

Najprostsze takie drzewo to takie o k = 2 wyjściach. Jest to po prostu pojedynczy równoważnik.
Mając dwa identyczne drzewa o k wyjściach, możemy skonstruować drzewo z k' = 2k, ustawiając jako wejście nowy równoważnik i podpinając jego wyjścia do wejść dwóch drzew o k wyjściach. Trzeba jeszcze odpowiednio ustawić wyjścia poddrzew, aby nowo utworzone drzewo było drzewem zliczającym z zachowaną własnością kroku.

Dzięki zastosowaniu na wejściu równoważnika oba poddrzewa będą miały na swoich wyjściach identyczną liczbę tokenów lub pierwsze poddrzewo będzie miało ich o 1 więcej, a korzystając z założenia indukcyjnego, wiemy, że oba zbiory tokenów będą miały zachowaną własność kroku. Te obserwacje pozwalają nam na ustalenie odpowiedniej permutacji wyjść dla nowego drzewa. Dla wyjść obu poddrzew należy dokonać przeplotu. Ostatecznie na wyjściu całego nowego drzewa 2k na miejscu 0 powinniśmy otrzymać wyjście 0 pierwszego poddrzewa, na miejscu 1 - wyjście 0 drugiego poddrzewa, na miejscu 2 - wyjście 1 pierwszego poddrzewa, na miejscu 3 - wyjście 1 drugiego poddrzewa itd. (ogólnie: jeśli wyjście nowego drzewa ma numer parzysty n, to ma być na nim wyjście n/2 pierwszego poddrzewa, a jeśli ma numer nieparzysty n, to należy wziąć (n-1)/2 drugiego poddrzewa).

## Zadanie 5
:::success
Autor: Wiktor Hamberger
:::
Wiele obiektów współdzielonych ma tę właściwość, że większość wywołań metod zwraca informacje o stanie obiektu bez jego modyfikacji, a inne tylko modyfikują obiekt. Wywołania metod pierwszego rodzaju nazywamy czytelnikami, a wywołania metod drugiego rodzaju pisarzami. Czytelnicy nie muszą się ze sobą synchronizować; jest całkowicie bezpieczne, by miały one współbieżny dostęp do obiektu. Z drugiej strony, pisarze muszą zablokować czytelników, jak również jak i innych pisarzy. Readers-writers lock pozwala wielu czytelnikom lub jednemu pisarzowi na równoczesne wejście do sekcji krytycznej. Używamy następującego interfejsu:

public interface ReadWriteLock {
Lock readLock();
Lock writeLock();
}

Ten interfejs wystawia dwa obiekty blokad: blokadę odczytu i blokadę zapisu. Spełniają one następujące właściwości bezpieczeństwa:
- Żaden wątek nie może zająć blokady zapisu, podczas gdy dowolny wątek posiada blokadę zapisu lub blokadę odczytu.
- Żaden wątek nie może zająć blokady odczytu, gdy dowolny wątek posiada blokadę zapisu.
Oczywiście, wiele wątków może trzymać blokadę odczytu w tym samym czasie.

## Zadanie 6
:::danger
Autor:
:::

## Zadanie 7
:::success
Autor: Daniel Boguszewski
:::

public class RedBlueLock {
    enum Color {
        RED, BLUE;
        static Color otherThan(Color color) {
            return (color == RED) ? BLUE : RED;
        }
    }

    private int count = 0;
    private long reservationTime;
    private final long reservationDuration, waitingDuration;
    private boolean openedForRed = false, openedForBlue = false;
    private Color colorInside;

    public RedBlueLock() {
        this.waitingDuration = 0;
        this.reservationDuration = 0;
        openFor(Color.RED);
    }

    public RedBlueLock(long reservationDuration, long waitingDuration) {
        this.waitingDuration = waitingDuration;
        this.reservationDuration = reservationDuration;
        openFor(Color.RED);
    }

    public synchronized void lock(Color myColor) throws InterruptedException {
        Color otherColor = Color.otherThan(myColor);
        while (!isOpenedFor(myColor)) {
            if (isReservationOverFor(otherColor)) {
                closeFor(otherColor);
                if (count == 0) {
                    openFor(myColor);
                    break;
                }
            }
            wait(waitingDuration);
        }
        count++;
    }

    public synchronized void unlock(Color myColor) {
        if (colorInside == myColor && count > 0) {
            count--;
            if (count == 0 && !isOpenedFor(myColor))
                openFor(Color.otherThan(myColor));
        }
    }

    private void closeFor(Color color) {
        if (color == Color.RED) openedForRed = false;
        else openedForBlue = false;
    }

    private void openFor(Color color) {
        colorInside = color;
        if (color == Color.RED) openedForRed = true;
        else openedForBlue = true;
        reservationTime = System.currentTimeMillis();
    }

    private boolean isOpenedFor(Color color) {
        return (color == Color.RED) ? openedForRed : openedForBlue;
    }

    private boolean isReservationOverFor(Color color) {
        return colorInside == color && System.currentTimeMillis() - reservationTime > reservationDuration;
    }
}

## Zadanie 8
:::danger
Autor:
:::

## Zadanie 9
:::danger
Autor:
:::