# Ćwiczenia 4, grupa śr. 10-12, 8 listopada 2023

###### 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 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | |
Konrad Kowalczyk | X | X | X | | X | X | | X |
Jakub Krzyżowski | X | X | | X | | X | | |
Łukasz Magnuszewski | | | | | | | | |
Marcin Majchrzyk | X | X | | | X | X | | X |
Jan Marek | X | | | | X | X | X | X |
Marcin Mierzejewski | | | | | | | | |
Juan Jose Nieto Ruiz | | | | | | | | |
Dominik Olejarz | | | | | | | | |
Konrad Oleksy | | | | | | | | |
Javier Rábago Montero | X | X | X | X | X | X | X | X |
Michał Mękarski | X | X | | | X | X | | X |
:::

Tutaj można zadeklarować zaległe zadanie 8 z listy 3:

:::danger
| | 3.8 |
| ----------------------:| ----- |
| Marcin Majchrzyk | X |
| Javier Rábago Montero | X |
:::

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

## Zadanie 1
:::success
Autor:Jan Marek
:::

Blokada Filter tworzy n-1 poziomów, przez które musi przejść wątek, zanim będzie mógł wejść do CS.
Poziomy zapewniają poniższe własności:

1) co najmniej jeden wątek próbujący wejść na poziom `l` odnosi sukces
2) jeśli więcej niż jeden wątek próbuje wejść na poziom `l`, to przynajmniej jeden z nich zostaje zablokowany (tzn. pozostaje na tym samym poziomie i czeka)

W blokadzie Petersona informacje o tym, czy wątek próbuje wejść do CS były zapisywane w 2-elementowej boolowskiej tablicy `flag`. W blokadzie Filter zostało to uogólnione za pomocą n-elementowej tablicy `level[]` typu int, gdzie wartość `level[A]` oznacza najwyższy poziom, na który próbuje wejść wątek A. Każdy wątek musi przejść przez n-1 poziomów, aby dostać się do swojej CS. Każdy poziom l ma odrębne pole `victim[l]`, które służy do "odfiltrowania" jednego wątku, aby wykluczyć go z następnego poziomu.

Lemat.
Dla (0 <= i <= n-1) jest co najwyżej n-i wątków na poziomie i.

Dowód. indukcja po i (po poziomach)

1) i = 0
Na poziomie 0 jest n - 0 = n wątków

2)
Z założenia indukcyjnego mamy, że przynajmniej n-i+1 wątków znajduje się na poziomie i-1.

Załóżmy nie wprost, że n-i+1 wątków jest na poziomie i.

Niech ostatnim wątkiem na poziomie i, który wykonał zapis w polu victim[i] będzie wątek A.
Ponieważ A jest ostatni, to dla każdego innego wątku B na poziomie i mamy:

`write_B(victim[i]) -> write_A(victim[i])`

Z kodu mamy, że wątek B zapisuje level[B] przed zapisaniem victim[i], więc:

write_B(level[B]=i) ->
write_B(victim[i]) ->
write_A(victim[i])

Dodatkowo widzimy, że wątek A odczytuje level[B] po zapisaniu victim[j], więc:

write_B(level[B]=i) ->
write_B(victim[i]) ->
write_A(victim[i]) ->
read_A(level[B])

Ponieważ wątek B znajduje się na poziomie i, to za każdym razem, gdy wątek A odczytuje wartość pola level[B], otrzymuje wartość >= i. Z tego wynika, że wątek A nie mógł opuścić swojej pętli oczekiwania, co jest sprzeczne z naszym założeniem.

Wejście do CS jest równoznaczne z wejściem na poziom n-1 oraz na poziomie n-i znajduje się co najwyżej i wątków.

## Zadanie 2
:::danger
Autor:Michał Mękarski
:::

## Zadanie 3
:::success
Autor:Konrad Kowalczyk
:::

<b>Własność r-ograniczonego czekania:</b>
Jeżeli D_A^k → D_B^j,
to wtedy CS_A^k → CS_B^j+r
Czyli jeżeli k-ta sekcja wejściowa wątku A została wykonana przed j-tą sekcją wejściową wątku B, to k-ta sekcja krytyczna wątku A musi wykonać się przed j+r-tą sekcją krytyczną wątku B.

<b>Własność niezagłodzenia:</b>
Jeżeli jakiś wątek wywołuje `lock()` to wykona w końcu wykona swoją sekcję krytyczną.

<br/>

Weźmy n (n >= 3) wątków. Załóżmy, że wątek `i` wszedł na poziom 1 jako ostatni. Wtedy `victim[1] = i`. Weźmy teraz wątki `j` oraz `k`. Wątki `j` oraz `k` przejdą na wyższe poziomy oraz wykonają swoje sekcje krytyczne, a wątek `i` będzie musiał na nie oczekiwać.

Gdy te wątki wrócą z powrotem na początek algorytmu, to ustawią (bez utraty ogólności) `victim[1] = j` oraz potem `victim[1] = k`, przez co wątek `i` nie będzie musiał już dłużej czekać z wejściem na kolejny poziom. Jednak jeżeli wątek `i` nie obudzi się w porę, to wątek `j` będzie mógł przejść przez następne poziomy (ponieważ `victim[1] = k` nadpisał `victim[1] = j`) oraz wrócić i ponownie ustawić `victim[1] = j`, przez co tym razem wątek `k` będzie mógł przejść przez następne poziomy.

Dopóki wątek `i` się nie wybudzi, wątki `j` i `k` będą mogły wykonywać się w nieskończoność, przez co nie jesteśmy w stanie ustalić takiej stałej r, żeby algorytm ten spełniał warunek r-ograniczonego czekania. Jednakże nie przeczy to warunkowi niezagłodzenia, ponieważ gdy tylko wątek `i` się wybudzi, będzie mógł natychmiast przejść na następny poziom (ponieważ `victim[1] != i`).

## Zadanie 4
:::success
Autor:Jakub Krzyżowski
:::

**1.**
Załóżmy, że $D_A \rightarrow D_B$ i $CS_B \rightarrow CS_A$
W takim razie:
$Write_A(flag[A] = true) \rightarrow Write_A(victim = A) \rightarrow$
$\rightarrow Write_B(flag[B] = true) \rightarrow Write_B(victim = B)$
Skoro B weszło do CS pierwsze, to musiało zaraz po zapisie siebie do victim musiało odczytać, że $victim == A$, co jest niemożliwe.

**2.**
Przy takiej definicji D może zajść:
$D_A \rightarrow D_B \rightarrow Write_B(victim=B) \rightarrow Write_A(victim=A)$,
a więc B może bez przeszkód wejść do CS przed A pomimo, że $D_A \rightarrow D_B$

**3.**
1. Jedynie odczytując wartości z komórek pamięci wątki w żaden sposób nie sygnalizują chęci wejścia do sekcji krytycznej, w związku z czym taki algorytm nie byłby w stanie rozróżnić sytuacji $D_A \rightarrow D_B$ od $D_B \rightarrow D_A$.
2. Załóżmy, że istnieje taki algorytm. Rozpatrzmy przypadki:
$D_A \rightarrow D_B$ w takim razie stan programu ``var_A = x; var_B = y``.
Na podstawie tego stanu $CS_A \rightarrow CS_B$
Drugi przypadek: $D_B \rightarrow D_A$.
W tym przypadku stan programu wygląda identycznie jak w poprzednim, a jednak $CS_B \rightarrow CS_A$, a więc na podstawie tych samych danych algorytm podjął inną decyzję, co jest niemożliwe.
3. Załóżmy, że taki algorytm istnieje.
W takim wypadku sytuacja $D_A \rightarrow D_B$ jest nieodróżnialna od sytuacji gdy tylko wątek B chce wejść do CS, bo w $D_B$ zostanie nadpisana informacja o tym, że wątek A chce wejść do sekcji krytycznej. W takim razie nie ma możliwości, że $CS_A \rightarrow CS_B$.

## Zadanie 5
:::success
Autor:Javier Rábago Montero
:::

In the first one B can´t read 1 because it could only read 1 or 2
In the second one, element y is dequeued 2 times.

## Zadanie 6
:::danger
Autor:Michał Mękarski
:::

## Zadanie 7
:::success
Autor:Javier Rábago Montero
:::

{ int head = 0, tail = 0; 
items = (T[]) new Object[capacity]; 
public void enq(Item x) { 
if (tail-head == capacity) throw 
new FullException(); 
items[tail % capacity] = x; tail++; 
} 
public Item deq() { 
if (tail == head) throw 
new EmptyException(); 
Item item = items[head % capacity]; head++; 
return item;
}}

There are 3 posibilities of a concurrent event, first one, the queue has only one item, and both threads try to queue and dequeue at the same time. There wouldn't be any problem.
The other 2 could have a conflict, these cases are full and empty queue. The linearization point would be tail++ and head++, which is when each function change the queue, but we will only need sequential consistency from each individual thread, as there are two different memory compartments (head and tail).

## Zadanie 8
:::success
Autor:Marcin Majchrzyk
:::

public void lock() {
    flag[i] = true;
    victim = i;
    while (flag[j] && victim == i) {};
}

public void unlock() {
    flag[i] = false;
}

Kolejność wykonania, aby wątek A wszedł do sekcji krytycznej:
$write_A(flag[A]=true) \rightarrow write_A(victim=A) \rightarrow read_A(flag[B] == false \lor victim == B)$

Kolejność wykonania, aby wątek B wszedł do sekcji krytycznej:
$write_B(flag[B]=true) \rightarrow write_B(victim=B) \rightarrow read_B(flag[A] == false \lor victim == A)$

Jeżeli kod będzie wykonywany na procesorze o modelu pamięci słabszym niż sekwencyja spójność może dojść do sytuacji:
$read_A(falag[B] == false) \rightarrow read_B(flag[A] == false) \rightarrow
write_A(flag[A] = true) \rightarrow write_B(flag[B] = true)$
W takiej sytuacji oba wątki wejdą do sekcji krytycznej.

## Zadanie 8 Lista 3
:::success
Autor:Marcin Majchrzyk
:::

class FindLongestSubsequence implements Runnable {
    int[] arr;
    int left, right;

    int longestLeft, longestRight, number;
    int leftNumber, leftLen;
    int rightNumber, rightLen;

    FindLongestSubsequence(int[] arr, int left, int right) {
        this.arr = arr;
        this.left = left;
        this.right = right;
    }

    @Override
    public void run() {
        if (left == right) {
            longestLeft = longestRight = left;
            number = arr[left];

            leftLen = 1;
            leftNumber = arr[left];

            rightLen = 1;
            rightNumber = arr[left];
        } else {
            int m = (left + right) / 2;

            FindLongestSubsequence c1 = new FindLongestSubsequence(arr, left, m);
            FindLongestSubsequence c2 = new FindLongestSubsequence(arr, m+1, right);

            Thread t = new Thread(c1);
            t.start();

            c2.run();

            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            //L-L      L-R  R-L      R-R
            // <-------->    <-------->
            //     c1            c2

            // check if left-left connects to right-left
            this.leftNumber = c1.leftNumber;
            if (c1.left + c1.leftLen == c2.left && c1.leftNumber == c2.leftNumber) {
                this.leftLen = c1.leftLen + c2.leftLen;
            } else {
                this.leftLen = c1.leftLen;
            }

            // check if right-right connects to left-right
            this.rightNumber = c2.rightNumber;
            if (c2.right - c2.rightLen == c1.right && c1.rightNumber == c2.rightNumber) {
                this.rightLen = c1.rightLen + c2.rightLen;
            } else {
                this.rightLen = c2.rightLen;
            }

            // find new longest
            if (c1.longestRight - c1.longestLeft < c2.longestRight - c2.longestLeft) {
                this.number = c2.number;
                this.longestLeft = c2.longestLeft;
                this.longestRight = c2.longestRight;
            } else {
                this.number = c1.number;
                this.longestLeft = c1.longestLeft;
                this.longestRight = c1.longestRight;
            }

            // check if left-right has same number as right-left and check if its new longest
            if (c1.rightNumber == c2.leftNumber && c1.rightLen + c2.leftLen > this.longestRight - this.longestLeft + 1) {
                this.number = c1.rightNumber;
                this.longestLeft = c1.right - (c1.rightLen - 1);
                this.longestRight = c2.left + (c2.leftLen - 1);
            }

        }
    }
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,2,1,2,1,2,2,2};

        FindLongestSubsequence c = new FindLongestSubsequence(arr, 0, arr.length - 1);
        c.run();

        for (int i : arr) System.out.printf("%d ", i);
        System.out.print("\n");

        System.out.printf("Longest subsequence size: %d\n", c.longestRight - c.longestLeft + 1);
        System.out.printf("Subsequence number: %d\n", c.number);
    }
}