---
# System prepended metadata

title: 'Ćwiczenia 1, grupa cz. 16-18, 12 października 2023'
tags: [pwit, ćwiczenia, PRW23]

---

# Ć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	
:::

![](https://hackmd.io/_uploads/S1xLbZKB-T.png)

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	
:::
![](https://hackmd.io/_uploads/SJE_r8gb6.png)
![](https://hackmd.io/_uploads/B1ZsS8gZT.png)

**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	
:::
![](https://hackmd.io/_uploads/SkxYZKSba.png)
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ń	
:::
![](https://hackmd.io/_uploads/SJeNNH-Za.png)

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	
:::
![](https://hackmd.io/_uploads/r1tQTzlWT.png)

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


![](https://hackmd.io/_uploads/r1aPZYHZ6.png)

![](https://hackmd.io/_uploads/ByNsfYB-a.png)


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

```java=
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.

```java=
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).