# Ćwiczenia 3, grupa cz. 16-18, 26 października 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Dominik Baziuk | | | X | X | X | X | X | |
Paweł Borek | X | | X | X | | | | |
Arti Brzozowski | | | | | | | | |
Mateusz Golisz | | | | | | | | |
Kacper Jóźwiak | X | | X | X | X | X | | |
Julia Konefał | | | | | | | | |
Adam Korta | ==x== | | x | x | x | | | |
Jakub Mikołajczyk | | | X | X | X | ==X== | X | |
Bartosz Morasz | x | x | x | ==x== | x | x | | |
Andrzej Morawski | | | | | | | | |
Aleksandra Nicpoń | x | | x | x | x | | | |
Mateusz Reis | X | X | X | X | X | X | ==X== |
Tomasz Stachurski | | | | | | | | |
Marcel Szelwiga | X | | X | X | X | | | |
Volha Tsekalo | x | x | ==x== | x | | | | |
Martyna Wybraniec | x | | x | x | x | | | |
Denys Zinoviev | | | | | | | | |
Dominik Olejarz | x | | x | x | x | | | |
:::

Tutaj można zadeklarować zadanie 9 z listy 2:
:::danger
| | 2.9 |
| ----------------------:| ----- |
| Marcel Szelwiga | ==X== |
| | |
| | |
| | |
:::

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

## Zadanie 1
:::success
Autor: Adam Korta
:::
### Zadanie 1

:::spoiler kod

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;
    }
}

:::

1) **Wzajemne wykluczanie - spełnia**
Załóżmy nie wprost, że 2 wątki(A, B) znalazły się w CS w tym samym czasi. BSO niech A będzie wątkiem, który pierwszy wszedł do CS. Rozpatrzmy 2 przypadki
a) Niech A < B, wtedy:
wątek B, aby wejść do CS musiał zobaczyć w pierwszej pętli, że flaga wątku A jest ustawiona na false(Jeżeli byłaby ustawiona na true to zatrzymałbym się w whilu). Jest to tylko możliwe jeżeli wątek A ustawiłbym swoją flagę na true po wątku B, ale wtedy wątek A czekałby w drugiej pętli bo flag[B] == true. Zatem sprzeczność.
b) Niech A > B, wtedy:
wątek B, aby wejść do CS musiałbym zobaczyć w drugiej pętl for, że flaga wątku A jest ustawiona na false. To znaczy, że B sprawdził flage A przed ustawieniem jej na true. Ale wtedy wątek A czekałbym w pierwszej pętli for, aż wątek B ustawi swoją flagę na false. Jest to tylko możliwe jak B wyjdzie z CS. Zatem sprzeczność 

3) **Niezakleszczenie - spełnia**
Zauważmy, że w pierwszej pętli sprawdzane są tylko wątki o mniejszy id. Wiemy, że id wątków są rożnowartościowe. Zatem istnieje dokładnie 1 najmniejszy wątek, który w ogóle nie będzie czekał w pierwszej pętli. Zatem w pierwszej pętli nie może dojść do zakleszczenia. Zauważmy, że mamy analogiczną sytuacje w drugiej pętli gdzie największy wątek wiejdzie do CS bez żadnego sprawdzania. Zatem Algorytm spełnia warunek niezakleszczenia.

5) **Niezagłodzenie - Niespełnia**
Weźmy 2 wątki (0 szybki) i (1 wolny). Niech wątek 0 szybko wchodzi i wychodzi z CS, a wątek 1 wolno reaguje na zmiane flagi wątku 0. Wtedy wątek 0 będzie głodzi wątek 1. Stąd algorytm nie spełnia warunku niezagłodzenia.

## Zadanie 2
:::success
Autor: Mateusz Reis
:::

Stan zamka jest **niespojny** gdy w sekcji krytycznej jest jakis watek a zamek wskazuje na to ze jest inaczej lub na odwrot.

Zaden zamek ktory jest wolny od zakleszczen, nie doprowadzi do **niespojnego** stanu.

Zamek jest w stanie **pokrywajacym** gdy co najmniej jeden watek bedzie pisac do kazdej
lokacji, a zamek wskazuje na to ze nie ma zadnego watku w sekcji krytycznej ani nie oczekuje na wejscie do niej.

W stanie pokrywajacym mowimy ze watek pokrywa dany bit jesli zaraz bedzie chcial go zapisac.

Pokazemy ze kazdy niezakleszczajacy sie zamek dla 3 watkow musi miec co najmniej 3 niezalezne bity informacji.

Zalozmy ze mamy niezakleszczajacy sie zamek dla 3 watkow, ktory ma tylko 2 bity pamieci.
W poczatkowym stanie $S$ zaden watek nie jest w sekcji krytycznej ani nie probuje sie do niej dostac. Jesli uruchomimy watki, to kazdy z nich bedzie musial zapisac co najmniej jeden bit zeby zaznaczyc swoja obecnosc w sekcji krytycznej, inaczej osiagniemy niespojny stan zamka. W ten sposob od razu widac ze zamek w ktorym jeden watek pisze tylko do jednej komorki pamieci wymaga co najmniej 3 bitow.

Teraz spojrzmy na zamek w ktorym bity moga byc zapisywane przez rozne watki (np.Petersona i pole $victim$). Wciaz mamy 3 watki i 2 bity informacji. Niech $S$ bedzie stanem pokrywajacym, w ktorym watki $A$ oraz $B$ chca zapisac rozne bity. Rozwazmy przebieg programu zaczynajac od stanu $S$:

Watek $C$ startuje i w koncu czasie wchodzi do sekcji krytycznej bo zamek sie nie zakleszcza, wtedy watki $A$ i $B$ nadpisuja bity ktore pokrywaly. Mamy wtedy zamek w stanie niespojnym, co prowadzi do sprzecznosci.

Stan ten jest niespojny bo zaden watek nie moze stwierdzic czy watek $C$ jest w sekcji krytycznej.

Ten dowod latwo rozszerzyc na wiecej watkow i bitow.

## Zadanie 3
:::success
Autor: Volha Tsekalo
:::

## Zadanie 4
:::success
Autor: Bartosz Morasz
:::


W każdym przypadku G=H, bo nie mamy żadnych oczekujących wywołań, wszystkie mają odpowiedź.

- Diagram 1

**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

**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

$$
\rightarrow G = \{B: r.write(1) \rightarrow B: r.read(2),\\
A: r.read(1) \rightarrow B: r.read(2),\\
C: r.write(2) \rightarrow B: r.read(2)\}
$$

$$
\rightarrow S = \{B: r.write(1) \rightarrow A: r.read(1),\\
A: r.read(1) \rightarrow C: r.write(2),\\
C: r.write(2) \rightarrow B: r.read(2)\}
$$

- Diagram 2

**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

**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

$$
\rightarrow G = \{B: r.write(1) \rightarrow B: r.read(1),\\
A: r.read(1) \rightarrow B: r.read(1),\\
C: r.write(2) \rightarrow B: r.read(1)\}
$$

$$
\rightarrow S = \{C: r.write(2) \rightarrow B: r.write(1),\\
B: r.write(1) \rightarrow A: r.read(1),\\
A: r.read(1) \rightarrow B: r.read(1)\}
$$

- Diagram 3

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

$$
\rightarrow G = \{A: r.enq(x) \rightarrow B: p.enq(y) \rightarrow B: p.deq(y)\}
$$

Nie możliwe ułożenie poprawnego S.

- Diagram 4

**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()
A: p: y

B: q.deq()
B: q: x

$$
\rightarrow G = \{A: p.enq(x) \rightarrow B: q.enq(y) \rightarrow A: q.enq(x) \rightarrow \\ B: p.enq(y) \rightarrow A: q.deq(y) \rightarrow B: q.deq(x)\}
$$

Tak jak w poprzednim, brak możliwości ułożenia poprawnego S.

## Zadanie 5
:::success
Autor: Dominik Baziuk
:::

class MergeSort implements Runnable {
    protected int array[];
    protected int helperArray[];
    protected int left, right;

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

    private void fillHelperArray(int left, int right) {
        for (int i = left; i <= right; i++) {
        	helperArray[i] = array[i];
        }
    }
    private void mergeToArray(int left, int middle, int right, int leftIndex, int rightIndex) {
    	int index = left;
        while (leftIndex < middle + 1 && rightIndex < right + 1) {
            if (helperArray[leftIndex] <= helperArray[rightIndex]) {
            	array[index] = helperArray[leftIndex];
                leftIndex += 1;
            } else {
            	array[index] = helperArray[rightIndex];
                rightIndex += 1;
            }
            index += 1;
        }
        while (leftIndex < middle + 1) {
        	array[index] = helperArray[leftIndex];
            index += 1;
            leftIndex += 1;
        }
        while (rightIndex < right + 1) {
        	array[index] = helperArray[rightIndex];
            index += 1;
            rightIndex += 1;
        }
    }

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

    @Override
    public void run() {
        if (this.left < this.right) {
            int middle = (this.left + this.right) / 2;
            MergeSort left = new MergeSort(array, helperArray, this.left, middle);
            MergeSort right = new MergeSort(array, helperArray, middle + 1, this.right);
            Thread t1 = new Thread(left);
            Thread t2 = new Thread(right);
            t1.start();
            t2.start();
            try {
                t1.join();
                t2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            this.merge(this.left, middle, this.right);
        }
    }
}

public class RookieMergeSort {

    public static void main(String[] args) {
        int arr[] = {11,5,15,16,6,8,7,12,4,3,10,1,9,13,2,14};
        int helperArray[] = new int[16];
        MergeSort w = new MergeSort(arr,helperArray, 0, 15);

        Thread t = new Thread(w);

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

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


    }
}

## Zadanie 6
:::success
Autor: Jakub Mikołajczyk
:::

package z6;

class MergeSort implements Runnable {
    protected int[] arr;
    protected int[] help_arr;

    protected int l, r;

    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) {

        System.arraycopy(arr, l, help_arr, l, r - l + 1);

        int leftIndex = l;
        int leftEnd = m + 1;

        int rightIndex = m + 1;
        int rightEnd = r + 1;

        int arrIndex = l;
        while (leftIndex < leftEnd && rightIndex < rightEnd){
            if (help_arr[leftIndex] <= help_arr[rightIndex]){
                arr[arrIndex] = help_arr[leftIndex];
                leftIndex++;
            }
            else {
                arr[arrIndex] = help_arr[rightIndex];
                rightIndex++;
            }
            arrIndex++;
        }
        System.arraycopy(help_arr, leftIndex, arr, arrIndex, leftEnd - leftIndex);
        System.arraycopy(help_arr, rightIndex, arr, arrIndex, rightEnd - rightIndex);
    }

    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 sortSmall(int l, int r){
        for (int i = l; i < r + 1; i++){
            int minIndex = i;
            for (int j = i + 1; j < r + 1; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(minIndex, i);
        }
    }

    private void swap(int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    @Override
    public void run() {
        if (this.l < this.r) {
            if (r - l + 1 < 5){
                sortSmall(l, 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);
                t1.start();
                right.run();
                try {
                    t1.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                this.merge(this.l, m, this.r);
            }
        }
    }
}

## Zadanie 7
:::success
Autor: Dominik Baziuk
:::

class MergeSort implements Runnable {
    public static final int maxThreads = 100;
    protected static int threadCounter = 1;
    protected static final Object lock = new Object();
    protected int array[];
    protected int helperArray[];
    protected int left, right;

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

    private void fillHelperArray(int left, int right) {
        for (int i = left; i <= right; i++) {
        	helperArray[i] = array[i];
        }
    }
    private void mergeToArray(int left, int middle, int right, int leftIndex, int rightIndex) {
    	int index = left;
        while (leftIndex < middle + 1 && rightIndex < right + 1) {
            if (helperArray[leftIndex] <= helperArray[rightIndex]) {
            	array[index] = helperArray[leftIndex];
                leftIndex += 1;
            } else {
            	array[index] = helperArray[rightIndex];
                rightIndex += 1;
            }
            index += 1;
        }
        while (leftIndex < middle + 1) {
        	array[index] = helperArray[leftIndex];
            index += 1;
            leftIndex += 1;
        }
        while (rightIndex < right + 1) {
        	array[index] = helperArray[rightIndex];
            index += 1;
            rightIndex += 1;
        }
    }

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

    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 middle = (this.left + this.right) / 2;
    		
    		Thread t1 = null;
    		
    		synchronized(lock) {
    			if(threadCounter + 1  <=  maxThreads) {
    				MergeSort left = new MergeSort(array, helperArray, this.left, middle);
    				t1 = new Thread(left);
    				threadCounter += 1;
    				System.out.println(threadCounter);
    			}
         	}
    		
    		Thread t2 = null;
    		
    		synchronized(lock) {
    			if(threadCounter + 1  <=  maxThreads) {
    				MergeSort right = new MergeSort(array, helperArray, middle + 1, this.right);   		             
    				t2 = new Thread(right);
    				threadCounter += 1;
    				System.out.println(threadCounter);
    			}
         	}
       
             if(t1 != null) {
            	 t1.start();
             }else {
            	 sort(this.left, middle);
             }
        
             if(t2 != null) {
            	 t2.start();
             }else {
            	 sort(middle + 1, this.right);   
             }
             
             try {
            	 if(t1 != null) {
            		 t1.join();
            	 }
                 
            	 if(t2 != null) {	
            		 t2.join();
            	 }
             } catch (InterruptedException e) {
                 e.printStackTrace();
             }
             this.merge(this.left, middle, this.right);
        	
        }
        synchronized(lock) {
    		threadCounter -= 1;
    	}
    }
}


public class RookieMergeSort {

    public static void main(String[] args) {
        int arr[] = {11,5,15,16,6,8,7,12,4,3,10,1,9,13,2,14};
        int helperArray[] = new int[16];
        MergeSort w = new MergeSort(arr,helperArray, 0, 15);

        Thread t = new Thread(w);

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

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

    }
}

## Zadanie 8
:::success
Autor: Dominik Baziuk
:::

:::info
Zadanie 8 (fork/join). Napisz wielowątkowy program, który w
zadanej tablicy liczb całkowitych wyszuka najdłuższy spójny
podciąg wystąpień tej samej liczby. Jeśli takich podciągów
jest wiele, to wystarczy znaleźć jeden. Np. dla ciągu
[1,2,1,2,1,2,1,2,3,3,3] wynik to [3,3,3], a dla [1,2,3,3,4,1]
wynik to [3,3]. Wynik należy wypisać na konsoli.
:::

class LongestSubstring implements Runnable {
    protected int array[];
    
    int leftBorder;
    int rightBorder;
    int middleBorder;
    
    int leftSubstringValue = 0;
    int leftSubstringLength = 0;
    
    int rightSubstringValue = 0;
    int rightSubstringLength = 0;
    
    int bestSubstringValue = 0;
    int bestSubstringLength = 0;
    
    LongestSubstring leftSide;
    LongestSubstring rightSide;
    
    Thread t1;
    Thread t2;
    
    LongestSubstring(int[] array,int leftBorder,int rightBorder) {
        this.array = array;
        this.leftBorder = leftBorder;
        this.rightBorder = rightBorder;
    }
    
    private void singleNumberCase() {
    	leftSubstringValue = rightSubstringValue = bestSubstringValue = array[leftBorder];
        leftSubstringLength = rightSubstringLength = bestSubstringLength = 1;
    }
    
    private void checkBestSubstrings() {
    	int candidateValue = -1;
    	int candidateLength = 0;
    	
    	if(leftSide.bestSubstringLength > candidateLength) {
    		candidateValue = leftSide.bestSubstringValue;
    		candidateLength = leftSide.bestSubstringLength;
    	}
    	
    	if(rightSide.bestSubstringLength > candidateLength) {
    		candidateValue = rightSide.bestSubstringValue;
    		candidateLength = rightSide.bestSubstringLength;
    	}
    	
    	if(rightSide.leftSubstringLength + leftSide.rightSubstringLength > candidateLength
    	&& rightSide.leftSubstringValue == leftSide.rightSubstringValue) {
    		candidateValue = leftSide.rightSubstringValue;
    		candidateLength = rightSide.leftSubstringLength + leftSide.rightSubstringLength;
    	}
    	
    	this.bestSubstringValue = candidateValue;
    	this.bestSubstringLength = candidateLength;
    }
    
    private void updateBorders() {
    	this.leftSubstringValue = leftSide.leftSubstringValue;
    	this.leftSubstringLength = leftSide.leftSubstringLength;
    	
    	int leftIndex = leftBorder + leftSide.leftSubstringLength;
    	if(leftIndex == middleBorder + 1
    	&& array[leftBorder] == array[middleBorder + 1]) {
    		this.leftSubstringLength += rightSide.rightSubstringLength;
    	}
    	
    	this.rightSubstringValue = rightSide.rightSubstringValue;
    	this.rightSubstringLength = rightSide.rightSubstringLength;
    	
    	int rightIndex = rightBorder - rightSide.rightSubstringLength;
    	if(rightIndex == middleBorder
    	&& array[rightBorder] == array[middleBorder]) {
    		this.rightSubstringLength += leftSide.rightSubstringLength;
    	}
    }

    private void makeThreads(){
    	middleBorder = (this.leftBorder + this.rightBorder) / 2;
        leftSide = new LongestSubstring(array, this.leftBorder, middleBorder);
        rightSide = new LongestSubstring(array, middleBorder + 1, this.rightBorder);
        t1 = new Thread(leftSide);
        t2 = new Thread(rightSide);
        t1.start();
        t2.start();        
    }
    
    private void joinThreads() {
    	try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    @Override
    public void run() {
        if (this.leftBorder < this.rightBorder) {
        	makeThreads();
        	joinThreads();
        	checkBestSubstrings();
        	updateBorders();
        }else {
        	singleNumberCase();
        }
       // System.out.println("[" + leftBorder + ", " + rightBorder + "] V = " + bestSubstringValue + " , L = " + bestSubstringLength +", LV = " + leftSubstringValue + " , LL = " + leftSubstringLength+",	RV = " + rightSubstringValue + " , RL = " + rightSubstringLength);
    }
}

public class LongestSubstringSolver {

    public static void main(String[] args) {
    				 // 0 1 2 3 4 5 6 7 8 9 10
        int array1[] = {1,2,1,2,1,2,1,2,3,3,3};
        int array2[] = {1,2,3,3,4,1};
        
        int n1 = 10;
        int n2 = 5;
        
        LongestSubstring w = new LongestSubstring(array1, 0, n1);

        Thread t = new Thread(w);

        t.start();
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
   
        System.out.println("Litera: " + w.bestSubstringValue);
        System.out.println("Wystąpienia w podciągu: " + w.bestSubstringLength);
    }
}