# Ćwiczenia 3, grupa śr. 14-16, 23 października 2024

###### tags: `PRW24` `ć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 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Michał Chawar | X | X | X | X | X | X | X | | |
Fabian Grodek | | | | | | | | | |
Maria Hreniak | X | X |==X==| X | X | X | X | | |
Aleksandra Jędrzejak | X | | X | X | X | X | | | |
Jan Kamyk | X | X | X | X | X | | | | |
Viktoriia Kashpruk | X | ==X== | X |X | X | X | X | | |
Miłosz Krzysiek | X | X | X | X | X | X | | | |
Michał Łukasik | X | X | X | X | X | X | X | | |
Kacper Pajor | | | X | | | | | | |
Ksawery Plis | X | X |==X==| X | X | X | | | |
Kacper Ponikowski | X | X | X | X | X | | | | |
Yaryna Rachkevych | X | | X | X | ==X== | X | X | | |
Cyprian Skrzypczak | X | X | X | X | | | | | |
Antoni Strasz | X | | X | ==X== | X | X | | | |
Marta Strzelec | | | | | | | | | |
Dominik Szczepaniak | X | X | X | X | X | X | | | |
Piotr Thamm | ==X== | | X | X | X | X | | | |
Michał Włodarczak | X | X | X | X | X | X | X | | |
:::

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

## Zadanie 1
:::success
Autor: Piotr Thamm

class OneBit implements Lock {
    private boolean[] flag;
    
    public OneBit (int n) {
        flag = new boolean[n]; // all initially false
    }
    public void lock() {
        int i = ThreadID.get(); // ThreadID.get() returns 0,1,..,n-1
        do {
            flag[i] = true;
            for (int j = 0; j < i; j++) {
                if (flag[j] == true) {
                    flag[i] = false;
                    while (flag[j] == true) {} // wait until flag[j] == false
                    break;
                }
            }
        } while (flag[i] == false);
        for (int j = i+1; j < n; j++) {
            while (flag[j] == true) {} // wait until flag[j] == false
        }
    }
    
    public void unlock() {
        flag[ThreadID.get()] = false;
    }
}

### Wzajemne wykluczanie - ok
Załóżmy nie wprost, że 2 wątki A oraz B znalazły się w CS w tym samym czasi.
Bez straty ogólności, niech A będzie tym wątkiem, który pierwszy wszedł do Strefy krytycznej.

#### Rozpatrzmy 2 przypadki
> **a) Niech A < B, wtedy:**
> Aby wątek B, wszedł do CS musiałby w pierwszej pętli(linia 11) zobaczyć, że ```flaga[A] == false```. Możliwe jest to tylko wtedy gdyby wątek A ustawiłbym swoją flagę na ```true``` po wątku B, ale wtedy wątek A czekałby w drugiej pętli(linia 19), ponieważ ```flag[B] == true```.
> <font color="red">Zatem sprzeczność.</font>
>
> **b) Niech A > B, wtedy:**
> W tej sytuacji wątek B, aby wejść do CS musiałby zobaczyć w drugiej pętli (linia 19), że ```flag[A] == false```. To znaczy, że B sprawdził flage A przed ustawieniem jej na true. Ale wtedy wątek A czekałby w linii 14, aż wątek B ustawi swoją flagę na false. Jest to tylko możliwe jak B wyjdzie z CS.
> <font color="red">Zatem sprzeczność.</font>

FORMALNIE:
#### a)
Aby wątek B, wszedł do CS, to w ostatniej iteracji pętli do-while jest READ_B(flag[a] == false).
_1
Wtedy również wiemy, że flaga B jest podniesiona, czyli $WRITE_B[flag[b] = true] \rightarrow_1 READ_B(flag[a] == false)$ i nie jest prawdą, że WRITE_B[flag[b] = true] -> WRITE_B[flag[b] = false]. Ponieważ $WRITE_B(flag[b]=true) \rightarrow_2 READ_B(flag[a] == false)$, to musi zajść READ_B(flag[a] == false) -> WRITE_A(flag[a] = true). To oznacza, że WRITE_B(flag[b]=true) -> WRITE_A(flag[a] = true). Ponieważ A jest w sekcji krytycznej to WRITE_A(flag[a] = true) -> READ_A(flag[b] == false) (read w wierszu 20), bo B > A. Zatem mamy WRITE_B(flag[b]=true) -> WRITE_A(flag[a] = true) -> READ_A(flag[b] == false).

### Niezakleszczenie - ok
Z pierwszej pętli for(linia 11) wyjdzie wątek o najmniejszym indeksie. Taki wątek zawsze istnieje. Zatem po kolei wątki od najmniejszego będą opuszczać pętle. W drugiej pętli sytuacja jest podobna. Jedyna różnica jest taka, że z pętli wychodzi (i jednocześnie wchodzi do CS) wątek o największym indeksie, a taki również zawsze istnieje.

### Niezagłodzenie - nie ok ;(

Jeżeli wątek $W_0$ będzie szybko wchodził i wychodził z ***sekcji krytycznej***, a pozostałe wątki nie będą na tyle szybko odczytywały zmiany flagi $W_0$, wtedy zostaną one zagłodzone.
:::

## Zadanie 2
:::success
Autor: Viktoriia Kashpruk

**Stan niespójny** dla obiektu Lock to sytuacja, w której bieżący stan blokady wskazuje, że żaden wątek nie znajduje się w sekcji krytycznej (CS) ani nie próbuje do niej wejść, ale w rzeczywistości jakiś wątek faktycznie jest w sekcji krytycznej. Innymi słowy, stan wewnętrzny blokady nie odpowiada rzeczywistej globalnej sytuacji systemu.
Dowód, że żaden zamek spełniający warunek niezakleszcenia nie wjedzie do stanu niespójnego.

Dowód: Załóżmy, że obiekt Lock znajduje się w niespójnym stanie s, w którym żaden wątek nie znajduje się w sekcji krytycznej ani nie próbuje do niej wejść. Jeśli wątek B spróbuje wejść do sekcji krytycznej, to musi mu się to ostatecznie udać, ponieważ algorytm jest wolny od zakleszczeń.

Załóżmy teraz, że obiekt Lock jest w niespójnym stanie s, w którym wątek A znajduje się w sekcji krytycznej. Jeśli wątek B spróbuje wejść do sekcji krytycznej, musi się zablokować, dopóki wątek A nie opuści sekcji.

Pojawia się sprzeczność, ponieważ wątek B nie może ustalić, czy wątek A jest w sekcji krytyczne

---
**Stan pokrycia** to sytuacja, w której wątki są bliskie zapisania wartości do współdzielonych lokalizacji (pokrywają te lokalizacje), ale w danej chwili stan tych lokalizacji „wygląda” tak, jakby sekcja krytyczna była pusta (nikt jej nie używa, ani nikt nie próbuje do niej wejść).

---
**Twierdzenie:** Każdy algorytm Lock, który poprzez operacje odczytu i zapisu do pamięci rozwiązuje problem wzajemnego wykluczania bez zakleszczeń dla trzech wątków, musi używać co najmniej trzech odrębnych lokalizacji w pamięci.

Zał nie wprost, że mamy zamek z wzajemnym wykluczaniem, bez zakleszczeń dla trzech wątków, używający 2 komórki pamięci.

Na początku mamy stan **s**, w którym żaden z wątków nie chce wejść do CS.
Jeśli jakiś wątek chce wejść do SK, to musi nadpisać jedną komórkę pamięci, inaczej inne wątki nie wiedzą czy SK już jest zajęta i mamy stan s niespójny.

Z tego wynika, że każdy wątek musi nadpisać conajmniej jedną komórkę pamięci przed wejściem do SK.
- 1) Jeśli mamy komórki pamięci niewspółdzielone, czyli, że tylko jeden wątek może je nadpisać to widzimy, że **3 komórki pamięci** są niezbędne

- 2) Jeśli mamy zmienne współdzielone (np **victim** w alg. Petersona)

Niech s będzie w stanie pokrycia, gdie wątki A i B pokrywają **różne** komórki pamięci. Niech C będzie trzecim wątkiem, który chce wejść do SK.
Z racji tego, ze zamek jest bez zakleszczeń, to wcześniej lub później C wejdzie do SK, i nadpisze miejsca, które są pokryte przez inne wątki (A i B)
Jak puścimy wątki A i B znowu, to oni nadpiszą miejsca, które pokrywają, i s będzie w stanie niespójnym, bo nie ma możliwości powiedzieć czy **C** jest w SK. Jeden z wątkow (A lub B) wejdzie do SK. Sprzeczność

Wystarczy pokazać, jak sprawić, żeby wątki A i B były w stanie pokrycia.

Rozpatrzymy przypadek, kiedy B przejdzie sekcję krytyczną 3 razy.
Ponieważ mamy 2 miejsca, i 3 przejścia, to wątek B nadpisze wartość jednej komórki 2 razy. Niech to będzie $L_B$.

- Pozwalamy wątku B działać, aż będzie gotowy nadpisać $L_B$
Jeśli wątek A teraz zadziała, to wejdzie do sekcji krytycznej, nadpisując $L_A$. Nie może nadpisać $L_B$, bo to by znaczyło, że jak puścimy wątek B z powrotem, to po nadpisaniu $L_B$ przez B nie będzie możliwości sprawdzenia czy A jest w SK, czyli stan będzie niespójny.
- Pozwalamy wątku A działać, aż będzie gotowy nadpisać $L_A$. Pozwalamy B działać i zatrzymujemy przed tym jak nadpisze $L_B$

W tym stanie, A chce nadpisać $L_A$ i B chce nadpisać $L_B$.

Współdzielone lokalizacje pamięci ($L_A$​ i $L_B$​) sugerują, że żaden wątek nie próbuje wejść do sekcji krytycznej, ponieważ ich wartości zostały zresetowane lub nadpisane przez wcześniejsze operacje.
To jest właśnie stan pokrycia: oba wątki są gotowe do zapisania w odpowiednie lokalizacje, ale obecne wartości tych lokalizacji sugerują, że sekcja krytyczna jest wolna.

:::

## Zadanie 3
:::success
Autor: Ksawery Plis
:::
### Diagram 1
**Linearyzowalne:**

r.write(1) -> r.read(1) -> r.write(2) -> r.read(2)

### Diagram 2
**Linearyzowalne:**

r.write(2) -> r.write(1) -> r.read(1) -> r.read(1)

### Diagram 3
**Nielinearyzowalne:**
Na kolejkę p wrzucamy x, potem y. W takim razie najpierw powinniśmy zdjąć x, a zdejmujemy y

### Diagram 4
**Nielinearyzowalne:**
Kolejka p tak samo jak na poprzednim diagramie, kolejka q analogiczna - najpierw wrzucamy y, potem x, więc najpierw powinniśmy zdjąć y a zdejmujemy x

## Zadanie 4
:::success
Autor: Antoni Strasz
:::


Historię G tworzymy poprzez :

1. kończenie niezakończonych wywołań
2. odrzucanie niezakończonych wywołań

Natomiast w każdym z przykładów wszystkie wywołania są zakończone, można więc pominąć H->G

### Diagramy:


H :

B r.write(1)
A r.read()
C r.write(2)
A r: 1
C r: void
B r: void
B r.read()
B r: 2

->$_{H} =$ {$A: r.read(1)$-> $B: r.read(2)$ ; $B: r.write(1)$-> $B: r.read(2)$ ; $C: r.write(2)$-> $B: r.read(2)$}

S :

B r.write(1)
B r: void
A r.read()
A r: 1
C r.write(2)
C r: void
B r.read()
B r: 2

->$_{S} =$ {$B: r.write(1)$-> $A: r.read(1)$ -> $C: r.write(2)$ -> $B: r.read(2)$}

:::success
Więc ->$_{H} \subset$ -> $_{S}$
:::

---

H :

B r.write(1)
A r.read()
C r.write(2)
A r: 1
C r: void
B r: void
B r.read()
B r: 1

->$_{H} =$ {$A: r.read(1)$-> $B: r.read(1)$ ; $B: r.write(1)$-> $B: r.read(1)$ ; $C: r.write(2)$-> $B: r.read(1)$}

S :

C r.write(2)
C r: void
B r.write(1)
B r: void
A r.read()
A r: 1
B r.read()
B r: 1

->$_{S} =$ {$C: r.write(2)$ -> $B: r.write(1)$-> $A: r.read(1)$ -> $B: r.read(1)$}

:::success
Więc ->$_{H} \subset$ ->$_{S}$
:::

---

H :

A p.enq(x)
A p : void

B p.enq(y)
B p : void

A p.deq()
A p : void

->$_{H} =$ {$A: p.enq(x)$ -> $B: p.enq(y)$-> $A: p.deq(y)$ }

Powyższa sekwencja jest sprzeczna, nie można zatem ułożyć legalnej sekwencyjnej histori S, że ->$_{H} \subset$ ->$_{S}$

---


H :

A p.enq(x)
A p : void

B q.enq(y)
B q : void

A q.enq(x)
A q : void

B p.enq(y)
B p : void

A p.deq()
A p : y

B q.deq()
B q : x

H|p : Jak powyżej
H|q : Symetrycznie jak powyżej

## Zadanie 5
:::success
Autor: Yaryna Rachkevych
:::spoiler Nowy kod

class MergeSort implements Runnable {
    protected int[] arr;
    protected int[] tempArray;
    protected int l, r;

    MergeSort(int[] arr, int[] tempArray, int left, int right) {
        this.arr = arr;
        this.tempArray = tempArray;
        this.l = left;
        this.r = right;
    }

    private void copyToTempArray(int left, int right) {
        for (int i = left; i <= right; i++) {
            tempArray[i] = arr[i];
        }
    }

    private void mergeArrays(int left, int middle, int right) {
        int i = left;
        int j = middle + 1;
        int k = left;

        while (i <= middle && j <= right) {
            if (tempArray[i] <= tempArray[j]) {
                arr[k] = tempArray[i];
                i += 1;
            } else {
                arr[k] = tempArray[j];
                j += 1;
            }
            k += 1;
        }

        // Kopiowanie pozostałych elementów z lewej podtablicy
        while (i <= middle) {
            arr[k] = tempArray[i];
            i += 1;
            k += 1;
        }

        // Elementy z prawej podtablicy są już na swoich miejscach
    }

    private void merge(int left, int middle, int right) {
        copyToTempArray(left, right); 
        mergeArrays(left, middle, right);  
    }

    // Funkcja sort jest zbędna
    // public void sort(int left, int right) {
    //     if (left < right) {
    //         int middle = (left + right) / 2;
    //         sort(left, middle);
    //         sort(middle + 1, right);
    //         merge(left, middle, right);
    //     }
    // }

    @Override
    public void run() {
        if (l < r) {
            int m = (l + r) / 2;

            MergeSort lToMerge = new MergeSort(arr, tempArray, l, m);
            MergeSort rToMerge = new MergeSort(arr, tempArray, m + 1, r);

            Thread lThread = new Thread(lToMerge);
            Thread rThread = new Thread(rToMerge);

            lThread.start();
            rThread.start();

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

            merge(l, m, r);
        }
    }
}

public class RookieMergeSortNew {

    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 10, 2, 23, 6, 17, 1};
        int[] tempArray = new int[arr.length]; 

        MergeSort toMerge = new MergeSort(arr, tempArray, 0, arr.length - 1);

        Thread mainThread = new Thread(toMerge);

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

        for (int i = 0; i < arr.length; i += 1) {
            System.out.printf("%d ", arr[i]);
        }
    }
}

:::
**Wydzielenie alokacji tablicy pomocniczej:**

Zamiast alokowania wielu tablic pomocniczych przy każdym wywołaniu metody merge, teraz jedna tablica tempArray jest tworzona w metodzie main i współdzielona między wszystkimi wątkami. To eliminuje zbędne alokacje pamięci.

**Usunięcie synchronizacji:**

Synchronizacja była zbędna, ponieważ każdy wątek pracuje nad niezależnymi fragmentami tablicy, a merge działa tylko na fragmentach, które nie są modyfikowane przez inne wątki w tym samym czasie. Dzięki współdzieleniu pomocniczej tablicy i ograniczeniu jej użycia do odczytu, nie ma potrzeby synchronizacji.
:::

## Zadanie 6
:::success
Autor: Dominik Szczepaniak
:::

class MergeSort implements Runnable 
{
    protected int[] arr;
    protected int[] helper;
    protected int left, right;
    private static int size_limit = 5;

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

    private void merge(int l, int m, int r) {
        int leftSize = m - l + 1;
        int rightSize = r - m;

        int leftPosition = l;
        int rightPosition = m + 1;
        int arrPosition = l;

        System.arraycopy(arr, leftPosition, helper, leftPosition, leftSize);
        System.arraycopy(arr, rightPosition, helper, rightPosition, rightSize);

        int leftEnd = l + leftSize;
        int rightEnd = rightPosition + rightSize;

        while (leftPosition < leftEnd && rightPosition < rightEnd) {
            if (helper[leftPosition] <= helper[rightPosition]) {
                arr[arrPosition++] = helper[leftPosition++];
            } else {
                arr[arrPosition++] = helper[rightPosition++];
            }
        }

        if (leftPosition < leftEnd) {
            System.arraycopy(helper, leftPosition, arr, arrPosition, leftEnd - leftPosition);
        }
    }

    public void sort (int left, int right) 
    {
        if (left < right) 
        {
            int middle = (left + right) / 2;

            sort(left, middle);
            sort(middle + 1, right);

            merge(left, middle, right);
        }
    }

    @Override
    public void run() 
    {
        if (this.left < this.right) 
        {
            int m = (this.left + this.right) / 2;

            if (right - left + 1 <= size_limit)
            {
                sort(left, right);
            }
            else
            {
                MergeSort left = new MergeSort(arr, this.left, m);
                MergeSort right = new MergeSort(arr, m + 1, this.right);

                Thread t1 = new Thread(left);

                t1.start();
                right.run();

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

                this.merge(this.left, m, this.right);
            }
        }
    }
}

## Zadanie 7
:::success
Autor: Michał Łukasik
:::

class MergeSort implements Runnable {
    protected int[] array;
    protected int[] tempArray;
    protected int leftIndex, rightIndex;
    private static final int THRESHOLD = 4;
    private static final int M = 4; //limit wątków
    private static int activeThreads = 0;

    private static final Object lock = new Object();

    MergeSort(int[] array, int[] tempArray,int leftIndex, int rightIndex) {
        this.array = array;
        this.tempArray = tempArray;
        this.leftIndex = leftIndex;
        this.rightIndex = rightIndex;
    }

    private void merge(int leftIndex, int middleIndex, int rightIndex) {
        for (int i = leftIndex; i <= rightIndex; i++) {
            tempArray[i] = array[i];
        }

        int i = leftIndex;
        int j = middleIndex + 1;
        int k = leftIndex;

        while (i <= middleIndex && j <= rightIndex) {
            if (tempArray[i] <= tempArray[j]) {
                array[k] = tempArray[i];
                i++;
            } else {
                array[k] = tempArray[j];
                j++;
            }
            k++;
        }

        while (i <= middleIndex) {
            array[k] = tempArray[i];
            i++;
            k++;
        }
        while (j <= rightIndex) {
            array[k] = tempArray[j];
            j++;
            k++;
        }
    }

    public void sort(int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < THRESHOLD) {
            insertionSort(leftIndex, rightIndex);
            return;
        }

        if (leftIndex < rightIndex) {
            int middleIndex = (leftIndex + rightIndex) / 2;

            boolean newThread = false;
            synchronized (lock) {
                if (activeThreads < M) {
                    activeThreads++;
                    newThread = true;
                }
            }

            if (newThread) {
                MergeSort rightTask = new MergeSort(array, tempArray, middleIndex + 1, rightIndex);
                Thread rightThread = new Thread(rightTask);
                rightThread.start();

                sort(leftIndex, middleIndex);

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

                synchronized (lock) {
                    activeThreads--;
                }
            } else {
                sort(leftIndex, middleIndex);
                sort(middleIndex + 1, rightIndex);
            }

            merge(leftIndex, middleIndex, rightIndex);
        }
    }

    private void insertionSort(int leftIndex, int rightIndex) {
        for (int i = leftIndex + 1; i <= rightIndex; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= leftIndex && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }

    @Override
    public void run() {
        sort(this.leftIndex, this.rightIndex);
    }
}

public class Z7 {
    public static void main(String[] args) {
        int[] array = {4, 3, 2, 1, 6, 5, 7, 8};
        int[] tempArray = new int[array.length];
        MergeSort mergeSortTask = new MergeSort(array, tempArray, 0, array.length - 1);

        Thread sortingThread = new Thread(mergeSortTask);
        sortingThread.start();

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

        for (int i = 0; i < array.length; i++) {
            System.out.printf("%d ", array[i]);
        }
    }
}

## Zadanie 8
:::success
Autor: Maria Hreniak
:::


class MergeSubsequence implements Runnable {
    private final int[] arr;
    private final int left;
    private final int right;

    private int[] longest; 
    private int[] longestFromLeft; 
    private int[] longestFromRight; 

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

    public int[] getLongest() {
        return longest;
    }

    public int[] getLongestFromLeft() {
        return longestFromLeft;
    }

    public int[] getLongestFromRight() {
        return longestFromRight;
    }

    // łączy wyniki z dwóch podtablic
    private void merge(MergeSubsequence leftBranch, MergeSubsequence rightBranch) {
        // dane o najdłuższych podciągach
        int[] leftLongest = leftBranch.getLongest();
        int[] leftLongestFromRight = leftBranch.getLongestFromRight();

        int[] rightLongest = rightBranch.getLongest();
        int[] rightLongestFromLeft = rightBranch.getLongestFromLeft();

        // ustalamy najdłuższy podciąg - czy jest w lewej czy w prawej podtablicy?
        longest = (leftLongest[1] > rightLongest[1]) ? leftLongest : rightLongest;

        // czy możemy połączyć podciągi z obu stron? 
        // tzn. czy na styku [   RfL] [LfR   ] jest ta sama wartość?
        if (leftLongestFromRight != null && rightLongestFromLeft != null && leftLongestFromRight[0] == rightLongestFromLeft[0]) {
            // długość po połączeniu
            int combinedLength = leftLongestFromRight[1] + rightLongestFromLeft[1];
            // sprawdzamy, czy po połączeniu jest dłuższy podciąg niż ten wyłoniony tylko z lewej i prawej
            if (combinedLength > longest[1]) {
                longest = new int[] {leftLongestFromRight[0], combinedLength};
            }
        }

        // ustalamy najdłuższy podciąg od lewej
        //[...RfL][LfR    ], czyli czy możemy zaktualizować najdłuższy od lewej
        if (leftLongestFromRight != null && leftLongestFromRight[0] == rightLongestFromLeft[0]) {
            
            longestFromLeft = new int[] {leftLongestFromRight[0], leftLongestFromRight[1] + rightLongestFromLeft[1]};
            
        } else {
            //bez zmian
            longestFromLeft = leftBranch.getLongestFromLeft();
        }

        // ustalamy najdłuższy podciąg od prawej
        //analogicznie [  RfL][LfR...], czyli czy możemy zaktualizować najdłuższy od prawej
        if (rightLongestFromLeft != null && rightLongestFromLeft[0] == leftLongestFromRight[0]) {
            
            longestFromRight = new int[] {rightLongestFromLeft[0], rightLongestFromLeft[1] + leftLongestFromRight[1]};
            
        } else {
            //bez zmian
            longestFromRight = rightBranch.getLongestFromRight();
        }
    }

    @Override
    public void run() {
        if (left == right) {
            longest = new int[] {arr[left], 1};
            longestFromLeft = new int[] {arr[left], 1};
            longestFromRight = new int[] {arr[right], 1};
        } else {
            // postępujemy analogicznie jak w mergesort
            int mid = (left + right) / 2;

            MergeSubsequence left = new MergeSubsequence(arr, left, mid);
            MergeSubsequence right = new MergeSubsequence(arr, mid + 1, right);

            // tworzymy wątki dla obu podtablic
            Thread leftThread = new Thread(left);
            Thread rightThread = new Thread(right);

            leftThread.start();
            rightThread.start();

            try {
                leftThread.join();
                rightThread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            merge(leftSort, rightSort);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,1,2,1,2,1,2,3,3,3}; 
        MergeSubsequence mergeSubsequence = new MergeSubsequence(arr, 0, arr.length - 1);

        // uruchamiamy w osobnym wątku
        Thread mainThread = new Thread(mergeSubsequence);
        mainThread.start();

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

        int number = mergeSubsequence.longest[0]; 
        int length = mergeSubsequence.longest[1]; 

        int[] longestSubsequence = new int[length]; // tablica najdłuższego podciągu
        for (int i = 0; i < length; i++) {
            longestSubsequence[i] = number;
        }

        for (int i = 0; i < longestSubsequence.length; i++) {
            System.out.print(longestSubsequence[i]);
            if (i < longestSubsequence.length - 1) {
                System.out.print(", "); 
            }
        }
        System.out.println("]");
    }
}

## Zadanie 9
:::success
Autor: Dominik Szczepaniak
:::

a)
Mamy trzy wątki - A, B i C
flag(A) = true
A czyta counter i idzie spać zanim go zwiększy.
flag(B) = true
label(B) = 0, counter++
flag( C ) = true
label( C ) = 1, counter++
B wchodzi do CS
B wychodzi
flag(B) = false
A wybudza się, ustawia counter na 1, wchodzi do CS, wychodzi i flag(A) = false
C wchodzi do CS i idzie spać
A ponownie próbuje wejść do CS
flag(A) = true
label(A) = 1
A wchodzi do CS, bo (label(A), 0) < (label(C), 2)
A i C są w CS

b) Do zakleszczenia dochodzi gdy jeden wątek czeka na inny.

Tak, **Do zakleszczenia nie dojdzie, ponieważ żeby doszło musi dla dwóch wątków A i B jednocześnie zachodzić flag(A) && label(B) > label(A) oraz flag(B) && label(A) > label(B), a nie może zajść jednocześnie label(B) > label(A) > label(B).** Może zajść natomiast, że label będą równe, ale wtedy wartości indeksów będą inne więc będzie porządek leksykograficzny.

c) Z definicji zagłodzenie to sytuacja w której wątek nigdy nie dostanie dostępu do CS.
W takim razie jeśli nawet counter będzie cofać swoją wartość, to może cofnąć ją do jakiegoś stanu wątku który odczytał counter w przeszłości i zasnął. Po tym jak ten wątek się wykona, wartości counter nie będziemy mogli cofnąć do wartości sprzed zasnięcia, chyba że zasnął jakiś inny wątek. Jednak liczba wątków jest skończona, więc po pewnym czasie nie będzie wątku który zaśnie z jakąś wartością counter. W takim razie po skończonej ilości wątkow (i cofnięć countera) dojdziemy do wartości counter na którą czeka potencjalnie zagłodzony wątek, więc wykona się on (co prawda zdecydowanie później niż powinien, ale wykona).