# Ćwiczenia 3, grupa cz. 14-16, 24 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 |
| --------------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Justyna Adamczyk | X | |==X==| X | X | X | | X | |
Kalina Białek | | | X |==X==| X | X | X | | |
Mateusz Budzyński | | | X | X | X | X | X | X | |
Karol Burczyk | | | | | | | | | |
Krystian Ćwikliński | X | |==X==| X | X | X | X | | |
Mikołaj Dygoń | X | | X | X | X |==X==| X | X | X |
Jose Javier Garcia Torrejon | X |==X==| | | X | X | X | X | X |
Mateusz Garncarczyk | | | X | X | X | X | | | |
Mikołaj Komarnicki | X | | X | X | X | X | X | X | X |
Beata Łakoma | X | X | X | X | X | X | X | | |
Jakub Malczak | X | X | X | X | X | X | ==X== | X | X |
Wiktor Małek | X | X | X | X | X | X | X | X | X |
Piotr Stachowicz | X | X | X | X | X | X | X | ==X== | X |
Dominik Walecko | X | | X | X | X | X | | | |
Natalia Zychowicz | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Dominik Walecko
:::

Załóżmy, że wątki $A$ i $B$ znalazły się w sekcji krytycznej w tym samym czasie i $A$ wszedł do niej jako pierwszy.

Rozważmy dwa przypadki:
**1. A < B:**
Skoro wątek $A$ wszedł do sekcji krytycznej jako pierwszy, to musiał przejść przez drugą pętlę, czyli:
$Write_A(flag[A] == True) \rightarrow Read_A(flag[B] == False) \rightarrow CS$

Skoro $Write_A(flag[A] = True) \rightarrow Read_A(flag[B] == False)$ i $A < B$ to wątek $B$ będzie musiał się zatrzymać w pierwszej pętli, dopóki $A$ nie wyjdzie z sekcji krytycznej i ustawi flagę z powrotem na $False$.

**2. A > B:**
Skoro $A > B$ i wątek $B$ wszedł do sekcji krytycznej, to ze względu na drugą pętlę musiało nastąpić:
$Write_B(Flag[B] = True) \rightarrow Read_B(flag[A] == False) \rightarrow CS$

Stąd, że $Read_B(flag[A] == False)$ wiemy, że wątek $A$ nie mógł w tym momencie być już za pierwszą pętlą i próbując z niej wyjść zauważy, że $Flag[B] == True$, co uniemożliwi mu wyjście z pierwszej pętli, bo $A > B$ i $B$ wejdzie do sekcji krytycznej jako pierwszy, co przeczy założeniu.

**b. Warunek niezakleszczenia:**
Wątek o najmniejszym ID nigdy nie będzie czekać w 1szej pętli. Wątek o największym ID nigdy nie będzie czekał w drugiej pętli.

**c. Głodzenie:**
Występuje. Wątek $1$ może wyprzedzić wątek $2$ w pierwszej pętli i wchodzić do sekcji krytycznej cały czas, jeśli wątek $2$ nie zareaguje na zmianę flagi wątku $1$ na $False$ odpowiednio szybko.

## Zadanie 2
:::success
Autor: Jose Javier Garcia Torrejon
:::

Zadanie 2 (2pkty). Poprzednie zadanie pokazało, że n
współdzielonych bitów wystarczy do implementacji zamka dla n
wątków. Okazuje się, że to ograniczenie jest dokładne, czyli
że n współdzielonych bitów jest koniecznych do rozwiązania
tego problemu. Udowodnij to twierdzenie.

STATEMENT:
The previous assignment showed that n shared bits are needed to implement a lock for n threads. It turns out that this constraint is exact, meaning that n shared bits are needed to solve this problem. Prove this theorem.

Hint: Chapter 2.9 of The Art of Multiprocessor Programming (2nd Edition).

ANSWER:

Each thread that wants to access the critical section needs a unique way of expressing this intention. This translates into the need for at least n independent memory locations for a system of n threads. Without these individual locations, the ability to unambiguously detect which thread is trying to access the critical section at a given time is lost, which is essential to ensure mutual exclusion

The ambiguity and inconsistency in shared states: If we reduce the number of shared memory locations below n, several threads would have to share these locations. This causes state overlap, meaning that multiple threads could use the same location to indicate their access intent. This is problematic as other threads would not be able to distinguish which thread is attempting to access it, thus violating mutual exclusion, as more than one thread could enter the critical section simultaneously due to confusion about the actual state

The linearity requirement and state coverage: In mutual exclusion theory, a fundamental characteristic is the linearity of the system, where every global state of the system (including shared memory and local variables of each thread) reflects an unambiguous situation. The state coverage is a situation in which every thread is about to write to a specific location to indicate its intent to access it. Without enough independent locations, it would be impossible to achieve this state coverage without falling into an inconsistent state, where it cannot be assured who is actually attempting to access the critical section

## Zadanie 3
:::success
Autor: Krystian Ćwikliński
:::
**Linearyzacja** to sposób na to, żeby w programie współbieżnym operacje wykonywane równolegle wyglądały tak, jakby **były wykonywane po kolei.** Każda operacja ma moment, w którym „oficjalnie” się kończy tzw **punkt linearyzacji**, a efekty programu muszą być zgodne z jakimś możliwym sekwencyjnym wykonaniem tych operacji.
### Przykład 1
### Przykład 2
### Przykład 3
### Przykład 4

## Zadanie 4
:::success
Autor: Kalina Białek
:::

Pozostałe dwa diagramy nie są linearyzowalne.

## Zadanie 5
:::success
Autor: Mateusz Budzyński

:::

## Zadanie 6
:::success
Autor: Wiktor Małek
:::
Idea jest taka, że "wpuszczamy" nowy wątek na lewo, a "obecny" wątek idzie na prawo.

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

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

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

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

        int i = l, j = m+1;
        int k = l;
        while (i <= m && j <= r) {
            if (helper_arr[i] <= helper_arr[j]) {
                arr[k] = helper_arr[i];
                i += 1;
            } else {
                arr[k] = helper_arr[j];
                j += 1;
            }
            k += 1;
        }
        while (i <= m) {
            arr[k] = helper_arr[i];
            k += 1;
            i += 1;
        }
        while (j <=r) {
            arr[k] = helper_arr[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);
        }
    }
    
    @Override
    public void run() {
        if (this.l < this.r && this.l - this.r + 1 > 4) {
            int m = (this.l + this.r) / 2;
            MergeSort left = new MergeSort(arr, helper_arr, this.l, m);
            MergeSort right = new MergeSort(arr, helper_arr, m + 1, this.r);
            Thread t = new Thread(left);
            t.start();
            right.run();
            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            this.merge(this.l, m, this.r);
        }else if(this.l < this.r){
            this.sort(this.l, this.r);
        }
    }
}


public class RookieMergeSort {

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

        Thread t = new Thread(w);

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

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


    }
}

## Zadanie 7
:::success
Autor: Jakub Malczak

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Random;

class MergeSort implements Runnable
{
    /* Variables */
    protected int[] arr;
    protected int left, right;
    static public int counter = 1;
    static public final Lock lock = new ReentrantLock();

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

    /* Put elements of two sorted arrays into one sorted array IN-PLACE */
    private void flush_arrays (int i, int j, int right_size)
    {
        int right = j + right_size - 1;

        while (i <= j && j <= right)
        {
            if (arr[i] <= arr[j])
            {
                ++i;
            }
            else
            {
                int temp = arr[j];

                for (int k = j; k > i; --k)
                {
                    arr[k] = arr[k - 1];
                }

                arr[i] = temp;

                ++i;
                ++j;
            }

        }
    }


    /* Merge two sorted arrays */
    private void merge (int left, int middle, int right)
    {
        int right_size = right - middle;

        flush_arrays(left, middle + 1, right_size);
    }

    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()
    {
        int size_limit = 5;

        if (this.left < this.right)
        {
            int m = (this.left + this.right) / 2;

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

                synchronized(lock)
                {
                    int m1 = 10;
                    if (counter + 1 <= m1)
                    {
                        t1 = new Thread(left_sort);
                        counter++;

                        System.out.println("Nowy watek: " + counter);
                        t1.start();
                    }
                }

                if (t1 == null)
                {
                    sort(left, right);
                }
                else
                {
                    right_sort.run();

                    try
                    {
                        t1.join();
                        synchronized(lock) {
                            counter--;
                        }
                    }
                    catch (InterruptedException e)
                    {
                        e.printStackTrace();
                    }

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

public class RookieMergeSort {

  public static void main(String[] args)
  {
    int size = 1000;
    int[] arr = new int[size];

    Random rand = new Random();

    for (int i = 0; i < size; ++i)
    {
      arr[i] = rand.nextInt(100);
    }


    MergeSort w = new MergeSort(arr, 0, size - 1);

    Thread t = new Thread(w);

    t.start();

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

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

    System.out.print("\n");
  }
}

:::

## Zadanie 8
:::success
Autor: Piotr Stachowicz

public class LongestSubSeq implements Runnable
{
  public class State
  {
    int idx = -1;
    int n = -1;
    int c = -1;
  }


  public State current_state;
  public int left, right;
  public int array[];


  LongestSubSeq(int org_arr[], int l, int r) 
  {
    this.array = org_arr;
    this.left = l;
    this.right = r;
    current_state = new State();
  }


  public void merge(State left, State right)
  {
    /* Left bigger than right */
    if (left.n >= right.n) 
    {
      current_state.n = left.n;
      current_state.idx = left.idx;
      current_state.c = left.c;
    }
    /* Right bigger than left */
    else
    {
      current_state.n = right.n;
      current_state.idx = right.idx;
      current_state.c = right.c;
    }

    /* Both have the same letter, thus check if they merge */
    if (left.c == right.c && left.idx + left.n == right.idx)
    {
      current_state.idx = left.idx;
      current_state.n = left.n + right.n;
      current_state.c = left.c;
    }

    /* Now we gonna check strip between the two */
    int strip_idx = -1;
    int strip_n = -1;
    int strip_c = -1;

    /* This is our result (if better than current) */
    int best_idx = -1;
    int best_n = -1;
    int best_c = -1;

    for (int i = left.idx + left.n; i < right.idx + right.n; ++i)
    {
      /* Edge case for first iteration */
      if (i == left.idx + left.n)
      {
        strip_idx = i;
        strip_n = 1;
        strip_c = array[strip_idx];
      }
      else
      {
        /* If mismatch, reset it */
        if (array[i] != strip_c)
        {
          strip_idx = i;
          strip_n = 1;
          strip_c = array[i];
        }
        else
        {
          strip_n += 1;
        }
        /* If better now, save it */
        if (strip_n > best_n)
        {
          best_idx = strip_idx;
          best_n = strip_n;
          best_c = strip_c;
        }
      }
    }



    /* If there is better sub sequence on strip, save it */
    if (best_n > current_state.n)
    {
      current_state.n = best_n;
      current_state.idx = best_idx;
      current_state.c = best_c;
    }
  }


  @Override
  public void run()
  {
    /* Recursive stop */
    if (left == right)
    {
      current_state.idx = left;
      current_state.c = array[left];
      current_state.n = 1;
      return;
    }

    /* Divide & Conquer */
    int middle = (left + right) / 2;

    LongestSubSeq left_rec = new LongestSubSeq(array, left, middle);
    LongestSubSeq right_rec = new LongestSubSeq(array, middle + 1, right);

    Thread thread1 = new Thread(left_rec);
    Thread thread2 = new Thread(right_rec);

    thread1.start();
    thread2.start();

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

    merge(left_rec.current_state, right_rec.current_state);
  }

  public static void main(String[] args)
  {
    int array1[] = {1, 2, 1, 2, 1, 2, 1, 2, 3, 3, 3};
    int array2[] = {3, 3, 3, 2, 3, 3};

    LongestSubSeq sub1 = new LongestSubSeq(array1, 0, array1.length - 1);
    LongestSubSeq sub2 = new LongestSubSeq(array2, 0, array2.length - 1);

    Thread job1 = new Thread(sub1);
    Thread job2 = new Thread(sub2);

    job1.start();
    job2.start();

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

    System.out.printf("i=%d, n=%d, val=%d\n", 
                   sub1.current_state.idx, sub1.current_state.n, sub1.current_state.c);

    System.out.printf("i=%d, n=%d, val=%d\n", 
                   sub2.current_state.idx, sub2.current_state.n, sub2.current_state.c);
  }
}

:::

## Zadanie 9
:::success
Autor: Wiktor Małek
:::

#### a)
Nie spełnia. Jeśli wątek $A$ poszedł spać na długo, z wczytaną wartością countera, a inne wątki w tym czasie wchodziły do sekcji krytycznej wiele razy oraz w momencie obudzenia się wątku $A$ był w sekcji krytycznej wątek $B$, to $A$ wejdzie do sekcji krytycznej, bo będzie miał najmniejszy label(doda 1 do dawno temu wczytanej wartośći `counter`).

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)
Rozważmy dwa wątki $A$ oraz $B$.

Wartości `counter` są niemonotoniczne, zatem rozpatrzymy przypadki(instrukcja `counter++` nie jest atomowa, więc w trakcie wyznaczania etykiety mogą się dziać różne rzeczy - np. pójście spać jednego z wątków):
$1^{\circ}$ $Label[A] \neq Label[B]$:
Skoro tak, to prawdą jest($\oplus$ - xor):
$$Label[A] < Label[B] \oplus Label[A] > Label[B]$$
Czyli dla jednego z wątków, warunek `while` będzie fałszem, czyli któryś wejdzie do $CS$.

$2^{\circ}$ $Label[A] = Label[B]$:
Skoro $A \neq B$, to prawdą jest:
$$(Label[A], A) <_{lex} (Label[B], B) \oplus (Label[A], A) >_{lex} (Label[B], B)$$
Czyli dla jednego z wątków, warunek `while` będzie fałszem, czyli któryś wejdzie do $CS$.

#### c)

Skoro miałoby dojść do zagłodzenia, to cały czas musiałaby istnieć etykieta, która jest mniejsza od nas.

Zauważmy, że aby `counter` uległ zmniejszeniu, to jakiś wątek musiałby wczytać jego wartość i pójść spać, a następnie po wybudzeniu się zwiększyć starą wartość o 1.

Jeśli nasz wątek $A$, czeka w pętli `while` na wejście do $CS$, to jego etykieta jest ustalona.

Jeśli istnieją wątki o mniejszych labelach, które mają obecnie pierwszeństwo wejścia do $CS$ ze względu na mniejszą etykietę, to nawet jeśli naprzemiennie wchodzą do $CS$ i zwiększają swoją etykietę i istnieje taki wątek, który śpi i trzyma małą wartość countera $c$, to po wybudzeniu ów wątku counter otrzyma wartość $c+1$, jeśli teraz następny wątek wczyta wartość countera $c+1$ i pójdzie spać, to ta wartość jest nową najmniejszą wartością i pozostałe działające wątki nigdy nie wczytają już wartości mniejszej niż $c+1$, stąd skoro różnica $d=Label[A] - MIN_{t \neq A}(Label[t])$ jest skończona, to wreszcie wątek $A$ wejdzie do sekcji krytycznej(po $d$ powrotach przez inne wątki do najmniejszej wartości).

Czyli niezagłodzenie zachodzi.