# Ćwiczenia 1, grupa śr. 16-18, 19 października 2022

###### tags: `PRW22` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | x | x | x | x | | | | |
Marcin Dąbrowski | | | | | | | | |
Jakub Gałecki | | | | | | | | |
Kamila Goszcz | x | x | x | x | x | x | |==x== |
Wiktor Hamberger | x | x | x | x | x | x | | x |
Jan Jankowicz | | X | X | X | | | | |
Mikołaj Jaszcza | ==X== | X | X | X | X | X | | X |
Zuzanna Kania | X | X | X | X | X | | | |
Wiktoria Kuna | X | | | X | X | X | | |
Patryk Mazur | X | X | X | X |==X==| X | | |
Hubert Obrzut | X | X | X | X | X | X | X | X |
Magdalena Rzepka | X | X | X | X | X |==X==| X | X |
Joanna Stachowicz | x | x |==x==| x | x | x | | |
Rafał Starypan | X | X | X | X | X | X | | |
Maria Szlasa | X | X | X |==X==| X | X | | X |
Daniel Wiczołek | X | 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: Mikołaj Jaszcza
:::

Rozważamy układ dwóch procesorów o jak najmniejszej (łącznej) mocy takich, aby wykonały dane zadanie w łącznym czasie równym pewnemu danemu mocniejszemu procesorowi.

Skoro algorytm da się zrównoleglić uzyskując dwukrotne przyspieszenie - nasz problem redukuje się do znalezienia takich parametrów procesora, aby działał 2 razy wolniej niż procesor "wzorcowy", a jednocześnie jego konstrukcja zużywała jak najmniej mocy.

Mamy więc moc procesora "wzorcowego":
$$ P = CV^2 * f_1 $$, czyli - za treścią zadania - możemy to przedstawić jako:
$$ P = cn_1 * \alpha^2 * f_1^2 * f_1 $$

gdzie $$n$$ jest liczbą tranzystorów, a $$ V $$ możemy oznaczyć jako $$\alpha* f$$
Oznaczmy czas, potrzebny mu na wykonanie zadania jako $$t_1$$ zgodnie z treścią zadania.

Upraszaczjąc:
$$ P = cn_1 * \alpha^2 * f_1^3 $$

Rozważmy procesor, który ma 2 razy więcej tranzystorów (tj. ma 2 rdzenie), tj: $$n_2 = n_1 * 2$$. Zmniejszmy jednak częstotliwość procesora w taki sposób, że
$$f_2 = f_1 * \frac{1}{2}$$. Zauważmy, że łącznie, mamy teraz 2 jednostki o 2 razy mniejszej częstotliwości niż bazowa - a skoro algorytm można było "zrównoleglić" - to czas działania wynosi $$t_2 = 2*t_1 * \frac{1}{2}$$. Zauważmy jednak, że uzyskaliśmy procesor zużywający mniej mocy, poniewać:
$$P_2 = cn_2 * \alpha^2 * f_2^3 $$, a korzystając z zależności opisanych wyżej mamy:
$$P_2 = c(2*n_1) * \alpha^2 * (\frac{1}{2} * f_1)^3 = 2 *\frac{1}{8} * cn_1 * \alpha^2 * f_1^3 = \frac{1}{4} * P_1 $$.

Zatem mając do dyspozycji 2 rdzenie o 2 razy mniejszej częstotliwości możemy uzyskać taki sam czas wykonania programu, jednocześnie pobierając 4 razy mniej mocy.

## Zadanie 2
:::success
Autor: Rafał Starypan
:::

Problem sekcji krytycznej - dwa wątki korzystają z jakiegoś wspólnego zasobu, np. z jeziora, podczas gdy w danym momencie tylko jeden proces może z niego korzystać.

Rozwiązanie z głodzeniem Boba:

Alicja:
1. Podnieś flagę
2. Poczekaj aż flaga Boba będzie obniżona
3. Wypuść smoka
4. Poczekaj aż smok wróci i opuść flagę

Bob:
1. Podnieś flagę
2. Dopóki flaga alicji jest w górze
2.1 Obniż flagę
2.2 Poczekaj aż jej flaga opadnie
2.3 Podnieś flagę
3. Wypuść smoka
4. Poczekaj aż smok wróci i opuść flagę

Ulepszone rozwiązanie:
Alicja:
1. Podnieś flagę
2. Dopóki flaga Boba jest w górze
2.1. Jeśli napis wskazuje Bob:
2.1.1 Obniż flagę
2.1.2 Czekaj aż napis wskaże Alicja
2.1.3 Podnieś flagę
3. Wypuść smoka
4. Poczekaj aż smok wróci
5. Ustaw napis na Bob
6. Obniż flagę

Bob:
1. Podnieś flagę
2. Dopóki flaga Alicji jest w górze:
2.1 Jeśli napis wskazuje Alicja:
2.1.1 Obniż flagę
2.1.2 Poczekaj aż napis wskaże Bob
2.1.3 Podnieś flagę
3. Wypuść smoka
4. Poczekaj aż smok wróci
5. Ustaw napis na alicja
6. Opuść flagę

Zagłodzenie

Załóżmy nie wprost, że doszło do zagłodzenia, czyli jeden ze smoków nigdy nie wejdzie do jeziora (niech będzie to smok Boba). Skoro Bob chce wpuścić smoka, a nie może, to znaczy, że ma obniżoną flagę i czeka aż napis wskaże jego imię. Smok Alicji wracając ustawi napis na "Bob", co prowadzi do sprzeczności.

Wzajemne wykluczanie

Załóżmy nie wprost, że w jeziorze znalazły się 2 smoki jednocześnie. Wtedy Alicja i Bob mają podniesione flagi. Bob wpuszcza smoka. Jeśli Alicja również wpuściła smoka, to odeszła od algorytmu, gdyż napis nie wskazywał jej imienia.

Zakleszczenie

Załóżmy nie wprost, że doszło do zakleszczenia, czyli zarówno Alicja jak i Bob chcą wpuścić smoka do jeziora, ale żadne z nich nie może tego zrobić. Napis wskazuje jedną z tych osób wpuszcza smoka do jeziora, a druga musi poczekać.

## Zadanie 3
:::success
Autor: Joanna Stachowicz
:::

## Zadanie 4
:::success
Autor: Maria Szlasa
:::


****

**własność żywotniści** - kiedyś stanie się coś pożądanego
brak żywotności to znaczy, że nastąpi np zakleszczenie

**własność bezpieczeństwa** - nigdy nic złego się nie stanie
brak bezpieczeństwa to znaczy, że dwie rzeczy będą w sekcji krytycznej

****

1. Klienci są obsługiwani zgodnie z kolejnością przybycia.
**własność bezpieczeństwa:** każdy z klientów zostanie osobno obsłużony i równo potraktowany
2. Co idzie do góry, musi zejść na dół.
**własność bezpieczeństwa:** to co weszło na górę, zejdzie na dół
3. Jeśli co najmniej dwa wątki oczekują na wejście do sekcji krytycznej, to przynajmniej jednemu to się udaje.
**własność żywotności:** chcemy, aby jednemu z wątków udało się wejść do sekcji krytycznej
4. Jeśli nastąpi przerwanie, to w ciągu sekundy drukowany jest komunikat.
**własność żywotności:** chcemy po sekundzie otrzymać komunikat
5. Jeśli nastąpi przerwanie, to drukowany jest komunikat.
**własność żywotności:** chcemy otrzymać wydrukowany komunikat
6. Koszt życia nigdy nie spada.
**własność bezpieczeństwa:** nie zdarzy się, że koszt życia spadnie
7. Dwie rzeczy są pewne: śmierć i podatki.
**własność żywotności:** śmierć
**własność bezpieczeństwa:** podatki
## Zadanie 5
:::success
Autor: Patryk Mazur
:::
:::spoiler Zadanie 5.
:::

**Strategia uwolnienia się (Gdy przełącznik jest poczatkowo wyłączony):**

Jeden z więźniów będzie licznikiem, on będzie odpowiedzialny za zliczanie więźniów oraz za oświadczenie, że każdy więzień był w pokoju przynajmniej raz.

Zakładamy, że licznik pamięta, ilu więźniów jest ogółem.

Strategia polega na tym, że każdy więzień, który wchodzi po raz pierwszy do pokoju ze zgaszonym przełącznikiem, zapala go i zapamiętuje to.
Jeżeli więzień wchodzi do pokoju z zapalonym przełącznikiem, nic nie robi. A jeżeli więzień, który już kiedyś zapalił przełącznik, wejdzie do pokoju ze zgaszonym to też nic nie robi.

Gdy licznik wchodzi do pokoju z zapalonym przełącznikiem, dodaje w głowie 1, oraz gasi przełącznik.

Przez to, że każdy pamięta o swoim "zapaleniu", mamy pewność, że nikt nie zapali przełącznika więcej niż raz.

Niech n będzie liczbą więźniów (bez licznika).
Jeżeli licznik doliczy do n to ma pewność, że każdy był w pokoju przynajmniej raz.

## Zadanie 6
:::success
Autor: Magdalena Rzepka
:::

**Jest n więźniów i my.**
My jesteśmy licznikiem (zaczynamy liczyć od 0).

Nasza strategia(licznika):
-**przycisk jest włączony - dodaj 1 do licznika i wyłącz przycisk.**
-przycisk jest wyłączony - nic nie rób.
-**gdy doliczymy do 2n to możemy wyjść z więzienia.**

Strategia więźniów:
-przycisk jest włączony - nic nie rób.
-**przycisk jest wyłączony - włącz, ale tylko 2 razy możesz to zrobić.**

Gdy licznik wynosi 2n to:
-przycisk był początkowo wyłączony i każdy więzień włączył go 2 razy.
-przycisk był początkowo włączony i każdy więzień włączył go 2 razy oprócz jednego, który włączył go tylko jeden raz.

Gdyby jedna osoba nigdy nie weszła to byłoby maksymalnie (n-1) * 2 + 1 = 2n - 2 + 1 = 2n - 1 < 2n
Więc mamy pewność, że każdy więzień był przynajmniej raz.

## Zadanie 7
:::success
Autor: Hubert Obrzut
:::


## Zadanie 8
:::success
Autor: Kamila Goszcz
:::

Żeby doszło do deadlocka każdy z filozofów musi mieć dokładnie po 1 widelcu.

Wystarczy, że jeden z filozofów będzie brał jako pierwszy prawy widelec wtedy (załóżmy, że to będzie 1):

| 1 | 2 |

Wtedy jeżeli 2 weźmie jeden widelec to 1 nie będzie mógł wziąć żadnego a zatem nigdy ie będzie sytuacji, że każdy z filozofów będzie miał dokładnie jeden widelec.

public class Main {
    static final int N = 5;
    public static void main(String[] args) throws InterruptedException {
        System.out.println("Starting...");
        Fork forks[] = new Fork[N];
        Philosopher philos[] = new Philosopher[N];
        for (int i = 0; i < N; i++)
            forks[i] = new Fork(i);
        Philosopher p;
        for (int i = 0; i < N; i++) {
            p = new Philosopher(i,
                    forks[i],
                    forks[(i + 1) % N]);
            philos[i] = p;
            p.start();
        }
        for (int i = 0; i < N; i++) {
            System.out.printf("Waiting for philosopher %d to finish\n", i);
            philos[i].join();
        }
    }
}

class Fork {
    boolean taken;
    int id ;
    public Fork(int myID) {
        id = myID;
    }
    public synchronized void get() throws InterruptedException {
        while (taken) {
            wait ();
        }
        taken = true;
    }
    public synchronized void put() {
        taken = false;
        notify ();
    }
}

import java.util.Random;

class Philosopher extends Thread {
    int id;
    Fork left;
    Fork right;
    public Philosopher(int myID, Fork myLeft, Fork myRight) {
        id = myID;
        left = myLeft;
        right = myRight;
    }
    public void run() {
        Random random = new Random();
        while (true) {
            try {
                sleep(random.nextInt(1000));
                sleep(100);
                System.out.println("Philosopher " + id + " is hungry");
                if (id == 0){
                    left.get();
                    right.get();
                } else {
                    right.get();
                    left.get();
                }
                left.put();
                right.put();
            } catch (InterruptedException ex) {
                return;
            }
        }
    }
}