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

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

## Zadanie 1
:::success
Autor:Martyna Wybraniec
:::


Moc zużywana przez pracujący procesor:
$$P = CV^2*f$$
Wiemy, że algorytm wykonywany na dwóch rdzeniach wykona się dwa razy szybciej, niż gdyby wykonany został na jednym rdzeniu z taką samą częstotliwością. Chcemy natomiast, aby czas wykonania algorytmu pozostał taki sam. Możemy to uzyskać zmniejszając dwukrotnie częstotliwość: $$t_2 = 2 * t_1 * \frac{1}{2} = t_1$$

Korzystając z liniowej zależności podanej w zadaniu: $$C = a * n \text{ gdzie } a \text{ to stała, a } n \text{ to liczba tranzystorów.}$$ $$V = b * f \text{ gdzie } b \text{ to stała, a } f \text{ to częstotliwość.}$$
Zatem:
$$P = CV^2*f = a * n * b^2 * f^3$$

Możemy teraz porównać moc obydwóch procesorów:
$$
P_2 = a * n_2 * b^2 * f_2^3 = a * 2 * n_1 * b^2*(\frac{1}{2}*f_1)^3=\\
a * 2 *n_1*b^2*\frac{1}{8}*f_1^3 = \frac{1}{4}*a*n_1*b^2*f_1^3 = \frac{1}{4}P_1
$$
Pokazaliśmy, że jest możliwość zaprojektowania procesora o takim samym czasie wykonania, ale zużywającego znacznie mniej mocy.

## Zadanie 2
:::success
Autor:Adam Korta
:::

**Problem sekcji krytycznej** - dwa wątki korzystają ze wspólnego zasobu, np. tak jak w tym przypadku - jeziora, podczas gdy w danym momencie tylko jeden proces może z niego korzystać.

:::spoiler Poprawiona wersja
Alicja:
1. Podnieś flagę
2. Dopóki flaga Boba jest w górze
1. Jeśli napis wskazuje Bob:
1. Obniż flagę
2. Czekaj aż napis wskaże Alicja
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:
1. Jeśli napis wskazuje Alicja:
1. Obniż flagę
2. Poczekaj aż napis wskaże Bob
3. Podnieś flagę
3. Wypuść smoka
4. Poczekaj aż smok wróci
5. Ustaw napis na Alicja
6. Opuść flagę
:::
## Zadanie 3
:::success
Autor:Tomasz Stachurski
:::

Problem **producenta-konsumenta** polega na tym, że konsument nie może zastać pustych półek, a producent nie może uzupełnić półek dopóki nie będą puste.

Po informatycznemu (bufor to sekcja krytyczna):
* Producent wkłada dane do bufora (dostarcza i zapisuje)
* Konsument zabiera dane z bufora (pobiera i przetwarza)

Ulepszona wersja z puszką dla każdego:

Alicja:
1. Czeka, aż Bob strąci jej puszkę
2. Wpuszcza zwierzaki do jeziora
3. Gdy wrócą sprawdza stan jeziora. Jeśli jest puste to ustawia swoją puszkę z powrotem i ciągnie za sznurek strącając puszkę Boba

Bob:
1. Czeka, aż Alicja strąci jego puszkę
2. Dokłada jedzenie do jeziora
3. Ustawia swoją puszkę z powrotem i ciągnie za sznurek strącając puszke Alicji

## Zadanie 4
:::success
Autor:Volha Tsekalo
:::
1.Bezpieczeństwa(źle - kilka osób na raz/ poza kolejnością)
2.Żywotności(pożadane - obiektu wróci na dół)
3.Żywotności(pożądane - wejście do sekcji)
4.Bezpieczeństwa(źle - brak komunikatu po sekundzie)
5.Żywotności(pożadanym jest komunikat)
6.Bezpieczeństwa(spadek kosztu życia nigdy się nie wydarzy)
7.Żywotności(pożądanymi rzeczami są śmierć i podatki)

## Zadanie 5
:::success
Autor:Aleksandra Nicpoń
:::

Nową strategią będzie nadanie więzniom roli. Jeden z więźniów będzie spamiętywał ile więźniów (załóżmy że jest ich n) weszło do przełączalni. Niech to będzie więzień X.
Na początku przełącznik jest wyłączony.
Mamy dwa przypadki:
**Przełącznik jest wyłączony**
- X nic nie robi

**Przełącznik jest włączony**
- X dodaje 1 do liczby więzniów które weszły do przełączalni.

Pozostali więzniowie po wejściu do przełączalni jeżeli zobaczą, że **przełącznik jest włączony**:
- nic nie robią

Natomiast jeżeli **przełącznik jest wyłączony**:
- włączają przełącznik, jeżeli nigdy wcześniej go nie włączyli

Jeżeli X doliczy się do N-1 więźniów którzy weszli do przełączalni to znaczy że każdy z nich oprócz X musiał włączyć raz przełącznik (nie mogą włączyć go kilkukrotnie).

## Zadanie 6
:::success
Autor:Arti Brzozowski
:::

Przywódca:
- Wyłącza przycisk i liczy go jeżeli przycisk był włączony
- Jeżeli przycisk był włączony to nic nie robi
- Jeżeli zliczył 2n-2 Powinien ogłosić, że wszyscy odwiedzili pokój

Więzień:
- Włącza przycisk jeżeli był wyłączony i nie włączał jeszcze przycisku 2 razy
- nic nie robi jeżeli przycisk był włączony

## Zadanie 7
:::success
Autor:Bartosz Morasz
:::



1.
$$
m = 0,4
$$

$$
p' = 1 - m = 0.6
$$

$$
lim_{n->\infty}s(n) = lim_{n->\infty}{1 \over 1-p' + {p' \over n}} = {1 \over 1-p'} = {1 \over 1-0,6} = 2.5
$$

2.

$$
m = 0,3
$$

$$
m = 1 - p''
$$

$$
{m \over x} = {1 - p'' \over x}
$$

$$
lim_{n->\infty}s'(n) = lim_{n->\infty}{1 \over {1-p'' \over x} + {p'' \over n}} = {x \over 1-p''} = {10 \over 3} x
$$

$$
lim_{n->\infty}s'(n) = 2*lim_{n->\infty}s(n)
$$

$$
{10 \over 3}x = 5
$$

$$
x = 1.5
$$

3.

$$
m = 1 - p''
$$

$$
{m \over 3} = {1 - p'' \over 3}
$$

$$
lim_{n->\infty}s'(n) = lim_{n->\infty}{1 \over {1-p'' \over 3} + {p'' \over n}} = {3 \over 1-p''} = {3 \over m}
$$

$$
lim_{n->\infty}s'(n) = 2*lim_{n->\infty}s(n)
$$

$$
{3 \over m} = 5
$$

$$
m = 0.6
$$

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

public void run() {
        Random random = new Random();
        while (true) {
            try {
                sleep(random.nextInt(1000));
                sleep(100);
                System.out.println("Philosopher " + id + " is hungry");
                left.get();
                right.get();
                left.put();
                right.put();
            } catch (InterruptedException ex) {
                return;
            }
        }
    }

Każdy filozof najpierw sięga po lewy widelec, a dopiero później po prawy. Ponieważ mamy N filozofów i N widelców to zakleszczenie nastąpi w sytuacji, kiedy każdy filozof weźmie do ręki lewy widelec, wtedy nie doczeka się on aż prawy kolega odłoży swój widelec.

Filozofowie biorą najpierw widelec z mniejszym indeksem, a dopiero potem z większym. Odkładają je odwrotnie najpierw większy, a dopiero potem mniejszy.

public void run() {
        Random random = new Random();
        while (true) {
            try {
                sleep(random.nextInt(1000));
                sleep(100);
                System.out.println("Philosopher " + id + " is hungry");
                if (left.id < right.id){
                    left.get();
                    right.get();
                    right.put();
                    left.put();
                }
                else {
                    right.get();
                    left.get();
                    left.put();
                    right.put();
                }
            } catch (InterruptedException ex) {
                return;
            }
        }
    }

Zakleszczenie teraz nie nastąpi, ponieważ N filozof zamiast lewego widelca będzie chciał wziąć prawy(ma mniejszy priorytet) zatem będzie on na niego czekał, dzięki temu N-1 filozof będzie miał dostępny prawy widelec. Kiedy skońcy on jedzenie odłoży najpierw prawy (N filozof wciąż czeka na prawy widelec), a potem lewy, który weźmie N-2 filozof (jego prawy widelec).