# Ćwiczenia 3, grupa śr. 10-12, 25 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | |
Konrad Kowalczyk | X | | X | X | X | | | |
Jakub Krzyżowski | | | X | X | X | | | |
Łukasz Magnuszewski | | | | | | | | |
Marcin Majchrzyk | | | X | X | X | X | X | X |
Jan Marek | X | | X | X | X | X | X | |
Michał Mękarski | | | | | | | | |
Marcin Mierzejewski | | | | | | | | |
Juan Jose Nieto Ruiz | x | x | | | x | x | x | x |
Dominik Olejarz | | | | | | | | |
Konrad Oleksy | | | X | X | X | X | X | |
Javier Rábago Montero | X | X | X | X | X | | | X |
:::

Tutaj można zadeklarować zaległe zadania 6 i 9 z listy 2:

:::danger
| | 2.6 | 2.9 |
| ----------------------:| ----- | --- |
| Javier Rábago Montero | | X |
| | | |
:::

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

## Zadanie 1
:::success
Autor: Konrad Kowalczyk
:::


<b>Wzajemne wykluczenie - spełnia</b>
Wątek musi ustawić swoją flagę na `true`, żeby wejść do sekcji krytycznej.
Rozpatrzmy dwa przypadki:
- Wątek, który znalazł się w sekcji krytycznej jako pierwszy (wątek `i`) ma mniejszy numer niż ten, który chce się dostać (wątek `j`) - wtedy wątek `j`, aby wejść, musiałby nie wykryć żadnego wątku podczas iterowania się w pierwszej pętli `for`. Jedyną taką możliwością jest sytuacja, w której wątek `i` ustawiłby swoją flagę na `true` po tym, jak wątek `j` sprawdzi jego flagę w pętli `for`. Jednak zauważmy, że wątek `j` ustawił swoją flagę na `true` przed wejściem do pętli `for`, a zatem wątek `i` wtedy wykryłby wątek `j` podczas iterowania się w drugiej pętli `for`, i musiałby na niego zaczekać, co jest sprzeczne z założeniem. Możliwe jest, że jakiś inny wątek sprawi, że wątek `j` ustawi swoją flagę na `false`, ale wtedy wątek `j` przerwie pętlę `for` i przejdzie ponownie przez `while`, gdzie tym razem będzie musiał już wykryć wątek `i` i na pewno nie wejdzie do sekcji krytycznej, gdy `i` wciąż w niej jest.
- Wątek, który znalazł się w sekcji krytycznej jako pierwszy (wątek `i`) ma większy numer niż ten, który chce się dostać (wątek `j`) - wtedy wątek `j`, aby wejść, musiałby nie wykryć żadnego wątku podczas iterowania się w drugiej pętli `for`. Jedyną taką możliwością jest sytuacja, w której wątek `i` ustawiłby swoją flagę na `true` po tym, jak wątek `j` sprawdzi jego flagę w pętli `for`. Jednak zauważmy, że w momencie iterowania się w drugiej pętli `for` wątek `j` ma ustawioną swoją flagę na `true`. Wątek `i`, po ustawieniu swojej flagi na `true` musiałby przeiterować się przez pierwszą pętlę `for`, gdzie w takiej sytuacji wykryłby wątek `j` i musiałby na niego zaczekać, co jest sprzeczne z założeniem.

<b>Niezakleszczenie - spełnia</b>
W pętli `do {...} while` wątek `i` sprawdza tylko wątki o numerze mniejszym od niego. To oznacza, że z pętli zawsze wyjdzie co najmniej wątek o najmniejszym numerze. A skoro wątek o następnym numerze mógł czekać tylko na niego, to on też zostanie odblokowany i tak dalej. W takim razie wątki nie mogą zakleszczyć się w pierwszej pętli `while`. Zauważmy też, że niemożliwym jest, aby wszystkie wątki zakleszczyły się w drugiej pętli `while`, ponieważ wątek o najwyższym numerze w ogóle nie wykonuje pętli `for`. A wątek o numerze o jeden niższym mógł czekać tylko na niego, a zatem na pewno się odblokuje i tak dalej.
<b>Niezagłodzenie - nie spełnia</b>
Możemy zauważyć, że wątek o numerze 0 zawsze przejdzie przez `do {...} while`. Może zajść sytuacja, w której pozostałe wątki będą na niego czekać. Jeśli nie wybudzą się w porę, wątek 0 zdąży ponownie ustawić swoją flagę na `true` i ponownie nic nie zatrzyma go przed kolejnym wejściem do sekcji krytycznej.

## Zadanie 2
:::success
Autor: Juan Jose Nieto Ruiz
:::
The theorem that states you need exactly n shared bits to implement a lock for n threads is known as the "bit constraint theorem" in mutual exclusion theory. To prove this theorem, we can use a proof by contradiction.

Suppose it's possible to implement a lock for n threads with fewer than n bits of shared memory, say k bits, where k < n. Now, we'll examine the contradiction this creates.

Each bit in shared memory can be in one of two states: 0 or 1. Therefore, there are a total of 2^k possible combinations of states for k bits of shared memory.

Now, consider that there are n different threads attempting to acquire the lock. Each thread can be in one of the following states: locked (waiting to acquire the lock) or unlocked (either already acquired the lock or doing something else). For n different threads, there are 2^n possible combinations of states for those threads.

Since there are 2^k possible combinations of states in the k bits of shared memory and 2^n possible combinations of states for the n threads, and k < n, then by the Pigeonhole Principle, there will be at least one combination of states in the k bits that repeats for different combinations of states of the n threads.

This fact leads to a contradiction. If two different sets of states for the n threads match the same combination of states in the k bits of shared memory, then you cannot guarantee proper mutual exclusion. If a thread relies only on the k bits to determine if it can acquire the lock, it won't be able to distinguish between these two sets of threads, which can lead to a violation of mutual exclusion.

## Zadanie 3
:::success
Autor: Jakub Krzyżowski
:::
Linearyzowalne:
$r.write(1) \rightarrow r.read(1) \rightarrow r.write(2) \rightarrow r.read(2)$

Linearyzowalne:
$r.write(2) \rightarrow r.write(1) \rightarrow r.read(1) \rightarrow r.read(1)$

Nielinearyzowalne:
W kolejce FIFO żeby ściągnąć y z p najpierw trzeba ściągnąć x.

Nielinearyzowalne:
H|p jest taka sama jak poprzednio, a H|q jest symetryczna.

## Zadanie 4
:::success
Autor:Jan Marek
:::

Nie mamy oczekujących wywołań, więć nie musimy rozszerzać H do G (a więc "H=G").

**(1)**
**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)}

**(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)}

**(3)**
**Historia G:**

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

G nie odpowiada żadnej legalnej sekwencyjnej historii S, ponieważ `p.enq(x) -> p.enq(y) -> p.deq(y)`, co jest sprzeczne. Przed wykonaniem p.deq(y) pierwszym elementem w kolejce p będzie x, więc wykonanie p.deq(y) jest niemożliwe.

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

Znów G nie odpowiada żadnej legalnej sekwencyjnej historii S, ponieważ mamy:
1. `p.enq(x) -> p.enq(y) -> p.deq(y)`
oraz
2. `q.enq(y) -> q.enq(x) -> q.deq(x)`
Co jest niemożliwe.

## Zadanie 5
:::success
Autor: Konrad Oleksy
:::

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.l = l;
        this.r = r;
        this.help_arr = help_arr;
        
    }

    private void merge(int l, int m, int r) {

         for (int i = l; i <= r; i++) {
            this.help_arr[i] = arr[i];
        }

        int left_index = l;
        int left_end =m;

        int right_index = m+1;
        int right_end= r;

        int index=l;

        while (left_index <= left_end && right_index <= right_end) {
            if (help_arr[left_index] <= help_arr[right_index]) {
                arr[index] = help_arr[left_index];
                left_index += 1;
            } else {
                arr[index] = help_arr[right_index];
                right_index += 1;
            }
            index += 1;
        }
        while (left_index <= left_end) {
            arr[index] = help_arr[left_index];
            index += 1;
            left_index += 1;
        }
        while (right_index <= right_end) {
            arr[index] = help_arr[right_index];
            index += 1;
            right_index += 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);
        }
    }

    @Override
    public void run() {

        if (this.l < this.r) {
            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);
            Thread t2 = new Thread(right);
            t1.start();
            t2.start();
            try {
                t1.join();
                t2.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            this.merge(this.l, m, this.r);
        }
    }
}


public class Zadanie5 {

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

        Thread t = new Thread(w);

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

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


    }
}

## Zadanie 6
:::success
Autor:Marcin Majchrzyk
:::

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

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

        this.helper = helper;
    }

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

        int arrPosition = l;
        int leftPosition = l, rightPosition = l + leftSize;

        int leftEnd = leftPosition + leftSize, rightEnd = rightPosition + rightSize;

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

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

        System.arraycopy(helper, leftPosition,  arr, arrPosition, leftEnd - leftPosition);
        System.arraycopy(helper, rightPosition, arr, arrPosition, rightEnd - rightPosition);
    }

    private void sortSmall(int l, int r)
    {
        if (arr[l] > arr[r])
        {
            int t = arr[l];
            arr[l] = arr[r];
            arr[r] = t;
        }
    }

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

            if (r - l < 4) {
                sortSmall(l, m);
                sortSmall(m+1, r);
            } else {
                MergeSortv2 left = new MergeSort(arr, this.l, m, helper);
                MergeSortv2 right = new MergeSort(arr, m + 1, this.r, helper);

                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: Jan Marek
:::

class MergeSort implements Runnable {
    protected int arr[];
    protected int shared_arr[];
    protected int left, right;

    public static final int MAX_THREAD_COUNT = 10;
    private static int active_threads_count = 0;
    private final Object lock = new Object();

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

    private void push_to_shared_arr(int arr[], int left, int middle, int right, int left_size, int right_size) {
        for (int i = 0; i < left_size; i++) {
            shared_arr[left + i] = arr[left + i];
        }
        for (int i = 0; i < right_size; i++) {
            shared_arr[middle + 1 + i] = arr[middle + 1 + i];
        }
    }

    private void merge(int left, int middle, int right) {
        int left_size = middle - left + 1;
        int right_size = right - middle;
        push_to_shared_arr(arr, left, middle, right, left_size, right_size);
        int i = 0, j = 0; // i - wsk. w lewej tab, j - wsk. w prawej tab
        int k = left; // akt. wsk.
        while (i < left_size && j < right_size) {
            if (shared_arr[left + i] <= shared_arr[middle + 1 + j]) {
                arr[k] = shared_arr[left + i];
                i += 1;
            } else {
                arr[k] = shared_arr[middle + 1 + j];
                j += 1;
            }
            k += 1;
        }
        while (i < left_size) {
            arr[k] = shared_arr[left + i];
            k += 1;
            i += 1;
        }
        while (j < right_size) {
            arr[k] = shared_arr[middle + 1 + j];
            k += 1;
            j += 1;
        }
    }

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

        synchronized (lock) {
            active_threads_count += 1;
        }
      
        if (this.left < this.right) {
            boolean sort_serially;
            synchronized (lock) {
                sort_serially = active_threads_count > MAX_THREAD_COUNT - 2;
            }
            if (sort_serially) {
                this.sort(this.left, this.right);
            }
            else {
                int middle = (this.left + this.right) / 2;
                MergeSort left_sort = new MergeSort(arr, shared_arr, this.left, middle);
                MergeSort right_sort = new MergeSort(arr, shared_arr, middle + 1, this.right);
                Thread thread_1 = new Thread(left_sort);
                Thread thread_2 = new Thread(right_sort);
                thread_1.start();
                thread_2.start();
                try {
                    thread_1.join();
                    thread_2.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                this.merge(this.left, middle, this.right);
            }
        }
        
        synchronized (lock) {
            active_threads_count -= 1;
        }

    }
}


public class RookieMergeSort {

    public static void main(String[] args) {
        int arr[] = {4, 3, 55, 2, 1, 18, 77, 0, -100, 12, 12};
        int[] shared_arr = new int[11];
        MergeSort sort = new MergeSort(arr, shared_arr, 0, 10);

        Thread main_thread = new Thread(sort);

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

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


    }
}

## Zadanie 8
:::danger
Autor: Marcin Majchrzyk
:::