# Ćwiczenia 3, grupa śr. 16-18, 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Bartosz Borecki | X | | X | X | X | X | | | |
Miriam Bouhajeb | | | | | | | | | |
Marceli Buczek | X | | ==X== | X | X | X | X | X | |
Maciej Ciepiela | X | | X | ==X== | X | X | X | | |
Maciej Dominiak | x | | x | x | | | | | |
Michał Hajahmadov | X | | X | X | X | X | | | |
Adam Majchrowski | X | | X | X | X | X | X | ==X== | |
Hanna Makowska | ==X== | | X | X | X | X | X | | |
Cezary Miłek | X | | X | X | X | X | | | |
Błażej Molik | X | | X | X | X | X | X | | |
Konrad Oleksy | | | X | X | X | X | X | | |
Kacper Osadowski | X | | X | X | | | | | |
Yurii Pryimak | | | | | | | | | |
Aliaksandr Tyszecki | | | | | | | | | |
Miłosz Urbanik | | | | | | | | | |
Yana Vashkevich | | | | | | | | | |
Piotr Warząchowski | X | | X | X | X | X | X | | |
:::

Poniżej można zadeklarować zadania 6 i 9 z listy 2.:

:::danger
| | 2.6 | 2.9 |
| ----------------------:| ----- | --- |
| | | |
| Hanna Makowska | | X |
| Adam Majchrowski | | X |
| Maciej Dominiak | | X |
Błażej Molik | | X|

:::

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

## Zadanie 1
Autor: Kacper Osadowski

mutual exclusion
aby wydarzyło się wspólne wejście musi zajść
załóżmy że mamy

więc dla n wątków
EventX = Vj >i+1 flag\[j]= false
EventY = Vj < i flag\[j]= false

A.read(Y) => A.read(X)
B.read(Y) => b.read(X)

więc mamy cykl ponieważ któryś z wątków musiał mieć Thread.Id mniejsze od 2

Dowód nie wprost.

Załóżmy, że dwa wątki A i B są w sekcji krytycznej. Niech A < B.

Wątek B przeszedł pętlę do-while, w szczególności zauważył, że $flag[A] == false$. Wątek A również
przeszedł przez do-while. Wątek B przeszedł przez pętlę for i zauważył, że flagi wątków o numerach wyższych są opuszczone. Wątek A "zrobił to samo", w szczególności zauważył, że $flag[B] == false$. To oznacza, że wątek A zauważył w pętli "for", że $flag[B] == false$ wcześniej, niż B opuścił do-while.

wiemy że wątek A musiał wejść pierwszy do for ponieważ musił zauważyć flag[B]==false oraz że wątek B musiał wejść pierwszy do for ponieważ zauwazył w do while flag[A] == false więc oba wątki musiały pierwsze wejść do pętli for

zagłodzenie

możemy zauwazyć że wątek 0 jest w stanie pomijać pętle do while i zapalać swoją flagę jednocześnie głodząc wszystkie inne

:::

## Zadanie 2
:::danger
Autor: do zadeklarowania na następnych ćwiczeniach
:::

## Zadanie 3
:::success
Autor: Marceli Buczek
:::
1) Linearyzowalne
2) Linearyzowalne
3) Nielinearyzowalne
4) Nielinearyzowalne

## Zadanie 4
:::success
Autor: Maciej Ciepiela
:::
Historia G:
B: r.write(1)
A: r.read(1)
C: r.write(2)
A: r: 1
C: r: void
B: r: void
B: r.read(2)
B: r: 2

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

→G = {B r.write(1) -> B r.read(2), A r.read(1) -> B r.read(2), C r.write(2) -> B r.read(2)}

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

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

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

→G = {C r.write(2) -> B r.read(1), B r.write(1) -> B r.read(1), A r.read(1) -> B r.read(1)}

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


Historia G:
A: p.enq(x)
A: p: void
B: p.enq(y)
B: p: void
A: p.deq(y)
A: p: y

G nie odpowiada żadnej legalnej sekwencyjnej historii S, ponieważ p.enq(x) -> p.enq(y) -> p.deq(y), jest sprzeczne.


Historia G:
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(y)
A: p: y
B: q.deq(x)
B: q: x

Znów G nie odpowiada żadnej legalnej sekwencyjnej historii S, ponieważ mamy:
p.enq(x) -> p.enq(y) -> p.deq(y)
q.enq(y) -> q.enq(x) -> q.deq(x)
A to są sprzeczności.

## Zadanie 5
:::success
Autor: Michał Hajahmadov
:::

class MergeSort implements Runnable {
    protected int arr[];
    protected int l, r;
    protected int tempArray[]; // tablica pomocnicza
    // dzieki niej bedziemy pracowac na kopii danych arr, co ulatwi nam manipulacje danymi

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

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

    // leftIndex -> poczatek lewej polowy
    // rightIndex -> poczatek prawej polowy
    private void mergeToArray(int left, int middle, int right, int leftIndex, int rightIndex) {
        int index = left;
        while (leftIndex <= middle && rightIndex <= right) {
            if (tempArray[leftIndex] <= tempArray[rightIndex]) {
                arr[index] = tempArray[leftIndex];
                leftIndex += 1;
            } else {
                arr[index] = tempArray[rightIndex];
                rightIndex += 1;
            }
            index += 1;
        }
        while (leftIndex <= middle) {
            arr[index] = tempArray[leftIndex];
            index += 1;
            leftIndex += 1;
        }
        while (rightIndex <= right) {
            arr[index] = tempArray[rightIndex];
            index += 1;
            rightIndex += 1;
        }
    }

    private void merge(int left, int middle, int right) {
        int leftIndex = left;
        int rightIndex = middle + 1;

        fillTempArray(left, right);
        mergeToArray(left, middle, right, leftIndex, rightIndex);
    }

    @Override
    public void run() {
        if (this.l < this.r) {
            int middle = (this.l + this.r) / 2;
            MergeSort left = new MergeSort(arr, tempArray, this.l, middle);
            MergeSort right = new MergeSort(arr, tempArray, middle + 1, this.r);
            Thread t1 = new Thread(left);
            Thread t2 = new Thread(right);
            // uruchamiamy wątki
            t1.start();
            t2.start();
            // i czekamy na ich zakończenie
            try {
                t1.join();
                t2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            this.merge(this.l, middle, this.r);
        }
    }
}


public class RookieMergeSort {

    public static void main(String[] args) {
        int arr[] = {4, 3, 2, 1};
        int tempArray[] = new int[4];
        MergeSort w = new MergeSort(arr, tempArray, 0, 3);

        Thread t = new Thread(w);

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

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

## Zadanie 6
:::success
Autor: Bartosz Borecki

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

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

    private void merge(int l, int m, int r) {
        for (int i = l; i <= r; i++) {
            help[i] = arr[i];
        }
        
        int l_l = l, l_r = m, r_l = m+1, r_r = r;
        int k = l;
        while (l_l <= l_r && r_l <= r_r) {
            if (help[l_l] <= help[r_l]) {
                arr[k] = help[l_l];
                l_l += 1;
            } else {
                arr[k] = help[r_l];
                r_l += 1;
            }
            k += 1;
        }
        while (l_l <= l_r) {
            arr[k] = help[l_l];
            k += 1;
            l_l += 1;
        }
        while (r_l <= r_r) {
            arr[k] = help[r_l];
            k += 1;
            r_l += 1;
        }
    }

    public void sort(int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(l, m);
            sort(m + 1, r);
            merge(l, m, r);
        }
    }

    public void sort_small(int l, int r){
	int key, j;
        for (int i = l+1; i <= r; i++){
	    key = arr[i];
            j = i-1;
            while (j >= 0 && arr[j] > key) {
	        arr[j+1] = arr[j];
		j -= 1;
            }
	    arr[j+1] = key;
        }
    }
    @Override
    public void run() {
        if (this.l < this.r) {
            if (r - l < 5){
                sort_small(l, r);
            }
            else
            {
                int m = (this.l + this.r) / 2;
                MergeSort left = new MergeSort(arr, this.l, m, help);
                MergeSort right = new MergeSort(arr, m + 1, this.r, help);
                Thread t1 = new Thread(left);
                t1.start();
                right.run();
                try {
                    t1.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                this.merge(this.l, m, this.r);
            }
        }
    }
}


public class RookieMergeSort {

    public static void main(String[] args) {
        int arr[] = {4, 3, 2, 1};
        MergeSort w = new MergeSort(arr, 0, 3, new int[arr.length]);
        
        Thread t = new Thread(w);
        t.start();
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

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


    }
}

:::

## Zadanie 7
:::success
Autor: Konrad Oleksy
:::

class MergeSort implements Runnable {
    protected int arr[];
    protected int help_arr[];
    protected int l, r;
    protected static int threads_left = 4;
    private final Object lock = new Object();

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

    private void merge(int l, int m, int r) {
        for (int i = l; i <= r; i++) {
            this.help_arr[i] = arr[i];
        }

        int i = 0, j = 0;
        int k = l;

        while (i <= m - l && j <= r - m - 1) {
            if (help_arr[l + i] <= help_arr[m + 1 + j]) {
                arr[k] = help_arr[l + i];
                i += 1;
            } else {
                arr[k] = help_arr[m + 1 + j];
                j += 1;
            }
            k += 1;
        }
        while (i <= m - l) {
            arr[k] = help_arr[l + i];
            k += 1;
            i += 1;
        }
        while (j <= r - m - 1) {
            arr[k] = help_arr[m + 1 + j];
            k += 1;
            j += 1;
        }

    }

    public void sort(int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(l, m);
            sort(m + 1, r);
            merge(l, m, r);
        }

    }

    public void select_sort(int l, int r) {

        for (int i = l; i <= r; i++) {

            int min_idx = i;

            for (int j = i + 1; j <= r; j++) {
                if (arr[j] < arr[min_idx])
                    min_idx = j;
            }

            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    @Override
    public void run() {
        if (this.l < this.r) {
            boolean use_threads = false;
            synchronized (lock) {
                if (threads_left > 1) {
                    use_threads = true;
                    
                }
            }
            if (this.r - this.r < 3 || !use_threads ) {
                select_sort(this.l, this.r);
            
            } else 
            {

                int m = (this.l + this.r) / 2;
                MergeSort left = new MergeSort(arr, help_arr, this.l, m);
                MergeSort right = new MergeSort(arr, help_arr, m + 1, this.r);
                Thread t1 = new Thread(left);
                synchronized (lock) {
                    threads_left -= 1;

                }
                t1.start();
                right.run();
                try {
                    t1.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                this.merge(this.l, m, this.r);

             
            }
            synchronized (lock) {
                threads_left += 1;

            }
        }
    }
}

## Zadanie 8
:::success
Autor: Adam Majchrowski
:::

// zadanie 8
/*
 * Co tu się właściwie dzieje?
 * Chciałem sobie ułatwić jakoś życie i skorzystać juz z "szkieletu" merge sorta, który
 * właściwie się przydał. 
 * Najwięcej jest zmienione w metodzie merge() bo zamiast scalać tablice to aktualizuje 3 zmienne:
 * - longest: czyli parę (num, amount) reprezentującą najdłuższy podciąg tych samych liczb w ciągu
 * - longest_from_left: reprezentującą najdłuższy podciąg tych samych liczb w ciągu od lewej
 * składających się z liczb takich jak pierwsza od lewej
 * - longest_from_right: analogicznie tylko od prawej
 */



class MergeSort implements Runnable {
    protected int arr[];
    protected int left_ID, right_ID;
    protected int longest[];
    protected int longest_from_left[];
    protected int longest_from_right[];

    MergeSort(int arr[], int l, int r ) {
        this.arr = arr;
        this.left_ID = l;
        this.right_ID = r;
    }

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

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

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

    private void merge(MergeSort left_branch, MergeSort right_branch) { 
        // tutaj wyciągamy sobie nasze potrzebne dane
        int[] lBranch_longest = left_branch.getLongest(); 
        int[] lBranch_longest_from_right = left_branch.getLongestFromRight();

        int[] rBranch_longest = right_branch.getLongest();
        int[] rBranch_longest_from_left = right_branch.getLongestFromLeft();
        

        if (lBranch_longest[1] > rBranch_longest[1]) {
            longest = lBranch_longest;
        } else {
            longest = rBranch_longest;
        }

        if (lBranch_longest_from_right != null && rBranch_longest_from_left != null && lBranch_longest_from_right[0] == rBranch_longest_from_left[0]) {
            
            int combined_length = lBranch_longest_from_right[1] + rBranch_longest_from_left[1];

            if (combined_length > longest[1]) {
                longest = new int[] {lBranch_longest_from_right[0], combined_length};
            } 
        }
            

        if (lBranch_longest_from_right != null && lBranch_longest_from_right[0] == rBranch_longest_from_left[0]) {
            
            longest_from_left = new int[] {lBranch_longest_from_right[0], lBranch_longest_from_right[1] + rBranch_longest_from_left[1]};
            } 
            else {
            
            longest_from_left = left_branch.getLongestFromLeft();
        }
        
        

        if (rBranch_longest_from_left != null && rBranch_longest_from_left[0] == lBranch_longest_from_right[0]) {
            
            longest_from_right = new int[] {rBranch_longest_from_left[0], rBranch_longest_from_left[1] + lBranch_longest_from_right[1]};
        } 
        else {
            
            longest_from_right = right_branch.getLongestFromRight();
        }

    }
    



    @Override
    public void run() {
        if (this.left_ID == this.right_ID) {
            longest = new int[] {arr[left_ID], 1};
            longest_from_left = new int[] {arr[left_ID], 1};
            longest_from_right = new int[] {arr[right_ID], 1};
        } 
        else {

            int m = (this.left_ID + this.right_ID) / 2;

            MergeSort left = new MergeSort(arr, this.left_ID, m);
            MergeSort right = new MergeSort(arr, m + 1, this.right_ID);

            Thread thread_left = new Thread(left);
            Thread thread_right = new Thread(right);

            thread_left.start();
            thread_right.start();

            try {
                thread_left.join();
                thread_right.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            merge(left, right);
        }
    }
}


public class RookieMergeSort {

    public static void main(String[] args) {
        int arr[] = {1, 2, 1, 2, 1, 3, 3, 3};
        // int arr[] = {1, 1, 1, 1, 1, 1, 1, 1};
        MergeSort w = new MergeSort(arr,  0, 7);

        Thread thread = new Thread(w);

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

        
        System.out.println("num: " + w.longest[0] + " amount: " + w.longest[1]);


    }
}

## Zadanie 9
:::success
Autor: Maciej Dominiak
:::

Przy 3 wątkach ( nazwanych i,j,l ) może wystąpić następująca sytuacja
read_i( counter == k ) -> read_j( counter == k ) -> write_j( counter = k + 1) -> read_l( counter == k + 1 ) -> write_l( counter = k + 2 ) -> write_i( counter = k + 1 )

Czyli zmienna counter miała taki stan: k, k + 1, k + 2, k + 1. Zmienna chwilowo zmiejszyła się. Widzimy więc iż tak na prawdę zmienna counter może posiadać dowolną wartość <min_ze_wszystkich_wątków + 1, max_do_tej_pory>

Pozostaje pytanie jak to wpływa na działanie algorytmu.

a) Wzajemne wykluczenie

warunek (label[i], i) > (label[j], j) dobrze rozwiązuje problem wzajemnego wykluczania, nie zależnie od wartości label.

Tak na prawdę moglibyśmy porównywać tylko (i, j) i to już wystarczy do zagwarantowania wzajemnego wykluczania.

Kontrprzykład:
numer A < numer B < numer C

1. Początkowy stan systemu: label[i] = 0, dla każdego i, wartość counter == 0.
2. Wątek A podczas wykonywania lock() odczytuje wartość counter i zasypia. flag[A] == true
3. Wątki B, C wykonują metodę lock() ustalając label[B] = 0, label[C] = 1 i counter = 2. Wątki zatrzymują się na pętli while.
4. Wątek A wybudza się, ustawia counter = 1 przechodzi przez pętlę while i wchodzi do sekcji krytycznej.
5. Wątek A opuszcza sekcję krytyczną, czyli flag[A] == false.
6. Wątek B budzi się, wchodzi do CS, wychodzi z CS i ustawia flag[B]=false
7. Wątek C budzi się, wchodzi do CS i zasypia
8. Wątek A wywołuje lock(), ustawia flag[A] == true, ustawia label[A] = 1
9. Ponieważ (label[A], A) < (label[C], C) to A wejdzie do sekcji krytycznej i spotka tam C.
Warunkek (label[A], A) < (label[C], C) zachodzi ponieważ label[A] = label[C] i numer A < numer C.

b) Warunek niezakleszczenia
Przypuśćmy, że doszło do zakleszczenia, czyli żaden wątek nie może wejść do sekcji krytycznej

wszystko opiera się o warunki w pętli while
(∃k flag[k] && (label[i], i) > (label[k], k))

aby wątek i nie wszedł do sekcji krytycznej musi istnieć jakiś inny wątek ( np k ) który go zablokuje
więc flag[k] == true, oraz albo label[i] > label[k] albo i > k
wątek o niższym indeksie będzie zawsze przepuszczony, więc nie będzie blokować naszego wątku.

Dlatego zobaczmy co się stanie z wątkiem 0.
Aby nie wszedł do sekcji krytycznej label[0] > label[k] dla jakiegoś k
jak wcześniej pokazaliśmy label[0] może być dowolną liczbą z przedziału <1, max_do_tej_pory>

aby ten warunek był prawdziwy label[0] musiałby być ustawiony jako ostatni
Jednak wtedy jakiś inny wątek będzie mógł wejść do sekcji krytycznej

c) Warunek niezagłodzenia

Zagłodzenie może nastąpić. Może się zdarzyć tak, iż ciągle będziemy się cofać z licznikiem, ostatni wątek będzie zawsze dostawać pomniejszoną wartość,
więc będzie przegrywać z jakimś innym wątkiem i nastąpi zagłodzenie. Im mniejszy index wątku tym większa szansa